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

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

Removed 'superfluous()' function from Assign nodes.

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