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

Last change on this file since 4888 was 4886, checked in by nmedfort, 3 years ago

Bug fixes

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