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

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

Temporary check-in.

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