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

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

Back-up check in

File size: 12.6 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 == expr2) {
32        return true;
33    } else if (expr1->getClassTypeId() == expr2->getClassTypeId()) {
34        if ((isa<Zeroes>(expr1)) || (isa<Ones>(expr1))) {
35            return true;
36        } else if (const Var * var1 = dyn_cast<const Var>(expr1)) {
37            if (const Var * var2 = cast<const Var>(expr2)) {
38                return (var1->getName() == var2->getName());
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        } 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                } else if (equals(and1->getExpr1(), and2->getExpr2())) {
49                    return equals(and1->getExpr2(), and2->getExpr1());
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                } else if (equals(or1->getExpr1(), or2->getExpr2())) {
57                    return equals(or1->getExpr2(), or2->getExpr1());
58                }
59            }
60        } else if (const Xor * xor1 = dyn_cast<const Xor>(expr1)) {
61            if (const Xor * xor2 = cast<const Xor>(expr2)) {
62                if (equals(xor1->getExpr1(), xor2->getExpr1())) {
63                    return equals(xor1->getExpr2(), xor2->getExpr2());
64                } else if (equals(xor1->getExpr1(), xor2->getExpr2())) {
65                    return equals(xor1->getExpr2(), xor2->getExpr1());
66                }
67            }
68        } else if (isa<Integer>(expr1) || isa<String>(expr1) || isa<Call>(expr1)) {
69            // If these weren't equivalent by address they won't be equivalent by their operands.
70            return false;
71        } else { // Non-reassociatable functions (i.e., Sel, Advance, ScanThru, MatchStar, Assign, Next)
72            const Statement * stmt1 = cast<Statement>(expr1);
73            const Statement * stmt2 = cast<Statement>(expr2);
74            assert (stmt1->getNumOperands() == stmt2->getNumOperands());
75            for (unsigned i = 0; i != stmt1->getNumOperands(); ++i) {
76                if (!equals(stmt1->getOperand(i), stmt2->getOperand(i))) {
77                    return false;
78                }
79            }
80            return true;
81        }
82    }
83    return false;
84}
85
86void PabloAST::replaceAllUsesWith(PabloAST * expr) {   
87    Statement * user[mUsers.size()];
88    Vector::size_type users = 0;
89    for (PabloAST * u : mUsers) {
90        if (isa<Statement>(u) && u != expr) {
91            user[users++] = cast<Statement>(u);
92        }
93    }
94    mUsers.clear();
95    assert (expr);
96    for (Vector::size_type i = 0; i != users; ++i) {
97        user[i]->replaceUsesOfWith(this, expr);
98    }
99}
100
101void Statement::setOperand(const unsigned index, PabloAST * const value) {
102    assert (value);
103    assert (index < getNumOperands());
104    assert (noRecursiveOperand(value));
105    PabloAST * const priorValue = getOperand(index);
106    if (LLVM_UNLIKELY(priorValue == value)) {
107        return;
108    }   
109    if (LLVM_LIKELY(priorValue != nullptr)) {
110        // Test just to be sure that we don't have multiple operands pointing to
111        // what we're replacing. If not, remove this from the prior value's
112        // user list.
113        unsigned count = 0;
114        for (unsigned i = 0; i != getNumOperands(); ++i) {
115            count += (getOperand(i) == priorValue) ? 1 : 0;
116        }
117        assert (count >= 1);
118        if (LLVM_LIKELY(count == 1)) {
119            priorValue->removeUser(this);
120        }
121    }
122    mOperand[index] = value;
123    value->addUser(this);
124}
125
126void Statement::insertBefore(Statement * const statement) {
127    if (LLVM_UNLIKELY(statement == this)) {
128        return;
129    }
130    else if (LLVM_UNLIKELY(statement == nullptr)) {
131        throw std::runtime_error("cannot insert before null statement!");
132    }
133    else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
134        throw std::runtime_error("statement is not contained in a pablo block!");
135    }
136    removeFromParent();
137    mParent = statement->mParent;
138    if (LLVM_UNLIKELY(mParent->mFirst == statement)) {
139        mParent->mFirst = this;
140    }
141    mNext = statement;
142    mPrev = statement->mPrev;
143    statement->mPrev = this;
144    if (LLVM_LIKELY(mPrev != nullptr)) {
145        mPrev->mNext = this;
146    }
147    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
148        PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
149        mParent->addUser(&body);
150    }
151}
152
153void Statement::insertAfter(Statement * const statement) {
154    if (LLVM_UNLIKELY(statement == this)) {
155        return;
156    }
157    else if (LLVM_UNLIKELY(statement == nullptr)) {
158        throw std::runtime_error("cannot insert after null statement!");
159    }
160    else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
161        throw std::runtime_error("statement is not contained in a pablo block!");
162    }
163    removeFromParent();
164    mParent = statement->mParent;
165    if (LLVM_UNLIKELY(mParent->mLast == statement)) {
166        mParent->mLast = this;
167    }
168    mPrev = statement;
169    mNext = statement->mNext;
170    statement->mNext = this;
171    if (LLVM_LIKELY(mNext != nullptr)) {
172        mNext->mPrev = this;
173    }
174    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
175        PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
176        mParent->addUser(&body);
177    }
178}
179
180Statement * Statement::removeFromParent() {
181    Statement * next = mNext;
182    if (LLVM_LIKELY(mParent != nullptr)) {
183        if (LLVM_UNLIKELY(mParent->mFirst == this)) {
184            mParent->mFirst = mNext;
185        }
186        if (LLVM_UNLIKELY(mParent->mLast == this)) {
187            mParent->mLast = mPrev;
188        }
189        if (LLVM_UNLIKELY(mParent->mInsertionPoint == this)) {
190            mParent->mInsertionPoint = mPrev;
191        }
192        if (LLVM_LIKELY(mPrev != nullptr)) {
193            mPrev->mNext = mNext;
194        }
195        if (LLVM_LIKELY(mNext != nullptr)) {
196            mNext->mPrev = mPrev;
197        }
198        if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
199            PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
200            mParent->removeUser(&body);
201        }
202    }
203    mPrev = nullptr;
204    mNext = nullptr;
205    mParent = nullptr;
206    return next;
207}
208
209Statement * Statement::eraseFromParent(const bool recursively) {
210    // remove this statement from its operands' users list
211    for (unsigned i = 0; i != mOperands; ++i) {
212        mOperand[i]->removeUser(this);
213    }
214    Statement * redundantBranch = nullptr;
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        PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
219        Statement * stmt = body.front();
220        // Note: by erasing the body, any Assign/Next nodes will be replaced with Zero.
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                auto & defs = ifNode->getDefined();
228                auto f = std::find(defs.begin(), defs.end(), this);
229                if (LLVM_LIKELY(f != defs.end())) {
230                    this->removeUser(ifNode);
231                    ifNode->removeUser(this);
232                    defs.erase(f);
233                    if (LLVM_UNLIKELY(defs.empty())) {
234                        redundantBranch = ifNode;
235                    }
236                    break;
237                }
238            }
239        }
240    } else if (LLVM_UNLIKELY(isa<Next>(this))) {
241        for (PabloAST * use : mUsers) {
242            if (While * whileNode = dyn_cast<While>(use)) {
243                auto & vars = whileNode->getVariants();
244                auto f = std::find(vars.begin(), vars.end(), this);
245                if (LLVM_LIKELY(f != vars.end())) {
246                    this->removeUser(whileNode);
247                    whileNode->removeUser(this);
248                    vars.erase(f);
249                    if (LLVM_UNLIKELY(vars.empty())) {
250                        redundantBranch = whileNode;
251                    }
252                    break;
253                }
254            }
255        }
256    }
257
258    replaceAllUsesWith(PabloBlock::createZeroes());
259
260    if (recursively) {
261        for (unsigned i = 0; i != mOperands; ++i) {
262            PabloAST * const op = mOperand[i];
263            if (LLVM_LIKELY(isa<Statement>(op))) {
264                bool erase = false;
265                if (op->getNumUses() == 0) {
266                    erase = true;
267                } else if ((isa<Assign>(op) || isa<Next>(op)) && op->getNumUses() == 1) {
268                    erase = true;
269                }
270                if (erase) {
271                    cast<Statement>(op)->eraseFromParent(true);
272                }
273            }
274        }
275        if (LLVM_UNLIKELY(redundantBranch != nullptr)) {
276            redundantBranch->eraseFromParent(true);
277        }
278    }
279
280    return removeFromParent();
281}
282
283Statement * Statement::replaceWith(PabloAST * const expr, const bool rename, const bool recursively) {
284    assert (expr);
285    if (LLVM_UNLIKELY(expr == this)) {
286        return getNextNode();
287    }
288    if (LLVM_LIKELY(rename && isa<Statement>(expr))) {
289        Statement * const stmt = cast<Statement>(expr);
290        if (getName()->isUserDefined() && stmt->getName()->isGenerated()) {
291            stmt->setName(getName());
292        }
293    }
294    replaceAllUsesWith(expr);   
295    return eraseFromParent(recursively);
296}
297
298#ifndef NDEBUG
299bool Statement::noRecursiveOperand(const PabloAST * const operand) {
300    if (const Statement * stmt = dyn_cast<Statement>(operand)) {
301        std::queue<const Statement *> Q;
302        std::unordered_set<const PabloAST *> V;
303        V.insert(stmt);
304        for (;;) {
305            if (stmt == this) {
306                return false;
307            }
308            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
309                const PabloAST * op = stmt->getOperand(i);               
310                if (isa<Statement>(op) && V.count(op) == 0) {
311                    Q.push(cast<Statement>(op));
312                    V.insert(op);
313                }
314            }
315            if (LLVM_UNLIKELY(Q.empty())) {
316                break;
317            }
318            stmt = Q.front();
319            Q.pop();
320        }
321    }
322    return true;
323}
324#endif
325
326bool StatementList::contains(Statement * const statement) {
327    for (Statement * stmt : *this) {
328        if (statement == stmt) {
329            return true;
330        }
331    }
332    return false;
333}
334
335StatementList::~StatementList() {
336
337}
338
339/** ------------------------------------------------------------------------------------------------------------- *
340 * @brief escapes
341 *
342 * Is this statement used outside of its scope?
343 ** ------------------------------------------------------------------------------------------------------------- */
344bool escapes(const Statement * statement) {
345    const PabloBlock * const parent = statement->getParent();
346    for (const PabloAST * user : statement->users()) {
347        if (LLVM_LIKELY(isa<Statement>(user))) {
348            const PabloBlock * used = cast<Statement>(user)->getParent();
349            while (used != parent) {
350                used = used->getParent();
351                if (used == nullptr) {
352                    assert (isa<Assign>(statement) || isa<Next>(statement));
353                    return true;
354                }
355            }
356        }
357    }
358    return false;
359}
360
361}
Note: See TracBrowser for help on using the repository browser.