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

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

Optimized Symbol Generation (and fixed potential bug that could allow duplicate names being constructed); made PabloKernel? extend PabloAST (temporarily removed PabloAST::getName() to avoid diamond problem); added an internal scalar to PabloKernel? struct for each Count to avoid InOut? output scalar variable problem; allowed CodeMotionPass? to move code within the same scope but across a branch statement. Began work on separating Kernels into either Block-Oriented or Segment-Oriented kernels.

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