source: icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

Last change on this file was 6215, checked in by cameron, 5 months ago

pablo.terminateAt

File size: 17.3 KB
Line 
1/*
2 *  Copyright (c) 2014 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6
7#include "pabloAST.h"
8#include <pablo/codegenstate.h>
9#include <pablo/pe_var.h>
10#include <pablo/boolean.h>
11#include <pablo/pe_infile.h>
12#include <pablo/pe_zeroes.h>
13#include <pablo/pe_ones.h>
14#include <pablo/ps_assign.h>
15#include <pablo/branch.h>
16#include <pablo/printer_pablos.h>
17#include <llvm/Support/ErrorHandling.h>
18#include <llvm/Support/raw_os_ostream.h>
19
20using namespace boost::container;
21using namespace llvm;
22
23namespace pablo {
24
25using TypeId = PabloAST::ClassTypeId;
26
27size_t constexpr __length(const char * const str) {
28    return *str ? 1 + __length(str + 1) : 0;
29}
30
31/** ------------------------------------------------------------------------------------------------------------- *
32 * @brief equals
33 *
34 *  Return true if expr1 and expr2 can be proven equivalent according to some rules, false otherwise.  Note that
35 *  false may be returned i some cases when the exprs are equivalent.
36 ** ------------------------------------------------------------------------------------------------------------- */
37bool equals(const PabloAST * const expr1, const PabloAST * const expr2) noexcept {
38    assert (expr1 && expr2);
39    if (LLVM_UNLIKELY(expr1 == expr2)) {
40        return true;
41    } else if (expr1->getClassTypeId() == expr2->getClassTypeId()) {
42        if (LLVM_LIKELY(expr1->getType() == expr2->getType())) {
43            if ((isa<Zeroes>(expr1)) || (isa<Ones>(expr1))) {
44                return true;
45            } else if (isa<Var>(expr1)) {
46                return (cast<Var>(expr1)->getName() == cast<Var>(expr2)->getName());
47            } else if (isa<Not>(expr1)) {
48                return equals(cast<Not>(expr1)->getOperand(0), cast<Not>(expr2)->getOperand(0));
49            } else if (isa<InFile>(expr1)) {
50                return equals(cast<InFile>(expr1)->getOperand(0), cast<InFile>(expr2)->getOperand(0));
51            } else if (isa<AtEOF>(expr1)) {
52                return equals(cast<AtEOF>(expr1)->getOperand(0), cast<AtEOF>(expr2)->getOperand(0));
53            } else if (isa<And>(expr1) || isa<Or>(expr1) || isa<Xor>(expr1)) {
54                PabloAST * op1[2];
55                PabloAST * op2[2];
56                op1[0] = cast<Statement>(expr1)->getOperand(0);
57                op1[1] = cast<Statement>(expr1)->getOperand(1);
58                if (op1[1] < op1[0]) {
59                    std::swap(op1[0], op1[1]);
60                }
61                op2[0] = cast<Statement>(expr2)->getOperand(0);
62                op2[1] = cast<Statement>(expr2)->getOperand(1);
63                if (op2[1] < op2[0]) {
64                    std::swap(op2[0], op2[1]);
65                }
66                return (op1[0] == op2[0]) && (op1[1] == op2[1]);
67            } else if (isa<Statement>(expr1)) {
68                const Statement * stmt1 = cast<Statement>(expr1);
69                const Statement * stmt2 = cast<Statement>(expr2);
70                assert (stmt1->getNumOperands() == stmt2->getNumOperands());
71                for (unsigned i = 0; i != stmt1->getNumOperands(); ++i) {
72                    if (!equals(stmt1->getOperand(i), stmt2->getOperand(i))) {
73                        return false;
74                    }
75                }
76                return true;
77            }
78
79        }
80    }
81    return false;
82}
83
84/** ------------------------------------------------------------------------------------------------------------- *
85 * @brief replaceAllUsesWith
86 ** ------------------------------------------------------------------------------------------------------------- */
87void PabloAST::replaceAllUsesWith(PabloAST * const expr) noexcept {
88    assert (expr);
89    if (LLVM_UNLIKELY(this == expr)) {
90        return;
91    }
92    Statement * replacement[mUsers.size()];
93    Users::size_type replacements = 0;
94    PabloAST * last = nullptr;
95    for (PabloAST * user : mUsers) {
96        if (LLVM_UNLIKELY(user == expr || user == last)) {
97            continue;
98        } else if (isa<Statement>(user)) {
99            replacement[replacements++] = cast<Statement>(user);
100            last = user;
101        }
102    }
103    for (Users::size_type i = 0; i != replacements; ++i) {
104        replacement[i]->replaceUsesOfWith(this, expr);
105    }
106}
107
108/** ------------------------------------------------------------------------------------------------------------- *
109 * @brief addUser
110 ** ------------------------------------------------------------------------------------------------------------- */
111bool PabloAST::addUser(PabloAST * const user) noexcept {
112    assert (user);
113    const auto p = std::lower_bound(mUsers.begin(), mUsers.end(), user);
114    const bool unique = p == mUsers.end() || *p != user;
115    mUsers.insert(p, user);
116    return unique;
117}
118
119/** ------------------------------------------------------------------------------------------------------------- *
120 * @brief removeUser
121 ** ------------------------------------------------------------------------------------------------------------- */
122bool PabloAST::removeUser(PabloAST * const user) noexcept {
123    assert (user);
124    const auto p = std::lower_bound(mUsers.begin(), mUsers.end(), user);
125    assert (p != mUsers.end() && *p == user);
126    const auto n = mUsers.erase(p);
127    return n == mUsers.end() || *n != user;
128}
129
130/** ------------------------------------------------------------------------------------------------------------- *
131 * @brief print
132 ** ------------------------------------------------------------------------------------------------------------- */
133void PabloAST::print(llvm::raw_ostream & O) const {
134    PabloPrinter::print(this, O);
135}
136
137/** ------------------------------------------------------------------------------------------------------------- *
138 * @brief setName
139 ** ------------------------------------------------------------------------------------------------------------- */
140void NamedPabloAST::setName(const String * const name) {
141    if (LLVM_UNLIKELY(name == nullptr)) {
142        llvm::report_fatal_error("name cannot be null");
143    }
144    mName = name;
145}
146
147/** ------------------------------------------------------------------------------------------------------------- *
148 * @brief getName
149 ** ------------------------------------------------------------------------------------------------------------- */
150const String & Statement::getName() const {
151    if (mName == nullptr) {
152        if (LLVM_UNLIKELY(mParent == nullptr)) {
153            llvm::report_fatal_error("cannot assign a default name to a statement that is not within a PabloBlock");
154        }
155        const char * prefix = nullptr;
156        size_t length = 0;
157        #define MAKE_PREFIX(type_id, name) \
158            case ClassTypeId:: type_id : prefix = name; length = __length(name); break
159        switch (mClassTypeId) {
160            // Boolean operations
161            MAKE_PREFIX(And, "and");
162            MAKE_PREFIX(Or, "or");
163            MAKE_PREFIX(Xor, "xor");
164            MAKE_PREFIX(Not, "not");
165            MAKE_PREFIX(Sel, "sel");
166            // Stream operations
167            MAKE_PREFIX(Advance, "advance");
168            MAKE_PREFIX(IndexedAdvance, "indexed_advance");
169            MAKE_PREFIX(ScanThru, "scanthru");
170            MAKE_PREFIX(AdvanceThenScanThru, "advscanthru");
171            MAKE_PREFIX(ScanTo, "scanto");
172            MAKE_PREFIX(AdvanceThenScanTo, "advscanto");
173            MAKE_PREFIX(Lookahead, "lookahead");
174            MAKE_PREFIX(MatchStar, "matchstar");
175            MAKE_PREFIX(InFile, "inFile");
176            MAKE_PREFIX(AtEOF, "atEOF");
177            MAKE_PREFIX(TerminateAt, "terminateAt");
178            // Statistics operations
179            MAKE_PREFIX(Count, "count");
180            // Misc. operations
181            MAKE_PREFIX(Repeat, "repeat");
182            MAKE_PREFIX(PackH, "packh");
183            MAKE_PREFIX(PackL, "packl");
184            default: llvm_unreachable("invalid statement type");
185        }
186        #undef MAKE_PREFIX
187        const StringRef __prefix(prefix, length);
188        mName = mParent->makeName(__prefix);
189    }
190    return *mName;
191}
192
193/** ------------------------------------------------------------------------------------------------------------- *
194 * @brief replaceUsesOfWith
195 ** ------------------------------------------------------------------------------------------------------------- */
196void Statement::replaceUsesOfWith(PabloAST * const from, PabloAST * const to) {
197    if (LLVM_LIKELY(from != to)) {
198        for (unsigned i = 0; i != getNumOperands(); ++i) {
199           if (getOperand(i) == from) {
200               setOperand(i, to);
201           }
202        }
203    }
204}
205
206/** ------------------------------------------------------------------------------------------------------------- *
207 * @brief setOperand
208 ** ------------------------------------------------------------------------------------------------------------- */
209void Statement::setOperand(const unsigned index, PabloAST * const value) {   
210    assert ("Operand cannot be null!" && value);
211    assert (index < getNumOperands());
212    PabloAST * const prior = getOperand(index);
213    assert ("Operand cannot be null!" && prior);
214    if (LLVM_UNLIKELY(prior == value)) {
215        return;
216    }     
217    if (LLVM_UNLIKELY(prior->getType() != value->getType())) {
218        std::string tmp;
219        raw_string_ostream out(tmp);
220        out << "Type mismatch replacing operand ";
221        prior->print(out);
222        out << " with ";
223        value->print(out);
224        out << " in statement ";
225        this->print(out);
226        llvm::report_fatal_error(out.str());
227    }
228    prior->removeUser(this);
229    mOperand[index] = value;
230    value->addUser(this);
231}
232
233/** ------------------------------------------------------------------------------------------------------------- *
234 * @brief insertBefore
235 ** ------------------------------------------------------------------------------------------------------------- */
236void Statement::insertBefore(Statement * const statement) {
237    if (LLVM_UNLIKELY(statement == this)) {
238        return;
239    } else if (LLVM_UNLIKELY(statement == nullptr)) {
240        llvm::report_fatal_error("cannot insert before null statement!");
241    } else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
242        llvm::report_fatal_error("statement is not contained in a pablo block!");
243    }
244    removeFromParent();
245    mParent = statement->mParent;
246    if (LLVM_UNLIKELY(mParent->mFirst == statement)) {
247        mParent->mFirst = this;
248    }
249    mNext = statement;
250    mPrev = statement->mPrev;
251    statement->mPrev = this;
252    if (LLVM_LIKELY(mPrev != nullptr)) {
253        mPrev->mNext = this;
254    }
255}
256
257/** ------------------------------------------------------------------------------------------------------------- *
258 * @brief insertAfter
259 ** ------------------------------------------------------------------------------------------------------------- */
260void Statement::insertAfter(Statement * const statement) {
261    if (LLVM_UNLIKELY(statement == this)) {
262        return;
263    } else if (LLVM_UNLIKELY(statement == nullptr)) {
264        llvm::report_fatal_error("cannot insert after null statement!");
265    } else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
266        llvm::report_fatal_error("statement is not contained in a pablo block!");
267    }
268    removeFromParent();
269    mParent = statement->mParent;
270    if (LLVM_UNLIKELY(mParent->mLast == statement)) {
271        mParent->mLast = this;
272    }
273    mPrev = statement;
274    mNext = statement->mNext;
275    statement->mNext = this;
276    if (LLVM_LIKELY(mNext != nullptr)) {
277        mNext->mPrev = this;
278    }
279}
280
281/** ------------------------------------------------------------------------------------------------------------- *
282 * @brief removeFromParent
283 ** ------------------------------------------------------------------------------------------------------------- */
284Statement * Statement::removeFromParent() noexcept {
285    Statement * next = mNext;
286    if (LLVM_LIKELY(mParent != nullptr)) {
287        if (LLVM_UNLIKELY(mParent->mFirst == this)) {
288            mParent->mFirst = mNext;
289        }
290        if (LLVM_UNLIKELY(mParent->mLast == this)) {
291            mParent->mLast = mPrev;
292        }
293        if (LLVM_UNLIKELY(mParent->mInsertionPoint == this)) {
294            mParent->mInsertionPoint = mPrev;
295        }
296        if (LLVM_LIKELY(mPrev != nullptr)) {
297            mPrev->mNext = mNext;
298        }
299        if (LLVM_LIKELY(mNext != nullptr)) {
300            mNext->mPrev = mPrev;
301        }
302    }
303    mPrev = nullptr;
304    mNext = nullptr;
305    mParent = nullptr;
306    return next;
307}
308
309/** ------------------------------------------------------------------------------------------------------------- *
310 * @brief eraseFromParent
311 ** ------------------------------------------------------------------------------------------------------------- */
312Statement * Statement::eraseFromParent(const bool recursively) noexcept {
313
314    if (LLVM_UNLIKELY(getParent() == nullptr)) {
315        return nullptr;
316    }
317
318    if (LLVM_UNLIKELY(isa<Branch>(this))) {
319        cast<Branch>(this)->getBody()->eraseFromParent(recursively);
320    } else if (LLVM_LIKELY(!isa<Assign>(this))) {
321        replaceAllUsesWith(getParent()->createZeroes(getType()));
322    }
323
324    Statement * const next = removeFromParent();
325    for (unsigned i = 0; i != mOperands; ++i) {
326        PabloAST * const op = mOperand[i]; assert (op);
327        op->removeUser(this);
328        if (LLVM_UNLIKELY(recursively && op->getNumUses() == 0)) {
329            if (LLVM_LIKELY(isa<Statement>(op))) {
330                cast<Statement>(op)->eraseFromParent(true);
331            }
332        }
333        mOperand[i] = nullptr;
334    }
335
336    return next;
337}
338
339/** ------------------------------------------------------------------------------------------------------------- *
340 * @brief replaceWith
341 ** ------------------------------------------------------------------------------------------------------------- */
342Statement * Statement::replaceWith(PabloAST * const expr, const bool rename, const bool recursively) noexcept {
343    assert (expr);
344    if (LLVM_UNLIKELY(expr == this)) {
345        return getNextNode();
346    }
347    if (LLVM_UNLIKELY(mName && rename)) {
348        if (LLVM_LIKELY(isa<Statement>(expr) && cast<Statement>(expr)->mName == nullptr)) {
349            cast<Statement>(expr)->setName(mName);
350            mName = nullptr;
351        }
352    }
353    replaceAllUsesWith(expr);
354    return eraseFromParent(recursively);
355}
356
357/** ------------------------------------------------------------------------------------------------------------- *
358 * @brief contains
359 ** ------------------------------------------------------------------------------------------------------------- */
360bool StatementList::contains(const Statement * const statement) const noexcept {
361    for (const Statement * stmt : *this) {
362        if (statement == stmt) {
363            return true;
364        }
365    }
366    return false;
367}
368
369/** ------------------------------------------------------------------------------------------------------------- *
370 * @brief dominates
371 *
372 * expr1 dominates (>>) expr2 if every path from the *entry* node to expr2 must go through expr1
373 *
374 * For example, consider the program (with entry node 1):
375 *
376 * 1. Assign a, s           1 >> 1, 2, 3, 4, 5, 6
377 * 2. While x:              2 >> 2, 3, 4, 5, 6
378 * 3.   Assign a, p         3 >> 3
379 * 4. While y:              4 >> 4, 5, 6
380 * 5.   Assign a, q         5 >> 5
381 * 6. Assign a, t           6 >> 6
382 ** ------------------------------------------------------------------------------------------------------------- */
383bool dominates(const PabloAST * const expr1, const PabloAST * const expr2) noexcept {
384    if (LLVM_UNLIKELY(expr1 == nullptr || expr2 == nullptr)) {
385        return (expr2 == nullptr);
386    } else if (LLVM_LIKELY(isa<Statement>(expr1))) {
387        const Statement * stmt1 = cast<Statement>(expr1);
388        assert ("expr1 is not in any block!" && stmt1->getParent());
389        if (isa<Statement>(expr2)) {
390            const Statement * stmt2 = cast<Statement>(expr2);
391            assert ("expr2 is not in any block!" && stmt2->getParent());
392
393            while (stmt1->getParent() != stmt2->getParent()) {
394                stmt2 = stmt2->getParent()->getBranch();
395                if (stmt2 == nullptr) {
396                    return false;
397                }
398            }
399
400            const Statement * temp1 = stmt1, * temp2 = stmt2;
401            while (temp1 && temp2) {
402                if (temp1 == stmt2) {
403                    return true;
404                } else if (temp2 == stmt1) {
405                    return false;
406                }
407                temp1 = temp1->getNextNode();
408                temp2 = temp2->getNextNode();
409            }
410            // If temp1 isn't null then temp2 must be null; thus stmt2 must succeed stmt1.
411            return (temp1 != nullptr);
412        }
413        return false;
414    }
415    return true;
416}
417
418/** ------------------------------------------------------------------------------------------------------------- *
419 * @brief postdominates
420 *
421 * expr1 post-dominates (<<) expr2 if all paths to the *exit* node starting at expr2 must go through expr1
422 *
423 * For example, consider the program (with exit node 6):
424 *
425 * 1. Assign a, s           1 << 1
426 * 2. While x:              2 << 1, 2
427 * 3.   Assign a, p         3 << 1, 2, 3
428 * 4. While y:              4 << 1, 2, 4
429 * 5.   Assign a, q         5 << 1, 2, 4, 5
430 * 6. Assign a, t           6 << 1, 2, 3, 4, 5, 6
431 ** ------------------------------------------------------------------------------------------------------------- */
432bool postdominates(const PabloAST * const expr1, const PabloAST * const expr2) noexcept {
433    throw std::runtime_error("not implemented yet!");
434}
435
436}
Note: See TracBrowser for help on using the repository browser.