source: icGREP/icgrep-devel/icgrep/pablo/analysis/pabloverifier.cpp @ 5202

Last change on this file since 5202 was 5202, checked in by nmedfort, 3 years ago

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

File size: 16.7 KB
Line 
1#include "pabloverifier.hpp"
2#include <pablo/function.h>
3#include <pablo/codegenstate.h>
4#include <pablo/printer_pablos.h>
5#include <iostream>
6#include <boost/container/flat_set.hpp>
7#include <queue>
8
9
10namespace pablo {
11
12using TypeId = PabloAST::ClassTypeId;
13
14template <typename Type>
15using SmallSet = boost::container::flat_set<Type>;
16
17using ScopeSet = SmallSet<const PabloBlock *>;
18
19/** ------------------------------------------------------------------------------------------------------------- *
20 * @brief verifyUseDefInformation
21 ** ------------------------------------------------------------------------------------------------------------- */
22void testUsers(const PabloAST * expr, const ScopeSet & validScopes) { 
23    size_t uses = 0;
24    SmallSet<const PabloAST *> verified;
25    for (const PabloAST * use : expr->users()) {
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) {
88                        notFound = false;
89                        ++uses;
90                    }
91                }
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))) {
104                ++uses;
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);
117    }
118    if (LLVM_UNLIKELY(uses != expr->getNumUses())) {
119        std::string tmp;
120        raw_string_ostream str(tmp);
121        str << "use-def error: ";
122        PabloPrinter::print(expr, str);
123        str << " is reported having " << expr->getNumUses() << " user(s)"
124            << " but was observed having " << uses << " user(s)";
125        throw std::runtime_error(str.str());
126    }
127}
128
129void testDefs(const Statement * stmt) {
130    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
131        const PabloAST * const def = stmt->getOperand(i);
132        bool notFound = true;
133        for (const PabloAST * use : def->users()) {
134            if (use == stmt) {
135                notFound = false;
136                break;
137            }
138        }
139        if (LLVM_UNLIKELY(notFound)) {
140            std::string tmp;
141            raw_string_ostream str(tmp);
142            str << "PabloVerifier: def-use error: ";
143            PabloPrinter::print(stmt, str);
144            str << " is not recorded in ";
145            PabloPrinter::print(def, str);
146            str << "'s user list";
147            throw std::runtime_error(str.str());
148        }
149    }
150}
151
152void verifyUseDefInformation(const PabloBlock * block, const ScopeSet & validScopes) {
153    for (const Statement * stmt : *block) {
154        testUsers(stmt, validScopes);
155        testDefs(stmt);
156        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
157            verifyUseDefInformation(cast<Branch>(stmt)->getBody(), validScopes);
158        }
159    }
160}
161
162void gatherValidScopes(const PabloBlock * block, ScopeSet & validScopes) {
163    validScopes.insert(block);
164    for (const Statement * stmt : *block) {
165        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
166            gatherValidScopes(cast<Branch>(stmt)->getBody(), validScopes);
167        }
168    }
169}
170
171void verifyUseDefInformation(const PabloFunction & function) {
172    ScopeSet validScopes;
173    gatherValidScopes(function.getEntryBlock(), validScopes);
174    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        }
178        testUsers(function.getParameter(i), validScopes);
179    }
180    for (unsigned i = 0; i < function.getNumOfResults(); ++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);
185    }
186    verifyUseDefInformation(function.getEntryBlock(), validScopes);
187}
188
189/** ------------------------------------------------------------------------------------------------------------- *
190 * @brief unreachable
191 ** ------------------------------------------------------------------------------------------------------------- */
192bool unreachable(const Statement * stmt, const PabloBlock * const block) {
193    PabloBlock * parent = stmt->getParent();
194    while (parent)  {
195        if (parent == block) {
196            return false;
197        }
198        parent = parent->getPredecessor();
199    }
200    return true;
201}
202
203/** ------------------------------------------------------------------------------------------------------------- *
204 * @brief throwReportedScopeError
205 ** ------------------------------------------------------------------------------------------------------------- */
206static void throwReportedScopeError(const Statement * const stmt) {
207    std::string tmp;
208    raw_string_ostream str(tmp);
209    str << "structure error: ";
210    PabloPrinter::print(stmt, str);
211    str << " is not contained in its reported scope block";
212    throw std::runtime_error(str.str());
213}
214
215/** ------------------------------------------------------------------------------------------------------------- *
216 * @brief throwMisreportedBranchError
217 ** ------------------------------------------------------------------------------------------------------------- */
218static void throwMisreportedBranchError(const Statement * const stmt, const Statement * const branch) {
219    std::string tmp;
220    raw_string_ostream str(tmp);
221    str << "structure error: ";
222    PabloPrinter::print(stmt, str);
223    str << " branches into a scope block that reports ";
224    PabloPrinter::print(branch, str);
225    str << " as its branching statement.";
226    throw std::runtime_error(str.str());
227}
228
229/** ------------------------------------------------------------------------------------------------------------- *
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    }
246}
247
248/** ------------------------------------------------------------------------------------------------------------- *
249 * @brief verifyProgramStructure
250 ** ------------------------------------------------------------------------------------------------------------- */
251void verifyProgramStructure(const PabloBlock * block, unsigned & nestingDepth) {
252    const Statement * prev = nullptr;
253    for (const Statement * stmt : *block) {
254        if (LLVM_UNLIKELY(stmt->getPrevNode() != prev)) {
255            std::string tmp;
256            raw_string_ostream str(tmp);
257            PabloPrinter::print(stmt, str);
258            str << " succeeds ";
259            PabloPrinter::print(prev, str);
260            str << " but ";
261            PabloPrinter::print(cast<PabloAST>(stmt), str);
262            str << " expects to succeed ";
263            PabloPrinter::print(stmt->getPrevNode(), str);
264            throw std::runtime_error(str.str());
265        }
266        prev = stmt;
267        if (LLVM_UNLIKELY(stmt->getParent() != block)) {
268            std::string tmp;
269            raw_string_ostream str(tmp);
270            PabloPrinter::print(stmt, str);
271            str << " is not contained in its reported scope block";
272            throw std::runtime_error(str.str());
273        }
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();
316            if (LLVM_UNLIKELY(nested->getBranch() != stmt)) {
317                throwMisreportedBranchError(stmt, nested->getBranch());
318            } else if (LLVM_UNLIKELY(nested->getPredecessor() != block)) {
319                throwReportedScopeError(stmt);
320            }
321            ++nestingDepth;
322            verifyProgramStructure(nested, nestingDepth);
323            --nestingDepth;
324        }
325    }   
326}
327
328inline void verifyProgramStructure(const PabloFunction & function) {
329    unsigned nestingDepth = 0;
330    verifyProgramStructure(function.getEntryBlock(), nestingDepth);
331    if (LLVM_UNLIKELY(nestingDepth != 0)) {
332        // This error isn't actually possible to occur with the current AST structure but that could change
333        // in the future. Leaving this test in for a reminder to check for it.
334        throw std::runtime_error("PabloVerifier: unbalanced If or While nesting depth.");
335    }
336}
337
338/** ------------------------------------------------------------------------------------------------------------- *
339 * @brief isTopologicallyOrdered
340 ** ------------------------------------------------------------------------------------------------------------- */
341struct OrderingVerifier {
342    OrderingVerifier() : mParent(nullptr) {}
343    OrderingVerifier(const OrderingVerifier & parent) : mParent(&parent) {}
344    bool count(const PabloAST * expr) const {
345        if (mSet.count(expr)) {
346            return true;
347        } else if (mParent) {
348            return mParent->count(expr);
349        }
350        return false;
351    }
352    void insert(const PabloAST * expr) {
353        mSet.insert(expr);
354    }
355private:
356    const OrderingVerifier * const mParent;
357    SmallSet<const PabloAST *> mSet;
358};
359
360void isTopologicallyOrdered(const PabloBlock * block, const OrderingVerifier & parent) {
361    OrderingVerifier ov(parent);
362    for (const Statement * stmt : *block) {
363        if (LLVM_UNLIKELY(isa<While>(stmt))) {
364            isTopologicallyOrdered(cast<While>(stmt)->getBody(), ov);
365            for (const Var * var : cast<While>(stmt)->getEscaped()) {
366                ov.insert(var);
367            }
368        } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
369            ov.insert(cast<Assign>(stmt)->getVariable());
370        }
371        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
372            const PabloAST * const op = stmt->getOperand(i);
373            if (LLVM_UNLIKELY((isa<Statement>(op) || isa<Var>(op)) && ov.count(op) == 0)) {
374                std::string tmp;
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.";
381                } else {
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());
391            }
392        }
393        ov.insert(stmt);
394        if (LLVM_UNLIKELY(isa<If>(stmt))) {
395            isTopologicallyOrdered(cast<If>(stmt)->getBody(), ov);
396            for (const Var * def : cast<If>(stmt)->getEscaped()) {
397                ov.insert(def);
398            }
399        }
400    }
401}
402
403void isTopologicallyOrdered(const PabloFunction & function) {
404    OrderingVerifier ov;
405    for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
406        ov.insert(function.getParameter(i));
407    }
408    for (unsigned i = 0; i != function.getNumOfResults(); ++i) {
409        ov.insert(function.getResult(i));
410    }
411    isTopologicallyOrdered(function.getEntryBlock(), ov);
412}
413
414void PabloVerifier::verify(const PabloFunction & function, const std::string location) {
415    try {
416        verifyProgramStructure(function);
417        verifyUseDefInformation(function);
418        isTopologicallyOrdered(function);
419    } catch(std::runtime_error & err) {
420        raw_os_ostream out(std::cerr);
421        PabloPrinter::print(function, out);
422        out.flush();
423        if (location.empty()) {
424            llvm::report_fatal_error(err.what());
425        } else {
426            llvm::report_fatal_error(std::string(err.what()) + " @ " + location);
427        }
428    }
429}
430
431}
Note: See TracBrowser for help on using the repository browser.