Ignore:
Timestamp:
Nov 6, 2016, 8:37:11 PM (3 years ago)
Author:
nmedfort
Message:

Initial work on adding types to PabloAST and mutable Var objects.

File:
1 edited

Legend:

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

    r5160 r5202  
    33#include <pablo/expression_map.hpp>
    44#include <pablo/function.h>
    5 #include <pablo/printer_pablos.h>
    65#include <pablo/analysis/pabloverifier.hpp>
    76#include <boost/container/flat_set.hpp>
    8 
     7#include <boost/container/flat_map.hpp>
    98#include <pablo/printer_pablos.h>
    109#include <iostream>
    1110
     11using namespace boost;
     12using namespace boost::container;
     13
    1214namespace pablo {
    13 
    14 template <typename Type>
    15 using SmallSet = boost::container::flat_set<Type>;
    1615
    1716using TypeId = PabloAST::ClassTypeId;
     
    7675        // Apply an implicit distribution + identity law whenever possible
    7776        //    (P ∧ Q) √ (P ∧ ¬Q) = P √ (Q ∧ ¬Q) ⇔ P
    78         const TypeId typeId = isa<And>(var) ? TypeId::Or : TypeId::And;
    79         for (unsigned i = 1; i < var->getNumOperands(); ++i) {
     77        TypeId typeId = isa<And>(var) ? TypeId::Or : TypeId::And;
     78        for (unsigned i = 0; i < var->getNumOperands(); ++i) {
    8079            if (var->getOperand(i)->getClassTypeId() == typeId) {
    8180                Variadic * const Vi = cast<Variadic>(var->getOperand(i));
    82                 if (LLVM_UNLIKELY(!std::is_sorted(Vi->begin(), Vi->end()))) {
    83                     std::sort(Vi->begin(), Vi->end());
    84                 }
     81                // Ensure the i-th operand is sorted incase it was altered after being folded.
     82                std::sort(Vi->begin(), Vi->end());
    8583                for (unsigned j = 0; j < i; ++j) {
    8684                    assert (var->getOperand(i) == Vi);
    8785                    if (var->getOperand(j)->getClassTypeId() == typeId) {
    8886                        Variadic * const Vj = cast<Variadic>(var->getOperand(j));
    89                         if (LLVM_UNLIKELY(!std::is_sorted(Vj->begin(), Vj->end()))) {
    90                             std::sort(Vj->begin(), Vj->end());
    91                         }
     87                        assert (std::is_sorted(Vj->begin(), Vj->end()));
    9288                        if (Vi->getNumOperands() == Vj->getNumOperands()) {
    93                             // If vi and vj differ by precisely one operand, say di and dj, and di ⇔ ¬dj, we can apply this rule.
     89                            // If vi and vj differ by precisely one operand, say di and dj,
     90                            // and di ⇔ ¬dj, we can apply this rule.
    9491                            unsigned vi = 0, vj = 0;
    9592                            const unsigned operands = Vi->getNumOperands();
     
    269266            if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(i)))) {
    270267                switch (stmt->getClassTypeId()) {
    271                     case PabloAST::ClassTypeId::Sel:
     268                    case TypeId::Sel:
    272269                        block->setInsertPoint(stmt->getPrevNode());
    273270                        switch (i) {
     
    276273                            case 2: return block->createAnd(stmt->getOperand(0), stmt->getOperand(1));
    277274                        }
    278                     case PabloAST::ClassTypeId::ScanThru:
    279                     case PabloAST::ClassTypeId::MatchStar:
     275                    case TypeId::ScanThru:
     276                    case TypeId::MatchStar:
    280277                        return stmt->getOperand(0);
    281278                    default: break;
     
    283280            } else if (LLVM_UNLIKELY(isa<Ones>(stmt->getOperand(i)))) {
    284281                switch (stmt->getClassTypeId()) {
    285                     case PabloAST::ClassTypeId::Sel:
     282                    case TypeId::Sel:
    286283                        block->setInsertPoint(stmt->getPrevNode());
    287284                        switch (i) {
     
    290287                            case 2: return block->createOr(block->createNot(stmt->getOperand(0)), stmt->getOperand(1));
    291288                        }
    292                     case PabloAST::ClassTypeId::ScanThru:
     289                    case TypeId::ScanThru:
    293290                        if (LLVM_UNLIKELY(i == 1)) {
    294291                            return block->createZeroes(stmt->getType());
    295292                        }
    296293                        break;
    297                     case PabloAST::ClassTypeId::MatchStar:
     294                    case TypeId::MatchStar:
    298295                        if (LLVM_UNLIKELY(i == 0)) {
    299296                            return block->createOnes(stmt->getType());
     
    306303    }
    307304    return nullptr;
    308 }
    309 
    310 /** ------------------------------------------------------------------------------------------------------------- *
    311  * @brief isSuperfluous
    312  ** ------------------------------------------------------------------------------------------------------------- */
    313 inline bool Simplifier::isSuperfluous(const Assign * const assign) {
    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             }
    326         }
    327     }
    328     return true;
    329 }
    330 
    331 /** ------------------------------------------------------------------------------------------------------------- *
    332  * @brief demoteDefinedVar
    333  ** ------------------------------------------------------------------------------------------------------------- */
    334 inline bool demoteDefinedVar(const If * ifNode, const Assign * def) {
    335     // If this value isn't used outside of this scope then there is no reason to allow it to escape it.
    336     if (!escapes(def)) {
    337         return true;
    338     }
    339     // Similarly if the defined variable is equivalent to the condition, an equivalent value is already available.
    340     if (ifNode->getCondition() == def->getExpression()) {
    341         return true;
    342     }
    343     // Finally, if the assignment is a constant, it's already known.
    344     if (isa<Zeroes>(def->getExpression()) || isa<Ones>(def->getExpression()))  {
    345         return true;
    346     }
    347     return false;
    348 }
    349 
    350 /** ------------------------------------------------------------------------------------------------------------- *
    351  * @brief replaceReachableUsersOfWith
    352  ** ------------------------------------------------------------------------------------------------------------- */
    353 inline void replaceReachableUsersOfWith(Statement * stmt, PabloAST * expr) {
    354     const PabloBlock * const root = stmt->getParent();
    355     SmallSet<const PabloBlock *> forbidden;
    356     for (PabloAST * use : stmt->users()) {
    357         if (LLVM_UNLIKELY(isa<Next>(use))) {
    358             const PabloBlock * parent = cast<Next>(use)->getParent();
    359             if (parent != root) {
    360                 forbidden.insert(parent);
    361             }
    362         }
    363     }
    364     for (PabloAST * use : stmt->users()) {
    365         if (Statement * user = dyn_cast<Statement>(use)) {
    366             const PabloBlock * parent = user->getParent();
    367             while (parent && forbidden.count(parent) == 0) {
    368                 if (LLVM_UNLIKELY(parent == root)) {
    369                     user->replaceUsesOfWith(stmt, expr);
    370                     break;
    371                 }
    372                 parent = parent->getPredecessor ();
    373             }
    374         }
    375     }
    376305}
    377306
     
    380309 *
    381310 * If this inner block is composed of only Boolean logic and Assign statements and there are fewer than 3
    382  * statements, just add the statements in the inner block to the current block->
     311 * statements, just add the statements in the inner block to the current block
    383312 ** ------------------------------------------------------------------------------------------------------------- */
    384313inline bool discardNestedIfBlock(const PabloBlock * const block) {
     
    386315    for (const Statement * stmt : *block) {
    387316        switch (stmt->getClassTypeId()) {
    388             case PabloAST::ClassTypeId::And:
    389             case PabloAST::ClassTypeId::Or:
    390             case PabloAST::ClassTypeId::Xor:
     317            case TypeId::And:
     318            case TypeId::Or:
     319            case TypeId::Xor:
    391320                if (++computations > 3) {
    392321                    return false;
    393322                }
    394             case PabloAST::ClassTypeId::Not:
    395             case PabloAST::ClassTypeId::Assign:
     323            case TypeId::Not:
     324            case TypeId::Assign:
    396325                break;
    397326            default:
     
    403332
    404333/** ------------------------------------------------------------------------------------------------------------- *
    405  * @brief removeIdenticalEscapedValues
    406  ** ------------------------------------------------------------------------------------------------------------- */
    407 template <class ValueList, class ValueType = typename ValueList::value_type>
    408 inline void removeIdenticalEscapedValues(ValueList & list) {
    409     std::vector<ValueType> identicalValues;
    410     for (auto i = list.begin(); i != list.end(); ++i) {
    411         for (auto j = i + 1; j != list.end(); ++j) {
    412             if (LLVM_UNLIKELY(equals(*i, *j))) {
    413                 identicalValues.push_back(*j);
    414             }
    415         }
    416         for (ValueType identicalValue : identicalValues) {
    417             identicalValue->replaceWith(*i);
    418         }
    419         identicalValues.clear();
    420     }
    421 }
     334 * @brief VariableTable
     335 ** ------------------------------------------------------------------------------------------------------------- */
     336struct Simplifier::VariableTable {
     337
     338    VariableTable(VariableTable * predecessor = nullptr)
     339    : mPredecessor(predecessor) {
     340
     341    }
     342
     343    PabloAST * get(PabloAST * const var) const {
     344        const auto f = mMap.find(var);
     345        if (f == mMap.end()) {
     346            return (mPredecessor) ? mPredecessor->get(var) : nullptr;
     347        }
     348        return f->second;
     349    }
     350
     351    void put(PabloAST * const var, PabloAST * value) {
     352        const auto f = mMap.find(var);
     353        if (LLVM_LIKELY(f == mMap.end())) {
     354            mMap.emplace(var, value);
     355        } else {
     356            f->second = value;
     357        }
     358        assert (get(var) == value);
     359    }
     360
     361private:
     362    VariableTable * const mPredecessor;
     363    flat_map<PabloAST *, PabloAST *> mMap;
     364};
    422365
    423366/** ------------------------------------------------------------------------------------------------------------- *
     
    427370 * as replacements. Let the DCE remove the unnecessary statements with the finalized Def-Use information.
    428371 ** ------------------------------------------------------------------------------------------------------------- */
    429 void Simplifier::redundancyElimination(PabloFunction & function, PabloBlock * const block, ExpressionTable * predecessor) {
    430     ExpressionTable encountered(predecessor);
     372void Simplifier::redundancyElimination(PabloBlock * const block, ExpressionTable * const et, VariableTable * const vt) {
     373    ExpressionTable expressions(et);
     374    VariableTable variables(vt);
     375
     376    // When processing a While body, we cannot use its initial value from the outer
     377    // body since the Var will likely be assigned a different value in the current
     378    // body that should be used on the subsequent iteration of the loop.
     379    if (While * br = dyn_cast_or_null<While>(block->getBranch())) {
     380        for (Var * var : br->getEscaped()) {
     381            variables.put(var, var);
     382        }
     383    }
     384
    431385    Statement * stmt = block->front();
    432386    while (stmt) {
    433         if (Assign * assign = dyn_cast<Assign>(stmt)) {
    434             // If we have an Assign whose users do not contain an If or Next node, we can replace its users with
    435             // the Assign's expression directly.
    436             if (isSuperfluous(assign)) {
    437                 stmt = assign->replaceWith(assign->getExpression());
    438                 continue;
    439             }
    440             // Force the uses of an Assign node that can reach the original expression to use the expression instead.
    441             replaceReachableUsersOfWith(assign, assign->getExpression());
    442         } else if (Next * next = dyn_cast<Next>(stmt)) {
    443             replaceReachableUsersOfWith(next, next->getExpr());
    444         } else if (If * ifNode = dyn_cast<If>(stmt)) {
    445             // Test whether we can ever take this branch
    446             if (LLVM_UNLIKELY(isa<Zeroes>(cast<If>(stmt)->getCondition()))) {
     387
     388        if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     389            Assign * const assign = cast<Assign>(stmt);
     390            PabloAST * const var = assign->getVariable();
     391            PabloAST * value = assign->getValue();
     392            while (LLVM_UNLIKELY(isa<Var>(value))) {
     393                PabloAST * next = variables.get(cast<Var>(value));
     394                if (LLVM_LIKELY(next == nullptr || next == value)) {
     395                    break;
     396                }
     397                value = next;
     398                assign->setValue(value);
     399            }
     400            if (LLVM_UNLIKELY(variables.get(var) == value)) {
    447401                stmt = stmt->eraseFromParent();
    448402                continue;
    449403            }
    450             // Test whether all of the defined variables are necessary
    451             If::DefinedVars & defs = ifNode->getDefined();
    452             for (auto def = defs.begin(); def != defs.end(); ) {
    453                 if (LLVM_UNLIKELY(demoteDefinedVar(ifNode, *def))) {
    454                     (*def)->replaceWith((*def)->getExpression());
    455                     def = ifNode->removeDefined(*def);
    456                     continue;
    457                 }
    458                 ++def;
    459             }
    460 
    461             // Process the If body
    462             redundancyElimination(function, cast<If>(stmt)->getBody(), &encountered);
    463 
    464             // If we ended up removing all of the defined variables, delete the If node.
    465             if (LLVM_UNLIKELY(defs.empty())) {
     404            variables.put(var, value);
     405        } else if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     406
     407            Branch * const br = cast<Branch>(stmt);
     408
     409            // Test whether we can ever take this branch
     410            PabloAST * cond = br->getCondition();
     411            if (isa<Var>(cond)) {
     412                PabloAST * const value = variables.get(cast<Var>(cond));
     413                if (value) {
     414                    cond = value;
     415                    // TODO: verify this works for a nested If node within a While body.
     416                    if (isa<If>(br)) {
     417                        br->setCondition(cond);
     418                    }
     419                }
     420            }
     421
     422            if (LLVM_UNLIKELY(isa<Zeroes>(cond))) {
    466423                stmt = stmt->eraseFromParent();
    467424                continue;
    468425            }
    469426
    470             // Otherwise check if we any Assign reports the same value as another. If so, replace all uses of the
    471             // second with the first. This will simplify future analysis.
    472             removeIdenticalEscapedValues(ifNode->getDefined());
    473 
    474             // Finally after we've eliminated everything we can from the If body, check whether testing the If
    475             // condition will meet or exceed the cost of executing the body.
    476             if (LLVM_UNLIKELY(discardNestedIfBlock(ifNode->getBody()))) {
    477                 Statement * nested = ifNode->getBody()->front();
     427            // Process the Branch body
     428            redundancyElimination(br->getBody(), &expressions, &variables);
     429
     430            // Check whether this If branch has enough operations nested within it to
     431            // be worth the cost of the branch.
     432            if (LLVM_UNLIKELY(isa<If>(br) && discardNestedIfBlock(br->getBody()))) {
     433                Statement * nested = br->getBody()->front();
    478434                while (nested) {
    479435                    Statement * next = nested->removeFromParent();
    480                     if (isa<Assign>(nested)) {
    481                         ifNode->removeDefined(cast<Assign>(nested));
    482                     }
    483436                    nested->insertAfter(stmt);
    484437                    stmt = nested;
    485438                    nested = next;
    486439                }
    487                 stmt = ifNode->eraseFromParent();
     440                stmt = br->eraseFromParent();
    488441                continue;
    489442            }
    490443
    491         } else if (While * whileNode = dyn_cast<While>(stmt)) {
    492             // Test whether we can ever take this branch
    493             const PabloAST * initial = cast<While>(stmt)->getCondition();
    494             if (LLVM_LIKELY(isa<Next>(initial))) {
    495                 initial = cast<Next>(initial)->getInitial();
    496             }
    497             if (LLVM_UNLIKELY(isa<Zeroes>(initial))) {
    498                 stmt = stmt->eraseFromParent();
    499                 continue;
    500             }
    501             redundancyElimination(function, whileNode->getBody(), &encountered);
    502             removeIdenticalEscapedValues(whileNode->getVariants());
    503             // If the condition's Next state is Zero, we can eliminate the loop after copying the internal
    504             // statements into the body.
    505444        } else {
     445
     446            // demote any uses of a Var whose value is in scope
     447            for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
     448                PabloAST * op = stmt->getOperand(i);
     449                if (isa<Var>(op)) {
     450                    PabloAST * const value = variables.get(cast<Var>(op));
     451                    if (value) {
     452                        stmt->setOperand(i, value);
     453                    }
     454                }
     455            }
     456
    506457            Statement * const prior = stmt->getPrevNode();
    507458            PabloAST * const folded = fold(stmt, block);
     
    513464                continue;
    514465            }
    515             // When we're creating the Pablo program, it's possible to have multiple instances of an "identical"
    516             // statement. By recording which statements have already been seen, we can detect the redundant statements
     466            // By recording which statements have already been seen, we can detect the redundant statements
    517467            // as any having the same type and operands. If so, we can replace its users with the prior statement.
    518468            // and erase this statement from the AST
    519             const auto f = encountered.findOrAdd(stmt);
     469            const auto f = expressions.findOrAdd(stmt);
    520470            if (!f.second) {
    521471                stmt = stmt->replaceWith(f.first, true);
     
    524474
    525475        }
     476
    526477        stmt = stmt->getNextNode();
    527478    }
    528 }
    529 
    530 /** ------------------------------------------------------------------------------------------------------------- *
    531  * @brief unused
    532  ** ------------------------------------------------------------------------------------------------------------- */
    533 inline static bool unused(const Statement * const stmt) {
    534     if (LLVM_UNLIKELY(stmt->getNumUses() == 0)) {
    535         // TODO: prototypes ought to state whether they have side effects.
    536         if (LLVM_UNLIKELY(isa<Call>(stmt) && cast<Call>(stmt)->getPrototype()->getNumOfResults() == 0)) {
    537             return false;
    538         }
    539         return true;
    540     }
    541     return false;
     479
     480    // If this block has a branch statement leading into it, we can verify whether an escaped value
     481    // was updated within this block and update the preceeding block's variable state appropriately.
     482
     483    if (Branch * const br = block->getBranch()) { assert (vt);
     484
     485        // When removing identical escaped values, we have to consider that the identical Vars could
     486        // be assigned new differing values later in the outer body. Thus instead of replacing them
     487        // directly, we map future uses of the duplicate Var to the initial one. The DCE pass will
     488        // later mark any Assign statement as dead if the Var is never read.
     489
     490        const auto escaped = br->getEscaped();
     491        const auto n = escaped.size();
     492        PabloAST * variable[n];
     493        PabloAST * incoming[n];
     494        PabloAST * outgoing[n];
     495
     496        size_t i = 0;
     497        for (Var * var : escaped) {
     498            incoming[i] = vt->get(var);
     499            outgoing[i] = variables.get(var);
     500            PabloAST * expr = var;
     501            if (LLVM_UNLIKELY(incoming[i] == outgoing[i])) {
     502                expr = incoming[i];
     503            } else {
     504                for (size_t j = 0; j != i; ++j) {
     505                    if ((outgoing[j] == outgoing[i]) && (incoming[j] == incoming[i])) {
     506                        expr = variable[j];
     507                        break;
     508                    }
     509                }
     510            }
     511            variable[i] = expr;
     512            vt->put(var, expr);
     513            ++i;
     514        }
     515    }
    542516}
    543517
     
    545519 * @brief deadCodeElimination
    546520 ** ------------------------------------------------------------------------------------------------------------- */
    547 void Simplifier::dce(PabloBlock * const block) {
     521void Simplifier::deadCodeElimination(PabloBlock * const block) {
     522
     523   flat_map<PabloAST *, Assign *> unread;
     524
    548525    Statement * stmt = block->front();
    549526    while (stmt) {
    550         if (LLVM_UNLIKELY(isa<If>(stmt))) {
    551             dce(cast<If>(stmt)->getBody());
    552         } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
    553             dce(cast<While>(stmt)->getBody());
    554         } else if (LLVM_UNLIKELY(unused(stmt))){
     527        if (unread.size() != 0) {
     528            for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
     529                PabloAST * const op = stmt->getOperand(i);
     530                if (LLVM_UNLIKELY(isa<Var>(op))) {
     531                    unread.erase(op);
     532                }
     533            }
     534        }
     535        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     536            Branch * const br = cast<Branch>(stmt);
     537            deadCodeElimination(br->getBody());
     538        } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     539            // An Assign statement is locally dead whenever its variable is not read
     540            // before being reassigned a value.
     541            PabloAST * var = cast<Assign>(stmt)->getVariable();
     542            auto f = unread.find(var);
     543            if (f != unread.end()) {
     544                auto prior = f->second;
     545                prior->eraseFromParent(true);
     546                f->second = cast<Assign>(stmt);
     547            } else {
     548                unread.emplace(var, cast<Assign>(stmt));
     549            }
     550        } else if (LLVM_UNLIKELY(stmt->getNumUses() == 0)) {
    555551            stmt = stmt->eraseFromParent(true);
    556552            continue;
     
    558554        stmt = stmt->getNextNode();
    559555    }
     556}
     557
     558/** ------------------------------------------------------------------------------------------------------------- *
     559 * @brief deadCodeElimination
     560 ** ------------------------------------------------------------------------------------------------------------- */
     561void Simplifier::deadCodeElimination(PabloFunction & f) {
     562
     563    deadCodeElimination(f.getEntryBlock());
     564
     565    for (unsigned i = 0; i < f.getNumOfVariables(); ++i) {
     566        Var * var = f.getVariable(i);
     567        bool unused = true;
     568        for (PabloAST * user : var->users()) {
     569            if (isa<Assign>(user)) {
     570                if (cast<Assign>(user)->getValue() == var) {
     571                    unused = false;
     572                    break;
     573                }
     574            } else {
     575                unused = false;
     576                break;
     577            }
     578        }
     579        if (LLVM_UNLIKELY(unused)) {
     580            for (PabloAST * user : var->users()) {
     581                cast<Assign>(user)->eraseFromParent(true);
     582            }
     583        }
     584    }
     585
    560586}
    561587
     
    568594    Statement * stmt = block->front();
    569595    while (stmt) {
    570         if (isa<If>(stmt)) {
    571             strengthReduction(cast<If>(stmt)->getBody());
    572         } else if (isa<While>(stmt)) {
    573             strengthReduction(cast<While>(stmt)->getBody());
     596        if (isa<Branch>(stmt)) {
     597            strengthReduction(cast<Branch>(stmt)->getBody());
    574598        } else if (isa<Advance>(stmt)) {
    575599            Advance * adv = cast<Advance>(stmt);
     
    591615                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
    592616                    block->setInsertPoint(scanThru->getPrevNode());
    593                     PabloAST * expr = block->createAdvance(op->getOperand(0), op->getAmount() - 1);
     617                    PabloAST * expr = block->createAdvance(op->getOperand(0), block->getInteger(op->getAmount() - 1));
    594618                    scanThru->setOperand(0, expr);
    595619                    scanThru->setOperand(1, block->createOr(scanThru->getOperand(1), expr));
     
    619643 ** ------------------------------------------------------------------------------------------------------------- */
    620644bool Simplifier::optimize(PabloFunction & function) {
    621     redundancyElimination(function, function.getEntryBlock());
     645    redundancyElimination(function.getEntryBlock());
    622646    strengthReduction(function.getEntryBlock());
    623     dce(function.getEntryBlock());
     647    deadCodeElimination(function);
    624648    #ifndef NDEBUG
    625649    PabloVerifier::verify(function, "post-simplification");
Note: See TracChangeset for help on using the changeset viewer.