Changeset 4774


Ignore:
Timestamp:
Sep 16, 2015, 2:51:23 PM (3 years ago)
Author:
nmedfort
Message:

Minor revisions.

Location:
icGREP/icgrep-devel/icgrep
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/icgrep.cpp

    r4770 r4774  
    244244#ifdef ENABLE_MULTIPLEXING
    245245    pablo::BDDMinimizationPass::optimize(*function);
    246     if (EnableMultiplexing) {
    247         pablo::AutoMultiplexing::optimize(*function);
    248     }
     246//    if (EnableMultiplexing) {
     247//        pablo::AutoMultiplexing::optimize(*function);
     248//    }
    249249    pablo::BooleanReassociationPass::optimize(*function);
    250250#endif
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

    r4773 r4774  
    287287 * @brief createTree
    288288 ** ------------------------------------------------------------------------------------------------------------- */
    289 static PabloAST * createTree(PabloBlock & block, const Vertex u, Graph & G) {
     289static PabloAST * createTree(PabloBlock & block, const Vertex u, Graph & G, const flat_map<const PabloAST *, unsigned> & writtenAt) {
    290290    flat_set<PabloAST *> sources;
    291291    for (const auto e : make_iterator_range(in_edges(u, G))) {
     
    295295    }
    296296    circular_buffer<PabloAST *> Q(sources.begin(), sources.end());
     297    // Sort the queue in order of how the inputs were written
     298    std::sort(Q.begin(), Q.end(), [&writtenAt](const PabloAST * const e1, const PabloAST * const e2) -> bool {
     299        const auto f1 = writtenAt.find(e1);
     300        const unsigned v1 = (f1 == writtenAt.end()) ? 0 : f1->second;
     301        const auto f2 = writtenAt.find(e2);
     302        const unsigned v2 = (f2 == writtenAt.end()) ? 0 : f2->second;
     303        return v1 < v2;
     304    });
     305
    297306    const TypeId typeId = std::get<0>(G[u]);
    298307    while (Q.size() > 1) {
     
    321330 * @brief processScope
    322331 ** ------------------------------------------------------------------------------------------------------------- */
    323 inline void BooleanReassociationPass::processScope(PabloFunction & function, PabloBlock & block) {
     332inline void BooleanReassociationPass::processScope(PabloFunction &, PabloBlock & block) {
    324333    Graph G;
    325334    summarizeAST(block, G);
    326335    redistributeAST(block, G);
    327     mergeAndWrite(block, G);
    328 }
    329 
    330 /** ------------------------------------------------------------------------------------------------------------- *
    331  * @brief mergeAndWrite
    332  ** ------------------------------------------------------------------------------------------------------------- */
    333 void BooleanReassociationPass::mergeAndWrite(PabloBlock & block, Graph & G) {
     336    rewriteAST(block, G);
     337}
     338
     339/** ------------------------------------------------------------------------------------------------------------- *
     340 * @brief rewriteAST
     341 ** ------------------------------------------------------------------------------------------------------------- */
     342void BooleanReassociationPass::rewriteAST(PabloBlock & block, Graph & G) {
    334343
    335344    circular_buffer<Vertex> Q(num_vertices(G));
     
    337346    block.setInsertPoint(nullptr);
    338347
    339     flat_set<PabloAST *> alreadyWritten;
    340 
     348    unsigned index = 0;
     349    flat_map<const PabloAST *, unsigned> writtenAt;
    341350    while (!Q.empty()) {
    342351        const Vertex u = Q.back(); Q.pop_back();
     
    344353            Statement * stmt = nullptr;
    345354            if (isOptimizable(G[u])) {
    346                 PabloAST * replacement = createTree(block, u, G);
     355                PabloAST * replacement = createTree(block, u, G, writtenAt);
    347356                if (LLVM_LIKELY(inCurrentBlock(replacement, block))) {
    348357                    stmt = cast<Statement>(replacement);
     
    355364            }
    356365            assert (stmt);
    357             assert (inCurrentBlock(stmt, block));
     366            assert (inCurrentBlock(stmt, block));           
     367            for (auto e : make_iterator_range(out_edges(u, G))) {
     368                if (G[e] && G[e] != stmt) {
     369                    PabloAST * expr = std::get<1>(G[target(e, G)]);
     370                    if (expr) { // processing a yet-to-be created value
     371                        cast<Statement>(expr)->replaceUsesOfWith(G[e], stmt);
     372                    }
     373                }
     374            }
    358375            // make sure that optimization doesn't reduce this to an already written statement
    359             if (alreadyWritten.insert(stmt).second) {
    360                 for (auto e : make_iterator_range(out_edges(u, G))) {
    361                     if (G[e] && G[e] != stmt) {
    362                         PabloAST * expr = std::get<1>(G[target(e, G)]);
    363                         if (expr) { // processing a yet-to-be created value
    364                             cast<Statement>(expr)->replaceUsesOfWith(G[e], stmt);
    365                         }
    366                     }
    367                 }
    368                 block.insert(stmt);
    369             }
    370         }
    371     }
    372 }
    373 
    374 /** ------------------------------------------------------------------------------------------------------------- *
    375  * @brief getVertex
    376  ** ------------------------------------------------------------------------------------------------------------- */
    377 static inline Vertex getVertex(PabloAST * expr, Graph & G, Map & M, const PabloBlock & block) {
    378     const auto f = M.find(expr);
    379     if (f != M.end()) {
    380         return f->second;
    381     }
    382     // To simplify future analysis, every statement not in the current block will be recorded as a Var.
    383     const TypeId typeId = inCurrentBlock(expr, block) ? expr->getClassTypeId() : TypeId::Var;
    384     const auto u = add_vertex(std::make_pair(typeId, expr), G);
    385     M.insert(std::make_pair(expr, u));
    386     return u;
     376            if (writtenAt.count(stmt)) {
     377                continue;
     378            }
     379            writtenAt.emplace(stmt, ++index);
     380            block.insert(stmt);
     381        }
     382    }
    387383}
    388384
     
    397393    // Compute the base def-use graph ...
    398394    for (Statement * stmt : block) {
    399         const Vertex u = getVertex(stmt, G, M, block);
     395        const Vertex u = getSummaryVertex(stmt, G, M, block);
    400396        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    401397            PabloAST * const op = stmt->getOperand(i);
     
    403399                continue;
    404400            }
    405             const Vertex v = getVertex(op, G, M, block);
     401            const Vertex v = getSummaryVertex(op, G, M, block);
    406402            add_edge(op, v, u, G);
    407403            // If this operand is a Not operation that is not in this PabloBlock,
     
    409405            if (LLVM_UNLIKELY(isa<Not>(op) && !inCurrentBlock(cast<Not>(op), block))) {
    410406                PabloAST * const negatedValue = cast<Not>(op)->getExpr();
    411                 add_edge(negatedValue, getVertex(negatedValue, G, M, block), v, G);
     407                add_edge(negatedValue, getSummaryVertex(negatedValue, G, M, block), v, G);
    412408            }
    413409        }
    414410        if (isa<If>(stmt)) {
    415411            for (Assign * def : cast<const If>(stmt)->getDefined()) {
    416                 const Vertex v = getVertex(def, G, M, block);
     412                const Vertex v = getSummaryVertex(def, G, M, block);
    417413                add_edge(def, u, v, G);
    418414                resolveUsages(v, def, block, G, M, stmt);
     
    424420            // the Next node dependent on the loop.
    425421            for (Next * var : cast<const While>(stmt)->getVariants()) {
    426                 const Vertex v = getVertex(var, G, M, block);
     422                const Vertex v = getSummaryVertex(var, G, M, block);
    427423                assert (in_degree(v, G) == 1);
    428424                add_edge(nullptr, source(first(in_edges(v, G)), G), u, G);
     
    463459                        }
    464460                        // Add in a Var denoting the user of this expression so that it can be updated if expr changes.
    465                         const Vertex v = getVertex(user, G, M, block);                       
     461                        const Vertex v = getSummaryVertex(user, G, M, block);
    466462                        add_edge(expr, u, v, G);
    467463
    468                         const Vertex w = getVertex(branch, G, M, block);
     464                        const Vertex w = getSummaryVertex(branch, G, M, block);
    469465                        add_edge(nullptr, v, w, G);
    470466                        break;
     
    689685 * @brief removeUnhelpfulBicliques
    690686 *
    691  * An intermediary vertex could have more than one outgoing edge but if any edge is not directed to a vertex in our
    692  * biclique, we'll need to compute that specific value anyway. Remove them from the clique set and if there are not
    693  * enough vertices in the biclique to make distribution profitable, eliminate the clique.
     687 * An intermediary vertex could have more than one outgoing edge but if any that are not directed to vertices in
     688 * the lower biclique, we'll need to compute that specific value anyway. Remove them from the clique set and if
     689 * there are not enough vertices in the biclique to make distribution profitable, eliminate the clique.
    694690 ** ------------------------------------------------------------------------------------------------------------- */
    695691static BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques, const Graph & G, DistributionGraph & H) {
     
    875871}
    876872
    877 }
     873/** ------------------------------------------------------------------------------------------------------------- *
     874 * @brief getVertex
     875 ** ------------------------------------------------------------------------------------------------------------- */
     876Vertex BooleanReassociationPass::getSummaryVertex(PabloAST * expr, Graph & G, Map & M, const PabloBlock & block) {
     877    const auto f = M.find(expr);
     878    if (f != M.end()) {
     879        return f->second;
     880    }
     881    // To simplify future analysis, every statement not in the current block will be recorded as a Var.
     882    const TypeId typeId = inCurrentBlock(expr, block) ? expr->getClassTypeId() : TypeId::Var;
     883    const auto u = add_vertex(std::make_pair(typeId, expr), G);
     884    M.insert(std::make_pair(expr, u));
     885    return u;
     886}
     887
     888}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r4773 r4774  
    2323    void processScopes(PabloFunction & function);
    2424    void processScopes(PabloFunction & function, PabloBlock & block);
    25     void processScope(PabloFunction & function, PabloBlock & block);
     25    void processScope(PabloFunction &, PabloBlock & block);
    2626    void summarizeAST(PabloBlock & block, Graph & G) const;
    2727    static void summarizeGraph(const PabloBlock & block, Graph & G, std::vector<Vertex> & mapping);
    2828    void resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, Statement * ignoreIfThis = nullptr) const;
    2929    void redistributeAST(const PabloBlock & block, Graph & G) const;
    30     void mergeAndWrite(PabloBlock & block, Graph & G);
     30    void rewriteAST(PabloBlock & block, Graph & G);
    3131public:
    3232    static bool isOptimizable(const VertexData & data);
     
    3434    static bool isNonEscaping(const VertexData & data);
    3535    static bool isSameType(const VertexData & data1, const VertexData & data2);
     36    static Vertex getSummaryVertex(PabloAST * expr, Graph & G, Map & M, const PabloBlock & block);
    3637private:
    3738    boost::container::flat_map<PabloBlock *, Statement *> mResolvedScopes;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.cpp

    r4772 r4774  
    2626bool BDDMinimizationPass::optimize(PabloFunction & function) {
    2727    BDDMinimizationPass am;
     28    am.initialize(function);
    2829    am.eliminateLogicallyEquivalentStatements(function);
     30
    2931    am.shutdown();
    3032    return Simplifier::optimize(function);
     
    3335/** ------------------------------------------------------------------------------------------------------------- *
    3436 * @brief initialize
    35  * @param vars the input vars for this program
    36  * @param entry the entry block
    3737 *
    3838 * Scan through the program to identify any advances and calls then initialize the BDD engine with
    3939 * the proper variable ordering.
    4040 ** ------------------------------------------------------------------------------------------------------------- */
    41 void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloFunction & function) {
     41void BDDMinimizationPass::initialize(PabloFunction & function) {
    4242
    4343    std::stack<Statement *> scope;
     
    6060                case TypeId::MatchStar:
    6161                case TypeId::ScanThru:
    62                     variableCount++;
    63                     break;                                   
     62                    ++variableCount;
     63                    break;
     64                case TypeId::Next:
     65                    if (escapes(stmt)) {
     66                        ++variableCount;
     67                    }
    6468                default:
    6569                    break;
     
    8690        mCharacterizationMap[function.getParameter(i)] = NewVar(function.getParameter(i));
    8791    }
    88 
     92    Cudd_SetSiftMaxVar(mManager, 1000000);
     93    Cudd_SetSiftMaxSwap(mManager, 1000000000);
     94    Cudd_AutodynEnable(mManager, CUDD_REORDER_LAZY_SIFT);
     95}
     96
     97/** ------------------------------------------------------------------------------------------------------------- *
     98 * @brief eliminateLogicallyEquivalentStatements
     99 ** ------------------------------------------------------------------------------------------------------------- */
     100void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloFunction & function) {
    89101    SubsitutionMap baseMap;
    90102    baseMap.insert(Zero(), function.getEntryBlock().createZeroes());
    91103    baseMap.insert(One(), function.getEntryBlock().createOnes());
    92 
    93     Cudd_SetSiftMaxVar(mManager, 1000000);
    94     Cudd_SetSiftMaxSwap(mManager, 1000000000);
    95     Cudd_AutodynEnable(mManager, CUDD_REORDER_LAZY_SIFT);
    96 
    97104    eliminateLogicallyEquivalentStatements(function.getEntryBlock(), baseMap);
    98105}
    99106
    100107/** ------------------------------------------------------------------------------------------------------------- *
    101  * @brief characterize
    102  * @param vars the input vars for this program
    103  *
    104  * Scan through the program and iteratively compute the BDDs for each statement.
     108 * @brief eliminateLogicallyEquivalentStatements
    105109 ** ------------------------------------------------------------------------------------------------------------- */
    106110void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent) {
     
    111115            eliminateLogicallyEquivalentStatements(cast<If>(stmt)->getBody(), map);
    112116            for (Assign * def : cast<const If>(stmt)->getDefined()) {
     117                // Any defined variable that wasn't used outside of the If scope would have
     118                // been demoted by the Simplifier pass.
    113119                map.insert(mCharacterizationMap[def], def);
    114120            }
     
    116122            eliminateLogicallyEquivalentStatements(cast<While>(stmt)->getBody(), map);
    117123            for (Next * var : cast<const While>(stmt)->getVariants()) {
    118                 map.insert(mCharacterizationMap[var], var);
     124                if (escapes(var)) {
     125                    map.insert(NewVar(var), var);
     126                } else { // we don't need to retain the BDD for this variant
     127                    Cudd_RecursiveDeref(mManager, mCharacterizationMap[var]);
     128                    mCharacterizationMap.erase(var);
     129                }
    119130            }
    120131        } else { // attempt to characterize this statement and replace it if we've encountered an equivalent one
     
    228239
    229240inline DdNode * BDDMinimizationPass::And(DdNode * const x, DdNode * const y) {
    230     DdNode * r = Cudd_bddAnd(mManager, x, y);
    231     return r;
    232 }
    233 
    234 inline DdNode * BDDMinimizationPass::Intersect(DdNode * const x, DdNode * const y) {
    235     DdNode * r = Cudd_bddIntersect(mManager, x, y); Cudd_Ref(r);
    236     return r;
     241    return Cudd_bddAnd(mManager, x, y);
    237242}
    238243
    239244inline DdNode * BDDMinimizationPass::Or(DdNode * const x, DdNode * const y) {
    240     DdNode * r = Cudd_bddOr(mManager, x, y);
    241     return r;
     245    return Cudd_bddOr(mManager, x, y);
    242246}
    243247
    244248inline DdNode * BDDMinimizationPass::Xor(DdNode * const x, DdNode * const y) {
    245     DdNode * r = Cudd_bddXor(mManager, x, y);
    246     return r;
     249    return Cudd_bddXor(mManager, x, y);
    247250}
    248251
     
    252255
    253256inline DdNode * BDDMinimizationPass::Ite(DdNode * const x, DdNode * const y, DdNode * const z) {
    254     DdNode * r = Cudd_bddIte(mManager, x, y, z);
    255     return r;
     257    return Cudd_bddIte(mManager, x, y, z);
    256258}
    257259
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.h

    r4771 r4774  
    4343    static bool optimize(PabloFunction & function);
    4444protected:
     45    void initialize(PabloFunction & function);
    4546    void eliminateLogicallyEquivalentStatements(PabloFunction & function);
    4647    void eliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4764 r4774  
    6565}
    6666
     67inline bool demoteDefinedVar(const If * ifNode, const Assign * def) {
     68    // If this value isn't used outside of this scope then there is no reason to allow it to escape it.
     69    if (!escapes(def) || (ifNode->getCondition() == def->getExpression())) {
     70        return true;
     71    }
     72    // Similarly if the defined variable is equivalent to the condition, an equivalent value is already available.
     73    if (ifNode->getCondition() == def->getExpression()) {
     74        return true;
     75    }
     76    // Finally, if the assignment is a constant Zero or One, it's already known.
     77    if (isa<Zeroes>(def->getExpression()) || isa<Ones>(def->getExpression()))  {
     78        return true;
     79    }
     80    return false;
     81}
     82
    6783void Simplifier::eliminateRedundantCode(PabloBlock & block, ExpressionTable * predecessor) {
    6884    ExpressionTable encountered(predecessor);
     
    107123                for (auto itr = defs.begin(); itr != defs.end(); ) {
    108124                    Assign * def = *itr;
    109                     // If this value isn't used outside of this scope then there is no reason to allow it to escape it.
    110                     bool unusedOutsideOfNestedScope = true;
    111                     for (PabloAST * user : def->users()) {
    112                         if (user != ifNode) {
    113                             PabloBlock * parent = cast<Statement>(user)->getParent();
    114                             while (parent && parent != def->getParent()) {
    115                                 parent = parent->getParent();
    116                             }
    117                             if (parent == nullptr) {
    118                                 unusedOutsideOfNestedScope = false;
    119                                 break;
    120                             }
    121                         }
    122                     }
    123                     // If the defined variable is actually equivalent to the condition, promote the assignment out of If
    124                     // scope and remove it from the list of defined variables. Additionally, replace any defined variable
    125                     // assigned Zero or One with the appropriate constant and remove it from the defined variable list.
    126                     if (LLVM_UNLIKELY(unusedOutsideOfNestedScope || (ifNode->getCondition() == def->getExpression()) || isa<Zeroes>(def->getExpression()) || isa<Ones>(def->getExpression()))) {
     125                    if (LLVM_UNLIKELY(demoteDefinedVar(ifNode, def))) {
    127126                        itr = defs.erase(itr);
    128                         def->replaceWith(def->getExpression(), unusedOutsideOfNestedScope, true);
     127                        def->replaceWith(def->getExpression(), false, true);
    129128                        evaluate = true;
    130129                        continue;
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4750 r4774  
    290290}
    291291
    292 }
     292/** ------------------------------------------------------------------------------------------------------------- *
     293 * @brief escapes
     294 *
     295 * Is this statement used outside of its scope?
     296 ** ------------------------------------------------------------------------------------------------------------- */
     297bool escapes(const Statement * statement) {
     298    const PabloBlock * const parent = statement->getParent();
     299    for (const PabloAST * user : statement->users()) {
     300        if (LLVM_LIKELY(isa<Statement>(user))) {
     301            const PabloBlock * used = cast<Statement>(user)->getParent();
     302            while (used != parent) {
     303                used = used->getParent();
     304                if (used == nullptr) {
     305                    assert (isa<Assign>(statement) || isa<Next>(statement));
     306                    return true;
     307                }
     308            }
     309        }
     310    }
     311    return false;
     312}
     313
     314}
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r4718 r4774  
    257257};
    258258
     259bool escapes(const Statement * statement);
     260
    259261class StatementList {
    260262    friend class Statement;
Note: See TracChangeset for help on using the changeset viewer.