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

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

Temporary check in

File size: 14.4 KB
Line 
1#include "booleanreassociationpass.h"
2#include <pablo/printer_pablos.h>
3#include <boost/container/flat_set.hpp>
4#include <boost/container/flat_map.hpp>
5#include <iostream>
6#include <boost/circular_buffer.hpp>
7#include <queue>
8#include <pablo/builder.hpp>
9#include <boost/graph/adjacency_list.hpp>
10#include <boost/graph/topological_sort.hpp>
11
12using namespace boost;
13using namespace boost::container;
14
15namespace pablo {
16
17bool BooleanReassociationPass::optimize(PabloFunction & function) {
18    BooleanReassociationPass brp;
19    brp.scan(function);
20    return true;
21}
22
23/** ------------------------------------------------------------------------------------------------------------- *
24 * @brief scan
25 ** ------------------------------------------------------------------------------------------------------------- */
26void BooleanReassociationPass::scan(PabloFunction & function) {
27    Terminals terminals;
28    for (unsigned i = 0; i != function.getNumOfResults(); ++i) {
29        terminals.push_back(function.getResult(i));
30    }
31    return scan(function.getEntryBlock(), std::move(terminals));
32}
33
34/** ------------------------------------------------------------------------------------------------------------- *
35 * @brief is_power_of_2
36 * @param n an integer
37 ** ------------------------------------------------------------------------------------------------------------- */
38static inline bool is_power_of_2(const size_t n) {
39    return ((n & (n - 1)) == 0);
40}
41
42/** ------------------------------------------------------------------------------------------------------------- *
43 * @brief log2_plus_one
44 ** ------------------------------------------------------------------------------------------------------------- */
45static inline size_t ceil_log2(const size_t n) {
46    return std::log2<size_t>(n) + (is_power_of_2(n) ? 0 : 1);
47}
48
49/** ------------------------------------------------------------------------------------------------------------- *
50 * @brief isACD
51 ** ------------------------------------------------------------------------------------------------------------- */
52static inline bool isaBooleanOperation(const PabloAST * const expr) {
53    switch (expr->getClassTypeId()) {
54        case PabloAST::ClassTypeId::And:
55        case PabloAST::ClassTypeId::Or:
56        case PabloAST::ClassTypeId::Xor:
57            return true;
58        default:
59            return false;
60    }
61}
62
63using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
64using Vertex = Graph::vertex_descriptor;
65
66/** ------------------------------------------------------------------------------------------------------------- *
67 * @brief isCutNecessary
68 ** ------------------------------------------------------------------------------------------------------------- */
69static inline bool isCutNecessary(const Vertex u, const Vertex v, const Graph & G, const std::vector<unsigned> & component) {
70    // Either this edge crosses a component boundary or the operations performed by the vertices differs, we need to cut
71    // the graph here and generate two partial equations.
72    if (LLVM_UNLIKELY(component[u] != component[v])) {
73        return true;
74    } else if (LLVM_UNLIKELY(out_degree(v, G) && in_degree(u, G) && G[u]->getClassTypeId() != G[v]->getClassTypeId())) {
75        return true;
76    }
77    return false;
78}
79
80/** ------------------------------------------------------------------------------------------------------------- *
81 * @brief scan
82 ** ------------------------------------------------------------------------------------------------------------- */
83void BooleanReassociationPass::scan(PabloBlock & block, Terminals && terminals) {
84
85    using Map = std::unordered_map<PabloAST *, Vertex>;
86    using VertexQueue = std::queue<Vertex>;
87    using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
88
89    PabloBuilder builder(block);
90
91    for (Statement * stmt : block) {
92        if (isa<If>(stmt)) {
93            const auto & defs = cast<const If>(stmt)->getDefined();
94            Terminals terminals(defs.begin(), defs.end());
95            scan(cast<If>(stmt)->getBody(), std::move(terminals));
96        } else if (isa<While>(stmt)) {
97            const auto & vars = cast<const While>(stmt)->getVariants();
98            Terminals terminals(vars.begin(), vars.end());
99            scan(cast<While>(stmt)->getBody(), std::move(terminals));
100        } else {
101            builder.record(stmt);
102        }
103    }
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
108    bool modifiedAST = false;
109
110    for (;;) {
111
112        Graph G;
113        Map M;
114
115        // Generate a graph depicting the relationships between the terminals. If the original terminals
116        // cannot be optimized with this algorithm bypass them in favour of their operands.
117
118        VertexQueue Q;
119
120        for (Statement * const term : terminals) {
121            if (isaBooleanOperation(term)) {
122                if (LLVM_LIKELY(M.count(term) == 0)) {
123                    const auto v = add_vertex(term, G);
124                    M.insert(std::make_pair(term, v));
125                    Q.push(v);
126                }
127            } else {
128                for (unsigned i = 0; i != term->getNumOperands(); ++i) {
129                    PabloAST * const op = term->getOperand(i);
130                    if (LLVM_LIKELY(isa<Statement>(op) && M.count(op) == 0)) {
131                        const auto v = add_vertex(op, G);
132                        M.insert(std::make_pair(op, v));
133                        Q.push(v);
134                    }
135                }
136            }
137        }
138
139        for (;;) {
140            const Vertex u = Q.front(); Q.pop();
141            if (isaBooleanOperation(G[u])) {
142                // Scan through the use-def chains to locate any chains of rearrangable expressions and their inputs
143                Statement * stmt = cast<Statement>(G[u]);
144                for (unsigned i = 0; i != 2; ++i) {
145                    PabloAST * op = stmt->getOperand(i);
146                    auto f = M.find(op);
147                    if (f == M.end()) {
148                        const auto v = add_vertex(op, G);
149                        f = M.insert(std::make_pair(op, v)).first;
150                        if (op->getClassTypeId() == stmt->getClassTypeId() && cast<Statement>(op)->getParent() == &block) {
151                            Q.push(v);
152                        }
153                    }
154                    add_edge(f->second, u, G);
155                }
156            }
157            if (Q.empty()) {
158                break;
159            }
160        }
161
162        // Generate a topological ordering for G; if one of our terminals happens to also be a partial computation of
163        // another terminal, we need to make sure we compute it as an independent subexpression.
164        std::vector<unsigned> ordering;
165        ordering.reserve(num_vertices(G));
166        topological_sort(G, std::back_inserter(ordering));
167        std::vector<unsigned> component(num_vertices(G));
168
169        for (;;) {
170
171            // Mark which computation component these vertices are in based on their topological (occurence) order.
172            unsigned components = 0;
173            for (auto u : ordering) {
174                unsigned id = 0;
175                // If this is a sink in G, it is the root of a new component.
176                if (out_degree(u, G) == 0) {
177                    id = ++components;
178                } else {
179                    for (auto e : make_iterator_range(out_edges(u, G))) {
180                        id = std::max(id, component[target(e, G)]);
181                    }
182                }
183                assert (id && "Topological ordering failed!");
184                component[u] = id;
185            }
186
187            // Cut the graph wherever a computation crosses a component or whenever we need to cut the graph because
188            // the instructions corresponding to the pair of nodes differs.
189            EdgeQueue Q;
190            graph_traits<Graph>::edge_iterator ei, ei_end;
191
192            for (std::tie(ei, ei_end) = edges(G); ei != ei_end; ) {
193                const Graph::edge_descriptor e = *ei++;
194                const Vertex u = source(e, G);
195                const Vertex v = target(e, G);
196                if (LLVM_UNLIKELY(isCutNecessary(u, v, G, component))) {
197                    Q.push(std::make_pair(u, v));
198                    remove_edge(u, v, G);
199                }
200            }
201
202            // If no cuts are necessary, we're done.
203            if (Q.empty()) {
204                break;
205            }
206
207            for (;;) {
208
209                Vertex u, v;
210                std::tie(u, v) = Q.front(); Q.pop();
211
212                // The vertex belonging to a component with a greater number must come "earlier"
213                // in the program. By replicating it, this ensures it's computed as an output of
214                // one component and used as an input of another.
215
216                if (component[u] < component[v]) {
217                    std::swap(u, v);
218                }
219
220                // Replicate u and fix the ordering and component vectors to reflect the change in G.
221                Vertex w = add_vertex(G[u], G);
222                ordering.insert(std::find(ordering.begin(), ordering.end(), u), w);
223                assert (component.size() == w);
224                component.push_back(component[v]);
225                add_edge(w, v, G);
226
227                // However, after we do so, we need to make sure the original source vertex will be a
228                // sink in G unless it is also an input variable (in which case we'd simply end up with
229                // extraneous isolated vertex. Otherwise, we need to make further cuts and replications.
230
231                if (in_degree(u, G) != 0) {
232                    for (auto e : make_iterator_range(out_edges(u, G))) {
233                        Q.push(std::make_pair(source(e, G), target(e, G)));
234                    }
235                    clear_out_edges(u, G);
236                }
237
238                if (Q.empty()) {
239                    break;
240                }
241
242            }
243        }
244
245        // Scan through the graph in reverse order so that we find all subexpressions first
246        for (const Vertex u : ordering) {
247            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
248
249                // While we're collecting our variable set V, keep track of the maximum path length L.
250                // If L == ceil(log2(|V|)), then this portion of the AST is already optimal.
251
252                flat_map<Vertex, unsigned> L;
253                flat_set<PabloAST *> V;
254                VertexQueue Q;
255
256                Vertex v = u;
257                unsigned maxPathLength = 0;
258                L.emplace(v, 0);
259                for (;;) {                   
260                    if (in_degree(v, G) == 0) {
261                        V.insert(G[v]);
262                    } else {
263                        const auto l = L[v] + 1;
264                        maxPathLength = std::max(maxPathLength, l);
265                        for (auto e : make_iterator_range(in_edges(v, G))) {
266                            const Vertex w = source(e, G);
267                            auto f = L.find(w);
268                            if (LLVM_LIKELY(f == L.end())) {
269                                L.emplace(w, l);
270                            } else {
271                                f->second = std::max(f->second, l);
272                            }
273                            Q.push(w);
274                        }
275                    }
276                    if (Q.empty()) {
277                        break;
278                    }
279                    v = Q.front();
280                    Q.pop();
281                }
282
283                // Should we optimize this portion of the AST?
284                if (maxPathLength > ceil_log2(V.size())) {
285                    Statement * stmt = cast<Statement>(G[u]);
286                    circular_buffer<PabloAST *> Q(V.size());
287                    for (PabloAST * var : V) {
288                        Q.push_back(var);
289                    }
290
291                    block.setInsertPoint(stmt->getPrevNode());
292                    if (isa<And>(stmt)) {
293                        while (Q.size() > 1) {
294                            PabloAST * e1 = Q.front(); Q.pop_front();
295                            PabloAST * e2 = Q.front(); Q.pop_front();
296                            Q.push_back(builder.createAnd(e1, e2));
297                        }
298                    } else if (isa<Or>(stmt)) {
299                        while (Q.size() > 1) {
300                            PabloAST * e1 = Q.front(); Q.pop_front();
301                            PabloAST * e2 = Q.front(); Q.pop_front();
302                            Q.push_back(builder.createOr(e1, e2));
303                        }
304                    } else { assert(isa<Xor>(stmt));
305                        while (Q.size() > 1) {
306                            PabloAST * e1 = Q.front(); Q.pop_front();
307                            PabloAST * e2 = Q.front(); Q.pop_front();
308                            Q.push_back(builder.createXor(e1, e2));
309                        }
310                    }
311                    stmt->replaceAllUsesWith(Q.front());
312                    modifiedAST = true;
313                }
314            }
315        }
316
317        // Determine the source variables of the next "layer" of the AST
318        flat_set<Statement *> nextSet;
319        for (auto u : ordering) {
320            if (in_degree(u, G) == 0) {
321                PabloAST * const var = G[u];
322                if (LLVM_LIKELY(isa<Statement>(var) && cast<Statement>(var)->getParent() == &block)) {
323                    nextSet.insert(cast<Statement>(var));
324                }
325            } else if (out_degree(u, G) == 0) { // an input may also be the output of some subgraph of G. We don't need to reevaluate it.
326                PabloAST * const var = G[u];
327                if (LLVM_LIKELY(isa<Statement>(var) && cast<Statement>(var)->getParent() == &block)) {
328                    nextSet.erase(cast<Statement>(var));
329                }
330            }
331        }
332
333        if (nextSet.empty()) {
334            break;
335        }
336
337        terminals.assign(nextSet.begin(), nextSet.end());
338    }
339
340    // If we modified the AST, we likely left dead code in it. Go through and remove any from this block.
341    if (modifiedAST) {
342        Statement * stmt = block.front();
343        while (stmt) {
344            if (stmt->getNumUses() == 0 && !(isa<If>(stmt) || isa<While>(stmt))){
345                stmt = stmt->eraseFromParent(true);
346            } else {
347                stmt = stmt->getNextNode();
348            }
349        }
350    }
351}
352
353BooleanReassociationPass::BooleanReassociationPass()
354{
355
356}
357
358
359}
Note: See TracBrowser for help on using the repository browser.