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

Last change on this file since 4416 was 4416, checked in by nmedfort, 5 years ago

Many use def info changes; removed dependency on boost system library. More work still needed on CSE.

File size: 8.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 "pabloAST.h"
8#include "pe_advance.h"
9#include "pe_and.h"
10#include "pe_call.h"
11#include "pe_matchstar.h"
12#include "pe_not.h"
13#include "pe_or.h"
14#include "pabloAST.h"
15#include "pe_scanthru.h"
16#include "pe_sel.h"
17#include "pe_var.h"
18#include "pe_xor.h"
19#include "pe_zeroes.h"
20#include "pe_ones.h"
21#include <pablo/codegenstate.h>
22#include <llvm/Support/Compiler.h>
23
24namespace pablo {
25
26PabloAST::Allocator PabloAST::mAllocator;
27
28/*
29
30    Return true if expr1 and expr2 can be proven equivalent according to some rules,
31    false otherwise.  Note that false may be returned i some cases when the exprs are
32    equivalent.
33
34*/
35
36bool equals(const PabloAST * expr1, const PabloAST * expr2) {
37    assert (expr1 && expr2);
38    if (expr1->getClassTypeId() == expr2->getClassTypeId()) {
39        if ((isa<const Zeroes>(expr1)) || (isa<const Ones>(expr1))) {
40            return true;
41        }
42        else if (const Var * var1 = dyn_cast<const Var>(expr1)) {
43            if (const Var * var2 = cast<const Var>(expr2)) {
44                return (var1->getName() == var2->getName());
45            }
46        }
47        else if (const Not* not1 = dyn_cast<const Not>(expr1)) {
48            if (const Not* not2 = cast<const Not>(expr2)) {
49                return equals(not1->getExpr(), not2->getExpr());
50            }
51        }
52        else if (const And* and1 = dyn_cast<const And>(expr1)) {
53            if (const And* and2 = cast<const And>(expr2)) {
54                if (equals(and1->getExpr1(), and2->getExpr1())) {
55                    return equals(and1->getExpr2(), and2->getExpr2());
56                }
57                else if (equals(and1->getExpr1(), and2->getExpr2())) {
58                    return equals(and1->getExpr2(), and2->getExpr1());
59                }
60            }
61        }
62        else if (const Or * or1 = dyn_cast<const Or>(expr1)) {
63            if (const Or* or2 = cast<const Or>(expr2)) {
64                if (equals(or1->getExpr1(), or2->getExpr1())) {
65                    return equals(or1->getExpr2(), or2->getExpr2());
66                }
67                else if (equals(or1->getExpr1(), or2->getExpr2())) {
68                    return equals(or1->getExpr2(), or2->getExpr1());
69                }
70            }
71        }
72        else if (const Xor * xor1 = dyn_cast<const Xor>(expr1)) {
73            if (const Xor * xor2 = cast<const Xor>(expr2)) {
74                if (equals(xor1->getExpr1(), xor2->getExpr1())) {
75                    return equals(xor1->getExpr2(), xor2->getExpr2());
76                }
77                else if (equals(xor1->getExpr1(), xor2->getExpr2())) {
78                    return equals(xor1->getExpr2(), xor2->getExpr1());
79                }
80            }
81        }
82        else if (const Sel* sel1 = dyn_cast<const Sel>(expr1)) {
83            if (const Sel* sel2 = cast<const Sel>(expr2)) {
84                if (equals(sel1->getCondition(), sel2->getCondition())) {
85                    if (equals(sel1->getTrueExpr(), sel2->getTrueExpr())) {
86                        return equals(sel1->getFalseExpr(), sel2->getFalseExpr());
87                    }
88                }
89            }
90        }
91    }
92    return false;
93}
94
95void PabloAST::setMetadata(const std::string & name, PMDNode * node) {
96    if (LLVM_UNLIKELY(mMetadataMap == nullptr)) {
97        mMetadataMap = new PMDNodeMap();
98    }
99    mMetadataMap->insert(std::make_pair(name, node));
100}
101
102PMDNode * PabloAST::getMetadata(const std::string & name) {
103    if (LLVM_UNLIKELY(mMetadataMap == nullptr)) {
104        return nullptr;
105    }
106    auto f = mMetadataMap->find(name);
107    if (f == mMetadataMap->end()) {
108        return nullptr;
109    }
110    return f->second;
111}
112
113void PabloAST::replaceAllUsesWith(PabloAST * expr) {
114    #ifndef NDEBUG
115    unsigned __userCount = getNumUses();
116    #endif
117    while (!mUsers.empty()) {
118        PabloAST * user = mUsers.pop_back_val();
119        assert(--__userCount == getNumUses());
120        if (isa<Statement>(user)) {
121            cast<Statement>(user)->replaceUsesOfWith(this, expr);
122        }
123        assert(__userCount == getNumUses());
124    }
125    assert (getNumUses() == 0);
126}
127
128void Statement::setOperand(const unsigned index, PabloAST * value) {
129    assert (index < getNumOperands());
130    if (LLVM_UNLIKELY(mOperand[index] == value)) {
131        return;
132    }
133    PabloAST * priorValue = mOperand[index];
134    // Test just to be sure we don't have multiple operands pointing to
135    // what we're replacing. If not, remove this from the prior value's
136    // user list.
137    unsigned count = 0;
138    for (unsigned i = 0; i != getNumOperands(); ++i) {
139        count += (mOperand[index] == priorValue) ? 1 : 0;
140    }
141    assert (count >= 1);
142    if (LLVM_LIKELY(count == 1)) {
143        priorValue->removeUser(this);
144    }
145    mOperand[index] = value;
146    value->addUser(this);
147}
148
149void Statement::insertBefore(Statement * const statement) {
150    assert (statement);
151    assert (statement != this);
152    assert (statement->mParent);
153    removeFromParent();
154    mParent = statement->mParent;
155    if (LLVM_UNLIKELY(mParent->mFirst == statement)) {
156        mParent->mFirst = this;
157    }
158    mNext = statement;
159    mPrev = statement->mPrev;
160    statement->mPrev = this;
161    if (LLVM_LIKELY(mPrev != nullptr)) {
162        mPrev->mNext = this;
163    }
164}
165
166void Statement::insertAfter(Statement * const statement) {
167    assert (statement);
168    assert (statement != this);
169    assert (statement->mParent);
170    removeFromParent();
171    mParent = statement->mParent;
172    if (LLVM_UNLIKELY(mParent->mLast == statement)) {
173        mParent->mLast = this;
174    }
175    mPrev = statement;
176    mNext = statement->mNext;
177    statement->mNext = this;
178    if (LLVM_LIKELY(mNext != nullptr)) {
179        mNext->mPrev = this;
180    }
181}
182
183Statement * Statement::removeFromParent() {
184    Statement * next = mNext;
185    if (LLVM_LIKELY(mParent != nullptr)) {
186        if (LLVM_UNLIKELY(mParent->mFirst == this)) {
187            mParent->mFirst = mNext;
188        }
189        if (LLVM_UNLIKELY(mParent->mLast == this)) {
190            mParent->mLast = mPrev;
191        }
192        if (mParent->mInsertionPoint == this) {
193            mParent->mInsertionPoint = mParent->mInsertionPoint->mPrev;
194        }
195        if (LLVM_LIKELY(mPrev != nullptr)) {
196            mPrev->mNext = mNext;
197        }
198        if (LLVM_LIKELY(mNext != nullptr)) {
199            mNext->mPrev = mPrev;
200        }
201    }   
202    mPrev = nullptr;
203    mNext = nullptr;
204    mParent = nullptr;
205    return next;
206}
207
208Statement * Statement::eraseFromParent(const bool recursively) {
209    Statement * next = removeFromParent();
210    // remove this statement from its operands' users list
211    for (PabloAST * op : mOperand) {
212        op->removeUser(this);
213        if (recursively && isa<Statement>(op) && op->getNumUses() == 0) {
214            cast<Statement>(op)->eraseFromParent();
215        }
216    }
217    return next;
218}
219
220void Statement::replaceWith(PabloAST * const expr) {
221
222    if (LLVM_UNLIKELY(expr == this)) {
223        return;
224    }
225
226    if (isa<Statement>(expr)) {
227        Statement * stmt = cast<Statement>(expr);
228        stmt->removeFromParent();
229        stmt->mParent = mParent;
230        stmt->mNext = mNext;
231        stmt->mPrev = mPrev;
232        if (LLVM_LIKELY(mPrev != nullptr)) {
233            mPrev->mNext = stmt;
234        }
235        if (LLVM_LIKELY(mNext != nullptr)) {
236            mNext->mPrev = stmt;
237        }
238        mParent=nullptr;
239        mNext=nullptr;
240        mPrev=nullptr;
241    }
242    else {
243        removeFromParent();
244    }
245
246    // remove this statement from its operands' users list
247    for (PabloAST * op : mOperand) {
248        op->removeUser(this);
249    }
250
251    while (!mUsers.empty()) {
252        PabloAST * user = mUsers.pop_back_val();
253        if (isa<Statement>(user)) {
254            assert(std::count(cast<Statement>(user)->mOperand.begin(), cast<Statement>(user)->mOperand.end(), this) == 1);
255            cast<Statement>(user)->replaceUsesOfWith(this, expr);
256        }
257    }
258
259}
260
261Statement::~Statement() {
262
263}
264
265void StatementList::insert(Statement * const statement) {
266    if (LLVM_UNLIKELY(mInsertionPoint == nullptr)) {
267        statement->mNext = mFirst;
268        if (mFirst) {
269            assert (mFirst->mPrev == nullptr);
270            mFirst->mPrev = statement;
271        }
272        mLast = (mLast == nullptr) ? statement : mLast;
273        mInsertionPoint = mFirst = statement;
274    }
275    else {
276        statement->insertAfter(mInsertionPoint);
277        mLast = (mLast == mInsertionPoint) ? statement : mLast;
278        mInsertionPoint = statement;
279    }
280}
281
282}
Note: See TracBrowser for help on using the repository browser.