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

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

Initial attempt to improve debugging capabilities with compilation stack traces on error.

File size: 18.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/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 ** ------------------------------------------------------------------------------------------------------------- */
32PabloAST * Simplifier::triviallyFold(Statement * stmt, PabloBlock * const block) {
33    if (isa<Not>(stmt)) {
34        PabloAST * value = stmt->getOperand(0);
35        if (LLVM_UNLIKELY(isa<Not>(value))) {
36            return cast<Not>(value)->getOperand(0); // ¬¬A ⇔ A
37        } else if (LLVM_UNLIKELY(isa<Zeroes>(value))) {
38            return block->createOnes(stmt->getType()); // ¬0 ⇔ 1
39        }  else if (LLVM_UNLIKELY(isa<Ones>(value))) {
40            return block->createZeroes(stmt->getType()); // ¬1 ⇔ 0
41        }
42    } else if (isa<Advance>(stmt)) {
43        if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(0)))) {
44            return block->createZeroes(stmt->getType());
45        }
46    } else if (isa<Add>(stmt) || isa<Subtract>(stmt)) {
47       if (LLVM_UNLIKELY(isa<Integer>(stmt->getOperand(0)) && isa<Integer>(stmt->getOperand(1)))) {
48           const Integer * const int0 = cast<Integer>(stmt->getOperand(0));
49           const Integer * const int1 = cast<Integer>(stmt->getOperand(1));
50           Integer::IntTy result = 0;
51           if (isa<Add>(stmt)) {
52               result = int0->value() + int1->value();
53           } else {
54               result = int0->value() - int1->value();
55           }
56           return block->getInteger(result);
57       }
58    } else {
59        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
60            if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(i)))) {
61                switch (stmt->getClassTypeId()) {
62                    case TypeId::Sel:
63                        block->setInsertPoint(stmt->getPrevNode());
64                        switch (i) {
65                            case 0: return stmt->getOperand(2);
66                            case 1: return block->createAnd(block->createNot(stmt->getOperand(0)), stmt->getOperand(2));
67                            case 2: return block->createAnd(stmt->getOperand(0), stmt->getOperand(1));
68                        }
69                    case TypeId::ScanThru:
70                    case TypeId::MatchStar:
71                        return stmt->getOperand(0);
72                    default: break;
73                }
74            } else if (LLVM_UNLIKELY(isa<Ones>(stmt->getOperand(i)))) {
75                switch (stmt->getClassTypeId()) {
76                    case TypeId::Sel:
77                        block->setInsertPoint(stmt->getPrevNode());
78                        switch (i) {
79                            case 0: return stmt->getOperand(1);
80                            case 1: return block->createOr(stmt->getOperand(0), stmt->getOperand(2));
81                            case 2: return block->createOr(block->createNot(stmt->getOperand(0)), stmt->getOperand(1));
82                        }
83                    case TypeId::ScanThru:
84                        if (LLVM_UNLIKELY(i == 1)) {
85                            return block->createZeroes(stmt->getType());
86                        }
87                        break;
88                    case TypeId::MatchStar:
89                        if (LLVM_UNLIKELY(i == 0)) {
90                            return block->createOnes(stmt->getType());
91                        }
92                        break;
93                    default: break;
94                }
95            }
96        }       
97    }
98    return nullptr;
99}
100
101/** ------------------------------------------------------------------------------------------------------------- *
102 * @brief discardNestedIfBlock
103 *
104 * If this inner block is composed of only Boolean logic and Assign statements and there are fewer than 3
105 * statements, just add the statements in the inner block to the current block
106 ** ------------------------------------------------------------------------------------------------------------- */
107inline bool discardNestedIfBlock(const PabloBlock * const block) {
108    unsigned computations = 0;
109    for (const Statement * stmt : *block) {
110        switch (stmt->getClassTypeId()) {
111            case TypeId::And:
112            case TypeId::Or:
113            case TypeId::Xor:
114                if (++computations > 3) {
115                    return false;
116                }
117            case TypeId::Not:
118            case TypeId::Assign:
119                break;
120            default:
121                return false;
122        }
123    }
124    return true;
125}
126
127/** ------------------------------------------------------------------------------------------------------------- *
128 * @brief VariableTable
129 ** ------------------------------------------------------------------------------------------------------------- */
130struct Simplifier::VariableTable {
131
132    VariableTable(VariableTable * predecessor = nullptr)
133    : mPredecessor(predecessor) {
134
135    }
136
137    PabloAST * get(PabloAST * const var) const {
138        const auto f = mMap.find(var);
139        if (f == mMap.end()) {
140            return (mPredecessor) ? mPredecessor->get(var) : nullptr;
141        }
142        return f->second;
143    }
144
145    void put(PabloAST * const var, PabloAST * value) {
146        const auto f = mMap.find(var);
147        if (LLVM_LIKELY(f == mMap.end())) {
148            mMap.emplace(var, value);
149        } else {
150            f->second = value;
151        }
152        assert (get(var) == value);
153    }
154
155private:
156    VariableTable * const mPredecessor;
157    flat_map<PabloAST *, PabloAST *> mMap;
158};
159
160/** ------------------------------------------------------------------------------------------------------------- *
161 * @brief redundancyElimination
162 *
163 * Note: Do not recursively delete statements in this function. The ExpressionTable could use deleted statements
164 * as replacements. Let the DCE remove the unnecessary statements with the finalized Def-Use information.
165 ** ------------------------------------------------------------------------------------------------------------- */
166void Simplifier::redundancyElimination(PabloBlock * const block, ExpressionTable * const et, VariableTable * const vt) {
167    VariableTable variables(vt);
168
169    // When processing a While body, we cannot use its initial value from the outer
170    // body since the Var will likely be assigned a different value in the current
171    // body that should be used on the subsequent iteration of the loop.
172    if (While * br = dyn_cast_or_null<While>(block->getBranch())) {
173        for (Var * var : br->getEscaped()) {
174            variables.put(var, var);
175        }
176    }
177
178    ExpressionTable expressions(et);
179
180    Statement * stmt = block->front();
181    while (stmt) {
182
183        if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
184            Assign * const assign = cast<Assign>(stmt);
185            PabloAST * const var = assign->getVariable();
186            PabloAST * value = assign->getValue();
187            while (LLVM_UNLIKELY(isa<Var>(value))) {
188                PabloAST * next = variables.get(cast<Var>(value));
189                if (LLVM_LIKELY(next == nullptr || next == value)) {
190                    break;
191                }
192                value = next;
193                assign->setValue(value);
194            }
195            if (LLVM_UNLIKELY(variables.get(var) == value)) {
196                stmt = stmt->eraseFromParent();
197                continue;
198            }
199            variables.put(var, value);
200        } else if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
201
202            Branch * const br = cast<Branch>(stmt);
203
204            // Test whether we can ever take this branch
205            PabloAST * cond = br->getCondition();
206            if (isa<Var>(cond)) {
207                PabloAST * const value = variables.get(cast<Var>(cond));
208                if (value) {
209                    cond = value;
210                    // TODO: verify this works for a nested If node within a While body.
211                    if (isa<If>(br)) {
212                        br->setCondition(cond);
213                    }
214                }
215            }
216
217            if (LLVM_UNLIKELY(isa<Zeroes>(cond))) {
218                stmt = stmt->eraseFromParent();
219                continue;
220            }
221
222            // Process the Branch body
223            redundancyElimination(br->getBody(), &expressions, &variables);
224
225            // Check whether this If branch has enough operations nested within it to
226            // be worth the cost of the branch.
227            if (LLVM_UNLIKELY(isa<If>(br) && discardNestedIfBlock(br->getBody()))) {
228                Statement * nested = br->getBody()->front();
229                while (nested) {
230                    Statement * next = nested->removeFromParent();
231                    nested->insertAfter(stmt);
232                    stmt = nested;
233                    nested = next;
234                }
235                stmt = br->eraseFromParent();
236                continue;
237            }
238
239        } else {
240
241            // demote any uses of a Var whose value is in scope
242            for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
243                PabloAST * op = stmt->getOperand(i);
244                if (LLVM_UNLIKELY(isa<Var>(op))) {
245                    PabloAST * const value = variables.get(cast<Var>(op));
246                    if (value && value != op) {
247                        stmt->setOperand(i, value);
248                    }
249                }
250            }
251
252            PabloAST * const folded = triviallyFold(stmt, block);
253            if (folded) {
254                stmt = stmt->replaceWith(folded);
255                continue;
256            }
257
258            // By recording which statements have already been seen, we can detect the redundant statements
259            // as any having the same type and operands. If so, we can replace its users with the prior statement.
260            // and erase this statement from the AST
261            const auto f = expressions.findOrAdd(stmt);
262            if (!f.second) {
263                stmt = stmt->replaceWith(f.first);
264                continue;
265            }
266
267        }
268
269        stmt = stmt->getNextNode();
270    }
271
272    // If this block has a branch statement leading into it, we can verify whether an escaped value
273    // was updated within this block and update the preceeding block's variable state appropriately.
274
275    if (Branch * const br = block->getBranch()) { assert (vt);
276
277        // When removing identical escaped values, we have to consider that the identical Vars could
278        // be assigned new differing values later in the outer body. Thus instead of replacing them
279        // directly, we map future uses of the duplicate Var to the initial one. The DCE pass will
280        // later mark any Assign statement as dead if the Var is never read.
281
282        /// TODO: this doesn't properly optimize the loop control variable(s) yet.
283
284        const auto escaped = br->getEscaped();
285        const auto n = escaped.size();
286        PabloAST * variable[n];
287        PabloAST * incoming[n];
288        PabloAST * outgoing[n];
289
290        for (unsigned i = 0; i < escaped.size(); ++i) {
291            PabloAST * var = escaped[i];
292            incoming[i] = vt->get(var);
293            outgoing[i] = variables.get(var);
294            if (LLVM_UNLIKELY(incoming[i] == outgoing[i])) {
295                var = incoming[i];
296            } else {
297                for (size_t j = 0; j != i; ++j) {
298                    if ((outgoing[j] == outgoing[i]) && (incoming[j] == incoming[i])) {
299                        var = variable[j];
300                        break;
301                    }
302                }
303            }
304            variable[i] = var;
305            vt->put(escaped[i], var);
306        }
307    }
308}
309
310/** ------------------------------------------------------------------------------------------------------------- *
311 * @brief deadCodeElimination
312 ** ------------------------------------------------------------------------------------------------------------- */
313void Simplifier::deadCodeElimination(PabloBlock * const block) {
314
315    flat_map<PabloAST *, Assign *> unread;
316
317    Statement * stmt = block->front();
318    while (stmt) {
319        if (unread.size() != 0) {
320            for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
321                PabloAST * const op = stmt->getOperand(i);
322                if (LLVM_UNLIKELY(isa<Var>(op))) {
323                    unread.erase(op);
324                }
325            }
326        }
327        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
328            Branch * const br = cast<Branch>(stmt);
329            deadCodeElimination(br->getBody());
330            if (LLVM_UNLIKELY(br->getEscaped().empty())) {
331                stmt = stmt->eraseFromParent(true);
332                continue;
333            }
334        } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
335            // An Assign statement is locally dead whenever its variable is not read
336            // before being reassigned a value.
337            PabloAST * var = cast<Assign>(stmt)->getVariable();
338            auto f = unread.find(var);
339            if (f != unread.end()) {
340                auto prior = f->second;
341                prior->eraseFromParent(true);
342                f->second = cast<Assign>(stmt);
343            } else {
344                unread.emplace(var, cast<Assign>(stmt));
345            }
346        } else if (LLVM_UNLIKELY(stmt->getNumUses() == 0)) {
347            stmt = stmt->eraseFromParent(true);
348            continue;
349        }
350        stmt = stmt->getNextNode();
351    }
352}
353
354/** ------------------------------------------------------------------------------------------------------------- *
355 * @brief deadCodeElimination
356 ** ------------------------------------------------------------------------------------------------------------- */
357void Simplifier::deadCodeElimination(PabloKernel * kernel) {
358
359    deadCodeElimination(kernel->getEntryBlock());
360
361    for (unsigned i = 0; i < kernel->getNumOfVariables(); ++i) {
362        Var * var = kernel->getVariable(i);
363        bool unused = true;
364        for (PabloAST * user : var->users()) {
365            if (isa<Assign>(user)) {
366                if (cast<Assign>(user)->getValue() == var) {
367                    unused = false;
368                    break;
369                }
370            } else {
371                unused = false;
372                break;
373            }
374        }
375        if (LLVM_UNLIKELY(unused)) {
376            for (PabloAST * user : var->users()) {
377                cast<Assign>(user)->eraseFromParent(true);
378            }
379        }
380    }
381
382}
383
384/** ------------------------------------------------------------------------------------------------------------- *
385 * @brief strengthReduction
386 *
387 * Find and replace any Pablo operations with a less expensive equivalent operation whenever possible.
388 ** ------------------------------------------------------------------------------------------------------------- */
389void Simplifier::strengthReduction(PabloBlock * const block) {
390
391    Statement * stmt = block->front();
392    while (stmt) {
393        if (isa<Branch>(stmt)) {
394            strengthReduction(cast<Branch>(stmt)->getBody());
395        } else if (isa<Advance>(stmt)) {
396            Advance * adv = cast<Advance>(stmt);
397            if (LLVM_UNLIKELY(isa<Advance>(adv->getOperand(0)))) {
398                // Replace an Advance(Advance(x, n), m) with an Advance(x,n + m)
399                // Test whether this will generate a long advance and abort?
400                Advance * op = cast<Advance>(stmt->getOperand(0));
401                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
402                    adv->setOperand(0, op->getOperand(0));
403                    adv->setOperand(1, block->getInteger(adv->getAmount() + op->getAmount()));
404                    op->eraseFromParent(false);
405                }
406            }
407        } else if (LLVM_UNLIKELY(isa<ScanThru>(stmt))) {
408            ScanThru * scanThru = cast<ScanThru>(stmt);
409            if (LLVM_UNLIKELY(isa<Advance>(scanThru->getScanFrom()))) {
410                // Replace a ScanThru(Advance(x,n),y) with an ScanThru(Advance(x, n - 1), Advance(x, n - 1) | y), where Advance(x, 0) = x
411                Advance * adv = cast<Advance>(scanThru->getScanFrom());
412                if (LLVM_UNLIKELY(adv->getNumUses() == 1)) {
413                    PabloAST * stream = adv->getExpression();
414                    block->setInsertPoint(stmt);
415                    if (LLVM_UNLIKELY(adv->getAmount() != 1)) {
416                        stream = block->createAdvance(stream, block->getInteger(adv->getAmount() - 1));
417                    }
418                    stmt = scanThru->replaceWith(block->createAdvanceThenScanThru(stream, scanThru->getScanThru()));
419                    adv->eraseFromParent(false);
420                    continue;
421                }
422            } else if (LLVM_UNLIKELY(isa<And>(scanThru->getScanFrom()))) {
423                // Suppose B is an arbitrary bitstream and A = Advance(B, 1). ScanThru(B ∧ ¬A, B) will leave a marker on the position
424                // following the end of any run of 1-bits in B. But this is equivalent to computing A ∧ ¬B since A will have exactly
425                // one 1-bit past the end of any run of 1-bits in B.
426
427
428
429
430
431            }
432        } else if (LLVM_UNLIKELY(isa<ScanTo>(stmt))) {
433            ScanTo * scanTo = cast<ScanTo>(stmt);
434            if (LLVM_UNLIKELY(isa<Advance>(scanTo->getScanFrom()))) {
435                // Replace a ScanTo(Advance(x,n),y) with an ScanTo(Advance(x, n - 1), Advance(x, n - 1) | y), where Advance(x, 0) = x
436                Advance * adv = cast<Advance>(scanTo->getScanFrom());
437                if (LLVM_UNLIKELY(adv->getNumUses() == 1)) {
438                    PabloAST * stream = adv->getExpression();
439                    block->setInsertPoint(stmt);
440                    if (LLVM_UNLIKELY(adv->getAmount() != 1)) {
441                        stream = block->createAdvance(stream, block->getInteger(adv->getAmount() - 1));
442                    }
443                    stmt = scanTo->replaceWith(block->createAdvanceThenScanTo(stream, scanTo->getScanTo()));
444                    adv->eraseFromParent(false);
445                    continue;
446                }
447            }
448        }
449        stmt = stmt->getNextNode();
450    }
451}
452
453/** ------------------------------------------------------------------------------------------------------------- *
454 * @brief optimize
455 ** ------------------------------------------------------------------------------------------------------------- */
456bool Simplifier::optimize(PabloKernel * kernel) {
457    redundancyElimination(kernel->getEntryBlock());
458    strengthReduction(kernel->getEntryBlock());
459    deadCodeElimination(kernel);
460    #ifndef NDEBUG
461    PabloVerifier::verify(kernel, "post-simplification");
462    #endif
463    return true;
464}
465
466}
Note: See TracBrowser for help on using the repository browser.