Ignore:
Timestamp:
Mar 18, 2017, 1:20:50 AM (2 years ago)
Author:
nmedfort
Message:

Work on non carry collapsing mode. Beginning work on pablo-level phi nodes.

Location:
icGREP/icgrep-devel/icgrep/pablo
Files:
3 added
6 edited

Legend:

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

    r5367 r5368  
    1616#include <pablo/pe_matchstar.h>
    1717#include <pablo/pe_var.h>
    18 // #include <llvm/Support/raw_ostream.h>
     18
    1919using namespace llvm;
    2020
     
    107107    assert (mCarryFrameStack.empty());
    108108
    109     assert (mCarryOutSummary.empty());
    110     mCarryOutSummary.push_back(Constant::getNullValue(mCarryPackType));
     109    assert (mCarrySummaryStack.empty());
     110    mCarrySummaryStack.push_back(Constant::getNullValue(mCarryPackType));
    111111
    112112    if (mHasLoop) {
     
    128128        mKernel->setScalarField("CarryBlockIndex", idx);
    129129    }
    130     assert (mCarryFrameStack.empty());
    131 
    132     assert (mCarryOutSummary.size() == 1);
    133     mCarryOutSummary.clear();
     130    assert (mCarryFrameStack.empty());   
     131    assert (mCarrySummaryStack.size() == 1);
     132    assert ("base summary value was overwritten!" && isa<Constant>(mCarrySummaryStack[0]) && cast<Constant>(mCarrySummaryStack[0])->isNullValue());
     133    mCarrySummaryStack.clear();
    134134
    135135    assert (mCarryScopeIndex.size() == 1);
     
    153153    if (mCarryInfo->hasSummary()) {
    154154        PHINode * phiCarryOutSummary = iBuilder->CreatePHI(mCarryPackType, 2, "summary");
    155         assert (!mCarryOutSummary.empty());
    156         phiCarryOutSummary->addIncoming(mCarryOutSummary.back(), entryBlock);
    157         // Replace the incoming carry summary with the phi node and add the phi node to the stack
    158         // so that we can properly OR it into the outgoing summary value.
    159         mCarryOutSummary.back() = phiCarryOutSummary;
    160         mCarryOutSummary.push_back(phiCarryOutSummary);
     155        assert (!mCarrySummaryStack.empty());
     156        phiCarryOutSummary->addIncoming(mCarrySummaryStack.back(), entryBlock);
     157        // Replace the incoming carry summary with the phi node and add the phi node to the stack  so that we can
     158        // properly OR it into the outgoing summary value.
     159        // NOTE: this may change the base summary value; when exiting to the base scope, replace this summary with
     160        // a null value to prevent subsequent nested scopes from inheriting the summary of this scope.
     161        mCarrySummaryStack.back() = phiCarryOutSummary;
     162        mCarrySummaryStack.push_back(phiCarryOutSummary);
    161163    }
    162164    if (LLVM_UNLIKELY(mCarryInfo->nonCarryCollapsingMode())) {
     
    278280        assert (mCarryInfo->hasSummary());
    279281
    280         ConstantInt * const summaryIndex = iBuilder->getInt32(mCurrentFrame->getType()->getPointerElementType()->getStructNumElements() - 1);
    281 
    282         Value * carryInAccumulator = readCarryInSummary(summaryIndex);
    283         Value * carryOutAccumulator = mCarryOutSummary.back();
     282        ConstantInt * const summaryIndex = iBuilder->getInt32(mCarryInfo->hasExplicitSummary() ? mCurrentFrameIndex : (mCurrentFrameIndex - 1));
     283
     284        Value * const carryInAccumulator = readCarryInSummary(summaryIndex);
     285        Value * const carryOutAccumulator = mCarrySummaryStack.back();
    284286
    285287        if (mCarryInfo->hasExplicitSummary()) {
     
    330332        Value * const carryInPtr = iBuilder->CreateGEP(summary, carryInOffset);
    331333        Value * const carryIn = iBuilder->CreateBlockAlignedLoad(carryInPtr);
    332         Value * const carryInPrime = iBuilder->CreateXor(carryIn, borrow);
    333         Value * const finalCarryInSummary = iBuilder->CreateOr(carryInSummary, carryInPrime);
    334         iBuilder->CreateBlockAlignedStore(carryInPrime, carryInPtr);
    335         carryInSummary->addIncoming(finalCarryInSummary, update);
     334        Value * const nextCarryIn = iBuilder->CreateXor(carryIn, borrow);
     335        Value * const nextSummary = iBuilder->CreateOr(carryInSummary, nextCarryIn);
     336        iBuilder->CreateBlockAlignedStore(nextCarryIn, carryInPtr);
     337        carryInSummary->addIncoming(nextSummary, update);
    336338        Value * finalBorrow = iBuilder->CreateAnd(iBuilder->CreateNot(carryIn), borrow);
    337339        borrow->addIncoming(finalBorrow, update);
     
    341343        Value * const carryOutPtr = iBuilder->CreateGEP(summary, carryOutOffset);
    342344        Value * const carryOut = iBuilder->CreateBlockAlignedLoad(carryOutPtr);
    343         Value * const carryOutPrime = iBuilder->CreateXor(carryOut, carry);
    344         iBuilder->CreateBlockAlignedStore(carryOutPrime, carryOutPtr);
     345        Value * const nextCarryOut = iBuilder->CreateXor(carryOut, carry);
     346        iBuilder->CreateBlockAlignedStore(nextCarryOut, carryOutPtr);
    345347        Value * finalCarry = iBuilder->CreateAnd(carryOut, carry);
    346348        carry->addIncoming(finalCarry, update);
     
    351353
    352354        iBuilder->SetInsertPoint(resume);
     355
     356        IntegerType * ty = IntegerType::get(iBuilder->getContext(), mCarryPackType->getPrimitiveSizeInBits());
     357        iBuilder->CreateAssert(iBuilder->CreateICmpEQ(iBuilder->CreateBitCast(finalBorrow, ty), ConstantInt::getNullValue(ty)), "finalBorrow != 0");
     358        iBuilder->CreateAssert(iBuilder->CreateICmpEQ(iBuilder->CreateBitCast(finalCarry, ty), ConstantInt::getNullValue(ty)), "finalCarry != 0");
    353359
    354360        assert (!mLoopIndicies.empty());
     
    357363        mLoopIndicies.pop_back();
    358364
    359         mNextSummaryTest = finalCarryInSummary;
     365        mNextSummaryTest = nextSummary;
    360366    }
    361367    if (mCarryInfo->hasSummary()) {
    362         const auto n = mCarryOutSummary.size(); assert (n > 1);
    363         Value * carryOut = mCarryOutSummary.back();
    364         mCarryOutSummary.pop_back();
    365         PHINode * phiCarryOut = cast<PHINode>(mCarryOutSummary.back());
     368        const auto n = mCarrySummaryStack.size(); assert (n > 1);
     369        Value * carryOut = mCarrySummaryStack.back();
     370        mCarrySummaryStack.pop_back();
     371        PHINode * phiCarryOut = cast<PHINode>(mCarrySummaryStack.back());
    366372        phiCarryOut->addIncoming(carryOut, iBuilder->GetInsertBlock());
    367         mCarryOutSummary.back() = carryOut;
     373        // If we're returning to the base scope, reset our accumulated summary value.
     374        if (n == 2) {
     375            carryOut = Constant::getNullValue(mCarryPackType);
     376        }
     377        mCarrySummaryStack.back() = carryOut;
    368378    }
    369379}
     
    384394    ++mIfDepth;
    385395    enterScope(scope);
    386     // We start with zero-initialized carry in order and later OR in the current carry summary so that upon
    387     // processing the subsequent block iteration, we branch into this If scope iff a carry was generated by
    388     // a statement within the If scope and not by a dominating statement in the outer scope.
    389     mCarryOutSummary.push_back(Constant::getNullValue(mCarryPackType));
     396    // We zero-initialized the nested summary value and later OR in the current summary into the escaping summary
     397    // so that upon processing the subsequent block iteration, we branch into this If scope iff a carry out was
     398    // generated by a statement within this If scope and not by a dominating statement in the outer scope.
    390399    if (LLVM_LIKELY(mCarryInfo->hasSummary())) {
    391400        assert (mCurrentFrameIndex == 0);
     
    395404        }
    396405    }
     406    mCarrySummaryStack.push_back(Constant::getNullValue(mCarryPackType));
    397407}
    398408
     
    422432void CarryManager::leaveIfBody(BasicBlock * const exitBlock) {
    423433    assert (exitBlock);
    424     const auto n = mCarryOutSummary.size();
    425     if (LLVM_LIKELY(mCarryInfo->hasSummary())) {
    426         if (LLVM_LIKELY(mCarryInfo->hasExplicitSummary())) {
    427             writeCarryOutSummary(mCarryOutSummary[n - 1], iBuilder->getInt32(0));
    428         }
     434    const auto n = mCarrySummaryStack.size();
     435    if (LLVM_LIKELY(mCarryInfo->hasExplicitSummary())) {
     436        writeCarryOutSummary(mCarrySummaryStack[n - 1], iBuilder->getInt32(0));
    429437    }
    430438    if (n > 2) {
    431         mCarryOutSummary[n - 1] = iBuilder->CreateOr(mCarryOutSummary[n - 1], mCarryOutSummary[n - 2], "summary");
     439        mCarrySummaryStack[n - 1] = iBuilder->CreateOr(mCarrySummaryStack[n - 1], mCarrySummaryStack[n - 2], "summary");
    432440    }
    433441}
     
    439447    assert (mIfDepth > 0);
    440448    if (LLVM_LIKELY(mCarryInfo->hasSummary())) {
    441         const auto n = mCarryOutSummary.size(); assert (n > 0);
     449        const auto n = mCarrySummaryStack.size(); assert (n > 0);
    442450        if (n > 2) {
    443451            // When leaving a nested If scope with a summary value, phi out the summary to ensure the
    444452            // appropriate summary is stored in the outer scope.
    445             Value * nested = mCarryOutSummary[n - 1];
    446             Value * outer = mCarryOutSummary[n - 2];
    447             if (LLVM_LIKELY(nested != outer)) {
    448                 assert (nested->getType() == outer->getType());
    449                 PHINode * const phi = iBuilder->CreatePHI(nested->getType(), 2, "summary");
    450                 phi->addIncoming(outer, entryBlock);
    451                 phi->addIncoming(nested, exitBlock);
    452                 mCarryOutSummary[n - 2] = phi;
    453             }
     453            Value * nested = mCarrySummaryStack[n - 1];
     454            Value * outer = mCarrySummaryStack[n - 2];
     455            assert (nested->getType() == outer->getType());
     456            PHINode * const phi = iBuilder->CreatePHI(nested->getType(), 2, "summary");
     457            phi->addIncoming(outer, entryBlock);
     458            phi->addIncoming(nested, exitBlock);
     459            mCarrySummaryStack[n - 2] = phi;
    454460        }
    455461    }
    456462    --mIfDepth;
    457463    leaveScope();
    458     mCarryOutSummary.pop_back();
     464    mCarrySummaryStack.pop_back();
    459465}
    460466
     
    618624
    619625/** ------------------------------------------------------------------------------------------------------------- *
    620  * @brief collapsingCarryMode
    621  ** ------------------------------------------------------------------------------------------------------------- */
    622 inline bool CarryManager::inCarryCollapsingMode() const {
    623     return (dyn_cast_or_null<While>(mCurrentScope->getBranch()) && !mCarryInfo->nonCarryCollapsingMode());
    624 }
    625 
    626 /** ------------------------------------------------------------------------------------------------------------- *
    627626 * @brief setNextCarryOut
    628627 ** ------------------------------------------------------------------------------------------------------------- */
     
    630629    assert (mCurrentFrameIndex < mCurrentFrame->getType()->getPointerElementType()->getStructNumElements());
    631630    carryOut = iBuilder->CreateBitCast(carryOut, mCarryPackType);
    632     if (mCarryInfo->hasExplicitSummary()) {
     631    if (mCarryInfo->hasSummary()) {
    633632        addToCarryOutSummary(carryOut);
    634633    }
     
    638637    } else {
    639638        carryOutPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(mCurrentFrameIndex), mNextLoopSelector});
     639        if (LLVM_LIKELY(!mCarryInfo->nonCarryCollapsingMode())) {
     640            Value * accum = iBuilder->CreateBlockAlignedLoad(carryOutPtr);
     641            carryOut = iBuilder->CreateOr(carryOut, accum);
     642        }
    640643    }
    641644    ++mCurrentFrameIndex;
    642     if (inCarryCollapsingMode()) {
    643         Value * accum = iBuilder->CreateBlockAlignedLoad(carryOutPtr);
    644         carryOut = iBuilder->CreateOr(carryOut, accum);
    645     }
    646645    assert (carryOutPtr->getType()->getPointerElementType() == mCarryPackType);
    647646    iBuilder->CreateBlockAlignedStore(carryOut, carryOutPtr);
    648 
    649647}
    650648
     
    667665    std::fill(indicies, indicies + count - 1, iBuilder->getInt32(0));
    668666    indicies[count - 1] = index;
    669     if (mLoopDepth > 0) {
     667    if (mLoopDepth != 0) {
    670668        indicies[count] = mLoopSelector;
    671669    }
     
    673671    Value * const ptr = iBuilder->CreateGEP(mCurrentFrame, ar);
    674672    Value * const summary = iBuilder->CreateBlockAlignedLoad(ptr);
    675     if (mLoopDepth > 0) {
     673    if (mLoopDepth != 0 && mCarryInfo->hasExplicitSummary()) {
    676674        iBuilder->CreateBlockAlignedStore(Constant::getNullValue(mCarryPackType), ptr);
    677675    }
     
    693691}
    694692
    695 
    696693/** ------------------------------------------------------------------------------------------------------------- *
    697694 * @brief addToCarryOutSummary
    698695 ** ------------------------------------------------------------------------------------------------------------- */
    699696inline void CarryManager::addToCarryOutSummary(Value * const value) {
    700     assert ("cannot add null summary value!" && value);
    701     assert ("summary stack is empty!" && !mCarryOutSummary.empty());
    702     mCarryOutSummary.back() = iBuilder->CreateOr(value, mCarryOutSummary.back());
     697    assert ("cannot add null summary value!" && value);   
     698    assert ("summary stack is empty!" && !mCarrySummaryStack.empty());
     699    assert (mCarryInfo->hasSummary());
     700    mCarrySummaryStack.back() = iBuilder->CreateOr(value, mCarrySummaryStack.back());
    703701}
    704702
  • icGREP/icgrep-devel/icgrep/pablo/carry_manager.h

    r5366 r5368  
    9898    llvm::Value * longAdvanceCarryInCarryOut(llvm::Value * const value, const unsigned shiftAmount);
    9999    llvm::Value * readCarryInSummary(llvm::ConstantInt *index) const;
    100     bool inCarryCollapsingMode() const;
    101100    void writeCarryOutSummary(llvm::Value * const summary, llvm::ConstantInt * index) const;
    102101
     
    139138
    140139//    std::vector<llvm::Value *>                      mCarryInSummary;
    141     std::vector<llvm::Value *>                      mCarryOutSummary;
     140    std::vector<llvm::Value *>                      mCarrySummaryStack;
    142141};
    143142
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.cpp

    r5329 r5368  
    1111#include <pablo/branch.h>
    1212#include <pablo/pe_advance.h>
     13#include <pablo/pe_count.h>
     14#include <pablo/pe_infile.h>
     15#include <pablo/pe_integer.h>
    1316#include <pablo/pe_lookahead.h>
    1417#include <pablo/pe_matchstar.h>
     18#include <pablo/pe_ones.h>
     19#include <pablo/pe_phi.h>
    1520#include <pablo/pe_scanthru.h>
    16 #include <pablo/pe_infile.h>
    17 #include <pablo/pe_count.h>
    18 #include <pablo/pe_integer.h>
    1921#include <pablo/pe_string.h>
     22#include <pablo/pe_var.h>
    2023#include <pablo/pe_zeroes.h>
    21 #include <pablo/pe_ones.h>
    22 #include <pablo/pe_var.h>
    2324#include <pablo/ps_assign.h>
    2425#include <pablo/pablo_kernel.h>
     
    3233
    3334namespace pablo {
     35
     36
     37Phi * PabloBlock::createPhi(Type * type, String * name) {
     38    if (type == nullptr) {
     39        type = getParent()->getBuilder()->getStreamTy();
     40    }
     41    if (name == nullptr) {
     42        name = makeName("phi");
     43    }
     44    return insertAtInsertionPoint(new (mAllocator) Phi(type, 2, name, mAllocator));
     45}
    3446
    3547/// UNARY CREATE FUNCTIONS
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r5340 r5368  
    3333namespace pablo { class Or; }
    3434namespace pablo { class PabloKernel; }
     35namespace pablo { class Phi; }
    3536namespace pablo { class ScanThru; }
    3637namespace pablo { class ScanTo; }
     
    4243namespace pablo { class Zeroes; }
    4344
    44 
    4545namespace pablo {
    4646
     
    275275    While * createWhile(PabloAST * condition, PabloBlock * body);
    276276
     277    Phi * createPhi(llvm::Type * type = nullptr) {
     278        return createPhi(type, nullptr);
     279    }
     280
     281    Phi * createPhi(llvm::Type * type, const llvm::StringRef & prefix) {
     282        return createPhi(type, makeName(prefix));
     283    }
     284
     285    Phi * createPhi(llvm::Type * type, String * name);
     286
    277287    llvm::Type * getStreamSetTy(const unsigned NumElements = 1, const unsigned FieldWidth = 1) {
    278288        return mParent->getStreamSetTy(NumElements, FieldWidth);
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r5329 r5368  
    4747
    4848    enum class ClassTypeId : unsigned {
    49         /** Non-statements **/
     49        /** Expressions and Constants **/
    5050        // Constants
    5151        Zeroes
    5252        , Ones
    53         // Internal types
    54         , Var       
    55         , Integer
    56         , String
    57         , Block
    58         , Kernel
    5953        // Arithmetic expressions
    6054        , Add
     
    6761        , GreaterThan
    6862        , NotEquals
     63        // Internal types
     64        , Var
     65        , Integer
     66        , String
     67        , Block
     68        , Kernel
    6969        /** Statements **/
    7070        // Boolean operations
     
    9292        , If
    9393        , While
     94        // Internal types
     95        , Phi
    9496    };
    9597
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

    r5361 r5368  
    4545
    4646void PabloCompiler::compile() {
    47 
    48     mCarryManager->initializeCodeGen();
    49      
     47    mCarryManager->initializeCodeGen();     
    5048    PabloBlock * const entryBlock = mKernel->getEntryBlock(); assert (entryBlock);
    5149    mMarker.emplace(entryBlock->createZeroes(), iBuilder->allZeroes());
    5250    mMarker.emplace(entryBlock->createOnes(), iBuilder->allOnes());
    53 
    5451    compileBlock(entryBlock);
    55 
    5652    mCarryManager->finalizeCodeGen();
    57 
    5853}
    5954
Note: See TracChangeset for help on using the changeset viewer.