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.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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);
Note: See TracChangeset for help on using the changeset viewer.