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

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

Bug fixes

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