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

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

Back-up check in

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