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

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

More work on n-ary operations. Unresolved bug in DistributionPass?.

File size: 20.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#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 foldReassociativeFunction
57 ** ------------------------------------------------------------------------------------------------------------- */
58PabloAST * Simplifier::foldReassociativeFunction(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                if (LLVM_UNLIKELY(var->getNumOperands() == 0)) {
83                    return PabloBlock::createZeroes();
84                }
85            }
86            continue;
87        }
88        ++i;
89    }
90
91    if (LLVM_LIKELY(!isa<Xor>(var))) {
92        // Apply the complementation law whenever possible.
93        for (unsigned i = 0; i < var->getNumOperands(); ++i) {
94            if (isa<Not>(var->getOperand(i))) {
95                const PabloAST * const negatedOp = cast<Not>(var->getOperand(i))->getOperand(0);
96                for (unsigned j = 0; j != var->getNumOperands(); ++j) {
97                    if (LLVM_UNLIKELY(equals(var->getOperand(j), negatedOp))) {
98                        if (isa<And>(var)) { // (A ∧ ¬A) ∧ B = 0 for any B
99                            return PabloBlock::createZeroes();
100                        } else if (isa<Or>(var)) { // (A √ ¬A) √ B = 1 for any B
101                            return PabloBlock::createOnes();
102                        }
103                    }
104                }
105            }
106        }
107    }
108
109    // Apply the annihilator and identity laws
110    for (unsigned i = 0; i != var->getNumOperands(); ) {
111        if (LLVM_UNLIKELY(isa<Zeroes>(var->getOperand(i)))) {
112            if (isa<And>(var)) {
113                return PabloBlock::createZeroes();
114            }
115            var->removeOperand(i);
116            continue;
117        } else if (LLVM_UNLIKELY(isa<Ones>(var->getOperand(i)))) {
118            if (isa<Or>(var)) {
119                return PabloBlock::createOnes();
120            } else if (isa<Xor>(var)) {
121                negated = !negated;
122            }
123            var->removeOperand(i);
124            continue;
125        }
126        ++i;
127    }
128
129    PabloAST * replacement = nullptr;
130    if (LLVM_UNLIKELY(var->getNumOperands() < 2)) {
131        replacement = (var->getNumOperands() == 0) ? PabloBlock::createZeroes() : var->getOperand(0);
132    }
133    if (LLVM_UNLIKELY(negated)) {
134        block->setInsertPoint(var);
135        if (replacement) {
136            replacement = block->createNot(replacement);
137        } else {
138            var->replaceAllUsesWith(block->createNot(var));
139        }
140    }
141    return replacement;
142}
143
144/** ------------------------------------------------------------------------------------------------------------- *
145 * @brief canTriviallyFold
146 ** ------------------------------------------------------------------------------------------------------------- */
147inline static PabloAST * canTriviallyFold(Statement * stmt, PabloBlock * block) {
148    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
149        if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(i)))) {
150            switch (stmt->getClassTypeId()) {
151                case PabloAST::ClassTypeId::Advance:
152                    return block->createZeroes();
153                case PabloAST::ClassTypeId::Not:
154                    return block->createOnes();
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::Not:
171                    return block->createZeroes();
172                case PabloAST::ClassTypeId::Sel:
173                    block->setInsertPoint(stmt->getPrevNode());
174                    switch (i) {
175                        case 0: return stmt->getOperand(1);
176                        case 1: return block->createOr(stmt->getOperand(0), stmt->getOperand(2));
177                        case 2: return block->createOr(block->createNot(stmt->getOperand(0)), stmt->getOperand(1));
178                    }
179                case PabloAST::ClassTypeId::ScanThru:
180                    if (i == 1) {
181                        return block->createZeroes();
182                    }
183                    break;
184                case PabloAST::ClassTypeId::MatchStar:
185                    if (i == 0) {
186                        return block->createOnes();
187                    }
188                    break;
189                default: break;
190            }
191        }
192    }
193    return nullptr;
194}
195
196/** ------------------------------------------------------------------------------------------------------------- *
197 * @brief isSuperfluous
198 ** ------------------------------------------------------------------------------------------------------------- */
199inline bool Simplifier::isSuperfluous(const Assign * const assign) {
200    for (const PabloAST * inst : assign->users()) {
201        if (isa<Next>(inst) || isa<PabloFunction>(inst) || (isa<If>(inst) && (cast<If>(inst)->getCondition() != assign))) {
202            return false;
203        }
204    }
205    return true;
206}
207
208/** ------------------------------------------------------------------------------------------------------------- *
209 * @brief demoteDefinedVar
210 ** ------------------------------------------------------------------------------------------------------------- */
211inline bool demoteDefinedVar(const If * ifNode, const Assign * def) {
212    // If this value isn't used outside of this scope then there is no reason to allow it to escape it.
213    if (!escapes(def)) {
214        return true;
215    }
216    // Similarly if the defined variable is equivalent to the condition, an equivalent value is already available.
217    if (ifNode->getCondition() == def->getExpression()) {
218        return true;
219    }
220    // Finally, if the assignment is a constant, it's already known.
221    if (isa<Zeroes>(def->getExpression()) || isa<Ones>(def->getExpression()))  {
222        return true;
223    }
224    return false;
225}
226
227/** ------------------------------------------------------------------------------------------------------------- *
228 * @brief replaceReachableUsersOfWith
229 ** ------------------------------------------------------------------------------------------------------------- */
230inline void replaceReachableUsersOfWith(Statement * stmt, PabloAST * expr) {
231    const PabloBlock * const root = stmt->getParent();
232    SmallSet<const PabloBlock *> forbidden;
233    for (PabloAST * use : stmt->users()) {
234        if (LLVM_UNLIKELY(isa<Next>(use))) {
235            const PabloBlock * parent = cast<Next>(use)->getParent();
236            if (parent != root) {
237                forbidden.insert(parent);
238            }
239        }
240    }
241    for (PabloAST * use : stmt->users()) {
242        if (Statement * user = dyn_cast<Statement>(use)) {
243            const PabloBlock * parent = user->getParent();
244            while (parent && forbidden.count(parent) == 0) {
245                if (LLVM_UNLIKELY(parent == root)) {
246                    user->replaceUsesOfWith(stmt, expr);
247                    break;
248                }
249                parent = parent->getParent();
250            }
251        }
252    }
253}
254
255/** ------------------------------------------------------------------------------------------------------------- *
256 * @brief discardNestedIfBlock
257 *
258 * If this inner block is composed of only Boolean logic and Assign statements and there are fewer than 3
259 * statements, just add the statements in the inner block to the current block->
260 ** ------------------------------------------------------------------------------------------------------------- */
261inline bool discardNestedIfBlock(const PabloBlock * const block) {
262    unsigned computations = 0;
263    for (const Statement * stmt : *block) {
264        switch (stmt->getClassTypeId()) {
265            case PabloAST::ClassTypeId::And:
266            case PabloAST::ClassTypeId::Or:
267            case PabloAST::ClassTypeId::Xor:
268                if (++computations > 3) {
269                    return false;
270                }
271            case PabloAST::ClassTypeId::Not:
272            case PabloAST::ClassTypeId::Assign:
273                break;
274            default:
275                return false;
276        }
277    }
278    return true;
279}
280
281/** ------------------------------------------------------------------------------------------------------------- *
282 * @brief removeIdenticalEscapedValues
283 ** ------------------------------------------------------------------------------------------------------------- */
284template <class ValueList, class ValueType = typename ValueList::value_type>
285inline void removeIdenticalEscapedValues(ValueList & list) {
286    std::vector<ValueType> identicalValues;
287    for (auto i = list.begin(); i != list.end(); ++i) {
288        for (auto j = i + 1; j != list.end(); ++j) {
289            if (LLVM_UNLIKELY(equals(*i, *j))) {
290                identicalValues.push_back(*j);
291            }
292        }
293        for (ValueType identicalValue : identicalValues) {
294            identicalValue->replaceWith(*i);
295        }
296        identicalValues.clear();
297    }
298}
299
300/** ------------------------------------------------------------------------------------------------------------- *
301 * @brief eliminateRedundantCode
302 *
303 * Note: Do not recursively delete statements in this function. The ExpressionTable could use deleted statements
304 * as replacements. Let the DCE remove the unnecessary statements with the finalized Def-Use information.
305 ** ------------------------------------------------------------------------------------------------------------- */
306void Simplifier::eliminateRedundantCode(PabloBlock * const block, ExpressionTable * predecessor) {
307    ExpressionTable encountered(predecessor);
308    Statement * stmt = block->front();
309
310    while (stmt) {
311
312        if (Assign * assign = dyn_cast<Assign>(stmt)) {
313            // If we have an Assign whose users do not contain an If or Next node, we can replace its users with
314            // the Assign's expression directly.
315            if (isSuperfluous(assign)) {
316                stmt = assign->replaceWith(assign->getExpression());
317                continue;
318            }
319            // Force the uses of an Assign node that can reach the original expression to use the expression instead.
320            replaceReachableUsersOfWith(assign, assign->getExpression());
321        } else if (Next * next = dyn_cast<Next>(stmt)) {
322            replaceReachableUsersOfWith(next, next->getExpr());
323        } else if (If * ifNode = dyn_cast<If>(stmt)) {
324            // Test whether we can ever take this branch
325            if (LLVM_UNLIKELY(isa<Zeroes>(cast<If>(stmt)->getCondition()))) {
326                stmt = stmt->eraseFromParent();
327                continue;
328            }
329            // Test whether all of the defined variables are necessary
330            If::DefinedVars & defs = ifNode->getDefined();
331            for (auto def = defs.begin(); def != defs.end(); ) {
332                if (LLVM_UNLIKELY(demoteDefinedVar(ifNode, *def))) {
333                    (*def)->replaceWith((*def)->getExpression());
334                    def = ifNode->removeDefined(*def);
335                    continue;
336                }
337                ++def;
338            }
339
340            // Process the If body
341            eliminateRedundantCode(cast<If>(stmt)->getBody(), &encountered);
342
343            // If we ended up removing all of the defined variables, delete the If node.
344            if (LLVM_UNLIKELY(defs.empty())) {
345                stmt = stmt->eraseFromParent();
346                continue;
347            }
348
349            // Otherwise check if we any Assign reports the same value as another. If so, replace all uses of the
350            // second with the first. This will simplify future analysis.
351            removeIdenticalEscapedValues(ifNode->getDefined());
352
353            // Finally after we've eliminated everything we can from the If body, check whether testing the If
354            // condition will meet or exceed the cost of executing the body.
355            if (LLVM_UNLIKELY(discardNestedIfBlock(ifNode->getBody()))) {
356                Statement * nested = ifNode->getBody()->front();
357                while (nested) {
358                    Statement * next = nested->removeFromParent();
359                    if (isa<Assign>(nested)) {
360                        ifNode->removeDefined(cast<Assign>(nested));
361                    }
362                    nested->insertAfter(stmt);
363                    stmt = nested;
364                    nested = next;
365                }
366                stmt = ifNode->eraseFromParent();
367                continue;
368            }
369
370        } else if (While * whileNode = dyn_cast<While>(stmt)) {
371            // Test whether we can ever take this branch
372            const PabloAST * initial = cast<While>(stmt)->getCondition();
373            if (LLVM_LIKELY(isa<Next>(initial))) {
374                initial = cast<Next>(initial)->getInitial();
375            }
376            if (LLVM_UNLIKELY(isa<Zeroes>(initial))) {
377                stmt = stmt->eraseFromParent();
378                continue;
379            }
380            eliminateRedundantCode(whileNode->getBody(), &encountered);
381            removeIdenticalEscapedValues(whileNode->getVariants());
382            // If the condition's Next state is Zero, we can eliminate the loop after copying the internal
383            // statements into the body.
384        } else {
385            PabloAST * folded = nullptr;
386            if (isReassociative(stmt)) {
387                folded =  foldReassociativeFunction(cast<Variadic>(stmt), block);
388            } else {
389                folded = canTriviallyFold(stmt, block);
390            }
391            if (folded) {
392                // If we determine we can fold this statement,
393                Statement * const prior = stmt->getPrevNode();
394                stmt->replaceWith(folded, true);
395                stmt = prior ? 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}
Note: See TracBrowser for help on using the repository browser.