Ignore:
Timestamp:
Nov 6, 2016, 8:37:11 PM (3 years ago)
Author:
nmedfort
Message:

Initial work on adding types to PabloAST and mutable Var objects.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r5160 r5202  
    1111#include <llvm/ADT/SmallVector.h>
    1212#include <boost/container/flat_set.hpp>
     13#include <pablo/printer_pablos.h>
    1314
    1415using namespace boost::container;
     
    1920PabloAST::VectorAllocator PabloAST::mVectorAllocator;
    2021
     22using TypeId = PabloAST::ClassTypeId;
     23
    2124/** ------------------------------------------------------------------------------------------------------------- *
    2225 * @brief equals
     
    2730bool equals(const PabloAST * const expr1, const PabloAST * const expr2) {
    2831    assert (expr1 && expr2);
    29     if (expr1 == expr2) {
     32    if (LLVM_UNLIKELY(expr1 == expr2)) {
    3033        return true;
    3134    } 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;
     35        if (LLVM_LIKELY(expr1->getType() == expr2->getType())) {
     36            if ((isa<Zeroes>(expr1)) || (isa<Ones>(expr1))) {
     37                return true;
     38            } else if (isa<Var>(expr1)) {
     39                return (cast<Var>(expr1)->getName() == cast<Var>(expr2)->getName());
     40            } else if (isa<Not>(expr1)) {
     41                return equals(cast<Not>(expr1)->getOperand(0), cast<Not>(expr2)->getOperand(0));
     42            } else if (isa<InFile>(expr1)) {
     43                return equals(cast<InFile>(expr1)->getOperand(0), cast<InFile>(expr2)->getOperand(0));
     44            } else if (isa<AtEOF>(expr1)) {
     45                return equals(cast<AtEOF>(expr1)->getOperand(0), cast<AtEOF>(expr2)->getOperand(0));
     46            } else if (isa<Variadic>(expr1)) {
     47                const Variadic * const var1 = cast<Variadic>(expr1);
     48                const Variadic * const var2 = cast<Variadic>(expr2);
     49                if (var1->getNumOperands() == var2->getNumOperands()) {
     50                    const unsigned operands = var1->getNumOperands();
     51                    for (unsigned i = 0; i != operands; ++i) {
     52                        bool missing = true;
     53                        for (unsigned j = 0; j != operands; ++j) {
     54                            // odds are both variadics will be sorted; optimize towards testing them in order.
     55                            unsigned k = i + j;
     56                            if (LLVM_UNLIKELY(k >= operands)) {
     57                                k -= operands;
     58                            }
     59                            if (equals(var1->getOperand(i), var2->getOperand(k))) {
     60                                missing = false;
     61                                break;
     62                            }
    5463                        }
    55                         if (equals(var1->getOperand(i), var2->getOperand(k))) {
    56                             missing = false;
    57                             break;
     64                        if (missing) {
     65                            return false;
    5866                        }
    5967                    }
    60                     if (missing) {
     68                    return true;
     69                }
     70            } else if (isa<Statement>(expr1)) {
     71                const Statement * stmt1 = cast<Statement>(expr1);
     72                const Statement * stmt2 = cast<Statement>(expr2);
     73                assert (stmt1->getNumOperands() == stmt2->getNumOperands());
     74                for (unsigned i = 0; i != stmt1->getNumOperands(); ++i) {
     75                    if (!equals(stmt1->getOperand(i), stmt2->getOperand(i))) {
    6176                        return false;
    6277                    }
     
    6479                return true;
    6580            }
    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;
     81
    7882        }
    7983    }
     
    108112 * @brief addUser
    109113 ** ------------------------------------------------------------------------------------------------------------- */
    110 void 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);
     114bool PabloAST::addUser(PabloAST * const user) { assert (user);
     115    const auto p = std::lower_bound(mUsers.begin(), mUsers.end(), user);
     116    const bool unique = p == mUsers.end() || *p != user;
     117    mUsers.insert(p, user);
     118    return unique;
    114119}
    115120
     
    117122 * @brief removeUser
    118123 ** ------------------------------------------------------------------------------------------------------------- */
    119 void 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  * @brief checkEscapedValueList
    137  ** ------------------------------------------------------------------------------------------------------------- */
    138 template <class ValueType, class ValueList>
    139 inline void Statement::checkEscapedValueList(Statement * const branch, PabloAST * const from, PabloAST * const to, ValueList & list) {
    140     if (LLVM_LIKELY(isa<ValueType>(from))) {
    141         const auto f = std::find(list.begin(), list.end(), cast<ValueType>(from));
    142         if (LLVM_LIKELY(f != list.end())) {
    143             branch->removeUser(from);
    144             from->removeUser(branch);
    145             if (LLVM_UNLIKELY(isa<ValueType>(to))) {
    146                 if (LLVM_LIKELY(std::find(list.begin(), list.end(), cast<ValueType>(to)) == list.end())) {
    147                     PabloBlock * parent = cast<ValueType>(to)->getParent();
    148                     for (;;) {
    149                         if (parent == cast<ValueType>(from)->getParent()) {
    150                             *f = cast<ValueType>(to);
    151                             branch->addUser(to);
    152                             to->addUser(branch);
    153                             return;
    154                         }
    155                         parent = parent->getPredecessor ();
    156                         if (parent == nullptr) {
    157                             break;
    158                         }
    159                     }
    160                 }
    161             }
    162             list.erase(f);
    163         }                             
    164     }
     124bool PabloAST::removeUser(PabloAST * const user) { assert (user);
     125    const auto p = std::lower_bound(mUsers.begin(), mUsers.end(), user);
     126    assert (p != mUsers.end() && *p == user);
     127    const auto n = mUsers.erase(p);
     128    return n == mUsers.end() || *n != user;
     129}
     130
     131/** ------------------------------------------------------------------------------------------------------------- *
     132 * @brief print
     133 ** ------------------------------------------------------------------------------------------------------------- */
     134void PabloAST::print(llvm::raw_ostream & O) const {
     135    PabloPrinter::print(this, O);
    165136}
    166137
     
    169140 ** ------------------------------------------------------------------------------------------------------------- */
    170141void Statement::replaceUsesOfWith(PabloAST * const from, PabloAST * const to) {
    171     if (LLVM_UNLIKELY(from == to)) {
    172         return;
    173     }
    174     for (unsigned i = 0; i != getNumOperands(); ++i) {
    175        if (getOperand(i) == from) {
    176            setOperand(i, to);
    177        }
    178     }
    179     if (LLVM_UNLIKELY(isa<If>(this))) {
    180         checkEscapedValueList<Assign>(this, from, to, cast<If>(this)->getDefined());
    181     } else if (LLVM_UNLIKELY(isa<While>(this))) {
    182         checkEscapedValueList<Next>(this, from, to, cast<While>(this)->getVariants());
     142    if (LLVM_LIKELY(from != to)) {
     143        for (unsigned i = 0; i != getNumOperands(); ++i) {
     144           if (getOperand(i) == from) {
     145               setOperand(i, to);
     146           }
     147        }
    183148    }
    184149}
     
    194159    if (LLVM_UNLIKELY(prior == value)) {
    195160        return;
    196     }   
    197     throwIfNonMatchingTypes(prior, value);
     161    }     
    198162    prior->removeUser(this);
    199163    mOperand[index] = value;
     
    207171    if (LLVM_UNLIKELY(statement == this)) {
    208172        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!");
     173    } else if (LLVM_UNLIKELY(statement == nullptr)) {
     174        llvm::report_fatal_error("cannot insert before null statement!");
     175    } else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
     176        llvm::report_fatal_error("statement is not contained in a pablo block!");
    215177    }
    216178    removeFromParent();
     
    225187        mPrev->mNext = this;
    226188    }
    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->setPredecessor (mParent);
    230     }
    231189}
    232190
     
    238196        return;
    239197    } else if (LLVM_UNLIKELY(statement == nullptr)) {
    240         throw std::runtime_error("cannot insert after null statement!");
     198        llvm::report_fatal_error("cannot insert after null statement!");
    241199    } else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
    242         throw std::runtime_error("statement is not contained in a pablo block!");
     200        llvm::report_fatal_error("statement is not contained in a pablo block!");
    243201    }
    244202    removeFromParent();
     
    253211        mNext->mPrev = this;
    254212    }
    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->setPredecessor (mParent);
    258     }
    259213}
    260214
     
    280234            mNext->mPrev = mPrev;
    281235        }
    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->setPredecessor (nullptr);
    285         }
    286236    }
    287237    mPrev = nullptr;
     
    300250    }
    301251
    302     SmallVector<Statement *, 1> redundantBranches;
    303     // If this is an If or While statement, we'll have to remove the statements within the
    304     // body or we'll lose track of them.
    305     if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
    306         PabloBlock * const body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
    307         body->eraseFromParent(recursively);
    308     } else if (LLVM_UNLIKELY(isa<Assign>(this))) {
    309         for (PabloAST * use : mUsers) {
    310             if (If * ifNode = dyn_cast<If>(use)) {
    311                 auto & defs = ifNode->getDefined();
    312                 auto f = std::find(defs.begin(), defs.end(), this);
    313                 if (LLVM_LIKELY(f != defs.end())) {
    314                     this->removeUser(ifNode);
    315                     ifNode->removeUser(this);
    316                     defs.erase(f);
    317                     if (LLVM_UNLIKELY(defs.empty())) {
    318                         redundantBranches.push_back(ifNode);
    319                     }
    320                 }
    321             }
    322         }
    323     } else if (LLVM_UNLIKELY(isa<Next>(this))) {
    324         for (PabloAST * use : mUsers) {
    325             if (While * whileNode = dyn_cast<While>(use)) {
    326                 auto & vars = whileNode->getVariants();
    327                 auto f = std::find(vars.begin(), vars.end(), this);
    328                 if (LLVM_LIKELY(f != vars.end())) {
    329                     this->removeUser(whileNode);
    330                     whileNode->removeUser(this);
    331                     vars.erase(f);
    332                     if (LLVM_UNLIKELY(vars.empty())) {
    333                         redundantBranches.push_back(whileNode);
    334                     }
    335                 }
    336             }
    337         }
    338     }
    339 
    340     replaceAllUsesWith(getParent()->createZeroes(getType()));
    341 
    342     if (recursively) {
    343         for (unsigned i = 0; i != mOperands; ++i) {
    344             PabloAST * const op = mOperand[i]; assert (op);
    345             op->removeUser(this);
    346             if (LLVM_UNLIKELY(op->getNumUses() == 0 && isa<Statement>(op))) {
     252    if (LLVM_UNLIKELY(isa<Branch>(this))) {
     253        cast<Branch>(this)->getBody()->eraseFromParent(recursively);
     254    } else if (LLVM_LIKELY(!isa<Assign>(this))) {
     255        replaceAllUsesWith(getParent()->createZeroes(getType()));
     256    }
     257
     258    Statement * const next = removeFromParent();
     259
     260    for (unsigned i = 0; i != mOperands; ++i) {
     261        PabloAST * const op = mOperand[i]; assert (op);
     262        op->removeUser(this);
     263        if (LLVM_UNLIKELY(recursively && op->getNumUses() == 0)) {
     264            if (LLVM_LIKELY(isa<Statement>(op))) {
    347265                cast<Statement>(op)->eraseFromParent(true);
    348266            }
    349             mOperand[i] = nullptr;
    350         }
    351         if (LLVM_UNLIKELY(redundantBranches.size() != 0)) {
    352             // By eliminating this redundant branch, we may inadvertantly delete the scope block this statement
    353             // resides within. Return null if so.
    354             bool eliminatedScope = false;
    355             for (Statement * br : redundantBranches) {
    356                 const PabloBlock * const body = isa<If>(br) ? cast<If>(br)->getBody() : cast<While>(br)->getBody();
    357                 if (LLVM_UNLIKELY(body == getParent())) {
    358                     eliminatedScope = true;
    359                 }
    360                 br->eraseFromParent(true);
    361             }
    362             if (eliminatedScope) {
    363                 return nullptr;
    364             }
    365         }
    366     } else { // just remove this statement from its operands' users list
    367         for (unsigned i = 0; i != mOperands; ++i) {
    368             PabloAST * const op = mOperand[i]; assert (op);
    369             op->removeUser(this);
    370             mOperand[i] = nullptr;
    371         }
    372     }
    373     Statement * const next = removeFromParent();
     267        }
     268        mOperand[i] = nullptr;
     269    }
     270
    374271    mAllocator.deallocate(reinterpret_cast<Allocator::pointer>(this));
    375272    return next;
     
    385282    }
    386283    if (LLVM_LIKELY(rename && isa<Statement>(expr))) {
    387         Statement * const stmt = cast<Statement>(expr);
    388         if (getName()->isUserDefined() && stmt->getName()->isGenerated()) {
    389             stmt->setName(getName());
     284        if (mName && cast<Statement>(expr)->mName == nullptr) {
     285            cast<Statement>(expr)->setName(mName);
    390286        }
    391287    }
     
    398294 ** ------------------------------------------------------------------------------------------------------------- */
    399295void Variadic::addOperand(PabloAST * const expr) {
    400     throwIfNonMatchingTypes(this, expr);
    401296    if (LLVM_UNLIKELY(mOperands == mCapacity)) {
    402297        mCapacity = std::max<unsigned>(mCapacity * 2, 2);
     
    441336
    442337/** ------------------------------------------------------------------------------------------------------------- *
    443  * @brief escapes
    444  *
    445  * Is this statement used outside of its scope?
    446  ** ------------------------------------------------------------------------------------------------------------- */
    447 bool escapes(const Statement * statement) {
    448     const PabloBlock * const parent = statement->getParent();
    449     for (const PabloAST * user : statement->users()) {
    450         if (LLVM_LIKELY(isa<Statement>(user))) {
    451             const PabloBlock * used = cast<Statement>(user)->getParent();
    452             while (used != parent) {
    453                 used = used->getPredecessor ();
    454                 if (used == nullptr) {
    455                     assert (isa<Assign>(statement) || isa<Next>(statement));
    456                     return true;
    457                 }
    458             }
    459         }
    460     }
    461     return false;
    462 }
    463 
    464 /** ------------------------------------------------------------------------------------------------------------- *
    465338 * @brief dominates
    466339 *
    467  * Does a precede (dominate) b?
     340 * expr1 dominates (>>) expr2 if every path from the *entry* node to expr2 must go through expr1
     341 *
     342 * For example, consider the program (with entry node 1):
     343 *
     344 * 1. Assign a, s           1 >> 1, 2, 3, 4, 5, 6
     345 * 2. While x:              2 >> 2, 3, 4, 5, 6
     346 * 3.   Assign a, p         3 >> 3
     347 * 4. While y:              4 >> 4, 5, 6
     348 * 5.   Assign a, q         5 >> 5
     349 * 6. Assign a, t           6 >> 6
    468350 ** ------------------------------------------------------------------------------------------------------------- */
    469351bool dominates(const PabloAST * const expr1, const PabloAST * const expr2) {
     
    478360
    479361            while (stmt1->getParent() != stmt2->getParent()) {
    480 
    481                 // Statement 1 preceeds Statement 2 if the branch leading to Statement 2
    482                 // succeeds Statement 1.
    483 
    484                 // But if Statement 1 escapes its block, it may still succeed Statement 2
    485                 // if and only if Statement 1 is an Assign or Next node whose outermost
    486                 // branch succeeds Statement 1. It is not enough to simply traverse back
    487                 // arbritarily. Test.
    488 
    489                 if (LLVM_UNLIKELY(isa<Assign>(stmt1))) {
    490                     for (const PabloAST * user : stmt1->users()) {
    491                         if (isa<If>(user)) {
    492                             for (const Assign * def : cast<If>(user)->getDefined()) {
    493                                 if (def == stmt1) {
    494                                     const Statement * test = stmt1;
    495                                     for (;;) {
    496                                         if (test->getParent() == stmt2->getParent()) {
    497                                             stmt1 = test;
    498                                             goto check;
    499                                         }
    500                                         test = test->getParent()->getBranch();
    501                                         if (test == nullptr) {
    502                                             break;
    503                                         }
    504                                     }
    505                                 }
    506                             }
    507                         }
    508                     }
    509                 } else if (LLVM_UNLIKELY(isa<Next>(stmt1))) {
    510                     for (const PabloAST * user : stmt1->users()) {
    511                         if (isa<While>(user)) {
    512                             for (const Next * var : cast<While>(user)->getVariants()) {
    513                                 if (var == stmt1) {
    514                                     const Statement * test = stmt1;
    515                                     for (;;) {
    516                                         if (test->getParent() == stmt2->getParent()) {
    517                                             stmt1 = test;
    518                                             goto check;
    519                                         }
    520                                         test = test->getParent()->getBranch();
    521                                         if (test == nullptr) {
    522                                             break;
    523                                         }
    524                                     }
    525                                 }
    526                             }
    527                         }
    528                     }
    529                 }
    530 
    531362                stmt2 = stmt2->getParent()->getBranch();
    532363                if (stmt2 == nullptr) {
    533364                    return false;
    534365                }
    535 
    536366            }
    537 
    538 check:      assert(stmt1->getParent() == stmt2->getParent());
    539367
    540368            const Statement * temp1 = stmt1, * temp2 = stmt2;
     
    548376                temp2 = temp2->getNextNode();
    549377            }
    550             return (temp2 == nullptr);
     378            // If temp1 isn't null then temp2 must be null; thus stmt2 must succeed stmt1.
     379            return (temp1 != nullptr);
    551380        }
    552381        return false;
     
    556385
    557386/** ------------------------------------------------------------------------------------------------------------- *
    558  * @brief throwIfNonMatchingTypes
    559  ** ------------------------------------------------------------------------------------------------------------- */
    560 void PabloAST::throwIfNonMatchingTypes(const PabloAST * const a, const PabloAST * const b) {
    561     if (LLVM_UNLIKELY(a->getType() != b->getType())) {
    562         std::string tmp;
    563         raw_string_ostream out(tmp);
    564         out << "Error: ";
    565         PabloPrinter::print(a, out);
    566         out << "'s type does not match ";
    567         PabloPrinter::print(b, out);
    568         throw std::runtime_error(out.str());
    569     }
    570 }
    571 
    572 /** ------------------------------------------------------------------------------------------------------------- *
    573  * @brief throwIfNonMatchingTypes
    574  ** ------------------------------------------------------------------------------------------------------------- */
    575 void PabloAST::throwIfNonMatchingType(const PabloAST * const a, const PabloType::TypeId typeId) {
    576     if (LLVM_UNLIKELY(a->getType() == nullptr || a->getType()->getTypeId() != typeId)) {
    577         std::string tmp;
    578         raw_string_ostream out(tmp);
    579         out << "Error: ";
    580         PabloPrinter::print(a, out);
    581         out << "'s type is invalid.";
    582         throw std::runtime_error(out.str());
    583     }
    584 }
    585 
    586 }
     387 * @brief postdominates
     388 *
     389 * expr1 post-dominates (<<) expr2 if all paths to the *exit* node starting at expr2 must go through expr1
     390 *
     391 * For example, consider the program (with exit node 6):
     392 *
     393 * 1. Assign a, s           1 << 1
     394 * 2. While x:              2 << 1, 2
     395 * 3.   Assign a, p         3 << 1, 2, 3
     396 * 4. While y:              4 << 1, 2, 4
     397 * 5.   Assign a, q         5 << 1, 2, 4, 5
     398 * 6. Assign a, t           6 << 1, 2, 3, 4, 5, 6
     399 ** ------------------------------------------------------------------------------------------------------------- */
     400bool postdominates(const PabloAST * const expr1, const PabloAST * const expr2) {
     401    throw std::runtime_error("not implemented yet!");
     402}
     403
     404}
Note: See TracChangeset for help on using the changeset viewer.