Ignore:
Timestamp:
Jan 29, 2016, 3:38:47 PM (4 years ago)
Author:
nmedfort
Message:

Incorporated a few common case boolean optimizations in the Simplifier.

File:
1 edited

Legend:

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

    r4919 r4922  
    77#include <boost/container/flat_set.hpp>
    88
     9#include <pablo/printer_pablos.h>
     10#include <iostream>
     11
    912namespace pablo {
    1013
     
    1215using SmallSet = boost::container::flat_set<Type>;
    1316
    14 /** ------------------------------------------------------------------------------------------------------------- *
    15  * @brief optimize
    16  ** ------------------------------------------------------------------------------------------------------------- */
    17 bool Simplifier::optimize(PabloFunction & function) {
    18     // negationsShouldImmediatelySucceedTheirLiteral(function.getEntryBlock());
    19     #ifndef NDEBUG
    20     PabloVerifier::verify(function, "post-negation-must-immediately-succeed-their-literal");
    21     #endif
    22     eliminateRedundantCode(function.getEntryBlock());
    23     #ifndef NDEBUG
    24     PabloVerifier::verify(function, "post-eliminate-redundant-code");
    25     #endif
    26     deadCodeElimination(function.getEntryBlock());
    27     #ifndef NDEBUG
    28     PabloVerifier::verify(function, "post-dead-code-elimination");
    29     #endif
    30     strengthReduction(function.getEntryBlock());
    31     #ifndef NDEBUG
    32     PabloVerifier::verify(function, "post-strength-reduction");
    33     #endif
    34     return true;
    35 }
    36 
    37 /** ------------------------------------------------------------------------------------------------------------- *
    38  * @brief isReassociative
    39  ** ------------------------------------------------------------------------------------------------------------- */
    40 inline bool isReassociative(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 }
     17using TypeId = PabloAST::ClassTypeId;
    4918
    5019/** ------------------------------------------------------------------------------------------------------------- *
    5120 * @brief fold
    52  ** ------------------------------------------------------------------------------------------------------------- */
    53 inline PabloAST * Simplifier::fold(Variadic * const var, PabloBlock * const block) {
     21 *
     22 * Note: if folding alters this variadic without making any other modification to the AST, it will return null as
     23 * if no change was made.
     24 ** ------------------------------------------------------------------------------------------------------------- */
     25PabloAST * Simplifier::fold(Variadic * var, PabloBlock * const block) {
    5426
    5527    assert (var);
     
    6840    // Ensure all operands of a reassociatiable function are consistently ordered.
    6941    std::sort(var->begin(), var->end());
    70 
    7142    // Apply the idempotence law to any And and Or statement and the identity law to any Xor
    72     for (unsigned i = 1; i < var->getNumOperands(); ) {
    73         if (var->getOperand(i - 1) == var->getOperand(i)) {
     43    for (int i = var->getNumOperands() - 1; i > 0; --i) {
     44        if (LLVM_UNLIKELY(var->getOperand(i) == var->getOperand(i - 1))) {
    7445            var->removeOperand(i);
    7546            if (LLVM_UNLIKELY(isa<Xor>(var))) {
    76                 var->removeOperand(i - 1);
    77             }
     47                var->removeOperand(--i);
     48            }
     49        }
     50    }
     51
     52    // Apply the annihilator and identity laws
     53    for (unsigned i = 0; i != var->getNumOperands(); ) {
     54        if (LLVM_UNLIKELY(isa<Zeroes>(var->getOperand(i)))) {
     55            if (LLVM_UNLIKELY(isa<And>(var))) {
     56                return PabloBlock::createZeroes();
     57            }
     58            var->removeOperand(i);
    7859            continue;
     60        } else if (LLVM_UNLIKELY(isa<Ones>(var->getOperand(i)))) {
     61            if (LLVM_UNLIKELY(isa<Or>(var))) {
     62                return PabloBlock::createOnes();
     63            } else if (LLVM_UNLIKELY(isa<Xor>(var))) {
     64                negated = !negated;
     65            }
     66            var->removeOperand(i);
     67            continue;
    7968        }
    8069        ++i;
    8170    }
    8271
    83     if (LLVM_LIKELY(!isa<Xor>(var))) {
     72    PabloAST * replacement = nullptr;
     73
     74    if (LLVM_LIKELY(isa<And>(var) || isa<Or>(var))) {
     75        // Apply an implicit distribution + identity law whenever possible
     76        //    (P ∧ Q) √ (P ∧ ¬Q) = P √ (Q ∧ ¬Q) ⇔ (P √ Q) ∧ (P √ ¬Q) = P ∧ (Q √ ¬Q) ⇔ P
     77        bool modified = false;
     78        const TypeId typeId = isa<And>(var) ? TypeId::Or : TypeId::And;
     79        for (unsigned i = 1; i < var->getNumOperands(); ++i) {
     80            if (var->getOperand(i)->getClassTypeId() == typeId) {
     81                Variadic * const op_i = cast<Variadic>(var->getOperand(i));
     82                assert (std::is_sorted(op_i->begin(), op_i->end()));
     83                for (unsigned j = 0; j < i; ++j) {
     84                    if (var->getOperand(j)->getClassTypeId() == typeId) {
     85                        Variadic * const op_j = cast<Variadic>(var->getOperand(j));
     86                        assert (std::is_sorted(op_j->begin(), op_j->end()));
     87                        if (op_i->getNumOperands() == op_j->getNumOperands()) {
     88                            // If vi and vj differ by precisely one operand each, say di and dj, and di ⇔ ¬dj, then
     89                            // we can apply this rule.
     90                            unsigned vi = 0, vj = 0;
     91                            const unsigned operands = op_i->getNumOperands();
     92                            unsigned di = operands - 1, dj = operands - 1;
     93                            bool differsByOne = true;
     94                            while (vi < operands && vj < operands) {
     95                                if (op_i->getOperand(vi) < op_j->getOperand(vj)) {
     96                                    if (LLVM_UNLIKELY(di != (operands - 1))) { // <- we want the branch predictor to fail only once
     97                                        differsByOne = false;
     98                                        break;
     99                                    }
     100                                    di = vi++;
     101                                } else if (op_j->getOperand(vj) < op_i->getOperand(vi)) {
     102                                    if (LLVM_UNLIKELY(dj != (operands - 1))) {
     103                                        differsByOne = false;
     104                                        break;
     105                                    }
     106                                    dj = vj++;
     107                                } else {
     108                                    ++vi;
     109                                    ++vj;
     110                                }
     111                            }
     112                            if (LLVM_UNLIKELY(differsByOne)) {
     113                                assert (di < operands && dj < operands);
     114                                assert ("Found an equivalent set of operations that was not deduced earlier!" && !equals(op_i, op_j));
     115                                bool apply = false;
     116                                if (isa<Not>(op_i->getOperand(di))) {
     117                                    apply = equals(cast<Not>(op_i->getOperand(di))->getOperand(0), op_j->getOperand(dj));
     118                                } else if (isa<Not>(op_j->getOperand(dj))) {
     119                                    apply = equals(cast<Not>(op_j->getOperand(dj))->getOperand(0), op_i->getOperand(di));
     120                                }
     121                                if (LLVM_UNLIKELY(apply)) {
     122                                    // Although we can apply this rule, we have a potential problem. If P is not a "literal", we cannot modify
     123                                    // var without creating a new And or Or statement. This however may mean that the "redundancyElimination"
     124                                    // pass could miss a statement if its not added after this statement.
     125                                    PabloAST * expr = nullptr;
     126                                    if (operands == 2) {
     127                                        expr = op_i->getOperand(1 ^ di);
     128                                        if (LLVM_LIKELY(var->getNumOperands() == 2)) {
     129                                            return expr;
     130                                        }
     131                                    } else { // if (operands > 2) {
     132                                        assert (operands > 2);
     133                                        block->setInsertPoint(var->getPrevNode());
     134                                        Variadic * nested = nullptr;
     135                                        if (typeId == TypeId::And) {
     136                                            nested = block->createAnd(operands - 1);
     137                                        } else { // if (typeId == TypeId::Or) {
     138                                            nested = block->createOr(operands - 1);
     139                                        }
     140                                        for (unsigned k = 0; k != di; ++k) {
     141                                            nested->addOperand(op_i->getOperand(k));
     142                                        }
     143                                        for (unsigned k = di + 1; k < operands; ++k) {
     144                                            nested->addOperand(op_i->getOperand(k));
     145                                        }
     146                                        expr = nested;
     147                                        replacement = var;
     148                                    }
     149                                    var->setOperand(j, expr);
     150                                    var->removeOperand(i);
     151                                    i = 0;
     152                                    modified = true;
     153                                    break;
     154                                }
     155                            }
     156                        }
     157                    }
     158                }
     159            }
     160        }
     161
     162        // Apply the absorption law whenever possible
     163        //   P √ (P ∧ Q) ⇔ P ∧ (P √ Q) ⇔ P
     164        for (unsigned i = 1; i < var->getNumOperands(); ++i) {
     165            PabloAST * const op = var->getOperand(i);
     166            if (op->getClassTypeId() == typeId) {
     167                Variadic * const vi = cast<Variadic>(op);
     168                assert (std::is_sorted(vi->begin(), vi->end()));
     169                for (unsigned j = 0; j < i; ++j) {
     170                    assert (var->getOperand(i) == vi);
     171                    if (var->getOperand(j)->getClassTypeId() == typeId) {
     172                        Variadic * const vj = cast<Variadic>(var->getOperand(j));
     173                        assert (std::is_sorted(vj->begin(), vj->end()));
     174                        if (vi->getNumOperands() < vj->getNumOperands()) {
     175                            if (LLVM_UNLIKELY(std::includes(vi->begin(), vi->end(), vj->begin(), vj->end()))) {
     176                                var->removeOperand(i--);
     177                                break;
     178                            }
     179                        } else { // if (vi->getNumOperands() >= vj->getNumOperands()) {
     180                            if (LLVM_UNLIKELY(std::includes(vj->begin(), vj->end(), vi->begin(), vi->end()))) {
     181                                var->removeOperand(j--); i--;
     182                            }
     183                        }
     184                    }
     185                }
     186            } else { // treat the operand as a literal
     187                for (unsigned j = 0; j < var->getNumOperands(); ) {
     188                    if (var->getOperand(j)->getClassTypeId() == typeId) {
     189                        Variadic * const vj = cast<Variadic>(var->getOperand(j));
     190                        assert (std::is_sorted(vj->begin(), vj->end()));
     191                        if (LLVM_UNLIKELY(std::binary_search(vj->begin(), vj->end(), op))) {
     192                            var->removeOperand(j);
     193                            continue;
     194                        }
     195                    }
     196                    ++j;
     197                }
     198            }
     199        }
     200
    84201        // Apply the complementation law whenever possible.
    85202        for (unsigned i = 0; i < var->getNumOperands(); ++i) {
    86203            if (isa<Not>(var->getOperand(i))) {
    87                 const PabloAST * const negatedOp = cast<Not>(var->getOperand(i))->getOperand(0);
     204                const PabloAST * const negated = cast<Not>(var->getOperand(i))->getOperand(0);
    88205                for (unsigned j = 0; j != var->getNumOperands(); ++j) {
    89                     if (LLVM_UNLIKELY(equals(var->getOperand(j), negatedOp))) {
    90                         if (isa<And>(var)) { // (A ∧ ¬A) ∧ B = 0 for any B
     206                    if (LLVM_UNLIKELY(var->getOperand(j) == negated)) {
     207                        if (isa<And>(var)) { // (A ∧ ¬A) ∧ B ⇔ 0 for any B
    91208                            return PabloBlock::createZeroes();
    92                         } else if (isa<Or>(var)) { // (A √ ¬A) √ B = 1 for any B
     209                        } else { // if (isa<Or>(var)) { // (A √ ¬A) √ B ⇔ 1 for any B
    93210                            return PabloBlock::createOnes();
    94211                        }
     
    97214            }
    98215        }
    99     }
    100 
    101     // Apply the annihilator and identity laws
    102     for (unsigned i = 0; i != var->getNumOperands(); ) {
    103         if (LLVM_UNLIKELY(isa<Zeroes>(var->getOperand(i)))) {
    104             if (isa<And>(var)) {
    105                 return PabloBlock::createZeroes();
    106             }
    107             var->removeOperand(i);
    108             continue;
    109         } else if (LLVM_UNLIKELY(isa<Ones>(var->getOperand(i)))) {
    110             if (isa<Or>(var)) {
    111                 return PabloBlock::createOnes();
    112             } else if (isa<Xor>(var)) {
    113                 negated = !negated;
    114             }
    115             var->removeOperand(i);
    116             continue;
    117         }
    118         ++i;
    119     }
    120 
    121     PabloAST * replacement = nullptr;
     216
     217        if (LLVM_UNLIKELY(modified)) {
     218            // Ensure all operands of a reassociatiable function are consistently ordered.
     219            std::sort(var->begin(), var->end());
     220            // Apply the idempotence law to any And and Or statement
     221            for (int i = var->getNumOperands() - 1; i > 0; --i) {
     222                if (LLVM_UNLIKELY(var->getOperand(i) == var->getOperand(i - 1))) {
     223                    var->removeOperand(i);
     224                }
     225            }
     226        }
     227
     228    } // end of if (LLVM_LIKELY(isa<And>(var) || isa<Or>(var)))
     229
    122230    if (LLVM_UNLIKELY(var->getNumOperands() < 2)) {
    123         replacement = (var->getNumOperands() == 0) ? PabloBlock::createZeroes() : var->getOperand(0);
     231        if (LLVM_UNLIKELY(var->getNumOperands() == 0)) {
     232            return PabloBlock::createZeroes();
     233        }
     234        replacement = var->getOperand(0);
     235    }
     236    // If we marked this var as being a replacement for itself, then we must have manipulated some of its inner
     237    // operands in such a way that we had to generate new statements for it. Thus we need to generate a new "var"
     238    // so that the "redundancyElimination" pass doesn't miss one of its operands.
     239    if (LLVM_UNLIKELY(replacement == var)) {
     240        Variadic * replacementVar = nullptr;
     241        if (isa<And>(var)) {
     242            replacementVar = block->createAnd(var->getNumOperands());
     243        } else if (isa<Or>(var)) {
     244            replacementVar = block->createOr(var->getNumOperands());
     245        } else { // if (isa<Xor>(var)) {
     246            replacementVar = block->createXor(var->getNumOperands());
     247        }
     248        assert (std::is_sorted(var->begin(), var->end()));
     249        for (unsigned i = 0; i != var->getNumOperands(); ++i) {
     250            replacementVar->addOperand(var->getOperand(i));
     251        }
     252        replacement = replacementVar;
    124253    }
    125254    if (LLVM_UNLIKELY(negated)) {
     255        assert (isa<Xor>(var));
    126256        block->setInsertPoint(var);
    127257        replacement = block->createNot(replacement ? replacement : var);
    128258    }
     259    assert (replacement != var);
    129260    return replacement;
    130261}
     
    133264 * @brief fold
    134265 ** ------------------------------------------------------------------------------------------------------------- */
    135 inline PabloAST * Simplifier::fold(Statement * stmt, PabloBlock * block) {
    136     if (isReassociative(stmt)) {
     266inline PabloAST * Simplifier::fold(Statement * stmt, PabloBlock * const block) {
     267    if (isa<Variadic>(stmt)) {
    137268        return fold(cast<Variadic>(stmt), block);
    138269    } else if (isa<Not>(stmt)) {
    139270        PabloAST * value = stmt->getOperand(0);
    140271        if (LLVM_UNLIKELY(isa<Not>(value))) {
    141             return cast<Not>(value)->getOperand(0);
     272            return cast<Not>(value)->getOperand(0); // ¬¬A ⇔ A
    142273        } else if (LLVM_UNLIKELY(isa<Zeroes>(value))) {
    143             return block->createOnes();
     274            return PabloBlock::createOnes(); // ¬0 ⇔ 1
    144275        }  else if (LLVM_UNLIKELY(isa<Ones>(value))) {
    145             return block->createZeroes();
     276            return PabloBlock::createZeroes(); // ¬1 ⇔ 0
    146277        }
    147278    } else if (isa<Advance>(stmt)) {
    148279        if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(0)))) {
    149             return block->createZeroes();
     280            return PabloBlock::createZeroes();
    150281        }
    151282    } else {
     
    166297                }
    167298            } else if (LLVM_UNLIKELY(isa<Ones>(stmt->getOperand(i)))) {
    168                 block->setInsertPoint(stmt->getPrevNode());
    169299                switch (stmt->getClassTypeId()) {
    170300                    case PabloAST::ClassTypeId::Sel:
     
    176306                        }
    177307                    case PabloAST::ClassTypeId::ScanThru:
    178                         if (i == 1) {
    179                             return block->createZeroes();
     308                        if (LLVM_UNLIKELY(i == 1)) {
     309                            return PabloBlock::createZeroes();
    180310                        }
    181311                        break;
    182312                    case PabloAST::ClassTypeId::MatchStar:
    183                         if (i == 0) {
    184                             return block->createOnes();
     313                        if (LLVM_UNLIKELY(i == 0)) {
     314                            return PabloBlock::createOnes();
    185315                        }
    186316                        break;
     
    305435
    306436/** ------------------------------------------------------------------------------------------------------------- *
    307  * @brief eliminateRedundantCode
     437 * @brief redundancyElimination
    308438 *
    309439 * Note: Do not recursively delete statements in this function. The ExpressionTable could use deleted statements
    310440 * as replacements. Let the DCE remove the unnecessary statements with the finalized Def-Use information.
    311441 ** ------------------------------------------------------------------------------------------------------------- */
    312 void Simplifier::eliminateRedundantCode(PabloBlock * const block, ExpressionTable * predecessor) {
     442void Simplifier::redundancyElimination(PabloBlock * const block, ExpressionTable * predecessor) {
    313443    ExpressionTable encountered(predecessor);
    314444    Statement * stmt = block->front();
     
    320450            // the Assign's expression directly.
    321451            if (isSuperfluous(assign)) {
    322                 stmt = assign->replaceWith(assign->getExpression());               
     452                stmt = assign->replaceWith(assign->getExpression());
    323453                continue;
    324454            }
     
    345475
    346476            // Process the If body
    347             eliminateRedundantCode(cast<If>(stmt)->getBody(), &encountered);
     477            redundancyElimination(cast<If>(stmt)->getBody(), &encountered);
    348478
    349479            // If we ended up removing all of the defined variables, delete the If node.
     
    384514                continue;
    385515            }
    386             eliminateRedundantCode(whileNode->getBody(), &encountered);
     516            redundancyElimination(whileNode->getBody(), &encountered);
    387517            removeIdenticalEscapedValues(whileNode->getVariants());
    388518            // If the condition's Next state is Zero, we can eliminate the loop after copying the internal
    389519            // statements into the body.
    390520        } else {
    391             if (PabloAST * folded = fold(stmt, block)) {
    392                 // If we determine we can fold this statement,
    393                 Statement * const prior = stmt->getPrevNode();
     521            Statement * const prior = stmt->getPrevNode();
     522            PabloAST * const folded = fold(stmt, block);
     523            if (folded) {
     524                // If we determine we can fold this statement, go back to the original prior node of this statement.
     525                // New statements may have been inserted after it.
    394526                stmt->replaceWith(folded, true);
    395527                stmt = LLVM_LIKELY(prior != nullptr) ? prior->getNextNode() : block->front();
     
    468600        stmt = stmt->getNextNode();
    469601    }
    470     block->setInsertPoint(block->back());
    471 }
    472 
    473 /** ------------------------------------------------------------------------------------------------------------- *
    474  * @brief negationsShouldImmediatelySucceedTheirLiteral
    475  *
    476  * Assuming that most negations are actually replaced by an ANDC operations or that we only need a literal or its
    477  * negation, by pushing all negations up to immediately succeed the literal we should generate equally efficient
    478  * code whilst simplifying analysis.
    479  *
    480  * TODO: this theory needs evaluation.
    481  ** ------------------------------------------------------------------------------------------------------------- */
    482 void Simplifier::negationsShouldImmediatelySucceedTheirLiteral(PabloBlock * const block) {
    483     Statement * stmt = block->front();
    484     while (stmt) {
    485         Statement * next = stmt->getNextNode();
    486         if (isa<If>(stmt)) {
    487             negationsShouldImmediatelySucceedTheirLiteral(cast<If>(stmt)->getBody());
    488         } else if (isa<While>(stmt)) {
    489             negationsShouldImmediatelySucceedTheirLiteral(cast<While>(stmt)->getBody());
    490         } else if (isa<Not>(stmt)) {
    491             PabloAST * op = cast<Not>(stmt)->getExpr();
    492             if (LLVM_LIKELY(isa<Statement>(op))) {
    493                 PabloBlock * scope = cast<Statement>(op)->getParent();
    494                 // If the operand is not in a nested scope, we can move it.
    495                 for (;;) {
    496                     if (LLVM_UNLIKELY(scope == nullptr)) {
    497                         stmt->insertAfter(cast<Statement>(op));
    498                         break;
    499                     }
    500                     scope = scope->getParent();
    501                     if (LLVM_UNLIKELY(scope == block)) {
    502                         break;
    503                     }
    504                 }
    505             }
    506         }
    507         stmt = next;
    508     }
    509 }
    510 
    511 }
     602}
     603
     604/** ------------------------------------------------------------------------------------------------------------- *
     605 * @brief optimize
     606 ** ------------------------------------------------------------------------------------------------------------- */
     607bool Simplifier::optimize(PabloFunction & function) {
     608    redundancyElimination(function.getEntryBlock());
     609    #ifndef NDEBUG
     610    PabloVerifier::verify(function, "post-eliminate-redundant-code");
     611    #endif
     612    deadCodeElimination(function.getEntryBlock());
     613    #ifndef NDEBUG
     614    PabloVerifier::verify(function, "post-dead-code-elimination");
     615    #endif
     616    strengthReduction(function.getEntryBlock());
     617    #ifndef NDEBUG
     618    PabloVerifier::verify(function, "post-strength-reduction");
     619    #endif
     620    return true;
     621}
     622
     623}
Note: See TracChangeset for help on using the changeset viewer.