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

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

Bug fixes

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