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

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

Code clean-up. Removed Pablo Call, SetIthBit? and Prototype.

File size: 16.5 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>          // for PabloBlock
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>        // for PabloPrinter
17
18using namespace boost::container;
19using namespace llvm;
20
21namespace pablo {
22
23using TypeId = PabloAST::ClassTypeId;
24
25/** ------------------------------------------------------------------------------------------------------------- *
26 * @brief equals
27 *
28 *  Return true if expr1 and expr2 can be proven equivalent according to some rules, false otherwise.  Note that
29 *  false may be returned i some cases when the exprs are equivalent.
30 ** ------------------------------------------------------------------------------------------------------------- */
31bool equals(const PabloAST * const expr1, const PabloAST * const expr2) {
32    assert (expr1 && expr2);
33    if (LLVM_UNLIKELY(expr1 == expr2)) {
34        return true;
35    } else if (expr1->getClassTypeId() == expr2->getClassTypeId()) {
36        if (LLVM_LIKELY(expr1->getType() == expr2->getType())) {
37            if ((isa<Zeroes>(expr1)) || (isa<Ones>(expr1))) {
38                return true;
39            } else if (isa<Var>(expr1)) {
40                return (cast<Var>(expr1)->getName() == cast<Var>(expr2)->getName());
41            } else if (isa<Not>(expr1)) {
42                return equals(cast<Not>(expr1)->getOperand(0), cast<Not>(expr2)->getOperand(0));
43            } else if (isa<InFile>(expr1)) {
44                return equals(cast<InFile>(expr1)->getOperand(0), cast<InFile>(expr2)->getOperand(0));
45            } else if (isa<AtEOF>(expr1)) {
46                return equals(cast<AtEOF>(expr1)->getOperand(0), cast<AtEOF>(expr2)->getOperand(0));
47            } else if (isa<Variadic>(expr1)) {
48                const Variadic * const var1 = cast<Variadic>(expr1);
49                const Variadic * const var2 = cast<Variadic>(expr2);
50                if (var1->getNumOperands() == var2->getNumOperands()) {
51                    const unsigned operands = var1->getNumOperands();
52                    for (unsigned i = 0; i != operands; ++i) {
53                        bool missing = true;
54                        for (unsigned j = 0; j != operands; ++j) {
55                            // odds are both variadics will be sorted; optimize towards testing them in order.
56                            unsigned k = i + j;
57                            if (LLVM_UNLIKELY(k >= operands)) {
58                                k -= operands;
59                            }
60                            if (equals(var1->getOperand(i), var2->getOperand(k))) {
61                                missing = false;
62                                break;
63                            }
64                        }
65                        if (missing) {
66                            return false;
67                        }
68                    }
69                    return true;
70                }
71            } else if (isa<Statement>(expr1)) {
72                const Statement * stmt1 = cast<Statement>(expr1);
73                const Statement * stmt2 = cast<Statement>(expr2);
74                assert (stmt1->getNumOperands() == stmt2->getNumOperands());
75                for (unsigned i = 0; i != stmt1->getNumOperands(); ++i) {
76                    if (!equals(stmt1->getOperand(i), stmt2->getOperand(i))) {
77                        return false;
78                    }
79                }
80                return true;
81            }
82
83        }
84    }
85    return false;
86}
87
88/** ------------------------------------------------------------------------------------------------------------- *
89 * @brief replaceAllUsesWith
90 ** ------------------------------------------------------------------------------------------------------------- */
91void PabloAST::replaceAllUsesWith(PabloAST * const expr) {
92    assert (expr);
93    if (LLVM_UNLIKELY(this == expr)) {
94        return;
95    }
96    Statement * replacement[mUsers.size()];
97    Users::size_type replacements = 0;
98    PabloAST * last = nullptr;
99    for (PabloAST * user : mUsers) {
100        if (LLVM_UNLIKELY(user == expr || user == last)) {
101            continue;
102        } else if (isa<Statement>(user)) {
103            replacement[replacements++] = cast<Statement>(user);
104            last = user;
105        }
106    }
107    for (Users::size_type i = 0; i != replacements; ++i) {
108        replacement[i]->replaceUsesOfWith(this, expr);
109    }
110}
111
112/** ------------------------------------------------------------------------------------------------------------- *
113 * @brief addUser
114 ** ------------------------------------------------------------------------------------------------------------- */
115bool PabloAST::addUser(PabloAST * const user) { assert (user);
116    const auto p = std::lower_bound(mUsers.begin(), mUsers.end(), user);
117    const bool unique = p == mUsers.end() || *p != user;
118    mUsers.insert(p, user);
119    return unique;
120}
121
122/** ------------------------------------------------------------------------------------------------------------- *
123 * @brief removeUser
124 ** ------------------------------------------------------------------------------------------------------------- */
125bool PabloAST::removeUser(PabloAST * const user) { assert (user);
126    const auto p = std::lower_bound(mUsers.begin(), mUsers.end(), user);
127    assert (p != mUsers.end() && *p == user);
128    const auto n = mUsers.erase(p);
129    return n == mUsers.end() || *n != user;
130}
131
132/** ------------------------------------------------------------------------------------------------------------- *
133 * @brief print
134 ** ------------------------------------------------------------------------------------------------------------- */
135void PabloAST::print(llvm::raw_ostream & O) const {
136    PabloPrinter::print(this, O);
137}
138
139/** ------------------------------------------------------------------------------------------------------------- *
140 * @brief replaceUsesOfWith
141 ** ------------------------------------------------------------------------------------------------------------- */
142void Statement::replaceUsesOfWith(PabloAST * const from, PabloAST * const to) {
143    if (LLVM_LIKELY(from != to)) {
144        for (unsigned i = 0; i != getNumOperands(); ++i) {
145           if (getOperand(i) == from) {
146               setOperand(i, to);
147           }
148        }
149    }
150}
151
152/** ------------------------------------------------------------------------------------------------------------- *
153 * @brief setOperand
154 ** ------------------------------------------------------------------------------------------------------------- */
155void Statement::setOperand(const unsigned index, PabloAST * const value) {   
156    assert ("Operand cannot be null!" && value);
157    assert (index < getNumOperands());
158    PabloAST * const prior = getOperand(index);
159    assert ("Operand cannot be null!" && prior);
160    if (LLVM_UNLIKELY(prior == value)) {
161        return;
162    }     
163    if (LLVM_UNLIKELY(prior->getType() != value->getType())) {
164        std::string tmp;
165        raw_string_ostream out(tmp);
166        out << "Type mismatch replacing operand ";
167        prior->print(out);
168        out << " with ";
169        value->print(out);
170        out << " in statement ";
171        this->print(out);
172        llvm::report_fatal_error(out.str());
173    }
174    prior->removeUser(this);
175    mOperand[index] = value;
176    value->addUser(this);
177}
178
179/** ------------------------------------------------------------------------------------------------------------- *
180 * @brief insertBefore
181 ** ------------------------------------------------------------------------------------------------------------- */
182void Statement::insertBefore(Statement * const statement) {
183    if (LLVM_UNLIKELY(statement == this)) {
184        return;
185    } else if (LLVM_UNLIKELY(statement == nullptr)) {
186        llvm::report_fatal_error("cannot insert before null statement!");
187    } else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
188        llvm::report_fatal_error("statement is not contained in a pablo block!");
189    }
190    removeFromParent();
191    mParent = statement->mParent;
192    if (LLVM_UNLIKELY(mParent->mFirst == statement)) {
193        mParent->mFirst = this;
194    }
195    mNext = statement;
196    mPrev = statement->mPrev;
197    statement->mPrev = this;
198    if (LLVM_LIKELY(mPrev != nullptr)) {
199        mPrev->mNext = this;
200    }
201}
202
203/** ------------------------------------------------------------------------------------------------------------- *
204 * @brief insertAfter
205 ** ------------------------------------------------------------------------------------------------------------- */
206void Statement::insertAfter(Statement * const statement) {
207    if (LLVM_UNLIKELY(statement == this)) {
208        return;
209    } else if (LLVM_UNLIKELY(statement == nullptr)) {
210        llvm::report_fatal_error("cannot insert after null statement!");
211    } else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
212        llvm::report_fatal_error("statement is not contained in a pablo block!");
213    }
214    removeFromParent();
215    mParent = statement->mParent;
216    if (LLVM_UNLIKELY(mParent->mLast == statement)) {
217        mParent->mLast = this;
218    }
219    mPrev = statement;
220    mNext = statement->mNext;
221    statement->mNext = this;
222    if (LLVM_LIKELY(mNext != nullptr)) {
223        mNext->mPrev = this;
224    }
225}
226
227/** ------------------------------------------------------------------------------------------------------------- *
228 * @brief removeFromParent
229 ** ------------------------------------------------------------------------------------------------------------- */
230Statement * Statement::removeFromParent() {
231    Statement * next = mNext;
232    if (LLVM_LIKELY(mParent != nullptr)) {
233        if (LLVM_UNLIKELY(mParent->mFirst == this)) {
234            mParent->mFirst = mNext;
235        }
236        if (LLVM_UNLIKELY(mParent->mLast == this)) {
237            mParent->mLast = mPrev;
238        }
239        if (LLVM_UNLIKELY(mParent->mInsertionPoint == this)) {
240            mParent->mInsertionPoint = mPrev;
241        }
242        if (LLVM_LIKELY(mPrev != nullptr)) {
243            mPrev->mNext = mNext;
244        }
245        if (LLVM_LIKELY(mNext != nullptr)) {
246            mNext->mPrev = mPrev;
247        }
248    }
249    mPrev = nullptr;
250    mNext = nullptr;
251    mParent = nullptr;
252    return next;
253}
254
255/** ------------------------------------------------------------------------------------------------------------- *
256 * @brief eraseFromParent
257 ** ------------------------------------------------------------------------------------------------------------- */
258Statement * Statement::eraseFromParent(const bool recursively) {
259
260    if (LLVM_UNLIKELY(getParent() == nullptr)) {
261        return nullptr;
262    }
263
264    if (LLVM_UNLIKELY(isa<Branch>(this))) {
265        cast<Branch>(this)->getBody()->eraseFromParent(recursively);
266    } else if (LLVM_LIKELY(!isa<Assign>(this))) {
267        replaceAllUsesWith(getParent()->createZeroes(getType()));
268    }
269
270    Statement * const next = removeFromParent();
271
272    for (unsigned i = 0; i != mOperands; ++i) {
273        PabloAST * const op = mOperand[i]; assert (op);
274        op->removeUser(this);
275        if (LLVM_UNLIKELY(recursively && op->getNumUses() == 0)) {
276            if (LLVM_LIKELY(isa<Statement>(op))) {
277                cast<Statement>(op)->eraseFromParent(true);
278            }
279        }
280        mOperand[i] = nullptr;
281    }
282
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 = mAllocator.allocate(mCapacity);
310        for (unsigned i = 0; i != mOperands; ++i) {
311            expandedOperandSpace[i] = mOperand[i];
312        }
313        mAllocator.deallocate(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.