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

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

Progress on reassociation pass

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