Ignore:
Timestamp:
Oct 11, 2015, 1:45:52 PM (4 years ago)
Author:
nmedfort
Message:

Back-up check in

Location:
icGREP/icgrep-devel/icgrep/pablo
Files:
3 edited

Legend:

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

    r4805 r4829  
    2525    eliminateRedundantCode(function.getEntryBlock());
    2626    deadCodeElimination(function.getEntryBlock());
    27     // eliminateRedundantComplexStatements(function.getEntryBlock());
     27    eliminateRedundantEquations(function.getEntryBlock());
    2828    #ifndef NDEBUG
    2929    PabloVerifier::verify(function, "post-simplification");
     
    3232}
    3333
    34 inline static bool canTriviallyFold(const Statement * stmt) {
     34inline static PabloAST * canTriviallyFold(Statement * stmt, PabloBlock & block) {
    3535    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    36         switch (stmt->getOperand(i)->getClassTypeId()) {
    37             case PabloAST::ClassTypeId::Zeroes:
    38             case PabloAST::ClassTypeId::Ones:
    39                 return true;
    40             default: break;
    41         }
    42     }
    43     return false;
     36        if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(i)))) {
     37            switch (stmt->getClassTypeId()) {
     38                case PabloAST::ClassTypeId::And:
     39                case PabloAST::ClassTypeId::Advance:
     40                    return block.createZeroes();
     41                case PabloAST::ClassTypeId::Xor:
     42                case PabloAST::ClassTypeId::Or:
     43                    return stmt->getOperand(1 - i);
     44                case PabloAST::ClassTypeId::Not:
     45                    return block.createOnes();
     46                case PabloAST::ClassTypeId::Sel:
     47                    block.setInsertPoint(stmt->getPrevNode());
     48                    switch (i) {
     49                        case 0: return stmt->getOperand(2);
     50                        case 1: return block.createAnd(block.createNot(stmt->getOperand(0)), stmt->getOperand(2));
     51                        case 2: return block.createAnd(stmt->getOperand(0), stmt->getOperand(1));
     52                    }
     53                case PabloAST::ClassTypeId::ScanThru:
     54                case PabloAST::ClassTypeId::MatchStar:
     55                    return stmt->getOperand(0);
     56                default: break;
     57            }
     58        } else if (LLVM_UNLIKELY(isa<Ones>(stmt->getOperand(i)))) {
     59            block.setInsertPoint(stmt->getPrevNode());
     60            switch (stmt->getClassTypeId()) {
     61                case PabloAST::ClassTypeId::And:
     62                    return stmt->getOperand(1 - i);
     63                case PabloAST::ClassTypeId::Or:
     64                    return block.createOnes();
     65                case PabloAST::ClassTypeId::Xor:
     66                    return block.createNot(stmt->getOperand(1 - i));
     67                case PabloAST::ClassTypeId::Not:
     68                    return block.createZeroes();
     69                case PabloAST::ClassTypeId::Sel:
     70                    block.setInsertPoint(stmt->getPrevNode());
     71                    switch (i) {
     72                        case 0: return stmt->getOperand(1);
     73                        case 1: return block.createOr(stmt->getOperand(0), stmt->getOperand(2));
     74                        case 2: return block.createOr(block.createNot(stmt->getOperand(0)), stmt->getOperand(1));
     75                    }
     76                default: break;
     77            }
     78        }
     79    }
     80    return nullptr;
    4481}
    4582
     
    114151        for (auto j = i + 1; j != list.end(); ) {
    115152            if (LLVM_UNLIKELY(equals(*i, *j))) {
    116                 (*j)->replaceWith(*i, false, true);
     153                Statement * redundantValue = *j;
    117154                j = list.erase(j);
     155                redundantValue->replaceWith(*i, false, true);
    118156                continue;
    119157            }
     
    178216
    179217        } else if (While * whileNode = dyn_cast<While>(stmt)) {
    180 
    181218            const PabloAST * initial = whileNode->getCondition();
    182219            if (LLVM_LIKELY(isa<Next>(initial))) {
     
    187224                continue;
    188225            }
    189 
    190226            eliminateRedundantCode(whileNode->getBody(), &encountered);
    191 
    192227            removeIdenticalEscapedValues(whileNode->getVariants());
    193 
    194         } else if (canTriviallyFold(stmt)) { // non-Assign node
    195             // Do a trivial folding test to see if we're using all 0s or 1s as an operand.
    196             PabloAST * expr = nullptr;
    197             block.setInsertPoint(stmt->getPrevNode());
    198             switch (stmt->getClassTypeId()) {
    199                 case PabloAST::ClassTypeId::Advance:
    200                     expr = block.createAdvance(stmt->getOperand(0), stmt->getOperand(1));
    201                     break;
    202                 case PabloAST::ClassTypeId::And:
    203                     expr = block.createAnd(stmt->getOperand(0), stmt->getOperand(1));
    204                     break;
    205                 case PabloAST::ClassTypeId::Or:
    206                     expr = block.createOr(stmt->getOperand(0), stmt->getOperand(1));
    207                     break;
    208                 case PabloAST::ClassTypeId::Not:
    209                     expr = block.createNot(stmt->getOperand(0));
    210                     break;
    211                 case PabloAST::ClassTypeId::Xor:
    212                     expr = block.createXor(stmt->getOperand(0), stmt->getOperand(1));
    213                     break;
    214                 case PabloAST::ClassTypeId::Sel:
    215                     expr = block.createSel(stmt->getOperand(0), stmt->getOperand(1), stmt->getOperand(2));
    216                     break;
    217                 case PabloAST::ClassTypeId::ScanThru:
    218                     expr = block.createScanThru(stmt->getOperand(0), stmt->getOperand(1));
    219                     break;
    220                 case PabloAST::ClassTypeId::MatchStar:
    221                     expr = block.createMatchStar(stmt->getOperand(0), stmt->getOperand(1));
    222                     break;
    223                 case PabloAST::ClassTypeId::Next:
    224                     expr = stmt;
    225                     break;
    226                 default: {
    227                     std::string tmp;
    228                     llvm::raw_string_ostream msg(tmp);
    229                     PabloPrinter::print(stmt, "Unhandled trivial folding optimization! ", msg);
    230                     throw std::runtime_error(msg.str());
    231                 }
    232             }
    233             stmt = stmt->replaceWith(expr);
    234             block.setInsertPoint(block.back());
     228        } else if (PabloAST * expr = canTriviallyFold(stmt, block)) {
     229            stmt = stmt->replaceWith(expr, true, true);
    235230            continue;
    236231        } else {
     
    240235            // and erase this statement from the AST
    241236            const auto f = encountered.findOrAdd(stmt);
    242             if (f.second == false) {
     237            if (!f.second) {
    243238                stmt = stmt->replaceWith(f.first, true, true);
    244239                continue;
     
    255250        if (isa<If>(stmt)) {
    256251            deadCodeElimination(cast<If>(stmt)->getBody());
    257         }
    258         else if (isa<While>(stmt)) {
     252        } else if (isa<While>(stmt)) {
    259253            deadCodeElimination(cast<While>(stmt)->getBody());
    260         }
    261         else if (stmt->getNumUses() == 0){
     254        } else if (stmt->getNumUses() == 0){
    262255            stmt = stmt->eraseFromParent(true);
    263256            continue;
     
    267260}
    268261
    269 void Simplifier::eliminateRedundantComplexStatements(PabloBlock & block) {
     262void Simplifier::eliminateRedundantEquations(PabloBlock & block) {
    270263    Statement * stmt = block.front();
    271264    while (stmt) {
    272265        if (isa<If>(stmt)) {
    273             eliminateRedundantComplexStatements(cast<If>(stmt)->getBody());
     266            eliminateRedundantEquations(cast<If>(stmt)->getBody());
    274267        }
    275268        else if (isa<While>(stmt)) {
    276             eliminateRedundantComplexStatements(cast<While>(stmt)->getBody());
    277         }
    278         else if (stmt->getNumOperands() == 2){
    279             if (isa<Advance>(stmt)) {
    280                 // If we're advancing an Advance and the internal Advance does not have any other user,
    281                 // we can merge both Advance instructions.
    282                 if (LLVM_UNLIKELY(isa<Advance>(stmt->getOperand(0)))) {
    283                     Advance * op = cast<Advance>(stmt->getOperand(0));
    284                     if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
    285                         Advance * adv = cast<Advance>(stmt);
    286                         adv->setOperand(0, op->getOperand(0));
    287                         adv->setOperand(1, block.getInteger(adv->getAdvanceAmount() + op->getAdvanceAmount()));
    288                         assert(op->getNumUses() == 0);
    289                         op->eraseFromParent();
    290                     }
    291                 }
    292             } else if (LLVM_UNLIKELY(isa<Advance>(stmt->getOperand(1)) && isa<Advance>(stmt->getOperand(0)))) {
    293                 // If an AND, OR or XOR instruction has two Advance instructions as inputs and neither Advance
    294                 // has another user and both shift their input by the same amount, we can perform the AND, OR
    295                 // or XOR on the inputs to the Advances and remove one of the Advance statements.
    296 
    297                 Advance * const a0 = cast<Advance>(stmt->getOperand(0));
    298                 Advance * const a1 = cast<Advance>(stmt->getOperand(1));
    299                 switch (stmt->getClassTypeId()) {
    300                     case PabloAST::ClassTypeId::And:
    301                     case PabloAST::ClassTypeId::Or:
    302                     case PabloAST::ClassTypeId::Xor:
    303                         if (LLVM_UNLIKELY(a0->getNumUses() == 1 && a1->getNumUses() == 1 && a0->getOperand(1) == a1->getOperand(1))) {
    304                             block.setInsertPoint(stmt);
    305                             stmt->setOperand(0, a0->getOperand(0));
    306                             stmt->setOperand(1, a1->getOperand(0));
    307                             a0->insertAfter(stmt);
    308                             a0->setOperand(0, stmt);
    309                             stmt->replaceAllUsesWith(a0);
    310                             assert(a1->getNumUses() == 0);
    311                             a1->eraseFromParent();
    312                             stmt = a0;
    313                     }
    314                     default: break;
    315                 }
    316             } else if (LLVM_UNLIKELY(isa<MatchStar>(stmt->getOperand(1)) && isa<MatchStar>(stmt->getOperand(0))) && isa<Or>(stmt)) {
    317 
    318 
    319             } /*else if (LLVM_UNLIKELY(isa<Or>(stmt) && isa<And>(stmt->getOperand(0)) && isa<And>(stmt->getOperand(1)))) {
    320 
    321                 // If we have an OR(AND(A,B),AND(NOT(A),C)) statement and neither of the inner operands are used elsewhere, we can
    322                 // promote the Or to a Sel statement.
    323 
    324                 And * const a0 = cast<And>(stmt->getOperand(0));
    325                 And * const a1 = cast<And>(stmt->getOperand(1));
    326 
    327                 if (LLVM_UNLIKELY(a0->getNumUses() == 1 && a1->getNumUses() == 1)) {
    328 
    329                     bool neg[4] = { false, false, false, false };
    330 
    331                     for (unsigned i = 0; i != 2; ++i) {
    332                         if (isa<Not>(a0->getOperand(i))) {
    333                             PabloAST * i0 = cast<Not>(a0->getOperand(i))->getOperand(0);
    334                             for (unsigned j = 0; j != 2; ++j) {
    335                                 if (a0->getOperand(j) == i0) {
    336                                     neg[i + j * 2] = true;
    337                                 }
    338                             }
    339                         }
    340                     }
    341 
    342 
    343 
    344 
    345 
    346 
    347 
    348 
    349 
    350                 }
    351 
    352             }*/
     269            eliminateRedundantEquations(cast<While>(stmt)->getBody());
     270        } else if (isa<Advance>(stmt)) {
     271            Advance * adv = cast<Advance>(stmt);
     272            if (LLVM_UNLIKELY(isa<Advance>(adv->getOperand(0)))) {
     273                // Replace an Advance(Advance(x, n), m) with an Advance(x,n + m)
     274                Advance * op = cast<Advance>(stmt->getOperand(0));
     275                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
     276                    adv->setOperand(0, op->getOperand(0));
     277                    adv->setOperand(1, block.getInteger(adv->getAdvanceAmount() + op->getAdvanceAmount()));
     278                    op->eraseFromParent(false);
     279                }
     280            }
     281        } else if (LLVM_UNLIKELY(isa<ScanThru>(stmt))) {
     282            ScanThru * scanThru = cast<ScanThru>(stmt);
     283            if (LLVM_UNLIKELY(isa<Advance>(scanThru->getOperand(0)))) {
     284                // Replace a ScanThru(Advance(x,n),y) with an ScanThru(Advance(x, n - 1), Advance(x, n - 1) | y), where Advance(x, 0) = x
     285                Advance * op = cast<Advance>(stmt->getOperand(0));
     286                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
     287                    block.setInsertPoint(scanThru);
     288                    PabloAST * expr = block.createAdvance(op->getOperand(0), op->getAdvanceAmount() - 1);
     289                    scanThru->setOperand(0, expr);
     290                    scanThru->setOperand(1, block.createOr(scanThru->getOperand(1), expr));
     291                    op->eraseFromParent(false);
     292                }
     293            }
    353294        }
    354295        stmt = stmt->getNextNode();
     
    357298}
    358299
    359 Simplifier::Simplifier()
    360 {
    361 
    362 }
    363 
    364 
    365 }
     300}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.hpp

    r4768 r4829  
    1414    static void deadCodeElimination(PabloBlock & block);
    1515protected:
    16     Simplifier();
     16    Simplifier() = default;
    1717private:
    1818    static void eliminateRedundantCode(PabloBlock & block, ExpressionTable * predecessor = nullptr);
    19     static void eliminateRedundantComplexStatements(PabloBlock & block);
     19    static void eliminateRedundantEquations(PabloBlock & block);
    2020    static bool isSuperfluous(const Assign * const assign);
    21 private:
    22 
    2321};
    2422
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4805 r4829  
    212212        mOperand[i]->removeUser(this);
    213213    }
     214    Statement * redundantBranch = nullptr;
    214215    // If this is an If or While statement, we'll have to remove the statements within the
    215216    // body or we'll lose track of them.
     
    217218        PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
    218219        Statement * stmt = body.front();
     220        // Note: by erasing the body, any Assign/Next nodes will be replaced with Zero.
    219221        while (stmt) {
    220222            stmt = stmt->eraseFromParent(recursively);
     
    223225        for (PabloAST * use : mUsers) {
    224226            if (If * ifNode = dyn_cast<If>(use)) {
    225                 const auto & defs = ifNode->getDefined();
    226                 if (LLVM_LIKELY(std::find(defs.begin(), defs.end(), this) != defs.end())) {
     227                auto & defs = ifNode->getDefined();
     228                auto f = std::find(defs.begin(), defs.end(), this);
     229                if (LLVM_LIKELY(f != defs.end())) {
    227230                    this->removeUser(ifNode);
    228231                    ifNode->removeUser(this);
     232                    defs.erase(f);
     233                    if (LLVM_UNLIKELY(defs.empty())) {
     234                        redundantBranch = ifNode;
     235                    }
    229236                    break;
    230237                }
     
    234241        for (PabloAST * use : mUsers) {
    235242            if (While * whileNode = dyn_cast<While>(use)) {
    236                 const auto & vars = whileNode->getVariants();
    237                 if (LLVM_LIKELY(std::find(vars.begin(), vars.end(), this) != vars.end())) {
     243                auto & vars = whileNode->getVariants();
     244                auto f = std::find(vars.begin(), vars.end(), this);
     245                if (LLVM_LIKELY(f != vars.end())) {
    238246                    this->removeUser(whileNode);
    239247                    whileNode->removeUser(this);
     248                    vars.erase(f);
     249                    if (LLVM_UNLIKELY(vars.empty())) {
     250                        redundantBranch = whileNode;
     251                    }
    240252                    break;
    241253                }
     
    249261        for (unsigned i = 0; i != mOperands; ++i) {
    250262            PabloAST * const op = mOperand[i];
    251             if (op->getNumUses() == 0 && isa<Statement>(op)) {
    252                 cast<Statement>(op)->eraseFromParent(true);
    253             }
     263            if (LLVM_LIKELY(isa<Statement>(op))) {
     264                bool erase = false;
     265                if (op->getNumUses() == 0) {
     266                    erase = true;
     267                } else if ((isa<Assign>(op) || isa<Next>(op)) && op->getNumUses() == 1) {
     268                    erase = true;
     269                }
     270                if (erase) {
     271                    cast<Statement>(op)->eraseFromParent(true);
     272                }
     273            }
     274        }
     275        if (LLVM_UNLIKELY(redundantBranch != nullptr)) {
     276            redundantBranch->eraseFromParent(true);
    254277        }
    255278    }
Note: See TracChangeset for help on using the changeset viewer.