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

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

Temporary check in

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