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

Last change on this file since 4856 was 4856, checked in by nmedfort, 3 years ago

Bug fix for use-def correctness regarding escaping values of If and While nodes.

File size: 16.6 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
24/** ------------------------------------------------------------------------------------------------------------- *
25 * @brief optimize
26 ** ------------------------------------------------------------------------------------------------------------- */
27bool Simplifier::optimize(PabloFunction & function) {
28    eliminateRedundantCode(function.getEntryBlock());
29    deadCodeElimination(function.getEntryBlock());
30    eliminateRedundantEquations(function.getEntryBlock());
31    #ifndef NDEBUG
32    PabloVerifier::verify(function, "post-simplification");
33    #endif
34    return true;
35}
36
37/** ------------------------------------------------------------------------------------------------------------- *
38 * @brief canTriviallyFold
39 ** ------------------------------------------------------------------------------------------------------------- */
40inline static PabloAST * canTriviallyFold(Statement * stmt, PabloBlock & block) {
41    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
42        if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(i)))) {
43            switch (stmt->getClassTypeId()) {
44                case PabloAST::ClassTypeId::And:
45                case PabloAST::ClassTypeId::Advance:
46                    return block.createZeroes();
47                case PabloAST::ClassTypeId::Xor:
48                case PabloAST::ClassTypeId::Or:
49                    return stmt->getOperand(1 - i);
50                case PabloAST::ClassTypeId::Not:
51                    return block.createOnes();
52                case PabloAST::ClassTypeId::Sel:
53                    block.setInsertPoint(stmt->getPrevNode());
54                    switch (i) {
55                        case 0: return stmt->getOperand(2);
56                        case 1: return block.createAnd(block.createNot(stmt->getOperand(0)), stmt->getOperand(2));
57                        case 2: return block.createAnd(stmt->getOperand(0), stmt->getOperand(1));
58                    }
59                case PabloAST::ClassTypeId::ScanThru:
60                case PabloAST::ClassTypeId::MatchStar:
61                    return stmt->getOperand(0);
62                default: break;
63            }
64        } else if (LLVM_UNLIKELY(isa<Ones>(stmt->getOperand(i)))) {
65            block.setInsertPoint(stmt->getPrevNode());
66            switch (stmt->getClassTypeId()) {
67                case PabloAST::ClassTypeId::And:
68                    return stmt->getOperand(1 - i);
69                case PabloAST::ClassTypeId::Or:
70                    return block.createOnes();
71                case PabloAST::ClassTypeId::Xor:
72                    return block.createNot(stmt->getOperand(1 - i));
73                case PabloAST::ClassTypeId::Not:
74                    return block.createZeroes();
75                case PabloAST::ClassTypeId::Sel:
76                    block.setInsertPoint(stmt->getPrevNode());
77                    switch (i) {
78                        case 0: return stmt->getOperand(1);
79                        case 1: return block.createOr(stmt->getOperand(0), stmt->getOperand(2));
80                        case 2: return block.createOr(block.createNot(stmt->getOperand(0)), stmt->getOperand(1));
81                    }
82                case PabloAST::ClassTypeId::ScanThru:
83                    if (i == 1) {
84                        return block.createZeroes();
85                    }
86                    break;
87                case PabloAST::ClassTypeId::MatchStar:
88                    if (i == 0) {
89                        return block.createOnes();
90                    }
91                    break;
92                default: break;
93            }
94        }
95    }
96    return nullptr;
97}
98
99/** ------------------------------------------------------------------------------------------------------------- *
100 * @brief isSuperfluous
101 ** ------------------------------------------------------------------------------------------------------------- */
102inline bool Simplifier::isSuperfluous(const Assign * const assign) {
103    for (const PabloAST * inst : assign->users()) {
104        if (isa<Next>(inst) || isa<PabloFunction>(inst)) {
105            return false;
106        } else if (isa<If>(inst)) {
107            const If * ifNode = cast<If>(inst);
108            if (ifNode->getCondition() == assign) {
109                bool notFound = true;
110                for (Assign * defVar : ifNode->getDefined()) {
111                    if (defVar == assign) {
112                        notFound = false;
113                        break;
114                    }
115                }
116                if (notFound) {
117                    continue;
118                }
119            }
120            return false;
121        }
122    }
123    return true;
124}
125
126/** ------------------------------------------------------------------------------------------------------------- *
127 * @brief demoteDefinedVar
128 ** ------------------------------------------------------------------------------------------------------------- */
129inline bool demoteDefinedVar(const If * ifNode, const Assign * def) {
130    // If this value isn't used outside of this scope then there is no reason to allow it to escape it.
131    if (!escapes(def)) {
132        return true;
133    }
134    // Similarly if the defined variable is equivalent to the condition, an equivalent value is already available.
135    if (ifNode->getCondition() == def->getExpression()) {
136        return true;
137    }
138    // Finally, if the assignment is a constant, it's already known.
139    if (isa<Zeroes>(def->getExpression()) || isa<Ones>(def->getExpression()))  {
140        return true;
141    }
142    return false;
143}
144
145/** ------------------------------------------------------------------------------------------------------------- *
146 * @brief replaceReachableUsersOfWith
147 ** ------------------------------------------------------------------------------------------------------------- */
148inline void replaceReachableUsersOfWith(Statement * stmt, PabloAST * expr) {
149    const PabloBlock * const root = stmt->getParent();
150    SmallSet<const PabloBlock *> forbidden;
151    for (PabloAST * use : stmt->users()) {
152        if (LLVM_UNLIKELY(isa<Next>(use))) {
153            const PabloBlock * parent = cast<Next>(use)->getParent();
154            if (parent != root) {
155                forbidden.insert(parent);
156            }
157        }
158    }
159    for (PabloAST * use : stmt->users()) {
160        if (Statement * user = dyn_cast<Statement>(use)) {
161            const PabloBlock * parent = user->getParent();
162            while (parent && forbidden.count(parent) == 0) {
163                if (LLVM_UNLIKELY(parent == root)) {
164                    user->replaceUsesOfWith(stmt, expr);
165                    break;
166                }
167                parent = parent->getParent();
168            }
169        }
170    }
171}
172
173/** ------------------------------------------------------------------------------------------------------------- *
174 * @brief discardNestedIfBlock
175 *
176 * If this inner block is composed of only Boolean logic and Assign statements and there are fewer than 3
177 * statements, just add the statements in the inner block to the current block.
178 ** ------------------------------------------------------------------------------------------------------------- */
179inline bool discardNestedIfBlock(const PabloBlock & pb) {
180    unsigned computations = 0;
181    for (const Statement * stmt : pb) {
182        switch (stmt->getClassTypeId()) {
183            case PabloAST::ClassTypeId::And:
184            case PabloAST::ClassTypeId::Or:
185            case PabloAST::ClassTypeId::Xor:
186                if (++computations > 3) {
187                    return false;
188                }
189            case PabloAST::ClassTypeId::Not:
190            case PabloAST::ClassTypeId::Assign:
191                break;
192            default:
193                return false;
194        }
195    }
196    return true;
197}
198
199/** ------------------------------------------------------------------------------------------------------------- *
200 * @brief removeIdenticalEscapedValues
201 ** ------------------------------------------------------------------------------------------------------------- */
202template <class ValueList, class ValueType = typename ValueList::value_type>
203inline void removeIdenticalEscapedValues(ValueList & list) {
204    std::vector<ValueType> identicalValues;
205    for (auto i = list.begin(); i != list.end(); ++i) {
206        for (auto j = i + 1; j != list.end(); ++j) {
207            if (LLVM_UNLIKELY(equals(*i, *j))) {
208                identicalValues.push_back(*j);
209            }
210        }
211        for (ValueType identicalValue : identicalValues) {
212            identicalValue->replaceWith(*i);
213        }
214        identicalValues.clear();
215    }
216}
217
218/** ------------------------------------------------------------------------------------------------------------- *
219 * @brief eliminateRedundantCode
220 ** ------------------------------------------------------------------------------------------------------------- */
221void Simplifier::eliminateRedundantCode(PabloBlock & block, ExpressionTable * predecessor) {
222    ExpressionTable encountered(predecessor);
223    Statement * stmt = block.front();
224    while (stmt) {
225        if (Assign * assign = dyn_cast<Assign>(stmt)) {
226            // If we have an Assign whose users do not contain an If or Next node, we can replace its users with
227            // the Assign's expression directly.
228            if (isSuperfluous(assign)) {
229                if (assign->getNumUses() == 0) {
230                    stmt = assign->eraseFromParent();
231                } else {
232                    stmt = assign->replaceWith(assign->getExpression(), true, true);
233                }
234                continue;
235            }
236            // Force the uses of an Assign node that can reach the original expression to use the expression instead.
237            replaceReachableUsersOfWith(assign, assign->getExpression());
238        } else if (Next * next = dyn_cast<Next>(stmt)) {
239            replaceReachableUsersOfWith(next, next->getExpr());
240        } else if (If * ifNode = dyn_cast<If>(stmt)) {
241            // Check to see if the Cond is Zero and delete the loop.
242            if (LLVM_UNLIKELY(isa<Zeroes>(ifNode->getCondition()))) {
243                stmt = stmt->eraseFromParent(true);
244                continue;
245            }
246
247            bool evaluate = true;
248            If::DefinedVars & defs = ifNode->getDefined();
249            while (evaluate) {
250                evaluate = false;
251                // Process the If body
252                eliminateRedundantCode(cast<If>(stmt)->getBody(), &encountered);
253                // Now test whether all of the defined variables are necessary
254                for (auto itr = defs.begin(); itr != defs.end(); ) {
255                    Assign * def = *itr;
256                    if (LLVM_UNLIKELY(demoteDefinedVar(ifNode, def))) {
257                        itr = defs.erase(itr);
258                        def->replaceWith(def->getExpression(), false, true);
259                        evaluate = true;
260                        continue;
261                    }
262                    ++itr;
263                }
264            }
265
266            // If we ended up removing all of the defined variables, delete the If node.
267            if (LLVM_UNLIKELY(defs.empty())) {
268                stmt = stmt->eraseFromParent(true);
269                continue;
270            }
271
272            // Otherwise check if we any Assign reports the same value as another. If so, replace all uses of the
273            // second with the first. This will simplify future analysis.
274            removeIdenticalEscapedValues(ifNode->getDefined());
275
276            // Finally after we've eliminated everything we can from the If body, check whether testing the If
277            // condition will meet or exceed the cost of executing the body.
278            if (LLVM_UNLIKELY(discardNestedIfBlock(ifNode->getBody()))) {
279                Statement * nested = ifNode->getBody().front();
280                while (nested) {
281                    Statement * next = nested->removeFromParent();
282                    if (isa<Assign>(nested)) {
283                        ifNode->removeDefined(cast<Assign>(nested));
284                    }
285                    nested->insertAfter(stmt);
286                    stmt = nested;
287                    nested = next;
288                }
289                stmt = ifNode->eraseFromParent(true);
290                continue;
291            }
292
293        } else if (While * whileNode = dyn_cast<While>(stmt)) {
294            const PabloAST * initial = whileNode->getCondition();
295            if (LLVM_LIKELY(isa<Next>(initial))) {
296                initial = cast<Next>(initial)->getInitial();
297            }
298            if (LLVM_UNLIKELY(isa<Zeroes>(initial))) {
299                stmt = stmt->eraseFromParent(true);
300                continue;
301            }
302            eliminateRedundantCode(whileNode->getBody(), &encountered);
303            removeIdenticalEscapedValues(whileNode->getVariants());
304        } else if (PabloAST * expr = canTriviallyFold(stmt, block)) {
305            stmt = stmt->replaceWith(expr, true, true);
306            continue;
307        } else {
308            // When we're creating the Pablo program, it's possible to have multiple instances of an "identical"
309            // statement. By recording which statements have already been seen, we can detect the redundant statements
310            // as any having the same type and operands. If so, we can replace its users with the prior statement.
311            // and erase this statement from the AST
312            const auto f = encountered.findOrAdd(stmt);
313            if (!f.second) {
314                stmt = stmt->replaceWith(f.first, true, true);
315                continue;
316            }
317        }
318        stmt = stmt->getNextNode();
319    }
320}
321
322/** ------------------------------------------------------------------------------------------------------------- *
323 * @brief deadCodeElimination
324 ** ------------------------------------------------------------------------------------------------------------- */
325void Simplifier::deadCodeElimination(PabloBlock & block) {
326    Statement * stmt = block.front();
327    while (stmt) {
328        if (isa<If>(stmt)) {
329            deadCodeElimination(cast<If>(stmt)->getBody());
330        } else if (isa<While>(stmt)) {
331            deadCodeElimination(cast<While>(stmt)->getBody());
332        } else if (stmt->getNumUses() == 0){
333            stmt = stmt->eraseFromParent(true);
334            continue;
335        }
336        stmt = stmt->getNextNode();
337    }
338}
339
340/** ------------------------------------------------------------------------------------------------------------- *
341 * @brief eliminateRedundantEquations
342 ** ------------------------------------------------------------------------------------------------------------- */
343void Simplifier::eliminateRedundantEquations(PabloBlock & block) {
344    Statement * stmt = block.front();
345    while (stmt) {
346        if (isa<If>(stmt)) {
347            eliminateRedundantEquations(cast<If>(stmt)->getBody());
348        } else if (isa<While>(stmt)) {
349            eliminateRedundantEquations(cast<While>(stmt)->getBody());
350        } else if (isa<Advance>(stmt)) {
351            Advance * adv = cast<Advance>(stmt);
352            if (LLVM_UNLIKELY(isa<Advance>(adv->getOperand(0)))) {
353                // Replace an Advance(Advance(x, n), m) with an Advance(x,n + m)
354                Advance * op = cast<Advance>(stmt->getOperand(0));
355                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
356                    adv->setOperand(0, op->getOperand(0));
357                    adv->setOperand(1, block.getInteger(adv->getAdvanceAmount() + op->getAdvanceAmount()));
358                    op->eraseFromParent(false);
359                }
360            }
361        } else if (LLVM_UNLIKELY(isa<ScanThru>(stmt))) {
362            ScanThru * scanThru = cast<ScanThru>(stmt);
363            if (LLVM_UNLIKELY(isa<Advance>(scanThru->getOperand(0)))) {
364                // Replace a ScanThru(Advance(x,n),y) with an ScanThru(Advance(x, n - 1), Advance(x, n - 1) | y), where Advance(x, 0) = x
365                Advance * op = cast<Advance>(stmt->getOperand(0));
366                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
367                    block.setInsertPoint(scanThru->getPrevNode());
368                    PabloAST * expr = block.createAdvance(op->getOperand(0), op->getAdvanceAmount() - 1);
369                    scanThru->setOperand(0, expr);
370                    scanThru->setOperand(1, block.createOr(scanThru->getOperand(1), expr));
371                    op->eraseFromParent(false);
372                }
373            }
374        }
375        stmt = stmt->getNextNode();
376    }
377    block.setInsertPoint(block.back());
378}
379
380}
Note: See TracBrowser for help on using the repository browser.