Ignore:
Timestamp:
Aug 31, 2015, 12:23:17 PM (4 years ago)
Author:
nmedfort
Message:

Removed dummy nodes from the reassociation pass and have edges pointing to the if/while node instead to allow for proper topological ordering.

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

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/CMakeLists.txt

    r4750 r4753  
    102102add_custom_command(OUTPUT ${PRECOMPILED_FILES}
    103103  COMMAND generate_predefined_ucd_functions
    104   ARGS -o ${PRECOMPILED_PROPERTIES_OBJ} -dir ${PROJECT_SOURCE_DIR}/UCD/ ${MULTIPLEXING_FLAG} -DefaultIfHierarchy
     104  ARGS -o ${PRECOMPILED_PROPERTIES_OBJ} -dir ${PROJECT_SOURCE_DIR}/UCD/ ${MULTIPLEXING_FLAG} -ldc=ldc.csv -DefaultIfHierarchy
    105105  DEPENDS generate_predefined_ucd_functions
    106106  COMMENT "Building predefined UCD functions..."
  • icGREP/icgrep-devel/icgrep/generate_predefined_ucd_functions.cpp

    r4750 r4753  
    1818#ifdef ENABLE_MULTIPLEXING
    1919#include <pablo/optimizers/pablo_automultiplexing.hpp>
     20#include <pablo/optimizers/booleanreassociationpass.h>
     21#include <pablo/optimizers/pablo_bddminimization.h>
    2022#endif
    2123#include <llvm/IR/Verifier.h>
     
    273275            (*MultiplexingDistributionFile) << ',' << getNumOfAdvances(function->getEntryBlock());
    274276        }
    275         AutoMultiplexing::optimize(*function);
     277        BDDMinimizationPass::optimize(*function);
     278        // AutoMultiplexing::optimize(*function);
     279        BooleanReassociationPass::optimize(*function);
     280        BDDMinimizationPass::optimize(*function);
    276281        if (MultiplexingDistributionFile) {
    277282            (*MultiplexingDistributionFile) << ',' << getNumOfAdvances(function->getEntryBlock()) << '\n';
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

    r4752 r4753  
    2222using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
    2323
    24 static void summarizeAST(PabloBlock & block, std::vector<Statement *> && terminals, Graph & G);
     24static void redistributeAST(Graph & G);
    2525
    2626/** ------------------------------------------------------------------------------------------------------------- *
     
    2929bool BooleanReassociationPass::optimize(PabloFunction & function) {
    3030    BooleanReassociationPass brp;
    31 //    raw_os_ostream out(std::cerr);
    32 //    out << "BEFORE:\n\n";
    33 //    PabloPrinter::print(function.getEntryBlock().statements(), out);
    34     brp.scan(function);
     31    brp.resolveScopes(function);
     32    brp.processScopes(function);
    3533    Simplifier::optimize(function);
    36 
    37 //    out << "\n\nAFTER:\n\n";
    38 //    PabloPrinter::print(function.getEntryBlock().statements(), out);
    3934    return true;
    4035}
    4136
    4237/** ------------------------------------------------------------------------------------------------------------- *
     38 * @brief resolveScopes
     39 ** ------------------------------------------------------------------------------------------------------------- */
     40inline void BooleanReassociationPass::resolveScopes(PabloFunction &function) {
     41    resolveScopes(function.getEntryBlock());
     42}
     43
     44/** ------------------------------------------------------------------------------------------------------------- *
     45 * @brief resolveScopes
     46 ** ------------------------------------------------------------------------------------------------------------- */
     47void BooleanReassociationPass::resolveScopes(PabloBlock & block) {
     48    for (Statement * stmt : block) {
     49        if (isa<If>(stmt) || isa<While>(stmt)) {
     50            PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     51            mResolvedScopes.emplace(&nested, stmt);
     52            resolveScopes(nested);
     53        }
     54    }
     55}
     56
     57
     58/** ------------------------------------------------------------------------------------------------------------- *
    4359 * @brief scan
    4460 ** ------------------------------------------------------------------------------------------------------------- */
    45 void BooleanReassociationPass::scan(PabloFunction & function) {
     61inline void BooleanReassociationPass::processScopes(PabloFunction & function) {
    4662    std::vector<Statement *> terminals;
    4763    for (unsigned i = 0; i != function.getNumOfResults(); ++i) {
    4864        terminals.push_back(function.getResult(i));
    4965    }
    50     scan(function.getEntryBlock(), std::move(terminals));
     66    processScopes(function.getEntryBlock(), std::move(terminals));
    5167}
    5268
     
    5470 * @brief scan
    5571 ** ------------------------------------------------------------------------------------------------------------- */
    56 void BooleanReassociationPass::scan(PabloBlock & block, std::vector<Statement *> && terminals) {
    57 
     72void BooleanReassociationPass::processScopes(PabloBlock & block, std::vector<Statement *> && terminals) {
    5873    processScope(block, std::move(terminals));
    59 
    6074    for (Statement * stmt : block) {
    6175        if (isa<If>(stmt)) {
    6276            const auto & defs = cast<const If>(stmt)->getDefined();
    6377            std::vector<Statement *> terminals(defs.begin(), defs.end());
    64             scan(cast<If>(stmt)->getBody(), std::move(terminals));
     78            processScopes(cast<If>(stmt)->getBody(), std::move(terminals));
    6579        } else if (isa<While>(stmt)) {
    6680            const auto & vars = cast<const While>(stmt)->getVariants();
    6781            std::vector<Statement *> terminals(vars.begin(), vars.end());
    68             scan(cast<While>(stmt)->getBody(), std::move(terminals));
    69         }
    70     }
    71 
     82            processScopes(cast<While>(stmt)->getBody(), std::move(terminals));
     83        }
     84    }
    7285}
    7386
     
    114127static inline bool inCurrentBlock(const PabloAST * expr, const PabloBlock & block) {
    115128    return isa<Statement>(expr) && inCurrentBlock(cast<Statement>(expr), block);
    116 }
    117 
    118 /** ------------------------------------------------------------------------------------------------------------- *
    119  * @brief isAnyUserNotInCurrentBlock
    120  ** ------------------------------------------------------------------------------------------------------------- */
    121 static inline bool isAnyUserNotInCurrentBlock(const PabloAST * expr, const PabloBlock & block) {
    122     for (PabloAST * user : expr->users()) {
    123         if (!inCurrentBlock(cast<Statement>(user), block)) {
    124             return true;
    125         }
    126     }
    127     return false;
    128129}
    129130
     
    201202
    202203/** ------------------------------------------------------------------------------------------------------------- *
    203  * @brief applyDistributionLaw
    204  ** ------------------------------------------------------------------------------------------------------------- */
    205 static bool applyDistributionLaw(PabloBlock & block, const PabloAST::ClassTypeId typeId, flat_set<PabloAST *> & vars) {
    206     circular_buffer<PabloAST *> Q0(vars.size());
    207     circular_buffer<PabloAST *> Q1(vars.size());
    208     std::vector<PabloAST *> distributedVars;
    209 
    210     for (auto vi = vars.begin(); vi != vars.end(); ) {
    211         PabloAST * const e0 = *vi;
    212 
    213         if (e0->getClassTypeId() == typeId) {
    214             Statement * const s0 = cast<Statement>(e0);
    215 
    216             for (auto vj = vi + 1; vj != vars.end(); ) {
    217                 PabloAST * const e1 = *vj;
    218 
    219                 if (e1->getClassTypeId() == typeId) {
    220                     Statement * const s1 = cast<Statement>(e1);
    221                     bool distributed = false;
    222 
    223                     if (s0->getOperand(0) == s1->getOperand(0)) {
    224                         Q0.push_back(s1->getOperand(1));
    225                         distributed = true;
    226                     } else if (s0->getOperand(0) == s1->getOperand(1)) {
    227                         Q0.push_back(s1->getOperand(0));
    228                         distributed = true;
    229                     }
    230 
    231                     if (s0->getOperand(1) == s1->getOperand(0)) {
    232                         Q1.push_back(s1->getOperand(1));
    233                         distributed = true;
    234                     } else if (s0->getOperand(1) == s1->getOperand(1)) {
    235                         Q1.push_back(s1->getOperand(0));
    236                         distributed = true;
    237                     }
    238 
    239                     if (distributed) {
    240                         vj = vars.erase(vj);
    241                         continue;
    242                     }
    243                 }
    244 
    245                 ++vj;
    246             }
    247 
    248             if (LLVM_UNLIKELY(Q0.size() > 0 || Q1.size() > 0)) {
    249                 const PabloAST::ClassTypeId innerTypeId =
    250                         (typeId == PabloAST::ClassTypeId::Or) ? PabloAST::ClassTypeId::And : PabloAST::ClassTypeId::Or;
    251 
    252                 vi = vars.erase(vi);
    253                 if (Q0.size() > 0) {
    254                     Q0.push_back(s0->getOperand(1));
    255                     PabloAST * distributed = createTree(block, innerTypeId, Q0);
    256                     switch (typeId) {
    257                         case PabloAST::ClassTypeId::And:
    258                             distributed = block.createAnd(s0->getOperand(0), distributed); break;
    259                         case PabloAST::ClassTypeId::Or:
    260                             distributed = block.createOr(s0->getOperand(0), distributed); break;
    261                         default: break;
    262                     }
    263                     distributedVars.push_back(distributed);
    264                 }
    265                 if (Q1.size() > 0) {
    266                     Q1.push_front(s0->getOperand(0));
    267                     PabloAST * distributed = createTree(block, innerTypeId, Q1);
    268                     switch (typeId) {
    269                         case PabloAST::ClassTypeId::And:
    270                             distributed = block.createAnd(s0->getOperand(1), distributed); break;
    271                         case PabloAST::ClassTypeId::Or:
    272                             distributed = block.createOr(s0->getOperand(1), distributed); break;
    273                         default: break;
    274                     }
    275                     distributedVars.push_back(distributed);
    276                 }
    277                 continue;
    278             }
    279         }
    280         ++vi;
    281     }
    282     if (distributedVars.empty()) {
    283         return false;
    284     }
    285     for (PabloAST * var : distributedVars) {
    286         vars.insert(var);
    287     }
    288     return true;
    289 }
    290 
    291 /** ------------------------------------------------------------------------------------------------------------- *
    292204 * @brief processScope
    293205 ** ------------------------------------------------------------------------------------------------------------- */
     
    296208    Graph G;
    297209    summarizeAST(block, std::move(terminals), G);
     210    redistributeAST(G);
    298211
    299212    raw_os_ostream out(std::cerr);
     
    359272 * reassociate them in the most efficient way possible.
    360273 ** ------------------------------------------------------------------------------------------------------------- */
    361 static void summarizeAST(PabloBlock & block, std::vector<Statement *> && terminals, Graph & G) {
     274void BooleanReassociationPass::summarizeAST(PabloBlock & block, std::vector<Statement *> && terminals, Graph & G) {
    362275
    363276    Map M;
     
    453366            if (isOptimizable(Gk[u])) {
    454367                Statement * stmt = cast<Statement>(Gk[u]);
    455                 if (isAnyUserNotInCurrentBlock(stmt, block)) {
    456                     const Vertex v = add_vertex(block.createZeroes(), Gk);
    457                     add_edge(u, v, Gk);
     368                // If any user of this statement is not in the current block, determine the outermost If/While node
     369                // that contains this statement within and add an edge from this statement to it to denote both the
     370                // topological ordering necessary and that this statement must be computed.
     371                for (PabloAST * user : stmt->users()) {
     372                    if (LLVM_LIKELY(isa<Statement>(user))) {
     373                        PabloBlock * parent = cast<Statement>(user)->getParent();
     374                        if (LLVM_UNLIKELY(parent != &block)) {
     375                            while (parent->getParent() != &block) {
     376                                parent = parent->getParent();
     377                            }
     378                            if (LLVM_UNLIKELY(parent == nullptr)) {
     379                                throw std::runtime_error("Could not locate nested scope block!");
     380                            }
     381                            const auto f = mResolvedScopes.find(parent);
     382                            if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
     383                                throw std::runtime_error("Failed to resolve scope block!");
     384                            }
     385                            add_edge(u, getVertex(f->second, Gk, Mk), Gk);
     386                        }
     387                    }
    458388                }
    459389                // Scan through the use-def chains to locate any chains of rearrangable expressions and their inputs
     
    492422                if (out_degree(u, Gk) == 0) {
    493423                    id = ++components;
    494                 } else {
     424                } else { // otherwise it belongs to the outermost component.
    495425                    for (auto e : make_iterator_range(out_edges(u, Gk))) {
    496426                        id = std::max(id, component[target(e, Gk)]);
     
    527457                // in the program. By replicating it, this ensures it's computed as an output of
    528458                // one component and used as an input of another.
    529 
    530459                if (component[u] < component[v]) {
    531460                    std::swap(u, v);
    532461                }
    533462
    534                 // Replicate u and fix the ordering and component vectors to reflect the change in G.
     463                // Replicate u and fix the ordering and component vectors to reflect the change in Gk.
    535464                Vertex w = add_vertex(Gk[u], Gk);
    536465                ordering.insert(std::find(ordering.begin(), ordering.end(), u), w);
     
    540469
    541470                // However, after we do so, we need to make sure the original source vertex will be a
    542                 // sink in G unless it is also an input variable (in which case we'd simply end up with
     471                // sink in Gk unless it is also an input variable (in which case we'd simply end up with
    543472                // extraneous isolated vertex. Otherwise, we need to make further cuts and replications.
    544 
    545473                if (in_degree(u, Gk) != 0) {
    546474                    for (auto e : make_iterator_range(out_edges(u, Gk))) {
     
    559487        for (const Vertex u : ordering) {
    560488            if (LLVM_UNLIKELY(out_degree(u, Gk) == 0)) {
    561                 if (LLVM_UNLIKELY(isa<Zeroes>(Gk[u]))) {
    562                     continue;
    563                 }
     489                // Create a vertex marking the output statement we may end up replacing
     490                // and collect the set of source variables in the component
    564491                const Vertex x = getVertex(Gk[u], G, M);
    565492                if (LLVM_LIKELY(in_degree(u, Gk) > 0)) {
     
    594521            if (LLVM_UNLIKELY(in_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) {
    595522                nextSet.insert(cast<Statement>(Gk[u]));
    596             } else if (LLVM_UNLIKELY(out_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) { // an input may also be the output of a subgraph of G. We don't need to reevaluate it.
     523            } else if (LLVM_UNLIKELY(out_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) {
     524                // some input will also be the output of some subgraph of Gk whenever we cut and
     525                // replicated a vertex. We don't need to reevaluate it as part of the next layer.
    597526                nextSet.erase(cast<Statement>(Gk[u]));
    598527            }
     
    605534        terminals.assign(nextSet.begin(), nextSet.end());
    606535    }
    607 
    608 }
    609 
     536}
     537
     538/** ------------------------------------------------------------------------------------------------------------- *
     539 * @brief redistributeAST
     540 *
     541 * Apply the distribution law to reduce computations whenever possible.
     542 ** ------------------------------------------------------------------------------------------------------------- */
     543static void redistributeAST(Graph & G) {
     544
     545}
     546
     547/** ------------------------------------------------------------------------------------------------------------- *
     548 * @brief applyDistributionLaw
     549 ** ------------------------------------------------------------------------------------------------------------- */
    610550BooleanReassociationPass::BooleanReassociationPass()
    611551{
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r4751 r4753  
    33
    44#include <pablo/codegenstate.h>
     5#include <boost/container/flat_map.hpp>
     6#include <boost/graph/adjacency_list.hpp>
    57
    68namespace pablo {
    79
    8 class BooleanReassociationPass {   
     10class BooleanReassociationPass {
     11    using Graph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, PabloAST *>;
    912public:
    1013    static bool optimize(PabloFunction & function);
    1114protected:
    1215    BooleanReassociationPass();
    13     void scan(PabloFunction & function);
    14     void scan(PabloBlock & block, std::vector<Statement *> && terminals);
     16    void resolveScopes(PabloFunction & function);
     17    void resolveScopes(PabloBlock &block);
     18    void processScopes(PabloFunction & function);
     19    void processScopes(PabloBlock & block, std::vector<Statement *> && terminals);
    1520    void processScope(PabloBlock & block, std::vector<Statement *> && terminals);
     21    void summarizeAST(PabloBlock & block, std::vector<Statement *> && terminals, Graph & G);
     22private:
     23    boost::container::flat_map<PabloBlock *, Statement *> mResolvedScopes;
    1624};
    1725
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4751 r4753  
    163163        am.topologicalSort(function.getEntryBlock());
    164164        RECORD_TIMESTAMP(end_topological_sort);
    165         LOG("TopologicalSort:        " << (end_topological_sort - start_topological_sort));
     165        LOG("TopologicalSort:         " << (end_topological_sort - start_topological_sort));
    166166
    167167        BooleanReassociationPass::optimize(function);
Note: See TracChangeset for help on using the changeset viewer.