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

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

Misc changes + potential SIGBUS fix for issue reported by Hongpu.

File size: 11.4 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 (Vector::size_type 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("statement is not contained in a pablo block!");
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 after null statement!");
161    }
162    else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
163        throw std::runtime_error("statement is not contained in a pablo block!");
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 (unsigned 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        PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
220        Statement * stmt = body.front();
221        while (stmt) {
222            stmt = stmt->eraseFromParent(recursively);
223        }
224    } else if (LLVM_UNLIKELY(isa<Assign>(this))) {
225        for (PabloAST * use : mUsers) {
226            if (If * ifNode = dyn_cast<If>(use)) {
227                const auto & defs = ifNode->getDefined();
228                if (LLVM_LIKELY(std::find(defs.begin(), defs.end(), this) != defs.end())) {
229                    this->removeUser(ifNode);
230                    ifNode->removeUser(this);
231                    break;
232                }
233            }
234        }
235    } else if (LLVM_UNLIKELY(isa<Next>(this))) {
236        for (PabloAST * use : mUsers) {
237            if (While * whileNode = dyn_cast<While>(use)) {
238                const auto & vars = whileNode->getVariants();
239                if (LLVM_LIKELY(std::find(vars.begin(), vars.end(), this) != vars.end())) {
240                    this->removeUser(whileNode);
241                    whileNode->removeUser(this);
242                    break;
243                }
244            }
245        }
246    }
247
248    replaceAllUsesWith(PabloBlock::createZeroes());
249
250    if (recursively) {
251        for (unsigned i = 0; i != mOperands; ++i) {
252            PabloAST * const op = mOperand[i];
253            if (op->getNumUses() == 0 && isa<Statement>(op)) {
254                cast<Statement>(op)->eraseFromParent(true);
255            }
256        }
257    }
258
259    return removeFromParent();
260}
261
262Statement * Statement::replaceWith(PabloAST * const expr, const bool rename, const bool recursively) {
263    assert (expr);
264    if (LLVM_UNLIKELY(expr == this)) {
265        return getNextNode();
266    }
267    if (LLVM_LIKELY(rename && isa<Statement>(expr))) {
268        Statement * const stmt = cast<Statement>(expr);
269        if (getName()->isUserDefined() && stmt->getName()->isGenerated()) {
270            stmt->setName(getName());
271        }
272    }
273    replaceAllUsesWith(expr);   
274    return eraseFromParent(recursively);
275}
276
277#ifndef NDEBUG
278bool Statement::noRecursiveOperand(const PabloAST * const operand) {
279    if (const Statement * stmt = dyn_cast<Statement>(operand)) {
280        std::queue<const Statement *> Q;
281        std::unordered_set<const PabloAST *> V;
282        V.insert(stmt);
283        for (;;) {
284            if (stmt == this) {
285                return false;
286            }
287            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
288                const PabloAST * op = stmt->getOperand(i);               
289                if (isa<Statement>(op) && V.count(op) == 0) {
290                    Q.push(cast<Statement>(op));
291                    V.insert(op);
292                }
293            }
294            if (LLVM_UNLIKELY(Q.empty())) {
295                break;
296            }
297            stmt = Q.front();
298            Q.pop();
299        }
300    }
301    return true;
302}
303#endif
304
305bool StatementList::contains(Statement * const statement) {
306    for (Statement * stmt : *this) {
307        if (statement == stmt) {
308            return true;
309        }
310    }
311    return false;
312}
313
314StatementList::~StatementList() {
315
316}
317
318/** ------------------------------------------------------------------------------------------------------------- *
319 * @brief escapes
320 *
321 * Is this statement used outside of its scope?
322 ** ------------------------------------------------------------------------------------------------------------- */
323bool escapes(const Statement * statement) {
324    const PabloBlock * const parent = statement->getParent();
325    for (const PabloAST * user : statement->users()) {
326        if (LLVM_LIKELY(isa<Statement>(user))) {
327            const PabloBlock * used = cast<Statement>(user)->getParent();
328            while (used != parent) {
329                used = used->getParent();
330                if (used == nullptr) {
331                    assert (isa<Assign>(statement) || isa<Next>(statement));
332                    return true;
333                }
334            }
335        }
336    }
337    return false;
338}
339
340}
Note: See TracBrowser for help on using the repository browser.