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

Last change on this file since 5082 was 5082, checked in by cameron, 3 years ago

More cppcheck fixes

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