Ignore:
Timestamp:
Sep 14, 2016, 2:56:54 PM (3 years ago)
Author:
nmedfort
Message:

Work on multiplexing and distribution passes + a few AST modification bug fixes.

File:
1 edited

Legend:

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

    r4959 r5156  
    7575    if (LLVM_LIKELY(isa<And>(var) || isa<Or>(var))) {
    7676        // Apply an implicit distribution + identity law whenever possible
    77         //    (P ∧ Q) √ (P ∧ ¬Q) = P √ (Q ∧ ¬Q) ⇔ (P √ Q) ∧ (P √ ¬Q) = P ∧ (Q √ ¬Q) ⇔ P
     77        //    (P ∧ Q) √ (P ∧ ¬Q) = P √ (Q ∧ ¬Q) ⇔ P
    7878        const TypeId typeId = isa<And>(var) ? TypeId::Or : TypeId::And;
    7979        for (unsigned i = 1; i < var->getNumOperands(); ++i) {
    8080            if (var->getOperand(i)->getClassTypeId() == typeId) {
    8181                Variadic * const Vi = cast<Variadic>(var->getOperand(i));
    82                 assert (std::is_sorted(Vi->begin(), Vi->end()));
     82                if (LLVM_UNLIKELY(!std::is_sorted(Vi->begin(), Vi->end()))) {
     83                    std::sort(Vi->begin(), Vi->end());
     84                }
    8385                for (unsigned j = 0; j < i; ++j) {
    8486                    assert (var->getOperand(i) == Vi);
    8587                    if (var->getOperand(j)->getClassTypeId() == typeId) {
    8688                        Variadic * const Vj = cast<Variadic>(var->getOperand(j));
    87                         assert (std::is_sorted(Vj->begin(), Vj->end()));
     89                        if (LLVM_UNLIKELY(!std::is_sorted(Vj->begin(), Vj->end()))) {
     90                            std::sort(Vj->begin(), Vj->end());
     91                        }
    8892                        if (Vi->getNumOperands() == Vj->getNumOperands()) {
    8993                            // If vi and vj differ by precisely one operand, say di and dj, and di ⇔ ¬dj, we can apply this rule.
     
    308312 ** ------------------------------------------------------------------------------------------------------------- */
    309313inline bool Simplifier::isSuperfluous(const Assign * const assign) {
    310     for (const PabloAST * user : assign->users()) {
    311         if (LLVM_UNLIKELY(isa<PabloFunction>(user) || isa<Next>(user))) {
    312             return false;
    313         } else if (isa<If>(user)) {
    314             if (LLVM_UNLIKELY(cast<If>(user)->getCondition() == assign)) {
    315                 continue;
    316             } else if (isa<Assign>(assign->getExpression())) {
    317                 continue;
    318             }
    319             return false;
     314    if (LLVM_LIKELY(isa<Statement>(assign->getExpression()))) {
     315        for (const PabloAST * user : assign->users()) {
     316            if (LLVM_UNLIKELY(isa<PabloFunction>(user) || isa<Next>(user))) {
     317                return false;
     318            } else if (isa<If>(user)) {
     319                if (LLVM_UNLIKELY(cast<If>(user)->getCondition() == assign)) {
     320                    continue;
     321                } else if (isa<Assign>(assign->getExpression())) {
     322                    continue;
     323                }
     324                return false;
     325            }
    320326        }
    321327    }
     
    421427 * as replacements. Let the DCE remove the unnecessary statements with the finalized Def-Use information.
    422428 ** ------------------------------------------------------------------------------------------------------------- */
    423 void Simplifier::redundancyElimination(PabloBlock * const block, ExpressionTable * predecessor) {
     429void Simplifier::redundancyElimination(PabloFunction & function, PabloBlock * const block, ExpressionTable * predecessor) {
    424430    ExpressionTable encountered(predecessor);
    425431    Statement * stmt = block->front();
    426432
    427433    while (stmt) {
    428 
    429434        if (Assign * assign = dyn_cast<Assign>(stmt)) {
    430435            // If we have an Assign whose users do not contain an If or Next node, we can replace its users with
     
    456461
    457462            // Process the If body
    458             redundancyElimination(cast<If>(stmt)->getBody(), &encountered);
     463            redundancyElimination(function, cast<If>(stmt)->getBody(), &encountered);
    459464
    460465            // If we ended up removing all of the defined variables, delete the If node.
     
    495500                continue;
    496501            }
    497             redundancyElimination(whileNode->getBody(), &encountered);
     502            redundancyElimination(function, whileNode->getBody(), &encountered);
    498503            removeIdenticalEscapedValues(whileNode->getVariants());
    499504            // If the condition's Next state is Zero, we can eliminate the loop after copying the internal
     
    541546 * @brief deadCodeElimination
    542547 ** ------------------------------------------------------------------------------------------------------------- */
    543 void Simplifier::deadCodeElimination(PabloBlock * const block) {
     548void Simplifier::dce(PabloBlock * const block) {
    544549    Statement * stmt = block->front();
    545550    while (stmt) {
    546551        if (LLVM_UNLIKELY(isa<If>(stmt))) {
    547             deadCodeElimination(cast<If>(stmt)->getBody());
     552            dce(cast<If>(stmt)->getBody());
    548553        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
    549             deadCodeElimination(cast<While>(stmt)->getBody());
     554            dce(cast<While>(stmt)->getBody());
    550555        } else if (LLVM_UNLIKELY(unused(stmt))){
    551556            stmt = stmt->eraseFromParent(true);
     
    615620 ** ------------------------------------------------------------------------------------------------------------- */
    616621bool Simplifier::optimize(PabloFunction & function) {
    617     redundancyElimination(function.getEntryBlock());
     622    redundancyElimination(function, function.getEntryBlock());
     623    strengthReduction(function.getEntryBlock());
     624    dce(function.getEntryBlock());
    618625    #ifndef NDEBUG
    619     PabloVerifier::verify(function, "post-eliminate-redundant-code");
    620     #endif
    621     strengthReduction(function.getEntryBlock());
    622     #ifndef NDEBUG
    623     PabloVerifier::verify(function, "post-strength-reduction");
    624     #endif
    625     deadCodeElimination(function.getEntryBlock());
    626     #ifndef NDEBUG
    627     PabloVerifier::verify(function, "post-dead-code-elimination");
     626    PabloVerifier::verify(function, "post-simplification");
    628627    #endif
    629628    return true;
Note: See TracChangeset for help on using the changeset viewer.