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

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

Temporary check in

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