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

Last change on this file since 4443 was 4443, checked in by nmedfort, 5 years ago

Temporary check in.

File size: 5.5 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                stmt = (stmt->getNumUses() == 0) ? assign->eraseFromParent() : assign->replaceWith(assign->getExpr());
58                continue;
59            }
60        }
61        else if (isa<If>(stmt)) {
62            eliminateRedundantCode(cast<If>(stmt)->getBody(), &encountered);
63        }
64        else if (isa<While>(stmt)) {
65            eliminateRedundantCode(cast<While>(stmt)->getBody(), &encountered);
66        }       
67        else if (stmt->getNumUses() == 0) {
68            // If this statement has no users, we can discard it. If a future "identical" statement occurs that does
69            // have users, we can use that statement instead.
70            stmt = stmt->eraseFromParent();
71            continue;
72        }
73        else if (canTriviallyFold(stmt)) { // non-Assign node
74
75            // Do a trivial folding test to see if we're using all 0s or 1s as an operand.
76            PabloAST * expr = nullptr;
77            block.setInsertPoint(stmt->getPrevNode());
78            switch (stmt->getClassTypeId()) {
79                case PabloAST::ClassTypeId::Advance:
80                    expr = block.createAdvance(stmt->getOperand(0), stmt->getOperand(1));
81                    break;
82                case PabloAST::ClassTypeId::And:
83                    expr = block.createAnd(stmt->getOperand(0), stmt->getOperand(1));
84                    break;
85                case PabloAST::ClassTypeId::Or:
86                    expr = block.createOr(stmt->getOperand(0), stmt->getOperand(1));
87                    break;
88                case PabloAST::ClassTypeId::Not:
89                    expr = block.createNot(stmt->getOperand(0));
90                    break;
91                case PabloAST::ClassTypeId::Xor:
92                    expr = block.createXor(stmt->getOperand(0), stmt->getOperand(1));
93                    break;
94                case PabloAST::ClassTypeId::Sel:
95                    expr = block.createSel(stmt->getOperand(0), stmt->getOperand(1), stmt->getOperand(2));
96                    break;
97                case PabloAST::ClassTypeId::ScanThru:
98                    expr = block.createScanThru(stmt->getOperand(0), stmt->getOperand(1));
99                    break;
100                case PabloAST::ClassTypeId::MatchStar:
101                    expr = block.createMatchStar(stmt->getOperand(0), stmt->getOperand(1));
102                    break;
103                default:
104                    throw std::runtime_error("Unhandled trivial folding optimization!");
105            }
106            stmt = stmt->replaceWith(expr);
107            // the next statement could be an Assign; just restart the loop.
108            continue;
109        }
110        else {
111            // When we're creating the Pablo program, it's possible to have multiple instances of an "identical"
112            // statement. By recording which statements have already been seen, we can detect the redundant statements
113            // as any having the same type and operands. If so, we can replace its users with the prior statement.
114            // and erase this statement from the AST
115            const auto f = encountered.findOrAdd(stmt);
116            if (!std::get<1>(f)) {
117                stmt = stmt->replaceWith(std::get<0>(f));
118                continue;
119            }
120        }
121        assert (stmt);
122        stmt = stmt->getNextNode();
123    }
124    block.setInsertPoint(block.back());
125}
126
127
128void Simplifier::deadCodeElimination(PabloBlock & block) {
129    Statement * stmt = block.front();
130    while (stmt) {
131        if (isa<If>(stmt)) {
132            deadCodeElimination(cast<If>(stmt)->getBody());
133        }
134        else if (isa<While>(stmt)) {
135            deadCodeElimination(cast<While>(stmt)->getBody());
136        }
137        else if (stmt->getNumUses() == 0){
138            assert ("Any Assign passed to this function ought to have users or be an output var!" && (!isa<Assign>(stmt) || cast<Assign>(stmt)->isOutputAssignment()));
139            if (!isa<Assign>(stmt)) {
140                stmt = stmt->eraseFromParent(true);
141                continue;
142            }
143        }
144        stmt = stmt->getNextNode();
145    }
146}
147
148
149
150
151Simplifier::Simplifier()
152{
153
154}
155
156
157}
Note: See TracBrowser for help on using the repository browser.