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

Last change on this file since 4778 was 4778, checked in by cameron, 4 years ago

Hongpu's option to use Boost mmap; fix an include for std::iota

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