Ignore:
Timestamp:
Aug 5, 2015, 11:47:53 AM (4 years ago)
Author:
cameron
Message:

Dynamic selection of carry strategy options

File:
1 edited

Legend:

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

    r4714 r4715  
    1313#include <pablo/pabloAST.h>
    1414#include <iostream>
     15
     16
     17static cl::opt<CarryManagerStrategy> Strategy(cl::desc("Choose carry management strategy:"),
     18                                              cl::values(
     19                                                         clEnumVal(BitBlockStrategy, "Unpacked, each carry in a separate bitblock."),
     20                                                         clEnumVal(SequentialFullyPackedStrategy, "Sequential packing, up to 64 carries per pack."),
     21                                                         clEnumValEnd));
     22
    1523
    1624namespace pablo {
     
    3341unsigned CarryManager::initialize(PabloBlock * pb, Value * carryPtr) {
    3442    mPabloRoot = pb;
    35 #ifdef PACKING
    36     mCarryPackType = mBuilder->getIntNTy(PACK_SIZE);
    37     mCarryPackBasePtr = mBuilder->CreateBitCast(carryPtr, Type::getInt64PtrTy(mBuilder->getContext()));
    38     mCarryBitBlockPtr = carryPtr;
    39     mZeroInitializer = mBuilder->getInt64(0);
    40     mOneInitializer = mBuilder->getInt64(-1);
    41 #else
    42 #define mCarryPackType mBitBlockType
    43     mCarryPackBasePtr = carryPtr;
    44 #define mCarryBitBlockPtr mCarryPackBasePtr
    45 #endif
     43    if (Strategy == SequentialFullyPackedStrategy) {
     44        mPACK_SIZE = 64;
     45        mITEMS_PER_PACK = 64;
     46        mCarryPackType = mBuilder->getIntNTy(mPACK_SIZE);
     47        mCarryPackBasePtr = mBuilder->CreateBitCast(carryPtr, Type::getInt64PtrTy(mBuilder->getContext()));
     48        mCarryBitBlockPtr = carryPtr;
     49        mZeroInitializer = mBuilder->getInt64(0);
     50        mOneInitializer = mBuilder->getInt64(-1);
     51    }
     52    else { // if Strategy == BitBlockStrategy
     53        mPACK_SIZE = BLOCK_SIZE;
     54        mITEMS_PER_PACK = 1;
     55        mCarryPackType = mBitBlockType;
     56        mCarryPackBasePtr = carryPtr;
     57        mCarryBitBlockPtr = mCarryPackBasePtr;
     58    }
    4659    unsigned scopeCount = doScopeCount(pb);
    4760    mCarryInfoVector.resize(scopeCount);
    48    
    4961    unsigned totalCarryDataSize = enumerate(pb, 0, 0);
    50 #ifdef PACKING
    51     mTotalCarryDataBitBlocks = (totalCarryDataSize + BLOCK_SIZE - 1)/BLOCK_SIZE;
    52 #else
    53     mTotalCarryDataBitBlocks = totalCarryDataSize;
    54 #endif
    55     // Carry Data area will have one extra bit block to store the block number.
    56     mBlockNoPtr = mBuilder->CreateBitCast(mBuilder->CreateGEP(carryPtr, mBuilder->getInt64(mTotalCarryDataBitBlocks)), Type::getInt64PtrTy(mBuilder->getContext()));
    57     mBlockNo = mBuilder->CreateLoad(mBlockNoPtr);
    58 #ifdef PACKING
    59     unsigned totalPackCount = (totalCarryDataSize + PACK_SIZE - 1)/PACK_SIZE;
     62   
     63    unsigned totalPackCount = (totalCarryDataSize + mITEMS_PER_PACK - 1)/mITEMS_PER_PACK;
     64
    6065    mCarryPackPtr.resize(totalPackCount);
    6166    mCarryInPack.resize(totalPackCount);
    6267    mCarryOutPack.resize(totalPackCount);
    6368    for (auto i = 0; i < totalPackCount; i++) mCarryInPack[i]=nullptr;
    64 #else
    65     mCarryPackPtr.resize(mTotalCarryDataBitBlocks);
    66     mCarryInPack.resize(mTotalCarryDataBitBlocks);
    67     mCarryOutPack.resize(mTotalCarryDataBitBlocks);
    68     for (auto i = 0; i < mTotalCarryDataBitBlocks; i++) mCarryInPack[i]=nullptr;
    69 #endif   
     69
     70    if (Strategy == SequentialFullyPackedStrategy) {
     71        mTotalCarryDataBitBlocks = (totalCarryDataSize + BLOCK_SIZE - 1)/BLOCK_SIZE;
     72    }
     73    else {
     74        mTotalCarryDataBitBlocks = totalCarryDataSize;
     75    }
     76    // Carry Data area will have one extra bit block to store the block number.
     77    mBlockNoPtr = mBuilder->CreateBitCast(mBuilder->CreateGEP(carryPtr, mBuilder->getInt64(mTotalCarryDataBitBlocks)), Type::getInt64PtrTy(mBuilder->getContext()));
     78    mBlockNo = mBuilder->CreateLoad(mBlockNoPtr);
    7079    /*  Set the current scope to PabloRoot */
    7180    mCurrentScope = mPabloRoot;
    7281    mCurrentFrameIndex = 0;
    7382    mCarryInfo = mCarryInfoVector[0];
    74 
    7583    return mTotalCarryDataBitBlocks + 1; // One extra element for the block no.
    7684}
     
    8896    llvm::raw_os_ostream cerr(std::cerr);
    8997    unsigned idx = blk->getScopeIndex();
    90     PabloBlockCarryData * cd = new PabloBlockCarryData(blk);
     98    PabloBlockCarryData * cd = new PabloBlockCarryData(blk, mPACK_SIZE, mITEMS_PER_PACK);
    9199    mCarryInfoVector[idx] = cd;
    92100
     
    99107            const unsigned ifCarryDataBits = enumerate(&ifStatement->getBody(), ifDepth+1, whileDepth);
    100108            PabloBlockCarryData * nestedBlockData = mCarryInfoVector[ifStatement->getBody().getScopeIndex()];
    101             if (ITEMS_PER_PACK == PACK_SIZE) {  // PACKING
     109            if (mITEMS_PER_PACK == mPACK_SIZE) {  // PACKING
    102110                if (cd->roomInFinalPack(nestedOffset) < ifCarryDataBits) {
    103                     nestedOffset = alignCeiling(nestedOffset, PACK_SIZE);
     111                    nestedOffset = alignCeiling(nestedOffset, mPACK_SIZE);
    104112                }
    105113            }
     
    117125            PabloBlockCarryData * nestedBlockData = mCarryInfoVector[whileStatement->getBody().getScopeIndex()];
    118126            //if (whileStatement->isMultiCarry()) whileCarryDataBits *= whileStatement->getMaxIterations();
    119             if (ITEMS_PER_PACK == PACK_SIZE) {  // PACKING
     127            if (mITEMS_PER_PACK == mPACK_SIZE) {  // PACKING
    120128                if (cd->roomInFinalPack(nestedOffset) < whileCarryDataBits) {
    121                     nestedOffset = alignCeiling(nestedOffset, PACK_SIZE);
     129                    nestedOffset = alignCeiling(nestedOffset, mPACK_SIZE);
    122130                }
    123131            }
     
    137145        // Need extra space for the summary variable, always the last
    138146        // entry within an if block.
    139         if (ITEMS_PER_PACK == PACK_SIZE) {  // PACKING
    140             cd->scopeCarryDataSize = alignCeiling(cd->scopeCarryDataSize, PACK_SIZE);
     147        if (mITEMS_PER_PACK == mPACK_SIZE) {  // PACKING
     148            cd->scopeCarryDataSize = alignCeiling(cd->scopeCarryDataSize, mPACK_SIZE);
    141149        }
    142150        cd->summary.frameOffset = cd->scopeCarryDataSize;
    143         cd->scopeCarryDataSize += ITEMS_PER_PACK;  //  computed summary is a full pack.
     151        cd->scopeCarryDataSize += mITEMS_PER_PACK;  //  computed summary is a full pack.
    144152    }
    145153    else {
     
    195203
    196204unsigned CarryManager::longAdvanceBitBlockPosition(unsigned localIndex) {
    197 #ifdef PACKING
    198     return (mCurrentFrameIndex + mCarryInfo->longAdvance.frameOffset) / BLOCK_SIZE + localIndex;
    199 #else
    200     return mCurrentFrameIndex + mCarryInfo->longAdvance.frameOffset + localIndex;
    201 #endif
     205    return (mCurrentFrameIndex + mCarryInfo->longAdvance.frameOffset) / mITEMS_PER_PACK + localIndex;
    202206}
    203207   
    204208unsigned CarryManager::localBasePack() {
    205 #ifdef PACKING
    206     return (mCurrentFrameIndex + mCarryInfo->shortAdvance.frameOffset) / PACK_SIZE;
    207 #else
    208     return mCurrentFrameIndex + mCarryInfo->shortAdvance.frameOffset;
    209 #endif
     209    return (mCurrentFrameIndex + mCarryInfo->shortAdvance.frameOffset) / mITEMS_PER_PACK;
    210210}
    211211   
    212212unsigned CarryManager::scopeBasePack() {
    213 #ifdef PACKING
    214     return mCurrentFrameIndex / PACK_SIZE;
    215 #else
    216     return mCurrentFrameIndex;
    217 #endif
     213    return mCurrentFrameIndex / mITEMS_PER_PACK;
    218214}
    219215   
     
    226222
    227223unsigned CarryManager::summaryPackIndex() {
    228 #ifdef PACKING
    229     return summaryPosition()/PACK_SIZE;
    230 #else
    231     return summaryPosition();
    232 #endif
     224    return summaryPosition()/mITEMS_PER_PACK;
    233225}
    234226
    235227unsigned CarryManager::summaryBits() {
    236 #ifdef PACKING
    237     if (mCarryInfo->scopeCarryDataSize > PACK_SIZE) return PACK_SIZE;
     228    if (mCarryInfo->scopeCarryDataSize > mITEMS_PER_PACK) return mPACK_SIZE;
    238229    else return mCarryInfo->scopeCarryDataSize;
    239 #else
    240     if (mCarryInfo->scopeCarryDataSize > 1) return PACK_SIZE;
    241     else return mCarryInfo->scopeCarryDataSize;
    242 #endif
    243230}
    244231
     
    250237        // Save the computed pointer - so that it can be used in storeCarryPack.
    251238        mCarryPackPtr[packIndex] = packPtr;
    252         mCarryInPack[packIndex] = mBuilder->CreateAlignedLoad(packPtr, PACK_SIZE/8);
     239        mCarryInPack[packIndex] = mBuilder->CreateAlignedLoad(packPtr, mPACK_SIZE/8);
    253240    }
    254241    return mCarryInPack[packIndex];
     
    256243
    257244void CarryManager::storeCarryPack(unsigned packIndex) {
    258     mBuilder->CreateAlignedStore(mCarryOutPack[packIndex], mCarryPackPtr[packIndex], PACK_SIZE/8);
     245    mBuilder->CreateAlignedStore(mCarryOutPack[packIndex], mCarryPackPtr[packIndex], mPACK_SIZE/8);
    259246}
    260247
     
    264251   
    265252Value * CarryManager::maskSelectBitRange(Value * pack, unsigned lo_bit, unsigned bitCount) {
    266     if (bitCount == PACK_SIZE) {
     253    if (bitCount == mPACK_SIZE) {
    267254        assert(lo_bit == 0);
    268255        return pack;
     
    273260   
    274261Value * CarryManager::getCarryInBits(unsigned carryBitPos, unsigned carryBitCount) {
    275     unsigned packIndex = carryBitPos / PACK_SIZE;
    276     unsigned packOffset = carryBitPos % PACK_SIZE;
     262    unsigned packIndex = carryBitPos / mPACK_SIZE;
     263    unsigned packOffset = carryBitPos % mPACK_SIZE;
    277264    Value * selected = maskSelectBitRange(getCarryPack(packIndex), packOffset, carryBitCount);
    278265    if (packOffset == 0) return selected;
     
    281268
    282269void CarryManager::extractAndSaveCarryOutBits(Value * bitblock, unsigned carryBit_pos, unsigned carryBitCount) {
    283     unsigned packIndex = carryBit_pos / PACK_SIZE;
    284     unsigned packOffset = carryBit_pos % PACK_SIZE;
    285     unsigned rshift = PACK_SIZE - packOffset - carryBitCount;
     270    unsigned packIndex = carryBit_pos / mPACK_SIZE;
     271    unsigned packOffset = carryBit_pos % mPACK_SIZE;
     272    unsigned rshift = mPACK_SIZE - packOffset - carryBitCount;
    286273    uint64_t mask = ((((uint64_t) 1) << carryBitCount) - 1)  << packOffset;
    287274    //std::cerr << "extractAndSaveCarryOutBits: packIndex =" << packIndex << ", packOffset = " << packOffset << ", mask = " << mask << std::endl;
    288     Value * field = iBuilder->mvmd_extract(PACK_SIZE, bitblock, BLOCK_SIZE/PACK_SIZE - 1);
     275    Value * field = iBuilder->mvmd_extract(mPACK_SIZE, bitblock, BLOCK_SIZE/mPACK_SIZE - 1);
    289276    //Value * field = maskSelectBitRange(field, PACK_SIZE - carryBitCount, carryBitCount);
    290277    if (rshift != 0) {
     
    311298Value * CarryManager::getCarryOpCarryIn(int localIndex) {
    312299    unsigned posn = carryOpPosition(localIndex);
    313 #ifdef PACKING
    314     return pack2bitblock(getCarryInBits(posn, 1));
    315 #else
    316     return getCarryPack(posn);
    317 #endif
     300    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
     301        return pack2bitblock(getCarryInBits(posn, 1));
     302    }
     303    else {
     304        return getCarryPack(posn);
     305    }
    318306}
    319307
     
    321309void CarryManager::setCarryOpCarryOut(unsigned localIndex, Value * carry_out_strm) {
    322310    unsigned posn = carryOpPosition(localIndex);
    323 #ifdef PACKING
    324     extractAndSaveCarryOutBits(carry_out_strm, posn, 1);
    325 #else
    326     Value * carry_bit = mBuilder->CreateLShr(mBuilder->CreateBitCast(carry_out_strm, mBuilder->getIntNTy(BLOCK_SIZE)), 127);
    327     mCarryOutPack[posn] = mBuilder->CreateBitCast(carry_bit, mBitBlockType);
    328     if (mCarryInfo->getWhileDepth() == 0) {
    329         storeCarryPack(posn);
    330     }
    331 #endif
     311    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
     312        extractAndSaveCarryOutBits(carry_out_strm, posn, 1);
     313    }
     314    else {
     315        Value * carry_bit = mBuilder->CreateLShr(mBuilder->CreateBitCast(carry_out_strm, mBuilder->getIntNTy(BLOCK_SIZE)), 127);
     316        mCarryOutPack[posn] = mBuilder->CreateBitCast(carry_bit, mBitBlockType);
     317        if (mCarryInfo->getWhileDepth() == 0) {
     318            storeCarryPack(posn);
     319        }
     320    }
    332321}
    333322
     
    373362Value * CarryManager::unitAdvanceCarryInCarryOut(int localIndex, Value * strm) {
    374363    unsigned posn = advance1Position(localIndex);
    375 #ifdef PACKING
    376     extractAndSaveCarryOutBits(strm, posn, 1);
    377     Value* carry_longint = mBuilder->CreateZExt(getCarryInBits(posn, 1), mBuilder->getIntNTy(BLOCK_SIZE));
    378     Value* strm_longint = mBuilder->CreateBitCast(strm, mBuilder->getIntNTy(BLOCK_SIZE));
    379     Value* adv_longint = mBuilder->CreateOr(mBuilder->CreateShl(strm_longint, 1), carry_longint);
    380     Value* result_value = mBuilder->CreateBitCast(adv_longint, mBitBlockType);
    381     return result_value;
    382 #else
    383     mCarryOutPack[posn] = strm; 
     364    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
     365        extractAndSaveCarryOutBits(strm, posn, 1);
     366        Value* carry_longint = mBuilder->CreateZExt(getCarryInBits(posn, 1), mBuilder->getIntNTy(BLOCK_SIZE));
     367        Value* strm_longint = mBuilder->CreateBitCast(strm, mBuilder->getIntNTy(BLOCK_SIZE));
     368        Value* adv_longint = mBuilder->CreateOr(mBuilder->CreateShl(strm_longint, 1), carry_longint);
     369        Value* result_value = mBuilder->CreateBitCast(adv_longint, mBitBlockType);
     370        return result_value;
     371    }
     372    mCarryOutPack[posn] = strm;
    384373    Value * carry_in = getCarryPack(posn);
    385374    if (mCarryInfo->getWhileDepth() == 0) {
     
    399388#endif
    400389    return result_value;
    401 #endif
    402390}
    403391
    404392Value * CarryManager::shortAdvanceCarryInCarryOut(int localIndex, int shift_amount, Value * strm) {
    405393    unsigned posn = shortAdvancePosition(localIndex);
    406 #ifdef PACKING
    407     extractAndSaveCarryOutBits(strm, posn, shift_amount);
    408     //std::cerr << "shortAdvanceCarryInCarryOut: posn = " << posn << ", shift_amount = " << shift_amount << std::endl;
    409     Value* carry_longint = mBuilder->CreateZExt(getCarryInBits(posn, shift_amount), mBuilder->getIntNTy(BLOCK_SIZE));
    410     Value* strm_longint = mBuilder->CreateBitCast(strm, mBuilder->getIntNTy(BLOCK_SIZE));
    411     Value* adv_longint = mBuilder->CreateOr(mBuilder->CreateShl(strm_longint, shift_amount), carry_longint);
    412     Value* result_value = mBuilder->CreateBitCast(adv_longint, mBitBlockType);
    413     return result_value;
    414 #else
    415     mCarryOutPack[posn] = strm; 
     394    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
     395        extractAndSaveCarryOutBits(strm, posn, shift_amount);
     396        //std::cerr << "shortAdvanceCarryInCarryOut: posn = " << posn << ", shift_amount = " << shift_amount << std::endl;
     397        Value* carry_longint = mBuilder->CreateZExt(getCarryInBits(posn, shift_amount), mBuilder->getIntNTy(BLOCK_SIZE));
     398        Value* strm_longint = mBuilder->CreateBitCast(strm, mBuilder->getIntNTy(BLOCK_SIZE));
     399        Value* adv_longint = mBuilder->CreateOr(mBuilder->CreateShl(strm_longint, shift_amount), carry_longint);
     400        Value* result_value = mBuilder->CreateBitCast(adv_longint, mBitBlockType);
     401        return result_value;
     402    }
     403    mCarryOutPack[posn] = strm;
    416404    Value * carry_in = getCarryPack(posn);
    417405    if (mCarryInfo->getWhileDepth() == 0) {
     
    422410    Value* adv_longint = mBuilder->CreateOr(mBuilder->CreateShl(strm_longint, shift_amount), mBuilder->CreateLShr(advanceq_longint, BLOCK_SIZE - shift_amount), "advance");
    423411    return mBuilder->CreateBitCast(adv_longint, mBitBlockType);
    424 #endif
    425412}
    426413   
     
    491478Value * CarryManager::getCarrySummaryExpr() {
    492479    unsigned summary_index = summaryPackIndex();
    493 #ifdef PACKING
    494     Value * pack = getCarryPack(summary_index);
    495     Value * summary_bits = maskSelectBitRange(pack, summaryPosition() % PACK_SIZE, summaryBits());
    496     return mBuilder->CreateBitCast(mBuilder->CreateZExt(summary_bits, mBuilder->getIntNTy(BLOCK_SIZE)), mBitBlockType);
    497 #else
    498     return getCarryPack(summary_index);
    499 #endif
     480    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
     481        Value * pack = getCarryPack(summary_index);
     482        Value * summary_bits = maskSelectBitRange(pack, summaryPosition() % mPACK_SIZE, summaryBits());
     483        return mBuilder->CreateBitCast(mBuilder->CreateZExt(summary_bits, mBuilder->getIntNTy(BLOCK_SIZE)), mBitBlockType);
     484    }
     485    else {
     486        return getCarryPack(summary_index);
     487    }
    500488}
    501489
     
    515503        return;
    516504    }
    517 #ifdef PACKING
    518     if (ifScopeCarrySize <= PACK_SIZE) {
    519         unsigned const ifPackIndex = scopeBasePack();
    520         PHINode * ifPack_phi = mBuilder->CreatePHI(mCarryPackType, 2, "ifPack");
    521         ifPack_phi->addIncoming(mCarryInfo->ifEntryPack, ifEntryBlock);
    522         ifPack_phi->addIncoming(mCarryOutPack[ifPackIndex], ifBodyFinalBlock);
    523         mCarryOutPack[ifPackIndex] = ifPack_phi;
    524         return;
    525     }
    526 #endif
     505    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
     506        if (ifScopeCarrySize <= mPACK_SIZE) {
     507            unsigned const ifPackIndex = scopeBasePack();
     508            PHINode * ifPack_phi = mBuilder->CreatePHI(mCarryPackType, 2, "ifPack");
     509            ifPack_phi->addIncoming(mCarryInfo->ifEntryPack, ifEntryBlock);
     510            ifPack_phi->addIncoming(mCarryOutPack[ifPackIndex], ifBodyFinalBlock);
     511            mCarryOutPack[ifPackIndex] = ifPack_phi;
     512            return;
     513        }
     514    }
    527515    if (mCarryInfo->getIfDepth() > 1) {
    528516        const unsigned summaryIndex = summaryPackIndex();
     
    655643   single full pack for this scope*/
    656644void CarryManager::ensureCarriesStoredLocal() {
    657 #ifdef PACKING
    658     const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
    659     if ((scopeCarryPacks > 0) && ((mCurrentFrameIndex % PACK_SIZE) == 0)) {
    660         // We have carry data and we are not in the middle of a pack.
    661         // Write out all local packs.
    662         auto localCarryIndex = localBasePack();
    663         auto localCarryPacks = mCarryInfo->getLocalCarryPackCount();
    664         for (auto i = localCarryIndex; i < localCarryIndex + localCarryPacks; i++) {
    665             storeCarryPack(i);
    666         }
    667         if ((localCarryPacks == 0) && (scopeCarryPacks == 1) && (mCarryInfo->nested.entries > 1)) {
    668             storeCarryPack(localCarryIndex);
    669         }
    670     }
    671 #endif
     645    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
     646        const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
     647        if ((scopeCarryPacks > 0) && ((mCurrentFrameIndex % mPACK_SIZE) == 0)) {
     648            // We have carry data and we are not in the middle of a pack.
     649            // Write out all local packs.
     650            auto localCarryIndex = localBasePack();
     651            auto localCarryPacks = mCarryInfo->getLocalCarryPackCount();
     652            for (auto i = localCarryIndex; i < localCarryIndex + localCarryPacks; i++) {
     653                storeCarryPack(i);
     654            }
     655            if ((localCarryPacks == 0) && (scopeCarryPacks == 1) && (mCarryInfo->nested.entries > 1)) {
     656                storeCarryPack(localCarryIndex);
     657            }
     658        }
     659    }
    672660}
    673661
Note: See TracChangeset for help on using the changeset viewer.