Ignore:
Timestamp:
Jan 21, 2016, 5:15:33 PM (3 years ago)
Author:
nmedfort
Message:

Work on lowering + some timing and papi information that will be cleaned up later.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/passes/factorizedfg.cpp

    r4899 r4919  
    66#include <pablo/passes/flattenassociativedfg.h>
    77#include <boost/container/flat_set.hpp>
     8#include <boost/circular_buffer.hpp>
     9#include <boost/graph/adjacency_list.hpp>
     10#include <boost/graph/adjacency_matrix.hpp>
     11#include <boost/graph/topological_sort.hpp>
     12#include <queue>
     13#include <tuple>
     14
    815#include <set>
     16#include <type_traits>
     17
     18#include <pablo/printer_pablos.h>
     19#include <iostream>
    920
    1021using namespace boost;
    1122using namespace boost::container;
    1223
    13 
    1424namespace pablo {
    1525
    16 using VertexSet = std::vector<PabloAST *>;
    17 using Biclique = std::pair<VertexSet, VertexSet>; // [{Operands}, {Users}]
    18 using BicliqueSet = std::vector<Biclique>;
    1926using TypeId = PabloAST::ClassTypeId;
    2027
    21 ///** ------------------------------------------------------------------------------------------------------------- *
    22 // * @brief lower
    23 // ** ------------------------------------------------------------------------------------------------------------- */
    24 //inline PabloAST * FactorizeDFG::lower(Variadic * const var, PabloBlock * block, OrderingMap & order) {
    25 //    PabloAST * result = nullptr;
    26 //    assert (var->getNumOperands() > 2);
    27 ////    // Sort the operands by their order in the current AST
    28 ////    std::sort(var->begin(), var->end(),
    29 ////        [&order](const PabloAST * const a, const PabloAST * const b)
    30 ////    {
    31 ////        return order.of(a) > order.of(b);
    32 ////    });
    33 ////    unsigned operands = var->getNumOperands();
    34 ////    // Swap the final two operands so that we can just append the temporary calculations onto the end
    35 ////    // and trust that the PENULTIMATE operand is the "latest" in the AST.
    36 ////    PabloAST * const item = var->getOperand(operands - 1);
    37 ////    var->setOperand(operands - 1, var->getOperand(operands - 2));
    38 ////    var->setOperand(operands - 2, item);
    39 //    // Finally rewrite all of the variadic statements as binary operations
    40 //    block->setInsertPoint(var->getPrevNode());
    41 //    while (var->getNumOperands() > 1) {
    42 //        PabloAST * const op2 = var->removeOperand(1);
    43 //        PabloAST * const op1 = var->removeOperand(0);
    44 //        assert (op1 != op2);
    45 //        if (isa<And>(var)) {
    46 //            result = block->createAnd(op1, op2);
    47 //        } else if (isa<Or>(var)) {
    48 //            result = block->createOr(op1, op2);
    49 //        } else { // if (isa<Xor>(var)) {
    50 //            result = block->createXor(op1, op2);
    51 //        }
    52 //        var->addOperand(result);
    53 //    }
    54 //    assert (result);
    55 //    return result;
    56 //}
    57 
    58 ///** ------------------------------------------------------------------------------------------------------------- *
    59 // * @brief lower
    60 // ** ------------------------------------------------------------------------------------------------------------- */
    61 //void FactorizeDFG::lower(PabloBlock * const block, OrderingMap & parent) {
    62 //    OrderingMap order(parent);
    63 //    Statement * stmt = block->front();
    64 //    while (stmt) {
    65 //        if (isa<If>(stmt) || isa<While>(stmt)) {
    66 //            lower(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), order);
    67 //            if (isa<If>(stmt)) {
    68 //                for (Assign * def : cast<If>(stmt)->getDefined()) {
    69 //                    order.enumerate(def);
    70 //                }
    71 //            } else { // if (isa<While>(stmt)) {
    72 //                for (Next * var : cast<While>(stmt)->getVariants()) {
    73 //                    order.enumerate(var);
    74 //                }
    75 //            }
    76 //        } else {
    77 //            if ((isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) && (stmt->getNumOperands() > 2)) {
    78 //                // We should maintain an ordering list and sort each Variadic according to it prior to writing them out.
    79 //                PabloAST * result = lower(cast<Variadic>(stmt), block, order);
    80 //                order.enumerate(result);
    81 //                stmt = stmt->replaceWith(result, true);
    82 //                continue;
    83 //            }
    84 //            order.enumerate(stmt);
    85 //        }
    86 //        stmt = stmt->getNextNode();
    87 //    }
    88 //}
    89 
    90 /** ------------------------------------------------------------------------------------------------------------- *
    91  * @brief finalize
    92  ** ------------------------------------------------------------------------------------------------------------- */
    93 inline Statement * FactorizeDFG::lower(Variadic * const var, PabloBlock * block) {
    94     PabloAST * result = nullptr;
     28// TODO: move the "tryToPartiallyExtractVariadic" from the coalescedfg class into here to run prior to lowering?
     29
     30/** ------------------------------------------------------------------------------------------------------------- *
     31 * @brief lower
     32 *
     33 * The goal of this function is to try and lower a variadic operation into binary form while attempting to mitigate
     34 * register pressure under the assumption that LLVM is not going to significantly change the IR (which was observed
     35 * when assessing the ASM output of LLVM 3.6.1 using O3.)
     36 ** ------------------------------------------------------------------------------------------------------------- */
     37inline Statement * FactorizeDFG::lower(Variadic * const var, PabloBlock * block) const {
     38
     39    using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *, int>;
     40    using Vertex = Graph::vertex_descriptor;
     41    using Map = flat_map<const PabloAST *, Vertex>;
     42    using SchedulingData = std::pair<unsigned, PabloAST *>;
     43    using SchedulingQueue = std::priority_queue<SchedulingData, std::vector<SchedulingData>, std::greater<SchedulingData>>;
     44
     45    const unsigned NOT_STEP = 1;
     46    const unsigned BOOLEAN_STEP = 10;
     47    const unsigned OTHER_STEP = 30;
     48    const unsigned DESIRED_GAP = 30;
     49
     50    assert (var->getParent() == block);
    9551    assert (var->getNumOperands() > 2);
    96     block->setInsertPoint(var->getPrevNode());
    97     while (var->getNumOperands() > 1) {
    98         PabloAST * const op2 = var->removeOperand(1);
    99         PabloAST * const op1 = var->removeOperand(0);
    100         assert (op1 != op2);
     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.
     59
     60    const unsigned operands = var->getNumOperands();
     61
     62    Graph G(operands + 1);
     63    Map M;
     64
     65    G[operands] = var;
     66    M.emplace(var, operands);
     67
     68    for (Vertex u = 0; u != operands; ++u) {
     69        PabloAST * const op = var->getOperand(u);
     70        G[u] = op;
     71        M.emplace(op, u);
     72        assert ("AST structural error!" && (op->getNumUses() > 0));
     73        for (PabloAST * user : op->users()) {
     74            if (LLVM_LIKELY(isa<Statement>(user))) {
     75                Statement * usage = cast<Statement>(user);
     76                PabloBlock * scope = usage->getParent();
     77                while (scope) {
     78                    if (scope == block) {
     79                        auto f = M.find(usage);
     80                        Vertex v = 0;
     81                        if (f == M.end()) {
     82                            v = add_vertex(usage, G);
     83                            M.emplace(usage, v);
     84                        } else {
     85                            v = f->second;
     86                        }
     87                        G[add_edge(u, v, G).first] = 0;
     88                        break;
     89                    }
     90                    usage = scope->getBranch();
     91                    scope = scope->getParent();
     92                }
     93            }
     94        }
     95    }
     96
     97    assert (M.count(var) == 1);
     98
     99    unsigned estQuantum = 0;
     100    circular_buffer<std::pair<unsigned, Vertex>> defs(operands);
     101    for (Statement * stmt : *block) {
     102        switch (stmt->getClassTypeId()) {
     103            case TypeId::And:
     104            case TypeId::Or:
     105            case TypeId::Xor:
     106                estQuantum += BOOLEAN_STEP;
     107                break;
     108            case TypeId::Not:
     109                estQuantum += NOT_STEP;
     110                break;
     111            default:
     112                estQuantum += OTHER_STEP;
     113        }
     114        auto f = M.find(stmt);
     115        if (LLVM_UNLIKELY(f != M.end())) {
     116            const auto u = f->second;
     117            if (LLVM_UNLIKELY(u == operands)) {
     118                assert (stmt == var);
     119                break;
     120            }
     121            for (auto e : make_iterator_range(in_edges(u, G)))   {
     122                G[e] = estQuantum;
     123            }
     124            if (u < operands) {
     125                defs.push_back(std::make_pair(estQuantum + DESIRED_GAP, u));
     126            }
     127        }
     128        // Annotate G to indicate when we expect a statement will be available
     129        while (defs.size() > 0) {
     130            unsigned availQuantum = 0;
     131            Vertex u = 0;
     132            std::tie(availQuantum, u) = defs.front();
     133            if (availQuantum > estQuantum) {
     134                break;
     135            }
     136            defs.pop_front();
     137            auto f = M.find(stmt);
     138            Vertex v = 0;
     139            if (f == M.end()) {
     140                v = add_vertex(stmt, G);
     141                M.emplace(stmt, v);
     142            } else {
     143                v = f->second;
     144            }
     145            G[add_edge(u, v, G).first] = estQuantum;
     146        }
     147    }
     148
     149    for (Vertex u = 0; u < operands; ++u) {
     150        unsigned quantum = 0;
     151        Vertex v = operands;
     152        for (auto e : make_iterator_range(out_edges(u, G))) {
     153            if (quantum < G[e]) {
     154                quantum = G[e];
     155                v = target(e, G);
     156            }
     157        }
     158        clear_out_edges(u, G);
     159        G[add_edge(u, v, G).first] = quantum;
     160    }
     161
     162    for (auto e : make_iterator_range(in_edges(operands, G)))   {
     163        G[e] = estQuantum;
     164    }
     165
     166    assert (num_edges(G) == var->getNumOperands());
     167
     168    SchedulingQueue Q;
     169    while (num_edges(G) > 0) {
     170
     171        Graph::edge_descriptor f;
     172        unsigned quantum = std::numeric_limits<unsigned>::max();
     173        for (auto e : make_iterator_range(edges(G))) {
     174            if (in_degree(source(e, G), G) == 0) {
     175                if (quantum > G[e]) {
     176                    quantum = G[e];
     177                    f = e;
     178                }
     179            }
     180        }
     181
     182        assert ("No edge selected!" && (quantum < std::numeric_limits<unsigned>::max()));
     183
     184        const auto u = source(f, G);
     185        assert (u < operands);
     186        const auto v = target(f, G);
     187        assert (isa<Statement>(G[v]));
     188        // Since this might have been a target of a prior pairing, read the original operand value instead of
     189        // G when checking which value is indicated by u.
     190        PabloAST * const op1 = var->getOperand(u);
     191        block->setInsertPoint(cast<Statement>(G[v]));
     192        remove_edge(f, G);
     193
     194        if (LLVM_LIKELY(Q.size() > 0)) {
     195            unsigned minQuantum = 0; PabloAST * op2 = nullptr;
     196            std::tie(minQuantum, op2) = Q.top();
     197            if (minQuantum < quantum) {
     198                Q.pop();
     199                PabloAST * result = nullptr;
     200                if (isa<And>(var)) {
     201                    result = block->createAnd(op1, op2);
     202                } else if (isa<Or>(var)) {
     203                    result = block->createOr(op1, op2);
     204                } else { // if (isa<Xor>(var)) {
     205                    result = block->createXor(op1, op2);
     206                }
     207                Q.emplace(quantum + DESIRED_GAP, result);
     208                G[v] = result; // update the insertion point node value
     209                continue;
     210            }
     211        }
     212        Q.emplace(quantum, op1);
     213    }
     214
     215    // If we've done our best to schedule the statements and have operands remaining in our queue, generate a
     216    // tree of the remaining operands.
     217    while (Q.size() > 1) {
     218        unsigned q1 = 0; PabloAST * op1 = nullptr;
     219        std::tie(q1, op1) = Q.top();
     220        Q.pop();
     221
     222        unsigned q2 = 0; PabloAST * op2 = nullptr;
     223        std::tie(q2, op2) = Q.top();
     224        Q.pop();
     225
     226        PabloAST * result = nullptr;
    101227        if (isa<And>(var)) {
    102228            result = block->createAnd(op1, op2);
     
    106232            result = block->createXor(op1, op2);
    107233        }
    108         var->addOperand(result);
    109     }
     234        Q.emplace(std::max(q1, q2) + DESIRED_GAP, result);
     235    }
     236
     237    assert (Q.size() == 1);
     238    return var->replaceWith(std::get<1>(Q.top()));
     239}
     240
     241#if 0
     242using EnumerationMap = flat_map<const PabloAST *, unsigned>;
     243
     244inline 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
     251inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     265inline 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
    110347    return var->replaceWith(result, true);
    111348}
    112 
    113 /** ------------------------------------------------------------------------------------------------------------- *
    114  * @brief finalize
    115  ** ------------------------------------------------------------------------------------------------------------- */
    116 void FactorizeDFG::lower(PabloBlock * const block) {
     349#endif
     350
     351/** ------------------------------------------------------------------------------------------------------------- *
     352 * @brief lower
     353 ** ------------------------------------------------------------------------------------------------------------- */
     354void FactorizeDFG::lower(PabloBlock * const block) const {
    117355    Statement * stmt = block->front();
    118356    while (stmt) {
    119357        if (isa<If>(stmt) || isa<While>(stmt)) {
    120358            lower(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    121         } else if ((isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) && (stmt->getNumOperands() > 2)) {
    122             // We should maintain an ordering list and sort each Variadic according to it prior to writing them out.
     359        } else if ((stmt->getNumOperands() > 2) && (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt))) {
    123360            stmt = lower(cast<Variadic>(stmt), block);
    124361            continue;
     
    128365}
    129366
    130 ///** ------------------------------------------------------------------------------------------------------------- *
    131 // * @brief lower
    132 // ** ------------------------------------------------------------------------------------------------------------- */
    133 //inline void FactorizeDFG::lower(PabloFunction & function) {
    134 //    OrderingMap ordering;
    135 //    for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
    136 //        ordering.enumerate(function.getParameter(i));
    137 //    }
    138 //    lower(function.getEntryBlock(), ordering);
    139 //}
     367/** ------------------------------------------------------------------------------------------------------------- *
     368 * @brief lower
     369 ** ------------------------------------------------------------------------------------------------------------- */
     370inline void FactorizeDFG::lower(PabloFunction & function) const {
     371    lower(function.getEntryBlock());
     372}
     373
     374#if 0
     375
     376using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, PabloAST *>;
     377using Vertex = Graph::vertex_descriptor;
     378using Map = flat_map<const PabloAST *, Vertex>;
     379
     380using VertexSet = std::vector<PabloAST *>;
     381using Biclique = std::pair<VertexSet, VertexSet>; // [{Operands}, {Users}]
     382using BicliqueSet = std::set<Biclique>;
     383using TypeId = PabloAST::ClassTypeId;
    140384
    141385/** ------------------------------------------------------------------------------------------------------------- *
     
    145389 * bicliques" by Alexe et. al. (2003).
    146390 ** ------------------------------------------------------------------------------------------------------------- */
    147 static BicliqueSet enumerateBicliques(Variadic * const var) {
    148     using IntersectionSets = std::set<VertexSet>;
     391inline void FactorizeDFG::enumerateBicliques(Variadic * const var, BicliqueSet & bicliques) {
     392    using IntersectionSets = flat_set<VertexSet>;
    149393
    150394    IntersectionSets B1;
     
    198442    }
    199443
    200     BicliqueSet bicliques;
    201     unsigned userSize = 2;
    202444    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
    203         if (userSize <= Bi->size()) {
    204             VertexSet Ai(var->begin(), var->end());
    205             for (const PabloAST * user : *Bi) {
    206                 VertexSet Aj(cast<Variadic>(user)->begin(), cast<Variadic>(user)->end());
    207                 std::sort(Aj.begin(), Aj.end());
    208                 VertexSet Ak;
    209                 Ak.reserve(std::min<unsigned>(Ai.size(), Aj.size()));
    210                 std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
    211                 Ai.swap(Ak);
    212             }
    213             if (Ai.size() > 1) {
    214                 if (userSize < Bi->size()) {
    215                     bicliques.clear();
    216                     userSize = Bi->size();
    217                 }
    218                 bicliques.emplace_back(std::move(Ai), std::move(*Bi));
    219             }
    220         }
    221     }
    222     return bicliques;
    223 }
    224 
    225 /** ------------------------------------------------------------------------------------------------------------- *
    226  * @brief pick
    227  ** ------------------------------------------------------------------------------------------------------------- */
    228 inline static Biclique pick(BicliqueSet && bicliques) {
    229     unsigned best_w = 0;
    230     auto best_c = bicliques.begin();
    231     for (auto c = bicliques.begin(); c != bicliques.end(); ++c) {
    232         const unsigned w = std::get<0>(*c).size();
    233         if (best_w < w) {
    234             best_c = c;
    235             best_w = w;
    236         }
    237     }
    238     return std::move(*best_c);
    239 }
    240 
    241 /** ------------------------------------------------------------------------------------------------------------- *
    242  * @brief chooseInsertionPoint
    243  ** ------------------------------------------------------------------------------------------------------------- */
    244 inline PabloBlock * FactorizeDFG::chooseInsertionScope(const ASTVector & users) {
     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 ** ------------------------------------------------------------------------------------------------------------- */
     463template <class Type>
     464inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     482inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     531inline PabloBlock * FactorizeDFG::findInsertionPoint(NodeSet & operands, NodeSet & users) const {
    245532
    246533    ScopeSet scopes;
    247534    scopes.reserve(users.size());
    248535
    249     flat_set<PabloBlock *> visited;
    250     visited.reserve(users.size());
    251 
    252536    for (PabloAST * user : users) {
    253         PabloBlock * const scope = cast<Statement>(user)->getParent();
    254         assert (scope);
    255         if (visited.insert(scope).second) {
     537        PabloBlock * const scope = cast<Statement>(user)->getParent(); assert (scope);
     538        if (std::find(scopes.begin(), scopes.end(), scope) == scopes.end()) {
    256539            scopes.push_back(scope);
    257540        }
     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!");
    258555    }
    259556
     
    286583    }
    287584    assert (scopes.size() == 1);
    288     return scopes[0];
    289 }
    290 
    291 /** ------------------------------------------------------------------------------------------------------------- *
    292  * @brief findInsertionPoint
    293  ** ------------------------------------------------------------------------------------------------------------- */
    294 void FactorizeDFG::findInsertionPoint(const ASTVector & operands, PabloBlock * const scope) {
    295     const flat_set<const PabloAST *> ops(operands.begin(), operands.end());
     585
     586    PabloBlock * const scope = scopes.front();
    296587    Statement * stmt = scope->back();
    297     scope->setInsertPoint(nullptr);
     588    std::sort(operands.begin(), operands.end());
    298589    while (stmt) {
    299590        if (isa<If>(stmt)) {
    300591            for (Assign * def : cast<If>(stmt)->getDefined()) {
    301                 if (ops.count(def)) {
     592                if (LLVM_UNLIKELY(std::binary_search(operands.begin(), operands.end(), def))) {
    302593                    scope->setInsertPoint(stmt);
    303                     return;
     594                    return scope;
    304595                }
    305596            }
    306597        } else if (isa<While>(stmt)) {
    307598            for (Next * var : cast<While>(stmt)->getVariants()) {
    308                 if (ops.count(var)) {
     599                if (LLVM_UNLIKELY(std::binary_search(operands.begin(), operands.end(), var))) {
    309600                    scope->setInsertPoint(stmt);
    310                     return;
    311                 }
    312             }
    313         } else if (ops.count(stmt)) {
     601                    return scope;
     602                }
     603            }
     604        } else if (LLVM_UNLIKELY(std::binary_search(operands.begin(), operands.end(), stmt))) {
    314605            scope->setInsertPoint(stmt);
    315             break;
     606            return scope;
    316607        }
    317608        stmt = stmt->getPrevNode();
    318609    }
    319 }
    320 
    321 /** ------------------------------------------------------------------------------------------------------------- *
    322  * @brief cse
    323  ** ------------------------------------------------------------------------------------------------------------- */
    324 inline void FactorizeDFG::cse(Variadic * var) {
    325     while (var->getNumOperands() > 2) {
    326         BicliqueSet bicliques = enumerateBicliques(var);
    327         if (bicliques.empty()) {
    328             break;
    329         }
    330         ASTVector operands;
    331         ASTVector users;
    332         std::tie(operands, users) = pick(std::move(bicliques));
    333         PabloBlock * const block = chooseInsertionScope(users);
    334         findInsertionPoint(operands, block);
     610    scope->setInsertPoint(nullptr);
     611    return scope;
     612}
     613
     614/** ------------------------------------------------------------------------------------------------------------- *
     615 * @brief processBicliques
     616 ** ------------------------------------------------------------------------------------------------------------- */
     617void 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);
    335623        Variadic * factored = nullptr;
    336         if (isa<And>(var)) {
     624        if (isa<And>(users.front())) {
    337625            factored = block->createAnd(operands.begin(), operands.end());
    338         } else if (isa<Or>(var)) {
     626        } else if (isa<Or>(users.front())) {
    339627            factored = block->createOr(operands.begin(), operands.end());
    340628        } else { // if (isa<Xor>(var)) {
     
    348636        }
    349637    }
    350 }
    351 
    352 /** ------------------------------------------------------------------------------------------------------------- *
    353  * @brief cse
     638    bicliques.clear();
     639}
     640
     641/** ------------------------------------------------------------------------------------------------------------- *
     642 * @brief factor
    354643 *
    355644 * Perform common subexpression elimination on the Variadic statements
    356645 ** ------------------------------------------------------------------------------------------------------------- */
    357 void FactorizeDFG::cse(PabloBlock * const block) {
     646void FactorizeDFG::factor(PabloBlock * const block, BicliqueSet & bicliques) const {
    358647    Statement * stmt = block->front();
    359648    while (stmt) {
    360         if (isa<If>(stmt) || isa<While>(stmt)) {           
    361             cse(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     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 ** ------------------------------------------------------------------------------------------------------------- */
     663inline void FactorizeDFG::factor(PabloFunction & function) const {
     664    BicliqueSet bicliques;
     665    factor(function.getEntryBlock(), bicliques);
     666}
     667
     668#endif
     669
     670#if 1
     671
     672using VertexSet = std::vector<PabloAST *>;
     673using Biclique = std::pair<VertexSet, VertexSet>; // [{Operands}, {Users}]
     674using BicliqueSet = std::vector<Biclique>;
     675using 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 ** ------------------------------------------------------------------------------------------------------------- */
     683inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     766template <class Type>
     767inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     787inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     835inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     883FactorizeDFG::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 ** ------------------------------------------------------------------------------------------------------------- */
     915inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     929inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     945inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     956inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     1003void 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 ** ------------------------------------------------------------------------------------------------------------- */
     1019inline 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
     1033using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, PabloAST *>;
     1034using Vertex = Graph::vertex_descriptor;
     1035using Map = flat_map<const PabloAST *, Vertex>;
     1036
     1037using VertexSet = std::vector<Vertex>;
     1038using Biclique = std::pair<VertexSet, VertexSet>; // [{Operands}, {Users}]
     1039using BicliqueSet = std::vector<Biclique>;
     1040using 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  ** ------------------------------------------------------------------------------------------------------------- */
     1049template <class Graph>
     1050static 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 ** ------------------------------------------------------------------------------------------------------------- */
     1128template <class Type>
     1129inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     1147template <unsigned side = 1>
     1148inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     1204template<class Type>
     1205inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     1256void 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 ** ------------------------------------------------------------------------------------------------------------- */
     1275void 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());
    3621287        } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
    363             cse(cast<Variadic>(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
     1307using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, PabloAST *>;
     1308using Matrix = adjacency_matrix<directedS>;
     1309using Vertex = Graph::vertex_descriptor;
     1310using Map = flat_map<const PabloAST *, Vertex>;
     1311using TypeId = PabloAST::ClassTypeId;
     1312
     1313/** ------------------------------------------------------------------------------------------------------------- *
     1314 * @brief getVertex
     1315 ** ------------------------------------------------------------------------------------------------------------- */
     1316static 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 ** ------------------------------------------------------------------------------------------------------------- */
     1330static 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 ** ------------------------------------------------------------------------------------------------------------- */
     1348static 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
     1367using VertexSet = std::vector<Vertex>;
     1368using Biclique = std::pair<VertexSet, VertexSet>; // [{Operands}, {Users}]
     1369using BicliqueSet = flat_set<Biclique>;
     1370using 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  ** ------------------------------------------------------------------------------------------------------------- */
     1379inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     1458inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     1525template <class Type>
     1526inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     1544inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     1591inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     1641void 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 ** ------------------------------------------------------------------------------------------------------------- */
     1671inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     1780inline 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 ** ------------------------------------------------------------------------------------------------------------- */
     1815void 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);
    3641822        }
    3651823        stmt = stmt->getNextNode();
     
    3771835            mScopeDepth.emplace(body, depth);
    3781836            enumerateScopeDepth(body, depth + 1);
     1837        } else if (stmt->getNumOperands() > 2 && (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt))) {
     1838            ++mNumOfVariadics;
    3791839        }
    3801840        stmt = stmt->getNextNode();
     
    3861846 ** ------------------------------------------------------------------------------------------------------------- */
    3871847inline void FactorizeDFG::enumerateScopeDepth(const PabloFunction & function) {
    388     mScopeDepth.emplace(function.getEntryBlock(), 0);
    389     enumerateScopeDepth(function.getEntryBlock(), 1);
     1848    mScopeDepth.emplace(nullptr, 0);
     1849    mScopeDepth.emplace(function.getEntryBlock(), 1);
     1850    enumerateScopeDepth(function.getEntryBlock(), 2);
     1851}
     1852
     1853/** ------------------------------------------------------------------------------------------------------------- *
     1854 * @brief scopeDepthOf
     1855 ** ------------------------------------------------------------------------------------------------------------- */
     1856inline unsigned FactorizeDFG::scopeDepthOf(const PabloAST * const expr) const {
     1857    return LLVM_LIKELY(isa<Statement>(expr)) ? scopeDepthOf(cast<Statement>(expr)->getParent()) : 0;
     1858}
     1859
     1860/** ------------------------------------------------------------------------------------------------------------- *
     1861 * @brief scopeDepthOf
     1862 ** ------------------------------------------------------------------------------------------------------------- */
     1863inline unsigned FactorizeDFG::scopeDepthOf(const PabloBlock * const block) const {
     1864    assert (block);
     1865    const auto f = mScopeDepth.find(block);
     1866    assert (f != mScopeDepth.end());
     1867    return f->second;
     1868}
     1869
     1870/** ------------------------------------------------------------------------------------------------------------- *
     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 ** ------------------------------------------------------------------------------------------------------------- */
     1876void 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    }
    3901894}
    3911895
     
    3951899void FactorizeDFG::transform(PabloFunction & function) {
    3961900    FactorizeDFG ldfg;
     1901//    ldfg.deMorgansExpansion(function.getEntryBlock());
     1902//    #ifndef NDEBUG
     1903//    PabloVerifier::verify(function, "post-demorgans-expansion");
     1904//    #endif
    3971905    ldfg.enumerateScopeDepth(function);
    398     ldfg.cse(function.getEntryBlock());
     1906    ldfg.factor(function);
    3991907    #ifndef NDEBUG
    400     PabloVerifier::verify(function, "post-cse");
     1908    PabloVerifier::verify(function, "post-factoring");
    4011909    #endif
    402     Simplifier::optimize(function);
    403     ldfg.lower(function.getEntryBlock());
     1910    ldfg.lower(function);
    4041911    #ifndef NDEBUG
    4051912    PabloVerifier::verify(function, "post-lowering");
    406     #endif   
    407 }
    408 
    409 }
     1913    #endif
     1914    ldfg.ensureLegality(function.getEntryBlock());
     1915}
     1916
     1917}
Note: See TracChangeset for help on using the changeset viewer.