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

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

Multi-threading support for PabloAST / PabloCompiler?. Requires unique LLVM Context / Module for each thread.

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