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

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

More work towards n-ary And/Or/Xor? functions.

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