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

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

More work on n-ary operations. Unresolved bug in DistributionPass?.

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