Ignore:
Timestamp:
Nov 6, 2016, 8:37:11 PM (3 years ago)
Author:
nmedfort
Message:

Initial work on adding types to PabloAST and mutable Var objects.

File:
1 edited

Legend:

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

    r5160 r5202  
    1010namespace pablo {
    1111
     12using TypeId = PabloAST::ClassTypeId;
     13
    1214template <typename Type>
    1315using SmallSet = boost::container::flat_set<Type>;
     
    1820 * @brief verifyUseDefInformation
    1921 ** ------------------------------------------------------------------------------------------------------------- */
    20 template<typename VectorType>
    21 inline bool checkVector(const PabloAST * const value, const VectorType & vector, size_t & uses) {
    22     for (auto escapedValue : vector) {
    23         if (escapedValue == value) {
    24             ++uses;
    25             return false;
    26         }
    27     }
    28     return true;
    29 }
    30 
    31 void testUsers(const PabloAST * expr, const ScopeSet & validScopes) {
    32     if (isa<Count>(expr)) { // !! matchedLineCount is not being correctly added to the function !!
    33         return;
    34     }
     22void testUsers(const PabloAST * expr, const ScopeSet & validScopes) {
    3523    size_t uses = 0;
    3624    SmallSet<const PabloAST *> verified;
    3725    for (const PabloAST * use : expr->users()) {
    38         if (LLVM_LIKELY(isa<Statement>(use))) {
    39             if (LLVM_LIKELY(verified.count(use) == 0)) {
    40                 const Statement * const user = cast<Statement>(use);
    41                 // test whether this user is in a block in the program
    42                 if (LLVM_UNLIKELY(validScopes.count(user->getParent()) == 0)) {
    43                     std::string tmp;
    44                     raw_string_ostream str(tmp);
    45                     str << "PabloVerifier: use-def error: ";
    46                     PabloPrinter::print(user, str);
    47                     str << " is a user of ";
    48                     PabloPrinter::print(expr, str);
    49                     if (user->getParent() == nullptr) {
    50                         str << " but is not in any scope.";
    51                     } else {
    52                         str << " but is in a deleted scope.";
    53                     }
    54                     throw std::runtime_error(str.str());
    55                 }
    56                 // expr may be used more than once by the same user.
    57                 bool notFound = true;
    58                 for (unsigned i = 0; i != user->getNumOperands(); ++i) {
    59                     if (user->getOperand(i) == expr) {
     26        if (LLVM_UNLIKELY(verified.count(use) != 0)) {
     27            continue;
     28        }
     29        if (LLVM_UNLIKELY(isa<PabloFunction>(use))) {
     30            const PabloFunction * f = cast<PabloFunction>(use);
     31            bool isParameter = false;
     32            bool isResult = false;
     33            for (unsigned i = 0; i != f->getNumOfParameters(); ++i) {
     34                if (f->getParameter(i) == expr) {
     35                    isParameter = true;
     36                    break;
     37                }
     38            }
     39            for (unsigned i = 0; i != f->getNumOfResults(); ++i) {
     40                if (f->getResult(i) == expr) {
     41                    isResult = true;
     42                    break;
     43                }
     44            }
     45            if (LLVM_UNLIKELY(!(isParameter ^ isResult))) {
     46                std::string tmp;
     47                raw_string_ostream str(tmp);
     48                str << "use-def error: ";
     49                PabloPrinter::print(expr, str);
     50                if (isParameter && isResult) {
     51                    str << " is both a parameter and result of ";
     52                } else {
     53                    str << " is neither a parameter nor result of ";
     54                }
     55                PabloPrinter::print(f, str);
     56                throw std::runtime_error(str.str());
     57            }
     58            ++uses;
     59        } else if (const Statement * const user = dyn_cast<Statement>(use)) {
     60            // test whether this user is in a block in the program
     61            if (LLVM_UNLIKELY(user->getParent() == nullptr || validScopes.count(user->getParent()) == 0)) {
     62                std::string tmp;
     63                raw_string_ostream str(tmp);
     64                str << "use-def error: ";
     65                PabloPrinter::print(user, str);
     66                str << " is a user of ";
     67                PabloPrinter::print(expr, str);
     68                str << " but ";
     69                PabloPrinter::print(use, str);
     70                if (user->getParent() == nullptr) {
     71                    str << " is not defined in any scope.";
     72                } else {
     73                    str << " is in an unreachable scope.";
     74                }
     75                throw std::runtime_error(str.str());
     76            }
     77            // expr may be used more than once by the same user.
     78            bool notFound = true;
     79            for (unsigned i = 0; i != user->getNumOperands(); ++i) {
     80                if (user->getOperand(i) == expr) {
     81                    notFound = false;
     82                    ++uses;
     83                }
     84            }
     85            if (isa<Branch>(user)) {
     86                for (const PabloAST * var : cast<Branch>(user)->getEscaped()) {
     87                    if (var == expr) {
    6088                        notFound = false;
    6189                        ++uses;
    6290                    }
    6391                }
    64                 if (const If * ifNode = dyn_cast<If>(expr)) {
    65                     notFound &= checkVector(user, ifNode->getDefined(), uses);
    66                 } else if (const If * ifNode = dyn_cast<If>(user)) {
    67                     notFound &= checkVector(expr, ifNode->getDefined(), uses);
    68                 } else if (const While * whileNode = dyn_cast<While>(expr)) {
    69                     notFound &= checkVector(user, whileNode->getVariants(), uses);
    70                 } else if (const While * whileNode = dyn_cast<While>(user)) {
    71                     notFound &= checkVector(expr, whileNode->getVariants(), uses);
    72                 } else if (isa<Next>(expr) && isa<Assign>(use)) {
    73                     notFound &= (use != cast<Next>(expr)->getInitial());
    74                 }
    75                 if (LLVM_UNLIKELY(notFound)) {
    76                     std::string tmp;
    77                     raw_string_ostream str(tmp);
    78                     str << "PabloVerifier: use-def error: ";
    79                     PabloPrinter::print(expr, str);
    80                     str << " is not a definition of ";
    81                     PabloPrinter::print(use, str);
    82                     throw std::runtime_error(str.str());
    83                 }
    84                 verified.insert(use);
    85             }
    86         } else if (LLVM_UNLIKELY(isa<PabloFunction>(use))) {
    87             if (LLVM_LIKELY(verified.count(use) == 0)) {
    88                 const PabloFunction * f = cast<PabloFunction>(use);
    89                 bool isParameter = false;
    90                 bool isResult = false;
    91                 for (unsigned i = 0; i != f->getNumOfParameters(); ++i) {
    92                     if (f->getParameter(i) == expr) {
    93                         isParameter = true;
    94                         break;
    95                     }
    96                 }
    97                 for (unsigned i = 0; i != f->getNumOfResults(); ++i) {
    98                     if (f->getResult(i) == expr) {
    99                         isResult = true;
    100                         break;
    101                     }
    102                 }
    103                 if (LLVM_UNLIKELY(!(isParameter ^ isResult))) {
    104                     std::string tmp;
    105                     raw_string_ostream str(tmp);
    106                     str << "PabloVerifier: use-def error: ";
    107                     PabloPrinter::print(expr, str);
    108                     if (isParameter && isResult) {
    109                         str << " is both a parameter and result of ";
    110                     } else {
    111                         str << " is not a parameter or result of ";
    112                     }
    113                     PabloPrinter::print(f, str);
    114                     throw std::runtime_error(str.str());
    115                 }
     92            }
     93            if (LLVM_UNLIKELY(notFound)) {
     94                std::string tmp;
     95                raw_string_ostream str(tmp);
     96                str << "use-def error: ";
     97                PabloPrinter::print(expr, str);
     98                str << " is not a definition of ";
     99                PabloPrinter::print(use, str);
     100                throw std::runtime_error(str.str());
     101            }
     102        } else if (isa<Var>(use)) {
     103            if (LLVM_UNLIKELY(isa<Branch>(expr) || isa<PabloFunction>(expr))) {
    116104                ++uses;
    117                 verified.insert(use);
    118             }
    119         } else {
    120             std::string tmp;
    121             raw_string_ostream str(tmp);
    122             str << "PabloVerifier: use-def error: expression ";
    123             PabloPrinter::print(use, str);
    124             str << " is incorrectly reported as a user of ";
    125             PabloPrinter::print(expr, str);
    126             throw std::runtime_error(str.str());
    127         }
     105            } else {
     106                std::string tmp;
     107                raw_string_ostream str(tmp);
     108                str << "use-def error: var ";
     109                PabloPrinter::print(use, str);
     110                str << " is a user of ";
     111                PabloPrinter::print(expr, str);
     112                str << " but can only be a user of a Branch or Function.";
     113                throw std::runtime_error(str.str());
     114            }
     115        }
     116        verified.insert(use);
    128117    }
    129118    if (LLVM_UNLIKELY(uses != expr->getNumUses())) {
    130119        std::string tmp;
    131120        raw_string_ostream str(tmp);
    132         str << "PabloVerifier: use-def error: ";
     121        str << "use-def error: ";
    133122        PabloPrinter::print(expr, str);
    134123        str << " is reported having " << expr->getNumUses() << " user(s)"
     
    165154        testUsers(stmt, validScopes);
    166155        testDefs(stmt);
    167         if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    168             verifyUseDefInformation(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), validScopes);
     156        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     157            verifyUseDefInformation(cast<Branch>(stmt)->getBody(), validScopes);
    169158        }
    170159    }
     
    174163    validScopes.insert(block);
    175164    for (const Statement * stmt : *block) {
    176         if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    177             gatherValidScopes(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), validScopes);
     165        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     166            gatherValidScopes(cast<Branch>(stmt)->getBody(), validScopes);
    178167        }
    179168    }
     
    184173    gatherValidScopes(function.getEntryBlock(), validScopes);
    185174    for (unsigned i = 0; i < function.getNumOfParameters(); ++i) {
     175        if (LLVM_UNLIKELY(function.getParameter(i) == nullptr)) {
     176            throw std::runtime_error("parameter " + std::to_string(i) + " is Null!");
     177        }
    186178        testUsers(function.getParameter(i), validScopes);
    187179    }
    188180    for (unsigned i = 0; i < function.getNumOfResults(); ++i) {
    189         testDefs(function.getResult(i));
     181        if (LLVM_UNLIKELY(function.getResult(i) == nullptr)) {
     182            throw std::runtime_error("result " + std::to_string(i) + " is Null!");
     183        }
     184        testUsers(function.getResult(i), validScopes);
    190185    }
    191186    verifyUseDefInformation(function.getEntryBlock(), validScopes);
     
    201196            return false;
    202197        }
    203         parent = parent->getPredecessor ();
     198        parent = parent->getPredecessor();
    204199    }
    205200    return true;
    206 }
    207 
    208 /** ------------------------------------------------------------------------------------------------------------- *
    209  * @brief throwUncontainedEscapedValueError
    210  ** ------------------------------------------------------------------------------------------------------------- */
    211 static void throwUncontainedEscapedValueError(const Statement * const stmt, const PabloAST * const value) {
    212     std::string tmp;
    213     raw_string_ostream str(tmp);
    214     str << "PabloVerifier: structure error: escaped value \"";
    215     PabloPrinter::print(value, str);
    216     str << "\" is not contained within the body of ";
    217     PabloPrinter::print(stmt, str);
    218     throw std::runtime_error(str.str());
    219 }
    220 
    221 /** ------------------------------------------------------------------------------------------------------------- *
    222  * @brief throwEscapedValueUsageError
    223  ** ------------------------------------------------------------------------------------------------------------- */
    224 static void throwEscapedValueUsageError(const Statement * const stmt, const PabloAST * const value, const PabloAST * const def, const PabloAST * const user, const unsigned count) {
    225     std::string tmp;
    226     raw_string_ostream str(tmp);
    227     str << "PabloVerifier: structure error: ";
    228     PabloPrinter::print(value, str);
    229     str << " is an escaped value of ";
    230     PabloPrinter::print(stmt, str);
    231     str << " but ";
    232     PabloPrinter::print(user, str);
    233     if (count == 0) {
    234         str << " is not considered a user of ";
    235     } else if (count > 0) {
    236         str << " was recorded too many times (" << count << ") in the user list of ";
    237     }
    238     PabloPrinter::print(def, str);
    239     throw std::runtime_error(str.str());
    240201}
    241202
     
    246207    std::string tmp;
    247208    raw_string_ostream str(tmp);
    248     str << "PabloVerifier: structure error: ";
     209    str << "structure error: ";
    249210    PabloPrinter::print(stmt, str);
    250211    str << " is not contained in its reported scope block";
     
    258219    std::string tmp;
    259220    raw_string_ostream str(tmp);
    260     str << "PabloVerifier: structure error: ";
     221    str << "structure error: ";
    261222    PabloPrinter::print(stmt, str);
    262223    str << " branches into a scope block that reports ";
     
    267228
    268229/** ------------------------------------------------------------------------------------------------------------- *
    269  * @brief throwReflexiveIfConditionError
    270  ** ------------------------------------------------------------------------------------------------------------- */
    271 static void throwReflexiveIfConditionError(const PabloAST * const ifNode) {
    272     std::string tmp;
    273     raw_string_ostream str(tmp);
    274     str << "PabloVerifier: structure error: the condition of ";
    275     PabloPrinter::print(ifNode, str);
    276     str << " cannot be defined by the If node itself.";
    277     throw std::runtime_error(str.str());
     230 * @brief illegalOperandType
     231 ** ------------------------------------------------------------------------------------------------------------- */
     232static inline bool illegalOperandType(const PabloAST * const op) {
     233    switch (op->getClassTypeId()) {
     234        case TypeId::Block:
     235        case TypeId::Function:
     236        case TypeId::Prototype:
     237        case TypeId::Assign:
     238        case TypeId::Call:
     239        case TypeId::SetIthBit:
     240        case TypeId::If:
     241        case TypeId::While:
     242            return true;
     243        default:
     244            return false;
     245    }
    278246}
    279247
     
    287255            std::string tmp;
    288256            raw_string_ostream str(tmp);
    289             str << "PabloVerifier: structure error: ";
    290257            PabloPrinter::print(stmt, str);
    291258            str << " succeeds ";
    292259            PabloPrinter::print(prev, str);
    293             str << " but expects to preceed ";
     260            str << " but ";
     261            PabloPrinter::print(cast<PabloAST>(stmt), str);
     262            str << " expects to succeed ";
    294263            PabloPrinter::print(stmt->getPrevNode(), str);
    295264            throw std::runtime_error(str.str());
     
    299268            std::string tmp;
    300269            raw_string_ostream str(tmp);
    301             str << "PabloVerifier: structure error: ";
    302270            PabloPrinter::print(stmt, str);
    303271            str << " is not contained in its reported scope block";
    304272            throw std::runtime_error(str.str());
    305273        }
    306         if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    307             const PabloBlock * nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     274
     275        for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
     276            PabloAST * op = stmt->getOperand(i);
     277            if (LLVM_UNLIKELY(illegalOperandType(op))) {
     278                std::string tmp;
     279                raw_string_ostream str(tmp);
     280                PabloPrinter::print(op, str);
     281                str << " cannot be an operand of ";
     282                PabloPrinter::print(stmt, str);
     283                throw std::runtime_error(str.str());
     284            }
     285        }
     286
     287        if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     288
     289            PabloAST * const variable = cast<Assign>(stmt)->getVariable();
     290            if (LLVM_UNLIKELY(!isa<Var>(variable) && !isa<Extract>(variable))) {
     291                std::string tmp;
     292                raw_string_ostream out(tmp);
     293                out << "invalid assignment: ";
     294                PabloPrinter::print(stmt, out);
     295                out << "  --- ";
     296                PabloPrinter::print(variable, out);
     297                out << " must be a Var or Extract";
     298                throw std::runtime_error(out.str());
     299            }
     300
     301            PabloAST * const value = cast<Assign>(stmt)->getValue();
     302            if (LLVM_UNLIKELY(variable->getType() != value->getType())) {
     303                std::string tmp;
     304                raw_string_ostream out(tmp);
     305                out << "invalid assignment: ";
     306                PabloPrinter::print(stmt, out);
     307                out << "  --- type of ";
     308                PabloPrinter::print(variable, out);
     309                out << " differs from ";
     310                PabloPrinter::print(value, out);
     311                throw std::runtime_error(out.str());
     312            }
     313
     314        } else if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     315            const PabloBlock * nested = cast<Branch>(stmt)->getBody();
    308316            if (LLVM_UNLIKELY(nested->getBranch() != stmt)) {
    309317                throwMisreportedBranchError(stmt, nested->getBranch());
    310             } else if (LLVM_UNLIKELY(nested->getPredecessor () != block)) {
     318            } else if (LLVM_UNLIKELY(nested->getPredecessor() != block)) {
    311319                throwReportedScopeError(stmt);
    312             }
    313             if (isa<If>(stmt)) {
    314                 for (const Assign * def : cast<If>(stmt)->getDefined()) {
    315                     if (LLVM_UNLIKELY(def == cast<If>(stmt)->getCondition())) {
    316                         throwReflexiveIfConditionError(stmt);
    317                     } else if (LLVM_UNLIKELY(unreachable(def, nested))) {
    318                         throwUncontainedEscapedValueError(stmt, def);
    319                     }
    320                     unsigned count = std::count(stmt->user_begin(), stmt->user_end(), def);
    321                     if (LLVM_UNLIKELY(count != 1)) {
    322                         throwEscapedValueUsageError(stmt, def, stmt, def, count);
    323                     }
    324                     count = std::count(def->user_begin(), def->user_end(), stmt);
    325                     if (LLVM_UNLIKELY(count != 1)) {
    326                         throwEscapedValueUsageError(stmt, def, def, stmt, count);
    327                     }
    328                 }
    329             } else {
    330                 for (const Next * var : cast<While>(stmt)->getVariants()) {
    331                     if (LLVM_UNLIKELY(unreachable(var, nested))) {
    332                         throwUncontainedEscapedValueError(stmt, var);
    333                     }
    334                     unsigned count = std::count(stmt->user_begin(), stmt->user_end(), var);
    335                     if (LLVM_UNLIKELY(count != 1)) {
    336                         throwEscapedValueUsageError(stmt, var, stmt, var, count);
    337                     }
    338                     count = std::count(var->user_begin(), var->user_end(), stmt);
    339                     if (LLVM_UNLIKELY(count != ((cast<While>(stmt)->getCondition() == var) ? 2 : 1))) {
    340                         throwEscapedValueUsageError(stmt, var, var, stmt, count);
    341                     }
    342                 }
    343320            }
    344321            ++nestingDepth;
     
    381358};
    382359
    383 bool recursivelyDefined(const Statement * const stmt) {
    384     std::queue<const Statement *> Q;
    385     SmallSet<const PabloAST *> V;
    386     V.insert(stmt);
    387     for (const Statement * ancestor = stmt;;) {
    388         for (unsigned i = 0; i != ancestor->getNumOperands(); ++i) {
    389             const PabloAST * op = ancestor->getOperand(i);
    390             if (isa<Statement>(op) && V.count(op) == 0) {
    391                 if (op == stmt) {
    392                     return true;
    393                 }
    394                 Q.push(cast<Statement>(op));
    395                 V.insert(op);
    396             }
    397         }
    398         if (LLVM_UNLIKELY(Q.empty())) {
    399             break;
    400         }
    401         ancestor = Q.front();
    402         Q.pop();
    403     }
    404     return false;
    405 }
    406 
    407360void isTopologicallyOrdered(const PabloBlock * block, const OrderingVerifier & parent) {
    408361    OrderingVerifier ov(parent);
     
    410363        if (LLVM_UNLIKELY(isa<While>(stmt))) {
    411364            isTopologicallyOrdered(cast<While>(stmt)->getBody(), ov);
    412             for (const Next * var : cast<While>(stmt)->getVariants()) {
     365            for (const Var * var : cast<While>(stmt)->getEscaped()) {
    413366                ov.insert(var);
    414367            }
     368        } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     369            ov.insert(cast<Assign>(stmt)->getVariable());
    415370        }
    416371        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     
    418373            if (LLVM_UNLIKELY((isa<Statement>(op) || isa<Var>(op)) && ov.count(op) == 0)) {
    419374                std::string tmp;
    420                 raw_string_ostream str(tmp);
    421                 str << "PabloVerifier: ordering volation: ";
    422                 if (LLVM_UNLIKELY(recursivelyDefined(stmt))) {
    423                     PabloPrinter::print(stmt, str);
    424                     str << " is defined by a recursive function!";
    425                     throw std::runtime_error(str.str());
    426                 }
    427                 // TODO: make this actually test whether the operand is ever defined,
    428                 // or if it was defined in a scope that cannot be reached?
    429 
    430                 str << "function is not topologically ordered! ";
    431                 PabloAST * op = stmt->getOperand(i);
    432                 PabloPrinter::print(op, str);
    433                 if (LLVM_UNLIKELY(isa<Statement>(op) && unreachable(stmt, cast<Statement>(op)->getParent()))) {
    434                     str << " was defined in a scope that is unreachable by ";
     375                raw_string_ostream out(tmp);
     376                if (isa<Var>(op)) {
     377                    PabloPrinter::print(op, out);
     378                    out << " is used by ";
     379                    PabloPrinter::print(stmt, out);
     380                    out << " before being assigned a value.";
    435381                } else {
    436                     str << " was used before definition by ";
    437                 }
    438                 PabloPrinter::print(stmt, str);
    439                 throw std::runtime_error(str.str());
     382                    PabloPrinter::print(op, out);
     383                    if (LLVM_UNLIKELY(isa<Statement>(op) && unreachable(stmt, cast<Statement>(op)->getParent()))) {
     384                        out << " was defined in a scope that is unreachable by ";
     385                    } else {
     386                        out << " was used before definition by ";
     387                    }
     388                    PabloPrinter::print(stmt, out);
     389                }
     390                throw std::runtime_error(out.str());
    440391            }
    441392        }
     
    443394        if (LLVM_UNLIKELY(isa<If>(stmt))) {
    444395            isTopologicallyOrdered(cast<If>(stmt)->getBody(), ov);
    445             for (const Assign * def : cast<If>(stmt)->getDefined()) {
     396            for (const Var * def : cast<If>(stmt)->getEscaped()) {
    446397                ov.insert(def);
    447398            }
     
    454405    for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
    455406        ov.insert(function.getParameter(i));
     407    }
     408    for (unsigned i = 0; i != function.getNumOfResults(); ++i) {
     409        ov.insert(function.getResult(i));
    456410    }
    457411    isTopologicallyOrdered(function.getEntryBlock(), ov);
     
    468422        out.flush();
    469423        if (location.empty()) {
    470             throw err;
     424            llvm::report_fatal_error(err.what());
    471425        } else {
    472             throw std::runtime_error(std::string(err.what()) + " @ " + location);
    473         }
    474     }
    475 }
    476 
    477 }
     426            llvm::report_fatal_error(std::string(err.what()) + " @ " + location);
     427        }
     428    }
     429}
     430
     431}
Note: See TracChangeset for help on using the changeset viewer.