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

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

Bug fixes for Carry Manager and issues reported by Fahad

File size: 15.1 KB
RevLine 
[4766]1#include "pabloverifier.hpp"
[5217]2#include <pablo/pablo_kernel.h>
[4766]3#include <pablo/codegenstate.h>
4#include <pablo/printer_pablos.h>
[4773]5#include <iostream>
[4775]6#include <boost/container/flat_set.hpp>
[4856]7#include <queue>
[4766]8
[4856]9
[4766]10namespace pablo {
11
[5202]12using TypeId = PabloAST::ClassTypeId;
13
[4804]14template <typename Type>
15using SmallSet = boost::container::flat_set<Type>;
[4797]16
[4804]17using ScopeSet = SmallSet<const PabloBlock *>;
18
[4797]19/** ------------------------------------------------------------------------------------------------------------- *
20 * @brief verifyUseDefInformation
21 ** ------------------------------------------------------------------------------------------------------------- */
[5202]22void testUsers(const PabloAST * expr, const ScopeSet & validScopes) { 
[5156]23    size_t uses = 0;
24    SmallSet<const PabloAST *> verified;
25    for (const PabloAST * use : expr->users()) {
[5202]26        if (LLVM_UNLIKELY(verified.count(use) != 0)) {
27            continue;
28        }
[5217]29        if (const Statement * const user = dyn_cast<Statement>(use)) {
[5202]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.";
[5156]44                }
[5202]45                throw std::runtime_error(str.str());
[5156]46            }
[5202]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;
[5156]53                }
[5202]54            }
55            if (isa<Branch>(user)) {
56                for (const PabloAST * var : cast<Branch>(user)->getEscaped()) {
57                    if (var == expr) {
58                        notFound = false;
59                        ++uses;
[4797]60                    }
61                }
[5202]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)) {
[5217]73            if (LLVM_UNLIKELY(isa<Branch>(expr))) {
[5156]74                ++uses;
[5202]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());
[4797]84            }
85        }
[5202]86        verified.insert(use);
[5156]87    }
88    if (LLVM_UNLIKELY(uses != expr->getNumUses())) {
89        std::string tmp;
90        raw_string_ostream str(tmp);
[5202]91        str << "use-def error: ";
[5156]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;
[4797]107            }
108        }
[5156]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);
[5202]126        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
127            verifyUseDefInformation(cast<Branch>(stmt)->getBody(), validScopes);
[4797]128        }
129    }
130}
131
[4870]132void gatherValidScopes(const PabloBlock * block, ScopeSet & validScopes) {
133    validScopes.insert(block);
134    for (const Statement * stmt : *block) {
[5202]135        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
136            gatherValidScopes(cast<Branch>(stmt)->getBody(), validScopes);
[4797]137        }
138    }
139}
140
[5217]141void verifyUseDefInformation(const PabloKernel * kernel) {
[4797]142    ScopeSet validScopes;
[5217]143    gatherValidScopes(kernel->getEntryBlock(), validScopes);
144    for (unsigned i = 0; i < kernel->getNumOfInputs(); ++i) {
145        testUsers(kernel->getInput(i), validScopes);
[5156]146    }
[5217]147    for (unsigned i = 0; i < kernel->getNumOfOutputs(); ++i) {
148        testUsers(kernel->getOutput(i), validScopes);
[5156]149    }
[5217]150    verifyUseDefInformation(kernel->getEntryBlock(), validScopes);
[4797]151}
152
153/** ------------------------------------------------------------------------------------------------------------- *
[4866]154 * @brief unreachable
155 ** ------------------------------------------------------------------------------------------------------------- */
[4870]156bool unreachable(const Statement * stmt, const PabloBlock * const block) {
[4866]157    PabloBlock * parent = stmt->getParent();
158    while (parent)  {
[4870]159        if (parent == block) {
[4866]160            return false;
161        }
[5202]162        parent = parent->getPredecessor();
[4866]163    }
164    return true;
165}
166
167/** ------------------------------------------------------------------------------------------------------------- *
[4919]168 * @brief throwReportedScopeError
169 ** ------------------------------------------------------------------------------------------------------------- */
170static void throwReportedScopeError(const Statement * const stmt) {
171    std::string tmp;
172    raw_string_ostream str(tmp);
[5202]173    str << "structure error: ";
[4919]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);
[5202]185    str << "structure error: ";
[4919]186    PabloPrinter::print(stmt, str);
187    str << " branches into a scope block that reports ";
[5156]188    PabloPrinter::print(branch, str);
[4919]189    str << " as its branching statement.";
190    throw std::runtime_error(str.str());
191}
192
193/** ------------------------------------------------------------------------------------------------------------- *
[5202]194 * @brief illegalOperandType
[4919]195 ** ------------------------------------------------------------------------------------------------------------- */
[5202]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    }
[4919]210}
211
212/** ------------------------------------------------------------------------------------------------------------- *
[4797]213 * @brief verifyProgramStructure
214 ** ------------------------------------------------------------------------------------------------------------- */
[4959]215void verifyProgramStructure(const PabloBlock * block, unsigned & nestingDepth) {
[4797]216    const Statement * prev = nullptr;
[4870]217    for (const Statement * stmt : *block) {
[4797]218        if (LLVM_UNLIKELY(stmt->getPrevNode() != prev)) {
219            std::string tmp;
220            raw_string_ostream str(tmp);
[4870]221            PabloPrinter::print(stmt, str);
[4797]222            str << " succeeds ";
223            PabloPrinter::print(prev, str);
[5202]224            str << " but ";
225            PabloPrinter::print(cast<PabloAST>(stmt), str);
226            str << " expects to succeed ";
[4797]227            PabloPrinter::print(stmt->getPrevNode(), str);
228            throw std::runtime_error(str.str());
229        }
230        prev = stmt;
[4870]231        if (LLVM_UNLIKELY(stmt->getParent() != block)) {
[4797]232            std::string tmp;
233            raw_string_ostream str(tmp);
[4870]234            PabloPrinter::print(stmt, str);
[4797]235            str << " is not contained in its reported scope block";
236            throw std::runtime_error(str.str());
237        }
[5202]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();
[4919]280            if (LLVM_UNLIKELY(nested->getBranch() != stmt)) {
281                throwMisreportedBranchError(stmt, nested->getBranch());
[5202]282            } else if (LLVM_UNLIKELY(nested->getPredecessor() != block)) {
[4919]283                throwReportedScopeError(stmt);
[4797]284            }
[4959]285            ++nestingDepth;
286            verifyProgramStructure(nested, nestingDepth);
287            --nestingDepth;
[4797]288        }
[4959]289    }   
[4797]290}
291
[5217]292inline void verifyProgramStructure(const PabloKernel * kernel) {
[4959]293    unsigned nestingDepth = 0;
[5217]294    verifyProgramStructure(kernel->getEntryBlock(), nestingDepth);
[4959]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    }
[4797]300}
301
302/** ------------------------------------------------------------------------------------------------------------- *
303 * @brief isTopologicallyOrdered
304 ** ------------------------------------------------------------------------------------------------------------- */
[4766]305struct OrderingVerifier {
[5233]306    OrderingVerifier() : mParent(nullptr), mSet() {}
[4766]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;
[4804]321    SmallSet<const PabloAST *> mSet;
[4766]322};
323
[4870]324void isTopologicallyOrdered(const PabloBlock * block, const OrderingVerifier & parent) {
[4766]325    OrderingVerifier ov(parent);
[4870]326    for (const Statement * stmt : *block) {
[4771]327        if (LLVM_UNLIKELY(isa<While>(stmt))) {
[4797]328            isTopologicallyOrdered(cast<While>(stmt)->getBody(), ov);
[5202]329            for (const Var * var : cast<While>(stmt)->getEscaped()) {
[4771]330                ov.insert(var);
331            }
[5202]332        } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
333            ov.insert(cast<Assign>(stmt)->getVariable());
[4771]334        }
[4766]335        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
[4797]336            const PabloAST * const op = stmt->getOperand(i);
337            if (LLVM_UNLIKELY((isa<Statement>(op) || isa<Var>(op)) && ov.count(op) == 0)) {
[4856]338                std::string tmp;
[5202]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.";
[4876]345                } else {
[5202]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);
[4876]353                }
[5202]354                throw std::runtime_error(out.str());
[4766]355            }
356        }
357        ov.insert(stmt);
358        if (LLVM_UNLIKELY(isa<If>(stmt))) {
[4797]359            isTopologicallyOrdered(cast<If>(stmt)->getBody(), ov);
[5202]360            for (const Var * def : cast<If>(stmt)->getEscaped()) {
[4766]361                ov.insert(def);
362            }
363        }
364    }
365}
366
[5217]367void isTopologicallyOrdered(const PabloKernel * kernel) {
[4766]368    OrderingVerifier ov;
[5217]369    for (unsigned i = 0; i != kernel->getNumOfInputs(); ++i) {
370        ov.insert(kernel->getInput(i));
[4766]371    }
[5217]372    for (unsigned i = 0; i != kernel->getNumOfOutputs(); ++i) {
373        ov.insert(kernel->getOutput(i));
[5202]374    }
[5217]375    isTopologicallyOrdered(kernel->getEntryBlock(), ov);
[4766]376}
377
[5217]378void PabloVerifier::verify(const PabloKernel * kernel, const std::string & location) {
[4773]379    try {
[5217]380        verifyProgramStructure(kernel);
381        verifyUseDefInformation(kernel);
382        isTopologicallyOrdered(kernel);
[5082]383    } catch(std::runtime_error & err) {
[4773]384        raw_os_ostream out(std::cerr);
[5217]385        PabloPrinter::print(kernel, out);
[4773]386        out.flush();
[4797]387        if (location.empty()) {
[5202]388            llvm::report_fatal_error(err.what());
[4797]389        } else {
[5202]390            llvm::report_fatal_error(std::string(err.what()) + " @ " + location);
[4797]391        }
[4773]392    }
[4766]393}
394
395}
Note: See TracBrowser for help on using the repository browser.