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

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

Progress on multi-target UCD compiler.

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