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

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

More work on the boolean reassociation pass.

File size: 16.3 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    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) ? 1 : 0);
47}
48
49/** ------------------------------------------------------------------------------------------------------------- *
50 * @brief scan
51 ** ------------------------------------------------------------------------------------------------------------- */
52void BooleanReassociationPass::scan(PabloBlock & block, Terminals && terminals) {
53
54    using Graph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, PabloAST *>;
55    using Vertex = Graph::vertex_descriptor;
56    using Map = std::unordered_map<PabloAST *, Vertex>;
57    using VertexQueue = std::queue<Vertex>;
58    using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
59
60    for (Statement * stmt : block) {
61        if (isa<If>(stmt)) {
62            const auto & defs = cast<const If>(stmt)->getDefined();
63            Terminals 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            Terminals terminals(vars.begin(), vars.end());
68            scan(cast<While>(stmt)->getBody(), std::move(terminals));
69        }
70    }
71
72    // And, Or and Xor instructions are all associative, commutative and distributive operations. Thus we can
73    // safely rearrange expressions such as "((((a √ b) √ c) √ d) √ e) √ f" into "((a √ b) √ (c √ d)) √ (e √ f)".
74
75    raw_os_ostream out(std::cerr);
76
77    // PabloBuilder builder(block);
78
79    out << "=================================================\n";
80
81    for (;;) {
82
83        Graph G;
84        Map M;
85
86        for (Statement * const term : terminals) {
87            M.insert(std::make_pair(term, add_vertex(term, G)));
88        }
89
90        // Generate a graph depicting the relationships between the terminals
91        for (Statement * const term : terminals) {
92            const Vertex u = M.find(term)->second;
93            for (unsigned i = 0; i != term->getNumOperands(); ++i) {
94                PabloAST * const var = term->getOperand(i);
95                if (LLVM_UNLIKELY(isa<Integer>(var) || isa<String>(var))) {
96                    continue;
97                }
98                auto f = M.find(var);
99                if (f == M.end()) {
100                    Vertex v = add_vertex(var, G);
101                    f = M.insert(std::make_pair(var, v)).first;
102                    if ((isa<And>(var) || isa<Or>(var) || isa<Xor>(var))) {
103                        VertexQueue Q;
104                        // Scan through the use-def chains to locate any chains of rearrangable expressions and their inputs
105                        for (Statement * stmt = cast<Statement>(var); ;) {
106                            for (unsigned i = 0; i != 2; ++i) {
107                                PabloAST * op = stmt->getOperand(i);
108                                auto f = M.find(op);
109                                if (f == M.end()) {
110                                    const auto w = add_vertex(op, G);
111                                    f = M.insert(std::make_pair(op, w)).first;
112                                    if (op->getClassTypeId() == stmt->getClassTypeId() && cast<Statement>(op)->getParent() == &block) {
113                                        Q.push(w);
114                                    }
115                                }
116                                add_edge(f->second, v, G);
117                            }
118                            if (Q.empty()) break;
119                            v = Q.front(); Q.pop();
120                            stmt = cast<Statement>(G[v]);
121                        }
122                    }
123                    add_edge(f->second, u, G);
124                }
125            }
126        }
127
128        // Generate a topological ordering for G; if one of our terminals happens to also be a partial computation of
129        // another terminal, we need to make sure we compute it.
130        std::vector<unsigned> ordering;
131        ordering.reserve(num_vertices(G));
132        topological_sort(G, std::back_inserter(ordering));
133        std::vector<unsigned> component(num_vertices(G));
134
135        // unsigned i = 0;
136
137        for (;;) {
138
139            // Mark which computation component these vertices are in based on their topological (occurence) order.
140            unsigned count = 0;
141            for (auto u : ordering) {
142                unsigned id = 0;
143                // If this one of our original terminals or a sink in G, it is the root of a new component.
144                if (u < terminals.size() || out_degree(u, G) == 0) {
145                    id = ++count;
146                } else {
147                    for (auto e : make_iterator_range(out_edges(u, G))) {
148                        id = std::max(id, component[target(e, G)]);
149                    }
150                }
151                assert (id && "Topological ordering failed!");
152                component[u] = id;
153            }
154
155            if (count > 1) {
156
157//                if (i++ == 0) {
158
159//                    out << "digraph G_" << i << " {\n";
160//                    unsigned i = 0;
161//                    for (auto u : ordering) {
162//                        out << "u" << u << " [label=\"";
163//                        out << i++ << " : ";
164//                        PabloPrinter::print(G[u], out);
165//                        out << " (" << component[u] << ')';
166//                        out << "\"];\n";
167//                    }
168//                    for (auto e : make_iterator_range(edges(G))) {
169//                        out << "u" << source(e, G) << " -> u" << target(e, G) << ";\n";
170//                    }
171//                    out << "}\n";
172//                    out.flush();
173
174//                    out << "*************************************************\n";
175
176//                }
177
178                // Cut the graph wherever a computation crosses a component
179                EdgeQueue Q;
180                graph_traits<Graph>::edge_iterator ei, ei_end;
181
182                for (std::tie(ei, ei_end) = edges(G); ei != ei_end; ) {
183                    const Graph::edge_descriptor e = *ei++;
184                    const Vertex u = source(e, G);
185                    const Vertex v = target(e, G);
186                    if (LLVM_UNLIKELY(component[u] != component[v])) {
187                        Q.push(std::make_pair(u, v));
188                        remove_edge(u, v, G);
189                    }
190                }
191
192                // If no edges cross a component, we're done.
193                if (Q.empty()) {
194                    break; // outer for loop
195                }
196
197                for (;;) {
198
199                    Vertex u, v;
200                    std::tie(u, v) = Q.front(); Q.pop();
201
202                    // The vertex belonging to a component with a greater number must come "earlier"
203                    // in the program. By replicating it, this ensures it's computed as an output of
204                    // one component and used as an input of another.
205
206                    if (component[u] < component[v]) {
207                        std::swap(u, v);
208                    }
209
210//                    out << " -- replicating ";
211//                    PabloPrinter::print(G[u], out);
212//                    out << " for component " << component[v] << '\n';
213//                    out.flush();
214
215                    // Replicate u and fix the ordering and component vectors to reflect the change in G.
216                    Vertex w = add_vertex(G[u], G);
217                    ordering.insert(std::find(ordering.begin(), ordering.end(), u), w);
218                    assert (component.size() == w);
219                    component.push_back(component[v]);
220                    add_edge(w, v, G);
221
222                    // However, after we do so, we need to make sure the original source vertex will be a
223                    // sink in G unless it is also an input variable (in which case we'd simply end up with
224                    // extraneous isolated vertex. Otherwise, we need to make further cuts and replications.
225
226                    if (in_degree(u, G) != 0) {
227                        for (auto e : make_iterator_range(out_edges(u, G))) {
228                            Q.push(std::make_pair(source(e, G), target(e, G)));
229                        }
230                        clear_out_edges(u, G);
231                    }
232
233                    if (Q.empty()) {
234                        break;
235                    }
236
237                }
238
239//                out << "*************************************************\n";
240
241                continue; // outer for loop
242            }
243            break; // outer for loop
244        }
245
246        out << "digraph X {\n";
247        unsigned i = 0;
248        for (auto u : ordering) {
249            out << "u" << u << " [label=\"";
250            out << i++ << " : ";
251            PabloPrinter::print(G[u], out);
252            out << " (" << component[u] << ')';
253            out << "\"];\n";
254        }
255        for (auto e : make_iterator_range(edges(G))) {
256            out << "u" << source(e, G) << " -> u" << target(e, G) << ";\n";
257        }
258        out << "}\n";
259        out.flush();
260
261        // Scan through the graph in reverse order so that we find all subexpressions first
262        for (auto ui = ordering.rbegin(), ui_end = ordering.rend(); ui != ui_end; ++ui) {
263            const Vertex u = *ui;
264            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
265
266                PabloAST * expr = G[u];
267
268
269                std::array<Vertex, 3> root;
270                unsigned count = 0;
271
272                if (isa<And>(expr) || isa<Or>(expr) || isa<Xor>(expr)) {
273                    root[count++] = u;
274                } else {
275                    for (auto e : make_iterator_range(in_edges(u, G))) {
276                        root[count++] = source(e, G);
277                    }
278                }
279
280                for (unsigned i = 0; i != count; ++i) {
281                    // While we're collecting our variable set V, keep track of the maximum path length L.
282                    // If L == ceil(log2(|V|)), then this portion of the AST is already optimal.
283
284                    flat_map<Vertex, unsigned> L;
285                    flat_set<PabloAST *> V;
286                    VertexQueue Q;
287
288                    Vertex v = root[i];
289                    unsigned maxPathLength = 0;
290                    L.emplace(v, 0);
291                    for (;;) {
292                        if (in_degree(v, G) == 0) {
293                            V.insert(G[v]);
294                        } else {
295                            const auto l = L[v] + 1;
296                            maxPathLength = std::max(maxPathLength, l);
297                            for (auto e : make_iterator_range(in_edges(v, G))) {
298                                const Vertex w = source(e, G);
299                                auto f = L.find(w);
300                                if (LLVM_LIKELY(f == L.end())) {
301                                    L.emplace(w, l);
302                                } else {
303                                    f->second = std::max(f->second, l);
304                                }
305                                Q.push(w);
306                            }
307                        }
308                        if (Q.empty()) {
309                            break;
310                        }
311                        v = Q.front();
312                        Q.pop();
313                    }
314
315                    // Should we optimize this portion of the AST?
316                    if (maxPathLength != ceil_log2(V.size())) {
317
318
319
320                    }
321
322
323                }
324
325
326
327
328
329            }
330        }
331
332        // if (u < terminals.size() || out_degree(u, G) == 0) {
333
334        for (auto e : make_iterator_range(edges(G))) {
335            Vertex u = target(e, G);
336            Vertex v = source(e, G);
337            if (u >= terminals.size() && out_degree(v, G) != 0 && G[u]->getClassTypeId() != G[v]->getClassTypeId()) {
338                throw std::runtime_error("Illegal graph generated!");
339            }
340        }
341
342        // Determine the source variables of the next "layer" of the AST
343        flat_set<Statement *> nextSet;
344        for (auto u : ordering) {
345            if (in_degree(u, G) == 0) {
346                PabloAST * const var = G[u];
347                if (LLVM_LIKELY(isa<Statement>(var) && cast<Statement>(var)->getParent() == &block)) {
348                    nextSet.insert(cast<Statement>(var));
349                }
350            } 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.
351                PabloAST * const var = G[u];
352                if (LLVM_LIKELY(isa<Statement>(var) && cast<Statement>(var)->getParent() == &block)) {
353                    nextSet.erase(cast<Statement>(var));
354                }
355            }
356        }
357
358        if (nextSet.empty()) {
359            break;
360        }
361
362        terminals.assign(nextSet.begin(), nextSet.end());
363
364        out << "-------------------------------------------------\n";
365
366
367
368
369
370//        if (variables.size() > 3) {
371
372//            circular_buffer<PabloAST *> Q(variables.size());
373
374//            out << "-------------------------------------------------\n";
375
376//            for (auto var : variables) {
377//                Q.push_back(var);
378
379//                out << " -> ";
380//                PabloPrinter::print(var, out); out << '\n';
381
382
383
384//                if (LLVM_LIKELY(isa<Statement>(var))) {
385//                    nextSet.insert(cast<Statement>(var));
386//                }
387//            }
388
389
390
391//            block.setInsertPoint(stmt->getPrevNode());
392//            while (Q.size() > 1) {
393//                PabloAST * e1 = Q.front(); Q.pop_front();
394//                PabloAST * e2 = Q.front(); Q.pop_front();
395//                PabloAST * r = nullptr;
396//                switch (classTypeId) {
397//                    case PabloAST::ClassTypeId::And:
398//                        r = builder.createAnd(e1, e2);
399//                        break;
400//                    case PabloAST::ClassTypeId::Or:
401//                        r = builder.createOr(e1, e2);
402//                        break;
403//                    case PabloAST::ClassTypeId::Xor:
404//                        r = builder.createAnd(e1, e2);
405//                        break;
406//                    default: LLVM_BUILTIN_UNREACHABLE;
407//                }
408//                Q.push_back(r);
409//            }
410//            cast<Statement>(op)->replaceWith(Q.front(), true, true);
411
412//            for (PabloAST * var : variables) {
413//                if (isa<Statement>(var) && cast<Statement>(var)->getParent() == &block) {
414//                    nextSet.insert(cast<Statement>(var));
415//                }
416//            }
417
418//        }
419
420
421
422//        if (nextSet.empty()) {
423//            break;
424//        }
425
426//        out << "-------------------------------------------------\n";
427
428//        terminals.assign(nextSet.begin(), nextSet.end());
429    }
430
431}
432
433BooleanReassociationPass::BooleanReassociationPass()
434{
435
436}
437
438
439}
Note: See TracBrowser for help on using the repository browser.