source: icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_codesinking.cpp @ 4799

Last change on this file since 4799 was 4799, checked in by nmedfort, 4 years ago

Bug fix for verifier and rewrite of the code sinking optimization pass.

File size: 4.9 KB
Line 
1#include "pablo_codesinking.hpp"
2#include <pablo/function.h>
3#include <pablo/analysis/pabloverifier.hpp>
4
5namespace pablo {
6
7/** ------------------------------------------------------------------------------------------------------------- *
8 * @brief optimize
9 ** ------------------------------------------------------------------------------------------------------------- */
10bool CodeSinking::optimize(PabloFunction & function) {
11    CodeSinking lcf;
12    lcf.sink(function.getEntryBlock());
13    #ifndef NDEBUG
14    PabloVerifier::verify(function, "post-sinking");
15    #endif
16    return true;
17}
18
19/** ------------------------------------------------------------------------------------------------------------- *
20 * @brief isSafeToMove
21 ** ------------------------------------------------------------------------------------------------------------- */
22inline static bool isSafeToMove(Statement * stmt) {
23    return !isa<Assign>(stmt) && !isa<Next>(stmt);
24}
25
26/** ------------------------------------------------------------------------------------------------------------- *
27 * @brief calculateDepthToCurrentBlock
28 ** ------------------------------------------------------------------------------------------------------------- */
29inline static unsigned calculateDepthToCurrentBlock(const PabloBlock * scope, const PabloBlock & root) {
30    unsigned depth = 0;
31    while (scope != &root) {
32        ++depth;
33        assert (scope);
34        scope = scope->getParent();
35    }
36    return depth;
37}
38
39/** ------------------------------------------------------------------------------------------------------------- *
40 * @brief sink
41 ** ------------------------------------------------------------------------------------------------------------- */
42void CodeSinking::sink(PabloBlock & block) {
43
44    Statement * stmt = block.back(); // note: reverse AST traversal
45    while (stmt) {
46        Statement * next = stmt->getPrevNode();
47        if (isa<If>(stmt)) {
48            sink(cast<If>(stmt)->getBody());
49        } else if (isa<While>(stmt)) {
50            sink(cast<While>(stmt)->getBody());
51        } else if (isSafeToMove(stmt)) {
52
53            // Scan through this statement's users to see if they're all in a nested scope. If so,
54            // find the least comon ancestor of the scope blocks. If it is not the current scope,
55            // then we can sink the instruction.
56
57            // (Note: the current scope is added to the list of processed ones AFTER we've traversed it.)
58
59            ScopeSet scopes;
60            bool canSinkInstruction = false;
61            for (const PabloAST * use : stmt->users()) {
62                if (const Statement * user = dyn_cast<Statement>(use)) {
63                    if (mProcessed.count(user->getParent())) {
64                        canSinkInstruction = true;
65                        scopes.insert(user->getParent());
66                        continue;
67                    }
68                    canSinkInstruction = false;
69                    break;
70                }
71            }
72            if (canSinkInstruction) {
73
74                while (scopes.size() > 1) {
75                    // Find the LCA of both scopes then add the LCA back to the list of scopes.
76                    PabloBlock * scope1 = scopes.back();
77                    scopes.pop_back();
78                    unsigned depth1 = calculateDepthToCurrentBlock(scope1, block);
79
80                    PabloBlock * scope2 = scopes.back();
81                    scopes.pop_back();
82                    unsigned depth2 = calculateDepthToCurrentBlock(scope2, block);
83
84                    // If one of these scopes is nested deeper than the other, scan upwards through
85                    // the scope tree until both scopes are at the same depth.
86                    while (depth1 > depth2) {
87                        scope1 = scope1->getParent();
88                        --depth1;
89                    }
90                    while (depth1 < depth2) {
91                        scope2 = scope2->getParent();
92                        --depth2;
93                    }
94
95                    // Then iteratively step backwards until we find a matching set of scopes; this
96                    // must be the LCA of our original scopes.
97                    while (scope1 != scope2) {
98                        scope1 = scope1->getParent();
99                        scope2 = scope2->getParent();
100                    }
101                    assert (scope1 && scope2);
102                    // But if the LCA is the current block, we can't sink the statement.
103                    if (scope1 == &block) {
104                        canSinkInstruction = false;
105                        break;
106                    }
107                    scopes.push_back(scope1);
108                }
109
110                if (canSinkInstruction) {
111                    assert (scopes.size() == 1);
112                    stmt->insertBefore(scopes.front()->front());
113                }
114            }
115        }
116        stmt = next;
117    }
118    mProcessed.insert(&block);
119}
120
121}
Note: See TracBrowser for help on using the repository browser.