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

Last change on this file since 5828 was 5828, checked in by nmedfort, 12 months ago

Pablo support for byte comparisions; LineFeed? kernel processes byte streams directly. Some clean up of PabloBuilder? functionality.

File size: 17.1 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
27/** ------------------------------------------------------------------------------------------------------------- *
28 * @brief equals
29 *
30 *  Return true if expr1 and expr2 can be proven equivalent according to some rules, false otherwise.  Note that
31 *  false may be returned i some cases when the exprs are equivalent.
32 ** ------------------------------------------------------------------------------------------------------------- */
33bool equals(const PabloAST * const expr1, const PabloAST * const expr2) {
34    assert (expr1 && expr2);
35    if (LLVM_UNLIKELY(expr1 == expr2)) {
36        return true;
37    } else if (expr1->getClassTypeId() == expr2->getClassTypeId()) {
38        if (LLVM_LIKELY(expr1->getType() == expr2->getType())) {
39            if ((isa<Zeroes>(expr1)) || (isa<Ones>(expr1))) {
40                return true;
41            } else if (isa<Var>(expr1)) {
42                return (cast<Var>(expr1)->getName() == cast<Var>(expr2)->getName());
43            } else if (isa<Not>(expr1)) {
44                return equals(cast<Not>(expr1)->getOperand(0), cast<Not>(expr2)->getOperand(0));
45            } else if (isa<InFile>(expr1)) {
46                return equals(cast<InFile>(expr1)->getOperand(0), cast<InFile>(expr2)->getOperand(0));
47            } else if (isa<AtEOF>(expr1)) {
48                return equals(cast<AtEOF>(expr1)->getOperand(0), cast<AtEOF>(expr2)->getOperand(0));
49            } else if (isa<Variadic>(expr1)) {
50                const Variadic * const var1 = cast<Variadic>(expr1);
51                const Variadic * const var2 = cast<Variadic>(expr2);
52                if (var1->getNumOperands() == var2->getNumOperands()) {
53                    const unsigned operands = var1->getNumOperands();
54                    for (unsigned i = 0; i != operands; ++i) {
55                        bool missing = true;
56                        for (unsigned j = 0; j != operands; ++j) {
57                            // odds are both variadics will be sorted; optimize towards testing them in order.
58                            unsigned k = i + j;
59                            if (LLVM_UNLIKELY(k >= operands)) {
60                                k -= operands;
61                            }
62                            if (equals(var1->getOperand(i), var2->getOperand(k))) {
63                                missing = false;
64                                break;
65                            }
66                        }
67                        if (missing) {
68                            return false;
69                        }
70                    }
71                    return true;
72                }
73            } else if (isa<Statement>(expr1)) {
74                const Statement * stmt1 = cast<Statement>(expr1);
75                const Statement * stmt2 = cast<Statement>(expr2);
76                assert (stmt1->getNumOperands() == stmt2->getNumOperands());
77                for (unsigned i = 0; i != stmt1->getNumOperands(); ++i) {
78                    if (!equals(stmt1->getOperand(i), stmt2->getOperand(i))) {
79                        return false;
80                    }
81                }
82                return true;
83            }
84
85        }
86    }
87    return false;
88}
89
90/** ------------------------------------------------------------------------------------------------------------- *
91 * @brief replaceAllUsesWith
92 ** ------------------------------------------------------------------------------------------------------------- */
93void PabloAST::replaceAllUsesWith(PabloAST * const expr) noexcept {
94    assert (expr);
95    if (LLVM_UNLIKELY(this == expr)) {
96        return;
97    }
98    Statement * replacement[mUsers.size()];
99    Users::size_type replacements = 0;
100    PabloAST * last = nullptr;
101    for (PabloAST * user : mUsers) {
102        if (LLVM_UNLIKELY(user == expr || user == last)) {
103            continue;
104        } else if (isa<Statement>(user)) {
105            replacement[replacements++] = cast<Statement>(user);
106            last = user;
107        }
108    }
109    for (Users::size_type i = 0; i != replacements; ++i) {
110        replacement[i]->replaceUsesOfWith(this, expr);
111    }
112}
113
114/** ------------------------------------------------------------------------------------------------------------- *
115 * @brief addUser
116 ** ------------------------------------------------------------------------------------------------------------- */
117bool PabloAST::addUser(PabloAST * const user) noexcept {
118    assert (user);
119    const auto p = std::lower_bound(mUsers.begin(), mUsers.end(), user);
120    const bool unique = p == mUsers.end() || *p != user;
121    mUsers.insert(p, user);
122    return unique;
123}
124
125/** ------------------------------------------------------------------------------------------------------------- *
126 * @brief removeUser
127 ** ------------------------------------------------------------------------------------------------------------- */
128bool PabloAST::removeUser(PabloAST * const user) noexcept {
129    assert (user);
130    const auto p = std::lower_bound(mUsers.begin(), mUsers.end(), user);
131    assert (p != mUsers.end() && *p == user);
132    const auto n = mUsers.erase(p);
133    return n == mUsers.end() || *n != user;
134}
135
136/** ------------------------------------------------------------------------------------------------------------- *
137 * @brief print
138 ** ------------------------------------------------------------------------------------------------------------- */
139void PabloAST::print(llvm::raw_ostream & O) const {
140    PabloPrinter::print(this, O);
141}
142
143/** ------------------------------------------------------------------------------------------------------------- *
144 * @brief replaceUsesOfWith
145 ** ------------------------------------------------------------------------------------------------------------- */
146void Statement::replaceUsesOfWith(PabloAST * const from, PabloAST * const to) {
147    if (LLVM_LIKELY(from != to)) {
148        for (unsigned i = 0; i != getNumOperands(); ++i) {
149           if (getOperand(i) == from) {
150               setOperand(i, to);
151           }
152        }
153    }
154}
155
156/** ------------------------------------------------------------------------------------------------------------- *
157 * @brief setOperand
158 ** ------------------------------------------------------------------------------------------------------------- */
159void Statement::setOperand(const unsigned index, PabloAST * const value) {   
160    assert ("Operand cannot be null!" && value);
161    assert (index < getNumOperands());
162    PabloAST * const prior = getOperand(index);
163    assert ("Operand cannot be null!" && prior);
164    if (LLVM_UNLIKELY(prior == value)) {
165        return;
166    }     
167    if (LLVM_UNLIKELY(prior->getType() != value->getType())) {
168        std::string tmp;
169        raw_string_ostream out(tmp);
170        out << "Type mismatch replacing operand ";
171        prior->print(out);
172        out << " with ";
173        value->print(out);
174        out << " in statement ";
175        this->print(out);
176        llvm::report_fatal_error(out.str());
177    }
178    prior->removeUser(this);
179    mOperand[index] = value;
180    value->addUser(this);
181}
182
183/** ------------------------------------------------------------------------------------------------------------- *
184 * @brief insertBefore
185 ** ------------------------------------------------------------------------------------------------------------- */
186void Statement::insertBefore(Statement * const statement) {
187    if (LLVM_UNLIKELY(statement == this)) {
188        return;
189    } else if (LLVM_UNLIKELY(statement == nullptr)) {
190        llvm::report_fatal_error("cannot insert before null statement!");
191    } else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
192        llvm::report_fatal_error("statement is not contained in a pablo block!");
193    }
194    removeFromParent();
195    mParent = statement->mParent;
196    if (LLVM_UNLIKELY(mParent->mFirst == statement)) {
197        mParent->mFirst = this;
198    }
199    mNext = statement;
200    mPrev = statement->mPrev;
201    statement->mPrev = this;
202    if (LLVM_LIKELY(mPrev != nullptr)) {
203        mPrev->mNext = this;
204    }
205}
206
207/** ------------------------------------------------------------------------------------------------------------- *
208 * @brief insertAfter
209 ** ------------------------------------------------------------------------------------------------------------- */
210void Statement::insertAfter(Statement * const statement) {
211    if (LLVM_UNLIKELY(statement == this)) {
212        return;
213    } else if (LLVM_UNLIKELY(statement == nullptr)) {
214        llvm::report_fatal_error("cannot insert after null statement!");
215    } else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
216        llvm::report_fatal_error("statement is not contained in a pablo block!");
217    }
218    removeFromParent();
219    mParent = statement->mParent;
220    if (LLVM_UNLIKELY(mParent->mLast == statement)) {
221        mParent->mLast = this;
222    }
223    mPrev = statement;
224    mNext = statement->mNext;
225    statement->mNext = this;
226    if (LLVM_LIKELY(mNext != nullptr)) {
227        mNext->mPrev = this;
228    }
229}
230
231/** ------------------------------------------------------------------------------------------------------------- *
232 * @brief removeFromParent
233 ** ------------------------------------------------------------------------------------------------------------- */
234Statement * Statement::removeFromParent() noexcept {
235    Statement * next = mNext;
236    if (LLVM_LIKELY(mParent != nullptr)) {
237        if (LLVM_UNLIKELY(mParent->mFirst == this)) {
238            mParent->mFirst = mNext;
239        }
240        if (LLVM_UNLIKELY(mParent->mLast == this)) {
241            mParent->mLast = mPrev;
242        }
243        if (LLVM_UNLIKELY(mParent->mInsertionPoint == this)) {
244            mParent->mInsertionPoint = mPrev;
245        }
246        if (LLVM_LIKELY(mPrev != nullptr)) {
247            mPrev->mNext = mNext;
248        }
249        if (LLVM_LIKELY(mNext != nullptr)) {
250            mNext->mPrev = mPrev;
251        }
252    }
253    mPrev = nullptr;
254    mNext = nullptr;
255    mParent = nullptr;
256    return next;
257}
258
259/** ------------------------------------------------------------------------------------------------------------- *
260 * @brief eraseFromParent
261 ** ------------------------------------------------------------------------------------------------------------- */
262Statement * Statement::eraseFromParent(const bool recursively) noexcept {
263
264    if (LLVM_UNLIKELY(getParent() == nullptr)) {
265        return nullptr;
266    }
267
268    if (LLVM_UNLIKELY(isa<Branch>(this))) {
269        cast<Branch>(this)->getBody()->eraseFromParent(recursively);
270    } else if (LLVM_LIKELY(!isa<Assign>(this))) {
271        replaceAllUsesWith(getParent()->createZeroes(getType()));
272    }
273
274    Statement * const next = removeFromParent();
275    for (unsigned i = 0; i != mOperands; ++i) {
276        PabloAST * const op = mOperand[i]; assert (op);
277        op->removeUser(this);
278        if (LLVM_UNLIKELY(recursively && op->getNumUses() == 0)) {
279            if (LLVM_LIKELY(isa<Statement>(op))) {
280                cast<Statement>(op)->eraseFromParent(true);
281            }
282        }
283        mOperand[i] = nullptr;
284    }
285
286    return next;
287}
288
289/** ------------------------------------------------------------------------------------------------------------- *
290 * @brief replaceWith
291 ** ------------------------------------------------------------------------------------------------------------- */
292Statement * Statement::replaceWith(PabloAST * const expr, const bool rename, const bool recursively) noexcept {
293    assert (expr);
294    if (LLVM_UNLIKELY(expr == this)) {
295        return getNextNode();
296    }
297    if (LLVM_LIKELY(rename && isa<Statement>(expr))) {
298        if (mName && cast<Statement>(expr)->mName == nullptr) {
299            cast<Statement>(expr)->setName(mName);
300        }
301    }
302    replaceAllUsesWith(expr);
303    return eraseFromParent(recursively);
304}
305
306/** ------------------------------------------------------------------------------------------------------------- *
307 * @brief setName
308 ** ------------------------------------------------------------------------------------------------------------- */
309void Statement::setName(const String * const name) noexcept {
310    if (LLVM_UNLIKELY(name == nullptr)) {
311        llvm::report_fatal_error("Statement name cannot be null!");
312    }
313    mName = name;
314}
315
316/** ------------------------------------------------------------------------------------------------------------- *
317 * @brief addOperand
318 ** ------------------------------------------------------------------------------------------------------------- */
319void Variadic::addOperand(PabloAST * const expr) noexcept {
320    if (LLVM_UNLIKELY(mOperands == mCapacity)) {
321        mCapacity = std::max<unsigned>(mCapacity * 2, 2);
322        PabloAST ** expandedOperandSpace = mAllocator.allocate(mCapacity);
323        for (unsigned i = 0; i != mOperands; ++i) {
324            expandedOperandSpace[i] = mOperand[i];
325        }
326        mAllocator.deallocate(mOperand);
327        mOperand = expandedOperandSpace;
328    }
329    mOperand[mOperands++] = expr;
330    expr->addUser(this);
331}
332
333/** ------------------------------------------------------------------------------------------------------------- *
334 * @brief removeOperand
335 ** ------------------------------------------------------------------------------------------------------------- */
336PabloAST * Variadic::removeOperand(const unsigned index) noexcept {
337    assert (index < mOperands);
338    PabloAST * const expr = mOperand[index];
339    assert (expr);
340    --mOperands;
341    for (unsigned i = index; i != mOperands; ++i) {
342        mOperand[i] = mOperand[i + 1];
343    }
344    mOperand[mOperands] = nullptr;
345    expr->removeUser(this);
346    return expr;
347}
348
349/** ------------------------------------------------------------------------------------------------------------- *
350 * @brief contains
351 ** ------------------------------------------------------------------------------------------------------------- */
352bool StatementList::contains(const Statement * const statement) const {
353    for (const Statement * stmt : *this) {
354        if (statement == stmt) {
355            return true;
356        }
357    }
358    return false;
359}
360
361/** ------------------------------------------------------------------------------------------------------------- *
362 * @brief dominates
363 *
364 * expr1 dominates (>>) expr2 if every path from the *entry* node to expr2 must go through expr1
365 *
366 * For example, consider the program (with entry node 1):
367 *
368 * 1. Assign a, s           1 >> 1, 2, 3, 4, 5, 6
369 * 2. While x:              2 >> 2, 3, 4, 5, 6
370 * 3.   Assign a, p         3 >> 3
371 * 4. While y:              4 >> 4, 5, 6
372 * 5.   Assign a, q         5 >> 5
373 * 6. Assign a, t           6 >> 6
374 ** ------------------------------------------------------------------------------------------------------------- */
375bool dominates(const PabloAST * const expr1, const PabloAST * const expr2) {
376    if (LLVM_UNLIKELY(expr1 == nullptr || expr2 == nullptr)) {
377        return (expr2 == nullptr);
378    } else if (LLVM_LIKELY(isa<Statement>(expr1))) {
379        const Statement * stmt1 = cast<Statement>(expr1);
380        assert ("expr1 is not in any block!" && stmt1->getParent());
381        if (isa<Statement>(expr2)) {
382            const Statement * stmt2 = cast<Statement>(expr2);
383            assert ("expr2 is not in any block!" && stmt2->getParent());
384
385            while (stmt1->getParent() != stmt2->getParent()) {
386                stmt2 = stmt2->getParent()->getBranch();
387                if (stmt2 == nullptr) {
388                    return false;
389                }
390            }
391
392            const Statement * temp1 = stmt1, * temp2 = stmt2;
393            while (temp1 && temp2) {
394                if (temp1 == stmt2) {
395                    return true;
396                } else if (temp2 == stmt1) {
397                    return false;
398                }
399                temp1 = temp1->getNextNode();
400                temp2 = temp2->getNextNode();
401            }
402            // If temp1 isn't null then temp2 must be null; thus stmt2 must succeed stmt1.
403            return (temp1 != nullptr);
404        }
405        return false;
406    }
407    return true;
408}
409
410/** ------------------------------------------------------------------------------------------------------------- *
411 * @brief postdominates
412 *
413 * expr1 post-dominates (<<) expr2 if all paths to the *exit* node starting at expr2 must go through expr1
414 *
415 * For example, consider the program (with exit node 6):
416 *
417 * 1. Assign a, s           1 << 1
418 * 2. While x:              2 << 1, 2
419 * 3.   Assign a, p         3 << 1, 2, 3
420 * 4. While y:              4 << 1, 2, 4
421 * 5.   Assign a, q         5 << 1, 2, 4, 5
422 * 6. Assign a, t           6 << 1, 2, 3, 4, 5, 6
423 ** ------------------------------------------------------------------------------------------------------------- */
424bool postdominates(const PabloAST * const expr1, const PabloAST * const expr2) {
425    throw std::runtime_error("not implemented yet!");
426}
427
428}
Note: See TracBrowser for help on using the repository browser.