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

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

More work on reassociation pass

File size: 13.8 KB
Line 
1#include <pablo/optimizers/pablo_simplifier.hpp>
2#include <pablo/codegenstate.h>
3#include <pablo/expression_map.hpp>
4#include <pablo/function.h>
5#include <pablo/printer_pablos.h>
6#include <unordered_map>
7#include <iostream>
8
9namespace pablo {
10
11bool Simplifier::optimize(PabloFunction & function) {
12    eliminateRedundantCode(function.getEntryBlock());
13    deadCodeElimination(function.getEntryBlock());
14    eliminateRedundantComplexStatements(function.getEntryBlock());
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
43inline bool Simplifier::isSuperfluous(const Assign * const assign) {
44    for (const PabloAST * inst : assign->users()) {
45        if (isa<Next>(inst) || isa<PabloFunction>(inst)) {
46            return false;
47        } else if (isa<If>(inst)) {
48            const If * ifNode = cast<If>(inst);
49            if (ifNode->getCondition() == assign) {
50                bool notFound = true;
51                for (Assign * defVar : ifNode->getDefined()) {
52                    if (defVar == assign) {
53                        notFound = false;
54                        break;
55                    }
56                }
57                if (notFound) {
58                    continue;
59                }
60            }
61            return false;
62        }
63    }
64    return true;
65}
66
67void Simplifier::eliminateRedundantCode(PabloBlock & block, ExpressionTable * predecessor) {
68    ExpressionTable encountered(predecessor);
69
70    Statement * stmt = block.front();
71
72    while (stmt) {
73
74        assert (stmt);
75        assert (verifyStatementIsInSameBlock(stmt, block));
76
77        if (Assign * assign = dyn_cast<Assign>(stmt)) {
78            // If we have an Assign whose users do not contain an If or Next node, we can replace its users with
79            // the Assign's expression directly.
80            if (isSuperfluous(assign)) {
81                if (assign->getNumUses() == 0) {
82                    stmt = assign->eraseFromParent();
83                }
84                else {
85                    stmt = assign->replaceWith(assign->getExpression(), true, true);
86                }
87                continue;
88            }
89        }
90        else if (If * ifNode = dyn_cast<If>(stmt)) {
91            // Check to see if the Cond is Zero and delete the loop.
92            if (LLVM_UNLIKELY(isa<Zeroes>(ifNode->getCondition()))) {
93                for (Assign * defVar : ifNode->getDefined()) {
94                    defVar->replaceWith(block.createZeroes(), false, true);
95                }
96                stmt = stmt->eraseFromParent(true);
97                continue;
98            }
99
100            bool evaluate = true;
101            If::DefinedVars & defs = ifNode->getDefined();
102            while (evaluate) {
103                evaluate = false;
104                // Process the If body
105                eliminateRedundantCode(cast<If>(stmt)->getBody(), &encountered);
106                // Now test whether all of the defined variables are necessary
107                for (auto itr = defs.begin(); itr != defs.end(); ) {
108                    Assign * def = *itr;
109                    // If this value isn't used outside of this scope then there is no reason to allow it to escape it.
110                    bool unusedOutsideOfNestedScope = true;
111                    for (PabloAST * user : def->users()) {
112                        if (user != ifNode) {
113                            PabloBlock * parent = cast<Statement>(user)->getParent();
114                            while (parent && parent != def->getParent()) {
115                                parent = parent->getParent();
116                            }
117                            if (parent == nullptr) {
118                                unusedOutsideOfNestedScope = false;
119                                break;
120                            }
121                        }
122                    }
123                    // If the defined variable is actually equivalent to the condition, promote the assignment out of If
124                    // scope and remove it from the list of defined variables. Additionally, replace any defined variable
125                    // assigned Zero or One with the appropriate constant and remove it from the defined variable list.
126                    if (LLVM_UNLIKELY(unusedOutsideOfNestedScope || (ifNode->getCondition() == def->getExpression()) || isa<Zeroes>(def->getExpression()) || isa<Ones>(def->getExpression()))) {
127                        itr = defs.erase(itr);
128                        def->replaceWith(def->getExpression(), unusedOutsideOfNestedScope, true);
129                        evaluate = true;
130                        continue;
131                    }
132                    ++itr;
133                }
134            }
135
136            // If we ended up removing all of the defined variables, delete the If node.
137            if (LLVM_UNLIKELY(defs.empty())) {
138                stmt = stmt->eraseFromParent(true);
139                continue;
140            }
141            // Otherwise check if we any Assign reports the same value as another. If so, replace all uses of the
142            // second with the first. This will simplify future analysis.
143            for (auto i = defs.begin(); i != defs.end(); ++i) {
144                PabloAST * expr = (*i)->getExpression();
145                for (auto j = i + 1; j != defs.end(); ) {
146                    Assign * def = (*j);
147                    if (LLVM_UNLIKELY(def->getExpression() == expr)) {
148                        j = defs.erase(j);
149                        def->replaceWith(*i, false, true);
150                        continue;
151                    }
152                    ++j;
153                }
154            }
155        }
156        else if (isa<While>(stmt)) {
157            eliminateRedundantCode(cast<While>(stmt)->getBody(), &encountered);
158        }       
159        else if (stmt->getNumUses() == 0) {
160            // If this statement has no users, we can discard it. If a future "identical" statement occurs that does
161            // have users, we can use that statement instead.
162            stmt = stmt->eraseFromParent();
163            continue;
164        }
165        else if (canTriviallyFold(stmt)) { // non-Assign node
166
167            // Do a trivial folding test to see if we're using all 0s or 1s as an operand.
168            PabloAST * expr = nullptr;
169            block.setInsertPoint(stmt->getPrevNode());
170            switch (stmt->getClassTypeId()) {
171                case PabloAST::ClassTypeId::Advance:
172                    expr = block.createAdvance(stmt->getOperand(0), stmt->getOperand(1));
173                    break;
174                case PabloAST::ClassTypeId::And:
175                    expr = block.createAnd(stmt->getOperand(0), stmt->getOperand(1));
176                    break;
177                case PabloAST::ClassTypeId::Or:
178                    expr = block.createOr(stmt->getOperand(0), stmt->getOperand(1));
179                    break;
180                case PabloAST::ClassTypeId::Not:
181                    expr = block.createNot(stmt->getOperand(0));
182                    break;
183                case PabloAST::ClassTypeId::Xor:
184                    expr = block.createXor(stmt->getOperand(0), stmt->getOperand(1));
185                    break;
186                case PabloAST::ClassTypeId::Sel:
187                    expr = block.createSel(stmt->getOperand(0), stmt->getOperand(1), stmt->getOperand(2));
188                    break;
189                case PabloAST::ClassTypeId::ScanThru:
190                    expr = block.createScanThru(stmt->getOperand(0), stmt->getOperand(1));
191                    break;
192                case PabloAST::ClassTypeId::MatchStar:
193                    expr = block.createMatchStar(stmt->getOperand(0), stmt->getOperand(1));
194                    break;
195                case PabloAST::ClassTypeId::Next:
196                    expr = stmt;
197                    break;
198                default: {
199                    std::string tmp;
200                    llvm::raw_string_ostream msg(tmp);
201                    PabloPrinter::print(stmt, "Unhandled trivial folding optimization! ", msg);
202                    throw std::runtime_error(msg.str());
203                }
204            }
205            stmt = stmt->replaceWith(expr);
206            // the next statement could be an Assign; just restart the loop.
207            continue;
208        }
209        else {
210            // When we're creating the Pablo program, it's possible to have multiple instances of an "identical"
211            // statement. By recording which statements have already been seen, we can detect the redundant statements
212            // as any having the same type and operands. If so, we can replace its users with the prior statement.
213            // and erase this statement from the AST
214            const auto f = encountered.findOrAdd(stmt);
215            if (!std::get<1>(f)) {
216                stmt = stmt->replaceWith(std::get<0>(f));
217                continue;
218            }
219        }
220        assert (stmt);
221        stmt = stmt->getNextNode();
222    }
223    block.setInsertPoint(block.back());
224}
225
226
227void Simplifier::deadCodeElimination(PabloBlock & block) {
228    Statement * stmt = block.front();
229    while (stmt) {
230        if (isa<If>(stmt)) {
231            deadCodeElimination(cast<If>(stmt)->getBody());
232        }
233        else if (isa<While>(stmt)) {
234            deadCodeElimination(cast<While>(stmt)->getBody());
235        }
236        else if (stmt->getNumUses() == 0){
237            stmt = stmt->eraseFromParent(true);
238            continue;
239        }
240        stmt = stmt->getNextNode();
241    }
242}
243
244void Simplifier::eliminateRedundantComplexStatements(PabloBlock & block) {
245    Statement * stmt = block.front();
246    while (stmt) {
247        if (isa<If>(stmt)) {
248            eliminateRedundantComplexStatements(cast<If>(stmt)->getBody());
249        }
250        else if (isa<While>(stmt)) {
251            eliminateRedundantComplexStatements(cast<While>(stmt)->getBody());
252        }
253        else if (stmt->getNumOperands() == 2){
254            if (isa<Advance>(stmt)) {
255                // If we're advancing an Advance and the internal Advance does not have any other user,
256                // we can merge both Advance instructions.
257                if (LLVM_UNLIKELY(isa<Advance>(stmt->getOperand(0)))) {
258                    Advance * op = cast<Advance>(stmt->getOperand(0));
259                    if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
260                        Advance * adv = cast<Advance>(stmt);
261                        adv->setOperand(0, op->getOperand(0));
262                        adv->setOperand(1, block.getInteger(adv->getAdvanceAmount() + op->getAdvanceAmount()));
263                        assert(op->getNumUses() == 0);
264                        op->eraseFromParent();
265                    }
266                }
267            } else if (LLVM_UNLIKELY(isa<Advance>(stmt->getOperand(1)) && isa<Advance>(stmt->getOperand(0)))) {
268                // If an AND, OR or XOR instruction has two Advance instructions as inputs and neither Advance
269                // has another user and both shift their input by the same amount, we can perform the AND, OR
270                // or XOR on the inputs to the Advances and remove one of the Advance statements.
271
272                Advance * const a0 = cast<Advance>(stmt->getOperand(0));
273                Advance * const a1 = cast<Advance>(stmt->getOperand(1));
274                switch (stmt->getClassTypeId()) {
275                    case PabloAST::ClassTypeId::And:
276                    case PabloAST::ClassTypeId::Or:
277                    case PabloAST::ClassTypeId::Xor:
278                        if (LLVM_UNLIKELY(a0->getNumUses() == 1 && a1->getNumUses() == 1 && a0->getOperand(1) == a1->getOperand(1))) {
279                            block.setInsertPoint(stmt);
280                            stmt->setOperand(0, a0->getOperand(0));
281                            stmt->setOperand(1, a1->getOperand(0));
282                            a0->insertAfter(stmt);
283                            a0->setOperand(0, stmt);
284                            stmt->replaceAllUsesWith(a0);
285                            assert(a1->getNumUses() == 0);
286                            a1->eraseFromParent();
287                            stmt = a0;
288                    }
289                    default: break;
290                }
291            } else if (LLVM_UNLIKELY(isa<MatchStar>(stmt->getOperand(1)) && isa<MatchStar>(stmt->getOperand(0))) && isa<Or>(stmt)) {
292
293
294            } /*else if (LLVM_UNLIKELY(isa<Or>(stmt) && isa<And>(stmt->getOperand(0)) && isa<And>(stmt->getOperand(1)))) {
295
296                // If we have an OR(AND(A,B),AND(NOT(A),C)) statement and neither of the inner operands are used elsewhere, we can
297                // promote the Or to a Sel statement.
298
299                And * const a0 = cast<And>(stmt->getOperand(0));
300                And * const a1 = cast<And>(stmt->getOperand(1));
301
302                if (LLVM_UNLIKELY(a0->getNumUses() == 1 && a1->getNumUses() == 1)) {
303
304                    bool neg[4] = { false, false, false, false };
305
306                    for (unsigned i = 0; i != 2; ++i) {
307                        if (isa<Not>(a0->getOperand(i))) {
308                            PabloAST * i0 = cast<Not>(a0->getOperand(i))->getOperand(0);
309                            for (unsigned j = 0; j != 2; ++j) {
310                                if (a0->getOperand(j) == i0) {
311                                    neg[i + j * 2] = true;
312                                }
313                            }
314                        }
315                    }
316
317
318
319
320
321
322
323
324
325                }
326
327            }*/
328        }
329        stmt = stmt->getNextNode();
330    }
331    block.setInsertPoint(block.back());
332}
333
334Simplifier::Simplifier()
335{
336
337}
338
339
340}
Note: See TracBrowser for help on using the repository browser.