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

Last change on this file was 5836, checked in by nmedfort, 13 months ago

Added PabloBlock/Builder? createScope() methods + minor code changes.

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