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

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

Optimized Symbol Generation (and fixed potential bug that could allow duplicate names being constructed); made PabloKernel? extend PabloAST (temporarily removed PabloAST::getName() to avoid diamond problem); added an internal scalar to PabloKernel? struct for each Count to avoid InOut? output scalar variable problem; allowed CodeMotionPass? to move code within the same scope but across a branch statement. Began work on separating Kernels into either Block-Oriented or Segment-Oriented kernels.

File size: 15.1 KB
Line 
1#include "pabloverifier.hpp"
2#include <pablo/branch.h>
3#include <pablo/pe_var.h>
4#include <pablo/ps_assign.h>
5#include <pablo/codegenstate.h>
6#include <pablo/pablo_kernel.h>
7#include <pablo/printer_pablos.h>
8#include <boost/container/flat_set.hpp>
9#include <llvm/Support/raw_ostream.h>
10
11using namespace llvm;
12
13namespace pablo {
14
15using TypeId = PabloAST::ClassTypeId;
16
17template <typename Type>
18using SmallSet = boost::container::flat_set<Type>;
19
20using ScopeSet = SmallSet<const PabloBlock *>;
21
22/** ------------------------------------------------------------------------------------------------------------- *
23 * @brief verifyUseDefInformation
24 ** ------------------------------------------------------------------------------------------------------------- */
25void testUsers(const PabloAST * expr, const ScopeSet & validScopes) { 
26    size_t uses = 0;
27    SmallSet<const PabloAST *> verified;
28    for (const PabloAST * use : expr->users()) {
29        if (LLVM_UNLIKELY(verified.count(use) != 0)) {
30            continue;
31        }
32        if (const Statement * const user = dyn_cast<Statement>(use)) {
33            // test whether this user is in a block in the program
34            if (LLVM_UNLIKELY(user->getParent() == nullptr || validScopes.count(user->getParent()) == 0)) {
35                std::string tmp;
36                raw_string_ostream str(tmp);
37                str << "use-def error: ";
38                PabloPrinter::print(user, str);
39                str << " is a user of ";
40                PabloPrinter::print(expr, str);
41                str << " but ";
42                PabloPrinter::print(use, str);
43                if (user->getParent() == nullptr) {
44                    str << " is not defined in any scope.";
45                } else {
46                    str << " is in an unreachable scope.";
47                }
48                throw std::runtime_error(str.str());
49            }
50            // expr may be used more than once by the same user.
51            bool notFound = true;
52            for (unsigned i = 0; i != user->getNumOperands(); ++i) {
53                if (user->getOperand(i) == expr) {
54                    notFound = false;
55                    ++uses;
56                }
57            }
58            if (isa<Branch>(user)) {
59                for (const PabloAST * var : cast<Branch>(user)->getEscaped()) {
60                    if (var == expr) {
61                        notFound = false;
62                        ++uses;
63                    }
64                }
65            }
66            if (LLVM_UNLIKELY(notFound)) {
67                std::string tmp;
68                raw_string_ostream str(tmp);
69                str << "use-def error: ";
70                PabloPrinter::print(expr, str);
71                str << " is not a definition of ";
72                PabloPrinter::print(use, str);
73                throw std::runtime_error(str.str());
74            }
75        } else if (isa<Var>(expr)) {
76            if (LLVM_UNLIKELY(isa<Branch>(use) || isa<PabloKernel>(use))) {
77                ++uses;
78            } else {
79                std::string tmp;
80                raw_string_ostream str(tmp);
81                str << "use-def error: var ";
82                PabloPrinter::print(use, str);
83                str << " is a user of ";
84                PabloPrinter::print(expr, str);
85                str << " but can only be a user of a Branch or Kernel.";
86                throw std::runtime_error(str.str());
87            }
88        }
89        verified.insert(use);
90    }
91    if (LLVM_UNLIKELY(uses != expr->getNumUses())) {
92        std::string tmp;
93        raw_string_ostream str(tmp);
94        str << "use-def error: ";
95        PabloPrinter::print(expr, str);
96        str << " is reported having " << expr->getNumUses() << " user(s)"
97            << " but was observed having " << uses << " user(s)";
98        throw std::runtime_error(str.str());
99    }
100}
101
102void testDefs(const Statement * stmt) {
103    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
104        const PabloAST * const def = stmt->getOperand(i);
105        bool notFound = true;
106        for (const PabloAST * use : def->users()) {
107            if (use == stmt) {
108                notFound = false;
109                break;
110            }
111        }
112        if (LLVM_UNLIKELY(notFound)) {
113            std::string tmp;
114            raw_string_ostream str(tmp);
115            str << "PabloVerifier: def-use error: ";
116            PabloPrinter::print(stmt, str);
117            str << " is not recorded in ";
118            PabloPrinter::print(def, str);
119            str << "'s user list";
120            throw std::runtime_error(str.str());
121        }
122    }
123}
124
125void verifyUseDefInformation(const PabloBlock * block, const ScopeSet & validScopes) {
126    for (const Statement * stmt : *block) {
127        testUsers(stmt, validScopes);
128        testDefs(stmt);
129        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
130            verifyUseDefInformation(cast<Branch>(stmt)->getBody(), validScopes);
131        }
132    }
133}
134
135void gatherValidScopes(const PabloBlock * block, ScopeSet & validScopes) {
136    validScopes.insert(block);
137    for (const Statement * stmt : *block) {
138        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
139            gatherValidScopes(cast<Branch>(stmt)->getBody(), validScopes);
140        }
141    }
142}
143
144void verifyUseDefInformation(const PabloKernel * kernel) {
145    ScopeSet validScopes;
146    gatherValidScopes(kernel->getEntryBlock(), validScopes);
147    for (unsigned i = 0; i < kernel->getNumOfInputs(); ++i) {
148        testUsers(kernel->getInput(i), validScopes);
149    }
150    for (unsigned i = 0; i < kernel->getNumOfOutputs(); ++i) {
151        testUsers(kernel->getOutput(i), validScopes);
152    }
153    verifyUseDefInformation(kernel->getEntryBlock(), validScopes);
154}
155
156/** ------------------------------------------------------------------------------------------------------------- *
157 * @brief unreachable
158 ** ------------------------------------------------------------------------------------------------------------- */
159bool unreachable(const Statement * stmt, const PabloBlock * const block) {
160    PabloBlock * parent = stmt->getParent();
161    while (parent)  {
162        if (parent == block) {
163            return false;
164        }
165        parent = parent->getPredecessor();
166    }
167    return true;
168}
169
170/** ------------------------------------------------------------------------------------------------------------- *
171 * @brief throwReportedScopeError
172 ** ------------------------------------------------------------------------------------------------------------- */
173static void throwReportedScopeError(const Statement * const stmt) {
174    std::string tmp;
175    raw_string_ostream str(tmp);
176    str << "structure error: ";
177    PabloPrinter::print(stmt, str);
178    str << " is not contained in its reported scope block";
179    throw std::runtime_error(str.str());
180}
181
182/** ------------------------------------------------------------------------------------------------------------- *
183 * @brief throwMisreportedBranchError
184 ** ------------------------------------------------------------------------------------------------------------- */
185static void throwMisreportedBranchError(const Statement * const stmt, const Statement * const branch) {
186    std::string tmp;
187    raw_string_ostream str(tmp);
188    str << "structure error: ";
189    PabloPrinter::print(stmt, str);
190    str << " branches into a scope block that reports ";
191    PabloPrinter::print(branch, str);
192    str << " as its branching statement.";
193    throw std::runtime_error(str.str());
194}
195
196/** ------------------------------------------------------------------------------------------------------------- *
197 * @brief illegalOperandType
198 ** ------------------------------------------------------------------------------------------------------------- */
199static inline bool illegalOperandType(const PabloAST * const op) {
200    switch (op->getClassTypeId()) {
201        case TypeId::Block:
202        case TypeId::Assign:
203        case TypeId::If:
204        case TypeId::While:
205            return true;
206        default:
207            return false;
208    }
209}
210
211/** ------------------------------------------------------------------------------------------------------------- *
212 * @brief verifyProgramStructure
213 ** ------------------------------------------------------------------------------------------------------------- */
214void verifyProgramStructure(const PabloBlock * block, unsigned & nestingDepth) {
215    const Statement * prev = nullptr;
216    for (const Statement * stmt : *block) {
217        if (LLVM_UNLIKELY(stmt->getPrevNode() != prev)) {
218            std::string tmp;
219            raw_string_ostream str(tmp);
220            PabloPrinter::print(stmt, str);
221            str << " succeeds ";
222            PabloPrinter::print(prev, str);
223            str << " but ";
224            PabloPrinter::print(cast<PabloAST>(stmt), str);
225            str << " expects to succeed ";
226            PabloPrinter::print(stmt->getPrevNode(), str);
227            throw std::runtime_error(str.str());
228        }
229        prev = stmt;
230        if (LLVM_UNLIKELY(stmt->getParent() != block)) {
231            std::string tmp;
232            raw_string_ostream str(tmp);
233            PabloPrinter::print(stmt, str);
234            str << " is not contained in its reported scope block";
235            throw std::runtime_error(str.str());
236        }
237
238        for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
239            PabloAST * op = stmt->getOperand(i);
240            if (LLVM_UNLIKELY(illegalOperandType(op))) {
241                std::string tmp;
242                raw_string_ostream str(tmp);
243                PabloPrinter::print(op, str);
244                str << " cannot be an operand of ";
245                PabloPrinter::print(stmt, str);
246                throw std::runtime_error(str.str());
247            }
248        }
249
250        if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
251
252            PabloAST * const variable = cast<Assign>(stmt)->getVariable();
253            if (LLVM_UNLIKELY(!isa<Var>(variable) && !isa<Extract>(variable))) {
254                std::string tmp;
255                raw_string_ostream out(tmp);
256                out << "invalid assignment: ";
257                PabloPrinter::print(stmt, out);
258                out << "  --- ";
259                PabloPrinter::print(variable, out);
260                out << " must be a Var or Extract";
261                throw std::runtime_error(out.str());
262            }
263
264            PabloAST * const value = cast<Assign>(stmt)->getValue();
265            if (LLVM_UNLIKELY(variable->getType() != value->getType())) {
266                std::string tmp;
267                raw_string_ostream out(tmp);
268                out << "invalid assignment: ";
269                PabloPrinter::print(stmt, out);
270                out << "  --- type of ";
271                PabloPrinter::print(variable, out);
272                out << " differs from ";
273                PabloPrinter::print(value, out);
274                throw std::runtime_error(out.str());
275            }
276
277        } else if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
278            const PabloBlock * nested = cast<Branch>(stmt)->getBody();
279            if (LLVM_UNLIKELY(nested->getBranch() != stmt)) {
280                throwMisreportedBranchError(stmt, nested->getBranch());
281            } else if (LLVM_UNLIKELY(nested->getPredecessor() != block)) {
282                throwReportedScopeError(stmt);
283            }
284            ++nestingDepth;
285            verifyProgramStructure(nested, nestingDepth);
286            --nestingDepth;
287        }
288    }   
289}
290
291inline void verifyProgramStructure(const PabloKernel * kernel) {
292    unsigned nestingDepth = 0;
293    verifyProgramStructure(kernel->getEntryBlock(), nestingDepth);
294    if (LLVM_UNLIKELY(nestingDepth != 0)) {
295        // This error isn't actually possible to occur with the current AST structure but that could change
296        // in the future. Leaving this test in for a reminder to check for it.
297        throw std::runtime_error("PabloVerifier: unbalanced If or While nesting depth.");
298    }
299}
300
301/** ------------------------------------------------------------------------------------------------------------- *
302 * @brief isTopologicallyOrdered
303 ** ------------------------------------------------------------------------------------------------------------- */
304struct OrderingVerifier {
305    OrderingVerifier() : mParent(nullptr), mSet() {}
306    OrderingVerifier(const OrderingVerifier & parent) : mParent(&parent) {}
307    bool count(const PabloAST * expr) const {
308        if (mSet.count(expr)) {
309            return true;
310        } else if (mParent) {
311            return mParent->count(expr);
312        }
313        return false;
314    }
315    void insert(const PabloAST * expr) {
316        mSet.insert(expr);
317    }
318private:
319    const OrderingVerifier * const mParent;
320    SmallSet<const PabloAST *> mSet;
321};
322
323void isTopologicallyOrdered(const PabloBlock * block, const OrderingVerifier & parent) {
324    OrderingVerifier ov(parent);
325    for (const Statement * stmt : *block) {
326        if (LLVM_UNLIKELY(isa<While>(stmt))) {
327            isTopologicallyOrdered(cast<While>(stmt)->getBody(), ov);
328            for (const Var * var : cast<While>(stmt)->getEscaped()) {
329                ov.insert(var);
330            }
331        } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
332            ov.insert(cast<Assign>(stmt)->getVariable());
333        }
334        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
335            const PabloAST * const op = stmt->getOperand(i);
336            if (LLVM_UNLIKELY((isa<Statement>(op) || isa<Var>(op)) && ov.count(op) == 0)) {
337                std::string tmp;
338                raw_string_ostream out(tmp);
339                if (isa<Var>(op)) {
340                    PabloPrinter::print(op, out);
341                    out << " is used by ";
342                    PabloPrinter::print(stmt, out);
343                    out << " before being assigned a value.";
344                } else {
345                    PabloPrinter::print(op, out);
346                    if (LLVM_UNLIKELY(isa<Statement>(op) && unreachable(stmt, cast<Statement>(op)->getParent()))) {
347                        out << " was defined in a scope that is unreachable by ";
348                    } else {
349                        out << " was used before definition by ";
350                    }
351                    PabloPrinter::print(stmt, out);
352                }
353                throw std::runtime_error(out.str());
354            }
355        }
356        ov.insert(stmt);
357        if (LLVM_UNLIKELY(isa<If>(stmt))) {
358            isTopologicallyOrdered(cast<If>(stmt)->getBody(), ov);
359            for (const Var * def : cast<If>(stmt)->getEscaped()) {
360                ov.insert(def);
361            }
362        }
363    }
364}
365
366void isTopologicallyOrdered(const PabloKernel * kernel) {
367    OrderingVerifier ov;
368    for (unsigned i = 0; i != kernel->getNumOfInputs(); ++i) {
369        ov.insert(kernel->getInput(i));
370    }
371    for (unsigned i = 0; i != kernel->getNumOfOutputs(); ++i) {
372        ov.insert(kernel->getOutput(i));
373    }
374    isTopologicallyOrdered(kernel->getEntryBlock(), ov);
375}
376
377void PabloVerifier::verify(const PabloKernel * kernel, const std::string & location) {
378    try {
379        verifyProgramStructure(kernel);
380        verifyUseDefInformation(kernel);
381        isTopologicallyOrdered(kernel);
382    } catch(std::runtime_error & err) {
383        PabloPrinter::print(kernel, errs());
384        errs().flush();
385        if (location.empty()) {
386            llvm::report_fatal_error(err.what());
387        } else {
388            llvm::report_fatal_error(std::string(err.what()) + " @ " + location);
389        }
390    }
391}
392
393}
Note: See TracBrowser for help on using the repository browser.