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

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

First stage of MultiBlockKernel? and pipeline restructuring

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