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

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

Initial work for incorporating Types into Pablo AST.

File size: 19.9 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
12template <typename Type>
13using SmallSet = boost::container::flat_set<Type>;
14
15using ScopeSet = SmallSet<const PabloBlock *>;
16
17/** ------------------------------------------------------------------------------------------------------------- *
18 * @brief verifyUseDefInformation
19 ** ------------------------------------------------------------------------------------------------------------- */
20template<typename VectorType>
21inline 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
31void testUsers(const PabloAST * expr, const ScopeSet & validScopes) {
32    if (isa<Count>(expr)) { // !! matchedLineCount is not being correctly added to the function !!
33        return;
34    }
35    size_t uses = 0;
36    SmallSet<const PabloAST *> verified;
37    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) {
60                        notFound = false;
61                        ++uses;
62                    }
63                }
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                }
116                ++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        }
128    }
129    if (LLVM_UNLIKELY(uses != expr->getNumUses())) {
130        std::string tmp;
131        raw_string_ostream str(tmp);
132        str << "PabloVerifier: use-def error: ";
133        PabloPrinter::print(expr, str);
134        str << " is reported having " << expr->getNumUses() << " user(s)"
135            << " but was observed having " << uses << " user(s)";
136        throw std::runtime_error(str.str());
137    }
138}
139
140void testDefs(const Statement * stmt) {
141    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
142        const PabloAST * const def = stmt->getOperand(i);
143        bool notFound = true;
144        for (const PabloAST * use : def->users()) {
145            if (use == stmt) {
146                notFound = false;
147                break;
148            }
149        }
150        if (LLVM_UNLIKELY(notFound)) {
151            std::string tmp;
152            raw_string_ostream str(tmp);
153            str << "PabloVerifier: def-use error: ";
154            PabloPrinter::print(stmt, str);
155            str << " is not recorded in ";
156            PabloPrinter::print(def, str);
157            str << "'s user list";
158            throw std::runtime_error(str.str());
159        }
160    }
161}
162
163void verifyUseDefInformation(const PabloBlock * block, const ScopeSet & validScopes) {
164    for (const Statement * stmt : *block) {
165        testUsers(stmt, validScopes);
166        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);
169        }
170    }
171}
172
173void gatherValidScopes(const PabloBlock * block, ScopeSet & validScopes) {
174    validScopes.insert(block);
175    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);
178        }
179    }
180}
181
182void verifyUseDefInformation(const PabloFunction & function) {
183    ScopeSet validScopes;
184    gatherValidScopes(function.getEntryBlock(), validScopes);
185    for (unsigned i = 0; i < function.getNumOfParameters(); ++i) {
186        testUsers(function.getParameter(i), validScopes);
187    }
188    for (unsigned i = 0; i < function.getNumOfResults(); ++i) {
189        testDefs(function.getResult(i));
190    }
191    verifyUseDefInformation(function.getEntryBlock(), validScopes);
192}
193
194/** ------------------------------------------------------------------------------------------------------------- *
195 * @brief unreachable
196 ** ------------------------------------------------------------------------------------------------------------- */
197bool unreachable(const Statement * stmt, const PabloBlock * const block) {
198    PabloBlock * parent = stmt->getParent();
199    while (parent)  {
200        if (parent == block) {
201            return false;
202        }
203        parent = parent->getPredecessor ();
204    }
205    return true;
206}
207
208/** ------------------------------------------------------------------------------------------------------------- *
209 * @brief throwUncontainedEscapedValueError
210 ** ------------------------------------------------------------------------------------------------------------- */
211static 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 ** ------------------------------------------------------------------------------------------------------------- */
224static 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());
240}
241
242/** ------------------------------------------------------------------------------------------------------------- *
243 * @brief throwReportedScopeError
244 ** ------------------------------------------------------------------------------------------------------------- */
245static void throwReportedScopeError(const Statement * const stmt) {
246    std::string tmp;
247    raw_string_ostream str(tmp);
248    str << "PabloVerifier: structure error: ";
249    PabloPrinter::print(stmt, str);
250    str << " is not contained in its reported scope block";
251    throw std::runtime_error(str.str());
252}
253
254/** ------------------------------------------------------------------------------------------------------------- *
255 * @brief throwMisreportedBranchError
256 ** ------------------------------------------------------------------------------------------------------------- */
257static void throwMisreportedBranchError(const Statement * const stmt, const Statement * const branch) {
258    std::string tmp;
259    raw_string_ostream str(tmp);
260    str << "PabloVerifier: structure error: ";
261    PabloPrinter::print(stmt, str);
262    str << " branches into a scope block that reports ";
263    PabloPrinter::print(branch, str);
264    str << " as its branching statement.";
265    throw std::runtime_error(str.str());
266}
267
268/** ------------------------------------------------------------------------------------------------------------- *
269 * @brief throwReflexiveIfConditionError
270 ** ------------------------------------------------------------------------------------------------------------- */
271static 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());
278}
279
280/** ------------------------------------------------------------------------------------------------------------- *
281 * @brief verifyProgramStructure
282 ** ------------------------------------------------------------------------------------------------------------- */
283void verifyProgramStructure(const PabloBlock * block, unsigned & nestingDepth) {
284    const Statement * prev = nullptr;
285    for (const Statement * stmt : *block) {
286        if (LLVM_UNLIKELY(stmt->getPrevNode() != prev)) {
287            std::string tmp;
288            raw_string_ostream str(tmp);
289            str << "PabloVerifier: structure error: ";
290            PabloPrinter::print(stmt, str);
291            str << " succeeds ";
292            PabloPrinter::print(prev, str);
293            str << " but expects to preceed ";
294            PabloPrinter::print(stmt->getPrevNode(), str);
295            throw std::runtime_error(str.str());
296        }
297        prev = stmt;
298        if (LLVM_UNLIKELY(stmt->getParent() != block)) {
299            std::string tmp;
300            raw_string_ostream str(tmp);
301            str << "PabloVerifier: structure error: ";
302            PabloPrinter::print(stmt, str);
303            str << " is not contained in its reported scope block";
304            throw std::runtime_error(str.str());
305        }
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();
308            if (LLVM_UNLIKELY(nested->getBranch() != stmt)) {
309                throwMisreportedBranchError(stmt, nested->getBranch());
310            } else if (LLVM_UNLIKELY(nested->getPredecessor () != block)) {
311                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                }
343            }
344            ++nestingDepth;
345            verifyProgramStructure(nested, nestingDepth);
346            --nestingDepth;
347        }
348    }   
349}
350
351inline void verifyProgramStructure(const PabloFunction & function) {
352    unsigned nestingDepth = 0;
353    verifyProgramStructure(function.getEntryBlock(), nestingDepth);
354    if (LLVM_UNLIKELY(nestingDepth != 0)) {
355        // This error isn't actually possible to occur with the current AST structure but that could change
356        // in the future. Leaving this test in for a reminder to check for it.
357        throw std::runtime_error("PabloVerifier: unbalanced If or While nesting depth.");
358    }
359}
360
361/** ------------------------------------------------------------------------------------------------------------- *
362 * @brief isTopologicallyOrdered
363 ** ------------------------------------------------------------------------------------------------------------- */
364struct OrderingVerifier {
365    OrderingVerifier() : mParent(nullptr) {}
366    OrderingVerifier(const OrderingVerifier & parent) : mParent(&parent) {}
367    bool count(const PabloAST * expr) const {
368        if (mSet.count(expr)) {
369            return true;
370        } else if (mParent) {
371            return mParent->count(expr);
372        }
373        return false;
374    }
375    void insert(const PabloAST * expr) {
376        mSet.insert(expr);
377    }
378private:
379    const OrderingVerifier * const mParent;
380    SmallSet<const PabloAST *> mSet;
381};
382
383bool 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
407void isTopologicallyOrdered(const PabloBlock * block, const OrderingVerifier & parent) {
408    OrderingVerifier ov(parent);
409    for (const Statement * stmt : *block) {
410        if (LLVM_UNLIKELY(isa<While>(stmt))) {
411            isTopologicallyOrdered(cast<While>(stmt)->getBody(), ov);
412            for (const Next * var : cast<While>(stmt)->getVariants()) {
413                ov.insert(var);
414            }
415        }
416        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
417            const PabloAST * const op = stmt->getOperand(i);
418            if (LLVM_UNLIKELY((isa<Statement>(op) || isa<Var>(op)) && ov.count(op) == 0)) {
419                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 ";
435                } else {
436                    str << " was used before definition by ";
437                }
438                PabloPrinter::print(stmt, str);
439                throw std::runtime_error(str.str());
440            }
441        }
442        ov.insert(stmt);
443        if (LLVM_UNLIKELY(isa<If>(stmt))) {
444            isTopologicallyOrdered(cast<If>(stmt)->getBody(), ov);
445            for (const Assign * def : cast<If>(stmt)->getDefined()) {
446                ov.insert(def);
447            }
448        }
449    }
450}
451
452void isTopologicallyOrdered(const PabloFunction & function) {
453    OrderingVerifier ov;
454    for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
455        ov.insert(function.getParameter(i));
456    }
457    isTopologicallyOrdered(function.getEntryBlock(), ov);
458}
459
460void PabloVerifier::verify(const PabloFunction & function, const std::string location) {
461    try {
462        verifyProgramStructure(function);
463        verifyUseDefInformation(function);
464        isTopologicallyOrdered(function);
465    } catch(std::runtime_error & err) {
466        raw_os_ostream out(std::cerr);
467        PabloPrinter::print(function, out);
468        out.flush();
469        if (location.empty()) {
470            throw err;
471        } else {
472            throw std::runtime_error(std::string(err.what()) + " @ " + location);
473        }
474    }
475}
476
477}
Note: See TracBrowser for help on using the repository browser.