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

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

Initial work on adding types to PabloAST and mutable Var objects.

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