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

Last change on this file since 4866 was 4866, checked in by nmedfort, 4 years ago

Bug fix for Linda.

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