Changeset 4264


Ignore:
Timestamp:
Oct 23, 2014, 8:02:32 PM (3 years ago)
Author:
nmedfort
Message:

Eliminated need for Mem2Reg pass. Automatic introduction of PHI nodes for Next nodes.

Location:
icGREP/icgrep-devel/icgrep
Files:
11 edited

Legend:

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

    r4260 r4264  
    1212/// UNARY CREATE FUNCTIONS
    1313
    14 PabloAST * PabloBlock::createAdvance(PabloAST * expr, int shiftAmount) {
     14PabloAST * PabloBlock::createAdvance(PabloAST * expr, const int shiftAmount) {
    1515    if (isa<Zeroes>(expr)) {
    1616        return expr;
     
    2727}
    2828
    29 Var * PabloBlock::createVar(String * name, const bool internal) {
    30     // Note: this is a unary function; internal is a hidden property passed into the constructor
    31     // when instantiating a new variable.
    32     return mUnary.findOrMake<Var>(PabloAST::ClassTypeId::Var, name, internal);
     29Var * PabloBlock::createVar(const std::string name) {
     30    return mUnary.findOrMake<Var>(PabloAST::ClassTypeId::Var, mSymbolGenerator.get(name));
     31}
     32
     33Var * PabloBlock::createVar(Assign * assign) {
     34    return mUnary.findOrMake<Var>(PabloAST::ClassTypeId::Var, assign);
     35}
     36
     37Var * PabloBlock::createVar(Next * next) {
     38    return mUnary.findOrMake<Var>(PabloAST::ClassTypeId::Var, next);
    3339}
    3440
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r4260 r4264  
    6363    }
    6464
    65     PabloAST * createAdvance(PabloAST * expr, int shiftAmount);
     65    PabloAST * createAdvance(PabloAST * expr, const int shiftAmount);
    6666
    6767    inline Zeroes * createZeroes() const {
     
    8383    }
    8484
    85     inline Var * createVar(const std::string name) {
    86         return createVar(mSymbolGenerator.get(name), false);
    87     }
    88 
    89     inline Var * createVar(Assign * assign) {
    90         return createVar(assign->mName, true);
    91     }
    92 
    93     inline Var * createVar(Next * next) {
    94         return createVar(next->mInitial->mName, true);
    95     }
     85    Var * createVar(const std::string name);
     86
     87    Var * createVar(Assign * assign);
     88
     89    Var * createVar(Next * next);
    9690
    9791    inline PabloAST * createVar(PabloAST * const input) {
     
    202196    };
    203197
    204     inline const ExpressionList & expressions() const {
     198    inline const StatementList & expressions() const {
    205199        return mStatements;
    206200    }
    207 
    208 protected:
    209 
    210     Var * createVar(String * name, const bool internal);
    211 
    212201private:       
    213202    Zeroes * const                                      mZeroes;
     
    218207    ExpressionMap<PabloAST *, PabloAST *>               mBinary;
    219208    ExpressionMap<PabloAST *, PabloAST *, PabloAST *>   mTernary;
    220     ExpressionList                                      mStatements;
     209    StatementList                                      mStatements;
    221210};
    222211
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r4252 r4264  
    5252bool equals(const PabloAST * expr1, const PabloAST *expr2);
    5353
    54 typedef std::vector<PabloAST *> ExpressionList;
     54typedef std::vector<PabloAST *> StatementList;
    5555
    5656}
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

    r4261 r4264  
    9898    InitializeNativeTarget();
    9999    std::string ErrStr;
    100     mExecutionEngine = EngineBuilder(mMod).setUseMCJIT(true).setErrorStr(&ErrStr).setOptLevel(CodeGenOpt::Level::Less).create();
     100    mExecutionEngine = EngineBuilder(mMod).setUseMCJIT(true).setErrorStr(&ErrStr).setOptLevel(CodeGenOpt::Level::None).create();
    101101    if (mExecutionEngine == nullptr) {
    102102        throw std::runtime_error("Could not create ExecutionEngine: " + ErrStr);
     
    170170        Value* indices[] = {b.getInt64(0), b.getInt32(i)};
    171171        const String * const name = mBasisBitVars[i]->getName();
    172         mMarkerMap.insert(std::make_pair(name, b.CreateGEP(mBasisBitsAddr, indices, name->str())));
     172        Value * gep = b.CreateGEP(mBasisBitsAddr, indices);
     173        LoadInst * basisBit = b.CreateAlignedLoad(gep, BLOCK_SIZE/8, false, name->str());
     174        mMarkerMap.insert(std::make_pair(name, basisBit));
    173175    }
    174176
     
    176178    Value * result = compileStatements(pb.expressions());
    177179    SetReturnMarker(result, 0); // matches
    178 
    179180    const String * lf = pb.createVar(mNameMap["LineFeed"]->getName())->getName();
    180 
    181     SetReturnMarker(GetMarker(lf), 1); // line feeds
     181    SetReturnMarker(mMarkerMap.find(lf)->second, 1); // line feeds
    182182
    183183    assert (mCarryQueueIdx == mCarryQueueSize);
     
    212212#endif
    213213
    214     fpm.add(createPromoteMemoryToRegisterPass()); //Transform to SSA form.
    215     fpm.add(createBasicAliasAnalysisPass());      //Provide basic AliasAnalysis support for GVN. (Global Value Numbering)
    216     fpm.add(createCFGSimplificationPass());       //Simplify the control flow graph.
     214    //fpm.add(createPromoteMemoryToRegisterPass()); //Transform to SSA form.
     215    //fpm.add(createBasicAliasAnalysisPass());      //Provide basic AliasAnalysis support for GVN. (Global Value Numbering)
     216    //fpm.add(createCFGSimplificationPass());       //Simplify the control flow graph.
    217217    fpm.add(createInstructionCombiningPass());    //Simple peephole optimizations and bit-twiddling.
    218218    fpm.add(createReassociatePass());             //Reassociate expressions.
     
    371371}
    372372
    373 void PabloCompiler::DeclareCallFunctions(const ExpressionList & stmts) {
     373void PabloCompiler::DeclareCallFunctions(const StatementList & stmts) {
    374374    for (PabloAST * stmt : stmts) {
    375375        if (const Assign * assign = dyn_cast<Assign>(stmt)) {
     
    496496void PabloCompiler::SetReturnMarker(Value * marker, const unsigned index) {
    497497    IRBuilder<> b(mBasicBlock);
    498     Value* marker_bitblock = b.CreateAlignedLoad(marker, BLOCK_SIZE/8, false);
    499     Value* output_indices[] = {b.getInt64(0), b.getInt32(index)};
    500     Value* output_struct_GEP = b.CreateGEP(mOutputAddrPtr, output_indices);
    501     b.CreateAlignedStore(marker_bitblock, output_struct_GEP, BLOCK_SIZE/8, false);
    502 }
    503 
    504 
    505 Value * PabloCompiler::compileStatements(const ExpressionList & stmts) {
     498    if (marker->getType()->isPointerTy()) {
     499        marker = b.CreateAlignedLoad(marker, BLOCK_SIZE/8, false);
     500    }
     501    Value* indices[] = {b.getInt64(0), b.getInt32(index)};
     502    Value* gep = b.CreateGEP(mOutputAddrPtr, indices);
     503    b.CreateAlignedStore(marker, gep, BLOCK_SIZE/8, false);
     504}
     505
     506
     507Value * PabloCompiler::compileStatements(const StatementList & stmts) {
    506508    Value * retVal = nullptr;
    507509    for (PabloAST * statement : stmts) {
     
    517519    {
    518520        Value* expr = compileExpression(assign->getExpr());
    519         Value* marker = GetMarker(assign->getName());
    520         IRBuilder<> b(mBasicBlock);
    521         b.CreateAlignedStore(expr, marker, BLOCK_SIZE/8, false);
    522         retVal = marker;
     521        mMarkerMap[assign->getName()] = expr;
     522        retVal = expr;
    523523    }
    524524    if (const Next * next = dyn_cast<const Next>(stmt))
    525525    {
    526         IRBuilder<> b(mBasicBlock);
    527         auto f = mMarkerMap.find(next->getName());
    528         assert (f != mMarkerMap.end());
    529         Value * marker = f->second;
    530         Value * expr = compileExpression(next->getExpr());
    531         b.CreateAlignedStore(expr, marker, BLOCK_SIZE/8, false);
    532         retVal = marker;
     526        Value* expr = compileExpression(next->getExpr());
     527        mMarkerMap[next->getName()] = expr;
     528        retVal = expr;
    533529    }
    534530    else if (const If * ifstmt = dyn_cast<const If>(stmt))
     
    584580        retVal = returnMarker;
    585581    }
    586     else if (const While * whl = dyn_cast<const While>(stmt))
     582    else if (const While * whileStatement = dyn_cast<const While>(stmt))
    587583    {
    588584        const auto baseCarryQueueIdx = mCarryQueueIdx;
    589585        if (mNestingDepth == 0) {
    590             for (auto i = 0; i != whl->getInclusiveCarryCount(); ++i) {
     586            for (auto i = 0; i != whileStatement->getInclusiveCarryCount(); ++i) {
    591587                genCarryInLoad(baseCarryQueueIdx + i);
    592588            }
    593589        }       
    594590
    595         // First compile the initial iteration statements; the calls to genCarryOutStore will update the
     591        SmallVector<Next*, 4> nextNodes;
     592        for (PabloAST * node : whileStatement->getBody()) {
     593            if (isa<Next>(node)) {
     594                nextNodes.push_back(cast<Next>(node));
     595            }
     596        }
     597
     598        // Compile the initial iteration statements; the calls to genCarryOutStore will update the
    596599        // mCarryQueueVector with the appropriate values. Although we're not actually entering a new basic
    597600        // block yet, increment the nesting depth so that any calls to genCarryInLoad or genCarryOutStore
    598601        // will refer to the previous value.
    599602        ++mNestingDepth;
    600         compileStatements(whl->getBody());
     603        compileStatements(whileStatement->getBody());
    601604        // Reset the carry queue index. Note: this ought to be changed in the future. Currently this assumes
    602605        // that compiling the while body twice will generate the equivalent IR. This is not necessarily true
     
    616619        IRBuilder<> bCond(whileCondBlock);
    617620        // generate phi nodes for any carry propogating instruction
    618         std::vector<PHINode*> carryQueuePhiNodes(whl->getInclusiveCarryCount());
    619         for (auto i = 0; i != whl->getInclusiveCarryCount(); ++i) {
     621        std::vector<PHINode*> phiNodes(whileStatement->getInclusiveCarryCount() + nextNodes.size());
     622        unsigned index = 0;
     623        for (index = 0; index != whileStatement->getInclusiveCarryCount(); ++index) {
    620624            PHINode * phi = bCond.CreatePHI(mXi64Vect, 2);
    621             phi->addIncoming(mCarryQueueVector[baseCarryQueueIdx + i], mBasicBlock);
    622             mCarryQueueVector[baseCarryQueueIdx + i] = mZeroInitializer; // phi; // (use phi for multi-carry mode.)
    623             carryQueuePhiNodes[i] = phi;
     625            phi->addIncoming(mCarryQueueVector[baseCarryQueueIdx + index], mBasicBlock);
     626            mCarryQueueVector[baseCarryQueueIdx + index] = mZeroInitializer; // (use phi for multi-carry mode.)
     627            phiNodes[index] = phi;
     628        }
     629        // and for any Next nodes in the loop body
     630        for (Next * n : nextNodes) {
     631            PHINode * phi = bCond.CreatePHI(mXi64Vect, 2, n->getName()->str());
     632            auto f = mMarkerMap.find(n->getName());
     633            assert (f != mMarkerMap.end());
     634            phi->addIncoming(f->second, mBasicBlock);
     635            mMarkerMap[n->getName()] = phi;
     636            phiNodes[index++] = phi;
    624637        }
    625638
    626639        mBasicBlock = whileCondBlock;
    627         bCond.CreateCondBr(genBitBlockAny(compileExpression(whl->getCondition())), whileEndBlock, whileBodyBlock);
     640        bCond.CreateCondBr(genBitBlockAny(compileExpression(whileStatement->getCondition())), whileEndBlock, whileBodyBlock);
    628641
    629642        // BODY BLOCK
    630643        mBasicBlock = whileBodyBlock;
    631         retVal = compileStatements(whl->getBody());
     644        retVal = compileStatements(whileStatement->getBody());
    632645        // update phi nodes for any carry propogating instruction
    633646        IRBuilder<> bWhileBody(mBasicBlock);
    634         for (auto i = 0; i != whl->getInclusiveCarryCount(); ++i) {
    635             Value * carryOut = bWhileBody.CreateOr(carryQueuePhiNodes[i], mCarryQueueVector[baseCarryQueueIdx + i]);
    636             carryQueuePhiNodes[i]->addIncoming(carryOut, mBasicBlock);
    637             mCarryQueueVector[baseCarryQueueIdx + i] = carryQueuePhiNodes[i];
     647        for (index = 0; index != whileStatement->getInclusiveCarryCount(); ++index) {
     648            Value * carryOut = bWhileBody.CreateOr(phiNodes[index], mCarryQueueVector[baseCarryQueueIdx + index]);
     649            PHINode * phi = phiNodes[index];
     650            phi->addIncoming(carryOut, mBasicBlock);
     651            mCarryQueueVector[baseCarryQueueIdx + index] = phi;
     652        }
     653        // and for any Next nodes in the loop body
     654        for (Next * n : nextNodes) {
     655            auto f = mMarkerMap.find(n->getName());
     656            assert (f != mMarkerMap.end());
     657            PHINode * phi = phiNodes[index++];
     658            phi->addIncoming(f->second, mBasicBlock);
     659            mMarkerMap[n->getName()] = phi;
    638660        }
    639661
     
    643665        mBasicBlock = whileEndBlock;   
    644666        if (--mNestingDepth == 0) {
    645             for (auto i = 0; i != whl->getInclusiveCarryCount(); ++i) {
    646                 genCarryOutStore(carryQueuePhiNodes[i], baseCarryQueueIdx + i);
     667            for (index = 0; index != whileStatement->getInclusiveCarryCount(); ++index) {
     668                genCarryOutStore(phiNodes[index], baseCarryQueueIdx + index);
    647669            }
    648670        }
     
    669691                throw std::runtime_error("Unexpected error locating static function for \"" + call->getCallee()->str() + "\"");
    670692            }
    671             Value * unicode_category = b.CreateCall(ci->second, mBasisBitsAddr);
    672             Value * ptr = b.CreateAlloca(mXi64Vect);
    673             b.CreateAlignedStore(unicode_category, ptr, BLOCK_SIZE/8, false);
    674             mi = mMarkerMap.insert(std::make_pair(call->getCallee(), ptr)).first;
    675         }
    676         retVal = b.CreateAlignedLoad(mi->second, BLOCK_SIZE/8, false, call->getCallee()->str() );
     693            mi = mMarkerMap.insert(std::make_pair(call->getCallee(), b.CreateCall(ci->second, mBasisBitsAddr))).first;
     694        }
     695        retVal = mi->second;
    677696    }
    678697    else if (const Var * var = dyn_cast<Var>(expr))
    679     {
     698    {       
    680699        auto f = mMarkerMap.find(var->getName());
    681700        assert (f != mMarkerMap.end());
    682         retVal = b.CreateAlignedLoad(f->second, BLOCK_SIZE/8, false, var->getName()->str() );
     701        retVal = f->second;
    683702    }
    684703    else if (const And * pablo_and = dyn_cast<And>(expr))
     
    690709        retVal = b.CreateOr(compileExpression(pablo_or->getExpr1()), compileExpression(pablo_or->getExpr2()), "or");
    691710    }
    692     else if (const Sel * pablo_sel = dyn_cast<Sel>(expr))
    693     {
    694         Value* ifMask = compileExpression(pablo_sel->getCondition());
    695         Value* and_if_true_result = b.CreateAnd(ifMask, compileExpression(pablo_sel->getTrueExpr()));
    696         Value* and_if_false_result = b.CreateAnd(genNot(ifMask), compileExpression(pablo_sel->getFalseExpr()));
    697         retVal = b.CreateOr(and_if_true_result, and_if_false_result);
     711    else if (const Sel * sel = dyn_cast<Sel>(expr))
     712    {
     713        Value* ifMask = compileExpression(sel->getCondition());
     714        Value* ifTrue = b.CreateAnd(ifMask, compileExpression(sel->getTrueExpr()));
     715        Value* ifFalse = b.CreateAnd(genNot(ifMask), compileExpression(sel->getFalseExpr()));
     716        retVal = b.CreateOr(ifTrue, ifFalse);
    698717    }
    699718    else if (const Not * pablo_not = dyn_cast<Not>(expr))
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.h

    r4260 r4264  
    9595    void DefineTypes();
    9696    void DeclareFunctions();
    97     void DeclareCallFunctions(const ExpressionList & stmts);
     97    void DeclareCallFunctions(const StatementList & stmts);
    9898    void DeclareCallFunctions(const PabloAST * expr);
    9999    void SetReturnMarker(Value * marker, const unsigned index);
     
    101101    Value* GetMarker(const String *name);
    102102
    103     Value* compileStatements(const ExpressionList & stmts);
     103    Value* compileStatements(const StatementList & stmts);
    104104    Value* compileStatement(const PabloAST * stmt);
    105 
    106105    Value* compileExpression(const PabloAST * expr);
    107106    Value* genCarryInLoad(const unsigned index);
  • icGREP/icgrep-devel/icgrep/pablo/pe_var.h

    r4258 r4264  
    1010#include <pablo/pabloAST.h>
    1111#include <pablo/ps_assign.h>
     12#include <pablo/pe_next.h>
    1213#include <pablo/pe_string.h>
     14#include <stdexcept>
     15
     16namespace llvm {
     17    class Value;
     18    class BasicBlock;
     19}
    1320
    1421namespace pablo {
     
    2835        return mName;
    2936    }
     37    inline const PabloAST * getVar() const {
     38        return mVar;
     39    }
    3040    inline bool isInternal() const {
    31         return mInternal;
     41        return mVar != mName;
    3242    }
    3343    inline bool isExternal() const {
    34         return !mInternal;
     44        return mVar == mName;
    3545    }
    3646protected:
    37     Var(const PabloAST * var, const bool internal)
     47    Var(const PabloAST * var)
    3848    : PabloAST(ClassTypeId::Var)
    39     , mName(cast<String>(var))
    40     , mInternal(internal) {
     49    , mVar(var)
     50    , mName(getNameOf(var))
     51    {
    4152
    4253    }
    4354private:
    44     const String * const mName;
    45     const bool           mInternal;
     55    static inline const String * getNameOf(const PabloAST * var) {
     56        if (isa<String>(var)) {
     57            return cast<String>(var);
     58        }
     59        if (isa<Assign>(var)) {
     60            return cast<Assign>(var)->getName();
     61        }
     62        if (isa<Next>(var)) {
     63            return cast<Next>(var)->getName();
     64        }
     65        throw std::runtime_error("Pablo Var only accepts String, Assign and Next nodes.");
     66    }
     67private:
     68    const PabloAST * const  mVar;
     69    const String * const    mName;
    4670};
    4771
  • icGREP/icgrep-devel/icgrep/pablo/printer_pablos.cpp

    r4260 r4264  
    5353}
    5454
    55 std::string StatementPrinter::Print_PB_PabloStmts(const ExpressionList & stmts) {
     55std::string StatementPrinter::Print_PB_PabloStmts(const StatementList & stmts) {
    5656    std::string strOut = "";
    5757    for (const auto stmt : stmts) {
     
    6161}
    6262
    63 std::string StatementPrinter::Print_CC_PabloStmts(const pablo::ExpressionList &stmts) {
     63std::string StatementPrinter::Print_CC_PabloStmts(const pablo::StatementList &stmts) {
    6464    std::string strOut = "Total Statements: " + std::to_string(stmts.size()) + "\n";
    6565    for (const auto stmt : stmts) {
  • icGREP/icgrep-devel/icgrep/pablo/printer_pablos.h

    r4252 r4264  
    1818public:
    1919    static std::string PrintStmts(const pablo::PabloBlock & cg_state);
    20     static std::string Print_CC_PabloStmts(const pablo::ExpressionList & stmts);
    21     static std::string Print_PB_PabloStmts(const pablo::ExpressionList & stmts);
     20    static std::string Print_CC_PabloStmts(const pablo::StatementList & stmts);
     21    static std::string Print_PB_PabloStmts(const pablo::StatementList & stmts);
    2222    static std::string ShowPabloAST(const pablo::PabloAST * expr);
    2323    static std::string ShowPabloS(const pablo::PabloAST *stmt);
  • icGREP/icgrep-devel/icgrep/pablo/ps_if.h

    r4257 r4264  
    2626        return mExpr;
    2727    }
    28     inline const ExpressionList & getBody() const {
     28    inline const StatementList & getBody() const {
    2929        return mBody;
    3030    }
     
    3636    }
    3737protected:
    38     If(PabloAST * expr, ExpressionList && body)
     38    If(PabloAST * expr, StatementList && body)
    3939    : PabloAST(ClassTypeId::If)
    4040    , mExpr(expr)
     
    4646private:
    4747    PabloAST * const    mExpr;
    48     ExpressionList      mBody;
     48    StatementList      mBody;
    4949    unsigned            mCarryCount;
    5050};
  • icGREP/icgrep-devel/icgrep/pablo/ps_while.h

    r4257 r4264  
    2626        return mExpr;
    2727    }
    28     inline const ExpressionList & getBody() const {
     28    inline const StatementList & getBody() const {
    2929        return mBody;
    3030    }
     
    3636    }
    3737protected:
    38     While(PabloAST * expr, ExpressionList && body)
     38    While(PabloAST * expr, StatementList && body)
    3939    : PabloAST(ClassTypeId::While)
    4040    , mExpr(expr)
     
    4646private:
    4747    PabloAST * const    mExpr;
    48     ExpressionList      mBody;
     48    StatementList      mBody;
    4949    unsigned            mCarryCount;
    5050};
  • icGREP/icgrep-devel/icgrep/re/re_compiler.cpp

    r4263 r4264  
    260260    }
    261261    else {
    262 
    263262        Var * targetVar = pb.createVar(target);
    264 
    265263        Assign * whileTest = pb.createAssign("test", targetVar);
    266264        Assign * whileAccum = pb.createAssign("accum", targetVar);
    267265
    268         PabloBlock wt(pb);
    269 
    270         Var * loopComputation = wt.createVar(process(repeated, whileTest, wt));
    271 
    272         Var * whileAccumVar = wt.createVar(whileAccum);
    273 
    274         wt.createNext(whileTest, wt.createAnd(loopComputation, wt.createNot(whileAccumVar)));
    275 
    276         wt.createNext(whileAccum, wt.createOr(loopComputation, whileAccumVar));
    277 
    278         pb.createWhile(pb.createVar(whileTest), std::move(wt));
     266        PabloBlock wb(pb);
     267
     268        Var * loopComputation = wb.createVar(process(repeated, whileTest, wb));
     269
     270        Var * whileAccumVar = wb.createVar(whileAccum);
     271
     272        Next * nextWhileTest = wb.createNext(whileTest, wb.createAnd(loopComputation, wb.createNot(whileAccumVar)));
     273
     274        wb.createNext(whileAccum, wb.createOr(loopComputation, whileAccumVar));
     275
     276        pb.createWhile(wb.createVar(nextWhileTest), std::move(wb));
    279277
    280278        unbounded = whileAccumVar;
Note: See TracChangeset for help on using the changeset viewer.