Changeset 4922


Ignore:
Timestamp:
Jan 29, 2016, 3:38:47 PM (3 years ago)
Author:
nmedfort
Message:

Incorporated a few common case boolean optimizations in the Simplifier.

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

Legend:

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

    r4920 r4922  
    6666SET(PABLO_SRC ${PABLO_SRC} pablo/analysis/pabloverifier.cpp)
    6767SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/codemotionpass.cpp)
    68 IF (ENABLE_MULTIPLEXING)
     68IF(ENABLE_MULTIPLEXING)
    6969SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/distributivepass.cpp pablo/passes/flattenassociativedfg.cpp pablo/passes/factorizedfg.cpp)
    7070SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/schedulingprepass.cpp pablo/optimizers/pablo_automultiplexing.cpp pablo/optimizers/pablo_bddminimization.cpp)
     
    7676add_library(CCADT cc/cc_compiler.cpp utf8_encoder.cpp UCD/CaseFolding_txt.cpp)
    7777add_library(UCDlib UCD/unicode_set.cpp UCD/ucd_compiler.cpp UCD/PropertyObjects.cpp UCD/resolve_properties.cpp)
    78 
    7978
    8079# add the executable
     
    139138
    140139
    141 IF (ENABLE_MULTIPLEXING)
     140IF(ENABLE_MULTIPLEXING)
    142141message(STATUS "Enabling Multiplexing")
    143142SET(BUDDY_ROOT "${CMAKE_SOURCE_DIR}/../buddy-2.4")
  • icGREP/icgrep-devel/icgrep/IDISA/idisa_builder.h

    r4898 r4922  
    1717namespace IDISA {
    1818
    19     class IDISA_Builder : public IRBuilder<> {
     19class IDISA_Builder : public IRBuilder<> {
    2020public:
    2121
    22         IDISA_Builder(Module * m, Type * bitBlockType) : IRBuilder<>(m->getContext())
     22    IDISA_Builder(Module * m, Type * bitBlockType) : IRBuilder<>(m->getContext())
    2323    , mMod(m)
    2424    , mBitBlockType(bitBlockType)
     
    2929
    3030    }
    31     virtual ~IDISA_Builder() {};
     31    virtual ~IDISA_Builder() {}
    3232   
    3333    Type * getBitBlockType() { return mBitBlockType;}
  • icGREP/icgrep-devel/icgrep/icgrep-devel.files

    r4919 r4922  
    494494pablo/optimizers/schedulingprepass.cpp
    495495papi_helper.hpp
     496kernels/s2p_gen.cpp
     497kernels/scanmatchgen.cpp
     498kernels/s2p_gen.h
     499kernels/scanmatchgen.h
     500IDISA/idisa_builder.cpp
     501IDISA/idisa_sse_builder.h
     502IDISA/idisa_sse_builder.cpp
     503IDISA/idisa_avx_builder.h
     504IDISA/idisa_avx_builder.cpp
     505IDISA/idisa_builder.h
  • icGREP/icgrep-devel/icgrep/icgrep-devel.includes

    r4919 r4922  
    1313pablo/passes
    1414../llvm-build/lib
     15kernels
     16IDISA
  • icGREP/icgrep-devel/icgrep/pablo/carry_manager.cpp

    r4909 r4922  
    1212#include <pablo/carry_manager.h>
    1313#include <pablo/pabloAST.h>
     14#ifdef CARRY_DEBUG
    1415#include <iostream>
     16#endif
    1517#include <llvm/Support/CommandLine.h>
    1618#include <llvm/IR/BasicBlock.h>
     
    2729namespace pablo {
    2830 
    29     unsigned doScopeCount(PabloBlock * pb) {
    30         unsigned count = 1;
    31        
    32         for (Statement * stmt : *pb) {
    33             if (If * ifStatement = dyn_cast<If>(stmt)) {
    34                 count += doScopeCount(ifStatement->getBody());
    35             }
    36             else if (While * whileStatement = dyn_cast<While>(stmt)) {
    37                 count += doScopeCount(whileStatement->getBody());
    38             }
    39         }
    40         return count;
    41        
    42     }
     31unsigned doScopeCount(PabloBlock * pb) {
     32    unsigned count = 1;
     33
     34    for (Statement * stmt : *pb) {
     35        if (If * ifStatement = dyn_cast<If>(stmt)) {
     36            count += doScopeCount(ifStatement->getBody());
     37        }
     38        else if (While * whileStatement = dyn_cast<While>(stmt)) {
     39            count += doScopeCount(whileStatement->getBody());
     40        }
     41    }
     42    return count;
     43
     44}
    4345   
    4446void CarryManager::generateCarryDataInitializer(Module * m) {
     
    7981    unsigned totalPackCount = (totalCarryDataSize + mITEMS_PER_PACK - 1)/mITEMS_PER_PACK;
    8082
    81     mCarryPackPtr.resize(totalPackCount);
    82     mCarryInPack.resize(totalPackCount);
    83     mCarryOutPack.resize(totalPackCount);
    84     for (unsigned i = 0; i < totalPackCount; i++) mCarryInPack[i]=nullptr;
     83    mCarryPackPtr.resize(totalPackCount, nullptr);
     84    mCarryInPack.resize(totalPackCount, nullptr);
     85    mCarryOutPack.resize(totalPackCount, nullptr);
    8586
    8687    if (Strategy == SequentialFullyPackedStrategy) {
     
    133134
    134135unsigned CarryManager::enumerate(PabloBlock * blk, unsigned ifDepth, unsigned whileDepth) {
     136#ifdef CARRY_DEBUG
    135137    llvm::raw_os_ostream cerr(std::cerr);
     138#endif
    136139    unsigned idx = blk->getScopeIndex();
    137140    PabloBlockCarryData * cd = new PabloBlockCarryData(blk, mPACK_SIZE, mITEMS_PER_PACK);
     
    635638    const unsigned carrySummaryIndex = summaryPackIndex();
    636639   
    637     Value * carry_summary = Constant::getNullValue(mCarryPackType);
     640    Value * carry_summary = nullptr;
    638641    if (mCarryInfo->blockHasLongAdvances()) { // Force if entry
    639642        carry_summary = Constant::getAllOnesValue(mCarryPackType);
    640643    }
    641644    else {
     645        carry_summary = Constant::getNullValue(mCarryPackType);
    642646        unsigned localCarryIndex = localBasePack();
    643647        unsigned localCarryPacks = mCarryInfo->getLocalCarryPackCount();
     
    645649            carry_summary = mCarryOutPack[localCarryIndex];
    646650            for (unsigned i = 1; i < localCarryPacks; i++) {
    647                 carry_summary = iBuilder->CreateOr(carry_summary, mCarryOutPack[localCarryIndex+i]);
     651                carry_summary = iBuilder->CreateOr(carry_summary, mCarryOutPack[localCarryIndex + i]);
    648652            }
    649653        }
     654
     655
     656        // iBuilder->SetInsertPoint(&(iBuilder->GetInsertBlock()->back()));
     657
    650658        for (Statement * stmt : *mCurrentScope) {
    651659            if (If * innerIf = dyn_cast<If>(stmt)) {
    652660                PabloBlock * inner_blk = innerIf->getBody();
    653661                enterScope(inner_blk);
    654                 if (blockHasCarries()) {
    655                   carry_summary = iBuilder->CreateOr(carry_summary, mCarryOutPack[summaryPackIndex()]);
     662                if (blockHasCarries()) {                   
     663                    carry_summary = iBuilder->CreateOr(carry_summary, mCarryOutPack[summaryPackIndex()]);
    656664                }
    657665                leaveScope();
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.cpp

    r4919 r4922  
    99#include <boost/graph/adjacency_list.hpp>
    1010
     11#include <pablo/printer_pablos.h>
     12#include <iostream>
     13
    1114using namespace boost;
    1215using namespace boost::container;
     
    1417namespace pablo {
    1518
    16 using DependencyGraph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
    17 using Vertex = DependencyGraph::vertex_descriptor;
    18 using SinkMap = flat_map<PabloAST *, Vertex>;
     19using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
     20using Vertex = Graph::vertex_descriptor;
     21using Map = flat_map<PabloAST *, Vertex>;
    1922using VertexSet = std::vector<Vertex>;
    2023using Biclique = std::pair<VertexSet, VertexSet>;
     
    2225using DistributionSet = std::tuple<VertexSet, VertexSet, VertexSet>;
    2326using DistributionSets = std::vector<DistributionSet>;
    24 
    2527using TypeId = PabloAST::ClassTypeId;
    26 
    27 /** ------------------------------------------------------------------------------------------------------------- *
    28  * @brief getVertex
    29  ** ------------------------------------------------------------------------------------------------------------- */
    30 static inline Vertex getVertex(PabloAST * value, DependencyGraph & G, SinkMap & M) {
    31     const auto f = M.find(value);
    32     if (f != M.end()) {
    33         return f->second;
    34     }
    35     const auto u = add_vertex(value, G);
    36     M.emplace(value, u);
    37     return u;
    38 }
    39 
    40 /** ------------------------------------------------------------------------------------------------------------- *
    41  * @brief generateDistributionGraph
    42  *
    43  * Generate a graph G describing the potential applications of the distributive law for the given block.
    44  ** ------------------------------------------------------------------------------------------------------------- */
    45 VertexSet generateDistributionGraph(PabloBlock * block, DependencyGraph & G) {
    46     SinkMap M;
    47     VertexSet distSet;
    48     for (Statement * stmt : *block) {
    49         if (isa<And>(stmt) || isa<Or>(stmt)) {
    50             const TypeId outerTypeId = stmt->getClassTypeId();
    51             const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
    52             flat_set<PabloAST *> distributable;
    53             for (PabloAST * const expr : *cast<Variadic>(stmt)) {
    54                 if (LLVM_UNLIKELY(expr->getClassTypeId() == innerTypeId)) {
    55                     bool safe = true;
    56                     for (PabloAST * const user : expr->users()) {
    57                         if (user->getClassTypeId() != outerTypeId) {
    58                             safe = false;
    59                             break;
    60                         }
    61                     }
    62                     if (safe) {
    63                         distributable.insert(expr);
    64                     }
    65                 }
    66             }
    67             if (LLVM_LIKELY(distributable.size() > 1)) {
    68                 flat_map<PabloAST *, bool> observedMoreThanOnce;
    69                 bool anyOpportunities = false;
    70                 for (const PabloAST * distOperation : distributable) {
    71                     for (PabloAST * const distVar : *cast<Variadic>(distOperation)) {
    72                         auto ob = observedMoreThanOnce.find(distVar);
    73                         if (ob == observedMoreThanOnce.end()) {
    74                             observedMoreThanOnce.emplace(distVar, false);
    75                         } else {
    76                             ob->second = true;
    77                             anyOpportunities = true;
    78                         }
    79                     }
    80                 }
    81                 if (anyOpportunities) {
    82                     for (const auto ob : observedMoreThanOnce) {
    83                         PabloAST * distVar = nullptr;
    84                         bool observedTwice = false;
    85                         std::tie(distVar, observedTwice) = ob;
    86                         if (observedTwice) {
    87                             const Vertex z = getVertex(stmt, G, M);
    88                             distSet.push_back(z);
    89                             for (PabloAST * const distOperation : distVar->users()) {
    90                                 if (distributable.count(distOperation)) {
    91                                     const Vertex y = getVertex(distOperation, G, M);
    92                                     add_edge(getVertex(distVar, G, M), y, G);
    93                                     add_edge(y, z, G);
    94                                 }
    95                             }
    96                         }
    97                     }
    98                 }
    99             }
    100         }
    101     }
    102     return distSet;
    103 }
    10428
    10529/** ------------------------------------------------------------------------------------------------------------- *
     
    12549 * @brief independentCliqueSets
    12650 ** ------------------------------------------------------------------------------------------------------------- */
    127 template <unsigned side>
    128 inline static BicliqueSet && independentCliqueSets(BicliqueSet && bicliques, const unsigned minimum) {
     51static BicliqueSet && independentCliqueSets(BicliqueSet && bicliques, const bool uppsetSet) {
    12952    using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
    13053
     
    13255    IndependentSetGraph I(l);
    13356
     57
    13458    // Initialize our weights and determine the constraints
    135     for (unsigned i = 0; i != l; ++i) {
    136         I[i] = std::pow(std::get<side>(bicliques[i]).size(), 2);
    137         for (unsigned j = i + 1; j != l; ++j) {
    138             if (intersects(std::get<side>(bicliques[i]), std::get<side>(bicliques[j]))) {
    139                 add_edge(i, j, I);
    140             }
    141         }
    142     }
    143 
    144 //    // Initialize our weights and determine the constraints
    145 //    for (auto i = bicliques.begin(); i != bicliques.end(); ++i) {
    146 //        I[std::distance(bicliques.begin(), i)] = std::pow(std::get<side>(*i).size(), 2);
    147 //        for (auto j = i; ++j != bicliques.end(); ) {
    148 //            if (intersects(i->second, j->second) && intersects(i->first, j->first)) {
    149 //                add_edge(std::distance(bicliques.begin(), i), std::distance(bicliques.begin(), j), I);
    150 //            }
    151 //        }
    152 //    }
     59    if (uppsetSet) {
     60        for (auto i = bicliques.begin(); i != bicliques.end(); ++i) {
     61            I[std::distance(bicliques.begin(), i)] = std::pow(std::get<0>(*i).size(), 2);
     62            for (auto j = i; ++j != bicliques.end(); ) {
     63                if (intersects(i->first, j->first)) {
     64                    add_edge(std::distance(bicliques.begin(), i), std::distance(bicliques.begin(), j), I);
     65                }
     66            }
     67        }
     68    } else {
     69        for (auto i = bicliques.begin(); i != bicliques.end(); ++i) {
     70            I[std::distance(bicliques.begin(), i)] = std::pow(std::get<1>(*i).size(), 2);
     71            for (auto j = i; ++j != bicliques.end(); ) {
     72                if (intersects(i->first, j->first) && intersects(i->second, j->second)) {
     73                    add_edge(std::distance(bicliques.begin(), i), std::distance(bicliques.begin(), j), I);
     74                }
     75            }
     76        }
     77    }
     78
    15379
    15480    // Use the greedy algorithm to choose our independent set
     
    16389            }
    16490        }
    165         if (w < minimum) break;
     91        if (w < (uppsetSet ? 2 : 1)) break;
    16692        selected.push_back(u);
    16793        I[u] = 0;
     
    189115 * bipartition A and their adjacencies to be in B.
    190116  ** ------------------------------------------------------------------------------------------------------------- */
    191 static BicliqueSet enumerateBicliques(const DependencyGraph & G, const VertexSet & A) {
     117static BicliqueSet enumerateBicliques(const Graph & G, const VertexSet & A, const unsigned min) {
    192118    using IntersectionSets = std::set<VertexSet>;
    193119
    194120    IntersectionSets B1;
     121    VertexSet tmp;
    195122    for (auto u : A) {
    196123        if (in_degree(u, G) > 0) {
    197             VertexSet incomingAdjacencies;
    198             incomingAdjacencies.reserve(in_degree(u, G));
     124            tmp.reserve(in_degree(u, G));
    199125            for (auto e : make_iterator_range(in_edges(u, G))) {
    200                 incomingAdjacencies.push_back(source(e, G));
    201             }
    202             std::sort(incomingAdjacencies.begin(), incomingAdjacencies.end());
    203             B1.insert(std::move(incomingAdjacencies));
     126                tmp.push_back(source(e, G));
     127            }
     128            if (tmp.size() >= min) {
     129                std::sort(tmp.begin(), tmp.end());
     130                B1.emplace(tmp.begin(), tmp.end());
     131            }
     132            tmp.clear();
    204133        }
    205134    }
     
    208137
    209138    IntersectionSets Bi;
    210 
    211     VertexSet clique;
    212139    for (auto i = B1.begin(); i != B1.end(); ++i) {
    213140        for (auto j = i; ++j != B1.end(); ) {
    214             std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
    215             if (clique.size() > 0) {
    216                 if (B.count(clique) == 0) {
    217                     Bi.insert(clique);
    218                 }
    219                 clique.clear();
    220             }
     141            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(tmp));
     142            if (tmp.size() >= min) {
     143                if (B.count(tmp) == 0) {
     144                    Bi.emplace(tmp.begin(), tmp.end());
     145                }
     146            }
     147            tmp.clear();
    221148        }
    222149    }
     
    230157        for (auto i = B1.begin(); i != B1.end(); ++i) {
    231158            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
    232                 std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
    233                 if (clique.size() > 0) {
    234                     if (B.count(clique) == 0) {
    235                         Bk.insert(clique);
     159                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(tmp));
     160                if (tmp.size() >= min) {
     161                    if (B.count(tmp) == 0) {
     162                        Bk.emplace(tmp.begin(), tmp.end());
    236163                    }
    237                     clique.clear();
    238                 }
     164                }
     165                tmp.clear();
    239166            }
    240167        }
     
    245172    cliques.reserve(B.size());
    246173    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
     174        assert (Bi->size() >= min);
    247175        VertexSet Ai(A);
    248176        for (const Vertex u : *Bi) {
     
    271199 * there are not enough vertices in the biclique to make distribution profitable, eliminate the clique.
    272200 ** ------------------------------------------------------------------------------------------------------------- */
    273 static BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques, DependencyGraph & G) {
     201static BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques, const Graph & G) {
    274202    for (auto ci = cliques.begin(); ci != cliques.end(); ) {
    275203        const auto cardinalityA = std::get<0>(*ci).size();
     
    294222 * @brief safeDistributionSets
    295223 ** ------------------------------------------------------------------------------------------------------------- */
    296 static DistributionSets safeDistributionSets(DependencyGraph & G, const VertexSet & distSet) {
     224inline static DistributionSets safeDistributionSets(const Graph & G, const VertexSet & A) {
    297225    DistributionSets T;
    298     BicliqueSet lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(G, distSet), G), 1);
     226    BicliqueSet lowerSet = independentCliqueSets(removeUnhelpfulBicliques(enumerateBicliques(G, A, 1), G), false);
    299227    for (Biclique & lower : lowerSet) {
    300         BicliqueSet upperSet = independentCliqueSets<0>(enumerateBicliques(G, std::get<1>(lower)), 2);
     228        BicliqueSet upperSet = independentCliqueSets(enumerateBicliques(G, std::get<1>(lower), 2), true);
    301229        for (Biclique & upper : upperSet) {
    302230            T.emplace_back(std::move(std::get<1>(upper)), std::move(std::get<0>(upper)), std::get<0>(lower));
     
    307235
    308236/** ------------------------------------------------------------------------------------------------------------- *
    309  * @brief process
    310  ** ------------------------------------------------------------------------------------------------------------- */
    311 inline void DistributivePass::process(PabloBlock * const block) {
    312 
    313     for (;;) {
    314 
    315         // FlattenAssociativeDFG::coalesce(block, false);
    316 
    317         DependencyGraph G;
    318 
    319         const VertexSet distSet = generateDistributionGraph(block, G);
    320 
    321         // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
    322         if (LLVM_UNLIKELY(distSet.empty())) {
     237 * @brief scopeDepthOf
     238 ** ------------------------------------------------------------------------------------------------------------- */
     239inline unsigned scopeDepthOf(const PabloBlock * block) {
     240    unsigned depth = 0;
     241    for (; block; ++depth, block = block->getParent());
     242    return depth;
     243}
     244
     245/** ------------------------------------------------------------------------------------------------------------- *
     246 * @brief findInsertionPoint
     247 ** ------------------------------------------------------------------------------------------------------------- */
     248inline PabloBlock * findInsertionPoint(const VertexSet & users, const Graph & G) {
     249    std::vector<PabloBlock *> scopes(0);
     250    scopes.reserve(users.size());
     251    for (Vertex u : users) {
     252        PabloBlock * const scope = cast<Statement>(G[u])->getParent(); assert (scope);
     253        if (std::find(scopes.begin(), scopes.end(), scope) == scopes.end()) {
     254            scopes.push_back(scope);
     255        }
     256    }
     257    while (scopes.size() > 1) {
     258        // Find the LCA of both scopes then add the LCA back to the list of scopes.
     259        PabloBlock * scope1 = scopes.back();
     260        scopes.pop_back();
     261        PabloBlock * scope2 = scopes.back();
     262        scopes.pop_back();
     263        assert (scope1 != scope2);
     264        unsigned depth1 = scopeDepthOf(scope1);
     265        unsigned depth2 = scopeDepthOf(scope2);
     266        // If one of these scopes is nested deeper than the other, scan upwards through
     267        // the scope tree until both scopes are at the same depth.
     268        while (depth1 > depth2) {
     269            scope1 = scope1->getParent();
     270            --depth1;
     271        }
     272        while (depth1 < depth2) {
     273            scope2 = scope2->getParent();
     274            --depth2;
     275        }
     276        assert (depth1 == depth2);
     277        // Then iteratively step backwards until we find a matching scopes; this must be
     278        // the LCA of our original pair.
     279        while (scope1 != scope2) {
     280            scope1 = scope1->getParent();
     281            scope2 = scope2->getParent();
     282        }
     283        assert (scope1 && scope2);
     284        if (std::find(scopes.begin(), scopes.end(), scope1) == scopes.end()) {
     285            scopes.push_back(scope1);
     286        }
     287    }
     288    assert (scopes.size() == 1);
     289    PabloBlock * const root = scopes.front();
     290    // Now that we know the common scope of these users, test which statement is the first to require it.
     291    flat_set<Statement *> usages;
     292    usages.reserve(users.size());
     293    for (Vertex u : users) {
     294        Statement * user = cast<Statement>(G[u]);
     295        PabloBlock * scope = user->getParent();
     296        while (scope != root) {
     297            assert (scope);
     298            user = scope->getBranch();
     299            scope = scope->getParent();
     300        }
     301        usages.insert(user);
     302    }
     303    Statement * ip = nullptr;
     304    for (Statement * stmt : *root) {
     305        if (usages.count(stmt)) {
     306            ip = stmt->getPrevNode();
    323307            break;
    324308        }
    325 
    326         const DistributionSets distributionSets = safeDistributionSets(G, distSet);
    327 
    328         if (LLVM_UNLIKELY(distributionSets.empty())) {
    329             break;
    330         }
    331 
    332         for (const DistributionSet & set : distributionSets) {
    333 
    334             // Each distribution tuple consists of the sources, intermediary, and sink nodes.
    335             const VertexSet & sources = std::get<0>(set);
    336             const VertexSet & intermediary = std::get<1>(set);
    337             const VertexSet & sinks = std::get<2>(set);
    338 
    339             // Find the first sink and set the insert point immediately before that.
    340             Variadic * innerOp = nullptr;
    341             Variadic * outerOp = nullptr;
    342 
    343             block->setInsertPoint(cast<Variadic>(G[sinks.front()])->getPrevNode());
    344             if (isa<And>(G[sinks.front()])) {
    345                 outerOp = block->createAnd(intermediary.size());
    346                 innerOp = block->createOr(sources.size() + 1);
    347             } else {
    348                 outerOp = block->createOr(intermediary.size());
    349                 innerOp = block->createAnd(sources.size() + 1);
    350             }
    351 
    352             for (const Vertex u : intermediary) {
    353                 for (const Vertex v : sinks) {
    354                     cast<Variadic>(G[v])->deleteOperand(G[u]);
    355                 }
    356                 outerOp->addOperand(G[u]);
    357             }
    358             CoalesceDFG::coalesce(outerOp);
    359 
    360             for (const Vertex u : sources) {
     309    }
     310    assert (ip);
     311    root->setInsertPoint(ip);
     312    return root;
     313}
     314
     315/** ------------------------------------------------------------------------------------------------------------- *
     316 * @brief computeDistributionGraph
     317 ** ------------------------------------------------------------------------------------------------------------- */
     318static inline void computeDistributionGraph(Variadic * const expr, Graph & G, VertexSet & A) {
     319
     320    const TypeId outerTypeId = expr->getClassTypeId();
     321    const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
     322
     323    assert (isa<And>(expr) || isa<Or>(expr));
     324
     325    Map M;
     326    for (unsigned i = 0; i != expr->getNumOperands(); ++i) {
     327        PabloAST * const op = expr->getOperand(i);
     328        if (op->getClassTypeId() == innerTypeId) {
     329            bool distributable = true;
     330            for (PabloAST * user : op->users()) {
     331                // Early check to see whether it'd be beneficial to distribute it. If this fails, we'd have
     332                // to compute the operand's value anyway, so just ignore this operand.
     333                if (user->getClassTypeId() != outerTypeId) {
     334                    distributable = false;
     335                    break;
     336                }
     337            }
     338            if (distributable) {
     339                const Vertex u = add_vertex(op, G);
     340                for (PabloAST * user : op->users()) {
     341                    const auto f = M.find(user);
     342                    Vertex v = 0;
     343                    if (LLVM_LIKELY(f != M.end())) {
     344                        v = f->second;
     345                    } else {
     346                        v = add_vertex(user, G);
     347                        M.emplace(user, v);
     348                        A.push_back(v);
     349                    }
     350                    add_edge(u, v, G);
     351                }
     352                for (PabloAST * input : *cast<Variadic>(op)) {
     353                    const auto f = M.find(input);
     354                    Vertex v = 0;
     355                    if (f != M.end()) {
     356                        v = f->second;
     357                    } else {
     358                        v = add_vertex(input, G);
     359                        M.emplace(input, v);
     360                    }
     361                    add_edge(v, u, G);
     362                }
     363            }
     364        }
     365    }
     366}
     367
     368/** ------------------------------------------------------------------------------------------------------------- *
     369 * @brief distribute
     370 *
     371 * Based on the knowledge that:
     372 *
     373 *   (P ∧ Q) √ (P ∧ R) ⇔ P ∧ (Q √ R) and (P √ Q) ∧ (P √ R) ⇔ P √ (Q ∧ R)
     374 *
     375 * Try to eliminate some of the unnecessary operations from the current Variadic expression.
     376 ** ------------------------------------------------------------------------------------------------------------- */
     377inline void DistributivePass::distribute(Variadic * const var) {
     378
     379    std::vector<Variadic *> Q;
     380
     381    assert (isa<And>(var) || isa<Or>(var));
     382
     383    Q.push_back(var);
     384
     385    Graph G;
     386    VertexSet A;
     387
     388    while (Q.size() > 0) {
     389
     390        Variadic * expr = CanonicalizeDFG::canonicalize(Q.back());
     391        Q.pop_back();
     392        PabloAST * const replacement = Simplifier::fold(expr, expr->getParent());
     393        if (LLVM_UNLIKELY(replacement != nullptr)) {
     394            expr->replaceWith(replacement, true, true);
     395            if (LLVM_UNLIKELY(isa<Variadic>(replacement))) {
     396                Q.push_back(cast<Variadic>(replacement));
     397            }
     398            continue;
     399        }
     400
     401        if (LLVM_LIKELY(isa<And>(expr) || isa<Or>(expr))) {
     402
     403            computeDistributionGraph(expr, G, A);
     404
     405            // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
     406            if (num_vertices(G) == 0) {
     407                assert (A.empty());
     408                continue;
     409            }
     410
     411            const auto S = safeDistributionSets(G, A);
     412            if (S.empty()) {
     413                G.clear();
     414                A.clear();
     415                continue;
     416            }
     417
     418            Q.push_back(expr);
     419
     420            for (const DistributionSet & set : S) {
     421
     422                // Each distribution tuple consists of the sources, intermediary, and sink nodes.
     423                const VertexSet & sources = std::get<0>(set);
     424                assert (sources.size() > 0);
     425                const VertexSet & intermediary = std::get<1>(set);
     426                assert (intermediary.size() > 1);
     427                const VertexSet & sinks = std::get<2>(set);
     428                assert (sinks.size() > 0);
     429
     430                // Test whether we can apply the identity law to distributed set. I.e., (P ∧ Q) √ (P ∧ ¬Q) ⇔ (P √ Q) ∧ (P √ ¬Q) ⇔ P
     431
     432
     433                for (const Vertex u : intermediary) {
     434                    for (const Vertex v : sources) {
     435                        cast<Variadic>(G[u])->deleteOperand(G[v]);
     436                    }
     437                }
     438                for (const Vertex u : sinks) {
     439                    for (const Vertex v : intermediary) {
     440                        cast<Variadic>(G[u])->deleteOperand(G[v]);
     441                    }
     442                }
     443
     444                PabloBlock * const block = findInsertionPoint(sinks, G);
     445                Variadic * innerOp = nullptr;
     446                Variadic * outerOp = nullptr;
     447                if (isa<And>(expr)) {
     448                    outerOp = block->createAnd(intermediary.size());
     449                    innerOp = block->createOr(sources.size() + 1);
     450                } else {
     451                    outerOp = block->createOr(intermediary.size());
     452                    innerOp = block->createAnd(sources.size() + 1);
     453                }
    361454                for (const Vertex v : intermediary) {
    362                     cast<Variadic>(G[v])->deleteOperand(G[u]);
    363                 }
    364                 innerOp->addOperand(G[u]);
    365             }
    366             innerOp->addOperand(outerOp);
    367             CoalesceDFG::coalesce(innerOp);
    368 
    369             for (const Vertex u : sinks) {
    370                 cast<Variadic>(G[u])->addOperand(innerOp);
    371             }
     455                    outerOp->addOperand(G[v]);
     456                }
     457                for (const Vertex v : sources) {
     458                    innerOp->addOperand(G[v]);
     459                }
     460                for (const Vertex u : sinks) {
     461                    cast<Variadic>(G[u])->addOperand(innerOp);
     462                }
     463                innerOp->addOperand(outerOp);
     464                // Push our newly constructed ops into the Q
     465                Q.push_back(innerOp);
     466                Q.push_back(outerOp);
     467            }
     468
     469            G.clear();
     470            A.clear();
    372471        }
    373472    }
     
    381480        if (isa<If>(stmt) || isa<While>(stmt)) {
    382481            distribute(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    383         }
    384     }
    385     process(block);
     482        } else if (isa<And>(stmt) || isa<Or>(stmt)) {
     483            distribute(cast<Variadic>(stmt));
     484        }
     485    }
    386486}
    387487
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.h

    r4887 r4922  
    1313protected:
    1414    static void distribute(PabloBlock * const block);
    15     static void process(PabloBlock * const block);
     15    static void distribute(Variadic * const expr);
    1616    DistributivePass() = default;
    1717};
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4919 r4922  
    77#include <boost/container/flat_set.hpp>
    88
     9#include <pablo/printer_pablos.h>
     10#include <iostream>
     11
    912namespace pablo {
    1013
     
    1215using SmallSet = boost::container::flat_set<Type>;
    1316
    14 /** ------------------------------------------------------------------------------------------------------------- *
    15  * @brief optimize
    16  ** ------------------------------------------------------------------------------------------------------------- */
    17 bool Simplifier::optimize(PabloFunction & function) {
    18     // negationsShouldImmediatelySucceedTheirLiteral(function.getEntryBlock());
    19     #ifndef NDEBUG
    20     PabloVerifier::verify(function, "post-negation-must-immediately-succeed-their-literal");
    21     #endif
    22     eliminateRedundantCode(function.getEntryBlock());
    23     #ifndef NDEBUG
    24     PabloVerifier::verify(function, "post-eliminate-redundant-code");
    25     #endif
    26     deadCodeElimination(function.getEntryBlock());
    27     #ifndef NDEBUG
    28     PabloVerifier::verify(function, "post-dead-code-elimination");
    29     #endif
    30     strengthReduction(function.getEntryBlock());
    31     #ifndef NDEBUG
    32     PabloVerifier::verify(function, "post-strength-reduction");
    33     #endif
    34     return true;
    35 }
    36 
    37 /** ------------------------------------------------------------------------------------------------------------- *
    38  * @brief isReassociative
    39  ** ------------------------------------------------------------------------------------------------------------- */
    40 inline bool isReassociative(const Statement * const stmt) {
    41     switch (stmt->getClassTypeId()) {
    42         case PabloAST::ClassTypeId::And:
    43         case PabloAST::ClassTypeId::Or:
    44         case PabloAST::ClassTypeId::Xor:
    45             return true;
    46         default: return false;
    47     }
    48 }
     17using TypeId = PabloAST::ClassTypeId;
    4918
    5019/** ------------------------------------------------------------------------------------------------------------- *
    5120 * @brief fold
    52  ** ------------------------------------------------------------------------------------------------------------- */
    53 inline PabloAST * Simplifier::fold(Variadic * const var, PabloBlock * const block) {
     21 *
     22 * Note: if folding alters this variadic without making any other modification to the AST, it will return null as
     23 * if no change was made.
     24 ** ------------------------------------------------------------------------------------------------------------- */
     25PabloAST * Simplifier::fold(Variadic * var, PabloBlock * const block) {
    5426
    5527    assert (var);
     
    6840    // Ensure all operands of a reassociatiable function are consistently ordered.
    6941    std::sort(var->begin(), var->end());
    70 
    7142    // Apply the idempotence law to any And and Or statement and the identity law to any Xor
    72     for (unsigned i = 1; i < var->getNumOperands(); ) {
    73         if (var->getOperand(i - 1) == var->getOperand(i)) {
     43    for (int i = var->getNumOperands() - 1; i > 0; --i) {
     44        if (LLVM_UNLIKELY(var->getOperand(i) == var->getOperand(i - 1))) {
    7445            var->removeOperand(i);
    7546            if (LLVM_UNLIKELY(isa<Xor>(var))) {
    76                 var->removeOperand(i - 1);
    77             }
     47                var->removeOperand(--i);
     48            }
     49        }
     50    }
     51
     52    // Apply the annihilator and identity laws
     53    for (unsigned i = 0; i != var->getNumOperands(); ) {
     54        if (LLVM_UNLIKELY(isa<Zeroes>(var->getOperand(i)))) {
     55            if (LLVM_UNLIKELY(isa<And>(var))) {
     56                return PabloBlock::createZeroes();
     57            }
     58            var->removeOperand(i);
    7859            continue;
     60        } else if (LLVM_UNLIKELY(isa<Ones>(var->getOperand(i)))) {
     61            if (LLVM_UNLIKELY(isa<Or>(var))) {
     62                return PabloBlock::createOnes();
     63            } else if (LLVM_UNLIKELY(isa<Xor>(var))) {
     64                negated = !negated;
     65            }
     66            var->removeOperand(i);
     67            continue;
    7968        }
    8069        ++i;
    8170    }
    8271
    83     if (LLVM_LIKELY(!isa<Xor>(var))) {
     72    PabloAST * replacement = nullptr;
     73
     74    if (LLVM_LIKELY(isa<And>(var) || isa<Or>(var))) {
     75        // Apply an implicit distribution + identity law whenever possible
     76        //    (P ∧ Q) √ (P ∧ ¬Q) = P √ (Q ∧ ¬Q) ⇔ (P √ Q) ∧ (P √ ¬Q) = P ∧ (Q √ ¬Q) ⇔ P
     77        bool modified = false;
     78        const TypeId typeId = isa<And>(var) ? TypeId::Or : TypeId::And;
     79        for (unsigned i = 1; i < var->getNumOperands(); ++i) {
     80            if (var->getOperand(i)->getClassTypeId() == typeId) {
     81                Variadic * const op_i = cast<Variadic>(var->getOperand(i));
     82                assert (std::is_sorted(op_i->begin(), op_i->end()));
     83                for (unsigned j = 0; j < i; ++j) {
     84                    if (var->getOperand(j)->getClassTypeId() == typeId) {
     85                        Variadic * const op_j = cast<Variadic>(var->getOperand(j));
     86                        assert (std::is_sorted(op_j->begin(), op_j->end()));
     87                        if (op_i->getNumOperands() == op_j->getNumOperands()) {
     88                            // If vi and vj differ by precisely one operand each, say di and dj, and di ⇔ ¬dj, then
     89                            // we can apply this rule.
     90                            unsigned vi = 0, vj = 0;
     91                            const unsigned operands = op_i->getNumOperands();
     92                            unsigned di = operands - 1, dj = operands - 1;
     93                            bool differsByOne = true;
     94                            while (vi < operands && vj < operands) {
     95                                if (op_i->getOperand(vi) < op_j->getOperand(vj)) {
     96                                    if (LLVM_UNLIKELY(di != (operands - 1))) { // <- we want the branch predictor to fail only once
     97                                        differsByOne = false;
     98                                        break;
     99                                    }
     100                                    di = vi++;
     101                                } else if (op_j->getOperand(vj) < op_i->getOperand(vi)) {
     102                                    if (LLVM_UNLIKELY(dj != (operands - 1))) {
     103                                        differsByOne = false;
     104                                        break;
     105                                    }
     106                                    dj = vj++;
     107                                } else {
     108                                    ++vi;
     109                                    ++vj;
     110                                }
     111                            }
     112                            if (LLVM_UNLIKELY(differsByOne)) {
     113                                assert (di < operands && dj < operands);
     114                                assert ("Found an equivalent set of operations that was not deduced earlier!" && !equals(op_i, op_j));
     115                                bool apply = false;
     116                                if (isa<Not>(op_i->getOperand(di))) {
     117                                    apply = equals(cast<Not>(op_i->getOperand(di))->getOperand(0), op_j->getOperand(dj));
     118                                } else if (isa<Not>(op_j->getOperand(dj))) {
     119                                    apply = equals(cast<Not>(op_j->getOperand(dj))->getOperand(0), op_i->getOperand(di));
     120                                }
     121                                if (LLVM_UNLIKELY(apply)) {
     122                                    // Although we can apply this rule, we have a potential problem. If P is not a "literal", we cannot modify
     123                                    // var without creating a new And or Or statement. This however may mean that the "redundancyElimination"
     124                                    // pass could miss a statement if its not added after this statement.
     125                                    PabloAST * expr = nullptr;
     126                                    if (operands == 2) {
     127                                        expr = op_i->getOperand(1 ^ di);
     128                                        if (LLVM_LIKELY(var->getNumOperands() == 2)) {
     129                                            return expr;
     130                                        }
     131                                    } else { // if (operands > 2) {
     132                                        assert (operands > 2);
     133                                        block->setInsertPoint(var->getPrevNode());
     134                                        Variadic * nested = nullptr;
     135                                        if (typeId == TypeId::And) {
     136                                            nested = block->createAnd(operands - 1);
     137                                        } else { // if (typeId == TypeId::Or) {
     138                                            nested = block->createOr(operands - 1);
     139                                        }
     140                                        for (unsigned k = 0; k != di; ++k) {
     141                                            nested->addOperand(op_i->getOperand(k));
     142                                        }
     143                                        for (unsigned k = di + 1; k < operands; ++k) {
     144                                            nested->addOperand(op_i->getOperand(k));
     145                                        }
     146                                        expr = nested;
     147                                        replacement = var;
     148                                    }
     149                                    var->setOperand(j, expr);
     150                                    var->removeOperand(i);
     151                                    i = 0;
     152                                    modified = true;
     153                                    break;
     154                                }
     155                            }
     156                        }
     157                    }
     158                }
     159            }
     160        }
     161
     162        // Apply the absorption law whenever possible
     163        //   P √ (P ∧ Q) ⇔ P ∧ (P √ Q) ⇔ P
     164        for (unsigned i = 1; i < var->getNumOperands(); ++i) {
     165            PabloAST * const op = var->getOperand(i);
     166            if (op->getClassTypeId() == typeId) {
     167                Variadic * const vi = cast<Variadic>(op);
     168                assert (std::is_sorted(vi->begin(), vi->end()));
     169                for (unsigned j = 0; j < i; ++j) {
     170                    assert (var->getOperand(i) == vi);
     171                    if (var->getOperand(j)->getClassTypeId() == typeId) {
     172                        Variadic * const vj = cast<Variadic>(var->getOperand(j));
     173                        assert (std::is_sorted(vj->begin(), vj->end()));
     174                        if (vi->getNumOperands() < vj->getNumOperands()) {
     175                            if (LLVM_UNLIKELY(std::includes(vi->begin(), vi->end(), vj->begin(), vj->end()))) {
     176                                var->removeOperand(i--);
     177                                break;
     178                            }
     179                        } else { // if (vi->getNumOperands() >= vj->getNumOperands()) {
     180                            if (LLVM_UNLIKELY(std::includes(vj->begin(), vj->end(), vi->begin(), vi->end()))) {
     181                                var->removeOperand(j--); i--;
     182                            }
     183                        }
     184                    }
     185                }
     186            } else { // treat the operand as a literal
     187                for (unsigned j = 0; j < var->getNumOperands(); ) {
     188                    if (var->getOperand(j)->getClassTypeId() == typeId) {
     189                        Variadic * const vj = cast<Variadic>(var->getOperand(j));
     190                        assert (std::is_sorted(vj->begin(), vj->end()));
     191                        if (LLVM_UNLIKELY(std::binary_search(vj->begin(), vj->end(), op))) {
     192                            var->removeOperand(j);
     193                            continue;
     194                        }
     195                    }
     196                    ++j;
     197                }
     198            }
     199        }
     200
    84201        // Apply the complementation law whenever possible.
    85202        for (unsigned i = 0; i < var->getNumOperands(); ++i) {
    86203            if (isa<Not>(var->getOperand(i))) {
    87                 const PabloAST * const negatedOp = cast<Not>(var->getOperand(i))->getOperand(0);
     204                const PabloAST * const negated = cast<Not>(var->getOperand(i))->getOperand(0);
    88205                for (unsigned j = 0; j != var->getNumOperands(); ++j) {
    89                     if (LLVM_UNLIKELY(equals(var->getOperand(j), negatedOp))) {
    90                         if (isa<And>(var)) { // (A ∧ ¬A) ∧ B = 0 for any B
     206                    if (LLVM_UNLIKELY(var->getOperand(j) == negated)) {
     207                        if (isa<And>(var)) { // (A ∧ ¬A) ∧ B ⇔ 0 for any B
    91208                            return PabloBlock::createZeroes();
    92                         } else if (isa<Or>(var)) { // (A √ ¬A) √ B = 1 for any B
     209                        } else { // if (isa<Or>(var)) { // (A √ ¬A) √ B ⇔ 1 for any B
    93210                            return PabloBlock::createOnes();
    94211                        }
     
    97214            }
    98215        }
    99     }
    100 
    101     // Apply the annihilator and identity laws
    102     for (unsigned i = 0; i != var->getNumOperands(); ) {
    103         if (LLVM_UNLIKELY(isa<Zeroes>(var->getOperand(i)))) {
    104             if (isa<And>(var)) {
    105                 return PabloBlock::createZeroes();
    106             }
    107             var->removeOperand(i);
    108             continue;
    109         } else if (LLVM_UNLIKELY(isa<Ones>(var->getOperand(i)))) {
    110             if (isa<Or>(var)) {
    111                 return PabloBlock::createOnes();
    112             } else if (isa<Xor>(var)) {
    113                 negated = !negated;
    114             }
    115             var->removeOperand(i);
    116             continue;
    117         }
    118         ++i;
    119     }
    120 
    121     PabloAST * replacement = nullptr;
     216
     217        if (LLVM_UNLIKELY(modified)) {
     218            // Ensure all operands of a reassociatiable function are consistently ordered.
     219            std::sort(var->begin(), var->end());
     220            // Apply the idempotence law to any And and Or statement
     221            for (int i = var->getNumOperands() - 1; i > 0; --i) {
     222                if (LLVM_UNLIKELY(var->getOperand(i) == var->getOperand(i - 1))) {
     223                    var->removeOperand(i);
     224                }
     225            }
     226        }
     227
     228    } // end of if (LLVM_LIKELY(isa<And>(var) || isa<Or>(var)))
     229
    122230    if (LLVM_UNLIKELY(var->getNumOperands() < 2)) {
    123         replacement = (var->getNumOperands() == 0) ? PabloBlock::createZeroes() : var->getOperand(0);
     231        if (LLVM_UNLIKELY(var->getNumOperands() == 0)) {
     232            return PabloBlock::createZeroes();
     233        }
     234        replacement = var->getOperand(0);
     235    }
     236    // If we marked this var as being a replacement for itself, then we must have manipulated some of its inner
     237    // operands in such a way that we had to generate new statements for it. Thus we need to generate a new "var"
     238    // so that the "redundancyElimination" pass doesn't miss one of its operands.
     239    if (LLVM_UNLIKELY(replacement == var)) {
     240        Variadic * replacementVar = nullptr;
     241        if (isa<And>(var)) {
     242            replacementVar = block->createAnd(var->getNumOperands());
     243        } else if (isa<Or>(var)) {
     244            replacementVar = block->createOr(var->getNumOperands());
     245        } else { // if (isa<Xor>(var)) {
     246            replacementVar = block->createXor(var->getNumOperands());
     247        }
     248        assert (std::is_sorted(var->begin(), var->end()));
     249        for (unsigned i = 0; i != var->getNumOperands(); ++i) {
     250            replacementVar->addOperand(var->getOperand(i));
     251        }
     252        replacement = replacementVar;
    124253    }
    125254    if (LLVM_UNLIKELY(negated)) {
     255        assert (isa<Xor>(var));
    126256        block->setInsertPoint(var);
    127257        replacement = block->createNot(replacement ? replacement : var);
    128258    }
     259    assert (replacement != var);
    129260    return replacement;
    130261}
     
    133264 * @brief fold
    134265 ** ------------------------------------------------------------------------------------------------------------- */
    135 inline PabloAST * Simplifier::fold(Statement * stmt, PabloBlock * block) {
    136     if (isReassociative(stmt)) {
     266inline PabloAST * Simplifier::fold(Statement * stmt, PabloBlock * const block) {
     267    if (isa<Variadic>(stmt)) {
    137268        return fold(cast<Variadic>(stmt), block);
    138269    } else if (isa<Not>(stmt)) {
    139270        PabloAST * value = stmt->getOperand(0);
    140271        if (LLVM_UNLIKELY(isa<Not>(value))) {
    141             return cast<Not>(value)->getOperand(0);
     272            return cast<Not>(value)->getOperand(0); // ¬¬A ⇔ A
    142273        } else if (LLVM_UNLIKELY(isa<Zeroes>(value))) {
    143             return block->createOnes();
     274            return PabloBlock::createOnes(); // ¬0 ⇔ 1
    144275        }  else if (LLVM_UNLIKELY(isa<Ones>(value))) {
    145             return block->createZeroes();
     276            return PabloBlock::createZeroes(); // ¬1 ⇔ 0
    146277        }
    147278    } else if (isa<Advance>(stmt)) {
    148279        if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(0)))) {
    149             return block->createZeroes();
     280            return PabloBlock::createZeroes();
    150281        }
    151282    } else {
     
    166297                }
    167298            } else if (LLVM_UNLIKELY(isa<Ones>(stmt->getOperand(i)))) {
    168                 block->setInsertPoint(stmt->getPrevNode());
    169299                switch (stmt->getClassTypeId()) {
    170300                    case PabloAST::ClassTypeId::Sel:
     
    176306                        }
    177307                    case PabloAST::ClassTypeId::ScanThru:
    178                         if (i == 1) {
    179                             return block->createZeroes();
     308                        if (LLVM_UNLIKELY(i == 1)) {
     309                            return PabloBlock::createZeroes();
    180310                        }
    181311                        break;
    182312                    case PabloAST::ClassTypeId::MatchStar:
    183                         if (i == 0) {
    184                             return block->createOnes();
     313                        if (LLVM_UNLIKELY(i == 0)) {
     314                            return PabloBlock::createOnes();
    185315                        }
    186316                        break;
     
    305435
    306436/** ------------------------------------------------------------------------------------------------------------- *
    307  * @brief eliminateRedundantCode
     437 * @brief redundancyElimination
    308438 *
    309439 * Note: Do not recursively delete statements in this function. The ExpressionTable could use deleted statements
    310440 * as replacements. Let the DCE remove the unnecessary statements with the finalized Def-Use information.
    311441 ** ------------------------------------------------------------------------------------------------------------- */
    312 void Simplifier::eliminateRedundantCode(PabloBlock * const block, ExpressionTable * predecessor) {
     442void Simplifier::redundancyElimination(PabloBlock * const block, ExpressionTable * predecessor) {
    313443    ExpressionTable encountered(predecessor);
    314444    Statement * stmt = block->front();
     
    320450            // the Assign's expression directly.
    321451            if (isSuperfluous(assign)) {
    322                 stmt = assign->replaceWith(assign->getExpression());               
     452                stmt = assign->replaceWith(assign->getExpression());
    323453                continue;
    324454            }
     
    345475
    346476            // Process the If body
    347             eliminateRedundantCode(cast<If>(stmt)->getBody(), &encountered);
     477            redundancyElimination(cast<If>(stmt)->getBody(), &encountered);
    348478
    349479            // If we ended up removing all of the defined variables, delete the If node.
     
    384514                continue;
    385515            }
    386             eliminateRedundantCode(whileNode->getBody(), &encountered);
     516            redundancyElimination(whileNode->getBody(), &encountered);
    387517            removeIdenticalEscapedValues(whileNode->getVariants());
    388518            // If the condition's Next state is Zero, we can eliminate the loop after copying the internal
    389519            // statements into the body.
    390520        } else {
    391             if (PabloAST * folded = fold(stmt, block)) {
    392                 // If we determine we can fold this statement,
    393                 Statement * const prior = stmt->getPrevNode();
     521            Statement * const prior = stmt->getPrevNode();
     522            PabloAST * const folded = fold(stmt, block);
     523            if (folded) {
     524                // If we determine we can fold this statement, go back to the original prior node of this statement.
     525                // New statements may have been inserted after it.
    394526                stmt->replaceWith(folded, true);
    395527                stmt = LLVM_LIKELY(prior != nullptr) ? prior->getNextNode() : block->front();
     
    468600        stmt = stmt->getNextNode();
    469601    }
    470     block->setInsertPoint(block->back());
    471 }
    472 
    473 /** ------------------------------------------------------------------------------------------------------------- *
    474  * @brief negationsShouldImmediatelySucceedTheirLiteral
    475  *
    476  * Assuming that most negations are actually replaced by an ANDC operations or that we only need a literal or its
    477  * negation, by pushing all negations up to immediately succeed the literal we should generate equally efficient
    478  * code whilst simplifying analysis.
    479  *
    480  * TODO: this theory needs evaluation.
    481  ** ------------------------------------------------------------------------------------------------------------- */
    482 void Simplifier::negationsShouldImmediatelySucceedTheirLiteral(PabloBlock * const block) {
    483     Statement * stmt = block->front();
    484     while (stmt) {
    485         Statement * next = stmt->getNextNode();
    486         if (isa<If>(stmt)) {
    487             negationsShouldImmediatelySucceedTheirLiteral(cast<If>(stmt)->getBody());
    488         } else if (isa<While>(stmt)) {
    489             negationsShouldImmediatelySucceedTheirLiteral(cast<While>(stmt)->getBody());
    490         } else if (isa<Not>(stmt)) {
    491             PabloAST * op = cast<Not>(stmt)->getExpr();
    492             if (LLVM_LIKELY(isa<Statement>(op))) {
    493                 PabloBlock * scope = cast<Statement>(op)->getParent();
    494                 // If the operand is not in a nested scope, we can move it.
    495                 for (;;) {
    496                     if (LLVM_UNLIKELY(scope == nullptr)) {
    497                         stmt->insertAfter(cast<Statement>(op));
    498                         break;
    499                     }
    500                     scope = scope->getParent();
    501                     if (LLVM_UNLIKELY(scope == block)) {
    502                         break;
    503                     }
    504                 }
    505             }
    506         }
    507         stmt = next;
    508     }
    509 }
    510 
    511 }
     602}
     603
     604/** ------------------------------------------------------------------------------------------------------------- *
     605 * @brief optimize
     606 ** ------------------------------------------------------------------------------------------------------------- */
     607bool Simplifier::optimize(PabloFunction & function) {
     608    redundancyElimination(function.getEntryBlock());
     609    #ifndef NDEBUG
     610    PabloVerifier::verify(function, "post-eliminate-redundant-code");
     611    #endif
     612    deadCodeElimination(function.getEntryBlock());
     613    #ifndef NDEBUG
     614    PabloVerifier::verify(function, "post-dead-code-elimination");
     615    #endif
     616    strengthReduction(function.getEntryBlock());
     617    #ifndef NDEBUG
     618    PabloVerifier::verify(function, "post-strength-reduction");
     619    #endif
     620    return true;
     621}
     622
     623}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.hpp

    r4919 r4922  
    1010
    1111class Simplifier {
     12    friend class DistributivePass;
    1213public:
    1314    static bool optimize(PabloFunction & function);
     
    1516    Simplifier() = default;
    1617private:
    17     static void negationsShouldImmediatelySucceedTheirLiteral(PabloBlock * const block);
    18     static void eliminateRedundantCode(PabloBlock * const block, ExpressionTable * predecessor = nullptr);
    19     static PabloAST * fold(Variadic * const var, PabloBlock * const block);
     18    static void redundancyElimination(PabloBlock * const block, ExpressionTable * predecessor = nullptr);
     19    static PabloAST * fold(Variadic * var, PabloBlock * const block);
    2020    static PabloAST * fold(Statement * const stmt, PabloBlock * const block);
    2121    static void deadCodeElimination(PabloBlock * const block);
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4899 r4922  
    364364    assert (index < mOperands);
    365365    PabloAST * const expr = mOperand[index];
     366    assert (expr);
    366367    --mOperands;
    367368    for (unsigned i = index; i != mOperands; ++i) {
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r4899 r4922  
    621621
    622622/** ------------------------------------------------------------------------------------------------------------- *
    623  * @brief removeOperand
     623 * @brief deleteOperand
    624624 ** ------------------------------------------------------------------------------------------------------------- */
    625625inline bool Variadic::deleteOperand(const PabloAST * const expr) {
    626626    for (unsigned i = 0; i != getNumOperands(); ++i) {
    627         if (getOperand(i) == expr) {
     627        if (LLVM_UNLIKELY(getOperand(i) == expr)) {
    628628            removeOperand(i);
    629629            return true;
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

    r4919 r4922  
    1717#include <IDISA/idisa_builder.h>
    1818#include <IDISA/idisa_avx_builder.h>
    19 #include <llvm/IR/Verifier.h>
    2019#include <llvm/Pass.h>
    2120#include <llvm/PassManager.h>
     
    4948#include <llvm/Support/raw_ostream.h>
    5049#include <llvm/Support/FileSystem.h>
     50#ifndef NDEBUG
     51#include <llvm/IR/Verifier.h>
     52#endif
    5153
    5254//#include <llvm/PassManager.h>
     
    144146    const timestamp_t pablo_compilation_end = read_cycle_counter();
    145147    std::cerr << "PABLO COMPILATION TIME: " << (pablo_compilation_end - pablo_compilation_start) << std::endl;
     148    #endif
     149
     150    #ifndef NDEBUG
     151    raw_os_ostream err(std::cerr);
     152    verifyModule(*mMod, &err);
    146153    #endif
    147154
     
    258265    mCarryManager->initializeCarryDataAtIfEntry();
    259266    compileBlock(ifBody);
     267    BasicBlock * ifBodyFinalBlock = iBuilder->GetInsertBlock();
     268
    260269    if (mCarryManager->blockHasCarries()) {
    261270        mCarryManager->generateCarryOutSummaryCodeIfNeeded();
    262271    }
    263     BasicBlock * ifBodyFinalBlock = iBuilder->GetInsertBlock();
     272
    264273    mCarryManager->ensureCarriesStoredLocal();
    265274    iBuilder->CreateBr(ifEndBlock);
  • icGREP/icgrep-devel/icgrep/pablo/passes/factorizedfg.cpp

    r4919 r4922  
    99#include <boost/graph/adjacency_list.hpp>
    1010#include <boost/graph/adjacency_matrix.hpp>
    11 #include <boost/graph/topological_sort.hpp>
    1211#include <queue>
    13 #include <tuple>
    14 
    15 #include <set>
    16 #include <type_traits>
    1712
    1813#include <pablo/printer_pablos.h>
     
    2419namespace pablo {
    2520
    26 using TypeId = PabloAST::ClassTypeId;
    27 
    28 // TODO: move the "tryToPartiallyExtractVariadic" from the coalescedfg class into here to run prior to lowering?
     21/** ------------------------------------------------------------------------------------------------------------- *
     22 * @brief enumerateFactoringsOf
     23 *
     24 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
     25 * bicliques" by Alexe et. al. (2003).
     26 ** ------------------------------------------------------------------------------------------------------------- */
     27FactorizeDFG::BicliqueSet FactorizeDFG::enumerateFactoringSets(ObjectSet params, PabloBlock * const entryScope, const TypeId typeId) {
     28    using IntersectionSets = flat_set<ObjectSet>;
     29
     30    ObjectSet tmp;
     31    tmp.reserve(params.size());
     32
     33    std::sort(params.begin(), params.end());
     34
     35
     36    IntersectionSets B1;
     37    for (PabloAST * op : params) {
     38        tmp.reserve(op->getNumUses());
     39        for (PabloAST * user : op->users()) {
     40            if (user->getClassTypeId() == typeId) {
     41                if (isa<Var>(op) || cast<Statement>(user)->getParent() == entryScope) {
     42                    tmp.push_back(user);
     43                }
     44            }
     45        }
     46        if (LLVM_LIKELY(tmp.size() > 1)) {
     47            std::sort(tmp.begin(), tmp.end());
     48            B1.emplace(tmp.begin(), tmp.end());
     49        }
     50        tmp.clear();
     51    }
     52
     53    IntersectionSets B(B1);
     54
     55    IntersectionSets Bi;
     56
     57    for (auto i = B1.begin(); i != B1.end(); ++i) {
     58        for (auto j = i; ++j != B1.end(); ) {
     59            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(tmp));
     60            assert (std::is_sorted(tmp.begin(), tmp.end()));
     61            if (tmp.size() > 1 && B.count(tmp) == 0) {
     62                Bi.emplace(tmp.begin(), tmp.end());
     63            }
     64            tmp.clear();
     65        }
     66    }
     67
     68    while (!Bi.empty()) {
     69        B.insert(Bi.begin(), Bi.end());
     70        IntersectionSets Bk;
     71        for (auto i = B1.begin(); i != B1.end(); ++i) {
     72            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
     73                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(tmp));
     74                assert (std::is_sorted(tmp.begin(), tmp.end()));
     75                if (tmp.size() > 1 && B.count(tmp) == 0) {
     76                    Bk.emplace(tmp.begin(), tmp.end());
     77                }
     78                tmp.clear();
     79            }
     80        }
     81        Bi.swap(Bk);
     82    }
     83
     84    BicliqueSet factoringSets(0);
     85    factoringSets.reserve(B.size());
     86    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
     87        ObjectSet Ai(params);
     88        assert (Bi->size() > 1);
     89        for (const PabloAST * user : *Bi) {
     90            ObjectSet Aj(cast<Variadic>(user)->begin(), cast<Variadic>(user)->end());
     91            std::sort(Aj.begin(), Aj.end());
     92            ObjectSet Ak;
     93            Ak.reserve(std::min<unsigned>(Ai.size(), Aj.size()));
     94            std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
     95            Ai.swap(Ak);
     96        }
     97        if (Ai.size() > 1) {
     98            factoringSets.emplace_back(std::move(Ai), std::move(*Bi));
     99        }
     100    }
     101
     102    return factoringSets;
     103}
     104
     105/** ------------------------------------------------------------------------------------------------------------- *
     106 * @brief enumerateFactoringsOf
     107 *
     108 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
     109 * bicliques" by Alexe et. al. (2003).
     110 ** ------------------------------------------------------------------------------------------------------------- */
     111inline FactorizeDFG::BicliqueSet FactorizeDFG::enumerateFactoringSets(Variadic * const var) {
     112    using IntersectionSets = flat_set<ObjectSet>;
     113
     114    ObjectSet tmp;
     115    tmp.reserve(var->getNumOperands());
     116
     117    IntersectionSets B1;
     118    for (unsigned i = 0; i != var->getNumOperands(); ++i) {
     119        PabloAST * const op = var->getOperand(i);       
     120        tmp.reserve(op->getNumUses());
     121        for (PabloAST * user : op->users()) {
     122            if (user->getClassTypeId() == var->getClassTypeId()) {               
     123                for (PabloBlock * scope = cast<Variadic>(user)->getParent(); scope; scope = scope->getParent()) {
     124                    if (LLVM_UNLIKELY(scope == var->getParent())) {
     125                        tmp.push_back(user);
     126                        break;
     127                    }
     128                }
     129            }
     130        }
     131        if (LLVM_LIKELY(tmp.size() > 1)) {
     132            std::sort(tmp.begin(), tmp.end());
     133            B1.emplace(tmp.begin(), tmp.end());
     134        }
     135        tmp.clear();
     136    }
     137
     138    IntersectionSets B(B1);
     139
     140    IntersectionSets Bi;
     141
     142    for (auto i = B1.begin(); i != B1.end(); ++i) {
     143        for (auto j = i; ++j != B1.end(); ) {
     144            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(tmp));
     145            assert (std::is_sorted(tmp.begin(), tmp.end()));
     146            if (tmp.size() > 1 && B.count(tmp) == 0) {
     147                Bi.emplace(tmp.begin(), tmp.end());
     148            }
     149            tmp.clear();
     150        }
     151    }
     152
     153    while (!Bi.empty()) {
     154        B.insert(Bi.begin(), Bi.end());
     155        IntersectionSets Bk;
     156        for (auto i = B1.begin(); i != B1.end(); ++i) {
     157            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
     158                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(tmp));
     159                assert (std::is_sorted(tmp.begin(), tmp.end()));
     160                if (tmp.size() > 1 && B.count(tmp) == 0) {
     161                    Bk.emplace(tmp.begin(), tmp.end());
     162                }
     163                tmp.clear();
     164            }
     165        }
     166        Bi.swap(Bk);
     167    }
     168
     169    BicliqueSet factoringSets(0);
     170    factoringSets.reserve(B.size());
     171    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {       
     172        ObjectSet Ai(var->begin(), var->end());
     173        assert (Bi->size() > 1);
     174        for (const PabloAST * user : *Bi) {
     175            ObjectSet Aj(cast<Variadic>(user)->begin(), cast<Variadic>(user)->end());
     176            std::sort(Aj.begin(), Aj.end());
     177            ObjectSet Ak;
     178            Ak.reserve(std::min<unsigned>(Ai.size(), Aj.size()));
     179            std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
     180            Ai.swap(Ak);
     181        }
     182        if (Ai.size() > 1) {
     183            factoringSets.emplace_back(std::move(Ai), std::move(*Bi));
     184        }
     185    }
     186
     187    return factoringSets;
     188}
     189
     190/** ------------------------------------------------------------------------------------------------------------- *
     191 * @brief intersects
     192 ** ------------------------------------------------------------------------------------------------------------- */
     193template <class Type>
     194inline bool intersects(const Type & A, const Type & B) {
     195    auto first1 = A.begin(), last1 = A.end();
     196    auto first2 = B.begin(), last2 = B.end();
     197    assert (std::is_sorted(first1, last1));
     198    assert (std::is_sorted(first2, last2));
     199    while (first1 != last1 && first2 != last2) {
     200        if (*first1 < *first2) {
     201            ++first1;
     202        } else if (*first2 < *first1) {
     203            ++first2;
     204        } else {
     205            return true;
     206        }
     207    }
     208    return false;
     209}
     210
     211/** ------------------------------------------------------------------------------------------------------------- *
     212 * @brief independentCliqueSets
     213 ** ------------------------------------------------------------------------------------------------------------- */
     214FactorizeDFG::BicliqueSet FactorizeDFG::independentFactoringSets(BicliqueSet && factorings, const unsigned side) {
     215    using IndependentSetGraph = adjacency_matrix<undirectedS, unsigned>;
     216    using Vertex = IndependentSetGraph::vertex_descriptor;
     217
     218    const auto l = factorings.size();
     219    IndependentSetGraph I(l);
     220
     221    // Initialize our weights and determine the constraints
     222    for (auto i = factorings.begin(); i != factorings.end(); ++i) {
     223        I[std::distance(factorings.begin(), i)] = std::pow(side == 0 ? std::get<0>(*i).size() : std::get<1>(*i).size(), 2);
     224        for (auto j = i; ++j != factorings.end(); ) {
     225            if (intersects(i->first, j->first) && intersects(i->second, j->second)) {
     226                add_edge(std::distance(factorings.begin(), i), std::distance(factorings.begin(), j), I);
     227            }
     228        }
     229    }
     230
     231    // Use the greedy algorithm to choose our independent set
     232    std::vector<Vertex> selected(0);
     233    selected.reserve(l);
     234
     235    for (;;) {
     236        unsigned w = 0;
     237        Vertex u = 0;
     238        for (unsigned i = 0; i != l; ++i) {
     239            if (I[i] > w) {
     240                w = I[i];
     241                u = i;
     242            }
     243        }
     244        if (w < 2) break;
     245        selected.push_back(u);
     246        I[u] = 0;
     247        for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
     248            I[v] = 0;
     249        }
     250    }
     251
     252    // Sort the selected list and then remove the unselected cliques
     253    std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
     254    auto end = factorings.end();
     255    for (const unsigned offset : selected) {
     256        end = factorings.erase(factorings.begin() + offset + 1, end) - 1;
     257    }
     258    factorings.erase(factorings.begin(), end);
     259
     260    return std::move(factorings);
     261}
     262
     263/** ------------------------------------------------------------------------------------------------------------- *
     264 * @brief makeCheckSet
     265 ** ------------------------------------------------------------------------------------------------------------- */
     266FactorizeDFG::CheckSet FactorizeDFG::makeCheckSet(PabloBlock * const scope, const ObjectSet & values) const {
     267    CheckSet checks;
     268    assert (scope);
     269    const unsigned baseScopeDepth = scopeDepthOf(scope);
     270    for (PabloAST * value : values) {
     271        if (isa<Statement>(value)) {
     272            unsigned scopeDepth = scopeDepthOf(cast<Statement>(value)->getParent());
     273            // Is this from a preceeding scope? Or a nested scope?
     274            if (scopeDepth < baseScopeDepth) {
     275                continue;
     276            } else if (scopeDepth > baseScopeDepth) {
     277                // If we're in a nested scope, we want to know what branch statement enters it and
     278                // add that to our checks instead of the operand itself.
     279                PabloBlock * nested = cast<Statement>(value)->getParent();
     280                for (;;) {
     281                    assert (nested);
     282                    value = nested->getBranch();
     283                    nested = nested->getParent();
     284                    if (nested == scope) {
     285                        break;
     286                    }
     287                }
     288            }
     289            checks.insert(value);
     290        }
     291    }
     292    return checks;
     293}
     294
     295/** ------------------------------------------------------------------------------------------------------------- *
     296 * @brief firstIn
     297 ** ------------------------------------------------------------------------------------------------------------- */
     298inline Statement * FactorizeDFG::firstIn(PabloBlock * const scope, Statement * const initial, const ObjectSet & users) const {
     299    const auto checks = makeCheckSet(scope, users);
     300    Statement * stmt = initial;
     301    while (stmt) {
     302        if (LLVM_UNLIKELY(checks.count(stmt) != 0)) {
     303            return stmt;
     304        }
     305        stmt = stmt->getNextNode();
     306    }
     307    return scope->back();
     308}
     309
     310/** ------------------------------------------------------------------------------------------------------------- *
     311 * @brief lastIn
     312 ** ------------------------------------------------------------------------------------------------------------- */
     313inline Statement * FactorizeDFG::lastIn(PabloBlock * const scope, Statement * const initial, const ObjectSet & operands) const {
     314    const auto checks = makeCheckSet(scope, operands);
     315    Statement * stmt = initial;
     316    while (stmt) {
     317        if (LLVM_UNLIKELY(checks.count(stmt) != 0)) {
     318            return stmt;
     319        }
     320        stmt = stmt->getPrevNode();
     321    }
     322    return scope->front();
     323}
     324
     325/** ------------------------------------------------------------------------------------------------------------- *
     326 * @brief findInsertionScope
     327 ** ------------------------------------------------------------------------------------------------------------- */
     328inline PabloBlock * FactorizeDFG::findInsertionScope(const ObjectSet & users) const {
     329    std::vector<PabloBlock *> scopes;
     330    scopes.reserve(users.size());
     331    for (PabloAST * user : users) {
     332        PabloBlock * const scope = cast<Statement>(user)->getParent(); assert (scope);
     333        if (std::find(scopes.begin(), scopes.end(), scope) == scopes.end()) {
     334            scopes.push_back(scope);
     335        }
     336    }
     337    while (scopes.size() > 1) {
     338        // Find the LCA of both scopes then add the LCA back to the list of scopes.
     339        PabloBlock * scope1 = scopes.back(); scopes.pop_back();
     340        PabloBlock * scope2 = scopes.back(); scopes.pop_back();
     341        assert (scope1 != scope2);
     342        unsigned depth1 = scopeDepthOf(scope1);
     343        unsigned depth2 = scopeDepthOf(scope2);
     344        // If one of these scopes is nested deeper than the other, scan upwards through
     345        // the scope tree until both scopes are at the same depth.
     346        while (depth1 > depth2) {
     347            scope1 = scope1->getParent();
     348            --depth1;
     349        }
     350        while (depth1 < depth2) {
     351            scope2 = scope2->getParent();
     352            --depth2;
     353        }
     354        assert (depth1 == depth2);
     355        // Then iteratively step backwards until we find a matching set of scopes; this
     356        // must be the LCA of our original scopes.
     357        while (scope1 != scope2) {
     358            scope1 = scope1->getParent();
     359            scope2 = scope2->getParent();
     360        }
     361        assert (scope1 && scope2);
     362        if (std::find(scopes.begin(), scopes.end(), scope1) == scopes.end()) {
     363            scopes.push_back(scope1);
     364        }
     365    }
     366    assert (scopes.size() == 1);
     367    return scopes.front();
     368}
     369
     370/** ------------------------------------------------------------------------------------------------------------- *
     371 * @brief factorize
     372 ** ------------------------------------------------------------------------------------------------------------- */
     373inline Variadic * FactorizeDFG::factorize(const TypeId typeId, PabloBlock * const scope, ObjectSet & operands, ObjectSet & users) const {
     374    Statement * const lastOperand = lastIn(scope, scope->back(), operands);
     375    Statement * const firstUsage = firstIn(scope, lastOperand, users);
     376    scope->setInsertPoint(firstUsage ? firstUsage->getPrevNode() : lastOperand);
     377    Variadic * factoring = nullptr;
     378    if (typeId == TypeId::Or) {
     379        factoring = scope->createOr(operands.begin(), operands.end());
     380    } else if (typeId == TypeId::And) {
     381        factoring = scope->createAnd(operands.begin(), operands.end());
     382    } else { // if (typeId == TypeId::Xor) {
     383        factoring = scope->createXor(operands.begin(), operands.end());
     384    }
     385    for (PabloAST * user : users) {
     386        assert (user->getClassTypeId() == typeId);
     387        for (PabloAST * op : operands) {
     388            cast<Variadic>(user)->deleteOperand(op);
     389        }
     390        cast<Variadic>(user)->addOperand(factoring);
     391    }
     392    return factoring;
     393}
     394
     395/** ------------------------------------------------------------------------------------------------------------- *
     396 * @brief processFactoringSets
     397 ** ------------------------------------------------------------------------------------------------------------- */
     398inline bool FactorizeDFG::processFactoringSets(const TypeId typeId, PabloBlock * const scope, BicliqueSet && factoringSets) const {
     399    const auto S = independentFactoringSets(std::move(factoringSets), 0);
     400    for (auto i : S) {
     401        factorize(typeId, scope, std::get<0>(i), std::get<1>(i));
     402    }
     403    return !S.empty();
     404}
     405
     406///** ------------------------------------------------------------------------------------------------------------- *
     407// * @brief processFactoringSets
     408// ** ------------------------------------------------------------------------------------------------------------- */
     409//inline bool FactorizeDFG::processFactoringSets(const TypeId typeId, BicliqueSet && factoringSets, ObjectSet & factorings) const {
     410//    const auto S = independentFactoringSets(std::move(factoringSets), 0);
     411//    for (auto i : S) {
     412//        factorings.push_back(factorize(typeId, findInsertionScope(std::get<1>(i)), std::get<0>(i), std::get<1>(i)));
     413//    }
     414//    return !S.empty();
     415//}
     416
     417/** ------------------------------------------------------------------------------------------------------------- *
     418 * @brief factor
     419 ** ------------------------------------------------------------------------------------------------------------- */
     420bool FactorizeDFG::factor(PabloBlock * const block) {
     421    Statement * stmt = block->front();
     422    bool factored = false;
     423    while (stmt) {
     424        if (isa<If>(stmt) || isa<While>(stmt)) {
     425            if (factor(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody())) {
     426                factored = true;
     427            }
     428        } else if (isa<Variadic>(stmt)) {
     429            if (processFactoringSets(stmt->getClassTypeId(), block, enumerateFactoringSets(cast<Variadic>(stmt)))) {
     430                factored = true;
     431            }
     432        }
     433        stmt = stmt->getNextNode();
     434    }
     435    return factored;
     436}
     437
     438///** ------------------------------------------------------------------------------------------------------------- *
     439// * @brief factor
     440// ** ------------------------------------------------------------------------------------------------------------- */
     441//void FactorizeDFG::factor(PabloFunction & function, const TypeId typeId) {
     442//    ObjectSet vars;
     443//    for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
     444//        vars.push_back(function.getParameter(i));
     445//    }
     446//    while (processFactoringSets(typeId, enumerateFactoringSets(vars, function.getEntryBlock(), typeId), vars));
     447//}
     448
     449/** ------------------------------------------------------------------------------------------------------------- *
     450 * @brief factor
     451 ** ------------------------------------------------------------------------------------------------------------- */
     452inline void FactorizeDFG::factor(PabloFunction & function) {
     453    while (factor(function.getEntryBlock()));
     454}
     455
     456//inline void print(PabloAST * expr, raw_ostream & out) {
     457//    if (isa<Statement>(expr)) {
     458//        PabloPrinter::print(cast<Statement>(expr), out);
     459//    } else {
     460//        PabloPrinter::print(expr, out);
     461//    }
     462//}
    29463
    30464/** ------------------------------------------------------------------------------------------------------------- *
     
    37471inline Statement * FactorizeDFG::lower(Variadic * const var, PabloBlock * block) const {
    38472
    39     using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *, int>;
     473    using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *, unsigned>;
    40474    using Vertex = Graph::vertex_descriptor;
    41475    using Map = flat_map<const PabloAST *, Vertex>;
    42476    using SchedulingData = std::pair<unsigned, PabloAST *>;
    43     using SchedulingQueue = std::priority_queue<SchedulingData, std::vector<SchedulingData>, std::greater<SchedulingData>>;
     477    using SchedulingPriorityQueue = std::priority_queue<SchedulingData, std::vector<SchedulingData>, std::greater<SchedulingData>>;
    44478
    45479    const unsigned NOT_STEP = 1;
     
    50484    assert (var->getParent() == block);
    51485    assert (var->getNumOperands() > 2);
    52 
    53     // Begin by computing a graph G depicting which operands are used by which statements. We know that
    54     // all of them are used by the Variadic but they might be used elsewhere in the current block.
    55 
    56 
    57     // If this operand was defined in this block, we want to indicate that in G as well so that we
    58     // don't mistakingly pair them together.
    59486
    60487    const unsigned operands = var->getNumOperands();
     
    166593    assert (num_edges(G) == var->getNumOperands());
    167594
    168     SchedulingQueue Q;
     595//    raw_os_ostream out(std::cerr);
     596
     597//    out << "==============================================================================\n";
     598//    PabloPrinter::print(var, out); out << '\n';
     599//    out << "------------------------------------------------------------------------------\n";
     600
     601//    out << "digraph G {\n";
     602//    for (auto u : make_iterator_range(vertices(G))) {
     603//        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
     604//            continue;
     605//        }
     606//        out << "v" << u << " [label=\"" << u << ": ";
     607//        PabloPrinter::print(G[u], out);
     608//        out << "\"];\n";
     609//    }
     610//    for (auto e : make_iterator_range(edges(G))) {
     611//        const auto s = source(e, G);
     612//        const auto t = target(e, G);
     613//        out << "v" << s << " -> v" << t << "[label=\"" << G[e] << "\"];\n";
     614//    }
     615
     616//    out << "}\n\n";
     617//    out.flush();
     618
     619//    out << "------------------------------------------------------------------------------\n";
     620
     621    SchedulingPriorityQueue Q;
    169622    while (num_edges(G) > 0) {
    170623
     
    184637        const auto u = source(f, G);
    185638        assert (u < operands);
     639        PabloAST * const op1 = var->getOperand(u);
    186640        const auto v = target(f, G);
    187641        assert (isa<Statement>(G[v]));
     642        remove_edge(f, G);
     643
    188644        // Since this might have been a target of a prior pairing, read the original operand value instead of
    189645        // G when checking which value is indicated by u.
    190         PabloAST * const op1 = var->getOperand(u);
    191646        block->setInsertPoint(cast<Statement>(G[v]));
    192         remove_edge(f, G);
    193 
    194647        if (LLVM_LIKELY(Q.size() > 0)) {
    195648            unsigned minQuantum = 0; PabloAST * op2 = nullptr;
     
    205658                    result = block->createXor(op1, op2);
    206659                }
    207                 Q.emplace(quantum + DESIRED_GAP, result);
    208                 G[v] = result; // update the insertion point node value
     660
     661//                out << " -- ";
     662//                print(op1, out);
     663//                out << " + ";
     664//                print(op2, out);
     665//                out << " -> ";
     666//                print(result, out);
     667//                out << '\n';
     668//                out.flush();
     669
     670                if (LLVM_LIKELY(isa<Statement>(result))) {
     671                    G[v] = result; // update the insertion point node value
     672                    quantum += DESIRED_GAP;
     673                } else {
     674                    G[v] = cast<Statement>(op2); // update the insertion point node value
     675                    quantum = estQuantum;
     676                }
     677                Q.emplace(quantum, result);
    209678                continue;
    210679            }
     
    212681        Q.emplace(quantum, op1);
    213682    }
     683
     684//    out << "------------------------------------------------------------------------------\n";
    214685
    215686    // If we've done our best to schedule the statements and have operands remaining in our queue, generate a
     
    223694        std::tie(q2, op2) = Q.top();
    224695        Q.pop();
     696
     697        assert (q2 >= q1);
    225698
    226699        PabloAST * result = nullptr;
     
    232705            result = block->createXor(op1, op2);
    233706        }
    234         Q.emplace(std::max(q1, q2) + DESIRED_GAP, result);
     707
     708//        out << " -- ";
     709//        print(op1, out);
     710//        out << " + ";
     711//        print(op2, out);
     712//        out << " -> ";
     713//        print(result, out);
     714//        out << '\n';
     715//        out.flush();
     716
     717        Q.emplace(q2 + DESIRED_GAP, result);
    235718    }
    236719
     
    238721    return var->replaceWith(std::get<1>(Q.top()));
    239722}
    240 
    241 #if 0
    242 using EnumerationMap = flat_map<const PabloAST *, unsigned>;
    243 
    244 inline void enumerate(PabloBlock * const block, EnumerationMap & M, std::vector<Statement *> & S) {
    245     for (Statement * stmt : *block) {
    246         M.emplace(stmt, static_cast<int>(S.size()));
    247         S.push_back(stmt);
    248     }
    249 }
    250 
    251 inline static unsigned indexOf(const PabloAST * const expr, const EnumerationMap & M) {
    252     assert (expr);
    253     const auto f = M.find(expr);
    254     assert (f != M.end());
    255     return f->second;
    256 }
    257 
    258 /** ------------------------------------------------------------------------------------------------------------- *
    259  * @brief lower
    260  *
    261  * The goal of this function is to try and lower a variadic operation into binary form while attempting to mitigate
    262  * register pressure under the assumption that LLVM is not going to significantly change the IR (which was observed
    263  * when assessing the ASM output of LLVM 3.6.1 using O3.)
    264  ** ------------------------------------------------------------------------------------------------------------- */
    265 inline Statement * FactorizeDFG::lower(Variadic * const var, PabloBlock * block) const {
    266 
    267     assert (var->getNumOperands() > 2);
    268 
    269     EnumerationMap M;
    270     std::vector<Statement *> S;
    271 
    272     enumerate(block, M, S);
    273 
    274     const int varIdx = indexOf(var, M);
    275 
    276     circular_buffer<std::tuple<unsigned, unsigned, PabloAST *>> lowered(var->getNumOperands());
    277     for (unsigned i = 0; i != var->getNumOperands(); ++i) {
    278         PabloAST * const op = var->getOperand(i);
    279 
    280         unsigned defIdx = 0;
    281         if (LLVM_LIKELY(isa<Statement>(op))) {
    282             Statement * producer = cast<Statement>(op);
    283             PabloBlock * scope = producer->getParent();
    284             while (scope && (scope != block)) {
    285                 producer = scope->getBranch();
    286                 scope = scope->getParent();
    287             }
    288             defIdx = producer ? indexOf(producer, M) : 0;
    289         }
    290 
    291         unsigned useIdx = defIdx;
    292         for (PabloAST * user : op->users()) {
    293             // if this user is in the current scope or a nested scope of this block
    294             if ((cast<Statement>(user)->getParent() == block) && (user != var)) {
    295                 useIdx = std::max(useIdx, indexOf(user, M));
    296             }
    297         }
    298         if (useIdx > varIdx) {
    299             useIdx = varIdx;
    300         }
    301         assert (!lowered.full());
    302         lowered.push_back(std::make_tuple(useIdx, defIdx, op));
    303     }
    304 
    305     std::sort(lowered.begin(), lowered.end());
    306 
    307     PabloAST * result = nullptr;
    308     while (lowered.size() > 1) {
    309 
    310         PabloAST * op1, * op2;
    311         unsigned def1, def2;
    312         unsigned use1, use2;
    313 
    314         std::tie(use1, def1, op1) = lowered.front(); lowered.pop_front();
    315         std::tie(use2, def2, op2) = lowered.front(); lowered.pop_front();
    316 
    317 //        if (((def1 < def2) ? ((def1 + 3) > def2) : ((def2 + 3) > def1)) && (lowered.size() > 0)) {
    318 //            unsigned def3 = def1;
    319 //            unsigned use3 = use1;
    320 //            PabloAST * op3 = op1;
    321 //            std::tie(use1, def1, op1) = lowered.front(); lowered.pop_front();
    322 //            lowered.push_front(std::make_tuple(use3, def3, op3));
    323 //        }
    324 
    325         // Is the last use of op1 prior to the definition of op2?
    326         if (use1 < def2) {
    327             use1 = def2;
    328         }
    329 
    330         block->setInsertPoint(S[use1]);
    331 
    332         if (isa<And>(var)) {
    333             result = block->createAnd(op1, op2);
    334         } else if (isa<Or>(var)) {
    335             result = block->createOr(op1, op2);
    336         } else { // if (isa<Xor>(var)) {
    337             result = block->createXor(op1, op2);
    338         }
    339 
    340         S[use1] = cast<Statement>(result);
    341 
    342         assert (!lowered.full());
    343         lowered.push_front(std::make_tuple(use1, use1, result));
    344     }
    345     assert (result);
    346 
    347     return var->replaceWith(result, true);
    348 }
    349 #endif
    350723
    351724/** ------------------------------------------------------------------------------------------------------------- *
     
    357730        if (isa<If>(stmt) || isa<While>(stmt)) {
    358731            lower(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    359         } else if ((stmt->getNumOperands() > 2) && (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt))) {
     732        } else if ((stmt->getNumOperands() > 2) && (isa<Variadic>(stmt))) {
    360733            stmt = lower(cast<Variadic>(stmt), block);
    361734            continue;
     
    372745}
    373746
    374 #if 0
    375 
    376 using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, PabloAST *>;
    377 using Vertex = Graph::vertex_descriptor;
    378 using Map = flat_map<const PabloAST *, Vertex>;
    379 
    380 using VertexSet = std::vector<PabloAST *>;
    381 using Biclique = std::pair<VertexSet, VertexSet>; // [{Operands}, {Users}]
    382 using BicliqueSet = std::set<Biclique>;
    383 using TypeId = PabloAST::ClassTypeId;
    384 
    385 /** ------------------------------------------------------------------------------------------------------------- *
    386  * @brief enumerateBicliques
    387  *
    388  * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
    389  * bicliques" by Alexe et. al. (2003).
    390  ** ------------------------------------------------------------------------------------------------------------- */
    391 inline void FactorizeDFG::enumerateBicliques(Variadic * const var, BicliqueSet & bicliques) {
    392     using IntersectionSets = flat_set<VertexSet>;
    393 
    394     IntersectionSets B1;
    395 
    396     const TypeId typeId = var->getClassTypeId();
    397     for (unsigned i = 0; i != var->getNumOperands(); ++i) {
    398         PabloAST * const op = var->getOperand(i);
    399         VertexSet B;
    400         B.reserve(op->getNumUses());
    401         for (PabloAST * user : op->users()) {
    402             if (user->getClassTypeId() == typeId) {
    403                 B.push_back(user);
    404             }
    405         }
    406         std::sort(B.begin(), B.end());
    407         B1.insert(std::move(B));
    408     }
    409 
    410     IntersectionSets B(B1);
    411 
    412     IntersectionSets Bi;
    413 
    414     VertexSet clique;
    415     for (auto i = B1.begin(); i != B1.end(); ++i) {
    416         for (auto j = i; ++j != B1.end(); ) {
    417             std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
    418             if (clique.size() > 0) {
    419                 if (B.count(clique) == 0) {
    420                     Bi.insert(clique);
    421                 }
    422                 clique.clear();
    423             }
    424         }
    425     }
    426 
    427     while (!Bi.empty()) {
    428         B.insert(Bi.begin(), Bi.end());
    429         IntersectionSets Bk;
    430         for (auto i = B1.begin(); i != B1.end(); ++i) {
    431             for (auto j = Bi.begin(); j != Bi.end(); ++j) {
    432                 std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
    433                 if (clique.size() > 0) {
    434                     if (B.count(clique) == 0) {
    435                         Bk.insert(clique);
    436                     }
    437                     clique.clear();
    438                 }
    439             }
    440         }
    441         Bi.swap(Bk);
    442     }
    443 
    444     for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
    445         VertexSet Ai(var->begin(), var->end());
    446         for (const PabloAST * user : *Bi) {
    447             VertexSet Aj(cast<Variadic>(user)->begin(), cast<Variadic>(user)->end());
    448             std::sort(Aj.begin(), Aj.end());
    449             VertexSet Ak;
    450             Ak.reserve(std::min<unsigned>(Ai.size(), Aj.size()));
    451             std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
    452             Ai.swap(Ak);
    453         }
    454         if (Ai.size() > 1 && Bi->size() > 1) {
    455             bicliques.emplace(std::move(Ai), std::move(*Bi));
    456         }
    457     }
    458 }
    459 
    460 /** ------------------------------------------------------------------------------------------------------------- *
    461  * @brief intersects
    462  ** ------------------------------------------------------------------------------------------------------------- */
    463 template <class Type>
    464 inline bool intersects(const Type & A, const Type & B) {
    465     auto first1 = A.begin(), last1 = A.end();
    466     auto first2 = B.begin(), last2 = B.end();
    467     while (first1 != last1 && first2 != last2) {
    468         if (*first1 < *first2) {
    469             ++first1;
    470         } else if (*first2 < *first1) {
    471             ++first2;
    472         } else {
    473             return true;
    474         }
    475     }
    476     return false;
    477 }
    478 
    479 /** ------------------------------------------------------------------------------------------------------------- *
    480  * @brief independentCliqueSets
    481  ** ------------------------------------------------------------------------------------------------------------- */
    482 inline void FactorizeDFG::independentCliqueSets(BicliqueSet & bicliques) {
    483     using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
    484 
    485     const auto l = bicliques.size();
    486     IndependentSetGraph I(l);
    487 
    488     // Initialize our weights and determine the constraints
    489     for (auto i = bicliques.begin(); i != bicliques.end(); ++i) {
    490         I[std::distance(bicliques.begin(), i)] = std::pow(std::get<0>(*i).size(), 2);
    491         for (auto j = i; ++j != bicliques.end(); ) {
    492             if (intersects(i->second, j->second) && intersects(i->first, j->first)) {
    493                 add_edge(std::distance(bicliques.begin(), i), std::distance(bicliques.begin(), j), I);
    494             }
    495         }
    496     }
    497 
    498     // Use the greedy algorithm to choose our independent set
    499     std::vector<Vertex> selected;
    500     for (;;) {
    501         unsigned w = 0;
    502         Vertex u = 0;
    503         for (unsigned i = 0; i != l; ++i) {
    504             if (I[i] > w) {
    505                 w = I[i];
    506                 u = i;
    507             }
    508         }
    509         if (w < 2) break;
    510         selected.push_back(u);
    511         I[u] = 0;
    512         for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
    513             I[v] = 0;
    514         }
    515     }
    516 
    517     // Sort the selected list and then remove the unselected cliques
    518     std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
    519     auto end = bicliques.end();
    520     for (const unsigned offset : selected) {
    521         end = bicliques.erase(bicliques.begin() + offset + 1, end) - 1;
    522     }
    523     bicliques.erase(bicliques.begin(), end);
    524 }
    525 
    526 /** ------------------------------------------------------------------------------------------------------------- *
    527  * @brief findInsertionPoint
    528  *
    529  * Look for the first user in this scope; if none can be found, look for the last operand.
    530  ** ------------------------------------------------------------------------------------------------------------- */
    531 inline PabloBlock * FactorizeDFG::findInsertionPoint(NodeSet & operands, NodeSet & users) const {
    532 
    533     ScopeSet scopes;
    534     scopes.reserve(users.size());
    535 
    536     for (PabloAST * user : users) {
    537         PabloBlock * const scope = cast<Statement>(user)->getParent(); assert (scope);
    538         if (std::find(scopes.begin(), scopes.end(), scope) == scopes.end()) {
    539             scopes.push_back(scope);
    540         }
    541     }
    542 
    543     if (LLVM_UNLIKELY(scopes.size() == 1)) {
    544         PabloBlock * const scope = scopes.front();
    545         Statement * stmt = scope->front();
    546         std::sort(users.begin(), users.end());
    547         while (stmt) {
    548             if (LLVM_UNLIKELY(std::binary_search(users.begin(), users.end(), stmt))) {
    549                 scope->setInsertPoint(stmt->getPrevNode());
    550                 return scope;
    551             }
    552             stmt = stmt->getNextNode();
    553         }
    554         llvm_unreachable("Failed to locate user in single scope block!");
    555     }
    556 
    557     while (scopes.size() > 1) {
    558         // Find the LCA of both scopes then add the LCA back to the list of scopes.
    559         PabloBlock * scope1 = scopes.back(); scopes.pop_back();
    560         PabloBlock * scope2 = scopes.back(); scopes.pop_back();
    561         if (scope1 != scope2) {
    562             unsigned depth1 = mScopeDepth.find(scope1)->second;
    563             unsigned depth2 = mScopeDepth.find(scope2)->second;
    564             // If one of these scopes is nested deeper than the other, scan upwards through
    565             // the scope tree until both scopes are at the same depth.
    566             while (depth1 > depth2) {
    567                 scope1 = scope1->getParent();
    568                 --depth1;
    569             }
    570             while (depth1 < depth2) {
    571                 scope2 = scope2->getParent();
    572                 --depth2;
    573             }
    574             // Then iteratively step backwards until we find a matching set of scopes; this
    575             // must be the LCA of our original scopes.
    576             while (scope1 != scope2) {
    577                 scope1 = scope1->getParent();
    578                 scope2 = scope2->getParent();
    579             }
    580             assert (scope1 && scope2);
    581         }
    582         scopes.push_back(scope1);
    583     }
    584     assert (scopes.size() == 1);
    585 
    586     PabloBlock * const scope = scopes.front();
    587     Statement * stmt = scope->back();
    588     std::sort(operands.begin(), operands.end());
    589     while (stmt) {
    590         if (isa<If>(stmt)) {
    591             for (Assign * def : cast<If>(stmt)->getDefined()) {
    592                 if (LLVM_UNLIKELY(std::binary_search(operands.begin(), operands.end(), def))) {
    593                     scope->setInsertPoint(stmt);
    594                     return scope;
    595                 }
    596             }
    597         } else if (isa<While>(stmt)) {
    598             for (Next * var : cast<While>(stmt)->getVariants()) {
    599                 if (LLVM_UNLIKELY(std::binary_search(operands.begin(), operands.end(), var))) {
    600                     scope->setInsertPoint(stmt);
    601                     return scope;
    602                 }
    603             }
    604         } else if (LLVM_UNLIKELY(std::binary_search(operands.begin(), operands.end(), stmt))) {
    605             scope->setInsertPoint(stmt);
    606             return scope;
    607         }
    608         stmt = stmt->getPrevNode();
    609     }
    610     scope->setInsertPoint(nullptr);
    611     return scope;
    612 }
    613 
    614 /** ------------------------------------------------------------------------------------------------------------- *
    615  * @brief processBicliques
    616  ** ------------------------------------------------------------------------------------------------------------- */
    617 void FactorizeDFG::processBicliques(BicliqueSet & bicliques) const {
    618     independentCliqueSets(bicliques);
    619     for (Biclique & B : bicliques) {
    620         VertexSet & operands = B.first;
    621         VertexSet & users = B.second;
    622         PabloBlock * const block = findInsertionPoint(operands, users);
    623         Variadic * factored = nullptr;
    624         if (isa<And>(users.front())) {
    625             factored = block->createAnd(operands.begin(), operands.end());
    626         } else if (isa<Or>(users.front())) {
    627             factored = block->createOr(operands.begin(), operands.end());
    628         } else { // if (isa<Xor>(var)) {
    629             factored = block->createXor(operands.begin(), operands.end());
    630         }
    631         for (PabloAST * user : users) {
    632             for (PabloAST * op : operands) {
    633                 cast<Variadic>(user)->deleteOperand(op);
    634             }
    635             cast<Variadic>(user)->addOperand(factored);
    636         }
    637     }
    638     bicliques.clear();
    639 }
    640 
    641 /** ------------------------------------------------------------------------------------------------------------- *
    642  * @brief factor
    643  *
    644  * Perform common subexpression elimination on the Variadic statements
    645  ** ------------------------------------------------------------------------------------------------------------- */
    646 void FactorizeDFG::factor(PabloBlock * const block, BicliqueSet & bicliques) const {
     747/** ------------------------------------------------------------------------------------------------------------- *
     748 * @brief initialize
     749 ** ------------------------------------------------------------------------------------------------------------- */
     750void FactorizeDFG::initialize(PabloBlock * const block, const unsigned depth) {
    647751    Statement * stmt = block->front();
    648     while (stmt) {
    649         if (isa<If>(stmt) || isa<While>(stmt)) {
    650             processBicliques(bicliques);
    651             factor(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), bicliques);
    652         } else if (stmt->getNumOperands() > 2 && (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt))) {
    653             enumerateBicliques(cast<Variadic>(stmt), bicliques);
    654         }
    655         stmt = stmt->getNextNode();
    656     }
    657     processBicliques(bicliques);
    658 }
    659 
    660 /** ------------------------------------------------------------------------------------------------------------- *
    661  * @brief factor
    662  ** ------------------------------------------------------------------------------------------------------------- */
    663 inline void FactorizeDFG::factor(PabloFunction & function) const {
    664     BicliqueSet bicliques;
    665     factor(function.getEntryBlock(), bicliques);
    666 }
    667 
    668 #endif
    669 
    670 #if 1
    671 
    672 using VertexSet = std::vector<PabloAST *>;
    673 using Biclique = std::pair<VertexSet, VertexSet>; // [{Operands}, {Users}]
    674 using BicliqueSet = std::vector<Biclique>;
    675 using TypeId = PabloAST::ClassTypeId;
    676 
    677 /** ------------------------------------------------------------------------------------------------------------- *
    678  * @brief findAllFactoringsOf
    679  *
    680  * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
    681  * bicliques" by Alexe et. al. (2003).
    682  ** ------------------------------------------------------------------------------------------------------------- */
    683 inline BicliqueSet FactorizeDFG::findAllFactoringsOf(Variadic * const var) {
    684     using IntersectionSets = flat_set<VertexSet>;
    685 
    686     IntersectionSets B1;
    687     const TypeId typeId = var->getClassTypeId();
    688     for (unsigned i = 0; i != var->getNumOperands(); ++i) {
    689         PabloAST * const op = var->getOperand(i);
    690         VertexSet B;
    691         B.reserve(op->getNumUses());
    692         for (PabloAST * user : op->users()) {
    693             if (user->getClassTypeId() == typeId) {
    694                 // Only consider a user who is in the same or a nested scope?
    695                 PabloBlock * scope = cast<Variadic>(user)->getParent();
    696                 while (scope) {
    697                     if (scope == var->getParent()) {
    698                         B.push_back(user);
    699                         break;
    700                     }
    701                     scope = scope->getParent();
    702                 }
    703 
    704 //                B.push_back(user);
    705             }
    706         }
    707         std::sort(B.begin(), B.end());
    708         B1.insert(std::move(B));
    709     }
    710 
    711     IntersectionSets B(B1);
    712 
    713     IntersectionSets Bi;
    714 
    715     VertexSet clique;
    716     for (auto i = B1.begin(); i != B1.end(); ++i) {
    717         for (auto j = i; ++j != B1.end(); ) {
    718             std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
    719             if (clique.size() > 0) {
    720                 if (B.count(clique) == 0) {
    721                     Bi.insert(clique);
    722                 }
    723                 clique.clear();
    724             }
    725         }
    726     }
    727 
    728     while (!Bi.empty()) {
    729         B.insert(Bi.begin(), Bi.end());
    730         IntersectionSets Bk;
    731         for (auto i = B1.begin(); i != B1.end(); ++i) {
    732             for (auto j = Bi.begin(); j != Bi.end(); ++j) {
    733                 std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
    734                 if (clique.size() > 0) {
    735                     if (B.count(clique) == 0) {
    736                         Bk.insert(clique);
    737                     }
    738                     clique.clear();
    739                 }
    740             }
    741         }
    742         Bi.swap(Bk);
    743     }
    744 
    745     BicliqueSet bicliques;
    746     for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
    747         VertexSet Ai(var->begin(), var->end());
    748         for (const PabloAST * user : *Bi) {
    749             VertexSet Aj(cast<Variadic>(user)->begin(), cast<Variadic>(user)->end());
    750             std::sort(Aj.begin(), Aj.end());
    751             VertexSet Ak;
    752             Ak.reserve(std::min<unsigned>(Ai.size(), Aj.size()));
    753             std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
    754             Ai.swap(Ak);
    755         }
    756         if (Ai.size() > 1 && Bi->size() > 1) {
    757             bicliques.emplace_back(std::move(Ai), std::move(*Bi));
    758         }
    759     }
    760     return bicliques;
    761 }
    762 
    763 /** ------------------------------------------------------------------------------------------------------------- *
    764  * @brief intersects
    765  ** ------------------------------------------------------------------------------------------------------------- */
    766 template <class Type>
    767 inline bool intersects(const Type & A, const Type & B) {
    768     auto first1 = A.begin(), last1 = A.end();
    769     auto first2 = B.begin(), last2 = B.end();
    770     assert (std::is_sorted(first1, last1));
    771     assert (std::is_sorted(first2, last2));
    772     while (first1 != last1 && first2 != last2) {
    773         if (*first1 < *first2) {
    774             ++first1;
    775         } else if (*first2 < *first1) {
    776             ++first2;
    777         } else {
    778             return true;
    779         }
    780     }
    781     return false;
    782 }
    783 
    784 /** ------------------------------------------------------------------------------------------------------------- *
    785  * @brief independentCliqueSets
    786  ** ------------------------------------------------------------------------------------------------------------- */
    787 inline void FactorizeDFG::independentCliqueSets(BicliqueSet & bicliques) {
    788     using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
    789     using Vertex = IndependentSetGraph::vertex_descriptor;
    790 
    791     const auto l = bicliques.size();
    792     IndependentSetGraph I(l);
    793 
    794     // Initialize our weights and determine the constraints
    795     for (auto i = bicliques.begin(); i != bicliques.end(); ++i) {
    796         I[std::distance(bicliques.begin(), i)] = std::pow(std::get<0>(*i).size(), 2);
    797         for (auto j = i; ++j != bicliques.end(); ) {
    798             if (intersects(i->second, j->second) && intersects(i->first, j->first)) {
    799                 add_edge(std::distance(bicliques.begin(), i), std::distance(bicliques.begin(), j), I);
    800             }
    801         }
    802     }
    803 
    804     // Use the greedy algorithm to choose our independent set
    805     std::vector<Vertex> selected;
    806     for (;;) {
    807         unsigned w = 0;
    808         Vertex u = 0;
    809         for (unsigned i = 0; i != l; ++i) {
    810             if (I[i] > w) {
    811                 w = I[i];
    812                 u = i;
    813             }
    814         }
    815         if (w < 2) break;
    816         selected.push_back(u);
    817         I[u] = 0;
    818         for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
    819             I[v] = 0;
    820         }
    821     }
    822 
    823     // Sort the selected list and then remove the unselected cliques
    824     std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
    825     auto end = bicliques.end();
    826     for (const unsigned offset : selected) {
    827         end = bicliques.erase(bicliques.begin() + offset + 1, end) - 1;
    828     }
    829     bicliques.erase(bicliques.begin(), end);
    830 }
    831 
    832 /** ------------------------------------------------------------------------------------------------------------- *
    833  * @brief findInsertionScope
    834  ** ------------------------------------------------------------------------------------------------------------- */
    835 inline PabloBlock * FactorizeDFG::findInsertionScope(const NodeSet & users) const {
    836     ScopeSet scopes;
    837     scopes.reserve(users.size());
    838 
    839     for (PabloAST * user : users) {
    840         PabloBlock * const scope = cast<Statement>(user)->getParent(); assert (scope);
    841         if (std::find(scopes.begin(), scopes.end(), scope) == scopes.end()) {
    842             scopes.push_back(scope);
    843         }
    844     }
    845 
    846     while (scopes.size() > 1) {
    847         // Find the LCA of both scopes then add the LCA back to the list of scopes.
    848         PabloBlock * scope1 = scopes.back(); scopes.pop_back();
    849         PabloBlock * scope2 = scopes.back(); scopes.pop_back();
    850         if (scope1 != scope2) {
    851             unsigned depth1 = scopeDepthOf(scope1);
    852             unsigned depth2 = scopeDepthOf(scope2);
    853             // If one of these scopes is nested deeper than the other, scan upwards through
    854             // the scope tree until both scopes are at the same depth.
    855             while (depth1 > depth2) {
    856                 scope1 = scope1->getParent();
    857                 --depth1;
    858             }
    859             while (depth1 < depth2) {
    860                 scope2 = scope2->getParent();
    861                 --depth2;
    862             }
    863             // Then iteratively step backwards until we find a matching set of scopes; this
    864             // must be the LCA of our original scopes.
    865             while (scope1 != scope2) {
    866                 scope1 = scope1->getParent();
    867                 scope2 = scope2->getParent();
    868             }
    869             assert (scope1 && scope2);
    870         }
    871         if (LLVM_LIKELY(std::find(scopes.begin(), scopes.end(), scope1) == scopes.end())) {
    872             scopes.push_back(scope1);
    873         }
    874     }
    875     assert (scopes.size() == 1);
    876 
    877     return scopes.front();
    878 }
    879 
    880 /** ------------------------------------------------------------------------------------------------------------- *
    881  * @brief makeCheckSet
    882  ** ------------------------------------------------------------------------------------------------------------- */
    883 FactorizeDFG::CheckSet FactorizeDFG::makeCheckSet(PabloBlock * const scope, const NodeSet & values) const {
    884     CheckSet checks;
    885     assert (scope);
    886     const unsigned baseScopeDepth = scopeDepthOf(scope);
    887     for (PabloAST * value : values) {
    888         if (isa<Statement>(value)) {
    889             unsigned scopeDepth = scopeDepthOf(cast<Statement>(value)->getParent());
    890             // Is this from a preceeding scope? Or a nested scope?
    891             if (scopeDepth < baseScopeDepth) {
    892                 continue;
    893             } else if (scopeDepth > baseScopeDepth) {
    894                 // If we're in a nested scope, we want to know what branch statement enters it and
    895                 // add that to our checks instead of the operand itself.
    896                 PabloBlock * nested = cast<Statement>(value)->getParent();
    897                 for (;;) {
    898                     assert (nested);
    899                     value = nested->getBranch();
    900                     nested = nested->getParent();
    901                     if (nested == scope) {
    902                         break;
    903                     }
    904                 }
    905             }
    906             checks.insert(value);
    907         }
    908     }
    909     return checks;
    910 }
    911 
    912 /** ------------------------------------------------------------------------------------------------------------- *
    913  * @brief firstIn
    914  ** ------------------------------------------------------------------------------------------------------------- */
    915 inline Statement * FactorizeDFG::firstIn(PabloBlock * const scope, Statement * stmt, const NodeSet & users) const {
    916     const auto checks = makeCheckSet(scope, users);
    917     while (stmt) {
    918         if (LLVM_UNLIKELY(checks.count(stmt) != 0)) {
    919             break;
    920         }
    921         stmt = stmt->getNextNode();
    922     }
    923     return stmt;
    924 }
    925 
    926 /** ------------------------------------------------------------------------------------------------------------- *
    927  * @brief lastIn
    928  ** ------------------------------------------------------------------------------------------------------------- */
    929 inline Statement * FactorizeDFG::lastIn(PabloBlock * const scope, Statement * stmt, const NodeSet & operands) const {
    930     const auto checks = makeCheckSet(scope, operands);
    931     while (stmt) {
    932         if (LLVM_UNLIKELY(checks.count(stmt) != 0)) {
    933             break;
    934         }
    935         stmt = stmt->getPrevNode();
    936     }
    937     return stmt;
    938 }
    939 
    940 /** ------------------------------------------------------------------------------------------------------------- *
    941  * @brief findInsertionPoint
    942  *
    943  * Look for the first user in this scope; if none can be found, look for the last operand.
    944  ** ------------------------------------------------------------------------------------------------------------- */
    945 inline PabloBlock * FactorizeDFG::findInsertionPoint(const NodeSet & operands, const NodeSet & users) const {
    946     PabloBlock * const scope = findInsertionScope(users);
    947     Statement * const lastOperand = lastIn(scope, scope->back(), operands);
    948     Statement * const firstUsage = firstIn(scope, lastOperand, users);
    949     scope->setInsertPoint(firstUsage ? firstUsage->getPrevNode() : lastOperand);
    950     return scope;
    951 }
    952 
    953 /** ------------------------------------------------------------------------------------------------------------- *
    954  * @brief factor
    955  ** ------------------------------------------------------------------------------------------------------------- */
    956 inline void FactorizeDFG::factor(Variadic * const var, Variadics & factors) const {
    957     if (var->getNumOperands() > 2) {
    958         BicliqueSet S = findAllFactoringsOf(var);
    959         if (S.empty()) return;
    960         independentCliqueSets(S);
    961         assert (S.size() > 0);
    962         for (Biclique & B : S) {
    963             VertexSet & operands = B.first;
    964             VertexSet & users = B.second;
    965             PabloBlock * const block = findInsertionPoint(operands, users);
    966             Variadic * factoring = nullptr;
    967             if (isa<And>(var)) {
    968                 factoring = block->createAnd(operands.begin(), operands.end());
    969             } else if (isa<Or>(var)) {
    970                 factoring = block->createOr(operands.begin(), operands.end());
    971             } else { // if (isa<Xor>(var)) {
    972                 factoring = block->createXor(operands.begin(), operands.end());
    973             }
    974             for (PabloAST * user : users) {
    975                 for (PabloAST * op : operands) {
    976                     cast<Variadic>(user)->deleteOperand(op);
    977                 }
    978                 cast<Variadic>(user)->addOperand(factoring);
    979             }
    980             if (factoring->getNumOperands() > 2) {
    981                 if (LLVM_UNLIKELY(factors.full())) {
    982                     factors.set_capacity(factors.capacity() + factors.capacity() / 2);
    983                 }
    984                 factors.push_back(factoring);
    985             }
    986         }
    987         if (var->getNumOperands() > 2) {
    988             if (LLVM_UNLIKELY(factors.full())) {
    989                 factors.set_capacity(factors.capacity() + factors.capacity() / 2);
    990             }
    991             factors.push_back(var);
    992         } else if (var->getNumOperands()  == 1) {
    993             var->replaceWith(var->getOperand(0));
    994         }
    995     }
    996 }
    997 
    998 /** ------------------------------------------------------------------------------------------------------------- *
    999  * @brief factor
    1000  *
    1001  * Perform common subexpression elimination on the Variadic statements
    1002  ** ------------------------------------------------------------------------------------------------------------- */
    1003 void FactorizeDFG::factor(PabloBlock * const block, Variadics & vars) const {
    1004     Statement * stmt = block->front();
    1005     while (stmt) {
    1006         if (isa<If>(stmt) || isa<While>(stmt)) {
    1007             factor(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), vars);
    1008         } else if (stmt->getNumOperands() > 2 && (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt))) {
    1009             assert (!vars.full());
    1010             vars.push_back(cast<Variadic>(stmt));
    1011         }
    1012         stmt = stmt->getNextNode();
    1013     }
    1014 }
    1015 
    1016 /** ------------------------------------------------------------------------------------------------------------- *
    1017  * @brief factor
    1018  ** ------------------------------------------------------------------------------------------------------------- */
    1019 inline void FactorizeDFG::factor(PabloFunction & function) const {
    1020     Variadics vars(mNumOfVariadics);
    1021     factor(function.getEntryBlock(), vars);
    1022     while (vars.size() > 0) {
    1023         Variadic * var = vars.front();
    1024         vars.pop_front();
    1025         factor(var, vars);
    1026     }
    1027 }
    1028 
    1029 #endif
    1030 
    1031 #if 0
    1032 
    1033 using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, PabloAST *>;
    1034 using Vertex = Graph::vertex_descriptor;
    1035 using Map = flat_map<const PabloAST *, Vertex>;
    1036 
    1037 using VertexSet = std::vector<Vertex>;
    1038 using Biclique = std::pair<VertexSet, VertexSet>; // [{Operands}, {Users}]
    1039 using BicliqueSet = std::vector<Biclique>;
    1040 using TypeId = PabloAST::ClassTypeId;
    1041 
    1042 /** ------------------------------------------------------------------------------------------------------------- *
    1043  * @brief enumerateBicliques
    1044  *
    1045  * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
    1046  * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies in set A to be in
    1047  * bipartition A and their adjacencies to be in B.
    1048   ** ------------------------------------------------------------------------------------------------------------- */
    1049 template <class Graph>
    1050 static BicliqueSet enumerateBicliques(const Graph & G, const VertexSet & A) {
    1051     using IntersectionSets = std::set<VertexSet>;
    1052 
    1053     IntersectionSets B1;
    1054     for (auto u : A) {
    1055         if (out_degree(u, G) > 0) {
    1056             VertexSet incomingAdjacencies;
    1057             incomingAdjacencies.reserve(out_degree(u, G));
    1058             for (auto e : make_iterator_range(out_edges(u, G))) {
    1059                 incomingAdjacencies.push_back(target(e, G));
    1060             }
    1061             std::sort(incomingAdjacencies.begin(), incomingAdjacencies.end());
    1062             B1.insert(std::move(incomingAdjacencies));
    1063         }
    1064     }
    1065 
    1066     IntersectionSets B(B1);
    1067 
    1068     IntersectionSets Bi;
    1069 
    1070     VertexSet clique;
    1071     for (auto i = B1.begin(); i != B1.end(); ++i) {
    1072         for (auto j = i; ++j != B1.end(); ) {
    1073             std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
    1074             if (clique.size() > 0) {
    1075                 if (B.count(clique) == 0) {
    1076                     Bi.insert(clique);
    1077                 }
    1078                 clique.clear();
    1079             }
    1080         }
    1081     }
    1082 
    1083     for (;;) {
    1084         if (Bi.empty()) {
    1085             break;
    1086         }
    1087         B.insert(Bi.begin(), Bi.end());
    1088         IntersectionSets Bk;
    1089         for (auto i = B1.begin(); i != B1.end(); ++i) {
    1090             for (auto j = Bi.begin(); j != Bi.end(); ++j) {
    1091                 std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
    1092                 if (clique.size() > 0) {
    1093                     if (B.count(clique) == 0) {
    1094                         Bk.insert(clique);
    1095                     }
    1096                     clique.clear();
    1097                 }
    1098             }
    1099         }
    1100         Bi.swap(Bk);
    1101     }
    1102 
    1103     BicliqueSet cliques;
    1104     cliques.reserve(B.size());
    1105     for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
    1106         VertexSet Ai(A);
    1107         for (const Vertex u : *Bi) {
    1108             VertexSet Aj;
    1109             Aj.reserve(in_degree(u, G));
    1110             for (auto e : make_iterator_range(in_edges(u, G))) {
    1111                 Aj.push_back(source(e, G));
    1112             }
    1113             std::sort(Aj.begin(), Aj.end());
    1114             VertexSet Ak;
    1115             Ak.reserve(std::min(Ai.size(), Aj.size()));
    1116             std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
    1117             Ai.swap(Ak);
    1118         }
    1119         assert (Ai.size() > 0); // cannot happen if this algorithm is working correctly
    1120         cliques.emplace_back(std::move(Ai), std::move(*Bi));
    1121     }
    1122     return std::move(cliques);
    1123 }
    1124 
    1125 /** ------------------------------------------------------------------------------------------------------------- *
    1126  * @brief intersects
    1127  ** ------------------------------------------------------------------------------------------------------------- */
    1128 template <class Type>
    1129 inline bool intersects(const Type & A, const Type & B) {
    1130     auto first1 = A.begin(), last1 = A.end();
    1131     auto first2 = B.begin(), last2 = B.end();
    1132     while (first1 != last1 && first2 != last2) {
    1133         if (*first1 < *first2) {
    1134             ++first1;
    1135         } else if (*first2 < *first1) {
    1136             ++first2;
    1137         } else {
    1138             return true;
    1139         }
    1140     }
    1141     return false;
    1142 }
    1143 
    1144 /** ------------------------------------------------------------------------------------------------------------- *
    1145  * @brief getMaximalIndependentBicliques
    1146  ** ------------------------------------------------------------------------------------------------------------- */
    1147 template <unsigned side = 1>
    1148 inline static BicliqueSet && maximalIndependentBicliques(BicliqueSet && cliques, const unsigned minimum = 1) {
    1149     using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
    1150 
    1151     static_assert((side == 0 || side == 1), "Side must be 0 (bipartition A) or 1 (bipartition B)");
    1152     assert ("Minimum must be at least 1 or an infinite number of empty sets would be generated!" && minimum > 0);
    1153 
    1154     const auto l = cliques.size();
    1155     IndependentSetGraph I(l);
    1156 
    1157     // Initialize our weights
    1158     for (unsigned i = 0; i != l; ++i) {
    1159         I[i] = std::pow(std::get<side>(cliques[i]).size(), 2);
    1160     }
    1161 
    1162     // Determine our constraints
    1163     for (unsigned i = 0; i != l; ++i) {
    1164         for (unsigned j = i + 1; j != l; ++j) {
    1165             if (intersects(std::get<side>(cliques[i]), std::get<side>(cliques[j]))) {
    1166                 add_edge(i, j, I);
    1167             }
    1168         }
    1169     }
    1170 
    1171     // Use the greedy algorithm to choose our independent set
    1172     VertexSet selected;
    1173     for (;;) {
    1174         unsigned w = 0;
    1175         Vertex u = 0;
    1176         for (unsigned i = 0; i != l; ++i) {
    1177             if (I[i] > w) {
    1178                 w = I[i];
    1179                 u = i;
    1180             }
    1181         }
    1182         if (w < minimum) break;
    1183         selected.push_back(u);
    1184         I[u] = 0;
    1185         for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
    1186             I[v] = 0;
    1187         }
    1188     }
    1189 
    1190     // Sort the selected list and then remove the unselected cliques
    1191     std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
    1192     auto end = cliques.end();
    1193     for (const unsigned offset : selected) {
    1194         end = cliques.erase(cliques.begin() + offset + 1, end) - 1;
    1195     }
    1196     cliques.erase(cliques.begin(), end);
    1197 
    1198     return std::move(cliques);
    1199 }
    1200 
    1201 /** ------------------------------------------------------------------------------------------------------------- *
    1202  * @brief factor
    1203  ** ------------------------------------------------------------------------------------------------------------- */
    1204 template<class Type>
    1205 inline void factorAny(Graph & G, VertexSet & A, const Biclique & Si, PabloBlock * const block) {
    1206 
    1207     static_assert (std::is_same<Type, And>::value || std::is_same<Type, Or>::value || std::is_same<Type, Xor>::value, "Can only factor And, Or or Xor statements here!");
    1208 
    1209     flat_set<Statement *> S;
    1210     for (auto u : Si.first) {
    1211         if (isa<Type>(G[u])) {
    1212             S.insert(cast<Type>(G[u]));
    1213         }
    1214     }
    1215     if (S.empty()) {
    1216         return;
    1217     }
    1218     // find the insertion point for this statement type
    1219     for (Statement * ip : *block) {
    1220         if (S.count(ip)) {
    1221             block->setInsertPoint(ip->getPrevNode());
    1222             break;
    1223         }
    1224     }
    1225     Variadic * factored = nullptr;
    1226     if (std::is_same<Type, And>::value) {
    1227         factored = block->createAnd(Si.second.size());
    1228     } else if (std::is_same<Type, Or>::value) {
    1229         factored = block->createOr(Si.second.size());
    1230     } else if (std::is_same<Type, Xor>::value) {
    1231         factored = block->createXor(Si.second.size());
    1232     }
    1233     const auto u = add_vertex(factored, G);
    1234     A.push_back(u);
    1235     for (auto v : Si.second) {
    1236         factored->addOperand(G[v]);
    1237         add_edge(u, v, G);
    1238     }
    1239     const auto w = add_vertex(factored, G);
    1240     for (auto u : Si.first) {
    1241         if (isa<Type>(G[u])) {
    1242             Type * factoring = cast<Type>(G[u]);
    1243             for (auto v : Si.second) {
    1244                 factoring->deleteOperand(G[v]);
    1245                 remove_edge(u, v, G);
    1246             }
    1247             factoring->addOperand(factored);
    1248             add_edge(u, w, G);
    1249         }
    1250     }
    1251 }
    1252 
    1253 /** ------------------------------------------------------------------------------------------------------------- *
    1254  * @brief eliminateCommonSubexpressions
    1255  ** ------------------------------------------------------------------------------------------------------------- */
    1256 void eliminateCommonSubexpressions(Graph & G, VertexSet & A, PabloBlock * const block) {
    1257     for (;;) {
    1258         const auto S = maximalIndependentBicliques<1>(enumerateBicliques(G, A), 2);
    1259         if (S.empty()) {
    1260             break;
    1261         }
    1262         for (const Biclique Si : S) {
    1263             factorAny<And>(G, A, Si, block);
    1264             factorAny<Or>(G, A, Si, block);
    1265             factorAny<Xor>(G, A, Si, block);
    1266         }
    1267     }
    1268 }
    1269 
    1270 /** ------------------------------------------------------------------------------------------------------------- *
    1271  * @brief factor
    1272  *
    1273  * Perform common subexpression elimination on the Variadic statements
    1274  ** ------------------------------------------------------------------------------------------------------------- */
    1275 void FactorizeDFG::factor(PabloBlock * const block) {
    1276 
    1277     Graph G;
    1278     VertexSet A;
    1279     Map B;
    1280 
    1281     Statement * stmt = block->front();
    1282     while (stmt) {
    1283         if (isa<If>(stmt) || isa<While>(stmt)) {
    1284             eliminateCommonSubexpressions(G, A, block);
    1285             G.clear(); A.clear(); B.clear();
    1286             factor(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    1287         } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
    1288             // When we encounter a reassociative statement, add it and its operands to our bigraph G.
    1289             const auto u = add_vertex(stmt, G);
    1290             A.push_back(u);
    1291             for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    1292                 auto f = B.find(stmt->getOperand(i));
    1293                 if (f == B.end()) {
    1294                     f = B.emplace(stmt->getOperand(i), add_vertex(stmt->getOperand(i), G)).first;
    1295                 }
    1296                 add_edge(f->second, u, G);
    1297             }
    1298         }
    1299         stmt = stmt->getNextNode();
    1300     }
    1301     eliminateCommonSubexpressions(G, A, block);
    1302 }
    1303 #endif
    1304 
    1305 #if 0
    1306 
    1307 using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, PabloAST *>;
    1308 using Matrix = adjacency_matrix<directedS>;
    1309 using Vertex = Graph::vertex_descriptor;
    1310 using Map = flat_map<const PabloAST *, Vertex>;
    1311 using TypeId = PabloAST::ClassTypeId;
    1312 
    1313 /** ------------------------------------------------------------------------------------------------------------- *
    1314  * @brief getVertex
    1315  ** ------------------------------------------------------------------------------------------------------------- */
    1316 static inline Vertex getVertex(PabloAST * expr, Graph & G, Map & M) {
    1317     auto f = M.find(expr);
    1318     if (LLVM_LIKELY(f != M.end())) {
    1319         return f->second;
    1320     } else {
    1321         const Vertex u = add_vertex(expr, G);
    1322         M.emplace(expr, u);
    1323         return u;
    1324     }
    1325 }
    1326 
    1327 /** ------------------------------------------------------------------------------------------------------------- *
    1328  * @brief buildDependencyGraph
    1329  ** ------------------------------------------------------------------------------------------------------------- */
    1330 static void buildDependencyGraph(PabloBlock * const block, Graph & G, Map & M) {
    1331     Statement * stmt = block->front();
    1332     while (stmt) {
    1333         if (isa<If>(stmt) || isa<While>(stmt)) {
    1334             buildDependencyGraph(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), G, M);
    1335         } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
    1336             const Vertex u = getVertex(stmt, G, M);
    1337             for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    1338                 add_edge(getVertex(stmt->getOperand(i), G, M), u, G);
    1339             }
    1340         }
    1341         stmt = stmt->getNextNode();
    1342     }
    1343 }
    1344 
    1345 /** ------------------------------------------------------------------------------------------------------------- *
    1346  * @brief transitiveClosure
    1347  ** ------------------------------------------------------------------------------------------------------------- */
    1348 static Matrix transitiveClosureOf(const Graph & G) {
    1349     std::vector<Vertex> rto; // reverse topological ordering
    1350     rto.reserve(num_vertices(G));
    1351     topological_sort(G, std::back_inserter(rto));
    1352     Matrix M(num_vertices(G));
    1353     for (auto u : rto) {
    1354         for (auto ej : make_iterator_range(in_edges(u, G))) {
    1355             add_edge(source(ej, G), target(ej, G), M);
    1356         }
    1357         for (auto ei : make_iterator_range(out_edges(u, M))) {
    1358             for (auto ej : make_iterator_range(in_edges(u, G))) {
    1359                 add_edge(source(ej, G), target(ei, M), M);
    1360             }
    1361         }
    1362         add_edge(u, u, M);
    1363     }
    1364     return std::move(M);
    1365 }
    1366 
    1367 using VertexSet = std::vector<Vertex>;
    1368 using Biclique = std::pair<VertexSet, VertexSet>; // [{Operands}, {Users}]
    1369 using BicliqueSet = flat_set<Biclique>;
    1370 using IntersectionSets = std::set<VertexSet>;
    1371 
    1372 /** ------------------------------------------------------------------------------------------------------------- *
    1373  * @brief enumerateBicliques
    1374  *
    1375  * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
    1376  * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies in set A to be in
    1377  * bipartition A and their adjacencies to be in B.
    1378   ** ------------------------------------------------------------------------------------------------------------- */
    1379 inline static void enumerateBicliques(VertexSet & A, VertexSet & B, const Graph & G, BicliqueSet & bicliques) {
    1380 
    1381     std::sort(A.begin(), A.end());
    1382     std::sort(B.begin(), B.end());
    1383 
    1384     VertexSet S;
    1385     IntersectionSets B1;
    1386     for (auto u : A) {
    1387         S.reserve(out_degree(u, G));
    1388         for (auto e : make_iterator_range(out_edges(u, G))) {
    1389             S.push_back(target(e, G));
    1390         }
    1391         assert (S.size() > 0);
    1392         std::sort(S.begin(), S.end());
    1393         VertexSet T;       
    1394         std::set_intersection(B.begin(), B.end(), S.begin(), S.end(), std::back_inserter(T));
    1395         assert (T.size() > 0);
    1396         B1.emplace(std::move(T));
    1397         S.clear();
    1398     }
    1399 
    1400     IntersectionSets C(B1);
    1401     IntersectionSets Bi;
    1402     for (auto i = B1.begin(); i != B1.end(); ++i) {
    1403         for (auto j = i; ++j != B1.end(); ) {
    1404             std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(S));
    1405             if (S.size() > 0) {
    1406                 if (C.count(S) == 0) {
    1407                     Bi.insert(S);
    1408                 }
    1409                 S.clear();
    1410             }
    1411         }
    1412     }
    1413 
    1414     for (;;) {
    1415         if (Bi.empty()) {
    1416             break;
    1417         }
    1418         C.insert(Bi.begin(), Bi.end());
    1419         IntersectionSets Bk;
    1420         for (auto i = B1.begin(); i != B1.end(); ++i) {
    1421             for (auto j = Bi.begin(); j != Bi.end(); ++j) {
    1422                 std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(S));
    1423                 if (S.size() > 0) {
    1424                     if (C.count(S) == 0) {
    1425                         Bk.insert(S);
    1426                     }
    1427                     S.clear();
    1428                 }
    1429             }
    1430         }
    1431         Bi.swap(Bk);
    1432     }
    1433 
    1434     for (auto Bi = C.begin(); Bi != C.end(); ++Bi) {
    1435         VertexSet Ai(A);
    1436         for (const Vertex u : *Bi) {
    1437             VertexSet Aj;
    1438             Aj.reserve(in_degree(u, G));
    1439             for (auto e : make_iterator_range(in_edges(u, G))) {
    1440                 Aj.push_back(source(e, G));
    1441             }
    1442             std::sort(Aj.begin(), Aj.end());
    1443             VertexSet Ak;
    1444             Ak.reserve(std::min(Ai.size(), Aj.size()));
    1445             std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
    1446             Ai.swap(Ak);
    1447         }
    1448         assert (Ai.size() > 0); // cannot happen if this algorithm is working correctly
    1449         if (Ai.size() > 1 && Bi->size() > 1) {
    1450             bicliques.emplace(std::move(Ai), std::move(*Bi));
    1451         }
    1452     }
    1453 }
    1454 
    1455 /** ------------------------------------------------------------------------------------------------------------- *
    1456  * @brief analyzeGraph
    1457  ** ------------------------------------------------------------------------------------------------------------- */
    1458 inline static void analyzeGraph(const Vertex u, Graph & G, const Matrix & M, BicliqueSet & bicliques, const unsigned traversalLimit = 10) {
    1459 
    1460     VertexSet A;
    1461     VertexSet B;
    1462 
    1463     std::vector<bool> visited(num_vertices(G), false);
    1464     circular_buffer<Vertex> Q(64);
    1465     const TypeId typeId = G[u]->getClassTypeId();
    1466 
    1467     Vertex v = u;
    1468     visited[v] = true;
    1469     for (;;) {
    1470         bool independent = true;
    1471         for (auto w : B) {
    1472             if (M.get_edge(v, w)) {
    1473                 independent = false;
    1474                 break;
    1475             }
    1476         }
    1477         if (independent) {
    1478             B.push_back(v);
    1479             if (B.size() < traversalLimit) {
    1480                 for (auto e : make_iterator_range(in_edges(v, G))) {
    1481                     const auto w = source(e, G);
    1482                     if (visited[w]) {
    1483                         continue;
    1484                     }
    1485                     bool independent = true;
    1486                     for (auto x : A) {
    1487                         if (M.get_edge(w, x)) {
    1488                             independent = false;
    1489                             break;
    1490                         }
    1491                     }
    1492                     visited[w] = true;
    1493                     if (independent) {
    1494                         A.push_back(w);
    1495                         for (auto e : make_iterator_range(out_edges(w, G))) {
    1496                             const auto x = target(e, G);
    1497                             if (visited[x]) {
    1498                                 continue;
    1499                             }
    1500                             visited[x] = true;
    1501                             if (G[x]->getClassTypeId() == typeId) {
    1502                                 if (LLVM_UNLIKELY(Q.full())) {
    1503                                     Q.set_capacity(Q.capacity() + (Q.capacity() / 2));
    1504                                 }
    1505                                 Q.push_back(x);
    1506                             }
    1507                         }
    1508                     }
    1509                 }
    1510             }
    1511         }
    1512         if (Q.empty()) {
    1513             break;
    1514         }
    1515         v = Q.front();
    1516         Q.pop_front();
    1517     }
    1518 
    1519     enumerateBicliques(A, B, G, bicliques);
    1520 }
    1521 
    1522 /** ------------------------------------------------------------------------------------------------------------- *
    1523  * @brief intersects
    1524  ** ------------------------------------------------------------------------------------------------------------- */
    1525 template <class Type>
    1526 inline bool intersects(const Type & A, const Type & B) {
    1527     auto first1 = A.begin(), last1 = A.end();
    1528     auto first2 = B.begin(), last2 = B.end();
    1529     while (first1 != last1 && first2 != last2) {
    1530         if (*first1 < *first2) {
    1531             ++first1;
    1532         } else if (*first2 < *first1) {
    1533             ++first2;
    1534         } else {
    1535             return true;
    1536         }
    1537     }
    1538     return false;
    1539 }
    1540 
    1541 /** ------------------------------------------------------------------------------------------------------------- *
    1542  * @brief independentCliqueSets
    1543  ** ------------------------------------------------------------------------------------------------------------- */
    1544 inline static void independentCliqueSets(BicliqueSet & bicliques, const unsigned minimum) {
    1545     using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
    1546 
    1547     const auto l = bicliques.size();
    1548     IndependentSetGraph I(l);
    1549 
    1550     // Initialize our weights and determine the constraints
    1551     for (auto i = bicliques.begin(); i != bicliques.end(); ++i) {
    1552         I[std::distance(bicliques.begin(), i)] = std::pow(std::get<0>(*i).size(), 2);
    1553         for (auto j = i; ++j != bicliques.end(); ) {
    1554             if (intersects(std::get<1>(*i), std::get<1>(*j))) {
    1555                 add_edge(std::distance(bicliques.begin(), i), std::distance(bicliques.begin(), j), I);
    1556             }
    1557         }
    1558     }
    1559 
    1560     // Use the greedy algorithm to choose our independent set
    1561     VertexSet selected;
    1562     for (;;) {
    1563         unsigned w = 0;
    1564         Vertex u = 0;
    1565         for (unsigned i = 0; i != l; ++i) {
    1566             if (I[i] > w) {
    1567                 w = I[i];
    1568                 u = i;
    1569             }
    1570         }
    1571         if (w < minimum) break;
    1572         selected.push_back(u);
    1573         I[u] = 0;
    1574         for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
    1575             I[v] = 0;
    1576         }
    1577     }
    1578 
    1579     // Sort the selected list and then remove the unselected cliques
    1580     std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
    1581     auto end = bicliques.end();
    1582     for (const unsigned offset : selected) {
    1583         end = bicliques.erase(bicliques.begin() + offset + 1, end) - 1;
    1584     }
    1585     bicliques.erase(bicliques.begin(), end);
    1586 }
    1587 
    1588 /** ------------------------------------------------------------------------------------------------------------- *
    1589  * @brief chooseInsertionPoint
    1590  ** ------------------------------------------------------------------------------------------------------------- */
    1591 inline PabloBlock * FactorizeDFG::chooseInsertionScope(const NodeSet & users) {
    1592 
    1593     ScopeSet scopes;
    1594     scopes.reserve(users.size());
    1595 
    1596     flat_set<PabloBlock *> visited;
    1597     visited.reserve(users.size());
    1598 
    1599     for (PabloAST * user : users) {
    1600         PabloBlock * const scope = cast<Statement>(user)->getParent();
    1601         assert (scope);
    1602         if (visited.insert(scope).second) {
    1603             scopes.push_back(scope);
    1604         }
    1605     }
    1606 
    1607     while (scopes.size() > 1) {
    1608         // Find the LCA of both scopes then add the LCA back to the list of scopes.
    1609         PabloBlock * scope1 = scopes.back(); scopes.pop_back();
    1610         PabloBlock * scope2 = scopes.back(); scopes.pop_back();
    1611         if (scope1 != scope2) {
    1612             unsigned depth1 = mScopeDepth.find(scope1)->second;
    1613             unsigned depth2 = mScopeDepth.find(scope2)->second;
    1614             // If one of these scopes is nested deeper than the other, scan upwards through
    1615             // the scope tree until both scopes are at the same depth.
    1616             while (depth1 > depth2) {
    1617                 scope1 = scope1->getParent();
    1618                 --depth1;
    1619             }
    1620             while (depth1 < depth2) {
    1621                 scope2 = scope2->getParent();
    1622                 --depth2;
    1623             }
    1624             // Then iteratively step backwards until we find a matching set of scopes; this
    1625             // must be the LCA of our original scopes.
    1626             while (scope1 != scope2) {
    1627                 scope1 = scope1->getParent();
    1628                 scope2 = scope2->getParent();
    1629             }
    1630             assert (scope1 && scope2);
    1631         }
    1632         scopes.push_back(scope1);
    1633     }
    1634     assert (scopes.size() == 1);
    1635     return scopes[0];
    1636 }
    1637 
    1638 /** ------------------------------------------------------------------------------------------------------------- *
    1639  * @brief findInsertionPoint
    1640  ** ------------------------------------------------------------------------------------------------------------- */
    1641 void FactorizeDFG::findInsertionPoint(const NodeSet & operands, PabloBlock * const scope) {
    1642     Statement * stmt = scope->back();
    1643     scope->setInsertPoint(nullptr);
    1644     assert (std::is_sorted(operands.begin(), operands.end()));
    1645     while (stmt) {
    1646         if (isa<If>(stmt)) {
    1647             for (Assign * def : cast<If>(stmt)->getDefined()) {
    1648                 if (std::binary_search(operands.begin(), operands.end(), def)) {
    1649                     scope->setInsertPoint(stmt);
    1650                     return;
    1651                 }
    1652             }
    1653         } else if (isa<While>(stmt)) {
    1654             for (Next * var : cast<While>(stmt)->getVariants()) {
    1655                 if (std::binary_search(operands.begin(), operands.end(), var)) {
    1656                     scope->setInsertPoint(stmt);
    1657                     return;
    1658                 }
    1659             }
    1660         } else if (std::binary_search(operands.begin(), operands.end(), stmt)) {
    1661             scope->setInsertPoint(stmt);
    1662             break;
    1663         }
    1664         stmt = stmt->getPrevNode();
    1665     }
    1666 }
    1667 
    1668 /** ------------------------------------------------------------------------------------------------------------- *
    1669  * @brief factor
    1670  ** ------------------------------------------------------------------------------------------------------------- */
    1671 inline void FactorizeDFG::factor(PabloFunction & function) {
    1672 
    1673 //    raw_os_ostream out(std::cerr);
    1674 
    1675 //    out << "BEFORE:\n\n";
    1676 //    PabloPrinter::print(function, out);
    1677 //    out << "******************************************\n";
    1678 //    out.flush();
    1679 
    1680     for (;;) {
    1681 
    1682         Graph G;
    1683         {
    1684             Map M;
    1685             // Let G be a DAG representing each associative statement and its inputs
    1686             buildDependencyGraph(function.getEntryBlock(), G, M);
    1687         }
    1688 
    1689         BicliqueSet S;
    1690         {
    1691             const Matrix M = transitiveClosureOf(G);
    1692             for (const Vertex u : make_iterator_range(vertices(M))) {
    1693                 if ((in_degree(u, G) > 2) && (isa<And>(G[u]) || isa<Or>(G[u]) || isa<Xor>(G[u]))) {
    1694                     analyzeGraph(u, G, M, S);
    1695                 }
    1696             }
    1697         }
    1698 
    1699         independentCliqueSets(S, 2);
    1700 
    1701         if (S.empty()) {
    1702             break;
    1703         }
    1704 
    1705         std::vector<PabloAST *> operands;
    1706         std::vector<PabloAST *> users;
    1707 
    1708         for (const Biclique & B : S) {
    1709             for (auto u : std::get<0>(B)) {
    1710                 operands.push_back(G[u]);
    1711             }
    1712             std::sort(operands.begin(), operands.end());
    1713 
    1714             for (auto u : std::get<1>(B)) {
    1715                 users.push_back(G[u]);
    1716             }
    1717             std::sort(users.begin(), users.end());
    1718 
    1719 //            out << " -- factoring {";
    1720 //            for (PabloAST * operand : operands) {
    1721 //                out << ' ';
    1722 //                PabloPrinter::print(operand, out);
    1723 //            }
    1724 //            out << " } from { ";
    1725 //            for (PabloAST * user : users) {
    1726 //                out << ' ';
    1727 //                PabloPrinter::print(user, out);
    1728 //            }
    1729 //            out << " } -> ";
    1730 
    1731             const TypeId typeId = users.front()->getClassTypeId();
    1732             assert(typeId == TypeId::And || typeId == TypeId::Or || typeId == TypeId::Xor);
    1733             #ifndef NDEBUG
    1734             for (PabloAST * user : users) {
    1735                 assert(user->getClassTypeId() == typeId);
    1736             }
    1737             #endif
    1738             PabloBlock * const block = chooseInsertionScope(users);
    1739             findInsertionPoint(operands, block);
    1740             Variadic * factored = nullptr;
    1741             if (typeId == TypeId::And) {
    1742                 factored = block->createAnd(operands.begin(), operands.end());
    1743             } else if (typeId == TypeId::Or) {
    1744                 factored = block->createOr(operands.begin(), operands.end());
    1745             } else { // if (isa<Xor>(var)) {
    1746                 factored = block->createXor(operands.begin(), operands.end());
    1747             }
    1748 
    1749 //            PabloPrinter::print(factored, out);
    1750 //            out << '\n';
    1751 //            out.flush();
    1752 
    1753             for (PabloAST * user : users) {
    1754                 for (PabloAST * op : operands) {
    1755                     cast<Variadic>(user)->deleteOperand(op);
    1756                 }
    1757                 cast<Variadic>(user)->addOperand(factored);
    1758             }
    1759             operands.clear();
    1760             users.clear();
    1761         }
    1762 //        out << "-----------------------------------------------------------------\n";
    1763     }
    1764 
    1765 //    out << "AFTER:\n\n";
    1766 //    PabloPrinter::print(function, out);
    1767 //    out << "******************************************\n";
    1768 
    1769 }
    1770 
    1771 
    1772 #endif
    1773 
    1774 /** ------------------------------------------------------------------------------------------------------------- *
    1775  * @brief deMorgansExpansion
    1776  *
    1777  * Apply the De Morgans' law to any negated And or Or statement with the intent of further coalescing its operands
    1778  * thereby allowing the Simplifier to check for tautologies and contradictions.
    1779  ** ------------------------------------------------------------------------------------------------------------- */
    1780 inline void FactorizeDFG::deMorgansExpansion(Not * const var, PabloBlock * const block) {
    1781     PabloAST * const negatedVar = var->getOperand(0);
    1782     if (isa<And>(negatedVar) || isa<Or>(negatedVar)) {
    1783         const TypeId desiredTypeId = isa<And>(negatedVar) ? TypeId::Or : TypeId::And;
    1784         bool canApplyDeMorgans = true;
    1785         for (PabloAST * user : var->users()) {
    1786             if (desiredTypeId != user->getClassTypeId()) {
    1787                 canApplyDeMorgans = false;
    1788                 break;
    1789             }
    1790         }
    1791         if (canApplyDeMorgans) {
    1792             const unsigned operands = cast<Variadic>(negatedVar)->getNumOperands();
    1793             PabloAST * negations[operands];
    1794             block->setInsertPoint(var);
    1795             for (unsigned i = 0; i != operands; ++i) {
    1796                 negations[i] = block->createNot(cast<Variadic>(negatedVar)->getOperand(i));
    1797             }
    1798             const unsigned users = var->getNumUses();
    1799             PabloAST * user[users];
    1800             std::copy(var->user_begin(), var->user_end(), user);
    1801             for (unsigned i = 0; i != users; ++i) {
    1802                 cast<Variadic>(user[i])->deleteOperand(var);
    1803                 for (unsigned j = 0; j != operands; ++j) {
    1804                     cast<Variadic>(user[i])->addOperand(negations[j]);
    1805                 }
    1806             }
    1807             var->eraseFromParent(true);
    1808         }
    1809     }
    1810 }
    1811 
    1812 /** ------------------------------------------------------------------------------------------------------------- *
    1813  * @brief deMorgansExpansion
    1814  ** ------------------------------------------------------------------------------------------------------------- */
    1815 void FactorizeDFG::deMorgansExpansion(PabloBlock * const block) {
    1816     Statement * stmt = block->front();
    1817     while (stmt) {
    1818         if (isa<If>(stmt) || isa<While>(stmt)) {
    1819             deMorgansExpansion(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    1820         } else if (isa<Not>(stmt)) {
    1821             deMorgansExpansion(cast<Not>(stmt), block);
    1822         }
    1823         stmt = stmt->getNextNode();
    1824     }
    1825 }
    1826 
    1827 /** ------------------------------------------------------------------------------------------------------------- *
    1828  * @brief enumerateScopeDepth
    1829  ** ------------------------------------------------------------------------------------------------------------- */
    1830 void FactorizeDFG::enumerateScopeDepth(const PabloBlock * const block, const unsigned depth) {
    1831     const Statement * stmt = block->front();
    1832752    while (stmt) {
    1833753        if (isa<If>(stmt) || isa<While>(stmt)) {
    1834754            PabloBlock * body = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    1835755            mScopeDepth.emplace(body, depth);
    1836             enumerateScopeDepth(body, depth + 1);
    1837         } else if (stmt->getNumOperands() > 2 && (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt))) {
    1838             ++mNumOfVariadics;
     756            initialize(body, depth + 1);
    1839757        }
    1840758        stmt = stmt->getNextNode();
     
    1845763 * @brief enumerateScopeDepth
    1846764 ** ------------------------------------------------------------------------------------------------------------- */
    1847 inline void FactorizeDFG::enumerateScopeDepth(const PabloFunction & function) {
     765inline void FactorizeDFG::initialize(PabloFunction & function) {
    1848766    mScopeDepth.emplace(nullptr, 0);
    1849767    mScopeDepth.emplace(function.getEntryBlock(), 1);
    1850     enumerateScopeDepth(function.getEntryBlock(), 2);
     768    initialize(function.getEntryBlock(), 2);
    1851769}
    1852770
     
    1869787
    1870788/** ------------------------------------------------------------------------------------------------------------- *
    1871  * @brief ensureLegality
    1872  *
    1873  * We don't want to run the simplifier after this as it might undo some of the ordering work we've done. Instead
    1874  * just do the minimum possible to ensure that each variadic is legal prior to compilation.
    1875  ** ------------------------------------------------------------------------------------------------------------- */
    1876 void FactorizeDFG::ensureLegality(PabloBlock * const block) {
    1877     Statement * stmt = block->front();
    1878     while (stmt) {
    1879         if (isa<If>(stmt) || isa<While>(stmt)) {
    1880             ensureLegality(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    1881         } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
    1882             assert (stmt->getNumOperands() <= 2);
    1883             if (LLVM_UNLIKELY(stmt->getNumOperands() < 2)) {
    1884                 if (LLVM_UNLIKELY(stmt->getNumOperands() == 0)) {
    1885                     stmt = stmt->eraseFromParent(true);
    1886                 } else {
    1887                     stmt = stmt->replaceWith(stmt->getOperand(0), true, true);
    1888                 }
    1889                 continue;
    1890             }
    1891         }
    1892         stmt = stmt->getNextNode();
    1893     }
    1894 }
    1895 
    1896 /** ------------------------------------------------------------------------------------------------------------- *
    1897789 * @brief transform
    1898790 ** ------------------------------------------------------------------------------------------------------------- */
    1899791void FactorizeDFG::transform(PabloFunction & function) {
    1900792    FactorizeDFG ldfg;
    1901 //    ldfg.deMorgansExpansion(function.getEntryBlock());
    1902 //    #ifndef NDEBUG
    1903 //    PabloVerifier::verify(function, "post-demorgans-expansion");
    1904 //    #endif
    1905     ldfg.enumerateScopeDepth(function);
     793    ldfg.initialize(function);
     794
    1906795    ldfg.factor(function);
    1907796    #ifndef NDEBUG
    1908797    PabloVerifier::verify(function, "post-factoring");
    1909798    #endif
     799    Simplifier::optimize(function);
     800
    1910801    ldfg.lower(function);
    1911802    #ifndef NDEBUG
    1912803    PabloVerifier::verify(function, "post-lowering");
    1913804    #endif
    1914     ldfg.ensureLegality(function.getEntryBlock());
    1915 }
    1916 
    1917 }
     805    Simplifier::optimize(function);
     806}
     807
     808}
  • icGREP/icgrep-devel/icgrep/pablo/passes/factorizedfg.h

    r4919 r4922  
    22#define FACTORIZEDFG_H
    33
     4
     5#include <boost/container/flat_set.hpp>
    46#include <boost/container/flat_map.hpp>
    5 #include <boost/circular_buffer.hpp>
     7#include <pablo/pabloAST.h>
    68#include <vector>
    7 #include <set>
    89
    910namespace pablo {
     
    1213class PabloBlock;
    1314class Variadic;
    14 class Not;
    1515class Statement;
    1616class PabloAST;
    1717
    1818class FactorizeDFG {
     19
    1920    using ScopeDepth = boost::container::flat_map<const PabloBlock *, unsigned>;
    20     using ScopeSet = std::vector<PabloBlock *>;
    21     using NodeSet = std::vector<PabloAST *>;
    22     // using Variadics = std::vector<Variadic *>;
    23     using Variadics = boost::circular_buffer<Variadic *>;
    24 
    25     using VertexSet = std::vector<PabloAST *>;
    26     using Biclique = std::pair<VertexSet, VertexSet>; // [{Operands}, {Users}]
    27     // using BicliqueSet = boost::container::flat_set<Biclique>;
     21    using ObjectSet = std::vector<PabloAST *>;
     22    using ScopeUsers = std::pair<PabloBlock *, ObjectSet>;
     23    using Biclique = std::pair<ObjectSet, ObjectSet>; // [{Operands}, {Users}]
    2824    using BicliqueSet = std::vector<Biclique>;
    2925    using CheckSet = boost::container::flat_set<PabloAST *>;
     26    using TypeId = PabloAST::ClassTypeId;
    3027public:
    3128    static void transform(PabloFunction & function);
    3229protected:   
    33     void enumerateScopeDepth(const PabloFunction & function);
    34     void enumerateScopeDepth(const PabloBlock * const block, const unsigned depth);
    35     static void deMorgansExpansion(Not * const var, PabloBlock * const block);
    36     static void deMorgansExpansion(PabloBlock * const block);
    37     void factor(PabloFunction & function) const;
    38     // static void factor(PabloBlock * const block, BicliqueSet & bicliques);
    39     // static void enumerateBicliques(Variadic * const var, BicliqueSet & bicliques);
    40     static BicliqueSet findAllFactoringsOf(Variadic * const var);
    41     static void independentCliqueSets(BicliqueSet & bicliques);
    42     void processBicliques(BicliqueSet & bicliques) const;
    43     // void factor(PabloBlock * const block, BicliqueSet & vars) const;
    44     void factor(PabloBlock * const block, Variadics & vars) const;
    45     void factor(Variadic * const var, Variadics & Q) const;
    46     PabloBlock * findInsertionScope(const NodeSet & users) const;
    47     CheckSet makeCheckSet(PabloBlock * const scope, const NodeSet & values) const;
    48     Statement * firstIn(PabloBlock * const scope, Statement * stmt, const NodeSet & operands) const;
    49     Statement * lastIn(PabloBlock * const scope, Statement * stmt, const NodeSet & users) const;
    50     PabloBlock * findInsertionPoint(const NodeSet & operands, const NodeSet & users) const;
     30    void initialize(PabloFunction &function);
     31    void initialize(PabloBlock * const block, const unsigned depth);
     32
     33    unsigned scopeDepthOf(const PabloBlock * const block) const;
     34    unsigned scopeDepthOf(const PabloAST * const expr) const;
     35
     36    CheckSet makeCheckSet(PabloBlock * const scope, const ObjectSet & values) const;
     37    Statement * firstIn(PabloBlock * const scope, Statement * const initial, const ObjectSet & operands) const;
     38    Statement * lastIn(PabloBlock * const scope, Statement * const initial, const ObjectSet & users) const;
     39    Variadic * factorize(const TypeId typeId, PabloBlock * const scope, ObjectSet & operands, ObjectSet & users) const;
     40    static BicliqueSet independentFactoringSets(BicliqueSet && factoringSets, const unsigned side);
     41    static BicliqueSet enumerateFactoringSets(Variadic * const var);
     42    static BicliqueSet enumerateFactoringSets(ObjectSet params, PabloBlock * const entryScope, const TypeId typeId);
     43    bool processFactoringSets(const TypeId typeId, PabloBlock * const scope, BicliqueSet && factoringSets) const;
     44    PabloBlock * findInsertionScope(const ObjectSet & users) const;
     45    bool processFactoringSets(const TypeId typeId, BicliqueSet && factoringSets, ObjectSet & factorings) const;
     46    bool factor(PabloBlock * const block);
     47    void factor(PabloFunction & function, const TypeId typeId);
     48    void factor(PabloFunction & function);
     49
    5150    void lower(PabloFunction & function) const;
    5251    void lower(PabloBlock * const block) const;
    5352    Statement * lower(Variadic * const var, PabloBlock * block) const;
    54     unsigned scopeDepthOf(const PabloBlock * const block) const;
    55     unsigned scopeDepthOf(const PabloAST * const expr) const;
    56     static void ensureLegality(PabloBlock * const block);
    57     FactorizeDFG() : mNumOfVariadics(0) {}
     53
     54    FactorizeDFG() = default;
     55
    5856private:
    59     unsigned        mNumOfVariadics;
    60     ScopeDepth      mScopeDepth;
     57    ScopeDepth              mScopeDepth;
    6158};
    6259
  • icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.cpp

    r4919 r4922  
    88#include <queue>
    99
     10#include <pablo/optimizers/distributivepass.h>
     11
    1012using namespace boost;
    1113using namespace boost::container;
     
    1618
    1719/** ------------------------------------------------------------------------------------------------------------- *
     20 * @brief canonicalize
     21 ** ------------------------------------------------------------------------------------------------------------- */
     22Variadic * CanonicalizeDFG::canonicalize(Variadic * var) {
     23    assert (isa<And>(var) || isa<Or>(var) || isa<Xor>(var));
     24    for (unsigned i = 0; i < var->getNumOperands(); ) {
     25        if (var->getOperand(i)->getClassTypeId() == var->getClassTypeId()) {
     26            Variadic * const removedVar = cast<Variadic>(var->removeOperand(i));
     27            for (unsigned j = 0; j != removedVar->getNumOperands(); ++j) {
     28                var->addOperand(removedVar->getOperand(j));
     29            }
     30            if (removedVar->getNumUses() == 0) {
     31                removedVar->eraseFromParent(true);
     32            }
     33            continue;
     34        }
     35        ++i;
     36    }
     37    return var;
     38}
     39
     40/** ------------------------------------------------------------------------------------------------------------- *
    1841 * @brief coalesce
    1942 ** ------------------------------------------------------------------------------------------------------------- */
    20 inline Variadic * CoalesceDFG::coalesce(Variadic * const var) {
    21     const TypeId typeId = var->getClassTypeId();
    22     for (unsigned i = 0; i < var->getNumOperands(); ) {
    23         PabloAST * const op = var->getOperand(i);
    24         if (op->getClassTypeId() == typeId) {
    25             Variadic * removedVar = cast<Variadic>(var->removeOperand(i));
    26             for (unsigned j = 0; j != cast<Variadic>(op)->getNumOperands(); ++j) {
    27                 var->addOperand(cast<Variadic>(op)->getOperand(j));
    28             }
    29             if (removedVar->getNumOperands() == 1) {
    30                 removedVar->replaceWith(removedVar->getOperand(0));
    31             } else if (removedVar->getNumUses() == 0) {
    32                 removedVar->eraseFromParent(true);
    33             }
    34             continue;
    35         }
    36         ++i;
    37     }
    38     return var;
    39 }
    40 
    41 /** ------------------------------------------------------------------------------------------------------------- *
    42  * @brief coalesce
    43  ** ------------------------------------------------------------------------------------------------------------- */
    44 void CoalesceDFG::coalesce(PabloBlock * const block, const bool traverse) {
     43void CanonicalizeDFG::canonicalize(PabloBlock * const block) {
    4544    Statement * stmt = block->front();
    4645    while (stmt) {
    4746        Statement * next = stmt->getNextNode();
    48         if (LLVM_UNLIKELY((isa<If>(stmt) || isa<While>(stmt)) && traverse)) {
    49             coalesce(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), true);
    50         } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
    51             coalesce(cast<Variadic>(stmt));
    52         }/* else if (isa<Not>(stmt)) {
    53             deMorgansExpansion(cast<Not>(stmt), block);
    54         }*/
     47        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     48            canonicalize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     49        } else if (isa<Variadic>(stmt)) {
     50            canonicalize(cast<Variadic>(stmt));
     51        }
    5552        stmt = next;
    5653    }
     
    6360 * thereby allowing the Simplifier to check for tautologies and contradictions.
    6461 ** ------------------------------------------------------------------------------------------------------------- */
    65 inline void CoalesceDFG::deMorgansExpansion(Not * const var, PabloBlock * const block) {
    66     PabloAST * const negatedVar = var->getOperand(0);
     62inline void CanonicalizeDFG::deMorgansExpansion(Not * const negation, PabloBlock * const block) {
     63    PabloAST * const negatedVar = negation->getOperand(0);
    6764    if (isa<And>(negatedVar) || isa<Or>(negatedVar)) {
    68         const TypeId desiredTypeId = isa<And>(negatedVar) ? TypeId::Or : TypeId::And;
    69         bool canApplyDeMorgans = true;
    70         for (PabloAST * user : var->users()) {
    71             if (desiredTypeId != user->getClassTypeId()) {
    72                 canApplyDeMorgans = false;
     65        const TypeId typeId = isa<And>(negatedVar) ? TypeId::Or : TypeId::And;
     66        bool expandable = false;
     67        for (PabloAST * user : negation->users()) {
     68            if (user->getClassTypeId() == typeId) {
     69                expandable = true;
    7370                break;
    7471            }
    7572        }
    76         if (canApplyDeMorgans) {
     73        if (expandable) {
     74
    7775            const unsigned operands = cast<Variadic>(negatedVar)->getNumOperands();
    7876            PabloAST * negations[operands];
    79             block->setInsertPoint(var);
    8077            for (unsigned i = 0; i != operands; ++i) {
    81                 negations[i] = block->createNot(cast<Variadic>(negatedVar)->getOperand(i));
    82             }
    83             const unsigned users = var->getNumUses();
    84             PabloAST * user[users];
    85             std::copy(var->user_begin(), var->user_end(), user);
    86             for (unsigned i = 0; i != users; ++i) {
    87                 cast<Variadic>(user[i])->deleteOperand(var);
    88                 for (unsigned j = 0; j != operands; ++j) {
    89                     cast<Variadic>(user[i])->addOperand(negations[j]);
    90                 }
    91             }
    92             var->eraseFromParent(true);
     78                PabloAST * op = cast<Variadic>(negatedVar)->getOperand(i);
     79                Statement * ip = negation;
     80                if (LLVM_LIKELY(isa<Statement>(op))) {
     81                    Statement * br = cast<Statement>(op);
     82                    PabloBlock * scope = br->getParent();
     83                    for (;;) {
     84                        if (LLVM_UNLIKELY(scope == nullptr)) {
     85                            break;
     86                        } else if (LLVM_UNLIKELY(scope == negation->getParent())) {
     87                            ip = br;
     88                            break;
     89                        }
     90                        br = scope->getBranch();
     91                        scope = scope->getParent();
     92                    }
     93                }
     94                block->setInsertPoint(ip);
     95                negations[i] = block->createNot(op);
     96            }
     97
     98            for (PabloAST * user : negation->users()) {
     99                if (user->getClassTypeId() == typeId) {
     100                    cast<Variadic>(user)->deleteOperand(negation);
     101                    for (unsigned i = 0; i != operands; ++i) {
     102                        cast<Variadic>(user)->addOperand(negations[i]);
     103                    }
     104                }
     105            }
     106
     107        }
     108    }
     109}
     110
     111/** ------------------------------------------------------------------------------------------------------------- *
     112 * @brief deMorgansExpansion
     113 ** ------------------------------------------------------------------------------------------------------------- */
     114void CanonicalizeDFG::deMorgansExpansion(PabloBlock * const block) {
     115    for (Statement * stmt : *block) {
     116        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     117            deMorgansExpansion(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     118        } else if (isa<Not>(stmt)) {
     119            deMorgansExpansion(cast<Not>(stmt), block);
    93120        }
    94121    }
     
    98125 * @brief deMorgansReduction
    99126 ** ------------------------------------------------------------------------------------------------------------- */
    100 inline void CoalesceDFG::deMorgansReduction(Variadic * const var, PabloBlock * const block) {
     127inline void CanonicalizeDFG::deMorgansReduction(Variadic * const var, PabloBlock * const block) {
     128    assert (isa<And>(var) || isa<Or>(var));
    101129    unsigned negations = 0;
    102     for (unsigned i = 0; i < var->getNumOperands(); ++i) {
    103         if (isa<Not>(var->getOperand(i))) {
    104             ++negations;
     130    const unsigned operands = var->getNumOperands();
     131    PabloAST * negated[operands];
     132    for (unsigned i = 0; i < operands; ++i) {
     133        PabloAST * const op = var->getOperand(i);
     134        if (isa<Not>(op)) {
     135            negated[negations++] = cast<Not>(op)->getOperand(0);
    105136        }
    106137    }
    107138    if (negations > 1) {
    108         PabloAST * negated[negations];
    109         for (unsigned i = var->getNumOperands(), j = negations; i && j; ) {
    110             if (isa<Not>(var->getOperand(--i))) {
    111                 negated[--j] = cast<Not>(var->removeOperand(i))->getOperand(0);
     139        for (unsigned i = operands; i; ) {
     140            PabloAST * const op = var->getOperand(--i);
     141            if (isa<Not>(op)) {
     142                var->removeOperand(i);
    112143            }
    113144        }
     
    129160 * @brief deMorgansReduction
    130161 ** ------------------------------------------------------------------------------------------------------------- */
    131 void CoalesceDFG::deMorgansReduction(PabloBlock * const block, const bool traverse) {
     162void CanonicalizeDFG::deMorgansReduction(PabloBlock * const block) {
    132163    for (Statement * stmt : *block) {
    133         if (LLVM_UNLIKELY((isa<If>(stmt) || isa<While>(stmt)) && traverse)) {
    134             deMorgansReduction(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), true);
     164        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     165            deMorgansReduction(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    135166        } else if (isa<And>(stmt) || isa<Or>(stmt)) {
    136167            deMorgansReduction(cast<Variadic>(stmt), block);
     
    352383 * @brief tryToPartiallyExtractVariadic
    353384 ** ------------------------------------------------------------------------------------------------------------- */
    354 inline void CoalesceDFG::tryToPartiallyExtractVariadic(Variadic * const var) {
     385inline void CanonicalizeDFG::tryToPartiallyExtractVariadic(Variadic * const var) {
    355386    for (unsigned i = 0; i < var->getNumOperands(); ++i) {
    356387        PabloAST * const op = var->getOperand(i);
     
    416447                                    joiner->addOperand(def->getOperand(0));                                   
    417448                                }
    418                                 Assign * const joined = block->createAssign("m", coalesce(joiner));
     449                                Assign * const joined = block->createAssign("m", canonicalize(joiner));
    419450                                for (Assign * def : defs) {
    420451                                    def->replaceWith(joined);
     
    438469 * @brief tryToPartiallyExtractVariadic
    439470 ** ------------------------------------------------------------------------------------------------------------- */
    440 void CoalesceDFG::tryToPartiallyExtractVariadic(PabloBlock * const block) {
     471void CanonicalizeDFG::tryToPartiallyExtractVariadic(PabloBlock * const block) {
    441472    for (Statement * stmt = block->back(); stmt; stmt = stmt->getPrevNode()) {
    442473        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     
    581612 * TODO: make this only iterate over the scope blocks and test the scope branch.
    582613 ** ------------------------------------------------------------------------------------------------------------- */
    583 inline void CoalesceDFG::removeFalseScopeDependencies(PabloFunction & function) {
     614inline void CanonicalizeDFG::removeFalseScopeDependencies(PabloFunction & function) {
    584615    ScopeDependencyGraph G;
    585616    {
     
    594625 * @brief transform
    595626 ** ------------------------------------------------------------------------------------------------------------- */
    596 void CoalesceDFG::transform(PabloFunction & function) {
    597 
    598     CoalesceDFG::coalesce(function.getEntryBlock(), true);
     627void CanonicalizeDFG::transform(PabloFunction & function) {
     628
     629    CanonicalizeDFG::canonicalize(function.getEntryBlock());
    599630    #ifndef NDEBUG
    600     PabloVerifier::verify(function, "post-coalescence");
     631    PabloVerifier::verify(function, "post-canonicalize");
    601632    #endif
    602633
    603634    Simplifier::optimize(function);
    604635
    605 //    CoalesceDFG::deMorgansReduction(function.getEntryBlock(), true);
     636//    CanonicalizeDFG::deMorgansReduction(function.getEntryBlock());
    606637//    #ifndef NDEBUG
    607638//    PabloVerifier::verify(function, "post-demorgans-reduction");
     
    610641//    Simplifier::optimize(function);
    611642
    612     CoalesceDFG::removeFalseScopeDependencies(function);
     643    CanonicalizeDFG::removeFalseScopeDependencies(function);
    613644    #ifndef NDEBUG
    614645    PabloVerifier::verify(function, "post-remove-false-scope-dependencies");
     
    617648    Simplifier::optimize(function);
    618649
    619     CoalesceDFG::tryToPartiallyExtractVariadic(function.getEntryBlock());
     650    CanonicalizeDFG::tryToPartiallyExtractVariadic(function.getEntryBlock());
    620651    #ifndef NDEBUG
    621652    PabloVerifier::verify(function, "post-partial-variadic-extraction");
     
    624655    Simplifier::optimize(function);
    625656
    626 
    627 }
    628 
    629 }
     657//    CanonicalizeDFG::deMorgansExpansion(function.getEntryBlock());
     658//    #ifndef NDEBUG
     659//    PabloVerifier::verify(function, "post-demorgans-expansion");
     660//    #endif
     661
     662//    Simplifier::optimize(function);
     663
     664
     665}
     666
     667}
  • icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.h

    r4919 r4922  
    1010class Not;
    1111class Assign;
     12class PabloAST;
    1213
    13 class CoalesceDFG {
     14class CanonicalizeDFG {
    1415    friend class DistributivePass;
    1516    friend class FactorizeDFG;
     
    1718    static void transform(PabloFunction & function);
    1819protected:
    19     static void coalesce(PabloBlock * const block, const bool traverse);
    20     static Variadic *coalesce(Variadic * const var);
    21     static void deMorgansExpansion(Not * const var, PabloBlock * const block);
    22     static void deMorgansReduction(PabloBlock * const block, const bool traverse);
     20    static void canonicalize(PabloBlock * const block);
     21    static Variadic * canonicalize(Variadic * var);
     22    static void deMorgansExpansion(PabloBlock * const block);
     23    static void deMorgansExpansion(Not * const negation, PabloBlock * const block);
     24    static void deMorgansReduction(PabloBlock * const block);
    2325    static void deMorgansReduction(Variadic * const var, PabloBlock * const block);
    2426    static void tryToPartiallyExtractVariadic(PabloBlock * const block);
    2527    static void tryToPartiallyExtractVariadic(Variadic * const var);
    2628    static void removeFalseScopeDependencies(PabloFunction & function);
    27     CoalesceDFG() = default;
     29    CanonicalizeDFG() = default;
    2830};
    2931
  • icGREP/icgrep-devel/icgrep/toolchain.cpp

    r4919 r4922  
    4242#include <pablo/optimizers/pablo_simplifier.hpp>
    4343#include <pablo/optimizers/codemotionpass.h>
     44#ifdef ENABLE_MULTIPLEXING
    4445#include <pablo/passes/flattenassociativedfg.h>
    4546#include <pablo/passes/factorizedfg.h>
    46 #ifdef ENABLE_MULTIPLEXING
    4747#include <pablo/optimizers/pablo_automultiplexing.hpp>
    4848#include <pablo/optimizers/pablo_bddminimization.h>
     
    297297    if (EnableLowering || EnablePreDistribution || EnablePostDistribution) {
    298298        READ_CYCLE_COUNTER(coalescing_start);
    299         CoalesceDFG::transform(*function);
     299        CanonicalizeDFG::transform(*function);
    300300        READ_CYCLE_COUNTER(coalescing_end);
    301301    }
     
    310310        READ_CYCLE_COUNTER(multiplexing_end);
    311311        if (EnableLowering || EnablePreDistribution || EnablePostDistribution) {
    312             CoalesceDFG::transform(*function);
     312            CanonicalizeDFG::transform(*function);
    313313        }
    314314    }
Note: See TracChangeset for help on using the changeset viewer.