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

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

Initial introduction of a PabloFunction? type.

File size: 9.5 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    if (LLVM_LIKELY(priorValue != nullptr)) {
111        // Test just to be sure that we don't have multiple operands pointing to
112        // what we're replacing. If not, remove this from the prior value's
113        // user list.
114        unsigned count = 0;
115        for (unsigned i = 0; i != getNumOperands(); ++i) {
116            count += (getOperand(i) == priorValue) ? 1 : 0;
117        }
118        assert (count >= 1);
119        if (LLVM_LIKELY(count == 1)) {
120            priorValue->removeUser(this);
121        }
122    }
123    mOperand[index] = value;
124    value->addUser(this);
125}
126
127void Statement::insertBefore(Statement * const statement) {
128    if (LLVM_UNLIKELY(statement == this)) {
129        return;
130    }
131    else if (LLVM_UNLIKELY(statement == nullptr)) {
132        throw std::runtime_error("Cannot insert before Null statement!");
133    }
134    else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
135        throw std::runtime_error("Cannot insert before before statement in Null AST!");
136    }
137    removeFromParent();
138    mParent = statement->mParent;
139    if (LLVM_UNLIKELY(mParent->mFirst == statement)) {
140        mParent->mFirst = this;
141    }
142    mNext = statement;
143    mPrev = statement->mPrev;
144    statement->mPrev = this;
145    if (LLVM_LIKELY(mPrev != nullptr)) {
146        mPrev->mNext = this;
147    }
148    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
149        PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
150        mParent->addUser(&body);
151    }
152}
153
154void Statement::insertAfter(Statement * const statement) {
155    if (LLVM_UNLIKELY(statement == this)) {
156        return;
157    }
158    else if (LLVM_UNLIKELY(statement == nullptr)) {
159        throw std::runtime_error("Cannot insert before Null statement!");
160    }
161    else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
162        throw std::runtime_error("Cannot insert before before statement in Null AST!");
163    }
164    removeFromParent();
165    mParent = statement->mParent;
166    if (LLVM_UNLIKELY(mParent->mLast == statement)) {
167        mParent->mLast = this;
168    }
169    mPrev = statement;
170    mNext = statement->mNext;
171    statement->mNext = this;
172    if (LLVM_LIKELY(mNext != nullptr)) {
173        mNext->mPrev = this;
174    }
175    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
176        PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
177        mParent->addUser(&body);
178    }
179}
180
181Statement * Statement::removeFromParent() {
182    Statement * next = mNext;
183    if (LLVM_LIKELY(mParent != nullptr)) {
184        if (LLVM_UNLIKELY(mParent->mFirst == this)) {
185            mParent->mFirst = mNext;
186        }
187        if (LLVM_UNLIKELY(mParent->mLast == this)) {
188            mParent->mLast = mPrev;
189        }
190        if (LLVM_UNLIKELY(mParent->mInsertionPoint == this)) {
191            mParent->mInsertionPoint = mPrev;
192        }
193        if (LLVM_LIKELY(mPrev != nullptr)) {
194            mPrev->mNext = mNext;
195        }
196        if (LLVM_LIKELY(mNext != nullptr)) {
197            mNext->mPrev = mPrev;
198        }
199        if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
200            PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
201            mParent->removeUser(&body);
202        }
203    }
204    mPrev = nullptr;
205    mNext = nullptr;
206    mParent = nullptr;
207    return next;
208}
209
210Statement * Statement::eraseFromParent(const bool recursively) {
211    // remove this statement from its operands' users list
212    for (auto i = 0; i != mOperands; ++i) {
213        mOperand[i]->removeUser(this);
214    }
215    // If this is an If or While statement, we'll have to remove the statements within the
216    // body or we'll lose track of them.
217    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
218        if (isa<If>(this)) {
219            // Eliminate the relationship between the If node and its defined vars ...
220            for (PabloAST * var : cast<If>(this)->getDefined()) {
221                var->removeUser(this);
222                this->removeUser(var);
223                var->replaceAllUsesWith(mParent->createZeroes());
224            }
225        }
226        PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
227        Statement * stmt = body.front();
228        while (stmt) {
229            stmt = stmt->eraseFromParent(recursively);
230        }       
231    }
232
233    if (recursively) {
234        for (auto i = 0; i != mOperands; ++i) {
235            PabloAST * const op = mOperand[i];
236            if (op->getNumUses() == 0 && isa<Statement>(op)) {
237                cast<Statement>(op)->eraseFromParent(true);
238            }
239        }
240    }
241    return removeFromParent();
242}
243
244Statement * Statement::replaceWith(PabloAST * const expr, const bool rename, const bool recursively) {
245    assert (expr);
246    if (LLVM_UNLIKELY(expr == this)) {
247        return getNextNode();
248    }
249    if (LLVM_LIKELY(rename && isa<Statement>(expr))) {
250        Statement * const stmt = cast<Statement>(expr);
251        if (getName()->isUserDefined() && stmt->getName()->isGenerated()) {
252            stmt->setName(getName());
253        }
254    }
255    replaceAllUsesWith(expr);   
256    return eraseFromParent(recursively);
257}
258
259#ifndef NDEBUG
260bool Statement::noRecursiveOperand(const PabloAST * const operand) {
261    if (operand && isa<Statement>(operand)) {
262        std::queue<const Statement *> Q;
263        Q.push(cast<Statement>(operand));
264        while (!Q.empty()) {
265            const Statement * stmt = Q.front();
266            if (stmt == this) {
267                return false;
268            }
269            Q.pop();
270            for (auto i = 0; i != stmt->getNumOperands(); ++i) {
271                const PabloAST * op = stmt->getOperand(i);
272                if (isa<Statement>(op)) {
273                    Q.push(cast<Statement>(op));
274                }
275            }
276        }
277    }
278    return true;
279}
280#endif
281
282StatementList::~StatementList() {
283
284}
285
286}
Note: See TracBrowser for help on using the repository browser.