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

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

Work on multiplexing and distribution passes + a few AST modification bug fixes.

File size: 29.6 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
9#include <pablo/printer_pablos.h>
10#include <iostream>
11
12namespace pablo {
13
14template <typename Type>
15using SmallSet = boost::container::flat_set<Type>;
16
17using TypeId = PabloAST::ClassTypeId;
18
19/** ------------------------------------------------------------------------------------------------------------- *
20 * @brief fold
21 *
22 * Note: if folding alters this variadic without making any other modification to the AST, it will return null as
23 * if no change was made.
24 ** ------------------------------------------------------------------------------------------------------------- */
25PabloAST * Simplifier::fold(Variadic * var, PabloBlock * const block) {
26
27    assert (var);
28
29    bool negated = false;
30    if (LLVM_UNLIKELY(isa<Xor>(var))) {
31        for (unsigned i = 0; i != var->getNumOperands(); ++i) {
32            if (isa<Not>(var->getOperand(i))) {
33                // (A ⊕ ¬B) = (A ⊕ (B ⊕ 1)) = ¬(A ⊕ B)
34                var->setOperand(i, cast<Not>(var->getOperand(i))->getOperand(0));
35                negated = !negated;
36            }
37        }
38    }
39
40    // Ensure all operands of a reassociatiable function are consistently ordered.
41    std::sort(var->begin(), var->end());
42
43    // Apply the idempotence law to any And and Or statement and the identity law to any Xor
44    for (int i = var->getNumOperands() - 1; i > 0; --i) {
45        if (LLVM_UNLIKELY(equals(var->getOperand(i), var->getOperand(i - 1)))) {
46            var->removeOperand(i);
47            if (LLVM_UNLIKELY(isa<Xor>(var))) {
48                var->removeOperand(--i);
49            }
50        }
51    }
52
53    // Apply the annihilator and identity laws
54    for (unsigned i = 0; i != var->getNumOperands(); ) {
55        if (LLVM_UNLIKELY(isa<Zeroes>(var->getOperand(i)))) {
56            if (LLVM_UNLIKELY(isa<And>(var))) {
57                return PabloBlock::createZeroes();
58            }
59            var->removeOperand(i);
60            continue;
61        } else if (LLVM_UNLIKELY(isa<Ones>(var->getOperand(i)))) {
62            if (LLVM_UNLIKELY(isa<Or>(var))) {
63                return PabloBlock::createOnes();
64            } else if (LLVM_UNLIKELY(isa<Xor>(var))) {
65                negated = !negated;
66            }
67            var->removeOperand(i);
68            continue;
69        }
70        ++i;
71    }
72
73    PabloAST * replacement = nullptr;
74
75    if (LLVM_LIKELY(isa<And>(var) || isa<Or>(var))) {
76        // Apply an implicit distribution + identity law whenever possible
77        //    (P ∧ Q) √ (P ∧ ¬Q) = P √ (Q ∧ ¬Q) ⇔ P
78        const TypeId typeId = isa<And>(var) ? TypeId::Or : TypeId::And;
79        for (unsigned i = 1; i < var->getNumOperands(); ++i) {
80            if (var->getOperand(i)->getClassTypeId() == typeId) {
81                Variadic * const Vi = cast<Variadic>(var->getOperand(i));
82                if (LLVM_UNLIKELY(!std::is_sorted(Vi->begin(), Vi->end()))) {
83                    std::sort(Vi->begin(), Vi->end());
84                }
85                for (unsigned j = 0; j < i; ++j) {
86                    assert (var->getOperand(i) == Vi);
87                    if (var->getOperand(j)->getClassTypeId() == typeId) {
88                        Variadic * const Vj = cast<Variadic>(var->getOperand(j));
89                        if (LLVM_UNLIKELY(!std::is_sorted(Vj->begin(), Vj->end()))) {
90                            std::sort(Vj->begin(), Vj->end());
91                        }
92                        if (Vi->getNumOperands() == Vj->getNumOperands()) {
93                            // If vi and vj differ by precisely one operand, say di and dj, and di ⇔ ¬dj, we can apply this rule.
94                            unsigned vi = 0, vj = 0;
95                            const unsigned operands = Vi->getNumOperands();
96                            unsigned di = operands - 1, dj = operands - 1;
97                            bool differsByOne = true;
98                            while (vi < operands && vj < operands) {
99                                if (Vi->getOperand(vi) < Vj->getOperand(vj)) {
100                                    if (LLVM_UNLIKELY(di != (operands - 1))) { // <- we want the branch predictor to fail only once
101                                        differsByOne = false;
102                                        break;
103                                    }
104                                    di = vi++;
105                                } else if (Vj->getOperand(vj) < Vi->getOperand(vi)) {
106                                    if (LLVM_UNLIKELY(dj != (operands - 1))) {
107                                        differsByOne = false;
108                                        break;
109                                    }
110                                    dj = vj++;
111                                } else {
112                                    ++vi;
113                                    ++vj;
114                                }
115                            }
116                            if (LLVM_UNLIKELY(differsByOne)) {
117                                assert (di < operands && dj < operands);
118                                assert ("Found an equivalent set of operations that was not deduced earlier!" && (!equals(Vi, Vj)));
119                                // test if di ⇔ ¬dj
120                                bool apply = false;
121                                if (isa<Not>(Vi->getOperand(di))) {
122                                    apply = cast<Not>(Vi->getOperand(di))->getOperand(0) == Vj->getOperand(dj);
123                                } else if (isa<Not>(Vj->getOperand(dj))) {
124                                    apply = cast<Not>(Vj->getOperand(dj))->getOperand(0) == Vi->getOperand(di);
125                                }
126                                if (LLVM_UNLIKELY(apply)) {
127                                    // Although we can apply this transformation, we have a potential problem. If P is not a "literal", we
128                                    // cannot optimize var without creating a new And/Or statement. However, the redundancy elimination
129                                    // pass will miss this new statement unless we mark "var" as its own replacement. We'll end up checking
130                                    // "var" again but termination is still guaranteed once none of the new statements can be replaced by
131                                    // prior statements in the AST.
132                                    PabloAST * expr = nullptr;
133                                    if (operands == 2) {
134                                        expr = Vi->getOperand(1 ^ di);
135                                        if (LLVM_LIKELY(var->getNumOperands() == 2)) {
136                                            return expr;
137                                        }
138                                    } else { // if (operands > 2) {
139                                        assert (operands > 2);
140                                        block->setInsertPoint(var->getPrevNode());
141                                        if (typeId == TypeId::And) {
142                                            expr = block->createAnd(operands - 1);
143                                        } else { // if (typeId == TypeId::Or) {
144                                            expr = block->createOr(operands - 1);
145                                        }
146                                        for (unsigned k = 0; k != di; ++k) {
147                                            cast<Variadic>(expr)->addOperand(Vi->getOperand(k));
148                                        }
149                                        for (unsigned k = di + 1; k < operands; ++k) {
150                                            cast<Variadic>(expr)->addOperand(Vi->getOperand(k));
151                                        }
152                                        replacement = var;
153                                    }
154                                    var->removeOperand(i);
155                                    var->removeOperand(j);
156                                    bool unique = true;
157                                    for (unsigned k = 0; k != var->getNumOperands(); ++k) {
158                                        if (LLVM_UNLIKELY(equals(var->getOperand(k), expr))) {
159                                            unique = false;
160                                            break;
161                                        }
162                                    }
163                                    if (LLVM_LIKELY(unique)) {
164                                        var->addOperand(expr);
165                                    }
166                                    i -= 2;
167                                    break; // out of for j = 0 to i - 1
168                                }
169                            }
170                        }
171                    }
172                }
173            }
174        }
175
176        // Apply the absorption law whenever possible
177        //   P √ (P ∧ Q) ⇔ P ∧ (P √ Q) ⇔ P
178        for (unsigned i = 1; i < var->getNumOperands(); ++i) {
179            PabloAST * const op = var->getOperand(i);
180            if (op->getClassTypeId() == typeId) {
181                Variadic * const vi = cast<Variadic>(op);
182                assert (std::is_sorted(vi->begin(), vi->end()));
183                for (unsigned j = 0; j < i; ++j) {
184                    assert (var->getOperand(i) == vi);
185                    if (var->getOperand(j)->getClassTypeId() == typeId) {
186                        Variadic * const vj = cast<Variadic>(var->getOperand(j));
187                        assert (std::is_sorted(vj->begin(), vj->end()));
188                        if (vi->getNumOperands() < vj->getNumOperands()) {
189                            if (LLVM_UNLIKELY(std::includes(vi->begin(), vi->end(), vj->begin(), vj->end()))) {
190                                var->removeOperand(i--);
191                                break;
192                            }
193                        } else { // if (vi->getNumOperands() >= vj->getNumOperands()) {
194                            if (LLVM_UNLIKELY(std::includes(vj->begin(), vj->end(), vi->begin(), vi->end()))) {
195                                var->removeOperand(j--);
196                                --i;
197                            }
198                        }
199                    }
200                }
201            } else { // treat the operand as a literal
202                for (unsigned j = 0; j < var->getNumOperands(); ) {
203                    if (var->getOperand(j)->getClassTypeId() == typeId) {
204                        Variadic * const vj = cast<Variadic>(var->getOperand(j));
205                        assert (std::is_sorted(vj->begin(), vj->end()));
206                        if (LLVM_UNLIKELY(std::binary_search(vj->begin(), vj->end(), op))) {
207                            var->removeOperand(j);
208                            continue;
209                        }
210                    }
211                    ++j;
212                }
213            }
214        }
215
216        // Apply the complementation law whenever possible.
217        for (unsigned i = 0; i < var->getNumOperands(); ++i) {
218            if (isa<Not>(var->getOperand(i))) {
219                const PabloAST * const negated = cast<Not>(var->getOperand(i))->getOperand(0);
220                for (unsigned j = 0; j != var->getNumOperands(); ++j) {
221                    if (LLVM_UNLIKELY(var->getOperand(j) == negated)) {
222                        if (isa<And>(var)) { // (A ∧ ¬A) ∧ B ⇔ 0 for any B
223                            return PabloBlock::createZeroes();
224                        } else { // if (isa<Or>(var)) { // (A √ ¬A) √ B ⇔ 1 for any B
225                            return PabloBlock::createOnes();
226                        }
227                    }
228                }
229            }
230        }
231
232    }
233
234    if (LLVM_UNLIKELY(var->getNumOperands() < 2)) {
235        if (LLVM_UNLIKELY(var->getNumOperands() == 0)) {
236            return PabloBlock::createZeroes();
237        }
238        replacement = var->getOperand(0);
239    }
240    if (LLVM_UNLIKELY(negated)) {
241        assert (isa<Xor>(var));
242        block->setInsertPoint(var);
243        replacement = block->createNot(replacement ? replacement : var);
244    }
245    return replacement;
246}
247
248/** ------------------------------------------------------------------------------------------------------------- *
249 * @brief fold
250 ** ------------------------------------------------------------------------------------------------------------- */
251inline PabloAST * Simplifier::fold(Statement * stmt, PabloBlock * const block) {
252    if (isa<Variadic>(stmt)) {
253        return fold(cast<Variadic>(stmt), block);
254    } else if (isa<Not>(stmt)) {
255        PabloAST * value = stmt->getOperand(0);
256        if (LLVM_UNLIKELY(isa<Not>(value))) {
257            return cast<Not>(value)->getOperand(0); // ¬¬A ⇔ A
258        } else if (LLVM_UNLIKELY(isa<Zeroes>(value))) {
259            return PabloBlock::createOnes(); // ¬0 ⇔ 1
260        }  else if (LLVM_UNLIKELY(isa<Ones>(value))) {
261            return PabloBlock::createZeroes(); // ¬1 ⇔ 0
262        }
263    } else if (isa<Advance>(stmt)) {
264        if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(0)))) {
265            return PabloBlock::createZeroes();
266        }
267    } else {
268        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
269            if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(i)))) {
270                switch (stmt->getClassTypeId()) {
271                    case PabloAST::ClassTypeId::Sel:
272                        block->setInsertPoint(stmt->getPrevNode());
273                        switch (i) {
274                            case 0: return stmt->getOperand(2);
275                            case 1: return block->createAnd(block->createNot(stmt->getOperand(0)), stmt->getOperand(2));
276                            case 2: return block->createAnd(stmt->getOperand(0), stmt->getOperand(1));
277                        }
278                    case PabloAST::ClassTypeId::ScanThru:
279                    case PabloAST::ClassTypeId::MatchStar:
280                        return stmt->getOperand(0);
281                    default: break;
282                }
283            } else if (LLVM_UNLIKELY(isa<Ones>(stmt->getOperand(i)))) {
284                switch (stmt->getClassTypeId()) {
285                    case PabloAST::ClassTypeId::Sel:
286                        block->setInsertPoint(stmt->getPrevNode());
287                        switch (i) {
288                            case 0: return stmt->getOperand(1);
289                            case 1: return block->createOr(stmt->getOperand(0), stmt->getOperand(2));
290                            case 2: return block->createOr(block->createNot(stmt->getOperand(0)), stmt->getOperand(1));
291                        }
292                    case PabloAST::ClassTypeId::ScanThru:
293                        if (LLVM_UNLIKELY(i == 1)) {
294                            return PabloBlock::createZeroes();
295                        }
296                        break;
297                    case PabloAST::ClassTypeId::MatchStar:
298                        if (LLVM_UNLIKELY(i == 0)) {
299                            return PabloBlock::createOnes();
300                        }
301                        break;
302                    default: break;
303                }
304            }
305        }       
306    }
307    return nullptr;
308}
309
310/** ------------------------------------------------------------------------------------------------------------- *
311 * @brief isSuperfluous
312 ** ------------------------------------------------------------------------------------------------------------- */
313inline bool Simplifier::isSuperfluous(const Assign * const assign) {
314    if (LLVM_LIKELY(isa<Statement>(assign->getExpression()))) {
315        for (const PabloAST * user : assign->users()) {
316            if (LLVM_UNLIKELY(isa<PabloFunction>(user) || isa<Next>(user))) {
317                return false;
318            } else if (isa<If>(user)) {
319                if (LLVM_UNLIKELY(cast<If>(user)->getCondition() == assign)) {
320                    continue;
321                } else if (isa<Assign>(assign->getExpression())) {
322                    continue;
323                }
324                return false;
325            }
326        }
327    }
328    return true;
329}
330
331/** ------------------------------------------------------------------------------------------------------------- *
332 * @brief demoteDefinedVar
333 ** ------------------------------------------------------------------------------------------------------------- */
334inline bool demoteDefinedVar(const If * ifNode, const Assign * def) {
335    // If this value isn't used outside of this scope then there is no reason to allow it to escape it.
336    if (!escapes(def)) {
337        return true;
338    }
339    // Similarly if the defined variable is equivalent to the condition, an equivalent value is already available.
340    if (ifNode->getCondition() == def->getExpression()) {
341        return true;
342    }
343    // Finally, if the assignment is a constant, it's already known.
344    if (isa<Zeroes>(def->getExpression()) || isa<Ones>(def->getExpression()))  {
345        return true;
346    }
347    return false;
348}
349
350/** ------------------------------------------------------------------------------------------------------------- *
351 * @brief replaceReachableUsersOfWith
352 ** ------------------------------------------------------------------------------------------------------------- */
353inline void replaceReachableUsersOfWith(Statement * stmt, PabloAST * expr) {
354    const PabloBlock * const root = stmt->getParent();
355    SmallSet<const PabloBlock *> forbidden;
356    for (PabloAST * use : stmt->users()) {
357        if (LLVM_UNLIKELY(isa<Next>(use))) {
358            const PabloBlock * parent = cast<Next>(use)->getParent();
359            if (parent != root) {
360                forbidden.insert(parent);
361            }
362        }
363    }
364    for (PabloAST * use : stmt->users()) {
365        if (Statement * user = dyn_cast<Statement>(use)) {
366            const PabloBlock * parent = user->getParent();
367            while (parent && forbidden.count(parent) == 0) {
368                if (LLVM_UNLIKELY(parent == root)) {
369                    user->replaceUsesOfWith(stmt, expr);
370                    break;
371                }
372                parent = parent->getParent();
373            }
374        }
375    }
376}
377
378/** ------------------------------------------------------------------------------------------------------------- *
379 * @brief discardNestedIfBlock
380 *
381 * If this inner block is composed of only Boolean logic and Assign statements and there are fewer than 3
382 * statements, just add the statements in the inner block to the current block->
383 ** ------------------------------------------------------------------------------------------------------------- */
384inline bool discardNestedIfBlock(const PabloBlock * const block) {
385    unsigned computations = 0;
386    for (const Statement * stmt : *block) {
387        switch (stmt->getClassTypeId()) {
388            case PabloAST::ClassTypeId::And:
389            case PabloAST::ClassTypeId::Or:
390            case PabloAST::ClassTypeId::Xor:
391                if (++computations > 3) {
392                    return false;
393                }
394            case PabloAST::ClassTypeId::Not:
395            case PabloAST::ClassTypeId::Assign:
396                break;
397            default:
398                return false;
399        }
400    }
401    return true;
402}
403
404/** ------------------------------------------------------------------------------------------------------------- *
405 * @brief removeIdenticalEscapedValues
406 ** ------------------------------------------------------------------------------------------------------------- */
407template <class ValueList, class ValueType = typename ValueList::value_type>
408inline void removeIdenticalEscapedValues(ValueList & list) {
409    std::vector<ValueType> identicalValues;
410    for (auto i = list.begin(); i != list.end(); ++i) {
411        for (auto j = i + 1; j != list.end(); ++j) {
412            if (LLVM_UNLIKELY(equals(*i, *j))) {
413                identicalValues.push_back(*j);
414            }
415        }
416        for (ValueType identicalValue : identicalValues) {
417            identicalValue->replaceWith(*i);
418        }
419        identicalValues.clear();
420    }
421}
422
423/** ------------------------------------------------------------------------------------------------------------- *
424 * @brief redundancyElimination
425 *
426 * Note: Do not recursively delete statements in this function. The ExpressionTable could use deleted statements
427 * as replacements. Let the DCE remove the unnecessary statements with the finalized Def-Use information.
428 ** ------------------------------------------------------------------------------------------------------------- */
429void Simplifier::redundancyElimination(PabloFunction & function, PabloBlock * const block, ExpressionTable * predecessor) {
430    ExpressionTable encountered(predecessor);
431    Statement * stmt = block->front();
432
433    while (stmt) {
434        if (Assign * assign = dyn_cast<Assign>(stmt)) {
435            // If we have an Assign whose users do not contain an If or Next node, we can replace its users with
436            // the Assign's expression directly.
437            if (isSuperfluous(assign)) {
438                stmt = assign->replaceWith(assign->getExpression());
439                continue;
440            }
441            // Force the uses of an Assign node that can reach the original expression to use the expression instead.
442            replaceReachableUsersOfWith(assign, assign->getExpression());
443        } else if (Next * next = dyn_cast<Next>(stmt)) {
444            replaceReachableUsersOfWith(next, next->getExpr());
445        } else if (If * ifNode = dyn_cast<If>(stmt)) {
446            // Test whether we can ever take this branch
447            if (LLVM_UNLIKELY(isa<Zeroes>(cast<If>(stmt)->getCondition()))) {
448                stmt = stmt->eraseFromParent();
449                continue;
450            }
451            // Test whether all of the defined variables are necessary
452            If::DefinedVars & defs = ifNode->getDefined();
453            for (auto def = defs.begin(); def != defs.end(); ) {
454                if (LLVM_UNLIKELY(demoteDefinedVar(ifNode, *def))) {
455                    (*def)->replaceWith((*def)->getExpression());
456                    def = ifNode->removeDefined(*def);
457                    continue;
458                }
459                ++def;
460            }
461
462            // Process the If body
463            redundancyElimination(function, cast<If>(stmt)->getBody(), &encountered);
464
465            // If we ended up removing all of the defined variables, delete the If node.
466            if (LLVM_UNLIKELY(defs.empty())) {
467                stmt = stmt->eraseFromParent();
468                continue;
469            }
470
471            // Otherwise check if we any Assign reports the same value as another. If so, replace all uses of the
472            // second with the first. This will simplify future analysis.
473            removeIdenticalEscapedValues(ifNode->getDefined());
474
475            // Finally after we've eliminated everything we can from the If body, check whether testing the If
476            // condition will meet or exceed the cost of executing the body.
477            if (LLVM_UNLIKELY(discardNestedIfBlock(ifNode->getBody()))) {
478                Statement * nested = ifNode->getBody()->front();
479                while (nested) {
480                    Statement * next = nested->removeFromParent();
481                    if (isa<Assign>(nested)) {
482                        ifNode->removeDefined(cast<Assign>(nested));
483                    }
484                    nested->insertAfter(stmt);
485                    stmt = nested;
486                    nested = next;
487                }
488                stmt = ifNode->eraseFromParent();
489                continue;
490            }
491
492        } else if (While * whileNode = dyn_cast<While>(stmt)) {
493            // Test whether we can ever take this branch
494            const PabloAST * initial = cast<While>(stmt)->getCondition();
495            if (LLVM_LIKELY(isa<Next>(initial))) {
496                initial = cast<Next>(initial)->getInitial();
497            }
498            if (LLVM_UNLIKELY(isa<Zeroes>(initial))) {
499                stmt = stmt->eraseFromParent();
500                continue;
501            }
502            redundancyElimination(function, whileNode->getBody(), &encountered);
503            removeIdenticalEscapedValues(whileNode->getVariants());
504            // If the condition's Next state is Zero, we can eliminate the loop after copying the internal
505            // statements into the body.
506        } else {
507            Statement * const prior = stmt->getPrevNode();
508            PabloAST * const folded = fold(stmt, block);
509            if (folded) {
510                // If we determine we can fold this statement, go back to the original prior node of this statement.
511                // New statements may have been inserted after it.
512                stmt->replaceWith(folded, true);
513                stmt = LLVM_LIKELY(prior != nullptr) ? prior->getNextNode() : block->front();
514                continue;
515            }
516            // When we're creating the Pablo program, it's possible to have multiple instances of an "identical"
517            // statement. By recording which statements have already been seen, we can detect the redundant statements
518            // as any having the same type and operands. If so, we can replace its users with the prior statement.
519            // and erase this statement from the AST
520            const auto f = encountered.findOrAdd(stmt);
521            if (!f.second) {
522                stmt = stmt->replaceWith(f.first, true);
523                continue;
524            }
525
526        }
527        stmt = stmt->getNextNode();
528    }
529}
530
531/** ------------------------------------------------------------------------------------------------------------- *
532 * @brief unused
533 ** ------------------------------------------------------------------------------------------------------------- */
534inline static bool unused(const Statement * const stmt) {
535    if (LLVM_UNLIKELY(stmt->getNumUses() == 0)) {
536        // TODO: prototypes ought to state whether they have side effects.
537        if (LLVM_UNLIKELY(isa<Call>(stmt) && cast<Call>(stmt)->getPrototype()->getNumOfResults() == 0)) {
538            return false;
539        }
540        return true;
541    }
542    return false;
543}
544
545/** ------------------------------------------------------------------------------------------------------------- *
546 * @brief deadCodeElimination
547 ** ------------------------------------------------------------------------------------------------------------- */
548void Simplifier::dce(PabloBlock * const block) {
549    Statement * stmt = block->front();
550    while (stmt) {
551        if (LLVM_UNLIKELY(isa<If>(stmt))) {
552            dce(cast<If>(stmt)->getBody());
553        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
554            dce(cast<While>(stmt)->getBody());
555        } else if (LLVM_UNLIKELY(unused(stmt))){
556            stmt = stmt->eraseFromParent(true);
557            continue;
558        }
559        stmt = stmt->getNextNode();
560    }
561}
562
563/** ------------------------------------------------------------------------------------------------------------- *
564 * @brief strengthReduction
565 *
566 * Find and replace any Pablo operations with a less expensive equivalent operation whenever possible.
567 ** ------------------------------------------------------------------------------------------------------------- */
568void Simplifier::strengthReduction(PabloBlock * const block) {
569    Statement * stmt = block->front();
570    while (stmt) {
571        if (isa<If>(stmt)) {
572            strengthReduction(cast<If>(stmt)->getBody());
573        } else if (isa<While>(stmt)) {
574            strengthReduction(cast<While>(stmt)->getBody());
575        } else if (isa<Advance>(stmt)) {
576            Advance * adv = cast<Advance>(stmt);
577            if (LLVM_UNLIKELY(isa<Advance>(adv->getOperand(0)))) {
578                // Replace an Advance(Advance(x, n), m) with an Advance(x,n + m)
579                // Test whether this will generate a long advance and abort?
580                Advance * op = cast<Advance>(stmt->getOperand(0));
581                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
582                    adv->setOperand(0, op->getOperand(0));
583                    adv->setOperand(1, block->getInteger(adv->getAmount() + op->getAmount()));
584                    op->eraseFromParent(false);
585                }
586            }
587        } else if (LLVM_UNLIKELY(isa<ScanThru>(stmt))) {
588            ScanThru * scanThru = cast<ScanThru>(stmt);
589            if (LLVM_UNLIKELY(isa<Advance>(scanThru->getOperand(0)))) {
590                // Replace a ScanThru(Advance(x,n),y) with an ScanThru(Advance(x, n - 1), Advance(x, n - 1) | y), where Advance(x, 0) = x
591                Advance * op = cast<Advance>(stmt->getOperand(0));
592                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
593                    block->setInsertPoint(scanThru->getPrevNode());
594                    PabloAST * expr = block->createAdvance(op->getOperand(0), op->getAmount() - 1);
595                    scanThru->setOperand(0, expr);
596                    scanThru->setOperand(1, block->createOr(scanThru->getOperand(1), expr));
597                    op->eraseFromParent(false);
598                }
599            } else if (isa<And>(scanThru->getOperand(0))) {
600                // Suppose B is an arbitrary bitstream and A = Advance(B, 1). ScanThru(B ∧ ¬A, B) will leave a marker on the position
601                // following the end of any run of 1-bits in B. But this is equivalent to computing A ∧ ¬B since A will have exactly
602                // one 1-bit past the end of any run of 1-bits in B.
603
604
605
606
607
608            }
609
610
611
612
613        }
614        stmt = stmt->getNextNode();
615    }
616}
617
618/** ------------------------------------------------------------------------------------------------------------- *
619 * @brief optimize
620 ** ------------------------------------------------------------------------------------------------------------- */
621bool Simplifier::optimize(PabloFunction & function) {
622    redundancyElimination(function, function.getEntryBlock());
623    strengthReduction(function.getEntryBlock());
624    dce(function.getEntryBlock());
625    #ifndef NDEBUG
626    PabloVerifier::verify(function, "post-simplification");
627    #endif
628    return true;
629}
630
631}
Note: See TracBrowser for help on using the repository browser.