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

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

Initial work on adding types to PabloAST and mutable Var objects.

File size: 16.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 <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    prior->removeUser(this);
163    mOperand[index] = value;
164    value->addUser(this);
165}
166
167/** ------------------------------------------------------------------------------------------------------------- *
168 * @brief insertBefore
169 ** ------------------------------------------------------------------------------------------------------------- */
170void Statement::insertBefore(Statement * const statement) {
171    if (LLVM_UNLIKELY(statement == this)) {
172        return;
173    } else if (LLVM_UNLIKELY(statement == nullptr)) {
174        llvm::report_fatal_error("cannot insert before null statement!");
175    } else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
176        llvm::report_fatal_error("statement is not contained in a pablo block!");
177    }
178    removeFromParent();
179    mParent = statement->mParent;
180    if (LLVM_UNLIKELY(mParent->mFirst == statement)) {
181        mParent->mFirst = this;
182    }
183    mNext = statement;
184    mPrev = statement->mPrev;
185    statement->mPrev = this;
186    if (LLVM_LIKELY(mPrev != nullptr)) {
187        mPrev->mNext = this;
188    }
189}
190
191/** ------------------------------------------------------------------------------------------------------------- *
192 * @brief insertAfter
193 ** ------------------------------------------------------------------------------------------------------------- */
194void Statement::insertAfter(Statement * const statement) {
195    if (LLVM_UNLIKELY(statement == this)) {
196        return;
197    } else if (LLVM_UNLIKELY(statement == nullptr)) {
198        llvm::report_fatal_error("cannot insert after null statement!");
199    } else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
200        llvm::report_fatal_error("statement is not contained in a pablo block!");
201    }
202    removeFromParent();
203    mParent = statement->mParent;
204    if (LLVM_UNLIKELY(mParent->mLast == statement)) {
205        mParent->mLast = this;
206    }
207    mPrev = statement;
208    mNext = statement->mNext;
209    statement->mNext = this;
210    if (LLVM_LIKELY(mNext != nullptr)) {
211        mNext->mPrev = this;
212    }
213}
214
215/** ------------------------------------------------------------------------------------------------------------- *
216 * @brief removeFromParent
217 ** ------------------------------------------------------------------------------------------------------------- */
218Statement * Statement::removeFromParent() {
219    Statement * next = mNext;
220    if (LLVM_LIKELY(mParent != nullptr)) {
221        if (LLVM_UNLIKELY(mParent->mFirst == this)) {
222            mParent->mFirst = mNext;
223        }
224        if (LLVM_UNLIKELY(mParent->mLast == this)) {
225            mParent->mLast = mPrev;
226        }
227        if (LLVM_UNLIKELY(mParent->mInsertionPoint == this)) {
228            mParent->mInsertionPoint = mPrev;
229        }
230        if (LLVM_LIKELY(mPrev != nullptr)) {
231            mPrev->mNext = mNext;
232        }
233        if (LLVM_LIKELY(mNext != nullptr)) {
234            mNext->mPrev = mPrev;
235        }
236    }
237    mPrev = nullptr;
238    mNext = nullptr;
239    mParent = nullptr;
240    return next;
241}
242
243/** ------------------------------------------------------------------------------------------------------------- *
244 * @brief eraseFromParent
245 ** ------------------------------------------------------------------------------------------------------------- */
246Statement * Statement::eraseFromParent(const bool recursively) {
247
248    if (LLVM_UNLIKELY(getParent() == nullptr)) {
249        return nullptr;
250    }
251
252    if (LLVM_UNLIKELY(isa<Branch>(this))) {
253        cast<Branch>(this)->getBody()->eraseFromParent(recursively);
254    } else if (LLVM_LIKELY(!isa<Assign>(this))) {
255        replaceAllUsesWith(getParent()->createZeroes(getType()));
256    }
257
258    Statement * const next = removeFromParent();
259
260    for (unsigned i = 0; i != mOperands; ++i) {
261        PabloAST * const op = mOperand[i]; assert (op);
262        op->removeUser(this);
263        if (LLVM_UNLIKELY(recursively && op->getNumUses() == 0)) {
264            if (LLVM_LIKELY(isa<Statement>(op))) {
265                cast<Statement>(op)->eraseFromParent(true);
266            }
267        }
268        mOperand[i] = nullptr;
269    }
270
271    mAllocator.deallocate(reinterpret_cast<Allocator::pointer>(this));
272    return next;
273}
274
275/** ------------------------------------------------------------------------------------------------------------- *
276 * @brief replaceWith
277 ** ------------------------------------------------------------------------------------------------------------- */
278Statement * Statement::replaceWith(PabloAST * const expr, const bool rename, const bool recursively) {
279    assert (expr);
280    if (LLVM_UNLIKELY(expr == this)) {
281        return getNextNode();
282    }
283    if (LLVM_LIKELY(rename && isa<Statement>(expr))) {
284        if (mName && cast<Statement>(expr)->mName == nullptr) {
285            cast<Statement>(expr)->setName(mName);
286        }
287    }
288    replaceAllUsesWith(expr);
289    return eraseFromParent(recursively);
290}
291
292/** ------------------------------------------------------------------------------------------------------------- *
293 * @brief addOperand
294 ** ------------------------------------------------------------------------------------------------------------- */
295void Variadic::addOperand(PabloAST * const expr) {
296    if (LLVM_UNLIKELY(mOperands == mCapacity)) {
297        mCapacity = std::max<unsigned>(mCapacity * 2, 2);
298        PabloAST ** expandedOperandSpace = reinterpret_cast<PabloAST**>(mAllocator.allocate(mCapacity * sizeof(PabloAST *)));
299        for (unsigned i = 0; i != mOperands; ++i) {
300            expandedOperandSpace[i] = mOperand[i];
301        }
302        mAllocator.deallocate(reinterpret_cast<Allocator::pointer>(mOperand));
303        mOperand = expandedOperandSpace;
304    }
305    mOperand[mOperands++] = expr;
306    expr->addUser(this);
307}
308
309/** ------------------------------------------------------------------------------------------------------------- *
310 * @brief removeOperand
311 ** ------------------------------------------------------------------------------------------------------------- */
312PabloAST * Variadic::removeOperand(const unsigned index) {
313    assert (index < mOperands);
314    PabloAST * const expr = mOperand[index];
315    assert (expr);
316    --mOperands;
317    for (unsigned i = index; i != mOperands; ++i) {
318        mOperand[i] = mOperand[i + 1];
319    }
320    mOperand[mOperands] = nullptr;
321    expr->removeUser(this);
322    return expr;
323}
324
325/** ------------------------------------------------------------------------------------------------------------- *
326 * @brief contains
327 ** ------------------------------------------------------------------------------------------------------------- */
328bool StatementList::contains(Statement * const statement) {
329    for (Statement * stmt : *this) {
330        if (statement == stmt) {
331            return true;
332        }
333    }
334    return false;
335}
336
337/** ------------------------------------------------------------------------------------------------------------- *
338 * @brief dominates
339 *
340 * expr1 dominates (>>) expr2 if every path from the *entry* node to expr2 must go through expr1
341 *
342 * For example, consider the program (with entry node 1):
343 *
344 * 1. Assign a, s           1 >> 1, 2, 3, 4, 5, 6
345 * 2. While x:              2 >> 2, 3, 4, 5, 6
346 * 3.   Assign a, p         3 >> 3
347 * 4. While y:              4 >> 4, 5, 6
348 * 5.   Assign a, q         5 >> 5
349 * 6. Assign a, t           6 >> 6
350 ** ------------------------------------------------------------------------------------------------------------- */
351bool dominates(const PabloAST * const expr1, const PabloAST * const expr2) {
352    if (LLVM_UNLIKELY(expr1 == nullptr || expr2 == nullptr)) {
353        return (expr2 == nullptr);
354    } else if (LLVM_LIKELY(isa<Statement>(expr1))) {
355        const Statement * stmt1 = cast<Statement>(expr1);
356        assert ("expr1 is not in any block!" && stmt1->getParent());
357        if (isa<Statement>(expr2)) {
358            const Statement * stmt2 = cast<Statement>(expr2);
359            assert ("expr2 is not in any block!" && stmt2->getParent());
360
361            while (stmt1->getParent() != stmt2->getParent()) {
362                stmt2 = stmt2->getParent()->getBranch();
363                if (stmt2 == nullptr) {
364                    return false;
365                }
366            }
367
368            const Statement * temp1 = stmt1, * temp2 = stmt2;
369            while (temp1 && temp2) {
370                if (temp1 == stmt2) {
371                    return true;
372                } else if (temp2 == stmt1) {
373                    return false;
374                }
375                temp1 = temp1->getNextNode();
376                temp2 = temp2->getNextNode();
377            }
378            // If temp1 isn't null then temp2 must be null; thus stmt2 must succeed stmt1.
379            return (temp1 != nullptr);
380        }
381        return false;
382    }
383    return true;
384}
385
386/** ------------------------------------------------------------------------------------------------------------- *
387 * @brief postdominates
388 *
389 * expr1 post-dominates (<<) expr2 if all paths to the *exit* node starting at expr2 must go through expr1
390 *
391 * For example, consider the program (with exit node 6):
392 *
393 * 1. Assign a, s           1 << 1
394 * 2. While x:              2 << 1, 2
395 * 3.   Assign a, p         3 << 1, 2, 3
396 * 4. While y:              4 << 1, 2, 4
397 * 5.   Assign a, q         5 << 1, 2, 4, 5
398 * 6. Assign a, t           6 << 1, 2, 3, 4, 5, 6
399 ** ------------------------------------------------------------------------------------------------------------- */
400bool postdominates(const PabloAST * const expr1, const PabloAST * const expr2) {
401    throw std::runtime_error("not implemented yet!");
402}
403
404}
Note: See TracBrowser for help on using the repository browser.