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

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

Bug fixes

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