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

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

Temporary check-in

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