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

Last change on this file was 6173, checked in by nmedfort, 7 months ago

Added RE_Inspector.

Migrated RE passes to RE_Transformer.

Incorporated Memoizer functionality into RE_Transformer/Inspector.

Removed Memoizer.

Bug fix for unicode_set.

File size: 11.6 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#ifndef NDEBUG
9#include <pablo/analysis/pabloverifier.hpp>
10#endif
11
12#include <llvm/Support/raw_ostream.h>
13#include <pablo/printer_pablos.h>
14
15using namespace llvm;
16
17namespace pablo {
18
19/** ------------------------------------------------------------------------------------------------------------- *
20 * @brief ScopeSet
21 ** ------------------------------------------------------------------------------------------------------------- */
22template <typename T>
23struct SetQueue : public std::vector<T> {
24    inline void insert(T const item) {
25        const auto i = std::lower_bound(std::vector<T>::begin(), std::vector<T>::end(), item);
26        if (i == std::vector<T>::end() || *i != item) {
27            std::vector<T>::insert(i, item);
28        }
29    }
30    inline bool count(T const item) const {
31        const auto i = std::lower_bound(std::vector<T>::begin(), std::vector<T>::end(), item);
32        return (i != std::vector<T>::end() && *i == item);
33    }
34};
35
36using ScopeSet = SetQueue<PabloBlock *>;
37
38using UserSet = SetQueue<Statement *>;
39
40using LoopVariants = boost::container::flat_set<const PabloAST *>;
41
42struct CodeMotionPassContainer {
43
44    /** ------------------------------------------------------------------------------------------------------------- *
45     * @brief depthOf
46     ** ------------------------------------------------------------------------------------------------------------- */
47    static int depthOf(PabloBlock * scope) {
48        int depth = 0;
49        while (scope) {
50            ++depth;
51            scope = scope->getPredecessor();
52        }
53        return depth;
54    }
55
56    /** ------------------------------------------------------------------------------------------------------------- *
57     * @brief findLCA
58     ** ------------------------------------------------------------------------------------------------------------- */
59    PabloBlock * getLCA(PabloBlock * scope1, PabloBlock * scope2) {
60        int depth1 = depthOf(scope1);
61        int depth2 = depthOf(scope2);
62        // If one of these scopes is nested deeper than the other, scan upwards through
63        // the scope tree until both scopes are at the same depth.
64        while (depth1 > depth2) {
65            scope1 = scope1->getPredecessor();
66            --depth1;
67        }
68        while (depth1 < depth2) {
69            scope2 = scope2->getPredecessor();
70            --depth2;
71        }
72        // Then iteratively step backwards until we find a matching set of scopes; this
73        // must be the LCA of our original scopes.
74        while (scope1 != scope2) {
75            assert (scope1 && scope2);
76            scope1 = scope1->getPredecessor();
77            scope2 = scope2->getPredecessor();
78        }
79        return scope1;
80    }
81
82    /** ------------------------------------------------------------------------------------------------------------- *
83     * @brief getScopesOfAllUsers
84     ** ------------------------------------------------------------------------------------------------------------- */
85    void getScopesOfAllUsers(PabloAST * expr) {
86        for (PabloAST * use : expr->users()) {
87            if (LLVM_LIKELY(isa<Statement>(use))) {
88                mScopes.insert(cast<Statement>(use)->getParent());
89            } else if (LLVM_UNLIKELY(isa<PabloKernel>(use))) {
90                mScopes.insert(cast<PabloKernel>(use)->getEntryScope());
91            }
92        }
93    }
94
95    /** ------------------------------------------------------------------------------------------------------------- *
96     * @brief getInScopeDominatorsOfAllUsers
97     ** ------------------------------------------------------------------------------------------------------------- */
98    void getInScopeDominatorsOfAllUsers(PabloAST * expr, PabloBlock * const block) {
99        for (PabloAST * use : expr->users()) {
100            if (LLVM_LIKELY(isa<Statement>(use))) {
101                Statement * user = cast<Statement>(use);
102                PabloBlock * parent = user->getParent();
103                while (parent != block) {
104                    assert (parent);
105                    user = parent->getBranch();
106                    parent = parent->getPredecessor();
107                }
108                mUsers.insert(user);
109            }
110        }
111    }
112
113    /** ------------------------------------------------------------------------------------------------------------- *
114     * @brief sinkIfAcceptableTarget
115     *
116     * Scan through this statement's users to see whether they're all in a nested scope. If not, check whether the
117     * statement can be moved past a branch statement within the same scope.
118     ** ------------------------------------------------------------------------------------------------------------- */
119    void sinkIfAcceptableTarget(Statement * const stmt, PabloBlock * const block) {
120        assert (mScopes.empty() && mUsers.empty());
121        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
122            for (Var * def : cast<Branch>(stmt)->getEscaped()) {
123                getScopesOfAllUsers(def);
124            }
125        } else {
126            getScopesOfAllUsers(isa<Assign>(stmt) ? cast<Assign>(stmt)->getVariable() : stmt);
127        }
128        if (LLVM_UNLIKELY(mScopes.empty())) {
129            return;
130        }
131        while (mScopes.size() > 1) {
132            PabloBlock * scope1 = mScopes.back(); mScopes.pop_back();
133            PabloBlock * scope2 = mScopes.back(); mScopes.pop_back();
134            mScopes.insert(getLCA(scope1, scope2));
135        }
136        PabloBlock * const scope = mScopes.back(); mScopes.clear();
137        if (LLVM_LIKELY(scope == block)) {
138            assert (mUsers.empty());
139            if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
140                for (Var * def : cast<Branch>(stmt)->getEscaped()) {
141                    getInScopeDominatorsOfAllUsers(def, block);
142                }
143            } else {
144                getInScopeDominatorsOfAllUsers(isa<Assign>(stmt) ? cast<Assign>(stmt)->getVariable() : stmt, block);
145            }
146            Branch * branch = nullptr;
147            Statement * temp = stmt;
148            for (;;) {
149                temp = temp->getNextNode();
150                if (temp == nullptr || mUsers.count(temp)) {
151                    if (branch) {
152                        // we can move the statement past a branch within its current scope
153                        stmt->insertAfter(branch);
154                    }
155                    break;
156                }
157                if (isa<Branch>(temp)) {
158                    branch = cast<Branch>(temp);
159                }
160            }
161            mUsers.clear();
162        } else { // test whether the LCA scope is nested within this scope.
163            PabloBlock * temp = scope;
164            for (;;) {
165                temp = temp->getPredecessor();
166                if (temp == nullptr) {
167                    break;
168                } else if (temp == block) {
169                    // we can move the statement into a nested scope
170                    stmt->insertBefore(scope->front());
171                    break;
172                }
173            }
174        }
175    }
176
177    /** ------------------------------------------------------------------------------------------------------------- *
178     * @brief hoistLoopInvariants
179     ** ------------------------------------------------------------------------------------------------------------- */
180    void hoistLoopInvariants(While * const loop) {
181
182        assert ("Loop variants were not cleared correctly." && mVariants.empty());
183
184        // Assume every escaped Var is tainted but not necessarily a variant. Then iterate
185        // through the loop body and mark any statement that uses a tainted expression as
186        // tainted itself. If a Var is assigned a tainted value, mark the Var as a variant.
187
188        for (const Var * var : loop->getEscaped()) {
189            mTainted.insert(var);
190        }
191
192        for (const Statement * stmt : *loop->getBody()) {
193            if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
194                // Trust that any escaped values of an inner branch is a variant.
195                for (const Var * var : cast<Branch>(stmt)->getEscaped()) {
196                    mVariants.insert(var);
197                }
198            } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
199                const Assign * const a = cast<Assign>(stmt);
200                if (LLVM_LIKELY(mTainted.count(a->getValue()))) {
201                    mVariants.insert(a->getVariable());
202               }
203            } else {
204                for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
205                    const PabloAST * const op = stmt->getOperand(i);
206                    if (mTainted.count(op)) {
207                        mTainted.insert(stmt);
208                        break;
209                    }
210                }
211            }
212        }
213
214        assert ("A loop without any variants is an infinite loop" && !mVariants.empty());
215
216        mVariants.reserve(mTainted.size());
217        mTainted.clear();
218
219        // Iterate over the loop again but this time move any invariants out of the loop.
220        // An invariant is any statement whose operands are all non-variants.
221
222        Statement * outerNode = loop->getPrevNode();
223        Statement * stmt = loop->getBody()->front();
224        while (stmt) {
225            if (isa<Branch>(stmt)) {
226                stmt = stmt->getNextNode();
227            } else {
228                bool invariant = true;
229                for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
230                    const PabloAST * const op = stmt->getOperand(i);
231                    if (mVariants.count(op)) {
232                        invariant = false;
233                        break;
234                    }
235                }
236                Statement * const next = stmt->getNextNode();
237                if (LLVM_UNLIKELY(invariant)) {
238                    stmt->insertAfter(outerNode);
239                    outerNode = stmt;
240                } else {
241                    mVariants.insert(stmt);
242                }
243                stmt = next;
244            }
245        }
246
247        mVariants.clear();
248    }
249
250    /** ------------------------------------------------------------------------------------------------------------- *
251     * @brief doCodeMovement
252     ** ------------------------------------------------------------------------------------------------------------- */
253    void doCodeMovement(PabloBlock * const block) {
254
255        std::vector<Branch *> branches;
256
257        Statement * stmt = block->back(); // note: reverse AST traversal
258        while (stmt) {
259            Statement * const prevNode = stmt->getPrevNode();
260            sinkIfAcceptableTarget(stmt, block);
261            if (isa<Branch>(stmt)) {
262                branches.push_back(cast<Branch>(stmt));
263            }
264            stmt = prevNode;
265        }
266
267        while (!branches.empty()) {
268            Branch * const br = branches.back();
269            branches.pop_back();
270            doCodeMovement(br->getBody());
271            if (isa<While>(br)) {
272                hoistLoopInvariants(cast<While>(br));
273            }
274        }
275
276    }
277
278private:
279    ScopeSet        mScopes;
280    UserSet         mUsers;
281    LoopVariants    mVariants;
282    LoopVariants    mTainted;
283};
284
285/** ------------------------------------------------------------------------------------------------------------- *
286 * @brief optimize
287 ** ------------------------------------------------------------------------------------------------------------- */
288bool CodeMotionPass::optimize(PabloKernel * kernel) {
289    CodeMotionPassContainer C;
290    C.doCodeMovement(kernel->getEntryScope());
291    #ifndef NDEBUG
292    PabloVerifier::verify(kernel, "post-code-motion");
293    #endif
294    return true;
295}
296
297
298}
Note: See TracBrowser for help on using the repository browser.