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

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

Progress on multi-target UCD compiler.

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