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

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

Progress on multi-target UCD compiler.

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