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

Last change on this file was 6189, checked in by nmedfort, 6 months ago

Bug fixes for 32-bit

File size: 16.6 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
262            Type * const A = value->getType();
263            Type * const B = variable->getType();
264
265            bool invalid = false;
266            if (A->isIntegerTy() && B->isIntegerTy()) {
267                invalid = A->getPrimitiveSizeInBits() > B->getPrimitiveSizeInBits();
268            } else {
269                invalid = !A->canLosslesslyBitCastTo(B);
270            }
271
272            if (LLVM_UNLIKELY(invalid)) {
273                std::string tmp;
274                raw_string_ostream out(tmp);
275                out << "invalid assignment: ";
276                PabloPrinter::print(stmt, out);
277                out << "  --- value cannot fit wthin variable";
278                throw std::runtime_error(out.str());
279            }
280
281        } else if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
282            const PabloBlock * nested = cast<Branch>(stmt)->getBody();
283            if (LLVM_UNLIKELY(nested->getBranch() != stmt)) {
284                throwMisreportedBranchError(stmt, nested->getBranch());
285            } else if (LLVM_UNLIKELY(nested->getPredecessor() != block)) {
286                throwReportedScopeError(stmt);
287            }
288            ++nestingDepth;
289            verifyProgramStructure(nested, nestingDepth);
290            --nestingDepth;
291        }
292    }   
293}
294
295inline void verifyProgramStructure(const PabloKernel * kernel) {
296    unsigned nestingDepth = 0;
297    verifyProgramStructure(kernel->getEntryScope(), nestingDepth);
298    if (LLVM_UNLIKELY(nestingDepth != 0)) {
299        // This error isn't actually possible to occur with the current AST structure but that could change
300        // in the future. Leaving this test in for a reminder to check for it.
301        throw std::runtime_error("PabloVerifier: unbalanced If or While nesting depth.");
302    }
303}
304
305/** ------------------------------------------------------------------------------------------------------------- *
306 * @brief verifyAllPathsDominate
307 ** ------------------------------------------------------------------------------------------------------------- */
308void verifyAllPathsDominate(const PabloBlock * block) {
309    for (const Statement * stmt : *block) {
310        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
311            const PabloAST * const op = stmt->getOperand(i);
312            if (LLVM_UNLIKELY(!dominates(op, stmt))) {
313                std::string tmp;
314                raw_string_ostream out(tmp);
315                PabloPrinter::print(cast<Statement>(op), out);
316                out << " does not dominate ";
317                PabloPrinter::print(stmt, out);
318                throw std::runtime_error(out.str());
319            }
320        }
321        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
322            verifyAllPathsDominate(cast<Branch>(stmt)->getBody());
323        }
324    }
325}
326
327void verifyAllPathsDominate(const PabloKernel * kernel) {
328    verifyAllPathsDominate(kernel->getEntryScope());
329}
330
331/** ------------------------------------------------------------------------------------------------------------- *
332 * @brief verifyVariableAssignments
333 ** ------------------------------------------------------------------------------------------------------------- */
334struct AssignmentSet {
335    AssignmentSet() : mParent(nullptr), mSet() {}
336    AssignmentSet(const AssignmentSet & parent) : mParent(&parent) {}
337    bool contains(const Var * expr) const {
338        if (mSet.count(expr)) {
339            return true;
340        } else if (mParent) {
341            return mParent->contains(expr);
342        }
343        return false;
344    }
345
346    void insert_full(const Var * expr) {
347        const auto n = getNumOfElements(expr);
348        auto f = mAssignment.find(expr);
349        if (LLVM_LIKELY(f == mAssignment.end())) {
350            mAssignment.insert(std::make_pair(expr, SmallBitVector(n, true)));
351        } else {
352            f->second.resize(n, true);
353        }
354    }
355
356    void insert(const Var * expr, const unsigned i) {
357        mSet.insert(expr);
358    }
359protected:
360
361    static unsigned getNumOfElements(const Var * expr) {
362        const Type * const ty = expr->getType();
363        if (ty->isArrayTy()) {
364            return ty->getArrayNumElements();
365        }
366        return 1;
367    }
368
369private:
370    const AssignmentSet * const mParent;
371    DenseMap<const Var *, SmallBitVector> mAssignment;
372
373    SmallSet<const Var *, 16> mSet;
374};
375
376//void verifyVariableUsages(const PabloBlock * block, const AssignmentSet & parent) {
377//    AssignmentSet A(parent);
378//    for (const Statement * stmt : *block) {
379//        if (isa<Assign>(stmt)) {
380//            PabloAST * var = cast<Assign>(stmt)->getVariable();
381//            if (isa<Extract>(var)) {
382//                var = cast<Extract>(var)->getArray();
383//            }
384//            A.insert(cast<Var>(var));
385//        } else if (isa<Extract>(stmt)) {
386//            Var * const var = cast<Var>(cast<Extract>(var)->getArray());
387//            if (A.contains(var)) {
388//                continue;
389//            }
390//        } else {
391//            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
392//                const PabloAST * const op = stmt->getOperand(i);
393//                if (isa<Var>(op)) {
394
395//                }
396//            }
397//        }
398
399
400
401//        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
402//            const PabloAST * const op = stmt->getOperand(i);
403//            if (LLVM_UNLIKELY(!dominates(op, stmt))) {
404//                std::string tmp;
405//                raw_string_ostream out(tmp);
406//                PabloPrinter::print(cast<Statement>(op), out);
407//                out << " does not dominate ";
408//                PabloPrinter::print(stmt, out);
409//                throw std::runtime_error(out.str());
410//            }
411//        }
412//        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
413//            verifyAllPathsDominate(cast<Branch>(stmt)->getBody());
414//        }
415//    }
416//}
417
418//void verifyVariableUsages(const PabloKernel * kernel) {
419//    AssignmentSet A;
420//    for (unsigned i = 0; i != kernel->getNumOfInputs(); ++i) {
421//        A.insert(kernel->getInput(i));
422//    }
423//    for (unsigned i = 0; i != kernel->getNumOfOutputs(); ++i) {
424//        A.insert(kernel->getOutput(i));
425//    }
426//    verifyVariableUsages(kernel->getEntryScope(), A);
427//}
428
429
430
431void PabloVerifier::verify(const PabloKernel * kernel, const std::string & location) {
432    try {
433        verifyProgramStructure(kernel);
434        verifyUseDefInformation(kernel);
435        verifyAllPathsDominate(kernel);
436    } catch(std::runtime_error & err) {
437        PabloPrinter::print(kernel, errs());
438        errs().flush();
439        if (location.empty()) {
440            llvm::report_fatal_error(err.what());
441        } else {
442            llvm::report_fatal_error(std::string(err.what()) + " @ " + location);
443        }
444    }
445}
446
447}
Note: See TracBrowser for help on using the repository browser.