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

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

Bug fix for Multiplexing. Added ability to set the body of a If/While? node after creation.

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