Ignore:
Timestamp:
Jan 7, 2015, 3:40:23 PM (5 years ago)
Author:
nmedfort
Message:

Changes to support 3-operand form for all instructions. CSE disabled but partially redundant now.

File:
1 edited

Legend:

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

    r4403 r4410  
    159159        IRBuilder<> b(mBasicBlock);
    160160        Value* indices[] = {b.getInt64(0), b.getInt32(i)};
    161         const String * const name = mBasisBits[i]->getName();
    162161        Value * gep = b.CreateGEP(mBasisBitsAddr, indices);
    163         LoadInst * basisBit = b.CreateAlignedLoad(gep, BLOCK_SIZE/8, false, name->str());
    164         mMarkerMap.insert(std::make_pair(name, basisBit));
     162        LoadInst * basisBit = b.CreateAlignedLoad(gep, BLOCK_SIZE/8, false, mBasisBits[i]->getName()->str());
     163        mMarkerMap.insert(std::make_pair(mBasisBits[i], basisBit));
    165164    }
    166165
     
    169168
    170169    assert (mCarryQueueIdx == mCarryQueueSize);
    171     assert (mAdvanceQueueIdx == mAdvanceQueueSize);
     170    assert (mAdvanceQueueIdx <= mAdvanceQueueSize);
    172171    assert (mNestingDepth == 0);
    173172    //Terminate the block
     
    492491
    493492void PabloCompiler::compileStatements(const StatementList & stmts) {
    494     for (const PabloAST * statement : stmts) {
     493    for (const Statement * statement : stmts) {
    495494        compileStatement(statement);
    496495    }
    497496}
    498497
    499 void PabloCompiler::compileStatement(const PabloAST * stmt)
     498void PabloCompiler::compileStatement(const Statement * stmt)
    500499{
    501     if (const Assign * assign = dyn_cast<const Assign>(stmt))
    502     {
    503         Value* expr = compileExpression(assign->getExpr());
    504         mMarkerMap[assign->getName()] = expr;
     500    IRBuilder<> b(mBasicBlock);
     501    if (const Assign * assign = dyn_cast<const Assign>(stmt)) {
     502        Value * expr = compileExpression(assign->getExpr());
     503        mMarkerMap[assign] = expr;
    505504        if (LLVM_UNLIKELY(assign->isOutputAssignment())) {
    506505            SetOutputValue(expr, assign->getOutputIndex());
    507506        }
    508507    }
    509     if (const Next * next = dyn_cast<const Next>(stmt))
    510     {
    511         Value* expr = compileExpression(next->getExpr());
    512         mMarkerMap[next->getName()] = expr;
     508    else if (const Next * next = dyn_cast<const Next>(stmt)) {
     509        Value * expr = compileExpression(next->getExpr());
     510        mMarkerMap[next->getInitial()] = expr;
    513511    }
    514512    else if (const If * ifStatement = dyn_cast<const If>(stmt))
    515     //
    516     //  The If-ElseZero stmt:
    517     //  if <predicate:expr> then <body:stmt>* elsezero <defined:var>* endif
    518     //  If the value of the predicate is nonzero, then determine the values of variables
    519     //  <var>* by executing the given statements.  Otherwise, the value of the
    520     //  variables are all zero.  Requirements: (a) no variable that is defined within
    521     //  the body of the if may be accessed outside unless it is explicitly 
    522     //  listed in the variable list, (b) every variable in the defined list receives
    523     //  a value within the body, and (c) the logical consequence of executing
    524     //  the statements in the event that the predicate is zero is that the
    525     //  values of all defined variables indeed work out to be 0.
    526     //
    527     //  Simple Implementation with Phi nodes:  a phi node in the if exit block
    528     //  is inserted for each variable in the defined variable list.  It receives
    529     //  a zero value from the ifentry block and the defined value from the if
    530     //  body.
    531     //
    532     {
     513    {
     514        //
     515        //  The If-ElseZero stmt:
     516        //  if <predicate:expr> then <body:stmt>* elsezero <defined:var>* endif
     517        //  If the value of the predicate is nonzero, then determine the values of variables
     518        //  <var>* by executing the given statements.  Otherwise, the value of the
     519        //  variables are all zero.  Requirements: (a) no variable that is defined within
     520        //  the body of the if may be accessed outside unless it is explicitly
     521        //  listed in the variable list, (b) every variable in the defined list receives
     522        //  a value within the body, and (c) the logical consequence of executing
     523        //  the statements in the event that the predicate is zero is that the
     524        //  values of all defined variables indeed work out to be 0.
     525        //
     526        //  Simple Implementation with Phi nodes:  a phi node in the if exit block
     527        //  is inserted for each variable in the defined variable list.  It receives
     528        //  a zero value from the ifentry block and the defined value from the if
     529        //  body.
     530        //
     531
    533532        BasicBlock * ifEntryBlock = mBasicBlock;  // The block we are in.
    534533        BasicBlock * ifBodyBlock = BasicBlock::Create(mMod->getContext(), "if.body", mFunction, 0);
     
    572571
    573572        // Entry processing is complete, now handle the body of the if.
    574        
    575573        mBasicBlock = ifBodyBlock;
    576        
    577574        compileStatements(ifStatement->getBody());
    578575
     
    587584
    588585            Value * carry_summary = mZeroInitializer;
    589             for (int c = baseCarryQueueIdx; c < baseCarryQueueIdx + ifCarryCount; c++)
    590             {
     586            for (int c = baseCarryQueueIdx; c < baseCarryQueueIdx + ifCarryCount; c++) {
    591587                int s = mCarryQueueSummaryIdx[c];
    592588                if (s == -1) {
    593589                    Value* carryq_value = mCarryQueueVector[c];
    594                     carry_summary = bIfBody.CreateOr(carry_summary, carryq_value);
     590                    if (carry_summary == mZeroInitializer) {
     591                        carry_summary = carryq_value;
     592                    }
     593                    else {
     594                        carry_summary = bIfBody.CreateOr(carry_summary, carryq_value);
     595                    }
    595596                    mCarryQueueSummaryIdx[c] = mAdvanceQueueIdx;
    596597                }
    597                
    598 
    599598            }
    600599            // Note that the limit in the following uses -1, because
    601600            // last entry of the advance queue is for the summary variable.
    602             for (int c = baseAdvanceQueueIdx; c < baseAdvanceQueueIdx + ifAdvanceCount - 1; c++)
    603             {
     601            for (int c = baseAdvanceQueueIdx; c < baseAdvanceQueueIdx + ifAdvanceCount - 1; c++) {
    604602                int s = mAdvanceQueueSummaryIdx[c];
    605603                if (s == -1 ) {
    606604                    Value* advance_q_value = mAdvanceQueueVector[c];
    607                     carry_summary = bIfBody.CreateOr(advance_q_value, carry_summary);
     605                    if (carry_summary == mZeroInitializer) {
     606                        carry_summary = advance_q_value;
     607                    }
     608                    else {
     609                        carry_summary = bIfBody.CreateOr(carry_summary, advance_q_value);
     610                    }
    608611                    mAdvanceQueueSummaryIdx[c] = mAdvanceQueueIdx;
    609612                }
    610613            }
    611             genAdvanceOutStore(carry_summary, mAdvanceQueueIdx++); //baseAdvanceQueueIdx + ifAdvanceCount - 1);
     614            genAdvanceOutStore(carry_summary, mAdvanceQueueIdx++);
    612615        }
    613616        bIfBody.CreateBr(ifEndBlock);
     
    616619        for (const Assign * a : ifStatement->getDefined()) {
    617620            PHINode * phi = bEnd.CreatePHI(mBitBlockType, 2, a->getName()->str());
    618             auto f = mMarkerMap.find(a->getName());
     621            auto f = mMarkerMap.find(a);
    619622            assert (f != mMarkerMap.end());
    620623            phi->addIncoming(mZeroInitializer, ifEntryBlock);
    621624            phi->addIncoming(f->second, mBasicBlock);
    622             mMarkerMap[a->getName()] = phi;
     625            mMarkerMap[a] = phi;
    623626        }
    624627        // Create the phi Node for the summary variable.
    625628        if (ifAdvanceCount >= 1) {
    626           // final AdvanceQ entry is summary variable.
    627           PHINode * summary_phi = bEnd.CreatePHI(mBitBlockType, 2, "summary");
    628           summary_phi->addIncoming(mZeroInitializer, ifEntryBlock);
    629           summary_phi->addIncoming(mAdvanceQueueVector[mAdvanceQueueIdx-1], mBasicBlock);
    630           mAdvanceQueueVector[mAdvanceQueueIdx-1] = summary_phi;
     629            // final AdvanceQ entry is summary variable.
     630            PHINode * summary_phi = bEnd.CreatePHI(mBitBlockType, 2, "summary");
     631            summary_phi->addIncoming(mZeroInitializer, ifEntryBlock);
     632            summary_phi->addIncoming(mAdvanceQueueVector[mAdvanceQueueIdx-1], mBasicBlock);
     633            mAdvanceQueueVector[mAdvanceQueueIdx-1] = summary_phi;
    631634        }
    632635        else if (ifCarryCount == 1) {
    633           PHINode * summary_phi = bEnd.CreatePHI(mBitBlockType, 2, "summary");
    634           summary_phi->addIncoming(mZeroInitializer, ifEntryBlock);
    635           summary_phi->addIncoming(mCarryQueueVector[baseCarryQueueIdx], mBasicBlock);
    636           mCarryQueueVector[baseCarryQueueIdx] = summary_phi;
     636            PHINode * summary_phi = bEnd.CreatePHI(mBitBlockType, 2, "summary");
     637            summary_phi->addIncoming(mZeroInitializer, ifEntryBlock);
     638            summary_phi->addIncoming(mCarryQueueVector[baseCarryQueueIdx], mBasicBlock);
     639            mCarryQueueVector[baseCarryQueueIdx] = summary_phi;
    637640        }
    638641       
     
    706709        for (const Next * n : nextNodes) {
    707710            PHINode * phi = bCond.CreatePHI(mBitBlockType, 2, n->getName()->str());
    708             auto f = mMarkerMap.find(n->getName());
     711            auto f = mMarkerMap.find(n->getInitial());
    709712            assert (f != mMarkerMap.end());
    710713            phi->addIncoming(f->second, mBasicBlock);
    711             mMarkerMap[n->getName()] = phi;
     714            mMarkerMap[n->getInitial()] = phi;
    712715            phiNodes[index++] = phi;
    713716        }
     
    735738        // and for any Next nodes in the loop body
    736739        for (const Next * n : nextNodes) {
    737             auto f = mMarkerMap.find(n->getName());
     740            auto f = mMarkerMap.find(n->getInitial());
    738741            assert (f != mMarkerMap.end());
    739742            PHINode * phi = phiNodes[index++];
    740743            phi->addIncoming(f->second, mBasicBlock);
    741             mMarkerMap[n->getName()] = phi;
     744            mMarkerMap[n->getInitial()] = phi;
    742745        }
    743746
     
    755758        }
    756759    }
    757 }
    758 
    759 Value * PabloCompiler::compileExpression(const PabloAST * expr)
    760 {
    761     IRBuilder<> b(mBasicBlock);
    762     if (isa<Ones>(expr)) {
    763         return mOneInitializer;
    764     }
    765     else if (isa<Zeroes>(expr)) {
    766         return mZeroInitializer;
    767     }
    768     else if (const Call* call = dyn_cast<Call>(expr)) {
     760    else if (const Call* call = dyn_cast<Call>(stmt)) {
    769761        //Call the callee once and store the result in the marker map.
    770         auto mi = mMarkerMap.find(call->getCallee());
     762        auto mi = mMarkerMap.find(call);
    771763        if (mi == mMarkerMap.end()) {
    772764            auto ci = mCalleeMap.find(call->getCallee());
     
    774766                throw std::runtime_error("Unexpected error locating static function for \"" + call->getCallee()->str() + "\"");
    775767            }
    776             mi = mMarkerMap.insert(std::make_pair(call->getCallee(), b.CreateCall(ci->second, mBasisBitsAddr))).first;
    777         }
    778         return mi->second;
    779     }
    780     else if (const Var * var = dyn_cast<Var>(expr))
    781     {
    782         auto f = mMarkerMap.find(var->getName());
    783         if (LLVM_UNLIKELY(f == mMarkerMap.end())) {
    784             throw std::runtime_error((var->getName()->str()) + " used before creation.");
    785         }
    786         return f->second;
    787     }
    788     else if (const And * pablo_and = dyn_cast<And>(expr))
    789     {
    790         return b.CreateAnd(compileExpression(pablo_and->getExpr1()), compileExpression(pablo_and->getExpr2()), "and");
    791     }
    792     else if (const Or * pablo_or = dyn_cast<Or>(expr))
    793     {
    794         return b.CreateOr(compileExpression(pablo_or->getExpr1()), compileExpression(pablo_or->getExpr2()), "or");
    795     }
    796     else if (const Xor * pablo_xor = dyn_cast<Xor>(expr))
    797     {
    798         return b.CreateXor(compileExpression(pablo_xor->getExpr1()), compileExpression(pablo_xor->getExpr2()), "xor");
    799     }
    800     else if (const Sel * sel = dyn_cast<Sel>(expr))
    801     {
     768            mi = mMarkerMap.insert(std::make_pair(call, b.CreateCall(ci->second, mBasisBitsAddr))).first;
     769        }
     770        // return mi->second;
     771    }
     772    else if (const And * pablo_and = dyn_cast<And>(stmt)) {
     773        Value * expr = b.CreateAnd(compileExpression(pablo_and->getExpr1()), compileExpression(pablo_and->getExpr2()), "and");
     774        mMarkerMap[pablo_and] = expr;
     775        // return expr;
     776    }
     777    else if (const Or * pablo_or = dyn_cast<Or>(stmt)) {
     778        Value * expr = b.CreateOr(compileExpression(pablo_or->getExpr1()), compileExpression(pablo_or->getExpr2()), "or");
     779        mMarkerMap[pablo_or] = expr;
     780        // return expr;
     781    }
     782    else if (const Xor * pablo_xor = dyn_cast<Xor>(stmt)) {
     783        Value * expr = b.CreateXor(compileExpression(pablo_xor->getExpr1()), compileExpression(pablo_xor->getExpr2()), "xor");
     784        mMarkerMap[pablo_xor] = expr;
     785        // return expr;
     786    }
     787    else if (const Sel * sel = dyn_cast<Sel>(stmt)) {
    802788        Value* ifMask = compileExpression(sel->getCondition());
    803789        Value* ifTrue = b.CreateAnd(ifMask, compileExpression(sel->getTrueExpr()));
    804790        Value* ifFalse = b.CreateAnd(genNot(ifMask), compileExpression(sel->getFalseExpr()));
    805         return b.CreateOr(ifTrue, ifFalse);
    806     }
    807     else if (const Not * pablo_not = dyn_cast<Not>(expr))
    808     {
    809         return genNot(compileExpression(pablo_not->getExpr()));
    810     }
    811     else if (const Advance * adv = dyn_cast<Advance>(expr))
    812     {
     791        Value * expr = b.CreateOr(ifTrue, ifFalse);
     792        mMarkerMap[sel] = expr;
     793        // return expr;
     794    }
     795    else if (const Not * pablo_not = dyn_cast<Not>(stmt)) {
     796        Value * expr = genNot(compileExpression(pablo_not->getExpr()));
     797        mMarkerMap[pablo_not] = expr;
     798        // return expr;
     799    }
     800    else if (const Advance * adv = dyn_cast<Advance>(stmt)) {
    813801        Value* strm_value = compileExpression(adv->getExpr());
    814802        int shift = adv->getAdvanceAmount();
    815         return genAdvanceWithCarry(strm_value, shift);
    816     }
    817     else if (const MatchStar * mstar = dyn_cast<MatchStar>(expr))
    818     {
    819         Value* marker = compileExpression(mstar->getMarker());
    820         Value* cc = compileExpression(mstar->getCharClass());
    821         Value* marker_and_cc = b.CreateAnd(marker, cc);
    822         return b.CreateOr(b.CreateXor(genAddWithCarry(marker_and_cc, cc), cc), marker, "matchstar");
    823     }
    824     else if (const ScanThru * sthru = dyn_cast<ScanThru>(expr))
    825     {
    826         Value* marker_expr = compileExpression(sthru->getScanFrom());
    827         Value* cc_expr = compileExpression(sthru->getScanThru());
    828         return b.CreateAnd(genAddWithCarry(marker_expr, cc_expr), genNot(cc_expr), "scanthru");
     803        Value * expr = genAdvanceWithCarry(strm_value, shift);
     804        mMarkerMap[adv] = expr;
     805        // return expr;
     806    }
     807    else if (const MatchStar * mstar = dyn_cast<MatchStar>(stmt))
     808    {
     809        Value * marker = compileExpression(mstar->getMarker());
     810        Value * cc = compileExpression(mstar->getCharClass());
     811        Value * marker_and_cc = b.CreateAnd(marker, cc);
     812        Value * expr = b.CreateOr(b.CreateXor(genAddWithCarry(marker_and_cc, cc), cc), marker, "matchstar");
     813        mMarkerMap[mstar] = expr;
     814        // return expr;
     815    }
     816    else if (const ScanThru * sthru = dyn_cast<ScanThru>(stmt))
     817    {
     818        Value * marker_expr = compileExpression(sthru->getScanFrom());
     819        Value * cc_expr = compileExpression(sthru->getScanThru());
     820        Value * expr = b.CreateAnd(genAddWithCarry(marker_expr, cc_expr), genNot(cc_expr), "scanthru");
     821        mMarkerMap[sthru] = expr;
     822        // return expr;
    829823    }
    830824    else {
     825        PabloPrinter::print(stmt, std::cerr);
     826        throw std::runtime_error("Unrecognized Pablo Statement! can't compile.");
     827    }
     828}
     829
     830Value * PabloCompiler::compileExpression(const PabloAST * expr) {
     831    if (isa<Ones>(expr)) {
     832        return mOneInitializer;
     833    }
     834    else if (isa<Zeroes>(expr)) {
     835        return mZeroInitializer;
     836    }
     837    else if (const Next * next = dyn_cast<Next>(expr)) {
     838        expr = next->getInitial();
     839    }
     840    auto f = mMarkerMap.find(expr);
     841    if (f == mMarkerMap.end()) {
    831842        throw std::runtime_error("Unrecognized Pablo expression type; can't compile.");
    832843    }
    833 
     844    return f->second;
    834845}
    835846
Note: See TracChangeset for help on using the changeset viewer.