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

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

Merged PabloFunction? and PabloKernel? classes. Updated projects where necessary.

File size: 7.3 KB
Line 
1#include "codemotionpass.h"
2#include <pablo/pablo_kernel.h>
3#include <pablo/codegenstate.h>
4#include <pablo/analysis/pabloverifier.hpp>
5#include <boost/container/flat_set.hpp>
6// #include <boost/circular_buffer.hpp>
7
8using namespace boost;
9using namespace boost::container;
10
11namespace pablo {
12
13/** ------------------------------------------------------------------------------------------------------------- *
14 * @brief optimize
15 ** ------------------------------------------------------------------------------------------------------------- */
16bool CodeMotionPass::optimize(PabloKernel * kernel) {
17    CodeMotionPass::movement(kernel->getEntryBlock());
18    #ifndef NDEBUG
19    PabloVerifier::verify(kernel, "post-code-motion");
20    #endif
21    return true;
22}
23
24/** ------------------------------------------------------------------------------------------------------------- *
25 * @brief movement
26 ** ------------------------------------------------------------------------------------------------------------- */
27void CodeMotionPass::movement(PabloBlock * const block) {
28    sink(block);
29    for (Statement * stmt : *block) {
30        if (isa<If>(stmt)) {
31            movement(cast<If>(stmt)->getBody());
32        } else if (isa<While>(stmt)) {
33            movement(cast<While>(stmt)->getBody());
34            // TODO: if we analyzed the probability of this loop being executed once, twice, or many times, we could
35            // determine whether hoisting will helpful or harmful to the expected run time.
36            hoistLoopInvariants(cast<While>(stmt));
37        }
38    }
39}
40
41/** ------------------------------------------------------------------------------------------------------------- *
42 * @brief depthTo
43 ** ------------------------------------------------------------------------------------------------------------- */
44inline static unsigned depthTo(const PabloBlock * scope, const PabloBlock * const root) {
45    unsigned depth = 0;
46    while (scope != root) {
47        ++depth;
48        assert (scope);
49        scope = scope->getPredecessor();
50    }
51    return depth;
52}
53
54/** ------------------------------------------------------------------------------------------------------------- *
55 * @brief findScopeUsages
56 ** ------------------------------------------------------------------------------------------------------------- */
57template <class ScopeSet>
58inline bool findScopeUsages(PabloAST * expr, ScopeSet & scopeSet, const PabloBlock * const block, const PabloBlock * const blocker) {
59    for (PabloAST * use : expr->users()) {
60        assert (isa<Statement>(use));
61        PabloBlock * const parent = cast<Statement>(use)->getParent();
62        if (LLVM_LIKELY(parent == block)) {
63            return false;
64        }
65        if (parent != blocker) {
66            scopeSet.insert(parent);
67        }
68    }
69    return true;
70}
71
72/** ------------------------------------------------------------------------------------------------------------- *
73 * @brief isAcceptableTarget
74 ** ------------------------------------------------------------------------------------------------------------- */
75inline bool CodeMotionPass::isAcceptableTarget(Statement * stmt, ScopeSet & scopeSet, const PabloBlock * const block) {
76    // Scan through this statement's users to see if they're all in a nested scope. If so,
77    // find the least common ancestor of the scope blocks. If it is not the current scope,
78    // then we can sink the instruction.
79    assert (scopeSet.empty());
80    if (isa<Branch>(stmt)) {
81        for (Var * def : cast<Branch>(stmt)->getEscaped()) {
82            if (!findScopeUsages(def, scopeSet, block, cast<Branch>(stmt)->getBody())) {
83                return false;
84            }
85        }
86    } else if (!isa<Assign>(stmt)) {
87        return findScopeUsages(stmt, scopeSet, block, nullptr);
88    }
89    return false;
90}
91
92/** ------------------------------------------------------------------------------------------------------------- *
93 * @brief sink
94 ** ------------------------------------------------------------------------------------------------------------- */
95inline void CodeMotionPass::sink(PabloBlock * const block) {
96    ScopeSet scopes;
97    Statement * stmt = block->back(); // note: reverse AST traversal
98    while (stmt) {
99        Statement * prevNode = stmt->getPrevNode();
100        if (isAcceptableTarget(stmt, scopes, block)) {
101            assert (scopes.size() > 0);
102            while (scopes.size() > 1) {
103                // Find the LCA of both scopes then add the LCA back to the list of scopes.
104                PabloBlock * scope1 = scopes.back(); scopes.pop_back();
105                unsigned depth1 = depthTo(scope1, block);
106
107                PabloBlock * scope2 = scopes.back(); scopes.pop_back();
108                unsigned depth2 = depthTo(scope2, block);
109
110                // If one of these scopes is nested deeper than the other, scan upwards through
111                // the scope tree until both scopes are at the same depth.
112                while (depth1 > depth2) {
113                    scope1 = scope1->getPredecessor();
114                    --depth1;
115                }
116                while (depth1 < depth2) {
117                    scope2 = scope2->getPredecessor();
118                    --depth2;
119                }
120
121                // Then iteratively step backwards until we find a matching set of scopes; this
122                // must be the LCA of our original scopes.
123                while (scope1 != scope2) {
124                    assert (scope1 && scope2);
125                    scope1 = scope1->getPredecessor();
126                    scope2 = scope2->getPredecessor();
127                }
128                assert (scope1);
129                // But if the LCA is the current block, we can't sink the statement.
130                if (scope1 == block) {
131                    goto abort;
132                }
133                scopes.push_back(scope1);
134            }
135            assert (scopes.size() == 1);
136            assert (isa<Branch>(stmt) ? (cast<Branch>(stmt)->getBody() != scopes.front()) : true);
137            stmt->insertBefore(scopes.front()->front());
138        }
139abort:  scopes.clear();
140        stmt = prevNode;
141    }
142}
143
144/** ------------------------------------------------------------------------------------------------------------- *
145 * @brief hoistWhileLoopInvariants
146 ** ------------------------------------------------------------------------------------------------------------- */
147void CodeMotionPass::hoistLoopInvariants(While * loop) {
148    flat_set<const PabloAST *> loopVariants;
149    for (Var * variant : loop->getEscaped()) {
150        loopVariants.insert(variant);
151    }
152    Statement * outerNode = loop->getPrevNode();
153    Statement * stmt = loop->getBody()->front();
154    while (stmt) {
155        if (isa<Branch>(stmt)) {
156            for (Var * var : cast<Branch>(stmt)->getEscaped()) {
157                loopVariants.insert(var);
158            }
159        } else {
160            bool invariant = true;
161            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
162                if (loopVariants.count(stmt->getOperand(i)) != 0) {
163                    invariant = false;
164                    break;
165                }
166            }
167            if (LLVM_UNLIKELY(invariant)) {
168                Statement * next = stmt->getNextNode();
169                stmt->insertAfter(outerNode);
170                outerNode = stmt;
171                stmt = next;
172            } else {
173                loopVariants.insert(stmt);
174                stmt = stmt->getNextNode();
175            }
176        }
177    }
178}
179
180}
Note: See TracBrowser for help on using the repository browser.