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

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

Bug fix for long advance

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