Ignore:
Timestamp:
Sep 14, 2016, 2:56:54 PM (3 years ago)
Author:
nmedfort
Message:

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r5042 r5156  
    1010#include <pablo/printer_pablos.h>
    1111#include <llvm/ADT/SmallVector.h>
     12#include <boost/container/flat_set.hpp>
     13
     14using namespace boost::container;
    1215
    1316namespace pablo {
     
    2225 *  false may be returned i some cases when the exprs are equivalent.
    2326 ** ------------------------------------------------------------------------------------------------------------- */
    24 bool equals(const PabloAST * expr1, const PabloAST * expr2) {
     27bool equals(const PabloAST * const expr1, const PabloAST * const expr2) {
    2528    assert (expr1 && expr2);
    2629    if (expr1 == expr2) {
     
    103106
    104107/** ------------------------------------------------------------------------------------------------------------- *
     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/** ------------------------------------------------------------------------------------------------------------- *
    105137 * @brief checkEscapedValueList
    106138 ** ------------------------------------------------------------------------------------------------------------- */
     
    108140inline void Statement::checkEscapedValueList(Statement * const branch, PabloAST * const from, PabloAST * const to, ValueList & list) {
    109141    if (LLVM_LIKELY(isa<ValueType>(from))) {
    110         auto f = std::find(list.begin(), list.end(), cast<ValueType>(from));
     142        const auto f = std::find(list.begin(), list.end(), cast<ValueType>(from));
    111143        if (LLVM_LIKELY(f != list.end())) {
    112144            branch->removeUser(from);
    113145            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;
     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                    }
    120161                }
    121162            }
     
    254295 ** ------------------------------------------------------------------------------------------------------------- */
    255296Statement * 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     }
     297
    260298    SmallVector<Statement *, 1> redundantBranches;
    261299    // If this is an If or While statement, we'll have to remove the statements within the
     
    300338    if (recursively) {
    301339        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             }
     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);
     344            }
     345            mOperand[i] = nullptr;
    308346        }
    309347        if (LLVM_UNLIKELY(redundantBranches.size() != 0)) {
     
    321359                return nullptr;
    322360            }
     361        }
     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;
    323367        }
    324368    }
     
    413457}
    414458
    415 }
     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;
     550}
     551
     552
     553}
Note: See TracChangeset for help on using the changeset viewer.