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

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

Work on multiplexing and distribution passes + a few AST modification bug fixes.

File size: 23.1 KB
RevLine 
[4244]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
[4419]7#include <pablo/pabloAST.h>
[4404]8#include <pablo/codegenstate.h>
[4276]9#include <llvm/Support/Compiler.h>
[4650]10#include <pablo/printer_pablos.h>
[4871]11#include <llvm/ADT/SmallVector.h>
[5156]12#include <boost/container/flat_set.hpp>
[4722]13
[5156]14using namespace boost::container;
15
[4244]16namespace pablo {
17
[4272]18PabloAST::Allocator PabloAST::mAllocator;
[5037]19PabloAST::VectorAllocator PabloAST::mVectorAllocator;
[4272]20
[4856]21/** ------------------------------------------------------------------------------------------------------------- *
22 * @brief equals
[4876]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.
[4856]26 ** ------------------------------------------------------------------------------------------------------------- */
[5156]27bool equals(const PabloAST * const expr1, const PabloAST * const expr2) {
[4276]28    assert (expr1 && expr2);
[4797]29    if (expr1 == expr2) {
30        return true;
31    } else if (expr1->getClassTypeId() == expr2->getClassTypeId()) {
[4510]32        if ((isa<Zeroes>(expr1)) || (isa<Ones>(expr1))) {
[4247]33            return true;
[4886]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));
[5023]38        } else if (isa<InFile>(expr1)) {
39            return equals(cast<InFile>(expr1)->getOperand(0), cast<InFile>(expr2)->getOperand(0));
[5042]40        } else if (isa<AtEOF>(expr1)) {
41            return equals(cast<AtEOF>(expr1)->getOperand(0), cast<AtEOF>(expr2)->getOperand(0));
[4886]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                    }
[4244]63                }
[4886]64                return true;
[4244]65            }
[4797]66        } else if (isa<Integer>(expr1) || isa<String>(expr1) || isa<Call>(expr1)) {
[4886]67            return false; // If these weren't equivalent by address they won't be equivalent by their operands.
[4805]68        } else { // Non-reassociatable functions (i.e., Sel, Advance, ScanThru, MatchStar, Assign, Next)
[4797]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;
[4244]75                }
76            }
[4797]77            return true;
[4244]78        }
79    }
80    return false;
81}
82
[4856]83/** ------------------------------------------------------------------------------------------------------------- *
84 * @brief replaceAllUsesWith
85 ** ------------------------------------------------------------------------------------------------------------- */
[4899]86void PabloAST::replaceAllUsesWith(PabloAST * const expr) {
[4876]87    assert (expr);
[4871]88    if (LLVM_UNLIKELY(this == expr)) {
89        return;
90    }
[4876]91    Statement * replacement[mUsers.size()];
92    Users::size_type replacements = 0;
93    PabloAST * last = nullptr;
[4868]94    for (PabloAST * user : mUsers) {
[4876]95        if (LLVM_UNLIKELY(user == expr || user == last)) {
[4868]96            continue;
[4876]97        } else if (isa<Statement>(user)) {
98            replacement[replacements++] = cast<Statement>(user);
99            last = user;
[4416]100        }
101    }
[4876]102    for (Users::size_type i = 0; i != replacements; ++i) {
103        replacement[i]->replaceUsesOfWith(this, expr);
[4868]104    }
[4416]105}
106
[4856]107/** ------------------------------------------------------------------------------------------------------------- *
[5156]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/** ------------------------------------------------------------------------------------------------------------- *
[4871]137 * @brief checkEscapedValueList
[4856]138 ** ------------------------------------------------------------------------------------------------------------- */
139template <class ValueType, class ValueList>
[4899]140inline void Statement::checkEscapedValueList(Statement * const branch, PabloAST * const from, PabloAST * const to, ValueList & list) {
[4856]141    if (LLVM_LIKELY(isa<ValueType>(from))) {
[5156]142        const auto f = std::find(list.begin(), list.end(), cast<ValueType>(from));
[4856]143        if (LLVM_LIKELY(f != list.end())) {
[4899]144            branch->removeUser(from);
145            from->removeUser(branch);
[5156]146            if (LLVM_UNLIKELY(isa<ValueType>(to))) {
147                if (LLVM_LIKELY(std::find(list.begin(), list.end(), cast<ValueType>(to)) == list.end())) {
148                    PabloBlock * parent = cast<ValueType>(to)->getParent();
149                    for (;;) {
150                        if (parent == cast<ValueType>(from)->getParent()) {
151                            *f = cast<ValueType>(to);
152                            branch->addUser(to);
153                            to->addUser(branch);
154                            return;
155                        }
156                        parent = parent->getParent();
157                        if (parent == nullptr) {
158                            break;
159                        }
160                    }
[4856]161                }
162            }
[4899]163            list.erase(f);
164        }                             
[4856]165    }
166}
167
168/** ------------------------------------------------------------------------------------------------------------- *
169 * @brief replaceUsesOfWith
170 ** ------------------------------------------------------------------------------------------------------------- */
171void Statement::replaceUsesOfWith(PabloAST * const from, PabloAST * const to) {
[4871]172    if (LLVM_UNLIKELY(from == to)) {
173        return;
174    }
[4856]175    for (unsigned i = 0; i != getNumOperands(); ++i) {
176       if (getOperand(i) == from) {
177           setOperand(i, to);
178       }
179    }
180    if (LLVM_UNLIKELY(isa<If>(this))) {
[4871]181        checkEscapedValueList<Assign>(this, from, to, cast<If>(this)->getDefined());
[4856]182    } else if (LLVM_UNLIKELY(isa<While>(this))) {
[4871]183        checkEscapedValueList<Next>(this, from, to, cast<While>(this)->getVariants());
[4856]184    }
185}
186
187/** ------------------------------------------------------------------------------------------------------------- *
188 * @brief setOperand
189 ** ------------------------------------------------------------------------------------------------------------- */
[4432]190void Statement::setOperand(const unsigned index, PabloAST * const value) {
[4899]191    assert ("Operand cannot be null!" && value);
[4415]192    assert (index < getNumOperands());
[4876]193    PabloAST * const prior = getOperand(index);
[4899]194    assert ("Operand cannot be null!" && prior);
[4876]195    if (LLVM_UNLIKELY(prior == value)) {
[4416]196        return;
[4722]197    }   
[4876]198    prior->removeUser(this);
[4416]199    mOperand[index] = value;
200    value->addUser(this);
[4415]201}
[4404]202
[4856]203/** ------------------------------------------------------------------------------------------------------------- *
204 * @brief insertBefore
205 ** ------------------------------------------------------------------------------------------------------------- */
[4404]206void Statement::insertBefore(Statement * const statement) {
[4650]207    if (LLVM_UNLIKELY(statement == this)) {
208        return;
209    }
210    else if (LLVM_UNLIKELY(statement == nullptr)) {
[4723]211        throw std::runtime_error("cannot insert before null statement!");
[4650]212    }
213    else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
[4723]214        throw std::runtime_error("statement is not contained in a pablo block!");
[4650]215    }
[4404]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    }
[4611]227    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
[4870]228        PabloBlock * body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
229        body->setParent(mParent);
[4611]230    }
[4404]231}
232
[4856]233/** ------------------------------------------------------------------------------------------------------------- *
234 * @brief insertAfter
235 ** ------------------------------------------------------------------------------------------------------------- */
[4404]236void Statement::insertAfter(Statement * const statement) {
[4650]237    if (LLVM_UNLIKELY(statement == this)) {
238        return;
[4871]239    } else if (LLVM_UNLIKELY(statement == nullptr)) {
[4723]240        throw std::runtime_error("cannot insert after null statement!");
[4871]241    } else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
[4723]242        throw std::runtime_error("statement is not contained in a pablo block!");
[4650]243    }
[4404]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    }
[4611]255    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
[4870]256        PabloBlock * body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
257        body->setParent(mParent);
[4611]258    }
[4404]259}
260
[4856]261/** ------------------------------------------------------------------------------------------------------------- *
262 * @brief removeFromParent
263 ** ------------------------------------------------------------------------------------------------------------- */
[4416]264Statement * Statement::removeFromParent() {
265    Statement * next = mNext;
[4404]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        }
[4650]273        if (LLVM_UNLIKELY(mParent->mInsertionPoint == this)) {
274            mParent->mInsertionPoint = mPrev;
[4415]275        }
[4404]276        if (LLVM_LIKELY(mPrev != nullptr)) {
277            mPrev->mNext = mNext;
278        }
279        if (LLVM_LIKELY(mNext != nullptr)) {
280            mNext->mPrev = mPrev;
281        }
[4611]282        if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
[4870]283            PabloBlock * body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
284            body->setParent(nullptr);
[4611]285        }
[4592]286    }
[4404]287    mPrev = nullptr;
288    mNext = nullptr;
289    mParent = nullptr;
[4416]290    return next;
[4404]291}
292
[4856]293/** ------------------------------------------------------------------------------------------------------------- *
294 * @brief eraseFromParent
295 ** ------------------------------------------------------------------------------------------------------------- */
[4416]296Statement * Statement::eraseFromParent(const bool recursively) {
[5156]297
[4871]298    SmallVector<Statement *, 1> redundantBranches;
[4594]299    // If this is an If or While statement, we'll have to remove the statements within the
300    // body or we'll lose track of them.
301    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
[4870]302        PabloBlock * const body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
303        body->eraseFromParent(recursively);
[4788]304    } else if (LLVM_UNLIKELY(isa<Assign>(this))) {
305        for (PabloAST * use : mUsers) {
306            if (If * ifNode = dyn_cast<If>(use)) {
[4829]307                auto & defs = ifNode->getDefined();
308                auto f = std::find(defs.begin(), defs.end(), this);
309                if (LLVM_LIKELY(f != defs.end())) {
[4788]310                    this->removeUser(ifNode);
311                    ifNode->removeUser(this);
[4829]312                    defs.erase(f);
313                    if (LLVM_UNLIKELY(defs.empty())) {
[4871]314                        redundantBranches.push_back(ifNode);
[4829]315                    }
[4788]316                }
317            }
318        }
319    } else if (LLVM_UNLIKELY(isa<Next>(this))) {
320        for (PabloAST * use : mUsers) {
321            if (While * whileNode = dyn_cast<While>(use)) {
[4829]322                auto & vars = whileNode->getVariants();
323                auto f = std::find(vars.begin(), vars.end(), this);
324                if (LLVM_LIKELY(f != vars.end())) {
[4788]325                    this->removeUser(whileNode);
326                    whileNode->removeUser(this);
[4829]327                    vars.erase(f);
328                    if (LLVM_UNLIKELY(vars.empty())) {
[4871]329                        redundantBranches.push_back(whileNode);
[4829]330                    }
[4788]331                }
332            }
333        }
[4594]334    }
335
[4788]336    replaceAllUsesWith(PabloBlock::createZeroes());
337
[4419]338    if (recursively) {
[4750]339        for (unsigned i = 0; i != mOperands; ++i) {
[5156]340            PabloAST * const op = mOperand[i]; assert (op);
341            op->removeUser(this);
342            if (LLVM_UNLIKELY(op->getNumUses() == 0 && isa<Statement>(op))) {
343                cast<Statement>(op)->eraseFromParent(true);
[4419]344            }
[5156]345            mOperand[i] = nullptr;
[4415]346        }
[4871]347        if (LLVM_UNLIKELY(redundantBranches.size() != 0)) {
[4870]348            // By eliminating this redundant branch, we may inadvertantly delete the scope block this statement
[4876]349            // resides within. Return null if so.
[4871]350            bool eliminatedScope = false;
351            for (Statement * br : redundantBranches) {
352                const PabloBlock * const body = isa<If>(br) ? cast<If>(br)->getBody() : cast<While>(br)->getBody();
353                if (LLVM_UNLIKELY(body == getParent())) {
354                    eliminatedScope = true;
355                }
356                br->eraseFromParent(true);
357            }
[4870]358            if (eliminatedScope) {
359                return nullptr;
360            }
[4829]361        }
[5156]362    } else { // just remove this statement from its operands' users list
363        for (unsigned i = 0; i != mOperands; ++i) {
364            PabloAST * const op = mOperand[i]; assert (op);
365            op->removeUser(this);
366            mOperand[i] = nullptr;
367        }
[4404]368    }
[4861]369    Statement * const next = removeFromParent();
370    mAllocator.deallocate(reinterpret_cast<Allocator::pointer>(this));
371    return next;
[4419]372}
[4280]373
[4856]374/** ------------------------------------------------------------------------------------------------------------- *
375 * @brief replaceWith
376 ** ------------------------------------------------------------------------------------------------------------- */
[4586]377Statement * Statement::replaceWith(PabloAST * const expr, const bool rename, const bool recursively) {
[4433]378    assert (expr);
[4419]379    if (LLVM_UNLIKELY(expr == this)) {
380        return getNextNode();
[4416]381    }
[4433]382    if (LLVM_LIKELY(rename && isa<Statement>(expr))) {
383        Statement * const stmt = cast<Statement>(expr);
384        if (getName()->isUserDefined() && stmt->getName()->isGenerated()) {
385            stmt->setName(getName());
386        }
387    }
[4899]388    replaceAllUsesWith(expr);
[4586]389    return eraseFromParent(recursively);
[4415]390}
391
[4856]392/** ------------------------------------------------------------------------------------------------------------- *
[4873]393 * @brief addOperand
394 ** ------------------------------------------------------------------------------------------------------------- */
[4876]395void Variadic::addOperand(PabloAST * const expr) {
396    if (LLVM_UNLIKELY(mOperands == mCapacity)) {
397        mCapacity = std::max<unsigned>(mCapacity * 2, 2);
398        PabloAST ** expandedOperandSpace = reinterpret_cast<PabloAST**>(mAllocator.allocate(mCapacity * sizeof(PabloAST *)));
399        for (unsigned i = 0; i != mOperands; ++i) {
400            expandedOperandSpace[i] = mOperand[i];
[4873]401        }
402        mAllocator.deallocate(reinterpret_cast<Allocator::pointer>(mOperand));
[4876]403        mOperand = expandedOperandSpace;
[4873]404    }
[4876]405    mOperand[mOperands++] = expr;
406    expr->addUser(this);
[4873]407}
408
409/** ------------------------------------------------------------------------------------------------------------- *
410 * @brief removeOperand
411 ** ------------------------------------------------------------------------------------------------------------- */
[4876]412PabloAST * Variadic::removeOperand(const unsigned index) {
413    assert (index < mOperands);
414    PabloAST * const expr = mOperand[index];
[4922]415    assert (expr);
[4873]416    --mOperands;
[4876]417    for (unsigned i = index; i != mOperands; ++i) {
418        mOperand[i] = mOperand[i + 1];
419    }
420    mOperand[mOperands] = nullptr;
421    expr->removeUser(this);
422    return expr;
[4873]423}
424
425/** ------------------------------------------------------------------------------------------------------------- *
[4856]426 * @brief contains
427 ** ------------------------------------------------------------------------------------------------------------- */
[4775]428bool StatementList::contains(Statement * const statement) {
429    for (Statement * stmt : *this) {
430        if (statement == stmt) {
431            return true;
432        }
433    }
434    return false;
435}
436
[4774]437/** ------------------------------------------------------------------------------------------------------------- *
438 * @brief escapes
439 *
440 * Is this statement used outside of its scope?
441 ** ------------------------------------------------------------------------------------------------------------- */
442bool escapes(const Statement * statement) {
443    const PabloBlock * const parent = statement->getParent();
444    for (const PabloAST * user : statement->users()) {
445        if (LLVM_LIKELY(isa<Statement>(user))) {
446            const PabloBlock * used = cast<Statement>(user)->getParent();
447            while (used != parent) {
448                used = used->getParent();
449                if (used == nullptr) {
450                    assert (isa<Assign>(statement) || isa<Next>(statement));
451                    return true;
452                }
453            }
454        }
455    }
456    return false;
[4432]457}
[4774]458
[5156]459/** ------------------------------------------------------------------------------------------------------------- *
460 * @brief dominates
461 *
462 * Does a precede (dominate) b?
463 ** ------------------------------------------------------------------------------------------------------------- */
464bool dominates(const PabloAST * const expr1, const PabloAST * const expr2) {
465    if (LLVM_UNLIKELY(expr1 == nullptr || expr2 == nullptr)) {
466        return (expr2 == nullptr);
467    } else if (LLVM_LIKELY(isa<Statement>(expr1))) {
468        const Statement * stmt1 = cast<Statement>(expr1);
469        assert ("expr1 is not in any block!" && stmt1->getParent());
470        if (isa<Statement>(expr2)) {
471            const Statement * stmt2 = cast<Statement>(expr2);
472            assert ("expr2 is not in any block!" && stmt2->getParent());
473
474            while (stmt1->getParent() != stmt2->getParent()) {
475
476                // Statement 1 preceeds Statement 2 if the branch leading to Statement 2
477                // succeeds Statement 1.
478
479                // But if Statement 1 escapes its block, it may still succeed Statement 2
480                // if and only if Statement 1 is an Assign or Next node whose outermost
481                // branch succeeds Statement 1. It is not enough to simply traverse back
482                // arbritarily. Test.
483
484                if (LLVM_UNLIKELY(isa<Assign>(stmt1))) {
485                    for (const PabloAST * user : stmt1->users()) {
486                        if (isa<If>(user)) {
487                            for (const Assign * def : cast<If>(user)->getDefined()) {
488                                if (def == stmt1) {
489                                    const Statement * test = stmt1;
490                                    for (;;) {
491                                        if (test->getParent() == stmt2->getParent()) {
492                                            stmt1 = test;
493                                            goto check;
494                                        }
495                                        test = test->getParent()->getBranch();
496                                        if (test == nullptr) {
497                                            break;
498                                        }
499                                    }
500                                }
501                            }
502                        }
503                    }
504                } else if (LLVM_UNLIKELY(isa<Next>(stmt1))) {
505                    for (const PabloAST * user : stmt1->users()) {
506                        if (isa<While>(user)) {
507                            for (const Next * var : cast<While>(user)->getVariants()) {
508                                if (var == stmt1) {
509                                    const Statement * test = stmt1;
510                                    for (;;) {
511                                        if (test->getParent() == stmt2->getParent()) {
512                                            stmt1 = test;
513                                            goto check;
514                                        }
515                                        test = test->getParent()->getBranch();
516                                        if (test == nullptr) {
517                                            break;
518                                        }
519                                    }
520                                }
521                            }
522                        }
523                    }
524                }
525
526                stmt2 = stmt2->getParent()->getBranch();
527                if (stmt2 == nullptr) {
528                    return false;
529                }
530
531            }
532
533check:      assert(stmt1->getParent() == stmt2->getParent());
534
535            const Statement * temp1 = stmt1, * temp2 = stmt2;
536            while (temp1 && temp2) {
537                if (temp1 == stmt2) {
538                    return true;
539                } else if (temp2 == stmt1) {
540                    return false;
541                }
542                temp1 = temp1->getNextNode();
543                temp2 = temp2->getNextNode();
544            }
545            return (temp2 == nullptr);
546        }
547        return false;
548    }
549    return true;
[4774]550}
[5156]551
552
553}
Note: See TracBrowser for help on using the repository browser.