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

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

More work on n-ary operations.

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