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

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

Merged PabloFunction? and PabloKernel? classes. Updated projects where necessary.

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