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

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

Misc. changes and start of dependency chain analysis in ucd generator.

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