Changeset 4887


Ignore:
Timestamp:
Dec 1, 2015, 10:22:46 PM (3 years ago)
Author:
nmedfort
Message:

Incorporated n-ary coalescing into DistributivePass?.

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

Legend:

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

    r4886 r4887  
    44#include <pablo/analysis/pabloverifier.hpp>
    55#include <pablo/optimizers/pablo_simplifier.hpp>
     6#include <pablo/passes/flattenassociativedfg.h>
    67#include <boost/container/flat_set.hpp>
    78#include <boost/container/flat_map.hpp>
     
    300301
    301302/** ------------------------------------------------------------------------------------------------------------- *
     303 * @brief process
     304 ** ------------------------------------------------------------------------------------------------------------- */
     305inline void DistributivePass::process(PabloBlock * const block) {
     306
     307    for (;;) {
     308
     309        FlattenAssociativeDFG::coalesce(block, false);
     310
     311        Graph G;
     312
     313        const VertexSet distSet = generateDistributionGraph(block, G);
     314
     315        // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
     316        if (LLVM_UNLIKELY(distSet.empty())) {
     317            break;
     318        }
     319
     320        const DistributionSets distributionSets = safeDistributionSets(G, distSet);
     321
     322        if (LLVM_UNLIKELY(distributionSets.empty())) {
     323            break;
     324        }
     325
     326        for (const DistributionSet & set : distributionSets) {
     327
     328            // Each distribution tuple consists of the sources, intermediary, and sink nodes.
     329            const VertexSet & sources = std::get<0>(set);
     330            const VertexSet & intermediary = std::get<1>(set);
     331            const VertexSet & sinks = std::get<2>(set);
     332
     333            // Find the first sink and set the insert point immediately before that.
     334            Variadic * innerOp = nullptr;
     335            Variadic * outerOp = nullptr;
     336
     337            block->setInsertPoint(cast<Variadic>(G[sinks.front()])->getPrevNode());
     338            if (isa<And>(G[sinks.front()])) {
     339                outerOp = block->createAnd(intermediary.size());
     340                innerOp = block->createOr(sources.size() + 1);
     341            } else {
     342                outerOp = block->createOr(intermediary.size());
     343                innerOp = block->createAnd(sources.size() + 1);
     344            }
     345
     346            for (const Vertex u : intermediary) {
     347                for (const Vertex v : sinks) {
     348                    cast<Variadic>(G[v])->deleteOperand(G[u]);
     349                }
     350                outerOp->addOperand(G[u]);
     351            }
     352
     353            for (const Vertex u : sources) {
     354                for (const Vertex v : intermediary) {
     355                    cast<Variadic>(G[v])->deleteOperand(G[u]);
     356                }
     357                innerOp->addOperand(G[u]);
     358            }
     359            innerOp->addOperand(outerOp);
     360
     361            for (const Vertex u : sinks) {
     362                cast<Variadic>(G[u])->addOperand(innerOp);
     363            }
     364        }
     365
     366    }
     367}
     368
     369/** ------------------------------------------------------------------------------------------------------------- *
    302370 * @brief distribute
    303371 ** ------------------------------------------------------------------------------------------------------------- */
    304 inline bool DistributivePass::distribute(PabloBlock * const block) {
    305 
    306     Graph G;
    307 
    308     const VertexSet distSet = generateDistributionGraph(block, G);
    309 
    310     // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
    311     if (LLVM_UNLIKELY(distSet.empty())) {
    312         return false;
    313     }
    314 
    315     const DistributionSets distributionSets = safeDistributionSets(G, distSet);
    316 
    317     if (LLVM_UNLIKELY(distributionSets.empty())) {
    318         return false;
    319     }
    320 
    321     for (const DistributionSet & set : distributionSets) {
    322 
    323         // Each distribution tuple consists of the sources, intermediary, and sink nodes.
    324         const VertexSet & sources = std::get<0>(set);
    325         const VertexSet & intermediary = std::get<1>(set);
    326         const VertexSet & sinks = std::get<2>(set);
    327 
    328         // Find the first sink and set the insert point immediately before that.
    329         Variadic * innerOp = nullptr;
    330         Variadic * outerOp = nullptr;
    331 
    332         block->setInsertPoint(cast<Variadic>(G[sinks.front()])->getPrevNode());
    333         if (isa<And>(G[sinks.front()])) {
    334             outerOp = block->createAnd(intermediary.size());
    335             innerOp = block->createOr(sources.size() + 1);
    336         } else {
    337             outerOp = block->createOr(intermediary.size());
    338             innerOp = block->createAnd(sources.size() + 1);
    339         }
    340 
    341         for (const Vertex u : intermediary) {
    342             for (const Vertex v : sinks) {
    343                 cast<Variadic>(G[v])->deleteOperand(G[u]);
    344             }
    345             outerOp->addOperand(G[u]);
    346         }
    347 
    348         for (const Vertex u : sources) {
    349             for (const Vertex v : intermediary) {
    350                 cast<Variadic>(G[v])->deleteOperand(G[u]);
    351             }
    352             innerOp->addOperand(G[u]);
    353         }
    354         innerOp->addOperand(outerOp);
    355 
    356         for (const Vertex u : sinks) {
    357             cast<Variadic>(G[u])->addOperand(innerOp);
    358         }
    359     }
    360 
    361     return true;
    362 }
    363 
    364 /** ------------------------------------------------------------------------------------------------------------- *
    365  * @brief process
    366  ** ------------------------------------------------------------------------------------------------------------- */
    367 bool DistributivePass::process(PabloBlock * const block) {
    368     bool modified = false;
     372void DistributivePass::distribute(PabloBlock * const block) {
    369373    for (Statement * stmt : *block) {
    370374        if (isa<If>(stmt) || isa<While>(stmt)) {
    371             modified |= process(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    372         }
    373     }
    374     modified |= distribute(block);
    375     return modified;
    376 }
    377 
    378 /** ------------------------------------------------------------------------------------------------------------- *
    379  * @brief process
    380  ** ------------------------------------------------------------------------------------------------------------- */
    381 bool DistributivePass::optimize(PabloFunction & function) {
    382     const bool modified = DistributivePass::process(function.getEntryBlock());
     375            distribute(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     376        }
     377    }
     378    process(block);
     379}
     380
     381/** ------------------------------------------------------------------------------------------------------------- *
     382 * @brief optimize
     383 ** ------------------------------------------------------------------------------------------------------------- */
     384void DistributivePass::optimize(PabloFunction & function) {
     385    DistributivePass::distribute(function.getEntryBlock());
    383386    #ifndef NDEBUG
    384387    PabloVerifier::verify(function, "post-distribution");
    385388    #endif
    386 
    387389    Simplifier::optimize(function);
    388     return modified;
    389 }
    390 
    391 
    392 }
     390    FlattenAssociativeDFG::deMorgansReduction(function.getEntryBlock());
     391    #ifndef NDEBUG
     392    PabloVerifier::verify(function, "post-demorgans-reduction");
     393    #endif
     394    Simplifier::optimize(function);
     395}
     396
     397
     398}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.h

    r4880 r4887  
    1010class DistributivePass {
    1111public:
    12     static bool optimize(PabloFunction & function);
     12    static void optimize(PabloFunction & function);
    1313protected:
    14     static bool process(PabloBlock * const block);
    15     static bool distribute(PabloBlock * const block);
     14    static void distribute(PabloBlock * const block);
     15    static void process(PabloBlock * const block);
    1616    DistributivePass() = default;
    1717};
  • icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.cpp

    r4886 r4887  
    4242 * @brief coalesce
    4343 ** ------------------------------------------------------------------------------------------------------------- */
    44 void FlattenAssociativeDFG::coalesce(PabloBlock * const block) {
     44void FlattenAssociativeDFG::coalesce(PabloBlock * const block, const bool traverse) {
    4545    Statement * stmt = block->front();
    4646    while (stmt) {
    4747        Statement * next = stmt->getNextNode();
    48         if (isa<If>(stmt) || isa<While>(stmt)) {
    49             coalesce(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     48        if (traverse && (isa<If>(stmt) || isa<While>(stmt))) {
     49            coalesce(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), true);
    5050        } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
    5151            coalesce(cast<Variadic>(stmt));
     
    133133void FlattenAssociativeDFG::transform(PabloFunction & function) {
    134134
    135     FlattenAssociativeDFG::coalesce(function.getEntryBlock());
     135    FlattenAssociativeDFG::coalesce(function.getEntryBlock(), true);
    136136    #ifndef NDEBUG
    137137    PabloVerifier::verify(function, "post-coalescence");
  • icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.h

    r4886 r4887  
    1616    static void transform(PabloFunction & function);
    1717protected:
    18     static void coalesce(PabloBlock * const block);
     18    static void coalesce(PabloBlock * const block, const bool traverse);
    1919    static void coalesce(Variadic * const var);
    2020    static void deMorgansExpansion(Not * const var, PabloBlock * const block);
  • icGREP/icgrep-devel/icgrep/toolchain.cpp

    r4885 r4887  
    4242#include <pablo/optimizers/pablo_automultiplexing.hpp>
    4343#include <pablo/optimizers/pablo_bddminimization.h>
    44 #include <pablo/optimizers/booleanreassociationpass.h>
     44#include <pablo/optimizers/distributivepass.h>
    4545#endif
    4646#include <pablo/function.h>
     
    9292                                         cl::desc("coalesce associative functions prior to optimization passes."),
    9393                                         cl::cat(cPabloOptimizationsOptions));
    94 static cl::opt<bool> EnableReassociation("reassoc", cl::init(false),
    95                                          cl::desc("perform reassocation and distribution law optimization."),
     94static cl::opt<bool> EnableDistribution("dist", cl::init(false),
     95                                         cl::desc("apply distribution law optimization."),
    9696                                         cl::cat(cPabloOptimizationsOptions));
    9797#endif
     
    148148    }
    149149#ifdef ENABLE_MULTIPLEXING
    150     if (EnableLowering || EnableMultiplexing) {
     150    if (EnableLowering || EnableMultiplexing || EnableDistribution) {
    151151        FlattenAssociativeDFG::transform(*function);
    152152    }
     
    157157#ifdef ENABLE_MULTIPLEXING   
    158158    if (EnableMultiplexing) {
    159         // BDDMinimizationPass::optimize(*function);
    160159        AutoMultiplexing::optimize(*function, MultiplexingSetLimit, MultiplexingSelectionLimit);
    161160        FlattenAssociativeDFG::transform(*function);
    162161    }
    163     if (EnableReassociation) {
    164         BooleanReassociationPass::optimize(*function);
    165     }
    166 #endif
    167     if (EnableLowering || EnableMultiplexing) {
     162    if (EnableDistribution) {
     163        DistributivePass::optimize(*function);
     164    }
     165    if (EnableLowering || EnableMultiplexing || EnableDistribution) {
    168166        FactorizeDFG::transform(*function);
    169167    }
     168#endif
    170169    if (PrintOptimizedREcode) {
    171170        //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
Note: See TracChangeset for help on using the changeset viewer.