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

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

Work on bug fixes for multiplexing pass.

File size: 17.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 <pablo/pabloAST.h>
8#include <pablo/codegenstate.h>
9#include <llvm/Support/Compiler.h>
10#include <pablo/printer_pablos.h>
11#include <iostream>
12
13namespace pablo {
14
15PabloAST::Allocator PabloAST::mAllocator;
16
17/*
18
19    Return true if expr1 and expr2 can be proven equivalent according to some rules,
20    false otherwise.  Note that false may be returned i some cases when the exprs are
21    equivalent.
22
23*/
24
25/** ------------------------------------------------------------------------------------------------------------- *
26 * @brief equals
27 ** ------------------------------------------------------------------------------------------------------------- */
28bool equals(const PabloAST * expr1, const PabloAST * expr2) {
29    assert (expr1 && expr2);
30    if (expr1 == expr2) {
31        return true;
32    } else if (expr1->getClassTypeId() == expr2->getClassTypeId()) {
33        if ((isa<Zeroes>(expr1)) || (isa<Ones>(expr1))) {
34            return true;
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        } else if (const Not* not1 = dyn_cast<const Not>(expr1)) {
40            if (const Not* not2 = cast<const Not>(expr2)) {
41                return equals(not1->getExpr(), not2->getExpr());
42            }
43        } else if (const And* and1 = dyn_cast<const And>(expr1)) {
44            if (const And* and2 = cast<const And>(expr2)) {
45                if (equals(and1->getExpr1(), and2->getExpr1())) {
46                    return equals(and1->getExpr2(), and2->getExpr2());
47                } else if (equals(and1->getExpr1(), and2->getExpr2())) {
48                    return equals(and1->getExpr2(), and2->getExpr1());
49                }
50            }
51        } else if (const Or * or1 = dyn_cast<const Or>(expr1)) {
52            if (const Or* or2 = cast<const Or>(expr2)) {
53                if (equals(or1->getExpr1(), or2->getExpr1())) {
54                    return equals(or1->getExpr2(), or2->getExpr2());
55                } else if (equals(or1->getExpr1(), or2->getExpr2())) {
56                    return equals(or1->getExpr2(), or2->getExpr1());
57                }
58            }
59        } else if (const Xor * xor1 = dyn_cast<const Xor>(expr1)) {
60            if (const Xor * xor2 = cast<const Xor>(expr2)) {
61                if (equals(xor1->getExpr1(), xor2->getExpr1())) {
62                    return equals(xor1->getExpr2(), xor2->getExpr2());
63                } else if (equals(xor1->getExpr1(), xor2->getExpr2())) {
64                    return equals(xor1->getExpr2(), xor2->getExpr1());
65                }
66            }
67        } else if (isa<Integer>(expr1) || isa<String>(expr1) || isa<Call>(expr1)) {
68            // If these weren't equivalent by address they won't be equivalent by their operands.
69            return false;
70        } else { // Non-reassociatable functions (i.e., Sel, Advance, ScanThru, MatchStar, Assign, Next)
71            const Statement * stmt1 = cast<Statement>(expr1);
72            const Statement * stmt2 = cast<Statement>(expr2);
73            assert (stmt1->getNumOperands() == stmt2->getNumOperands());
74            for (unsigned i = 0; i != stmt1->getNumOperands(); ++i) {
75                if (!equals(stmt1->getOperand(i), stmt2->getOperand(i))) {
76                    return false;
77                }
78            }
79            return true;
80        }
81    }
82    return false;
83}
84
85/** ------------------------------------------------------------------------------------------------------------- *
86 * @brief replaceAllUsesWith
87 ** ------------------------------------------------------------------------------------------------------------- */
88void PabloAST::replaceAllUsesWith(PabloAST * expr) {   
89    Statement * replacements[mUsers.size()];
90    Vector::size_type users = 0;
91    bool exprIsAUser = false;
92    assert (expr);
93    for (PabloAST * user : mUsers) {
94        if (LLVM_UNLIKELY(user == expr)) {
95            exprIsAUser = true;
96            continue;
97        }
98        replacements[users++] = cast<Statement>(user);
99    }
100    mUsers.clear();
101    if (LLVM_UNLIKELY(exprIsAUser)) {
102        mUsers.push_back(expr);
103    }
104    for (Vector::size_type i = 0; i != users; ++i) {
105        replacements[i]->replaceUsesOfWith(this, expr);
106    }
107}
108
109/** ------------------------------------------------------------------------------------------------------------- *
110 * @brief checkForReplacementInEscapedValueList
111 ** ------------------------------------------------------------------------------------------------------------- */
112template <class ValueType, class ValueList>
113inline void Statement::checkForReplacementInEscapedValueList(Statement * branch, PabloAST * const from, PabloAST * const to, ValueList & list) {
114    if (LLVM_LIKELY(isa<ValueType>(from))) {
115        auto f = std::find(list.begin(), list.end(), cast<ValueType>(from));
116        if (LLVM_LIKELY(f != list.end())) {
117            if (LLVM_LIKELY(isa<ValueType>(to))) {
118                if (std::find(list.begin(), list.end(), cast<ValueType>(to)) == list.end()) {
119                    *f = cast<ValueType>(to);
120                    branch->addUser(to);
121                } else {
122                    list.erase(f);
123                }
124                branch->removeUser(from);
125                assert (std::find(list.begin(), list.end(), cast<ValueType>(to)) != list.end());
126                assert (std::find(branch->user_begin(), branch->user_end(), cast<ValueType>(to)) != branch->user_end());
127            } else { // replacement error occured
128                std::string tmp;
129                raw_string_ostream str(tmp);
130                str << "cannot replace escaped value ";
131                PabloPrinter::print(from, str);
132                str << " with ";
133                PabloPrinter::print(to, str);
134                str << " in ";
135                PabloPrinter::print(branch, str);
136                throw std::runtime_error(str.str());
137            }
138        }               
139        assert (std::find(list.begin(), list.end(), cast<ValueType>(from)) == list.end());
140        assert (std::find(branch->user_begin(), branch->user_end(), cast<ValueType>(from)) == branch->user_end());
141    }
142}
143
144/** ------------------------------------------------------------------------------------------------------------- *
145 * @brief replaceUsesOfWith
146 ** ------------------------------------------------------------------------------------------------------------- */
147void Statement::replaceUsesOfWith(PabloAST * const from, PabloAST * const to) {
148    for (unsigned i = 0; i != getNumOperands(); ++i) {
149       if (getOperand(i) == from) {
150           setOperand(i, to);
151       }
152    }
153    if (LLVM_UNLIKELY(isa<If>(this))) {
154        checkForReplacementInEscapedValueList<Assign>(this, from, to, cast<If>(this)->getDefined());
155    } else if (LLVM_UNLIKELY(isa<While>(this))) {
156        checkForReplacementInEscapedValueList<Next>(this, from, to, cast<While>(this)->getVariants());
157    }
158}
159
160/** ------------------------------------------------------------------------------------------------------------- *
161 * @brief setOperand
162 ** ------------------------------------------------------------------------------------------------------------- */
163void Statement::setOperand(const unsigned index, PabloAST * const value) {
164    assert (value);
165    assert (index < getNumOperands());
166    PabloAST * const priorValue = getOperand(index);
167    if (LLVM_UNLIKELY(priorValue == value)) {
168        return;
169    }   
170    if (LLVM_LIKELY(priorValue != nullptr)) {
171        // Test just to be sure that we don't have multiple operands pointing to
172        // what we're replacing. If not, remove this from the prior value's
173        // user list.
174        unsigned count = 0;
175        for (unsigned i = 0; i != getNumOperands(); ++i) {
176            count += (getOperand(i) == priorValue) ? 1 : 0;
177        }
178        assert (count >= 1);
179        if (LLVM_LIKELY(count == 1)) {
180            priorValue->removeUser(this);
181        }
182    }
183    mOperand[index] = value;
184    value->addUser(this);
185}
186
187/** ------------------------------------------------------------------------------------------------------------- *
188 * @brief insertBefore
189 ** ------------------------------------------------------------------------------------------------------------- */
190void Statement::insertBefore(Statement * const statement) {
191    if (LLVM_UNLIKELY(statement == this)) {
192        return;
193    }
194    else if (LLVM_UNLIKELY(statement == nullptr)) {
195        throw std::runtime_error("cannot insert before null statement!");
196    }
197    else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
198        throw std::runtime_error("statement is not contained in a pablo block!");
199    }
200    removeFromParent();
201    mParent = statement->mParent;
202    if (LLVM_UNLIKELY(mParent->mFirst == statement)) {
203        mParent->mFirst = this;
204    }
205    mNext = statement;
206    mPrev = statement->mPrev;
207    statement->mPrev = this;
208    if (LLVM_LIKELY(mPrev != nullptr)) {
209        mPrev->mNext = this;
210    }
211    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
212        PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
213        mParent->addUser(&body);
214    }
215}
216
217/** ------------------------------------------------------------------------------------------------------------- *
218 * @brief insertAfter
219 ** ------------------------------------------------------------------------------------------------------------- */
220void Statement::insertAfter(Statement * const statement) {
221    if (LLVM_UNLIKELY(statement == this)) {
222        return;
223    }
224    else if (LLVM_UNLIKELY(statement == nullptr)) {
225        throw std::runtime_error("cannot insert after null statement!");
226    }
227    else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
228        throw std::runtime_error("statement is not contained in a pablo block!");
229    }
230    removeFromParent();
231    mParent = statement->mParent;
232    if (LLVM_UNLIKELY(mParent->mLast == statement)) {
233        mParent->mLast = this;
234    }
235    mPrev = statement;
236    mNext = statement->mNext;
237    statement->mNext = this;
238    if (LLVM_LIKELY(mNext != nullptr)) {
239        mNext->mPrev = this;
240    }
241    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
242        PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
243        mParent->addUser(&body);
244    }
245}
246
247/** ------------------------------------------------------------------------------------------------------------- *
248 * @brief removeFromParent
249 ** ------------------------------------------------------------------------------------------------------------- */
250Statement * Statement::removeFromParent() {
251    Statement * next = mNext;
252    if (LLVM_LIKELY(mParent != nullptr)) {
253        if (LLVM_UNLIKELY(mParent->mFirst == this)) {
254            mParent->mFirst = mNext;
255        }
256        if (LLVM_UNLIKELY(mParent->mLast == this)) {
257            mParent->mLast = mPrev;
258        }
259        if (LLVM_UNLIKELY(mParent->mInsertionPoint == this)) {
260            mParent->mInsertionPoint = mPrev;
261        }
262        if (LLVM_LIKELY(mPrev != nullptr)) {
263            mPrev->mNext = mNext;
264        }
265        if (LLVM_LIKELY(mNext != nullptr)) {
266            mNext->mPrev = mPrev;
267        }
268        if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
269            PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
270            mParent->removeUser(&body);
271        }
272    }
273    mPrev = nullptr;
274    mNext = nullptr;
275    mParent = nullptr;
276    return next;
277}
278
279/** ------------------------------------------------------------------------------------------------------------- *
280 * @brief eraseFromParent
281 ** ------------------------------------------------------------------------------------------------------------- */
282Statement * Statement::eraseFromParent(const bool recursively) {
283    // remove this statement from its operands' users list
284    for (unsigned i = 0; i != mOperands; ++i) {
285        mOperand[i]->removeUser(this);
286    }
287    Statement * redundantBranch = nullptr;
288    // If this is an If or While statement, we'll have to remove the statements within the
289    // body or we'll lose track of them.
290    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
291        PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
292        Statement * stmt = body.front();
293        // Note: by erasing the body, any Assign/Next nodes will be replaced with Zero.
294        while (stmt) {
295            stmt = stmt->eraseFromParent(recursively);
296        }
297    } else if (LLVM_UNLIKELY(isa<Assign>(this))) {
298        for (PabloAST * use : mUsers) {
299            if (If * ifNode = dyn_cast<If>(use)) {
300                auto & defs = ifNode->getDefined();
301                auto f = std::find(defs.begin(), defs.end(), this);
302                if (LLVM_LIKELY(f != defs.end())) {
303                    this->removeUser(ifNode);
304                    ifNode->removeUser(this);
305                    defs.erase(f);
306                    if (LLVM_UNLIKELY(defs.empty())) {
307                        redundantBranch = ifNode;
308                    }
309                    break;
310                }
311            }
312        }
313    } else if (LLVM_UNLIKELY(isa<Next>(this))) {
314        for (PabloAST * use : mUsers) {
315            if (While * whileNode = dyn_cast<While>(use)) {
316                auto & vars = whileNode->getVariants();
317                auto f = std::find(vars.begin(), vars.end(), this);
318                if (LLVM_LIKELY(f != vars.end())) {
319                    this->removeUser(whileNode);
320                    whileNode->removeUser(this);
321                    vars.erase(f);
322                    if (LLVM_UNLIKELY(vars.empty())) {
323                        redundantBranch = whileNode;
324                    }
325                    break;
326                }
327            }
328        }
329    }
330
331    replaceAllUsesWith(PabloBlock::createZeroes());
332
333    if (recursively) {
334        for (unsigned i = 0; i != mOperands; ++i) {
335            PabloAST * const op = mOperand[i];
336            if (LLVM_LIKELY(isa<Statement>(op))) {
337                bool erase = false;
338                if (op->getNumUses() == 0) {
339                    erase = true;
340                } else if ((isa<Assign>(op) || isa<Next>(op)) && op->getNumUses() == 1) {
341                    erase = true;
342                }
343                if (erase) {
344                    cast<Statement>(op)->eraseFromParent(true);
345                }
346            }
347        }
348        if (LLVM_UNLIKELY(redundantBranch != nullptr)) {
349            redundantBranch->eraseFromParent(true);
350        }
351    }
352
353    Statement * const next = removeFromParent();
354    mAllocator.deallocate(reinterpret_cast<Allocator::pointer>(this));
355    return next;
356}
357
358/** ------------------------------------------------------------------------------------------------------------- *
359 * @brief replaceWith
360 ** ------------------------------------------------------------------------------------------------------------- */
361Statement * Statement::replaceWith(PabloAST * const expr, const bool rename, const bool recursively) {
362    assert (expr);
363    if (LLVM_UNLIKELY(expr == this)) {
364        return getNextNode();
365    }
366    if (LLVM_LIKELY(rename && isa<Statement>(expr))) {
367        Statement * const stmt = cast<Statement>(expr);
368        if (getName()->isUserDefined() && stmt->getName()->isGenerated()) {
369            stmt->setName(getName());
370        }
371    }
372    replaceAllUsesWith(expr);   
373    return eraseFromParent(recursively);
374}
375
376/** ------------------------------------------------------------------------------------------------------------- *
377 * @brief contains
378 ** ------------------------------------------------------------------------------------------------------------- */
379bool StatementList::contains(Statement * const statement) {
380    for (Statement * stmt : *this) {
381        if (statement == stmt) {
382            return true;
383        }
384    }
385    return false;
386}
387
388/** ------------------------------------------------------------------------------------------------------------- *
389 * @brief clear
390 ** ------------------------------------------------------------------------------------------------------------- */
391void StatementList::clear() {
392    Statement * stmt = front();
393    while (stmt) {
394        Statement * next = stmt->mNext;
395        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
396            PabloBlock & body = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
397            stmt->mParent->removeUser(&body);
398        }
399        stmt->mPrev = nullptr;
400        stmt->mNext = nullptr;
401        stmt->mParent = nullptr;
402        stmt = next;
403    }
404    mInsertionPoint = nullptr;
405    mFirst = nullptr;
406    mLast = nullptr;
407}
408
409StatementList::~StatementList() {
410
411}
412
413/** ------------------------------------------------------------------------------------------------------------- *
414 * @brief escapes
415 *
416 * Is this statement used outside of its scope?
417 ** ------------------------------------------------------------------------------------------------------------- */
418bool escapes(const Statement * statement) {
419    const PabloBlock * const parent = statement->getParent();
420    for (const PabloAST * user : statement->users()) {
421        if (LLVM_LIKELY(isa<Statement>(user))) {
422            const PabloBlock * used = cast<Statement>(user)->getParent();
423            while (used != parent) {
424                used = used->getParent();
425                if (used == nullptr) {
426                    assert (isa<Assign>(statement) || isa<Next>(statement));
427                    return true;
428                }
429            }
430        }
431    }
432    return false;
433}
434
435}
Note: See TracBrowser for help on using the repository browser.