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

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

Work on lowering + some timing and papi information that will be cleaned up later.

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