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

Last change on this file since 5782 was 5782, checked in by nmedfort, 15 months ago

Initial check-in of LookAhead? support; modified LineBreakKernel? to compute CR+LF using LookAhead?(1) + misc. fixes.

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