Ignore:
Timestamp:
May 31, 2017, 4:25:33 PM (2 years ago)
Author:
nmedfort
Message:

Initial attempt to improve debugging capabilities with compilation stack traces on error.

File:
1 edited

Legend:

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

    r5454 r5486  
    2929/** ------------------------------------------------------------------------------------------------------------- *
    3030 * @brief fold
    31  *
    32  * Note: if folding alters this variadic without making any other modification to the AST, it will return null as
    33  * if no change was made.
    34  ** ------------------------------------------------------------------------------------------------------------- */
    35 inline PabloAST * Simplifier::fold(Variadic * var, PabloBlock * const block) {
    36 
    37     assert (var);
    38 
    39     bool negated = false;
    40     if (LLVM_UNLIKELY(isa<Xor>(var))) {
    41         for (unsigned i = 0; i != var->getNumOperands(); ++i) {
    42             if (isa<Not>(var->getOperand(i))) {
    43                 // (A ⊕ ¬B) = (A ⊕ (B ⊕ 1)) = ¬(A ⊕ B)
    44                 var->setOperand(i, cast<Not>(var->getOperand(i))->getOperand(0));
    45                 negated = !negated;
    46             }
    47         }
    48     }
    49 
    50     // Ensure all operands of a reassociatiable function are consistently ordered.
    51     std::sort(var->begin(), var->end());
    52 
    53     // Apply the idempotence law to any And and Or statement and the identity law to any Xor
    54     for (int i = var->getNumOperands() - 1; i > 0; --i) {
    55         if (LLVM_UNLIKELY(equals(var->getOperand(i), var->getOperand(i - 1)))) {
    56             var->removeOperand(i);
    57             if (LLVM_UNLIKELY(isa<Xor>(var))) {
    58                 var->removeOperand(--i);
    59             }
    60         }
    61     }
    62 
    63     // Apply the annihilator and identity laws
    64     for (unsigned i = 0; i != var->getNumOperands(); ) {
    65         if (LLVM_UNLIKELY(isa<Zeroes>(var->getOperand(i)))) {
    66             if (LLVM_UNLIKELY(isa<And>(var))) {
    67                 return block->createZeroes(var->getType());
    68             }
    69             var->removeOperand(i);
    70             continue;
    71         } else if (LLVM_UNLIKELY(isa<Ones>(var->getOperand(i)))) {
    72             if (LLVM_UNLIKELY(isa<Or>(var))) {
    73                 return block->createOnes(var->getType());
    74             } else if (LLVM_UNLIKELY(isa<Xor>(var))) {
    75                 negated = !negated;
    76             }
    77             var->removeOperand(i);
    78             continue;
    79         }
    80         ++i;
    81     }
    82 
    83     PabloAST * replacement = nullptr;
    84 
    85     if (LLVM_LIKELY(isa<And>(var) || isa<Or>(var))) {
    86         // Apply an implicit distribution + identity law whenever possible
    87         //    (P ∧ Q) √ (P ∧ ¬Q) = P √ (Q ∧ ¬Q) ⇔ P
    88         TypeId typeId = isa<And>(var) ? TypeId::Or : TypeId::And;
    89         for (unsigned i = 0; i < var->getNumOperands(); ++i) {
    90             if (var->getOperand(i)->getClassTypeId() == typeId) {
    91                 Variadic * const Vi = cast<Variadic>(var->getOperand(i));
    92                 // Ensure the i-th operand is sorted incase it was altered after being folded.
    93                 std::sort(Vi->begin(), Vi->end());
    94                 for (unsigned j = 0; j < i; ++j) {
    95                     assert (var->getOperand(i) == Vi);
    96                     if (var->getOperand(j)->getClassTypeId() == typeId) {
    97                         Variadic * const Vj = cast<Variadic>(var->getOperand(j));
    98                         assert (std::is_sorted(Vj->begin(), Vj->end()));
    99                         if (Vi->getNumOperands() == Vj->getNumOperands()) {
    100                             // If vi and vj differ by precisely one operand, say di and dj,
    101                             // and di ⇔ ¬dj, we can apply this rule.
    102                             unsigned vi = 0, vj = 0;
    103                             const unsigned operands = Vi->getNumOperands();
    104                             unsigned di = operands - 1, dj = operands - 1;
    105                             bool differsByOne = true;
    106                             while (vi < operands && vj < operands) {
    107                                 if (Vi->getOperand(vi) < Vj->getOperand(vj)) {
    108                                     if (LLVM_UNLIKELY(di != (operands - 1))) { // <- we want the branch predictor to fail only once
    109                                         differsByOne = false;
    110                                         break;
    111                                     }
    112                                     di = vi++;
    113                                 } else if (Vj->getOperand(vj) < Vi->getOperand(vi)) {
    114                                     if (LLVM_UNLIKELY(dj != (operands - 1))) {
    115                                         differsByOne = false;
    116                                         break;
    117                                     }
    118                                     dj = vj++;
    119                                 } else {
    120                                     ++vi;
    121                                     ++vj;
    122                                 }
    123                             }
    124                             if (LLVM_UNLIKELY(differsByOne)) {
    125                                 assert (di < operands && dj < operands);
    126                                 assert ("Found an equivalent set of operations that was not deduced earlier!" && (!equals(Vi, Vj)));
    127                                 // test if di ⇔ ¬dj
    128                                 bool apply = false;
    129                                 if (isa<Not>(Vi->getOperand(di))) {
    130                                     apply = cast<Not>(Vi->getOperand(di))->getOperand(0) == Vj->getOperand(dj);
    131                                 } else if (isa<Not>(Vj->getOperand(dj))) {
    132                                     apply = cast<Not>(Vj->getOperand(dj))->getOperand(0) == Vi->getOperand(di);
    133                                 }
    134                                 if (LLVM_UNLIKELY(apply)) {
    135                                     // Although we can apply this transformation, we have a potential problem. If P is not a "literal", we
    136                                     // cannot optimize var without creating a new And/Or statement. However, the redundancy elimination
    137                                     // pass will miss this new statement unless we mark "var" as its own replacement. We'll end up checking
    138                                     // "var" again but termination is still guaranteed once none of the new statements can be replaced by
    139                                     // prior statements in the AST.
    140                                     PabloAST * expr = nullptr;
    141                                     if (operands == 2) {
    142                                         expr = Vi->getOperand(1 ^ di);
    143                                         if (LLVM_LIKELY(var->getNumOperands() == 2)) {
    144                                             return expr;
    145                                         }
    146                                     } else { // if (operands > 2) {
    147                                         assert (operands > 2);
    148                                         block->setInsertPoint(var->getPrevNode());
    149                                         if (typeId == TypeId::And) {
    150                                             expr = block->createAnd(var->getType(), operands - 1);
    151                                         } else { // if (typeId == TypeId::Or) {
    152                                             expr = block->createOr(var->getType(), operands - 1);
    153                                         }
    154                                         for (unsigned k = 0; k != di; ++k) {
    155                                             cast<Variadic>(expr)->addOperand(Vi->getOperand(k));
    156                                         }
    157                                         for (unsigned k = di + 1; k < operands; ++k) {
    158                                             cast<Variadic>(expr)->addOperand(Vi->getOperand(k));
    159                                         }
    160                                         replacement = var;
    161                                     }
    162                                     var->removeOperand(i);
    163                                     var->removeOperand(j);
    164                                     bool unique = true;
    165                                     for (unsigned k = 0; k != var->getNumOperands(); ++k) {
    166                                         if (LLVM_UNLIKELY(equals(var->getOperand(k), expr))) {
    167                                             unique = false;
    168                                             break;
    169                                         }
    170                                     }
    171                                     if (LLVM_LIKELY(unique)) {
    172                                         var->addOperand(expr);
    173                                     }
    174                                     i -= 2;
    175                                     break; // out of for j = 0 to i - 1
    176                                 }
    177                             }
    178                         }
    179                     }
    180                 }
    181             }
    182         }
    183 
    184         // Apply the absorption law whenever possible
    185         //   P √ (P ∧ Q) ⇔ P ∧ (P √ Q) ⇔ P
    186         for (unsigned i = 1; i < var->getNumOperands(); ++i) {
    187             PabloAST * const op = var->getOperand(i);
    188             if (op->getClassTypeId() == typeId) {
    189                 Variadic * const vi = cast<Variadic>(op);
    190                 assert (std::is_sorted(vi->begin(), vi->end()));
    191                 for (unsigned j = 0; j < i; ++j) {
    192                     assert (var->getOperand(i) == vi);
    193                     if (var->getOperand(j)->getClassTypeId() == typeId) {
    194                         Variadic * const vj = cast<Variadic>(var->getOperand(j));
    195                         assert (std::is_sorted(vj->begin(), vj->end()));
    196                         if (vi->getNumOperands() < vj->getNumOperands()) {
    197                             if (LLVM_UNLIKELY(std::includes(vi->begin(), vi->end(), vj->begin(), vj->end()))) {
    198                                 var->removeOperand(i--);
    199                                 break;
    200                             }
    201                         } else { // if (vi->getNumOperands() >= vj->getNumOperands()) {
    202                             if (LLVM_UNLIKELY(std::includes(vj->begin(), vj->end(), vi->begin(), vi->end()))) {
    203                                 var->removeOperand(j--);
    204                                 --i;
    205                             }
    206                         }
    207                     }
    208                 }
    209             } else { // treat the operand as a literal
    210                 for (unsigned j = 0; j < var->getNumOperands(); ) {
    211                     if (var->getOperand(j)->getClassTypeId() == typeId) {
    212                         Variadic * const vj = cast<Variadic>(var->getOperand(j));
    213                         assert (std::is_sorted(vj->begin(), vj->end()));
    214                         if (LLVM_UNLIKELY(std::binary_search(vj->begin(), vj->end(), op))) {
    215                             var->removeOperand(j);
    216                             continue;
    217                         }
    218                     }
    219                     ++j;
    220                 }
    221             }
    222         }
    223 
    224         // Apply the complementation law whenever possible.
    225         for (unsigned i = 0; i < var->getNumOperands(); ++i) {
    226             if (isa<Not>(var->getOperand(i))) {
    227                 const PabloAST * const negated = cast<Not>(var->getOperand(i))->getOperand(0);
    228                 for (unsigned j = 0; j != var->getNumOperands(); ++j) {
    229                     if (LLVM_UNLIKELY(var->getOperand(j) == negated)) {
    230                         if (isa<And>(var)) { // (A ∧ ¬A) ∧ B ⇔ 0 for any B
    231                             return block->createZeroes(var->getType());
    232                         } else { // if (isa<Or>(var)) { // (A √ ¬A) √ B ⇔ 1 for any B
    233                             return block->createOnes(var->getType());
    234                         }
    235                     }
    236                 }
    237             }
    238         }
    239 
    240     }
    241 
    242     if (LLVM_UNLIKELY(var->getNumOperands() < 2)) {
    243         if (LLVM_UNLIKELY(var->getNumOperands() == 0)) {
    244             return block->createZeroes(var->getType());
    245         }
    246         replacement = var->getOperand(0);
    247     }
    248     if (LLVM_UNLIKELY(negated)) {
    249         assert (isa<Xor>(var));
    250         block->setInsertPoint(var);
    251         replacement = block->createNot(replacement ? replacement : var);
    252     }
    253     return replacement;
    254 }
    255 
    256 /** ------------------------------------------------------------------------------------------------------------- *
    257  * @brief fold
    258  ** ------------------------------------------------------------------------------------------------------------- */
    259 PabloAST * Simplifier::fold(Statement * stmt, PabloBlock * const block) {
    260     if (isa<Variadic>(stmt)) {
    261         return fold(cast<Variadic>(stmt), block);
    262     } else if (isa<Not>(stmt)) {
     31 ** ------------------------------------------------------------------------------------------------------------- */
     32PabloAST * Simplifier::triviallyFold(Statement * stmt, PabloBlock * const block) {
     33    if (isa<Not>(stmt)) {
    26334        PabloAST * value = stmt->getOperand(0);
    26435        if (LLVM_UNLIKELY(isa<Not>(value))) {
     
    479250            }
    480251
    481             Statement * const prior = stmt->getPrevNode();
    482             PabloAST * const folded = fold(stmt, block);
     252            PabloAST * const folded = triviallyFold(stmt, block);
    483253            if (folded) {
    484                 // If we determine we can fold this statement, go back to the original prior node of this statement.
    485                 // New statements may have been inserted after it.
    486                 stmt->replaceWith(folded, true);
    487                 stmt = LLVM_LIKELY(prior != nullptr) ? prior->getNextNode() : block->front();
    488                 continue;
    489             }
     254                stmt = stmt->replaceWith(folded);
     255                continue;
     256            }
     257
    490258            // By recording which statements have already been seen, we can detect the redundant statements
    491259            // as any having the same type and operands. If so, we can replace its users with the prior statement.
     
    493261            const auto f = expressions.findOrAdd(stmt);
    494262            if (!f.second) {
    495                 stmt = stmt->replaceWith(f.first, true);
     263                stmt = stmt->replaceWith(f.first);
    496264                continue;
    497265            }
Note: See TracChangeset for help on using the changeset viewer.