Ignore:
Timestamp:
Feb 2, 2016, 4:02:08 PM (4 years ago)
Author:
nmedfort
Message:

Slight optimization for Simplifier; major change to CarryManager? to build summary variables whenever a carry operation is performed.

File:
1 edited

Legend:

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

    r4922 r4925  
    7575        // Apply an implicit distribution + identity law whenever possible
    7676        //    (P ∧ Q) √ (P ∧ ¬Q) = P √ (Q ∧ ¬Q) ⇔ (P √ Q) ∧ (P √ ¬Q) = P ∧ (Q √ ¬Q) ⇔ P
    77         bool modified = false;
    7877        const TypeId typeId = isa<And>(var) ? TypeId::Or : TypeId::And;
    7978        for (unsigned i = 1; i < var->getNumOperands(); ++i) {
    8079            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()));
     80                Variadic * const Vi = cast<Variadic>(var->getOperand(i));
     81                assert (std::is_sorted(Vi->begin(), Vi->end()));
    8382                for (unsigned j = 0; j < i; ++j) {
     83                    assert (var->getOperand(i) == Vi);
    8484                    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.
     85                        Variadic * const Vj = cast<Variadic>(var->getOperand(j));
     86                        assert (std::is_sorted(Vj->begin(), Vj->end()));
     87                        if (Vi->getNumOperands() == Vj->getNumOperands()) {
     88                            // If vi and vj differ by precisely one operand, say di and dj, and di ⇔ ¬dj, we can apply this rule.
    9089                            unsigned vi = 0, vj = 0;
    91                             const unsigned operands = op_i->getNumOperands();
     90                            const unsigned operands = Vi->getNumOperands();
    9291                            unsigned di = operands - 1, dj = operands - 1;
    9392                            bool differsByOne = true;
    9493                            while (vi < operands && vj < operands) {
    95                                 if (op_i->getOperand(vi) < op_j->getOperand(vj)) {
     94                                if (Vi->getOperand(vi) < Vj->getOperand(vj)) {
    9695                                    if (LLVM_UNLIKELY(di != (operands - 1))) { // <- we want the branch predictor to fail only once
    9796                                        differsByOne = false;
     
    9998                                    }
    10099                                    di = vi++;
    101                                 } else if (op_j->getOperand(vj) < op_i->getOperand(vi)) {
     100                                } else if (Vj->getOperand(vj) < Vi->getOperand(vi)) {
    102101                                    if (LLVM_UNLIKELY(dj != (operands - 1))) {
    103102                                        differsByOne = false;
     
    112111                            if (LLVM_UNLIKELY(differsByOne)) {
    113112                                assert (di < operands && dj < operands);
    114                                 assert ("Found an equivalent set of operations that was not deduced earlier!" && !equals(op_i, op_j));
     113                                assert ("Found an equivalent set of operations that was not deduced earlier!" && (!equals(Vi, Vj)));
     114                                // test if di ⇔ ¬dj
    115115                                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));
     116                                if (isa<Not>(Vi->getOperand(di))) {
     117                                    apply = cast<Not>(Vi->getOperand(di))->getOperand(0) == Vj->getOperand(dj);
     118                                } else if (isa<Not>(Vj->getOperand(dj))) {
     119                                    apply = cast<Not>(Vj->getOperand(dj))->getOperand(0) == Vi->getOperand(di);
    120120                                }
    121121                                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.
     122                                    // Although we can apply this transformation, we have a potential problem. If P is not a "literal", we
     123                                    // cannot optimize var without creating a new And/Or statement. However, the redundancy elimination
     124                                    // pass will miss this new statement unless we mark "var" as its own replacement.
    125125                                    PabloAST * expr = nullptr;
    126126                                    if (operands == 2) {
    127                                         expr = op_i->getOperand(1 ^ di);
     127                                        expr = Vi->getOperand(1 ^ di);
    128128                                        if (LLVM_LIKELY(var->getNumOperands() == 2)) {
    129129                                            return expr;
     
    132132                                        assert (operands > 2);
    133133                                        block->setInsertPoint(var->getPrevNode());
    134                                         Variadic * nested = nullptr;
    135134                                        if (typeId == TypeId::And) {
    136                                             nested = block->createAnd(operands - 1);
     135                                            expr = block->createAnd(operands - 1);
    137136                                        } else { // if (typeId == TypeId::Or) {
    138                                             nested = block->createOr(operands - 1);
     137                                            expr = block->createOr(operands - 1);
    139138                                        }
    140139                                        for (unsigned k = 0; k != di; ++k) {
    141                                             nested->addOperand(op_i->getOperand(k));
     140                                            cast<Variadic>(expr)->addOperand(Vi->getOperand(k));
    142141                                        }
    143142                                        for (unsigned k = di + 1; k < operands; ++k) {
    144                                             nested->addOperand(op_i->getOperand(k));
     143                                            cast<Variadic>(expr)->addOperand(Vi->getOperand(k));
    145144                                        }
    146                                         expr = nested;
    147145                                        replacement = var;
    148146                                    }
     
    150148                                    var->removeOperand(i);
    151149                                    i = 0;
    152                                     modified = true;
    153                                     break;
     150                                    break; // out of for j = 0 to i - 1
    154151                                }
    155152                            }
     
    179176                        } else { // if (vi->getNumOperands() >= vj->getNumOperands()) {
    180177                            if (LLVM_UNLIKELY(std::includes(vj->begin(), vj->end(), vi->begin(), vi->end()))) {
    181                                 var->removeOperand(j--); i--;
     178                                var->removeOperand(j--);
     179                                --i;
    182180                            }
    183181                        }
     
    215213        }
    216214
    217         if (LLVM_UNLIKELY(modified)) {
     215        if (LLVM_UNLIKELY(replacement != nullptr)) {
    218216            // Ensure all operands of a reassociatiable function are consistently ordered.
    219217            std::sort(var->begin(), var->end());
     
    226224        }
    227225
    228     } // end of if (LLVM_LIKELY(isa<And>(var) || isa<Or>(var)))
     226    }
    229227
    230228    if (LLVM_UNLIKELY(var->getNumOperands() < 2)) {
     
    233231        }
    234232        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;
    253233    }
    254234    if (LLVM_UNLIKELY(negated)) {
     
    257237        replacement = block->createNot(replacement ? replacement : var);
    258238    }
    259     assert (replacement != var);
    260239    return replacement;
    261240}
     
    577556            if (LLVM_UNLIKELY(isa<Advance>(adv->getOperand(0)))) {
    578557                // Replace an Advance(Advance(x, n), m) with an Advance(x,n + m)
     558                // Test whether this will generate a long advance and abort?
    579559                Advance * op = cast<Advance>(stmt->getOperand(0));
    580560                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
Note: See TracChangeset for help on using the changeset viewer.