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

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

More work on reassociation + distribution pass

File size: 41.9 KB
Line 
1#include "booleanreassociationpass.h"
2#include <boost/container/flat_set.hpp>
3#include <boost/container/flat_map.hpp>
4#include <boost/circular_buffer.hpp>
5#include <boost/graph/adjacency_list.hpp>
6#include <boost/graph/filtered_graph.hpp>
7#include <boost/graph/topological_sort.hpp>
8#include <pablo/optimizers/pablo_simplifier.hpp>
9#include <algorithm>
10#include <queue>
11#include <set>
12#include <iostream>
13#include <pablo/printer_pablos.h>
14#include "graph-facade.hpp"
15
16using namespace boost;
17using namespace boost::container;
18
19namespace pablo {
20
21using Graph = BooleanReassociationPass::Graph;
22using Vertex = Graph::vertex_descriptor;
23using VertexQueue = circular_buffer<Vertex>;
24using Map = BooleanReassociationPass::Map;
25using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
26
27/** ------------------------------------------------------------------------------------------------------------- *
28 * @brief optimize
29 ** ------------------------------------------------------------------------------------------------------------- */
30bool BooleanReassociationPass::optimize(PabloFunction & function) {
31    BooleanReassociationPass brp;
32    brp.resolveScopes(function);
33    brp.processScopes(function);
34    Simplifier::optimize(function);
35    return true;
36}
37
38/** ------------------------------------------------------------------------------------------------------------- *
39 * @brief resolveScopes
40 ** ------------------------------------------------------------------------------------------------------------- */
41inline void BooleanReassociationPass::resolveScopes(PabloFunction &function) {
42    resolveScopes(function.getEntryBlock());
43}
44
45/** ------------------------------------------------------------------------------------------------------------- *
46 * @brief resolveScopes
47 ** ------------------------------------------------------------------------------------------------------------- */
48void BooleanReassociationPass::resolveScopes(PabloBlock & block) {
49    for (Statement * stmt : block) {
50        if (isa<If>(stmt) || isa<While>(stmt)) {
51            PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
52            mResolvedScopes.emplace(&nested, stmt);
53            resolveScopes(nested);
54        }
55    }
56}
57
58
59/** ------------------------------------------------------------------------------------------------------------- *
60 * @brief scan
61 ** ------------------------------------------------------------------------------------------------------------- */
62inline void BooleanReassociationPass::processScopes(PabloFunction & function) {
63    std::vector<Statement *> terminals;
64    for (unsigned i = 0; i != function.getNumOfResults(); ++i) {
65        terminals.push_back(function.getResult(i));
66    }
67    processScopes(function.getEntryBlock(), std::move(terminals));
68}
69
70/** ------------------------------------------------------------------------------------------------------------- *
71 * @brief scan
72 ** ------------------------------------------------------------------------------------------------------------- */
73void BooleanReassociationPass::processScopes(PabloBlock & block, std::vector<Statement *> && terminals) {
74    processScope(block, std::move(terminals));
75    for (Statement * stmt : block) {
76        if (isa<If>(stmt)) {
77            const auto & defs = cast<const If>(stmt)->getDefined();
78            std::vector<Statement *> terminals(defs.begin(), defs.end());
79            processScopes(cast<If>(stmt)->getBody(), std::move(terminals));
80        } else if (isa<While>(stmt)) {
81            const auto & vars = cast<const While>(stmt)->getVariants();
82            std::vector<Statement *> terminals(vars.begin(), vars.end());
83            processScopes(cast<While>(stmt)->getBody(), std::move(terminals));
84        }
85    }
86}
87
88/** ------------------------------------------------------------------------------------------------------------- *
89 * @brief is_power_of_2
90 * @param n an integer
91 ** ------------------------------------------------------------------------------------------------------------- */
92static inline bool is_power_of_2(const size_t n) {
93    return ((n & (n - 1)) == 0);
94}
95
96/** ------------------------------------------------------------------------------------------------------------- *
97 * @brief log2_plus_one
98 ** ------------------------------------------------------------------------------------------------------------- */
99static inline size_t ceil_log2(const size_t n) {
100    return std::log2<size_t>(n) + (is_power_of_2(n) ? 0 : 1);
101}
102
103/** ------------------------------------------------------------------------------------------------------------- *
104 * @brief isOptimizable
105 *
106 * And, Or and Xor instructions are all associative, commutative and distributive operations. Thus we can
107 * safely rearrange expressions such as "((((a √ b) √ c) √ d) √ e) √ f" into "((a √ b) √ (c √ d)) √ (e √ f)".
108 ** ------------------------------------------------------------------------------------------------------------- */
109static inline bool isOptimizable(const PabloAST * const expr) {
110    assert (expr);
111    switch (expr->getClassTypeId()) {
112        case PabloAST::ClassTypeId::And:
113        case PabloAST::ClassTypeId::Or:
114        case PabloAST::ClassTypeId::Xor:
115            return true;
116        default:
117            return false;
118    }
119}
120
121/** ------------------------------------------------------------------------------------------------------------- *
122 * @brief inCurrentBlock
123 ** ------------------------------------------------------------------------------------------------------------- */
124static inline bool inCurrentBlock(const Statement * stmt, const PabloBlock & block) {
125    return stmt->getParent() == &block;
126}
127
128static inline bool inCurrentBlock(const PabloAST * expr, const PabloBlock & block) {
129    return isa<Statement>(expr) && inCurrentBlock(cast<Statement>(expr), block);
130}
131
132/** ------------------------------------------------------------------------------------------------------------- *
133 * @brief isCutNecessary
134 ** ------------------------------------------------------------------------------------------------------------- */
135static inline bool isCutNecessary(const Vertex u, const Vertex v, const Graph & G, const std::vector<unsigned> & component) {
136    // Either this edge crosses a component boundary or the operations performed by the vertices differs, we need to cut
137    // the graph here and generate two partial equations.
138    if (LLVM_UNLIKELY(component[u] != component[v])) {
139        return true;
140    } else if (LLVM_UNLIKELY((in_degree(u, G) != 0) && (G[u]->getClassTypeId() != G[v]->getClassTypeId()))) {
141        return true;
142    }
143    return false;
144}
145
146/** ------------------------------------------------------------------------------------------------------------- *
147 * @brief push
148 ** ------------------------------------------------------------------------------------------------------------- */
149static inline void push(const Vertex u, VertexQueue & Q) {
150    if (LLVM_UNLIKELY(Q.full())) {
151        Q.set_capacity(Q.capacity() * 2);
152    }
153    Q.push_back(u);
154    assert (Q.back() == u);
155}
156
157/** ------------------------------------------------------------------------------------------------------------- *
158 * @brief pop
159 ** ------------------------------------------------------------------------------------------------------------- */
160static inline Vertex pop(VertexQueue & Q) {
161    assert (!Q.empty() && "Popping an empty vertex queue");
162    const Vertex u = Q.front();
163    Q.pop_front();
164    return u;
165}
166
167/** ------------------------------------------------------------------------------------------------------------- *
168 * @brief getVertex
169 ** ------------------------------------------------------------------------------------------------------------- */
170template<typename ValueType, typename GraphType, typename MapType>
171static inline Vertex getVertex(ValueType value, GraphType & G, MapType & M) {
172    const auto f = M.find(value);
173    if (f != M.end()) {
174        return f->second;
175    }
176    const auto u = add_vertex(value, G);
177    M.insert(std::make_pair(value, u));
178    return u;
179}
180
181/** ------------------------------------------------------------------------------------------------------------- *
182 * @brief createTree
183 ** ------------------------------------------------------------------------------------------------------------- */
184static PabloAST * createTree(PabloBlock & block, const PabloAST::ClassTypeId typeId, circular_buffer<PabloAST *> & Q) {
185    while (Q.size() > 1) {
186        PabloAST * e1 = Q.front(); Q.pop_front();
187        PabloAST * e2 = Q.front(); Q.pop_front();
188        PabloAST * expr = nullptr;
189        // Note: this switch ought to compile to an array of function pointers to the appropriate method.
190        switch (typeId) {
191            case PabloAST::ClassTypeId::And:
192                expr = block.createAnd(e1, e2); break;
193            case PabloAST::ClassTypeId::Or:
194                expr = block.createOr(e1, e2); break;
195            case PabloAST::ClassTypeId::Xor:
196                expr = block.createXor(e1, e2); break;
197            default: break;
198        }
199        Q.push_back(expr);
200    }
201    PabloAST * r = Q.front();
202    Q.clear();
203    return r;
204}
205
206/** ------------------------------------------------------------------------------------------------------------- *
207 * @brief printGraph
208 ** ------------------------------------------------------------------------------------------------------------- */
209static void printGraph(PabloBlock & block, const Graph & G, const std::string name) {
210    raw_os_ostream out(std::cerr);
211    out << "digraph " << name << " {\n";
212    for (auto u : make_iterator_range(vertices(G))) {
213        out << "v" << u << " [label=\"";
214        PabloAST * expr = G[u];
215        if (isa<Statement>(expr)) {
216            if (LLVM_UNLIKELY(isa<If>(expr))) {
217                out << "If ";
218                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
219                out << ":";
220            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
221                out << "While ";
222                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
223                out << ":";
224            } else {
225                PabloPrinter::print(cast<Statement>(expr), "", out);
226            }
227        } else {
228            PabloPrinter::print(expr, out);
229        }
230        out << "\"";
231        if (!inCurrentBlock(expr, block)) {
232            out << " style=dashed";
233        }
234        out << "];\n";
235    }
236    for (auto e : make_iterator_range(edges(G))) {
237        out << "v" << source(e, G) << " -> v" << target(e, G) << ";\n";
238    }
239
240    if (num_vertices(G) > 0) {
241
242        out << "{ rank=same;";
243        for (auto u : make_iterator_range(vertices(G))) {
244            if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
245                out << " v" << u;
246            }
247        }
248        out << "}\n";
249
250        out << "{ rank=same;";
251        for (auto u : make_iterator_range(vertices(G))) {
252            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
253                out << " v" << u;
254            }
255        }
256        out << "}\n";
257
258    }
259
260    out << "}\n\n";
261    out.flush();
262}
263
264/** ------------------------------------------------------------------------------------------------------------- *
265 * @brief printGraph
266 ** ------------------------------------------------------------------------------------------------------------- */
267template<typename SubgraphType>
268static void printGraph(PabloBlock & block, const SubgraphType & S, const Graph & G, const std::string name) {
269    raw_os_ostream out(std::cerr);
270    out << "digraph " << name << " {\n";
271    for (auto u : make_iterator_range(vertices(S))) {
272        if (in_degree(u, S) == 0 && out_degree(u, S) == 0) {
273            continue;
274        }
275        out << "v" << u << " [label=\"";
276        PabloAST * expr = G[S[u]];
277        if (isa<Statement>(expr)) {
278            if (LLVM_UNLIKELY(isa<If>(expr))) {
279                out << "If ";
280                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
281                out << ":";
282            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
283                out << "While ";
284                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
285                out << ":";
286            } else {
287                PabloPrinter::print(cast<Statement>(expr), "", out);
288            }
289        } else {
290            PabloPrinter::print(expr, out);
291        }
292        out << "\"";
293        if (!inCurrentBlock(expr, block)) {
294            out << " style=dashed";
295        }
296        out << "];\n";
297    }
298    for (auto e : make_iterator_range(edges(S))) {
299        out << "v" << source(e, S) << " -> v" << target(e, S) << ";\n";
300    }
301
302    if (num_vertices(S) > 0) {
303
304        out << "{ rank=same;";
305        for (auto u : make_iterator_range(vertices(S))) {
306            if (in_degree(u, S) == 0 && out_degree(u, S) != 0) {
307                out << " v" << u;
308            }
309        }
310        out << "}\n";
311
312        out << "{ rank=same;";
313        for (auto u : make_iterator_range(vertices(S))) {
314            if (out_degree(u, S) == 0 && in_degree(u, S) != 0) {
315                out << " v" << u;
316            }
317        }
318        out << "}\n";
319
320    }
321
322    out << "}\n\n";
323    out.flush();
324}
325
326/** ------------------------------------------------------------------------------------------------------------- *
327 * @brief processScope
328 ** ------------------------------------------------------------------------------------------------------------- */
329void BooleanReassociationPass::processScope(PabloBlock & block, std::vector<Statement *> && terminals) {
330
331    Graph G;
332
333    summarizeAST(block, terminals, G);
334    printGraph(block, G, "G");
335    if (redistributeAST(block, G)) {
336        printGraph(block, G, "H");
337    }
338}
339
340/** ------------------------------------------------------------------------------------------------------------- *
341 * @brief summarizeAST
342 *
343 * This function scans through a basic block (starting by its terminals) and computes a DAG in which any sequences
344 * of AND, OR or XOR functions are "flattened" (i.e., allowed to have any number of inputs.) This allows us to
345 * reassociate them in the most efficient way possible.
346 ** ------------------------------------------------------------------------------------------------------------- */
347void BooleanReassociationPass::summarizeAST(PabloBlock & block, std::vector<Statement *> terminals, Graph & G) const {
348
349    VertexQueue Q(128);
350    EdgeQueue E;
351    Map M;
352
353    for (;;) {
354
355        Graph Gk;
356        Map Mk;
357
358        // Generate a graph depicting the relationships between the terminals. If the original terminals
359        // cannot be optimized with this algorithm bypass them in favour of their operands. If those cannot
360        // be optimized, they'll be left as the initial terminals for the next "layer" of the AST.
361
362        for (Statement * term : terminals) {
363            if (LLVM_LIKELY(Mk.count(term) == 0)) {
364                // add or find this terminal in our global graph
365                Vertex x = getVertex(term, G, M);
366                if (inCurrentBlock(term, block)) {
367                    if (isOptimizable(term)) {
368                        const Vertex u = add_vertex(term, Gk);
369                        Mk.insert(std::make_pair(term, u));
370                        push(u, Q);
371                        continue;
372                    }
373                } else if (isa<Assign>(term) || isa<Next>(term)) {
374                    // If this is an Assign (Next) node whose operand does not originate from the current block
375                    // then check to see if there is an If (While) node that does.
376                    Statement * branch = nullptr;
377                    if (isa<Assign>(term)) {
378                        for (PabloAST * user : term->users()) {
379                            if (isa<If>(user)) {
380                                const If * ifNode = cast<If>(user);
381                                if (inCurrentBlock(ifNode, block)) {
382                                    const auto & defs = ifNode->getDefined();
383                                    if (LLVM_LIKELY(std::find(defs.begin(), defs.end(), cast<Assign>(term)) != defs.end())) {
384                                        branch = cast<Statement>(user);
385                                        break;
386                                    }
387                                }
388                            }
389                        }
390                    } else { // if (isa<Next>(term))
391                        for (PabloAST * user : term->users()) {
392                            if (isa<While>(user)) {
393                                const While * whileNode = cast<While>(user);
394                                if (inCurrentBlock(whileNode, block)) {
395                                    const auto & vars = whileNode->getVariants();
396                                    if (LLVM_LIKELY(std::find(vars.begin(), vars.end(), cast<Next>(term)) != vars.end())) {
397                                        branch = cast<Statement>(user);
398                                        break;
399                                    }
400                                }
401                            }
402                        }
403                    }
404
405                    // If we didn't find a branch, then the Assign (Next) node must have come from a preceeding
406                    // block. Just skip it for now.
407                    if (branch == nullptr) {
408                        continue;
409                    }
410
411                    // Otherwise add the branch to G and test its operands rather than the original terminal
412                    const Vertex z = getVertex(branch, G, M);
413                    add_edge(z, x, G);
414                    x = z;
415                    term = branch;
416                }
417
418                for (unsigned i = 0; i != term->getNumOperands(); ++i) {
419                    PabloAST * const op = term->getOperand(i);
420                    if (LLVM_LIKELY(inCurrentBlock(op, block))) {
421                        const Vertex y = getVertex(op, G, M);
422                        add_edge(y, x, G);
423                        if (LLVM_LIKELY(Mk.count(op) == 0)) {
424                            const Vertex v = add_vertex(op, Gk);
425                            Mk.insert(std::make_pair(op, v));
426                            push(v, Q);
427                        }
428                    }
429                }
430            }
431        }
432
433        if (LLVM_UNLIKELY(Q.empty())) {
434            break;
435        }
436
437        for (;;) {
438            const Vertex u = pop(Q);
439            if (isOptimizable(Gk[u])) {
440                Statement * stmt = cast<Statement>(Gk[u]);
441                // If any user of this statement is not in the current block, determine the outermost If/While node
442                // that contains this statement within and add an edge from this statement to it to denote both the
443                // topological ordering necessary and that this statement must be computed.
444                for (PabloAST * user : stmt->users()) {
445                    if (LLVM_LIKELY(isa<Statement>(user))) {
446                        PabloBlock * parent = cast<Statement>(user)->getParent();
447                        if (LLVM_UNLIKELY(parent != &block)) {
448                            while (parent->getParent() != &block) {
449                                parent = parent->getParent();
450                            }
451                            if (LLVM_UNLIKELY(parent == nullptr)) {
452                                throw std::runtime_error("Could not locate nested scope block!");
453                            }
454                            const auto f = mResolvedScopes.find(parent);
455                            if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
456                                throw std::runtime_error("Failed to resolve scope block!");
457                            }
458                            add_edge(u, getVertex(f->second, Gk, Mk), Gk);
459                        }
460                    }
461                }
462                // Scan through the use-def chains to locate any chains of rearrangable expressions and their inputs
463                for (unsigned i = 0; i != 2; ++i) {
464                    PabloAST * op = stmt->getOperand(i);
465                    auto f = Mk.find(op);
466                    if (f == Mk.end()) {
467                        const Vertex v = add_vertex(op, Gk);
468                        f = Mk.insert(std::make_pair(op, v)).first;
469                        if (op->getClassTypeId() == stmt->getClassTypeId() && inCurrentBlock(cast<Statement>(op), block)) {
470                            push(v, Q);
471                        }
472                    }
473                    add_edge(f->second, u, Gk);
474                }
475            }
476            if (Q.empty()) {
477                break;
478            }
479        }
480
481        // Generate a topological ordering for G; if one of our terminals happens to also be a partial computation of
482        // another terminal, we need to make sure we compute it as an independent subexpression.
483        std::vector<unsigned> ordering;
484        ordering.reserve(num_vertices(Gk));
485        topological_sort(Gk, std::back_inserter(ordering));
486        std::vector<unsigned> component(num_vertices(Gk));
487
488        for (;;) {
489
490            // Mark which computation component these vertices are in based on their topological (occurence) order.
491            unsigned components = 0;
492            for (auto u : ordering) {
493                unsigned id = 0;
494                // If this is a sink in G, it is the root of a new component.
495                if (out_degree(u, Gk) == 0) {
496                    id = ++components;
497                } else { // otherwise it belongs to the outermost component.
498                    for (auto e : make_iterator_range(out_edges(u, Gk))) {
499                        id = std::max(id, component[target(e, Gk)]);
500                    }
501                }
502                assert (id && "Topological ordering failed!");
503                component[u] = id;
504            }
505
506            // Cut the graph wherever a computation crosses a component or whenever we need to cut the graph because
507            // the instructions corresponding to the pair of nodes differs.
508            graph_traits<Graph>::edge_iterator ei, ei_end;
509            for (std::tie(ei, ei_end) = edges(Gk); ei != ei_end; ) {
510                const Graph::edge_descriptor e = *ei++;
511                const Vertex u = source(e, Gk);
512                const Vertex v = target(e, Gk);
513                if (LLVM_UNLIKELY(isCutNecessary(u, v, Gk, component))) {
514                    E.push(std::make_pair(u, v));
515                    remove_edge(u, v, Gk);
516                }
517            }
518
519            // If no cuts are necessary, we're done.
520            if (E.empty()) {
521                break;
522            }
523
524            for (;;) {
525
526                Vertex u, v;
527                std::tie(u, v) = E.front(); E.pop();
528
529                // The vertex belonging to a component with a greater number must come "earlier"
530                // in the program. By replicating it, this ensures it's computed as an output of
531                // one component and used as an input of another.
532                if (component[u] < component[v]) {
533                    std::swap(u, v);
534                }
535
536                // Replicate u and fix the ordering and component vectors to reflect the change in Gk.
537                Vertex w = add_vertex(Gk[u], Gk);
538                ordering.insert(std::find(ordering.begin(), ordering.end(), u), w);
539                assert (component.size() == w);
540                component.push_back(component[v]);
541                add_edge(w, v, Gk);
542
543                // However, after we do so, we need to make sure the original source vertex will be a
544                // sink in Gk unless it is also an input variable (in which case we'd simply end up with
545                // extraneous isolated vertex. Otherwise, we need to make further cuts and replications.
546                if (in_degree(u, Gk) != 0) {
547                    for (auto e : make_iterator_range(out_edges(u, Gk))) {
548                        E.push(std::make_pair(source(e, Gk), target(e, Gk)));
549                    }
550                    clear_out_edges(u, Gk);
551                }
552
553                if (E.empty()) {
554                    break;
555                }
556            }
557        }
558
559        // Scan through the graph so that we process the outermost expressions first
560        for (const Vertex u : ordering) {
561            if (LLVM_UNLIKELY(out_degree(u, Gk) == 0)) {
562                // Create a vertex marking the output statement we may end up replacing
563                // and collect the set of source variables in the component
564                const Vertex x = getVertex(Gk[u], G, M);
565                if (LLVM_LIKELY(in_degree(u, Gk) > 0)) {
566                    flat_set<PabloAST *> vars;
567                    flat_set<Vertex> visited;
568                    for (Vertex v = u;;) {
569                        if (in_degree(v, Gk) == 0) {
570                            vars.insert(Gk[v]);
571                        } else {
572                            for (auto e : make_iterator_range(in_edges(v, Gk))) {
573                                const Vertex w = source(e, Gk);
574                                if (LLVM_LIKELY(visited.insert(w).second)) {
575                                    push(w, Q);
576                                }
577                            }
578                        }
579                        if (Q.empty()) {
580                            break;
581                        }
582                        v = pop(Q);
583                    }
584                    for (PabloAST * var : vars) {
585                        add_edge(getVertex(var, G, M), x, G);
586                    }
587                }
588            }
589        }
590
591        // Determine the source variables of the next "layer" of the AST
592        flat_set<Statement *> nextSet;
593        for (auto u : ordering) {
594            if (LLVM_UNLIKELY(in_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) {
595                nextSet.insert(cast<Statement>(Gk[u]));
596            } else if (LLVM_UNLIKELY(out_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) {
597                // some input will also be the output of some subgraph of Gk whenever we cut and
598                // replicated a vertex. We don't need to reevaluate it as part of the next layer.
599                nextSet.erase(cast<Statement>(Gk[u]));
600            }
601        }
602
603        if (LLVM_UNLIKELY(nextSet.empty())) {
604            break;
605        }
606
607        terminals.assign(nextSet.begin(), nextSet.end());
608    }
609}
610
611using VertexSet = std::vector<Vertex>;
612using VertexSets = std::vector<VertexSet>;
613
614template <class Graph>
615static VertexSet incomingVertexSet(const Vertex u, const Graph & G) {
616    VertexSet V;
617    V.reserve(G.in_degree(u));
618    for (auto e : make_iterator_range(G.in_edges(u))) {
619        V.push_back(G.source(e));
620    }
621    std::sort(V.begin(), V.end());
622    return std::move(V);
623}
624
625template <class Graph>
626static VertexSet outgoingVertexSet(const Vertex u, const Graph & G) {
627    VertexSet V;
628    V.reserve(G.out_degree(u));
629    for (auto e : make_iterator_range(G.out_edges(u))) {
630        V.push_back(G.target(e));
631    }
632    std::sort(V.begin(), V.end());
633    return std::move(V);
634}
635
636/** ------------------------------------------------------------------------------------------------------------- *
637 * @brief enumerateBicliques
638 *
639 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
640 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies with an in-degree of 0
641 * to be in bipartition A and their adjacencies to be in B.
642  ** ------------------------------------------------------------------------------------------------------------- */
643template <class Graph>
644static VertexSets enumerateBicliques(const Graph & G) {
645    using IntersectionSets = std::set<VertexSet>;
646
647    IntersectionSets B1;
648    for (auto u : make_iterator_range(G.vertices())) {
649        if (G.in_degree(u) == 0) {
650            B1.insert(std::move(outgoingVertexSet(u, G)));
651        }
652    }
653
654    IntersectionSets C(B1.begin(), B1.end());
655
656    IntersectionSets Bi;
657    VertexSet clique;
658    for (auto i = B1.begin(); i != B1.end(); ++i) {
659        for (auto j = i; ++j != B1.end(); ) {
660            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
661            if (clique.size() > 0) {
662                if (C.count(clique) == 0) {
663                    Bi.insert(clique);
664                }
665                clique.clear();
666            }
667        }
668    }
669
670    for (;;) {
671        if (Bi.empty()) {
672            break;
673        }
674        C.insert(Bi.begin(), Bi.end());
675        IntersectionSets Bk;
676        for (auto i = B1.begin(); i != B1.end(); ++i) {
677            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
678                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
679                if (clique.size() > 0) {
680                    if (C.count(clique) == 0) {
681                        Bk.insert(clique);
682                    }
683                    clique.clear();
684                }
685            }
686        }
687        Bi.swap(Bk);
688    }
689
690    return VertexSets(C.begin(), C.end());
691}
692
693/** ------------------------------------------------------------------------------------------------------------- *
694 * @brief intersects
695 ** ------------------------------------------------------------------------------------------------------------- */
696template <class Type>
697inline bool intersects(const Type & A, const Type & B) {
698    auto first1 = A.begin(), last1 = A.end();
699    auto first2 = B.begin(), last2 = B.end();
700    while (first1 != last1 && first2 != last2) {
701        if (*first1 < *first2) {
702            ++first1;
703        } else if (*first2 < *first1) {
704            ++first2;
705        } else {
706            return true;
707        }
708    }
709    return false;
710}
711
712/** ------------------------------------------------------------------------------------------------------------- *
713 * @brief maximalIndependentSet
714 ** ------------------------------------------------------------------------------------------------------------- */
715static VertexSets && maximalIndependentSet(VertexSets && V) {
716    using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
717    const auto l = V.size();
718    IndependentSetGraph I(l);
719    // Initialize our weights
720    for (unsigned i = 0; i != l; ++i) {
721        I[i] = V[i].size();
722    }
723    // Determine our constraints
724    for (unsigned i = 0; i != l; ++i) {
725        for (unsigned j = i + 1; j != l; ++j) {
726            if (intersects(V[i], V[j])) {
727                add_edge(i, j, I);
728            }
729        }
730    }
731    // Use the greedy algorithm to choose our independent set (TODO: try the similar randomized approach)
732    VertexSet selected;
733    std::vector<bool> ignored(l, false);
734    for (;;) {
735        unsigned w = 0;
736        Vertex u = 0;
737        for (unsigned i = 0; i != l; ++i) {
738            if (!ignored[i] && I[i] > w) {
739                w = I[i];
740                u = i;
741            }
742        }
743        if (w == 0) break;
744        selected.push_back(u);
745        ignored[u] = true;
746        for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
747            ignored[v] = true;
748        }
749    }
750    // Sort the selected list and then remove the unselected sets from V
751    std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
752    auto end = V.end();
753    for (const unsigned offset : selected) {
754        end = V.erase(V.begin() + offset + 1, end) - 1;
755    }
756    V.erase(V.begin(), end);
757    return std::move(V);
758}
759
760/** ------------------------------------------------------------------------------------------------------------- *
761 * @brief sinkIndependentBicliques
762 ** ------------------------------------------------------------------------------------------------------------- */
763template <class Graph>
764static VertexSets sinkIndependentBicliques(Graph && G) {
765    VertexSets B = maximalIndependentSet(std::move(enumerateBicliques(G)));
766    VertexSets A;
767    A.reserve(B.size());
768    for (const VertexSet & Bi : B) {
769        // Compute our A set
770        auto bi = Bi.begin();
771        VertexSet Ai = incomingVertexSet(*bi, G);
772        while (++bi != Bi.end()) {
773            VertexSet Ai = incomingVertexSet(*bi, G);
774            VertexSet Ak;
775            std::set_intersection(Ai.begin(), Ai.end(), Ai.begin(), Ai.end(), std::back_inserter(Ak));
776            Ai.swap(Ak);
777        }
778        A.emplace_back(std::move(Ai));
779    }
780    std::vector<Vertex> sources;
781    std::vector<Vertex> intermediary;
782    for (auto u : make_iterator_range(G.vertices())) {
783        if (G.in_degree(u) == 0) {
784            sources.push_back(u);
785        } else if (G.out_degree(u) != 0) {
786            intermediary.push_back(u);
787        }
788    }
789    for (auto u : sources) {
790        G.clear_out_edges(u);
791    }
792    for (unsigned i = 0; i != B.size(); ++i) {
793        for (auto u : A[i]) {
794            for (auto v : B[i]) {
795                G.add_edge(u, v);
796            }
797        }
798    }
799    for (auto u : intermediary) {
800        if (G.in_degree(u) == 0) {
801            G.clear_out_edges(u);
802        }
803    }
804    return std::move(A);
805}
806
807/** ------------------------------------------------------------------------------------------------------------- *
808 * @brief safeDistributionSets
809 ** ------------------------------------------------------------------------------------------------------------- */
810template <class Graph>
811static VertexSets safeDistributionSets(Graph & G) {
812    VertexSets sinks(std::move(sinkIndependentBicliques(makeTransposedGraphFacade(G))));
813    // Scan through G and replicate any source that has more than one sink until G is broken
814    // into weakly connected components in which each has exactly one sink.
815    if (sinks.size() > 1) {
816        std::vector<unsigned> component(num_vertices(G), 0);
817        unsigned components = 0;
818        for (const VertexSet & S : sinks) {
819            ++components;
820            for (auto e : make_iterator_range(in_edges(S.front(), G))) {
821                component[source(e, G)] = components;
822            }
823        }
824        for (const Vertex u : make_iterator_range(vertices(G))) {
825            if (LLVM_UNLIKELY(in_degree(u, G) == 0)) {
826                flat_set<unsigned> membership;
827                for (auto e : make_iterator_range(out_edges(u, G))) {
828                    membership.insert(component[target(e, G)]);
829                }
830                if (LLVM_UNLIKELY(membership.size() > 1)) {
831                    VertexSet adjacent;
832                    adjacent.reserve(out_degree(u, G));
833                    for (auto e : make_iterator_range(out_edges(u, G))) {
834                        adjacent.push_back(target(e, G));
835                    }
836                    clear_out_edges(u, G);
837                    auto mi = membership.begin();
838                    for (Vertex w = u; ;) {
839                        const unsigned m = *mi;
840                        for (auto v : adjacent) {
841                            if (component[v] == m) {
842                                add_edge(w, v, G);
843                            }
844                        }
845                        if (++mi == membership.end()) {
846                            break;
847                        }
848                        w = add_vertex(G[u], G);
849                    }
850                }
851            }
852        }
853    }
854    return std::move(sinkIndependentBicliques(makeGraphFacade(G)));
855}
856
857/** ------------------------------------------------------------------------------------------------------------- *
858 * @brief segmentInto3LevelGraph
859 *
860 * Ensure that every source-to-sink path in G has a distance of exactly 2.
861 ** ------------------------------------------------------------------------------------------------------------- */
862template <class Graph>
863Graph & segmentInto3LevelGraph(Graph & G) {
864
865    std::vector<Vertex> ordering;
866    ordering.reserve(num_vertices(G));
867
868    topological_sort(G, std::back_inserter(ordering));
869
870    std::vector<unsigned> distance(num_vertices(G));
871    // Compute the distance to furthest sink for each node
872    for (Vertex u : ordering) {
873        unsigned d = 0;
874        for (auto e : make_iterator_range(out_edges(u, G))) {
875            d = std::max<unsigned>(d, distance[target(e, G)] + 1);
876        }
877        distance[u] = d;
878    }
879
880
881
882
883    return G;
884}
885
886/** ------------------------------------------------------------------------------------------------------------- *
887 * @brief redistributeAST
888 *
889 * Apply the distribution law to reduce computations whenever possible.
890 ** ------------------------------------------------------------------------------------------------------------- */
891bool BooleanReassociationPass::redistributeAST(PabloBlock & block, Graph & G) const {
892    using TypeId = PabloAST::ClassTypeId;
893
894    bool anyChanges = false;
895
896    for (;;) {
897
898        adjacency_list<hash_setS, vecS, bidirectionalS, Vertex> H;
899        flat_map<Vertex, Vertex> M;
900
901        for (const Vertex u : make_iterator_range(vertices(G))) {
902            const TypeId outerTypeId = G[u]->getClassTypeId();
903            if (outerTypeId == TypeId::And || outerTypeId == TypeId::Or) {
904                if (inCurrentBlock(cast<Statement>(G[u]), block)) {
905                    const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
906                    flat_set<Vertex> distributable;
907                    for (auto e : make_iterator_range(in_edges(u, G))) {
908                        const Vertex v = source(e, G);
909                        if (LLVM_UNLIKELY(G[v]->getClassTypeId() == innerTypeId) && LLVM_LIKELY(inCurrentBlock(cast<Statement>(G[v]), block))) {
910                            bool safe = true;
911                            for (const auto e : make_iterator_range(out_edges(v, G))) {
912                                if (G[target(e, G)]->getClassTypeId() != outerTypeId) {
913                                    safe = false;
914                                    break;
915                                }
916                            }
917                            if (safe) {
918                                distributable.insert(v);
919                            }
920                        }
921                    }
922                    if (LLVM_LIKELY(distributable.size() > 1)) {
923                        // We're only interested in computing a subgraph of G in which every source has an out-degree
924                        // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical
925                        // benefit. (Note: this does not consider register pressure / liveness.)
926                        flat_map<Vertex, unsigned> observed;
927                        bool anyOpportunities = false;
928                        for (const Vertex v : distributable) {
929                            for (auto e : make_iterator_range(in_edges(v, G))) {
930                                const Vertex w = source(e, G);
931                                const auto f = observed.find(w);
932                                if (f == observed.end()) {
933                                    observed.emplace(w, 0);
934                                } else {
935                                    f->second += 1;
936                                    anyOpportunities = true;
937                                }
938                            }
939                        }
940                        if (anyOpportunities) {
941                            for (auto ob : observed) {
942                                if (std::get<1>(ob)) {
943                                    const Vertex w = std::get<0>(ob);
944                                    for (auto e : make_iterator_range(out_edges(w, G))) {
945                                        const Vertex v = target(e, G);
946                                        if (distributable.count(v)) {
947                                            const Vertex y = getVertex(v, H, M);
948                                            add_edge(y, getVertex(u, H, M), H);
949                                            add_edge(getVertex(w, H, M), y, H);
950                                        }
951                                    }
952                                }
953                            }
954                        }
955                    }
956                }
957            }
958        }
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 VertexSets distributionSets = safeDistributionSets(segmentInto3LevelGraph(H));
966
967        // If no sources remain, no bicliques were found that would have a meaningful impact on the AST.
968        if (LLVM_UNLIKELY(distributionSets.size() == 0)) {
969            break;
970        }
971
972        for (const VertexSet & sources : distributionSets) {
973            assert (sources.size() > 0);
974            const VertexSet intermediary = outgoingVertexSet(sources.front(), makeGraphFacade(H));
975            assert (intermediary.size() > 0);
976            const VertexSet sinks = outgoingVertexSet(intermediary.front(), makeGraphFacade(H));
977            assert (sinks.size() > 0);
978
979            // Now begin transforming the AST
980            const TypeId typeId = G[H[sinks.front()]]->getClassTypeId();
981            assert (typeId == TypeId::And || typeId == TypeId::Or);
982
983            circular_buffer<PabloAST *> Q(std::max(sources.size(), intermediary.size() + 1));
984            for (const Vertex u : intermediary) {
985                Q.push_back(G[H[u]]);
986            }
987            PabloAST * merged = createTree(block, typeId, Q);
988            for (const Vertex s : sources) {
989                Q.push_back(G[H[s]]);
990            }
991            Q.push_back(merged);
992            PabloAST * masked = createTree(block, typeId == TypeId::Or ? TypeId::And : TypeId::Or, Q);
993
994            // Eliminate the edges from our original graph
995            for (const Vertex u : intermediary) {
996                for (const Vertex s : sources) {
997                    remove_edge(H[s], H[u], G);
998                }
999                for (const Vertex t : sinks) {
1000                    remove_edge(H[u], H[t], G);
1001                }
1002            }
1003
1004            // Finally update G to match the desired changes
1005            const Vertex x = add_vertex(merged, G);
1006            const Vertex y = add_vertex(masked, G);
1007            for (const Vertex u : intermediary) {
1008                add_edge(H[u], x, G);
1009            }
1010            add_edge(x, y, G);
1011            for (const Vertex s : sources) {
1012                add_edge(H[s], y, G);
1013            }
1014            for (const Vertex t : sinks) {
1015                add_edge(y, H[t], G);
1016            }
1017        }
1018        anyChanges = true;
1019    }
1020
1021    return anyChanges;
1022}
1023
1024}
Note: See TracBrowser for help on using the repository browser.