source: icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp @ 4984

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

Incorporated a few common case boolean optimizations in the Simplifier.

File size: 16.8 KB
Line 
1/*
2 *  Copyright (c) 2014 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6
7#include <pablo/pabloAST.h>
8#include <pablo/codegenstate.h>
9#include <llvm/Support/Compiler.h>
10#include <pablo/printer_pablos.h>
11#include <llvm/ADT/SmallVector.h>
12
13namespace pablo {
14
15PabloAST::Allocator PabloAST::mAllocator;
16
17/** ------------------------------------------------------------------------------------------------------------- *
18 * @brief equals
19 *
20 *  Return true if expr1 and expr2 can be proven equivalent according to some rules, false otherwise.  Note that
21 *  false may be returned i some cases when the exprs are equivalent.
22 ** ------------------------------------------------------------------------------------------------------------- */
23bool equals(const PabloAST * expr1, const PabloAST * expr2) {
24    assert (expr1 && expr2);
25    if (expr1 == expr2) {
26        return true;
27    } else if (expr1->getClassTypeId() == expr2->getClassTypeId()) {
28        if ((isa<Zeroes>(expr1)) || (isa<Ones>(expr1))) {
29            return true;
30        } else if (isa<Var>(expr1)) {
31            return (cast<Var>(expr1)->getName() == cast<Var>(expr2)->getName());
32        } else if (isa<Not>(expr1)) {
33            return equals(cast<Not>(expr1)->getOperand(0), cast<Not>(expr2)->getOperand(0));
34        } else if (isa<Variadic>(expr1)) {
35            const Variadic * const var1 = cast<Variadic>(expr1);
36            const Variadic * const var2 = cast<Variadic>(expr2);
37            if (var1->getNumOperands() == var2->getNumOperands()) {
38                const unsigned operands = var1->getNumOperands();
39                for (unsigned i = 0; i != operands; ++i) {
40                    bool missing = true;
41                    for (unsigned j = 0; j != operands; ++j) {
42                        // odds are both variadics will be sorted; optimize towards testing them in order.
43                        unsigned k = i + j;
44                        if (LLVM_UNLIKELY(k >= operands)) {
45                            k -= operands;
46                        }
47                        if (equals(var1->getOperand(i), var2->getOperand(k))) {
48                            missing = false;
49                            break;
50                        }
51                    }
52                    if (missing) {
53                        return false;
54                    }
55                }
56                return true;
57            }
58        } else if (isa<Integer>(expr1) || isa<String>(expr1) || isa<Call>(expr1)) {
59            return false; // If these weren't equivalent by address they won't be equivalent by their operands.
60        } else { // Non-reassociatable functions (i.e., Sel, Advance, ScanThru, MatchStar, Assign, Next)
61            const Statement * stmt1 = cast<Statement>(expr1);
62            const Statement * stmt2 = cast<Statement>(expr2);
63            assert (stmt1->getNumOperands() == stmt2->getNumOperands());
64            for (unsigned i = 0; i != stmt1->getNumOperands(); ++i) {
65                if (!equals(stmt1->getOperand(i), stmt2->getOperand(i))) {
66                    return false;
67                }
68            }
69            return true;
70        }
71    }
72    return false;
73}
74
75/** ------------------------------------------------------------------------------------------------------------- *
76 * @brief replaceAllUsesWith
77 ** ------------------------------------------------------------------------------------------------------------- */
78void PabloAST::replaceAllUsesWith(PabloAST * const expr) {
79    assert (expr);
80    if (LLVM_UNLIKELY(this == expr)) {
81        return;
82    }
83    Statement * replacement[mUsers.size()];
84    Users::size_type replacements = 0;
85    PabloAST * last = nullptr;
86    for (PabloAST * user : mUsers) {
87        if (LLVM_UNLIKELY(user == expr || user == last)) {
88            continue;
89        } else if (isa<Statement>(user)) {
90            replacement[replacements++] = cast<Statement>(user);
91            last = user;
92        }
93    }
94    for (Users::size_type i = 0; i != replacements; ++i) {
95        replacement[i]->replaceUsesOfWith(this, expr);
96    }
97}
98
99/** ------------------------------------------------------------------------------------------------------------- *
100 * @brief checkEscapedValueList
101 ** ------------------------------------------------------------------------------------------------------------- */
102template <class ValueType, class ValueList>
103inline void Statement::checkEscapedValueList(Statement * const branch, PabloAST * const from, PabloAST * const to, ValueList & list) {
104    if (LLVM_LIKELY(isa<ValueType>(from))) {
105        auto f = std::find(list.begin(), list.end(), cast<ValueType>(from));
106        if (LLVM_LIKELY(f != list.end())) {
107            branch->removeUser(from);
108            from->removeUser(branch);
109            if (LLVM_LIKELY(isa<ValueType>(to))) {
110                if (std::count(list.begin(), list.end(), cast<ValueType>(to)) == 0) {
111                    *f = cast<ValueType>(to);
112                    branch->addUser(to);
113                    to->addUser(branch);
114                    return;
115                }
116            }
117            list.erase(f);
118        }                             
119    }
120}
121
122/** ------------------------------------------------------------------------------------------------------------- *
123 * @brief replaceUsesOfWith
124 ** ------------------------------------------------------------------------------------------------------------- */
125void Statement::replaceUsesOfWith(PabloAST * const from, PabloAST * const to) {
126    if (LLVM_UNLIKELY(from == to)) {
127        return;
128    }
129    for (unsigned i = 0; i != getNumOperands(); ++i) {
130       if (getOperand(i) == from) {
131           setOperand(i, to);
132       }
133    }
134    if (LLVM_UNLIKELY(isa<If>(this))) {
135        checkEscapedValueList<Assign>(this, from, to, cast<If>(this)->getDefined());
136    } else if (LLVM_UNLIKELY(isa<While>(this))) {
137        checkEscapedValueList<Next>(this, from, to, cast<While>(this)->getVariants());
138    }
139}
140
141/** ------------------------------------------------------------------------------------------------------------- *
142 * @brief setOperand
143 ** ------------------------------------------------------------------------------------------------------------- */
144void Statement::setOperand(const unsigned index, PabloAST * const value) {
145    assert ("Operand cannot be null!" && value);
146    assert (index < getNumOperands());
147    PabloAST * const prior = getOperand(index);
148    assert ("Operand cannot be null!" && prior);
149    if (LLVM_UNLIKELY(prior == value)) {
150        return;
151    }   
152    prior->removeUser(this);
153    mOperand[index] = value;
154    value->addUser(this);
155}
156
157/** ------------------------------------------------------------------------------------------------------------- *
158 * @brief insertBefore
159 ** ------------------------------------------------------------------------------------------------------------- */
160void Statement::insertBefore(Statement * const statement) {
161    if (LLVM_UNLIKELY(statement == this)) {
162        return;
163    }
164    else if (LLVM_UNLIKELY(statement == nullptr)) {
165        throw std::runtime_error("cannot insert before null statement!");
166    }
167    else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
168        throw std::runtime_error("statement is not contained in a pablo block!");
169    }
170    removeFromParent();
171    mParent = statement->mParent;
172    if (LLVM_UNLIKELY(mParent->mFirst == statement)) {
173        mParent->mFirst = this;
174    }
175    mNext = statement;
176    mPrev = statement->mPrev;
177    statement->mPrev = this;
178    if (LLVM_LIKELY(mPrev != nullptr)) {
179        mPrev->mNext = this;
180    }
181    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
182        PabloBlock * body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
183        body->setParent(mParent);
184    }
185}
186
187/** ------------------------------------------------------------------------------------------------------------- *
188 * @brief insertAfter
189 ** ------------------------------------------------------------------------------------------------------------- */
190void Statement::insertAfter(Statement * const statement) {
191    if (LLVM_UNLIKELY(statement == this)) {
192        return;
193    } else if (LLVM_UNLIKELY(statement == nullptr)) {
194        throw std::runtime_error("cannot insert after null statement!");
195    } else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
196        throw std::runtime_error("statement is not contained in a pablo block!");
197    }
198    removeFromParent();
199    mParent = statement->mParent;
200    if (LLVM_UNLIKELY(mParent->mLast == statement)) {
201        mParent->mLast = this;
202    }
203    mPrev = statement;
204    mNext = statement->mNext;
205    statement->mNext = this;
206    if (LLVM_LIKELY(mNext != nullptr)) {
207        mNext->mPrev = this;
208    }
209    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
210        PabloBlock * body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
211        body->setParent(mParent);
212    }
213}
214
215/** ------------------------------------------------------------------------------------------------------------- *
216 * @brief removeFromParent
217 ** ------------------------------------------------------------------------------------------------------------- */
218Statement * Statement::removeFromParent() {
219    Statement * next = mNext;
220    if (LLVM_LIKELY(mParent != nullptr)) {
221        if (LLVM_UNLIKELY(mParent->mFirst == this)) {
222            mParent->mFirst = mNext;
223        }
224        if (LLVM_UNLIKELY(mParent->mLast == this)) {
225            mParent->mLast = mPrev;
226        }
227        if (LLVM_UNLIKELY(mParent->mInsertionPoint == this)) {
228            mParent->mInsertionPoint = mPrev;
229        }
230        if (LLVM_LIKELY(mPrev != nullptr)) {
231            mPrev->mNext = mNext;
232        }
233        if (LLVM_LIKELY(mNext != nullptr)) {
234            mNext->mPrev = mPrev;
235        }
236        if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
237            PabloBlock * body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
238            body->setParent(nullptr);
239        }
240    }
241    mPrev = nullptr;
242    mNext = nullptr;
243    mParent = nullptr;
244    return next;
245}
246
247/** ------------------------------------------------------------------------------------------------------------- *
248 * @brief eraseFromParent
249 ** ------------------------------------------------------------------------------------------------------------- */
250Statement * Statement::eraseFromParent(const bool recursively) {
251    // remove this statement from its operands' users list
252    for (unsigned i = 0; i != mOperands; ++i) {
253        mOperand[i]->removeUser(this);
254    }
255    SmallVector<Statement *, 1> redundantBranches;
256    // If this is an If or While statement, we'll have to remove the statements within the
257    // body or we'll lose track of them.
258    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
259        PabloBlock * const body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
260        body->eraseFromParent(recursively);
261    } else if (LLVM_UNLIKELY(isa<Assign>(this))) {
262        for (PabloAST * use : mUsers) {
263            if (If * ifNode = dyn_cast<If>(use)) {
264                auto & defs = ifNode->getDefined();
265                auto f = std::find(defs.begin(), defs.end(), this);
266                if (LLVM_LIKELY(f != defs.end())) {
267                    this->removeUser(ifNode);
268                    ifNode->removeUser(this);
269                    defs.erase(f);
270                    if (LLVM_UNLIKELY(defs.empty())) {
271                        redundantBranches.push_back(ifNode);
272                    }
273                }
274            }
275        }
276    } else if (LLVM_UNLIKELY(isa<Next>(this))) {
277        for (PabloAST * use : mUsers) {
278            if (While * whileNode = dyn_cast<While>(use)) {
279                auto & vars = whileNode->getVariants();
280                auto f = std::find(vars.begin(), vars.end(), this);
281                if (LLVM_LIKELY(f != vars.end())) {
282                    this->removeUser(whileNode);
283                    whileNode->removeUser(this);
284                    vars.erase(f);
285                    if (LLVM_UNLIKELY(vars.empty())) {
286                        redundantBranches.push_back(whileNode);
287                    }
288                }
289            }
290        }
291    }
292
293    replaceAllUsesWith(PabloBlock::createZeroes());
294
295    if (recursively) {
296        for (unsigned i = 0; i != mOperands; ++i) {
297            PabloAST * const op = mOperand[i];
298            if (LLVM_LIKELY(isa<Statement>(op))) {
299                if (op->getNumUses() == 0) {
300                    cast<Statement>(op)->eraseFromParent(true);
301                }
302            }
303        }
304        if (LLVM_UNLIKELY(redundantBranches.size() != 0)) {
305            // By eliminating this redundant branch, we may inadvertantly delete the scope block this statement
306            // resides within. Return null if so.
307            bool eliminatedScope = false;
308            for (Statement * br : redundantBranches) {
309                const PabloBlock * const body = isa<If>(br) ? cast<If>(br)->getBody() : cast<While>(br)->getBody();
310                if (LLVM_UNLIKELY(body == getParent())) {
311                    eliminatedScope = true;
312                }
313                br->eraseFromParent(true);
314            }
315            if (eliminatedScope) {
316                return nullptr;
317            }
318        }
319    }
320    Statement * const next = removeFromParent();
321    mAllocator.deallocate(reinterpret_cast<Allocator::pointer>(this));
322    return next;
323}
324
325/** ------------------------------------------------------------------------------------------------------------- *
326 * @brief replaceWith
327 ** ------------------------------------------------------------------------------------------------------------- */
328Statement * Statement::replaceWith(PabloAST * const expr, const bool rename, const bool recursively) {
329    assert (expr);
330    if (LLVM_UNLIKELY(expr == this)) {
331        return getNextNode();
332    }
333    if (LLVM_LIKELY(rename && isa<Statement>(expr))) {
334        Statement * const stmt = cast<Statement>(expr);
335        if (getName()->isUserDefined() && stmt->getName()->isGenerated()) {
336            stmt->setName(getName());
337        }
338    }
339    replaceAllUsesWith(expr);
340    return eraseFromParent(recursively);
341}
342
343/** ------------------------------------------------------------------------------------------------------------- *
344 * @brief addOperand
345 ** ------------------------------------------------------------------------------------------------------------- */
346void Variadic::addOperand(PabloAST * const expr) {
347    if (LLVM_UNLIKELY(mOperands == mCapacity)) {
348        mCapacity = std::max<unsigned>(mCapacity * 2, 2);
349        PabloAST ** expandedOperandSpace = reinterpret_cast<PabloAST**>(mAllocator.allocate(mCapacity * sizeof(PabloAST *)));
350        for (unsigned i = 0; i != mOperands; ++i) {
351            expandedOperandSpace[i] = mOperand[i];
352        }
353        mAllocator.deallocate(reinterpret_cast<Allocator::pointer>(mOperand));
354        mOperand = expandedOperandSpace;
355    }
356    mOperand[mOperands++] = expr;
357    expr->addUser(this);
358}
359
360/** ------------------------------------------------------------------------------------------------------------- *
361 * @brief removeOperand
362 ** ------------------------------------------------------------------------------------------------------------- */
363PabloAST * Variadic::removeOperand(const unsigned index) {
364    assert (index < mOperands);
365    PabloAST * const expr = mOperand[index];
366    assert (expr);
367    --mOperands;
368    for (unsigned i = index; i != mOperands; ++i) {
369        mOperand[i] = mOperand[i + 1];
370    }
371    mOperand[mOperands] = nullptr;
372    expr->removeUser(this);
373    return expr;
374}
375
376/** ------------------------------------------------------------------------------------------------------------- *
377 * @brief contains
378 ** ------------------------------------------------------------------------------------------------------------- */
379bool StatementList::contains(Statement * const statement) {
380    for (Statement * stmt : *this) {
381        if (statement == stmt) {
382            return true;
383        }
384    }
385    return false;
386}
387
388/** ------------------------------------------------------------------------------------------------------------- *
389 * @brief escapes
390 *
391 * Is this statement used outside of its scope?
392 ** ------------------------------------------------------------------------------------------------------------- */
393bool escapes(const Statement * statement) {
394    const PabloBlock * const parent = statement->getParent();
395    for (const PabloAST * user : statement->users()) {
396        if (LLVM_LIKELY(isa<Statement>(user))) {
397            const PabloBlock * used = cast<Statement>(user)->getParent();
398            while (used != parent) {
399                used = used->getParent();
400                if (used == nullptr) {
401                    assert (isa<Assign>(statement) || isa<Next>(statement));
402                    return true;
403                }
404            }
405        }
406    }
407    return false;
408}
409
410}
Note: See TracBrowser for help on using the repository browser.