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

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

Work on lowering + minor bug fixes.

File size: 15.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        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 recorded in ";
172    } else if (count > 0) {
173        str << " is recorded" << count << " times in ";
174    }
175    PabloPrinter::print(def, str);
176    str << "'s user list.";
177    throw std::runtime_error(str.str());
178}
179
180/** ------------------------------------------------------------------------------------------------------------- *
181 * @brief verifyProgramStructure
182 ** ------------------------------------------------------------------------------------------------------------- */
183void verifyProgramStructure(const PabloBlock * block) {
184    const Statement * prev = nullptr;
185    for (const Statement * stmt : *block) {
186        if (LLVM_UNLIKELY(stmt->getPrevNode() != prev)) {
187            std::string tmp;
188            raw_string_ostream str(tmp);
189            str << "PabloVerifier: structure error: ";
190            PabloPrinter::print(stmt, str);
191            str << " succeeds ";
192            PabloPrinter::print(prev, str);
193            str << " but expects to preceed ";
194            PabloPrinter::print(stmt->getPrevNode(), str);
195            throw std::runtime_error(str.str());
196        }
197        prev = stmt;
198        if (LLVM_UNLIKELY(stmt->getParent() != block)) {
199            std::string tmp;
200            raw_string_ostream str(tmp);
201            str << "PabloVerifier: structure error: ";
202            PabloPrinter::print(stmt, str);
203            str << " is not contained in its reported scope block";
204            throw std::runtime_error(str.str());
205        }
206        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
207            const PabloBlock * nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
208            if (LLVM_UNLIKELY(nested->getParent() != block)) {
209                std::string tmp;
210                raw_string_ostream str(tmp);
211                str << "PabloVerifier: structure error: body of ";
212                PabloPrinter::print(stmt, str);
213                str << " is not nested within the expected scope block";
214                throw std::runtime_error(str.str());
215            }
216            if (isa<If>(stmt)) {
217                for (const Assign * def : cast<If>(stmt)->getDefined()) {
218                    if (LLVM_UNLIKELY(def == cast<If>(stmt)->getCondition())) {
219                        std::string tmp;
220                        raw_string_ostream str(tmp);
221                        str << "PabloVerifier: structure error: the condition of ";
222                        PabloPrinter::print(cast<PabloAST>(stmt), str);
223                        str << " cannot be defined by the If node itself.";
224                        throw std::runtime_error(str.str());
225                    }
226                }
227            }
228            if (isa<If>(stmt)) {
229                for (const Assign * def : cast<If>(stmt)->getDefined()) {
230                    if (LLVM_UNLIKELY(unreachable(def, nested))) {
231                        throwUncontainedEscapedValueError(stmt, def);
232                    }
233                    unsigned count = std::count(stmt->user_begin(), stmt->user_end(), def);
234                    if (LLVM_UNLIKELY(count != 1)) {
235                        throwEscapedValueUsageError(stmt, def, stmt, def, count);
236                    }
237                    count = std::count(def->user_begin(), def->user_end(), stmt);
238                    if (LLVM_UNLIKELY(count != 1)) {
239                        throwEscapedValueUsageError(stmt, def, def, stmt, count);
240                    }
241                }
242            } else {
243                for (const Next * var : cast<While>(stmt)->getVariants()) {
244                    if (LLVM_UNLIKELY(unreachable(var, nested))) {
245                        throwUncontainedEscapedValueError(stmt, var);
246                    }
247                    unsigned count = std::count(stmt->user_begin(), stmt->user_end(), var);
248                    if (LLVM_UNLIKELY(count != 1)) {
249                        throwEscapedValueUsageError(stmt, var, stmt, var, count);
250                    }
251                    count = std::count(var->user_begin(), var->user_end(), stmt);
252                    if (LLVM_UNLIKELY(count != 1)) {
253                        throwEscapedValueUsageError(stmt, var, var, stmt, count);
254                    }
255                }
256            }
257            verifyProgramStructure(nested);
258        }
259    }
260}
261
262inline void verifyProgramStructure(const PabloFunction & function) {
263    verifyProgramStructure(function.getEntryBlock());
264}
265
266/** ------------------------------------------------------------------------------------------------------------- *
267 * @brief isTopologicallyOrdered
268 ** ------------------------------------------------------------------------------------------------------------- */
269struct OrderingVerifier {
270    OrderingVerifier() : mParent(nullptr) {}
271    OrderingVerifier(const OrderingVerifier & parent) : mParent(&parent) {}
272    bool count(const PabloAST * expr) const {
273        if (mSet.count(expr)) {
274            return true;
275        } else if (mParent) {
276            return mParent->count(expr);
277        }
278        return false;
279    }
280    void insert(const PabloAST * expr) {
281        mSet.insert(expr);
282    }
283private:
284    const OrderingVerifier * const mParent;
285    SmallSet<const PabloAST *> mSet;
286};
287
288bool recursivelyDefined(const Statement * const stmt) {
289    std::queue<const Statement *> Q;
290    SmallSet<const PabloAST *> V;
291    V.insert(stmt);
292    for (const Statement * ancestor = stmt;;) {
293        for (unsigned i = 0; i != ancestor->getNumOperands(); ++i) {
294            const PabloAST * op = ancestor->getOperand(i);
295            if (isa<Statement>(op) && V.count(op) == 0) {
296                if (op == stmt) {
297                    return true;
298                }
299                Q.push(cast<Statement>(op));
300                V.insert(op);
301            }
302        }
303        if (LLVM_UNLIKELY(Q.empty())) {
304            break;
305        }
306        ancestor = Q.front();
307        Q.pop();
308    }
309    return false;
310}
311
312void isTopologicallyOrdered(const PabloBlock * block, const OrderingVerifier & parent) {
313    OrderingVerifier ov(parent);
314    for (const Statement * stmt : *block) {
315        if (LLVM_UNLIKELY(isa<While>(stmt))) {
316            isTopologicallyOrdered(cast<While>(stmt)->getBody(), ov);
317            for (const Next * var : cast<While>(stmt)->getVariants()) {
318                ov.insert(var);
319            }
320        }
321        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
322            const PabloAST * const op = stmt->getOperand(i);
323            if (LLVM_UNLIKELY((isa<Statement>(op) || isa<Var>(op)) && ov.count(op) == 0)) {
324                std::string tmp;
325                raw_string_ostream str(tmp);
326                str << "PabloVerifier: ordering volation: ";
327                if (LLVM_UNLIKELY(recursivelyDefined(stmt))) {
328                    PabloPrinter::print(stmt, str);
329                    str << " is defined by a recursive function!";
330                    throw std::runtime_error(str.str());
331                }
332                // TODO: make this actually test whether the operand is ever defined,
333                // or if it was defined in a scope that cannot be reached?
334
335                str << "function is not topologically ordered! ";
336                PabloAST * op = stmt->getOperand(i);
337                PabloPrinter::print(op, str);
338                if (LLVM_UNLIKELY(isa<Statement>(op) && unreachable(stmt, cast<Statement>(op)->getParent()))) {
339                    str << " was defined in a scope that is unreachable by ";
340                } else {
341                    str << " was used before definition by ";
342                }
343                PabloPrinter::print(stmt, str);
344                throw std::runtime_error(str.str());
345            }
346        }
347        ov.insert(stmt);
348        if (LLVM_UNLIKELY(isa<If>(stmt))) {
349            isTopologicallyOrdered(cast<If>(stmt)->getBody(), ov);
350            for (const Assign * def : cast<If>(stmt)->getDefined()) {
351                ov.insert(def);
352            }
353        }
354    }
355}
356
357void isTopologicallyOrdered(const PabloFunction & function) {
358    OrderingVerifier ov;
359    for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
360        ov.insert(function.getParameter(i));
361    }
362    isTopologicallyOrdered(function.getEntryBlock(), ov);
363}
364
365void PabloVerifier::verify(const PabloFunction & function, const std::string location) {
366    try {
367        verifyProgramStructure(function);
368        verifyUseDefInformation(function);
369        isTopologicallyOrdered(function);
370    } catch(std::runtime_error err) {
371        raw_os_ostream out(std::cerr);
372        PabloPrinter::print(function, out);
373        out.flush();
374        if (location.empty()) {
375            throw err;
376        } else {
377            throw std::runtime_error(std::string(err.what()) + " @ " + location);
378        }
379    }
380}
381
382}
Note: See TracBrowser for help on using the repository browser.