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

Last change on this file since 4860 was 4860, checked in by nmedfort, 3 years ago

Back up check in. Memory leaks should be fixed.

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