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

Last change on this file since 6155 was 5836, checked in by nmedfort, 20 months ago

Added PabloBlock/Builder? createScope() methods + minor code changes.

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            // Statistics operations
178            MAKE_PREFIX(Count, "count");
179            // Misc. operations
180            MAKE_PREFIX(Repeat, "repeat");
181            MAKE_PREFIX(PackH, "packh");
182            MAKE_PREFIX(PackL, "packl");
183            default: llvm_unreachable("invalid statement type");
184        }
185        #undef MAKE_PREFIX
186        const StringRef __prefix(prefix, length);
187        mName = mParent->makeName(__prefix);
188    }
189    return *mName;
190}
191
192/** ------------------------------------------------------------------------------------------------------------- *
193 * @brief replaceUsesOfWith
194 ** ------------------------------------------------------------------------------------------------------------- */
195void Statement::replaceUsesOfWith(PabloAST * const from, PabloAST * const to) {
196    if (LLVM_LIKELY(from != to)) {
197        for (unsigned i = 0; i != getNumOperands(); ++i) {
198           if (getOperand(i) == from) {
199               setOperand(i, to);
200           }
201        }
202    }
203}
204
205/** ------------------------------------------------------------------------------------------------------------- *
206 * @brief setOperand
207 ** ------------------------------------------------------------------------------------------------------------- */
208void Statement::setOperand(const unsigned index, PabloAST * const value) {   
209    assert ("Operand cannot be null!" && value);
210    assert (index < getNumOperands());
211    PabloAST * const prior = getOperand(index);
212    assert ("Operand cannot be null!" && prior);
213    if (LLVM_UNLIKELY(prior == value)) {
214        return;
215    }     
216    if (LLVM_UNLIKELY(prior->getType() != value->getType())) {
217        std::string tmp;
218        raw_string_ostream out(tmp);
219        out << "Type mismatch replacing operand ";
220        prior->print(out);
221        out << " with ";
222        value->print(out);
223        out << " in statement ";
224        this->print(out);
225        llvm::report_fatal_error(out.str());
226    }
227    prior->removeUser(this);
228    mOperand[index] = value;
229    value->addUser(this);
230}
231
232/** ------------------------------------------------------------------------------------------------------------- *
233 * @brief insertBefore
234 ** ------------------------------------------------------------------------------------------------------------- */
235void Statement::insertBefore(Statement * const statement) {
236    if (LLVM_UNLIKELY(statement == this)) {
237        return;
238    } else if (LLVM_UNLIKELY(statement == nullptr)) {
239        llvm::report_fatal_error("cannot insert before null statement!");
240    } else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
241        llvm::report_fatal_error("statement is not contained in a pablo block!");
242    }
243    removeFromParent();
244    mParent = statement->mParent;
245    if (LLVM_UNLIKELY(mParent->mFirst == statement)) {
246        mParent->mFirst = this;
247    }
248    mNext = statement;
249    mPrev = statement->mPrev;
250    statement->mPrev = this;
251    if (LLVM_LIKELY(mPrev != nullptr)) {
252        mPrev->mNext = this;
253    }
254}
255
256/** ------------------------------------------------------------------------------------------------------------- *
257 * @brief insertAfter
258 ** ------------------------------------------------------------------------------------------------------------- */
259void Statement::insertAfter(Statement * const statement) {
260    if (LLVM_UNLIKELY(statement == this)) {
261        return;
262    } else if (LLVM_UNLIKELY(statement == nullptr)) {
263        llvm::report_fatal_error("cannot insert after null statement!");
264    } else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
265        llvm::report_fatal_error("statement is not contained in a pablo block!");
266    }
267    removeFromParent();
268    mParent = statement->mParent;
269    if (LLVM_UNLIKELY(mParent->mLast == statement)) {
270        mParent->mLast = this;
271    }
272    mPrev = statement;
273    mNext = statement->mNext;
274    statement->mNext = this;
275    if (LLVM_LIKELY(mNext != nullptr)) {
276        mNext->mPrev = this;
277    }
278}
279
280/** ------------------------------------------------------------------------------------------------------------- *
281 * @brief removeFromParent
282 ** ------------------------------------------------------------------------------------------------------------- */
283Statement * Statement::removeFromParent() noexcept {
284    Statement * next = mNext;
285    if (LLVM_LIKELY(mParent != nullptr)) {
286        if (LLVM_UNLIKELY(mParent->mFirst == this)) {
287            mParent->mFirst = mNext;
288        }
289        if (LLVM_UNLIKELY(mParent->mLast == this)) {
290            mParent->mLast = mPrev;
291        }
292        if (LLVM_UNLIKELY(mParent->mInsertionPoint == this)) {
293            mParent->mInsertionPoint = mPrev;
294        }
295        if (LLVM_LIKELY(mPrev != nullptr)) {
296            mPrev->mNext = mNext;
297        }
298        if (LLVM_LIKELY(mNext != nullptr)) {
299            mNext->mPrev = mPrev;
300        }
301    }
302    mPrev = nullptr;
303    mNext = nullptr;
304    mParent = nullptr;
305    return next;
306}
307
308/** ------------------------------------------------------------------------------------------------------------- *
309 * @brief eraseFromParent
310 ** ------------------------------------------------------------------------------------------------------------- */
311Statement * Statement::eraseFromParent(const bool recursively) noexcept {
312
313    if (LLVM_UNLIKELY(getParent() == nullptr)) {
314        return nullptr;
315    }
316
317    if (LLVM_UNLIKELY(isa<Branch>(this))) {
318        cast<Branch>(this)->getBody()->eraseFromParent(recursively);
319    } else if (LLVM_LIKELY(!isa<Assign>(this))) {
320        replaceAllUsesWith(getParent()->createZeroes(getType()));
321    }
322
323    Statement * const next = removeFromParent();
324    for (unsigned i = 0; i != mOperands; ++i) {
325        PabloAST * const op = mOperand[i]; assert (op);
326        op->removeUser(this);
327        if (LLVM_UNLIKELY(recursively && op->getNumUses() == 0)) {
328            if (LLVM_LIKELY(isa<Statement>(op))) {
329                cast<Statement>(op)->eraseFromParent(true);
330            }
331        }
332        mOperand[i] = nullptr;
333    }
334
335    return next;
336}
337
338/** ------------------------------------------------------------------------------------------------------------- *
339 * @brief replaceWith
340 ** ------------------------------------------------------------------------------------------------------------- */
341Statement * Statement::replaceWith(PabloAST * const expr, const bool rename, const bool recursively) noexcept {
342    assert (expr);
343    if (LLVM_UNLIKELY(expr == this)) {
344        return getNextNode();
345    }
346    if (LLVM_UNLIKELY(mName && rename)) {
347        if (LLVM_LIKELY(isa<Statement>(expr) && cast<Statement>(expr)->mName == nullptr)) {
348            cast<Statement>(expr)->setName(mName);
349            mName = nullptr;
350        }
351    }
352    replaceAllUsesWith(expr);
353    return eraseFromParent(recursively);
354}
355
356/** ------------------------------------------------------------------------------------------------------------- *
357 * @brief contains
358 ** ------------------------------------------------------------------------------------------------------------- */
359bool StatementList::contains(const Statement * const statement) const noexcept {
360    for (const Statement * stmt : *this) {
361        if (statement == stmt) {
362            return true;
363        }
364    }
365    return false;
366}
367
368/** ------------------------------------------------------------------------------------------------------------- *
369 * @brief dominates
370 *
371 * expr1 dominates (>>) expr2 if every path from the *entry* node to expr2 must go through expr1
372 *
373 * For example, consider the program (with entry node 1):
374 *
375 * 1. Assign a, s           1 >> 1, 2, 3, 4, 5, 6
376 * 2. While x:              2 >> 2, 3, 4, 5, 6
377 * 3.   Assign a, p         3 >> 3
378 * 4. While y:              4 >> 4, 5, 6
379 * 5.   Assign a, q         5 >> 5
380 * 6. Assign a, t           6 >> 6
381 ** ------------------------------------------------------------------------------------------------------------- */
382bool dominates(const PabloAST * const expr1, const PabloAST * const expr2) noexcept {
383    if (LLVM_UNLIKELY(expr1 == nullptr || expr2 == nullptr)) {
384        return (expr2 == nullptr);
385    } else if (LLVM_LIKELY(isa<Statement>(expr1))) {
386        const Statement * stmt1 = cast<Statement>(expr1);
387        assert ("expr1 is not in any block!" && stmt1->getParent());
388        if (isa<Statement>(expr2)) {
389            const Statement * stmt2 = cast<Statement>(expr2);
390            assert ("expr2 is not in any block!" && stmt2->getParent());
391
392            while (stmt1->getParent() != stmt2->getParent()) {
393                stmt2 = stmt2->getParent()->getBranch();
394                if (stmt2 == nullptr) {
395                    return false;
396                }
397            }
398
399            const Statement * temp1 = stmt1, * temp2 = stmt2;
400            while (temp1 && temp2) {
401                if (temp1 == stmt2) {
402                    return true;
403                } else if (temp2 == stmt1) {
404                    return false;
405                }
406                temp1 = temp1->getNextNode();
407                temp2 = temp2->getNextNode();
408            }
409            // If temp1 isn't null then temp2 must be null; thus stmt2 must succeed stmt1.
410            return (temp1 != nullptr);
411        }
412        return false;
413    }
414    return true;
415}
416
417/** ------------------------------------------------------------------------------------------------------------- *
418 * @brief postdominates
419 *
420 * expr1 post-dominates (<<) expr2 if all paths to the *exit* node starting at expr2 must go through expr1
421 *
422 * For example, consider the program (with exit node 6):
423 *
424 * 1. Assign a, s           1 << 1
425 * 2. While x:              2 << 1, 2
426 * 3.   Assign a, p         3 << 1, 2, 3
427 * 4. While y:              4 << 1, 2, 4
428 * 5.   Assign a, q         5 << 1, 2, 4, 5
429 * 6. Assign a, t           6 << 1, 2, 3, 4, 5, 6
430 ** ------------------------------------------------------------------------------------------------------------- */
431bool postdominates(const PabloAST * const expr1, const PabloAST * const expr2) noexcept {
432    throw std::runtime_error("not implemented yet!");
433}
434
435}
Note: See TracBrowser for help on using the repository browser.