Changeset 4856


Ignore:
Timestamp:
Oct 31, 2015, 12:20:31 PM (3 years ago)
Author:
nmedfort
Message:

Bug fix for use-def correctness regarding escaping values of If and While nodes.

Location:
icGREP/icgrep-devel/icgrep
Files:
9 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/CMakeLists.txt

    r4854 r4856  
    330330SET(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS} -O3 -DNDEBUG")
    331331IF (${CMAKE_SYSTEM} MATCHES "Linux")
    332     SET(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS} -g") # -fsanitize=address
     332    SET(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS} -g -fsanitize=address") # -fsanitize=address
    333333ENDIF()
    334334
  • icGREP/icgrep-devel/icgrep/pablo/analysis/pabloverifier.cpp

    r4804 r4856  
    99#include <unordered_set>
    1010#endif
     11#include <queue>
     12
    1113
    1214namespace pablo {
     
    4648                    raw_string_ostream str(tmp);
    4749                    PabloPrinter::print(user, "PabloVerifier: use-def error: ", str);
    48                     PabloPrinter::print(stmt, " is a user of ", str);
     50                    str << " is a user of ";
     51                    PabloPrinter::print(stmt, str);
    4952                    if (user->getParent() == nullptr) {
    5053                        str << " but is not in any scope.";
     
    136139            str << " succeeds ";
    137140            PabloPrinter::print(prev, str);
    138             str << " but expects to preceed  ";
     141            str << " but expects to preceed ";
    139142            PabloPrinter::print(stmt->getPrevNode(), str);
    140143            throw std::runtime_error(str.str());
     
    158161                throw std::runtime_error(str.str());
    159162            }
    160             const Statement * misreportedEscapingValue = nullptr;
     163            const Statement * badEscapedValue = nullptr;
    161164            if (isa<If>(stmt)) {
    162165                for (const Assign * def : cast<If>(stmt)->getDefined()) {
    163166                    if (def->getParent() != &nested) {
    164                         misreportedEscapingValue = def;
     167                        badEscapedValue = def;
    165168                        break;
    166169                    }
     
    169172                for (const Next * var : cast<While>(stmt)->getVariants()) {
    170173                    if (var->getParent() != &nested) {
    171                         misreportedEscapingValue = var;
    172                         break;
    173                     }
    174                 }
    175             }
    176             if (misreportedEscapingValue) {
     174                        badEscapedValue = var;
     175                        break;
     176                    }
     177                }
     178            }
     179            if (badEscapedValue) {
    177180                std::string tmp;
    178181                raw_string_ostream str(tmp);
    179182                str << "PabloVerifier: structure error: ";
    180                 PabloPrinter::print(misreportedEscapingValue, str);
     183                PabloPrinter::print(badEscapedValue, str);
    181184                str << " is not contained within the body of ";
    182185                PabloPrinter::print(stmt, str);
     186                throw std::runtime_error(str.str());
     187            }
     188            if (isa<If>(stmt)) {
     189                for (const Assign * def : cast<If>(stmt)->getDefined()) {
     190                    if (LLVM_UNLIKELY(std::find(stmt->user_begin(), stmt->user_end(), def) == stmt->user_end())) {
     191                        badEscapedValue = def;
     192                        break;
     193                    }
     194                }
     195            } else {
     196                for (const Next * var : cast<While>(stmt)->getVariants()) {
     197                    if (LLVM_UNLIKELY(std::find(stmt->user_begin(), stmt->user_end(), var) == stmt->user_end())) {
     198                        badEscapedValue = var;
     199                        break;
     200                    }
     201                }
     202            }
     203            if (badEscapedValue) {
     204                std::string tmp;
     205                raw_string_ostream str(tmp);
     206                str << "PabloVerifier: structure error: ";
     207                PabloPrinter::print(badEscapedValue, str);
     208                str << " is an escaped value of ";
     209                PabloPrinter::print(stmt, str);
     210                str << " but not a user";
    183211                throw std::runtime_error(str.str());
    184212            }
     
    214242};
    215243
     244bool recursivelyDefined(const Statement * const stmt) {
     245    std::queue<const Statement *> Q;
     246    SmallSet<const PabloAST *> V;
     247    V.insert(stmt);
     248    for (const Statement * ancestor = stmt;;) {
     249        for (unsigned i = 0; i != ancestor->getNumOperands(); ++i) {
     250            const PabloAST * op = ancestor->getOperand(i);
     251            if (isa<Statement>(op) && V.count(op) == 0) {
     252                if (op == stmt) {
     253                    return true;
     254                }
     255                Q.push(cast<Statement>(op));
     256                V.insert(op);
     257            }
     258        }
     259        if (LLVM_UNLIKELY(Q.empty())) {
     260            break;
     261        }
     262        ancestor = Q.front();
     263        Q.pop();
     264    }
     265    return false;
     266}
     267
    216268void isTopologicallyOrdered(const PabloBlock & block, const OrderingVerifier & parent) {
    217269    OrderingVerifier ov(parent);
     
    226278            const PabloAST * const op = stmt->getOperand(i);
    227279            if (LLVM_UNLIKELY((isa<Statement>(op) || isa<Var>(op)) && ov.count(op) == 0)) {
     280
     281                std::string tmp;
     282                raw_string_ostream str(tmp);
     283                str << "PabloVerifier: ordering volation: ";
     284                if (LLVM_UNLIKELY(recursivelyDefined(stmt))) {
     285                    PabloPrinter::print(stmt, str);
     286                    str << " is recursively defined!";
     287                    throw std::runtime_error(str.str());
     288                }
    228289                // TODO: make this actually test whether the operand is ever defined,
    229290                // or if it was defined in a scope that cannot be reached?
    230                 std::string tmp;
    231                 raw_string_ostream str(tmp);
    232                 str << "PabloVerifier: function is not topologically ordered! ";
     291
     292                str << "function is not topologically ordered! ";
    233293                PabloPrinter::print(stmt->getOperand(i), str);
    234294                PabloPrinter::print(stmt, " was used before definition by ", str);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/codemotionpass.cpp

    r4854 r4856  
    4747}
    4848
    49 
    5049/** ------------------------------------------------------------------------------------------------------------- *
    5150 * @brief isSafeToMove
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4852 r4856  
    200200 * @brief removeIdenticalEscapedValues
    201201 ** ------------------------------------------------------------------------------------------------------------- */
    202 template <class ValueList>
     202template <class ValueList, class ValueType = typename ValueList::value_type>
    203203inline void removeIdenticalEscapedValues(ValueList & list) {
     204    std::vector<ValueType> identicalValues;
    204205    for (auto i = list.begin(); i != list.end(); ++i) {
    205         for (auto j = i + 1; j != list.end(); ) {
     206        for (auto j = i + 1; j != list.end(); ++j) {
    206207            if (LLVM_UNLIKELY(equals(*i, *j))) {
    207                 Statement * redundantValue = *j;
    208                 j = list.erase(j);
    209                 redundantValue->replaceWith(*i, false, true);
    210                 continue;
    211             }
    212             ++j;
    213         }
     208                identicalValues.push_back(*j);
     209            }
     210        }
     211        for (ValueType identicalValue : identicalValues) {
     212            identicalValue->replaceWith(*i);
     213        }
     214        identicalValues.clear();
    214215    }
    215216}
     
    279280                while (nested) {
    280281                    Statement * next = nested->removeFromParent();
     282                    if (isa<Assign>(nested)) {
     283                        ifNode->removeDefined(cast<Assign>(nested));
     284                    }
    281285                    nested->insertAfter(stmt);
    282286                    stmt = nested;
    283287                    nested = next;
    284288                }
    285                 ifNode->getDefined().clear();
    286289                stmt = ifNode->eraseFromParent(true);
    287290                continue;
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4829 r4856  
    99#include <llvm/Support/Compiler.h>
    1010#include <pablo/printer_pablos.h>
    11 #ifndef NDEBUG
    12 #include <queue>
    13 #include <unordered_set>
    14 #endif
     11#include <iostream>
    1512
    1613namespace pablo {
     
    2724*/
    2825
     26/** ------------------------------------------------------------------------------------------------------------- *
     27 * @brief equals
     28 ** ------------------------------------------------------------------------------------------------------------- */
    2929bool equals(const PabloAST * expr1, const PabloAST * expr2) {
    3030    assert (expr1 && expr2);
     
    8484}
    8585
     86/** ------------------------------------------------------------------------------------------------------------- *
     87 * @brief replaceAllUsesWith
     88 ** ------------------------------------------------------------------------------------------------------------- */
    8689void PabloAST::replaceAllUsesWith(PabloAST * expr) {   
    8790    Statement * user[mUsers.size()];
     
    99102}
    100103
     104/** ------------------------------------------------------------------------------------------------------------- *
     105 * @brief checkForReplacementInEscapedValueList
     106 ** ------------------------------------------------------------------------------------------------------------- */
     107template <class ValueType, class ValueList>
     108inline void Statement::checkForReplacementInEscapedValueList(Statement * 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            if (LLVM_LIKELY(isa<ValueType>(to))) {
     113                if (std::find(list.begin(), list.end(), cast<ValueType>(to)) == list.end()) {
     114                    *f = cast<ValueType>(to);
     115                    branch->addUser(to);
     116                } else {
     117                    list.erase(f);
     118                }
     119                branch->removeUser(from);
     120                assert (std::find(list.begin(), list.end(), cast<ValueType>(to)) != list.end());
     121                assert (std::find(branch->user_begin(), branch->user_end(), cast<ValueType>(to)) != branch->user_end());
     122            } else { // replacement error occured
     123                std::string tmp;
     124                raw_string_ostream str(tmp);
     125                str << "cannot replace escaped value ";
     126                PabloPrinter::print(from, str);
     127                str << " with ";
     128                PabloPrinter::print(to, str);
     129                str << " in ";
     130                PabloPrinter::print(branch, str);
     131                throw std::runtime_error(str.str());
     132            }
     133        }               
     134        assert (std::find(list.begin(), list.end(), cast<ValueType>(from)) == list.end());
     135        assert (std::find(branch->user_begin(), branch->user_end(), cast<ValueType>(from)) == branch->user_end());
     136    }
     137}
     138
     139/** ------------------------------------------------------------------------------------------------------------- *
     140 * @brief replaceUsesOfWith
     141 ** ------------------------------------------------------------------------------------------------------------- */
     142void Statement::replaceUsesOfWith(PabloAST * const from, PabloAST * const to) {
     143    for (unsigned i = 0; i != getNumOperands(); ++i) {
     144       if (getOperand(i) == from) {
     145           setOperand(i, to);
     146       }
     147    }
     148    if (LLVM_UNLIKELY(isa<If>(this))) {
     149        checkForReplacementInEscapedValueList<Assign>(this, from, to, cast<If>(this)->getDefined());
     150    } else if (LLVM_UNLIKELY(isa<While>(this))) {
     151        checkForReplacementInEscapedValueList<Next>(this, from, to, cast<While>(this)->getVariants());
     152    }
     153}
     154
     155/** ------------------------------------------------------------------------------------------------------------- *
     156 * @brief setOperand
     157 ** ------------------------------------------------------------------------------------------------------------- */
    101158void Statement::setOperand(const unsigned index, PabloAST * const value) {
    102159    assert (value);
    103160    assert (index < getNumOperands());
    104     assert (noRecursiveOperand(value));
    105161    PabloAST * const priorValue = getOperand(index);
    106162    if (LLVM_UNLIKELY(priorValue == value)) {
     
    124180}
    125181
     182/** ------------------------------------------------------------------------------------------------------------- *
     183 * @brief insertBefore
     184 ** ------------------------------------------------------------------------------------------------------------- */
    126185void Statement::insertBefore(Statement * const statement) {
    127186    if (LLVM_UNLIKELY(statement == this)) {
     
    151210}
    152211
     212/** ------------------------------------------------------------------------------------------------------------- *
     213 * @brief insertAfter
     214 ** ------------------------------------------------------------------------------------------------------------- */
    153215void Statement::insertAfter(Statement * const statement) {
    154216    if (LLVM_UNLIKELY(statement == this)) {
     
    178240}
    179241
     242/** ------------------------------------------------------------------------------------------------------------- *
     243 * @brief removeFromParent
     244 ** ------------------------------------------------------------------------------------------------------------- */
    180245Statement * Statement::removeFromParent() {
    181246    Statement * next = mNext;
     
    207272}
    208273
     274/** ------------------------------------------------------------------------------------------------------------- *
     275 * @brief eraseFromParent
     276 ** ------------------------------------------------------------------------------------------------------------- */
    209277Statement * Statement::eraseFromParent(const bool recursively) {
    210278    // remove this statement from its operands' users list
     
    281349}
    282350
     351/** ------------------------------------------------------------------------------------------------------------- *
     352 * @brief replaceWith
     353 ** ------------------------------------------------------------------------------------------------------------- */
    283354Statement * Statement::replaceWith(PabloAST * const expr, const bool rename, const bool recursively) {
    284355    assert (expr);
     
    296367}
    297368
    298 #ifndef NDEBUG
    299 bool Statement::noRecursiveOperand(const PabloAST * const operand) {
    300     if (const Statement * stmt = dyn_cast<Statement>(operand)) {
    301         std::queue<const Statement *> Q;
    302         std::unordered_set<const PabloAST *> V;
    303         V.insert(stmt);
    304         for (;;) {
    305             if (stmt == this) {
    306                 return false;
    307             }
    308             for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    309                 const PabloAST * op = stmt->getOperand(i);               
    310                 if (isa<Statement>(op) && V.count(op) == 0) {
    311                     Q.push(cast<Statement>(op));
    312                     V.insert(op);
    313                 }
    314             }
    315             if (LLVM_UNLIKELY(Q.empty())) {
    316                 break;
    317             }
    318             stmt = Q.front();
    319             Q.pop();
    320         }
    321     }
    322     return true;
    323 }
    324 #endif
    325 
     369/** ------------------------------------------------------------------------------------------------------------- *
     370 * @brief contains
     371 ** ------------------------------------------------------------------------------------------------------------- */
    326372bool StatementList::contains(Statement * const statement) {
    327373    for (Statement * stmt : *this) {
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r4841 r4856  
    2121class PabloBlock;
    2222class String;
     23class Statement;
    2324
    2425class PabloAST {
     
    162163    friend class Simplifier;
    163164    friend class PabloBlock;
     165    template <class ValueType, class ValueList>
     166    friend void checkForReplacementInEscapedValueList(const Statement *, const PabloAST * const, PabloAST * const, ValueList &);
    164167public:
    165168    static inline bool classof(const PabloAST * e) {
     
    185188    }
    186189
    187     inline void replaceUsesOfWith(const PabloAST * const from, PabloAST * const to) {
    188         for (unsigned i = 0; i != getNumOperands(); ++i) {
    189             if (getOperand(i) == from) {
    190                 setOperand(i, to);
    191             }
    192         }
    193     }
     190    void replaceUsesOfWith(PabloAST * const from, PabloAST * const to);
    194191
    195192    inline PabloAST * getOperand(const unsigned index) const {
     
    243240        }
    244241    } 
    245 #ifndef NDEBUG
    246     bool noRecursiveOperand(const PabloAST * const operand);
    247 #endif
     242private:
     243    template <class ValueType, class ValueList>
     244    void checkForReplacementInEscapedValueList(Statement * branch, PabloAST * const from, PabloAST * const to, ValueList & list);
    248245protected:   
    249246    const String *              mName;
  • icGREP/icgrep-devel/icgrep/pablo/ps_if.cpp

    r4764 r4856  
    2323    for (PabloAST * def : mDefined) {
    2424        def->addUser(this);
    25         addUser(def);
     25        this->addUser(def);
    2626    }
    2727}
     
    3434    for (PabloAST * def : mDefined) {
    3535        def->addUser(this);
    36         addUser(def);
     36        this->addUser(def);
    3737    }
    3838}
    3939
    4040void If::addDefined(Assign * def) {
    41     if (LLVM_LIKELY(std::find(mDefined.begin(), mDefined.end(), def) != mDefined.end())) {
    42         const auto size = mDefined.size();
     41    if (LLVM_LIKELY(std::find(mDefined.begin(), mDefined.end(), def) == mDefined.end())) {
    4342        mDefined.push_back(def);
    44         assert (mDefined.size() == size + 1);
    45         assert (mDefined.back() == def);
    4643        def->addUser(this);
    47         addUser(def);
     44        this->addUser(def);
     45    }
     46}
     47
     48void If::removeDefined(Assign * def) {
     49    auto f = std::find(mDefined.begin(), mDefined.end(), def);
     50    if (LLVM_LIKELY(f != mDefined.end())) {
     51        mDefined.erase(f);
     52        def->removeUser(this);
     53        this->removeUser(def);
    4854    }
    4955}
  • icGREP/icgrep-devel/icgrep/pablo/ps_if.h

    r4841 r4856  
    4848    }
    4949    void addDefined(Assign * def);
     50    void removeDefined(Assign * def);
    5051protected:
    5152    If(PabloAST * expr, const std::initializer_list<Assign *> definedVars, PabloBlock & body);
  • icGREP/icgrep-devel/icgrep/pablo/ps_while.cpp

    r4751 r4856  
    1010    for (Next * variant : nextVars) {
    1111        variant->addUser(this);
     12        this->addUser(variant);
    1213    }
    1314}
     
    1920    for (Next * variant : nextVars) {
    2021        variant->addUser(this);
     22        this->addUser(variant);
    2123    }
    2224}
Note: See TracChangeset for help on using the changeset viewer.