source: icGREP/icgrep-devel/icgrep/pablo/optimizers/codemotionpass.cpp @ 4927

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

Bug fixes

File size: 9.9 KB
Line 
1#include "codemotionpass.h"
2#include <pablo/codegenstate.h>
3#include <pablo/analysis/pabloverifier.hpp>
4#include <boost/container/flat_set.hpp>
5#include <boost/container/flat_map.hpp>
6#include <boost/graph/adjacency_list.hpp>
7#include <boost/graph/topological_sort.hpp>
8#include <boost/circular_buffer.hpp>
9
10using namespace boost;
11using namespace boost::container;
12
13namespace pablo {
14
15/** ------------------------------------------------------------------------------------------------------------- *
16 * @brief optimize
17 ** ------------------------------------------------------------------------------------------------------------- */
18bool CodeMotionPass::optimize(PabloFunction & function) {
19    CodeMotionPass::movement(function.getEntryBlock());
20    #ifndef NDEBUG
21    PabloVerifier::verify(function, "post-code-motion");
22    #endif
23    return true;
24}
25
26/** ------------------------------------------------------------------------------------------------------------- *
27 * @brief movement
28 ** ------------------------------------------------------------------------------------------------------------- */
29void CodeMotionPass::movement(PabloBlock * const block) {
30    sink(block);
31    for (Statement * stmt : *block) {
32        if (isa<If>(stmt)) {
33            movement(cast<If>(stmt)->getBody());
34        } else if (isa<While>(stmt)) {
35            movement(cast<While>(stmt)->getBody());
36            // TODO: if we analyzed the probability of this loop being executed once, twice, or many times, we could
37            // determine whether hoisting will helpful or harmful to the expected run time.
38            hoistLoopInvariants(cast<While>(stmt));
39        }
40    }
41    reschedule(block);
42}
43
44/** ------------------------------------------------------------------------------------------------------------- *
45 * @brief isSafeToMove
46 ** ------------------------------------------------------------------------------------------------------------- */
47inline static bool isSafeToMove(Statement * stmt) {
48    return !isa<Assign>(stmt) && !isa<Next>(stmt);
49}
50
51/** ------------------------------------------------------------------------------------------------------------- *
52 * @brief calculateDepthToCurrentBlock
53 ** ------------------------------------------------------------------------------------------------------------- */
54inline static unsigned depthTo(const PabloBlock * scope, const PabloBlock * const root) {
55    unsigned depth = 0;
56    while (scope != root) {
57        ++depth;
58        assert (scope);
59        scope = scope->getParent();
60    }
61    return depth;
62}
63
64/** ------------------------------------------------------------------------------------------------------------- *
65 * @brief findScopeUsages
66 ** ------------------------------------------------------------------------------------------------------------- */
67template <class ScopeSet>
68inline bool findScopeUsages(Statement * stmt, ScopeSet & scopeSet, const PabloBlock * const block, const PabloBlock * const blocker) {
69    for (PabloAST * use : stmt->users()) {
70        assert (isa<Statement>(use));
71        PabloBlock * const parent = cast<Statement>(use)->getParent();
72        if (LLVM_LIKELY(parent == block)) {
73            return false;
74        }
75        if (parent != blocker) {
76            scopeSet.insert(parent);
77        }
78    }
79    return true;
80}
81
82/** ------------------------------------------------------------------------------------------------------------- *
83 * @brief isAcceptableTarget
84 ** ------------------------------------------------------------------------------------------------------------- */
85inline bool CodeMotionPass::isAcceptableTarget(Statement * stmt, ScopeSet & scopeSet, const PabloBlock * const block) {
86    // Scan through this statement's users to see if they're all in a nested scope. If so,
87    // find the least common ancestor of the scope blocks. If it is not the current scope,
88    // then we can sink the instruction.
89    if (isa<If>(stmt)) {
90        for (Assign * def : cast<If>(stmt)->getDefined()) {
91            if (!findScopeUsages(def, scopeSet, block, cast<If>(stmt)->getBody())) {
92                return false;
93            }
94        }
95    } else if (isa<While>(stmt)) {
96        for (Next * var : cast<While>(stmt)->getVariants()) {
97            if (escapes(var) && !findScopeUsages(var, scopeSet, block, cast<While>(stmt)->getBody())) {
98                return false;
99            }
100        }
101    } else if (isSafeToMove(stmt)) {
102        return findScopeUsages(stmt, scopeSet, block, nullptr);
103    }
104    return false;
105}
106
107/** ------------------------------------------------------------------------------------------------------------- *
108 * @brief sink
109 ** ------------------------------------------------------------------------------------------------------------- */
110inline void CodeMotionPass::sink(PabloBlock * const block) {
111    ScopeSet scopes;
112    Statement * stmt = block->back(); // note: reverse AST traversal
113    while (stmt) {
114        Statement * prevNode = stmt->getPrevNode();
115        if (isAcceptableTarget(stmt, scopes, block)) {
116            assert (scopes.size() > 0);
117            while (scopes.size() > 1) {
118                // Find the LCA of both scopes then add the LCA back to the list of scopes.
119                PabloBlock * scope1 = scopes.back(); scopes.pop_back();
120                unsigned depth1 = depthTo(scope1, block);
121
122                PabloBlock * scope2 = scopes.back(); scopes.pop_back();
123                unsigned depth2 = depthTo(scope2, block);
124
125                // If one of these scopes is nested deeper than the other, scan upwards through
126                // the scope tree until both scopes are at the same depth.
127                while (depth1 > depth2) {
128                    scope1 = scope1->getParent();
129                    --depth1;
130                }
131                while (depth1 < depth2) {
132                    scope2 = scope2->getParent();
133                    --depth2;
134                }
135
136                // Then iteratively step backwards until we find a matching set of scopes; this
137                // must be the LCA of our original scopes.
138                while (scope1 != scope2) {
139                    assert (scope1 && scope2);
140                    scope1 = scope1->getParent();
141                    scope2 = scope2->getParent();
142                }
143                assert (scope1);
144                // But if the LCA is the current block, we can't sink the statement.
145                if (scope1 == block) {
146                    goto abort;
147                }
148                scopes.push_back(scope1);
149            }
150            assert (scopes.size() == 1);
151            assert (isa<If>(stmt) ? (cast<If>(stmt)->getBody() != scopes.front()) : true);
152            assert (isa<While>(stmt) ? (cast<While>(stmt)->getBody() != scopes.front()) : true);
153            stmt->insertBefore(scopes.front()->front());
154        }
155abort:  scopes.clear();
156        stmt = prevNode;
157    }
158}
159
160/** ------------------------------------------------------------------------------------------------------------- *
161 * @brief hoistWhileLoopInvariants
162 ** ------------------------------------------------------------------------------------------------------------- */
163void CodeMotionPass::hoistLoopInvariants(While * loop) {
164    flat_set<const PabloAST *> loopVariants;
165    for (Next * variant : loop->getVariants()) {
166        loopVariants.insert(variant);
167        loopVariants.insert(variant->getInitial());
168    }
169    Statement * outerNode = loop->getPrevNode();
170    Statement * stmt = loop->getBody()->front();
171    while (stmt) {
172        if (isa<If>(stmt)) {
173            for (Assign * def : cast<If>(stmt)->getDefined()) {
174                loopVariants.insert(def);
175            }
176        } else if (isa<While>(stmt)) {
177            for (Next * var : cast<While>(stmt)->getVariants()) {
178                loopVariants.insert(var);
179            }
180        } else {
181            bool invariant = true;
182            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
183                if (loopVariants.count(stmt->getOperand(i)) != 0) {
184                    invariant = false;
185                    break;
186                }
187            }
188            if (LLVM_UNLIKELY(invariant)) {
189                Statement * next = stmt->getNextNode();
190                stmt->insertAfter(outerNode);
191                outerNode = stmt;
192                stmt = next;
193            } else {
194                loopVariants.insert(stmt);
195                stmt = stmt->getNextNode();
196            }
197        }
198    }
199}
200
201/** ------------------------------------------------------------------------------------------------------------- *
202 * @brief reschedule
203 ** ------------------------------------------------------------------------------------------------------------- */
204void CodeMotionPass::reschedule(PabloBlock * const block) {
205
206//    using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, Statement *>;
207//    using Vertex = Graph::vertex_descriptor;
208//    using Map = flat_map<Statement *, Vertex>;
209
210//    const unsigned size = std::distance(block->begin(), block->end());
211
212//    Graph G(size);
213//    Map M;
214
215//    M.reserve(size);
216
217//    unsigned i = 0;
218//    for (Statement * stmt : *block) {
219//        G[i] = stmt;
220//        M.emplace(stmt, i);
221//        ++i;
222//    }
223
224//    i = 0;
225//    for (Statement * stmt : *block) {
226//        for (PabloAST * user : stmt->users()) {
227//            if (isa<Statement>(user)) {
228//                Statement * use = cast<Statement>(user);
229//                PabloBlock * parent = use->getParent();
230//                while (parent) {
231//                    if (parent == block) {
232//                        break;
233//                    }
234//                    use = parent->getBranch();
235//                    parent = parent->getParent();
236//                }
237//                auto f = M.find(use);
238//                assert (f != M.end());
239//                add_edge(i, f->second, G);
240//            }
241//        }
242//        ++i;
243//    }
244
245//    circular_buffer<Vertex> ordering(size);
246//    std::vector<unsigned> cumulativeDependencies;
247//    topological_sort(G, std::back_inserter(ordering));
248   
249
250
251}
252
253}
Note: See TracBrowser for help on using the repository browser.