source: icGREP/icgrep-devel/icgrep/pablo/passes/factorizedfg.cpp @ 4919

Last change on this file since 4919 was 4919, checked in by nmedfort, 3 years ago

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

File size: 72.4 KB
Line 
1#include "factorizedfg.h"
2
3#include <pablo/codegenstate.h>
4#include <pablo/analysis/pabloverifier.hpp>
5#include <pablo/optimizers/pablo_simplifier.hpp>
6#include <pablo/passes/flattenassociativedfg.h>
7#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
15#include <set>
16#include <type_traits>
17
18#include <pablo/printer_pablos.h>
19#include <iostream>
20
21using namespace boost;
22using namespace boost::container;
23
24namespace pablo {
25
26using TypeId = PabloAST::ClassTypeId;
27
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);
51    assert (var->getNumOperands() > 2);
52
53    // Begin by computing a graph G depicting which operands are used by which statements. We know that
54    // all of them are used by the Variadic but they might be used elsewhere in the current block.
55
56
57    // If this operand was defined in this block, we want to indicate that in G as well so that we
58    // don't mistakingly pair them together.
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;
227        if (isa<And>(var)) {
228            result = block->createAnd(op1, op2);
229        } else if (isa<Or>(var)) {
230            result = block->createOr(op1, op2);
231        } else { // if (isa<Xor>(var)) {
232            result = block->createXor(op1, op2);
233        }
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
347    return var->replaceWith(result, true);
348}
349#endif
350
351/** ------------------------------------------------------------------------------------------------------------- *
352 * @brief lower
353 ** ------------------------------------------------------------------------------------------------------------- */
354void FactorizeDFG::lower(PabloBlock * const block) const {
355    Statement * stmt = block->front();
356    while (stmt) {
357        if (isa<If>(stmt) || isa<While>(stmt)) {
358            lower(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
359        } else if ((stmt->getNumOperands() > 2) && (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt))) {
360            stmt = lower(cast<Variadic>(stmt), block);
361            continue;
362        }
363        stmt = stmt->getNextNode();
364    }
365}
366
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;
384
385/** ------------------------------------------------------------------------------------------------------------- *
386 * @brief enumerateBicliques
387 *
388 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
389 * bicliques" by Alexe et. al. (2003).
390 ** ------------------------------------------------------------------------------------------------------------- */
391inline void FactorizeDFG::enumerateBicliques(Variadic * const var, BicliqueSet & bicliques) {
392    using IntersectionSets = flat_set<VertexSet>;
393
394    IntersectionSets B1;
395
396    const TypeId typeId = var->getClassTypeId();
397    for (unsigned i = 0; i != var->getNumOperands(); ++i) {
398        PabloAST * const op = var->getOperand(i);
399        VertexSet B;
400        B.reserve(op->getNumUses());
401        for (PabloAST * user : op->users()) {
402            if (user->getClassTypeId() == typeId) {
403                B.push_back(user);
404            }
405        }
406        std::sort(B.begin(), B.end());
407        B1.insert(std::move(B));
408    }
409
410    IntersectionSets B(B1);
411
412    IntersectionSets Bi;
413
414    VertexSet clique;
415    for (auto i = B1.begin(); i != B1.end(); ++i) {
416        for (auto j = i; ++j != B1.end(); ) {
417            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
418            if (clique.size() > 0) {
419                if (B.count(clique) == 0) {
420                    Bi.insert(clique);
421                }
422                clique.clear();
423            }
424        }
425    }
426
427    while (!Bi.empty()) {
428        B.insert(Bi.begin(), Bi.end());
429        IntersectionSets Bk;
430        for (auto i = B1.begin(); i != B1.end(); ++i) {
431            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
432                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
433                if (clique.size() > 0) {
434                    if (B.count(clique) == 0) {
435                        Bk.insert(clique);
436                    }
437                    clique.clear();
438                }
439            }
440        }
441        Bi.swap(Bk);
442    }
443
444    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
445        VertexSet Ai(var->begin(), var->end());
446        for (const PabloAST * user : *Bi) {
447            VertexSet Aj(cast<Variadic>(user)->begin(), cast<Variadic>(user)->end());
448            std::sort(Aj.begin(), Aj.end());
449            VertexSet Ak;
450            Ak.reserve(std::min<unsigned>(Ai.size(), Aj.size()));
451            std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
452            Ai.swap(Ak);
453        }
454        if (Ai.size() > 1 && Bi->size() > 1) {
455            bicliques.emplace(std::move(Ai), std::move(*Bi));
456        }
457    }
458}
459
460/** ------------------------------------------------------------------------------------------------------------- *
461 * @brief intersects
462 ** ------------------------------------------------------------------------------------------------------------- */
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 {
532
533    ScopeSet scopes;
534    scopes.reserve(users.size());
535
536    for (PabloAST * user : users) {
537        PabloBlock * const scope = cast<Statement>(user)->getParent(); assert (scope);
538        if (std::find(scopes.begin(), scopes.end(), scope) == scopes.end()) {
539            scopes.push_back(scope);
540        }
541    }
542
543    if (LLVM_UNLIKELY(scopes.size() == 1)) {
544        PabloBlock * const scope = scopes.front();
545        Statement * stmt = scope->front();
546        std::sort(users.begin(), users.end());
547        while (stmt) {
548            if (LLVM_UNLIKELY(std::binary_search(users.begin(), users.end(), stmt))) {
549                scope->setInsertPoint(stmt->getPrevNode());
550                return scope;
551            }
552            stmt = stmt->getNextNode();
553        }
554        llvm_unreachable("Failed to locate user in single scope block!");
555    }
556
557    while (scopes.size() > 1) {
558        // Find the LCA of both scopes then add the LCA back to the list of scopes.
559        PabloBlock * scope1 = scopes.back(); scopes.pop_back();
560        PabloBlock * scope2 = scopes.back(); scopes.pop_back();
561        if (scope1 != scope2) {
562            unsigned depth1 = mScopeDepth.find(scope1)->second;
563            unsigned depth2 = mScopeDepth.find(scope2)->second;
564            // If one of these scopes is nested deeper than the other, scan upwards through
565            // the scope tree until both scopes are at the same depth.
566            while (depth1 > depth2) {
567                scope1 = scope1->getParent();
568                --depth1;
569            }
570            while (depth1 < depth2) {
571                scope2 = scope2->getParent();
572                --depth2;
573            }
574            // Then iteratively step backwards until we find a matching set of scopes; this
575            // must be the LCA of our original scopes.
576            while (scope1 != scope2) {
577                scope1 = scope1->getParent();
578                scope2 = scope2->getParent();
579            }
580            assert (scope1 && scope2);
581        }
582        scopes.push_back(scope1);
583    }
584    assert (scopes.size() == 1);
585
586    PabloBlock * const scope = scopes.front();
587    Statement * stmt = scope->back();
588    std::sort(operands.begin(), operands.end());
589    while (stmt) {
590        if (isa<If>(stmt)) {
591            for (Assign * def : cast<If>(stmt)->getDefined()) {
592                if (LLVM_UNLIKELY(std::binary_search(operands.begin(), operands.end(), def))) {
593                    scope->setInsertPoint(stmt);
594                    return scope;
595                }
596            }
597        } else if (isa<While>(stmt)) {
598            for (Next * var : cast<While>(stmt)->getVariants()) {
599                if (LLVM_UNLIKELY(std::binary_search(operands.begin(), operands.end(), var))) {
600                    scope->setInsertPoint(stmt);
601                    return scope;
602                }
603            }
604        } else if (LLVM_UNLIKELY(std::binary_search(operands.begin(), operands.end(), stmt))) {
605            scope->setInsertPoint(stmt);
606            return scope;
607        }
608        stmt = stmt->getPrevNode();
609    }
610    scope->setInsertPoint(nullptr);
611    return scope;
612}
613
614/** ------------------------------------------------------------------------------------------------------------- *
615 * @brief processBicliques
616 ** ------------------------------------------------------------------------------------------------------------- */
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);
623        Variadic * factored = nullptr;
624        if (isa<And>(users.front())) {
625            factored = block->createAnd(operands.begin(), operands.end());
626        } else if (isa<Or>(users.front())) {
627            factored = block->createOr(operands.begin(), operands.end());
628        } else { // if (isa<Xor>(var)) {
629            factored = block->createXor(operands.begin(), operands.end());
630        }
631        for (PabloAST * user : users) {
632            for (PabloAST * op : operands) {
633                cast<Variadic>(user)->deleteOperand(op);
634            }
635            cast<Variadic>(user)->addOperand(factored);
636        }
637    }
638    bicliques.clear();
639}
640
641/** ------------------------------------------------------------------------------------------------------------- *
642 * @brief factor
643 *
644 * Perform common subexpression elimination on the Variadic statements
645 ** ------------------------------------------------------------------------------------------------------------- */
646void FactorizeDFG::factor(PabloBlock * const block, BicliqueSet & bicliques) const {
647    Statement * stmt = block->front();
648    while (stmt) {
649        if (isa<If>(stmt) || isa<While>(stmt)) {
650            processBicliques(bicliques);
651            factor(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), bicliques);
652        } else if (stmt->getNumOperands() > 2 && (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt))) {
653            enumerateBicliques(cast<Variadic>(stmt), bicliques);
654        }
655        stmt = stmt->getNextNode();
656    }
657    processBicliques(bicliques);
658}
659
660/** ------------------------------------------------------------------------------------------------------------- *
661 * @brief factor
662 ** ------------------------------------------------------------------------------------------------------------- */
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());
1287        } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
1288            // When we encounter a reassociative statement, add it and its operands to our bigraph G.
1289            const auto u = add_vertex(stmt, G);
1290            A.push_back(u);
1291            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
1292                auto f = B.find(stmt->getOperand(i));
1293                if (f == B.end()) {
1294                    f = B.emplace(stmt->getOperand(i), add_vertex(stmt->getOperand(i), G)).first;
1295                }
1296                add_edge(f->second, u, G);
1297            }
1298        }
1299        stmt = stmt->getNextNode();
1300    }
1301    eliminateCommonSubexpressions(G, A, block);
1302}
1303#endif
1304
1305#if 0
1306
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);
1822        }
1823        stmt = stmt->getNextNode();
1824    }
1825}
1826
1827/** ------------------------------------------------------------------------------------------------------------- *
1828 * @brief enumerateScopeDepth
1829 ** ------------------------------------------------------------------------------------------------------------- */
1830void FactorizeDFG::enumerateScopeDepth(const PabloBlock * const block, const unsigned depth) {
1831    const Statement * stmt = block->front();
1832    while (stmt) {
1833        if (isa<If>(stmt) || isa<While>(stmt)) {
1834            PabloBlock * body = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
1835            mScopeDepth.emplace(body, depth);
1836            enumerateScopeDepth(body, depth + 1);
1837        } else if (stmt->getNumOperands() > 2 && (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt))) {
1838            ++mNumOfVariadics;
1839        }
1840        stmt = stmt->getNextNode();
1841    }
1842}
1843
1844/** ------------------------------------------------------------------------------------------------------------- *
1845 * @brief enumerateScopeDepth
1846 ** ------------------------------------------------------------------------------------------------------------- */
1847inline void FactorizeDFG::enumerateScopeDepth(const PabloFunction & function) {
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    }
1894}
1895
1896/** ------------------------------------------------------------------------------------------------------------- *
1897 * @brief transform
1898 ** ------------------------------------------------------------------------------------------------------------- */
1899void FactorizeDFG::transform(PabloFunction & function) {
1900    FactorizeDFG ldfg;
1901//    ldfg.deMorgansExpansion(function.getEntryBlock());
1902//    #ifndef NDEBUG
1903//    PabloVerifier::verify(function, "post-demorgans-expansion");
1904//    #endif
1905    ldfg.enumerateScopeDepth(function);
1906    ldfg.factor(function);
1907    #ifndef NDEBUG
1908    PabloVerifier::verify(function, "post-factoring");
1909    #endif
1910    ldfg.lower(function);
1911    #ifndef NDEBUG
1912    PabloVerifier::verify(function, "post-lowering");
1913    #endif
1914    ldfg.ensureLegality(function.getEntryBlock());
1915}
1916
1917}
Note: See TracBrowser for help on using the repository browser.