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

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

More work on reassociation pass.

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