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

Last change on this file since 5032 was 5023, checked in by cameron, 3 years ago

pablo.InFile? initial support

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