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

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

Temporary check-in

File size: 10.1 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                case PabloAST::ClassTypeId::Next:
135                    expr = stmt;
136                    break;
137                default: {
138                    std::string tmp;
139                    llvm::raw_string_ostream msg(tmp);
140                    PabloPrinter::print(stmt, "Unhandled trivial folding optimization! ", msg);
141                    throw std::runtime_error(msg.str());
142                }
143            }
144            stmt = stmt->replaceWith(expr);
145            // the next statement could be an Assign; just restart the loop.
146            continue;
147        }
148        else {
149            // When we're creating the Pablo program, it's possible to have multiple instances of an "identical"
150            // statement. By recording which statements have already been seen, we can detect the redundant statements
151            // as any having the same type and operands. If so, we can replace its users with the prior statement.
152            // and erase this statement from the AST
153            const auto f = encountered.findOrAdd(stmt);
154            if (!std::get<1>(f)) {
155                stmt = stmt->replaceWith(std::get<0>(f));
156                continue;
157            }
158        }
159        assert (stmt);
160        stmt = stmt->getNextNode();
161    }
162    block.setInsertPoint(block.back());
163}
164
165
166void Simplifier::deadCodeElimination(PabloBlock & block) {
167    Statement * stmt = block.front();
168    while (stmt) {
169        if (isa<If>(stmt)) {
170            deadCodeElimination(cast<If>(stmt)->getBody());
171        }
172        else if (isa<While>(stmt)) {
173            deadCodeElimination(cast<While>(stmt)->getBody());
174        }
175        else if (stmt->getNumUses() == 0){
176            assert ("Any Assign passed to this function ought to have users or be an output var!" && (!isa<Assign>(stmt) || cast<Assign>(stmt)->isOutputAssignment()));
177            if (!isa<Assign>(stmt)) {
178                stmt = stmt->eraseFromParent(true);
179                continue;
180            }
181        }
182        stmt = stmt->getNextNode();
183    }
184    block.setInsertPoint(block.back());
185}
186
187void Simplifier::eliminateRedundantComplexStatements(PabloBlock & block) {
188    Statement * stmt = block.front();
189    while (stmt) {
190        if (isa<If>(stmt)) {
191            eliminateRedundantComplexStatements(cast<If>(stmt)->getBody());
192        }
193        else if (isa<While>(stmt)) {
194            eliminateRedundantComplexStatements(cast<While>(stmt)->getBody());
195        }
196        else if (stmt->getNumOperands() == 2){
197            if (isa<Advance>(stmt)) {
198                // If we're advancing an Advance and the internal Advance does not have any other user,
199                // we can merge both Advance instructions.
200                if (LLVM_UNLIKELY(isa<Advance>(stmt->getOperand(0)))) {
201                    Advance * op = cast<Advance>(stmt->getOperand(0));
202                    if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
203                        Advance * adv = cast<Advance>(stmt);
204                        adv->setOperand(0, op->getOperand(0));
205                        adv->setOperand(1, block.getInteger(adv->getAdvanceAmount() + op->getAdvanceAmount()));
206                        assert(op->getNumUses() == 0);
207                        op->eraseFromParent();
208                    }
209                }
210            }
211            // If an AND, OR or XOR instruction has two Advance instructions as inputs and neither Advance
212            // has another user and both shift their input by the same amount, we can perform the AND, OR
213            // or XOR on the inputs to the Advances and remove one of the Advance statements.
214            else if (LLVM_UNLIKELY(isa<Advance>(stmt->getOperand(1)) && isa<Advance>(stmt->getOperand(0)))) {
215                Advance * const a0 = cast<Advance>(stmt->getOperand(0));
216                Advance * const a1 = cast<Advance>(stmt->getOperand(1));
217                switch (stmt->getClassTypeId()) {
218                    case PabloAST::ClassTypeId::And:
219                    case PabloAST::ClassTypeId::Or:
220                    case PabloAST::ClassTypeId::Xor:
221                        if (LLVM_UNLIKELY(a0->getNumUses() == 1 && a1->getNumUses() == 1 && a0->getOperand(1) == a1->getOperand(1))) {
222                            block.setInsertPoint(stmt);
223                            stmt->setOperand(0, a0->getOperand(0));
224                            stmt->setOperand(1, a1->getOperand(0));
225                            a0->insertAfter(stmt);
226                            a0->setOperand(0, stmt);
227                            stmt->replaceAllUsesWith(a0);
228                            assert(a1->getNumUses() == 0);
229                            a1->eraseFromParent();
230                            stmt = a0;
231                    }
232                    default: break;
233                }
234            }
235            else if (LLVM_UNLIKELY(isa<MatchStar>(stmt->getOperand(1)) && isa<MatchStar>(stmt->getOperand(0))) && isa<Or>(stmt)) {
236
237
238            }
239        }
240        stmt = stmt->getNextNode();
241    }
242    block.setInsertPoint(block.back());
243}
244
245
246Simplifier::Simplifier()
247{
248
249}
250
251
252}
Note: See TracBrowser for help on using the repository browser.