Ignore:
Timestamp:
Sep 27, 2015, 1:32:27 AM (4 years ago)
Author:
nmedfort
Message:

Progress on multi-target UCD compiler.

File:
1 edited

Legend:

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

    r4775 r4797  
    55#include <iostream>
    66#include <boost/container/flat_set.hpp>
     7#include <boost/container/flat_map.hpp>
     8
     9using namespace boost::container;
    710
    811namespace pablo {
    912
     13using ScopeSet = flat_set<const PabloBlock *>;
     14
     15/** ------------------------------------------------------------------------------------------------------------- *
     16 * @brief verifyUseDefInformation
     17 ** ------------------------------------------------------------------------------------------------------------- */
     18template<typename VectorType>
     19bool checkVector(const Statement * value, const VectorType & vector) {
     20    for (auto escapedValue : vector) {
     21        if (escapedValue == value) {
     22            return false;
     23        }
     24    }
     25    return true;
     26}
     27
     28void verifyUseDefInformation(const PabloBlock & block, const ScopeSet & validScopes) {
     29    for (const Statement * stmt : block) {
     30
     31        for (const PabloAST * use : stmt->users()) {
     32            if (LLVM_LIKELY(isa<Statement>(use))) {
     33                const Statement * const user = cast<Statement>(use);
     34                // test whether this user is in a block in the program
     35                if (LLVM_UNLIKELY(validScopes.count(user->getParent()) == 0)) {
     36                    std::string tmp;
     37                    raw_string_ostream str(tmp);
     38                    PabloPrinter::print(user, "PabloVerifier: use-def error: ", str);
     39                    PabloPrinter::print(stmt, " is a user of ", str);
     40                    if (user->getParent() == nullptr) {
     41                        str << " but is not in any scope.";
     42                    } else {
     43                        str << " but is in a deleted scope.";
     44                    }
     45                    throw std::runtime_error(str.str());
     46                }
     47                bool notFound = true;
     48                for (unsigned i = 0; i != user->getNumOperands(); ++i) {
     49                    if (user->getOperand(i) == stmt) {
     50                        notFound = false;
     51                        break;
     52                    }
     53                }
     54                if (LLVM_UNLIKELY(notFound)) {
     55                    if (const If * ifNode = dyn_cast<If>(stmt)) {
     56                        notFound = checkVector(user, ifNode->getDefined());
     57                    } else if (const If * ifNode = dyn_cast<If>(user)) {
     58                        notFound = checkVector(stmt, ifNode->getDefined());
     59                    } else if (const While * whileNode = dyn_cast<While>(stmt)) {
     60                        notFound = checkVector(user, whileNode->getVariants());
     61                    } else if (const While * whileNode = dyn_cast<While>(user)) {
     62                        notFound = checkVector(stmt, whileNode->getVariants());
     63                    } else if (isa<Next>(stmt) && isa<Assign>(use)) {
     64                        notFound = (use != cast<Next>(stmt)->getInitial());
     65                    }
     66                    if (LLVM_UNLIKELY(notFound)) {
     67                        std::string tmp;
     68                        raw_string_ostream str(tmp);
     69                        str << "PabloVerifier: use-def error: ";
     70                        PabloPrinter::print(stmt, str);
     71                        str << " is not a definition of ";
     72                        PabloPrinter::print(use, str);
     73                        throw std::runtime_error(str.str());
     74                    }
     75                }
     76            }
     77        }
     78        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     79            const PabloAST * const def = stmt->getOperand(i);
     80            bool notFound = true;
     81            for (const PabloAST * use : def->users()) {
     82                if (use == stmt) {
     83                    notFound = false;
     84                    break;
     85                }
     86            }
     87            if (LLVM_UNLIKELY(notFound)) {
     88                std::string tmp;
     89                raw_string_ostream str(tmp);
     90                PabloPrinter::print(stmt, "PabloVerifier: def-use error: ", str);
     91                str << " is not a user of ";
     92                PabloPrinter::print(def, str);
     93                throw std::runtime_error(str.str());
     94            }
     95        }
     96        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     97            verifyUseDefInformation(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), validScopes);
     98        }
     99    }
     100}
     101
     102void gatherValidScopes(const PabloBlock & block, ScopeSet & validScopes) {
     103    validScopes.insert(&block);
     104    for (const Statement * stmt : block) {
     105        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     106            gatherValidScopes(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), validScopes);
     107        }
     108    }
     109}
     110
     111void verifyUseDefInformation(const PabloFunction & function) {
     112    ScopeSet validScopes;
     113    gatherValidScopes(function.getEntryBlock(), validScopes);
     114    verifyUseDefInformation(function.getEntryBlock(), validScopes);
     115}
     116
     117/** ------------------------------------------------------------------------------------------------------------- *
     118 * @brief verifyProgramStructure
     119 ** ------------------------------------------------------------------------------------------------------------- */
     120void verifyProgramStructure(const PabloBlock & block) {
     121    const Statement * prev = nullptr;
     122    for (const Statement * stmt : block) {
     123        if (LLVM_UNLIKELY(stmt->getPrevNode() != prev)) {
     124            std::string tmp;
     125            raw_string_ostream str(tmp);
     126            PabloPrinter::print(stmt, "PabloVerifier: structure error: ", str);
     127            str << " succeeds ";
     128            PabloPrinter::print(prev, str);
     129            str << " but expects to preceed  ";
     130            PabloPrinter::print(stmt->getPrevNode(), str);
     131            throw std::runtime_error(str.str());
     132        }
     133        prev = stmt;
     134        if (LLVM_UNLIKELY(stmt->getParent() != &block)) {
     135            std::string tmp;
     136            raw_string_ostream str(tmp);
     137            PabloPrinter::print(stmt, "PabloVerifier: structure error: ", str);
     138            str << " is not contained in its reported scope block";
     139            throw std::runtime_error(str.str());
     140        }
     141        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     142            const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     143            if (LLVM_UNLIKELY(nested.getParent() != &block)) {
     144                std::string tmp;
     145                raw_string_ostream str(tmp);
     146                str << "PabloVerifier: structure error: body of ";
     147                PabloPrinter::print(stmt, str);
     148                str << " is not nested within the expected scope block";
     149                throw std::runtime_error(str.str());
     150            }
     151            const Statement * misreportedEscapingValue = nullptr;
     152            if (isa<If>(stmt)) {
     153                for (const Assign * def : cast<If>(stmt)->getDefined()) {
     154                    if (def->getParent() != &block) {
     155                        misreportedEscapingValue = def;
     156                        break;
     157                    }
     158                }
     159            } else {
     160                for (const Next * var : cast<While>(stmt)->getVariants()) {
     161                    if (var->getParent() != &block) {
     162                        misreportedEscapingValue = var;
     163                        break;
     164                    }
     165                }
     166            }
     167            if (misreportedEscapingValue) {
     168                std::string tmp;
     169                raw_string_ostream str(tmp);
     170                str << "PabloVerifier: structure error: ";
     171                PabloPrinter::print(misreportedEscapingValue, str);
     172                str << " is not contained within the body of ";
     173                PabloPrinter::print(stmt, str);
     174                throw std::runtime_error(str.str());
     175            }
     176            verifyProgramStructure(nested);
     177        }
     178    }
     179}
     180
     181inline void verifyProgramStructure(const PabloFunction & function) {
     182    verifyProgramStructure(function.getEntryBlock());
     183}
     184
     185/** ------------------------------------------------------------------------------------------------------------- *
     186 * @brief isTopologicallyOrdered
     187 ** ------------------------------------------------------------------------------------------------------------- */
    10188struct OrderingVerifier {
    11189    OrderingVerifier() : mParent(nullptr) {}
     
    27205};
    28206
    29 void isTopologicallyOrdered(const PabloBlock & block, const OrderingVerifier & parent, const bool ignoreUnusedStatements) {
     207void isTopologicallyOrdered(const PabloBlock & block, const OrderingVerifier & parent) {
    30208    OrderingVerifier ov(parent);
    31     const Statement * previousStatement = nullptr;
    32     for (const Statement * stmt : block) {
    33         if (stmt->getPrevNode() != previousStatement) {
    34             // TODO: make this actually test whether the operand is ever defined,
    35             // or if it was defined in a scope that cannot be reached?
    36             std::string tmp;
    37             raw_string_ostream str(tmp);
    38             PabloPrinter::print(stmt, "PabloVerifier: ", str);
    39             str << " is not preceeded by the expected statement!";
    40             throw std::runtime_error(str.str());
    41         }
    42         previousStatement = stmt;
    43         if (stmt->getNumUses() == 0 && ignoreUnusedStatements) {
    44             continue;
    45         }
     209    for (const Statement * stmt : block) {
    46210        if (LLVM_UNLIKELY(isa<While>(stmt))) {
    47             isTopologicallyOrdered(cast<While>(stmt)->getBody(), ov, ignoreUnusedStatements);
     211            isTopologicallyOrdered(cast<While>(stmt)->getBody(), ov);
    48212            for (const Next * var : cast<While>(stmt)->getVariants()) {
    49213                ov.insert(var);
     
    51215        }
    52216        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    53             const PabloAST * op = stmt->getOperand(i);
    54             if ((isa<Statement>(op) || isa<Var>(op)) && ov.count(op) == false) {
     217            const PabloAST * const op = stmt->getOperand(i);
     218            if (LLVM_UNLIKELY((isa<Statement>(op) || isa<Var>(op)) && ov.count(op) == 0)) {
    55219                // TODO: make this actually test whether the operand is ever defined,
    56220                // or if it was defined in a scope that cannot be reached?
     
    65229        ov.insert(stmt);
    66230        if (LLVM_UNLIKELY(isa<If>(stmt))) {
    67             isTopologicallyOrdered(cast<If>(stmt)->getBody(), ov, ignoreUnusedStatements);
     231            isTopologicallyOrdered(cast<If>(stmt)->getBody(), ov);
    68232            for (const Assign * def : cast<If>(stmt)->getDefined()) {
    69233                ov.insert(def);
     
    73237}
    74238
    75 void isTopologicallyOrdered(const PabloFunction & function, const bool ignoreUnusedStatements) {
     239void isTopologicallyOrdered(const PabloFunction & function) {
    76240    OrderingVerifier ov;
    77241    for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
    78242        ov.insert(function.getParameter(i));
    79243    }
    80     isTopologicallyOrdered(function.getEntryBlock(), ov, ignoreUnusedStatements);
    81 }
    82 
    83 void PabloVerifier::verify(const PabloFunction & function, const bool ignoreUnusedStatements) {
     244    isTopologicallyOrdered(function.getEntryBlock(), ov);
     245}
     246
     247void PabloVerifier::verify(const PabloFunction & function, const std::string location) {
    84248    try {
    85         isTopologicallyOrdered(function, ignoreUnusedStatements);
     249        verifyProgramStructure(function);
     250        verifyUseDefInformation(function);
     251        isTopologicallyOrdered(function);
    86252    } catch(std::runtime_error err) {
    87253        raw_os_ostream out(std::cerr);
    88254        PabloPrinter::print(function.getEntryBlock().statements(), out);
    89255        out.flush();
    90         throw err;
    91     }
    92 }
    93 
    94 }
     256        if (location.empty()) {
     257            throw err;
     258        } else {
     259            throw std::runtime_error(std::string(err.what()) + " @ " + location);
     260        }
     261    }
     262}
     263
     264}
Note: See TracChangeset for help on using the changeset viewer.