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

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

Initial stages of a simple boolean equation reassociation pass.

File size: 11.6 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
23void BooleanReassociationPass::scan(PabloFunction & function) {
24    Terminals terminals;
25    for (unsigned i = 0; i != function.getNumOfResults(); ++i) {
26        terminals.push_back(function.getResult(i));
27    }
28    scan(function.getEntryBlock(), std::move(terminals));
29}
30
31void BooleanReassociationPass::scan(PabloBlock & block, Terminals && terminals) {
32
33    using Graph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, PabloAST *>;
34    using Vertex = Graph::vertex_descriptor;
35    using Map = std::unordered_map<PabloAST *, Vertex>;
36    using Queue = std::queue<Vertex>;
37
38    for (Statement * stmt : block) {
39        if (isa<If>(stmt)) {
40            const auto & defs = cast<const If>(stmt)->getDefined();
41            Terminals terminals(defs.begin(), defs.end());
42            scan(cast<If>(stmt)->getBody(), std::move(terminals));
43        } else if (isa<While>(stmt)) {
44            const auto & vars = cast<const While>(stmt)->getVariants();
45            Terminals terminals(vars.begin(), vars.end());
46            scan(cast<While>(stmt)->getBody(), std::move(terminals));
47        }
48    }
49
50    // And, Or and Xor instructions are all associative, commutative and distributive operations. Thus we can
51    // safely rearrange expressions such as "((((a √ b) √ c) √ d) √ e) √ f" into "((a √ b) √ (c √ d)) √ (e √ f)".
52
53    raw_os_ostream out(std::cerr);
54
55    // PabloBuilder builder(block);
56
57    out << "=================================================\n";
58
59    for (;;) {
60
61        Graph G;
62        Map M;
63
64        for (Statement * const term : terminals) {
65            M.insert(std::make_pair(term, add_vertex(term, G)));
66        }
67
68        // Generate a graph depicting the relationships between the terminals
69        for (Statement * const term : terminals) {
70            const Vertex u = M.find(term)->second;
71            for (unsigned i = 0; i != term->getNumOperands(); ++i) {
72                PabloAST * const var = term->getOperand(i);
73                if (LLVM_UNLIKELY(isa<Integer>(var) || isa<String>(var))) {
74                    continue;
75                }
76                auto f = M.find(var);
77                if (f == M.end()) {
78                    Vertex v = add_vertex(var, G);
79                    f = M.insert(std::make_pair(var, v)).first;
80                    if ((isa<And>(var) || isa<Or>(var) || isa<Xor>(var))) {
81                        Queue Q;
82                        // Scan through the use-def chains to locate any chains of rearrangable expressions and their inputs
83                        for (Statement * stmt = cast<Statement>(var); ;) {
84                            for (unsigned i = 0; i != 2; ++i) {
85                                PabloAST * op = stmt->getOperand(i);
86                                auto f = M.find(op);
87                                if (f == M.end()) {
88                                    const auto w = add_vertex(op, G);
89                                    f = M.insert(std::make_pair(op, w)).first;
90                                    if (op->getClassTypeId() == stmt->getClassTypeId() && cast<Statement>(op)->getParent() == &block) {
91                                        Q.push(w);
92                                    }
93                                }
94                                add_edge(f->second, v, G);
95                            }
96                            if (Q.empty()) break;
97                            v = Q.front(); Q.pop();
98                            stmt = cast<Statement>(G[v]);
99                        }
100                    }
101                    add_edge(f->second, u, G);
102                }
103            }
104        }
105
106        // Generate a topological ordering for G; if one of our terminals happens to also be a partial computation of
107        // another terminal, we need to make sure we compute it.
108        std::vector<unsigned> ordering;
109        ordering.reserve(num_vertices(G));
110        topological_sort(G, std::back_inserter(ordering));
111        std::vector<unsigned> component(num_vertices(G));
112
113        for (unsigned i = 0; ;) {
114
115            // Mark which computation component these vertices are in based on their topological (occurence) order.
116            unsigned count = 0;
117            for (auto u : ordering) {
118                unsigned id = 0;
119                if (out_degree(u, G) == 0) {
120                    id = ++count;
121                } else {
122                    for (auto e : make_iterator_range(out_edges(u, G))) {
123                        id = std::max(id, component[target(e, G)]);
124                    }
125                }
126                assert (id && "Topological ordering failed!");
127                component[u] = id;
128            }
129
130            if (count > 1) {
131
132                if (i++ == 0) {
133
134                    out << "digraph G_" << i << " {\n";
135                    unsigned i = 0;
136                    for (auto u : ordering) {
137                        out << "u" << u << " [label=\"";
138                        out << i++ << " : ";
139                        PabloPrinter::print(G[u], out);
140                        out << " (" << component[u] << ')';
141                        out << "\"];\n";
142                    }
143                    for (auto e : make_iterator_range(edges(G))) {
144                        out << "u" << source(e, G) << " -> u" << target(e, G) << ";\n";
145                    }
146                    out << "}\n";
147                    out.flush();
148
149                    out << "*************************************************\n";
150
151                }
152
153                // Cut the graph wherever a computation is crosses a component
154                std::queue<std::pair<Vertex, Vertex>> Q;
155                graph_traits<Graph>::edge_iterator ei, ei_end;
156
157                for (std::tie(ei, ei_end) = edges(G); ei != ei_end; ) {
158                    const Graph::edge_descriptor e = *ei++;
159                    const Vertex u = source(e, G);
160                    const Vertex v = target(e, G);
161                    if (LLVM_UNLIKELY(component[u] != component[v])) {
162                        Q.push(std::make_pair(u, v));
163                        remove_edge(u, v, G);
164                    }
165                }
166
167                // If no edges cross a component, we're done.
168                if (Q.empty()) {
169                    break; // outer for loop
170                }
171
172                for (;;) {
173
174                    Vertex u, v;
175                    std::tie(u, v) = Q.front(); Q.pop();
176
177                    // The vertex belonging to a component with a greater number must come "earlier"
178                    // in the program. Thus it must be computed first.
179
180                    if (component[u] < component[v]) {
181                        std::swap(u, v);
182                    }
183
184                    out << " -- replicating ";
185                    PabloPrinter::print(G[u], out);
186                    out << " for component " << component[v] << '\n';
187                    out.flush();
188
189                    // Replicate u and fix the ordering and component vectors to reflect the change in G.
190                    Vertex w = add_vertex(G[u], G);
191                    ordering.insert(std::find(ordering.begin(), ordering.end(), u), w);
192                    assert (component.size() == w);
193                    component.push_back(component[v]);
194                    add_edge(w, v, G);
195
196                    // However, after we do so, we need to make sure the original source vertex will be a
197                    // sink in G unless it is also an input variable (in which case we'd simply end up with
198                    // extraneous isolated vertex. Otherwise, we need to make further cuts and replications.
199
200                    if (in_degree(u, G) != 0) {
201                        for (auto e : make_iterator_range(out_edges(u, G))) {
202                            Q.push(std::make_pair(source(e, G), target(e, G)));
203                        }
204                        clear_out_edges(u, G);
205                    }
206
207                    if (Q.empty()) {
208                        break;
209                    }
210
211                }
212
213                out << "*************************************************\n";
214
215                continue; // outer for loop
216            }
217            break; // outer for loop
218        }
219
220        out << "digraph X {\n";
221        unsigned i = 0;
222        for (auto u : ordering) {
223            out << "u" << u << " [label=\"";
224            out << i++ << " : ";
225            PabloPrinter::print(G[u], out);
226            out << " (" << component[u] << ')';
227            out << "\"];\n";
228        }
229        for (auto e : make_iterator_range(edges(G))) {
230            out << "u" << source(e, G) << " -> u" << target(e, G) << ";\n";
231        }
232        out << "}\n";
233        out.flush();
234
235
236        // Determine the source variables in this portion of the AST
237        flat_set<PabloAST *> variables;
238
239        for (auto u : make_iterator_range(vertices(G))) {
240            if (in_degree(u, G) == 0) {
241                variables.insert(G[u]);
242            }
243        }
244
245        terminals.clear();
246        for (PabloAST * var : variables) {
247            if (isa<Statement>(var) && cast<Statement>(var)->getParent() == &block) {
248                terminals.push_back(cast<Statement>(var));
249            }
250        }
251
252        if (terminals.empty()) {
253            break;
254        }
255
256        out << "-------------------------------------------------\n";
257
258
259
260
261
262//        if (variables.size() > 3) {
263
264//            circular_buffer<PabloAST *> Q(variables.size());
265
266//            out << "-------------------------------------------------\n";
267
268//            for (auto var : variables) {
269//                Q.push_back(var);
270
271//                out << " -> ";
272//                PabloPrinter::print(var, out); out << '\n';
273
274
275
276//                if (LLVM_LIKELY(isa<Statement>(var))) {
277//                    nextSet.insert(cast<Statement>(var));
278//                }
279//            }
280
281
282
283//            block.setInsertPoint(stmt->getPrevNode());
284//            while (Q.size() > 1) {
285//                PabloAST * e1 = Q.front(); Q.pop_front();
286//                PabloAST * e2 = Q.front(); Q.pop_front();
287//                PabloAST * r = nullptr;
288//                switch (classTypeId) {
289//                    case PabloAST::ClassTypeId::And:
290//                        r = builder.createAnd(e1, e2);
291//                        break;
292//                    case PabloAST::ClassTypeId::Or:
293//                        r = builder.createOr(e1, e2);
294//                        break;
295//                    case PabloAST::ClassTypeId::Xor:
296//                        r = builder.createAnd(e1, e2);
297//                        break;
298//                    default: LLVM_BUILTIN_UNREACHABLE;
299//                }
300//                Q.push_back(r);
301//            }
302//            cast<Statement>(op)->replaceWith(Q.front(), true, true);
303
304//            for (PabloAST * var : variables) {
305//                if (isa<Statement>(var) && cast<Statement>(var)->getParent() == &block) {
306//                    nextSet.insert(cast<Statement>(var));
307//                }
308//            }
309
310//        }
311
312
313
314//        if (nextSet.empty()) {
315//            break;
316//        }
317
318//        out << "-------------------------------------------------\n";
319
320//        terminals.assign(nextSet.begin(), nextSet.end());
321    }
322
323}
324
325BooleanReassociationPass::BooleanReassociationPass()
326{
327
328}
329
330
331}
Note: See TracBrowser for help on using the repository browser.