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

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

Bug fix check in for DumpTrace?, compilation of DoBlock? / DoFinalBlock? functions. Pablo CodeMotionPass? optimized and enabled by default.

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