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

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

Bug fix for use-def correctness regarding escaping values of If and While nodes.

File size: 13.0 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
42        for (const PabloAST * use : stmt->users()) {
43            if (LLVM_LIKELY(isa<Statement>(use))) {
44                const Statement * const user = cast<Statement>(use);
45                // test whether this user is in a block in the program
46                if (LLVM_UNLIKELY(validScopes.count(user->getParent()) == 0)) {
47                    std::string tmp;
48                    raw_string_ostream str(tmp);
49                    PabloPrinter::print(user, "PabloVerifier: use-def error: ", 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                PabloPrinter::print(stmt, "PabloVerifier: def-use error: ", str);
103                str << " is not a user of ";
104                PabloPrinter::print(def, str);
105                throw std::runtime_error(str.str());
106            }
107        }
108        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
109            verifyUseDefInformation(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), validScopes);
110        }
111    }
112}
113
114void gatherValidScopes(const PabloBlock & block, ScopeSet & validScopes) {
115    validScopes.insert(&block);
116    for (const Statement * stmt : block) {
117        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
118            gatherValidScopes(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), validScopes);
119        }
120    }
121}
122
123void verifyUseDefInformation(const PabloFunction & function) {
124    ScopeSet validScopes;
125    gatherValidScopes(function.getEntryBlock(), validScopes);
126    verifyUseDefInformation(function.getEntryBlock(), validScopes);
127}
128
129/** ------------------------------------------------------------------------------------------------------------- *
130 * @brief verifyProgramStructure
131 ** ------------------------------------------------------------------------------------------------------------- */
132void verifyProgramStructure(const PabloBlock & block) {
133    const Statement * prev = nullptr;
134    for (const Statement * stmt : block) {
135        if (LLVM_UNLIKELY(stmt->getPrevNode() != prev)) {
136            std::string tmp;
137            raw_string_ostream str(tmp);
138            PabloPrinter::print(stmt, "PabloVerifier: structure error: ", str);
139            str << " succeeds ";
140            PabloPrinter::print(prev, str);
141            str << " but expects to preceed ";
142            PabloPrinter::print(stmt->getPrevNode(), str);
143            throw std::runtime_error(str.str());
144        }
145        prev = stmt;
146        if (LLVM_UNLIKELY(stmt->getParent() != &block)) {
147            std::string tmp;
148            raw_string_ostream str(tmp);
149            PabloPrinter::print(stmt, "PabloVerifier: structure error: ", str);
150            str << " is not contained in its reported scope block";
151            throw std::runtime_error(str.str());
152        }
153        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
154            const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
155            if (LLVM_UNLIKELY(nested.getParent() != &block)) {
156                std::string tmp;
157                raw_string_ostream str(tmp);
158                str << "PabloVerifier: structure error: body of ";
159                PabloPrinter::print(stmt, str);
160                str << " is not nested within the expected scope block";
161                throw std::runtime_error(str.str());
162            }
163            const Statement * badEscapedValue = nullptr;
164            if (isa<If>(stmt)) {
165                for (const Assign * def : cast<If>(stmt)->getDefined()) {
166                    if (def->getParent() != &nested) {
167                        badEscapedValue = def;
168                        break;
169                    }
170                }
171            } else {
172                for (const Next * var : cast<While>(stmt)->getVariants()) {
173                    if (var->getParent() != &nested) {
174                        badEscapedValue = var;
175                        break;
176                    }
177                }
178            }
179            if (badEscapedValue) {
180                std::string tmp;
181                raw_string_ostream str(tmp);
182                str << "PabloVerifier: structure error: ";
183                PabloPrinter::print(badEscapedValue, str);
184                str << " is not contained within the body of ";
185                PabloPrinter::print(stmt, str);
186                throw std::runtime_error(str.str());
187            }
188            if (isa<If>(stmt)) {
189                for (const Assign * def : cast<If>(stmt)->getDefined()) {
190                    if (LLVM_UNLIKELY(std::find(stmt->user_begin(), stmt->user_end(), def) == stmt->user_end())) {
191                        badEscapedValue = def;
192                        break;
193                    }
194                }
195            } else {
196                for (const Next * var : cast<While>(stmt)->getVariants()) {
197                    if (LLVM_UNLIKELY(std::find(stmt->user_begin(), stmt->user_end(), var) == stmt->user_end())) {
198                        badEscapedValue = var;
199                        break;
200                    }
201                }
202            }
203            if (badEscapedValue) {
204                std::string tmp;
205                raw_string_ostream str(tmp);
206                str << "PabloVerifier: structure error: ";
207                PabloPrinter::print(badEscapedValue, str);
208                str << " is an escaped value of ";
209                PabloPrinter::print(stmt, str);
210                str << " but not a user";
211                throw std::runtime_error(str.str());
212            }
213            verifyProgramStructure(nested);
214        }
215    }
216}
217
218inline void verifyProgramStructure(const PabloFunction & function) {
219    verifyProgramStructure(function.getEntryBlock());
220}
221
222/** ------------------------------------------------------------------------------------------------------------- *
223 * @brief isTopologicallyOrdered
224 ** ------------------------------------------------------------------------------------------------------------- */
225struct OrderingVerifier {
226    OrderingVerifier() : mParent(nullptr) {}
227    OrderingVerifier(const OrderingVerifier & parent) : mParent(&parent) {}
228    bool count(const PabloAST * expr) const {
229        if (mSet.count(expr)) {
230            return true;
231        } else if (mParent) {
232            return mParent->count(expr);
233        }
234        return false;
235    }
236    void insert(const PabloAST * expr) {
237        mSet.insert(expr);
238    }
239private:
240    const OrderingVerifier * const mParent;
241    SmallSet<const PabloAST *> mSet;
242};
243
244bool recursivelyDefined(const Statement * const stmt) {
245    std::queue<const Statement *> Q;
246    SmallSet<const PabloAST *> V;
247    V.insert(stmt);
248    for (const Statement * ancestor = stmt;;) {
249        for (unsigned i = 0; i != ancestor->getNumOperands(); ++i) {
250            const PabloAST * op = ancestor->getOperand(i);
251            if (isa<Statement>(op) && V.count(op) == 0) {
252                if (op == stmt) {
253                    return true;
254                }
255                Q.push(cast<Statement>(op));
256                V.insert(op);
257            }
258        }
259        if (LLVM_UNLIKELY(Q.empty())) {
260            break;
261        }
262        ancestor = Q.front();
263        Q.pop();
264    }
265    return false;
266}
267
268void isTopologicallyOrdered(const PabloBlock & block, const OrderingVerifier & parent) {
269    OrderingVerifier ov(parent);
270    for (const Statement * stmt : block) {
271        if (LLVM_UNLIKELY(isa<While>(stmt))) {
272            isTopologicallyOrdered(cast<While>(stmt)->getBody(), ov);
273            for (const Next * var : cast<While>(stmt)->getVariants()) {
274                ov.insert(var);
275            }
276        }
277        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
278            const PabloAST * const op = stmt->getOperand(i);
279            if (LLVM_UNLIKELY((isa<Statement>(op) || isa<Var>(op)) && ov.count(op) == 0)) {
280
281                std::string tmp;
282                raw_string_ostream str(tmp);
283                str << "PabloVerifier: ordering volation: ";
284                if (LLVM_UNLIKELY(recursivelyDefined(stmt))) {
285                    PabloPrinter::print(stmt, str);
286                    str << " is recursively defined!";
287                    throw std::runtime_error(str.str());
288                }
289                // TODO: make this actually test whether the operand is ever defined,
290                // or if it was defined in a scope that cannot be reached?
291
292                str << "function is not topologically ordered! ";
293                PabloPrinter::print(stmt->getOperand(i), str);
294                PabloPrinter::print(stmt, " was used before definition by ", str);
295                throw std::runtime_error(str.str());
296            }
297        }
298        ov.insert(stmt);
299        if (LLVM_UNLIKELY(isa<If>(stmt))) {
300            isTopologicallyOrdered(cast<If>(stmt)->getBody(), ov);
301            for (const Assign * def : cast<If>(stmt)->getDefined()) {
302                ov.insert(def);
303            }
304        }
305    }
306}
307
308void isTopologicallyOrdered(const PabloFunction & function) {
309    OrderingVerifier ov;
310    for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
311        ov.insert(function.getParameter(i));
312    }
313    isTopologicallyOrdered(function.getEntryBlock(), ov);
314}
315
316void PabloVerifier::verify(const PabloFunction & function, const std::string location) {
317    try {
318        verifyProgramStructure(function);
319        verifyUseDefInformation(function);
320        isTopologicallyOrdered(function);
321    } catch(std::runtime_error err) {
322        raw_os_ostream out(std::cerr);
323        PabloPrinter::print(function.getEntryBlock().statements(), out);
324        out.flush();
325        if (location.empty()) {
326            throw err;
327        } else {
328            throw std::runtime_error(std::string(err.what()) + " @ " + location);
329        }
330    }
331}
332
333}
Note: See TracBrowser for help on using the repository browser.