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

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

Rewrite of the CarryManager? to support non-carry-collapsing loops.

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