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

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

Optimized Symbol Generation (and fixed potential bug that could allow duplicate names being constructed); made PabloKernel? extend PabloAST (temporarily removed PabloAST::getName() to avoid diamond problem); added an internal scalar to PabloKernel? struct for each Count to avoid InOut? output scalar variable problem; allowed CodeMotionPass? to move code within the same scope but across a branch statement. Began work on separating Kernels into either Block-Oriented or Segment-Oriented kernels.

File size: 10.0 KB
Line 
1#include "codemotionpass.h"
2#include <pablo/pablo_kernel.h>
3#include <pablo/codegenstate.h>
4#include <pablo/branch.h>
5#include <pablo/ps_assign.h>
6#include <pablo/pe_var.h>
7#include <boost/container/flat_set.hpp>
8#include <vector>
9#ifndef NDEBUG
10#include <pablo/analysis/pabloverifier.hpp>
11#endif
12
13using namespace boost;
14using namespace boost::container;
15using namespace llvm;
16
17namespace pablo {
18
19/** ------------------------------------------------------------------------------------------------------------- *
20 * @brief optimize
21 ** ------------------------------------------------------------------------------------------------------------- */
22bool CodeMotionPass::optimize(PabloKernel * kernel) {
23    CodeMotionPass::movement(kernel->getEntryBlock());
24    #ifndef NDEBUG
25    PabloVerifier::verify(kernel, "post-code-motion");
26    #endif
27    return true;
28}
29
30/** ------------------------------------------------------------------------------------------------------------- *
31 * @brief movement
32 ** ------------------------------------------------------------------------------------------------------------- */
33void CodeMotionPass::movement(PabloBlock * const block) {
34    sink(block);
35    for (Statement * stmt : *block) {
36        if (isa<If>(stmt)) {
37            movement(cast<If>(stmt)->getBody());
38        } else if (isa<While>(stmt)) {
39            movement(cast<While>(stmt)->getBody());
40            // TODO: if we analyzed the probability of this loop being executed once, twice, or many times, we could
41            // determine whether hoisting will helpful or harmful to the expected run time.
42            hoistLoopInvariants(cast<While>(stmt));
43        }
44    }
45}
46
47/** ------------------------------------------------------------------------------------------------------------- *
48 * @brief depthOf
49 ** ------------------------------------------------------------------------------------------------------------- */
50inline static int depthOf(PabloBlock * scope) {
51    int depth = 0;
52    while (scope) {
53        ++depth;
54        scope = scope->getPredecessor();
55    }
56    return depth;
57}
58
59/** ------------------------------------------------------------------------------------------------------------- *
60 * @brief findLCA
61 ** ------------------------------------------------------------------------------------------------------------- */
62inline PabloBlock * getLCA(PabloBlock * scope1, PabloBlock * scope2) {
63    int depth1 = depthOf(scope1);
64    int depth2 = depthOf(scope2);
65    // If one of these scopes is nested deeper than the other, scan upwards through
66    // the scope tree until both scopes are at the same depth.
67    while (depth1 > depth2) {
68        scope1 = scope1->getPredecessor();
69        --depth1;
70    }
71    while (depth1 < depth2) {
72        scope2 = scope2->getPredecessor();
73        --depth2;
74    }
75    // Then iteratively step backwards until we find a matching set of scopes; this
76    // must be the LCA of our original scopes.
77    while (scope1 != scope2) {
78        assert (scope1 && scope2);
79        scope1 = scope1->getPredecessor();
80        scope2 = scope2->getPredecessor();
81    }
82    return scope1;
83}
84
85/** ------------------------------------------------------------------------------------------------------------- *
86 * @brief ScopeSet
87 ** ------------------------------------------------------------------------------------------------------------- */
88template <typename T>
89struct SetQueue : public std::vector<T> {
90    inline void insert(T const item) {
91        const auto i = std::lower_bound(std::vector<T>::begin(), std::vector<T>::end(), item);
92        if (i == std::vector<T>::end() || *i != item) {
93            std::vector<T>::insert(i, item);
94        }
95    }
96    inline bool count(T const item) const {
97        const auto i = std::lower_bound(std::vector<T>::begin(), std::vector<T>::end(), item);
98        return (i != std::vector<T>::end() && *i == item);
99    }
100};
101
102using ScopeSet = SetQueue<PabloBlock *>;
103
104using UserSet = SetQueue<Statement *>;
105
106/** ------------------------------------------------------------------------------------------------------------- *
107 * @brief getScopesOfAllUsers
108 ** ------------------------------------------------------------------------------------------------------------- */
109inline void getScopesOfAllUsers(PabloAST * expr, ScopeSet & scopes) {
110    for (PabloAST * use : expr->users()) {
111        if (LLVM_LIKELY(isa<Statement>(use))) {
112            scopes.insert(cast<Statement>(use)->getParent());
113        } else if (LLVM_UNLIKELY(isa<PabloKernel>(use))) {
114            scopes.insert(cast<PabloKernel>(use)->getEntryBlock());
115        }
116    }
117}
118
119/** ------------------------------------------------------------------------------------------------------------- *
120 * @brief getInScopeDominatorsOfAllUsers
121 ** ------------------------------------------------------------------------------------------------------------- */
122inline void getInScopeDominatorsOfAllUsers(PabloAST * expr, UserSet & users, PabloBlock * const block) {
123    for (PabloAST * use : expr->users()) {
124        if (LLVM_LIKELY(isa<Statement>(use))) {
125            Statement * user = cast<Statement>(use);
126            PabloBlock * parent = user->getParent();
127            while (parent != block) {
128                assert (parent);
129                user = parent->getBranch();
130                parent = parent->getPredecessor();
131            }
132            users.insert(user);
133        }
134    }
135}
136
137/** ------------------------------------------------------------------------------------------------------------- *
138 * @brief sinkIfAcceptableTarget
139 *
140 * Scan through this statement's users to see whether they're all in a nested scope. If not, check whether the
141 * statement can be moved past a branch statement within the same scope.
142 ** ------------------------------------------------------------------------------------------------------------- */
143inline void sinkIfAcceptableTarget(Statement * const stmt, PabloBlock * const block, ScopeSet & scopes, UserSet & users) {
144    assert (scopes.empty());
145    if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
146        for (Var * def : cast<Branch>(stmt)->getEscaped()) {
147            getScopesOfAllUsers(def, scopes);
148        }
149    } else {
150        getScopesOfAllUsers(isa<Assign>(stmt) ? cast<Assign>(stmt)->getVariable() : stmt, scopes);
151    }   
152    if (LLVM_UNLIKELY(scopes.empty())) {
153        assert (!isa<Assign>(stmt));
154        // should not occur unless we have a branch with no escaped vars or a statement
155        // that has no users. In either event, the statement itself should be removed.
156        stmt->eraseFromParent(true);
157        return;
158    }
159    while (scopes.size() > 1) {
160        PabloBlock * scope1 = scopes.back(); scopes.pop_back();
161        PabloBlock * scope2 = scopes.back(); scopes.pop_back();
162        scopes.insert(getLCA(scope1, scope2));
163    }
164    PabloBlock * const scope = scopes.back(); scopes.clear();
165    if (LLVM_LIKELY(scope == block)) {
166        assert (users.empty());
167        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
168            for (Var * def : cast<Branch>(stmt)->getEscaped()) {
169                getInScopeDominatorsOfAllUsers(def, users, block);
170            }
171        } else {
172            getInScopeDominatorsOfAllUsers(isa<Assign>(stmt) ? cast<Assign>(stmt)->getVariable() : stmt, users, block);
173        }
174        Branch * branch = nullptr;
175        Statement * temp = stmt;
176        for (;;) {
177            temp = temp->getNextNode();
178            if (temp == nullptr || users.count(temp)) {
179                if (branch) {
180                    // we can move the statement past a branch within its current scope
181                    stmt->insertAfter(branch);
182                }
183                break;
184            }
185            if (isa<Branch>(temp)) {
186                branch = cast<Branch>(temp);
187            }
188        }
189        users.clear();
190    } else { // test whether the LCA scope is nested within this scope.
191        PabloBlock * temp = scope;
192        for (;;) {
193            temp = temp->getPredecessor();
194            if (temp == nullptr) {
195                break;
196            } else if (temp == block) {
197                // we can move the statement into a nested scope
198                stmt->insertBefore(scope->front());
199                break;
200            }
201        }
202    }
203}
204
205/** ------------------------------------------------------------------------------------------------------------- *
206 * @brief sink
207 ** ------------------------------------------------------------------------------------------------------------- */
208inline void CodeMotionPass::sink(PabloBlock * const block) {
209    ScopeSet scopes;
210    UserSet users;
211    Statement * stmt = block->back(); // note: reverse AST traversal
212    while (stmt) {
213        Statement * prevNode = stmt->getPrevNode();
214        sinkIfAcceptableTarget(stmt, block, scopes, users);
215        stmt = prevNode;
216    }
217}
218
219/** ------------------------------------------------------------------------------------------------------------- *
220 * @brief hoistLoopInvariants
221 ** ------------------------------------------------------------------------------------------------------------- */
222void CodeMotionPass::hoistLoopInvariants(While * loop) {
223    flat_set<const PabloAST *> loopVariants;
224    for (Var * variant : loop->getEscaped()) {
225        loopVariants.insert(variant);
226    }
227    Statement * outerNode = loop->getPrevNode();
228    Statement * stmt = loop->getBody()->front();
229    while (stmt) {
230        if (isa<Branch>(stmt)) {
231            for (Var * var : cast<Branch>(stmt)->getEscaped()) {
232                loopVariants.insert(var);
233            }
234        } else {
235            bool invariant = true;
236            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
237                if (loopVariants.count(stmt->getOperand(i)) != 0) {
238                    invariant = false;
239                    break;
240                }
241            }
242            if (LLVM_UNLIKELY(invariant)) {
243                Statement * next = stmt->getNextNode();
244                stmt->insertAfter(outerNode);
245                outerNode = stmt;
246                stmt = next;
247            } else {
248                loopVariants.insert(stmt);
249                stmt = stmt->getNextNode();
250            }
251        }
252    }
253}
254
255}
Note: See TracBrowser for help on using the repository browser.