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

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

Initial work for incorporating Types into Pablo AST.

File size: 24.6 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 <boost/container/flat_set.hpp>
13
14using namespace boost::container;
15
16namespace pablo {
17
18PabloAST::Allocator PabloAST::mAllocator;
19PabloAST::VectorAllocator PabloAST::mVectorAllocator;
20
21/** ------------------------------------------------------------------------------------------------------------- *
22 * @brief equals
23 *
24 *  Return true if expr1 and expr2 can be proven equivalent according to some rules, false otherwise.  Note that
25 *  false may be returned i some cases when the exprs are equivalent.
26 ** ------------------------------------------------------------------------------------------------------------- */
27bool equals(const PabloAST * const expr1, const PabloAST * const expr2) {
28    assert (expr1 && expr2);
29    if (expr1 == expr2) {
30        return true;
31    } else if (expr1->getClassTypeId() == expr2->getClassTypeId()) {
32        if ((isa<Zeroes>(expr1)) || (isa<Ones>(expr1))) {
33            return true;
34        } else if (isa<Var>(expr1)) {
35            return (cast<Var>(expr1)->getName() == cast<Var>(expr2)->getName());
36        } else if (isa<Not>(expr1)) {
37            return equals(cast<Not>(expr1)->getOperand(0), cast<Not>(expr2)->getOperand(0));
38        } else if (isa<InFile>(expr1)) {
39            return equals(cast<InFile>(expr1)->getOperand(0), cast<InFile>(expr2)->getOperand(0));
40        } else if (isa<AtEOF>(expr1)) {
41            return equals(cast<AtEOF>(expr1)->getOperand(0), cast<AtEOF>(expr2)->getOperand(0));
42        } else if (isa<Variadic>(expr1)) {
43            const Variadic * const var1 = cast<Variadic>(expr1);
44            const Variadic * const var2 = cast<Variadic>(expr2);
45            if (var1->getNumOperands() == var2->getNumOperands()) {
46                const unsigned operands = var1->getNumOperands();
47                for (unsigned i = 0; i != operands; ++i) {
48                    bool missing = true;
49                    for (unsigned j = 0; j != operands; ++j) {
50                        // odds are both variadics will be sorted; optimize towards testing them in order.
51                        unsigned k = i + j;
52                        if (LLVM_UNLIKELY(k >= operands)) {
53                            k -= operands;
54                        }
55                        if (equals(var1->getOperand(i), var2->getOperand(k))) {
56                            missing = false;
57                            break;
58                        }
59                    }
60                    if (missing) {
61                        return false;
62                    }
63                }
64                return true;
65            }
66        } else if (isa<Integer>(expr1) || isa<String>(expr1) || isa<Call>(expr1)) {
67            return false; // If these weren't equivalent by address they won't be equivalent by their operands.
68        } else { // Non-reassociatable functions (i.e., Sel, Advance, ScanThru, MatchStar, Assign, Next)
69            const Statement * stmt1 = cast<Statement>(expr1);
70            const Statement * stmt2 = cast<Statement>(expr2);
71            assert (stmt1->getNumOperands() == stmt2->getNumOperands());
72            for (unsigned i = 0; i != stmt1->getNumOperands(); ++i) {
73                if (!equals(stmt1->getOperand(i), stmt2->getOperand(i))) {
74                    return false;
75                }
76            }
77            return true;
78        }
79    }
80    return false;
81}
82
83/** ------------------------------------------------------------------------------------------------------------- *
84 * @brief replaceAllUsesWith
85 ** ------------------------------------------------------------------------------------------------------------- */
86void PabloAST::replaceAllUsesWith(PabloAST * const expr) {
87    assert (expr);
88    if (LLVM_UNLIKELY(this == expr)) {
89        return;
90    }
91    Statement * replacement[mUsers.size()];
92    Users::size_type replacements = 0;
93    PabloAST * last = nullptr;
94    for (PabloAST * user : mUsers) {
95        if (LLVM_UNLIKELY(user == expr || user == last)) {
96            continue;
97        } else if (isa<Statement>(user)) {
98            replacement[replacements++] = cast<Statement>(user);
99            last = user;
100        }
101    }
102    for (Users::size_type i = 0; i != replacements; ++i) {
103        replacement[i]->replaceUsesOfWith(this, expr);
104    }
105}
106
107/** ------------------------------------------------------------------------------------------------------------- *
108 * @brief addUser
109 ** ------------------------------------------------------------------------------------------------------------- */
110void PabloAST::addUser(PabloAST * const user) {
111    assert (user);
112    // Note: for the rare situation that this node is used multiple times by the same statement, duplicates are allowed.
113    mUsers.insert(std::lower_bound(mUsers.begin(), mUsers.end(), user), user);
114}
115
116/** ------------------------------------------------------------------------------------------------------------- *
117 * @brief removeUser
118 ** ------------------------------------------------------------------------------------------------------------- */
119void PabloAST::removeUser(PabloAST * const user) {
120    assert (user);
121    const auto pos = std::lower_bound(mUsers.begin(), mUsers.end(), user);
122    if (LLVM_UNLIKELY(pos == mUsers.end() || *pos != user)) {
123        std::string tmp;
124        raw_string_ostream out(tmp);
125        out << "Cannot remove user ";
126        PabloPrinter::print(user, out);
127        out << " from ";
128        PabloPrinter::print(this, out);
129        out << " because it's not in its user list!";
130        throw std::runtime_error(out.str());
131    }
132    mUsers.erase(pos);
133}
134
135/** ------------------------------------------------------------------------------------------------------------- *
136 * @brief checkEscapedValueList
137 ** ------------------------------------------------------------------------------------------------------------- */
138template <class ValueType, class ValueList>
139inline void Statement::checkEscapedValueList(Statement * const branch, PabloAST * const from, PabloAST * const to, ValueList & list) {
140    if (LLVM_LIKELY(isa<ValueType>(from))) {
141        const auto f = std::find(list.begin(), list.end(), cast<ValueType>(from));
142        if (LLVM_LIKELY(f != list.end())) {
143            branch->removeUser(from);
144            from->removeUser(branch);
145            if (LLVM_UNLIKELY(isa<ValueType>(to))) {
146                if (LLVM_LIKELY(std::find(list.begin(), list.end(), cast<ValueType>(to)) == list.end())) {
147                    PabloBlock * parent = cast<ValueType>(to)->getParent();
148                    for (;;) {
149                        if (parent == cast<ValueType>(from)->getParent()) {
150                            *f = cast<ValueType>(to);
151                            branch->addUser(to);
152                            to->addUser(branch);
153                            return;
154                        }
155                        parent = parent->getPredecessor ();
156                        if (parent == nullptr) {
157                            break;
158                        }
159                    }
160                }
161            }
162            list.erase(f);
163        }                             
164    }
165}
166
167/** ------------------------------------------------------------------------------------------------------------- *
168 * @brief replaceUsesOfWith
169 ** ------------------------------------------------------------------------------------------------------------- */
170void Statement::replaceUsesOfWith(PabloAST * const from, PabloAST * const to) {
171    if (LLVM_UNLIKELY(from == to)) {
172        return;
173    }
174    for (unsigned i = 0; i != getNumOperands(); ++i) {
175       if (getOperand(i) == from) {
176           setOperand(i, to);
177       }
178    }
179    if (LLVM_UNLIKELY(isa<If>(this))) {
180        checkEscapedValueList<Assign>(this, from, to, cast<If>(this)->getDefined());
181    } else if (LLVM_UNLIKELY(isa<While>(this))) {
182        checkEscapedValueList<Next>(this, from, to, cast<While>(this)->getVariants());
183    }
184}
185
186/** ------------------------------------------------------------------------------------------------------------- *
187 * @brief setOperand
188 ** ------------------------------------------------------------------------------------------------------------- */
189void Statement::setOperand(const unsigned index, PabloAST * const value) {   
190    assert ("Operand cannot be null!" && value);
191    assert (index < getNumOperands());
192    PabloAST * const prior = getOperand(index);
193    assert ("Operand cannot be null!" && prior);
194    if (LLVM_UNLIKELY(prior == value)) {
195        return;
196    }   
197    throwIfNonMatchingTypes(prior, value);
198    prior->removeUser(this);
199    mOperand[index] = value;
200    value->addUser(this);
201}
202
203/** ------------------------------------------------------------------------------------------------------------- *
204 * @brief insertBefore
205 ** ------------------------------------------------------------------------------------------------------------- */
206void Statement::insertBefore(Statement * const statement) {
207    if (LLVM_UNLIKELY(statement == this)) {
208        return;
209    }
210    else if (LLVM_UNLIKELY(statement == nullptr)) {
211        throw std::runtime_error("cannot insert before null statement!");
212    }
213    else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
214        throw std::runtime_error("statement is not contained in a pablo block!");
215    }
216    removeFromParent();
217    mParent = statement->mParent;
218    if (LLVM_UNLIKELY(mParent->mFirst == statement)) {
219        mParent->mFirst = this;
220    }
221    mNext = statement;
222    mPrev = statement->mPrev;
223    statement->mPrev = this;
224    if (LLVM_LIKELY(mPrev != nullptr)) {
225        mPrev->mNext = this;
226    }
227    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
228        PabloBlock * body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
229        body->setPredecessor (mParent);
230    }
231}
232
233/** ------------------------------------------------------------------------------------------------------------- *
234 * @brief insertAfter
235 ** ------------------------------------------------------------------------------------------------------------- */
236void Statement::insertAfter(Statement * const statement) {
237    if (LLVM_UNLIKELY(statement == this)) {
238        return;
239    } else if (LLVM_UNLIKELY(statement == nullptr)) {
240        throw std::runtime_error("cannot insert after null statement!");
241    } else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
242        throw std::runtime_error("statement is not contained in a pablo block!");
243    }
244    removeFromParent();
245    mParent = statement->mParent;
246    if (LLVM_UNLIKELY(mParent->mLast == statement)) {
247        mParent->mLast = this;
248    }
249    mPrev = statement;
250    mNext = statement->mNext;
251    statement->mNext = this;
252    if (LLVM_LIKELY(mNext != nullptr)) {
253        mNext->mPrev = this;
254    }
255    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
256        PabloBlock * body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
257        body->setPredecessor (mParent);
258    }
259}
260
261/** ------------------------------------------------------------------------------------------------------------- *
262 * @brief removeFromParent
263 ** ------------------------------------------------------------------------------------------------------------- */
264Statement * Statement::removeFromParent() {
265    Statement * next = mNext;
266    if (LLVM_LIKELY(mParent != nullptr)) {
267        if (LLVM_UNLIKELY(mParent->mFirst == this)) {
268            mParent->mFirst = mNext;
269        }
270        if (LLVM_UNLIKELY(mParent->mLast == this)) {
271            mParent->mLast = mPrev;
272        }
273        if (LLVM_UNLIKELY(mParent->mInsertionPoint == this)) {
274            mParent->mInsertionPoint = mPrev;
275        }
276        if (LLVM_LIKELY(mPrev != nullptr)) {
277            mPrev->mNext = mNext;
278        }
279        if (LLVM_LIKELY(mNext != nullptr)) {
280            mNext->mPrev = mPrev;
281        }
282        if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
283            PabloBlock * body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
284            body->setPredecessor (nullptr);
285        }
286    }
287    mPrev = nullptr;
288    mNext = nullptr;
289    mParent = nullptr;
290    return next;
291}
292
293/** ------------------------------------------------------------------------------------------------------------- *
294 * @brief eraseFromParent
295 ** ------------------------------------------------------------------------------------------------------------- */
296Statement * Statement::eraseFromParent(const bool recursively) {
297
298    if (LLVM_UNLIKELY(getParent() == nullptr)) {
299        return nullptr;
300    }
301
302    SmallVector<Statement *, 1> redundantBranches;
303    // If this is an If or While statement, we'll have to remove the statements within the
304    // body or we'll lose track of them.
305    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
306        PabloBlock * const body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
307        body->eraseFromParent(recursively);
308    } else if (LLVM_UNLIKELY(isa<Assign>(this))) {
309        for (PabloAST * use : mUsers) {
310            if (If * ifNode = dyn_cast<If>(use)) {
311                auto & defs = ifNode->getDefined();
312                auto f = std::find(defs.begin(), defs.end(), this);
313                if (LLVM_LIKELY(f != defs.end())) {
314                    this->removeUser(ifNode);
315                    ifNode->removeUser(this);
316                    defs.erase(f);
317                    if (LLVM_UNLIKELY(defs.empty())) {
318                        redundantBranches.push_back(ifNode);
319                    }
320                }
321            }
322        }
323    } else if (LLVM_UNLIKELY(isa<Next>(this))) {
324        for (PabloAST * use : mUsers) {
325            if (While * whileNode = dyn_cast<While>(use)) {
326                auto & vars = whileNode->getVariants();
327                auto f = std::find(vars.begin(), vars.end(), this);
328                if (LLVM_LIKELY(f != vars.end())) {
329                    this->removeUser(whileNode);
330                    whileNode->removeUser(this);
331                    vars.erase(f);
332                    if (LLVM_UNLIKELY(vars.empty())) {
333                        redundantBranches.push_back(whileNode);
334                    }
335                }
336            }
337        }
338    }
339
340    replaceAllUsesWith(getParent()->createZeroes(getType()));
341
342    if (recursively) {
343        for (unsigned i = 0; i != mOperands; ++i) {
344            PabloAST * const op = mOperand[i]; assert (op);
345            op->removeUser(this);
346            if (LLVM_UNLIKELY(op->getNumUses() == 0 && isa<Statement>(op))) {
347                cast<Statement>(op)->eraseFromParent(true);
348            }
349            mOperand[i] = nullptr;
350        }
351        if (LLVM_UNLIKELY(redundantBranches.size() != 0)) {
352            // By eliminating this redundant branch, we may inadvertantly delete the scope block this statement
353            // resides within. Return null if so.
354            bool eliminatedScope = false;
355            for (Statement * br : redundantBranches) {
356                const PabloBlock * const body = isa<If>(br) ? cast<If>(br)->getBody() : cast<While>(br)->getBody();
357                if (LLVM_UNLIKELY(body == getParent())) {
358                    eliminatedScope = true;
359                }
360                br->eraseFromParent(true);
361            }
362            if (eliminatedScope) {
363                return nullptr;
364            }
365        }
366    } else { // just remove this statement from its operands' users list
367        for (unsigned i = 0; i != mOperands; ++i) {
368            PabloAST * const op = mOperand[i]; assert (op);
369            op->removeUser(this);
370            mOperand[i] = nullptr;
371        }
372    }
373    Statement * const next = removeFromParent();
374    mAllocator.deallocate(reinterpret_cast<Allocator::pointer>(this));
375    return next;
376}
377
378/** ------------------------------------------------------------------------------------------------------------- *
379 * @brief replaceWith
380 ** ------------------------------------------------------------------------------------------------------------- */
381Statement * Statement::replaceWith(PabloAST * const expr, const bool rename, const bool recursively) {
382    assert (expr);
383    if (LLVM_UNLIKELY(expr == this)) {
384        return getNextNode();
385    }
386    if (LLVM_LIKELY(rename && isa<Statement>(expr))) {
387        Statement * const stmt = cast<Statement>(expr);
388        if (getName()->isUserDefined() && stmt->getName()->isGenerated()) {
389            stmt->setName(getName());
390        }
391    }
392    replaceAllUsesWith(expr);
393    return eraseFromParent(recursively);
394}
395
396/** ------------------------------------------------------------------------------------------------------------- *
397 * @brief addOperand
398 ** ------------------------------------------------------------------------------------------------------------- */
399void Variadic::addOperand(PabloAST * const expr) {
400    throwIfNonMatchingTypes(this, expr);
401    if (LLVM_UNLIKELY(mOperands == mCapacity)) {
402        mCapacity = std::max<unsigned>(mCapacity * 2, 2);
403        PabloAST ** expandedOperandSpace = reinterpret_cast<PabloAST**>(mAllocator.allocate(mCapacity * sizeof(PabloAST *)));
404        for (unsigned i = 0; i != mOperands; ++i) {
405            expandedOperandSpace[i] = mOperand[i];
406        }
407        mAllocator.deallocate(reinterpret_cast<Allocator::pointer>(mOperand));
408        mOperand = expandedOperandSpace;
409    }
410    mOperand[mOperands++] = expr;
411    expr->addUser(this);
412}
413
414/** ------------------------------------------------------------------------------------------------------------- *
415 * @brief removeOperand
416 ** ------------------------------------------------------------------------------------------------------------- */
417PabloAST * Variadic::removeOperand(const unsigned index) {
418    assert (index < mOperands);
419    PabloAST * const expr = mOperand[index];
420    assert (expr);
421    --mOperands;
422    for (unsigned i = index; i != mOperands; ++i) {
423        mOperand[i] = mOperand[i + 1];
424    }
425    mOperand[mOperands] = nullptr;
426    expr->removeUser(this);
427    return expr;
428}
429
430/** ------------------------------------------------------------------------------------------------------------- *
431 * @brief contains
432 ** ------------------------------------------------------------------------------------------------------------- */
433bool StatementList::contains(Statement * const statement) {
434    for (Statement * stmt : *this) {
435        if (statement == stmt) {
436            return true;
437        }
438    }
439    return false;
440}
441
442/** ------------------------------------------------------------------------------------------------------------- *
443 * @brief escapes
444 *
445 * Is this statement used outside of its scope?
446 ** ------------------------------------------------------------------------------------------------------------- */
447bool escapes(const Statement * statement) {
448    const PabloBlock * const parent = statement->getParent();
449    for (const PabloAST * user : statement->users()) {
450        if (LLVM_LIKELY(isa<Statement>(user))) {
451            const PabloBlock * used = cast<Statement>(user)->getParent();
452            while (used != parent) {
453                used = used->getPredecessor ();
454                if (used == nullptr) {
455                    assert (isa<Assign>(statement) || isa<Next>(statement));
456                    return true;
457                }
458            }
459        }
460    }
461    return false;
462}
463
464/** ------------------------------------------------------------------------------------------------------------- *
465 * @brief dominates
466 *
467 * Does a precede (dominate) b?
468 ** ------------------------------------------------------------------------------------------------------------- */
469bool dominates(const PabloAST * const expr1, const PabloAST * const expr2) {
470    if (LLVM_UNLIKELY(expr1 == nullptr || expr2 == nullptr)) {
471        return (expr2 == nullptr);
472    } else if (LLVM_LIKELY(isa<Statement>(expr1))) {
473        const Statement * stmt1 = cast<Statement>(expr1);
474        assert ("expr1 is not in any block!" && stmt1->getParent());
475        if (isa<Statement>(expr2)) {
476            const Statement * stmt2 = cast<Statement>(expr2);
477            assert ("expr2 is not in any block!" && stmt2->getParent());
478
479            while (stmt1->getParent() != stmt2->getParent()) {
480
481                // Statement 1 preceeds Statement 2 if the branch leading to Statement 2
482                // succeeds Statement 1.
483
484                // But if Statement 1 escapes its block, it may still succeed Statement 2
485                // if and only if Statement 1 is an Assign or Next node whose outermost
486                // branch succeeds Statement 1. It is not enough to simply traverse back
487                // arbritarily. Test.
488
489                if (LLVM_UNLIKELY(isa<Assign>(stmt1))) {
490                    for (const PabloAST * user : stmt1->users()) {
491                        if (isa<If>(user)) {
492                            for (const Assign * def : cast<If>(user)->getDefined()) {
493                                if (def == stmt1) {
494                                    const Statement * test = stmt1;
495                                    for (;;) {
496                                        if (test->getParent() == stmt2->getParent()) {
497                                            stmt1 = test;
498                                            goto check;
499                                        }
500                                        test = test->getParent()->getBranch();
501                                        if (test == nullptr) {
502                                            break;
503                                        }
504                                    }
505                                }
506                            }
507                        }
508                    }
509                } else if (LLVM_UNLIKELY(isa<Next>(stmt1))) {
510                    for (const PabloAST * user : stmt1->users()) {
511                        if (isa<While>(user)) {
512                            for (const Next * var : cast<While>(user)->getVariants()) {
513                                if (var == stmt1) {
514                                    const Statement * test = stmt1;
515                                    for (;;) {
516                                        if (test->getParent() == stmt2->getParent()) {
517                                            stmt1 = test;
518                                            goto check;
519                                        }
520                                        test = test->getParent()->getBranch();
521                                        if (test == nullptr) {
522                                            break;
523                                        }
524                                    }
525                                }
526                            }
527                        }
528                    }
529                }
530
531                stmt2 = stmt2->getParent()->getBranch();
532                if (stmt2 == nullptr) {
533                    return false;
534                }
535
536            }
537
538check:      assert(stmt1->getParent() == stmt2->getParent());
539
540            const Statement * temp1 = stmt1, * temp2 = stmt2;
541            while (temp1 && temp2) {
542                if (temp1 == stmt2) {
543                    return true;
544                } else if (temp2 == stmt1) {
545                    return false;
546                }
547                temp1 = temp1->getNextNode();
548                temp2 = temp2->getNextNode();
549            }
550            return (temp2 == nullptr);
551        }
552        return false;
553    }
554    return true;
555}
556
557/** ------------------------------------------------------------------------------------------------------------- *
558 * @brief throwIfNonMatchingTypes
559 ** ------------------------------------------------------------------------------------------------------------- */
560void PabloAST::throwIfNonMatchingTypes(const PabloAST * const a, const PabloAST * const b) {
561    if (LLVM_UNLIKELY(a->getType() != b->getType())) {
562        std::string tmp;
563        raw_string_ostream out(tmp);
564        out << "Error: ";
565        PabloPrinter::print(a, out);
566        out << "'s type does not match ";
567        PabloPrinter::print(b, out);
568        throw std::runtime_error(out.str());
569    }
570}
571
572/** ------------------------------------------------------------------------------------------------------------- *
573 * @brief throwIfNonMatchingTypes
574 ** ------------------------------------------------------------------------------------------------------------- */
575void PabloAST::throwIfNonMatchingType(const PabloAST * const a, const PabloType::TypeId typeId) {
576    if (LLVM_UNLIKELY(a->getType() == nullptr || a->getType()->getTypeId() != typeId)) {
577        std::string tmp;
578        raw_string_ostream out(tmp);
579        out << "Error: ";
580        PabloPrinter::print(a, out);
581        out << "'s type is invalid.";
582        throw std::runtime_error(out.str());
583    }
584}
585
586}
Note: See TracBrowser for help on using the repository browser.