source: icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp @ 4532

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

Many memory deallocation fixes.

File size: 5.6 KB
Line 
1#include <pablo/optimizers/pablo_simplifier.hpp>
2#include <pablo/codegenstate.h>
3#include <pablo/expression_map.hpp>
4
5#include <pablo/printer_pablos.h>
6
7
8
9namespace pablo {
10
11bool Simplifier::optimize(PabloBlock & block) {
12    eliminateRedundantCode(block);
13    deadCodeElimination(block);
14
15    return true;
16}
17
18inline static bool canTriviallyFold(const Statement * stmt) {
19    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
20        switch (stmt->getOperand(i)->getClassTypeId()) {
21            case PabloAST::ClassTypeId::Zeroes:
22            case PabloAST::ClassTypeId::Ones:
23                return true;
24            default: break;
25        }
26    }
27    return false;
28}
29
30#ifndef NDEBUG
31static bool verifyStatementIsInSameBlock(const Statement * const stmt, const PabloBlock & block) {
32    Statement * curr = block.front();
33    while (curr) {
34        if (curr == stmt) {
35            return true;
36        }
37        curr = curr->getNextNode();
38    }
39    return false;
40}
41#endif
42
43void Simplifier::eliminateRedundantCode(PabloBlock & block, ExpressionTable * predecessor) {
44    ExpressionTable encountered(predecessor);
45
46    Statement * stmt = block.front();
47
48    while (stmt) {
49
50        assert (stmt);
51        assert (verifyStatementIsInSameBlock(stmt, block));
52
53        if (Assign * assign = dyn_cast<Assign>(stmt)) {
54            // If we have an Assign whose users do not contain an If or Next node, we can replace its users with
55            // the Assign's expression directly.
56            if (assign->superfluous()) {
57                if (stmt->getNumUses() == 0) {
58                    stmt = assign->eraseFromParent();
59                }
60                else {
61                    stmt = assign->replaceWith(assign->getExpr());
62                }
63                continue;
64            }
65        }
66        else if (isa<If>(stmt)) {
67            eliminateRedundantCode(cast<If>(stmt)->getBody(), &encountered);
68        }
69        else if (isa<While>(stmt)) {
70            eliminateRedundantCode(cast<While>(stmt)->getBody(), &encountered);
71        }       
72        else if (stmt->getNumUses() == 0) {
73            // If this statement has no users, we can discard it. If a future "identical" statement occurs that does
74            // have users, we can use that statement instead.
75            stmt = stmt->eraseFromParent();
76            continue;
77        }
78        else if (canTriviallyFold(stmt)) { // non-Assign node
79
80            // Do a trivial folding test to see if we're using all 0s or 1s as an operand.
81            PabloAST * expr = nullptr;
82            block.setInsertPoint(stmt->getPrevNode());
83            switch (stmt->getClassTypeId()) {
84                case PabloAST::ClassTypeId::Advance:
85                    expr = block.createAdvance(stmt->getOperand(0), stmt->getOperand(1));
86                    break;
87                case PabloAST::ClassTypeId::And:
88                    expr = block.createAnd(stmt->getOperand(0), stmt->getOperand(1));
89                    break;
90                case PabloAST::ClassTypeId::Or:
91                    expr = block.createOr(stmt->getOperand(0), stmt->getOperand(1));
92                    break;
93                case PabloAST::ClassTypeId::Not:
94                    expr = block.createNot(stmt->getOperand(0));
95                    break;
96                case PabloAST::ClassTypeId::Xor:
97                    expr = block.createXor(stmt->getOperand(0), stmt->getOperand(1));
98                    break;
99                case PabloAST::ClassTypeId::Sel:
100                    expr = block.createSel(stmt->getOperand(0), stmt->getOperand(1), stmt->getOperand(2));
101                    break;
102                case PabloAST::ClassTypeId::ScanThru:
103                    expr = block.createScanThru(stmt->getOperand(0), stmt->getOperand(1));
104                    break;
105                case PabloAST::ClassTypeId::MatchStar:
106                    expr = block.createMatchStar(stmt->getOperand(0), stmt->getOperand(1));
107                    break;
108                default:
109                    throw std::runtime_error("Unhandled trivial folding optimization!");
110            }
111            stmt = stmt->replaceWith(expr);
112            // the next statement could be an Assign; just restart the loop.
113            continue;
114        }
115        else {
116            // When we're creating the Pablo program, it's possible to have multiple instances of an "identical"
117            // statement. By recording which statements have already been seen, we can detect the redundant statements
118            // as any having the same type and operands. If so, we can replace its users with the prior statement.
119            // and erase this statement from the AST
120            const auto f = encountered.findOrAdd(stmt);
121            if (!std::get<1>(f)) {
122                stmt = stmt->replaceWith(std::get<0>(f));
123                continue;
124            }
125        }
126        assert (stmt);
127        stmt = stmt->getNextNode();
128    }
129    block.setInsertPoint(block.back());
130}
131
132
133void Simplifier::deadCodeElimination(PabloBlock & block) {
134    Statement * stmt = block.front();
135    while (stmt) {
136        if (isa<If>(stmt)) {
137            deadCodeElimination(cast<If>(stmt)->getBody());
138        }
139        else if (isa<While>(stmt)) {
140            deadCodeElimination(cast<While>(stmt)->getBody());
141        }
142        else if (stmt->getNumUses() == 0){
143            assert ("Any Assign passed to this function ought to have users or be an output var!" && (!isa<Assign>(stmt) || cast<Assign>(stmt)->isOutputAssignment()));
144            if (!isa<Assign>(stmt)) {
145                stmt = stmt->eraseFromParent(true);
146                continue;
147            }
148        }
149        stmt = stmt->getNextNode();
150    }
151}
152
153
154
155
156Simplifier::Simplifier()
157{
158
159}
160
161
162}
Note: See TracBrowser for help on using the repository browser.