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

Last change on this file since 5512 was 5512, checked in by nmedfort, 2 years ago

Fix for last check in

File size: 12.7 KB
Line 
1#include "schedulingprepass.h"
2
3#include <pablo/pablo_kernel.h>
4#include <pablo/codegenstate.h>
5#include <pablo/ps_assign.h>
6#include <pablo/pe_var.h>
7#include <pablo/branch.h>
8#ifndef NDEBUG
9#include <pablo/analysis/pabloverifier.hpp>
10#endif
11#include <boost/container/flat_set.hpp>
12#include <boost/graph/adjacency_list.hpp>
13#include <random>
14#include <unordered_map>
15
16#include <llvm/Support/raw_ostream.h>
17
18
19
20
21using namespace llvm;
22using namespace boost;
23using namespace boost::container;
24
25namespace pablo {
26
27using IndexPair = std::pair<unsigned, Statement *>;
28using Graph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
29using Vertex = Graph::vertex_descriptor;
30using Map = std::unordered_map<const PabloAST *, Vertex>;
31using ReadyPair = std::pair<Vertex, size_t>;
32
33struct SchedulingPrePassContainer {
34
35    void run(PabloBlock * const block) {
36        // traverse to the inner-most branch first
37        for (Statement * stmt : *block) {
38            if (isa<Branch>(stmt)) {
39                run(cast<Branch>(stmt)->getBody());
40            }
41        }
42        // starting with the inner-most scope(s) first, attempt to schedule the statements to
43        // minimize the number of simulaneously live variables.
44        schedule(block);
45    }
46
47protected:
48
49    /** ------------------------------------------------------------------------------------------------------------- *
50     * @brief schedule
51     ** ------------------------------------------------------------------------------------------------------------- */
52    void schedule(PabloBlock * const block) {
53        build_data_dependency_dag(block);
54        initialize_process();
55        initialize_probabilities();
56
57        unsigned count = 0;
58        std::vector<size_t> W;
59        W.reserve(num_vertices(G));
60        for (;;) {
61            ready_sort();
62            const auto u = choose_ready(++count);
63            queue_to_ready(u);
64            if (LLVM_UNLIKELY(R.empty())) {
65                break;
66            }
67            update_liveness(u);
68            W.push_back(get_live_weight());
69        }
70
71        const auto m = W.size() / 2;
72        std::nth_element(W.begin(), W.begin() + m, W.end());
73
74        errs() << "median_live_weight: " << W[m] << "\n";
75
76
77
78//        std::sort(I.begin(), I.end(), [](const IndexPair & A, const IndexPair & B){
79//            return std::get<0>(A) < std::get<0>(B);
80//        });
81
82//        block->setInsertPoint(nullptr);
83//        for (const auto & p : I) {
84//            Statement * stmt = std::get<1>(p);
85//            assert (std::get<0>(p) > 0);
86//            assert (stmt->getParent() == block);
87//            block->insert(stmt);
88//        }
89//        assert (block->getInsertPoint() == block->back());
90
91        I.clear();
92        G.clear();
93        L.clear();
94    }
95
96    void build_data_dependency_dag(PabloBlock * const block) {
97        assert (M.empty());
98        for (Statement * stmt : *block) {
99            const auto u = find(stmt);
100            if (isa<Assign>(stmt)) {
101                addDominatedUsers(u, cast<Assign>(stmt), block);
102            } else if (isa<Branch>(stmt)) {
103                addEscapedUsers(u, cast<Branch>(stmt), block);
104            } else {
105                addUsers(u, stmt, block);
106            }
107        }
108        M.clear();
109    }
110
111    void addUsers(const Vertex u, Statement * const stmt, PabloBlock * const block) {
112        for (PabloAST * use : stmt->users()) {
113            if (LLVM_LIKELY(isa<Statement>(use))) {
114                Statement * user = cast<Statement>(use);
115                while (user->getParent() != block) {
116                    PabloBlock * const parent = user->getParent();
117                    assert (parent);
118                    user = parent->getBranch();
119                    assert (user);
120                }
121                assert (strictly_dominates(stmt, user));
122                add_edge(u, find(user), G);
123            }
124        }
125    }
126
127    void addEscapedUsers(const Vertex u, Branch * const br, PabloBlock * const block) {
128        for (Var * var : br->getEscaped()) {
129            for (PabloAST * use : var->users()) {
130                if (LLVM_LIKELY(isa<Statement>(use))) {
131                    Statement * user = cast<Statement>(use);
132                    for (;;) {
133                        if (user->getParent() == block) {
134                            if (LLVM_LIKELY(isa<Assign>(user) ? dominates(br, user) : (br != user))) {
135                                add_edge(u, find(user), G);
136                            }
137                            break;
138                        }
139                        PabloBlock * const parent = user->getParent();
140                        assert (parent);
141                        user = parent->getBranch();
142                        if (LLVM_UNLIKELY(user == nullptr)) {
143                            break;
144                        }
145                    }
146                }
147            }
148        }
149    }
150
151    void addDominatedUsers(const Vertex u, Assign * const assignment, PabloBlock * const block) {
152        for (PabloAST * use : assignment->getVariable()->users()) {
153            if (LLVM_LIKELY(isa<Statement>(use))) {
154                Statement * user = cast<Statement>(use);
155                for (;;) {
156                    if (user->getParent() == block) {
157                        if (user != assignment) {
158                            const auto v = find(user);
159                            if (strictly_dominates(assignment, user)) {
160                                add_edge(u, v, G);
161                            } else {
162                                assert (strictly_dominates(user, assignment));
163                                // although there is not actually a dependency here, a prior value
164                                // must be read by statement v prior to assignment u
165                                add_edge(v, u, G);
166                            }
167                        }
168                        break;
169                    }
170                    PabloBlock * const parent = user->getParent();
171                    assert (parent);
172                    user = parent->getBranch();
173                    if (LLVM_UNLIKELY(user == nullptr)) {
174                        break;
175                    }
176                }
177            }
178        }
179    }
180
181    void printGraph(const std::string name, raw_ostream & out) {
182        out << "\ndigraph " << name << " {\n";
183        for (auto u : make_iterator_range(vertices(G))) {
184            out << "v" << u << " [label=\"" << u << " : ";
185            std::get<1>(I[u])->print(out);
186            out << "  " << std::get<0>(I[u]) << "\"];\n";
187        }
188        for (auto e : make_iterator_range(edges(G))) {
189            out << "v" << source(e, G) << " -> v" << target(e, G) << ";\n";
190        }
191        out << "}\n\n";
192        out.flush();
193    }
194
195    void initialize_process() {
196        assert ("Ready set was not cleared prior to initializing!" && R.empty());
197        std::vector<Vertex> Q;
198        Q.reserve(64);
199        for (auto u : make_iterator_range(vertices(G))) {
200            if (out_degree(u, G) == 0) {
201                Q.push_back(u);
202            } else if (in_degree(u, G) == 0) {
203                R.push_back(u);
204            }
205        }
206
207        // perform a transitive reduction of G to remove the unnecessary dependency analysis work
208        // within the genetic algorithm search process
209
210        const auto n = num_vertices(G);
211
212        std::vector<flat_set<Vertex>> reachability(n);
213        flat_set<Vertex> pending;
214
215        for (;;) {
216            const auto u = Q.back();
217            Q.pop_back();
218
219            flat_set<Vertex> & D = reachability[u];
220
221            assert (D.empty());
222
223            // initially we do not immediately consider any adjacent vertices reachable
224            for (auto e : make_iterator_range(out_edges(u, G))) {
225                const auto v = target(e, G);
226                const auto & R = reachability[v];
227                assert (R.count(v) == 0);
228                D.insert(R.begin(), R.end());
229            }
230
231            // so that if one of our outgoing targets is already reachable, we can remove it.
232            remove_out_edge_if(u, [&D, this](Graph::edge_descriptor e) {
233
234                // TODO: if we remove this edge, add the liveness weight of statement u to the
235                // target since the "liveness" of u is transitively implied.
236
237                return D.count(target(e, G)) != 0;
238            }, G);
239
240            // afterwards we insert any remaining outgoing targets to finalize our reachable set
241            for (auto e : make_iterator_range(out_edges(u, G))) {
242                D.insert(target(e, G));
243            }
244
245            // add any incoming source to our pending set
246            for (auto e : make_iterator_range(in_edges(u, G))) {
247                pending.insert(source(e, G));
248            }
249
250            // so that when we exhaust the queue, we can repopulate it with the next 'layer' of the graph
251            if (LLVM_UNLIKELY(Q.empty())) {
252                if (LLVM_UNLIKELY(pending.empty())) {
253                    break;
254                }
255                for (auto v : pending) {
256                    bool ready = true;
257                    for (auto e : make_iterator_range(out_edges(v, G))) {
258                        const auto w = target(e, G);
259                        if (LLVM_UNLIKELY(out_degree(w, G) != 0 && reachability[w].empty())) {
260                            ready = false;
261                            break;
262                        }
263                    }
264                    if (ready) {
265                        Q.push_back(v);
266                    }
267                }
268                pending.clear();
269                assert (!Q.empty());
270            }
271
272        }
273    }
274
275    void initialize_probabilities() {
276        std::random_device rd;
277        std::default_random_engine rand(rd());
278        std::uniform_int_distribution<size_t> dist(std::numeric_limits<size_t>::min(), std::numeric_limits<size_t>::max());
279        const auto n = num_vertices(G);
280        P.resize(n);
281        std::generate_n(P.begin(), n, [&dist, &rand](){ return dist(rand); });
282    }
283
284    void ready_sort() {
285        std::sort(R.begin(), R.end(), [this](const Vertex u, const Vertex v){ return P[u] < P[v]; });
286    }
287
288    Vertex choose_ready(const unsigned index) {
289        assert (!R.empty());
290        const auto u = R.back();
291        assert (std::get<0>(I[u]) == 0);
292        std::get<0>(I[u]) = index;
293        R.pop_back();
294        return u;
295    }
296
297    void update_liveness(const Vertex u) {
298        // determine which statements were killed (i.e., u was its last unscheduled user) or
299        // killable (i.e., u is the penultimate unscheduled user)
300        for (auto ei : make_iterator_range(in_edges(u, G))) {
301            const auto v = source(ei, G);
302            const auto f = L.find(v);
303            if (f != L.end()) {
304                bool killed = true;
305                for (auto ej : make_iterator_range(out_edges(v, G))) {
306                    if (std::get<0>(I[target(ej, G)]) == 0) {
307                        killed = false;
308                        break;
309                    }
310                }
311                if (killed) {
312                    L.erase(f);
313                }
314            }
315        }
316        L.insert(u);
317    }
318
319    size_t get_live_weight() {
320        return L.size();
321    }
322
323    void queue_to_ready(const Vertex u) {
324        // determine which statements are now ready (i.e., u was its last unscheduled input)
325        for (auto ei : make_iterator_range(out_edges(u, G))) {
326            const auto v = target(ei, G);
327            bool ready = true;
328            for (auto ej : make_iterator_range(in_edges(v, G))) {
329                if (std::get<0>(I[source(ej, G)]) == 0) {
330                    ready = false;
331                    break;
332                }
333            }
334            if (ready) {
335                R.push_back(v);
336            }
337        }
338    }
339
340
341
342private:
343
344    Vertex find(Statement * expr) {
345        const auto f = M.find(expr);
346        if (f == M.end()) {
347            const auto u = add_vertex(G);
348            assert (u == I.size());
349            I.emplace_back(0, expr);
350            M.emplace(expr, u);
351            return u;
352        } else {
353            return f->second;
354        }
355    }
356
357private:
358
359    std::vector<Vertex> R;      // ready
360    flat_set<Vertex> L;         // live variables
361    std::vector<IndexPair> I;   // index
362    std::vector<size_t> P;
363
364    Graph G;
365    Map M;
366};
367
368
369/** ------------------------------------------------------------------------------------------------------------- *
370 * @brief optimize
371 ** ------------------------------------------------------------------------------------------------------------- */
372bool SchedulingPrePass::optimize(PabloKernel * const kernel) {
373    #ifdef NDEBUG
374    report_fatal_error("DistributivePass is unsupported");
375    #else
376    SchedulingPrePassContainer S;
377    S.run(kernel->getEntryBlock());
378    PabloVerifier::verify(kernel, "post-scheduling-prepass");
379    return true;
380    #endif
381}
382
383
384}
Note: See TracBrowser for help on using the repository browser.