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

Last change on this file since 5202 was 5202, checked in by nmedfort, 2 years ago

Initial work on adding types to PabloAST and mutable Var objects.

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