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

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

Temporary check-in

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 (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(index) == 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    assert (statement);
127    assert (statement != this);
128    assert (statement->mParent);
129    removeFromParent();
130    mParent = statement->mParent;
131    if (LLVM_UNLIKELY(mParent->mFirst == statement)) {
132        mParent->mFirst = this;
133    }
134    mNext = statement;
135    mPrev = statement->mPrev;
136    statement->mPrev = this;
137    if (LLVM_LIKELY(mPrev != nullptr)) {
138        mPrev->mNext = this;
139    }
140}
141
142void Statement::insertAfter(Statement * const statement) {
143    assert (statement);
144    assert (statement != this);
145    assert (statement->mParent);
146    removeFromParent();
147    mParent = statement->mParent;
148    if (LLVM_UNLIKELY(mParent->mLast == statement)) {
149        mParent->mLast = this;
150    }
151    mPrev = statement;
152    mNext = statement->mNext;
153    statement->mNext = this;
154    if (LLVM_LIKELY(mNext != nullptr)) {
155        mNext->mPrev = this;
156    }
157}
158
159Statement * Statement::removeFromParent() {
160    Statement * next = mNext;
161    if (LLVM_LIKELY(mParent != nullptr)) {
162        if (LLVM_UNLIKELY(mParent->mFirst == this)) {
163            mParent->mFirst = mNext;
164        }
165        if (LLVM_UNLIKELY(mParent->mLast == this)) {
166            mParent->mLast = mPrev;
167        }
168        if (mParent->mInsertionPoint == this) {
169            mParent->mInsertionPoint = mParent->mInsertionPoint->mPrev;
170        }
171        if (LLVM_LIKELY(mPrev != nullptr)) {
172            mPrev->mNext = mNext;
173        }
174        if (LLVM_LIKELY(mNext != nullptr)) {
175            mNext->mPrev = mPrev;
176        }
177    }   
178    mPrev = nullptr;
179    mNext = nullptr;
180    mParent = nullptr;
181    return next;
182}
183
184Statement * Statement::eraseFromParent(const bool recursively) {
185
186    // remove this statement from its operands' users list
187    for (auto i = 0; i != mOperands; ++i) {
188        PabloAST * const op = mOperand[i];
189        op->removeUser(this);
190    }
191
192    if (recursively) {
193        for (auto i = 0; i != mOperands; ++i) {
194            PabloAST * const op = mOperand[i];
195            if (op->getNumUses() == 0 && isa<Statement>(op)) {
196                cast<Statement>(op)->eraseFromParent(true);
197            }
198        }
199    }
200    return removeFromParent();
201}
202
203Statement * Statement::replaceWith(PabloAST * const expr, const bool rename) {
204    assert (expr);
205    if (LLVM_UNLIKELY(expr == this)) {
206        return getNextNode();
207    }
208    if (LLVM_LIKELY(rename && isa<Statement>(expr))) {
209        Statement * const stmt = cast<Statement>(expr);
210        if (getName()->isUserDefined() && stmt->getName()->isGenerated()) {
211            stmt->setName(getName());
212        }
213    }
214    replaceAllUsesWith(expr);
215    return eraseFromParent();
216}
217
218#ifndef NDEBUG
219    bool Statement::noRecursiveOperand(const PabloAST * const operand) {
220        if (operand && isa<Statement>(operand)) {
221            std::queue<const Statement *> Q;
222            Q.push(cast<Statement>(operand));
223            while (!Q.empty()) {
224                const Statement * stmt = Q.front();
225                if (stmt == this) {
226                    return false;
227                }
228                Q.pop();
229                for (auto i = 0; i != stmt->getNumOperands(); ++i) {
230                    const PabloAST * op = stmt->getOperand(i);
231                    if (isa<Statement>(op)) {
232                        Q.push(cast<Statement>(op));
233                    }
234                }
235            }
236        }
237        return true;
238    }
239#endif
240
241void StatementList::insert(Statement * const statement) {
242    if (LLVM_UNLIKELY(mInsertionPoint == nullptr)) {
243        statement->mNext = mFirst;
244        if (mFirst) {
245            assert (mFirst->mPrev == nullptr);
246            mFirst->mPrev = statement;
247        }
248        mLast = (mLast == nullptr) ? statement : mLast;
249        mInsertionPoint = mFirst = statement;
250    }
251    else {
252        statement->insertAfter(mInsertionPoint);
253        mLast = (mLast == mInsertionPoint) ? statement : mLast;
254        mInsertionPoint = statement;
255    }
256}
257
258StatementList::~StatementList() {
259
260}
261
262}
Note: See TracBrowser for help on using the repository browser.