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

Last change on this file since 5834 was 5834, checked in by nmedfort, 18 months ago

Removed Variadic functionality; allowed for deferred creation of statement names

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