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

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

Work on distribution law.

File size: 36.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
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        out << "v" << u << " [label=\"";
272        PabloAST * expr = G[S[u]];
273        if (isa<Statement>(expr)) {
274            if (LLVM_UNLIKELY(isa<If>(expr))) {
275                out << "If ";
276                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
277                out << ":";
278            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
279                out << "While ";
280                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
281                out << ":";
282            } else {
283                PabloPrinter::print(cast<Statement>(expr), "", out);
284            }
285        } else {
286            PabloPrinter::print(expr, out);
287        }
288        out << "\"";
289        if (!inCurrentBlock(expr, block)) {
290            out << " style=dashed";
291        }
292        out << "];\n";
293    }
294    for (auto e : make_iterator_range(edges(S))) {
295        out << "v" << source(e, S) << " -> v" << target(e, S) << ";\n";
296    }
297
298    if (num_vertices(S) > 0) {
299
300        out << "{ rank=same;";
301        for (auto u : make_iterator_range(vertices(S))) {
302            if (in_degree(u, S) == 0 && out_degree(u, S) != 0) {
303                out << " v" << u;
304            }
305        }
306        out << "}\n";
307
308        out << "{ rank=same;";
309        for (auto u : make_iterator_range(vertices(S))) {
310            if (out_degree(u, S) == 0 && in_degree(u, S) != 0) {
311                out << " v" << u;
312            }
313        }
314        out << "}\n";
315
316    }
317
318    out << "}\n\n";
319    out.flush();
320}
321
322/** ------------------------------------------------------------------------------------------------------------- *
323 * @brief processScope
324 ** ------------------------------------------------------------------------------------------------------------- */
325void BooleanReassociationPass::processScope(PabloBlock & block, std::vector<Statement *> && terminals) {
326
327    Graph G;
328
329    summarizeAST(block, terminals, G);
330    redistributeAST(block, G);
331
332//    for (;;) {
333//        summarizeAST(block, terminals, G);
334//        if (redistributeAST(block, G)) {
335//            G.clear();
336//        } else {
337//            break;
338//        }
339//    }
340
341    printGraph(block, G, "G");
342
343}
344
345/** ------------------------------------------------------------------------------------------------------------- *
346 * @brief summarizeAST
347 *
348 * This function scans through a basic block (starting by its terminals) and computes a DAG in which any sequences
349 * of AND, OR or XOR functions are "flattened" (i.e., allowed to have any number of inputs.) This allows us to
350 * reassociate them in the most efficient way possible.
351 ** ------------------------------------------------------------------------------------------------------------- */
352void BooleanReassociationPass::summarizeAST(PabloBlock & block, std::vector<Statement *> terminals, Graph & G) const {
353
354    VertexQueue Q(128);
355    EdgeQueue E;
356    Map M;
357
358    for (;;) {
359
360        Graph Gk;
361        Map Mk;
362
363        // Generate a graph depicting the relationships between the terminals. If the original terminals
364        // cannot be optimized with this algorithm bypass them in favour of their operands. If those cannot
365        // be optimized, they'll be left as the initial terminals for the next "layer" of the AST.
366
367        for (Statement * term : terminals) {
368            if (LLVM_LIKELY(Mk.count(term) == 0)) {
369                // add or find this terminal in our global graph
370                Vertex x = getVertex(term, G, M);
371                if (inCurrentBlock(term, block)) {
372                    if (isOptimizable(term)) {
373                        const Vertex u = add_vertex(term, Gk);
374                        Mk.insert(std::make_pair(term, u));
375                        push(u, Q);
376                        continue;
377                    }
378                } else if (isa<Assign>(term) || isa<Next>(term)) {
379                    // If this is an Assign (Next) node whose operand does not originate from the current block
380                    // then check to see if there is an If (While) node that does.
381                    Statement * branch = nullptr;
382                    if (isa<Assign>(term)) {
383                        for (PabloAST * user : term->users()) {
384                            if (isa<If>(user)) {
385                                const If * ifNode = cast<If>(user);
386                                if (inCurrentBlock(ifNode, block)) {
387                                    const auto & defs = ifNode->getDefined();
388                                    if (LLVM_LIKELY(std::find(defs.begin(), defs.end(), cast<Assign>(term)) != defs.end())) {
389                                        branch = cast<Statement>(user);
390                                        break;
391                                    }
392                                }
393                            }
394                        }
395                    } else { // if (isa<Next>(term))
396                        for (PabloAST * user : term->users()) {
397                            if (isa<While>(user)) {
398                                const While * whileNode = cast<While>(user);
399                                if (inCurrentBlock(whileNode, block)) {
400                                    const auto & vars = whileNode->getVariants();
401                                    if (LLVM_LIKELY(std::find(vars.begin(), vars.end(), cast<Next>(term)) != vars.end())) {
402                                        branch = cast<Statement>(user);
403                                        break;
404                                    }
405                                }
406                            }
407                        }
408                    }
409
410                    // If we didn't find a branch, then the Assign (Next) node must have come from a preceeding
411                    // block. Just skip it for now.
412                    if (branch == nullptr) {
413                        continue;
414                    }
415
416                    // Otherwise add the branch to G and test its operands rather than the original terminal
417                    const Vertex z = getVertex(branch, G, M);
418                    add_edge(z, x, G);
419                    x = z;
420                    term = branch;
421                }
422
423                for (unsigned i = 0; i != term->getNumOperands(); ++i) {
424                    PabloAST * const op = term->getOperand(i);
425                    if (LLVM_LIKELY(inCurrentBlock(op, block))) {
426                        const Vertex y = getVertex(op, G, M);
427                        add_edge(y, x, G);
428                        if (LLVM_LIKELY(Mk.count(op) == 0)) {
429                            const Vertex v = add_vertex(op, Gk);
430                            Mk.insert(std::make_pair(op, v));
431                            push(v, Q);
432                        }
433                    }
434                }
435            }
436        }
437
438        if (LLVM_UNLIKELY(Q.empty())) {
439            break;
440        }
441
442        for (;;) {
443            const Vertex u = pop(Q);
444            if (isOptimizable(Gk[u])) {
445                Statement * stmt = cast<Statement>(Gk[u]);
446                // If any user of this statement is not in the current block, determine the outermost If/While node
447                // that contains this statement within and add an edge from this statement to it to denote both the
448                // topological ordering necessary and that this statement must be computed.
449                for (PabloAST * user : stmt->users()) {
450                    if (LLVM_LIKELY(isa<Statement>(user))) {
451                        PabloBlock * parent = cast<Statement>(user)->getParent();
452                        if (LLVM_UNLIKELY(parent != &block)) {
453                            while (parent->getParent() != &block) {
454                                parent = parent->getParent();
455                            }
456                            if (LLVM_UNLIKELY(parent == nullptr)) {
457                                throw std::runtime_error("Could not locate nested scope block!");
458                            }
459                            const auto f = mResolvedScopes.find(parent);
460                            if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
461                                throw std::runtime_error("Failed to resolve scope block!");
462                            }
463                            add_edge(u, getVertex(f->second, Gk, Mk), Gk);
464                        }
465                    }
466                }
467                // Scan through the use-def chains to locate any chains of rearrangable expressions and their inputs
468                for (unsigned i = 0; i != 2; ++i) {
469                    PabloAST * op = stmt->getOperand(i);
470                    auto f = Mk.find(op);
471                    if (f == Mk.end()) {
472                        const Vertex v = add_vertex(op, Gk);
473                        f = Mk.insert(std::make_pair(op, v)).first;
474                        if (op->getClassTypeId() == stmt->getClassTypeId() && inCurrentBlock(cast<Statement>(op), block)) {
475                            push(v, Q);
476                        }
477                    }
478                    add_edge(f->second, u, Gk);
479                }
480            }
481            if (Q.empty()) {
482                break;
483            }
484        }
485
486        // Generate a topological ordering for G; if one of our terminals happens to also be a partial computation of
487        // another terminal, we need to make sure we compute it as an independent subexpression.
488        std::vector<unsigned> ordering;
489        ordering.reserve(num_vertices(Gk));
490        topological_sort(Gk, std::back_inserter(ordering));
491        std::vector<unsigned> component(num_vertices(Gk));
492
493        for (;;) {
494
495            // Mark which computation component these vertices are in based on their topological (occurence) order.
496            unsigned components = 0;
497            for (auto u : ordering) {
498                unsigned id = 0;
499                // If this is a sink in G, it is the root of a new component.
500                if (out_degree(u, Gk) == 0) {
501                    id = ++components;
502                } else { // otherwise it belongs to the outermost component.
503                    for (auto e : make_iterator_range(out_edges(u, Gk))) {
504                        id = std::max(id, component[target(e, Gk)]);
505                    }
506                }
507                assert (id && "Topological ordering failed!");
508                component[u] = id;
509            }
510
511            // Cut the graph wherever a computation crosses a component or whenever we need to cut the graph because
512            // the instructions corresponding to the pair of nodes differs.
513            graph_traits<Graph>::edge_iterator ei, ei_end;
514            for (std::tie(ei, ei_end) = edges(Gk); ei != ei_end; ) {
515                const Graph::edge_descriptor e = *ei++;
516                const Vertex u = source(e, Gk);
517                const Vertex v = target(e, Gk);
518                if (LLVM_UNLIKELY(isCutNecessary(u, v, Gk, component))) {
519                    E.push(std::make_pair(u, v));
520                    remove_edge(u, v, Gk);
521                }
522            }
523
524            // If no cuts are necessary, we're done.
525            if (E.empty()) {
526                break;
527            }
528
529            for (;;) {
530
531                Vertex u, v;
532                std::tie(u, v) = E.front(); E.pop();
533
534                // The vertex belonging to a component with a greater number must come "earlier"
535                // in the program. By replicating it, this ensures it's computed as an output of
536                // one component and used as an input of another.
537                if (component[u] < component[v]) {
538                    std::swap(u, v);
539                }
540
541                // Replicate u and fix the ordering and component vectors to reflect the change in Gk.
542                Vertex w = add_vertex(Gk[u], Gk);
543                ordering.insert(std::find(ordering.begin(), ordering.end(), u), w);
544                assert (component.size() == w);
545                component.push_back(component[v]);
546                add_edge(w, v, Gk);
547
548                // However, after we do so, we need to make sure the original source vertex will be a
549                // sink in Gk unless it is also an input variable (in which case we'd simply end up with
550                // extraneous isolated vertex. Otherwise, we need to make further cuts and replications.
551                if (in_degree(u, Gk) != 0) {
552                    for (auto e : make_iterator_range(out_edges(u, Gk))) {
553                        E.push(std::make_pair(source(e, Gk), target(e, Gk)));
554                    }
555                    clear_out_edges(u, Gk);
556                }
557
558                if (E.empty()) {
559                    break;
560                }
561            }
562        }
563
564        // Scan through the graph so that we process the outermost expressions first
565        for (const Vertex u : ordering) {
566            if (LLVM_UNLIKELY(out_degree(u, Gk) == 0)) {
567                // Create a vertex marking the output statement we may end up replacing
568                // and collect the set of source variables in the component
569                const Vertex x = getVertex(Gk[u], G, M);
570                if (LLVM_LIKELY(in_degree(u, Gk) > 0)) {
571                    flat_set<PabloAST *> vars;
572                    flat_set<Vertex> visited;
573                    for (Vertex v = u;;) {
574                        if (in_degree(v, Gk) == 0) {
575                            vars.insert(Gk[v]);
576                        } else {
577                            for (auto e : make_iterator_range(in_edges(v, Gk))) {
578                                const Vertex w = source(e, Gk);
579                                if (LLVM_LIKELY(visited.insert(w).second)) {
580                                    push(w, Q);
581                                }
582                            }
583                        }
584                        if (Q.empty()) {
585                            break;
586                        }
587                        v = pop(Q);
588                    }
589                    for (PabloAST * var : vars) {
590                        add_edge(getVertex(var, G, M), x, G);
591                    }
592                }
593            }
594        }
595
596        // Determine the source variables of the next "layer" of the AST
597        flat_set<Statement *> nextSet;
598        for (auto u : ordering) {
599            if (LLVM_UNLIKELY(in_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) {
600                nextSet.insert(cast<Statement>(Gk[u]));
601            } else if (LLVM_UNLIKELY(out_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) {
602                // some input will also be the output of some subgraph of Gk whenever we cut and
603                // replicated a vertex. We don't need to reevaluate it as part of the next layer.
604                nextSet.erase(cast<Statement>(Gk[u]));
605            }
606        }
607
608        if (LLVM_UNLIKELY(nextSet.empty())) {
609            break;
610        }
611
612        terminals.assign(nextSet.begin(), nextSet.end());
613    }
614}
615
616using VertexSet = std::vector<Vertex>;
617using VertexSets = std::set<VertexSet>;
618
619/** ------------------------------------------------------------------------------------------------------------- *
620 * @brief mica
621 *
622 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
623 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies with an in-degree of 0
624 * to be in bipartition A and their adjacencies to be in bipartition B. Because we do not care about the rank 1
625 * (star) cliques, this does not record them.
626 ** ------------------------------------------------------------------------------------------------------------- */
627static std::vector<VertexSet> mica(const Graph & G) {
628
629    VertexSets B1;
630    for (auto u : make_iterator_range(vertices(G))) {
631        if (in_degree(u, G) == 0) {
632            VertexSet B;
633            B.reserve(out_degree(u, G));
634            for (auto e : make_iterator_range(out_edges(u, G))) {
635                B.push_back(target(e, G));
636            }
637            std::sort(B.begin(), B.end()); // note: these already ought to be in order
638            B1.insert(std::move(B));
639        }
640    }
641
642    VertexSets Bi;
643
644    VertexSet clique;
645    for (auto i = B1.begin(); i != B1.end(); ++i) {
646        for (auto j = i; ++j != B1.end(); ) {
647            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
648            if (clique.size() > 0) {
649                Bi.insert(clique);
650                clique.clear();
651            }
652        }
653    }
654
655    VertexSets C;
656
657    for (;;) {
658        if (Bi.empty()) {
659            break;
660        }
661        C.insert(Bi.begin(), Bi.end());
662
663        VertexSets Bk;
664        for (auto i = B1.begin(); i != B1.end(); ++i) {
665            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
666                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
667                if (clique.size() > 0) {
668                    if (C.count(clique) == 0) {
669                        Bk.insert(clique);
670                    }
671                    clique.clear();
672                }
673            }
674        }
675        Bi.swap(Bk);
676    }
677
678    return std::vector<VertexSet>(C.begin(), C.end());
679}
680
681/** ------------------------------------------------------------------------------------------------------------- *
682 * @brief areNonDisjoint
683 ** ------------------------------------------------------------------------------------------------------------- */
684template <class Type>
685inline bool areNonDisjoint(const Type & A, const Type & B) {
686    auto first1 = A.begin(), last1 = A.end();
687    auto first2 = B.begin(), last2 = B.end();
688    while (first1 != last1 && first2 != last2) {
689        if (*first1 < *first2) {
690            ++first1;
691        } else if (*first2 < *first1) {
692            ++first2;
693        } else {
694            return true;
695        }
696    }
697    return false;
698}
699
700/** ------------------------------------------------------------------------------------------------------------- *
701 * @brief maximalIndependentSet
702 ** ------------------------------------------------------------------------------------------------------------- */
703static void maximalIndependentSet(std::vector<VertexSet> & V) {
704    using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
705    const auto l = V.size();
706    IndependentSetGraph I(l);
707    // Initialize our weights
708    for (unsigned i = 0; i != l; ++i) {
709        I[i] = std::pow(V[i].size(), 2);
710    }
711    // Determine our constraints
712    for (unsigned i = 0; i != l; ++i) {
713        for (unsigned j = i + 1; j != l; ++j) {
714            if (areNonDisjoint(V[i], V[j])) {
715                add_edge(i, j, I);
716            }
717        }
718    }
719    // Use the greedy algorithm to choose our independent set (TODO: try the similar randomized approach)
720    std::vector<Vertex> selected;
721
722    std::vector<bool> ignored(l, false);
723    for (;;) {
724        unsigned w = 0;
725        Vertex u = 0;
726        for (unsigned i = 0; i != l; ++i) {
727            if (!ignored[i] && I[i] > w) {
728                w = I[i];
729                u = i;
730            }
731        }
732        if (w < 2) break;
733        selected.push_back(u);
734        ignored[u] = true;
735        for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
736            ignored[v] = true;
737        }
738    }
739
740    // Sort the selected list and then remove the unselected sets from V
741    std::sort(selected.begin(), selected.end(), std::greater<unsigned>());
742    auto end = V.end();
743    for (const unsigned offset : selected) {
744        end = V.erase(V.begin() + offset + 1, end) - 1;
745    }
746    V.erase(V.begin(), end);
747
748}
749
750
751/** ------------------------------------------------------------------------------------------------------------- *
752 * @brief maximalIndependentBicliqueSet
753 ** ------------------------------------------------------------------------------------------------------------- */
754static void maximalIndependentBicliqueSet(Graph & G) {
755    // First enumerate our bicliques in G.
756    auto R = mica(G);
757    // Then compute the maximal independent set of the vertices in the B bipartition.
758    // NOTE: this means vertices in A can point to more than one vertex in B. These
759    // have to be resolved specially later.
760    maximalIndependentSet(R);
761    // Update G to reflect our maximal independent biclique set
762    std::vector<VertexSet> L;
763    for (const VertexSet & B : R) {
764        // Compute our A set
765        VertexSet A;
766        auto bi = B.begin();
767        A.reserve(in_degree(*bi, G));
768        for (auto e : make_iterator_range(in_edges(*bi, G))) {
769            A.push_back(source(e, G));
770        }
771        std::sort(A.begin(), A.end());
772        while (++bi != B.end()) {
773            VertexSet Ai;
774            Ai.reserve(in_degree(*bi, G));
775            for (auto e : make_iterator_range(in_edges(*bi, G))) {
776                Ai.push_back(source(e, G));
777            }
778            std::sort(Ai.begin(), Ai.end());
779            VertexSet Ak;
780            std::set_intersection(A.begin(), A.end(), Ai.begin(), Ai.end(), std::back_inserter(Ak));
781            A.swap(Ak);
782        }
783        L.emplace_back(std::move(A));
784    }
785    for (auto u : make_iterator_range(vertices(G))) {
786        if (in_degree(u, G) == 0) {
787            clear_out_edges(u, G);
788        }
789    }
790    for (unsigned i = 0; i != R.size(); ++i) {
791        for (auto u : L[i]) {
792            for (auto v : R[i]) {
793                add_edge(u, v, G);
794            }
795        }
796    }
797}
798
799/** ------------------------------------------------------------------------------------------------------------- *
800 * @brief redistributeAST
801 *
802 * Apply the distribution law to reduce computations whenever possible.
803 ** ------------------------------------------------------------------------------------------------------------- */
804bool BooleanReassociationPass::redistributeAST(PabloBlock & block, Graph & G) const {
805    using TypeId = PabloAST::ClassTypeId;
806
807    Graph B;
808    Map M;
809
810    for (const Vertex u : make_iterator_range(vertices(G))) {
811        const TypeId outerTypeId = G[u]->getClassTypeId();
812        if (outerTypeId == TypeId::And || outerTypeId == TypeId::Or) {
813            if (inCurrentBlock(cast<Statement>(G[u]), block)) {
814                const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
815                flat_set<Vertex> distributable;
816                for (auto e : make_iterator_range(in_edges(u, G))) {
817                    const Vertex v = source(e, G);
818                    if (G[v]->getClassTypeId() == innerTypeId && inCurrentBlock(cast<Statement>(G[v]), block)) {
819                        bool safe = true;
820                        for (PabloAST * user : G[v]->users()) {
821                            if (user->getClassTypeId() != outerTypeId) {
822                                safe = false;
823                                break;
824                            }
825                        }
826                        if (safe) {
827                            distributable.insert(v);
828                        }
829                    }
830                }
831                if (LLVM_LIKELY(distributable.size() > 1)) {
832                    // We're only interested in computing a subgraph of G in which every source has an out-degree
833                    // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical
834                    // benefit. (Note: this does not consider register pressure / liveness.)
835                    flat_map<Vertex, unsigned> observed;
836                    bool anyOpportunities = false;
837                    for (const Vertex v : distributable) {
838                        for (auto e : make_iterator_range(in_edges(v, G))) {
839                            const Vertex w = source(e, G);
840                            const auto f = observed.find(w);
841                            if (f == observed.end()) {
842                                observed.emplace(w, 0);
843                            } else {
844                                f->second += 1;
845                                anyOpportunities = true;
846                            }
847                        }
848                    }
849                    if (anyOpportunities) {
850                        for (auto ob : observed) {
851                            if (std::get<1>(ob)) {
852                                const Vertex v = std::get<0>(ob);
853                                for (auto e : make_iterator_range(out_edges(v, G))) {
854                                    const Vertex w = target(e, G);
855                                    if (distributable.count(w)) {
856                                        add_edge(getVertex(G[v], B, M), getVertex(G[w], B, M), B);
857                                    }
858                                }
859                            }
860                        }
861                    }
862                }
863            }
864        }
865    }
866
867    // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
868    if (num_vertices(B) == 0) {
869        return false;
870    }
871
872    printGraph(block, B, "B0");
873
874    // By finding the maximal set of independent bicliques in S,
875
876    maximalIndependentBicliqueSet(B);
877
878
879    printGraph(block, B, "B1");
880
881
882
883    return true;
884}
885
886}
Note: See TracBrowser for help on using the repository browser.