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

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

Temporary check in

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