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

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

Progress on multi-target UCD compilation

File size: 6.3 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 findScopeUsages
41 ** ------------------------------------------------------------------------------------------------------------- */
42template <class ScopeSet>
43inline bool findScopeUsages(Statement * stmt, ScopeSet & scopeSet, const PabloBlock & block) {
44    for (PabloAST * use : stmt->users()) {
45        assert (isa<Statement>(use));
46        PabloBlock * const parent = cast<Statement>(use)->getParent();
47        if (LLVM_LIKELY(parent == &block)) {
48            return false;
49        }
50        scopeSet.insert(parent);
51    }
52    return true;
53}
54
55/** ------------------------------------------------------------------------------------------------------------- *
56 * @brief findScopeUsages
57 ** ------------------------------------------------------------------------------------------------------------- */
58template <class ScopeSet>
59inline bool findScopeUsages(Statement * stmt, ScopeSet & scopeSet, const PabloBlock & block, const PabloBlock & ignored) {
60    for (PabloAST * use : stmt->users()) {
61        assert (isa<Statement>(use));
62        PabloBlock * const parent = cast<Statement>(use)->getParent();
63        if (LLVM_LIKELY(parent == &block)) {
64            return false;
65        }
66        if (parent != &ignored) {
67            scopeSet.insert(parent);
68        }
69    }
70    return true;
71}
72
73/** ------------------------------------------------------------------------------------------------------------- *
74 * @brief sink
75 ** ------------------------------------------------------------------------------------------------------------- */
76void CodeSinking::sink(PabloBlock & block) {
77
78    ScopeSet scopes;
79    Statement * stmt = block.back(); // note: reverse AST traversal
80    while (stmt) {
81        Statement * prevNode = stmt->getPrevNode();
82
83        bool sinkable = true;
84        // Scan through this statement's users to see if they're all in a nested scope. If so,
85        // find the least common ancestor of the scope blocks. If it is not the current scope,
86        // then we can sink the instruction.
87        if (isa<If>(stmt)) {
88            PabloBlock & nested = cast<If>(stmt)->getBody();
89            sink(nested);
90            for (Assign * def : cast<const If>(stmt)->getDefined()) {
91                if (!findScopeUsages(def, scopes, block, nested)) {
92                    sinkable = false;
93                    break;
94                }
95            }
96        } else if (isa<While>(stmt)) {
97            PabloBlock & nested = cast<While>(stmt)->getBody();
98            sink(nested);
99            for (Next * var : cast<const While>(stmt)->getVariants()) {
100                if (escapes(var) && !findScopeUsages(var, scopes, block, nested)) {
101                    sinkable = false;
102                    break;
103                }
104            }
105        } else {
106            sinkable = isSafeToMove(stmt) ? findScopeUsages(stmt, scopes, block) : false;
107        }
108
109        if (sinkable) {
110            assert (scopes.size() > 0);
111            while (scopes.size() > 1) {
112                // Find the LCA of both scopes then add the LCA back to the list of scopes.
113                PabloBlock * scope1 = scopes.back(); scopes.pop_back();
114                unsigned depth1 = calculateDepthToCurrentBlock(scope1, block);
115
116                PabloBlock * scope2 = scopes.back(); scopes.pop_back();
117                unsigned depth2 = calculateDepthToCurrentBlock(scope2, block);
118
119                // If one of these scopes is nested deeper than the other, scan upwards through
120                // the scope tree until both scopes are at the same depth.
121                while (depth1 > depth2) {
122                    scope1 = scope1->getParent();
123                    --depth1;
124                }
125                while (depth1 < depth2) {
126                    scope2 = scope2->getParent();
127                    --depth2;
128                }
129
130                // Then iteratively step backwards until we find a matching set of scopes; this
131                // must be the LCA of our original scopes.
132                while (scope1 != scope2) {
133                    scope1 = scope1->getParent();
134                    scope2 = scope2->getParent();
135                }
136                assert (scope1 && scope2);
137                // But if the LCA is the current block, we can't sink the statement.
138                if (scope1 == &block) {
139                    sinkable = false;
140                    break;
141                }
142                scopes.push_back(scope1);
143            }
144            if (sinkable) {
145                assert (scopes.size() == 1);
146                assert (isa<If>(stmt) ? &(cast<If>(stmt)->getBody()) != scopes.front() : true);
147                assert (isa<While>(stmt) ? &(cast<While>(stmt)->getBody()) != scopes.front() : true);
148                stmt->insertBefore(scopes.front()->front());
149            }
150        }
151        scopes.clear();
152        stmt = prevNode;
153    }
154}
155
156}
Note: See TracBrowser for help on using the repository browser.