Ignore:
Timestamp:
Nov 19, 2015, 4:47:28 PM (4 years ago)
Author:
nmedfort
Message:

More work towards n-ary And/Or/Xor? functions.

Location:
icGREP/icgrep-devel/icgrep/pablo/optimizers
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4871 r4876  
    3636
    3737/** ------------------------------------------------------------------------------------------------------------- *
     38 * @brief isReassociatable
     39 ** ------------------------------------------------------------------------------------------------------------- */
     40inline bool isReassociatable(const Statement * const stmt) {
     41    switch (stmt->getClassTypeId()) {
     42        case PabloAST::ClassTypeId::And:
     43        case PabloAST::ClassTypeId::Or:
     44        case PabloAST::ClassTypeId::Xor:
     45            return true;
     46        default: return false;
     47    }
     48}
     49
     50/** ------------------------------------------------------------------------------------------------------------- *
     51 * @brief foldReassociativeFunction
     52 ** ------------------------------------------------------------------------------------------------------------- */
     53PabloAST * Simplifier::foldReassociativeFunction(Variadic * const var, PabloBlock * const block) {
     54
     55    assert (var);
     56
     57    // Ensure all operands of a reassociatiable function are consistently ordered.
     58    std::sort(var->begin(), var->end());
     59
     60    // Apply the idempotence law to any And and Or statement and the identity law to any Xor
     61    for (unsigned i = 1; i < var->getNumOperands(); ) {
     62        if (var->getOperand(i - 1) == var->getOperand(i)) {
     63            var->removeOperand(i);
     64            if (LLVM_UNLIKELY(isa<Xor>(var))) {
     65                var->removeOperand(i - 1);
     66                if (LLVM_UNLIKELY(var->getNumOperands() == 0)) {
     67                    return PabloBlock::createZeroes();
     68                }
     69            }
     70            continue;
     71        }
     72        ++i;
     73    }
     74
     75    // Apply the complementation law whenever possible.
     76    bool negated = false;
     77    for (unsigned i = 0; i < var->getNumOperands(); ++i) {
     78        if (isa<Not>(var->getOperand(i))) {
     79            PabloAST * const negatedOp = cast<Not>(var->getOperand(i))->getOperand(0);
     80            bool complementation = false;
     81            for (unsigned j = 0; j != var->getNumOperands(); ++j) {
     82                if (LLVM_UNLIKELY(var->getOperand(j) == negatedOp)) {
     83                    if (isa<And>(var)) { // (A ∧ ¬A) ∧ B = 0 for any B
     84                        return PabloBlock::createZeroes();
     85                    } else if (isa<Or>(var)) { // (A √ ¬A) √ B = 1 for any B
     86                        return PabloBlock::createOnes();
     87                    }
     88                    var->removeOperand(i); // (A ⊕ ¬A) ⊕ B = 1 ⊕ B = ¬B for any B
     89                    var->removeOperand(j);
     90                    negated = !negated;
     91                    complementation = true;
     92                    break;
     93                }
     94            }
     95            if (complementation) {
     96                continue;
     97            }
     98        }
     99        ++i;
     100    }
     101
     102    // Apply the annihilator and identity laws
     103    for (unsigned i = 0; i != var->getNumOperands(); ) {
     104        if (LLVM_UNLIKELY(isa<Zeroes>(var->getOperand(i)))) {
     105            if (isa<And>(var)) {
     106                return PabloBlock::createZeroes();
     107            }
     108            var->removeOperand(i);
     109            continue;
     110        } else if (LLVM_UNLIKELY(isa<Ones>(var->getOperand(i)))) {
     111            if (isa<Or>(var)) {
     112                return PabloBlock::createOnes();
     113            } else if (isa<Xor>(var)) {
     114                negated = !negated;
     115            }
     116            var->removeOperand(i);
     117            continue;
     118        }
     119        ++i;
     120    }
     121
     122    PabloAST * replacement = nullptr;
     123    if (LLVM_UNLIKELY(var->getNumOperands() < 2)) {
     124        replacement = (var->getNumOperands() == 0) ? PabloBlock::createZeroes() : var->getOperand(0);
     125    }
     126    if (LLVM_UNLIKELY(negated)) {
     127        block->setInsertPoint(var);
     128        if (replacement) {
     129            replacement = block->createNot(replacement);
     130        } else {
     131            var->replaceAllUsesWith(block->createNot(var));
     132        }
     133    }
     134    return replacement;
     135}
     136
     137/** ------------------------------------------------------------------------------------------------------------- *
    38138 * @brief canTriviallyFold
    39139 ** ------------------------------------------------------------------------------------------------------------- */
     
    42142        if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(i)))) {
    43143            switch (stmt->getClassTypeId()) {
    44                 case PabloAST::ClassTypeId::And:
    45144                case PabloAST::ClassTypeId::Advance:
    46145                    return block->createZeroes();
    47                 case PabloAST::ClassTypeId::Xor:
    48                 case PabloAST::ClassTypeId::Or:
    49                     return stmt->getOperand(1 - i);
    50146                case PabloAST::ClassTypeId::Not:
    51147                    return block->createOnes();
     
    65161            block->setInsertPoint(stmt->getPrevNode());
    66162            switch (stmt->getClassTypeId()) {
    67                 case PabloAST::ClassTypeId::And:
    68                     return stmt->getOperand(1 - i);
    69                 case PabloAST::ClassTypeId::Or:
    70                     return block->createOnes();
    71                 case PabloAST::ClassTypeId::Xor:
    72                     return block->createNot(stmt->getOperand(1 - i));
    73163                case PabloAST::ClassTypeId::Not:
    74164                    return block->createZeroes();
     
    240330            replaceReachableUsersOfWith(next, next->getExpr());
    241331        } else if (If * ifNode = dyn_cast<If>(stmt)) {
     332            // Test whether we can ever take this branch
     333            if (LLVM_UNLIKELY(isa<Zeroes>(cast<If>(stmt)->getCondition()))) {
     334                stmt = stmt->eraseFromParent();
     335                continue;
     336            }
    242337            // Test whether all of the defined variables are necessary
    243338            If::DefinedVars & defs = ifNode->getDefined();
     
    282377
    283378        } else if (While * whileNode = dyn_cast<While>(stmt)) {
     379            // Test whether we can ever take this branch
     380            const PabloAST * initial = cast<While>(stmt)->getCondition();
     381            if (LLVM_LIKELY(isa<Next>(initial))) {
     382                initial = cast<Next>(initial)->getInitial();
     383            }
     384            if (LLVM_UNLIKELY(isa<Zeroes>(initial))) {
     385                stmt = stmt->eraseFromParent();
     386                continue;
     387            }
    284388            eliminateRedundantCode(whileNode->getBody(), &encountered);
    285389            removeIdenticalEscapedValues(whileNode->getVariants());
    286390            // If the condition's Next state is Zero, we can eliminate the loop after copying the internal
    287391            // statements into the body.
    288 
    289 
    290         } else if (PabloAST * expr = canTriviallyFold(stmt, block)) {
    291             stmt = stmt->replaceWith(expr, true);
    292             continue;
    293392        } else {
     393            PabloAST * folded = nullptr;
     394            if (isReassociatable(stmt)) {
     395                folded =  foldReassociativeFunction(cast<Variadic>(stmt), block);
     396            } else {
     397                folded = canTriviallyFold(stmt, block);
     398            }
     399            if (folded) {
     400                // If we determine we can fold this statement,
     401                Statement * const prior = stmt->getPrevNode();
     402                stmt->replaceWith(folded, true);
     403                stmt = prior ? prior->getNextNode() : block->front();
     404                continue;
     405            }
    294406            // When we're creating the Pablo program, it's possible to have multiple instances of an "identical"
    295407            // statement. By recording which statements have already been seen, we can detect the redundant statements
     
    301413                continue;
    302414            }
     415
    303416        }
    304417        stmt = stmt->getNextNode();
     
    313426    while (stmt) {
    314427        if (isa<If>(stmt)) {
    315             if (LLVM_UNLIKELY(isa<Zeroes>(cast<If>(stmt)->getCondition()))) {
    316                 stmt = stmt->eraseFromParent();
    317                 continue;
    318             }
    319428            deadCodeElimination(cast<If>(stmt)->getBody());
    320429        } else if (isa<While>(stmt)) {
    321             const PabloAST * initial = cast<While>(stmt)->getCondition();
    322             if (LLVM_LIKELY(isa<Next>(initial))) {
    323                 initial = cast<Next>(initial)->getInitial();
    324             }
    325             if (LLVM_UNLIKELY(isa<Zeroes>(initial))) {
    326                 stmt = stmt->eraseFromParent();
    327                 continue;
    328             }
    329430            deadCodeElimination(cast<While>(stmt)->getBody());
    330431        } else if (stmt->getNumUses() == 0){
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.hpp

    r4871 r4876  
    1010
    1111class Simplifier {
     12    friend class FlattenAssociativeDFG;
    1213public:
    1314    static bool optimize(PabloFunction & function);
     
    1617private:
    1718    static void eliminateRedundantCode(PabloBlock * const block, ExpressionTable * predecessor = nullptr);
     19    static PabloAST * foldReassociativeFunction(Variadic * const var, PabloBlock * const block);
    1820    static void deadCodeElimination(PabloBlock * const block);
    1921    static void eliminateRedundantEquations(PabloBlock * const block);
Note: See TracChangeset for help on using the changeset viewer.