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

Last change on this file since 5074 was 5042, checked in by cameron, 3 years ago

Add pablo.atEOF; clean out bit4/6 hack for unterminated final lines in icgrep.

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