Changeset 4416 for icGREP


Ignore:
Timestamp:
Jan 13, 2015, 4:01:06 PM (5 years ago)
Author:
nmedfort
Message:

Many use def info changes; removed dependency on boost system library. More work still needed on CSE.

Location:
icGREP/icgrep-devel/icgrep
Files:
4 added
2 deleted
23 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/CMakeLists.txt

    r4404 r4416  
    5151set(Boost_USE_MULTITHREADED OFF)
    5252set(Boost_USE_STATIC_RUNTIME OFF)
    53 find_package(Boost COMPONENTS system REQUIRED)
    54 
    55 add_library(PabloADT pablo/pe_and.cpp pablo/pe_not.cpp pablo/pe_or.cpp pablo/pabloAST.cpp pablo/pe_sel.cpp pablo/pe_xor.cpp pablo/ps_if.cpp pablo/ps_while.cpp pablo/codegenstate.cpp pablo/symbol_generator.cpp pablo/analysis/useanalysis.cpp pablo/printer_pablos.cpp pablo/pablo_compiler.cpp)
     53find_package(Boost)
     54
     55add_library(PabloADT pablo/pe_and.cpp pablo/pe_not.cpp pablo/pe_or.cpp pablo/pabloAST.cpp pablo/pe_sel.cpp pablo/pe_xor.cpp pablo/ps_assign.cpp pablo/ps_if.cpp pablo/ps_while.cpp pablo/codegenstate.cpp pablo/symbol_generator.cpp pablo/printer_pablos.cpp pablo/pablo_compiler.cpp pablo/optimizers/pablo_simplifier.cpp)
    5656add_library(RegExpADT re/re_re.cpp re/re_cc.cpp re/re_parser.cpp re/re_rep.cpp re/parsefailure.cpp re/re_nullable.cpp re/re_simplifier.cpp re/re_compiler.cpp re/printer_re.cpp re/re_diff.cpp re/re_intersect.cpp re/re_analysis.cpp)
    5757add_library(CCADT cc/cc_namemap.cpp cc/cc_compiler.cpp utf_encoding.cpp utf8_encoder.cpp UCD/CaseFolding_txt.cpp)
     
    7878    link_directories(${Boost_LIBRARY_DIR})
    7979    SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -DUSE_BOOST")
    80     target_link_libraries (CCADT ${Boost_LIBRARIES})
    81     target_link_libraries (PabloADT ${Boost_LIBRARIES})
    82     target_link_libraries (RegExpADT ${Boost_LIBRARIES})
     80    # target_link_libraries (CCADT ${Boost_LIBRARIES})
     81    # target_link_libraries (PabloADT ${Boost_LIBRARIES})
     82    # target_link_libraries (RegExpADT ${Boost_LIBRARIES})
    8383ENDIF()
    8484
  • icGREP/icgrep-devel/icgrep/compiler.cpp

    r4412 r4416  
    1717#include <cc/cc_namemap.hpp>
    1818#include <pablo/pablo_compiler.h>
    19 #include <pablo/analysis/useanalysis.h>
    20 
     19#include <pablo/optimizers/pablo_simplifier.hpp>
    2120#include "UCD/precompiled_gc.h"
    2221#include "UCD/precompiled_sc.h"
     
    141140
    142141    // Scan through the pablo code and perform DCE and CSE
    143     // UseAnalysis::optimize(main);
     142    Simplifier::optimize(main);
    144143
    145144    if (PrintAllPablo || PrintOptimizedREcode) {
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.cpp

    r4415 r4416  
    1111/// UNARY CREATE FUNCTIONS
    1212
     13Assign * PabloBlock::createAssign(const std::string prefix, PabloAST * expr, const int outputIndex)  {
     14    return insertAtInsertionPoint(new Assign(expr, outputIndex, mSymbolGenerator->make(prefix), this));
     15}
     16
    1317PabloAST * PabloBlock::createAdvance(PabloAST * expr, const int shiftAmount) {
    1418    if (isa<Zeroes>(expr) || shiftAmount == 0) {
    1519        return expr;
    1620    }
    17     return insertIfNew(mUnaryWithInt.findOrMake<Advance>(PabloAST::ClassTypeId::Advance, expr, shiftAmount, mSymbolGenerator, this));
    18 }
    19 
    20 Assign * PabloBlock::createImmutableAssign(const std::string prefix, PabloAST * expr, const int outputIndex) {
    21     return insertIfNew(mUnary.findOrMake<Assign>(PabloAST::ClassTypeId::Assign, expr, outputIndex, mSymbolGenerator->make(prefix), this));
     21    return insertAtInsertionPoint(new Advance(expr, shiftAmount, mSymbolGenerator, this));
    2222}
    2323
     
    2727
    2828Call * PabloBlock::createCall(String * name) {
    29     return insertIfNew(mUnary.findOrMake<Call>(PabloAST::ClassTypeId::Call, name, this));
     29    return insertAtInsertionPoint(new Call(name, this));
    3030}
    3131
    3232PabloAST * PabloBlock::createNot(PabloAST * expr) {
    33     return mUnary.findOrCall<OptimizeNot>(PabloAST::ClassTypeId::Not, expr, this);
     33    OptimizeNot op;
     34    return op(expr, this);
    3435}
    3536
    3637Not * PabloBlock::createNotImm(PabloAST * expr) {
    37     return insertIfNew(mUnary.findOrMake<Not>(PabloAST::ClassTypeId::Not, expr, this));
     38    return insertAtInsertionPoint(new Not(expr, this));
    3839}
    3940
     
    4344
    4445Var * PabloBlock::createVar(String * name) {
    45     return mUnary.findOrMake<Var>(PabloAST::ClassTypeId::Var, name, this).first;
     46    return insertAtInsertionPoint(new Var(name, this));
    4647}
    4748
     
    4950
    5051Next * PabloBlock::createNext(Assign * assign, PabloAST * expr) {
    51     return insertIfNew(mBinary.findOrMake<Next>(PabloAST::ClassTypeId::Next, assign, expr, this));
     52    return insertAtInsertionPoint(new Next(assign, expr, this));
    5253}
    5354
     
    5657        return marker;
    5758    }
    58     return insertIfNew(mBinary.findOrMake<MatchStar>(PabloAST::ClassTypeId::MatchStar, marker, charclass, mSymbolGenerator, this));
     59    return insertAtInsertionPoint(new MatchStar(marker, charclass, mSymbolGenerator, this));
    5960}
    6061
     
    6364        return from;
    6465    }
    65     return insertIfNew(mBinary.findOrMake<ScanThru>(PabloAST::ClassTypeId::ScanThru, from, thru, mSymbolGenerator, this));
     66    return insertAtInsertionPoint(new ScanThru(from, thru, mSymbolGenerator, this));
    6667}
    6768
     
    7071        std::swap(expr1, expr2);
    7172    }
    72     return mBinary.findOrCall<OptimizeAnd>(PabloAST::ClassTypeId::And, expr1, expr2, this);
     73    OptimizeAnd op;
     74    return op(expr1, expr2, this);
    7375}
    7476
    7577And * PabloBlock::createAndImm(PabloAST * expr1, PabloAST * expr2) {
    76     return insertIfNew(mBinary.findOrMake<And>(PabloAST::ClassTypeId::And, expr1, expr2, this));
     78    return insertAtInsertionPoint(new And(expr1, expr2, this));
    7779}
    7880
     
    8183        std::swap(expr1, expr2);
    8284    }
    83     return mBinary.findOrCall<OptimizeOr>(PabloAST::ClassTypeId::Or, expr1, expr2, this);
     85    OptimizeOr op;
     86    return op(expr1, expr2, this);
    8487}
    8588
    8689Or * PabloBlock::createOrImm(PabloAST * expr1, PabloAST * expr2) {
    87     return insertIfNew(mBinary.findOrMake<Or>(PabloAST::ClassTypeId::Or, expr1, expr2, this));
     90    return insertAtInsertionPoint(new Or(expr1, expr2, this));
    8891}
    8992
     
    9295        std::swap(expr1, expr2);
    9396    }
    94     return mBinary.findOrCall<OptimizeXor>(PabloAST::ClassTypeId::Xor, expr1, expr2, this);
     97    OptimizeXor op;
     98    return op(expr1, expr2, this);
    9599}
    96100
    97101Xor * PabloBlock::createXorImm(PabloAST * expr1, PabloAST * expr2) {
    98     return insertIfNew(mBinary.findOrMake<Xor>(PabloAST::ClassTypeId::Xor, expr1, expr2,  this));
     102    return insertAtInsertionPoint(new Xor(expr1, expr2,  this));
    99103}
    100104
     
    102106
    103107PabloAST * PabloBlock::createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr) {
    104     return mTernary.findOrCall<OptimizeSel>(PabloAST::ClassTypeId::Sel, condition, trueExpr, falseExpr, this);
     108    OptimizeSel op;
     109    return op(condition, trueExpr, falseExpr, this);
    105110}
    106111
    107112Sel * PabloBlock::createSelImm(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr) {
    108     return insertIfNew(mTernary.findOrMake<Sel>(PabloAST::ClassTypeId::Sel, condition, trueExpr, falseExpr, this));
     113    return insertAtInsertionPoint(new Sel(condition, trueExpr, falseExpr, this));
    109114}
    110115
    111 PabloAST * PabloBlock::setOperandOf(Statement * inst, const unsigned index, PabloAST * value) {
    112116
    113     assert (index < inst->getNumOperands() && inst->getOperand(index) != value);
     117If * PabloBlock::createIf(PabloAST * condition, std::vector<Assign *> && definedVars, PabloBlock & body) {
     118    return insertAtInsertionPoint(new If(condition, std::move(definedVars), body, this));
     119}
    114120
    115     // get the current insertion point so we can restore it later
    116     Statement * const ip = getInsertPoint();
    117     const bool replacingCurrentIP = (ip == inst);
     121While * PabloBlock::createWhile(PabloAST * cond, PabloBlock & body) {
     122    return insertAtInsertionPoint(new While(cond, body, this));
     123}
    118124
    119     // set the current ip to the position of the inst we're "updating"
    120     setInsertPoint(inst);
    121     // this will move the ip back to inst's prior node
    122     inst->removeFromParent();
     125/// CONSTRUCTOR
    123126
    124     PabloAST * retVal = inst;
     127PabloBlock::PabloBlock()
     128: mZeroes(new Zeroes())
     129, mOnes(new Ones())
     130, mSymbolGenerator(new SymbolGenerator())
     131{
    125132
    126     switch (inst->getClassTypeId()) {
    127         case PabloAST::ClassTypeId::Advance:
    128             retVal = createAdvance(value, cast<Advance>(inst)->getAdvanceAmount());
    129             break;
    130         case PabloAST::ClassTypeId::Not:
    131             retVal = createNot(value);
    132             break;
    133 //        case PabloAST::ClassTypeId::Assign:
    134 //            retVal = createAssign(value, cast<Assign>(inst)->getOutputIndex());
    135 //            break;
    136         case PabloAST::ClassTypeId::Var:
    137             retVal = createVar(cast<String>(value));
    138             break;
    139         case PabloAST::ClassTypeId::Call:
    140             retVal = createCall(cast<String>(value));
    141             break;
    142         case PabloAST::ClassTypeId::And:
    143             retVal = createAnd(index == 0 ? value : inst->getOperand(0), index == 1 ? value : inst->getOperand(1));
    144             break;
    145         case PabloAST::ClassTypeId::Or:
    146             retVal = createOr(index == 0 ? value : inst->getOperand(0), index == 1 ? value : inst->getOperand(1));
    147             break;
    148         case PabloAST::ClassTypeId::Xor:
    149             retVal = createXor(index == 0 ? value : inst->getOperand(0), index == 1 ? value : inst->getOperand(1));
    150             break;
    151         case PabloAST::ClassTypeId::Next:
    152             retVal = createNext(cast<Assign>(index == 0 ? value : inst->getOperand(0)), index == 1 ? value : inst->getOperand(1));
    153             break;
    154         case PabloAST::ClassTypeId::ScanThru:
    155             retVal = createScanThru(index == 0 ? value : inst->getOperand(0), index == 1 ? value : inst->getOperand(1));
    156             break;
    157         case PabloAST::ClassTypeId::MatchStar:
    158             retVal = createMatchStar(index == 0 ? value : inst->getOperand(0), index == 1 ? value : inst->getOperand(1));
    159             break;
    160         case PabloAST::ClassTypeId::Sel:
    161             retVal = createSel(index == 0 ? value : inst->getOperand(0), index == 1 ? value : inst->getOperand(1), index == 2 ? value : inst->getOperand(2));
    162             break;
    163         default:
    164             break;
    165     }
     133}
    166134
    167     // restore our insertion point
    168     setInsertPoint(replacingCurrentIP ? inst : ip);
     135PabloBlock::PabloBlock(PabloBlock * predecessor)
     136: mZeroes(predecessor->mZeroes) // inherit the original "Zeroes" variable for simplicity
     137, mOnes(predecessor->mOnes) // inherit the original "Ones" variable for simplicity
     138, mSymbolGenerator(predecessor->mSymbolGenerator)
     139{
    169140
    170     return retVal;
    171141}
    172142
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r4415 r4416  
    99
    1010#include <pablo/pabloAST.h>
    11 #include <pablo/pabloAST.h>
     11#include <pablo/symbol_generator.h>
    1212#include <pablo/pe_advance.h>
    1313#include <pablo/pe_and.h>
     
    2828#include <pablo/ps_if.h>
    2929#include <pablo/ps_while.h>
    30 #include <pablo/symbol_generator.h>
    31 #include <map>
    32 #include <vector>
    33 #include <string>
    34 #include <array>
    35 #include <tuple>
    36 #include <pablo/printer_pablos.h>
     30#include <stdexcept>
    3731
    3832namespace pablo {
     33
     34class Assign;
     35class Advance;
     36class And;
     37class Call;
     38class MatchStar;
     39class Next;
     40class Not;
     41class Or;
     42class Ones;
     43class ScanThru;
     44class Sel;
     45class String;
     46class Integer;
     47class Var;
     48class Xor;
     49class Zeroes;
     50class If;
     51class While;
     52
    3953
    4054class PabloBlock : public StatementList {
     
    6983    Call * createCall(String * name);
    7084
    71     Assign * createAssign(const std::string prefix, PabloAST * expr, const int outputIndex = -1)  {
    72         // Note: we cannot just use the findOrMake method to obtain this; an Assign node cannot be considered
    73         // unique until we prove it has no Next node associated with it. But the Assign node must be created
    74         // before the Next node. Should we create a "Constant" flag for this?
    75         Assign * assign = new Assign(expr, outputIndex, mSymbolGenerator->make(prefix), this);
    76         insert(assign);
    77         return assign;
    78     }
    79 
    80     Assign * createImmutableAssign(const std::string prefix, PabloAST * expr, const int outputIndex = -1);
     85    Assign * createAssign(const std::string prefix, PabloAST * expr, const int outputIndex = -1);
    8186
    8287    Var * createVar(const std::string name);
     
    114119    Sel * createSelImm(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr);
    115120
    116     inline If * createIf(PabloAST * condition, std::vector<Assign *> && definedVars, PabloBlock & body) {
    117         If * statement = new If(condition, std::move(definedVars), body, this);
    118         insert(statement);
    119         return statement;
    120     }
     121    If * createIf(PabloAST * condition, std::vector<Assign *> && definedVars, PabloBlock & body);
    121122
    122     inline While * createWhile(PabloAST * cond, PabloBlock & body) {
    123         While * statement = new While(cond, body, this);
    124         insert(statement);
    125         return statement;
    126     }
    127 
    128     PabloAST * setOperandOf(Statement * inst, const unsigned index, PabloAST * value);
    129 
    130     template<typename... Args>
    131     struct ExpressionMap {
    132         enum {N = sizeof...(Args)};
    133         typedef ExpressionMap<Args...> MapType;
    134         typedef std::tuple<PabloAST::ClassTypeId, Args...> Key;
    135 
    136         inline ExpressionMap(MapType * predecessor)
    137         : mPredecessor(predecessor)
    138         {
    139 
    140         }
    141 
    142         template <class Type, typename... Params>
    143         inline std::pair<Type *, bool> findOrMake(const PabloAST::ClassTypeId type, Args... args, Params... params) {
    144             Key key = std::make_tuple(type, args...);
    145             PabloAST * const f = find(key);
    146             if (f) {
    147                 return std::make_pair(cast<Type>(f), false);
    148             }
    149             PabloAST * const expr = new Type(std::forward<Args>(args)..., std::forward<Params>(params)...);
    150             mMap.insert(std::make_pair(std::move(key), expr));
    151             return std::make_pair(cast<Type>(expr), isa<Statement>(expr));
    152         }
    153 
    154         template <class Functor, typename... Params>
    155         inline PabloAST * findOrCall(const PabloAST::ClassTypeId type, Args... args, Params... params) {
    156             Key key = std::make_tuple(type, args...);
    157             PabloAST * const f = find(key);
    158             if (f) {
    159                 return f;
    160             }
    161             Functor mf;
    162             PabloAST * const expr = mf(std::forward<Args>(args)..., std::forward<Params>(params)...);
    163             mMap.insert(std::make_pair(std::move(key), expr));
    164             return expr;
    165         }
    166 
    167         template <class Functor, typename... Params>
    168         inline PabloAST * findOrAdd(const PabloAST::ClassTypeId type, Args... args, PabloAST * expr) {
    169             Key key = std::make_tuple(type, args...);
    170             PabloAST * const f = find(key);
    171             if (f) {
    172                 return f;
    173             }
    174             mMap.insert(std::make_pair(std::move(key), expr));
    175             return expr;
    176         }
    177 
    178         inline bool erase(const PabloAST::ClassTypeId type, Args... args) {
    179             Key key = std::make_tuple(type, args...);
    180             auto itr = mMap.find(key);
    181             if (itr == mMap.end()) {
    182                 return mPredecessor ? mPredecessor->erase(type, args...) : false;
    183             }
    184             mMap.erase(itr);
    185             return true;
    186         }
    187 
    188         inline PabloAST * find(const Key & key) const {
    189             // check this map to see if we have it
    190             auto itr = mMap.find(key);
    191             if (itr != mMap.end()) {
    192                 return itr->second;
    193             }
    194             // check any previous maps to see if it exists
    195             auto * pred = mPredecessor;
    196             while (pred) {
    197                 itr = pred->mMap.find(key);
    198                 if (itr == pred->mMap.end()) {
    199                     pred = pred->mPredecessor;
    200                     continue;
    201                 }
    202                 return itr->second;
    203             }
    204             return nullptr;
    205         }
    206 
    207     private:
    208         MapType * const             mPredecessor;
    209         std::map<Key, PabloAST *>   mMap;
    210     };
     123    While * createWhile(PabloAST * cond, PabloBlock & body);
    211124
    212125    inline StatementList & statements() {
     
    217130        return *this;
    218131    }
     132
    219133    inline String * getName(const std::string name) const {
    220134        return mSymbolGenerator->get(name);
    221135    }
     136
    222137    inline String * makeName(const std::string prefix) const {
    223138        return mSymbolGenerator->make(prefix);
    224139    }
     140
    225141protected:
    226     PabloBlock()
    227     : mZeroes(new Zeroes())
    228     , mOnes(new Ones())
    229     , mSymbolGenerator(new SymbolGenerator())
    230     , mUnary(nullptr)
    231     , mUnaryWithInt(nullptr)
    232     , mBinary(nullptr)
    233     , mTernary(nullptr)
    234     {
     142    PabloBlock();
    235143
    236     }
     144    PabloBlock(PabloBlock * predecessor);
    237145
    238     PabloBlock(PabloBlock * predecessor)
    239     : mZeroes(predecessor->mZeroes) // inherit the original "Zeroes" variable for simplicity
    240     , mOnes(predecessor->mOnes) // inherit the original "Ones" variable for simplicity
    241     , mSymbolGenerator(predecessor->mSymbolGenerator)
    242     , mUnary(&(predecessor->mUnary))
    243     , mUnaryWithInt(&(predecessor->mUnaryWithInt))
    244     , mBinary(&(predecessor->mBinary))
    245     , mTernary(&(predecessor->mTernary))
    246     {
    247 
    248     }
    249 
    250     void* operator new (std::size_t size) noexcept {
     146    void * operator new (std::size_t size) noexcept {
    251147        return PabloAST::mAllocator.allocate(size);
    252148    }
    253149
    254150    template<typename Type>
    255     inline Type insertIfNew(std::pair<Type, bool> retVal) {
    256         if (std::get<1>(retVal)) {
    257             insert(cast<Statement>(std::get<0>(retVal)));
     151    inline Type * insertAtInsertionPoint(Type * expr) {
     152        if (isa<Statement>(expr)) {
     153            insert(cast<Statement>(expr));
    258154        }
    259         return std::get<0>(retVal);
     155        return expr;
    260156    }
    261157
     
    264160    Ones * const                                        mOnes;
    265161    SymbolGenerator * const                             mSymbolGenerator;
    266     ExpressionMap<PabloAST *>                           mUnary;
    267     ExpressionMap<PabloAST *, int>                      mUnaryWithInt;
    268     ExpressionMap<PabloAST *, PabloAST *>               mBinary;
    269     ExpressionMap<PabloAST *, PabloAST *, PabloAST *>   mTernary;
    270162};
    271163
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4415 r4416  
    111111}
    112112
    113 PabloAST * Statement::setOperand(const unsigned index, PabloAST * value) {
     113void PabloAST::replaceAllUsesWith(PabloAST * expr) {
     114    #ifndef NDEBUG
     115    unsigned __userCount = getNumUses();
     116    #endif
     117    while (!mUsers.empty()) {
     118        PabloAST * user = mUsers.pop_back_val();
     119        assert(--__userCount == getNumUses());
     120        if (isa<Statement>(user)) {
     121            cast<Statement>(user)->replaceUsesOfWith(this, expr);
     122        }
     123        assert(__userCount == getNumUses());
     124    }
     125    assert (getNumUses() == 0);
     126}
     127
     128void Statement::setOperand(const unsigned index, PabloAST * value) {
    114129    assert (index < getNumOperands());
    115     return mParent->setOperandOf(this, index, value);
     130    if (LLVM_UNLIKELY(mOperand[index] == value)) {
     131        return;
     132    }
     133    PabloAST * priorValue = mOperand[index];
     134    // Test just to be sure we don't have multiple operands pointing to
     135    // what we're replacing. If not, remove this from the prior value's
     136    // user list.
     137    unsigned count = 0;
     138    for (unsigned i = 0; i != getNumOperands(); ++i) {
     139        count += (mOperand[index] == priorValue) ? 1 : 0;
     140    }
     141    assert (count >= 1);
     142    if (LLVM_LIKELY(count == 1)) {
     143        priorValue->removeUser(this);
     144    }
     145    mOperand[index] = value;
     146    value->addUser(this);
    116147}
    117148
     
    150181}
    151182
    152 void Statement::removeFromParent() {
     183Statement * Statement::removeFromParent() {
     184    Statement * next = mNext;
    153185    if (LLVM_LIKELY(mParent != nullptr)) {
    154186        if (LLVM_UNLIKELY(mParent->mFirst == this)) {
     
    171203    mNext = nullptr;
    172204    mParent = nullptr;
    173 }
    174 
    175 void Statement::replaceWith(Statement * const statement) {
    176     if (statement != this) {
    177         statement->removeFromParent();
    178         statement->mParent = mParent;
    179         statement->mNext = mNext;
    180         statement->mPrev = mPrev;
     205    return next;
     206}
     207
     208Statement * Statement::eraseFromParent(const bool recursively) {
     209    Statement * next = removeFromParent();
     210    // remove this statement from its operands' users list
     211    for (PabloAST * op : mOperand) {
     212        op->removeUser(this);
     213        if (recursively && isa<Statement>(op) && op->getNumUses() == 0) {
     214            cast<Statement>(op)->eraseFromParent();
     215        }
     216    }
     217    return next;
     218}
     219
     220void Statement::replaceWith(PabloAST * const expr) {
     221
     222    if (LLVM_UNLIKELY(expr == this)) {
     223        return;
     224    }
     225
     226    if (isa<Statement>(expr)) {
     227        Statement * stmt = cast<Statement>(expr);
     228        stmt->removeFromParent();
     229        stmt->mParent = mParent;
     230        stmt->mNext = mNext;
     231        stmt->mPrev = mPrev;
    181232        if (LLVM_LIKELY(mPrev != nullptr)) {
    182             mPrev->mNext = statement;
     233            mPrev->mNext = stmt;
    183234        }
    184235        if (LLVM_LIKELY(mNext != nullptr)) {
    185             mNext->mPrev = statement;
     236            mNext->mPrev = stmt;
    186237        }
    187238        mParent=nullptr;
     
    189240        mPrev=nullptr;
    190241    }
     242    else {
     243        removeFromParent();
     244    }
     245
     246    // remove this statement from its operands' users list
     247    for (PabloAST * op : mOperand) {
     248        op->removeUser(this);
     249    }
     250
     251    while (!mUsers.empty()) {
     252        PabloAST * user = mUsers.pop_back_val();
     253        if (isa<Statement>(user)) {
     254            assert(std::count(cast<Statement>(user)->mOperand.begin(), cast<Statement>(user)->mOperand.end(), this) == 1);
     255            cast<Statement>(user)->replaceUsesOfWith(this, expr);
     256        }
     257    }
     258
    191259}
    192260
    193261Statement::~Statement() {
    194262
    195 }
    196 
    197 void StatementList::setInsertPoint(Statement * const statement) {
    198     mInsertionPoint = statement;
    199 }
    200 
    201 void StatementList::setInsertPoint(StatementList * const list) {
    202     mInsertionPoint = list->mLast;
    203263}
    204264
     
    220280}
    221281
    222 void StatementList::insertAfterLastOperand(Statement * const statement) {
    223     assert (false);
    224 }
    225 
    226 }
     282}
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r4415 r4416  
    3232    friend class SymbolGenerator;
    3333    typedef std::unordered_map<std::string, PMDNode *> PMDNodeMap;
     34
    3435public:
     36
     37    using Users = SetVector<PabloAST *>;
     38    using user_iterator = Users::iterator;
     39
    3540    typedef SlabAllocator<4096> Allocator;
    3641    enum class ClassTypeId : unsigned {
     
    6671    }
    6772
     73    inline user_iterator user_begin() const {
     74        return mUsers.begin();
     75    }
     76
     77    inline user_iterator user_end() const {
     78        return mUsers.end();
     79    }
     80
     81    inline Users & users() {
     82        return mUsers;
     83    }
     84
     85    inline const Users & users() const {
     86        return mUsers;
     87    }
     88
     89    void replaceAllUsesWith(PabloAST * expr);
     90
     91    inline Users::size_type getNumUses() const {
     92        return mUsers.size();
     93    }
     94
    6895    void* operator new (std::size_t size) noexcept {
    6996        return mAllocator.allocate(size);
     
    76103
    77104    }
    78     inline void addUser(PabloAST * user) {
     105    inline void addUser(PabloAST * user) {       
    79106        mUsers.insert(user);
    80107    }
     
    85112private:
    86113    const ClassTypeId       mClassTypeId;
    87     SetVector<PabloAST *>   mUsers;
     114    Users                   mUsers;
    88115    PMDNodeMap *            mMetadataMap;
    89116};
     
    99126    friend class If;
    100127    friend class While;
     128    friend class Simplifier;
    101129    friend class PabloBlock;
    102130public:
     
    104132        switch (e->getClassTypeId()) {
    105133            case PabloAST::ClassTypeId::String:
     134            case PabloAST::ClassTypeId::Integer:
     135            case PabloAST::ClassTypeId::Zeroes:
     136            case PabloAST::ClassTypeId::Ones:
     137            case PabloAST::ClassTypeId::Var:
    106138                return false;
    107139            default:
     
    116148    }
    117149
    118     inline PabloAST * replaceUsesOfWith(PabloAST * from, PabloAST * to) {
    119         if (from == to) {
    120             return this;
    121         }
     150    inline void replaceUsesOfWith(PabloAST * from, PabloAST * to) {
    122151        for (unsigned i = 0; i != getNumOperands(); ++i) {
    123152            if (getOperand(i) == from) {
    124                 return setOperand(i, to);
     153                setOperand(i, to);
    125154            }
    126155        }
    127         return this;
    128     }
    129 
    130     PabloAST * getOperand(const unsigned index) const {
     156    }
     157
     158    inline PabloAST * getOperand(const unsigned index) const {
    131159        assert (index < getNumOperands());
    132160        return mOperand[index];
    133161    }
    134162
    135     PabloAST * setOperand(const unsigned index, PabloAST * value);
    136 
    137     unsigned getNumOperands() const {
     163    void setOperand(const unsigned index, PabloAST * value);
     164
     165    inline unsigned getNumOperands() const {
    138166        return mOperand.size();
    139167    }
     
    141169    void insertBefore(Statement * const statement);
    142170    void insertAfter(Statement * const statement);
    143     void removeFromParent();
    144     void replaceWith(Statement * const statement);
     171    Statement * removeFromParent();
     172    Statement * eraseFromParent(const bool recursively = false);
     173    void replaceWith(PabloAST * const expr);
    145174
    146175    inline const String * getName() const {
     
    169198        }
    170199    }
    171 
     200    inline void setName(const String * name) {
     201        mName = name;
     202    }
    172203    virtual ~Statement() = 0;
    173204protected:
     
    397428    }
    398429
    399     Statement * front() const {
     430    inline Statement * front() const {
    400431        return mFirst;
    401432    }
    402433
    403     Statement * back() const {
     434    inline Statement * back() const {
    404435        return mLast;
    405436    }
    406437
    407     void setInsertPoint(Statement * const statement);
    408 
    409     void setInsertPoint(StatementList * const list);
    410 
    411     Statement * getInsertPoint() const {
     438    inline void setInsertPoint(Statement * const statement) {
     439        mInsertionPoint = statement;
     440    }
     441
     442    inline void setInsertPoint(StatementList * const list) {
     443        mInsertionPoint = list->back();
     444    }
     445
     446    inline Statement * getInsertPoint() const {
    412447        return mInsertionPoint;
    413448    }
    414449
    415450    void insert(Statement * const statement);
    416 
    417     void insertAfterLastOperand(Statement * const statement);
    418451
    419452private:
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

    r4415 r4416  
    1818#include <stdexcept>
    1919#include <include/simd-lib/bitblock.hpp>
     20#include <sstream>
    2021
    2122#ifdef USE_LLVM_3_4
     
    617618        //End Block
    618619        IRBuilder<> bEnd(ifEndBlock);
    619         for (const Assign * a : ifStatement->getDefined()) {
     620        for (const Statement * a : ifStatement->getDefined()) {
    620621            PHINode * phi = bEnd.CreatePHI(mBitBlockType, 2, a->getName()->str());
    621622            auto f = mMarkerMap.find(a);
     
    840841    auto f = mMarkerMap.find(expr);
    841842    if (f == mMarkerMap.end()) {
    842         throw std::runtime_error("Unrecognized Pablo expression type; can't compile.");
     843        std::stringstream str;
     844        str << "\"";
     845        PabloPrinter::print(expr, str);
     846        str << "\" was used before definition!";
     847        throw std::runtime_error(str.str());
    843848    }
    844849    return f->second;
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.h

    r4410 r4416  
    1818
    1919//Pablo Expressions
    20 #include <pablo/codegenstate.h>
    21 #include <pablo/pabloAST.h>
    2220#include <string>
    2321#include <list>
     
    2523#include <algorithm>
    2624#include <llvm/ADT/Twine.h>
     25#include <unordered_map>
     26#include <string>
    2727
    2828namespace llvm {
     
    3636    class FunctionType;
    3737    class Function;
     38    class BasicBlock;
    3839}
     40
     41namespace pablo {
    3942
    4043using namespace llvm;
    4144
    42 namespace pablo {
     45class PabloAST;
     46class PabloBlock;
     47class String;
     48class Var;
     49class Statement;
     50class StatementList;
    4351
    4452struct LLVM_Gen_RetVal
  • icGREP/icgrep-devel/icgrep/pablo/pe_and.cpp

    r4414 r4416  
    77#include <pablo/pe_and.h>
    88#include <pablo/codegenstate.h>
     9#include <pablo/pe_not.h>
     10#include <pablo/pe_zeroes.h>
     11#include <pablo/pe_ones.h>
    912
    1013namespace pablo {
     
    1720
    1821PabloAST * OptimizeAnd::operator ()(PabloAST * expr1, PabloAST * expr2, PabloBlock * pb) {
     22
     23    assert (expr1 && expr2 && pb);
     24
    1925    if (isa<Zeroes>(expr2) || isa<Ones>(expr1)) {
    2026        return expr2;
  • icGREP/icgrep-devel/icgrep/pablo/pe_integer.h

    r4415 r4416  
    77
    88class Integer : public PabloAST {
    9     using value_t = size_t;
     9    friend class SymbolGenerator;
     10    typedef u_int64_t integer_t;
    1011    static inline bool classof(const PabloAST * e) {
    1112        return e->getClassTypeId() == ClassTypeId::Integer;
     
    1718
    1819    }
    19     inline value_t value() const {
     20    inline integer_t value() const {
    2021        return mValue;
    2122    }
    2223protected:
    23     Integer(const value_t value) noexcept
     24    Integer(const integer_t value) noexcept
    2425    : PabloAST(ClassTypeId::Integer)
    2526    , mValue(value)
     
    2829    }
    2930private:
    30     const value_t mValue;
     31    const integer_t mValue;
    3132};
    3233
  • icGREP/icgrep-devel/icgrep/pablo/pe_next.h

    r4414 r4416  
    2828protected:
    2929    Next(PabloAST * initial, PabloAST * expr, PabloBlock * parent)
    30     : Statement(ClassTypeId::Next, {{cast<Assign>(initial), expr}}, cast<Assign>(initial)->getName(), parent)
    31     {
    32 
     30    : Statement(ClassTypeId::Next, {{cast<Assign>(initial), expr}}, cast<Assign>(initial)->getName(), parent) {
     31        this->addUser(initial);
    3332    }
    3433};
  • icGREP/icgrep-devel/icgrep/pablo/pe_not.cpp

    r4414 r4416  
    77#include <pablo/pe_not.h>
    88#include <pablo/codegenstate.h>
    9 
     9#include <pablo/pe_ones.h>
     10#include <pablo/pe_zeroes.h>
    1011
    1112namespace pablo {
     
    1819
    1920PabloAST * OptimizeNot::operator ()(PabloAST * expr, PabloBlock * pb) {
     21
     22    assert (expr && pb);
     23
    2024    if (isa<Ones>(expr)) {
    2125        return pb->createZeroes();
  • icGREP/icgrep-devel/icgrep/pablo/pe_or.cpp

    r4414 r4416  
    77#include <pablo/pe_or.h>
    88#include <pablo/codegenstate.h>
     9#include <pablo/pe_ones.h>
     10#include <pablo/pe_zeroes.h>
     11#include <pablo/pe_not.h>
     12#include <pablo/pe_and.h>
    913
    1014namespace pablo {
     
    1721
    1822PabloAST * OptimizeOr::operator ()(PabloAST * expr1, PabloAST * expr2, PabloBlock * pb) {
     23
     24    assert (expr1 && expr2 && pb);
     25
    1926    if (isa<Zeroes>(expr2) || isa<Ones>(expr1)) {
    2027        return expr1;
  • icGREP/icgrep-devel/icgrep/pablo/pe_sel.cpp

    r4414 r4416  
    77#include <pablo/pe_sel.h>
    88#include <pablo/codegenstate.h>
     9#include <pablo/pe_ones.h>
     10#include <pablo/pe_zeroes.h>
     11#include <pablo/pe_not.h>
     12
    913
    1014namespace pablo {
     
    1721
    1822PabloAST * OptimizeSel::operator()(PabloAST * if_expr, PabloAST * t_expr, PabloAST * f_expr, PabloBlock * pb) {
     23
     24    assert (if_expr && t_expr && f_expr && pb);
     25
    1926    if (isa<Ones>(if_expr)) {
    2027        return t_expr;
  • icGREP/icgrep-devel/icgrep/pablo/pe_string.h

    r4415 r4416  
    88
    99class String : public PabloAST {
    10     friend String * makeString(const std::string value) noexcept;
     10    friend class SymbolGenerator;
    1111public:
    1212    static inline bool classof(const PabloAST * e) {
     
    3636};
    3737
    38 inline String * makeString(const std::string value) noexcept {
    39     return new String(std::move(value));
    40 }
    41 
    42 
    4338}
    4439
  • icGREP/icgrep-devel/icgrep/pablo/pe_xor.cpp

    r4414 r4416  
    77#include <pablo/pe_xor.h>
    88#include <pablo/codegenstate.h>
     9#include <pablo/pe_ones.h>
     10#include <pablo/pe_zeroes.h>
     11#include <pablo/pe_not.h>
    912
    1013namespace pablo {
     
    1720
    1821PabloAST * OptimizeXor::operator()(PabloAST * expr1, PabloAST * expr2, PabloBlock * pb) {
     22
     23    assert (expr1 && expr2 && pb);
     24
    1925    if (isa<Ones>(expr1)) {
    2026        return pb->createNot(expr2);
  • icGREP/icgrep-devel/icgrep/pablo/printer_pablos.cpp

    r4410 r4416  
    5151    for (const Statement * stmt : stmts) {
    5252        print(stmt, indent, strm);
     53        strm << std::endl;
    5354    }
    5455}
     
    5758    strm << indent;
    5859    if (stmt == nullptr) {
    59         strm << "<null-stmt>" << std::endl;
     60        strm << "<null-stmt>";
    6061    }
    6162    else if (const Assign * an = dyn_cast<const Assign>(stmt)) {
     
    6566        strm << an->getName()->str() << " = ";
    6667        print(an->getExpr(), strm);
    67         strm << std::endl;
    6868    }
    6969    else if (const Next * next = dyn_cast<const Next>(stmt)) {       
    7070        strm << "Next(" << next->getName()->str() << ") = ";
    7171        print(next->getExpr(), strm);
    72         strm << std::endl;
    7372    }
    7473    else if (const If * ifstmt = dyn_cast<const If>(stmt)) {
     
    8685    else if (const Call * pablo_call = dyn_cast<const Call>(stmt)) {
    8786        print(pablo_call, strm);
    88         strm << " = " << pablo_call->getCallee()->str() << "()" << std::endl;;
     87        strm << " = " << pablo_call->getCallee()->str() << "()";
    8988    }
    9089    else if (const And * pablo_and = dyn_cast<const And>(stmt)) {
     
    9493        strm << " & ";
    9594        print(pablo_and->getExpr2(), strm);
    96         strm << ")" << std::endl;;
     95        strm << ")";
    9796    }
    9897    else if (const Or * pablo_or = dyn_cast<const Or>(stmt)) {
     
    102101        strm << " | ";
    103102        print(pablo_or->getExpr2(), strm);
    104         strm << ")" << std::endl;;
     103        strm << ")";
    105104    }
    106105    else if (const Xor * pablo_xor = dyn_cast<const Xor>(stmt)) {
     
    110109        strm << " ^ ";
    111110        print(pablo_xor->getExpr2(), strm);
    112         strm << ")" << std::endl;;
     111        strm << ")";
    113112    }
    114113    else if (const Sel * pablo_sel = dyn_cast<const Sel>(stmt)) {
     
    120119        strm << " : ";
    121120        print(pablo_sel->getFalseExpr(), strm);
    122         strm << ")" << std::endl;;
     121        strm << ")";
    123122    }
    124123    else if (const Not * pablo_not = dyn_cast<const Not>(stmt)) {
     
    126125        strm << " = (~";
    127126        print(pablo_not->getExpr(), strm);
    128         strm << ")" << std::endl;;
     127        strm << ")";
    129128    }
    130129    else if (const Advance * adv = dyn_cast<const Advance>(stmt)) {
     
    132131        strm << " = pablo.Advance(";
    133132        print(adv->getExpr(), strm);
    134         strm << ", " << std::to_string(adv->getAdvanceAmount()) << ")" << std::endl;;
     133        strm << ", " << std::to_string(adv->getAdvanceAmount()) << ")";
    135134    }
    136135    else if (const MatchStar * mstar = dyn_cast<const MatchStar>(stmt)) {
     
    140139        strm << ", ";
    141140        print(mstar->getCharClass(), strm);
    142         strm << ")" << std::endl;;
     141        strm << ")";
    143142    }
    144143    else if (const ScanThru * sthru = dyn_cast<const ScanThru>(stmt)) {
     
    148147        strm << ", ";
    149148        print(sthru->getScanThru(), strm);
    150         strm << ")" << std::endl;;
     149        strm << ")";
    151150    }
    152151    else {
  • icGREP/icgrep-devel/icgrep/pablo/ps_assign.h

    r4414 r4416  
    99
    1010#include <pablo/pe_string.h>
    11 #include <pablo/symbol_generator.h>
    12 #include <array>
    1311
    1412namespace pablo {
     
    3634        return mOutputIndex;
    3735    }
     36    bool isConstant() const;
    3837protected:
    3938    explicit Assign(PabloAST * expr, int outputIndex, String * name, PabloBlock * parent)
  • icGREP/icgrep-devel/icgrep/pablo/ps_if.cpp

    r4415 r4416  
    11#include <pablo/ps_if.h>
    22#include <pablo/codegenstate.h>
     3#include <pablo/ps_assign.h>
    34
    45namespace pablo {
     
    2021    // embedded into the If, the defined var is a user of the If node.
    2122
    22     for (Assign * x : mDefined) {
    23         addUser(x);
     23    for (PabloAST * assign : mDefined) {
     24        assign->addUser(this);
     25        addUser(assign);
     26    }
     27}
     28
     29void If::replaceCondOrDefinedVar(PabloAST * from, PabloAST * to) {
     30    if (mOperand[0] == from) {
     31        mOperand[0] = to;
     32    }
     33    if (isa<Statement>(from) && mDefined.remove(cast<Statement>(from))) {
     34        if (isa<Statement>(to)) {
     35            mDefined.insert(cast<Statement>(to));
     36        }
    2437    }
    2538}
  • icGREP/icgrep-devel/icgrep/pablo/ps_if.h

    r4415 r4416  
    3737        return mBody;
    3838    }
    39     inline const SetVector<Assign*> & getDefined() const {
     39    inline const SetVector<Statement *> & getDefined() const {
    4040        return mDefined;
    4141    }
     
    5454protected:
    5555    If(PabloAST * expr, DefinedVars && definedVars, PabloBlock & body, PabloBlock * parent);
     56
     57    void replaceCondOrDefinedVar(PabloAST * from, PabloAST * to);
     58
    5659private:
    57     PabloBlock &        mBody;
    58     SetVector<Assign*>  mDefined;
    59     unsigned            mCarryCount;
    60     unsigned            mAdvanceCount;
     60    PabloBlock &            mBody;
     61    SetVector<Statement *>  mDefined;
     62    unsigned                mCarryCount;
     63    unsigned                mAdvanceCount;
    6164};
    6265
  • icGREP/icgrep-devel/icgrep/pablo/symbol_generator.cpp

    r4410 r4416  
    77#include <pablo/symbol_generator.h>
    88#include <pablo/pe_string.h>
     9#include <pablo/pe_integer.h>
    910
    1011namespace pablo {
     
    2021    String * result;
    2122    if (f == mStringMap.end()) {
    22         result = makeString(name);
    23         mStringMap.insert(std::make_pair(std::move(name), result));
     23        result = new String(std::move(name));
     24        mStringMap.insert(std::make_pair(name, result));
     25    }
     26    else {
     27        result = f->second;
     28    }
     29    return result;
     30}
     31
     32Integer * SymbolGenerator::get(const integer_t value) {
     33    auto f = mIntegerMap.find(value);
     34    Integer * result;
     35    if (f == mIntegerMap.end()) {
     36        result = new Integer(value);
     37        mIntegerMap.insert(std::make_pair(value, result));
    2438    }
    2539    else {
  • icGREP/icgrep-devel/icgrep/pablo/symbol_generator.h

    r4410 r4416  
    1515
    1616class String;
     17class Integer;
    1718
    1819class SymbolGenerator {
    1920    friend class PabloBlock;
    2021public:
     22    typedef u_int64_t integer_t;
     23
    2124    String * get(const std::string name);
    2225    String * make(const std::string prefix);
     26    Integer * get(const integer_t value);
    2327protected:
    2428    SymbolGenerator();
     
    2731    }
    2832private:
    29     std::unordered_map<std::string, unsigned>   mPrefixMap;
     33    std::unordered_map<std::string, unsigned>   mPrefixMap;   
    3034    std::unordered_map<std::string, String *>   mStringMap;
     35    std::unordered_map<integer_t, Integer *>    mIntegerMap;
    3136};
    3237
  • icGREP/icgrep-devel/icgrep/re/re_compiler.cpp

    r4411 r4416  
    415415        PabloAST * loopComputation = markerVar(AdvanceMarker(process(repeated, makeMarker(InitialPostPositionByte, whileTest), wb), InitialPostPositionByte, wb));
    416416        Next * nextWhileTest = wb.createNext(whileTest, wb.createAnd(loopComputation, wb.createNot(whileAccum)));
    417         wb.createNext(whileAccum, wb.createOr(loopComputation, whileAccum));
     417        Next * nextWhileAccum = wb.createNext(whileAccum, wb.createOr(loopComputation, whileAccum));
    418418
    419419        pb.createWhile(nextWhileTest, wb);
    420420
    421         return makeMarker(InitialPostPositionByte, pb.createAssign("unbounded", whileAccum));
     421        return makeMarker(InitialPostPositionByte, pb.createAssign("unbounded", nextWhileAccum));
    422422    }   
    423423} // end of namespace re
Note: See TracChangeset for help on using the changeset viewer.