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

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

Added ability to infer mutual exclusivity / subset relationships based on already proven relationships. Simplifer can now eliminate If nodes whenever all of the defined vars are Zeroes.

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