source: icGREP/icgrep-devel/icgrep/pablo/optimizers/schedulingprepass.cpp @ 5160

Last change on this file since 5160 was 5160, checked in by nmedfort, 3 years ago

Initial work for incorporating Types into Pablo AST.

File size: 11.9 KB
Line 
1#include "schedulingprepass.h"
2#include <pablo/codegenstate.h>
3#include <boost/circular_buffer.hpp>
4#include <boost/container/flat_set.hpp>
5#include <boost/container/flat_map.hpp>
6#include <pablo/analysis/pabloverifier.hpp>
7#include <boost/graph/adjacency_list.hpp>
8#include <unordered_map>
9
10#include <pablo/printer_pablos.h>
11#include <iostream>
12
13using namespace boost;
14using namespace boost::container;
15
16namespace pablo {
17
18using DependencyGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, std::vector<PabloAST *>>;
19using Vertex = DependencyGraph::vertex_descriptor;
20using Map = std::unordered_map<const PabloAST *, Vertex>;
21using ReadyPair = std::pair<unsigned, Vertex>;
22using ReadySet = std::vector<ReadyPair>;
23
24using weight_t = unsigned;
25using TypeId = PabloAST::ClassTypeId;
26using LiveSet = flat_set<Vertex>;
27
28void schedule(PabloBlock * const block);
29
30/** ------------------------------------------------------------------------------------------------------------- *
31 * @brief printGraph
32 ** ------------------------------------------------------------------------------------------------------------- */
33template <typename DependencyGraph>
34static void printGraph(const DependencyGraph & G, const std::vector<unsigned> & ordering, const std::string name, raw_ostream & out) {
35    out << "*******************************************\n";
36    out << "digraph " << name << " {\n";
37    for (auto u : make_iterator_range(vertices(G))) {
38        if (G[u].empty()) {
39            continue;
40        }
41        out << "v" << u << " [label=\"" << ordering[u] << " : ";
42        bool newLine = false;
43        for (PabloAST * expr : G[u]) {
44            if (newLine) {
45                out << '\n';
46            }
47            newLine = true;
48            if (isa<Statement>(expr)) {
49                PabloPrinter::print(cast<Statement>(expr), out);
50            } else {
51                PabloPrinter::print(expr, out);
52            }
53        }
54        out << "\"];\n";
55    }
56    for (auto e : make_iterator_range(edges(G))) {
57        out << "v" << source(e, G) << " -> v" << target(e, G);
58        out << ";\n";
59    }
60
61    out << "}\n\n";
62    out.flush();
63}
64
65/** ------------------------------------------------------------------------------------------------------------- *
66 * @brief resolveNestedUsages
67 ** ------------------------------------------------------------------------------------------------------------- */
68static void resolveNestedUsages(Statement * const root, Statement * const stmt, DependencyGraph & G, Map & M, PabloBlock * const block) {
69    for (PabloAST * use : stmt->users()) {
70        if (LLVM_LIKELY(isa<Statement>(use))) {
71            const PabloBlock * scope = cast<Statement>(use)->getParent();
72            if (scope != block) {
73                for (PabloBlock * prior = scope->getPredecessor (); prior; scope = prior, prior = prior->getPredecessor ()) {
74                    if (prior == block) {
75                        assert (scope->getBranch());
76                        auto v = M.find(scope->getBranch());
77                        assert (v != M.end());
78                        auto u = M.find(root);
79                        assert (u != M.end());
80                        if (u->second != v->second) {
81                            add_edge(u->second, v->second, G);
82                        }
83                        break;
84                    }
85                }
86            }
87        }
88    }
89}
90
91/** ------------------------------------------------------------------------------------------------------------- *
92 * @brief resolveNestedUsages
93 ** ------------------------------------------------------------------------------------------------------------- */
94static void computeDependencyGraph(DependencyGraph & G, PabloBlock * const block) {
95    Map M;
96    // Construct a use-def graph G representing the current scope block
97    for (Statement * stmt : *block) {
98        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
99            schedule(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
100        }
101        const auto u = add_vertex({stmt}, G);
102        M.insert(std::make_pair(stmt, u));
103        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
104            const PabloAST * const op = stmt->getOperand(i);
105            if (LLVM_LIKELY(isa<Statement>(op))) {
106                const PabloBlock * scope = cast<Statement>(op)->getParent();
107                // Was this instruction computed by this block?
108                if (scope == block) {
109                    auto v = M.find(op);
110                    assert (v != M.end());
111                    assert (v->second != u);
112                    add_edge(v->second, u, G);
113                } else if (isa<Assign>(op) || isa<Next>(op)) {
114                    // if this statement isn't an Assign or Next node, it cannot come from a nested scope
115                    // unless the function is invalid.
116                    for (PabloBlock * prior = scope->getPredecessor (); prior; scope = prior, prior = prior->getPredecessor ()) {
117                        // Was this instruction computed by a nested block?
118                        if (prior == block) {
119                            assert (scope->getBranch());
120                            auto v = M.find(scope->getBranch());
121                            assert (v != M.end());
122                            if (v->second != u) {
123                                add_edge(v->second, u, G);
124                            }
125                            break;
126                        }
127                    }
128                }
129            }
130        }
131    }
132    // Do a second pass to ensure that we've accounted for any nested usage of an If or While statement
133    for (Statement * stmt : *block) {
134        if (LLVM_UNLIKELY(isa<If>(stmt))) {
135            for (Assign * def : cast<If>(stmt)->getDefined()) {
136                resolveNestedUsages(stmt, def, G, M, block);
137            }
138        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
139            for (Next * var : cast<While>(stmt)->getVariants()) {
140                resolveNestedUsages(stmt, var, G, M, block);
141            }
142        } else {
143            resolveNestedUsages(stmt, stmt, G, M, block);
144        }
145    }
146    // Contract the graph
147    for (;;) {
148        bool done = true;
149        for (const Vertex u : make_iterator_range(vertices(G))) {
150            if (out_degree(u, G) == 1) {
151                const Vertex v = target(*(out_edges(u, G).first), G);
152                G[v].insert(G[v].begin(), G[u].begin(), G[u].end());
153                for (auto e : make_iterator_range(in_edges(u, G))) {
154                    add_edge(source(e, G), v, G);
155                }
156                G[u].clear();
157                clear_vertex(u, G);
158                done = false;
159            }
160        }
161        if (done) {
162            break;
163        }
164    }
165
166
167}
168
169/** ------------------------------------------------------------------------------------------------------------- *
170 * @brief computeGraphOrdering
171 ** ------------------------------------------------------------------------------------------------------------- */
172std::vector<weight_t> computeGraphOrdering(const DependencyGraph & G) {
173    // Determine the bottom-up ordering of G
174    std::vector<weight_t> ordering(num_vertices(G));
175    circular_buffer<Vertex> Q(num_vertices(G));
176    for (const Vertex u : make_iterator_range(vertices(G))) {
177        if (out_degree(u, G) == 0 && G[u].size() > 0) {
178            ordering[u] = 1;
179            Q.push_back(u);
180        }
181    }
182    while (!Q.empty()) {
183        const Vertex u = Q.front();
184        Q.pop_front();
185        assert (ordering[u] > 0);
186        for (const auto ei : make_iterator_range(in_edges(u, G))) {
187            const Vertex v = source(ei, G);
188            if (ordering[v] == 0) {
189                weight_t weight = 0;
190                bool ready = true;
191                for (const auto ej : make_iterator_range(out_edges(v, G))) {
192                    const Vertex w = target(ej, G);
193                    const weight_t t = ordering[w];
194                    if (t == 0) {
195                        ready = false;
196                        break;
197                    }
198                    weight = std::max(weight, t);
199                }
200                if (ready) {
201                    assert (weight < std::numeric_limits<unsigned>::max());
202                    assert (weight > 0);
203                    ordering[v] = weight + 1;
204                    Q.push_back(v);
205                }
206            }
207        }
208    }
209    return ordering;
210}
211
212/** ------------------------------------------------------------------------------------------------------------- *
213 * @brief schedule
214 ** ------------------------------------------------------------------------------------------------------------- */
215void schedule(PabloBlock * const block) {
216    DependencyGraph G;
217    computeDependencyGraph(G, block);
218    std::vector<weight_t> ordering = computeGraphOrdering(G);
219
220//    raw_os_ostream out(std::cerr);
221//    printGraph(G, ordering, "G", out);
222
223    // Compute the initial ready set
224    ReadySet readySet;
225    for (const Vertex u : make_iterator_range(vertices(G))) {
226        if (in_degree(u, G) == 0 && G[u].size() > 0) {
227            readySet.emplace_back(ordering[u], u);
228        }
229    }
230
231    struct {
232        bool operator()(const ReadyPair a, const ReadyPair b) {
233            return std::get<0>(a) > std::get<0>(b);
234        }
235    } readyComparator;
236
237    std::sort(readySet.begin(), readySet.end(), readyComparator);
238
239    block->setInsertPoint(nullptr);
240
241    // Rewrite the AST
242    while (!readySet.empty()) {
243        DependencyGraph::degree_size_type killed = 0;
244        auto chosen = readySet.begin();
245        for (auto ri = readySet.begin(); ri != readySet.end(); ++ri) {
246            DependencyGraph::degree_size_type kills = 0;
247            for (auto e : make_iterator_range(in_edges(ri->first, G))) {
248                if (out_degree(source(e, G), G) == 1) {
249                    ++kills;
250                }
251            }
252            if (kills > killed) {
253                chosen = ri;
254                killed = kills;
255            }
256        }
257
258        Vertex u; unsigned weight;
259        std::tie(weight, u) = *chosen;
260        readySet.erase(chosen);
261        clear_in_edges(u, G);
262
263        assert ("Error: SchedulingPrePass is attempting to reschedule a statement!" && (weight > 0));
264
265        // insert the statement then mark it as written ...
266        for (PabloAST * expr : G[u]) {
267            block->insert(cast<Statement>(expr));
268        }
269
270        ordering[u] = 0;
271        // Now check whether any new instructions are ready
272        for (auto ei : make_iterator_range(out_edges(u, G))) {
273            bool ready = true;
274            const auto v = target(ei, G);
275            for (auto ej : make_iterator_range(in_edges(v, G))) {
276                if (ordering[source(ej, G)]) {
277                    ready = false;
278                    break;
279                }
280            }
281            if (ready) {
282                auto entry = std::make_pair(ordering[v], v);
283                auto position = std::lower_bound(readySet.begin(), readySet.end(), entry, readyComparator);
284                readySet.insert(position, entry);
285                assert (std::is_sorted(readySet.cbegin(), readySet.cend(), readyComparator));
286            }
287        }
288    }
289
290}
291
292/** ------------------------------------------------------------------------------------------------------------- *
293 * @brief schedule
294 ** ------------------------------------------------------------------------------------------------------------- */
295void schedule(PabloFunction & function) {
296    schedule(function.getEntryBlock());
297}
298
299/** ------------------------------------------------------------------------------------------------------------- *
300 * @brief optimize
301 ** ------------------------------------------------------------------------------------------------------------- */
302bool SchedulingPrePass::optimize(PabloFunction & function) {
303    schedule(function);
304    #ifndef NDEBUG
305    PabloVerifier::verify(function, "post-scheduling-prepass");
306    #endif
307    return true;
308
309}
310
311
312}
Note: See TracBrowser for help on using the repository browser.