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
RevLine 
[4244]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
[4419]7#include <pablo/pabloAST.h>
[4404]8#include <pablo/codegenstate.h>
[4276]9#include <llvm/Support/Compiler.h>
[4650]10#include <pablo/printer_pablos.h>
[4510]11#ifndef NDEBUG
12#include <queue>
[4722]13#include <unordered_set>
[4510]14#endif
[4722]15
[4244]16namespace pablo {
17
[4272]18PabloAST::Allocator PabloAST::mAllocator;
[4510]19PabloAST::VectorAllocator PabloAST::mVectorAllocator;
[4272]20
[4244]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) {
[4276]30    assert (expr1 && expr2);
[4797]31    if (expr1 == expr2) {
32        return true;
33    } else if (expr1->getClassTypeId() == expr2->getClassTypeId()) {
[4510]34        if ((isa<Zeroes>(expr1)) || (isa<Ones>(expr1))) {
[4247]35            return true;
[4797]36        } else if (const Var * var1 = dyn_cast<const Var>(expr1)) {
[4244]37            if (const Var * var2 = cast<const Var>(expr2)) {
38                return (var1->getName() == var2->getName());
39            }
[4797]40        } else if (const Not* not1 = dyn_cast<const Not>(expr1)) {
[4244]41            if (const Not* not2 = cast<const Not>(expr2)) {
42                return equals(not1->getExpr(), not2->getExpr());
43            }
[4797]44        } else if (const And* and1 = dyn_cast<const And>(expr1)) {
[4244]45            if (const And* and2 = cast<const And>(expr2)) {
46                if (equals(and1->getExpr1(), and2->getExpr1())) {
47                    return equals(and1->getExpr2(), and2->getExpr2());
[4797]48                } else if (equals(and1->getExpr1(), and2->getExpr2())) {
[4244]49                    return equals(and1->getExpr2(), and2->getExpr1());
50                }
51            }
[4797]52        } else if (const Or * or1 = dyn_cast<const Or>(expr1)) {
[4244]53            if (const Or* or2 = cast<const Or>(expr2)) {
54                if (equals(or1->getExpr1(), or2->getExpr1())) {
55                    return equals(or1->getExpr2(), or2->getExpr2());
[4797]56                } else if (equals(or1->getExpr1(), or2->getExpr2())) {
[4244]57                    return equals(or1->getExpr2(), or2->getExpr1());
58                }
59            }
[4797]60        } else if (const Xor * xor1 = dyn_cast<const Xor>(expr1)) {
[4244]61            if (const Xor * xor2 = cast<const Xor>(expr2)) {
62                if (equals(xor1->getExpr1(), xor2->getExpr1())) {
63                    return equals(xor1->getExpr2(), xor2->getExpr2());
[4797]64                } else if (equals(xor1->getExpr1(), xor2->getExpr2())) {
[4244]65                    return equals(xor1->getExpr2(), xor2->getExpr1());
66                }
67            }
[4797]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;
[4805]71        } else { // Non-reassociatable functions (i.e., Sel, Advance, ScanThru, MatchStar, Assign, Next)
[4797]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;
[4244]78                }
79            }
[4797]80            return true;
[4244]81        }
82    }
83    return false;
84}
85
[4510]86void PabloAST::replaceAllUsesWith(PabloAST * expr) {   
87    Statement * user[mUsers.size()];
[4656]88    Vector::size_type users = 0;
[4510]89    for (PabloAST * u : mUsers) {
[4711]90        if (isa<Statement>(u) && u != expr) {
[4510]91            user[users++] = cast<Statement>(u);
[4416]92        }
93    }
[4510]94    mUsers.clear();
95    assert (expr);
[4750]96    for (Vector::size_type i = 0; i != users; ++i) {
[4510]97        user[i]->replaceUsesOfWith(this, expr);
98    }
[4416]99}
100
[4432]101void Statement::setOperand(const unsigned index, PabloAST * const value) {
[4585]102    assert (value);
[4415]103    assert (index < getNumOperands());
[4510]104    assert (noRecursiveOperand(value));
[4722]105    PabloAST * const priorValue = getOperand(index);
106    if (LLVM_UNLIKELY(priorValue == value)) {
[4416]107        return;
[4722]108    }   
[4657]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        }
[4416]121    }
122    mOperand[index] = value;
123    value->addUser(this);
[4415]124}
[4404]125
126void Statement::insertBefore(Statement * const statement) {
[4650]127    if (LLVM_UNLIKELY(statement == this)) {
128        return;
129    }
130    else if (LLVM_UNLIKELY(statement == nullptr)) {
[4723]131        throw std::runtime_error("cannot insert before null statement!");
[4650]132    }
133    else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
[4723]134        throw std::runtime_error("statement is not contained in a pablo block!");
[4650]135    }
[4404]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    }
[4611]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    }
[4404]151}
152
153void Statement::insertAfter(Statement * const statement) {
[4650]154    if (LLVM_UNLIKELY(statement == this)) {
155        return;
156    }
157    else if (LLVM_UNLIKELY(statement == nullptr)) {
[4723]158        throw std::runtime_error("cannot insert after null statement!");
[4650]159    }
160    else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
[4723]161        throw std::runtime_error("statement is not contained in a pablo block!");
[4650]162    }
[4404]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    }
[4611]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    }
[4404]178}
179
[4416]180Statement * Statement::removeFromParent() {
181    Statement * next = mNext;
[4404]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        }
[4650]189        if (LLVM_UNLIKELY(mParent->mInsertionPoint == this)) {
190            mParent->mInsertionPoint = mPrev;
[4415]191        }
[4404]192        if (LLVM_LIKELY(mPrev != nullptr)) {
193            mPrev->mNext = mNext;
194        }
195        if (LLVM_LIKELY(mNext != nullptr)) {
196            mNext->mPrev = mPrev;
197        }
[4611]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        }
[4592]202    }
[4404]203    mPrev = nullptr;
204    mNext = nullptr;
205    mParent = nullptr;
[4416]206    return next;
[4404]207}
208
[4416]209Statement * Statement::eraseFromParent(const bool recursively) {
210    // remove this statement from its operands' users list
[4750]211    for (unsigned i = 0; i != mOperands; ++i) {
[4592]212        mOperand[i]->removeUser(this);
[4416]213    }
[4829]214    Statement * redundantBranch = nullptr;
[4594]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();
[4829]220        // Note: by erasing the body, any Assign/Next nodes will be replaced with Zero.
[4594]221        while (stmt) {
222            stmt = stmt->eraseFromParent(recursively);
[4788]223        }
224    } else if (LLVM_UNLIKELY(isa<Assign>(this))) {
225        for (PabloAST * use : mUsers) {
226            if (If * ifNode = dyn_cast<If>(use)) {
[4829]227                auto & defs = ifNode->getDefined();
228                auto f = std::find(defs.begin(), defs.end(), this);
229                if (LLVM_LIKELY(f != defs.end())) {
[4788]230                    this->removeUser(ifNode);
231                    ifNode->removeUser(this);
[4829]232                    defs.erase(f);
233                    if (LLVM_UNLIKELY(defs.empty())) {
234                        redundantBranch = ifNode;
235                    }
[4788]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)) {
[4829]243                auto & vars = whileNode->getVariants();
244                auto f = std::find(vars.begin(), vars.end(), this);
245                if (LLVM_LIKELY(f != vars.end())) {
[4788]246                    this->removeUser(whileNode);
247                    whileNode->removeUser(this);
[4829]248                    vars.erase(f);
249                    if (LLVM_UNLIKELY(vars.empty())) {
250                        redundantBranch = whileNode;
251                    }
[4788]252                    break;
253                }
254            }
255        }
[4594]256    }
257
[4788]258    replaceAllUsesWith(PabloBlock::createZeroes());
259
[4419]260    if (recursively) {
[4750]261        for (unsigned i = 0; i != mOperands; ++i) {
[4432]262            PabloAST * const op = mOperand[i];
[4829]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                }
[4419]273            }
[4415]274        }
[4829]275        if (LLVM_UNLIKELY(redundantBranch != nullptr)) {
276            redundantBranch->eraseFromParent(true);
277        }
[4404]278    }
[4788]279
[4419]280    return removeFromParent();
281}
[4280]282
[4586]283Statement * Statement::replaceWith(PabloAST * const expr, const bool rename, const bool recursively) {
[4433]284    assert (expr);
[4419]285    if (LLVM_UNLIKELY(expr == this)) {
286        return getNextNode();
[4416]287    }
[4433]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    }
[4592]294    replaceAllUsesWith(expr);   
[4586]295    return eraseFromParent(recursively);
[4415]296}
297
[4510]298#ifndef NDEBUG
[4611]299bool Statement::noRecursiveOperand(const PabloAST * const operand) {
[4722]300    if (const Statement * stmt = dyn_cast<Statement>(operand)) {
[4611]301        std::queue<const Statement *> Q;
[4722]302        std::unordered_set<const PabloAST *> V;
303        V.insert(stmt);
304        for (;;) {
[4611]305            if (stmt == this) {
306                return false;
307            }
[4722]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) {
[4611]311                    Q.push(cast<Statement>(op));
[4722]312                    V.insert(op);
[4510]313                }
314            }
[4722]315            if (LLVM_UNLIKELY(Q.empty())) {
316                break;
317            }
318            stmt = Q.front();
319            Q.pop();
[4510]320        }
321    }
[4611]322    return true;
323}
[4510]324#endif
325
[4775]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
[4432]335StatementList::~StatementList() {
336
[4276]337}
[4432]338
[4774]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;
[4432]359}
[4774]360
361}
Note: See TracBrowser for help on using the repository browser.