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

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

Temporary check in.

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