source: icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp @ 4764

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

More work on reassociation pass

File size: 34.5 KB
Line 
1#include "booleanreassociationpass.h"
2#include <boost/container/flat_set.hpp>
3#include <boost/container/flat_map.hpp>
4#include <boost/circular_buffer.hpp>
5#include <boost/graph/adjacency_list.hpp>
6#include <boost/graph/filtered_graph.hpp>
7#include <boost/graph/topological_sort.hpp>
8#include <pablo/optimizers/pablo_simplifier.hpp>
9#include <algorithm>
10#include <queue>
11#include <set>
12#include <iostream>
13#include <pablo/printer_pablos.h>
14#include "graph-facade.hpp"
15
16using namespace boost;
17using namespace boost::container;
18
19namespace pablo {
20
21using Graph = BooleanReassociationPass::Graph;
22using Vertex = Graph::vertex_descriptor;
23using VertexQueue = circular_buffer<Vertex>;
24using Map = BooleanReassociationPass::Map;
25using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
26using TypeId = PabloAST::ClassTypeId;
27
28/** ------------------------------------------------------------------------------------------------------------- *
29 * @brief optimize
30 ** ------------------------------------------------------------------------------------------------------------- */
31bool BooleanReassociationPass::optimize(PabloFunction & function) {
32    BooleanReassociationPass brp;
33
34    raw_os_ostream out(std::cerr);
35
36    out << "BEFORE:\n";
37    PabloPrinter::print(function.getEntryBlock().statements(), out);
38    out << "----------------------------------------------------------\n";
39    out.flush();
40
41    brp.resolveScopes(function);
42    brp.processScopes(function);
43    Simplifier::optimize(function);
44
45    out << "AFTER:\n";
46    PabloPrinter::print(function.getEntryBlock().statements(), out);
47
48    return true;
49}
50
51/** ------------------------------------------------------------------------------------------------------------- *
52 * @brief resolveScopes
53 ** ------------------------------------------------------------------------------------------------------------- */
54inline void BooleanReassociationPass::resolveScopes(PabloFunction &function) {
55    mResolvedScopes.emplace(&function.getEntryBlock(), nullptr);
56    resolveScopes(function.getEntryBlock());
57}
58
59/** ------------------------------------------------------------------------------------------------------------- *
60 * @brief resolveScopes
61 ** ------------------------------------------------------------------------------------------------------------- */
62void BooleanReassociationPass::resolveScopes(PabloBlock & block) {
63    for (Statement * stmt : block) {
64        if (isa<If>(stmt) || isa<While>(stmt)) {
65            PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
66            mResolvedScopes.emplace(&nested, stmt);
67            resolveScopes(nested);
68        }
69    }
70}
71
72/** ------------------------------------------------------------------------------------------------------------- *
73 * @brief processScopes
74 ** ------------------------------------------------------------------------------------------------------------- */
75inline void BooleanReassociationPass::processScopes(PabloFunction & function) {
76    std::vector<Statement *> terminals;
77    for (unsigned i = 0; i != function.getNumOfResults(); ++i) {
78        terminals.push_back(function.getResult(i));
79    }
80    processScopes(function.getEntryBlock(), std::move(terminals));
81}
82
83/** ------------------------------------------------------------------------------------------------------------- *
84 * @brief processScopes
85 ** ------------------------------------------------------------------------------------------------------------- */
86void BooleanReassociationPass::processScopes(PabloBlock & block, std::vector<Statement *> && terminals) {
87    processScope(block, std::move(terminals));
88    for (Statement * stmt : block) {
89        if (isa<If>(stmt)) {
90            const auto & defs = cast<const If>(stmt)->getDefined();
91            std::vector<Statement *> terminals(defs.begin(), defs.end());
92            processScopes(cast<If>(stmt)->getBody(), std::move(terminals));
93        } else if (isa<While>(stmt)) {
94            const auto & vars = cast<const While>(stmt)->getVariants();
95            std::vector<Statement *> terminals(vars.begin(), vars.end());
96            processScopes(cast<While>(stmt)->getBody(), std::move(terminals));
97        }
98    }
99}
100
101/** ------------------------------------------------------------------------------------------------------------- *
102 * @brief isOptimizable
103 *
104 * And, Or and Xor instructions are all associative, commutative and distributive operations. Thus we can
105 * safely rearrange expressions such as "((((a √ b) √ c) √ d) √ e) √ f" into "((a √ b) √ (c √ d)) √ (e √ f)".
106 ** ------------------------------------------------------------------------------------------------------------- */
107static inline bool isOptimizable(const PabloAST * const expr) {
108    assert (expr);
109    switch (expr->getClassTypeId()) {
110        case PabloAST::ClassTypeId::And:
111        case PabloAST::ClassTypeId::Or:
112        case PabloAST::ClassTypeId::Xor:
113            return true;
114        default:
115            return false;
116    }
117}
118
119/** ------------------------------------------------------------------------------------------------------------- *
120 * @brief inCurrentBlock
121 ** ------------------------------------------------------------------------------------------------------------- */
122static inline bool inCurrentBlock(const Statement * stmt, const PabloBlock & block) {
123    return stmt->getParent() == &block;
124}
125
126static inline bool inCurrentBlock(const PabloAST * expr, const PabloBlock & block) {
127    return isa<Statement>(expr) && inCurrentBlock(cast<Statement>(expr), block);
128}
129
130/** ------------------------------------------------------------------------------------------------------------- *
131 * @brief getVertex
132 ** ------------------------------------------------------------------------------------------------------------- */
133template<typename ValueType, typename GraphType, typename MapType>
134static inline Vertex getVertex(const ValueType value, GraphType & G, MapType & M) {
135    const auto f = M.find(value);
136    if (f != M.end()) {
137        return f->second;
138    }
139    const auto u = add_vertex(value, G);
140    M.insert(std::make_pair(value, u));
141    return u;
142}
143
144/** ------------------------------------------------------------------------------------------------------------- *
145 * @brief createTree
146 ** ------------------------------------------------------------------------------------------------------------- */
147static PabloAST * createTree(PabloBlock & block, const PabloAST::ClassTypeId typeId, circular_buffer<PabloAST *> & Q) {
148    assert (!Q.empty());
149    while (Q.size() > 1) {
150        PabloAST * e1 = Q.front(); Q.pop_front();
151        PabloAST * e2 = Q.front(); Q.pop_front();
152        PabloAST * expr = nullptr;
153        // Note: this switch ought to compile to an array of function pointers to the appropriate method.
154        switch (typeId) {
155            case PabloAST::ClassTypeId::And:
156                expr = block.createAnd(e1, e2); break;
157            case PabloAST::ClassTypeId::Or:
158                expr = block.createOr(e1, e2); break;
159            case PabloAST::ClassTypeId::Xor:
160                expr = block.createXor(e1, e2); break;
161            default: break;
162        }
163        Q.push_back(expr);
164    }
165    PabloAST * r = Q.front();
166    Q.clear();
167    return r;
168}
169
170/** ------------------------------------------------------------------------------------------------------------- *
171 * @brief printGraph
172 ** ------------------------------------------------------------------------------------------------------------- */
173static void printGraph(PabloBlock & block, const Graph & G, const std::string name) {
174    raw_os_ostream out(std::cerr);
175    out << "digraph " << name << " {\n";
176    for (auto u : make_iterator_range(vertices(G))) {
177//        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
178//            continue;
179//        }
180        out << "v" << u << " [label=\"";
181        PabloAST * expr = G[u];
182        if (isa<Statement>(expr)) {
183            if (LLVM_UNLIKELY(isa<If>(expr))) {
184                out << "If ";
185                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
186                out << ":";
187            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
188                out << "While ";
189                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
190                out << ":";
191            } else {
192                PabloPrinter::print(cast<Statement>(expr), "", out);
193            }
194        } else {
195            PabloPrinter::print(expr, out);
196        }
197        out << "\"";
198        if (!inCurrentBlock(expr, block)) {
199            out << " style=dashed";
200        }
201        out << "];\n";
202    }
203    for (auto e : make_iterator_range(edges(G))) {
204        out << "v" << source(e, G) << " -> v" << target(e, G) << ";\n";
205    }
206
207    if (num_vertices(G) > 0) {
208
209        out << "{ rank=same;";
210        for (auto u : make_iterator_range(vertices(G))) {
211            if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
212                out << " v" << u;
213            }
214        }
215        out << "}\n";
216
217        out << "{ rank=same;";
218        for (auto u : make_iterator_range(vertices(G))) {
219            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
220                out << " v" << u;
221            }
222        }
223        out << "}\n";
224
225    }
226
227    out << "}\n\n";
228    out.flush();
229}
230
231/** ------------------------------------------------------------------------------------------------------------- *
232 * @brief printGraph
233 ** ------------------------------------------------------------------------------------------------------------- */
234template<typename SubgraphType>
235static void printGraph(PabloBlock & block, const SubgraphType & S, const Graph & G, const std::string name) {
236    raw_os_ostream out(std::cerr);
237    out << "digraph " << name << " {\n";
238    for (auto u : make_iterator_range(vertices(S))) {
239        if (in_degree(u, S) == 0 && out_degree(u, S) == 0) {
240            continue;
241        }
242        out << "v" << u << " [label=\"";
243        PabloAST * expr = G[S[u]];
244        if (isa<Statement>(expr)) {
245            if (LLVM_UNLIKELY(isa<If>(expr))) {
246                out << "If ";
247                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
248                out << ":";
249            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
250                out << "While ";
251                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
252                out << ":";
253            } else {
254                PabloPrinter::print(cast<Statement>(expr), "", out);
255            }
256        } else {
257            PabloPrinter::print(expr, out);
258        }
259        out << "\"";
260        if (!inCurrentBlock(expr, block)) {
261            out << " style=dashed";
262        }
263        out << "];\n";
264    }
265    for (auto e : make_iterator_range(edges(S))) {
266        out << "v" << source(e, S) << " -> v" << target(e, S) << ";\n";
267    }
268
269    if (num_vertices(S) > 0) {
270
271        out << "{ rank=same;";
272        for (auto u : make_iterator_range(vertices(S))) {
273            if (in_degree(u, S) == 0 && out_degree(u, S) != 0) {
274                out << " v" << u;
275            }
276        }
277        out << "}\n";
278
279        out << "{ rank=same;";
280        for (auto u : make_iterator_range(vertices(S))) {
281            if (out_degree(u, S) == 0 && in_degree(u, S) != 0) {
282                out << " v" << u;
283            }
284        }
285        out << "}\n";
286
287    }
288
289    out << "}\n\n";
290    out.flush();
291}
292
293/** ------------------------------------------------------------------------------------------------------------- *
294 * @brief processScope
295 ** ------------------------------------------------------------------------------------------------------------- */
296inline void BooleanReassociationPass::processScope(PabloBlock & block, std::vector<Statement *> && terminals) {
297    Graph G;
298
299    summarizeAST(block, G);
300    redistributeAST(block, G);
301
302    circular_buffer<Vertex> Q(num_vertices(G));
303    topological_sort(G, std::front_inserter(Q));
304    assert (Q.size() == num_vertices(G));
305
306    circular_buffer<PabloAST *> nodes;
307    block.setInsertPoint(block.back());
308
309    while (!Q.empty()) {
310        const Vertex u = Q.front(); Q.pop_front();
311        PabloAST * expr = G[u];
312        if (LLVM_LIKELY(inCurrentBlock(expr, block))) {
313            if (isOptimizable(expr)) {
314                if (in_degree(u, G) == 0) {
315                    cast<Statement>(expr)->eraseFromParent(false);
316                    continue;
317                } else {
318                    if (LLVM_UNLIKELY(nodes.capacity() < in_degree(u, G))) {
319                        nodes.set_capacity(in_degree(u, G));
320                    }
321                    for (auto e : make_iterator_range(in_edges(u, G))) {
322                        nodes.push_back(G[source(e, G)]);
323                    }
324                    assert (nodes.size() == in_degree(u, G));
325                    PabloAST * replacement = createTree(block, expr->getClassTypeId(), nodes);
326
327                    cast<Statement>(expr)->replaceWith(replacement, true, false);
328                    expr = replacement;
329                    G[u] = replacement;
330                }
331            }
332            block.insert(cast<Statement>(expr));
333        }
334    }
335}
336
337/** ------------------------------------------------------------------------------------------------------------- *
338 * @brief summarizeAST
339 *
340 * This function scans through a basic block (starting by its terminals) and computes a DAG in which any sequences
341 * of AND, OR or XOR functions are "flattened" (i.e., allowed to have any number of inputs.) This allows us to
342 * reassociate them in the most efficient way possible.
343 ** ------------------------------------------------------------------------------------------------------------- */
344void BooleanReassociationPass::summarizeAST(PabloBlock & block, Graph & G) const {
345
346    Map M;
347
348    // Compute the base def-use graph ...
349    for (Statement * stmt : block) {
350        const Vertex u = getVertex(stmt, G, M);
351        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
352            PabloAST * const op = stmt->getOperand(i);
353            if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
354                continue;
355            }
356            add_edge(getVertex(op, G, M), u, G);
357        }
358        if (isa<If>(stmt)) {
359            for (Assign * def : cast<const If>(stmt)->getDefined()) {
360                const Vertex v = getVertex(def, G, M);
361                add_edge(u, v, G);
362                resolveUsages(v, def, block, G, M);
363            }
364        } else if (isa<While>(stmt)) {
365            for (Next * var : cast<const While>(stmt)->getVariants()) {
366                const Vertex v = getVertex(var, G, M);
367                add_edge(u, v, G);
368                resolveUsages(v, var, block, G, M);
369            }
370        } else {
371            resolveUsages(u, stmt, block, G, M);
372        }
373    }
374
375    std::vector<Vertex> ordering;
376    ordering.reserve(num_vertices(G));
377    topological_sort(G, std::back_inserter(ordering));
378
379    for (auto i = ordering.rbegin(); i != ordering.rend(); ++i) {
380        const Vertex u = *i;
381        if (isOptimizable(G[u])) {
382            std::vector<Vertex> removable;
383            for (auto e : make_iterator_range(in_edges(u, G))) {
384                const Vertex v = source(e, G);
385                if (out_degree(v, G) == 1 && in_degree(v, G) != 0 && G[u]->getClassTypeId() == G[v]->getClassTypeId()) {
386                    removable.push_back(v);
387                    for (auto e : make_iterator_range(in_edges(v, G))) {
388                        add_edge(source(e, G), u, G);
389                    }
390                }
391            }
392            for (auto v : removable) {
393                clear_vertex(v, G);
394            }
395        }
396    }
397}
398
399/** ------------------------------------------------------------------------------------------------------------- *
400 * @brief resolveUsages
401 ** ------------------------------------------------------------------------------------------------------------- */
402void BooleanReassociationPass::resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M) const {
403    for (PabloAST * user : expr->users()) {
404        assert (user);
405        if (LLVM_LIKELY(user != expr && isa<Statement>(user))) {
406            PabloBlock * parent = cast<Statement>(user)->getParent();
407            assert (parent);
408            if (LLVM_UNLIKELY(parent != &block)) {
409                for (;;) {
410                    if (LLVM_UNLIKELY(parent == nullptr)) {
411                        assert (isa<Assign>(expr) || isa<Next>(expr));
412                        break;
413                    } else if (parent->getParent() == &block) {
414                        const auto f = mResolvedScopes.find(parent);
415                        if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
416                            throw std::runtime_error("Failed to resolve scope block!");
417                        }
418                        add_edge(u, getVertex(f->second, G, M), G);
419                        break;
420                    }
421                    parent = parent->getParent();
422                }
423            }
424        }
425    }
426}
427
428using VertexSet = std::vector<Vertex>;
429using VertexSets = std::vector<VertexSet>;
430
431template <class Graph>
432static VertexSet incomingVertexSet(const Vertex u, const Graph & G) {
433    VertexSet V;
434    V.reserve(G.in_degree(u));
435    for (auto e : make_iterator_range(G.in_edges(u))) {
436        V.push_back(G.source(e));
437    }
438    std::sort(V.begin(), V.end());
439    return std::move(V);
440}
441
442template <class Graph>
443static VertexSet outgoingVertexSet(const Vertex u, const Graph & G) {
444    VertexSet V;
445    V.reserve(G.out_degree(u));
446    for (auto e : make_iterator_range(G.out_edges(u))) {
447        V.push_back(G.target(e));
448    }
449    std::sort(V.begin(), V.end());
450    return std::move(V);
451}
452
453/** ------------------------------------------------------------------------------------------------------------- *
454 * @brief enumerateBicliques
455 *
456 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
457 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies with an in-degree of 0
458 * to be in bipartition A and their adjacencies to be in B.
459  ** ------------------------------------------------------------------------------------------------------------- */
460template <class Graph>
461static VertexSets enumerateBicliques(const Graph & G) {
462    using IntersectionSets = std::set<VertexSet>;
463
464    IntersectionSets B1;
465    for (auto u : make_iterator_range(G.vertices())) {
466        if (G.in_degree(u) == 0) {
467            B1.insert(std::move(outgoingVertexSet(u, G)));
468        }
469    }
470
471    IntersectionSets C(B1.begin(), B1.end());
472
473    IntersectionSets Bi;
474    VertexSet clique;
475    for (auto i = B1.begin(); i != B1.end(); ++i) {
476        for (auto j = i; ++j != B1.end(); ) {
477            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
478            if (clique.size() > 0) {
479                if (C.count(clique) == 0) {
480                    Bi.insert(clique);
481                }
482                clique.clear();
483            }
484        }
485    }
486
487    for (;;) {
488        if (Bi.empty()) {
489            break;
490        }
491        C.insert(Bi.begin(), Bi.end());
492        IntersectionSets Bk;
493        for (auto i = B1.begin(); i != B1.end(); ++i) {
494            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
495                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
496                if (clique.size() > 0) {
497                    if (C.count(clique) == 0) {
498                        Bk.insert(clique);
499                    }
500                    clique.clear();
501                }
502            }
503        }
504        Bi.swap(Bk);
505    }
506    return VertexSets(C.begin(), C.end());
507}
508
509/** ------------------------------------------------------------------------------------------------------------- *
510 * @brief intersects
511 ** ------------------------------------------------------------------------------------------------------------- */
512template <class Type>
513inline bool intersects(const Type & A, const Type & B) {
514    auto first1 = A.begin(), last1 = A.end();
515    auto first2 = B.begin(), last2 = B.end();
516    while (first1 != last1 && first2 != last2) {
517        if (*first1 < *first2) {
518            ++first1;
519        } else if (*first2 < *first1) {
520            ++first2;
521        } else {
522            return true;
523        }
524    }
525    return false;
526}
527
528/** ------------------------------------------------------------------------------------------------------------- *
529 * @brief maximalIndependentSet
530 ** ------------------------------------------------------------------------------------------------------------- */
531static VertexSets && maximalIndependentSet(VertexSets && V) {
532    using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
533    const auto l = V.size();
534    IndependentSetGraph I(l);
535    // Initialize our weights
536    for (unsigned i = 0; i != l; ++i) {
537        I[i] = V[i].size();
538    }
539    // Determine our constraints
540    for (unsigned i = 0; i != l; ++i) {
541        for (unsigned j = i + 1; j != l; ++j) {
542            if (intersects(V[i], V[j])) {
543                add_edge(i, j, I);
544            }
545        }
546    }
547    // Use the greedy algorithm to choose our independent set (TODO: try the similar randomized approach)
548    VertexSet selected;
549    std::vector<bool> ignored(l, false);
550    for (;;) {
551        unsigned w = 0;
552        Vertex u = 0;
553        for (unsigned i = 0; i != l; ++i) {
554            if (!ignored[i] && I[i] > w) {
555                w = I[i];
556                u = i;
557            }
558        }
559        if (w == 0) break;
560        selected.push_back(u);
561        ignored[u] = true;
562        for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
563            ignored[v] = true;
564        }
565    }
566    // Sort the selected list and then remove the unselected sets from V
567    std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
568    auto end = V.end();
569    for (const unsigned offset : selected) {
570        end = V.erase(V.begin() + offset + 1, end) - 1;
571    }
572    V.erase(V.begin(), end);
573    return std::move(V);
574}
575
576/** ------------------------------------------------------------------------------------------------------------- *
577 * @brief sinkIndependentMaximalBicliques
578 ** ------------------------------------------------------------------------------------------------------------- */
579template <class Graph>
580static VertexSets sinkIndependentMaximalBicliques(Graph && G) {
581    VertexSets B = maximalIndependentSet(std::move(enumerateBicliques(G)));
582    VertexSets A;
583    A.reserve(B.size());
584    for (const VertexSet & Bi : B) {
585        // Compute our A set
586        auto bi = Bi.begin();
587        VertexSet Ai = incomingVertexSet(*bi, G);
588        while (++bi != Bi.end()) {
589            VertexSet Ai = incomingVertexSet(*bi, G);
590            VertexSet Ak;
591            std::set_intersection(Ai.begin(), Ai.end(), Ai.begin(), Ai.end(), std::back_inserter(Ak));
592            Ai.swap(Ak);
593        }
594        A.emplace_back(std::move(Ai));
595    }
596    std::vector<Vertex> sources;
597    std::vector<Vertex> intermediary;
598    for (auto u : make_iterator_range(G.vertices())) {
599        if (G.in_degree(u) == 0) {
600            sources.push_back(u);
601        } else if (G.out_degree(u) != 0) {
602            intermediary.push_back(u);
603        }
604    }
605    for (auto u : sources) {
606        G.clear_out_edges(u);
607    }
608    for (unsigned i = 0; i != B.size(); ++i) {
609        for (auto u : A[i]) {
610            for (auto v : B[i]) {
611                G.add_edge(u, v);
612            }
613        }
614    }
615    for (auto u : intermediary) {
616        if (G.in_degree(u) == 0) {
617            G.clear_out_edges(u);
618        }
619    }
620    return std::move(A);
621}
622
623/** ------------------------------------------------------------------------------------------------------------- *
624 * @brief safeDistributionSets
625 ** ------------------------------------------------------------------------------------------------------------- */
626template <class Graph>
627static VertexSets safeDistributionSets(Graph & G) {
628    VertexSets sinks = sinkIndependentMaximalBicliques(makeTransposedGraphFacade(G));
629    // Scan through G and replicate any source that has more than one sink until G is broken
630    // into weakly connected components in which each has exactly one sink.
631    if (sinks.size() > 1) {
632        std::vector<unsigned> component(num_vertices(G), 0);
633        unsigned components = 0;
634        for (const VertexSet & S : sinks) {
635            ++components;
636            for (auto e : make_iterator_range(in_edges(S.front(), G))) {
637                component[source(e, G)] = components;
638            }
639        }
640        for (const Vertex u : make_iterator_range(vertices(G))) {
641            if (LLVM_UNLIKELY(in_degree(u, G) == 0)) {
642                flat_set<unsigned> membership;
643                for (auto e : make_iterator_range(out_edges(u, G))) {
644                    membership.insert(component[target(e, G)]);
645                }
646                if (LLVM_UNLIKELY(membership.size() > 1)) {
647                    VertexSet adjacent;
648                    adjacent.reserve(out_degree(u, G));
649                    for (auto e : make_iterator_range(out_edges(u, G))) {
650                        adjacent.push_back(target(e, G));
651                    }
652                    clear_out_edges(u, G);
653                    auto mi = membership.begin();
654                    for (Vertex w = u; ;) {
655                        const unsigned m = *mi;
656                        for (auto v : adjacent) {
657                            if (component[v] == m) {
658                                add_edge(w, v, G);
659                            }
660                        }
661                        if (++mi == membership.end()) {
662                            break;
663                        }
664                        w = add_vertex(G[u], G);
665                    }
666                }
667            }
668        }
669    }
670    return std::move(sinkIndependentMaximalBicliques(makeGraphFacade(G)));
671}
672
673/** ------------------------------------------------------------------------------------------------------------- *
674 * @brief segmentInto3LevelGraph
675 *
676 * Ensure that every source-to-sink path in G has an edge-distance of exactly 2. The safeDistributionSets algorithm
677 * expects that G exibits this property but if an input to a distributable function is also the output of another
678 * distributable function, this complicates the analysis process. Thus method resolves that by replicating the
679 * appropriate vertices into input-only and output-only vertices.
680 ** ------------------------------------------------------------------------------------------------------------- */
681template <class Graph>
682Graph & segmentInto3LevelGraph(Graph & G) {
683    std::vector<unsigned> distance(num_vertices(G), 0);
684    std::queue<Vertex> Q;
685    for (const Vertex u : make_iterator_range(vertices(G))) {
686        if (in_degree(u, G) == 0) {
687            distance[u] = 1;
688            for (const auto e : make_iterator_range(out_edges(u, G))) {
689                Q.push(target(e, G));
690            }
691        }
692    }
693    for (;;) {
694        const Vertex u = Q.front(); Q.pop();
695        unsigned dist = 0;
696        bool ready = true;
697        for (const auto e : make_iterator_range(in_edges(u, G))) {
698            const Vertex v = source(e, G);
699            if (LLVM_UNLIKELY(distance[v] == 0)) {
700                ready = false;
701                break;
702            }
703            dist = std::max(dist, distance[v]);
704        }
705        assert (dist <= 4);
706        if (ready) {
707            if (LLVM_UNLIKELY(dist == 4)) {
708                for (const auto e : make_iterator_range(in_edges(u, G))) {
709                    const Vertex v = source(e, G);
710                    if (distance[v] == 3) {
711                        const Vertex w = add_vertex(G[v], G);
712                        for (const auto e : make_iterator_range(out_edges(v, G))) {
713                            add_edge(w, target(e, G), G);
714                        }
715                        clear_out_edges(v, G);
716                        assert (w == distance.size());
717                        distance.push_back(0);
718                        Q.push(w);
719                    }
720                }
721            } else { // update the distance and add in the adjacent vertices to Q
722                distance[u] = dist + 1;
723                for (const auto e : make_iterator_range(out_edges(u, G))) {
724                    Q.push(target(e, G));
725                }
726            }
727        }
728        if (Q.empty()) {
729            break;
730        }
731    }
732    return G;
733}
734
735/** ------------------------------------------------------------------------------------------------------------- *
736 * @brief redistributeAST
737 *
738 * Apply the distribution law to reduce computations whenever possible.
739 ** ------------------------------------------------------------------------------------------------------------- */
740bool BooleanReassociationPass::redistributeAST(PabloBlock & block, Graph & G) const {
741    bool anyChanges = false;
742    for (;;) {
743
744        adjacency_list<hash_setS, vecS, bidirectionalS, Vertex> H;
745        flat_map<Vertex, Vertex> M;
746
747        for (const Vertex u : make_iterator_range(vertices(G))) {
748            const TypeId outerTypeId = G[u]->getClassTypeId();
749            if (outerTypeId == TypeId::And || outerTypeId == TypeId::Or) {
750                if (inCurrentBlock(cast<Statement>(G[u]), block)) {
751                    const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
752                    flat_set<Vertex> distributable;
753                    for (auto e : make_iterator_range(in_edges(u, G))) {
754                        const Vertex v = source(e, G);
755                        if (LLVM_UNLIKELY(G[v]->getClassTypeId() == innerTypeId) && LLVM_LIKELY(inCurrentBlock(cast<Statement>(G[v]), block))) {
756                            bool safe = true;
757                            for (const auto e : make_iterator_range(out_edges(v, G))) {
758                                if (G[target(e, G)]->getClassTypeId() != outerTypeId) {
759                                    safe = false;
760                                    break;
761                                }
762                            }
763                            if (safe) {
764                                distributable.insert(v);
765                            }
766                        }
767                    }
768                    if (LLVM_LIKELY(distributable.size() > 1)) {
769                        // We're only interested in computing a subgraph of G in which every source has an out-degree
770                        // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical
771                        // benefit. (Note: this does not consider register pressure / liveness.)
772                        flat_map<Vertex, unsigned> observed;
773                        bool anyOpportunities = false;
774                        for (const Vertex v : distributable) {
775                            for (auto e : make_iterator_range(in_edges(v, G))) {
776                                const Vertex w = source(e, G);
777                                const auto f = observed.find(w);
778                                if (f == observed.end()) {
779                                    observed.emplace(w, 0);
780                                } else {
781                                    f->second += 1;
782                                    anyOpportunities = true;
783                                }
784                            }
785                        }
786                        if (anyOpportunities) {
787                            for (auto ob : observed) {
788                                if (std::get<1>(ob)) {
789                                    const Vertex w = std::get<0>(ob);
790                                    for (auto e : make_iterator_range(out_edges(w, G))) {
791                                        const Vertex v = target(e, G);
792                                        if (distributable.count(v)) {
793                                            const Vertex y = getVertex(v, H, M);
794                                            add_edge(y, getVertex(u, H, M), H);
795                                            add_edge(getVertex(w, H, M), y, H);
796                                        }
797                                    }
798                                }
799                            }
800                        }
801                    }
802                }
803            }
804        }
805
806        // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
807        if (num_vertices(H) == 0) {
808            break;
809        }
810
811        printGraph(block, H, G, "H1");
812
813        const VertexSets distributionSets = safeDistributionSets(segmentInto3LevelGraph(H));
814
815        printGraph(block, H, G, "H2");
816
817        // If no sources remain, no bicliques were found that would have a meaningful impact on the AST.
818        if (LLVM_UNLIKELY(distributionSets.size() == 0)) {
819            break;
820        }
821
822        for (const VertexSet & sources : distributionSets) {
823            assert (sources.size() > 0);
824            const VertexSet intermediary = outgoingVertexSet(sources.front(), makeGraphFacade(H));
825            assert (intermediary.size() > 0);
826            const VertexSet sinks = outgoingVertexSet(intermediary.front(), makeGraphFacade(H));
827            assert (sinks.size() > 0);
828
829            // Now begin transforming the AST
830            const TypeId typeId = G[H[sinks.front()]]->getClassTypeId();
831            assert (typeId == TypeId::And || typeId == TypeId::Or);
832
833            circular_buffer<PabloAST *> Q(std::max(sources.size(), intermediary.size() + 1));
834            for (const Vertex u : intermediary) {
835                Q.push_back(G[H[u]]);
836            }
837            PabloAST * merged = createTree(block, typeId, Q);
838            for (const Vertex s : sources) {
839                Q.push_back(G[H[s]]);
840            }
841            Q.push_back(merged);
842            PabloAST * masked = createTree(block, typeId == TypeId::Or ? TypeId::And : TypeId::Or, Q);
843
844            // Eliminate the edges from our original graph
845            for (const Vertex u : intermediary) {
846                for (const Vertex s : sources) {
847                    remove_edge(H[s], H[u], G);
848                }
849                for (const Vertex t : sinks) {
850                    remove_edge(H[u], H[t], G);
851                }
852            }
853
854            // Finally update G to match the desired changes
855            const Vertex x = add_vertex(merged, G);
856            const Vertex y = add_vertex(masked, G);
857            for (const Vertex u : intermediary) {
858                add_edge(H[u], x, G);
859            }
860            add_edge(x, y, G);
861            for (const Vertex s : sources) {
862                add_edge(H[s], y, G);
863            }
864            for (const Vertex t : sinks) {
865                add_edge(y, H[t], G);
866            }
867            for (const Vertex u : intermediary) {
868                if (LLVM_UNLIKELY(in_degree(H[u], G) == 0)) {
869                    clear_out_edges(H[u], G);
870                }
871            }
872        }
873        anyChanges = true;
874    }
875    return anyChanges;
876}
877
878}
Note: See TracBrowser for help on using the repository browser.