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

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

Work on coalescing algorithm + minor changes.

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