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

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

Initial introduction of a PabloFunction? type.

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