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

Last change on this file since 5930 was 5930, checked in by cameron, 11 months ago

Auto RE grouping/threading

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