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

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

Added ability to infer mutual exclusivity / subset relationships based on already proven relationships. Simplifer can now eliminate If nodes whenever all of the defined vars are Zeroes.

File size: 9.9 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    eliminateRedundantComplexStatements(block);
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 (If * ifNode = dyn_cast<If>(stmt)) {
67            // Check to see if the Cond is Zero and delete the loop.
68            if (LLVM_UNLIKELY(isa<Zeroes>(ifNode->getCondition()))) {
69                for (PabloAST * defVar : ifNode->getDefined()) {
70                    cast<Assign>(defVar)->replaceWith(block.createZeroes(), false, true);
71                }
72                stmt = stmt->eraseFromParent(true);
73                continue;
74            }
75            // Process the If body
76            eliminateRedundantCode(cast<If>(stmt)->getBody(), &encountered);
77            // Scan through and replace any defined variable that is assigned Zero with a Zero object
78            // and remove it from the defined variable list.
79            If::DefinedVars & defVars = ifNode->getDefined();
80            for (auto i = defVars.begin(); i != defVars.end(); ) {
81                Assign * defVar = cast<Assign>(*i);
82                if (LLVM_UNLIKELY(isa<Zeroes>(defVar->getExpr()))) {
83                    i = defVars.erase(i);
84                    defVar->replaceWith(block.createZeroes(), false, true);
85                    continue;
86                }
87                ++i;
88            }
89            // If we ended up Zero-ing out all of the defined variables, delete the If node.
90            if (LLVM_UNLIKELY(defVars.empty())) {
91                stmt = stmt->eraseFromParent(true);
92                continue;
93            }
94        }
95        else if (isa<While>(stmt)) {
96            eliminateRedundantCode(cast<While>(stmt)->getBody(), &encountered);
97        }       
98        else if (stmt->getNumUses() == 0) {
99            // If this statement has no users, we can discard it. If a future "identical" statement occurs that does
100            // have users, we can use that statement instead.
101            stmt = stmt->eraseFromParent();
102            continue;
103        }
104        else if (canTriviallyFold(stmt)) { // non-Assign node
105
106            // Do a trivial folding test to see if we're using all 0s or 1s as an operand.
107            PabloAST * expr = nullptr;
108            block.setInsertPoint(stmt->getPrevNode());
109            switch (stmt->getClassTypeId()) {
110                case PabloAST::ClassTypeId::Advance:
111                    expr = block.createAdvance(stmt->getOperand(0), stmt->getOperand(1));
112                    break;
113                case PabloAST::ClassTypeId::And:
114                    expr = block.createAnd(stmt->getOperand(0), stmt->getOperand(1));
115                    break;
116                case PabloAST::ClassTypeId::Or:
117                    expr = block.createOr(stmt->getOperand(0), stmt->getOperand(1));
118                    break;
119                case PabloAST::ClassTypeId::Not:
120                    expr = block.createNot(stmt->getOperand(0));
121                    break;
122                case PabloAST::ClassTypeId::Xor:
123                    expr = block.createXor(stmt->getOperand(0), stmt->getOperand(1));
124                    break;
125                case PabloAST::ClassTypeId::Sel:
126                    expr = block.createSel(stmt->getOperand(0), stmt->getOperand(1), stmt->getOperand(2));
127                    break;
128                case PabloAST::ClassTypeId::ScanThru:
129                    expr = block.createScanThru(stmt->getOperand(0), stmt->getOperand(1));
130                    break;
131                case PabloAST::ClassTypeId::MatchStar:
132                    expr = block.createMatchStar(stmt->getOperand(0), stmt->getOperand(1));
133                    break;
134                default:
135                    throw std::runtime_error("Unhandled trivial folding optimization!");
136            }
137            stmt = stmt->replaceWith(expr);
138            // the next statement could be an Assign; just restart the loop.
139            continue;
140        }
141        else {
142            // When we're creating the Pablo program, it's possible to have multiple instances of an "identical"
143            // statement. By recording which statements have already been seen, we can detect the redundant statements
144            // as any having the same type and operands. If so, we can replace its users with the prior statement.
145            // and erase this statement from the AST
146            const auto f = encountered.findOrAdd(stmt);
147            if (!std::get<1>(f)) {
148                stmt = stmt->replaceWith(std::get<0>(f));
149                continue;
150            }
151        }
152        assert (stmt);
153        stmt = stmt->getNextNode();
154    }
155    block.setInsertPoint(block.back());
156}
157
158
159void Simplifier::deadCodeElimination(PabloBlock & block) {
160    Statement * stmt = block.front();
161    while (stmt) {
162        if (isa<If>(stmt)) {
163            deadCodeElimination(cast<If>(stmt)->getBody());
164        }
165        else if (isa<While>(stmt)) {
166            deadCodeElimination(cast<While>(stmt)->getBody());
167        }
168        else if (stmt->getNumUses() == 0){
169            assert ("Any Assign passed to this function ought to have users or be an output var!" && (!isa<Assign>(stmt) || cast<Assign>(stmt)->isOutputAssignment()));
170            if (!isa<Assign>(stmt)) {
171                stmt = stmt->eraseFromParent(true);
172                continue;
173            }
174        }
175        stmt = stmt->getNextNode();
176    }
177    block.setInsertPoint(block.back());
178}
179
180void Simplifier::eliminateRedundantComplexStatements(PabloBlock & block) {
181    Statement * stmt = block.front();
182    while (stmt) {
183        if (isa<If>(stmt)) {
184            eliminateRedundantComplexStatements(cast<If>(stmt)->getBody());
185        }
186        else if (isa<While>(stmt)) {
187            eliminateRedundantComplexStatements(cast<While>(stmt)->getBody());
188        }
189        else if (stmt->getNumOperands() == 2){
190            if (isa<Advance>(stmt)) {
191                // If we're advancing an Advance and the internal Advance does not have any other user,
192                // we can merge both Advance instructions.
193                if (LLVM_UNLIKELY(isa<Advance>(stmt->getOperand(0)))) {
194                    Advance * op = cast<Advance>(stmt->getOperand(0));
195                    if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
196                        Advance * adv = cast<Advance>(stmt);
197                        adv->setOperand(0, op->getOperand(0));
198                        adv->setOperand(1, block.getInteger(adv->getAdvanceAmount() + op->getAdvanceAmount()));
199                        assert(op->getNumUses() == 0);
200                        op->eraseFromParent();
201                    }
202                }
203            }
204            // If an AND, OR or XOR instruction has two Advance instructions as inputs and neither Advance
205            // has another user and both shift their input by the same amount, we can perform the AND, OR
206            // or XOR on the inputs to the Advances and remove one of the Advance statements.
207            else if (LLVM_UNLIKELY(isa<Advance>(stmt->getOperand(1)) && isa<Advance>(stmt->getOperand(0)))) {
208                Advance * const a0 = cast<Advance>(stmt->getOperand(0));
209                Advance * const a1 = cast<Advance>(stmt->getOperand(1));
210                switch (stmt->getClassTypeId()) {
211                    case PabloAST::ClassTypeId::And:
212                    case PabloAST::ClassTypeId::Or:
213                    case PabloAST::ClassTypeId::Xor:
214                        if (LLVM_UNLIKELY(a0->getNumUses() == 1 && a1->getNumUses() == 1 && a0->getOperand(1) == a1->getOperand(1))) {
215                            block.setInsertPoint(stmt);
216                            stmt->setOperand(0, a0->getOperand(0));
217                            stmt->setOperand(1, a1->getOperand(0));
218                            a0->insertAfter(stmt);
219                            a0->setOperand(0, stmt);
220                            stmt->replaceAllUsesWith(a0);
221                            assert(a1->getNumUses() == 0);
222                            a1->eraseFromParent();
223                            stmt = a0;
224                    }
225                    default: break;
226                }
227            }
228            else if (LLVM_UNLIKELY(isa<MatchStar>(stmt->getOperand(1)) && isa<MatchStar>(stmt->getOperand(0))) && isa<Or>(stmt)) {
229
230
231            }
232        }
233        stmt = stmt->getNextNode();
234    }
235    block.setInsertPoint(block.back());
236}
237
238
239Simplifier::Simplifier()
240{
241
242}
243
244
245}
Note: See TracBrowser for help on using the repository browser.