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

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

Bug fix for Multiplexing. Added ability to set the body of a If/While? node after creation.

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