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

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

Removed dummy nodes from the reassociation pass and have edges pointing to the if/while node instead to allow for proper topological ordering.

File size: 23.9 KB
Line 
1#include "booleanreassociationpass.h"
2#include <boost/container/flat_set.hpp>
3#include <boost/container/flat_map.hpp>
4#include <boost/circular_buffer.hpp>
5#include <boost/graph/adjacency_list.hpp>
6#include <boost/graph/topological_sort.hpp>
7#include <pablo/optimizers/pablo_simplifier.hpp>
8#include <queue>
9#include <iostream>
10#include <pablo/printer_pablos.h>
11
12
13using namespace boost;
14using namespace boost::container;
15
16namespace pablo {
17
18using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
19using Vertex = Graph::vertex_descriptor;
20using VertexQueue = circular_buffer<Vertex>;
21using Map = std::unordered_map<PabloAST *, Vertex>;
22using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
23
24static void redistributeAST(Graph & G);
25
26/** ------------------------------------------------------------------------------------------------------------- *
27 * @brief optimize
28 ** ------------------------------------------------------------------------------------------------------------- */
29bool BooleanReassociationPass::optimize(PabloFunction & function) {
30    BooleanReassociationPass brp;
31    brp.resolveScopes(function);
32    brp.processScopes(function);
33    Simplifier::optimize(function);
34    return true;
35}
36
37/** ------------------------------------------------------------------------------------------------------------- *
38 * @brief resolveScopes
39 ** ------------------------------------------------------------------------------------------------------------- */
40inline void BooleanReassociationPass::resolveScopes(PabloFunction &function) {
41    resolveScopes(function.getEntryBlock());
42}
43
44/** ------------------------------------------------------------------------------------------------------------- *
45 * @brief resolveScopes
46 ** ------------------------------------------------------------------------------------------------------------- */
47void BooleanReassociationPass::resolveScopes(PabloBlock & block) {
48    for (Statement * stmt : block) {
49        if (isa<If>(stmt) || isa<While>(stmt)) {
50            PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
51            mResolvedScopes.emplace(&nested, stmt);
52            resolveScopes(nested);
53        }
54    }
55}
56
57
58/** ------------------------------------------------------------------------------------------------------------- *
59 * @brief scan
60 ** ------------------------------------------------------------------------------------------------------------- */
61inline void BooleanReassociationPass::processScopes(PabloFunction & function) {
62    std::vector<Statement *> terminals;
63    for (unsigned i = 0; i != function.getNumOfResults(); ++i) {
64        terminals.push_back(function.getResult(i));
65    }
66    processScopes(function.getEntryBlock(), std::move(terminals));
67}
68
69/** ------------------------------------------------------------------------------------------------------------- *
70 * @brief scan
71 ** ------------------------------------------------------------------------------------------------------------- */
72void BooleanReassociationPass::processScopes(PabloBlock & block, std::vector<Statement *> && terminals) {
73    processScope(block, std::move(terminals));
74    for (Statement * stmt : block) {
75        if (isa<If>(stmt)) {
76            const auto & defs = cast<const If>(stmt)->getDefined();
77            std::vector<Statement *> terminals(defs.begin(), defs.end());
78            processScopes(cast<If>(stmt)->getBody(), std::move(terminals));
79        } else if (isa<While>(stmt)) {
80            const auto & vars = cast<const While>(stmt)->getVariants();
81            std::vector<Statement *> terminals(vars.begin(), vars.end());
82            processScopes(cast<While>(stmt)->getBody(), std::move(terminals));
83        }
84    }
85}
86
87/** ------------------------------------------------------------------------------------------------------------- *
88 * @brief is_power_of_2
89 * @param n an integer
90 ** ------------------------------------------------------------------------------------------------------------- */
91static inline bool is_power_of_2(const size_t n) {
92    return ((n & (n - 1)) == 0);
93}
94
95/** ------------------------------------------------------------------------------------------------------------- *
96 * @brief log2_plus_one
97 ** ------------------------------------------------------------------------------------------------------------- */
98static inline size_t ceil_log2(const size_t n) {
99    return std::log2<size_t>(n) + (is_power_of_2(n) ? 0 : 1);
100}
101
102/** ------------------------------------------------------------------------------------------------------------- *
103 * @brief isOptimizable
104 *
105 * And, Or and Xor instructions are all associative, commutative and distributive operations. Thus we can
106 * safely rearrange expressions such as "((((a √ b) √ c) √ d) √ e) √ f" into "((a √ b) √ (c √ d)) √ (e √ f)".
107 ** ------------------------------------------------------------------------------------------------------------- */
108static inline bool isOptimizable(const PabloAST * const expr) {
109    assert (expr);
110    switch (expr->getClassTypeId()) {
111        case PabloAST::ClassTypeId::And:
112        case PabloAST::ClassTypeId::Or:
113        case PabloAST::ClassTypeId::Xor:
114            return true;
115        default:
116            return false;
117    }
118}
119
120/** ------------------------------------------------------------------------------------------------------------- *
121 * @brief inCurrentBlock
122 ** ------------------------------------------------------------------------------------------------------------- */
123static inline bool inCurrentBlock(const Statement * stmt, const PabloBlock & block) {
124    return stmt->getParent() == &block;
125}
126
127static inline bool inCurrentBlock(const PabloAST * expr, const PabloBlock & block) {
128    return isa<Statement>(expr) && inCurrentBlock(cast<Statement>(expr), block);
129}
130
131/** ------------------------------------------------------------------------------------------------------------- *
132 * @brief isCutNecessary
133 ** ------------------------------------------------------------------------------------------------------------- */
134static inline bool isCutNecessary(const Vertex u, const Vertex v, const Graph & G, const std::vector<unsigned> & component) {
135    // Either this edge crosses a component boundary or the operations performed by the vertices differs, we need to cut
136    // the graph here and generate two partial equations.
137    if (LLVM_UNLIKELY(component[u] != component[v])) {
138        return true;
139    } else if (LLVM_UNLIKELY((in_degree(u, G) != 0) && (G[u]->getClassTypeId() != G[v]->getClassTypeId()))) {
140        return true;
141    }
142    return false;
143}
144
145/** ------------------------------------------------------------------------------------------------------------- *
146 * @brief push
147 ** ------------------------------------------------------------------------------------------------------------- */
148static inline void push(const Vertex u, VertexQueue & Q) {
149    if (LLVM_UNLIKELY(Q.full())) {
150        Q.set_capacity(Q.capacity() * 2);
151    }
152    Q.push_back(u);
153    assert (Q.back() == u);
154}
155
156/** ------------------------------------------------------------------------------------------------------------- *
157 * @brief pop
158 ** ------------------------------------------------------------------------------------------------------------- */
159static inline Vertex pop(VertexQueue & Q) {
160    assert (!Q.empty() && "Popping an empty vertex queue");
161    const Vertex u = Q.front();
162    Q.pop_front();
163    return u;
164}
165
166/** ------------------------------------------------------------------------------------------------------------- *
167 * @brief getVertex
168 ** ------------------------------------------------------------------------------------------------------------- */
169static inline Vertex getVertex(PabloAST * expr, Graph & G, Map & M) {
170    const auto f = M.find(expr);
171    if (f != M.end()) {
172        return f->second;
173    }
174    const auto u = add_vertex(expr, G);
175    M.insert(std::make_pair(expr, u));
176    return u;
177}
178
179/** ------------------------------------------------------------------------------------------------------------- *
180 * @brief createTree
181 ** ------------------------------------------------------------------------------------------------------------- */
182static PabloAST * createTree(PabloBlock & block, const PabloAST::ClassTypeId typeId, circular_buffer<PabloAST *> & Q) {
183    while (Q.size() > 1) {
184        PabloAST * e1 = Q.front(); Q.pop_front();
185        PabloAST * e2 = Q.front(); Q.pop_front();
186        PabloAST * expr = nullptr;
187        switch (typeId) {
188            case PabloAST::ClassTypeId::And:
189                expr = block.createAnd(e1, e2); break;
190            case PabloAST::ClassTypeId::Or:
191                expr = block.createOr(e1, e2); break;
192            case PabloAST::ClassTypeId::Xor:
193                expr = block.createXor(e1, e2); break;
194            default: break;
195        }
196        Q.push_back(expr);
197    }
198    PabloAST * r = Q.front();
199    Q.clear();
200    return r;
201}
202
203/** ------------------------------------------------------------------------------------------------------------- *
204 * @brief processScope
205 ** ------------------------------------------------------------------------------------------------------------- */
206void BooleanReassociationPass::processScope(PabloBlock & block, std::vector<Statement *> && terminals) {
207
208    Graph G;
209    summarizeAST(block, std::move(terminals), G);
210    redistributeAST(G);
211
212    raw_os_ostream out(std::cerr);
213    out << "digraph G {\n";
214    for (auto u : make_iterator_range(vertices(G))) {
215        out << "v" << u << " [label=\"";
216        PabloAST * expr = G[u];
217        if (isa<Statement>(expr)) {
218            if (LLVM_UNLIKELY(isa<If>(expr))) {
219                out << "if ";
220                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
221                out << ":";
222            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
223                out << "while ";
224                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
225                out << ":";
226            } else {
227                PabloPrinter::print(cast<Statement>(expr), "", out);
228            }
229        } else {
230            PabloPrinter::print(expr, out);
231        }
232        out << "\"";
233        if (!inCurrentBlock(expr, block)) {
234            out << " style=dashed";
235        }
236        out << "];\n";
237    }
238    for (auto e : make_iterator_range(edges(G))) {
239        out << "v" << source(e, G) << " -> v" << target(e, G) << ";\n";
240    }
241
242    out << "{ rank=same;";
243    for (auto u : make_iterator_range(vertices(G))) {
244        if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
245            out << " v" << u;
246        }
247    }
248    out << "}\n";
249
250    out << "{ rank=same;";
251    for (auto u : make_iterator_range(vertices(G))) {
252        if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
253            out << " v" << u;
254        }
255    }
256    out << "}\n";
257
258    out << "}\n\n";
259    out.flush();
260
261
262
263
264
265}
266
267/** ------------------------------------------------------------------------------------------------------------- *
268 * @brief summarizeAST
269 *
270 * This function scans through a basic block (starting by its terminals) and computes a DAG in which any sequences
271 * of AND, OR or XOR functions are "flattened" and allowed to have any number of inputs. This allows us to
272 * reassociate them in the most efficient way possible.
273 ** ------------------------------------------------------------------------------------------------------------- */
274void BooleanReassociationPass::summarizeAST(PabloBlock & block, std::vector<Statement *> && terminals, Graph & G) {
275
276    Map M;
277    VertexQueue Q(128);
278    EdgeQueue E;
279
280    for (;;) {
281
282        Graph Gk;
283        Map Mk;
284
285        // Generate a graph depicting the relationships between the terminals. If the original terminals
286        // cannot be optimized with this algorithm bypass them in favour of their operands. If those cannot
287        // be optimized, they'll be left as the initial terminals for the next "layer" of the AST.
288
289        for (Statement * term : terminals) {
290            if (LLVM_LIKELY(Mk.count(term) == 0)) {
291                // add or find this terminal in our global graph
292                Vertex x = getVertex(term, G, M);
293                if (inCurrentBlock(term, block)) {
294                    if (isOptimizable(term)) {
295                        const Vertex u = add_vertex(term, Gk);
296                        Mk.insert(std::make_pair(term, u));
297                        push(u, Q);
298                        continue;
299                    }
300                } else if (isa<Assign>(term) || isa<Next>(term)) {
301                    // If this is an Assign (Next) node whose operand does not originate from the current block
302                    // then check to see if there is an If (While) node that does.
303                    Statement * branch = nullptr;
304                    if (isa<Assign>(term)) {
305                        for (PabloAST * user : term->users()) {
306                            if (isa<If>(user)) {
307                                const If * ifNode = cast<If>(user);
308                                if (inCurrentBlock(ifNode, block)) {
309                                    const auto & defs = ifNode->getDefined();
310                                    if (LLVM_LIKELY(std::find(defs.begin(), defs.end(), cast<Assign>(term)) != defs.end())) {
311                                        branch = cast<Statement>(user);
312                                        break;
313                                    }
314                                }
315                            }
316                        }
317                    } else { // if (isa<Next>(term))
318                        for (PabloAST * user : term->users()) {
319                            if (isa<While>(user)) {
320                                const While * whileNode = cast<While>(user);
321                                if (inCurrentBlock(whileNode, block)) {
322                                    const auto & vars = whileNode->getVariants();
323                                    if (LLVM_LIKELY(std::find(vars.begin(), vars.end(), cast<Next>(term)) != vars.end())) {
324                                        branch = cast<Statement>(user);
325                                        break;
326                                    }
327                                }
328                            }
329                        }
330                    }
331
332                    // If we didn't find a branch, then the Assign (Next) node must have come from a preceeding
333                    // block. Just skip it for now.
334                    if (branch == nullptr) {
335                        continue;
336                    }
337
338                    // Otherwise add the branch to G and test its operands rather than the original terminal
339                    const Vertex z = getVertex(branch, G, M);
340                    add_edge(z, x, G);
341                    x = z;
342                    term = branch;
343                }
344
345                for (unsigned i = 0; i != term->getNumOperands(); ++i) {
346                    PabloAST * const op = term->getOperand(i);
347                    if (LLVM_LIKELY(inCurrentBlock(op, block))) {
348                        const Vertex y = getVertex(op, G, M);
349                        add_edge(y, x, G);
350                        if (LLVM_LIKELY(Mk.count(op) == 0)) {
351                            const Vertex v = add_vertex(op, Gk);
352                            Mk.insert(std::make_pair(op, v));
353                            push(v, Q);
354                        }
355                    }
356                }
357            }
358        }
359
360        if (LLVM_UNLIKELY(Q.empty())) {
361            break;
362        }
363
364        for (;;) {
365            const Vertex u = pop(Q);
366            if (isOptimizable(Gk[u])) {
367                Statement * stmt = cast<Statement>(Gk[u]);
368                // If any user of this statement is not in the current block, determine the outermost If/While node
369                // that contains this statement within and add an edge from this statement to it to denote both the
370                // topological ordering necessary and that this statement must be computed.
371                for (PabloAST * user : stmt->users()) {
372                    if (LLVM_LIKELY(isa<Statement>(user))) {
373                        PabloBlock * parent = cast<Statement>(user)->getParent();
374                        if (LLVM_UNLIKELY(parent != &block)) {
375                            while (parent->getParent() != &block) {
376                                parent = parent->getParent();
377                            }
378                            if (LLVM_UNLIKELY(parent == nullptr)) {
379                                throw std::runtime_error("Could not locate nested scope block!");
380                            }
381                            const auto f = mResolvedScopes.find(parent);
382                            if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
383                                throw std::runtime_error("Failed to resolve scope block!");
384                            }
385                            add_edge(u, getVertex(f->second, Gk, Mk), Gk);
386                        }
387                    }
388                }
389                // Scan through the use-def chains to locate any chains of rearrangable expressions and their inputs
390                for (unsigned i = 0; i != 2; ++i) {
391                    PabloAST * op = stmt->getOperand(i);
392                    auto f = Mk.find(op);
393                    if (f == Mk.end()) {
394                        const Vertex v = add_vertex(op, Gk);
395                        f = Mk.insert(std::make_pair(op, v)).first;
396                        if (op->getClassTypeId() == stmt->getClassTypeId() && inCurrentBlock(cast<Statement>(op), block)) {
397                            push(v, Q);
398                        }
399                    }
400                    add_edge(f->second, u, Gk);
401                }
402            }
403            if (Q.empty()) {
404                break;
405            }
406        }
407
408        // Generate a topological ordering for G; if one of our terminals happens to also be a partial computation of
409        // another terminal, we need to make sure we compute it as an independent subexpression.
410        std::vector<unsigned> ordering;
411        ordering.reserve(num_vertices(Gk));
412        topological_sort(Gk, std::back_inserter(ordering));
413        std::vector<unsigned> component(num_vertices(Gk));
414
415        for (;;) {
416
417            // Mark which computation component these vertices are in based on their topological (occurence) order.
418            unsigned components = 0;
419            for (auto u : ordering) {
420                unsigned id = 0;
421                // If this is a sink in G, it is the root of a new component.
422                if (out_degree(u, Gk) == 0) {
423                    id = ++components;
424                } else { // otherwise it belongs to the outermost component.
425                    for (auto e : make_iterator_range(out_edges(u, Gk))) {
426                        id = std::max(id, component[target(e, Gk)]);
427                    }
428                }
429                assert (id && "Topological ordering failed!");
430                component[u] = id;
431            }
432
433            // Cut the graph wherever a computation crosses a component or whenever we need to cut the graph because
434            // the instructions corresponding to the pair of nodes differs.
435            graph_traits<Graph>::edge_iterator ei, ei_end;
436            for (std::tie(ei, ei_end) = edges(Gk); ei != ei_end; ) {
437                const Graph::edge_descriptor e = *ei++;
438                const Vertex u = source(e, Gk);
439                const Vertex v = target(e, Gk);
440                if (LLVM_UNLIKELY(isCutNecessary(u, v, Gk, component))) {
441                    E.push(std::make_pair(u, v));
442                    remove_edge(u, v, Gk);
443                }
444            }
445
446            // If no cuts are necessary, we're done.
447            if (E.empty()) {
448                break;
449            }
450
451            for (;;) {
452
453                Vertex u, v;
454                std::tie(u, v) = E.front(); E.pop();
455
456                // The vertex belonging to a component with a greater number must come "earlier"
457                // in the program. By replicating it, this ensures it's computed as an output of
458                // one component and used as an input of another.
459                if (component[u] < component[v]) {
460                    std::swap(u, v);
461                }
462
463                // Replicate u and fix the ordering and component vectors to reflect the change in Gk.
464                Vertex w = add_vertex(Gk[u], Gk);
465                ordering.insert(std::find(ordering.begin(), ordering.end(), u), w);
466                assert (component.size() == w);
467                component.push_back(component[v]);
468                add_edge(w, v, Gk);
469
470                // However, after we do so, we need to make sure the original source vertex will be a
471                // sink in Gk unless it is also an input variable (in which case we'd simply end up with
472                // extraneous isolated vertex. Otherwise, we need to make further cuts and replications.
473                if (in_degree(u, Gk) != 0) {
474                    for (auto e : make_iterator_range(out_edges(u, Gk))) {
475                        E.push(std::make_pair(source(e, Gk), target(e, Gk)));
476                    }
477                    clear_out_edges(u, Gk);
478                }
479
480                if (E.empty()) {
481                    break;
482                }
483            }
484        }
485
486        // Scan through the graph so that we process the outermost expressions first
487        for (const Vertex u : ordering) {
488            if (LLVM_UNLIKELY(out_degree(u, Gk) == 0)) {
489                // Create a vertex marking the output statement we may end up replacing
490                // and collect the set of source variables in the component
491                const Vertex x = getVertex(Gk[u], G, M);
492                if (LLVM_LIKELY(in_degree(u, Gk) > 0)) {
493                    flat_set<PabloAST *> vars;
494                    flat_set<Vertex> visited;
495                    for (Vertex v = u;;) {
496                        if (in_degree(v, Gk) == 0) {
497                            vars.insert(Gk[v]);
498                        } else {
499                            for (auto e : make_iterator_range(in_edges(v, Gk))) {
500                                const Vertex w = source(e, Gk);
501                                if (LLVM_LIKELY(visited.insert(w).second)) {
502                                    push(w, Q);
503                                }
504                            }
505                        }
506                        if (Q.empty()) {
507                            break;
508                        }
509                        v = pop(Q);
510                    }
511                    for (PabloAST * var : vars) {
512                        add_edge(getVertex(var, G, M), x, G);
513                    }
514                }
515            }
516        }
517
518        // Determine the source variables of the next "layer" of the AST
519        flat_set<Statement *> nextSet;
520        for (auto u : ordering) {
521            if (LLVM_UNLIKELY(in_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) {
522                nextSet.insert(cast<Statement>(Gk[u]));
523            } else if (LLVM_UNLIKELY(out_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) {
524                // some input will also be the output of some subgraph of Gk whenever we cut and
525                // replicated a vertex. We don't need to reevaluate it as part of the next layer.
526                nextSet.erase(cast<Statement>(Gk[u]));
527            }
528        }
529
530        if (LLVM_UNLIKELY(nextSet.empty())) {
531            break;
532        }
533
534        terminals.assign(nextSet.begin(), nextSet.end());
535    }
536}
537
538/** ------------------------------------------------------------------------------------------------------------- *
539 * @brief redistributeAST
540 *
541 * Apply the distribution law to reduce computations whenever possible.
542 ** ------------------------------------------------------------------------------------------------------------- */
543static void redistributeAST(Graph & G) {
544
545}
546
547/** ------------------------------------------------------------------------------------------------------------- *
548 * @brief applyDistributionLaw
549 ** ------------------------------------------------------------------------------------------------------------- */
550BooleanReassociationPass::BooleanReassociationPass()
551{
552
553}
554
555
556}
Note: See TracBrowser for help on using the repository browser.