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

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

Work on lowering + minor bug fixes.

File size: 20.5 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
13namespace pablo {
14
15#ifdef USE_BOOST
16template <typename Type>
17using SmallSet = boost::container::flat_set<Type>;
18#else
19template <typename Type>
20using SmallSet = std::unordered_set<Type>;
21#endif
22
23/** ------------------------------------------------------------------------------------------------------------- *
24 * @brief optimize
25 ** ------------------------------------------------------------------------------------------------------------- */
26bool Simplifier::optimize(PabloFunction & function) {
27    eliminateRedundantCode(function.getEntryBlock());
28    #ifndef NDEBUG
29    PabloVerifier::verify(function, "post-eliminate-redundant-code");
30    #endif
31    deadCodeElimination(function.getEntryBlock());
32    #ifndef NDEBUG
33    PabloVerifier::verify(function, "post-dead-code-elimination");
34    #endif
35    strengthReduction(function.getEntryBlock());
36    #ifndef NDEBUG
37    PabloVerifier::verify(function, "post-strength-reduction");
38    #endif
39    return true;
40}
41
42/** ------------------------------------------------------------------------------------------------------------- *
43 * @brief isReassociative
44 ** ------------------------------------------------------------------------------------------------------------- */
45inline bool isReassociative(const Statement * const stmt) {
46    switch (stmt->getClassTypeId()) {
47        case PabloAST::ClassTypeId::And:
48        case PabloAST::ClassTypeId::Or:
49        case PabloAST::ClassTypeId::Xor:
50            return true;
51        default: return false;
52    }
53}
54
55/** ------------------------------------------------------------------------------------------------------------- *
56 * @brief fold
57 ** ------------------------------------------------------------------------------------------------------------- */
58inline PabloAST * Simplifier::fold(Variadic * const var, PabloBlock * const block) {
59
60    assert (var);
61
62    bool negated = false;
63    if (LLVM_UNLIKELY(isa<Xor>(var))) {
64        for (unsigned i = 0; i != var->getNumOperands(); ++i) {
65            if (isa<Not>(var->getOperand(i))) {
66                // (A ⊕ ¬B) = (A ⊕ (B ⊕ 1)) = ¬(A ⊕ B)
67                var->setOperand(i, cast<Not>(var->getOperand(i))->getOperand(0));
68                negated = !negated;
69            }
70        }
71    }
72
73    // Ensure all operands of a reassociatiable function are consistently ordered.
74    std::sort(var->begin(), var->end());
75
76    // Apply the idempotence law to any And and Or statement and the identity law to any Xor
77    for (unsigned i = 1; i < var->getNumOperands(); ) {
78        if (var->getOperand(i - 1) == var->getOperand(i)) {
79            var->removeOperand(i);
80            if (LLVM_UNLIKELY(isa<Xor>(var))) {
81                var->removeOperand(i - 1);
82            }
83            continue;
84        }
85        ++i;
86    }
87
88    if (LLVM_LIKELY(!isa<Xor>(var))) {
89        // Apply the complementation law whenever possible.
90        for (unsigned i = 0; i < var->getNumOperands(); ++i) {
91            if (isa<Not>(var->getOperand(i))) {
92                const PabloAST * const negatedOp = cast<Not>(var->getOperand(i))->getOperand(0);
93                for (unsigned j = 0; j != var->getNumOperands(); ++j) {
94                    if (LLVM_UNLIKELY(equals(var->getOperand(j), negatedOp))) {
95                        if (isa<And>(var)) { // (A ∧ ¬A) ∧ B = 0 for any B
96                            return PabloBlock::createZeroes();
97                        } else if (isa<Or>(var)) { // (A √ ¬A) √ B = 1 for any B
98                            return PabloBlock::createOnes();
99                        }
100                    }
101                }
102            }
103        }
104    }
105
106    // Apply the annihilator and identity laws
107    for (unsigned i = 0; i != var->getNumOperands(); ) {
108        if (LLVM_UNLIKELY(isa<Zeroes>(var->getOperand(i)))) {
109            if (isa<And>(var)) {
110                return PabloBlock::createZeroes();
111            }
112            var->removeOperand(i);
113            continue;
114        } else if (LLVM_UNLIKELY(isa<Ones>(var->getOperand(i)))) {
115            if (isa<Or>(var)) {
116                return PabloBlock::createOnes();
117            } else if (isa<Xor>(var)) {
118                negated = !negated;
119            }
120            var->removeOperand(i);
121            continue;
122        }
123        ++i;
124    }
125
126    PabloAST * replacement = nullptr;
127    if (LLVM_UNLIKELY(var->getNumOperands() < 2)) {
128        replacement = (var->getNumOperands() == 0) ? PabloBlock::createZeroes() : var->getOperand(0);
129    }
130    if (LLVM_UNLIKELY(negated)) {
131        block->setInsertPoint(var);
132        replacement = block->createNot(replacement ? replacement : var);
133    }
134    return replacement;
135}
136
137/** ------------------------------------------------------------------------------------------------------------- *
138 * @brief fold
139 ** ------------------------------------------------------------------------------------------------------------- */
140inline PabloAST * Simplifier::fold(Statement * stmt, PabloBlock * block) {
141    if (isReassociative(stmt)) {
142        return fold(cast<Variadic>(stmt), block);
143    } else if (isa<Not>(stmt)) {
144        PabloAST * value = stmt->getOperand(0);
145        if (LLVM_UNLIKELY(isa<Not>(value))) {
146            return cast<Not>(value)->getOperand(0);
147        } else if (LLVM_UNLIKELY(isa<Zeroes>(value))) {
148            return block->createOnes();
149        }  else if (LLVM_UNLIKELY(isa<Ones>(value))) {
150            return block->createZeroes();
151        }
152    } else if (isa<Advance>(stmt)) {
153        if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(0)))) {
154            return block->createZeroes();
155        }
156    } else {
157        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
158            if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(i)))) {
159                switch (stmt->getClassTypeId()) {
160                    case PabloAST::ClassTypeId::Sel:
161                        block->setInsertPoint(stmt->getPrevNode());
162                        switch (i) {
163                            case 0: return stmt->getOperand(2);
164                            case 1: return block->createAnd(block->createNot(stmt->getOperand(0)), stmt->getOperand(2));
165                            case 2: return block->createAnd(stmt->getOperand(0), stmt->getOperand(1));
166                        }
167                    case PabloAST::ClassTypeId::ScanThru:
168                    case PabloAST::ClassTypeId::MatchStar:
169                        return stmt->getOperand(0);
170                    default: break;
171                }
172            } else if (LLVM_UNLIKELY(isa<Ones>(stmt->getOperand(i)))) {
173                block->setInsertPoint(stmt->getPrevNode());
174                switch (stmt->getClassTypeId()) {
175                    case PabloAST::ClassTypeId::Sel:
176                        block->setInsertPoint(stmt->getPrevNode());
177                        switch (i) {
178                            case 0: return stmt->getOperand(1);
179                            case 1: return block->createOr(stmt->getOperand(0), stmt->getOperand(2));
180                            case 2: return block->createOr(block->createNot(stmt->getOperand(0)), stmt->getOperand(1));
181                        }
182                    case PabloAST::ClassTypeId::ScanThru:
183                        if (i == 1) {
184                            return block->createZeroes();
185                        }
186                        break;
187                    case PabloAST::ClassTypeId::MatchStar:
188                        if (i == 0) {
189                            return block->createOnes();
190                        }
191                        break;
192                    default: break;
193                }
194            }
195        }       
196    }
197    return nullptr;
198}
199
200/** ------------------------------------------------------------------------------------------------------------- *
201 * @brief isSuperfluous
202 ** ------------------------------------------------------------------------------------------------------------- */
203inline bool Simplifier::isSuperfluous(const Assign * const assign) {
204    for (const PabloAST * user : assign->users()) {
205        if (LLVM_UNLIKELY(isa<PabloFunction>(user) || isa<Next>(user))) {
206            return false;
207        } else if (isa<If>(user)) {
208            if (LLVM_UNLIKELY(cast<If>(user)->getCondition() == assign)) {
209                continue;
210            } else if (isa<Assign>(assign->getExpression())) {
211                continue;
212            }
213            return false;
214        }
215    }
216    return true;
217}
218
219/** ------------------------------------------------------------------------------------------------------------- *
220 * @brief demoteDefinedVar
221 ** ------------------------------------------------------------------------------------------------------------- */
222inline bool demoteDefinedVar(const If * ifNode, const Assign * def) {
223    // If this value isn't used outside of this scope then there is no reason to allow it to escape it.
224    if (!escapes(def)) {
225        return true;
226    }
227    // Similarly if the defined variable is equivalent to the condition, an equivalent value is already available.
228    if (ifNode->getCondition() == def->getExpression()) {
229        return true;
230    }
231    // Finally, if the assignment is a constant, it's already known.
232    if (isa<Zeroes>(def->getExpression()) || isa<Ones>(def->getExpression()))  {
233        return true;
234    }
235    return false;
236}
237
238/** ------------------------------------------------------------------------------------------------------------- *
239 * @brief replaceReachableUsersOfWith
240 ** ------------------------------------------------------------------------------------------------------------- */
241inline void replaceReachableUsersOfWith(Statement * stmt, PabloAST * expr) {
242    const PabloBlock * const root = stmt->getParent();
243    SmallSet<const PabloBlock *> forbidden;
244    for (PabloAST * use : stmt->users()) {
245        if (LLVM_UNLIKELY(isa<Next>(use))) {
246            const PabloBlock * parent = cast<Next>(use)->getParent();
247            if (parent != root) {
248                forbidden.insert(parent);
249            }
250        }
251    }
252    for (PabloAST * use : stmt->users()) {
253        if (Statement * user = dyn_cast<Statement>(use)) {
254            const PabloBlock * parent = user->getParent();
255            while (parent && forbidden.count(parent) == 0) {
256                if (LLVM_UNLIKELY(parent == root)) {
257                    user->replaceUsesOfWith(stmt, expr);
258                    break;
259                }
260                parent = parent->getParent();
261            }
262        }
263    }
264}
265
266/** ------------------------------------------------------------------------------------------------------------- *
267 * @brief discardNestedIfBlock
268 *
269 * If this inner block is composed of only Boolean logic and Assign statements and there are fewer than 3
270 * statements, just add the statements in the inner block to the current block->
271 ** ------------------------------------------------------------------------------------------------------------- */
272inline bool discardNestedIfBlock(const PabloBlock * const block) {
273    unsigned computations = 0;
274    for (const Statement * stmt : *block) {
275        switch (stmt->getClassTypeId()) {
276            case PabloAST::ClassTypeId::And:
277            case PabloAST::ClassTypeId::Or:
278            case PabloAST::ClassTypeId::Xor:
279                if (++computations > 3) {
280                    return false;
281                }
282            case PabloAST::ClassTypeId::Not:
283            case PabloAST::ClassTypeId::Assign:
284                break;
285            default:
286                return false;
287        }
288    }
289    return true;
290}
291
292/** ------------------------------------------------------------------------------------------------------------- *
293 * @brief removeIdenticalEscapedValues
294 ** ------------------------------------------------------------------------------------------------------------- */
295template <class ValueList, class ValueType = typename ValueList::value_type>
296inline void removeIdenticalEscapedValues(ValueList & list) {
297    std::vector<ValueType> identicalValues;
298    for (auto i = list.begin(); i != list.end(); ++i) {
299        for (auto j = i + 1; j != list.end(); ++j) {
300            if (LLVM_UNLIKELY(equals(*i, *j))) {
301                identicalValues.push_back(*j);
302            }
303        }
304        for (ValueType identicalValue : identicalValues) {
305            identicalValue->replaceWith(*i);
306        }
307        identicalValues.clear();
308    }
309}
310
311/** ------------------------------------------------------------------------------------------------------------- *
312 * @brief eliminateRedundantCode
313 *
314 * Note: Do not recursively delete statements in this function. The ExpressionTable could use deleted statements
315 * as replacements. Let the DCE remove the unnecessary statements with the finalized Def-Use information.
316 ** ------------------------------------------------------------------------------------------------------------- */
317void Simplifier::eliminateRedundantCode(PabloBlock * const block, ExpressionTable * predecessor) {
318    ExpressionTable encountered(predecessor);
319    Statement * stmt = block->front();
320
321    while (stmt) {
322
323        if (Assign * assign = dyn_cast<Assign>(stmt)) {
324            // If we have an Assign whose users do not contain an If or Next node, we can replace its users with
325            // the Assign's expression directly.
326            if (isSuperfluous(assign)) {
327                stmt = assign->replaceWith(assign->getExpression());               
328                continue;
329            }
330            // Force the uses of an Assign node that can reach the original expression to use the expression instead.
331            replaceReachableUsersOfWith(assign, assign->getExpression());
332        } else if (Next * next = dyn_cast<Next>(stmt)) {
333            replaceReachableUsersOfWith(next, next->getExpr());
334        } else if (If * ifNode = dyn_cast<If>(stmt)) {
335            // Test whether we can ever take this branch
336            if (LLVM_UNLIKELY(isa<Zeroes>(cast<If>(stmt)->getCondition()))) {
337                stmt = stmt->eraseFromParent();
338                continue;
339            }
340            // Test whether all of the defined variables are necessary
341            If::DefinedVars & defs = ifNode->getDefined();
342            for (auto def = defs.begin(); def != defs.end(); ) {
343                if (LLVM_UNLIKELY(demoteDefinedVar(ifNode, *def))) {
344                    (*def)->replaceWith((*def)->getExpression());
345                    def = ifNode->removeDefined(*def);
346                    continue;
347                }
348                ++def;
349            }
350
351            // Process the If body
352            eliminateRedundantCode(cast<If>(stmt)->getBody(), &encountered);
353
354            // If we ended up removing all of the defined variables, delete the If node.
355            if (LLVM_UNLIKELY(defs.empty())) {
356                stmt = stmt->eraseFromParent();
357                continue;
358            }
359
360            // Otherwise check if we any Assign reports the same value as another. If so, replace all uses of the
361            // second with the first. This will simplify future analysis.
362            removeIdenticalEscapedValues(ifNode->getDefined());
363
364            // Finally after we've eliminated everything we can from the If body, check whether testing the If
365            // condition will meet or exceed the cost of executing the body.
366            if (LLVM_UNLIKELY(discardNestedIfBlock(ifNode->getBody()))) {
367                Statement * nested = ifNode->getBody()->front();
368                while (nested) {
369                    Statement * next = nested->removeFromParent();
370                    if (isa<Assign>(nested)) {
371                        ifNode->removeDefined(cast<Assign>(nested));
372                    }
373                    nested->insertAfter(stmt);
374                    stmt = nested;
375                    nested = next;
376                }
377                stmt = ifNode->eraseFromParent();
378                continue;
379            }
380
381        } else if (While * whileNode = dyn_cast<While>(stmt)) {
382            // Test whether we can ever take this branch
383            const PabloAST * initial = cast<While>(stmt)->getCondition();
384            if (LLVM_LIKELY(isa<Next>(initial))) {
385                initial = cast<Next>(initial)->getInitial();
386            }
387            if (LLVM_UNLIKELY(isa<Zeroes>(initial))) {
388                stmt = stmt->eraseFromParent();
389                continue;
390            }
391            eliminateRedundantCode(whileNode->getBody(), &encountered);
392            removeIdenticalEscapedValues(whileNode->getVariants());
393            // If the condition's Next state is Zero, we can eliminate the loop after copying the internal
394            // statements into the body.
395        } else {
396            if (PabloAST * folded = fold(stmt, block)) {
397                // If we determine we can fold this statement,
398                Statement * const prior = stmt->getPrevNode();
399                stmt->replaceWith(folded, true);
400                stmt = LLVM_LIKELY(prior != nullptr) ? prior->getNextNode() : block->front();
401                continue;
402            }
403            // When we're creating the Pablo program, it's possible to have multiple instances of an "identical"
404            // statement. By recording which statements have already been seen, we can detect the redundant statements
405            // as any having the same type and operands. If so, we can replace its users with the prior statement.
406            // and erase this statement from the AST
407            const auto f = encountered.findOrAdd(stmt);
408            if (!f.second) {
409                stmt = stmt->replaceWith(f.first, true);
410                continue;
411            }
412
413        }
414        stmt = stmt->getNextNode();
415    }
416}
417
418/** ------------------------------------------------------------------------------------------------------------- *
419 * @brief deadCodeElimination
420 ** ------------------------------------------------------------------------------------------------------------- */
421void Simplifier::deadCodeElimination(PabloBlock * const block) {
422    Statement * stmt = block->front();
423    while (stmt) {
424        if (isa<If>(stmt)) {
425            deadCodeElimination(cast<If>(stmt)->getBody());
426        } else if (isa<While>(stmt)) {
427            deadCodeElimination(cast<While>(stmt)->getBody());
428        } else if (stmt->getNumUses() == 0){
429            stmt = stmt->eraseFromParent(true);
430            continue;
431        }
432        stmt = stmt->getNextNode();
433    }
434}
435
436/** ------------------------------------------------------------------------------------------------------------- *
437 * @brief strengthReduction
438 *
439 * Find and replace any Pablo operations with the less expensive equivalent operations whenever possible.
440 ** ------------------------------------------------------------------------------------------------------------- */
441void Simplifier::strengthReduction(PabloBlock * const block) {
442    Statement * stmt = block->front();
443    while (stmt) {
444        if (isa<If>(stmt)) {
445            strengthReduction(cast<If>(stmt)->getBody());
446        } else if (isa<While>(stmt)) {
447            strengthReduction(cast<While>(stmt)->getBody());
448        } else if (isa<Advance>(stmt)) {
449            Advance * adv = cast<Advance>(stmt);
450            if (LLVM_UNLIKELY(isa<Advance>(adv->getOperand(0)))) {
451                // Replace an Advance(Advance(x, n), m) with an Advance(x,n + m)
452                Advance * op = cast<Advance>(stmt->getOperand(0));
453                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
454                    adv->setOperand(0, op->getOperand(0));
455                    adv->setOperand(1, block->getInteger(adv->getAdvanceAmount() + op->getAdvanceAmount()));
456                    op->eraseFromParent(false);
457                }
458            }
459        } else if (LLVM_UNLIKELY(isa<ScanThru>(stmt))) {
460            ScanThru * scanThru = cast<ScanThru>(stmt);
461            if (LLVM_UNLIKELY(isa<Advance>(scanThru->getOperand(0)))) {
462                // Replace a ScanThru(Advance(x,n),y) with an ScanThru(Advance(x, n - 1), Advance(x, n - 1) | y), where Advance(x, 0) = x
463                Advance * op = cast<Advance>(stmt->getOperand(0));
464                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
465                    block->setInsertPoint(scanThru->getPrevNode());
466                    PabloAST * expr = block->createAdvance(op->getOperand(0), op->getAdvanceAmount() - 1);
467                    scanThru->setOperand(0, expr);
468                    scanThru->setOperand(1, block->createOr(scanThru->getOperand(1), expr));
469                    op->eraseFromParent(false);
470                }
471            }
472        }
473        stmt = stmt->getNextNode();
474    }
475    block->setInsertPoint(block->back());
476}
477
478}
Note: See TracBrowser for help on using the repository browser.