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

Last change on this file since 5217 was 5217, checked in by nmedfort, 2 years ago

Merged PabloFunction? and PabloKernel? classes. Updated projects where necessary.

File size: 15.1 KB
Line 
1#include "pabloverifier.hpp"
2#include <pablo/pablo_kernel.h>
3#include <pablo/codegenstate.h>
4#include <pablo/printer_pablos.h>
5#include <iostream>
6#include <boost/container/flat_set.hpp>
7#include <queue>
8
9
10namespace pablo {
11
12using TypeId = PabloAST::ClassTypeId;
13
14template <typename Type>
15using SmallSet = boost::container::flat_set<Type>;
16
17using ScopeSet = SmallSet<const PabloBlock *>;
18
19/** ------------------------------------------------------------------------------------------------------------- *
20 * @brief verifyUseDefInformation
21 ** ------------------------------------------------------------------------------------------------------------- */
22void testUsers(const PabloAST * expr, const ScopeSet & validScopes) { 
23    size_t uses = 0;
24    SmallSet<const PabloAST *> verified;
25    for (const PabloAST * use : expr->users()) {
26        if (LLVM_UNLIKELY(verified.count(use) != 0)) {
27            continue;
28        }
29        if (const Statement * const user = dyn_cast<Statement>(use)) {
30            // test whether this user is in a block in the program
31            if (LLVM_UNLIKELY(user->getParent() == nullptr || validScopes.count(user->getParent()) == 0)) {
32                std::string tmp;
33                raw_string_ostream str(tmp);
34                str << "use-def error: ";
35                PabloPrinter::print(user, str);
36                str << " is a user of ";
37                PabloPrinter::print(expr, str);
38                str << " but ";
39                PabloPrinter::print(use, str);
40                if (user->getParent() == nullptr) {
41                    str << " is not defined in any scope.";
42                } else {
43                    str << " is in an unreachable scope.";
44                }
45                throw std::runtime_error(str.str());
46            }
47            // expr may be used more than once by the same user.
48            bool notFound = true;
49            for (unsigned i = 0; i != user->getNumOperands(); ++i) {
50                if (user->getOperand(i) == expr) {
51                    notFound = false;
52                    ++uses;
53                }
54            }
55            if (isa<Branch>(user)) {
56                for (const PabloAST * var : cast<Branch>(user)->getEscaped()) {
57                    if (var == expr) {
58                        notFound = false;
59                        ++uses;
60                    }
61                }
62            }
63            if (LLVM_UNLIKELY(notFound)) {
64                std::string tmp;
65                raw_string_ostream str(tmp);
66                str << "use-def error: ";
67                PabloPrinter::print(expr, str);
68                str << " is not a definition of ";
69                PabloPrinter::print(use, str);
70                throw std::runtime_error(str.str());
71            }
72        } else if (isa<Var>(use)) {
73            if (LLVM_UNLIKELY(isa<Branch>(expr))) {
74                ++uses;
75            } else {
76                std::string tmp;
77                raw_string_ostream str(tmp);
78                str << "use-def error: var ";
79                PabloPrinter::print(use, str);
80                str << " is a user of ";
81                PabloPrinter::print(expr, str);
82                str << " but can only be a user of a Branch or Function.";
83                throw std::runtime_error(str.str());
84            }
85        }
86        verified.insert(use);
87    }
88    if (LLVM_UNLIKELY(uses != expr->getNumUses())) {
89        std::string tmp;
90        raw_string_ostream str(tmp);
91        str << "use-def error: ";
92        PabloPrinter::print(expr, str);
93        str << " is reported having " << expr->getNumUses() << " user(s)"
94            << " but was observed having " << uses << " user(s)";
95        throw std::runtime_error(str.str());
96    }
97}
98
99void testDefs(const Statement * stmt) {
100    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
101        const PabloAST * const def = stmt->getOperand(i);
102        bool notFound = true;
103        for (const PabloAST * use : def->users()) {
104            if (use == stmt) {
105                notFound = false;
106                break;
107            }
108        }
109        if (LLVM_UNLIKELY(notFound)) {
110            std::string tmp;
111            raw_string_ostream str(tmp);
112            str << "PabloVerifier: def-use error: ";
113            PabloPrinter::print(stmt, str);
114            str << " is not recorded in ";
115            PabloPrinter::print(def, str);
116            str << "'s user list";
117            throw std::runtime_error(str.str());
118        }
119    }
120}
121
122void verifyUseDefInformation(const PabloBlock * block, const ScopeSet & validScopes) {
123    for (const Statement * stmt : *block) {
124        testUsers(stmt, validScopes);
125        testDefs(stmt);
126        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
127            verifyUseDefInformation(cast<Branch>(stmt)->getBody(), validScopes);
128        }
129    }
130}
131
132void gatherValidScopes(const PabloBlock * block, ScopeSet & validScopes) {
133    validScopes.insert(block);
134    for (const Statement * stmt : *block) {
135        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
136            gatherValidScopes(cast<Branch>(stmt)->getBody(), validScopes);
137        }
138    }
139}
140
141void verifyUseDefInformation(const PabloKernel * kernel) {
142    ScopeSet validScopes;
143    gatherValidScopes(kernel->getEntryBlock(), validScopes);
144    for (unsigned i = 0; i < kernel->getNumOfInputs(); ++i) {
145        testUsers(kernel->getInput(i), validScopes);
146    }
147    for (unsigned i = 0; i < kernel->getNumOfOutputs(); ++i) {
148        testUsers(kernel->getOutput(i), validScopes);
149    }
150    verifyUseDefInformation(kernel->getEntryBlock(), validScopes);
151}
152
153/** ------------------------------------------------------------------------------------------------------------- *
154 * @brief unreachable
155 ** ------------------------------------------------------------------------------------------------------------- */
156bool unreachable(const Statement * stmt, const PabloBlock * const block) {
157    PabloBlock * parent = stmt->getParent();
158    while (parent)  {
159        if (parent == block) {
160            return false;
161        }
162        parent = parent->getPredecessor();
163    }
164    return true;
165}
166
167/** ------------------------------------------------------------------------------------------------------------- *
168 * @brief throwReportedScopeError
169 ** ------------------------------------------------------------------------------------------------------------- */
170static void throwReportedScopeError(const Statement * const stmt) {
171    std::string tmp;
172    raw_string_ostream str(tmp);
173    str << "structure error: ";
174    PabloPrinter::print(stmt, str);
175    str << " is not contained in its reported scope block";
176    throw std::runtime_error(str.str());
177}
178
179/** ------------------------------------------------------------------------------------------------------------- *
180 * @brief throwMisreportedBranchError
181 ** ------------------------------------------------------------------------------------------------------------- */
182static void throwMisreportedBranchError(const Statement * const stmt, const Statement * const branch) {
183    std::string tmp;
184    raw_string_ostream str(tmp);
185    str << "structure error: ";
186    PabloPrinter::print(stmt, str);
187    str << " branches into a scope block that reports ";
188    PabloPrinter::print(branch, str);
189    str << " as its branching statement.";
190    throw std::runtime_error(str.str());
191}
192
193/** ------------------------------------------------------------------------------------------------------------- *
194 * @brief illegalOperandType
195 ** ------------------------------------------------------------------------------------------------------------- */
196static inline bool illegalOperandType(const PabloAST * const op) {
197    switch (op->getClassTypeId()) {
198        case TypeId::Block:
199        case TypeId::Function:
200        case TypeId::Prototype:
201        case TypeId::Assign:
202        case TypeId::Call:
203        case TypeId::SetIthBit:
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) {}
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        raw_os_ostream out(std::cerr);
385        PabloPrinter::print(kernel, out);
386        out.flush();
387        if (location.empty()) {
388            llvm::report_fatal_error(err.what());
389        } else {
390            llvm::report_fatal_error(std::string(err.what()) + " @ " + location);
391        }
392    }
393}
394
395}
Note: See TracBrowser for help on using the repository browser.