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

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

Continued work on multiplexing pass.

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 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 * inst : assign->users()) {
205        if (isa<Next>(inst) || isa<PabloFunction>(inst) || (isa<If>(inst) && (cast<If>(inst)->getCondition() != assign))) {
206            return false;
207        }
208    }
209    return true;
210}
211
212/** ------------------------------------------------------------------------------------------------------------- *
213 * @brief demoteDefinedVar
214 ** ------------------------------------------------------------------------------------------------------------- */
215inline bool demoteDefinedVar(const If * ifNode, const Assign * def) {
216    // If this value isn't used outside of this scope then there is no reason to allow it to escape it.
217    if (!escapes(def)) {
218        return true;
219    }
220    // Similarly if the defined variable is equivalent to the condition, an equivalent value is already available.
221    if (ifNode->getCondition() == def->getExpression()) {
222        return true;
223    }
224    // Finally, if the assignment is a constant, it's already known.
225    if (isa<Zeroes>(def->getExpression()) || isa<Ones>(def->getExpression()))  {
226        return true;
227    }
228    return false;
229}
230
231/** ------------------------------------------------------------------------------------------------------------- *
232 * @brief replaceReachableUsersOfWith
233 ** ------------------------------------------------------------------------------------------------------------- */
234inline void replaceReachableUsersOfWith(Statement * stmt, PabloAST * expr) {
235    const PabloBlock * const root = stmt->getParent();
236    SmallSet<const PabloBlock *> forbidden;
237    for (PabloAST * use : stmt->users()) {
238        if (LLVM_UNLIKELY(isa<Next>(use))) {
239            const PabloBlock * parent = cast<Next>(use)->getParent();
240            if (parent != root) {
241                forbidden.insert(parent);
242            }
243        }
244    }
245    for (PabloAST * use : stmt->users()) {
246        if (Statement * user = dyn_cast<Statement>(use)) {
247            const PabloBlock * parent = user->getParent();
248            while (parent && forbidden.count(parent) == 0) {
249                if (LLVM_UNLIKELY(parent == root)) {
250                    user->replaceUsesOfWith(stmt, expr);
251                    break;
252                }
253                parent = parent->getParent();
254            }
255        }
256    }
257}
258
259/** ------------------------------------------------------------------------------------------------------------- *
260 * @brief discardNestedIfBlock
261 *
262 * If this inner block is composed of only Boolean logic and Assign statements and there are fewer than 3
263 * statements, just add the statements in the inner block to the current block->
264 ** ------------------------------------------------------------------------------------------------------------- */
265inline bool discardNestedIfBlock(const PabloBlock * const block) {
266    unsigned computations = 0;
267    for (const Statement * stmt : *block) {
268        switch (stmt->getClassTypeId()) {
269            case PabloAST::ClassTypeId::And:
270            case PabloAST::ClassTypeId::Or:
271            case PabloAST::ClassTypeId::Xor:
272                if (++computations > 3) {
273                    return false;
274                }
275            case PabloAST::ClassTypeId::Not:
276            case PabloAST::ClassTypeId::Assign:
277                break;
278            default:
279                return false;
280        }
281    }
282    return true;
283}
284
285/** ------------------------------------------------------------------------------------------------------------- *
286 * @brief removeIdenticalEscapedValues
287 ** ------------------------------------------------------------------------------------------------------------- */
288template <class ValueList, class ValueType = typename ValueList::value_type>
289inline void removeIdenticalEscapedValues(ValueList & list) {
290    std::vector<ValueType> identicalValues;
291    for (auto i = list.begin(); i != list.end(); ++i) {
292        for (auto j = i + 1; j != list.end(); ++j) {
293            if (LLVM_UNLIKELY(equals(*i, *j))) {
294                identicalValues.push_back(*j);
295            }
296        }
297        for (ValueType identicalValue : identicalValues) {
298            identicalValue->replaceWith(*i);
299        }
300        identicalValues.clear();
301    }
302}
303
304/** ------------------------------------------------------------------------------------------------------------- *
305 * @brief eliminateRedundantCode
306 *
307 * Note: Do not recursively delete statements in this function. The ExpressionTable could use deleted statements
308 * as replacements. Let the DCE remove the unnecessary statements with the finalized Def-Use information.
309 ** ------------------------------------------------------------------------------------------------------------- */
310void Simplifier::eliminateRedundantCode(PabloBlock * const block, ExpressionTable * predecessor) {
311    ExpressionTable encountered(predecessor);
312    Statement * stmt = block->front();
313
314    while (stmt) {
315
316        if (Assign * assign = dyn_cast<Assign>(stmt)) {
317            // If we have an Assign whose users do not contain an If or Next node, we can replace its users with
318            // the Assign's expression directly.
319            if (isSuperfluous(assign)) {
320                stmt = assign->replaceWith(assign->getExpression());
321                continue;
322            }
323            // Force the uses of an Assign node that can reach the original expression to use the expression instead.
324            replaceReachableUsersOfWith(assign, assign->getExpression());
325        } else if (Next * next = dyn_cast<Next>(stmt)) {
326            replaceReachableUsersOfWith(next, next->getExpr());
327        } else if (If * ifNode = dyn_cast<If>(stmt)) {
328            // Test whether we can ever take this branch
329            if (LLVM_UNLIKELY(isa<Zeroes>(cast<If>(stmt)->getCondition()))) {
330                stmt = stmt->eraseFromParent();
331                continue;
332            }
333            // Test whether all of the defined variables are necessary
334            If::DefinedVars & defs = ifNode->getDefined();
335            for (auto def = defs.begin(); def != defs.end(); ) {
336                if (LLVM_UNLIKELY(demoteDefinedVar(ifNode, *def))) {
337                    (*def)->replaceWith((*def)->getExpression());
338                    def = ifNode->removeDefined(*def);
339                    continue;
340                }
341                ++def;
342            }
343
344            // Process the If body
345            eliminateRedundantCode(cast<If>(stmt)->getBody(), &encountered);
346
347            // If we ended up removing all of the defined variables, delete the If node.
348            if (LLVM_UNLIKELY(defs.empty())) {
349                stmt = stmt->eraseFromParent();
350                continue;
351            }
352
353            // Otherwise check if we any Assign reports the same value as another. If so, replace all uses of the
354            // second with the first. This will simplify future analysis.
355            removeIdenticalEscapedValues(ifNode->getDefined());
356
357            // Finally after we've eliminated everything we can from the If body, check whether testing the If
358            // condition will meet or exceed the cost of executing the body.
359            if (LLVM_UNLIKELY(discardNestedIfBlock(ifNode->getBody()))) {
360                Statement * nested = ifNode->getBody()->front();
361                while (nested) {
362                    Statement * next = nested->removeFromParent();
363                    if (isa<Assign>(nested)) {
364                        ifNode->removeDefined(cast<Assign>(nested));
365                    }
366                    nested->insertAfter(stmt);
367                    stmt = nested;
368                    nested = next;
369                }
370                stmt = ifNode->eraseFromParent();
371                continue;
372            }
373
374        } else if (While * whileNode = dyn_cast<While>(stmt)) {
375            // Test whether we can ever take this branch
376            const PabloAST * initial = cast<While>(stmt)->getCondition();
377            if (LLVM_LIKELY(isa<Next>(initial))) {
378                initial = cast<Next>(initial)->getInitial();
379            }
380            if (LLVM_UNLIKELY(isa<Zeroes>(initial))) {
381                stmt = stmt->eraseFromParent();
382                continue;
383            }
384            eliminateRedundantCode(whileNode->getBody(), &encountered);
385            removeIdenticalEscapedValues(whileNode->getVariants());
386            // If the condition's Next state is Zero, we can eliminate the loop after copying the internal
387            // statements into the body.
388        } else {
389            if (PabloAST * folded = fold(stmt, block)) {
390                // If we determine we can fold this statement,
391                Statement * const prior = stmt->getPrevNode();
392                stmt->replaceWith(folded, true);
393                stmt = LLVM_LIKELY(prior != nullptr) ? prior->getNextNode() : block->front();
394                continue;
395            }
396            // When we're creating the Pablo program, it's possible to have multiple instances of an "identical"
397            // statement. By recording which statements have already been seen, we can detect the redundant statements
398            // as any having the same type and operands. If so, we can replace its users with the prior statement.
399            // and erase this statement from the AST
400            const auto f = encountered.findOrAdd(stmt);
401            if (!f.second) {
402                stmt = stmt->replaceWith(f.first, true);
403                continue;
404            }
405
406        }
407        stmt = stmt->getNextNode();
408    }
409}
410
411/** ------------------------------------------------------------------------------------------------------------- *
412 * @brief deadCodeElimination
413 ** ------------------------------------------------------------------------------------------------------------- */
414void Simplifier::deadCodeElimination(PabloBlock * const block) {
415    Statement * stmt = block->front();
416    while (stmt) {
417        if (isa<If>(stmt)) {
418            deadCodeElimination(cast<If>(stmt)->getBody());
419        } else if (isa<While>(stmt)) {
420            deadCodeElimination(cast<While>(stmt)->getBody());
421        } else if (stmt->getNumUses() == 0){
422            stmt = stmt->eraseFromParent(true);
423            continue;
424        }
425        stmt = stmt->getNextNode();
426    }
427}
428
429/** ------------------------------------------------------------------------------------------------------------- *
430 * @brief strengthReduction
431 *
432 * Find and replace any Pablo operations with the less expensive equivalent operations whenever possible.
433 ** ------------------------------------------------------------------------------------------------------------- */
434void Simplifier::strengthReduction(PabloBlock * const block) {
435    Statement * stmt = block->front();
436    while (stmt) {
437        if (isa<If>(stmt)) {
438            strengthReduction(cast<If>(stmt)->getBody());
439        } else if (isa<While>(stmt)) {
440            strengthReduction(cast<While>(stmt)->getBody());
441        } else if (isa<Advance>(stmt)) {
442            Advance * adv = cast<Advance>(stmt);
443            if (LLVM_UNLIKELY(isa<Advance>(adv->getOperand(0)))) {
444                // Replace an Advance(Advance(x, n), m) with an Advance(x,n + m)
445                Advance * op = cast<Advance>(stmt->getOperand(0));
446                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
447                    adv->setOperand(0, op->getOperand(0));
448                    adv->setOperand(1, block->getInteger(adv->getAdvanceAmount() + op->getAdvanceAmount()));
449                    op->eraseFromParent(false);
450                }
451            }
452        } else if (LLVM_UNLIKELY(isa<ScanThru>(stmt))) {
453            ScanThru * scanThru = cast<ScanThru>(stmt);
454            if (LLVM_UNLIKELY(isa<Advance>(scanThru->getOperand(0)))) {
455                // Replace a ScanThru(Advance(x,n),y) with an ScanThru(Advance(x, n - 1), Advance(x, n - 1) | y), where Advance(x, 0) = x
456                Advance * op = cast<Advance>(stmt->getOperand(0));
457                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
458                    block->setInsertPoint(scanThru->getPrevNode());
459                    PabloAST * expr = block->createAdvance(op->getOperand(0), op->getAdvanceAmount() - 1);
460                    scanThru->setOperand(0, expr);
461                    scanThru->setOperand(1, block->createOr(scanThru->getOperand(1), expr));
462                    op->eraseFromParent(false);
463                }
464            }
465        }
466        stmt = stmt->getNextNode();
467    }
468    block->setInsertPoint(block->back());
469}
470
471}
Note: See TracBrowser for help on using the repository browser.