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

Last change on this file since 4899 was 4899, checked in by nmedfort, 3 years ago

Work on lowering + minor bug fixes.

File size: 16.8 KB
RevLine 
[4244]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
[4419]7#include <pablo/pabloAST.h>
[4404]8#include <pablo/codegenstate.h>
[4276]9#include <llvm/Support/Compiler.h>
[4650]10#include <pablo/printer_pablos.h>
[4871]11#include <llvm/ADT/SmallVector.h>
[4722]12
[4244]13namespace pablo {
14
[4272]15PabloAST::Allocator PabloAST::mAllocator;
16
[4856]17/** ------------------------------------------------------------------------------------------------------------- *
18 * @brief equals
[4876]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.
[4856]22 ** ------------------------------------------------------------------------------------------------------------- */
[4244]23bool equals(const PabloAST * expr1, const PabloAST * expr2) {
[4276]24    assert (expr1 && expr2);
[4797]25    if (expr1 == expr2) {
26        return true;
27    } else if (expr1->getClassTypeId() == expr2->getClassTypeId()) {
[4510]28        if ((isa<Zeroes>(expr1)) || (isa<Ones>(expr1))) {
[4247]29            return true;
[4886]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                    }
[4244]55                }
[4886]56                return true;
[4244]57            }
[4797]58        } else if (isa<Integer>(expr1) || isa<String>(expr1) || isa<Call>(expr1)) {
[4886]59            return false; // If these weren't equivalent by address they won't be equivalent by their operands.
[4805]60        } else { // Non-reassociatable functions (i.e., Sel, Advance, ScanThru, MatchStar, Assign, Next)
[4797]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;
[4244]67                }
68            }
[4797]69            return true;
[4244]70        }
71    }
72    return false;
73}
74
[4856]75/** ------------------------------------------------------------------------------------------------------------- *
76 * @brief replaceAllUsesWith
77 ** ------------------------------------------------------------------------------------------------------------- */
[4899]78void PabloAST::replaceAllUsesWith(PabloAST * const expr) {
[4876]79    assert (expr);
[4871]80    if (LLVM_UNLIKELY(this == expr)) {
81        return;
82    }
[4876]83    Statement * replacement[mUsers.size()];
84    Users::size_type replacements = 0;
85    PabloAST * last = nullptr;
[4868]86    for (PabloAST * user : mUsers) {
[4876]87        if (LLVM_UNLIKELY(user == expr || user == last)) {
[4868]88            continue;
[4876]89        } else if (isa<Statement>(user)) {
90            replacement[replacements++] = cast<Statement>(user);
91            last = user;
[4416]92        }
93    }
[4876]94    for (Users::size_type i = 0; i != replacements; ++i) {
95        replacement[i]->replaceUsesOfWith(this, expr);
[4868]96    }
[4416]97}
98
[4856]99/** ------------------------------------------------------------------------------------------------------------- *
[4871]100 * @brief checkEscapedValueList
[4856]101 ** ------------------------------------------------------------------------------------------------------------- */
102template <class ValueType, class ValueList>
[4899]103inline void Statement::checkEscapedValueList(Statement * const branch, PabloAST * const from, PabloAST * const to, ValueList & list) {
[4856]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())) {
[4899]107            branch->removeUser(from);
108            from->removeUser(branch);
[4856]109            if (LLVM_LIKELY(isa<ValueType>(to))) {
[4899]110                if (std::count(list.begin(), list.end(), cast<ValueType>(to)) == 0) {
[4856]111                    *f = cast<ValueType>(to);
112                    branch->addUser(to);
[4899]113                    to->addUser(branch);
114                    return;
[4856]115                }
116            }
[4899]117            list.erase(f);
118        }                             
[4856]119    }
120}
121
122/** ------------------------------------------------------------------------------------------------------------- *
123 * @brief replaceUsesOfWith
124 ** ------------------------------------------------------------------------------------------------------------- */
125void Statement::replaceUsesOfWith(PabloAST * const from, PabloAST * const to) {
[4871]126    if (LLVM_UNLIKELY(from == to)) {
127        return;
128    }
[4856]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))) {
[4871]135        checkEscapedValueList<Assign>(this, from, to, cast<If>(this)->getDefined());
[4856]136    } else if (LLVM_UNLIKELY(isa<While>(this))) {
[4871]137        checkEscapedValueList<Next>(this, from, to, cast<While>(this)->getVariants());
[4856]138    }
139}
140
141/** ------------------------------------------------------------------------------------------------------------- *
142 * @brief setOperand
143 ** ------------------------------------------------------------------------------------------------------------- */
[4432]144void Statement::setOperand(const unsigned index, PabloAST * const value) {
[4899]145    assert ("Operand cannot be null!" && value);
[4415]146    assert (index < getNumOperands());
[4876]147    PabloAST * const prior = getOperand(index);
[4899]148    assert ("Operand cannot be null!" && prior);
[4876]149    if (LLVM_UNLIKELY(prior == value)) {
[4416]150        return;
[4722]151    }   
[4876]152    prior->removeUser(this);
[4416]153    mOperand[index] = value;
154    value->addUser(this);
[4415]155}
[4404]156
[4856]157/** ------------------------------------------------------------------------------------------------------------- *
158 * @brief insertBefore
159 ** ------------------------------------------------------------------------------------------------------------- */
[4404]160void Statement::insertBefore(Statement * const statement) {
[4650]161    if (LLVM_UNLIKELY(statement == this)) {
162        return;
163    }
164    else if (LLVM_UNLIKELY(statement == nullptr)) {
[4723]165        throw std::runtime_error("cannot insert before null statement!");
[4650]166    }
167    else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
[4723]168        throw std::runtime_error("statement is not contained in a pablo block!");
[4650]169    }
[4404]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    }
[4611]181    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
[4870]182        PabloBlock * body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
183        body->setParent(mParent);
[4611]184    }
[4404]185}
186
[4856]187/** ------------------------------------------------------------------------------------------------------------- *
188 * @brief insertAfter
189 ** ------------------------------------------------------------------------------------------------------------- */
[4404]190void Statement::insertAfter(Statement * const statement) {
[4650]191    if (LLVM_UNLIKELY(statement == this)) {
192        return;
[4871]193    } else if (LLVM_UNLIKELY(statement == nullptr)) {
[4723]194        throw std::runtime_error("cannot insert after null statement!");
[4871]195    } else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
[4723]196        throw std::runtime_error("statement is not contained in a pablo block!");
[4650]197    }
[4404]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    }
[4611]209    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
[4870]210        PabloBlock * body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
211        body->setParent(mParent);
[4611]212    }
[4404]213}
214
[4856]215/** ------------------------------------------------------------------------------------------------------------- *
216 * @brief removeFromParent
217 ** ------------------------------------------------------------------------------------------------------------- */
[4416]218Statement * Statement::removeFromParent() {
219    Statement * next = mNext;
[4404]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        }
[4650]227        if (LLVM_UNLIKELY(mParent->mInsertionPoint == this)) {
228            mParent->mInsertionPoint = mPrev;
[4415]229        }
[4404]230        if (LLVM_LIKELY(mPrev != nullptr)) {
231            mPrev->mNext = mNext;
232        }
233        if (LLVM_LIKELY(mNext != nullptr)) {
234            mNext->mPrev = mPrev;
235        }
[4611]236        if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
[4870]237            PabloBlock * body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
238            body->setParent(nullptr);
[4611]239        }
[4592]240    }
[4404]241    mPrev = nullptr;
242    mNext = nullptr;
243    mParent = nullptr;
[4416]244    return next;
[4404]245}
246
[4856]247/** ------------------------------------------------------------------------------------------------------------- *
248 * @brief eraseFromParent
249 ** ------------------------------------------------------------------------------------------------------------- */
[4416]250Statement * Statement::eraseFromParent(const bool recursively) {
251    // remove this statement from its operands' users list
[4750]252    for (unsigned i = 0; i != mOperands; ++i) {
[4592]253        mOperand[i]->removeUser(this);
[4416]254    }
[4871]255    SmallVector<Statement *, 1> redundantBranches;
[4594]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))) {
[4870]259        PabloBlock * const body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
260        body->eraseFromParent(recursively);
[4788]261    } else if (LLVM_UNLIKELY(isa<Assign>(this))) {
262        for (PabloAST * use : mUsers) {
263            if (If * ifNode = dyn_cast<If>(use)) {
[4829]264                auto & defs = ifNode->getDefined();
265                auto f = std::find(defs.begin(), defs.end(), this);
266                if (LLVM_LIKELY(f != defs.end())) {
[4788]267                    this->removeUser(ifNode);
268                    ifNode->removeUser(this);
[4829]269                    defs.erase(f);
270                    if (LLVM_UNLIKELY(defs.empty())) {
[4871]271                        redundantBranches.push_back(ifNode);
[4829]272                    }
[4788]273                }
274            }
275        }
276    } else if (LLVM_UNLIKELY(isa<Next>(this))) {
277        for (PabloAST * use : mUsers) {
278            if (While * whileNode = dyn_cast<While>(use)) {
[4829]279                auto & vars = whileNode->getVariants();
280                auto f = std::find(vars.begin(), vars.end(), this);
281                if (LLVM_LIKELY(f != vars.end())) {
[4788]282                    this->removeUser(whileNode);
283                    whileNode->removeUser(this);
[4829]284                    vars.erase(f);
285                    if (LLVM_UNLIKELY(vars.empty())) {
[4871]286                        redundantBranches.push_back(whileNode);
[4829]287                    }
[4788]288                }
289            }
290        }
[4594]291    }
292
[4788]293    replaceAllUsesWith(PabloBlock::createZeroes());
294
[4419]295    if (recursively) {
[4750]296        for (unsigned i = 0; i != mOperands; ++i) {
[4432]297            PabloAST * const op = mOperand[i];
[4829]298            if (LLVM_LIKELY(isa<Statement>(op))) {
299                if (op->getNumUses() == 0) {
300                    cast<Statement>(op)->eraseFromParent(true);
301                }
[4419]302            }
[4415]303        }
[4871]304        if (LLVM_UNLIKELY(redundantBranches.size() != 0)) {
[4870]305            // By eliminating this redundant branch, we may inadvertantly delete the scope block this statement
[4876]306            // resides within. Return null if so.
[4871]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            }
[4870]315            if (eliminatedScope) {
316                return nullptr;
317            }
[4829]318        }
[4404]319    }
[4861]320    Statement * const next = removeFromParent();
321    mAllocator.deallocate(reinterpret_cast<Allocator::pointer>(this));
322    return next;
[4419]323}
[4280]324
[4856]325/** ------------------------------------------------------------------------------------------------------------- *
326 * @brief replaceWith
327 ** ------------------------------------------------------------------------------------------------------------- */
[4586]328Statement * Statement::replaceWith(PabloAST * const expr, const bool rename, const bool recursively) {
[4433]329    assert (expr);
[4419]330    if (LLVM_UNLIKELY(expr == this)) {
331        return getNextNode();
[4416]332    }
[4433]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    }
[4899]339    replaceAllUsesWith(expr);
[4586]340    return eraseFromParent(recursively);
[4415]341}
342
[4856]343/** ------------------------------------------------------------------------------------------------------------- *
[4873]344 * @brief addOperand
345 ** ------------------------------------------------------------------------------------------------------------- */
[4876]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];
[4873]352        }
353        mAllocator.deallocate(reinterpret_cast<Allocator::pointer>(mOperand));
[4876]354        mOperand = expandedOperandSpace;
[4873]355    }
[4876]356    mOperand[mOperands++] = expr;
357    expr->addUser(this);
[4873]358}
359
360/** ------------------------------------------------------------------------------------------------------------- *
361 * @brief removeOperand
362 ** ------------------------------------------------------------------------------------------------------------- */
[4876]363PabloAST * Variadic::removeOperand(const unsigned index) {
364    assert (index < mOperands);
365    PabloAST * const expr = mOperand[index];
[4873]366    --mOperands;
[4876]367    for (unsigned i = index; i != mOperands; ++i) {
368        mOperand[i] = mOperand[i + 1];
369    }
370    mOperand[mOperands] = nullptr;
371    expr->removeUser(this);
372    return expr;
[4873]373}
374
375/** ------------------------------------------------------------------------------------------------------------- *
[4856]376 * @brief contains
377 ** ------------------------------------------------------------------------------------------------------------- */
[4775]378bool StatementList::contains(Statement * const statement) {
379    for (Statement * stmt : *this) {
380        if (statement == stmt) {
381            return true;
382        }
383    }
384    return false;
385}
386
[4774]387/** ------------------------------------------------------------------------------------------------------------- *
388 * @brief escapes
389 *
390 * Is this statement used outside of its scope?
391 ** ------------------------------------------------------------------------------------------------------------- */
392bool escapes(const Statement * statement) {
393    const PabloBlock * const parent = statement->getParent();
394    for (const PabloAST * user : statement->users()) {
395        if (LLVM_LIKELY(isa<Statement>(user))) {
396            const PabloBlock * used = cast<Statement>(user)->getParent();
397            while (used != parent) {
398                used = used->getParent();
399                if (used == nullptr) {
400                    assert (isa<Assign>(statement) || isa<Next>(statement));
401                    return true;
402                }
403            }
404        }
405    }
406    return false;
[4432]407}
[4774]408
409}
Note: See TracBrowser for help on using the repository browser.