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

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

added code sinking module; disabled by default as it hurts performance unless if-insertions occur.

File size: 3.5 KB
Line 
1#include "pablo_codesinking.hpp"
2
3namespace pablo {
4
5bool CodeSinking::optimize(PabloBlock & block)
6{
7    CodeSinking lcf;
8    lcf.sink(block);
9    return true;
10}
11
12inline static bool isSafeToMove(Statement * stmt) {
13    if (isa<Assign>(stmt) || isa<Next>(stmt)) {
14        return false;
15    }
16    return true;
17}
18
19void CodeSinking::sink(PabloBlock & block) {
20
21    Statement * stmt = block.back();
22    while (stmt) {
23        Statement * next = stmt->getPrevNode();
24        if (isa<If>(stmt)) {
25            If * ifNode = cast<If>(stmt);
26            assert (ifNode->getParent() == &block);
27            sink(ifNode->getBody());
28        }
29        else if (isa<While>(stmt)) {
30            While * whileNode = cast<While>(stmt);
31            assert (whileNode->getParent() == &block);
32            sink(whileNode->getBody());
33        }
34        else if (isSafeToMove(stmt)) {
35
36            BlockSetVector ancestors;
37            bool canSinkInstruction = false;
38            for (const PabloAST * u : stmt->users()) {
39                if (const Statement * use = dyn_cast<Statement>(u)) {
40                    if (mProcessed.count(use->getParent())) {
41                        canSinkInstruction = true;
42                        ancestors.insert(use->getParent());
43                        continue;
44                    }
45                    canSinkInstruction = false;
46                    break;
47                }
48            }
49            if (canSinkInstruction) {
50
51                assert (ancestors.size() >= 1);
52
53                if (ancestors.size() > 1) {
54                    BlockSetVector P1, P2;
55                    while (ancestors.size() > 1) {
56
57                        PabloBlock * u = ancestors.back();
58                        while (u != &block) {
59                            P1.push_back(u);
60                            u = u->getParent();
61                        }
62                        ancestors.pop_back();
63
64                        PabloBlock * v = ancestors.back();
65                        while (v != &block) {
66                            P2.push_back(v);
67                            v = v->getParent();
68                        }
69                        ancestors.pop_back();
70
71                        // P1 and P2 now contain the paths from the 'sink' to the 'source'. Scan backwards though them
72                        // to find the first differing element. The last non-differing block is our LCA. If none
73                        // exists for any two paths, this instruction cannot be sunk (or would just be sunk to the
74                        // same position it's at now.)
75
76                        PabloBlock * lca = nullptr;
77                        auto p1 = P1.rbegin(), p2 = P2.rbegin();
78
79                        for (; p1 != P1.rend() && p2 != P2.rend(); ++p1, ++p2) {
80                            if (*p1 != *p2) {
81                                break;
82                            }
83
84                            lca = *p1;
85                        }
86
87                        if (lca == nullptr) {
88                            canSinkInstruction = false;
89                            break;
90                        }
91
92                        P1.clear();
93                        P2.clear();
94                        ancestors.insert(lca);
95                    }
96                }
97
98                if (canSinkInstruction) {
99                    assert (ancestors.size() == 1);
100                    PabloBlock * const lca = *ancestors.begin();
101                    stmt->insertBefore(lca->front());
102                }
103            }
104        }
105        stmt = next;
106    }
107    mProcessed.insert(&block);
108}
109
110}
Note: See TracBrowser for help on using the repository browser.