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

Last change on this file since 5933 was 5933, checked in by cameron, 14 months ago

Including IR/DerivedTypes.h for missing inlines: getSequentialElementType

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