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

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

Bug fixes

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