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

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

Progress on multi-target UCD compilation

File size: 33.9 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 <pablo/analysis/pabloverifier.hpp>
10#include <algorithm>
11#include <numeric> // std::iota
12#include <queue>
13#include <set>
14#include <pablo/printer_pablos.h>
15
16using namespace boost;
17using namespace boost::container;
18
19namespace pablo {
20
21using TypeId = PabloAST::ClassTypeId;
22using Graph = BooleanReassociationPass::Graph;
23using Vertex = Graph::vertex_descriptor;
24using VertexData = BooleanReassociationPass::VertexData;
25using Map = BooleanReassociationPass::Map;
26using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>;
27using DistributionMap = flat_map<Graph::vertex_descriptor, DistributionGraph::vertex_descriptor>;
28using VertexSet = std::vector<Vertex>;
29using VertexSets = std::vector<VertexSet>;
30using Biclique = std::pair<VertexSet, VertexSet>;
31using BicliqueSet = std::vector<Biclique>;
32using DistributionSet = std::tuple<VertexSet, VertexSet, VertexSet>;
33using DistributionSets = std::vector<DistributionSet>;
34
35/** ------------------------------------------------------------------------------------------------------------- *
36 * @brief helper functions
37 ** ------------------------------------------------------------------------------------------------------------- */
38template<typename Iterator>
39inline Graph::edge_descriptor first(const std::pair<Iterator, Iterator> & range) {
40    assert (range.first != range.second);
41    return *range.first;
42}
43
44#ifndef NDEBUG
45static bool no_path(const Vertex u, const Vertex v, const Graph & G) {
46    if (u == v) return false;
47    flat_set<Vertex> V;
48    std::queue<Vertex> Q;
49    Q.push(u);
50    for (;;) {
51        Vertex w = Q.front();
52        if (w == v) {
53            return false;
54        }
55        Q.pop();
56        for (auto e : make_iterator_range(out_edges(w, G))) {
57            Vertex x = target(e, G);
58            if (V.count(x)) continue;
59            Q.push(x);
60            V.insert(x);
61        }
62        if (Q.empty()) {
63            break;
64        }
65    }
66    return true;
67}
68#endif
69
70inline void add_edge(PabloAST * expr, const Vertex u, const Vertex v, Graph & G) {
71    assert (no_path(v, u, G));
72    // Make sure each edge is unique
73    for (auto e : make_iterator_range(out_edges(u, G))) {
74        if (LLVM_UNLIKELY(target(e, G) == v && (G[e] == nullptr || G[e] == expr))) {
75            G[e] = expr;
76            return;
77        }
78    }
79    G[std::get<0>(add_edge(u, v, G))] = expr;
80}
81
82static inline bool inCurrentBlock(const Statement * stmt, const PabloBlock & block) {
83    return stmt->getParent() == &block;
84}
85
86static inline bool inCurrentBlock(const PabloAST * expr, const PabloBlock & block) {
87    return expr ? isa<Statement>(expr) && inCurrentBlock(cast<Statement>(expr), block) : true;
88}
89
90inline TypeId & getType(VertexData & data) {
91    return std::get<0>(data);
92}
93
94inline TypeId getType(const VertexData & data) {
95    return std::get<0>(data);
96}
97
98inline PabloAST *& getValue(VertexData & data) {
99    return std::get<1>(data);
100}
101
102inline PabloAST * getValue(const VertexData & data) {
103    return std::get<1>(data);
104}
105
106inline bool isAssociative(const VertexData & data) {
107    switch (getType(data)) {
108        case TypeId::And:
109        case TypeId::Or:
110        case TypeId::Xor:
111            return true;
112        default:
113            return false;
114    }
115}
116
117inline bool isDistributive(const VertexData & data) {
118    switch (getType(data)) {
119        case TypeId::And:
120        case TypeId::Or:
121            return true;
122        default:
123            return false;
124    }
125}
126
127inline bool isMutable(const VertexData & data, const PabloBlock &) {
128    return getType(data) != TypeId::Var;
129}
130
131inline bool isNonEscaping(const VertexData & data) {
132    return getType(data) != TypeId::Assign && getType(data) != TypeId::Next;
133}
134
135inline bool isSameType(const VertexData & data1, const VertexData & data2) {
136    return getType(data1) == getType(data2);
137}
138
139/** ------------------------------------------------------------------------------------------------------------- *
140 * @brief intersects
141 ** ------------------------------------------------------------------------------------------------------------- */
142template <class Type>
143inline bool intersects(const Type & A, const Type & B) {
144    auto first1 = A.begin(), last1 = A.end();
145    auto first2 = B.begin(), last2 = B.end();
146    while (first1 != last1 && first2 != last2) {
147        if (*first1 < *first2) {
148            ++first1;
149        } else if (*first2 < *first1) {
150            ++first2;
151        } else {
152            return true;
153        }
154    }
155    return false;
156}
157
158/** ------------------------------------------------------------------------------------------------------------- *
159 * @brief optimize
160 ** ------------------------------------------------------------------------------------------------------------- */
161bool BooleanReassociationPass::optimize(PabloFunction & function) {
162    BooleanReassociationPass brp;
163    brp.resolveScopes(function);
164    brp.processScopes(function);   
165    #ifndef NDEBUG
166    Simplifier::deadCodeElimination(function.getEntryBlock());
167    PabloVerifier::verify(function, "post-reassociation");
168    #endif
169    Simplifier::optimize(function);
170    return true;
171}
172
173/** ------------------------------------------------------------------------------------------------------------- *
174 * @brief resolveScopes
175 ** ------------------------------------------------------------------------------------------------------------- */
176inline void BooleanReassociationPass::resolveScopes(PabloFunction &function) {
177    mResolvedScopes.emplace(&function.getEntryBlock(), nullptr);
178    resolveScopes(function.getEntryBlock());
179}
180
181/** ------------------------------------------------------------------------------------------------------------- *
182 * @brief resolveScopes
183 ** ------------------------------------------------------------------------------------------------------------- */
184void BooleanReassociationPass::resolveScopes(PabloBlock & block) {
185    for (Statement * stmt : block) {
186        if (isa<If>(stmt) || isa<While>(stmt)) {
187            PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
188            mResolvedScopes.emplace(&nested, stmt);
189            resolveScopes(nested);
190        }
191    }
192}
193
194/** ------------------------------------------------------------------------------------------------------------- *
195 * @brief processScopes
196 ** ------------------------------------------------------------------------------------------------------------- */
197inline void BooleanReassociationPass::processScopes(PabloFunction & function) {
198    processScopes(function, function.getEntryBlock());
199}
200
201/** ------------------------------------------------------------------------------------------------------------- *
202 * @brief processScopes
203 ** ------------------------------------------------------------------------------------------------------------- */
204void BooleanReassociationPass::processScopes(PabloFunction & function, PabloBlock & block) {
205    for (Statement * stmt : block) {
206        if (isa<If>(stmt)) {
207            processScopes(function, cast<If>(stmt)->getBody());
208        } else if (isa<While>(stmt)) {
209            processScopes(function, cast<While>(stmt)->getBody());
210        }
211    }
212    processScope(function, block);
213}
214
215/** ------------------------------------------------------------------------------------------------------------- *
216 * @brief getVertex
217 ** ------------------------------------------------------------------------------------------------------------- */
218template<typename ValueType, typename GraphType, typename MapType>
219static inline Vertex getVertex(const ValueType value, GraphType & G, MapType & M) {
220    const auto f = M.find(value);
221    if (f != M.end()) {
222        return f->second;
223    }
224    const auto u = add_vertex(value, G);
225    M.insert(std::make_pair(value, u));
226    return u;
227}
228
229/** ------------------------------------------------------------------------------------------------------------- *
230 * @brief createTree
231 ** ------------------------------------------------------------------------------------------------------------- */
232PabloAST * BooleanReassociationPass::createTree(PabloBlock & block, const Vertex u, Graph & G, const WrittenAt & writtenAt) {
233    flat_set<PabloAST *> sources;
234    for (const auto e : make_iterator_range(in_edges(u, G))) {
235        PabloAST * expr = getValue(G[source(e, G)]);
236        assert ("G contains a null input variable!" && (expr != nullptr));
237        sources.insert(expr);
238    }
239    circular_buffer<PabloAST *> Q(sources.begin(), sources.end());
240    // Sort the queue in order of how the inputs were written
241    std::sort(Q.begin(), Q.end(), [&writtenAt](const PabloAST * const e1, const PabloAST * const e2) -> bool {
242        const auto f1 = writtenAt.find(e1); assert (f1 != writtenAt.end());
243        const auto f2 = writtenAt.find(e2); assert (f2 != writtenAt.end());
244        return f1->second < f2->second;
245    });
246
247    const TypeId typeId = getType(G[u]);
248    while (Q.size() > 1) {
249        PabloAST * e1 = Q.front(); Q.pop_front();       
250        PabloAST * e2 = Q.front(); Q.pop_front();
251        PabloAST * expr = nullptr;
252        switch (typeId) {
253            case TypeId::And:
254                expr = block.createAnd(e1, e2); break;
255            case TypeId::Or:
256                expr = block.createOr(e1, e2); break;
257            case TypeId::Xor:
258                expr = block.createXor(e1, e2); break;
259            default: break;
260        }
261        Q.push_back(expr);
262    }
263    PabloAST * const result = Q.front();
264    assert (result);
265    getValue(G[u]) = result;
266    return result;
267}
268
269/** ------------------------------------------------------------------------------------------------------------- *
270 * @brief processScope
271 ** ------------------------------------------------------------------------------------------------------------- */
272inline void BooleanReassociationPass::processScope(PabloFunction &, PabloBlock & block) {
273    Graph G;
274    Map M;
275    summarizeAST(block, G, M);
276    redistributeAST(block, G, M);
277    rewriteAST(block, G);
278}
279
280/** ------------------------------------------------------------------------------------------------------------- *
281 * @brief rewriteAST
282 ** ------------------------------------------------------------------------------------------------------------- */
283void BooleanReassociationPass::rewriteAST(PabloBlock & block, Graph & G) {
284    // Rewrite the AST in accordance to G
285    circular_buffer<Vertex> Q(num_vertices(G));
286    topological_sort(G, std::back_inserter(Q));
287
288    block.setInsertPoint(nullptr);
289    unsigned statementCount = 0;
290    WrittenAt writtenAt;
291    writtenAt.emplace(PabloBlock::createZeroes(), 0);
292    writtenAt.emplace(PabloBlock::createOnes(), 0);
293    while (!Q.empty()) {
294        const Vertex u = Q.back();
295        Q.pop_back();
296        // Supress any isolated vertices
297        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
298            continue;
299        }
300        unsigned statementIndex = 0;
301        PabloAST * expr = getValue(G[u]);
302        if (LLVM_LIKELY(isMutable(G[u], block))) {
303            Statement * stmt = nullptr;
304            if (isAssociative(G[u])) {
305                PabloAST * replacement = createTree(block, u, G, writtenAt);
306                if (LLVM_LIKELY(inCurrentBlock(replacement, block))) {
307                    stmt = cast<Statement>(replacement);
308                } else { // optimization reduced this to a Constant, Var or a prior-scope statement
309                    getType(G[u]) = TypeId::Var;
310                    continue;
311                }
312            } else { // update any potential mappings
313                stmt = cast<Statement>(getValue(G[u]));
314            }
315            assert (stmt);
316            for (auto e : make_iterator_range(out_edges(u, G))) {
317                if (G[e] && G[e] != stmt) {
318                    PabloAST * expr = getValue(G[target(e, G)]);
319                    if (expr) { // processing a yet-to-be created value
320                        cast<Statement>(expr)->replaceUsesOfWith(G[e], stmt);
321                    }
322                }
323            }
324            // make sure that optimization doesn't reduce this to an already written statement
325            if (writtenAt.count(stmt)) {
326                continue;
327            }
328            block.insert(stmt);
329            statementIndex = ++statementCount;
330            expr = stmt;
331        }
332        writtenAt.emplace(expr, statementIndex);
333    }
334}
335
336/** ------------------------------------------------------------------------------------------------------------- *
337 * @brief summarizeAST
338 *
339 * This function scans through a scope blockand computes a DAG G in which any sequences of AND, OR or XOR functions
340 * are "flattened" (i.e., allowed to have any number of inputs.)
341 ** ------------------------------------------------------------------------------------------------------------- */
342void BooleanReassociationPass::summarizeAST(PabloBlock & block, Graph & G, Map & M) const {
343    // Compute the base def-use graph ...
344    for (Statement * stmt : block) {
345        const Vertex u = getSummaryVertex(stmt, G, M, block);
346        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
347            PabloAST * const op = stmt->getOperand(i);
348            if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
349                continue;
350            }
351            const Vertex v = getSummaryVertex(op, G, M, block);
352            add_edge(op, v, u, G);
353            // If this operand is a Not operation that is not in this PabloBlock,
354            // pull its input operand in. It may lead to future optimizations.
355            if (LLVM_UNLIKELY(isa<Not>(op) && !inCurrentBlock(cast<Not>(op), block))) {
356                PabloAST * const negatedValue = cast<Not>(op)->getExpr();
357                add_edge(negatedValue, getSummaryVertex(negatedValue, G, M, block), v, G);
358            }
359        }
360        if (isa<If>(stmt)) {
361            for (Assign * def : cast<const If>(stmt)->getDefined()) {
362                const Vertex v = getSummaryVertex(def, G, M, block);
363                add_edge(def, u, v, G);
364                resolveUsages(v, def, block, G, M, stmt);
365            }
366        } else if (isa<While>(stmt)) {
367            // To keep G a DAG, we need to do a bit of surgery on loop variants because
368            // the next variables it produces can be used within the condition. Instead,
369            // we make the loop dependent on the original value of each Next node and
370            // the Next node dependent on the loop.
371            for (Next * var : cast<const While>(stmt)->getVariants()) {
372                const Vertex v = getSummaryVertex(var, G, M, block);
373                assert (in_degree(v, G) == 1);
374                add_edge(nullptr, source(first(in_edges(v, G)), G), u, G);
375                remove_edge(v, u, G);
376                add_edge(var, u, v, G);
377                resolveUsages(v, var, block, G, M, stmt);
378            }
379        } else {
380            resolveUsages(u, stmt, block, G, M);
381        }
382    }
383    std::vector<Vertex> mapping(num_vertices(G));
384    summarizeGraph(block, G, mapping, M);
385}
386
387/** ------------------------------------------------------------------------------------------------------------- *
388 * @brief resolveUsages
389 ** ------------------------------------------------------------------------------------------------------------- */
390void BooleanReassociationPass::resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, const Statement * const ignoreIfThis) const {
391    for (PabloAST * user : expr->users()) {
392        assert (user);
393        if (LLVM_LIKELY(user != expr && isa<Statement>(user))) {
394            PabloBlock * parent = cast<Statement>(user)->getParent();
395            assert (parent);
396            if (LLVM_UNLIKELY(parent != &block)) {
397                for (;;) {
398                    if (LLVM_UNLIKELY(parent == nullptr)) {
399                        assert (isa<Assign>(expr) || isa<Next>(expr));
400                        break;
401                    } else if (parent->getParent() == &block) {
402                        const auto f = mResolvedScopes.find(parent);
403                        if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
404                            throw std::runtime_error("Failed to resolve scope block!");
405                        }
406                        Statement * const branch = f->second;
407                        if (LLVM_UNLIKELY(branch == ignoreIfThis)) {
408                            break;
409                        }
410                        // Add in a Var denoting the user of this expression so that it can be updated if expr changes.
411                        const Vertex v = getSummaryVertex(user, G, M, block);
412                        add_edge(expr, u, v, G);
413
414                        const Vertex w = getSummaryVertex(branch, G, M, block);
415                        add_edge(nullptr, v, w, G);
416                        break;
417                    }
418                    parent = parent->getParent();
419                }
420            }
421        }
422    }
423}
424
425/** ------------------------------------------------------------------------------------------------------------- *
426 * @brief summarizeGraph
427 ** ------------------------------------------------------------------------------------------------------------- */
428inline void BooleanReassociationPass::summarizeGraph(const PabloBlock &, Graph & G, std::vector<Vertex> & mapping, Map &) {
429    std::vector<Vertex> reverse_topological_ordering;
430    reverse_topological_ordering.reserve(num_vertices(G));
431
432    topological_sort(G, std::back_inserter(reverse_topological_ordering));
433    assert(mapping.size() >= num_vertices(G));
434    for (const Vertex u : reverse_topological_ordering) {       
435        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
436            continue;
437        } else if (LLVM_LIKELY(out_degree(u, G) > 0)) {
438            if (isAssociative(G[u])) {
439                if (LLVM_UNLIKELY(in_degree(u, G) == 1)) {
440                    // We have a redundant node here that'll simply end up being a duplicate
441                    // of the input value. Remove it and add any of its outgoing edges to its
442                    // input node.
443                    const auto ei = first(in_edges(u, G));
444                    const Vertex v = source(ei, G);
445                    for (auto ej : make_iterator_range(out_edges(u, G))) {
446                        const Vertex w = target(ej, G);
447                        add_edge(G[ei], v, w, G);
448                        if (mapping[w] == mapping[u]) {
449                            mapping[w] = v;
450                        }
451                    }
452                    mapping[u] = v;
453                    clear_vertex(u, G);                   
454                    getType(G[u]) = TypeId::Var;
455                    getValue(G[u]) = nullptr;
456                    continue;
457                } else if (LLVM_UNLIKELY(out_degree(u, G) == 1)) {
458                    // Otherwise if we have a single user, we have a similar case as above but
459                    // we can only merge this vertex into the outgoing instruction if they are
460                    // of the same type.
461                    const auto ei = first(out_edges(u, G));
462                    const Vertex v = target(ei, G);
463                    if (LLVM_UNLIKELY(isSameType(G[v], G[u]))) {
464                        for (auto ej : make_iterator_range(in_edges(u, G))) {
465                            add_edge(G[ei], source(ej, G), v, G);
466                        }
467                        mapping[u] = v;
468                        clear_vertex(u, G);
469                        getType(G[u]) = TypeId::Var;
470                        getValue(G[u]) = nullptr;
471                        continue;
472                    }
473                }
474            }
475        } else if (isNonEscaping(G[u])) {
476            clear_in_edges(u, G);
477            getType(G[u]) = TypeId::Var;
478            getValue(G[u]) = nullptr;
479            continue;
480        }
481    }   
482}
483
484/** ------------------------------------------------------------------------------------------------------------- *
485 * @brief enumerateBicliques
486 *
487 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
488 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies in set A to be in
489 * bipartition A and their adjacencies to be in B.
490  ** ------------------------------------------------------------------------------------------------------------- */
491template <class Graph>
492static BicliqueSet enumerateBicliques(const Graph & G, const VertexSet & A) {
493    using IntersectionSets = std::set<VertexSet>;
494
495    IntersectionSets B1;
496    for (auto u : A) {
497        if (in_degree(u, G) > 0) {
498            VertexSet incomingAdjacencies;
499            incomingAdjacencies.reserve(in_degree(u, G));
500            for (auto e : make_iterator_range(in_edges(u, G))) {
501                incomingAdjacencies.push_back(source(e, G));
502            }
503            std::sort(incomingAdjacencies.begin(), incomingAdjacencies.end());
504            B1.insert(std::move(incomingAdjacencies));
505        }
506    }
507
508    IntersectionSets B(B1);
509
510    IntersectionSets Bi;
511
512    VertexSet clique;
513    for (auto i = B1.begin(); i != B1.end(); ++i) {
514        for (auto j = i; ++j != B1.end(); ) {
515            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
516            if (clique.size() > 0) {
517                if (B.count(clique) == 0) {
518                    Bi.insert(clique);
519                }
520                clique.clear();
521            }
522        }
523    }
524
525    for (;;) {
526        if (Bi.empty()) {
527            break;
528        }
529        B.insert(Bi.begin(), Bi.end());
530        IntersectionSets Bk;
531        for (auto i = B1.begin(); i != B1.end(); ++i) {
532            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
533                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
534                if (clique.size() > 0) {
535                    if (B.count(clique) == 0) {
536                        Bk.insert(clique);
537                    }
538                    clique.clear();
539                }
540            }
541        }
542        Bi.swap(Bk);
543    }
544
545    BicliqueSet cliques;
546    cliques.reserve(B.size());
547    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
548        VertexSet Ai(A);
549        for (const Vertex u : *Bi) {                                   
550            VertexSet Aj;
551            Aj.reserve(out_degree(u, G));
552            for (auto e : make_iterator_range(out_edges(u, G))) {
553                Aj.push_back(target(e, G));
554            }
555            std::sort(Aj.begin(), Aj.end());
556            VertexSet Ak;
557            Ak.reserve(std::min(Ai.size(), Aj.size()));
558            std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
559            Ai.swap(Ak);
560        }
561        assert (Ai.size() > 0); // cannot happen if this algorithm is working correctly
562        cliques.emplace_back(std::move(Ai), std::move(*Bi));
563    }
564    return std::move(cliques);
565}
566
567/** ------------------------------------------------------------------------------------------------------------- *
568 * @brief independentCliqueSets
569 ** ------------------------------------------------------------------------------------------------------------- */
570template <unsigned side>
571inline static BicliqueSet && independentCliqueSets(BicliqueSet && cliques, const unsigned minimum) {
572    using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
573
574    const auto l = cliques.size();
575    IndependentSetGraph I(l);
576
577    // Initialize our weights
578    for (unsigned i = 0; i != l; ++i) {
579        I[i] = std::pow(std::get<side>(cliques[i]).size(), 2);
580    }
581
582    // Determine our constraints
583    for (unsigned i = 0; i != l; ++i) {
584        for (unsigned j = i + 1; j != l; ++j) {
585            if (intersects(std::get<side>(cliques[i]), std::get<side>(cliques[j]))) {
586                add_edge(i, j, I);
587            }
588        }
589    }
590
591    // Use the greedy algorithm to choose our independent set
592    VertexSet selected;
593    for (;;) {
594        unsigned w = 0;
595        Vertex u = 0;
596        for (unsigned i = 0; i != l; ++i) {
597            if (I[i] > w) {
598                w = I[i];
599                u = i;
600            }
601        }
602        if (w < minimum) break;
603        selected.push_back(u);
604        I[u] = 0;
605        for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
606            I[v] = 0;
607        }
608    }
609
610    // Sort the selected list and then remove the unselected cliques
611    std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
612    auto end = cliques.end();
613    for (const unsigned offset : selected) {
614        end = cliques.erase(cliques.begin() + offset + 1, end) - 1;
615    }
616    cliques.erase(cliques.begin(), end);
617
618    return std::move(cliques);
619}
620
621/** ------------------------------------------------------------------------------------------------------------- *
622 * @brief removeUnhelpfulBicliques
623 *
624 * An intermediary vertex could have more than one outgoing edge but if any that are not directed to vertices in
625 * the lower biclique, we'll need to compute that specific value anyway. Remove them from the clique set and if
626 * there are not enough vertices in the biclique to make distribution profitable, eliminate the clique.
627 ** ------------------------------------------------------------------------------------------------------------- */
628static BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques, const Graph & G, DistributionGraph & H) {
629    for (auto ci = cliques.begin(); ci != cliques.end(); ) {
630        const auto cardinalityA = std::get<0>(*ci).size();
631        VertexSet & B = std::get<1>(*ci);
632        for (auto bi = B.begin(); bi != B.end(); ) {
633            if (out_degree(H[*bi], G) == cardinalityA) {
634                ++bi;
635            } else {
636                bi = B.erase(bi);
637            }
638        }
639        if (B.size() > 1) {
640            ++ci;
641        } else {
642            ci = cliques.erase(ci);
643        }
644    }
645    return std::move(cliques);
646}
647
648/** ------------------------------------------------------------------------------------------------------------- *
649 * @brief safeDistributionSets
650 ** ------------------------------------------------------------------------------------------------------------- */
651static DistributionSets safeDistributionSets(const Graph & G, DistributionGraph & H) {
652
653    VertexSet sinks;
654    for (const Vertex u : make_iterator_range(vertices(H))) {
655        if (out_degree(u, H) == 0 && in_degree(u, G) != 0) {
656            sinks.push_back(u);
657        }
658    }
659    std::sort(sinks.begin(), sinks.end());
660
661    DistributionSets T;
662    BicliqueSet lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(H, sinks), G, H), 1);
663    for (Biclique & lower : lowerSet) {
664        BicliqueSet upperSet = independentCliqueSets<0>(enumerateBicliques(H, std::get<1>(lower)), 2);
665        for (Biclique & upper : upperSet) {
666            T.emplace_back(std::move(std::get<1>(upper)), std::move(std::get<0>(upper)), std::get<0>(lower));
667        }
668    }
669    return std::move(T);
670}
671
672/** ------------------------------------------------------------------------------------------------------------- *
673 * @brief generateDistributionGraph
674 ** ------------------------------------------------------------------------------------------------------------- */
675void generateDistributionGraph(const Graph & G, DistributionGraph & H) {
676    DistributionMap M;
677    for (const Vertex u : make_iterator_range(vertices(G))) {
678        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
679            continue;
680        } else if (isDistributive(G[u])) {
681            const TypeId outerTypeId = getType(G[u]);
682            const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
683            flat_set<Vertex> distributable;
684            for (auto e : make_iterator_range(in_edges(u, G))) {
685                const Vertex v = source(e, G);
686                if (LLVM_UNLIKELY(getType(G[v]) == innerTypeId)) {
687                    bool safe = true;
688                    for (const auto e : make_iterator_range(out_edges(v, G))) {
689                        if (getType(G[target(e, G)]) != outerTypeId) {
690                            safe = false;
691                            break;
692                        }
693                    }
694                    if (safe) {
695                        distributable.insert(v);
696                    }
697                }
698            }
699            if (LLVM_LIKELY(distributable.size() > 1)) {
700                // We're only interested in computing a subgraph of G in which every source has an out-degree
701                // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical
702                // benefit. (Note: this does not consider register pressure / liveness.)
703                flat_map<Vertex, bool> observedMoreThanOnce;
704                bool anyOpportunities = false;
705                for (const Vertex v : distributable) {
706                    for (auto e : make_iterator_range(in_edges(v, G))) {
707                        const Vertex w = source(e, G);
708                        auto ob = observedMoreThanOnce.find(w);
709                        if (ob == observedMoreThanOnce.end()) {
710                            observedMoreThanOnce.emplace(w, false);
711                        } else {
712                            ob->second = true;
713                            anyOpportunities = true;
714                        }
715                    }
716                }
717                if (anyOpportunities) {
718                    for (const auto ob : observedMoreThanOnce) {
719                        if (std::get<1>(ob)) {
720                            const Vertex w = std::get<0>(ob);
721                            for (auto e : make_iterator_range(out_edges(w, G))) {
722                                const Vertex v = target(e, G);
723                                if (distributable.count(v)) {
724                                    const Vertex y = getVertex(v, H, M);
725                                    add_edge(y, getVertex(u, H, M), H);
726                                    add_edge(getVertex(w, H, M), y, H);
727                                }
728                            }
729                        }
730                    }
731                }
732            }
733        }
734    }
735}
736
737/** ------------------------------------------------------------------------------------------------------------- *
738 * @brief redistributeAST
739 *
740 * Apply the distribution law to reduce computations whenever possible.
741 ** ------------------------------------------------------------------------------------------------------------- */
742void BooleanReassociationPass::redistributeAST(const PabloBlock & block, Graph & G, Map & M) const {
743
744    std::vector<Vertex> mapping(num_vertices(G) + 16);
745    std::iota(mapping.begin(), mapping.end(), 0); // 0,1,.....n
746
747    for (;;) {
748
749        DistributionGraph H;
750
751        generateDistributionGraph(G, H);
752
753        // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
754        if (num_vertices(H) == 0) {
755            break;
756        }
757
758        const DistributionSets distributionSets = safeDistributionSets(G, H);
759
760        if (LLVM_UNLIKELY(distributionSets.empty())) {
761            break;
762        }
763
764        for (const DistributionSet & set : distributionSets) {
765
766            // Each distribution tuple consists of the sources, intermediary, and sink nodes.
767            const VertexSet & sources = std::get<0>(set);
768            const VertexSet & intermediary = std::get<1>(set);
769            const VertexSet & sinks = std::get<2>(set);
770
771            const TypeId outerTypeId = getType(G[mapping[H[sinks.front()]]]);
772            assert (outerTypeId == TypeId::And || outerTypeId == TypeId::Or);
773            const TypeId innerTypeId = (outerTypeId == TypeId::Or) ? TypeId::And : TypeId::Or;
774
775            // Update G to match the desired change
776            const Vertex x = addSummaryVertex(outerTypeId, G);
777            const Vertex y = addSummaryVertex(innerTypeId, G);
778            mapping.resize(num_vertices(G));
779            mapping[x] = x;
780            mapping[y] = y;
781
782            for (const Vertex i : intermediary) {
783                const auto u = mapping[H[i]];
784                assert (getType(G[u]) == innerTypeId);
785                for (const Vertex t : sinks) {
786                    assert (getType(G[mapping[H[t]]]) == outerTypeId);
787                    remove_edge(u, mapping[H[t]], G);
788                }
789                add_edge(nullptr, u, x, G);
790            }           
791
792            for (const Vertex s : sources) {
793                const auto u = mapping[H[s]];
794                for (const Vertex i : intermediary) {
795                    remove_edge(u, mapping[H[i]], G);
796                }
797                add_edge(nullptr, u, y, G);
798            }
799            add_edge(nullptr, x, y, G);
800
801            for (const Vertex t : sinks) {
802                const auto v = mapping[H[t]];
803                add_edge(getValue(G[v]), y, v, G);
804            }
805
806            summarizeGraph(block, G, mapping, M);
807        }
808    }
809}
810
811/** ------------------------------------------------------------------------------------------------------------- *
812 * @brief addSummaryVertex
813 ** ------------------------------------------------------------------------------------------------------------- */
814inline Vertex BooleanReassociationPass::addSummaryVertex(const TypeId typeId, Graph & G) {
815    return add_vertex(std::make_pair(typeId, nullptr), G);
816}
817
818/** ------------------------------------------------------------------------------------------------------------- *
819 * @brief getVertex
820 ** ------------------------------------------------------------------------------------------------------------- */
821Vertex BooleanReassociationPass::getSummaryVertex(PabloAST * expr, Graph & G, Map & M, const PabloBlock & block) {
822    const auto f = M.find(expr);
823    if (f != M.end()) {
824        return f->second;
825    }
826    // To simplify future analysis, every statement not in the current block will be recorded as a Var.
827    const TypeId typeId = inCurrentBlock(expr, block) ? expr->getClassTypeId() : TypeId::Var;
828    const auto u = add_vertex(std::make_pair(typeId, expr), G);
829    M.insert(std::make_pair(expr, u));
830    return u;
831}
832
833}
Note: See TracBrowser for help on using the repository browser.