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

Last change on this file since 4922 was 4922, checked in by nmedfort, 4 years ago

Incorporated a few common case boolean optimizations in the Simplifier.

File size: 31.0 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 <queue>
12
13#include <pablo/printer_pablos.h>
14#include <iostream>
15
16using namespace boost;
17using namespace boost::container;
18
19namespace pablo {
20
21/** ------------------------------------------------------------------------------------------------------------- *
22 * @brief enumerateFactoringsOf
23 *
24 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
25 * bicliques" by Alexe et. al. (2003).
26 ** ------------------------------------------------------------------------------------------------------------- */
27FactorizeDFG::BicliqueSet FactorizeDFG::enumerateFactoringSets(ObjectSet params, PabloBlock * const entryScope, const TypeId typeId) {
28    using IntersectionSets = flat_set<ObjectSet>;
29
30    ObjectSet tmp;
31    tmp.reserve(params.size());
32
33    std::sort(params.begin(), params.end());
34
35
36    IntersectionSets B1;
37    for (PabloAST * op : params) {
38        tmp.reserve(op->getNumUses());
39        for (PabloAST * user : op->users()) {
40            if (user->getClassTypeId() == typeId) {
41                if (isa<Var>(op) || cast<Statement>(user)->getParent() == entryScope) {
42                    tmp.push_back(user);
43                }
44            }
45        }
46        if (LLVM_LIKELY(tmp.size() > 1)) {
47            std::sort(tmp.begin(), tmp.end());
48            B1.emplace(tmp.begin(), tmp.end());
49        }
50        tmp.clear();
51    }
52
53    IntersectionSets B(B1);
54
55    IntersectionSets Bi;
56
57    for (auto i = B1.begin(); i != B1.end(); ++i) {
58        for (auto j = i; ++j != B1.end(); ) {
59            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(tmp));
60            assert (std::is_sorted(tmp.begin(), tmp.end()));
61            if (tmp.size() > 1 && B.count(tmp) == 0) {
62                Bi.emplace(tmp.begin(), tmp.end());
63            }
64            tmp.clear();
65        }
66    }
67
68    while (!Bi.empty()) {
69        B.insert(Bi.begin(), Bi.end());
70        IntersectionSets Bk;
71        for (auto i = B1.begin(); i != B1.end(); ++i) {
72            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
73                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(tmp));
74                assert (std::is_sorted(tmp.begin(), tmp.end()));
75                if (tmp.size() > 1 && B.count(tmp) == 0) {
76                    Bk.emplace(tmp.begin(), tmp.end());
77                }
78                tmp.clear();
79            }
80        }
81        Bi.swap(Bk);
82    }
83
84    BicliqueSet factoringSets(0);
85    factoringSets.reserve(B.size());
86    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
87        ObjectSet Ai(params);
88        assert (Bi->size() > 1);
89        for (const PabloAST * user : *Bi) {
90            ObjectSet Aj(cast<Variadic>(user)->begin(), cast<Variadic>(user)->end());
91            std::sort(Aj.begin(), Aj.end());
92            ObjectSet Ak;
93            Ak.reserve(std::min<unsigned>(Ai.size(), Aj.size()));
94            std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
95            Ai.swap(Ak);
96        }
97        if (Ai.size() > 1) {
98            factoringSets.emplace_back(std::move(Ai), std::move(*Bi));
99        }
100    }
101
102    return factoringSets;
103}
104
105/** ------------------------------------------------------------------------------------------------------------- *
106 * @brief enumerateFactoringsOf
107 *
108 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
109 * bicliques" by Alexe et. al. (2003).
110 ** ------------------------------------------------------------------------------------------------------------- */
111inline FactorizeDFG::BicliqueSet FactorizeDFG::enumerateFactoringSets(Variadic * const var) {
112    using IntersectionSets = flat_set<ObjectSet>;
113
114    ObjectSet tmp;
115    tmp.reserve(var->getNumOperands());
116
117    IntersectionSets B1;
118    for (unsigned i = 0; i != var->getNumOperands(); ++i) {
119        PabloAST * const op = var->getOperand(i);       
120        tmp.reserve(op->getNumUses());
121        for (PabloAST * user : op->users()) {
122            if (user->getClassTypeId() == var->getClassTypeId()) {               
123                for (PabloBlock * scope = cast<Variadic>(user)->getParent(); scope; scope = scope->getParent()) {
124                    if (LLVM_UNLIKELY(scope == var->getParent())) {
125                        tmp.push_back(user);
126                        break;
127                    }
128                }
129            }
130        }
131        if (LLVM_LIKELY(tmp.size() > 1)) {
132            std::sort(tmp.begin(), tmp.end());
133            B1.emplace(tmp.begin(), tmp.end());
134        }
135        tmp.clear();
136    }
137
138    IntersectionSets B(B1);
139
140    IntersectionSets Bi;
141
142    for (auto i = B1.begin(); i != B1.end(); ++i) {
143        for (auto j = i; ++j != B1.end(); ) {
144            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(tmp));
145            assert (std::is_sorted(tmp.begin(), tmp.end()));
146            if (tmp.size() > 1 && B.count(tmp) == 0) {
147                Bi.emplace(tmp.begin(), tmp.end());
148            }
149            tmp.clear();
150        }
151    }
152
153    while (!Bi.empty()) {
154        B.insert(Bi.begin(), Bi.end());
155        IntersectionSets Bk;
156        for (auto i = B1.begin(); i != B1.end(); ++i) {
157            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
158                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(tmp));
159                assert (std::is_sorted(tmp.begin(), tmp.end()));
160                if (tmp.size() > 1 && B.count(tmp) == 0) {
161                    Bk.emplace(tmp.begin(), tmp.end());
162                }
163                tmp.clear();
164            }
165        }
166        Bi.swap(Bk);
167    }
168
169    BicliqueSet factoringSets(0);
170    factoringSets.reserve(B.size());
171    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {       
172        ObjectSet Ai(var->begin(), var->end());
173        assert (Bi->size() > 1);
174        for (const PabloAST * user : *Bi) {
175            ObjectSet Aj(cast<Variadic>(user)->begin(), cast<Variadic>(user)->end());
176            std::sort(Aj.begin(), Aj.end());
177            ObjectSet Ak;
178            Ak.reserve(std::min<unsigned>(Ai.size(), Aj.size()));
179            std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
180            Ai.swap(Ak);
181        }
182        if (Ai.size() > 1) {
183            factoringSets.emplace_back(std::move(Ai), std::move(*Bi));
184        }
185    }
186
187    return factoringSets;
188}
189
190/** ------------------------------------------------------------------------------------------------------------- *
191 * @brief intersects
192 ** ------------------------------------------------------------------------------------------------------------- */
193template <class Type>
194inline bool intersects(const Type & A, const Type & B) {
195    auto first1 = A.begin(), last1 = A.end();
196    auto first2 = B.begin(), last2 = B.end();
197    assert (std::is_sorted(first1, last1));
198    assert (std::is_sorted(first2, last2));
199    while (first1 != last1 && first2 != last2) {
200        if (*first1 < *first2) {
201            ++first1;
202        } else if (*first2 < *first1) {
203            ++first2;
204        } else {
205            return true;
206        }
207    }
208    return false;
209}
210
211/** ------------------------------------------------------------------------------------------------------------- *
212 * @brief independentCliqueSets
213 ** ------------------------------------------------------------------------------------------------------------- */
214FactorizeDFG::BicliqueSet FactorizeDFG::independentFactoringSets(BicliqueSet && factorings, const unsigned side) {
215    using IndependentSetGraph = adjacency_matrix<undirectedS, unsigned>;
216    using Vertex = IndependentSetGraph::vertex_descriptor;
217
218    const auto l = factorings.size();
219    IndependentSetGraph I(l);
220
221    // Initialize our weights and determine the constraints
222    for (auto i = factorings.begin(); i != factorings.end(); ++i) {
223        I[std::distance(factorings.begin(), i)] = std::pow(side == 0 ? std::get<0>(*i).size() : std::get<1>(*i).size(), 2);
224        for (auto j = i; ++j != factorings.end(); ) {
225            if (intersects(i->first, j->first) && intersects(i->second, j->second)) {
226                add_edge(std::distance(factorings.begin(), i), std::distance(factorings.begin(), j), I);
227            }
228        }
229    }
230
231    // Use the greedy algorithm to choose our independent set
232    std::vector<Vertex> selected(0);
233    selected.reserve(l);
234
235    for (;;) {
236        unsigned w = 0;
237        Vertex u = 0;
238        for (unsigned i = 0; i != l; ++i) {
239            if (I[i] > w) {
240                w = I[i];
241                u = i;
242            }
243        }
244        if (w < 2) break;
245        selected.push_back(u);
246        I[u] = 0;
247        for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
248            I[v] = 0;
249        }
250    }
251
252    // Sort the selected list and then remove the unselected cliques
253    std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
254    auto end = factorings.end();
255    for (const unsigned offset : selected) {
256        end = factorings.erase(factorings.begin() + offset + 1, end) - 1;
257    }
258    factorings.erase(factorings.begin(), end);
259
260    return std::move(factorings);
261}
262
263/** ------------------------------------------------------------------------------------------------------------- *
264 * @brief makeCheckSet
265 ** ------------------------------------------------------------------------------------------------------------- */
266FactorizeDFG::CheckSet FactorizeDFG::makeCheckSet(PabloBlock * const scope, const ObjectSet & values) const {
267    CheckSet checks;
268    assert (scope);
269    const unsigned baseScopeDepth = scopeDepthOf(scope);
270    for (PabloAST * value : values) {
271        if (isa<Statement>(value)) {
272            unsigned scopeDepth = scopeDepthOf(cast<Statement>(value)->getParent());
273            // Is this from a preceeding scope? Or a nested scope?
274            if (scopeDepth < baseScopeDepth) {
275                continue;
276            } else if (scopeDepth > baseScopeDepth) {
277                // If we're in a nested scope, we want to know what branch statement enters it and
278                // add that to our checks instead of the operand itself.
279                PabloBlock * nested = cast<Statement>(value)->getParent();
280                for (;;) {
281                    assert (nested);
282                    value = nested->getBranch();
283                    nested = nested->getParent();
284                    if (nested == scope) {
285                        break;
286                    }
287                }
288            }
289            checks.insert(value);
290        }
291    }
292    return checks;
293}
294
295/** ------------------------------------------------------------------------------------------------------------- *
296 * @brief firstIn
297 ** ------------------------------------------------------------------------------------------------------------- */
298inline Statement * FactorizeDFG::firstIn(PabloBlock * const scope, Statement * const initial, const ObjectSet & users) const {
299    const auto checks = makeCheckSet(scope, users);
300    Statement * stmt = initial;
301    while (stmt) {
302        if (LLVM_UNLIKELY(checks.count(stmt) != 0)) {
303            return stmt;
304        }
305        stmt = stmt->getNextNode();
306    }
307    return scope->back();
308}
309
310/** ------------------------------------------------------------------------------------------------------------- *
311 * @brief lastIn
312 ** ------------------------------------------------------------------------------------------------------------- */
313inline Statement * FactorizeDFG::lastIn(PabloBlock * const scope, Statement * const initial, const ObjectSet & operands) const {
314    const auto checks = makeCheckSet(scope, operands);
315    Statement * stmt = initial;
316    while (stmt) {
317        if (LLVM_UNLIKELY(checks.count(stmt) != 0)) {
318            return stmt;
319        }
320        stmt = stmt->getPrevNode();
321    }
322    return scope->front();
323}
324
325/** ------------------------------------------------------------------------------------------------------------- *
326 * @brief findInsertionScope
327 ** ------------------------------------------------------------------------------------------------------------- */
328inline PabloBlock * FactorizeDFG::findInsertionScope(const ObjectSet & users) const {
329    std::vector<PabloBlock *> scopes;
330    scopes.reserve(users.size());
331    for (PabloAST * user : users) {
332        PabloBlock * const scope = cast<Statement>(user)->getParent(); assert (scope);
333        if (std::find(scopes.begin(), scopes.end(), scope) == scopes.end()) {
334            scopes.push_back(scope);
335        }
336    }
337    while (scopes.size() > 1) {
338        // Find the LCA of both scopes then add the LCA back to the list of scopes.
339        PabloBlock * scope1 = scopes.back(); scopes.pop_back();
340        PabloBlock * scope2 = scopes.back(); scopes.pop_back();
341        assert (scope1 != scope2);
342        unsigned depth1 = scopeDepthOf(scope1);
343        unsigned depth2 = scopeDepthOf(scope2);
344        // If one of these scopes is nested deeper than the other, scan upwards through
345        // the scope tree until both scopes are at the same depth.
346        while (depth1 > depth2) {
347            scope1 = scope1->getParent();
348            --depth1;
349        }
350        while (depth1 < depth2) {
351            scope2 = scope2->getParent();
352            --depth2;
353        }
354        assert (depth1 == depth2);
355        // Then iteratively step backwards until we find a matching set of scopes; this
356        // must be the LCA of our original scopes.
357        while (scope1 != scope2) {
358            scope1 = scope1->getParent();
359            scope2 = scope2->getParent();
360        }
361        assert (scope1 && scope2);
362        if (std::find(scopes.begin(), scopes.end(), scope1) == scopes.end()) {
363            scopes.push_back(scope1);
364        }
365    }
366    assert (scopes.size() == 1);
367    return scopes.front();
368}
369
370/** ------------------------------------------------------------------------------------------------------------- *
371 * @brief factorize
372 ** ------------------------------------------------------------------------------------------------------------- */
373inline Variadic * FactorizeDFG::factorize(const TypeId typeId, PabloBlock * const scope, ObjectSet & operands, ObjectSet & users) const {
374    Statement * const lastOperand = lastIn(scope, scope->back(), operands);
375    Statement * const firstUsage = firstIn(scope, lastOperand, users);
376    scope->setInsertPoint(firstUsage ? firstUsage->getPrevNode() : lastOperand);
377    Variadic * factoring = nullptr;
378    if (typeId == TypeId::Or) {
379        factoring = scope->createOr(operands.begin(), operands.end());
380    } else if (typeId == TypeId::And) {
381        factoring = scope->createAnd(operands.begin(), operands.end());
382    } else { // if (typeId == TypeId::Xor) {
383        factoring = scope->createXor(operands.begin(), operands.end());
384    }
385    for (PabloAST * user : users) {
386        assert (user->getClassTypeId() == typeId);
387        for (PabloAST * op : operands) {
388            cast<Variadic>(user)->deleteOperand(op);
389        }
390        cast<Variadic>(user)->addOperand(factoring);
391    }
392    return factoring;
393}
394
395/** ------------------------------------------------------------------------------------------------------------- *
396 * @brief processFactoringSets
397 ** ------------------------------------------------------------------------------------------------------------- */
398inline bool FactorizeDFG::processFactoringSets(const TypeId typeId, PabloBlock * const scope, BicliqueSet && factoringSets) const {
399    const auto S = independentFactoringSets(std::move(factoringSets), 0);
400    for (auto i : S) {
401        factorize(typeId, scope, std::get<0>(i), std::get<1>(i));
402    }
403    return !S.empty();
404}
405
406///** ------------------------------------------------------------------------------------------------------------- *
407// * @brief processFactoringSets
408// ** ------------------------------------------------------------------------------------------------------------- */
409//inline bool FactorizeDFG::processFactoringSets(const TypeId typeId, BicliqueSet && factoringSets, ObjectSet & factorings) const {
410//    const auto S = independentFactoringSets(std::move(factoringSets), 0);
411//    for (auto i : S) {
412//        factorings.push_back(factorize(typeId, findInsertionScope(std::get<1>(i)), std::get<0>(i), std::get<1>(i)));
413//    }
414//    return !S.empty();
415//}
416
417/** ------------------------------------------------------------------------------------------------------------- *
418 * @brief factor
419 ** ------------------------------------------------------------------------------------------------------------- */
420bool FactorizeDFG::factor(PabloBlock * const block) {
421    Statement * stmt = block->front();
422    bool factored = false;
423    while (stmt) {
424        if (isa<If>(stmt) || isa<While>(stmt)) {
425            if (factor(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody())) {
426                factored = true;
427            }
428        } else if (isa<Variadic>(stmt)) {
429            if (processFactoringSets(stmt->getClassTypeId(), block, enumerateFactoringSets(cast<Variadic>(stmt)))) {
430                factored = true;
431            }
432        }
433        stmt = stmt->getNextNode();
434    }
435    return factored;
436}
437
438///** ------------------------------------------------------------------------------------------------------------- *
439// * @brief factor
440// ** ------------------------------------------------------------------------------------------------------------- */
441//void FactorizeDFG::factor(PabloFunction & function, const TypeId typeId) {
442//    ObjectSet vars;
443//    for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
444//        vars.push_back(function.getParameter(i));
445//    }
446//    while (processFactoringSets(typeId, enumerateFactoringSets(vars, function.getEntryBlock(), typeId), vars));
447//}
448
449/** ------------------------------------------------------------------------------------------------------------- *
450 * @brief factor
451 ** ------------------------------------------------------------------------------------------------------------- */
452inline void FactorizeDFG::factor(PabloFunction & function) {
453    while (factor(function.getEntryBlock()));
454}
455
456//inline void print(PabloAST * expr, raw_ostream & out) {
457//    if (isa<Statement>(expr)) {
458//        PabloPrinter::print(cast<Statement>(expr), out);
459//    } else {
460//        PabloPrinter::print(expr, out);
461//    }
462//}
463
464/** ------------------------------------------------------------------------------------------------------------- *
465 * @brief lower
466 *
467 * The goal of this function is to try and lower a variadic operation into binary form while attempting to mitigate
468 * register pressure under the assumption that LLVM is not going to significantly change the IR (which was observed
469 * when assessing the ASM output of LLVM 3.6.1 using O3.)
470 ** ------------------------------------------------------------------------------------------------------------- */
471inline Statement * FactorizeDFG::lower(Variadic * const var, PabloBlock * block) const {
472
473    using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *, unsigned>;
474    using Vertex = Graph::vertex_descriptor;
475    using Map = flat_map<const PabloAST *, Vertex>;
476    using SchedulingData = std::pair<unsigned, PabloAST *>;
477    using SchedulingPriorityQueue = std::priority_queue<SchedulingData, std::vector<SchedulingData>, std::greater<SchedulingData>>;
478
479    const unsigned NOT_STEP = 1;
480    const unsigned BOOLEAN_STEP = 10;
481    const unsigned OTHER_STEP = 30;
482    const unsigned DESIRED_GAP = 30;
483
484    assert (var->getParent() == block);
485    assert (var->getNumOperands() > 2);
486
487    const unsigned operands = var->getNumOperands();
488
489    Graph G(operands + 1);
490    Map M;
491
492    G[operands] = var;
493    M.emplace(var, operands);
494
495    for (Vertex u = 0; u != operands; ++u) {
496        PabloAST * const op = var->getOperand(u);
497        G[u] = op;
498        M.emplace(op, u);
499        assert ("AST structural error!" && (op->getNumUses() > 0));
500        for (PabloAST * user : op->users()) {
501            if (LLVM_LIKELY(isa<Statement>(user))) {
502                Statement * usage = cast<Statement>(user);
503                PabloBlock * scope = usage->getParent();
504                while (scope) {
505                    if (scope == block) {
506                        auto f = M.find(usage);
507                        Vertex v = 0;
508                        if (f == M.end()) {
509                            v = add_vertex(usage, G);
510                            M.emplace(usage, v);
511                        } else {
512                            v = f->second;
513                        }
514                        G[add_edge(u, v, G).first] = 0;
515                        break;
516                    }
517                    usage = scope->getBranch();
518                    scope = scope->getParent();
519                }
520            }
521        }
522    }
523
524    assert (M.count(var) == 1);
525
526    unsigned estQuantum = 0;
527    circular_buffer<std::pair<unsigned, Vertex>> defs(operands);
528    for (Statement * stmt : *block) {
529        switch (stmt->getClassTypeId()) {
530            case TypeId::And:
531            case TypeId::Or:
532            case TypeId::Xor:
533                estQuantum += BOOLEAN_STEP;
534                break;
535            case TypeId::Not:
536                estQuantum += NOT_STEP;
537                break;
538            default:
539                estQuantum += OTHER_STEP;
540        }
541        auto f = M.find(stmt);
542        if (LLVM_UNLIKELY(f != M.end())) {
543            const auto u = f->second;
544            if (LLVM_UNLIKELY(u == operands)) {
545                assert (stmt == var);
546                break;
547            }
548            for (auto e : make_iterator_range(in_edges(u, G)))   {
549                G[e] = estQuantum;
550            }
551            if (u < operands) {
552                defs.push_back(std::make_pair(estQuantum + DESIRED_GAP, u));
553            }
554        }
555        // Annotate G to indicate when we expect a statement will be available
556        while (defs.size() > 0) {
557            unsigned availQuantum = 0;
558            Vertex u = 0;
559            std::tie(availQuantum, u) = defs.front();
560            if (availQuantum > estQuantum) {
561                break;
562            }
563            defs.pop_front();
564            auto f = M.find(stmt);
565            Vertex v = 0;
566            if (f == M.end()) {
567                v = add_vertex(stmt, G);
568                M.emplace(stmt, v);
569            } else {
570                v = f->second;
571            }
572            G[add_edge(u, v, G).first] = estQuantum;
573        }
574    }
575
576    for (Vertex u = 0; u < operands; ++u) {
577        unsigned quantum = 0;
578        Vertex v = operands;
579        for (auto e : make_iterator_range(out_edges(u, G))) {
580            if (quantum < G[e]) {
581                quantum = G[e];
582                v = target(e, G);
583            }
584        }
585        clear_out_edges(u, G);
586        G[add_edge(u, v, G).first] = quantum;
587    }
588
589    for (auto e : make_iterator_range(in_edges(operands, G)))   {
590        G[e] = estQuantum;
591    }
592
593    assert (num_edges(G) == var->getNumOperands());
594
595//    raw_os_ostream out(std::cerr);
596
597//    out << "==============================================================================\n";
598//    PabloPrinter::print(var, out); out << '\n';
599//    out << "------------------------------------------------------------------------------\n";
600
601//    out << "digraph G {\n";
602//    for (auto u : make_iterator_range(vertices(G))) {
603//        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
604//            continue;
605//        }
606//        out << "v" << u << " [label=\"" << u << ": ";
607//        PabloPrinter::print(G[u], out);
608//        out << "\"];\n";
609//    }
610//    for (auto e : make_iterator_range(edges(G))) {
611//        const auto s = source(e, G);
612//        const auto t = target(e, G);
613//        out << "v" << s << " -> v" << t << "[label=\"" << G[e] << "\"];\n";
614//    }
615
616//    out << "}\n\n";
617//    out.flush();
618
619//    out << "------------------------------------------------------------------------------\n";
620
621    SchedulingPriorityQueue Q;
622    while (num_edges(G) > 0) {
623
624        Graph::edge_descriptor f;
625        unsigned quantum = std::numeric_limits<unsigned>::max();
626        for (auto e : make_iterator_range(edges(G))) {
627            if (in_degree(source(e, G), G) == 0) {
628                if (quantum > G[e]) {
629                    quantum = G[e];
630                    f = e;
631                }
632            }
633        }
634
635        assert ("No edge selected!" && (quantum < std::numeric_limits<unsigned>::max()));
636
637        const auto u = source(f, G);
638        assert (u < operands);
639        PabloAST * const op1 = var->getOperand(u);
640        const auto v = target(f, G);
641        assert (isa<Statement>(G[v]));
642        remove_edge(f, G);
643
644        // Since this might have been a target of a prior pairing, read the original operand value instead of
645        // G when checking which value is indicated by u.
646        block->setInsertPoint(cast<Statement>(G[v]));
647        if (LLVM_LIKELY(Q.size() > 0)) {
648            unsigned minQuantum = 0; PabloAST * op2 = nullptr;
649            std::tie(minQuantum, op2) = Q.top();
650            if (minQuantum < quantum) {
651                Q.pop();
652                PabloAST * result = nullptr;
653                if (isa<And>(var)) {
654                    result = block->createAnd(op1, op2);
655                } else if (isa<Or>(var)) {
656                    result = block->createOr(op1, op2);
657                } else { // if (isa<Xor>(var)) {
658                    result = block->createXor(op1, op2);
659                }
660
661//                out << " -- ";
662//                print(op1, out);
663//                out << " + ";
664//                print(op2, out);
665//                out << " -> ";
666//                print(result, out);
667//                out << '\n';
668//                out.flush();
669
670                if (LLVM_LIKELY(isa<Statement>(result))) {
671                    G[v] = result; // update the insertion point node value
672                    quantum += DESIRED_GAP;
673                } else {
674                    G[v] = cast<Statement>(op2); // update the insertion point node value
675                    quantum = estQuantum;
676                }
677                Q.emplace(quantum, result);
678                continue;
679            }
680        }
681        Q.emplace(quantum, op1);
682    }
683
684//    out << "------------------------------------------------------------------------------\n";
685
686    // If we've done our best to schedule the statements and have operands remaining in our queue, generate a
687    // tree of the remaining operands.
688    while (Q.size() > 1) {
689        unsigned q1 = 0; PabloAST * op1 = nullptr;
690        std::tie(q1, op1) = Q.top();
691        Q.pop();
692
693        unsigned q2 = 0; PabloAST * op2 = nullptr;
694        std::tie(q2, op2) = Q.top();
695        Q.pop();
696
697        assert (q2 >= q1);
698
699        PabloAST * result = nullptr;
700        if (isa<And>(var)) {
701            result = block->createAnd(op1, op2);
702        } else if (isa<Or>(var)) {
703            result = block->createOr(op1, op2);
704        } else { // if (isa<Xor>(var)) {
705            result = block->createXor(op1, op2);
706        }
707
708//        out << " -- ";
709//        print(op1, out);
710//        out << " + ";
711//        print(op2, out);
712//        out << " -> ";
713//        print(result, out);
714//        out << '\n';
715//        out.flush();
716
717        Q.emplace(q2 + DESIRED_GAP, result);
718    }
719
720    assert (Q.size() == 1);
721    return var->replaceWith(std::get<1>(Q.top()));
722}
723
724/** ------------------------------------------------------------------------------------------------------------- *
725 * @brief lower
726 ** ------------------------------------------------------------------------------------------------------------- */
727void FactorizeDFG::lower(PabloBlock * const block) const {
728    Statement * stmt = block->front();
729    while (stmt) {
730        if (isa<If>(stmt) || isa<While>(stmt)) {
731            lower(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
732        } else if ((stmt->getNumOperands() > 2) && (isa<Variadic>(stmt))) {
733            stmt = lower(cast<Variadic>(stmt), block);
734            continue;
735        }
736        stmt = stmt->getNextNode();
737    }
738}
739
740/** ------------------------------------------------------------------------------------------------------------- *
741 * @brief lower
742 ** ------------------------------------------------------------------------------------------------------------- */
743inline void FactorizeDFG::lower(PabloFunction & function) const {
744    lower(function.getEntryBlock());
745}
746
747/** ------------------------------------------------------------------------------------------------------------- *
748 * @brief initialize
749 ** ------------------------------------------------------------------------------------------------------------- */
750void FactorizeDFG::initialize(PabloBlock * const block, const unsigned depth) {
751    Statement * stmt = block->front();
752    while (stmt) {
753        if (isa<If>(stmt) || isa<While>(stmt)) {
754            PabloBlock * body = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
755            mScopeDepth.emplace(body, depth);
756            initialize(body, depth + 1);
757        }
758        stmt = stmt->getNextNode();
759    }
760}
761
762/** ------------------------------------------------------------------------------------------------------------- *
763 * @brief enumerateScopeDepth
764 ** ------------------------------------------------------------------------------------------------------------- */
765inline void FactorizeDFG::initialize(PabloFunction & function) {
766    mScopeDepth.emplace(nullptr, 0);
767    mScopeDepth.emplace(function.getEntryBlock(), 1);
768    initialize(function.getEntryBlock(), 2);
769}
770
771/** ------------------------------------------------------------------------------------------------------------- *
772 * @brief scopeDepthOf
773 ** ------------------------------------------------------------------------------------------------------------- */
774inline unsigned FactorizeDFG::scopeDepthOf(const PabloAST * const expr) const {
775    return LLVM_LIKELY(isa<Statement>(expr)) ? scopeDepthOf(cast<Statement>(expr)->getParent()) : 0;
776}
777
778/** ------------------------------------------------------------------------------------------------------------- *
779 * @brief scopeDepthOf
780 ** ------------------------------------------------------------------------------------------------------------- */
781inline unsigned FactorizeDFG::scopeDepthOf(const PabloBlock * const block) const {
782    assert (block);
783    const auto f = mScopeDepth.find(block);
784    assert (f != mScopeDepth.end());
785    return f->second;
786}
787
788/** ------------------------------------------------------------------------------------------------------------- *
789 * @brief transform
790 ** ------------------------------------------------------------------------------------------------------------- */
791void FactorizeDFG::transform(PabloFunction & function) {
792    FactorizeDFG ldfg;
793    ldfg.initialize(function);
794
795    ldfg.factor(function);
796    #ifndef NDEBUG
797    PabloVerifier::verify(function, "post-factoring");
798    #endif
799    Simplifier::optimize(function);
800
801    ldfg.lower(function);
802    #ifndef NDEBUG
803    PabloVerifier::verify(function, "post-lowering");
804    #endif
805    Simplifier::optimize(function);
806}
807
808}
Note: See TracBrowser for help on using the repository browser.