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
RevLine 
[4766]1#include "pabloverifier.hpp"
2#include <pablo/function.h>
3#include <pablo/codegenstate.h>
4#include <pablo/printer_pablos.h>
[4773]5#include <iostream>
[4804]6#ifdef USE_BOOST
[4775]7#include <boost/container/flat_set.hpp>
[4804]8#else
9#include <unordered_set>
10#endif
[4856]11#include <queue>
[4766]12
[4856]13
[4766]14namespace pablo {
15
[4804]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
[4797]23
[4804]24using ScopeSet = SmallSet<const PabloBlock *>;
25
[4797]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
[4870]39void verifyUseDefInformation(const PabloBlock * block, const ScopeSet & validScopes) {
40    for (const Statement * stmt : *block) {
[4797]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);
[4870]48                    str << "PabloVerifier: use-def error: ";
49                    PabloPrinter::print(user, str);
[4856]50                    str << " is a user of ";
51                    PabloPrinter::print(stmt, str);
[4797]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);
[4870]102                str << "PabloVerifier: def-use error: ";
103                PabloPrinter::print(stmt, str);
[4876]104                str << " is not recorded in ";
[4797]105                PabloPrinter::print(def, str);
[4876]106                str << "'s user list";
[4797]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
[4870]116void gatherValidScopes(const PabloBlock * block, ScopeSet & validScopes) {
117    validScopes.insert(block);
118    for (const Statement * stmt : *block) {
[4797]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/** ------------------------------------------------------------------------------------------------------------- *
[4866]132 * @brief unreachable
133 ** ------------------------------------------------------------------------------------------------------------- */
[4870]134bool unreachable(const Statement * stmt, const PabloBlock * const block) {
[4866]135    PabloBlock * parent = stmt->getParent();
136    while (parent)  {
[4870]137        if (parent == block) {
[4866]138            return false;
139        }
140        parent = parent->getParent();
141    }
142    return true;
143}
144
145/** ------------------------------------------------------------------------------------------------------------- *
[4899]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/** ------------------------------------------------------------------------------------------------------------- *
[4797]181 * @brief verifyProgramStructure
182 ** ------------------------------------------------------------------------------------------------------------- */
[4870]183void verifyProgramStructure(const PabloBlock * block) {
[4797]184    const Statement * prev = nullptr;
[4870]185    for (const Statement * stmt : *block) {
[4797]186        if (LLVM_UNLIKELY(stmt->getPrevNode() != prev)) {
187            std::string tmp;
188            raw_string_ostream str(tmp);
[4870]189            str << "PabloVerifier: structure error: ";
190            PabloPrinter::print(stmt, str);
[4797]191            str << " succeeds ";
192            PabloPrinter::print(prev, str);
[4856]193            str << " but expects to preceed ";
[4797]194            PabloPrinter::print(stmt->getPrevNode(), str);
195            throw std::runtime_error(str.str());
196        }
197        prev = stmt;
[4870]198        if (LLVM_UNLIKELY(stmt->getParent() != block)) {
[4797]199            std::string tmp;
200            raw_string_ostream str(tmp);
[4870]201            str << "PabloVerifier: structure error: ";
202            PabloPrinter::print(stmt, str);
[4797]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))) {
[4870]207            const PabloBlock * nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
208            if (LLVM_UNLIKELY(nested->getParent() != block)) {
[4797]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            }
[4885]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            }
[4797]228            if (isa<If>(stmt)) {
229                for (const Assign * def : cast<If>(stmt)->getDefined()) {
[4899]230                    if (LLVM_UNLIKELY(unreachable(def, nested))) {
231                        throwUncontainedEscapedValueError(stmt, def);
[4797]232                    }
[4899]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);
[4797]236                    }
[4899]237                    count = std::count(def->user_begin(), def->user_end(), stmt);
238                    if (LLVM_UNLIKELY(count != 1)) {
239                        throwEscapedValueUsageError(stmt, def, def, stmt, count);
[4856]240                    }
241                }
242            } else {
243                for (const Next * var : cast<While>(stmt)->getVariants()) {
[4899]244                    if (LLVM_UNLIKELY(unreachable(var, nested))) {
245                        throwUncontainedEscapedValueError(stmt, var);
[4856]246                    }
[4899]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                    }
[4856]255                }
256            }
[4797]257            verifyProgramStructure(nested);
258        }
259    }
260}
261
262inline void verifyProgramStructure(const PabloFunction & function) {
263    verifyProgramStructure(function.getEntryBlock());
264}
265
266/** ------------------------------------------------------------------------------------------------------------- *
267 * @brief isTopologicallyOrdered
268 ** ------------------------------------------------------------------------------------------------------------- */
[4766]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;
[4804]285    SmallSet<const PabloAST *> mSet;
[4766]286};
287
[4856]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
[4870]312void isTopologicallyOrdered(const PabloBlock * block, const OrderingVerifier & parent) {
[4766]313    OrderingVerifier ov(parent);
[4870]314    for (const Statement * stmt : *block) {
[4771]315        if (LLVM_UNLIKELY(isa<While>(stmt))) {
[4797]316            isTopologicallyOrdered(cast<While>(stmt)->getBody(), ov);
[4771]317            for (const Next * var : cast<While>(stmt)->getVariants()) {
318                ov.insert(var);
319            }
320        }
[4766]321        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
[4797]322            const PabloAST * const op = stmt->getOperand(i);
323            if (LLVM_UNLIKELY((isa<Statement>(op) || isa<Var>(op)) && ov.count(op) == 0)) {
[4856]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);
[4876]329                    str << " is defined by a recursive function!";
[4856]330                    throw std::runtime_error(str.str());
331                }
[4766]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?
[4856]334
335                str << "function is not topologically ordered! ";
[4876]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                }
[4870]343                PabloPrinter::print(stmt, str);
[4766]344                throw std::runtime_error(str.str());
345            }
346        }
347        ov.insert(stmt);
348        if (LLVM_UNLIKELY(isa<If>(stmt))) {
[4797]349            isTopologicallyOrdered(cast<If>(stmt)->getBody(), ov);
[4766]350            for (const Assign * def : cast<If>(stmt)->getDefined()) {
351                ov.insert(def);
352            }
353        }
354    }
355}
356
[4797]357void isTopologicallyOrdered(const PabloFunction & function) {
[4766]358    OrderingVerifier ov;
359    for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
360        ov.insert(function.getParameter(i));
361    }
[4797]362    isTopologicallyOrdered(function.getEntryBlock(), ov);
[4766]363}
364
[4797]365void PabloVerifier::verify(const PabloFunction & function, const std::string location) {
[4773]366    try {
[4797]367        verifyProgramStructure(function);
368        verifyUseDefInformation(function);
369        isTopologicallyOrdered(function);
[4773]370    } catch(std::runtime_error err) {
371        raw_os_ostream out(std::cerr);
[4870]372        PabloPrinter::print(function, out);
[4773]373        out.flush();
[4797]374        if (location.empty()) {
375            throw err;
376        } else {
377            throw std::runtime_error(std::string(err.what()) + " @ " + location);
378        }
[4773]379    }
[4766]380}
381
382}
Note: See TracBrowser for help on using the repository browser.