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

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

Work on multiplexing and distribution passes + a few AST modification bug fixes.

File size: 23.1 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
14using namespace boost::container;
15
16namespace pablo {
17
18PabloAST::Allocator PabloAST::mAllocator;
19PabloAST::VectorAllocator PabloAST::mVectorAllocator;
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 (expr1 == expr2) {
30        return true;
31    } else if (expr1->getClassTypeId() == expr2->getClassTypeId()) {
32        if ((isa<Zeroes>(expr1)) || (isa<Ones>(expr1))) {
33            return true;
34        } else if (isa<Var>(expr1)) {
35            return (cast<Var>(expr1)->getName() == cast<Var>(expr2)->getName());
36        } else if (isa<Not>(expr1)) {
37            return equals(cast<Not>(expr1)->getOperand(0), cast<Not>(expr2)->getOperand(0));
38        } else if (isa<InFile>(expr1)) {
39            return equals(cast<InFile>(expr1)->getOperand(0), cast<InFile>(expr2)->getOperand(0));
40        } else if (isa<AtEOF>(expr1)) {
41            return equals(cast<AtEOF>(expr1)->getOperand(0), cast<AtEOF>(expr2)->getOperand(0));
42        } else if (isa<Variadic>(expr1)) {
43            const Variadic * const var1 = cast<Variadic>(expr1);
44            const Variadic * const var2 = cast<Variadic>(expr2);
45            if (var1->getNumOperands() == var2->getNumOperands()) {
46                const unsigned operands = var1->getNumOperands();
47                for (unsigned i = 0; i != operands; ++i) {
48                    bool missing = true;
49                    for (unsigned j = 0; j != operands; ++j) {
50                        // odds are both variadics will be sorted; optimize towards testing them in order.
51                        unsigned k = i + j;
52                        if (LLVM_UNLIKELY(k >= operands)) {
53                            k -= operands;
54                        }
55                        if (equals(var1->getOperand(i), var2->getOperand(k))) {
56                            missing = false;
57                            break;
58                        }
59                    }
60                    if (missing) {
61                        return false;
62                    }
63                }
64                return true;
65            }
66        } else if (isa<Integer>(expr1) || isa<String>(expr1) || isa<Call>(expr1)) {
67            return false; // If these weren't equivalent by address they won't be equivalent by their operands.
68        } else { // Non-reassociatable functions (i.e., Sel, Advance, ScanThru, MatchStar, Assign, Next)
69            const Statement * stmt1 = cast<Statement>(expr1);
70            const Statement * stmt2 = cast<Statement>(expr2);
71            assert (stmt1->getNumOperands() == stmt2->getNumOperands());
72            for (unsigned i = 0; i != stmt1->getNumOperands(); ++i) {
73                if (!equals(stmt1->getOperand(i), stmt2->getOperand(i))) {
74                    return false;
75                }
76            }
77            return true;
78        }
79    }
80    return false;
81}
82
83/** ------------------------------------------------------------------------------------------------------------- *
84 * @brief replaceAllUsesWith
85 ** ------------------------------------------------------------------------------------------------------------- */
86void PabloAST::replaceAllUsesWith(PabloAST * const expr) {
87    assert (expr);
88    if (LLVM_UNLIKELY(this == expr)) {
89        return;
90    }
91    Statement * replacement[mUsers.size()];
92    Users::size_type replacements = 0;
93    PabloAST * last = nullptr;
94    for (PabloAST * user : mUsers) {
95        if (LLVM_UNLIKELY(user == expr || user == last)) {
96            continue;
97        } else if (isa<Statement>(user)) {
98            replacement[replacements++] = cast<Statement>(user);
99            last = user;
100        }
101    }
102    for (Users::size_type i = 0; i != replacements; ++i) {
103        replacement[i]->replaceUsesOfWith(this, expr);
104    }
105}
106
107/** ------------------------------------------------------------------------------------------------------------- *
108 * @brief addUser
109 ** ------------------------------------------------------------------------------------------------------------- */
110void PabloAST::addUser(PabloAST * const user) {
111    assert (user);
112    // Note: for the rare situation that this node is used multiple times by the same statement, duplicates are allowed.
113    mUsers.insert(std::lower_bound(mUsers.begin(), mUsers.end(), user), user);
114}
115
116/** ------------------------------------------------------------------------------------------------------------- *
117 * @brief removeUser
118 ** ------------------------------------------------------------------------------------------------------------- */
119void PabloAST::removeUser(PabloAST * const user) {
120    assert (user);
121    const auto pos = std::lower_bound(mUsers.begin(), mUsers.end(), user);
122    if (LLVM_UNLIKELY(pos == mUsers.end() || *pos != user)) {
123        std::string tmp;
124        raw_string_ostream out(tmp);
125        out << "Cannot remove user ";
126        PabloPrinter::print(user, out);
127        out << " from ";
128        PabloPrinter::print(this, out);
129        out << " because it's not in its user list!";
130        throw std::runtime_error(out.str());
131    }
132    mUsers.erase(pos);
133}
134
135
136/** ------------------------------------------------------------------------------------------------------------- *
137 * @brief checkEscapedValueList
138 ** ------------------------------------------------------------------------------------------------------------- */
139template <class ValueType, class ValueList>
140inline void Statement::checkEscapedValueList(Statement * const branch, PabloAST * const from, PabloAST * const to, ValueList & list) {
141    if (LLVM_LIKELY(isa<ValueType>(from))) {
142        const auto f = std::find(list.begin(), list.end(), cast<ValueType>(from));
143        if (LLVM_LIKELY(f != list.end())) {
144            branch->removeUser(from);
145            from->removeUser(branch);
146            if (LLVM_UNLIKELY(isa<ValueType>(to))) {
147                if (LLVM_LIKELY(std::find(list.begin(), list.end(), cast<ValueType>(to)) == list.end())) {
148                    PabloBlock * parent = cast<ValueType>(to)->getParent();
149                    for (;;) {
150                        if (parent == cast<ValueType>(from)->getParent()) {
151                            *f = cast<ValueType>(to);
152                            branch->addUser(to);
153                            to->addUser(branch);
154                            return;
155                        }
156                        parent = parent->getParent();
157                        if (parent == nullptr) {
158                            break;
159                        }
160                    }
161                }
162            }
163            list.erase(f);
164        }                             
165    }
166}
167
168/** ------------------------------------------------------------------------------------------------------------- *
169 * @brief replaceUsesOfWith
170 ** ------------------------------------------------------------------------------------------------------------- */
171void Statement::replaceUsesOfWith(PabloAST * const from, PabloAST * const to) {
172    if (LLVM_UNLIKELY(from == to)) {
173        return;
174    }
175    for (unsigned i = 0; i != getNumOperands(); ++i) {
176       if (getOperand(i) == from) {
177           setOperand(i, to);
178       }
179    }
180    if (LLVM_UNLIKELY(isa<If>(this))) {
181        checkEscapedValueList<Assign>(this, from, to, cast<If>(this)->getDefined());
182    } else if (LLVM_UNLIKELY(isa<While>(this))) {
183        checkEscapedValueList<Next>(this, from, to, cast<While>(this)->getVariants());
184    }
185}
186
187/** ------------------------------------------------------------------------------------------------------------- *
188 * @brief setOperand
189 ** ------------------------------------------------------------------------------------------------------------- */
190void Statement::setOperand(const unsigned index, PabloAST * const value) {
191    assert ("Operand cannot be null!" && value);
192    assert (index < getNumOperands());
193    PabloAST * const prior = getOperand(index);
194    assert ("Operand cannot be null!" && prior);
195    if (LLVM_UNLIKELY(prior == value)) {
196        return;
197    }   
198    prior->removeUser(this);
199    mOperand[index] = value;
200    value->addUser(this);
201}
202
203/** ------------------------------------------------------------------------------------------------------------- *
204 * @brief insertBefore
205 ** ------------------------------------------------------------------------------------------------------------- */
206void Statement::insertBefore(Statement * const statement) {
207    if (LLVM_UNLIKELY(statement == this)) {
208        return;
209    }
210    else if (LLVM_UNLIKELY(statement == nullptr)) {
211        throw std::runtime_error("cannot insert before null statement!");
212    }
213    else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
214        throw std::runtime_error("statement is not contained in a pablo block!");
215    }
216    removeFromParent();
217    mParent = statement->mParent;
218    if (LLVM_UNLIKELY(mParent->mFirst == statement)) {
219        mParent->mFirst = this;
220    }
221    mNext = statement;
222    mPrev = statement->mPrev;
223    statement->mPrev = this;
224    if (LLVM_LIKELY(mPrev != nullptr)) {
225        mPrev->mNext = this;
226    }
227    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
228        PabloBlock * body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
229        body->setParent(mParent);
230    }
231}
232
233/** ------------------------------------------------------------------------------------------------------------- *
234 * @brief insertAfter
235 ** ------------------------------------------------------------------------------------------------------------- */
236void Statement::insertAfter(Statement * const statement) {
237    if (LLVM_UNLIKELY(statement == this)) {
238        return;
239    } else if (LLVM_UNLIKELY(statement == nullptr)) {
240        throw std::runtime_error("cannot insert after null statement!");
241    } else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
242        throw std::runtime_error("statement is not contained in a pablo block!");
243    }
244    removeFromParent();
245    mParent = statement->mParent;
246    if (LLVM_UNLIKELY(mParent->mLast == statement)) {
247        mParent->mLast = this;
248    }
249    mPrev = statement;
250    mNext = statement->mNext;
251    statement->mNext = this;
252    if (LLVM_LIKELY(mNext != nullptr)) {
253        mNext->mPrev = this;
254    }
255    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
256        PabloBlock * body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
257        body->setParent(mParent);
258    }
259}
260
261/** ------------------------------------------------------------------------------------------------------------- *
262 * @brief removeFromParent
263 ** ------------------------------------------------------------------------------------------------------------- */
264Statement * Statement::removeFromParent() {
265    Statement * next = mNext;
266    if (LLVM_LIKELY(mParent != nullptr)) {
267        if (LLVM_UNLIKELY(mParent->mFirst == this)) {
268            mParent->mFirst = mNext;
269        }
270        if (LLVM_UNLIKELY(mParent->mLast == this)) {
271            mParent->mLast = mPrev;
272        }
273        if (LLVM_UNLIKELY(mParent->mInsertionPoint == this)) {
274            mParent->mInsertionPoint = mPrev;
275        }
276        if (LLVM_LIKELY(mPrev != nullptr)) {
277            mPrev->mNext = mNext;
278        }
279        if (LLVM_LIKELY(mNext != nullptr)) {
280            mNext->mPrev = mPrev;
281        }
282        if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
283            PabloBlock * body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
284            body->setParent(nullptr);
285        }
286    }
287    mPrev = nullptr;
288    mNext = nullptr;
289    mParent = nullptr;
290    return next;
291}
292
293/** ------------------------------------------------------------------------------------------------------------- *
294 * @brief eraseFromParent
295 ** ------------------------------------------------------------------------------------------------------------- */
296Statement * Statement::eraseFromParent(const bool recursively) {
297
298    SmallVector<Statement *, 1> redundantBranches;
299    // If this is an If or While statement, we'll have to remove the statements within the
300    // body or we'll lose track of them.
301    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
302        PabloBlock * const body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
303        body->eraseFromParent(recursively);
304    } else if (LLVM_UNLIKELY(isa<Assign>(this))) {
305        for (PabloAST * use : mUsers) {
306            if (If * ifNode = dyn_cast<If>(use)) {
307                auto & defs = ifNode->getDefined();
308                auto f = std::find(defs.begin(), defs.end(), this);
309                if (LLVM_LIKELY(f != defs.end())) {
310                    this->removeUser(ifNode);
311                    ifNode->removeUser(this);
312                    defs.erase(f);
313                    if (LLVM_UNLIKELY(defs.empty())) {
314                        redundantBranches.push_back(ifNode);
315                    }
316                }
317            }
318        }
319    } else if (LLVM_UNLIKELY(isa<Next>(this))) {
320        for (PabloAST * use : mUsers) {
321            if (While * whileNode = dyn_cast<While>(use)) {
322                auto & vars = whileNode->getVariants();
323                auto f = std::find(vars.begin(), vars.end(), this);
324                if (LLVM_LIKELY(f != vars.end())) {
325                    this->removeUser(whileNode);
326                    whileNode->removeUser(this);
327                    vars.erase(f);
328                    if (LLVM_UNLIKELY(vars.empty())) {
329                        redundantBranches.push_back(whileNode);
330                    }
331                }
332            }
333        }
334    }
335
336    replaceAllUsesWith(PabloBlock::createZeroes());
337
338    if (recursively) {
339        for (unsigned i = 0; i != mOperands; ++i) {
340            PabloAST * const op = mOperand[i]; assert (op);
341            op->removeUser(this);
342            if (LLVM_UNLIKELY(op->getNumUses() == 0 && isa<Statement>(op))) {
343                cast<Statement>(op)->eraseFromParent(true);
344            }
345            mOperand[i] = nullptr;
346        }
347        if (LLVM_UNLIKELY(redundantBranches.size() != 0)) {
348            // By eliminating this redundant branch, we may inadvertantly delete the scope block this statement
349            // resides within. Return null if so.
350            bool eliminatedScope = false;
351            for (Statement * br : redundantBranches) {
352                const PabloBlock * const body = isa<If>(br) ? cast<If>(br)->getBody() : cast<While>(br)->getBody();
353                if (LLVM_UNLIKELY(body == getParent())) {
354                    eliminatedScope = true;
355                }
356                br->eraseFromParent(true);
357            }
358            if (eliminatedScope) {
359                return nullptr;
360            }
361        }
362    } else { // just remove this statement from its operands' users list
363        for (unsigned i = 0; i != mOperands; ++i) {
364            PabloAST * const op = mOperand[i]; assert (op);
365            op->removeUser(this);
366            mOperand[i] = nullptr;
367        }
368    }
369    Statement * const next = removeFromParent();
370    mAllocator.deallocate(reinterpret_cast<Allocator::pointer>(this));
371    return next;
372}
373
374/** ------------------------------------------------------------------------------------------------------------- *
375 * @brief replaceWith
376 ** ------------------------------------------------------------------------------------------------------------- */
377Statement * Statement::replaceWith(PabloAST * const expr, const bool rename, const bool recursively) {
378    assert (expr);
379    if (LLVM_UNLIKELY(expr == this)) {
380        return getNextNode();
381    }
382    if (LLVM_LIKELY(rename && isa<Statement>(expr))) {
383        Statement * const stmt = cast<Statement>(expr);
384        if (getName()->isUserDefined() && stmt->getName()->isGenerated()) {
385            stmt->setName(getName());
386        }
387    }
388    replaceAllUsesWith(expr);
389    return eraseFromParent(recursively);
390}
391
392/** ------------------------------------------------------------------------------------------------------------- *
393 * @brief addOperand
394 ** ------------------------------------------------------------------------------------------------------------- */
395void Variadic::addOperand(PabloAST * const expr) {
396    if (LLVM_UNLIKELY(mOperands == mCapacity)) {
397        mCapacity = std::max<unsigned>(mCapacity * 2, 2);
398        PabloAST ** expandedOperandSpace = reinterpret_cast<PabloAST**>(mAllocator.allocate(mCapacity * sizeof(PabloAST *)));
399        for (unsigned i = 0; i != mOperands; ++i) {
400            expandedOperandSpace[i] = mOperand[i];
401        }
402        mAllocator.deallocate(reinterpret_cast<Allocator::pointer>(mOperand));
403        mOperand = expandedOperandSpace;
404    }
405    mOperand[mOperands++] = expr;
406    expr->addUser(this);
407}
408
409/** ------------------------------------------------------------------------------------------------------------- *
410 * @brief removeOperand
411 ** ------------------------------------------------------------------------------------------------------------- */
412PabloAST * Variadic::removeOperand(const unsigned index) {
413    assert (index < mOperands);
414    PabloAST * const expr = mOperand[index];
415    assert (expr);
416    --mOperands;
417    for (unsigned i = index; i != mOperands; ++i) {
418        mOperand[i] = mOperand[i + 1];
419    }
420    mOperand[mOperands] = nullptr;
421    expr->removeUser(this);
422    return expr;
423}
424
425/** ------------------------------------------------------------------------------------------------------------- *
426 * @brief contains
427 ** ------------------------------------------------------------------------------------------------------------- */
428bool StatementList::contains(Statement * const statement) {
429    for (Statement * stmt : *this) {
430        if (statement == stmt) {
431            return true;
432        }
433    }
434    return false;
435}
436
437/** ------------------------------------------------------------------------------------------------------------- *
438 * @brief escapes
439 *
440 * Is this statement used outside of its scope?
441 ** ------------------------------------------------------------------------------------------------------------- */
442bool escapes(const Statement * statement) {
443    const PabloBlock * const parent = statement->getParent();
444    for (const PabloAST * user : statement->users()) {
445        if (LLVM_LIKELY(isa<Statement>(user))) {
446            const PabloBlock * used = cast<Statement>(user)->getParent();
447            while (used != parent) {
448                used = used->getParent();
449                if (used == nullptr) {
450                    assert (isa<Assign>(statement) || isa<Next>(statement));
451                    return true;
452                }
453            }
454        }
455    }
456    return false;
457}
458
459/** ------------------------------------------------------------------------------------------------------------- *
460 * @brief dominates
461 *
462 * Does a precede (dominate) b?
463 ** ------------------------------------------------------------------------------------------------------------- */
464bool dominates(const PabloAST * const expr1, const PabloAST * const expr2) {
465    if (LLVM_UNLIKELY(expr1 == nullptr || expr2 == nullptr)) {
466        return (expr2 == nullptr);
467    } else if (LLVM_LIKELY(isa<Statement>(expr1))) {
468        const Statement * stmt1 = cast<Statement>(expr1);
469        assert ("expr1 is not in any block!" && stmt1->getParent());
470        if (isa<Statement>(expr2)) {
471            const Statement * stmt2 = cast<Statement>(expr2);
472            assert ("expr2 is not in any block!" && stmt2->getParent());
473
474            while (stmt1->getParent() != stmt2->getParent()) {
475
476                // Statement 1 preceeds Statement 2 if the branch leading to Statement 2
477                // succeeds Statement 1.
478
479                // But if Statement 1 escapes its block, it may still succeed Statement 2
480                // if and only if Statement 1 is an Assign or Next node whose outermost
481                // branch succeeds Statement 1. It is not enough to simply traverse back
482                // arbritarily. Test.
483
484                if (LLVM_UNLIKELY(isa<Assign>(stmt1))) {
485                    for (const PabloAST * user : stmt1->users()) {
486                        if (isa<If>(user)) {
487                            for (const Assign * def : cast<If>(user)->getDefined()) {
488                                if (def == stmt1) {
489                                    const Statement * test = stmt1;
490                                    for (;;) {
491                                        if (test->getParent() == stmt2->getParent()) {
492                                            stmt1 = test;
493                                            goto check;
494                                        }
495                                        test = test->getParent()->getBranch();
496                                        if (test == nullptr) {
497                                            break;
498                                        }
499                                    }
500                                }
501                            }
502                        }
503                    }
504                } else if (LLVM_UNLIKELY(isa<Next>(stmt1))) {
505                    for (const PabloAST * user : stmt1->users()) {
506                        if (isa<While>(user)) {
507                            for (const Next * var : cast<While>(user)->getVariants()) {
508                                if (var == stmt1) {
509                                    const Statement * test = stmt1;
510                                    for (;;) {
511                                        if (test->getParent() == stmt2->getParent()) {
512                                            stmt1 = test;
513                                            goto check;
514                                        }
515                                        test = test->getParent()->getBranch();
516                                        if (test == nullptr) {
517                                            break;
518                                        }
519                                    }
520                                }
521                            }
522                        }
523                    }
524                }
525
526                stmt2 = stmt2->getParent()->getBranch();
527                if (stmt2 == nullptr) {
528                    return false;
529                }
530
531            }
532
533check:      assert(stmt1->getParent() == stmt2->getParent());
534
535            const Statement * temp1 = stmt1, * temp2 = stmt2;
536            while (temp1 && temp2) {
537                if (temp1 == stmt2) {
538                    return true;
539                } else if (temp2 == stmt1) {
540                    return false;
541                }
542                temp1 = temp1->getNextNode();
543                temp2 = temp2->getNextNode();
544            }
545            return (temp2 == nullptr);
546        }
547        return false;
548    }
549    return true;
550}
551
552
553}
Note: See TracBrowser for help on using the repository browser.