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

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

Work on lowering + minor bug fixes.

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