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

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

Temporary check in.

File size: 10.7 KB
RevLine 
[4416]1#include <pablo/optimizers/pablo_simplifier.hpp>
2#include <pablo/codegenstate.h>
3#include <pablo/expression_map.hpp>
[4657]4#include <pablo/function.h>
[4419]5#include <pablo/printer_pablos.h>
[4416]6
7
8
9namespace pablo {
10
[4657]11bool Simplifier::optimize(PabloFunction & function) {
12    eliminateRedundantCode(function.getEntryBlock());
13    deadCodeElimination(function.getEntryBlock());
14    eliminateRedundantComplexStatements(function.getEntryBlock());
[4416]15    return true;
16}
17
[4432]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
[4433]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
[4432]42
[4658]43inline bool Simplifier::isSuperfluous(const Assign * const assign) {
44    for (const PabloAST * inst : assign->users()) {
[4699]45        if (isa<Next>(inst) || isa<PabloFunction>(inst)) {
[4658]46            return false;
[4699]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;
[4658]62        }
63    }
64    return true;
65}
66
[4419]67void Simplifier::eliminateRedundantCode(PabloBlock & block, ExpressionTable * predecessor) {
[4416]68    ExpressionTable encountered(predecessor);
69
70    Statement * stmt = block.front();
[4433]71
[4416]72    while (stmt) {
[4433]73
74        assert (stmt);
75        assert (verifyStatementIsInSameBlock(stmt, block));
76
77        if (Assign * assign = dyn_cast<Assign>(stmt)) {
[4416]78            // If we have an Assign whose users do not contain an If or Next node, we can replace its users with
[4433]79            // the Assign's expression directly.
[4658]80            if (isSuperfluous(assign)) {
81                if (assign->getNumUses() == 0) {
[4510]82                    stmt = assign->eraseFromParent();
83                }
84                else {
[4699]85                    stmt = assign->replaceWith(assign->getExpression(), true, true);
[4510]86                }
[4416]87                continue;
88            }
89        }
[4594]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()))) {
[4658]93                for (Assign * defVar : ifNode->getDefined()) {
94                    defVar->replaceWith(block.createZeroes(), false, true);
[4594]95                }
96                stmt = stmt->eraseFromParent(true);
97                continue;
98            }
99            // Process the If body
[4433]100            eliminateRedundantCode(cast<If>(stmt)->getBody(), &encountered);
[4594]101            // Scan through and replace any defined variable that is assigned Zero with a Zero object
102            // and remove it from the defined variable list.
103            If::DefinedVars & defVars = ifNode->getDefined();
104            for (auto i = defVars.begin(); i != defVars.end(); ) {
105                Assign * defVar = cast<Assign>(*i);
[4657]106                if (LLVM_UNLIKELY(isa<Zeroes>(defVar->getExpression()))) {
[4594]107                    i = defVars.erase(i);
108                    defVar->replaceWith(block.createZeroes(), false, true);
109                    continue;
110                }
111                ++i;
112            }
113            // If we ended up Zero-ing out all of the defined variables, delete the If node.
114            if (LLVM_UNLIKELY(defVars.empty())) {
115                stmt = stmt->eraseFromParent(true);
116                continue;
117            }
[4433]118        }
119        else if (isa<While>(stmt)) {
120            eliminateRedundantCode(cast<While>(stmt)->getBody(), &encountered);
121        }       
122        else if (stmt->getNumUses() == 0) {
123            // If this statement has no users, we can discard it. If a future "identical" statement occurs that does
124            // have users, we can use that statement instead.
125            stmt = stmt->eraseFromParent();
126            continue;
127        }
128        else if (canTriviallyFold(stmt)) { // non-Assign node
[4416]129
[4419]130            // Do a trivial folding test to see if we're using all 0s or 1s as an operand.
[4433]131            PabloAST * expr = nullptr;
132            block.setInsertPoint(stmt->getPrevNode());
133            switch (stmt->getClassTypeId()) {
134                case PabloAST::ClassTypeId::Advance:
135                    expr = block.createAdvance(stmt->getOperand(0), stmt->getOperand(1));
136                    break;
137                case PabloAST::ClassTypeId::And:
138                    expr = block.createAnd(stmt->getOperand(0), stmt->getOperand(1));
139                    break;
140                case PabloAST::ClassTypeId::Or:
141                    expr = block.createOr(stmt->getOperand(0), stmt->getOperand(1));
142                    break;
143                case PabloAST::ClassTypeId::Not:
144                    expr = block.createNot(stmt->getOperand(0));
145                    break;
146                case PabloAST::ClassTypeId::Xor:
147                    expr = block.createXor(stmt->getOperand(0), stmt->getOperand(1));
148                    break;
149                case PabloAST::ClassTypeId::Sel:
150                    expr = block.createSel(stmt->getOperand(0), stmt->getOperand(1), stmt->getOperand(2));
151                    break;
152                case PabloAST::ClassTypeId::ScanThru:
153                    expr = block.createScanThru(stmt->getOperand(0), stmt->getOperand(1));
154                    break;
155                case PabloAST::ClassTypeId::MatchStar:
156                    expr = block.createMatchStar(stmt->getOperand(0), stmt->getOperand(1));
157                    break;
[4611]158                case PabloAST::ClassTypeId::Next:
159                    expr = stmt;
160                    break;
161                default: {
162                    std::string tmp;
163                    llvm::raw_string_ostream msg(tmp);
164                    PabloPrinter::print(stmt, "Unhandled trivial folding optimization! ", msg);
165                    throw std::runtime_error(msg.str());
166                }
[4419]167            }
[4433]168            stmt = stmt->replaceWith(expr);
169            // the next statement could be an Assign; just restart the loop.
170            continue;
[4416]171        }
[4434]172        else {
173            // When we're creating the Pablo program, it's possible to have multiple instances of an "identical"
174            // statement. By recording which statements have already been seen, we can detect the redundant statements
175            // as any having the same type and operands. If so, we can replace its users with the prior statement.
176            // and erase this statement from the AST
[4443]177            const auto f = encountered.findOrAdd(stmt);
[4434]178            if (!std::get<1>(f)) {
179                stmt = stmt->replaceWith(std::get<0>(f));
180                continue;
181            }
[4433]182        }
183        assert (stmt);
[4416]184        stmt = stmt->getNextNode();
185    }
[4419]186    block.setInsertPoint(block.back());
[4416]187}
188
189
[4419]190void Simplifier::deadCodeElimination(PabloBlock & block) {
191    Statement * stmt = block.front();
192    while (stmt) {
193        if (isa<If>(stmt)) {
194            deadCodeElimination(cast<If>(stmt)->getBody());
195        }
196        else if (isa<While>(stmt)) {
197            deadCodeElimination(cast<While>(stmt)->getBody());
198        }
199        else if (stmt->getNumUses() == 0){
[4658]200            stmt = stmt->eraseFromParent(true);
201            continue;
[4419]202        }
203        stmt = stmt->getNextNode();
204    }
[4416]205}
206
[4569]207void Simplifier::eliminateRedundantComplexStatements(PabloBlock & block) {
208    Statement * stmt = block.front();
209    while (stmt) {
210        if (isa<If>(stmt)) {
211            eliminateRedundantComplexStatements(cast<If>(stmt)->getBody());
212        }
213        else if (isa<While>(stmt)) {
214            eliminateRedundantComplexStatements(cast<While>(stmt)->getBody());
215        }
216        else if (stmt->getNumOperands() == 2){
217            if (isa<Advance>(stmt)) {
218                // If we're advancing an Advance and the internal Advance does not have any other user,
219                // we can merge both Advance instructions.
220                if (LLVM_UNLIKELY(isa<Advance>(stmt->getOperand(0)))) {
221                    Advance * op = cast<Advance>(stmt->getOperand(0));
222                    if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
223                        Advance * adv = cast<Advance>(stmt);
224                        adv->setOperand(0, op->getOperand(0));
225                        adv->setOperand(1, block.getInteger(adv->getAdvanceAmount() + op->getAdvanceAmount()));
226                        assert(op->getNumUses() == 0);
227                        op->eraseFromParent();
228                    }
229                }
230            }
231            // If an AND, OR or XOR instruction has two Advance instructions as inputs and neither Advance
232            // has another user and both shift their input by the same amount, we can perform the AND, OR
233            // or XOR on the inputs to the Advances and remove one of the Advance statements.
234            else if (LLVM_UNLIKELY(isa<Advance>(stmt->getOperand(1)) && isa<Advance>(stmt->getOperand(0)))) {
235                Advance * const a0 = cast<Advance>(stmt->getOperand(0));
236                Advance * const a1 = cast<Advance>(stmt->getOperand(1));
237                switch (stmt->getClassTypeId()) {
238                    case PabloAST::ClassTypeId::And:
239                    case PabloAST::ClassTypeId::Or:
240                    case PabloAST::ClassTypeId::Xor:
241                        if (LLVM_UNLIKELY(a0->getNumUses() == 1 && a1->getNumUses() == 1 && a0->getOperand(1) == a1->getOperand(1))) {
242                            block.setInsertPoint(stmt);
243                            stmt->setOperand(0, a0->getOperand(0));
244                            stmt->setOperand(1, a1->getOperand(0));
245                            a0->insertAfter(stmt);
246                            a0->setOperand(0, stmt);
247                            stmt->replaceAllUsesWith(a0);
248                            assert(a1->getNumUses() == 0);
249                            a1->eraseFromParent();
250                            stmt = a0;
251                    }
252                    default: break;
253                }
254            }
255            else if (LLVM_UNLIKELY(isa<MatchStar>(stmt->getOperand(1)) && isa<MatchStar>(stmt->getOperand(0))) && isa<Or>(stmt)) {
[4416]256
257
[4569]258            }
259        }
260        stmt = stmt->getNextNode();
261    }
262    block.setInsertPoint(block.back());
263}
[4416]264
[4569]265
[4416]266Simplifier::Simplifier()
267{
268
269}
270
271
272}
Note: See TracBrowser for help on using the repository browser.