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

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

Bug fixes for statement scheduling in reassociation pass.

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