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

Last change on this file since 4878 was 4878, checked in by nmedfort, 4 years ago

More work on n-ary operations.

File size: 20.5 KB
Line 
1#include <pablo/optimizers/pablo_simplifier.hpp>
2#include <pablo/codegenstate.h>
3#include <pablo/expression_map.hpp>
4#include <pablo/function.h>
5#include <pablo/printer_pablos.h>
6#include <pablo/analysis/pabloverifier.hpp>
7#ifdef USE_BOOST
8#include <boost/container/flat_set.hpp>
9#else
10#include <unordered_set>
11#endif
12#include <iostream>
13
14namespace pablo {
15
16#ifdef USE_BOOST
17template <typename Type>
18using SmallSet = boost::container::flat_set<Type>;
19#else
20template <typename Type>
21using SmallSet = std::unordered_set<Type>;
22#endif
23
24/** ------------------------------------------------------------------------------------------------------------- *
25 * @brief optimize
26 ** ------------------------------------------------------------------------------------------------------------- */
27bool Simplifier::optimize(PabloFunction & function) {
28    eliminateRedundantCode(function.getEntryBlock());
29    deadCodeElimination(function.getEntryBlock());
30    eliminateRedundantEquations(function.getEntryBlock());
31    #ifndef NDEBUG
32    PabloVerifier::verify(function, "post-simplification");
33    #endif
34    return true;
35}
36
37/** ------------------------------------------------------------------------------------------------------------- *
38 * @brief isReassociative
39 ** ------------------------------------------------------------------------------------------------------------- */
40inline bool isReassociative(const Statement * const stmt) {
41    switch (stmt->getClassTypeId()) {
42        case PabloAST::ClassTypeId::And:
43        case PabloAST::ClassTypeId::Or:
44        case PabloAST::ClassTypeId::Xor:
45            return true;
46        default: return false;
47    }
48}
49
50/** ------------------------------------------------------------------------------------------------------------- *
51 * @brief foldReassociativeFunction
52 ** ------------------------------------------------------------------------------------------------------------- */
53PabloAST * Simplifier::foldReassociativeFunction(Variadic * const var, PabloBlock * const block) {
54
55    assert (var);
56
57    bool negated = false;
58    if (LLVM_UNLIKELY(isa<Xor>(var))) {
59        for (unsigned i = 0; i != var->getNumOperands(); ++i) {
60            if (isa<Not>(var->getOperand(i))) {
61                // (A ⊕ ¬B) = ¬(A ⊕ B)
62                var->setOperand(i, cast<Not>(var->getOperand(i))->getOperand(0));
63                negated = !negated;
64            }
65        }
66    }
67
68    // Ensure all operands of a reassociatiable function are consistently ordered.
69    std::sort(var->begin(), var->end());
70
71    // Apply the idempotence law to any And and Or statement and the identity law to any Xor
72    for (unsigned i = 1; i < var->getNumOperands(); ) {
73        if (var->getOperand(i - 1) == var->getOperand(i)) {
74            var->removeOperand(i);
75            if (LLVM_UNLIKELY(isa<Xor>(var))) {
76                var->removeOperand(i - 1);
77                if (LLVM_UNLIKELY(var->getNumOperands() == 0)) {
78                    return PabloBlock::createZeroes();
79                }
80            }
81            continue;
82        }
83        ++i;
84    }
85
86    if (LLVM_LIKELY(!isa<Xor>(var))) {
87        // Apply the complementation law whenever possible.
88        for (unsigned i = 0; i < var->getNumOperands(); ++i) {
89            if (isa<Not>(var->getOperand(i))) {
90                const PabloAST * const negatedOp = cast<Not>(var->getOperand(i))->getOperand(0);
91                for (unsigned j = 0; j != var->getNumOperands(); ++j) {
92                    if (LLVM_UNLIKELY(var->getOperand(j) == negatedOp)) {
93                        if (isa<And>(var)) { // (A ∧ ¬A) ∧ B = 0 for any B
94                            return PabloBlock::createZeroes();
95                        } else if (isa<Or>(var)) { // (A √ ¬A) √ B = 1 for any B
96                            return PabloBlock::createOnes();
97                        }
98                    }
99                }
100            }
101        }
102    }
103
104    // Apply the annihilator and identity laws
105    for (unsigned i = 0; i != var->getNumOperands(); ) {
106        if (LLVM_UNLIKELY(isa<Zeroes>(var->getOperand(i)))) {
107            if (isa<And>(var)) {
108                return PabloBlock::createZeroes();
109            }
110            var->removeOperand(i);
111            continue;
112        } else if (LLVM_UNLIKELY(isa<Ones>(var->getOperand(i)))) {
113            if (isa<Or>(var)) {
114                return PabloBlock::createOnes();
115            } else if (isa<Xor>(var)) {
116                negated = !negated;
117            }
118            var->removeOperand(i);
119            continue;
120        }
121        ++i;
122    }
123
124    PabloAST * replacement = nullptr;
125    if (LLVM_UNLIKELY(var->getNumOperands() < 2)) {
126        replacement = (var->getNumOperands() == 0) ? PabloBlock::createZeroes() : var->getOperand(0);
127    }
128    if (LLVM_UNLIKELY(negated)) {
129        block->setInsertPoint(var);
130        if (replacement) {
131            replacement = block->createNot(replacement);
132        } else {
133            var->replaceAllUsesWith(block->createNot(var));
134        }
135    }
136    return replacement;
137}
138
139/** ------------------------------------------------------------------------------------------------------------- *
140 * @brief canTriviallyFold
141 ** ------------------------------------------------------------------------------------------------------------- */
142inline static PabloAST * canTriviallyFold(Statement * stmt, PabloBlock * block) {
143    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
144        if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(i)))) {
145            switch (stmt->getClassTypeId()) {
146                case PabloAST::ClassTypeId::Advance:
147                    return block->createZeroes();
148                case PabloAST::ClassTypeId::Not:
149                    return block->createOnes();
150                case PabloAST::ClassTypeId::Sel:
151                    block->setInsertPoint(stmt->getPrevNode());
152                    switch (i) {
153                        case 0: return stmt->getOperand(2);
154                        case 1: return block->createAnd(block->createNot(stmt->getOperand(0)), stmt->getOperand(2));
155                        case 2: return block->createAnd(stmt->getOperand(0), stmt->getOperand(1));
156                    }
157                case PabloAST::ClassTypeId::ScanThru:
158                case PabloAST::ClassTypeId::MatchStar:
159                    return stmt->getOperand(0);
160                default: break;
161            }
162        } else if (LLVM_UNLIKELY(isa<Ones>(stmt->getOperand(i)))) {
163            block->setInsertPoint(stmt->getPrevNode());
164            switch (stmt->getClassTypeId()) {
165                case PabloAST::ClassTypeId::Not:
166                    return block->createZeroes();
167                case PabloAST::ClassTypeId::Sel:
168                    block->setInsertPoint(stmt->getPrevNode());
169                    switch (i) {
170                        case 0: return stmt->getOperand(1);
171                        case 1: return block->createOr(stmt->getOperand(0), stmt->getOperand(2));
172                        case 2: return block->createOr(block->createNot(stmt->getOperand(0)), stmt->getOperand(1));
173                    }
174                case PabloAST::ClassTypeId::ScanThru:
175                    if (i == 1) {
176                        return block->createZeroes();
177                    }
178                    break;
179                case PabloAST::ClassTypeId::MatchStar:
180                    if (i == 0) {
181                        return block->createOnes();
182                    }
183                    break;
184                default: break;
185            }
186        }
187    }
188    return nullptr;
189}
190
191/** ------------------------------------------------------------------------------------------------------------- *
192 * @brief isSuperfluous
193 ** ------------------------------------------------------------------------------------------------------------- */
194inline bool Simplifier::isSuperfluous(const Assign * const assign) {
195    for (const PabloAST * inst : assign->users()) {
196        if (isa<Next>(inst) || isa<PabloFunction>(inst)) {
197            return false;
198        } else if (isa<If>(inst)) {
199            const If * ifNode = cast<If>(inst);
200            if (ifNode->getCondition() == assign) {
201                bool notFound = true;
202                for (Assign * defVar : ifNode->getDefined()) {
203                    if (defVar == assign) {
204                        notFound = false;
205                        break;
206                    }
207                }
208                if (notFound) {
209                    continue;
210                }
211            }
212            return false;
213        }
214    }
215    return true;
216}
217
218/** ------------------------------------------------------------------------------------------------------------- *
219 * @brief demoteDefinedVar
220 ** ------------------------------------------------------------------------------------------------------------- */
221inline bool demoteDefinedVar(const If * ifNode, const Assign * def) {
222    // If this value isn't used outside of this scope then there is no reason to allow it to escape it.
223    if (!escapes(def)) {
224        return true;
225    }
226    // Similarly if the defined variable is equivalent to the condition, an equivalent value is already available.
227    if (ifNode->getCondition() == def->getExpression()) {
228        return true;
229    }
230    // Finally, if the assignment is a constant, it's already known.
231    if (isa<Zeroes>(def->getExpression()) || isa<Ones>(def->getExpression()))  {
232        return true;
233    }
234    return false;
235}
236
237/** ------------------------------------------------------------------------------------------------------------- *
238 * @brief replaceReachableUsersOfWith
239 ** ------------------------------------------------------------------------------------------------------------- */
240inline void replaceReachableUsersOfWith(Statement * stmt, PabloAST * expr) {
241    const PabloBlock * const root = stmt->getParent();
242    SmallSet<const PabloBlock *> forbidden;
243    for (PabloAST * use : stmt->users()) {
244        if (LLVM_UNLIKELY(isa<Next>(use))) {
245            const PabloBlock * parent = cast<Next>(use)->getParent();
246            if (parent != root) {
247                forbidden.insert(parent);
248            }
249        }
250    }
251    for (PabloAST * use : stmt->users()) {
252        if (Statement * user = dyn_cast<Statement>(use)) {
253            const PabloBlock * parent = user->getParent();
254            while (parent && forbidden.count(parent) == 0) {
255                if (LLVM_UNLIKELY(parent == root)) {
256                    user->replaceUsesOfWith(stmt, expr);
257                    break;
258                }
259                parent = parent->getParent();
260            }
261        }
262    }
263}
264
265/** ------------------------------------------------------------------------------------------------------------- *
266 * @brief discardNestedIfBlock
267 *
268 * If this inner block is composed of only Boolean logic and Assign statements and there are fewer than 3
269 * statements, just add the statements in the inner block to the current block->
270 ** ------------------------------------------------------------------------------------------------------------- */
271inline bool discardNestedIfBlock(const PabloBlock * const block) {
272    unsigned computations = 0;
273    for (const Statement * stmt : *block) {
274        switch (stmt->getClassTypeId()) {
275            case PabloAST::ClassTypeId::And:
276            case PabloAST::ClassTypeId::Or:
277            case PabloAST::ClassTypeId::Xor:
278                if (++computations > 3) {
279                    return false;
280                }
281            case PabloAST::ClassTypeId::Not:
282            case PabloAST::ClassTypeId::Assign:
283                break;
284            default:
285                return false;
286        }
287    }
288    return true;
289}
290
291/** ------------------------------------------------------------------------------------------------------------- *
292 * @brief removeIdenticalEscapedValues
293 ** ------------------------------------------------------------------------------------------------------------- */
294template <class ValueList, class ValueType = typename ValueList::value_type>
295inline void removeIdenticalEscapedValues(ValueList & list) {
296    std::vector<ValueType> identicalValues;
297    for (auto i = list.begin(); i != list.end(); ++i) {
298        for (auto j = i + 1; j != list.end(); ++j) {
299            if (LLVM_UNLIKELY(equals(*i, *j))) {
300                identicalValues.push_back(*j);
301            }
302        }
303        for (ValueType identicalValue : identicalValues) {
304            identicalValue->replaceWith(*i);
305        }
306        identicalValues.clear();
307    }
308}
309
310/** ------------------------------------------------------------------------------------------------------------- *
311 * @brief eliminateRedundantCode
312 *
313 * Note: Do not recursively delete statements in this function. The ExpressionTable could use deleted statements
314 * as replacements. Let the DCE remove the unnecessary statements with the finalized Def-Use information.
315 ** ------------------------------------------------------------------------------------------------------------- */
316void Simplifier::eliminateRedundantCode(PabloBlock * const block, ExpressionTable * predecessor) {
317    ExpressionTable encountered(predecessor);
318    Statement * stmt = block->front();
319
320    while (stmt) {
321
322        if (Assign * assign = dyn_cast<Assign>(stmt)) {
323            // If we have an Assign whose users do not contain an If or Next node, we can replace its users with
324            // the Assign's expression directly.
325            if (isSuperfluous(assign)) {
326                stmt = assign->replaceWith(assign->getExpression());
327                continue;
328            }
329            // Force the uses of an Assign node that can reach the original expression to use the expression instead.
330            replaceReachableUsersOfWith(assign, assign->getExpression());
331        } else if (Next * next = dyn_cast<Next>(stmt)) {
332            replaceReachableUsersOfWith(next, next->getExpr());
333        } else if (If * ifNode = dyn_cast<If>(stmt)) {
334            // Test whether we can ever take this branch
335            if (LLVM_UNLIKELY(isa<Zeroes>(cast<If>(stmt)->getCondition()))) {
336                stmt = stmt->eraseFromParent();
337                continue;
338            }
339            // Test whether all of the defined variables are necessary
340            If::DefinedVars & defs = ifNode->getDefined();
341            for (auto def = defs.begin(); def != defs.end(); ) {
342                if (LLVM_UNLIKELY(demoteDefinedVar(ifNode, *def))) {
343                    (*def)->replaceWith((*def)->getExpression());
344                    def = ifNode->removeDefined(*def);
345                    continue;
346                }
347                ++def;
348            }
349
350            // Process the If body
351            eliminateRedundantCode(cast<If>(stmt)->getBody(), &encountered);
352
353            // If we ended up removing all of the defined variables, delete the If node.
354            if (LLVM_UNLIKELY(defs.empty())) {
355                stmt = stmt->eraseFromParent();
356                continue;
357            }
358
359            // Otherwise check if we any Assign reports the same value as another. If so, replace all uses of the
360            // second with the first. This will simplify future analysis.
361            removeIdenticalEscapedValues(ifNode->getDefined());
362
363            // Finally after we've eliminated everything we can from the If body, check whether testing the If
364            // condition will meet or exceed the cost of executing the body.
365            if (LLVM_UNLIKELY(discardNestedIfBlock(ifNode->getBody()))) {
366                Statement * nested = ifNode->getBody()->front();
367                while (nested) {
368                    Statement * next = nested->removeFromParent();
369                    if (isa<Assign>(nested)) {
370                        ifNode->removeDefined(cast<Assign>(nested));
371                    }
372                    nested->insertAfter(stmt);
373                    stmt = nested;
374                    nested = next;
375                }
376                stmt = ifNode->eraseFromParent();
377                continue;
378            }
379
380        } else if (While * whileNode = dyn_cast<While>(stmt)) {
381            // Test whether we can ever take this branch
382            const PabloAST * initial = cast<While>(stmt)->getCondition();
383            if (LLVM_LIKELY(isa<Next>(initial))) {
384                initial = cast<Next>(initial)->getInitial();
385            }
386            if (LLVM_UNLIKELY(isa<Zeroes>(initial))) {
387                stmt = stmt->eraseFromParent();
388                continue;
389            }
390            eliminateRedundantCode(whileNode->getBody(), &encountered);
391            removeIdenticalEscapedValues(whileNode->getVariants());
392            // If the condition's Next state is Zero, we can eliminate the loop after copying the internal
393            // statements into the body.
394        } else {
395            PabloAST * folded = nullptr;
396            if (isReassociative(stmt)) {
397                folded =  foldReassociativeFunction(cast<Variadic>(stmt), block);
398            } else {
399                folded = canTriviallyFold(stmt, block);
400            }
401            if (folded) {
402                // If we determine we can fold this statement,
403                Statement * const prior = stmt->getPrevNode();
404                stmt->replaceWith(folded, true);
405                stmt = prior ? prior->getNextNode() : block->front();
406                continue;
407            }
408            // When we're creating the Pablo program, it's possible to have multiple instances of an "identical"
409            // statement. By recording which statements have already been seen, we can detect the redundant statements
410            // as any having the same type and operands. If so, we can replace its users with the prior statement.
411            // and erase this statement from the AST
412            const auto f = encountered.findOrAdd(stmt);
413            if (!f.second) {
414                stmt = stmt->replaceWith(f.first, true);
415                continue;
416            }
417
418        }
419        stmt = stmt->getNextNode();
420    }
421}
422
423/** ------------------------------------------------------------------------------------------------------------- *
424 * @brief deadCodeElimination
425 ** ------------------------------------------------------------------------------------------------------------- */
426void Simplifier::deadCodeElimination(PabloBlock * const block) {
427    Statement * stmt = block->front();
428    while (stmt) {
429        if (isa<If>(stmt)) {
430            deadCodeElimination(cast<If>(stmt)->getBody());
431        } else if (isa<While>(stmt)) {
432            deadCodeElimination(cast<While>(stmt)->getBody());
433        } else if (stmt->getNumUses() == 0){
434            stmt = stmt->eraseFromParent(true);
435            continue;
436        }
437        stmt = stmt->getNextNode();
438    }
439}
440
441/** ------------------------------------------------------------------------------------------------------------- *
442 * @brief eliminateRedundantEquations
443 ** ------------------------------------------------------------------------------------------------------------- */
444void Simplifier::eliminateRedundantEquations(PabloBlock * const block) {
445    Statement * stmt = block->front();
446    while (stmt) {
447        if (isa<If>(stmt)) {
448            eliminateRedundantEquations(cast<If>(stmt)->getBody());
449        } else if (isa<While>(stmt)) {
450            eliminateRedundantEquations(cast<While>(stmt)->getBody());
451        } else if (isa<Advance>(stmt)) {
452            Advance * adv = cast<Advance>(stmt);
453            if (LLVM_UNLIKELY(isa<Advance>(adv->getOperand(0)))) {
454                // Replace an Advance(Advance(x, n), m) with an Advance(x,n + m)
455                Advance * op = cast<Advance>(stmt->getOperand(0));
456                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
457                    adv->setOperand(0, op->getOperand(0));
458                    adv->setOperand(1, block->getInteger(adv->getAdvanceAmount() + op->getAdvanceAmount()));
459                    op->eraseFromParent(false);
460                }
461            }
462        } else if (LLVM_UNLIKELY(isa<ScanThru>(stmt))) {
463            ScanThru * scanThru = cast<ScanThru>(stmt);
464            if (LLVM_UNLIKELY(isa<Advance>(scanThru->getOperand(0)))) {
465                // Replace a ScanThru(Advance(x,n),y) with an ScanThru(Advance(x, n - 1), Advance(x, n - 1) | y), where Advance(x, 0) = x
466                Advance * op = cast<Advance>(stmt->getOperand(0));
467                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
468                    block->setInsertPoint(scanThru->getPrevNode());
469                    PabloAST * expr = block->createAdvance(op->getOperand(0), op->getAdvanceAmount() - 1);
470                    scanThru->setOperand(0, expr);
471                    scanThru->setOperand(1, block->createOr(scanThru->getOperand(1), expr));
472                    op->eraseFromParent(false);
473                }
474            }
475        }
476        stmt = stmt->getNextNode();
477    }
478    block->setInsertPoint(block->back());
479}
480
481}
Note: See TracBrowser for help on using the repository browser.