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

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

Bug fixes for multigrep mode. Optional PabloKernel? branch hit counter added. Minor optimizations.

File size: 11.3 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 contains(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)->getEntryBlock());
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            assert (!isa<Assign>(stmt));
130            // should not occur unless we have a branch with no escaped vars or a statement
131            // that has no users. In either event, the statement itself should be removed.
132            stmt->eraseFromParent(true);
133            return;
134        }
135        while (mScopes.size() > 1) {
136            PabloBlock * scope1 = mScopes.back(); mScopes.pop_back();
137            PabloBlock * scope2 = mScopes.back(); mScopes.pop_back();
138            mScopes.insert(getLCA(scope1, scope2));
139        }
140        PabloBlock * const scope = mScopes.back(); mScopes.clear();
141        if (LLVM_LIKELY(scope == block)) {
142            assert (mUsers.empty());
143            if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
144                for (Var * def : cast<Branch>(stmt)->getEscaped()) {
145                    getInScopeDominatorsOfAllUsers(def, block);
146                }
147            } else {
148                getInScopeDominatorsOfAllUsers(isa<Assign>(stmt) ? cast<Assign>(stmt)->getVariable() : stmt, block);
149            }
150            Branch * branch = nullptr;
151            Statement * temp = stmt;
152            for (;;) {
153                temp = temp->getNextNode();
154                if (temp == nullptr || mUsers.contains(temp)) {
155                    if (branch) {
156                        // we can move the statement past a branch within its current scope
157                        stmt->insertAfter(branch);
158                    }
159                    break;
160                }
161                if (isa<Branch>(temp)) {
162                    branch = cast<Branch>(temp);
163                }
164            }
165            mUsers.clear();
166        } else { // test whether the LCA scope is nested within this scope.
167            PabloBlock * temp = scope;
168            for (;;) {
169                temp = temp->getPredecessor();
170                if (temp == nullptr) {
171                    break;
172                } else if (temp == block) {
173                    // we can move the statement into a nested scope
174                    stmt->insertBefore(scope->front());
175                    break;
176                }
177            }
178        }
179    }
180
181    /** ------------------------------------------------------------------------------------------------------------- *
182     * @brief hoistLoopInvariants
183     ** ------------------------------------------------------------------------------------------------------------- */
184    void hoistLoopInvariants(Branch * const loop) {
185        assert (mLoopVariants.empty());
186        for (Var * variant : loop->getEscaped()) {
187            mLoopVariants.insert(variant);
188            mLoopInvariants.insert(variant);
189        }
190        mLoopInvariants.erase(loop->getCondition());
191
192        Statement * outerNode = loop->getPrevNode();
193        Statement * stmt = loop->getBody()->front();
194        while (stmt) {
195            if (isa<Branch>(stmt)) {
196                for (Var * var : cast<Branch>(stmt)->getEscaped()) {
197                    mLoopVariants.insert(var);
198                    mLoopInvariants.erase(var);
199                }
200                stmt = stmt->getNextNode();
201            } else {
202                bool invariant = true;
203                if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
204                    if (mLoopVariants.count(cast<Assign>(stmt)->getValue()) != 0) {
205                        invariant = false;
206                    }
207                } else {
208                    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
209                        const PabloAST * const op = stmt->getOperand(i);
210                        if (mLoopVariants.count(op) != 0) {
211                            if (isa<Var>(op)) {
212                                mLoopInvariants.erase(op);
213                            }
214                            invariant = false;
215                        }
216                    }
217                }
218
219                Statement * const next = stmt->getNextNode();
220                if (LLVM_UNLIKELY(invariant)) {                   
221                    stmt->insertAfter(outerNode);
222                    outerNode = stmt;                   
223                } else {
224                    mLoopVariants.insert(stmt);
225                }
226                stmt = next;
227            }
228        }
229        mLoopVariants.clear();
230        assert (mLoopInvariants.empty());
231    }
232
233    /** ------------------------------------------------------------------------------------------------------------- *
234     * @brief doCodeMovement
235     ** ------------------------------------------------------------------------------------------------------------- */
236    void doCodeMovement(PabloBlock * const block) {
237
238        std::vector<Branch *> branches;
239
240        Statement * stmt = block->back(); // note: reverse AST traversal
241        while (stmt) {
242            Statement * const prevNode = stmt->getPrevNode();
243            sinkIfAcceptableTarget(stmt, block);
244            if (isa<Branch>(stmt)) {
245                branches.push_back(cast<Branch>(stmt));
246            }
247            stmt = prevNode;
248        }
249
250        while (!branches.empty()) {
251            Branch * const br = branches.back();
252            branches.pop_back();
253            doCodeMovement(br->getBody());
254            if (isa<While>(br)) {
255                // TODO: if we analyzed the probability of this loop being executed once, twice, or many times, we could
256                // determine whether hoisting will helpful or harmful to the expected run time.
257                hoistLoopInvariants(br);
258            }
259
260        }
261
262    }
263
264private:
265    ScopeSet        mScopes;
266    UserSet         mUsers;
267    LoopVariants    mLoopVariants;
268    LoopVariants    mLoopInvariants;
269};
270
271/** ------------------------------------------------------------------------------------------------------------- *
272 * @brief optimize
273 ** ------------------------------------------------------------------------------------------------------------- */
274bool CodeMotionPass::optimize(PabloKernel * kernel) {
275    CodeMotionPassContainer C;
276    C.doCodeMovement(kernel->getEntryBlock());
277    #ifndef NDEBUG
278    PabloVerifier::verify(kernel, "post-code-motion");
279    #endif
280    return true;
281}
282
283
284}
Note: See TracBrowser for help on using the repository browser.