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

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

Temporary check-in

File size: 9.5 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
100void Statement::setOperand(const unsigned index, PabloAST * const value) {
101    assert (value);
102    assert (index < getNumOperands());
103    assert (noRecursiveOperand(value));
104    if (LLVM_UNLIKELY(getOperand(index) == value)) {
105        return;
106    }
107    PabloAST * priorValue = getOperand(index);
108    // Test just to be sure that we don't have multiple operands pointing to
109    // what we're replacing. If not, remove this from the prior value's
110    // user list.
111    unsigned count = 0;
112    for (unsigned i = 0; i != getNumOperands(); ++i) {
113        count += (getOperand(i) == priorValue) ? 1 : 0;
114    }
115    assert (count >= 1);
116    if (LLVM_LIKELY(count == 1)) {
117        priorValue->removeUser(this);
118    }
119    mOperand[index] = value;
120    value->addUser(this);
121}
122
123void Statement::insertBefore(Statement * const statement) {
124    assert (statement);
125    assert (statement != this);
126    assert (statement->mParent);
127    removeFromParent();
128    mParent = statement->mParent;
129    if (LLVM_UNLIKELY(mParent->mFirst == statement)) {
130        mParent->mFirst = this;
131    }
132    mNext = statement;
133    mPrev = statement->mPrev;
134    statement->mPrev = this;
135    if (LLVM_LIKELY(mPrev != nullptr)) {
136        mPrev->mNext = this;
137    }
138    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
139        PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
140        mParent->addUser(&body);
141    }
142}
143
144void Statement::insertAfter(Statement * const statement) {
145    assert (statement);
146    assert (statement != this);
147    assert (statement->mParent);
148    removeFromParent();
149    mParent = statement->mParent;
150    if (LLVM_UNLIKELY(mParent->mLast == statement)) {
151        mParent->mLast = this;
152    }
153    mPrev = statement;
154    mNext = statement->mNext;
155    statement->mNext = this;
156    if (LLVM_LIKELY(mNext != nullptr)) {
157        mNext->mPrev = this;
158    }
159    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
160        PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
161        mParent->addUser(&body);
162    }
163}
164
165Statement * Statement::removeFromParent() {
166    Statement * next = mNext;
167    if (LLVM_LIKELY(mParent != nullptr)) {
168        if (LLVM_UNLIKELY(mParent->mFirst == this)) {
169            mParent->mFirst = mNext;
170        }
171        if (LLVM_UNLIKELY(mParent->mLast == this)) {
172            mParent->mLast = mPrev;
173        }
174        if (mParent->mInsertionPoint == this) {
175            mParent->mInsertionPoint = mParent->mInsertionPoint->mPrev;
176        }
177        if (LLVM_LIKELY(mPrev != nullptr)) {
178            mPrev->mNext = mNext;
179        }
180        if (LLVM_LIKELY(mNext != nullptr)) {
181            mNext->mPrev = mPrev;
182        }
183        if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
184            PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
185            mParent->removeUser(&body);
186        }
187    }
188    mPrev = nullptr;
189    mNext = nullptr;
190    mParent = nullptr;
191    return next;
192}
193
194Statement * Statement::eraseFromParent(const bool recursively) {
195    // remove this statement from its operands' users list
196    for (auto i = 0; i != mOperands; ++i) {
197        mOperand[i]->removeUser(this);
198    }
199    // If this is an If or While statement, we'll have to remove the statements within the
200    // body or we'll lose track of them.
201    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
202        if (isa<If>(this)) {
203            // Eliminate the relationship between the If node and its defined vars ...
204            for (PabloAST * var : cast<If>(this)->getDefined()) {
205                var->removeUser(this);
206                this->removeUser(var);
207                var->replaceAllUsesWith(mParent->createZeroes());
208            }
209        }
210        PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
211        Statement * stmt = body.front();
212        while (stmt) {
213            stmt = stmt->eraseFromParent(recursively);
214        }       
215    }
216
217    if (recursively) {
218        for (auto i = 0; i != mOperands; ++i) {
219            PabloAST * const op = mOperand[i];
220            if (op->getNumUses() == 0 && isa<Statement>(op)) {
221                cast<Statement>(op)->eraseFromParent(true);
222            }
223        }
224    }
225    return removeFromParent();
226}
227
228Statement * Statement::replaceWith(PabloAST * const expr, const bool rename, const bool recursively) {
229    assert (expr);
230    if (LLVM_UNLIKELY(expr == this)) {
231        return getNextNode();
232    }
233    if (LLVM_LIKELY(rename && isa<Statement>(expr))) {
234        Statement * const stmt = cast<Statement>(expr);
235        if (getName()->isUserDefined() && stmt->getName()->isGenerated()) {
236            stmt->setName(getName());
237        }
238    }
239    replaceAllUsesWith(expr);   
240    return eraseFromParent(recursively);
241}
242
243#ifndef NDEBUG
244bool Statement::noRecursiveOperand(const PabloAST * const operand) {
245    if (operand && isa<Statement>(operand)) {
246        std::queue<const Statement *> Q;
247        Q.push(cast<Statement>(operand));
248        while (!Q.empty()) {
249            const Statement * stmt = Q.front();
250            if (stmt == this) {
251                return false;
252            }
253            Q.pop();
254            for (auto i = 0; i != stmt->getNumOperands(); ++i) {
255                const PabloAST * op = stmt->getOperand(i);
256                if (isa<Statement>(op)) {
257                    Q.push(cast<Statement>(op));
258                }
259            }
260        }
261    }
262    return true;
263}
264#endif
265
266void StatementList::insert(Statement * const statement) {
267    if (LLVM_UNLIKELY(mInsertionPoint == nullptr)) {
268        statement->mNext = mFirst;
269        if (mFirst) {
270            assert (mFirst->mPrev == nullptr);
271            mFirst->mPrev = statement;
272        }
273        mLast = (mLast == nullptr) ? statement : mLast;
274        mInsertionPoint = mFirst = statement;
275    }
276    else {
277        statement->insertAfter(mInsertionPoint);
278        mLast = (mLast == mInsertionPoint) ? statement : mLast;
279        assert (statement->mPrev == mInsertionPoint);
280        mInsertionPoint = statement;
281    }
282}
283
284StatementList::~StatementList() {
285
286}
287
288}
Note: See TracBrowser for help on using the repository browser.