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.

Location:
icGREP/icgrep-devel/icgrep/pablo
Files:
5 added
6 deleted
57 edited

Legend:

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

    r5160 r5202  
    1010namespace pablo {
    1111
     12using TypeId = PabloAST::ClassTypeId;
     13
    1214template <typename Type>
    1315using SmallSet = boost::container::flat_set<Type>;
     
    1820 * @brief verifyUseDefInformation
    1921 ** ------------------------------------------------------------------------------------------------------------- */
    20 template<typename VectorType>
    21 inline bool checkVector(const PabloAST * const value, const VectorType & vector, size_t & uses) {
    22     for (auto escapedValue : vector) {
    23         if (escapedValue == value) {
    24             ++uses;
    25             return false;
    26         }
    27     }
    28     return true;
    29 }
    30 
    31 void testUsers(const PabloAST * expr, const ScopeSet & validScopes) {
    32     if (isa<Count>(expr)) { // !! matchedLineCount is not being correctly added to the function !!
    33         return;
    34     }
     22void testUsers(const PabloAST * expr, const ScopeSet & validScopes) {
    3523    size_t uses = 0;
    3624    SmallSet<const PabloAST *> verified;
    3725    for (const PabloAST * use : expr->users()) {
    38         if (LLVM_LIKELY(isa<Statement>(use))) {
    39             if (LLVM_LIKELY(verified.count(use) == 0)) {
    40                 const Statement * const user = cast<Statement>(use);
    41                 // test whether this user is in a block in the program
    42                 if (LLVM_UNLIKELY(validScopes.count(user->getParent()) == 0)) {
    43                     std::string tmp;
    44                     raw_string_ostream str(tmp);
    45                     str << "PabloVerifier: use-def error: ";
    46                     PabloPrinter::print(user, str);
    47                     str << " is a user of ";
    48                     PabloPrinter::print(expr, str);
    49                     if (user->getParent() == nullptr) {
    50                         str << " but is not in any scope.";
    51                     } else {
    52                         str << " but is in a deleted scope.";
    53                     }
    54                     throw std::runtime_error(str.str());
    55                 }
    56                 // expr may be used more than once by the same user.
    57                 bool notFound = true;
    58                 for (unsigned i = 0; i != user->getNumOperands(); ++i) {
    59                     if (user->getOperand(i) == expr) {
     26        if (LLVM_UNLIKELY(verified.count(use) != 0)) {
     27            continue;
     28        }
     29        if (LLVM_UNLIKELY(isa<PabloFunction>(use))) {
     30            const PabloFunction * f = cast<PabloFunction>(use);
     31            bool isParameter = false;
     32            bool isResult = false;
     33            for (unsigned i = 0; i != f->getNumOfParameters(); ++i) {
     34                if (f->getParameter(i) == expr) {
     35                    isParameter = true;
     36                    break;
     37                }
     38            }
     39            for (unsigned i = 0; i != f->getNumOfResults(); ++i) {
     40                if (f->getResult(i) == expr) {
     41                    isResult = true;
     42                    break;
     43                }
     44            }
     45            if (LLVM_UNLIKELY(!(isParameter ^ isResult))) {
     46                std::string tmp;
     47                raw_string_ostream str(tmp);
     48                str << "use-def error: ";
     49                PabloPrinter::print(expr, str);
     50                if (isParameter && isResult) {
     51                    str << " is both a parameter and result of ";
     52                } else {
     53                    str << " is neither a parameter nor result of ";
     54                }
     55                PabloPrinter::print(f, str);
     56                throw std::runtime_error(str.str());
     57            }
     58            ++uses;
     59        } else if (const Statement * const user = dyn_cast<Statement>(use)) {
     60            // test whether this user is in a block in the program
     61            if (LLVM_UNLIKELY(user->getParent() == nullptr || validScopes.count(user->getParent()) == 0)) {
     62                std::string tmp;
     63                raw_string_ostream str(tmp);
     64                str << "use-def error: ";
     65                PabloPrinter::print(user, str);
     66                str << " is a user of ";
     67                PabloPrinter::print(expr, str);
     68                str << " but ";
     69                PabloPrinter::print(use, str);
     70                if (user->getParent() == nullptr) {
     71                    str << " is not defined in any scope.";
     72                } else {
     73                    str << " is in an unreachable scope.";
     74                }
     75                throw std::runtime_error(str.str());
     76            }
     77            // expr may be used more than once by the same user.
     78            bool notFound = true;
     79            for (unsigned i = 0; i != user->getNumOperands(); ++i) {
     80                if (user->getOperand(i) == expr) {
     81                    notFound = false;
     82                    ++uses;
     83                }
     84            }
     85            if (isa<Branch>(user)) {
     86                for (const PabloAST * var : cast<Branch>(user)->getEscaped()) {
     87                    if (var == expr) {
    6088                        notFound = false;
    6189                        ++uses;
    6290                    }
    6391                }
    64                 if (const If * ifNode = dyn_cast<If>(expr)) {
    65                     notFound &= checkVector(user, ifNode->getDefined(), uses);
    66                 } else if (const If * ifNode = dyn_cast<If>(user)) {
    67                     notFound &= checkVector(expr, ifNode->getDefined(), uses);
    68                 } else if (const While * whileNode = dyn_cast<While>(expr)) {
    69                     notFound &= checkVector(user, whileNode->getVariants(), uses);
    70                 } else if (const While * whileNode = dyn_cast<While>(user)) {
    71                     notFound &= checkVector(expr, whileNode->getVariants(), uses);
    72                 } else if (isa<Next>(expr) && isa<Assign>(use)) {
    73                     notFound &= (use != cast<Next>(expr)->getInitial());
    74                 }
    75                 if (LLVM_UNLIKELY(notFound)) {
    76                     std::string tmp;
    77                     raw_string_ostream str(tmp);
    78                     str << "PabloVerifier: use-def error: ";
    79                     PabloPrinter::print(expr, str);
    80                     str << " is not a definition of ";
    81                     PabloPrinter::print(use, str);
    82                     throw std::runtime_error(str.str());
    83                 }
    84                 verified.insert(use);
    85             }
    86         } else if (LLVM_UNLIKELY(isa<PabloFunction>(use))) {
    87             if (LLVM_LIKELY(verified.count(use) == 0)) {
    88                 const PabloFunction * f = cast<PabloFunction>(use);
    89                 bool isParameter = false;
    90                 bool isResult = false;
    91                 for (unsigned i = 0; i != f->getNumOfParameters(); ++i) {
    92                     if (f->getParameter(i) == expr) {
    93                         isParameter = true;
    94                         break;
    95                     }
    96                 }
    97                 for (unsigned i = 0; i != f->getNumOfResults(); ++i) {
    98                     if (f->getResult(i) == expr) {
    99                         isResult = true;
    100                         break;
    101                     }
    102                 }
    103                 if (LLVM_UNLIKELY(!(isParameter ^ isResult))) {
    104                     std::string tmp;
    105                     raw_string_ostream str(tmp);
    106                     str << "PabloVerifier: use-def error: ";
    107                     PabloPrinter::print(expr, str);
    108                     if (isParameter && isResult) {
    109                         str << " is both a parameter and result of ";
    110                     } else {
    111                         str << " is not a parameter or result of ";
    112                     }
    113                     PabloPrinter::print(f, str);
    114                     throw std::runtime_error(str.str());
    115                 }
     92            }
     93            if (LLVM_UNLIKELY(notFound)) {
     94                std::string tmp;
     95                raw_string_ostream str(tmp);
     96                str << "use-def error: ";
     97                PabloPrinter::print(expr, str);
     98                str << " is not a definition of ";
     99                PabloPrinter::print(use, str);
     100                throw std::runtime_error(str.str());
     101            }
     102        } else if (isa<Var>(use)) {
     103            if (LLVM_UNLIKELY(isa<Branch>(expr) || isa<PabloFunction>(expr))) {
    116104                ++uses;
    117                 verified.insert(use);
    118             }
    119         } else {
    120             std::string tmp;
    121             raw_string_ostream str(tmp);
    122             str << "PabloVerifier: use-def error: expression ";
    123             PabloPrinter::print(use, str);
    124             str << " is incorrectly reported as a user of ";
    125             PabloPrinter::print(expr, str);
    126             throw std::runtime_error(str.str());
    127         }
     105            } else {
     106                std::string tmp;
     107                raw_string_ostream str(tmp);
     108                str << "use-def error: var ";
     109                PabloPrinter::print(use, str);
     110                str << " is a user of ";
     111                PabloPrinter::print(expr, str);
     112                str << " but can only be a user of a Branch or Function.";
     113                throw std::runtime_error(str.str());
     114            }
     115        }
     116        verified.insert(use);
    128117    }
    129118    if (LLVM_UNLIKELY(uses != expr->getNumUses())) {
    130119        std::string tmp;
    131120        raw_string_ostream str(tmp);
    132         str << "PabloVerifier: use-def error: ";
     121        str << "use-def error: ";
    133122        PabloPrinter::print(expr, str);
    134123        str << " is reported having " << expr->getNumUses() << " user(s)"
     
    165154        testUsers(stmt, validScopes);
    166155        testDefs(stmt);
    167         if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    168             verifyUseDefInformation(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), validScopes);
     156        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     157            verifyUseDefInformation(cast<Branch>(stmt)->getBody(), validScopes);
    169158        }
    170159    }
     
    174163    validScopes.insert(block);
    175164    for (const Statement * stmt : *block) {
    176         if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    177             gatherValidScopes(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), validScopes);
     165        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     166            gatherValidScopes(cast<Branch>(stmt)->getBody(), validScopes);
    178167        }
    179168    }
     
    184173    gatherValidScopes(function.getEntryBlock(), validScopes);
    185174    for (unsigned i = 0; i < function.getNumOfParameters(); ++i) {
     175        if (LLVM_UNLIKELY(function.getParameter(i) == nullptr)) {
     176            throw std::runtime_error("parameter " + std::to_string(i) + " is Null!");
     177        }
    186178        testUsers(function.getParameter(i), validScopes);
    187179    }
    188180    for (unsigned i = 0; i < function.getNumOfResults(); ++i) {
    189         testDefs(function.getResult(i));
     181        if (LLVM_UNLIKELY(function.getResult(i) == nullptr)) {
     182            throw std::runtime_error("result " + std::to_string(i) + " is Null!");
     183        }
     184        testUsers(function.getResult(i), validScopes);
    190185    }
    191186    verifyUseDefInformation(function.getEntryBlock(), validScopes);
     
    201196            return false;
    202197        }
    203         parent = parent->getPredecessor ();
     198        parent = parent->getPredecessor();
    204199    }
    205200    return true;
    206 }
    207 
    208 /** ------------------------------------------------------------------------------------------------------------- *
    209  * @brief throwUncontainedEscapedValueError
    210  ** ------------------------------------------------------------------------------------------------------------- */
    211 static void throwUncontainedEscapedValueError(const Statement * const stmt, const PabloAST * const value) {
    212     std::string tmp;
    213     raw_string_ostream str(tmp);
    214     str << "PabloVerifier: structure error: escaped value \"";
    215     PabloPrinter::print(value, str);
    216     str << "\" is not contained within the body of ";
    217     PabloPrinter::print(stmt, str);
    218     throw std::runtime_error(str.str());
    219 }
    220 
    221 /** ------------------------------------------------------------------------------------------------------------- *
    222  * @brief throwEscapedValueUsageError
    223  ** ------------------------------------------------------------------------------------------------------------- */
    224 static void throwEscapedValueUsageError(const Statement * const stmt, const PabloAST * const value, const PabloAST * const def, const PabloAST * const user, const unsigned count) {
    225     std::string tmp;
    226     raw_string_ostream str(tmp);
    227     str << "PabloVerifier: structure error: ";
    228     PabloPrinter::print(value, str);
    229     str << " is an escaped value of ";
    230     PabloPrinter::print(stmt, str);
    231     str << " but ";
    232     PabloPrinter::print(user, str);
    233     if (count == 0) {
    234         str << " is not considered a user of ";
    235     } else if (count > 0) {
    236         str << " was recorded too many times (" << count << ") in the user list of ";
    237     }
    238     PabloPrinter::print(def, str);
    239     throw std::runtime_error(str.str());
    240201}
    241202
     
    246207    std::string tmp;
    247208    raw_string_ostream str(tmp);
    248     str << "PabloVerifier: structure error: ";
     209    str << "structure error: ";
    249210    PabloPrinter::print(stmt, str);
    250211    str << " is not contained in its reported scope block";
     
    258219    std::string tmp;
    259220    raw_string_ostream str(tmp);
    260     str << "PabloVerifier: structure error: ";
     221    str << "structure error: ";
    261222    PabloPrinter::print(stmt, str);
    262223    str << " branches into a scope block that reports ";
     
    267228
    268229/** ------------------------------------------------------------------------------------------------------------- *
    269  * @brief throwReflexiveIfConditionError
    270  ** ------------------------------------------------------------------------------------------------------------- */
    271 static void throwReflexiveIfConditionError(const PabloAST * const ifNode) {
    272     std::string tmp;
    273     raw_string_ostream str(tmp);
    274     str << "PabloVerifier: structure error: the condition of ";
    275     PabloPrinter::print(ifNode, str);
    276     str << " cannot be defined by the If node itself.";
    277     throw std::runtime_error(str.str());
     230 * @brief illegalOperandType
     231 ** ------------------------------------------------------------------------------------------------------------- */
     232static inline bool illegalOperandType(const PabloAST * const op) {
     233    switch (op->getClassTypeId()) {
     234        case TypeId::Block:
     235        case TypeId::Function:
     236        case TypeId::Prototype:
     237        case TypeId::Assign:
     238        case TypeId::Call:
     239        case TypeId::SetIthBit:
     240        case TypeId::If:
     241        case TypeId::While:
     242            return true;
     243        default:
     244            return false;
     245    }
    278246}
    279247
     
    287255            std::string tmp;
    288256            raw_string_ostream str(tmp);
    289             str << "PabloVerifier: structure error: ";
    290257            PabloPrinter::print(stmt, str);
    291258            str << " succeeds ";
    292259            PabloPrinter::print(prev, str);
    293             str << " but expects to preceed ";
     260            str << " but ";
     261            PabloPrinter::print(cast<PabloAST>(stmt), str);
     262            str << " expects to succeed ";
    294263            PabloPrinter::print(stmt->getPrevNode(), str);
    295264            throw std::runtime_error(str.str());
     
    299268            std::string tmp;
    300269            raw_string_ostream str(tmp);
    301             str << "PabloVerifier: structure error: ";
    302270            PabloPrinter::print(stmt, str);
    303271            str << " is not contained in its reported scope block";
    304272            throw std::runtime_error(str.str());
    305273        }
    306         if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    307             const PabloBlock * nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     274
     275        for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
     276            PabloAST * op = stmt->getOperand(i);
     277            if (LLVM_UNLIKELY(illegalOperandType(op))) {
     278                std::string tmp;
     279                raw_string_ostream str(tmp);
     280                PabloPrinter::print(op, str);
     281                str << " cannot be an operand of ";
     282                PabloPrinter::print(stmt, str);
     283                throw std::runtime_error(str.str());
     284            }
     285        }
     286
     287        if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     288
     289            PabloAST * const variable = cast<Assign>(stmt)->getVariable();
     290            if (LLVM_UNLIKELY(!isa<Var>(variable) && !isa<Extract>(variable))) {
     291                std::string tmp;
     292                raw_string_ostream out(tmp);
     293                out << "invalid assignment: ";
     294                PabloPrinter::print(stmt, out);
     295                out << "  --- ";
     296                PabloPrinter::print(variable, out);
     297                out << " must be a Var or Extract";
     298                throw std::runtime_error(out.str());
     299            }
     300
     301            PabloAST * const value = cast<Assign>(stmt)->getValue();
     302            if (LLVM_UNLIKELY(variable->getType() != value->getType())) {
     303                std::string tmp;
     304                raw_string_ostream out(tmp);
     305                out << "invalid assignment: ";
     306                PabloPrinter::print(stmt, out);
     307                out << "  --- type of ";
     308                PabloPrinter::print(variable, out);
     309                out << " differs from ";
     310                PabloPrinter::print(value, out);
     311                throw std::runtime_error(out.str());
     312            }
     313
     314        } else if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     315            const PabloBlock * nested = cast<Branch>(stmt)->getBody();
    308316            if (LLVM_UNLIKELY(nested->getBranch() != stmt)) {
    309317                throwMisreportedBranchError(stmt, nested->getBranch());
    310             } else if (LLVM_UNLIKELY(nested->getPredecessor () != block)) {
     318            } else if (LLVM_UNLIKELY(nested->getPredecessor() != block)) {
    311319                throwReportedScopeError(stmt);
    312             }
    313             if (isa<If>(stmt)) {
    314                 for (const Assign * def : cast<If>(stmt)->getDefined()) {
    315                     if (LLVM_UNLIKELY(def == cast<If>(stmt)->getCondition())) {
    316                         throwReflexiveIfConditionError(stmt);
    317                     } else if (LLVM_UNLIKELY(unreachable(def, nested))) {
    318                         throwUncontainedEscapedValueError(stmt, def);
    319                     }
    320                     unsigned count = std::count(stmt->user_begin(), stmt->user_end(), def);
    321                     if (LLVM_UNLIKELY(count != 1)) {
    322                         throwEscapedValueUsageError(stmt, def, stmt, def, count);
    323                     }
    324                     count = std::count(def->user_begin(), def->user_end(), stmt);
    325                     if (LLVM_UNLIKELY(count != 1)) {
    326                         throwEscapedValueUsageError(stmt, def, def, stmt, count);
    327                     }
    328                 }
    329             } else {
    330                 for (const Next * var : cast<While>(stmt)->getVariants()) {
    331                     if (LLVM_UNLIKELY(unreachable(var, nested))) {
    332                         throwUncontainedEscapedValueError(stmt, var);
    333                     }
    334                     unsigned count = std::count(stmt->user_begin(), stmt->user_end(), var);
    335                     if (LLVM_UNLIKELY(count != 1)) {
    336                         throwEscapedValueUsageError(stmt, var, stmt, var, count);
    337                     }
    338                     count = std::count(var->user_begin(), var->user_end(), stmt);
    339                     if (LLVM_UNLIKELY(count != ((cast<While>(stmt)->getCondition() == var) ? 2 : 1))) {
    340                         throwEscapedValueUsageError(stmt, var, var, stmt, count);
    341                     }
    342                 }
    343320            }
    344321            ++nestingDepth;
     
    381358};
    382359
    383 bool recursivelyDefined(const Statement * const stmt) {
    384     std::queue<const Statement *> Q;
    385     SmallSet<const PabloAST *> V;
    386     V.insert(stmt);
    387     for (const Statement * ancestor = stmt;;) {
    388         for (unsigned i = 0; i != ancestor->getNumOperands(); ++i) {
    389             const PabloAST * op = ancestor->getOperand(i);
    390             if (isa<Statement>(op) && V.count(op) == 0) {
    391                 if (op == stmt) {
    392                     return true;
    393                 }
    394                 Q.push(cast<Statement>(op));
    395                 V.insert(op);
    396             }
    397         }
    398         if (LLVM_UNLIKELY(Q.empty())) {
    399             break;
    400         }
    401         ancestor = Q.front();
    402         Q.pop();
    403     }
    404     return false;
    405 }
    406 
    407360void isTopologicallyOrdered(const PabloBlock * block, const OrderingVerifier & parent) {
    408361    OrderingVerifier ov(parent);
     
    410363        if (LLVM_UNLIKELY(isa<While>(stmt))) {
    411364            isTopologicallyOrdered(cast<While>(stmt)->getBody(), ov);
    412             for (const Next * var : cast<While>(stmt)->getVariants()) {
     365            for (const Var * var : cast<While>(stmt)->getEscaped()) {
    413366                ov.insert(var);
    414367            }
     368        } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     369            ov.insert(cast<Assign>(stmt)->getVariable());
    415370        }
    416371        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     
    418373            if (LLVM_UNLIKELY((isa<Statement>(op) || isa<Var>(op)) && ov.count(op) == 0)) {
    419374                std::string tmp;
    420                 raw_string_ostream str(tmp);
    421                 str << "PabloVerifier: ordering volation: ";
    422                 if (LLVM_UNLIKELY(recursivelyDefined(stmt))) {
    423                     PabloPrinter::print(stmt, str);
    424                     str << " is defined by a recursive function!";
    425                     throw std::runtime_error(str.str());
    426                 }
    427                 // TODO: make this actually test whether the operand is ever defined,
    428                 // or if it was defined in a scope that cannot be reached?
    429 
    430                 str << "function is not topologically ordered! ";
    431                 PabloAST * op = stmt->getOperand(i);
    432                 PabloPrinter::print(op, str);
    433                 if (LLVM_UNLIKELY(isa<Statement>(op) && unreachable(stmt, cast<Statement>(op)->getParent()))) {
    434                     str << " was defined in a scope that is unreachable by ";
     375                raw_string_ostream out(tmp);
     376                if (isa<Var>(op)) {
     377                    PabloPrinter::print(op, out);
     378                    out << " is used by ";
     379                    PabloPrinter::print(stmt, out);
     380                    out << " before being assigned a value.";
    435381                } else {
    436                     str << " was used before definition by ";
    437                 }
    438                 PabloPrinter::print(stmt, str);
    439                 throw std::runtime_error(str.str());
     382                    PabloPrinter::print(op, out);
     383                    if (LLVM_UNLIKELY(isa<Statement>(op) && unreachable(stmt, cast<Statement>(op)->getParent()))) {
     384                        out << " was defined in a scope that is unreachable by ";
     385                    } else {
     386                        out << " was used before definition by ";
     387                    }
     388                    PabloPrinter::print(stmt, out);
     389                }
     390                throw std::runtime_error(out.str());
    440391            }
    441392        }
     
    443394        if (LLVM_UNLIKELY(isa<If>(stmt))) {
    444395            isTopologicallyOrdered(cast<If>(stmt)->getBody(), ov);
    445             for (const Assign * def : cast<If>(stmt)->getDefined()) {
     396            for (const Var * def : cast<If>(stmt)->getEscaped()) {
    446397                ov.insert(def);
    447398            }
     
    454405    for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
    455406        ov.insert(function.getParameter(i));
     407    }
     408    for (unsigned i = 0; i != function.getNumOfResults(); ++i) {
     409        ov.insert(function.getResult(i));
    456410    }
    457411    isTopologicallyOrdered(function.getEntryBlock(), ov);
     
    468422        out.flush();
    469423        if (location.empty()) {
    470             throw err;
     424            llvm::report_fatal_error(err.what());
    471425        } else {
    472             throw std::runtime_error(std::string(err.what()) + " @ " + location);
    473         }
    474     }
    475 }
    476 
    477 }
     426            llvm::report_fatal_error(std::string(err.what()) + " @ " + location);
     427        }
     428    }
     429}
     430
     431}
  • icGREP/icgrep-devel/icgrep/pablo/builder.cpp

    r5081 r5202  
    11#include <pablo/builder.hpp>
     2// #include <boost/current_function.hpp> // BOOST_CURRENT_FUNCTION
    23
    34namespace pablo {
     
    89        return mPb->NAME(arg); \
    910    } \
    10     inline PabloAST * operator()(PabloAST * arg, const std::string & name) { \
    11         return mPb->NAME(arg, name); \
    12     } \
    1311    inline __##NAME(PabloBlock * pb) : mPb(pb) {} \
    1412private: \
     
    1816PabloAST * result = mExprTable.findUnaryOrCall(std::move(functor), TYPE, ARGS)
    1917
     18#define MAKE_NAMED_UNARY(NAME, TYPE, PREFIX, ARGS...) \
     19struct __##NAME { \
     20    inline PabloAST * operator()(PabloAST * arg) { \
     21        return mPb->NAME(arg, mPrefix); \
     22    } \
     23    inline __##NAME(PabloBlock * pb, const std::string & prefix) : mPb(pb), mPrefix(prefix) {} \
     24private: \
     25    PabloBlock * mPb; \
     26    const std::string & mPrefix; \
     27}; \
     28__##NAME functor(mPb, prefix); \
     29PabloAST * result = mExprTable.findUnaryOrCall(std::move(functor), TYPE, ARGS)
     30
    2031#define MAKE_BINARY(NAME, TYPE, ARGS...) \
    2132struct __##NAME { \
     
    2334        return mPb->NAME(arg1, arg2); \
    2435    } \
    25     inline PabloAST * operator()(PabloAST * arg1, PabloAST * arg2, const std::string & name) { \
    26         return mPb->NAME(arg1, arg2, name); \
    27     } \
    2836    inline __##NAME(PabloBlock * pb) : mPb(pb) {} \
    2937private: \
     
    3341PabloAST * result = mExprTable.findBinaryOrCall(std::move(functor), TYPE, ARGS)
    3442
     43#define MAKE_NAMED_BINARY(NAME, TYPE, PREFIX, ARGS...) \
     44struct __##NAME { \
     45    inline PabloAST * operator()(PabloAST * arg1, PabloAST * arg2) { \
     46        return mPb->NAME(arg1, arg2, mPrefix); \
     47    } \
     48    inline __##NAME(PabloBlock * pb, const std::string & prefix) : mPb(pb), mPrefix(prefix) {} \
     49private: \
     50    PabloBlock * mPb; \
     51    const std::string & mPrefix; \
     52}; \
     53__##NAME functor(mPb, PREFIX); \
     54PabloAST * result = mExprTable.findBinaryOrCall(std::move(functor), TYPE, ARGS)
    3555
    3656#define MAKE_TERNARY(NAME, TYPE, ARGS...) \
     
    3959        return mPb->NAME(arg1, arg2, arg3); \
    4060    } \
    41     inline PabloAST * operator()(PabloAST * arg1, PabloAST * arg2, PabloAST * arg3, const std::string & name) { \
    42         return mPb->NAME(arg1, arg2, arg3, name); \
    43     } \
    4461    inline __##NAME(PabloBlock * pb) : mPb(pb) {} \
    4562private: \
     
    4966PabloAST * result = mExprTable.findTernaryOrCall(std::move(functor), TYPE, ARGS)
    5067
     68#define MAKE_NAMED_TERNARY(NAME, TYPE, PREFIX, ARGS...) \
     69struct __##NAME { \
     70    inline PabloAST * operator()(PabloAST * arg1, PabloAST * arg2, PabloAST * arg3) { \
     71        return mPb->NAME(arg1, arg2, arg3, mPrefix); \
     72    } \
     73    inline __##NAME(PabloBlock * pb, const std::string & prefix) : mPb(pb), mPrefix(prefix) {} \
     74private: \
     75    PabloBlock * mPb; \
     76    const std::string & mPrefix; \
     77}; \
     78__##NAME functor(mPb, PREFIX); \
     79PabloAST * result = mExprTable.findTernaryOrCall(std::move(functor), TYPE, ARGS)
     80
    5181#define MAKE_VARIABLE(NAME, TYPE, ARGS...) \
    5282struct __##NAME { \
     
    5989}; \
    6090__##NAME functor(mPb); \
    61 PabloAST * result = mExprTable.findVariableOrCall(std::move(functor), TYPE, ARGS)
     91PabloAST * result = mExprTable.findVariadicOrCall(std::move(functor), TYPE, ARGS)
     92
     93template<typename Type>
     94static inline Type * isBinary(PabloAST * expr) {
     95    if (isa<Type>(expr) && cast<Type>(expr)->getNumOperands() == 2) {
     96        return cast<Type>(expr);
     97    }
     98    return nullptr;
     99}
     100
     101using TypeId = PabloAST::ClassTypeId;
    62102
    63103Call * PabloBuilder::createCall(Prototype * prototype, const std::vector<PabloAST *> & args) {
     
    68108        throw std::runtime_error("Invalid number of arguments passed into Call object!");
    69109    }
    70     MAKE_VARIABLE(createCall, PabloAST::ClassTypeId::Call, prototype->getName(), args, prototype);
     110    MAKE_VARIABLE(createCall, TypeId::Call, prototype->getName(), args, prototype);
    71111    return cast<Call>(result);
    72112}
    73113
    74114PabloAST * PabloBuilder::createAdvance(PabloAST * expr, PabloAST * shiftAmount) {
    75     MAKE_BINARY(createAdvance, PabloAST::ClassTypeId::Advance, expr, shiftAmount);
    76     return result;
    77 }
    78 
    79 PabloAST * PabloBuilder::createAdvance(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix) {
    80     MAKE_BINARY(createAdvance, PabloAST::ClassTypeId::Advance, expr, shiftAmount, prefix);
    81     return result;
     115    if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
     116        return expr;
     117    }
     118    MAKE_BINARY(createAdvance, TypeId::Advance, expr, shiftAmount);
     119    return result;
     120}
     121
     122PabloAST * PabloBuilder::createAdvance(PabloAST * expr, PabloAST * shiftAmount, const std::string & prefix) {
     123    if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
     124        return expr;
     125    }
     126    MAKE_NAMED_BINARY(createAdvance, TypeId::Advance, prefix, expr, shiftAmount);
     127    return result;
     128}
     129
     130Extract * PabloBuilder::createExtract(PabloAST * value, not_null<PabloAST *> index) {
     131    MAKE_BINARY(createExtract, TypeId::Extract, value, index);
     132    return cast<Extract>(result);
     133}
     134
     135Extract * PabloBuilder::createExtract(PabloAST * value, not_null<PabloAST *> index, const std::string & prefix) {
     136    MAKE_NAMED_BINARY(createExtract, TypeId::Extract, prefix, value, index);
     137    return cast<Extract>(result);
    82138}
    83139
    84140PabloAST * PabloBuilder::createLookahead(PabloAST * expr, PabloAST * shiftAmount) {
    85     MAKE_BINARY(createLookahead, PabloAST::ClassTypeId::Lookahead, expr, shiftAmount);
    86     return result;
    87 }
    88 
    89 PabloAST * PabloBuilder::createLookahead(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix) {
    90     MAKE_BINARY(createLookahead, PabloAST::ClassTypeId::Lookahead, expr, shiftAmount, prefix);
     141    if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
     142        return expr;
     143    }
     144    MAKE_BINARY(createLookahead, TypeId::Lookahead, expr, shiftAmount);
     145    return result;
     146}
     147
     148PabloAST * PabloBuilder::createLookahead(PabloAST * expr, PabloAST * shiftAmount, const std::string & prefix) {
     149    if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
     150        return expr;
     151    }
     152    MAKE_NAMED_BINARY(createLookahead, TypeId::Lookahead, prefix, expr, shiftAmount);
    91153    return result;
    92154}
    93155
    94156PabloAST * PabloBuilder::createNot(PabloAST * expr) {
    95     MAKE_UNARY(createNot, PabloAST::ClassTypeId::Not, expr);
    96     return result;
    97 }
    98 
    99 PabloAST * PabloBuilder::createNot(PabloAST * expr, const std::string prefix) {
    100     MAKE_UNARY(createNot, PabloAST::ClassTypeId::Not, expr, prefix);
     157    if (isa<Ones>(expr)) {
     158        return createZeroes(expr->getType());
     159    }
     160    else if (isa<Zeroes>(expr)){
     161        return createOnes(expr->getType());
     162    }
     163    else if (Not * not1 = dyn_cast<Not>(expr)) {
     164        return not1->getOperand(0);
     165    }
     166    MAKE_UNARY(createNot, TypeId::Not, expr);
     167    return result;
     168}
     169
     170PabloAST * PabloBuilder::createNot(PabloAST * expr, const std::string & prefix) {
     171    if (isa<Ones>(expr)) {
     172        return createZeroes(expr->getType());
     173    }
     174    else if (isa<Zeroes>(expr)){
     175        return createOnes(expr->getType());
     176    }
     177    else if (Not * not1 = dyn_cast<Not>(expr)) {
     178        return not1->getOperand(0);
     179    }
     180    MAKE_NAMED_UNARY(createNot, TypeId::Not, prefix, expr);
     181    return result;
     182}
     183
     184PabloAST * PabloBuilder::createCount(PabloAST * expr) {
     185    MAKE_UNARY(createCount, TypeId::Count, expr);
     186    return result;
     187}
     188
     189PabloAST * PabloBuilder::createCount(PabloAST * expr, const std::string & prefix) {
     190    MAKE_NAMED_UNARY(createCount, TypeId::Count, prefix, expr);
     191    return result;
     192}
     193
     194PabloAST * PabloBuilder::createAssign(PabloAST * const variable, PabloAST * const value) {
     195    MAKE_BINARY(createAssign, TypeId::Assign, variable, value);
    101196    return result;
    102197}
    103198
    104199PabloAST * PabloBuilder::createAnd(PabloAST * expr1, PabloAST * expr2) {
    105     assert (expr1);
    106     assert (expr2);
    107     if (isa<Not>(expr1) || expr1 > expr2) {
    108         std::swap(expr1, expr2);
    109     }
    110     MAKE_BINARY(createAnd, PabloAST::ClassTypeId::And, expr1, expr2);
    111     return result;
    112 }
    113 
    114 PabloAST * PabloBuilder::createAnd(PabloAST * expr1, PabloAST * expr2, const std::string prefix) {
    115     assert (expr1);
    116     assert (expr2);
    117     if (isa<Not>(expr1) || expr1 > expr2) {
    118         std::swap(expr1, expr2);
    119     }
    120     MAKE_BINARY(createAnd, PabloAST::ClassTypeId::And, expr1, expr2, prefix);
    121     return result;
    122 }
    123 
    124 PabloAST * PabloBuilder::createOr(PabloAST * expr1, PabloAST * expr2) {
    125     assert (expr1);
    126     assert (expr2);
     200    if (isa<Zeroes>(expr2) || isa<Ones>(expr1)) {
     201        return expr2;
     202    } else if (isa<Zeroes>(expr1) || isa<Ones>(expr2) || equals(expr1, expr2)){
     203        return expr1;
     204    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
     205        if (Not * not2 = dyn_cast<Not>(expr2)) {
     206            return createNot(createOr(not1->getOperand(0), not2->getOperand(0)));
     207        } else if (equals(not1->getOperand(0), expr2)) {
     208            return createZeroes(expr1->getType());
     209        }
     210    } else if (Not * not2 = dyn_cast<Not>(expr2)) {
     211        if (equals(expr1, not2->getOperand(0))) {
     212            return createZeroes(expr1->getType());
     213        }
     214    } else if (Or * or1 = isBinary<Or>(expr1)) {
     215        if (equals(or1->getOperand(0), expr2) || equals(or1->getOperand(1), expr2)) {
     216            return expr2;
     217        }
     218    } else if (Or * or2 = isBinary<Or>(expr2)) {
     219        if (equals(or2->getOperand(0), expr1) || equals(or2->getOperand(1), expr1)) {
     220            return expr1;
     221        }
     222    }
    127223    if (expr1 > expr2) {
    128224        std::swap(expr1, expr2);
    129225    }
    130     MAKE_BINARY(createOr, PabloAST::ClassTypeId::Or, expr1, expr2);
    131     return result;
    132 }
    133 
    134 PabloAST * PabloBuilder::createOr(PabloAST * expr1, PabloAST * expr2, const std::string prefix) {
    135     assert (expr1);
    136     assert (expr2);
     226    MAKE_BINARY(createAnd, TypeId::And, expr1, expr2);
     227    return result;
     228}
     229
     230PabloAST * PabloBuilder::createAnd(PabloAST * expr1, PabloAST * expr2, const std::string & prefix) {
     231    if (isa<Zeroes>(expr2) || isa<Ones>(expr1)) {
     232        return expr2;
     233    } else if (isa<Zeroes>(expr1) || isa<Ones>(expr2) || equals(expr1, expr2)){
     234        return expr1;
     235    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
     236        if (Not * not2 = dyn_cast<Not>(expr2)) {
     237            return createNot(createOr(not1->getOperand(0), not2->getOperand(0)), prefix);
     238        } else if (equals(not1->getOperand(0), expr2)) {
     239            return createZeroes(expr1->getType());
     240        }
     241    } else if (Not * not2 = dyn_cast<Not>(expr2)) {
     242        if (equals(expr1, not2->getOperand(0))) {
     243            return createZeroes(expr1->getType());
     244        }
     245    } else if (Or * or1 = isBinary<Or>(expr1)) {
     246        if (equals(or1->getOperand(0), expr2) || equals(or1->getOperand(1), expr2)) {
     247            return expr2;
     248        }
     249    } else if (Or * or2 = isBinary<Or>(expr2)) {
     250        if (equals(or2->getOperand(0), expr1) || equals(or2->getOperand(1), expr1)) {
     251            return expr1;
     252        }
     253    }
    137254    if (expr1 > expr2) {
    138255        std::swap(expr1, expr2);
    139256    }
    140     MAKE_BINARY(createOr, PabloAST::ClassTypeId::Or, expr1, expr2, prefix);
    141     return result;
    142 }
    143 
    144 PabloAST * PabloBuilder::createXor(PabloAST * expr1, PabloAST * expr2) {
    145     assert (expr1);
    146     assert (expr2);
     257    MAKE_NAMED_BINARY(createAnd, TypeId::And, prefix, expr1, expr2);
     258    return result;
     259}
     260
     261PabloAST * PabloBuilder::createOr(PabloAST * expr1, PabloAST * expr2) {
     262    if (isa<Zeroes>(expr1) || isa<Ones>(expr2)){
     263        return expr2;
     264    }
     265    if (isa<Zeroes>(expr2) || isa<Ones>(expr1) || equals(expr1, expr2)) {
     266        return expr1;
     267    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
     268        // ¬a√b = ¬¬(¬a √ b) = ¬(a ∧ ¬b)
     269        return createNot(createAnd(not1->getOperand(0), createNot(expr2)));
     270    } else if (Not * not2 = dyn_cast<Not>(expr2)) {
     271        // a√¬b = ¬¬(¬b √ a) = ¬(b ∧ ¬a)
     272        return createNot(createAnd(not2->getOperand(0), createNot(expr1)));
     273    } else if (equals(expr1, expr2)) {
     274        return expr1;
     275    } else if (And * and1 = isBinary<And>(expr1)) {
     276        PabloAST * const expr1a = and1->getOperand(0);
     277        PabloAST * const expr1b = and1->getOperand(1);
     278        if (And * and2 = isBinary<And>(expr2)) {
     279            PabloAST * const expr2a = and2->getOperand(0);
     280            PabloAST * const expr2b = and2->getOperand(1);
     281            //These optimizations factor out common components that can occur when sets are formed by union
     282            //(e.g., union of [a-z] and [A-Z].
     283            if (equals(expr1a, expr2a)) {
     284                return createAnd(expr1a, createOr(expr1b, expr2b));
     285            } else if (equals(expr1b, expr2b)) {
     286                return createAnd(expr1b, createOr(expr1a, expr2a));
     287            } else if (equals(expr1a, expr2b)) {
     288                return createAnd(expr1a, createOr(expr1b, expr2a));
     289            } else if (equals(expr1b, expr2a)) {
     290                return createAnd(expr1b, createOr(expr1a, expr2b));
     291            }
     292        } else if (equals(expr1a, expr2) || equals(expr1b, expr2)) {
     293            // (a ∧ b) √ a = a
     294            return expr2;
     295        }
     296    } else if (And * and2 = isBinary<And>(expr2)) {
     297        if (equals(and2->getOperand(0), expr1) || equals(and2->getOperand(1), expr1)) {
     298            return expr1;
     299        }
     300    }
    147301    if (expr1 > expr2) {
    148302        std::swap(expr1, expr2);
    149303    }
    150     MAKE_BINARY(createXor, PabloAST::ClassTypeId::Xor, expr1, expr2);
    151     return result;
    152 }
    153 
    154 PabloAST * PabloBuilder::createXor(PabloAST * expr1, PabloAST * expr2, const std::string prefix) {
    155     assert (expr1);
    156     assert (expr2);
     304    MAKE_BINARY(createOr, TypeId::Or, expr1, expr2);
     305    return result;
     306}
     307
     308PabloAST * PabloBuilder::createOr(PabloAST * expr1, PabloAST * expr2, const std::string & prefix) {
     309    if (isa<Zeroes>(expr1) || isa<Ones>(expr2)){
     310        return expr2;
     311    }
     312    if (isa<Zeroes>(expr2) || isa<Ones>(expr1) || equals(expr1, expr2)) {
     313        return expr1;
     314    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
     315        // ¬a√b = ¬¬(¬a √ b) = ¬(a ∧ ¬b)
     316        return createNot(createAnd(not1->getOperand(0), createNot(expr2)), prefix);
     317    } else if (Not * not2 = dyn_cast<Not>(expr2)) {
     318        // a√¬b = ¬¬(¬b √ a) = ¬(b ∧ ¬a)
     319        return createNot(createAnd(not2->getOperand(0), createNot(expr1)), prefix);
     320    } else if (equals(expr1, expr2)) {
     321        return expr1;
     322    } else if (And * and1 = isBinary<And>(expr1)) {
     323        PabloAST * const expr1a = and1->getOperand(0);
     324        PabloAST * const expr1b = and1->getOperand(1);
     325        if (And * and2 = isBinary<And>(expr2)) {
     326            PabloAST * const expr2a = and2->getOperand(0);
     327            PabloAST * const expr2b = and2->getOperand(1);
     328            //These optimizations factor out common components that can occur when sets are formed by union
     329            //(e.g., union of [a-z] and [A-Z].
     330            if (equals(expr1a, expr2a)) {
     331                return createAnd(expr1a, createOr(expr1b, expr2b), prefix);
     332            } else if (equals(expr1b, expr2b)) {
     333                return createAnd(expr1b, createOr(expr1a, expr2a), prefix);
     334            } else if (equals(expr1a, expr2b)) {
     335                return createAnd(expr1a, createOr(expr1b, expr2a), prefix);
     336            } else if (equals(expr1b, expr2a)) {
     337                return createAnd(expr1b, createOr(expr1a, expr2b), prefix);
     338            }
     339        } else if (equals(expr1a, expr2) || equals(expr1b, expr2)) {
     340            // (a ∧ b) √ a = a
     341            return expr2;
     342        }
     343    } else if (And * and2 = isBinary<And>(expr2)) {
     344        if (equals(and2->getOperand(0), expr1) || equals(and2->getOperand(1), expr1)) {
     345            return expr1;
     346        }
     347    }
    157348    if (expr1 > expr2) {
    158349        std::swap(expr1, expr2);
    159350    }
    160     MAKE_BINARY(createXor, PabloAST::ClassTypeId::Xor, expr1, expr2, prefix);
     351    MAKE_NAMED_BINARY(createOr, TypeId::Or, prefix, expr1, expr2);
     352    return result;
     353}
     354
     355PabloAST * PabloBuilder::createXor(PabloAST * expr1, PabloAST * expr2) {
     356    if (expr1 == expr2) {
     357        return createZeroes(expr1->getType());
     358    } else if (isa<Ones>(expr1)) {
     359        return createNot(expr2);
     360    } else if (isa<Zeroes>(expr1)){
     361        return expr2;
     362    } else if (isa<Ones>(expr2)) {
     363        return createNot(expr1);
     364    } else if (isa<Zeroes>(expr2)){
     365        return expr1;
     366    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
     367        if (Not * not2 = dyn_cast<Not>(expr2)) {
     368            return createXor(not1->getOperand(0), not2->getOperand(0));
     369        }
     370    }
     371    if (expr1 > expr2) {
     372        std::swap(expr1, expr2);
     373    }
     374    MAKE_BINARY(createXor, TypeId::Xor, expr1, expr2);
     375    return result;
     376}
     377
     378PabloAST * PabloBuilder::createXor(PabloAST * expr1, PabloAST * expr2, const std::string & prefix) {
     379    if (expr1 == expr2) {
     380        return createZeroes(expr1->getType());
     381    } else if (isa<Ones>(expr1)) {
     382        return createNot(expr2);
     383    } else if (isa<Zeroes>(expr1)){
     384        return expr2;
     385    } else if (isa<Ones>(expr2)) {
     386        return createNot(expr1);
     387    } else if (isa<Zeroes>(expr2)){
     388        return expr1;
     389    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
     390        if (Not * not2 = dyn_cast<Not>(expr2)) {
     391            return createXor(not1->getOperand(0), not2->getOperand(0), prefix);
     392        }
     393    }
     394    if (expr1 > expr2) {
     395        std::swap(expr1, expr2);
     396    }
     397    MAKE_NAMED_BINARY(createXor, TypeId::Xor, prefix, expr1, expr2);
    161398    return result;
    162399}
    163400
    164401PabloAST * PabloBuilder::createInFile(PabloAST * expr) {
    165     MAKE_UNARY(createInFile, PabloAST::ClassTypeId::InFile, expr);
    166     return result;
    167 }
    168 
    169 PabloAST * PabloBuilder::createInFile(PabloAST * expr, const std::string prefix) {
    170     MAKE_UNARY(createInFile, PabloAST::ClassTypeId::InFile, expr, prefix);
     402    MAKE_UNARY(createInFile, TypeId::InFile, expr);
     403    return result;
     404}
     405
     406PabloAST * PabloBuilder::createInFile(PabloAST * expr, const std::string & prefix) {
     407    MAKE_NAMED_UNARY(createInFile, TypeId::InFile, prefix, expr);
    171408    return result;
    172409}
    173410
    174411PabloAST * PabloBuilder::createAtEOF(PabloAST * expr) {
    175     MAKE_UNARY(createAtEOF, PabloAST::ClassTypeId::AtEOF, expr);
    176     return result;
    177 }
    178 
    179 PabloAST * PabloBuilder::createAtEOF(PabloAST * expr, const std::string prefix) {
    180     MAKE_UNARY(createAtEOF, PabloAST::ClassTypeId::AtEOF, expr, prefix);
     412    MAKE_UNARY(createAtEOF, TypeId::AtEOF, expr);
     413    return result;
     414}
     415
     416PabloAST * PabloBuilder::createAtEOF(PabloAST * expr, const std::string & prefix) {
     417    MAKE_NAMED_UNARY(createAtEOF, TypeId::AtEOF, prefix, expr);
    181418    return result;
    182419}
    183420
    184421PabloAST * PabloBuilder::createMatchStar(PabloAST * marker, PabloAST * charclass) {
    185 MAKE_BINARY(createMatchStar, PabloAST::ClassTypeId::MatchStar, marker, charclass);
    186 return result;
    187 }
    188 
    189 PabloAST * PabloBuilder::createMatchStar(PabloAST * marker, PabloAST * charclass, const std::string prefix) {
    190     MAKE_BINARY(createMatchStar, PabloAST::ClassTypeId::MatchStar, marker, charclass, prefix);
     422    if (isa<Zeroes>(marker) || isa<Zeroes>(charclass)) {
     423        return marker;
     424    }
     425    MAKE_BINARY(createMatchStar, TypeId::MatchStar, marker, charclass);
     426    return result;
     427}
     428
     429PabloAST * PabloBuilder::createMatchStar(PabloAST * marker, PabloAST * charclass, const std::string & prefix) {
     430    if (isa<Zeroes>(marker) || isa<Zeroes>(charclass)) {
     431        return marker;
     432    }
     433    MAKE_NAMED_BINARY(createMatchStar, TypeId::MatchStar, prefix, marker, charclass);
    191434    return result;
    192435}
    193436
    194437PabloAST * PabloBuilder::createScanThru(PabloAST * from, PabloAST * thru) {
    195     MAKE_BINARY(createScanThru, PabloAST::ClassTypeId::ScanThru, from, thru);
    196     return result;
    197 }
    198 
    199 PabloAST * PabloBuilder::createScanThru(PabloAST * from, PabloAST * thru, const std::string prefix) {
    200     MAKE_BINARY(createScanThru, PabloAST::ClassTypeId::ScanThru, from, thru, prefix);
     438    if (isa<Zeroes>(from) || isa<Zeroes>(thru)) {
     439        return from;
     440    }
     441    MAKE_BINARY(createScanThru, TypeId::ScanThru, from, thru);
     442    return result;
     443}
     444
     445PabloAST * PabloBuilder::createScanThru(PabloAST * from, PabloAST * thru, const std::string & prefix) {
     446    if (isa<Zeroes>(from) || isa<Zeroes>(thru)) {
     447        return from;
     448    }
     449    MAKE_NAMED_BINARY(createScanThru, TypeId::ScanThru, prefix, from, thru);
    201450    return result;
    202451}
     
    204453
    205454PabloAST * PabloBuilder::createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr) {
    206     MAKE_TERNARY(createSel, PabloAST::ClassTypeId::Sel, condition, trueExpr, falseExpr);
    207     return result;
    208 }
    209 
    210 PabloAST * PabloBuilder::createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr, const std::string prefix) {
    211     MAKE_TERNARY(createSel, PabloAST::ClassTypeId::Sel, condition, trueExpr, falseExpr, prefix);
    212     return result;
    213 }
    214 
    215 }
     455    if (isa<Ones>(condition)) {
     456        return trueExpr;
     457    } else if (isa<Zeroes>(condition)){
     458        return falseExpr;
     459    } else if (isa<Ones>(trueExpr)) {
     460        return createOr(condition, falseExpr);
     461    } else if (isa<Zeroes>(trueExpr)){
     462        return createAnd(createNot(condition), falseExpr);
     463    } else if (isa<Ones>(falseExpr)) {
     464        return createOr(createNot(condition), trueExpr);
     465    } else if (isa<Zeroes>(falseExpr)){
     466        return createAnd(condition, trueExpr);
     467    } else if (equals(trueExpr, falseExpr)) {
     468        return trueExpr;
     469    } else if (isa<Not>(trueExpr) && equals(cast<Not>(trueExpr)->getOperand(0), falseExpr)) {
     470        return createXor(condition, falseExpr);
     471    } else if (isa<Not>(falseExpr) && equals(trueExpr, cast<Not>(falseExpr)->getOperand(0))){
     472        return createXor(condition, trueExpr);
     473    }
     474    MAKE_TERNARY(createSel, TypeId::Sel, condition, trueExpr, falseExpr);
     475    return result;
     476}
     477
     478PabloAST * PabloBuilder::createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr, const std::string & prefix) {
     479    if (isa<Ones>(condition)) {
     480        return trueExpr;
     481    } else if (isa<Zeroes>(condition)){
     482        return falseExpr;
     483    } else if (isa<Ones>(trueExpr)) {
     484        return createOr(condition, falseExpr);
     485    } else if (isa<Zeroes>(trueExpr)){
     486        return createAnd(createNot(condition), falseExpr);
     487    } else if (isa<Ones>(falseExpr)) {
     488        return createOr(createNot(condition), trueExpr);
     489    } else if (isa<Zeroes>(falseExpr)){
     490        return createAnd(condition, trueExpr);
     491    } else if (equals(trueExpr, falseExpr)) {
     492        return trueExpr;
     493    } else if (isa<Not>(trueExpr) && equals(cast<Not>(trueExpr)->getOperand(0), falseExpr)) {
     494        return createXor(condition, falseExpr);
     495    } else if (isa<Not>(falseExpr) && equals(trueExpr, cast<Not>(falseExpr)->getOperand(0))){
     496        return createXor(condition, trueExpr);
     497    }
     498    MAKE_NAMED_TERNARY(createSel, TypeId::Sel, prefix, condition, trueExpr, falseExpr);
     499    return result;
     500}
     501
     502}
  • icGREP/icgrep-devel/icgrep/pablo/builder.hpp

    r5160 r5202  
    1010public:
    1111
    12     explicit PabloBuilder(PabloBlock * block) : mPb(block), mParent(nullptr), mExprTable(nullptr) {}
    13 
    14     explicit PabloBuilder(PabloBlock * block, PabloBuilder & parent) : mPb(block), mParent(&parent), mExprTable(&(parent.mExprTable)) {}
    15 
    16     PabloBuilder(PabloBuilder && builder) : mPb(builder.mPb), mParent(builder.mParent), mExprTable(std::move(builder.mExprTable)) {}
     12    template<typename T>
     13    struct not_null {
     14        inline not_null(T const value) : _value(value) { assert(_value); }
     15        inline not_null(std::nullptr_t) = delete;
     16        inline not_null(unsigned) = delete;
     17        operator T() const { return _value; }
     18        T operator-> () const { return _value; }
     19        T get() const { return _value; }
     20    private:
     21        T const  _value;
     22    };
     23
     24    explicit PabloBuilder(PabloBlock * block)
     25    : mPb(block), mParent(nullptr), mExprTable(nullptr) {
     26
     27    }
    1728
    1829    PabloBuilder & operator=(PabloBuilder) = delete;
    1930
    2031    PabloBuilder & operator=(PabloBuilder &) = delete;
     32
     33    PabloBuilder(PabloBuilder && builder)
     34    : mPb(builder.mPb)
     35    , mParent(builder.mParent)
     36    , mExprTable(std::move(builder.mExprTable)) {
     37
     38    }
    2139
    2240    PabloBuilder & operator=(PabloBuilder && builder) {
     
    3957    }
    4058
    41     inline Zeroes * createZeroes(const PabloType * const type = nullptr) {
     59    inline Zeroes * createZeroes(Type * const type = nullptr) {
    4260        return mPb->createZeroes(type);
    4361    }
    4462
    45     inline Ones * createOnes(const PabloType * const type = nullptr) {
     63    inline Ones * createOnes(Type * const type = nullptr) {
    4664        return mPb->createOnes(type);
    4765    }
    4866
    49     inline Var * createVar(const std::string name, const PabloType * const type) {
     67    inline Var * createVar(const std::string name, Type * const type = nullptr) {
     68        return createVar(makeName(name), type);
     69    }
     70
     71    inline Var * createVar(const std::string name, PabloAST * value) {
     72        Var * var = createVar(name, value->getType());
     73        createAssign(var, value);
     74        return var;
     75    }
     76
     77    inline Var * createVar(String * const name, Type * const type = nullptr) {
    5078        return mPb->createVar(name, type);
    5179    }
    5280
    53     inline Var * createVar(String * const name, const PabloType * const type) {
    54         return mPb->createVar(name, type);
    55     }
    56 
    57     inline Var * createVar(PabloAST * const name, const PabloType * const type) {
    58         return mPb->createVar(name, type);
     81    Extract * createExtract(PabloAST * value, not_null<PabloAST *> index);
     82
     83    inline Extract * createExtract(PabloAST * value, const Integer::Type index) {
     84        return createExtract(value, getInteger(index));
     85    }
     86
     87    Extract * createExtract(PabloAST * value, not_null<PabloAST *> index, const std::string & prefix);
     88
     89    inline Extract * createExtract(PabloAST * value, const Integer::Type index, const std::string & prefix) {
     90        return createExtract(value, getInteger(index), prefix);
    5991    }
    6092
     
    6597    Call * createCall(Prototype * prototype, const std::vector<PabloAST *> &vars);
    6698
    67     Assign * createAssign(const std::string && prefix, PabloAST * expr) {
    68         return mPb->createAssign(std::move(prefix), expr);
    69     }
    70 
    7199    inline PabloAST * createAdvance(PabloAST * expr, const Integer::Type shiftAmount) {
    72         if (shiftAmount == 0) {
    73             return expr;
    74         }
    75100        return createAdvance(expr, mPb->getInteger(shiftAmount));
    76101    }
     
    78103    PabloAST * createAdvance(PabloAST * expr, PabloAST * shiftAmount);
    79104
    80     inline PabloAST * createAdvance(PabloAST * expr, const Integer::Type shiftAmount, const std::string prefix) {
    81         if (shiftAmount == 0) {
    82             return expr;
    83         }
     105    inline PabloAST * createAdvance(PabloAST * expr, const Integer::Type shiftAmount, const std::string & prefix) {
    84106        return createAdvance(expr, mPb->getInteger(shiftAmount), prefix);
    85107    }
    86108
    87     PabloAST * createAdvance(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix);
     109    PabloAST * createAdvance(PabloAST * expr, PabloAST * shiftAmount, const std::string & prefix);
    88110
    89111    inline PabloAST * createLookahead(PabloAST * expr, const Integer::Type shiftAmount) {
     
    96118    PabloAST * createLookahead(PabloAST * expr, PabloAST * shiftAmount);
    97119
    98     inline PabloAST * createLookahead(PabloAST * expr, const Integer::Type shiftAmount, const std::string prefix) {
     120    inline PabloAST * createLookahead(PabloAST * expr, const Integer::Type shiftAmount, const std::string & prefix) {
    99121        if (shiftAmount == 0) {
    100122            return expr;
     
    103125    }
    104126
    105     PabloAST * createLookahead(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix);
    106 
    107     inline Next * createNext(Assign * assign, PabloAST * expr) {
    108         return mPb->createNext(assign, expr);
    109     }
     127    PabloAST * createLookahead(PabloAST * expr, PabloAST * shiftAmount, const std::string & prefix);
     128
     129    PabloAST * createAssign(PabloAST * const variable, PabloAST * const value);
    110130
    111131    PabloAST * createAnd(PabloAST * expr1, PabloAST * expr2);
    112132
    113     PabloAST * createAnd(PabloAST * expr1, PabloAST * expr2, const std::string prefix);
     133    PabloAST * createAnd(PabloAST * expr1, PabloAST * expr2, const std::string & prefix);
    114134
    115135    PabloAST * createNot(PabloAST * expr);
    116136
    117     PabloAST * createNot(PabloAST * expr, const std::string prefix);
     137    PabloAST * createNot(PabloAST * expr, const std::string & prefix);
    118138
    119139    PabloAST * createOr(PabloAST * expr1, PabloAST * expr2);
    120140
    121     PabloAST * createOr(PabloAST * expr1, PabloAST * expr2, const std::string prefix);
     141    PabloAST * createOr(PabloAST * expr1, PabloAST * expr2, const std::string & prefix);
    122142
    123143    PabloAST * createXor(PabloAST * expr1, PabloAST * expr2);
    124144
    125     PabloAST * createXor(PabloAST * expr1, PabloAST * expr2, const std::string prefix);
     145    PabloAST * createXor(PabloAST * expr1, PabloAST * expr2, const std::string & prefix);
    126146
    127147    PabloAST * createMatchStar(PabloAST * marker, PabloAST * charclass);
    128148
    129     PabloAST * createMatchStar(PabloAST * marker, PabloAST * charclass, const std::string prefix);
     149    PabloAST * createMatchStar(PabloAST * marker, PabloAST * charclass, const std::string & prefix);
    130150
    131151    PabloAST * createScanThru(PabloAST * from, PabloAST * thru);
    132152
    133     PabloAST * createScanThru(PabloAST * from, PabloAST * thru, const std::string prefix);
     153    PabloAST * createScanThru(PabloAST * from, PabloAST * thru, const std::string & prefix);
    134154
    135155    PabloAST * createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr);
    136156
    137     PabloAST * createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr, const std::string prefix);
    138    
    139     Count * createCount(const std::string counter, PabloAST * expr) {
    140         return mPb->createCount(counter, expr);
    141     }
    142    
     157    PabloAST * createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr, const std::string & prefix);
     158
     159    PabloAST * createCount(PabloAST * expr);
     160   
     161    PabloAST * createCount(PabloAST * expr, const std::string & prefix);
     162
    143163    PabloAST * createInFile(PabloAST * expr);
    144164   
    145     PabloAST * createInFile(PabloAST * expr, const std::string prefix);
     165    PabloAST * createInFile(PabloAST * expr, const std::string & prefix);
    146166   
    147167    PabloAST * createAtEOF(PabloAST * expr);
    148168   
    149     PabloAST * createAtEOF(PabloAST * expr, const std::string prefix);
    150    
    151     /// CreateIf Wrappers
    152 
    153     inline If * createIf(PabloAST * condition, std::initializer_list<Assign *> definedVars, PabloBlock * body) {
    154         return mPb->createIf(condition, std::move(definedVars), body);
    155     }
    156 
    157     inline If * createIf(PabloAST * condition, const std::vector<Assign *> & definedVars, PabloBlock * body) {
    158         return mPb->createIf(condition, definedVars, body);
    159     }
    160 
    161     inline If * createIf(PabloAST * condition, std::vector<Assign *> && definedVars, PabloBlock * body) {
    162         return mPb->createIf(condition, std::move(definedVars), body);
    163     }
    164 
    165     inline If * createIf(PabloAST * condition, std::initializer_list<Assign *> definedVars, PabloBuilder & builder) {
    166         return mPb->createIf(condition, std::move(definedVars), builder.mPb);
    167     }
    168 
    169     inline If * createIf(PabloAST * condition, const std::vector<Assign *> & definedVars, PabloBuilder & builder) {
    170         return mPb->createIf(condition, definedVars, builder.mPb);
    171     }
    172 
    173     inline If * createIf(PabloAST * condition, std::vector<Assign *> && definedVars, PabloBuilder & builder) {
    174         return mPb->createIf(condition, std::move(definedVars), builder.mPb);
    175     }
    176 
    177     /// CreateWhile Wrappers
    178 
    179     inline While * createWhile(PabloAST * condition, const std::initializer_list<Next *> nextVars, PabloBlock * body) {
    180         return mPb->createWhile(condition, nextVars, body);
    181     }
    182 
    183     inline While * createWhile(PabloAST * condition, const std::vector<Next *> & nextVars, PabloBlock * body) {
    184         return mPb->createWhile(condition, nextVars, body);
    185     }
    186 
    187     inline While * createWhile(PabloAST * condition, std::vector<Next *> && nextVars, PabloBlock * body) {
    188         return mPb->createWhile(condition, std::move(nextVars), body);
    189     }
    190 
    191     inline While * createWhile(PabloAST * condition, const std::initializer_list<Next *> nextVars, PabloBuilder & builder) {
    192         return mPb->createWhile(condition, std::move(nextVars), builder.mPb);
    193     }
    194 
    195     inline While * createWhile(PabloAST * condition, const std::vector<Next *> & nextVars, PabloBuilder & builder) {
    196         return mPb->createWhile(condition, nextVars, builder.mPb);
    197     }
    198 
    199     inline While * createWhile(PabloAST * condition, std::vector<Next *> && nextVars, PabloBuilder & builder) {
    200         return mPb->createWhile(condition, std::move(nextVars), builder.mPb);
     169    PabloAST * createAtEOF(PabloAST * expr, const std::string & prefix);
     170   
     171    inline If * createIf(PabloAST * condition, PabloBlock * body) {
     172        return mPb->createIf(condition, body);
     173    }
     174
     175    inline If * createIf(PabloAST * condition, PabloBuilder & builder) {
     176        return mPb->createIf(condition, builder.mPb);
     177    }
     178
     179    inline While * createWhile(PabloAST * condition, PabloBlock * body) {
     180        return mPb->createWhile(condition, body);
     181    }
     182
     183    inline While * createWhile(PabloAST * condition, PabloBuilder & builder) {
     184        return mPb->createWhile(condition, builder.mPb);
    201185    }
    202186
     
    235219    }
    236220
    237     inline String * getName(const std::string name, const bool generated = true) const {
    238         return mPb->getName(std::move(name), generated);
    239     }
    240 
    241     inline String * makeName(const std::string prefix, const bool generated = true) const {
    242         return mPb->makeName(std::move(prefix), generated);
    243     }
    244 
    245     inline Integer * getInteger(Integer::Type value) {
    246         return mPb->getInteger(value);
    247     }
    248 
    249 
    250221    inline Statement * getInsertPoint() const {
    251222        return mPb->getInsertPoint();
    252223    }
    253224
    254     inline PabloBlock * getPabloBlock() {
     225    inline PabloBlock * getPabloBlock() const {
    255226        return mPb;
    256227    }
    257228
    258     inline PabloBuilder * getParent() {
     229    inline PabloBuilder * getParent() const {
    259230        return mParent;
    260231    }
    261232
    262     inline void record(Statement * stmt) {
    263         mExprTable.findOrAdd(stmt);
     233    inline String * getName(const std::string name) const {
     234        return mPb->getName(name);
     235    }
     236
     237    inline String * makeName(const std::string & prefix) const {
     238        return mPb->makeName(prefix);
     239    }
     240
     241    inline Integer * getInteger(Integer::Type value) const {
     242        return mPb->getInteger(value);
     243    }
     244
     245    inline SymbolGenerator * getSymbolTable() const {
     246        return mPb->getSymbolTable();
     247    }
     248
     249protected:
     250
     251    explicit PabloBuilder(PabloBlock * block, PabloBuilder & parent)
     252    : mPb(block), mParent(&parent), mExprTable(&(parent.mExprTable)) {
     253
    264254    }
    265255
  • icGREP/icgrep-devel/icgrep/pablo/carry_manager.cpp

    r5160 r5202  
    8181    assert (mCurrentScope != mRootScope);
    8282    mCurrentFrameIndex -= mCarryInfo->getFrameIndex();
    83     mCurrentScope = mCurrentScope->getPredecessor ();
     83    mCurrentScope = mCurrentScope->getPredecessor();
    8484    mCarryInfo = mCarryInfoVector[mCurrentScope->getScopeIndex()];
    8585    assert(summaryPack() < mCarryOutPack.size());
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.cpp

    r5160 r5202  
    66
    77#include <pablo/codegenstate.h>
    8 #include <iostream>
    98#include <pablo/printer_pablos.h>
    109
    1110namespace pablo {
    1211
    13 inline PabloAST * PabloBlock::renameNonNamedNode(PabloAST * expr, const std::string && prefix) {
    14     if (Statement * stmt = dyn_cast<Statement>(expr)) {
    15         if (stmt->getName()->isGenerated()) {
    16             stmt->setName(makeName(prefix, false));
    17         }
    18     }
    19     return expr;
    20 }
    21 
     12/// UNARY CREATE FUNCTIONS
     13///
     14
     15Call * PabloBlock::createCall(PabloAST * prototype, const std::vector<PabloAST *> &) {
     16    assert (prototype);
     17    return insertAtInsertionPoint(new Call(prototype));
     18}
     19
     20Count * PabloBlock::createCount(PabloAST * expr) {
     21    return insertAtInsertionPoint(new Count(expr, makeName("count")));
     22}
     23
     24Count * PabloBlock::createCount(PabloAST * const expr, const std::string & prefix)  {
     25    return insertAtInsertionPoint(new Count(expr, makeName(prefix)));
     26}
     27
     28Not * PabloBlock::createNot(PabloAST * expr, String * name) {
     29    assert (expr);
     30    if (name == nullptr) {
     31        name = makeName("not");
     32    }
     33    return insertAtInsertionPoint(new Not(expr, name));
     34}
     35
     36Var * PabloBlock::createVar(PabloAST * name, Type * type) {
     37    if (type == nullptr) {
     38        type = getStreamTy();
     39    }
     40    if (LLVM_UNLIKELY(name == nullptr || !isa<String>(name))) {
     41        throw std::runtime_error("Var objects must have a String name");
     42    }
     43    return mParent->makeVariable(name, type);
     44}
     45
     46InFile * PabloBlock::createInFile(PabloAST * expr, String * name) {
     47    assert (expr);
     48    if (name == nullptr) {
     49        name = makeName("inFile");
     50    }
     51    return insertAtInsertionPoint(new InFile(expr, name));
     52}
     53
     54AtEOF * PabloBlock::createAtEOF(PabloAST * expr, String * name) {
     55    assert (expr);
     56    if (name == nullptr) {
     57        name = makeName("atEOF");
     58    }
     59    return insertAtInsertionPoint(new AtEOF(expr, name));
     60}
     61   
     62   
     63/// BINARY CREATE FUNCTIONS
     64
     65Advance * PabloBlock::createAdvance(PabloAST * expr, PabloAST * shiftAmount, String * name) {
     66    if (name == nullptr) {
     67        name = makeName("advance");
     68    }
     69    return insertAtInsertionPoint(new Advance(expr, shiftAmount, name));
     70}
     71
     72Lookahead * PabloBlock::createLookahead(PabloAST * expr, PabloAST * shiftAmount, String * name) {
     73    if (name == nullptr) {
     74        name = makeName("lookahead");
     75    }
     76    return insertAtInsertionPoint(new Lookahead(expr, shiftAmount, name));
     77}
     78
     79Extract * PabloBlock::createExtract(PabloAST * array, PabloAST * index, String * name) {
     80    assert (array && index);
     81    if (LLVM_LIKELY(isa<ArrayType>(array->getType()))) {
     82        if (name == nullptr) {
     83            std::string tmp;
     84            raw_string_ostream out(tmp);
     85            PabloPrinter::print(array, out);
     86            PabloPrinter::print(index, out);
     87            name = makeName(out.str());
     88        }
     89        return insertAtInsertionPoint(new Extract(array, index, name));
     90    }
     91    std::string tmp;
     92    raw_string_ostream out(tmp);
     93    out << "cannot extract element from ";
     94    array->print(out);
     95    out << ": type is not a valid ArrayType";
     96    throw std::runtime_error(out.str());
     97}
     98
     99And * PabloBlock::createAnd(PabloAST * expr1, PabloAST * expr2, String * name) {
     100    if (name == nullptr) {
     101        name = makeName("and");
     102    }
     103    return insertAtInsertionPoint(new And(expr1->getType(), expr1, expr2, name));
     104}
     105
     106And * PabloBlock::createAnd(Type * const type, const unsigned reserved, String * name) {
     107    if (name == nullptr) {
     108        name = makeName("and");
     109    }
     110    return insertAtInsertionPoint(new And(type, reserved, name));
     111}
     112
     113Or * PabloBlock::createOr(PabloAST * expr1, PabloAST * expr2, String * name) {
     114    if (name == nullptr) {
     115        name = makeName("or");
     116    }
     117    return insertAtInsertionPoint(new Or(expr1->getType(), expr1, expr2, name));
     118}
     119
     120Or * PabloBlock::createOr(Type * const type, const unsigned reserved, String * name) {
     121    if (name == nullptr) {
     122        name = makeName("or");
     123    }
     124    return insertAtInsertionPoint(new Or(type, reserved, name));
     125}
     126
     127Xor * PabloBlock::createXor(PabloAST * expr1, PabloAST * expr2, String * name) {
     128    if (name == nullptr) {
     129        name = makeName("xor");
     130    }
     131    return insertAtInsertionPoint(new Xor(expr1->getType(), expr1, expr2, name));
     132}
     133
     134Xor * PabloBlock::createXor(Type * const type, const unsigned reserved, String * name) {
     135    if (name == nullptr) {
     136        name = makeName("xor");
     137    }
     138    return insertAtInsertionPoint(new Xor(type, reserved, name));
     139}
     140
     141Assign * PabloBlock::createAssign(PabloAST * const var, PabloAST * const value) {
     142    return insertAtInsertionPoint(new Assign(var, value));
     143}
     144
     145MatchStar * PabloBlock::createMatchStar(PabloAST * marker, PabloAST * charclass, String * name) {
     146    if (name == nullptr) {
     147        name = makeName("matchstar");
     148    }
     149    return insertAtInsertionPoint(new MatchStar(marker, charclass, name));
     150}
     151
     152ScanThru * PabloBlock::createScanThru(PabloAST * from, PabloAST * thru, String * name) {
     153    if (name == nullptr) {
     154        name = makeName("scanthru");
     155    }
     156    return insertAtInsertionPoint(new ScanThru(from, thru, name));
     157}
     158
     159If * PabloBlock::createIf(PabloAST * condition, PabloBlock * body) {
     160    assert (condition);
     161    If * const node = insertAtInsertionPoint(new If(condition, body));
     162    body->setBranch(node);
     163    return node;
     164}
     165
     166While * PabloBlock::createWhile(PabloAST * condition, PabloBlock * body) {
     167    assert (condition);
     168    While * const node = insertAtInsertionPoint(new While(condition, body));
     169    body->setBranch(node);
     170    return node;
     171}
     172
     173/// TERNARY CREATE FUNCTION
     174
     175Sel * PabloBlock::createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr, String * name) {
     176    if (name == nullptr) {
     177        name = makeName("sel");
     178    }
     179    return insertAtInsertionPoint(new Sel(condition, trueExpr, falseExpr, name));
     180}
     181
     182/** ------------------------------------------------------------------------------------------------------------- *
     183 * @brief insert
     184 ** ------------------------------------------------------------------------------------------------------------- */
    22185void PabloBlock::insert(Statement * const statement) {
    23186    assert (statement);
     
    38201}
    39202
    40 /// UNARY CREATE FUNCTIONS
    41 
    42 Assign * PabloBlock::createAssign(const std::string && prefix, PabloAST * const expr)  {
    43     assert ("Assign expression cannot be null!" && expr);
    44     return insertAtInsertionPoint(new Assign(expr, makeName(prefix, false)));
    45 }
    46 
    47 PabloAST * PabloBlock::createAdvance(PabloAST * expr, PabloAST * shiftAmount) {
    48     PabloAST::throwIfNonMatchingType(expr, PabloType::Stream);
    49     if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
    50         return expr;
    51     }
    52     return insertAtInsertionPoint(new Advance(expr, shiftAmount, makeName("advance")));
    53 }
    54 
    55 PabloAST * PabloBlock::createAdvance(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix) {
    56     PabloAST::throwIfNonMatchingType(expr, PabloType::Stream);
    57     if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
    58         return expr;
    59     }
    60     return insertAtInsertionPoint(new Advance(expr, shiftAmount, makeName(prefix, false)));
    61 }
    62 
    63 PabloAST * PabloBlock::createAdvance(PabloAST * expr, const Integer::Type shiftAmount) {
    64     PabloAST::throwIfNonMatchingType(expr, PabloType::Stream);
    65     if (isa<Zeroes>(expr) || shiftAmount == 0) {
    66         return expr;
    67     }
    68     return insertAtInsertionPoint(new Advance(expr, getInteger(shiftAmount), makeName("advance")));
    69 }
    70 
    71 PabloAST * PabloBlock::createAdvance(PabloAST * expr, const Integer::Type shiftAmount, const std::string prefix) {
    72     PabloAST::throwIfNonMatchingType(expr, PabloType::Stream);
    73     if (isa<Zeroes>(expr) || shiftAmount == 0) {
    74         return renameNonNamedNode(expr, std::move(prefix));
    75     }
    76     return insertAtInsertionPoint(new Advance(expr, getInteger(shiftAmount), makeName(prefix, false)));
    77 }
    78 
    79 Count * PabloBlock::createCount(const std::string counterName, PabloAST * const expr)  {
    80     PabloAST::throwIfNonMatchingType(expr, PabloType::Stream);
    81     return insertAtInsertionPoint(new Count(expr, makeName(counterName, false)));
    82 }
    83    
    84 
    85 PabloAST * PabloBlock::createLookahead(PabloAST * expr, PabloAST * shiftAmount) {
    86     if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
    87         return expr;
    88     }
    89     return insertAtInsertionPoint(new Lookahead(expr, shiftAmount, makeName("lookahead")));
    90 }
    91 
    92 PabloAST * PabloBlock::createLookahead(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix) {
    93     PabloAST::throwIfNonMatchingType(expr, PabloType::Stream);
    94     if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
    95         return expr;
    96     }
    97     return insertAtInsertionPoint(new Lookahead(expr, shiftAmount, makeName(prefix, false)));
    98 }
    99 
    100 PabloAST * PabloBlock::createLookahead(PabloAST * expr, const Integer::Type shiftAmount) {
    101     PabloAST::throwIfNonMatchingType(expr, PabloType::Stream);
    102     if (isa<Zeroes>(expr) || shiftAmount == 0) {
    103         return expr;
    104     }
    105     return insertAtInsertionPoint(new Lookahead(expr, getInteger(shiftAmount), makeName("lookahead")));
    106 }
    107 
    108 PabloAST * PabloBlock::createLookahead(PabloAST * expr, const Integer::Type shiftAmount, const std::string prefix) {
    109     PabloAST::throwIfNonMatchingType(expr, PabloType::Stream);
    110     if (isa<Zeroes>(expr) || shiftAmount == 0) {
    111         return renameNonNamedNode(expr, std::move(prefix));
    112     }
    113     return insertAtInsertionPoint(new Lookahead(expr, getInteger(shiftAmount), makeName(prefix, false)));
    114 }
    115 
    116 Call * PabloBlock::createCall(PabloAST * prototype, const std::vector<PabloAST *> &) {
    117     assert (prototype);
    118     return insertAtInsertionPoint(new Call(prototype));
    119 }
    120 
    121 
    122 PabloAST * PabloBlock::createNot(PabloAST * expr) {
    123     assert (expr);
    124     PabloAST::throwIfNonMatchingType(expr, PabloType::Stream);
    125     if (isa<Ones>(expr)) {
    126         return createZeroes(expr->getType());
    127     }
    128     else if (isa<Zeroes>(expr)){
    129         return createOnes(expr->getType());
    130     }
    131     else if (Not * not1 = dyn_cast<Not>(expr)) {
    132         return not1->getOperand(0);
    133     }
    134     return insertAtInsertionPoint(new Not(expr, makeName("not_")));
    135 }
    136 
    137 PabloAST * PabloBlock::createNot(PabloAST * expr, const std::string prefix) {
    138     assert (expr);
    139     PabloAST::throwIfNonMatchingType(expr, PabloType::Stream);
    140     if (isa<Ones>(expr)) {
    141         return createZeroes(expr->getType());
    142     }
    143     else if (isa<Zeroes>(expr)){
    144         return createOnes(expr->getType());
    145     }
    146     else if (Not * not1 = dyn_cast<Not>(expr)) {       
    147         return renameNonNamedNode(not1->getOperand(0), std::move(prefix));
    148     }
    149     return insertAtInsertionPoint(new Not(expr, makeName(prefix, false)));
    150 }
    151 
    152 Var * PabloBlock::createVar(PabloAST * name, const PabloType * const type) {
    153     assert (name);
    154     return new Var(name, type);
    155 }
    156 
    157 PabloAST * PabloBlock::createInFile(PabloAST * expr) {
    158     assert (expr);
    159     return insertAtInsertionPoint(new InFile(expr, makeName("inFile_")));
    160 }
    161 
    162 PabloAST * PabloBlock::createInFile(PabloAST * expr, const std::string prefix) {
    163     assert (expr);
    164     return insertAtInsertionPoint(new InFile(expr, makeName(prefix, false)));
    165 }
    166 
    167 
    168 PabloAST * PabloBlock::createAtEOF(PabloAST * expr) {
    169     assert (expr);
    170     return insertAtInsertionPoint(new AtEOF(expr, makeName("atEOF_")));
    171 }
    172 
    173 PabloAST * PabloBlock::createAtEOF(PabloAST * expr, const std::string prefix) {
    174     assert (expr);
    175     return insertAtInsertionPoint(new AtEOF(expr, makeName(prefix, false)));
    176 }
    177    
    178    
    179     /// BINARY CREATE FUNCTIONS
    180 
    181 Next * PabloBlock::createNext(Assign * assign, PabloAST * expr) {
    182     assert (assign && expr);
    183     return insertAtInsertionPoint(new Next(assign, expr));
    184 }
    185 
    186 PabloAST * PabloBlock::createMatchStar(PabloAST * marker, PabloAST * charclass) {
    187     throwIfNonMatchingTypes(marker, charclass);
    188     if (isa<Zeroes>(marker) || isa<Zeroes>(charclass)) {
    189         return marker;
    190     }
    191     return insertAtInsertionPoint(new MatchStar(marker, charclass, makeName("matchstar")));
    192 }
    193 
    194 PabloAST * PabloBlock::createMatchStar(PabloAST * marker, PabloAST * charclass, const std::string prefix) {   
    195     throwIfNonMatchingTypes(marker, charclass);
    196     throwIfNonMatchingType(marker, PabloType::Stream);
    197     if (isa<Zeroes>(marker) || isa<Zeroes>(charclass)) {
    198         return renameNonNamedNode(marker, std::move(prefix));
    199     }
    200     return insertAtInsertionPoint(new MatchStar(marker, charclass, makeName(prefix, false)));
    201 }
    202 
    203 PabloAST * PabloBlock::createScanThru(PabloAST * from, PabloAST * thru) {   
    204     throwIfNonMatchingTypes(from, thru);
    205     throwIfNonMatchingType(from, PabloType::Stream);
    206     if (isa<Zeroes>(from) || isa<Zeroes>(thru)) {
    207         return from;
    208     }
    209     return insertAtInsertionPoint(new ScanThru(from, thru, makeName("scanthru")));
    210 }
    211 
    212 PabloAST * PabloBlock::createScanThru(PabloAST * from, PabloAST * thru, const std::string prefix) {
    213     throwIfNonMatchingTypes(from, thru);
    214     throwIfNonMatchingType(from, PabloType::Stream);
    215     if (isa<Zeroes>(from) || isa<Zeroes>(thru)) {       
    216         return renameNonNamedNode(from, std::move(prefix));
    217     }
    218     return insertAtInsertionPoint(new ScanThru(from, thru, makeName(prefix, false)));
    219 }
    220 
    221 template<typename Type>
    222 static inline Type * isBinary(PabloAST * expr) {
    223     if (isa<Type>(expr) && cast<Type>(expr)->getNumOperands() == 2) {
    224         return cast<Type>(expr);
    225     }
    226     return nullptr;
    227 }
    228 
    229 PabloAST * PabloBlock::createAnd(PabloAST * expr1, PabloAST * expr2) {
    230     throwIfNonMatchingTypes(expr1, expr2);
    231     if (isa<Zeroes>(expr2) || isa<Ones>(expr1)) {
    232         return expr2;
    233     } else if (isa<Zeroes>(expr1) || isa<Ones>(expr2) || equals(expr1, expr2)){
    234         return expr1;
    235     } else if (Not * not1 = dyn_cast<Not>(expr1)) {
    236         if (Not * not2 = dyn_cast<Not>(expr2)) {
    237             return createNot(createOr(not1->getOperand(0), not2->getOperand(0)));
    238         } else if (equals(not1->getOperand(0), expr2)) {
    239             return createZeroes(expr1->getType());
    240         }
    241     } else if (Not * not2 = dyn_cast<Not>(expr2)) {
    242         if (equals(expr1, not2->getOperand(0))) {
    243             return createZeroes(expr1->getType());
    244         }
    245     } else if (Or * or1 = isBinary<Or>(expr1)) {
    246         if (equals(or1->getOperand(0), expr2) || equals(or1->getOperand(1), expr2)) {
    247             return expr2;
    248         }
    249     } else if (Or * or2 = isBinary<Or>(expr2)) {
    250         if (equals(or2->getOperand(0), expr1) || equals(or2->getOperand(1), expr1)) {
    251             return expr1;
    252         }
    253     }
    254     return insertAtInsertionPoint(new And(expr1->getType(), expr1, expr2, makeName("and_")));
    255 }
    256 
    257 PabloAST * PabloBlock::createAnd(PabloAST * expr1, PabloAST * expr2, const std::string prefix) {
    258     throwIfNonMatchingTypes(expr1, expr2);
    259     if (isa<Zeroes>(expr2) || isa<Ones>(expr1)) {
    260         return renameNonNamedNode(expr2, std::move(prefix));
    261     }
    262     else if (isa<Zeroes>(expr1) || isa<Ones>(expr2) || equals(expr1, expr2)){
    263         return renameNonNamedNode(expr1, std::move(prefix));
    264     } else if (Not * not1 = dyn_cast<Not>(expr1)) {
    265         if (Not * not2 = dyn_cast<Not>(expr2)) {
    266             return createNot(createOr(not1->getOperand(0), not2->getOperand(0)), prefix);
    267         }
    268         else if (equals(not1->getOperand(0), expr2)) {
    269             return createZeroes(expr1->getType());
    270         }
    271     } else if (Not * not2 = dyn_cast<Not>(expr2)) {
    272         if (equals(expr1, not2->getOperand(0))) {
    273             return createZeroes(expr1->getType());
    274         }
    275     } else if (Or * or1 = isBinary<Or>(expr1)) {
    276         if (equals(or1->getOperand(0), expr2) || equals(or1->getOperand(1), expr2)) {
    277             return expr2;
    278         }
    279     } else if (Or * or2 = isBinary<Or>(expr2)) {
    280         if (equals(or2->getOperand(0), expr1) || equals(or2->getOperand(1), expr1)) {
    281             return expr1;
    282         }
    283     }
    284     return insertAtInsertionPoint(new And(expr1->getType(), expr1, expr2, makeName(prefix, false)));
    285 }
    286 
    287 And * PabloBlock::createAnd(const PabloType * const type, const unsigned reserved) {
    288     return insertAtInsertionPoint(new And(type, reserved, makeName("and_")));
    289 }
    290 
    291 And * PabloBlock::createAnd(const PabloType * const type, const unsigned reserved, const std::string prefix) {
    292     return insertAtInsertionPoint(new And(type, reserved, makeName(prefix, false)));
    293 }
    294 
    295 And * PabloBlock::createAnd(const PabloType * const type, std::vector<PabloAST *>::iterator begin, std::vector<PabloAST *>::iterator end) {
    296     return insertAtInsertionPoint(new And(type, begin, end, makeName("and_")));
    297 }
    298 
    299 And * PabloBlock::createAnd(const PabloType * const type, Variadic::iterator begin, Variadic::iterator end) {
    300     return insertAtInsertionPoint(new And(type, begin, end, makeName("and_")));
    301 }
    302 
    303 PabloAST * PabloBlock::createOr(PabloAST * expr1, PabloAST * expr2) {
    304     throwIfNonMatchingTypes(expr1, expr2);
    305     if (isa<Zeroes>(expr1) || isa<Ones>(expr2)){
    306         return expr2;
    307     }
    308     if (isa<Zeroes>(expr2) || isa<Ones>(expr1) || equals(expr1, expr2)) {
    309         return expr1;
    310     } else if (Not * not1 = dyn_cast<Not>(expr1)) {
    311         // ¬a√b = ¬¬(¬a √ b) = ¬(a ∧ ¬b)
    312         return createNot(createAnd(not1->getOperand(0), createNot(expr2)));
    313     } else if (Not * not2 = dyn_cast<Not>(expr2)) {
    314         // a√¬b = ¬¬(¬b √ a) = ¬(b ∧ ¬a)
    315         return createNot(createAnd(not2->getOperand(0), createNot(expr1)));
    316     } else if (equals(expr1, expr2)) {
    317         return expr1;
    318     } else if (And * and1 = isBinary<And>(expr1)) {
    319         if (And * and2 = isBinary<And>(expr2)) {
    320             PabloAST * const expr1a = and1->getOperand(0);
    321             PabloAST * const expr1b = and1->getOperand(1);
    322             PabloAST * const expr2a = and2->getOperand(0);
    323             PabloAST * const expr2b = and2->getOperand(1);
    324             //These optimizations factor out common components that can occur when sets are formed by union
    325             //(e.g., union of [a-z] and [A-Z].
    326             if (equals(expr1a, expr2a)) {
    327                 return createAnd(expr1a, createOr(expr1b, expr2b));
    328             } else if (equals(expr1b, expr2b)) {
    329                 return createAnd(expr1b, createOr(expr1a, expr2a));
    330             } else if (equals(expr1a, expr2b)) {
    331                 return createAnd(expr1a, createOr(expr1b, expr2a));
    332             } else if (equals(expr1b, expr2a)) {
    333                 return createAnd(expr1b, createOr(expr1a, expr2b));
    334             }
    335         } else if (equals(and1->getOperand(0), expr2) || equals(and1->getOperand(1), expr2)) {
    336             // (a ∧ b) √ a = a
    337             return expr2;
    338         }
    339     } else if (And * and2 = isBinary<And>(expr2)) {
    340         if (equals(and2->getOperand(0), expr1) || equals(and2->getOperand(1), expr1)) {
    341             return expr1;
    342         }
    343     }
    344     return insertAtInsertionPoint(new Or(expr1->getType(), expr1, expr2, makeName("or_")));
    345 }
    346 
    347 PabloAST * PabloBlock::createOr(PabloAST * expr1, PabloAST * expr2, const std::string prefix) {
    348     throwIfNonMatchingTypes(expr1, expr2);
    349     if (isa<Zeroes>(expr1) || isa<Ones>(expr2)){
    350         return renameNonNamedNode(expr2, std::move(prefix));
    351     }
    352     else if (isa<Zeroes>(expr2) || isa<Ones>(expr1) || equals(expr1, expr2)) {
    353         return renameNonNamedNode(expr1, std::move(prefix));
    354     } else if (Not * not1 = dyn_cast<Not>(expr1)) {
    355         // ¬a√b = ¬¬(¬a√b) = ¬(a ∧ ¬b)
    356         return createNot(createAnd(not1->getOperand(0), createNot(expr2)), prefix);
    357     } else if (Not * not2 = dyn_cast<Not>(expr2)) {
    358         // a√¬b = ¬¬(¬b√a) = ¬(b ∧ ¬a)
    359         return createNot(createAnd(not2->getOperand(0), createNot(expr1)), prefix);
    360     } else if (And * and1 = isBinary<And>(expr1)) {
    361         if (And * and2 = isBinary<And>(expr2)) {
    362             PabloAST * const expr1a = and1->getOperand(0);
    363             PabloAST * const expr1b = and1->getOperand(1);
    364             PabloAST * const expr2a = and2->getOperand(0);
    365             PabloAST * const expr2b = and2->getOperand(1);
    366             //These optimizations factor out common components that can occur when sets are formed by union
    367             //(e.g., union of [a-z] and [A-Z].
    368             if (equals(expr1a, expr2a)) {
    369                 return createAnd(expr1a, createOr(expr1b, expr2b), prefix);
    370             } else if (equals(expr1b, expr2b)) {
    371                 return createAnd(expr1b, createOr(expr1a, expr2a), prefix);
    372             } else if (equals(expr1a, expr2b)) {
    373                 return createAnd(expr1a, createOr(expr1b, expr2a), prefix);
    374             } else if (equals(expr1b, expr2a)) {
    375                 return createAnd(expr1b, createOr(expr1a, expr2b), prefix);
    376             }
    377         } else if (equals(and1->getOperand(0), expr2) || equals(and1->getOperand(1), expr2)) {
    378             // (a∧b) √ a = a
    379             return expr2;
    380         }
    381     } else if (And * and2 = isBinary<And>(expr2)) {
    382         if (equals(and2->getOperand(0), expr1) || equals(and2->getOperand(1), expr1)) {
    383             return expr1;
    384         }
    385     }
    386     return insertAtInsertionPoint(new Or(expr1->getType(), expr1, expr2, makeName(prefix, false)));
    387 }
    388 
    389 Or * PabloBlock::createOr(const PabloType * const type, const unsigned reserved) {
    390     return insertAtInsertionPoint(new Or(type, reserved, makeName("or_")));
    391 }
    392 
    393 Or * PabloBlock::createOr(const PabloType * const type, const unsigned reserved, const std::string prefix) {
    394     return insertAtInsertionPoint(new Or(type, reserved, makeName(prefix, false)));
    395 }
    396 
    397 Or * PabloBlock::createOr(const PabloType * const type, std::vector<PabloAST *>::iterator begin, std::vector<PabloAST *>::iterator end) {
    398     return insertAtInsertionPoint(new Or(type, begin, end, makeName("or_")));
    399 }
    400 
    401 Or * PabloBlock::createOr(const PabloType * const type, Variadic::iterator begin, Variadic::iterator end) {
    402     return insertAtInsertionPoint(new Or(type, begin, end, makeName("or_")));
    403 }
    404 
    405 PabloAST * PabloBlock::createXor(PabloAST * expr1, PabloAST * expr2) {
    406     throwIfNonMatchingTypes(expr1, expr2);
    407     if (expr1 == expr2) {
    408         return PabloBlock::createZeroes(expr1->getType());
    409     } else if (isa<Ones>(expr1)) {
    410         return createNot(expr2);
    411     } else if (isa<Zeroes>(expr1)){
    412         return expr2;
    413     } else if (isa<Ones>(expr2)) {
    414         return createNot(expr1);
    415     } else if (isa<Zeroes>(expr2)){
    416         return expr1;
    417     } else if (Not * not1 = dyn_cast<Not>(expr1)) {
    418         if (Not * not2 = dyn_cast<Not>(expr2)) {
    419             return createXor(not1->getOperand(0), not2->getOperand(0));
    420         }
    421     }
    422     return insertAtInsertionPoint(new Xor(expr1->getType(), expr1, expr2, makeName("xor_")));
    423 }
    424 
    425 PabloAST * PabloBlock::createXor(PabloAST * expr1, PabloAST * expr2, const std::string prefix) {
    426     throwIfNonMatchingTypes(expr1, expr2);
    427     if (expr1 == expr2) {
    428         return PabloBlock::createZeroes(expr1->getType());
    429     } else if (isa<Ones>(expr1)) {
    430         return createNot(expr2, prefix);
    431     } else if (isa<Zeroes>(expr1)){
    432         return expr2;
    433     } else if (isa<Ones>(expr2)) {
    434         return createNot(expr1, prefix);
    435     } else if (isa<Zeroes>(expr2)){
    436         return expr1;
    437     } else if (Not * not1 = dyn_cast<Not>(expr1)) {
    438         if (Not * not2 = dyn_cast<Not>(expr2)) {
    439             return createXor(not1->getOperand(0), not2->getOperand(0), prefix);
    440         }
    441     }
    442     return insertAtInsertionPoint(new Xor(expr1->getType(), expr1, expr2, makeName(prefix, false)));
    443 }
    444 
    445 Xor * PabloBlock::createXor(const PabloType * const type, const unsigned reserved) {
    446     return insertAtInsertionPoint(new Xor(type, reserved, makeName("xor_")));
    447 }
    448 
    449 Xor * PabloBlock::createXor(const PabloType * const type, const unsigned reserved, const std::string prefix) {
    450     return insertAtInsertionPoint(new Xor(type, reserved, makeName(prefix, false)));
    451 }
    452 
    453 Xor * PabloBlock::createXor(const PabloType * const type, std::vector<PabloAST *>::iterator begin, std::vector<PabloAST *>::iterator end) {
    454     return insertAtInsertionPoint(new Xor(type, begin, end, makeName("xor_")));
    455 }
    456 
    457 Xor * PabloBlock::createXor(const PabloType * const type, Variadic::iterator begin, Variadic::iterator end) {
    458     return insertAtInsertionPoint(new Xor(type, begin, end, makeName("xor_")));
    459 }
    460 
    461 /// TERNARY CREATE FUNCTION
    462 
    463 PabloAST * PabloBlock::createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr) {
    464     throwIfNonMatchingTypes(trueExpr, falseExpr);
    465     if (isa<Ones>(condition)) {
    466         return trueExpr;
    467     } else if (isa<Zeroes>(condition)){
    468         return falseExpr;
    469     } else if (isa<Ones>(trueExpr)) {
    470         return createOr(condition, falseExpr);
    471     } else if (isa<Zeroes>(trueExpr)){
    472         return createAnd(createNot(condition), falseExpr);
    473     } else if (isa<Ones>(falseExpr)) {
    474         return createOr(createNot(condition), trueExpr);
    475     } else if (isa<Zeroes>(falseExpr)){
    476         return createAnd(condition, trueExpr);
    477     } else if (equals(trueExpr, falseExpr)) {
    478         return trueExpr;
    479     } else if (isa<Not>(trueExpr) && equals(cast<Not>(trueExpr)->getOperand(0), falseExpr)) {
    480         return createXor(condition, falseExpr);
    481     } else if (isa<Not>(falseExpr) && equals(trueExpr, cast<Not>(falseExpr)->getOperand(0))){
    482         return createXor(condition, trueExpr);
    483     }
    484     return insertAtInsertionPoint(new Sel(condition, trueExpr, falseExpr, makeName("sel")));
    485 }
    486 
    487 PabloAST * PabloBlock::createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr, const std::string prefix) {
    488     throwIfNonMatchingTypes(trueExpr, falseExpr);
    489     if (isa<Zeroes>(condition)){
    490         return renameNonNamedNode(falseExpr, std::move(prefix));
    491     } else if (isa<Ones>(condition) || equals(trueExpr, falseExpr)) {
    492         return renameNonNamedNode(trueExpr, std::move(prefix));
    493     } else if (isa<Ones>(trueExpr)) {
    494         return createOr(condition, falseExpr, prefix);
    495     } else if (isa<Zeroes>(trueExpr)){
    496         return createAnd(createNot(condition), falseExpr, prefix);
    497     } else if (isa<Ones>(falseExpr)) {
    498         return createOr(createNot(condition), trueExpr, prefix);
    499     } else if (isa<Zeroes>(falseExpr)){
    500         return createAnd(condition, trueExpr, prefix);
    501     } else if (isa<Not>(trueExpr) && equals(cast<Not>(trueExpr)->getOperand(0), falseExpr)) {
    502         return createXor(condition, falseExpr, prefix);
    503     } else if (isa<Not>(falseExpr) && equals(trueExpr, cast<Not>(falseExpr)->getOperand(0))){
    504         return createXor(condition, trueExpr, prefix);
    505     }
    506     return insertAtInsertionPoint(new Sel(condition, trueExpr, falseExpr, makeName(prefix, false)));
    507 }
    508 
    509 If * PabloBlock::createIf(PabloAST * condition, const std::initializer_list<Assign *> definedVars, PabloBlock * body) {
    510     assert (condition);
    511     return insertAtInsertionPoint(new If(condition, definedVars, body));
    512 }
    513 
    514 If * PabloBlock::createIf(PabloAST * condition, const std::vector<Assign *> & definedVars, PabloBlock * body) {
    515     assert (condition);
    516     return insertAtInsertionPoint(new If(condition, definedVars, body));
    517 }
    518 
    519 If * PabloBlock::createIf(PabloAST * condition, std::vector<Assign *> && definedVars, PabloBlock * body) {
    520     assert (condition);
    521     return insertAtInsertionPoint(new If(condition, definedVars, body));
    522 }
    523 
    524 While * PabloBlock::createWhile(PabloAST * condition, const std::initializer_list<Next *> nextVars, PabloBlock * body) {
    525     assert (condition);
    526     return insertAtInsertionPoint(new While(condition, nextVars, body));
    527 }
    528 
    529 While * PabloBlock::createWhile(PabloAST * condition, const std::vector<Next *> & nextVars, PabloBlock * body) {
    530     assert (condition);
    531     return insertAtInsertionPoint(new While(condition, nextVars, body));
    532 }
    533 
    534 While * PabloBlock::createWhile(PabloAST * condition, std::vector<Next *> && nextVars, PabloBlock * body) {
    535     assert (condition);
    536     return insertAtInsertionPoint(new While(condition, nextVars, body));
    537 }
    538 
    539203/** ------------------------------------------------------------------------------------------------------------- *
    540204 * @brief eraseFromParent
     
    542206void PabloBlock::eraseFromParent(const bool recursively) {
    543207    Statement * stmt = front();
    544     // Note: by erasing the scope block, any Assign/Next nodes will be replaced with Zero and removed from
    545     // the If/While node
    546208    while (stmt) {
    547209        stmt = stmt->eraseFromParent(recursively);
     
    550212}
    551213
    552 
    553 // Assign sequential scope indexes, returning the next unassigned index   
    554 
     214/** ------------------------------------------------------------------------------------------------------------- *
     215 * @brief enumerateScopes
     216 *
     217 * Assign sequential scope indexes, returning the next unassigned index
     218 ** ------------------------------------------------------------------------------------------------------------- */
    555219unsigned PabloBlock::enumerateScopes(unsigned baseScopeIndex) {
    556220    mScopeIndex = baseScopeIndex;
     
    569233/// CONSTRUCTOR
    570234
    571 PabloBlock::PabloBlock(PabloFunction * parent, PabloBlock *predecessor) noexcept
    572 : PabloAST(PabloAST::ClassTypeId::Block, nullptr)
     235PabloBlock::PabloBlock(PabloFunction * const parent) noexcept
     236: PabloAST(PabloAST::ClassTypeId::Block, nullptr, nullptr)
    573237, mParent(parent)
    574 , mPredecessor(predecessor)
    575238, mBranch(nullptr)
    576239, mScopeIndex(0)
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r5160 r5202  
    1515#include <pablo/pe_call.h>
    1616#include <pablo/pe_matchstar.h>
    17 #include <pablo/pe_next.h>
    1817#include <pablo/pe_not.h>
    1918#include <pablo/pe_ones.h>
     
    2928#include <pablo/pe_count.h>
    3029#include <pablo/ps_assign.h>
    31 #include <pablo/ps_if.h>
    32 #include <pablo/ps_while.h>
     30#include <pablo/branch.h>
    3331#include <pablo/function.h>
    3432#include <llvm/ADT/ArrayRef.h>
     
    3937class PabloBlock : public PabloAST, public StatementList {
    4038    friend class PabloAST;
    41     friend class If;
    42     friend class While;
     39    friend class Branch;
    4340    friend class PabloBuilder;
    4441public:
     
    5855
    5956    inline static PabloBlock * Create(PabloFunction & parent) noexcept {
    60         return new PabloBlock(&parent, nullptr);
     57        return new PabloBlock(&parent);
    6158    }
    6259
    6360    inline static PabloBlock * Create(PabloBlock * const predecessor) noexcept {
    64         return new PabloBlock(predecessor->mParent, predecessor);
    65     }
    66 
    67     PabloAST * createAdvance(PabloAST * expr, const Integer::Type shiftAmount);
    68 
    69     PabloAST * createAdvance(PabloAST * expr, PabloAST * shiftAmount);
    70 
    71     PabloAST * createAdvance(PabloAST * expr, const Integer::Type shiftAmount, const std::string prefix);
    72 
    73     PabloAST * createAdvance(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix);
    74 
    75     PabloAST * createLookahead(PabloAST * expr, const Integer::Type shiftAmount);
    76 
    77     PabloAST * createLookahead(PabloAST * expr, PabloAST * shiftAmount);
    78 
    79     PabloAST * createLookahead(PabloAST * expr, const Integer::Type shiftAmount, const std::string prefix);
    80 
    81     PabloAST * createLookahead(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix);
    82 
    83     inline Zeroes * createZeroes(const PabloType * const type = nullptr) {
     61        return new PabloBlock(predecessor->mParent);
     62    }
     63
     64    Advance * createAdvance(PabloAST * expr, PabloAST * shiftAmount) {
     65        return createAdvance(expr, shiftAmount, nullptr);
     66    }
     67
     68    Advance * createAdvance(PabloAST * expr, PabloAST * shiftAmount, const std::string & prefix) {
     69        return createAdvance(expr, shiftAmount, makeName(prefix));
     70    }
     71
     72    Advance * createAdvance(PabloAST * expr, PabloAST * shiftAmount, String * const name);
     73
     74    Lookahead * createLookahead(PabloAST * expr, PabloAST * shiftAmount) {
     75        return createLookahead(expr, shiftAmount, nullptr);
     76    }
     77
     78    Lookahead * createLookahead(PabloAST * expr, PabloAST * shiftAmount, const std::string & prefix) {
     79        return createLookahead(expr, shiftAmount, makeName(prefix));
     80    }
     81
     82    Lookahead * createLookahead(PabloAST * expr, PabloAST * shiftAmount, String * const name);
     83
     84    inline Zeroes * createZeroes(Type * const type = nullptr) {
    8485        return mParent->getNullValue(type);
    8586    }
    8687
    87     inline Ones * createOnes(const PabloType * const type = nullptr) {
     88    inline Ones * createOnes(Type * const type = nullptr) {
    8889        return mParent->getAllOnesValue(type);
    8990    }
     
    103104    }
    104105
    105     Assign * createAssign(const std::string && prefix, PabloAST * const expr);
    106 
    107     inline Var * createVar(const std::string name, const PabloType * const type) {
    108         return createVar(getName(name, false), type);
    109     }
    110 
    111     inline Var * createVar(String * name, const PabloType * const type) {
     106    Not * createNot(PabloAST * expr) {
     107        return createNot(expr, nullptr);
     108    }
     109
     110    Not * createNot(PabloAST * expr, const std::string & prefix) {
     111        return createNot(expr, makeName(prefix));
     112    }
     113
     114    Not * createNot(PabloAST * expr, String * const name);
     115
     116    inline Var * createVar(const std::string & name, Type * const type = nullptr) {
     117        return createVar(makeName(name), type);
     118    }
     119
     120    inline Var * createVar(String * name, Type * const type = nullptr) {
    112121        return createVar(cast<PabloAST>(name), type);
    113122    }
    114123
    115     Next * createNext(Assign * assign, PabloAST * expr);
    116 
    117     PabloAST * createAnd(PabloAST * expr1, PabloAST * expr2);
    118 
    119     PabloAST * createAnd(PabloAST * expr1, PabloAST * expr2, const std::string prefix);
    120 
    121     And * createAnd(const PabloType * const type, const unsigned reserved);
    122 
    123     And * createAnd(const PabloType * const type, const unsigned reserved, const std::string prefix);
    124 
    125     And * createAnd(const PabloType * const type, std::vector<PabloAST *>::iterator begin, std::vector<PabloAST *>::iterator end);
    126 
    127     And * createAnd(const PabloType * const type, Variadic::iterator begin, Variadic::iterator end);
    128 
    129     PabloAST * createNot(PabloAST * expr);
    130 
    131     PabloAST * createNot(PabloAST * expr, const std::string prefix);
    132 
    133     PabloAST * createOr(PabloAST * expr1, PabloAST * expr2);
    134 
    135     PabloAST * createOr(PabloAST * expr1, PabloAST * expr2, const std::string prefix);
    136 
    137     Or * createOr(const PabloType * const type, std::vector<PabloAST *>::iterator begin, std::vector<PabloAST *>::iterator end);
    138 
    139     Or * createOr(const PabloType * const type, Variadic::iterator begin, Variadic::iterator end);
    140 
    141     Or * createOr(const PabloType * const type, const unsigned reserved);
    142 
    143     Or * createOr(const PabloType * const type, const unsigned reserved, const std::string prefix);
    144 
    145     PabloAST * createXor(PabloAST * expr1, PabloAST * expr2);
    146 
    147     PabloAST * createXor(PabloAST * expr1, PabloAST * expr2, const std::string prefix);
    148 
    149     Xor * createXor(const PabloType * const type, std::vector<PabloAST *>::iterator begin, std::vector<PabloAST *>::iterator end);
    150 
    151     Xor * createXor(const PabloType * const type, Variadic::iterator begin, Variadic::iterator end);
    152 
    153     Xor * createXor(const PabloType * const type, const unsigned reserved);
    154 
    155     Xor * createXor(const PabloType * const type, const unsigned reserved, const std::string prefix);
    156 
    157     PabloAST * createMatchStar(PabloAST * marker, PabloAST * charclass);
    158 
    159     PabloAST * createMatchStar(PabloAST * marker, PabloAST * charclass, const std::string prefix);
    160 
    161     PabloAST * createScanThru(PabloAST * from, PabloAST * thru);
    162 
    163     PabloAST * createScanThru(PabloAST * from, PabloAST * thru, const std::string prefix);
    164 
    165     PabloAST * createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr);
    166 
    167     PabloAST * createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr, const std::string prefix);
    168 
    169     Count * createCount(const std::string counter, PabloAST * const expr);
     124    Count * createCount(PabloAST * expr);
     125
     126    Count * createCount(PabloAST * expr, const std::string & prefix);
     127
     128    InFile * createInFile(PabloAST * expr) {
     129        return createInFile(expr, nullptr);
     130    }
     131
     132    InFile * createInFile(PabloAST * expr, const std::string & prefix) {
     133        return createInFile(expr, makeName(prefix));
     134    }
     135
     136    InFile * createInFile(PabloAST * expr, String * const name);
     137
     138    AtEOF * createAtEOF(PabloAST * expr) {
     139        return createAtEOF(expr, nullptr);
     140    }
     141
     142    AtEOF * createAtEOF(PabloAST * expr, const std::string & prefix) {
     143        return createAtEOF(expr, makeName(prefix));
     144    }
     145
     146    AtEOF * createAtEOF(PabloAST * expr, String * const name);
     147
     148    Extract * createExtract(PabloAST * array, const Integer::Type index) {
     149        return createExtract(array, getInteger(index), nullptr);
     150    }
     151
     152    inline Extract * createExtract(PabloAST * array, PabloAST * index) {
     153        return createExtract(array, index, nullptr);
     154    }
     155
     156    Extract * createExtract(PabloAST * array, PabloAST * index, const std::string & prefix) {
     157        return createExtract(array, index, makeName(prefix));
     158    }
     159
     160    Extract * createExtract(PabloAST * array, const Integer::Type index, const std::string & prefix) {
     161        return createExtract(array, getInteger(index), makeName(prefix));
     162    }
     163
     164    Extract * createExtract(PabloAST * array, PabloAST * index, String * const name);
     165
     166    Assign * createAssign(PabloAST * const var, PabloAST * const value);
     167
     168    And * createAnd(PabloAST * expr1, PabloAST * expr2) {
     169        return createAnd(expr1, expr2, nullptr);
     170    }
     171
     172    And * createAnd(PabloAST * expr1, PabloAST * expr2, const std::string & prefix) {
     173        return createAnd(expr1, expr2, nullptr);
     174    }
     175
     176    And * createAnd(PabloAST * expr1, PabloAST * expr2, String * const name);
     177
     178    And * createAnd(Type * const type, const unsigned reserved) {
     179        return createAnd(type, reserved, nullptr);
     180    }
     181
     182    And * createAnd(Type * const type, const unsigned reserved, String * const name);
     183
     184    Or * createOr(PabloAST * expr1, PabloAST * expr2) {
     185        return createOr(expr1, expr2, nullptr);
     186    }
     187
     188    Or * createOr(PabloAST * expr1, PabloAST * expr2, const std::string & prefix) {
     189        return createOr(expr1, expr2, makeName(prefix));
     190    }
     191
     192    Or * createOr(PabloAST * expr1, PabloAST * expr2, String * const name);
     193
     194    Or * createOr(Type * const type, const unsigned reserved) {
     195        return createOr(type, reserved, nullptr);
     196    }
     197
     198    Or * createOr(Type * const type, const unsigned reserved, String * const name);
     199
     200    Xor * createXor(PabloAST * expr1, PabloAST * expr2) {
     201        return createXor(expr1, expr2, nullptr);
     202    }
     203
     204    Xor * createXor(PabloAST * expr1, PabloAST * expr2, const std::string & prefix) {
     205        return createXor(expr1, expr2, makeName(prefix));
     206    }
     207
     208    Xor * createXor(PabloAST * expr1, PabloAST * expr2, String * const name);
     209
     210    Xor * createXor(Type * const type, const unsigned reserved) {
     211        return createXor(type, reserved, nullptr);
     212    }
     213
     214    Xor * createXor(Type * const type, const unsigned reserved, String * const name);
     215
     216    MatchStar * createMatchStar(PabloAST * marker, PabloAST * charclass) {
     217        return createMatchStar(marker, charclass, nullptr);
     218    }
     219
     220    MatchStar * createMatchStar(PabloAST * marker, PabloAST * charclass, const std::string & prefix) {
     221        return createMatchStar(marker, charclass, makeName(prefix));
     222    }
     223
     224    MatchStar * createMatchStar(PabloAST * marker, PabloAST * charclass, String * const name);
     225
     226    ScanThru * createScanThru(PabloAST * from, PabloAST * thru) {
     227        return createScanThru(from, thru, nullptr);
     228    }
     229
     230    ScanThru * createScanThru(PabloAST * from, PabloAST * thru, const std::string & prefix) {
     231        return createScanThru(from, thru, makeName(prefix));
     232    }
     233
     234    ScanThru * createScanThru(PabloAST * from, PabloAST * thru, String * const name);
     235
     236    Sel * createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr) {
     237        return createSel(condition, trueExpr, falseExpr, nullptr);
     238    }
     239
     240    Sel * createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr, const std::string & prefix) {
     241        return createSel(condition, trueExpr, falseExpr, makeName(prefix));
     242    }
     243
     244    Sel * createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr, String * const name);
    170245   
    171     PabloAST * createInFile(PabloAST * expr);
    172    
    173     PabloAST * createInFile(PabloAST * expr, const std::string prefix);
    174    
    175     PabloAST * createAtEOF(PabloAST * expr);
    176    
    177     PabloAST * createAtEOF(PabloAST * expr, const std::string prefix);
    178    
    179     If * createIf(PabloAST * condition, const std::initializer_list<Assign *> definedVars, PabloBlock * body);
    180 
    181     If * createIf(PabloAST * condition, const std::vector<Assign *> & definedVars, PabloBlock * body);
    182 
    183     If * createIf(PabloAST * condition, std::vector<Assign *> && definedVars, PabloBlock * body);
    184 
    185     While * createWhile(PabloAST * condition, const std::initializer_list<Next *> nextVars, PabloBlock * body);
    186 
    187     While * createWhile(PabloAST * condition, const std::vector<Next *> & nextVars, PabloBlock * body);
    188 
    189     While * createWhile(PabloAST * condition, std::vector<Next *> && nextVars, PabloBlock * body);
    190 
    191     inline StatementList & statements() {
    192         return *this;
    193     }
    194 
    195     inline const StatementList & statements() const {
    196         return *this;
    197     }
    198 
    199     inline String * getName(const std::string name, const bool generated = true) const {
    200         return getSymbolTable()->get(name, generated);
    201     }
    202 
    203     inline String * makeName(const std::string prefix, const bool generated = true) const {
    204         return getSymbolTable()->make(prefix, generated);
    205     }
    206 
    207     inline Integer * getInteger(Integer::Type value) {
    208         return getSymbolTable()->getInteger(value);
    209     }
     246    If * createIf(PabloAST * condition, PabloBlock * body);
     247
     248    While * createWhile(PabloAST * condition, PabloBlock * body);
    210249
    211250    inline PabloBlock * getPredecessor() const {
    212         return mPredecessor;
    213     }
    214    
    215     void setPredecessor(PabloBlock * const predecessor) {
    216         mPredecessor = predecessor;
     251        return getBranch() ? getBranch()->getParent() : nullptr;
    217252    }
    218253
     
    235270    void eraseFromParent(const bool recursively = false);
    236271
    237     inline Statement * getBranch() const {
     272    inline Branch * getBranch() const {
    238273        return mBranch;
     274    }
     275
     276    inline void setBranch(Branch * const branch) {
     277        mBranch = branch;
     278    }
     279
     280    inline String * getName(const std::string name) const {
     281        return getSymbolTable()->get(name);
     282    }
     283
     284    inline String * makeName(const std::string & prefix) const {
     285        return getSymbolTable()->make(prefix);
     286    }
     287
     288    inline Integer * getInteger(Integer::Type value) const {
     289        return getSymbolTable()->getInteger(value);
    239290    }
    240291
     
    247298protected:
    248299
    249     explicit PabloBlock(PabloFunction * parent, PabloBlock * predecessor) noexcept;
    250 
    251     PabloAST * renameNonNamedNode(PabloAST * expr, const std::string && prefix);
     300    explicit PabloBlock(PabloFunction * parent) noexcept;
    252301
    253302    template<typename Type>
    254303    inline Type * insertAtInsertionPoint(Type * expr) {
    255304        if (isa<Statement>(expr)) {
    256             if (LLVM_UNLIKELY(isa<If>(expr) || isa<While>(expr))) {
    257                 PabloBlock * const body = isa<If>(expr) ? cast<If>(expr)->getBody() : cast<While>(expr)->getBody();
    258                 body->setPredecessor (this);
    259                 addUser(body);
    260             }
    261305            insert(cast<Statement>(expr));
    262306        }
     
    264308    }
    265309
    266     inline void setBranch(Statement * const branch) {
    267         mBranch = branch;
    268     }
    269 
    270 private:
    271 
    272310    Call * createCall(PabloAST * prototype, const std::vector<PabloAST *> &);
    273311
    274     Var * createVar(PabloAST * name, const PabloType * const type);
     312    Var * createVar(PabloAST * name, Type * const type);
    275313
    276314private:       
    277315    PabloFunction *                                     mParent;
    278     PabloBlock *                                        mPredecessor;
    279     Statement *                                         mBranch; // What statement branches into this scope block?
     316    Branch *                                            mBranch;
    280317    unsigned                                            mScopeIndex;
    281318};
  • icGREP/icgrep-devel/icgrep/pablo/expression_map.hpp

    r4983 r5202  
    3030
    3131    template <class Functor, typename... Params>
    32     inline PabloAST * findOrCall(Functor && functor, const PabloAST::ClassTypeId type, Args... args, Params... params) {
     32    PabloAST * findOrCall(Functor && functor, const PabloAST::ClassTypeId type, Args... args, Params... params) {
    3333        Key key = std::make_tuple(type, args...);
    3434        PabloAST * const f = find(key);
     
    4141    }
    4242
    43     inline std::pair<PabloAST *, bool> findOrAdd(PabloAST * object, const PabloAST::ClassTypeId type, Args... args) {
     43    std::pair<PabloAST *, bool> findOrAdd(PabloAST * object, const PabloAST::ClassTypeId type, Args... args) {
    4444        Key key = std::make_tuple(type, args...);
    4545        PabloAST * const entry = find(key);
     
    5151    }
    5252
    53     inline bool erase(const PabloAST::ClassTypeId type, Args... args) {
     53    bool erase(const PabloAST::ClassTypeId type, Args... args) {
    5454        Key key = std::make_tuple(type, args...);
    5555        for (Type * obj = this; obj; obj = obj->mPredecessor) {
     
    6969private:
    7070
    71     inline PabloAST * find(const Key & key) const {
     71    PabloAST * find(const Key & key) const {
    7272        // check this map to see if we have it
    7373        auto itr = mMap.find(key);
    7474        if (itr != mMap.end()) {
    7575            return itr->second;
    76         }
    77         // check any previous maps to see if it exists
    78         auto * pred = mPredecessor;
    79         while (pred) {
    80             itr = pred->mMap.find(key);
    81             if (itr == pred->mMap.end()) {
    82                 pred = pred->mPredecessor;
    83                 continue;
    84             }
    85             return itr->second;
     76        } else { // check any previous maps to see if it exists
     77            auto * pred = mPredecessor;
     78            while (pred) {
     79                itr = pred->mMap.find(key);
     80                if (itr == pred->mMap.end()) {
     81                    pred = pred->mPredecessor;
     82                    continue;
     83                }
     84                return itr->second;
     85            }
    8686        }
    8787        return nullptr;
     
    166166
    167167    template <class Functor, typename... Params>
    168     inline PabloAST * findOrCall(Functor && functor, const PabloAST::ClassTypeId type, const PabloAST * arg1, const std::vector<PabloAST *> & args, Params... params) {
     168    PabloAST * findOrCall(Functor && functor, const PabloAST::ClassTypeId type, const PabloAST * arg1, const std::vector<PabloAST *> & args, Params... params) {
    169169        Key key(type, arg1, args, mAllocator);
    170170        PabloAST * const f = find(key);
     
    178178    }
    179179
    180     inline std::pair<PabloAST *, bool> findOrAdd(Variadic * object, const PabloAST::ClassTypeId type) {
     180    std::pair<PabloAST *, bool> findOrAdd(Variadic * object, const PabloAST::ClassTypeId type) {
    181181        Key key(type, object, mAllocator);
    182182        PabloAST * const entry = find(key);
     
    191191private:
    192192
    193     inline PabloAST * find(const Key & key) const {
     193    PabloAST * find(const Key & key) const {
    194194        // check this map to see if we have it
    195195        auto itr = mMap.find(key);
    196196        if (itr != mMap.end()) {
    197197            return itr->second;
    198         }
    199         // check any previous maps to see if it exists
    200         auto * pred = mPredecessor;
    201         while (pred) {
    202             itr = pred->mMap.find(key);
    203             if (itr == pred->mMap.end()) {
    204                 pred = pred->mPredecessor;
    205                 continue;
    206             }
    207             return itr->second;
     198        } else { // check any previous maps to see if it exists
     199            auto * pred = mPredecessor;
     200            while (pred) {
     201                itr = pred->mMap.find(key);
     202                if (itr == pred->mMap.end()) {
     203                    pred = pred->mPredecessor;
     204                    continue;
     205                }
     206                return itr->second;
     207            }
    208208        }
    209209        return nullptr;
     
    223223            mBinary.mPredecessor = &(predecessor->mBinary);
    224224            mTernary.mPredecessor = &(predecessor->mTernary);
    225             mVariable.mPredecessor = &(predecessor->mVariable);
     225            mVariadic.mPredecessor = &(predecessor->mVariadic);
    226226        }
    227227    }
     
    233233    , mBinary(std::move(other.mBinary))
    234234    , mTernary(std::move(other.mTernary))
    235     , mVariable(std::move(other.mVariable)) {
     235    , mVariadic(std::move(other.mVariadic)) {
    236236
    237237    }
     
    241241        mBinary = std::move(other.mBinary);
    242242        mTernary = std::move(other.mTernary);
    243         mVariable = std::move(other.mVariable);
     243        mVariadic = std::move(other.mVariadic);
    244244        return *this;
    245245    }
     
    261261
    262262    template <class Functor, typename... Params>
    263     inline PabloAST * findVariableOrCall(Functor && functor, const PabloAST::ClassTypeId type, const PabloAST * arg1, const std::vector<PabloAST *> & args, Params... params) {
    264         return mVariable.findOrCall(std::move(functor), type, arg1, args, std::forward<Params>(params)...);
     263    inline PabloAST * findVariadicOrCall(Functor && functor, const PabloAST::ClassTypeId type, const PabloAST * arg1, const std::vector<PabloAST *> & args, Params... params) {
     264        return mVariadic.findOrCall(std::move(functor), type, arg1, args, std::forward<Params>(params)...);
    265265    }
    266266
    267267    std::pair<PabloAST *, bool> findOrAdd(Statement * stmt) {
    268         switch (stmt->getClassTypeId()) {           
    269             case PabloAST::ClassTypeId::Assign:           
     268        switch (stmt->getClassTypeId()) {                     
    270269            case PabloAST::ClassTypeId::Var:
    271270            case PabloAST::ClassTypeId::Not:
     
    275274            case PabloAST::ClassTypeId::Or:
    276275            case PabloAST::ClassTypeId::Xor:
    277                 return mVariable.findOrAdd(cast<Variadic>(stmt), stmt->getClassTypeId());
     276                return mVariadic.findOrAdd(cast<Variadic>(stmt), stmt->getClassTypeId());
    278277            case PabloAST::ClassTypeId::Advance:
    279278            case PabloAST::ClassTypeId::ScanThru:
    280279            case PabloAST::ClassTypeId::MatchStar:
    281             case PabloAST::ClassTypeId::Next:
     280            case PabloAST::ClassTypeId::Assign:
    282281                return mBinary.findOrAdd(stmt, stmt->getClassTypeId(), stmt->getOperand(0), stmt->getOperand(1));
    283282            case PabloAST::ClassTypeId::Sel:
     
    295294    FixedArgMap<PabloAST *, PabloAST *>                 mBinary;
    296295    FixedArgMap<PabloAST *, PabloAST *, PabloAST *>     mTernary;
    297     VarArgMap                                           mVariable;
     296    VarArgMap                                           mVariadic;
    298297};
    299298
  • icGREP/icgrep-devel/icgrep/pablo/function.cpp

    r5160 r5202  
    55namespace pablo {
    66
    7 Prototype::Prototype(const PabloAST::ClassTypeId type, std::string && name, const unsigned numOfParameters, const unsigned numOfResults, void * functionPtr)
    8 : PabloAST(type, nullptr)
    9 , mName(GlobalSymbolGenerator.get(name, false))
     7Prototype::Prototype(const PabloAST::ClassTypeId type, std::string && name, const unsigned numOfParameters, const unsigned numOfResults)
     8: PabloAST(type, nullptr, nullptr)
     9, mName(GlobalSymbolGenerator.get(name))
    1010, mNumOfParameters(numOfParameters)
    11 , mNumOfResults(numOfResults)
    12 , mFunctionPtr(functionPtr) {
     11, mNumOfResults(numOfResults) {
    1312
    1413}
    1514
    16 PabloFunction::PabloFunction(std::string && name, const unsigned numOfParameters, const unsigned numOfResults)
    17 : Prototype(ClassTypeId::Function, std::move(name), numOfParameters, numOfResults, nullptr)
     15PabloFunction::PabloFunction(std::string && name)
     16: Prototype(ClassTypeId::Function, std::move(name), 0, 0)
    1817, mSymbolTable(new SymbolGenerator())
    19 , mBitStreamType(getPabloType(PabloType::Stream, 1))
    2018, mEntryBlock(PabloBlock::Create(*this))
    21 , mParameters(numOfParameters, nullptr)
    22 , mResults(numOfResults, nullptr)
    2319, mConstants(0, nullptr) {
    2420
    2521}
    2622
    27 Zeroes * PabloFunction::getNullValue(const PabloType * type) {
     23Var * PabloFunction::addParameter(const std::string name, Type * const type) {
     24    Var * param = new Var(mSymbolTable->make(name), type);
     25    mParameters.push_back(param);
     26    mNumOfParameters = mParameters.size();
     27    return param;
     28}
     29
     30Var * PabloFunction::addResult(const std::string name, Type * const type) {
     31    Var * result = new Var(mSymbolTable->make(name), type);
     32    mResults.push_back(result);
     33    mNumOfResults = mResults.size();
     34    return result;
     35}
     36
     37Var * PabloFunction::makeVariable(PabloAST * name, Type * const type) {
     38    Var * const var = new Var(name, type);
     39    mVariables.push_back(var);
     40    return var;
     41}
     42
     43Zeroes * PabloFunction::getNullValue(Type * type) {
    2844    if (type == nullptr) {
    29         type = mBitStreamType;
     45        type = getStreamTy();
    3046    }
    3147    for (PabloAST * constant : mConstants) {
     
    3955}
    4056
    41 Ones * PabloFunction::getAllOnesValue(const PabloType * type) {
     57Ones * PabloFunction::getAllOnesValue(Type * type) {
    4258    if (type == nullptr) {
    43         type = mBitStreamType;
     59        type = getStreamTy();
    4460    }
    4561    for (PabloAST * constant : mConstants) {
  • icGREP/icgrep-devel/icgrep/pablo/function.h

    r5160 r5202  
    3838    }
    3939
    40     void * getFunctionPtr() const {
    41         return mFunctionPtr;
    42     }
    4340protected:
    44     Prototype(const PabloAST::ClassTypeId type, std::string && name, const unsigned numOfParameters, const unsigned numOfResults, void * functionPtr);
     41    Prototype(const PabloAST::ClassTypeId type, std::string && name, const unsigned numOfParameters, const unsigned numOfResults);
    4542protected:
    4643    const String * const    mName;
    47     const unsigned          mNumOfParameters;
    48     const unsigned          mNumOfResults;
    49     void *                  mFunctionPtr;
     44    unsigned                mNumOfParameters;
     45    unsigned                mNumOfResults;
    5046};
    5147
    52 inline Prototype * Prototype::Create(std::string name, const unsigned numOfParameters, const unsigned numOfResults, void * functionPtr) {
    53     return new Prototype(PabloAST::ClassTypeId::Prototype, std::move(name), numOfParameters, numOfResults, functionPtr);
     48inline Prototype * Prototype::Create(std::string name, const unsigned numOfParameters, const unsigned numOfResults, void *) {
     49    return new Prototype(PabloAST::ClassTypeId::Prototype, std::move(name), numOfParameters, numOfResults);
    5450}
    5551
    5652class PabloFunction : public Prototype {
    5753    friend class PabloBlock;
     54    friend class Branch;
    5855    using Allocator = SlabAllocator<PabloAST *>;
    5956public:
     
    7370    }
    7471
    75     static PabloFunction * Create(std::string name, const unsigned numOfParameters, const unsigned numOfResults);
     72    static PabloFunction * Create(std::string name);
    7673   
    7774    virtual bool operator==(const PabloAST & other) const {
     
    9491
    9592    Var * getParameter(const unsigned index) {
    96         if (LLVM_LIKELY(index < getNumOfParameters()))
    97             return cast<Var>(mParameters[index]);
    98         else throwInvalidParameterIndex(index);
     93        return static_cast<Var *>(mParameters[index]);
    9994    }
    10095
    10196    const Var * getParameter(const unsigned index) const {
    102         if (LLVM_LIKELY(index < getNumOfParameters()))
    103             return cast<Var>(mParameters[index]);
    104         else throwInvalidParameterIndex(index);
     97        return static_cast<Var *>(mParameters[index]);
    10598    }
    10699
    107     void setParameter(const unsigned index, Var * value) {
    108         if (LLVM_LIKELY(index < getNumOfParameters()))
    109             mParameters[index] = value;
    110         else throwInvalidParameterIndex(index);
     100    Var * addParameter(const std::string name, Type * const type);
     101
     102    Var * getResult(const unsigned index) {
     103        return static_cast<Var *>(mResults[index]);
    111104    }
    112105
    113     Assign * getResult(const unsigned index) {
    114         if (LLVM_LIKELY(index < getNumOfResults()))
    115             return cast<Assign>(mResults[index]);
    116         else throwInvalidResultIndex(index);
     106    const Var * getResult(const unsigned index) const {
     107        return static_cast<Var *>(mResults[index]);
    117108    }
    118109
    119     const Assign * getResult(const unsigned index) const {
    120         if (LLVM_LIKELY(index < getNumOfResults()))
    121             return cast<Assign>(mResults[index]);
    122         else throwInvalidResultIndex(index);
     110    Var * addResult(const std::string name, Type * const type);
     111
     112    Var * makeVariable(PabloAST * name, Type * const type);
     113
     114    Var * getVariable(const unsigned index) {
     115        return static_cast<Var *>(mVariables[index]);
    123116    }
    124117
    125     void setResult(const unsigned index, Assign * value) {       
    126         if (LLVM_LIKELY(index < getNumOfResults())) {
    127             if (LLVM_LIKELY(mResults[index] != value)) {
    128                 if (LLVM_UNLIKELY(mResults[index] != nullptr)) {
    129                     mResults[index]->removeUser(this);
    130                 }
    131                 mResults[index] = value;
    132                 value->addUser(this);
    133             }
    134         }
    135         else throwInvalidResultIndex(index);
     118    unsigned getNumOfVariables() {
     119        return mVariables.size();
    136120    }
    137121
    138     void setResultCount(Count * value) {
    139         value->addUser(this);
    140     }
    141    
    142     void setFunctionPtr(void * functionPtr) {
    143         mFunctionPtr = functionPtr;
    144     }
     122    Zeroes * getNullValue(Type * const type);
    145123
    146     Zeroes * getNullValue(const PabloType * const type);
    147 
    148     Ones * getAllOnesValue(const PabloType * const type);
     124    Ones * getAllOnesValue(Type * const type);
    149125
    150126    void operator delete (void*);
     
    162138    __attribute__((noreturn)) void throwInvalidResultIndex(const unsigned index) const;
    163139
    164     PabloFunction(std::string && name, const unsigned numOfParameters, const unsigned numOfResults);
     140    PabloFunction(std::string && name);
    165141private:
    166142    SymbolGenerator *                           mSymbolTable;
    167     const PabloType *                           mBitStreamType;
    168143    PabloBlock *                                mEntryBlock;
    169144    std::vector<PabloAST *, Allocator>          mParameters;
    170145    std::vector<PabloAST *, Allocator>          mResults;
    171146    std::vector<PabloAST *, Allocator>          mConstants;
     147    std::vector<PabloAST *, Allocator>          mVariables;
    172148};
    173149
    174 inline PabloFunction * PabloFunction::Create(std::string name, const unsigned numOfParameters, const unsigned numOfResults) {
    175     return new PabloFunction(std::move(name), numOfParameters, numOfResults);
     150inline PabloFunction * PabloFunction::Create(std::string name) {
     151    return new PabloFunction(std::move(name));
    176152}
    177153   
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

    r5160 r5202  
    145145 ** ------------------------------------------------------------------------------------------------------------- */
    146146template <class Type>
    147 inline bool intersects(const Type & A, const Type & B) {
     147inline bool intersects(Type & A, Type & B) {
    148148    auto first1 = A.begin(), last1 = A.end();
    149149    auto first2 = B.begin(), last2 = B.end();
     
    325325    const auto offset = mRefs.size();
    326326    for (Statement * stmt = block->front(); stmt; ) {
    327         if (LLVM_UNLIKELY(isa<If>(stmt))) {
    328             if (LLVM_UNLIKELY(isa<Zeroes>(cast<If>(stmt)->getCondition()))) {
     327        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     328            if (LLVM_UNLIKELY(isa<Zeroes>(cast<Branch>(stmt)->getCondition()))) {
    329329                stmt = stmt->eraseFromParent(true);
    330330            } else {
    331331                CharacterizationMap nested(C);
    332                 processScopes(cast<If>(stmt)->getBody(), nested);
    333                 for (Assign * def : cast<If>(stmt)->getDefined()) {
     332                processScopes(cast<Branch>(stmt)->getBody(), nested);
     333                for (Var * def : cast<Branch>(stmt)->getEscaped()) {
    334334                    C.add(def, makeVar());
    335                 }
    336                 stmt = stmt->getNextNode();
    337             }
    338         } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
    339             if (LLVM_UNLIKELY(isa<Zeroes>(cast<While>(stmt)->getCondition()))) {
    340                 stmt = stmt->eraseFromParent(true);
    341             } else {
    342                 CharacterizationMap nested(C);
    343                 processScopes(cast<While>(stmt)->getBody(), nested);
    344                 for (Next * var : cast<While>(stmt)->getVariants()) {
    345                     C.add(var, makeVar());
    346335                }
    347336                stmt = stmt->getNextNode();
     
    409398        check[1] = isa<InFile>(stmt) ? mInFile : Z3_mk_not(mContext, mInFile); assert (check[1]);
    410399        node = Z3_mk_and(mContext, 2, check);
    411     } else if (LLVM_UNLIKELY(isa<Assign>(stmt) || isa<Next>(stmt))) {
     400    } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
    412401        return stmt->getNextNode();
    413402    }  else {
     
    526515            }
    527516            if (LLVM_UNLIKELY(isa<If>(stmt))) {
    528                 for (Assign * def : cast<const If>(stmt)->getDefined()) {
     517                for (Var * def : cast<If>(stmt)->getEscaped()) {
    529518                    const Vertex v = makeVertex(TypeId::Var, def, C, S, M, G);
    530519                    add_edge(def, u, v, G);
     
    537526                // we make the loop dependent on the original value of each Next node and
    538527                // the Next node dependent on the loop.
    539                 for (Next * var : cast<const While>(stmt)->getVariants()) {
     528                for (Var * var : cast<While>(stmt)->getEscaped()) {
    540529                    const Vertex v = makeVertex(TypeId::Var, var, C, S, M, G);
    541530                    assert (in_degree(v, G) == 1);
     
    574563            if (LLVM_UNLIKELY(parent != mBlock)) {
    575564                for (;;) {
    576                     if (parent->getPredecessor () == mBlock) {
     565                    if (parent->getPredecessor() == mBlock) {
    577566                        Statement * const branch = parent->getBranch();
    578567                        if (LLVM_UNLIKELY(branch != ignoreIfThis)) {
     
    585574                        break;
    586575                    }
    587                     parent = parent->getPredecessor ();
     576                    parent = parent->getPredecessor();
    588577                    if (LLVM_UNLIKELY(parent == nullptr)) {
    589                         assert (isa<Assign>(expr) || isa<Next>(expr));
     578                        assert (isa<Assign>(expr));
    590579                        break;
    591580                    }
     
    811800            continue;
    812801        } else if (isDistributive(G[u])) {
    813             const TypeId outerTypeId = getType(G[u]);
    814             const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
     802            TypeId outerTypeId = getType(G[u]);
     803            TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
    815804            flat_set<Vertex> distributable;
    816805            for (auto e : make_iterator_range(in_edges(u, G))) {
     
    855844 * @brief recomputeDefinition
    856845 ** ------------------------------------------------------------------------------------------------------------- */
    857 inline Z3_ast BooleanReassociationPass::computeDefinition(const TypeId typeId, const Vertex u, Graph & G, const bool use_expensive_minimization) const {
     846inline Z3_ast BooleanReassociationPass::computeDefinition(TypeId typeId, const Vertex u, Graph & G, const bool use_expensive_minimization) const {
    858847    const unsigned n = in_degree(u, G);
    859848    Z3_ast operands[n];
     
    876865 * Apply the distribution law to reduce computations whenever possible.
    877866 ** ------------------------------------------------------------------------------------------------------------- */
    878 Vertex BooleanReassociationPass::updateIntermediaryDefinition(const TypeId typeId, const Vertex u, VertexMap & M, Graph & G) {
     867Vertex BooleanReassociationPass::updateIntermediaryDefinition(TypeId typeId, const Vertex u, VertexMap & M, Graph & G) {
    879868
    880869    Z3_ast def = computeDefinition(typeId, u, G);
     
    914903 * Apply the distribution law to reduce computations whenever possible.
    915904 ** ------------------------------------------------------------------------------------------------------------- */
    916 Vertex BooleanReassociationPass::updateSinkDefinition(const TypeId typeId, const Vertex u, CharacterizationMap & C, VertexMap & M, Graph & G) {
     905Vertex BooleanReassociationPass::updateSinkDefinition(TypeId typeId, const Vertex u, CharacterizationMap & C, VertexMap & M, Graph & G) {
    917906
    918907    Z3_ast const def = computeDefinition(typeId, u, G);
     
    10611050            const VertexSet & sinks = std::get<2>(set);
    10621051
    1063             const TypeId outerTypeId = getType(G[H[sinks.front()]]);
     1052            TypeId outerTypeId = getType(G[H[sinks.front()]]);
    10641053            assert (outerTypeId == TypeId::And || outerTypeId == TypeId::Or);
    1065             const TypeId innerTypeId = (outerTypeId == TypeId::Or) ? TypeId::And : TypeId::Or;
     1054            TypeId innerTypeId = (outerTypeId == TypeId::Or) ? TypeId::And : TypeId::Or;
    10661055
    10671056            const Vertex x = makeVertex(outerTypeId, nullptr, G);
     
    11181107    switch (getType(data)) {
    11191108        case TypeId::Assign:
    1120         case TypeId::Next:
    11211109        case TypeId::If:
    11221110        case TypeId::While:
     
    12181206 * @brief factorGraph
    12191207 ** ------------------------------------------------------------------------------------------------------------- */
    1220 bool BooleanReassociationPass::factorGraph(const TypeId typeId, Graph & G, std::vector<Vertex> & factors) const {
     1208bool BooleanReassociationPass::factorGraph(TypeId typeId, Graph & G, std::vector<Vertex> & factors) const {
    12211209
    12221210    if (LLVM_UNLIKELY(factors.empty())) {
     
    15881576* @brief makeVertex
    15891577** ------------------------------------------------------------------------------------------------------------- */
    1590 Vertex BooleanReassociationPass::makeVertex(const TypeId typeId, PabloAST * const expr, CharacterizationMap & C, StatementMap & S, VertexMap & M, Graph & G) {
     1578Vertex BooleanReassociationPass::makeVertex(TypeId typeId, PabloAST * const expr, CharacterizationMap & C, StatementMap & S, VertexMap & M, Graph & G) {
    15911579    assert (expr);
    15921580    const auto f = S.find(expr);
     
    16071595 * @brief makeVertex
    16081596 ** ------------------------------------------------------------------------------------------------------------- */
    1609 Vertex BooleanReassociationPass::makeVertex(const TypeId typeId, PabloAST * const expr, StatementMap & M, Graph & G, Z3_ast node) {
     1597Vertex BooleanReassociationPass::makeVertex(TypeId typeId, PabloAST * const expr, StatementMap & M, Graph & G, Z3_ast node) {
    16101598    assert (expr);
    16111599    const auto f = M.find(expr);
     
    16221610 * @brief makeVertex
    16231611 ** ------------------------------------------------------------------------------------------------------------- */
    1624 Vertex BooleanReassociationPass::makeVertex(const TypeId typeId, PabloAST * const expr, Graph & G, Z3_ast node) {
     1612Vertex BooleanReassociationPass::makeVertex(TypeId typeId, PabloAST * const expr, Graph & G, Z3_ast node) {
    16251613//    for (Vertex u : make_iterator_range(vertices(G))) {
    16261614//        if (LLVM_UNLIKELY(in_degree(u, G) == 0 && out_degree(u, G) == 0)) {
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r5160 r5202  
    5656    void reduceVertex(const Vertex u, CharacterizationMap & C, VertexMap & M, Graph & G);
    5757
    58     bool factorGraph(const TypeId typeId, Graph & G, std::vector<Vertex> & factors) const;
     58    bool factorGraph(TypeId typeId, Graph & G, std::vector<Vertex> & factors) const;
    5959    bool factorGraph(Graph & G) const;
    6060
    61     static Vertex makeVertex(const TypeId typeId, PabloAST * const expr, Graph & G, Z3_ast node = nullptr);
    62     static Vertex makeVertex(const TypeId typeId, PabloAST * const expr, StatementMap & M, Graph & G, Z3_ast node = nullptr);
    63     static Vertex makeVertex(const TypeId typeId, PabloAST * const expr, CharacterizationMap & C, StatementMap & S, VertexMap & M, Graph & G);
     61    static Vertex makeVertex(TypeId typeId, PabloAST * const expr, Graph & G, Z3_ast node = nullptr);
     62    static Vertex makeVertex(TypeId typeId, PabloAST * const expr, StatementMap & M, Graph & G, Z3_ast node = nullptr);
     63    static Vertex makeVertex(TypeId typeId, PabloAST * const expr, CharacterizationMap & C, StatementMap & S, VertexMap & M, Graph & G);
    6464
    6565    void removeVertex(const Vertex u, VertexMap & M, Graph & G) const;
    6666    void removeVertex(const Vertex u, Graph & G) const;
    6767
    68     Z3_ast computeDefinition(const TypeId typeId, const Vertex u, Graph & G, const bool use_expensive_minimization = false) const;
    69     Vertex updateIntermediaryDefinition(const TypeId typeId, const Vertex u, VertexMap & M, Graph & G);
    70     Vertex updateSinkDefinition(const TypeId typeId, const Vertex u, CharacterizationMap &C, VertexMap & M, Graph & G);
     68    Z3_ast computeDefinition(TypeId typeId, const Vertex u, Graph & G, const bool use_expensive_minimization = false) const;
     69    Vertex updateIntermediaryDefinition(TypeId typeId, const Vertex u, VertexMap & M, Graph & G);
     70    Vertex updateSinkDefinition(TypeId typeId, const Vertex u, CharacterizationMap &C, VertexMap & M, Graph & G);
    7171    bool redistributeGraph(CharacterizationMap & C, VertexMap & M, Graph & G);
    7272
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/codemotionpass.cpp

    r5160 r5202  
    3939        }
    4040    }
    41     reschedule(block);
    4241}
    4342
    4443/** ------------------------------------------------------------------------------------------------------------- *
    45  * @brief isSafeToMove
    46  ** ------------------------------------------------------------------------------------------------------------- */
    47 inline static bool isSafeToMove(Statement * stmt) {
    48     return !isa<Assign>(stmt) && !isa<Next>(stmt);
    49 }
    50 
    51 /** ------------------------------------------------------------------------------------------------------------- *
    52  * @brief calculateDepthToCurrentBlock
     44 * @brief depthTo
    5345 ** ------------------------------------------------------------------------------------------------------------- */
    5446inline static unsigned depthTo(const PabloBlock * scope, const PabloBlock * const root) {
     
    5749        ++depth;
    5850        assert (scope);
    59         scope = scope->getPredecessor ();
     51        scope = scope->getPredecessor();
    6052    }
    6153    return depth;
     
    6658 ** ------------------------------------------------------------------------------------------------------------- */
    6759template <class ScopeSet>
    68 inline bool findScopeUsages(Statement * stmt, ScopeSet & scopeSet, const PabloBlock * const block, const PabloBlock * const blocker) {
    69     for (PabloAST * use : stmt->users()) {
     60inline bool findScopeUsages(PabloAST * expr, ScopeSet & scopeSet, const PabloBlock * const block, const PabloBlock * const blocker) {
     61    for (PabloAST * use : expr->users()) {
    7062        assert (isa<Statement>(use));
    7163        PabloBlock * const parent = cast<Statement>(use)->getParent();
     
    8779    // find the least common ancestor of the scope blocks. If it is not the current scope,
    8880    // then we can sink the instruction.
    89     if (isa<If>(stmt)) {
    90         for (Assign * def : cast<If>(stmt)->getDefined()) {
    91             if (!findScopeUsages(def, scopeSet, block, cast<If>(stmt)->getBody())) {
     81    assert (scopeSet.empty());
     82    if (isa<Branch>(stmt)) {
     83        for (Var * def : cast<Branch>(stmt)->getEscaped()) {
     84            if (!findScopeUsages(def, scopeSet, block, cast<Branch>(stmt)->getBody())) {
    9285                return false;
    9386            }
    9487        }
    95     } else if (isa<While>(stmt)) {
    96         for (Next * var : cast<While>(stmt)->getVariants()) {
    97             if (escapes(var) && !findScopeUsages(var, scopeSet, block, cast<While>(stmt)->getBody())) {
    98                 return false;
    99             }
    100         }
    101     } else if (isSafeToMove(stmt)) {
     88    } else if (!isa<Assign>(stmt)) {
    10289        return findScopeUsages(stmt, scopeSet, block, nullptr);
    10390    }
     
    126113                // the scope tree until both scopes are at the same depth.
    127114                while (depth1 > depth2) {
    128                     scope1 = scope1->getPredecessor ();
     115                    scope1 = scope1->getPredecessor();
    129116                    --depth1;
    130117                }
    131118                while (depth1 < depth2) {
    132                     scope2 = scope2->getPredecessor ();
     119                    scope2 = scope2->getPredecessor();
    133120                    --depth2;
    134121                }
     
    138125                while (scope1 != scope2) {
    139126                    assert (scope1 && scope2);
    140                     scope1 = scope1->getPredecessor ();
    141                     scope2 = scope2->getPredecessor ();
     127                    scope1 = scope1->getPredecessor();
     128                    scope2 = scope2->getPredecessor();
    142129                }
    143130                assert (scope1);
     
    149136            }
    150137            assert (scopes.size() == 1);
    151             assert (isa<If>(stmt) ? (cast<If>(stmt)->getBody() != scopes.front()) : true);
    152             assert (isa<While>(stmt) ? (cast<While>(stmt)->getBody() != scopes.front()) : true);
     138            assert (isa<Branch>(stmt) ? (cast<Branch>(stmt)->getBody() != scopes.front()) : true);
    153139            stmt->insertBefore(scopes.front()->front());
    154140        }
     
    163149void CodeMotionPass::hoistLoopInvariants(While * loop) {
    164150    flat_set<const PabloAST *> loopVariants;
    165     for (Next * variant : loop->getVariants()) {
     151    for (Var * variant : loop->getEscaped()) {
    166152        loopVariants.insert(variant);
    167         loopVariants.insert(variant->getInitial());
    168153    }
    169154    Statement * outerNode = loop->getPrevNode();
    170155    Statement * stmt = loop->getBody()->front();
    171156    while (stmt) {
    172         if (isa<If>(stmt)) {
    173             for (Assign * def : cast<If>(stmt)->getDefined()) {
    174                 loopVariants.insert(def);
    175             }
    176         } else if (isa<While>(stmt)) {
    177             for (Next * var : cast<While>(stmt)->getVariants()) {
     157        if (isa<Branch>(stmt)) {
     158            for (Var * var : cast<Branch>(stmt)->getEscaped()) {
    178159                loopVariants.insert(var);
    179160            }
     
    199180}
    200181
    201 /** ------------------------------------------------------------------------------------------------------------- *
    202  * @brief reschedule
    203  ** ------------------------------------------------------------------------------------------------------------- */
    204 void CodeMotionPass::reschedule(PabloBlock * const block) {
    205 
    206 //    using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, Statement *>;
    207 //    using Vertex = Graph::vertex_descriptor;
    208 //    using Map = flat_map<Statement *, Vertex>;
    209 
    210 //    const unsigned size = std::distance(block->begin(), block->end());
    211 
    212 //    Graph G(size);
    213 //    Map M;
    214 
    215 //    M.reserve(size);
    216 
    217 //    unsigned i = 0;
    218 //    for (Statement * stmt : *block) {
    219 //        G[i] = stmt;
    220 //        M.emplace(stmt, i);
    221 //        ++i;
    222 //    }
    223 
    224 //    i = 0;
    225 //    for (Statement * stmt : *block) {
    226 //        for (PabloAST * user : stmt->users()) {
    227 //            if (isa<Statement>(user)) {
    228 //                Statement * use = cast<Statement>(user);
    229 //                PabloBlock * parent = use->getParent();
    230 //                while (parent) {
    231 //                    if (parent == block) {
    232 //                        break;
    233 //                    }
    234 //                    use = parent->getBranch();
    235 //                    parent = parent->getParent();
    236 //                }
    237 //                auto f = M.find(use);
    238 //                assert (f != M.end());
    239 //                add_edge(i, f->second, G);
    240 //            }
    241 //        }
    242 //        ++i;
    243 //    }
    244 
    245 //    circular_buffer<Vertex> ordering(size);
    246 //    std::vector<unsigned> cumulativeDependencies;
    247 //    topological_sort(G, std::back_inserter(ordering));
    248    
    249 
    250 
    251182}
    252 
    253 }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/codemotionpass.h

    r4927 r5202  
    3535    static void sink(PabloBlock * const block);
    3636    static void hoistLoopInvariants(While * loop);
    37 
    38     static void reschedule(PabloBlock * const block);
    3937};
    4038
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.cpp

    r5160 r5202  
    3131 ** ------------------------------------------------------------------------------------------------------------- */
    3232template <class Type>
    33 inline bool intersects(const Type & A, const Type & B) {
     33inline bool intersects(Type & A, Type & B) {
    3434    auto first1 = A.begin(), last1 = A.end();
    3535    auto first2 = B.begin(), last2 = B.end();
     
    239239inline unsigned scopeDepthOf(const PabloBlock * block) {
    240240    unsigned depth = 0;
    241     for (; block; ++depth, block = block->getPredecessor ());
     241    for (; block; ++depth, block = block->getPredecessor());
    242242    return depth;
    243243}
     
    267267        // the scope tree until both scopes are at the same depth.
    268268        while (depth1 > depth2) {
    269             scope1 = scope1->getPredecessor ();
     269            scope1 = scope1->getPredecessor();
    270270            --depth1;
    271271        }
    272272        while (depth1 < depth2) {
    273             scope2 = scope2->getPredecessor ();
     273            scope2 = scope2->getPredecessor();
    274274            --depth2;
    275275        }
     
    278278        // the LCA of our original pair.
    279279        while (scope1 != scope2) {
    280             scope1 = scope1->getPredecessor ();
    281             scope2 = scope2->getPredecessor ();
     280            scope1 = scope1->getPredecessor();
     281            scope2 = scope2->getPredecessor();
    282282        }
    283283        assert (scope1 && scope2);
     
    297297            assert (scope);
    298298            user = scope->getBranch();
    299             scope = scope->getPredecessor ();
     299            scope = scope->getPredecessor();
    300300        }
    301301        usages.insert(user);
     
    318318static inline void computeDistributionGraph(Variadic * const expr, Graph & G, VertexSet & A) {
    319319
    320     const TypeId outerTypeId = expr->getClassTypeId();
    321     const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
     320    TypeId outerTypeId = expr->getClassTypeId();
     321    TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
    322322
    323323    assert (isa<And>(expr) || isa<Or>(expr));
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r5160 r5202  
    9292                optimize(cast<If>(stmt)->getBody());
    9393            } else if (isa<While>(stmt)) {
    94                 for (const Next * var : cast<While>(stmt)->getVariants()) {
    95                     Z3_inc_ref(mContext, get(var->getInitial()));
     94                for (const Var * var : cast<While>(stmt)->getEscaped()) {
     95                    Z3_inc_ref(mContext, get(var));
    9696                }
    9797                optimize(cast<While>(stmt)->getBody());
    9898                // since we cannot be certain that we'll always execute at least one iteration of a loop, we must
    9999                // assume that the variants could either be their initial or resulting value.
    100                 for (const Next * var : cast<While>(stmt)->getVariants()) {
    101                     Z3_ast v0 = get(var->getInitial());
     100                for (const Var * var : cast<While>(stmt)->getEscaped()) {
     101                    Z3_ast v0 = get(var);
    102102                    Z3_ast & v1 = get(var);
    103103                    Z3_ast merge[2] = { v0, v1 };
     
    172172    switch (stmt->getClassTypeId()) {
    173173        case TypeId::Assign:
    174         case TypeId::Next:
    175174        case TypeId::AtEOF:
    176175        case TypeId::InFile:
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.cpp

    r4880 r5202  
    110110        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
    111111            eliminateLogicallyEquivalentStatements(cast<While>(stmt)->getBody(), map);
    112             for (Next * var : cast<const While>(stmt)->getVariants()) {
    113                 if (!escapes(var)) {
    114                     bdd_delref(mCharacterizationMap[var]);
    115                     mCharacterizationMap.erase(var);
    116                 }
     112            for (Var * var : cast<const While>(stmt)->getVariants()) {
     113                bdd_delref(mCharacterizationMap[var]);
     114                mCharacterizationMap.erase(var);
    117115            }
    118116        } else { // attempt to characterize this statement and replace it if we've encountered an equivalent one
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r5160 r5202  
    33#include <pablo/expression_map.hpp>
    44#include <pablo/function.h>
    5 #include <pablo/printer_pablos.h>
    65#include <pablo/analysis/pabloverifier.hpp>
    76#include <boost/container/flat_set.hpp>
    8 
     7#include <boost/container/flat_map.hpp>
    98#include <pablo/printer_pablos.h>
    109#include <iostream>
    1110
     11using namespace boost;
     12using namespace boost::container;
     13
    1214namespace pablo {
    13 
    14 template <typename Type>
    15 using SmallSet = boost::container::flat_set<Type>;
    1615
    1716using TypeId = PabloAST::ClassTypeId;
     
    7675        // Apply an implicit distribution + identity law whenever possible
    7776        //    (P ∧ Q) √ (P ∧ ¬Q) = P √ (Q ∧ ¬Q) ⇔ P
    78         const TypeId typeId = isa<And>(var) ? TypeId::Or : TypeId::And;
    79         for (unsigned i = 1; i < var->getNumOperands(); ++i) {
     77        TypeId typeId = isa<And>(var) ? TypeId::Or : TypeId::And;
     78        for (unsigned i = 0; i < var->getNumOperands(); ++i) {
    8079            if (var->getOperand(i)->getClassTypeId() == typeId) {
    8180                Variadic * const Vi = cast<Variadic>(var->getOperand(i));
    82                 if (LLVM_UNLIKELY(!std::is_sorted(Vi->begin(), Vi->end()))) {
    83                     std::sort(Vi->begin(), Vi->end());
    84                 }
     81                // Ensure the i-th operand is sorted incase it was altered after being folded.
     82                std::sort(Vi->begin(), Vi->end());
    8583                for (unsigned j = 0; j < i; ++j) {
    8684                    assert (var->getOperand(i) == Vi);
    8785                    if (var->getOperand(j)->getClassTypeId() == typeId) {
    8886                        Variadic * const Vj = cast<Variadic>(var->getOperand(j));
    89                         if (LLVM_UNLIKELY(!std::is_sorted(Vj->begin(), Vj->end()))) {
    90                             std::sort(Vj->begin(), Vj->end());
    91                         }
     87                        assert (std::is_sorted(Vj->begin(), Vj->end()));
    9288                        if (Vi->getNumOperands() == Vj->getNumOperands()) {
    93                             // If vi and vj differ by precisely one operand, say di and dj, and di ⇔ ¬dj, we can apply this rule.
     89                            // If vi and vj differ by precisely one operand, say di and dj,
     90                            // and di ⇔ ¬dj, we can apply this rule.
    9491                            unsigned vi = 0, vj = 0;
    9592                            const unsigned operands = Vi->getNumOperands();
     
    269266            if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(i)))) {
    270267                switch (stmt->getClassTypeId()) {
    271                     case PabloAST::ClassTypeId::Sel:
     268                    case TypeId::Sel:
    272269                        block->setInsertPoint(stmt->getPrevNode());
    273270                        switch (i) {
     
    276273                            case 2: return block->createAnd(stmt->getOperand(0), stmt->getOperand(1));
    277274                        }
    278                     case PabloAST::ClassTypeId::ScanThru:
    279                     case PabloAST::ClassTypeId::MatchStar:
     275                    case TypeId::ScanThru:
     276                    case TypeId::MatchStar:
    280277                        return stmt->getOperand(0);
    281278                    default: break;
     
    283280            } else if (LLVM_UNLIKELY(isa<Ones>(stmt->getOperand(i)))) {
    284281                switch (stmt->getClassTypeId()) {
    285                     case PabloAST::ClassTypeId::Sel:
     282                    case TypeId::Sel:
    286283                        block->setInsertPoint(stmt->getPrevNode());
    287284                        switch (i) {
     
    290287                            case 2: return block->createOr(block->createNot(stmt->getOperand(0)), stmt->getOperand(1));
    291288                        }
    292                     case PabloAST::ClassTypeId::ScanThru:
     289                    case TypeId::ScanThru:
    293290                        if (LLVM_UNLIKELY(i == 1)) {
    294291                            return block->createZeroes(stmt->getType());
    295292                        }
    296293                        break;
    297                     case PabloAST::ClassTypeId::MatchStar:
     294                    case TypeId::MatchStar:
    298295                        if (LLVM_UNLIKELY(i == 0)) {
    299296                            return block->createOnes(stmt->getType());
     
    306303    }
    307304    return nullptr;
    308 }
    309 
    310 /** ------------------------------------------------------------------------------------------------------------- *
    311  * @brief isSuperfluous
    312  ** ------------------------------------------------------------------------------------------------------------- */
    313 inline bool Simplifier::isSuperfluous(const Assign * const assign) {
    314     if (LLVM_LIKELY(isa<Statement>(assign->getExpression()))) {
    315         for (const PabloAST * user : assign->users()) {
    316             if (LLVM_UNLIKELY(isa<PabloFunction>(user) || isa<Next>(user))) {
    317                 return false;
    318             } else if (isa<If>(user)) {
    319                 if (LLVM_UNLIKELY(cast<If>(user)->getCondition() == assign)) {
    320                     continue;
    321                 } else if (isa<Assign>(assign->getExpression())) {
    322                     continue;
    323                 }
    324                 return false;
    325             }
    326         }
    327     }
    328     return true;
    329 }
    330 
    331 /** ------------------------------------------------------------------------------------------------------------- *
    332  * @brief demoteDefinedVar
    333  ** ------------------------------------------------------------------------------------------------------------- */
    334 inline bool demoteDefinedVar(const If * ifNode, const Assign * def) {
    335     // If this value isn't used outside of this scope then there is no reason to allow it to escape it.
    336     if (!escapes(def)) {
    337         return true;
    338     }
    339     // Similarly if the defined variable is equivalent to the condition, an equivalent value is already available.
    340     if (ifNode->getCondition() == def->getExpression()) {
    341         return true;
    342     }
    343     // Finally, if the assignment is a constant, it's already known.
    344     if (isa<Zeroes>(def->getExpression()) || isa<Ones>(def->getExpression()))  {
    345         return true;
    346     }
    347     return false;
    348 }
    349 
    350 /** ------------------------------------------------------------------------------------------------------------- *
    351  * @brief replaceReachableUsersOfWith
    352  ** ------------------------------------------------------------------------------------------------------------- */
    353 inline void replaceReachableUsersOfWith(Statement * stmt, PabloAST * expr) {
    354     const PabloBlock * const root = stmt->getParent();
    355     SmallSet<const PabloBlock *> forbidden;
    356     for (PabloAST * use : stmt->users()) {
    357         if (LLVM_UNLIKELY(isa<Next>(use))) {
    358             const PabloBlock * parent = cast<Next>(use)->getParent();
    359             if (parent != root) {
    360                 forbidden.insert(parent);
    361             }
    362         }
    363     }
    364     for (PabloAST * use : stmt->users()) {
    365         if (Statement * user = dyn_cast<Statement>(use)) {
    366             const PabloBlock * parent = user->getParent();
    367             while (parent && forbidden.count(parent) == 0) {
    368                 if (LLVM_UNLIKELY(parent == root)) {
    369                     user->replaceUsesOfWith(stmt, expr);
    370                     break;
    371                 }
    372                 parent = parent->getPredecessor ();
    373             }
    374         }
    375     }
    376305}
    377306
     
    380309 *
    381310 * If this inner block is composed of only Boolean logic and Assign statements and there are fewer than 3
    382  * statements, just add the statements in the inner block to the current block->
     311 * statements, just add the statements in the inner block to the current block
    383312 ** ------------------------------------------------------------------------------------------------------------- */
    384313inline bool discardNestedIfBlock(const PabloBlock * const block) {
     
    386315    for (const Statement * stmt : *block) {
    387316        switch (stmt->getClassTypeId()) {
    388             case PabloAST::ClassTypeId::And:
    389             case PabloAST::ClassTypeId::Or:
    390             case PabloAST::ClassTypeId::Xor:
     317            case TypeId::And:
     318            case TypeId::Or:
     319            case TypeId::Xor:
    391320                if (++computations > 3) {
    392321                    return false;
    393322                }
    394             case PabloAST::ClassTypeId::Not:
    395             case PabloAST::ClassTypeId::Assign:
     323            case TypeId::Not:
     324            case TypeId::Assign:
    396325                break;
    397326            default:
     
    403332
    404333/** ------------------------------------------------------------------------------------------------------------- *
    405  * @brief removeIdenticalEscapedValues
    406  ** ------------------------------------------------------------------------------------------------------------- */
    407 template <class ValueList, class ValueType = typename ValueList::value_type>
    408 inline void removeIdenticalEscapedValues(ValueList & list) {
    409     std::vector<ValueType> identicalValues;
    410     for (auto i = list.begin(); i != list.end(); ++i) {
    411         for (auto j = i + 1; j != list.end(); ++j) {
    412             if (LLVM_UNLIKELY(equals(*i, *j))) {
    413                 identicalValues.push_back(*j);
    414             }
    415         }
    416         for (ValueType identicalValue : identicalValues) {
    417             identicalValue->replaceWith(*i);
    418         }
    419         identicalValues.clear();
    420     }
    421 }
     334 * @brief VariableTable
     335 ** ------------------------------------------------------------------------------------------------------------- */
     336struct Simplifier::VariableTable {
     337
     338    VariableTable(VariableTable * predecessor = nullptr)
     339    : mPredecessor(predecessor) {
     340
     341    }
     342
     343    PabloAST * get(PabloAST * const var) const {
     344        const auto f = mMap.find(var);
     345        if (f == mMap.end()) {
     346            return (mPredecessor) ? mPredecessor->get(var) : nullptr;
     347        }
     348        return f->second;
     349    }
     350
     351    void put(PabloAST * const var, PabloAST * value) {
     352        const auto f = mMap.find(var);
     353        if (LLVM_LIKELY(f == mMap.end())) {
     354            mMap.emplace(var, value);
     355        } else {
     356            f->second = value;
     357        }
     358        assert (get(var) == value);
     359    }
     360
     361private:
     362    VariableTable * const mPredecessor;
     363    flat_map<PabloAST *, PabloAST *> mMap;
     364};
    422365
    423366/** ------------------------------------------------------------------------------------------------------------- *
     
    427370 * as replacements. Let the DCE remove the unnecessary statements with the finalized Def-Use information.
    428371 ** ------------------------------------------------------------------------------------------------------------- */
    429 void Simplifier::redundancyElimination(PabloFunction & function, PabloBlock * const block, ExpressionTable * predecessor) {
    430     ExpressionTable encountered(predecessor);
     372void Simplifier::redundancyElimination(PabloBlock * const block, ExpressionTable * const et, VariableTable * const vt) {
     373    ExpressionTable expressions(et);
     374    VariableTable variables(vt);
     375
     376    // When processing a While body, we cannot use its initial value from the outer
     377    // body since the Var will likely be assigned a different value in the current
     378    // body that should be used on the subsequent iteration of the loop.
     379    if (While * br = dyn_cast_or_null<While>(block->getBranch())) {
     380        for (Var * var : br->getEscaped()) {
     381            variables.put(var, var);
     382        }
     383    }
     384
    431385    Statement * stmt = block->front();
    432386    while (stmt) {
    433         if (Assign * assign = dyn_cast<Assign>(stmt)) {
    434             // If we have an Assign whose users do not contain an If or Next node, we can replace its users with
    435             // the Assign's expression directly.
    436             if (isSuperfluous(assign)) {
    437                 stmt = assign->replaceWith(assign->getExpression());
    438                 continue;
    439             }
    440             // Force the uses of an Assign node that can reach the original expression to use the expression instead.
    441             replaceReachableUsersOfWith(assign, assign->getExpression());
    442         } else if (Next * next = dyn_cast<Next>(stmt)) {
    443             replaceReachableUsersOfWith(next, next->getExpr());
    444         } else if (If * ifNode = dyn_cast<If>(stmt)) {
    445             // Test whether we can ever take this branch
    446             if (LLVM_UNLIKELY(isa<Zeroes>(cast<If>(stmt)->getCondition()))) {
     387
     388        if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     389            Assign * const assign = cast<Assign>(stmt);
     390            PabloAST * const var = assign->getVariable();
     391            PabloAST * value = assign->getValue();
     392            while (LLVM_UNLIKELY(isa<Var>(value))) {
     393                PabloAST * next = variables.get(cast<Var>(value));
     394                if (LLVM_LIKELY(next == nullptr || next == value)) {
     395                    break;
     396                }
     397                value = next;
     398                assign->setValue(value);
     399            }
     400            if (LLVM_UNLIKELY(variables.get(var) == value)) {
    447401                stmt = stmt->eraseFromParent();
    448402                continue;
    449403            }
    450             // Test whether all of the defined variables are necessary
    451             If::DefinedVars & defs = ifNode->getDefined();
    452             for (auto def = defs.begin(); def != defs.end(); ) {
    453                 if (LLVM_UNLIKELY(demoteDefinedVar(ifNode, *def))) {
    454                     (*def)->replaceWith((*def)->getExpression());
    455                     def = ifNode->removeDefined(*def);
    456                     continue;
    457                 }
    458                 ++def;
    459             }
    460 
    461             // Process the If body
    462             redundancyElimination(function, cast<If>(stmt)->getBody(), &encountered);
    463 
    464             // If we ended up removing all of the defined variables, delete the If node.
    465             if (LLVM_UNLIKELY(defs.empty())) {
     404            variables.put(var, value);
     405        } else if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     406
     407            Branch * const br = cast<Branch>(stmt);
     408
     409            // Test whether we can ever take this branch
     410            PabloAST * cond = br->getCondition();
     411            if (isa<Var>(cond)) {
     412                PabloAST * const value = variables.get(cast<Var>(cond));
     413                if (value) {
     414                    cond = value;
     415                    // TODO: verify this works for a nested If node within a While body.
     416                    if (isa<If>(br)) {
     417                        br->setCondition(cond);
     418                    }
     419                }
     420            }
     421
     422            if (LLVM_UNLIKELY(isa<Zeroes>(cond))) {
    466423                stmt = stmt->eraseFromParent();
    467424                continue;
    468425            }
    469426
    470             // Otherwise check if we any Assign reports the same value as another. If so, replace all uses of the
    471             // second with the first. This will simplify future analysis.
    472             removeIdenticalEscapedValues(ifNode->getDefined());
    473 
    474             // Finally after we've eliminated everything we can from the If body, check whether testing the If
    475             // condition will meet or exceed the cost of executing the body.
    476             if (LLVM_UNLIKELY(discardNestedIfBlock(ifNode->getBody()))) {
    477                 Statement * nested = ifNode->getBody()->front();
     427            // Process the Branch body
     428            redundancyElimination(br->getBody(), &expressions, &variables);
     429
     430            // Check whether this If branch has enough operations nested within it to
     431            // be worth the cost of the branch.
     432            if (LLVM_UNLIKELY(isa<If>(br) && discardNestedIfBlock(br->getBody()))) {
     433                Statement * nested = br->getBody()->front();
    478434                while (nested) {
    479435                    Statement * next = nested->removeFromParent();
    480                     if (isa<Assign>(nested)) {
    481                         ifNode->removeDefined(cast<Assign>(nested));
    482                     }
    483436                    nested->insertAfter(stmt);
    484437                    stmt = nested;
    485438                    nested = next;
    486439                }
    487                 stmt = ifNode->eraseFromParent();
     440                stmt = br->eraseFromParent();
    488441                continue;
    489442            }
    490443
    491         } else if (While * whileNode = dyn_cast<While>(stmt)) {
    492             // Test whether we can ever take this branch
    493             const PabloAST * initial = cast<While>(stmt)->getCondition();
    494             if (LLVM_LIKELY(isa<Next>(initial))) {
    495                 initial = cast<Next>(initial)->getInitial();
    496             }
    497             if (LLVM_UNLIKELY(isa<Zeroes>(initial))) {
    498                 stmt = stmt->eraseFromParent();
    499                 continue;
    500             }
    501             redundancyElimination(function, whileNode->getBody(), &encountered);
    502             removeIdenticalEscapedValues(whileNode->getVariants());
    503             // If the condition's Next state is Zero, we can eliminate the loop after copying the internal
    504             // statements into the body.
    505444        } else {
     445
     446            // demote any uses of a Var whose value is in scope
     447            for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
     448                PabloAST * op = stmt->getOperand(i);
     449                if (isa<Var>(op)) {
     450                    PabloAST * const value = variables.get(cast<Var>(op));
     451                    if (value) {
     452                        stmt->setOperand(i, value);
     453                    }
     454                }
     455            }
     456
    506457            Statement * const prior = stmt->getPrevNode();
    507458            PabloAST * const folded = fold(stmt, block);
     
    513464                continue;
    514465            }
    515             // When we're creating the Pablo program, it's possible to have multiple instances of an "identical"
    516             // statement. By recording which statements have already been seen, we can detect the redundant statements
     466            // By recording which statements have already been seen, we can detect the redundant statements
    517467            // as any having the same type and operands. If so, we can replace its users with the prior statement.
    518468            // and erase this statement from the AST
    519             const auto f = encountered.findOrAdd(stmt);
     469            const auto f = expressions.findOrAdd(stmt);
    520470            if (!f.second) {
    521471                stmt = stmt->replaceWith(f.first, true);
     
    524474
    525475        }
     476
    526477        stmt = stmt->getNextNode();
    527478    }
    528 }
    529 
    530 /** ------------------------------------------------------------------------------------------------------------- *
    531  * @brief unused
    532  ** ------------------------------------------------------------------------------------------------------------- */
    533 inline static bool unused(const Statement * const stmt) {
    534     if (LLVM_UNLIKELY(stmt->getNumUses() == 0)) {
    535         // TODO: prototypes ought to state whether they have side effects.
    536         if (LLVM_UNLIKELY(isa<Call>(stmt) && cast<Call>(stmt)->getPrototype()->getNumOfResults() == 0)) {
    537             return false;
    538         }
    539         return true;
    540     }
    541     return false;
     479
     480    // If this block has a branch statement leading into it, we can verify whether an escaped value
     481    // was updated within this block and update the preceeding block's variable state appropriately.
     482
     483    if (Branch * const br = block->getBranch()) { assert (vt);
     484
     485        // When removing identical escaped values, we have to consider that the identical Vars could
     486        // be assigned new differing values later in the outer body. Thus instead of replacing them
     487        // directly, we map future uses of the duplicate Var to the initial one. The DCE pass will
     488        // later mark any Assign statement as dead if the Var is never read.
     489
     490        const auto escaped = br->getEscaped();
     491        const auto n = escaped.size();
     492        PabloAST * variable[n];
     493        PabloAST * incoming[n];
     494        PabloAST * outgoing[n];
     495
     496        size_t i = 0;
     497        for (Var * var : escaped) {
     498            incoming[i] = vt->get(var);
     499            outgoing[i] = variables.get(var);
     500            PabloAST * expr = var;
     501            if (LLVM_UNLIKELY(incoming[i] == outgoing[i])) {
     502                expr = incoming[i];
     503            } else {
     504                for (size_t j = 0; j != i; ++j) {
     505                    if ((outgoing[j] == outgoing[i]) && (incoming[j] == incoming[i])) {
     506                        expr = variable[j];
     507                        break;
     508                    }
     509                }
     510            }
     511            variable[i] = expr;
     512            vt->put(var, expr);
     513            ++i;
     514        }
     515    }
    542516}
    543517
     
    545519 * @brief deadCodeElimination
    546520 ** ------------------------------------------------------------------------------------------------------------- */
    547 void Simplifier::dce(PabloBlock * const block) {
     521void Simplifier::deadCodeElimination(PabloBlock * const block) {
     522
     523   flat_map<PabloAST *, Assign *> unread;
     524
    548525    Statement * stmt = block->front();
    549526    while (stmt) {
    550         if (LLVM_UNLIKELY(isa<If>(stmt))) {
    551             dce(cast<If>(stmt)->getBody());
    552         } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
    553             dce(cast<While>(stmt)->getBody());
    554         } else if (LLVM_UNLIKELY(unused(stmt))){
     527        if (unread.size() != 0) {
     528            for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
     529                PabloAST * const op = stmt->getOperand(i);
     530                if (LLVM_UNLIKELY(isa<Var>(op))) {
     531                    unread.erase(op);
     532                }
     533            }
     534        }
     535        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     536            Branch * const br = cast<Branch>(stmt);
     537            deadCodeElimination(br->getBody());
     538        } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     539            // An Assign statement is locally dead whenever its variable is not read
     540            // before being reassigned a value.
     541            PabloAST * var = cast<Assign>(stmt)->getVariable();
     542            auto f = unread.find(var);
     543            if (f != unread.end()) {
     544                auto prior = f->second;
     545                prior->eraseFromParent(true);
     546                f->second = cast<Assign>(stmt);
     547            } else {
     548                unread.emplace(var, cast<Assign>(stmt));
     549            }
     550        } else if (LLVM_UNLIKELY(stmt->getNumUses() == 0)) {
    555551            stmt = stmt->eraseFromParent(true);
    556552            continue;
     
    558554        stmt = stmt->getNextNode();
    559555    }
     556}
     557
     558/** ------------------------------------------------------------------------------------------------------------- *
     559 * @brief deadCodeElimination
     560 ** ------------------------------------------------------------------------------------------------------------- */
     561void Simplifier::deadCodeElimination(PabloFunction & f) {
     562
     563    deadCodeElimination(f.getEntryBlock());
     564
     565    for (unsigned i = 0; i < f.getNumOfVariables(); ++i) {
     566        Var * var = f.getVariable(i);
     567        bool unused = true;
     568        for (PabloAST * user : var->users()) {
     569            if (isa<Assign>(user)) {
     570                if (cast<Assign>(user)->getValue() == var) {
     571                    unused = false;
     572                    break;
     573                }
     574            } else {
     575                unused = false;
     576                break;
     577            }
     578        }
     579        if (LLVM_UNLIKELY(unused)) {
     580            for (PabloAST * user : var->users()) {
     581                cast<Assign>(user)->eraseFromParent(true);
     582            }
     583        }
     584    }
     585
    560586}
    561587
     
    568594    Statement * stmt = block->front();
    569595    while (stmt) {
    570         if (isa<If>(stmt)) {
    571             strengthReduction(cast<If>(stmt)->getBody());
    572         } else if (isa<While>(stmt)) {
    573             strengthReduction(cast<While>(stmt)->getBody());
     596        if (isa<Branch>(stmt)) {
     597            strengthReduction(cast<Branch>(stmt)->getBody());
    574598        } else if (isa<Advance>(stmt)) {
    575599            Advance * adv = cast<Advance>(stmt);
     
    591615                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
    592616                    block->setInsertPoint(scanThru->getPrevNode());
    593                     PabloAST * expr = block->createAdvance(op->getOperand(0), op->getAmount() - 1);
     617                    PabloAST * expr = block->createAdvance(op->getOperand(0), block->getInteger(op->getAmount() - 1));
    594618                    scanThru->setOperand(0, expr);
    595619                    scanThru->setOperand(1, block->createOr(scanThru->getOperand(1), expr));
     
    619643 ** ------------------------------------------------------------------------------------------------------------- */
    620644bool Simplifier::optimize(PabloFunction & function) {
    621     redundancyElimination(function, function.getEntryBlock());
     645    redundancyElimination(function.getEntryBlock());
    622646    strengthReduction(function.getEntryBlock());
    623     dce(function.getEntryBlock());
     647    deadCodeElimination(function);
    624648    #ifndef NDEBUG
    625649    PabloVerifier::verify(function, "post-simplification");
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.hpp

    r5160 r5202  
    66namespace pablo {
    77
     8class PabloFunction;
    89struct ExpressionTable;
    9 class PabloFunction;
    1010
    1111class Simplifier {
    12     friend class DistributivePass;
    13     friend class FactorizeDFG;
    1412    friend class BooleanReassociationPass;
     13    struct VariableTable;
    1514public:
    1615    static bool optimize(PabloFunction & function);
    17     static void dce(PabloBlock * const block);
    1816protected:
    1917    Simplifier() = default;
    2018private:
    21     static void redundancyElimination(PabloFunction & function, PabloBlock * const block, ExpressionTable * predecessor = nullptr);
    2219    static PabloAST * fold(Variadic * var, PabloBlock * const block);
    2320    static PabloAST * fold(Statement * const stmt, PabloBlock * const block);
     21    static void redundancyElimination(PabloBlock * const block, ExpressionTable * et = nullptr, VariableTable * const vt = nullptr);
     22    static void deadCodeElimination(PabloFunction & f);
     23    static void deadCodeElimination(PabloBlock * const block);
    2424    static void strengthReduction(PabloBlock * const block);
    25     static bool isSuperfluous(const Assign * const assign);
    2625};
    2726
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/schedulingprepass.cpp

    r5160 r5202  
    6666 * @brief resolveNestedUsages
    6767 ** ------------------------------------------------------------------------------------------------------------- */
    68 static void resolveNestedUsages(Statement * const root, Statement * const stmt, DependencyGraph & G, Map & M, PabloBlock * const block) {
    69     for (PabloAST * use : stmt->users()) {
     68static void resolveNestedUsages(Statement * const root, PabloAST * const expr, DependencyGraph & G, Map & M, PabloBlock * const block) {
     69    for (PabloAST * use : expr->users()) {
    7070        if (LLVM_LIKELY(isa<Statement>(use))) {
    7171            const PabloBlock * scope = cast<Statement>(use)->getParent();
    7272            if (scope != block) {
    73                 for (PabloBlock * prior = scope->getPredecessor (); prior; scope = prior, prior = prior->getPredecessor ()) {
     73                for (PabloBlock * prior = scope->getPredecessor(); prior; scope = prior, prior = prior->getPredecessor()) {
    7474                    if (prior == block) {
    7575                        assert (scope->getBranch());
     
    111111                    assert (v->second != u);
    112112                    add_edge(v->second, u, G);
    113                 } else if (isa<Assign>(op) || isa<Next>(op)) {
     113                } else if (isa<Assign>(op)) {
    114114                    // if this statement isn't an Assign or Next node, it cannot come from a nested scope
    115115                    // unless the function is invalid.
    116                     for (PabloBlock * prior = scope->getPredecessor (); prior; scope = prior, prior = prior->getPredecessor ()) {
     116                    for (PabloBlock * prior = scope->getPredecessor(); prior; scope = prior, prior = prior->getPredecessor()) {
    117117                        // Was this instruction computed by a nested block?
    118118                        if (prior == block) {
     
    132132    // Do a second pass to ensure that we've accounted for any nested usage of an If or While statement
    133133    for (Statement * stmt : *block) {
    134         if (LLVM_UNLIKELY(isa<If>(stmt))) {
    135             for (Assign * def : cast<If>(stmt)->getDefined()) {
    136                 resolveNestedUsages(stmt, def, G, M, block);
    137             }
    138         } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
    139             for (Next * var : cast<While>(stmt)->getVariants()) {
     134        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     135            for (Var * var : cast<Branch>(stmt)->getEscaped()) {
    140136                resolveNestedUsages(stmt, var, G, M, block);
    141137            }
  • 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}
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r5160 r5202  
    88#define PE_PabloAST_H
    99
     10#include <pablo/type/streamtype.h>
    1011#include <llvm/Support/Casting.h>
    1112#include <llvm/Support/Compiler.h>
    1213#include <boost/iterator/iterator_facade.hpp>
    13 #include <iterator>
    1414#include <util/slab_allocator.h>
    1515#include <type_traits>
    16 #include <unordered_map>
    1716#include <vector>
    18 #include <pablo/pablo_type.h>
    1917
    2018using namespace llvm;
     
    2523class Statement;
    2624class String;
     25class Branch;
    2726
    2827class PabloAST {
     
    3029    friend class Variadic;
    3130    friend class StatementList;
    32     friend class Var;
    33     friend class If;   
    34     friend class While;
     31    friend class Branch;
    3532    friend class PabloBlock;
    3633    friend class Prototype;
     
    3835    friend class SymbolGenerator;
    3936    friend class Count;
     37    friend class Var;
     38    friend void addUsage(PabloAST *, PabloBlock *);
     39    friend void removeUsage(PabloAST *, PabloBlock *);
    4040public:
    4141
     
    4545    using user_iterator = Users::iterator;
    4646    using const_user_iterator = Users::const_iterator;
     47
     48    static inline bool classof(const PabloAST *) {
     49        return true;
     50    }
     51    static inline bool classof(const void *) {
     52        return false;
     53    }
    4754
    4855    enum class ClassTypeId : unsigned {
     
    5259        , Ones
    5360        // Internal types
    54         , Var
     61        , Var       
    5562        , Integer
    5663        , String
     
    7683        // Variable assignments
    7784        , Assign
    78         , Next
     85        , Extract     
    7986        , Call
    8087        , SetIthBit
     
    8390        , While
    8491    };
    85     inline ClassTypeId getClassTypeId() const {
     92
     93    inline ClassTypeId getClassTypeId() const noexcept {
    8694        return mClassTypeId;
     95    }
     96
     97    inline llvm::Type * getType() const noexcept {
     98        return mType;
     99    }
     100
     101    inline void setType(Type * type) noexcept {
     102        mType = type;
     103    }
     104
     105    inline const String * getName() const noexcept {
     106        return mName;
     107    }
     108
     109    inline void setName(const String * const name) noexcept {
     110        mName = name;
    87111    }
    88112
     
    111135    }
    112136
    113     inline const PabloType * getType() const {
    114         return mType;
    115     }
    116 
    117137    void replaceAllUsesWith(PabloAST * const expr);
    118138
     
    121141    }
    122142
    123     void* operator new (std::size_t size) noexcept {
     143    void * operator new (std::size_t size) noexcept {
    124144        return mAllocator.allocate(size);
    125145    }
     
    129149    }
    130150
     151    void print(raw_ostream & O) const;
     152
    131153protected:
    132     inline PabloAST(const ClassTypeId id, const PabloType * const type)
     154    inline PabloAST(const ClassTypeId id, Type * const type, const String * name)
    133155    : mClassTypeId(id)
    134156    , mType(type)
     157    , mName(name)
    135158    , mUsers(mVectorAllocator)
    136159    {
    137160
    138161    }
    139     void addUser(PabloAST * const user);
    140     void removeUser(PabloAST * const user);
     162    bool addUser(PabloAST * const user);
     163    bool removeUser(PabloAST * const user);
    141164    virtual ~PabloAST() {
    142165        mUsers.clear();
    143166    }   
    144     static void throwIfNonMatchingTypes(const PabloAST * const a, const PabloAST * const b);
    145     static void throwIfNonMatchingType(const PabloAST * const a, const PabloType::TypeId typeId);
    146167    static Allocator        mAllocator;
    147168    static VectorAllocator  mVectorAllocator;
    148169private:
    149170    const ClassTypeId       mClassTypeId;
    150     const PabloType * const mType;
     171    Type *                  mType;
     172    const String *          mName;
    151173    Users                   mUsers;
    152174};
     
    155177
    156178bool dominates(const PabloAST * const expr1, const PabloAST * const expr2);
     179
     180bool postdominates(const PabloAST * const expr1, const PabloAST * const expr2);
    157181
    158182class StatementList;
     
    166190    friend class Simplifier;
    167191    friend class PabloBlock;
    168     template <class ValueType, class ValueList>
    169     friend void checkEscapedValueList(const Statement *, const PabloAST * const, PabloAST * const, ValueList &);
    170192public:
    171193    static inline bool classof(const PabloAST * e) {
     
    210232    Statement * replaceWith(PabloAST * const expr, const bool rename = true, const bool recursively = false);
    211233
    212     inline const String * getName() const {
    213         return mName;
    214     }
    215     inline void setName(const String * const name) {
    216         mName = name;
    217     }
    218234    inline Statement * getNextNode() const {
    219235        return mNext;
     
    227243    virtual ~Statement() {}
    228244protected:
    229     explicit Statement(const ClassTypeId id, const PabloType * const type, std::initializer_list<PabloAST *> operands, const String * const name)
    230     : PabloAST(id, type)
    231     , mName(name)
     245    explicit Statement(const ClassTypeId id, Type * const type, std::initializer_list<PabloAST *> operands, const String * const name)
     246    : PabloAST(id, type, name)
    232247    , mNext(nullptr)
    233248    , mPrev(nullptr)
     
    243258        }
    244259    }
    245     explicit Statement(const ClassTypeId id, const PabloType * const type, const unsigned reserved, const String * const name)
    246     : PabloAST(id, type)
    247     , mName(name)
     260    explicit Statement(const ClassTypeId id, Type * const type, const unsigned reserved, const String * const name)
     261    : PabloAST(id, type, name)
    248262    , mNext(nullptr)
    249263    , mPrev(nullptr)
     
    254268    }
    255269    template<typename iterator>
    256     explicit Statement(const ClassTypeId id, const PabloType * const type, iterator begin, iterator end, const String * const name)
    257     : PabloAST(id, type)
    258     , mName(name)
     270    explicit Statement(const ClassTypeId id, Type * const type, iterator begin, iterator end, const String * const name)
     271    : PabloAST(id, type, name)
    259272    , mNext(nullptr)
    260273    , mPrev(nullptr)
     
    269282        }
    270283    }
    271 private:
    272     template <class ValueType, class ValueList>
    273     void checkEscapedValueList(Statement * branch, PabloAST * const from, PabloAST * const to, ValueList & list);
    274284protected:   
    275     const String *  mName;
    276285    Statement *     mNext;
    277286    Statement *     mPrev;
     
    343352
    344353protected:
    345     explicit Variadic(const ClassTypeId id, const PabloType * const type, std::initializer_list<PabloAST *> operands, const String * const name)
     354    explicit Variadic(const ClassTypeId id, Type * const type, std::initializer_list<PabloAST *> operands, const String * const name)
    346355    : Statement(id, type, operands, name)
    347356    , mCapacity(operands.size()) {
    348357
    349358    }
    350     explicit Variadic(const ClassTypeId id, const PabloType * const type, const unsigned reserved, String * name)
     359    explicit Variadic(const ClassTypeId id, Type * const type, const unsigned reserved, const String * name)
    351360    : Statement(id, type, reserved, name)
    352361    , mCapacity(reserved) {
     
    354363    }
    355364    template<typename iterator>
    356     explicit Variadic(const ClassTypeId id, const PabloType * const type, iterator begin, iterator end, String * name)
     365    explicit Variadic(const ClassTypeId id, Type * const type, iterator begin, iterator end, const String * name)
    357366    : Statement(id, type, begin, end, name)
    358367    , mCapacity(std::distance(begin, end)) {
     
    362371    unsigned        mCapacity;
    363372};
    364 
    365 bool escapes(const Statement * statement);
    366373
    367374class StatementList {
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

    r5199 r5202  
    2323namespace pablo {
    2424
    25 PabloCompiler::PabloCompiler(IDISA::IDISA_Builder * b, PabloKernel * k, PabloFunction * const function)
    26 : mMod(b->getModule())
    27 , iBuilder(b)
    28 , mBitBlockType(b->getBitBlockType())
     25PabloCompiler::PabloCompiler(PabloKernel * k, PabloFunction * const function)
     26: iBuilder(k->getBuilder())
     27, mBitBlockType(iBuilder->getBitBlockType())
    2928, mCarryManager(nullptr)
    3029, mPabloFunction(function)
    31 , mPabloBlock(nullptr)
    3230, mKernelBuilder(k)
    3331, mWhileDepth(0)
     
    3836}
    3937
    40 
    4138Type * PabloCompiler::initializeKernelData() {
    42     Examine(mPabloFunction);
    43    
     39    Examine(mPabloFunction);   
    4440    mCarryManager = std::unique_ptr<CarryManager>(new CarryManager(iBuilder));
    4541    Type * carryDataType = mCarryManager->initializeCarryData(mPabloFunction);
     
    4743}
    4844   
     45void PabloCompiler::verifyParameter(const Var * var, const Value * param) {
     46    if (LLVM_UNLIKELY(&(param->getContext()) != &(iBuilder->getContext()))) {
     47        std::string tmp;
     48        raw_string_ostream out(tmp);
     49        out << "Cannot compile ";
     50        mPabloFunction->print(out);
     51        out << ": LLVM Context for ";
     52        var->print(out);
     53        out << " differs from that of the kernel.";
     54        throw std::runtime_error(out.str());
     55    }
     56}
     57
    4958void PabloCompiler::compile(Function * doBlockFunction) {
    5059
    5160    // Make sure that we generate code into the right module.
    52     mMod = iBuilder->getModule();
    5361    mFunction = doBlockFunction;
    5462    #ifdef PRINT_TIMING_INFORMATION
     
    5967    iBuilder->SetInsertPoint(BasicBlock::Create(iBuilder->getContext(), "entry", doBlockFunction, 0));
    6068    mSelf = mKernelBuilder->getParameter(doBlockFunction, "self");
     69
    6170    mCarryManager->initializeCodeGen(mKernelBuilder, mSelf);
    6271     
    63     Value * blockNo = mKernelBuilder->getScalarField(mSelf, blockNoScalar);
    64     std::string inputName = mKernelBuilder->mStreamSetInputs[0].ssName;
    65     Value * inputSet_ptr  = mKernelBuilder->getStreamSetBlockPtr(mSelf, inputName, blockNo);
    66 
    67     Value * outputSet_ptr = nullptr;
    68     if (mPabloFunction->getNumOfResults() > 0) {
    69         std::string outputName = mKernelBuilder->mStreamSetOutputs[0].ssName;
    70         outputSet_ptr = mKernelBuilder->getStreamSetBlockPtr(mSelf, outputName, blockNo);
    71     }
    72 
    73     PabloBlock * const entryBlock = mPabloFunction->getEntryBlock();
     72    PabloBlock * const entryBlock = mPabloFunction->getEntryBlock(); assert (entryBlock);
    7473    mMarkerMap.emplace(entryBlock->createZeroes(), iBuilder->allZeroes());
    7574    mMarkerMap.emplace(entryBlock->createOnes(), iBuilder->allOnes());
    76     for (unsigned j = 0; j < mPabloFunction->getNumOfParameters(); ++j) {
    77         Value * inputVal = iBuilder->CreateGEP(inputSet_ptr, {iBuilder->getInt32(0), iBuilder->getInt32(j)});
    78         const Var * const var = mPabloFunction->getParameter(j);
    79         if (DebugOptionIsSet(DumpTrace)) {
    80             iBuilder->CallPrintRegister(var->getName()->to_string(), iBuilder->CreateBlockAlignedLoad(inputVal));
    81         }
    82         mMarkerMap.emplace(var, inputVal);
    83     }
    84    
     75
     76    Value * const blockNo = mKernelBuilder->getScalarField(mSelf, blockNoScalar);
     77
     78    for (unsigned i = 0, j = 0; i < mPabloFunction->getNumOfParameters(); ++i) {
     79        Var * var = mPabloFunction->getParameter(i);
     80        std::string name = var->getName()->to_string();
     81        Value * input = nullptr;
     82        if (var->getType()->isSingleValueType()) {
     83            input = mKernelBuilder->getScalarFieldPtr(mSelf, name);
     84        } else {
     85            input = mKernelBuilder->getStreamSetBlockPtr(mSelf, name, blockNo);
     86            input = iBuilder->CreateGEP(input, {iBuilder->getInt32(0), iBuilder->getInt32(j++)});
     87        }
     88        verifyParameter(var, input);
     89        mMarkerMap.emplace(var, input);
     90    }
     91
     92    for (unsigned i = 0, j = 0; i < mPabloFunction->getNumOfResults(); ++i) {
     93        Var * var = mPabloFunction->getResult(i);
     94        std::string name = var->getName()->to_string();
     95        Value * output = nullptr;
     96        if (var->getType()->isSingleValueType()) {
     97            output = mKernelBuilder->getScalarFieldPtr(mSelf, name);
     98        } else {
     99            output = mKernelBuilder->getStreamSetBlockPtr(mSelf, name, blockNo);
     100            output = iBuilder->CreateGEP(output, {iBuilder->getInt32(0), iBuilder->getInt32(j++)});
     101        }
     102        verifyParameter(var, output);
     103        mMarkerMap.emplace(var, output);
     104    }
     105
    85106    compileBlock(entryBlock);
    86    
    87     for (unsigned j = 0; j < mPabloFunction->getNumOfResults(); ++j) {
    88         const auto f = mMarkerMap.find(mPabloFunction->getResult(j));
    89         if (LLVM_UNLIKELY(f == mMarkerMap.end())) {
    90             throw std::runtime_error("PabloCompiler: result " + std::to_string(j) + " was not assigned a value!");
    91         }
    92         iBuilder->CreateBlockAlignedStore(f->second, outputSet_ptr, {iBuilder->getInt32(0), iBuilder->getInt32(j)});
    93     }
    94    
     107
    95108    #ifdef PRINT_TIMING_INFORMATION
    96109    const timestamp_t pablo_compilation_end = read_cycle_counter();
     
    107120
    108121void PabloCompiler::Examine(const PabloBlock * const block) {
    109     unsigned maxOffset = 0;
    110122    for (const Statement * stmt : *block) {
    111          boost::container::flat_set<unsigned> offsets;
    112123        if (LLVM_UNLIKELY(isa<Lookahead>(stmt))) {
    113124            const Lookahead * const la = cast<Lookahead>(stmt);
    114125            assert (isa<Var>(la->getExpr()));
    115             if (la->getAmount() > maxOffset) maxOffset = la->getAmount();
     126            if (LLVM_LIKELY(la->getAmount() > mKernelBuilder->getLookAhead())) {
     127                mKernelBuilder->setLookAhead(la->getAmount());
     128            }
    116129        } else {
    117130            if (LLVM_UNLIKELY(isa<If>(stmt))) {
     
    123136            }
    124137        }
    125         mKernelBuilder->setLookAhead(maxOffset);
    126     }
    127 }
    128 
    129 void PabloCompiler::compileBlock(const PabloBlock * const block) {
    130     mPabloBlock = block;
     138    }   
     139}
     140
     141inline void PabloCompiler::compileBlock(const PabloBlock * const block) {
    131142    for (const Statement * statement : *block) {
    132143        compileStatement(statement);
    133144    }
    134     mPabloBlock = block->getPredecessor ();
    135 }
    136 
    137 void PabloCompiler::compileIf(const If * ifStatement) {       
     145}
     146
     147static const llvm::StringRef EmptyString;
     148
     149inline const llvm::StringRef & getName(const PabloAST * expr) {
     150    if (expr->getName()) {
     151        return expr->getName()->value();
     152    }
     153    return EmptyString;
     154}
     155
     156void PabloCompiler::compileIf(const If * const ifStatement) {
    138157    //
    139158    //  The If-ElseZero stmt:
     
    154173    //
    155174
     175    Module * const mod = iBuilder->getModule();
    156176    BasicBlock * const ifEntryBlock = iBuilder->GetInsertBlock();
    157     BasicBlock * const ifBodyBlock = BasicBlock::Create(mMod->getContext(), "if.body", mFunction, 0);
    158     BasicBlock * const ifEndBlock = BasicBlock::Create(mMod->getContext(), "if.end", mFunction, 0);
    159    
     177    BasicBlock * const ifBodyBlock = BasicBlock::Create(mod->getContext(), "if.body", mFunction, 0);
     178    BasicBlock * const ifEndBlock = BasicBlock::Create(mod->getContext(), "if.end", mFunction, 0);
     179   
     180    std::vector<std::pair<const Var *, Value *>> incoming;
     181
     182    for (const Var * var : ifStatement->getEscaped()) {
     183        auto f = mMarkerMap.find(var);
     184        if (LLVM_UNLIKELY(f == mMarkerMap.end())) {
     185            std::string tmp;
     186            raw_string_ostream out(tmp);
     187            PabloPrinter::print(var, out);
     188            out << " is uninitialized prior to entering ";
     189            PabloPrinter::print(ifStatement, out);
     190            llvm::report_fatal_error(out.str());
     191        }
     192        incoming.emplace_back(var, f->second);
     193    }
     194
    160195    PabloBlock * ifBody = ifStatement->getBody();
    161196   
     
    169204   
    170205    compileBlock(ifBody);
     206
    171207    BasicBlock * ifExitBlock = iBuilder->GetInsertBlock();
    172208
     
    179215    //End Block
    180216    iBuilder->SetInsertPoint(ifEndBlock);
    181     for (const PabloAST * node : ifStatement->getDefined()) {
    182         const Assign * assign = cast<Assign>(node);
    183         PHINode * phi = iBuilder->CreatePHI(mBitBlockType, 2, assign->getName()->value());
    184         auto f = mMarkerMap.find(assign);
    185         assert (f != mMarkerMap.end());
    186         phi->addIncoming(iBuilder->allZeroes(), ifEntryBlock);
     217    for (const auto i : incoming) {
     218        const Var * var; Value * value;
     219        std::tie(var, value) = i;
     220
     221        auto f = mMarkerMap.find(var);
     222        if (LLVM_UNLIKELY(f == mMarkerMap.end() || f->second == value)) {
     223            std::string tmp;
     224            raw_string_ostream out(tmp);
     225            PabloPrinter::print(var, out);
     226            out << " was not assigned a value.";
     227            llvm::report_fatal_error(out.str());
     228        }
     229
     230        PHINode * phi = iBuilder->CreatePHI(mBitBlockType, 2, getName(var));
     231        phi->addIncoming(value, ifEntryBlock);
    187232        phi->addIncoming(f->second, ifExitBlock);
    188233        f->second = phi;
    189         assert (mMarkerMap[assign] == phi);
     234
     235        assert (mMarkerMap[var] == phi);
    190236    }
    191237    // Create the phi Node for the summary variable, if needed.
     
    194240}
    195241
    196 void PabloCompiler::compileWhile(const While * whileStatement) {
     242void PabloCompiler::compileWhile(const While * const whileStatement) {
    197243
    198244    PabloBlock * const whileBody = whileStatement->getBody();
    199245   
    200246    BasicBlock * whileEntryBlock = iBuilder->GetInsertBlock();
    201     BasicBlock * whileBodyBlock = BasicBlock::Create(mMod->getContext(), "while.body", mFunction, 0);
    202     BasicBlock * whileEndBlock = BasicBlock::Create(mMod->getContext(), "while.end", mFunction, 0);
     247
     248    Module * const mod = iBuilder->getModule();
     249    BasicBlock * whileBodyBlock = BasicBlock::Create(mod->getContext(), "while.body", mFunction, 0);
     250    BasicBlock * whileEndBlock = BasicBlock::Create(mod->getContext(), "while.end", mFunction, 0);
    203251
    204252    mCarryManager->enterScope(whileBody);
    205253    mCarryManager->ensureCarriesLoadedRecursive();
    206254
    207     const auto & nextNodes = whileStatement->getVariants();
    208     std::vector<PHINode *> nextPhis;
    209     nextPhis.reserve(nextNodes.size());
    210255#ifdef ENABLE_BOUNDED_WHILE
    211256    PHINode * bound_phi = nullptr;  // Needed for bounded while loops.
     
    229274    mCarryManager->initializeWhileEntryCarryDataPhis(whileEntryBlock);
    230275
     276    std::vector<std::pair<const Var *, PHINode *>> variants;
     277
    231278    // for any Next nodes in the loop body, initialize to (a) pre-loop value.
    232     for (const Next * n : nextNodes) {
    233         PHINode * phi = iBuilder->CreatePHI(mBitBlockType, 2, n->getName()->value());
    234         auto f = mMarkerMap.find(n->getInitial());       
    235         assert (f != mMarkerMap.end());
     279    for (const auto var : whileStatement->getEscaped()) {
     280        PHINode * phi = iBuilder->CreatePHI(mBitBlockType, 2, getName(var));
     281        auto f = mMarkerMap.find(var);
     282        if (LLVM_UNLIKELY(f == mMarkerMap.end())) {
     283            std::string tmp;
     284            raw_string_ostream out(tmp);
     285            PabloPrinter::print(var, out);
     286            out << " was not assigned a value.";
     287            llvm::report_fatal_error(out.str());
     288        }
    236289        phi->addIncoming(f->second, whileEntryBlock);
    237290        f->second = phi;
    238         assert(mMarkerMap[n->getInitial()] == phi);
    239         nextPhis.push_back(phi);
     291        assert(mMarkerMap[var] == phi);
     292        variants.emplace_back(var, phi);
    240293    }
    241294#ifdef ENABLE_BOUNDED_WHILE
     
    270323    iBuilder->CreateCondBr(cond_expr, whileBodyBlock, whileEndBlock);
    271324
    272     // and for any Next nodes in the loop body
    273     for (unsigned i = 0; i < nextNodes.size(); i++) {
    274         const Next * n = nextNodes[i];
    275         const auto f = mMarkerMap.find(n->getExpr());
    276         if (LLVM_UNLIKELY(f == mMarkerMap.end())) {
    277             throw std::runtime_error("Next node expression was not compiled!");
    278         }
    279         nextPhis[i]->addIncoming(f->second, whileExitBlock);
     325    // and for any variant nodes in the loop body
     326    for (const auto variant : variants) {
     327        const Var * var; PHINode * phi;
     328        std::tie(var, phi) = variant;
     329        const auto f = mMarkerMap.find(var);
     330        if (LLVM_UNLIKELY(f == mMarkerMap.end() || f->second == phi)) {
     331            std::string tmp;
     332            raw_string_ostream out(tmp);
     333            PabloPrinter::print(var, out);
     334            out << " was not assigned a value.";
     335            llvm::report_fatal_error(out.str());
     336        }
     337        phi->addIncoming(f->second, whileExitBlock);
     338        f->second = phi;
    280339    }
    281340
     
    287346}
    288347
    289 
    290348void PabloCompiler::compileStatement(const Statement * stmt) {
    291     Value * expr = nullptr;
    292     if (const Assign * assign = dyn_cast<const Assign>(stmt)) {
    293         expr = compileExpression(assign->getExpression());
    294     } else if (const Next * next = dyn_cast<const Next>(stmt)) {
    295         expr = compileExpression(next->getExpr());
    296     } else if (const If * ifStatement = dyn_cast<const If>(stmt)) {
    297         compileIf(ifStatement);
    298         return;
    299     } else if (const While * whileStatement = dyn_cast<const While>(stmt)) {
    300         compileWhile(whileStatement);
    301         return;
    302 //    } else if (const Call* call = dyn_cast<Call>(stmt)) {
    303 //        // Call the callee once and store the result in the marker map.
    304 //        if (LLVM_UNLIKELY(mMarkerMap.count(call) == 0)) {
    305 //            return;
    306 //        }
    307 
    308 //        const Prototype * proto = call->getPrototype();
    309 //        const String * callee = proto->getName();
    310 
    311 //        Type * inputType = StructType::get(mMod->getContext(), std::vector<Type *>{proto->getNumOfParameters(), mBitBlockType});
    312 //        Type * outputType = StructType::get(mMod->getContext(), std::vector<Type *>{proto->getNumOfResults(), mBitBlockType});
    313 //        FunctionType * functionType = FunctionType::get(Type::getVoidTy(mMod->getContext()), std::vector<Type *>{PointerType::get(inputType, 0), PointerType::get(outputType, 0)}, false);
    314 
    315 //        //Starts on process_block
    316 //        SmallVector<AttributeSet, 3> Attrs;
    317 //        Attrs.push_back(AttributeSet::get(mMod->getContext(), 1U, std::vector<Attribute::AttrKind>({ Attribute::ReadOnly, Attribute::NoCapture })));
    318 //        Attrs.push_back(AttributeSet::get(mMod->getContext(), 2U, std::vector<Attribute::AttrKind>({ Attribute::ReadNone, Attribute::NoCapture })));
    319 //        AttributeSet AttrSet = AttributeSet::get(mMod->getContext(), Attrs);
    320 
    321 //        Function * externalFunction = cast<Function>(mMod->getOrInsertFunction(callee->value(), functionType, AttrSet));
    322 //        if (LLVM_UNLIKELY(externalFunction == nullptr)) {
    323 //            throw std::runtime_error("Could not create static method call for external function \"" + callee->to_string() + "\"");
    324 //        }
    325 //        externalFunction->setCallingConv(llvm::CallingConv::C);
    326 
    327 //        AllocaInst * outputStruct = iBuilder->CreateAlloca(outputType);
    328 //        iBuilder->CreateCall2(externalFunction, mInputAddressPtr, outputStruct);
    329 //        Value * outputPtr = iBuilder->CreateGEP(outputStruct, std::vector<Value *>({ iBuilder->getInt32(0), iBuilder->getInt32(0) }));
    330 
    331 //        expr = iBuilder->CreateBlockAlignedLoad(outputPtr);
    332     } else if (const And * pablo_and = dyn_cast<And>(stmt)) {
    333         expr = iBuilder->simd_and(compileExpression(pablo_and->getOperand(0)), compileExpression(pablo_and->getOperand(1)));
    334     } else if (const Or * pablo_or = dyn_cast<Or>(stmt)) {
    335         expr = iBuilder->simd_or(compileExpression(pablo_or->getOperand(0)), compileExpression(pablo_or->getOperand(1)));
    336     } else if (const Xor * pablo_xor = dyn_cast<Xor>(stmt)) {
    337         expr = iBuilder->simd_xor(compileExpression(pablo_xor->getOperand(0)), compileExpression(pablo_xor->getOperand(1)));
    338     } else if (const Sel * sel = dyn_cast<Sel>(stmt)) {
    339         Value* ifMask = compileExpression(sel->getCondition());
    340         Value* ifTrue = iBuilder->simd_and(ifMask, compileExpression(sel->getTrueExpr()));
    341         Value* ifFalse = iBuilder->simd_and(iBuilder->simd_not(ifMask), compileExpression(sel->getFalseExpr()));
    342         expr = iBuilder->simd_or(ifTrue, ifFalse);
    343     } else if (const Not * pablo_not = dyn_cast<Not>(stmt)) {
    344         expr = iBuilder->simd_not(compileExpression(pablo_not->getExpr()));
    345     } else if (const Advance * adv = dyn_cast<Advance>(stmt)) {
    346         Value * const strm_value = compileExpression(adv->getExpr());
    347         expr = mCarryManager->advanceCarryInCarryOut(adv->getLocalIndex(), adv->getAmount(), strm_value);
    348     } else if (const MatchStar * mstar = dyn_cast<MatchStar>(stmt)) {
    349         Value * const marker = compileExpression(mstar->getMarker());
    350         Value * const cc = compileExpression(mstar->getCharClass());
    351         Value * const marker_and_cc = iBuilder->simd_and(marker, cc);
    352         Value * const sum = mCarryManager->addCarryInCarryOut(mstar->getLocalCarryIndex(), marker_and_cc, cc);
    353         expr = iBuilder->simd_or(iBuilder->simd_xor(sum, cc), marker);
    354     } else if (const ScanThru * sthru = dyn_cast<ScanThru>(stmt)) {
    355         Value * const  marker_expr = compileExpression(sthru->getScanFrom());
    356         Value * const  cc_expr = compileExpression(sthru->getScanThru());
    357         Value * const  sum = mCarryManager->addCarryInCarryOut(sthru->getLocalCarryIndex(), marker_expr, cc_expr);
    358         expr = iBuilder->simd_and(sum, iBuilder->simd_not(cc_expr));
    359     } else if (const InFile * e = dyn_cast<InFile>(stmt)) {
    360         Value * EOFmask = mKernelBuilder->getScalarField(mSelf, "EOFmask");
    361         expr = iBuilder->simd_xor(compileExpression(e->getExpr()), EOFmask);
    362     } else if (const AtEOF * e = dyn_cast<AtEOF>(stmt)) {
    363         Value * EOFbit = mKernelBuilder->getScalarField(mSelf, "EOFbit");
    364                 expr = iBuilder->simd_and(compileExpression(e->getExpr()), EOFbit);
    365     } else if (const Count * c = dyn_cast<Count>(stmt)) {
    366         Value * const to_count = compileExpression(c->getExpr());
    367         std::string counter = c->getName()->to_string();
    368         Value * countSoFar = mKernelBuilder->getScalarField(mSelf, counter);
    369         unsigned counterSize = countSoFar->getType()->getIntegerBitWidth();
    370         Value * fieldCounts = iBuilder->simd_popcount(counterSize, to_count);
    371         for (unsigned i = 0; i < iBuilder->getBitBlockWidth()/counterSize; ++i) {
    372             countSoFar = iBuilder->CreateAdd(countSoFar, iBuilder->mvmd_extract(counterSize, fieldCounts, i));
    373         }
    374         mKernelBuilder->setScalarField(mSelf, counter, countSoFar);
    375         expr = iBuilder->bitCast(iBuilder->CreateZExt(countSoFar, iBuilder->getIntNTy(iBuilder->getBitBlockWidth())));
    376     } else if (const Lookahead * l = dyn_cast<Lookahead>(stmt)) {
    377         PabloAST * const var = l->getExpr();
    378         if (LLVM_UNLIKELY(!isa<Var>(var))) {
    379             throw std::runtime_error("Lookahead operations may only be applied to input streams");
    380         }
    381         unsigned index = 0;
    382         for (; index < mPabloFunction->getNumOfParameters(); ++index) {
    383             if (mPabloFunction->getParameter(index) == var) {
    384                 break;
    385             }
    386         }
    387         if (LLVM_UNLIKELY(index >= mPabloFunction->getNumOfParameters())) {
    388             throw std::runtime_error("Lookahead has an illegal Var operand");
    389         }
    390         const unsigned bit_shift = (l->getAmount() % iBuilder->getBitBlockWidth());
    391         const unsigned block_shift = (l->getAmount() / iBuilder->getBitBlockWidth());
    392         std::string inputName = mKernelBuilder->mStreamSetInputs[0].ssName;
    393         Value * blockNo = mKernelBuilder->getScalarField(mSelf, blockNoScalar);
    394         Value * lookAhead_blockPtr  = mKernelBuilder->getStreamSetBlockPtr(mSelf, inputName, iBuilder->CreateAdd(blockNo, ConstantInt::get(iBuilder->getSizeTy(), block_shift)));
    395         Value * lookAhead_inputPtr = iBuilder->CreateGEP(lookAhead_blockPtr, {iBuilder->getInt32(0), iBuilder->getInt32(index)});
    396         Value * lookAhead = iBuilder->CreateBlockAlignedLoad(lookAhead_inputPtr);
    397         if (bit_shift == 0) {  // Simple case with no intra-block shifting.
    398             expr = lookAhead; 
    399         }
    400         else { // Need to form shift result from two adjacent blocks.
    401             Value * lookAhead_blockPtr1  = mKernelBuilder->getStreamSetBlockPtr(mSelf, inputName, iBuilder->CreateAdd(blockNo, ConstantInt::get(iBuilder->getSizeTy(), block_shift + 1)));
    402             Value * lookAhead_inputPtr1 = iBuilder->CreateGEP(lookAhead_blockPtr1, {iBuilder->getInt32(0), iBuilder->getInt32(index)});
    403             Value * lookAhead1 = iBuilder->CreateBlockAlignedLoad(lookAhead_inputPtr1);
    404             if (LLVM_UNLIKELY((bit_shift % 8) == 0)) { // Use a single whole-byte shift, if possible.
    405                 expr = iBuilder->mvmd_dslli(8, lookAhead1, lookAhead, (bit_shift / 8));
    406             }
    407             else {
    408                 Type  * const streamType = iBuilder->getIntNTy(iBuilder->getBitBlockWidth());
    409                 Value * b1 = iBuilder->CreateBitCast(lookAhead1, streamType);
    410                 Value * b0 = iBuilder->CreateBitCast(lookAhead, streamType);
    411                 Value * result = iBuilder->CreateOr(iBuilder->CreateShl(b1, iBuilder->getBitBlockWidth() - bit_shift), iBuilder->CreateLShr(b0, bit_shift));
    412                 expr = iBuilder->CreateBitCast(result, mBitBlockType);
    413             }
    414         }
     349
     350