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

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

Initial modifications to Pablo Compiler and Kernel Builder to support circular buffers for Lookahead.

File size: 17.3 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#ifdef USE_BOOST
7#include <boost/container/flat_set.hpp>
8#else
9#include <unordered_set>
10#endif
11#include <queue>
12
13
14namespace pablo {
15
16#ifdef USE_BOOST
17template <typename Type>
18using SmallSet = boost::container::flat_set<Type>;
19#else
20template <typename Type>
21using SmallSet = std::unordered_set<Type>;
22#endif
23
24using ScopeSet = SmallSet<const PabloBlock *>;
25
26/** ------------------------------------------------------------------------------------------------------------- *
27 * @brief verifyUseDefInformation
28 ** ------------------------------------------------------------------------------------------------------------- */
29template<typename VectorType>
30bool checkVector(const Statement * value, const VectorType & vector) {
31    for (auto escapedValue : vector) {
32        if (escapedValue == value) {
33            return false;
34        }
35    }
36    return true;
37}
38
39void verifyUseDefInformation(const PabloBlock * block, const ScopeSet & validScopes) {
40    for (const Statement * stmt : *block) {
41        for (const PabloAST * use : stmt->users()) {
42            if (LLVM_LIKELY(isa<Statement>(use))) {
43                const Statement * const user = cast<Statement>(use);
44                // test whether this user is in a block in the program
45                if (LLVM_UNLIKELY(validScopes.count(user->getParent()) == 0)) {
46                    std::string tmp;
47                    raw_string_ostream str(tmp);
48                    str << "PabloVerifier: use-def error: ";
49                    PabloPrinter::print(user, str);
50                    str << " is a user of ";
51                    PabloPrinter::print(stmt, str);
52                    if (user->getParent() == nullptr) {
53                        str << " but is not in any scope.";
54                    } else {
55                        str << " but is in a deleted scope.";
56                    }
57                    throw std::runtime_error(str.str());
58                }
59                bool notFound = true;
60                for (unsigned i = 0; i != user->getNumOperands(); ++i) {
61                    if (user->getOperand(i) == stmt) {
62                        notFound = false;
63                        break;
64                    }
65                }
66                if (LLVM_UNLIKELY(notFound)) {
67                    if (const If * ifNode = dyn_cast<If>(stmt)) {
68                        notFound = checkVector(user, ifNode->getDefined());
69                    } else if (const If * ifNode = dyn_cast<If>(user)) {
70                        notFound = checkVector(stmt, ifNode->getDefined());
71                    } else if (const While * whileNode = dyn_cast<While>(stmt)) {
72                        notFound = checkVector(user, whileNode->getVariants());
73                    } else if (const While * whileNode = dyn_cast<While>(user)) {
74                        notFound = checkVector(stmt, whileNode->getVariants());
75                    } else if (isa<Next>(stmt) && isa<Assign>(use)) {
76                        notFound = (use != cast<Next>(stmt)->getInitial());
77                    }
78                    if (LLVM_UNLIKELY(notFound)) {
79                        std::string tmp;
80                        raw_string_ostream str(tmp);
81                        str << "PabloVerifier: use-def error: ";
82                        PabloPrinter::print(stmt, str);
83                        str << " is not a definition of ";
84                        PabloPrinter::print(use, str);
85                        throw std::runtime_error(str.str());
86                    }
87                }
88            }
89        }
90        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
91            const PabloAST * const def = stmt->getOperand(i);
92            bool notFound = true;
93            for (const PabloAST * use : def->users()) {
94                if (use == stmt) {
95                    notFound = false;
96                    break;
97                }
98            }
99            if (LLVM_UNLIKELY(notFound)) {
100                std::string tmp;
101                raw_string_ostream str(tmp);
102                str << "PabloVerifier: def-use error: ";
103                PabloPrinter::print(stmt, str);
104                str << " is not recorded in ";
105                PabloPrinter::print(def, str);
106                str << "'s user list";
107                throw std::runtime_error(str.str());
108            }
109        }
110        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
111            verifyUseDefInformation(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), validScopes);
112        }
113    }
114}
115
116void gatherValidScopes(const PabloBlock * block, ScopeSet & validScopes) {
117    validScopes.insert(block);
118    for (const Statement * stmt : *block) {
119        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
120            gatherValidScopes(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), validScopes);
121        }
122    }
123}
124
125void verifyUseDefInformation(const PabloFunction & function) {
126    ScopeSet validScopes;
127    gatherValidScopes(function.getEntryBlock(), validScopes);
128    verifyUseDefInformation(function.getEntryBlock(), validScopes);
129}
130
131/** ------------------------------------------------------------------------------------------------------------- *
132 * @brief unreachable
133 ** ------------------------------------------------------------------------------------------------------------- */
134bool unreachable(const Statement * stmt, const PabloBlock * const block) {
135    PabloBlock * parent = stmt->getParent();
136    while (parent)  {
137        if (parent == block) {
138            return false;
139        }
140        parent = parent->getParent();
141    }
142    return true;
143}
144
145/** ------------------------------------------------------------------------------------------------------------- *
146 * @brief throwUncontainedEscapedValueError
147 ** ------------------------------------------------------------------------------------------------------------- */
148static void throwUncontainedEscapedValueError(const Statement * const stmt, const PabloAST * const value) {
149    std::string tmp;
150    raw_string_ostream str(tmp);
151    str << "PabloVerifier: structure error: escaped value \"";
152    PabloPrinter::print(value, str);
153    str << "\" is not contained within the body of ";
154    PabloPrinter::print(stmt, str);
155    throw std::runtime_error(str.str());
156}
157
158/** ------------------------------------------------------------------------------------------------------------- *
159 * @brief throwEscapedValueUsageError
160 ** ------------------------------------------------------------------------------------------------------------- */
161static void throwEscapedValueUsageError(const Statement * const stmt, const PabloAST * const value, const PabloAST * const def, const PabloAST * const user, const unsigned count) {
162    std::string tmp;
163    raw_string_ostream str(tmp);
164    str << "PabloVerifier: structure error: ";
165    PabloPrinter::print(value, str);
166    str << " is an escaped value of ";
167    PabloPrinter::print(stmt, str);
168    str << " but ";
169    PabloPrinter::print(user, str);
170    if (count == 0) {
171        str << " is not considered a user of ";
172    } else if (count > 0) {
173        str << " was recorded too many times (" << count << ") in the user list of ";
174    }
175    PabloPrinter::print(def, str);
176    throw std::runtime_error(str.str());
177}
178
179/** ------------------------------------------------------------------------------------------------------------- *
180 * @brief throwReportedScopeError
181 ** ------------------------------------------------------------------------------------------------------------- */
182static void throwReportedScopeError(const Statement * const stmt) {
183    std::string tmp;
184    raw_string_ostream str(tmp);
185    str << "PabloVerifier: structure error: ";
186    PabloPrinter::print(stmt, str);
187    str << " is not contained in its reported scope block";
188    throw std::runtime_error(str.str());
189}
190
191/** ------------------------------------------------------------------------------------------------------------- *
192 * @brief throwMisreportedBranchError
193 ** ------------------------------------------------------------------------------------------------------------- */
194static void throwMisreportedBranchError(const Statement * const stmt, const Statement * const branch) {
195    std::string tmp;
196    raw_string_ostream str(tmp);
197    str << "PabloVerifier: structure error: ";
198    PabloPrinter::print(stmt, str);
199    str << " branches into a scope block that reports ";
200    PabloPrinter::print(stmt, str);
201    str << " as its branching statement.";
202    throw std::runtime_error(str.str());
203}
204
205/** ------------------------------------------------------------------------------------------------------------- *
206 * @brief throwReflexiveIfConditionError
207 ** ------------------------------------------------------------------------------------------------------------- */
208static void throwReflexiveIfConditionError(const PabloAST * const ifNode) {
209    std::string tmp;
210    raw_string_ostream str(tmp);
211    str << "PabloVerifier: structure error: the condition of ";
212    PabloPrinter::print(ifNode, str);
213    str << " cannot be defined by the If node itself.";
214    throw std::runtime_error(str.str());
215}
216
217/** ------------------------------------------------------------------------------------------------------------- *
218 * @brief verifyProgramStructure
219 ** ------------------------------------------------------------------------------------------------------------- */
220void verifyProgramStructure(const PabloBlock * block, unsigned & nestingDepth) {
221    const Statement * prev = nullptr;
222    for (const Statement * stmt : *block) {
223        if (LLVM_UNLIKELY(stmt->getPrevNode() != prev)) {
224            std::string tmp;
225            raw_string_ostream str(tmp);
226            str << "PabloVerifier: structure error: ";
227            PabloPrinter::print(stmt, str);
228            str << " succeeds ";
229            PabloPrinter::print(prev, str);
230            str << " but expects to preceed ";
231            PabloPrinter::print(stmt->getPrevNode(), str);
232            throw std::runtime_error(str.str());
233        }
234        prev = stmt;
235        if (LLVM_UNLIKELY(stmt->getParent() != block)) {
236            std::string tmp;
237            raw_string_ostream str(tmp);
238            str << "PabloVerifier: structure error: ";
239            PabloPrinter::print(stmt, str);
240            str << " is not contained in its reported scope block";
241            throw std::runtime_error(str.str());
242        }
243        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
244            const PabloBlock * nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
245            if (LLVM_UNLIKELY(nested->getBranch() != stmt)) {
246                throwMisreportedBranchError(stmt, nested->getBranch());
247            } else if (LLVM_UNLIKELY(nested->getParent() != block)) {
248                throwReportedScopeError(stmt);
249            }
250            if (isa<If>(stmt)) {
251                for (const Assign * def : cast<If>(stmt)->getDefined()) {
252                    if (LLVM_UNLIKELY(def == cast<If>(stmt)->getCondition())) {
253                        throwReflexiveIfConditionError(stmt);
254                    } else if (LLVM_UNLIKELY(unreachable(def, nested))) {
255                        throwUncontainedEscapedValueError(stmt, def);
256                    }
257                    unsigned count = std::count(stmt->user_begin(), stmt->user_end(), def);
258                    if (LLVM_UNLIKELY(count != 1)) {
259                        throwEscapedValueUsageError(stmt, def, stmt, def, count);
260                    }
261                    count = std::count(def->user_begin(), def->user_end(), stmt);
262                    if (LLVM_UNLIKELY(count != 1)) {
263                        throwEscapedValueUsageError(stmt, def, def, stmt, count);
264                    }
265                }
266            } else {
267                for (const Next * var : cast<While>(stmt)->getVariants()) {
268                    if (LLVM_UNLIKELY(unreachable(var, nested))) {
269                        throwUncontainedEscapedValueError(stmt, var);
270                    }
271                    unsigned count = std::count(stmt->user_begin(), stmt->user_end(), var);
272                    if (LLVM_UNLIKELY(count != 1)) {
273                        throwEscapedValueUsageError(stmt, var, stmt, var, count);
274                    }
275                    count = std::count(var->user_begin(), var->user_end(), stmt);
276                    if (LLVM_UNLIKELY(count != ((cast<While>(stmt)->getCondition() == var) ? 2 : 1))) {
277                        throwEscapedValueUsageError(stmt, var, var, stmt, count);
278                    }
279                }
280            }
281            ++nestingDepth;
282            verifyProgramStructure(nested, nestingDepth);
283            --nestingDepth;
284        }
285    }   
286}
287
288inline void verifyProgramStructure(const PabloFunction & function) {
289    unsigned nestingDepth = 0;
290    verifyProgramStructure(function.getEntryBlock(), nestingDepth);
291    if (LLVM_UNLIKELY(nestingDepth != 0)) {
292        // This error isn't actually possible to occur with the current AST structure but that could change
293        // in the future. Leaving this test in for a reminder to check for it.
294        throw std::runtime_error("PabloVerifier: unbalanced If or While nesting depth.");
295    }
296}
297
298/** ------------------------------------------------------------------------------------------------------------- *
299 * @brief isTopologicallyOrdered
300 ** ------------------------------------------------------------------------------------------------------------- */
301struct OrderingVerifier {
302    OrderingVerifier() : mParent(nullptr) {}
303    OrderingVerifier(const OrderingVerifier & parent) : mParent(&parent) {}
304    bool count(const PabloAST * expr) const {
305        if (mSet.count(expr)) {
306            return true;
307        } else if (mParent) {
308            return mParent->count(expr);
309        }
310        return false;
311    }
312    void insert(const PabloAST * expr) {
313        mSet.insert(expr);
314    }
315private:
316    const OrderingVerifier * const mParent;
317    SmallSet<const PabloAST *> mSet;
318};
319
320bool recursivelyDefined(const Statement * const stmt) {
321    std::queue<const Statement *> Q;
322    SmallSet<const PabloAST *> V;
323    V.insert(stmt);
324    for (const Statement * ancestor = stmt;;) {
325        for (unsigned i = 0; i != ancestor->getNumOperands(); ++i) {
326            const PabloAST * op = ancestor->getOperand(i);
327            if (isa<Statement>(op) && V.count(op) == 0) {
328                if (op == stmt) {
329                    return true;
330                }
331                Q.push(cast<Statement>(op));
332                V.insert(op);
333            }
334        }
335        if (LLVM_UNLIKELY(Q.empty())) {
336            break;
337        }
338        ancestor = Q.front();
339        Q.pop();
340    }
341    return false;
342}
343
344void isTopologicallyOrdered(const PabloBlock * block, const OrderingVerifier & parent) {
345    OrderingVerifier ov(parent);
346    for (const Statement * stmt : *block) {
347        if (LLVM_UNLIKELY(isa<While>(stmt))) {
348            isTopologicallyOrdered(cast<While>(stmt)->getBody(), ov);
349            for (const Next * var : cast<While>(stmt)->getVariants()) {
350                ov.insert(var);
351            }
352        }
353        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
354            const PabloAST * const op = stmt->getOperand(i);
355            if (LLVM_UNLIKELY((isa<Statement>(op) || isa<Var>(op)) && ov.count(op) == 0)) {
356                std::string tmp;
357                raw_string_ostream str(tmp);
358                str << "PabloVerifier: ordering volation: ";
359                if (LLVM_UNLIKELY(recursivelyDefined(stmt))) {
360                    PabloPrinter::print(stmt, str);
361                    str << " is defined by a recursive function!";
362                    throw std::runtime_error(str.str());
363                }
364                // TODO: make this actually test whether the operand is ever defined,
365                // or if it was defined in a scope that cannot be reached?
366
367                str << "function is not topologically ordered! ";
368                PabloAST * op = stmt->getOperand(i);
369                PabloPrinter::print(op, str);
370                if (LLVM_UNLIKELY(isa<Statement>(op) && unreachable(stmt, cast<Statement>(op)->getParent()))) {
371                    str << " was defined in a scope that is unreachable by ";
372                } else {
373                    str << " was used before definition by ";
374                }
375                PabloPrinter::print(stmt, str);
376                throw std::runtime_error(str.str());
377            }
378        }
379        ov.insert(stmt);
380        if (LLVM_UNLIKELY(isa<If>(stmt))) {
381            isTopologicallyOrdered(cast<If>(stmt)->getBody(), ov);
382            for (const Assign * def : cast<If>(stmt)->getDefined()) {
383                ov.insert(def);
384            }
385        }
386    }
387}
388
389void isTopologicallyOrdered(const PabloFunction & function) {
390    OrderingVerifier ov;
391    for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
392        ov.insert(function.getParameter(i));
393    }
394    isTopologicallyOrdered(function.getEntryBlock(), ov);
395}
396
397void PabloVerifier::verify(const PabloFunction & function, const std::string location) {
398    try {
399        verifyProgramStructure(function);
400        verifyUseDefInformation(function);
401        isTopologicallyOrdered(function);
402    } catch(std::runtime_error err) {
403        raw_os_ostream out(std::cerr);
404        PabloPrinter::print(function, out);
405        out.flush();
406        if (location.empty()) {
407            throw err;
408        } else {
409            throw std::runtime_error(std::string(err.what()) + " @ " + location);
410        }
411    }
412}
413
414}
Note: See TracBrowser for help on using the repository browser.