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

Last change on this file since 4568 was 4510, checked in by nmedfort, 5 years ago

Many memory deallocation fixes.

File size: 8.1 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#ifndef NDEBUG
11#include <queue>
12#endif
13namespace pablo {
14
15PabloAST::Allocator PabloAST::mAllocator;
16PabloAST::VectorAllocator PabloAST::mVectorAllocator;
17
18/*
19
20    Return true if expr1 and expr2 can be proven equivalent according to some rules,
21    false otherwise.  Note that false may be returned i some cases when the exprs are
22    equivalent.
23
24*/
25
26bool equals(const PabloAST * expr1, const PabloAST * expr2) {
27    assert (expr1 && expr2);
28    if (expr1->getClassTypeId() == expr2->getClassTypeId()) {
29        if ((isa<Zeroes>(expr1)) || (isa<Ones>(expr1))) {
30            return true;
31        }
32        else if (const Var * var1 = dyn_cast<const Var>(expr1)) {
33            if (const Var * var2 = cast<const Var>(expr2)) {
34                return (var1->getName() == var2->getName());
35            }
36        }
37        else if (const Not* not1 = dyn_cast<const Not>(expr1)) {
38            if (const Not* not2 = cast<const Not>(expr2)) {
39                return equals(not1->getExpr(), not2->getExpr());
40            }
41        }
42        else if (const And* and1 = dyn_cast<const And>(expr1)) {
43            if (const And* and2 = cast<const And>(expr2)) {
44                if (equals(and1->getExpr1(), and2->getExpr1())) {
45                    return equals(and1->getExpr2(), and2->getExpr2());
46                }
47                else if (equals(and1->getExpr1(), and2->getExpr2())) {
48                    return equals(and1->getExpr2(), and2->getExpr1());
49                }
50            }
51        }
52        else if (const Or * or1 = dyn_cast<const Or>(expr1)) {
53            if (const Or* or2 = cast<const Or>(expr2)) {
54                if (equals(or1->getExpr1(), or2->getExpr1())) {
55                    return equals(or1->getExpr2(), or2->getExpr2());
56                }
57                else if (equals(or1->getExpr1(), or2->getExpr2())) {
58                    return equals(or1->getExpr2(), or2->getExpr1());
59                }
60            }
61        }
62        else if (const Xor * xor1 = dyn_cast<const Xor>(expr1)) {
63            if (const Xor * xor2 = cast<const Xor>(expr2)) {
64                if (equals(xor1->getExpr1(), xor2->getExpr1())) {
65                    return equals(xor1->getExpr2(), xor2->getExpr2());
66                }
67                else if (equals(xor1->getExpr1(), xor2->getExpr2())) {
68                    return equals(xor1->getExpr2(), xor2->getExpr1());
69                }
70            }
71        }
72        else if (const Sel* sel1 = dyn_cast<const Sel>(expr1)) {
73            if (const Sel* sel2 = cast<const Sel>(expr2)) {
74                if (equals(sel1->getCondition(), sel2->getCondition())) {
75                    if (equals(sel1->getTrueExpr(), sel2->getTrueExpr())) {
76                        return equals(sel1->getFalseExpr(), sel2->getFalseExpr());
77                    }
78                }
79            }
80        }
81    }
82    return false;
83}
84
85void PabloAST::replaceAllUsesWith(PabloAST * expr) {   
86    Statement * user[mUsers.size()];
87    Users::size_type users = 0;
88    for (PabloAST * u : mUsers) {
89        if (isa<Statement>(u)) {
90            user[users++] = cast<Statement>(u);
91        }
92    }
93    mUsers.clear();
94    assert (expr);
95    for (auto i = 0; i != users; ++i) {
96        user[i]->replaceUsesOfWith(this, expr);
97    }
98}
99
100
101
102void Statement::setOperand(const unsigned index, PabloAST * const value) {
103    assert (index < getNumOperands());
104    assert (noRecursiveOperand(value));
105    if (LLVM_UNLIKELY(getOperand(index) == value)) {
106        return;
107    }
108    PabloAST * priorValue = getOperand(index);
109    // Test just to be sure that we don't have multiple operands pointing to
110    // what we're replacing. If not, remove this from the prior value's
111    // user list.
112    unsigned count = 0;
113    for (unsigned i = 0; i != getNumOperands(); ++i) {
114        count += (getOperand(index) == priorValue) ? 1 : 0;
115    }
116    assert (count >= 1);
117    if (LLVM_LIKELY(count == 1)) {
118        priorValue->removeUser(this);
119    }
120    mOperand[index] = value;
121    value->addUser(this);
122}
123
124void Statement::insertBefore(Statement * const statement) {
125    assert (statement);
126    assert (statement != this);
127    assert (statement->mParent);
128    removeFromParent();
129    mParent = statement->mParent;
130    if (LLVM_UNLIKELY(mParent->mFirst == statement)) {
131        mParent->mFirst = this;
132    }
133    mNext = statement;
134    mPrev = statement->mPrev;
135    statement->mPrev = this;
136    if (LLVM_LIKELY(mPrev != nullptr)) {
137        mPrev->mNext = this;
138    }
139}
140
141void Statement::insertAfter(Statement * const statement) {
142    assert (statement);
143    assert (statement != this);
144    assert (statement->mParent);
145    removeFromParent();
146    mParent = statement->mParent;
147    if (LLVM_UNLIKELY(mParent->mLast == statement)) {
148        mParent->mLast = this;
149    }
150    mPrev = statement;
151    mNext = statement->mNext;
152    statement->mNext = this;
153    if (LLVM_LIKELY(mNext != nullptr)) {
154        mNext->mPrev = this;
155    }
156}
157
158Statement * Statement::removeFromParent() {
159    Statement * next = mNext;
160    if (LLVM_LIKELY(mParent != nullptr)) {
161        if (LLVM_UNLIKELY(mParent->mFirst == this)) {
162            mParent->mFirst = mNext;
163        }
164        if (LLVM_UNLIKELY(mParent->mLast == this)) {
165            mParent->mLast = mPrev;
166        }
167        if (mParent->mInsertionPoint == this) {
168            mParent->mInsertionPoint = mParent->mInsertionPoint->mPrev;
169        }
170        if (LLVM_LIKELY(mPrev != nullptr)) {
171            mPrev->mNext = mNext;
172        }
173        if (LLVM_LIKELY(mNext != nullptr)) {
174            mNext->mPrev = mPrev;
175        }
176    }   
177    mPrev = nullptr;
178    mNext = nullptr;
179    mParent = nullptr;
180    return next;
181}
182
183Statement * Statement::eraseFromParent(const bool recursively) {
184
185    // remove this statement from its operands' users list
186    for (auto i = 0; i != mOperands; ++i) {
187        PabloAST * const op = mOperand[i];
188        op->removeUser(this);
189    }
190
191    if (recursively) {
192        for (auto i = 0; i != mOperands; ++i) {
193            PabloAST * const op = mOperand[i];
194            if (op->getNumUses() == 0 && isa<Statement>(op)) {
195                cast<Statement>(op)->eraseFromParent(true);
196            }
197        }
198    }
199    return removeFromParent();
200}
201
202Statement * Statement::replaceWith(PabloAST * const expr, const bool rename) {
203    assert (expr);
204    if (LLVM_UNLIKELY(expr == this)) {
205        return getNextNode();
206    }
207    if (LLVM_LIKELY(rename && isa<Statement>(expr))) {
208        Statement * const stmt = cast<Statement>(expr);
209        if (getName()->isUserDefined() && stmt->getName()->isGenerated()) {
210            stmt->setName(getName());
211        }
212    }
213    replaceAllUsesWith(expr);
214    return eraseFromParent();
215}
216
217#ifndef NDEBUG
218    bool Statement::noRecursiveOperand(const PabloAST * const operand) {
219        if (operand && isa<Statement>(operand)) {
220            std::queue<const Statement *> Q;
221            Q.push(cast<Statement>(operand));
222            while (!Q.empty()) {
223                const Statement * stmt = Q.front();
224                if (stmt == this) {
225                    return false;
226                }
227                Q.pop();
228                for (auto i = 0; i != stmt->getNumOperands(); ++i) {
229                    const PabloAST * op = stmt->getOperand(i);
230                    if (isa<Statement>(op)) {
231                        Q.push(cast<Statement>(op));
232                    }
233                }
234            }
235        }
236        return true;
237    }
238#endif
239
240void StatementList::insert(Statement * const statement) {
241    if (LLVM_UNLIKELY(mInsertionPoint == nullptr)) {
242        statement->mNext = mFirst;
243        if (mFirst) {
244            assert (mFirst->mPrev == nullptr);
245            mFirst->mPrev = statement;
246        }
247        mLast = (mLast == nullptr) ? statement : mLast;
248        mInsertionPoint = mFirst = statement;
249    }
250    else {
251        statement->insertAfter(mInsertionPoint);
252        mLast = (mLast == mInsertionPoint) ? statement : mLast;
253        mInsertionPoint = statement;
254    }
255}
256
257StatementList::~StatementList() {
258
259}
260
261}
Note: See TracBrowser for help on using the repository browser.