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

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

Initial work on adding types to PabloAST and mutable Var objects.

File size: 11.6 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, PabloAST * const expr, DependencyGraph & G, Map & M, PabloBlock * const block) {
69    for (PabloAST * use : expr->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)) {
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<Branch>(stmt))) {
135            for (Var * var : cast<Branch>(stmt)->getEscaped()) {
136                resolveNestedUsages(stmt, var, G, M, block);
137            }
138        } else {
139            resolveNestedUsages(stmt, stmt, G, M, block);
140        }
141    }
142    // Contract the graph
143    for (;;) {
144        bool done = true;
145        for (const Vertex u : make_iterator_range(vertices(G))) {
146            if (out_degree(u, G) == 1) {
147                const Vertex v = target(*(out_edges(u, G).first), G);
148                G[v].insert(G[v].begin(), G[u].begin(), G[u].end());
149                for (auto e : make_iterator_range(in_edges(u, G))) {
150                    add_edge(source(e, G), v, G);
151                }
152                G[u].clear();
153                clear_vertex(u, G);
154                done = false;
155            }
156        }
157        if (done) {
158            break;
159        }
160    }
161
162
163}
164
165/** ------------------------------------------------------------------------------------------------------------- *
166 * @brief computeGraphOrdering
167 ** ------------------------------------------------------------------------------------------------------------- */
168std::vector<weight_t> computeGraphOrdering(const DependencyGraph & G) {
169    // Determine the bottom-up ordering of G
170    std::vector<weight_t> ordering(num_vertices(G));
171    circular_buffer<Vertex> Q(num_vertices(G));
172    for (const Vertex u : make_iterator_range(vertices(G))) {
173        if (out_degree(u, G) == 0 && G[u].size() > 0) {
174            ordering[u] = 1;
175            Q.push_back(u);
176        }
177    }
178    while (!Q.empty()) {
179        const Vertex u = Q.front();
180        Q.pop_front();
181        assert (ordering[u] > 0);
182        for (const auto ei : make_iterator_range(in_edges(u, G))) {
183            const Vertex v = source(ei, G);
184            if (ordering[v] == 0) {
185                weight_t weight = 0;
186                bool ready = true;
187                for (const auto ej : make_iterator_range(out_edges(v, G))) {
188                    const Vertex w = target(ej, G);
189                    const weight_t t = ordering[w];
190                    if (t == 0) {
191                        ready = false;
192                        break;
193                    }
194                    weight = std::max(weight, t);
195                }
196                if (ready) {
197                    assert (weight < std::numeric_limits<unsigned>::max());
198                    assert (weight > 0);
199                    ordering[v] = weight + 1;
200                    Q.push_back(v);
201                }
202            }
203        }
204    }
205    return ordering;
206}
207
208/** ------------------------------------------------------------------------------------------------------------- *
209 * @brief schedule
210 ** ------------------------------------------------------------------------------------------------------------- */
211void schedule(PabloBlock * const block) {
212    DependencyGraph G;
213    computeDependencyGraph(G, block);
214    std::vector<weight_t> ordering = computeGraphOrdering(G);
215
216//    raw_os_ostream out(std::cerr);
217//    printGraph(G, ordering, "G", out);
218
219    // Compute the initial ready set
220    ReadySet readySet;
221    for (const Vertex u : make_iterator_range(vertices(G))) {
222        if (in_degree(u, G) == 0 && G[u].size() > 0) {
223            readySet.emplace_back(ordering[u], u);
224        }
225    }
226
227    struct {
228        bool operator()(const ReadyPair a, const ReadyPair b) {
229            return std::get<0>(a) > std::get<0>(b);
230        }
231    } readyComparator;
232
233    std::sort(readySet.begin(), readySet.end(), readyComparator);
234
235    block->setInsertPoint(nullptr);
236
237    // Rewrite the AST
238    while (!readySet.empty()) {
239        DependencyGraph::degree_size_type killed = 0;
240        auto chosen = readySet.begin();
241        for (auto ri = readySet.begin(); ri != readySet.end(); ++ri) {
242            DependencyGraph::degree_size_type kills = 0;
243            for (auto e : make_iterator_range(in_edges(ri->first, G))) {
244                if (out_degree(source(e, G), G) == 1) {
245                    ++kills;
246                }
247            }
248            if (kills > killed) {
249                chosen = ri;
250                killed = kills;
251            }
252        }
253
254        Vertex u; unsigned weight;
255        std::tie(weight, u) = *chosen;
256        readySet.erase(chosen);
257        clear_in_edges(u, G);
258
259        assert ("Error: SchedulingPrePass is attempting to reschedule a statement!" && (weight > 0));
260
261        // insert the statement then mark it as written ...
262        for (PabloAST * expr : G[u]) {
263            block->insert(cast<Statement>(expr));
264        }
265
266        ordering[u] = 0;
267        // Now check whether any new instructions are ready
268        for (auto ei : make_iterator_range(out_edges(u, G))) {
269            bool ready = true;
270            const auto v = target(ei, G);
271            for (auto ej : make_iterator_range(in_edges(v, G))) {
272                if (ordering[source(ej, G)]) {
273                    ready = false;
274                    break;
275                }
276            }
277            if (ready) {
278                auto entry = std::make_pair(ordering[v], v);
279                auto position = std::lower_bound(readySet.begin(), readySet.end(), entry, readyComparator);
280                readySet.insert(position, entry);
281                assert (std::is_sorted(readySet.cbegin(), readySet.cend(), readyComparator));
282            }
283        }
284    }
285
286}
287
288/** ------------------------------------------------------------------------------------------------------------- *
289 * @brief schedule
290 ** ------------------------------------------------------------------------------------------------------------- */
291void schedule(PabloFunction & function) {
292    schedule(function.getEntryBlock());
293}
294
295/** ------------------------------------------------------------------------------------------------------------- *
296 * @brief optimize
297 ** ------------------------------------------------------------------------------------------------------------- */
298bool SchedulingPrePass::optimize(PabloFunction & function) {
299    schedule(function);
300    #ifndef NDEBUG
301    PabloVerifier::verify(function, "post-scheduling-prepass");
302    #endif
303    return true;
304
305}
306
307
308}
Note: See TracBrowser for help on using the repository browser.