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

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

Progress on multi-target UCD compiler.

File size: 10.8 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#include <boost/container/flat_set.hpp>
7#include <boost/container/flat_map.hpp>
8
9using namespace boost::container;
10
11namespace pablo {
12
13using ScopeSet = flat_set<const PabloBlock *>;
14
15/** ------------------------------------------------------------------------------------------------------------- *
16 * @brief verifyUseDefInformation
17 ** ------------------------------------------------------------------------------------------------------------- */
18template<typename VectorType>
19bool checkVector(const Statement * value, const VectorType & vector) {
20    for (auto escapedValue : vector) {
21        if (escapedValue == value) {
22            return false;
23        }
24    }
25    return true;
26}
27
28void verifyUseDefInformation(const PabloBlock & block, const ScopeSet & validScopes) {
29    for (const Statement * stmt : block) {
30
31        for (const PabloAST * use : stmt->users()) {
32            if (LLVM_LIKELY(isa<Statement>(use))) {
33                const Statement * const user = cast<Statement>(use);
34                // test whether this user is in a block in the program
35                if (LLVM_UNLIKELY(validScopes.count(user->getParent()) == 0)) {
36                    std::string tmp;
37                    raw_string_ostream str(tmp);
38                    PabloPrinter::print(user, "PabloVerifier: use-def error: ", str);
39                    PabloPrinter::print(stmt, " is a user of ", str);
40                    if (user->getParent() == nullptr) {
41                        str << " but is not in any scope.";
42                    } else {
43                        str << " but is in a deleted scope.";
44                    }
45                    throw std::runtime_error(str.str());
46                }
47                bool notFound = true;
48                for (unsigned i = 0; i != user->getNumOperands(); ++i) {
49                    if (user->getOperand(i) == stmt) {
50                        notFound = false;
51                        break;
52                    }
53                }
54                if (LLVM_UNLIKELY(notFound)) {
55                    if (const If * ifNode = dyn_cast<If>(stmt)) {
56                        notFound = checkVector(user, ifNode->getDefined());
57                    } else if (const If * ifNode = dyn_cast<If>(user)) {
58                        notFound = checkVector(stmt, ifNode->getDefined());
59                    } else if (const While * whileNode = dyn_cast<While>(stmt)) {
60                        notFound = checkVector(user, whileNode->getVariants());
61                    } else if (const While * whileNode = dyn_cast<While>(user)) {
62                        notFound = checkVector(stmt, whileNode->getVariants());
63                    } else if (isa<Next>(stmt) && isa<Assign>(use)) {
64                        notFound = (use != cast<Next>(stmt)->getInitial());
65                    }
66                    if (LLVM_UNLIKELY(notFound)) {
67                        std::string tmp;
68                        raw_string_ostream str(tmp);
69                        str << "PabloVerifier: use-def error: ";
70                        PabloPrinter::print(stmt, str);
71                        str << " is not a definition of ";
72                        PabloPrinter::print(use, str);
73                        throw std::runtime_error(str.str());
74                    }
75                }
76            }
77        }
78        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
79            const PabloAST * const def = stmt->getOperand(i);
80            bool notFound = true;
81            for (const PabloAST * use : def->users()) {
82                if (use == stmt) {
83                    notFound = false;
84                    break;
85                }
86            }
87            if (LLVM_UNLIKELY(notFound)) {
88                std::string tmp;
89                raw_string_ostream str(tmp);
90                PabloPrinter::print(stmt, "PabloVerifier: def-use error: ", str);
91                str << " is not a user of ";
92                PabloPrinter::print(def, str);
93                throw std::runtime_error(str.str());
94            }
95        }
96        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
97            verifyUseDefInformation(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), validScopes);
98        }
99    }
100}
101
102void gatherValidScopes(const PabloBlock & block, ScopeSet & validScopes) {
103    validScopes.insert(&block);
104    for (const Statement * stmt : block) {
105        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
106            gatherValidScopes(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), validScopes);
107        }
108    }
109}
110
111void verifyUseDefInformation(const PabloFunction & function) {
112    ScopeSet validScopes;
113    gatherValidScopes(function.getEntryBlock(), validScopes);
114    verifyUseDefInformation(function.getEntryBlock(), validScopes);
115}
116
117/** ------------------------------------------------------------------------------------------------------------- *
118 * @brief verifyProgramStructure
119 ** ------------------------------------------------------------------------------------------------------------- */
120void verifyProgramStructure(const PabloBlock & block) {
121    const Statement * prev = nullptr;
122    for (const Statement * stmt : block) {
123        if (LLVM_UNLIKELY(stmt->getPrevNode() != prev)) {
124            std::string tmp;
125            raw_string_ostream str(tmp);
126            PabloPrinter::print(stmt, "PabloVerifier: structure error: ", str);
127            str << " succeeds ";
128            PabloPrinter::print(prev, str);
129            str << " but expects to preceed  ";
130            PabloPrinter::print(stmt->getPrevNode(), str);
131            throw std::runtime_error(str.str());
132        }
133        prev = stmt;
134        if (LLVM_UNLIKELY(stmt->getParent() != &block)) {
135            std::string tmp;
136            raw_string_ostream str(tmp);
137            PabloPrinter::print(stmt, "PabloVerifier: structure error: ", str);
138            str << " is not contained in its reported scope block";
139            throw std::runtime_error(str.str());
140        }
141        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
142            const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
143            if (LLVM_UNLIKELY(nested.getParent() != &block)) {
144                std::string tmp;
145                raw_string_ostream str(tmp);
146                str << "PabloVerifier: structure error: body of ";
147                PabloPrinter::print(stmt, str);
148                str << " is not nested within the expected scope block";
149                throw std::runtime_error(str.str());
150            }
151            const Statement * misreportedEscapingValue = nullptr;
152            if (isa<If>(stmt)) {
153                for (const Assign * def : cast<If>(stmt)->getDefined()) {
154                    if (def->getParent() != &block) {
155                        misreportedEscapingValue = def;
156                        break;
157                    }
158                }
159            } else {
160                for (const Next * var : cast<While>(stmt)->getVariants()) {
161                    if (var->getParent() != &block) {
162                        misreportedEscapingValue = var;
163                        break;
164                    }
165                }
166            }
167            if (misreportedEscapingValue) {
168                std::string tmp;
169                raw_string_ostream str(tmp);
170                str << "PabloVerifier: structure error: ";
171                PabloPrinter::print(misreportedEscapingValue, str);
172                str << " is not contained within the body of ";
173                PabloPrinter::print(stmt, str);
174                throw std::runtime_error(str.str());
175            }
176            verifyProgramStructure(nested);
177        }
178    }
179}
180
181inline void verifyProgramStructure(const PabloFunction & function) {
182    verifyProgramStructure(function.getEntryBlock());
183}
184
185/** ------------------------------------------------------------------------------------------------------------- *
186 * @brief isTopologicallyOrdered
187 ** ------------------------------------------------------------------------------------------------------------- */
188struct OrderingVerifier {
189    OrderingVerifier() : mParent(nullptr) {}
190    OrderingVerifier(const OrderingVerifier & parent) : mParent(&parent) {}
191    bool count(const PabloAST * expr) const {
192        if (mSet.count(expr)) {
193            return true;
194        } else if (mParent) {
195            return mParent->count(expr);
196        }
197        return false;
198    }
199    void insert(const PabloAST * expr) {
200        mSet.insert(expr);
201    }
202private:
203    const OrderingVerifier * const mParent;
204    boost::container::flat_set<const PabloAST *> mSet;
205};
206
207void isTopologicallyOrdered(const PabloBlock & block, const OrderingVerifier & parent) {
208    OrderingVerifier ov(parent);
209    for (const Statement * stmt : block) {
210        if (LLVM_UNLIKELY(isa<While>(stmt))) {
211            isTopologicallyOrdered(cast<While>(stmt)->getBody(), ov);
212            for (const Next * var : cast<While>(stmt)->getVariants()) {
213                ov.insert(var);
214            }
215        }
216        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
217            const PabloAST * const op = stmt->getOperand(i);
218            if (LLVM_UNLIKELY((isa<Statement>(op) || isa<Var>(op)) && ov.count(op) == 0)) {
219                // TODO: make this actually test whether the operand is ever defined,
220                // or if it was defined in a scope that cannot be reached?
221                std::string tmp;
222                raw_string_ostream str(tmp);
223                str << "PabloVerifier: function is not topologically ordered! ";
224                PabloPrinter::print(stmt->getOperand(i), str);
225                PabloPrinter::print(stmt, " was used before definition by ", str);
226                throw std::runtime_error(str.str());
227            }
228        }
229        ov.insert(stmt);
230        if (LLVM_UNLIKELY(isa<If>(stmt))) {
231            isTopologicallyOrdered(cast<If>(stmt)->getBody(), ov);
232            for (const Assign * def : cast<If>(stmt)->getDefined()) {
233                ov.insert(def);
234            }
235        }
236    }
237}
238
239void isTopologicallyOrdered(const PabloFunction & function) {
240    OrderingVerifier ov;
241    for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
242        ov.insert(function.getParameter(i));
243    }
244    isTopologicallyOrdered(function.getEntryBlock(), ov);
245}
246
247void PabloVerifier::verify(const PabloFunction & function, const std::string location) {
248    try {
249        verifyProgramStructure(function);
250        verifyUseDefInformation(function);
251        isTopologicallyOrdered(function);
252    } catch(std::runtime_error err) {
253        raw_os_ostream out(std::cerr);
254        PabloPrinter::print(function.getEntryBlock().statements(), out);
255        out.flush();
256        if (location.empty()) {
257            throw err;
258        } else {
259            throw std::runtime_error(std::string(err.what()) + " @ " + location);
260        }
261    }
262}
263
264}
Note: See TracBrowser for help on using the repository browser.