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

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

Misc changes + potential SIGBUS fix for issue reported by Hongpu.

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