source: icGREP/icgrep-devel/icgrep/pablo/carry_manager.cpp @ 4898

Last change on this file since 4898 was 4898, checked in by cameron, 3 years ago

Add IRBuilder functionality to IDISA_Builder; eliminate separate mBuilder

File size: 34.0 KB
RevLine 
[4644]1/*
2 *  Copyright (c) 2015 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6
7
8#include <include/simd-lib/bitblock.hpp>
9#include <stdexcept>
[4683]10#include <pablo/carry_data.h>
11#include <pablo/codegenstate.h>
12#include <pablo/carry_manager.h>
13#include <pablo/pabloAST.h>
[4647]14#include <iostream>
[4722]15#include <llvm/Support/CommandLine.h>
[4726]16#include <llvm/IR/BasicBlock.h>
17#include <llvm/IR/CallingConv.h>
18#include <llvm/IR/Function.h>
[4644]19
[4715]20static cl::opt<CarryManagerStrategy> Strategy(cl::desc("Choose carry management strategy:"),
21                                              cl::values(
22                                                         clEnumVal(BitBlockStrategy, "Unpacked, each carry in a separate bitblock."),
23                                                         clEnumVal(SequentialFullyPackedStrategy, "Sequential packing, up to 64 carries per pack."),
24                                                         clEnumValEnd));
25
26
[4644]27namespace pablo {
[4687]28 
29    unsigned doScopeCount(PabloBlock * pb) {
30        unsigned count = 1;
31       
32        for (Statement * stmt : *pb) {
33            if (If * ifStatement = dyn_cast<If>(stmt)) {
[4870]34                count += doScopeCount(ifStatement->getBody());
[4687]35            }
36            else if (While * whileStatement = dyn_cast<While>(stmt)) {
[4870]37                count += doScopeCount(whileStatement->getBody());
[4687]38            }
39        }
40        return count;
41       
42    }
[4824]43   
44void CarryManager::generateCarryDataInitializer(Module * m) {
45    FunctionType * functionType = FunctionType::get(Type::getVoidTy(m->getContext()), std::vector<Type *>({}), false);
46    SmallVector<AttributeSet, 1> Attrs;
47    Attrs.push_back(AttributeSet::get(m->getContext(), ~0U, std::vector<Attribute::AttrKind>({ Attribute::NoUnwind, Attribute::UWTable })));
48    AttributeSet AttrSet = AttributeSet::get(m->getContext(), Attrs);
49   
50    // Create the function that will be generated.
51    Function * f = Function::Create(functionType, GlobalValue::ExternalLinkage, "process_block_initialize_carries", m);
52    f->setCallingConv(CallingConv::C);
53    f->setAttributes(AttrSet);
[4898]54    llvm::IRBuilderBase::InsertPoint ip = iBuilder->saveIP();
55    iBuilder->SetInsertPoint(BasicBlock::Create(m->getContext(), "entry1", f,0));
56    iBuilder->CreateMemSet(mCarryBitBlockPtr, iBuilder->getInt8(0), mTotalCarryDataBitBlocks * mBITBLOCK_WIDTH/8, 4);
57    ReturnInst::Create(m->getContext(), iBuilder->GetInsertBlock());
58    iBuilder->restoreIP(ip);
[4824]59}
60   
61   
[4644]62
[4726]63void CarryManager::initialize(Module * m, PabloBlock * pb) {
[4644]64    mPabloRoot = pb;
[4687]65    unsigned scopeCount = doScopeCount(pb);
66    mCarryInfoVector.resize(scopeCount);
[4729]67    if (Strategy == SequentialFullyPackedStrategy) {
68        mPACK_SIZE = 64;
69        mITEMS_PER_PACK = 64;
[4898]70        mCarryPackType = iBuilder->getIntNTy(mPACK_SIZE);
[4729]71    }
72    else {
[4827]73        mPACK_SIZE = mBITBLOCK_WIDTH;
[4729]74        mITEMS_PER_PACK = 1;
75        mCarryPackType = mBitBlockType;
76    }
[4715]77    unsigned totalCarryDataSize = enumerate(pb, 0, 0);
[4687]78   
[4715]79    unsigned totalPackCount = (totalCarryDataSize + mITEMS_PER_PACK - 1)/mITEMS_PER_PACK;
80
[4703]81    mCarryPackPtr.resize(totalPackCount);
82    mCarryInPack.resize(totalPackCount);
83    mCarryOutPack.resize(totalPackCount);
[4750]84    for (unsigned i = 0; i < totalPackCount; i++) mCarryInPack[i]=nullptr;
[4715]85
86    if (Strategy == SequentialFullyPackedStrategy) {
[4827]87        mTotalCarryDataBitBlocks = (totalCarryDataSize + mBITBLOCK_WIDTH - 1)/mBITBLOCK_WIDTH;       
[4715]88    }
89    else {
90        mTotalCarryDataBitBlocks = totalCarryDataSize;
91    }
[4726]92   
93    ArrayType* cdArrayTy = ArrayType::get(mBitBlockType, mTotalCarryDataBitBlocks);
94    GlobalVariable* cdArray = new GlobalVariable(*m, cdArrayTy, /*isConstant=*/false, GlobalValue::CommonLinkage, /*Initializer=*/0, "process_block_carry_data");
[4827]95    cdArray->setAlignment(mBITBLOCK_WIDTH/8);
[4726]96    ConstantAggregateZero* cdInitData = ConstantAggregateZero::get(cdArrayTy);
97    cdArray->setInitializer(cdInitData);
98   
[4898]99    mCarryPackBasePtr = iBuilder->CreateBitCast(cdArray, PointerType::get(mCarryPackType, 0));
100    mCarryBitBlockPtr = iBuilder->CreateBitCast(cdArray, PointerType::get(mBitBlockType, 0));
[4726]101   
[4824]102    generateCarryDataInitializer(m);
103   
[4720]104    // Popcount data is stored after all the carry data.
105    if (mPabloCountCount > 0) {
[4898]106        ArrayType* pcArrayTy = ArrayType::get(iBuilder->getIntNTy(64), mPabloCountCount);
[4726]107        GlobalVariable* pcArray = new GlobalVariable(*m, pcArrayTy, /*isConstant=*/false, GlobalValue::CommonLinkage, 0, "popcount_data");
[4827]108        cdArray->setAlignment(mBITBLOCK_WIDTH/8);
[4726]109        ConstantAggregateZero* pcInitData = ConstantAggregateZero::get(pcArrayTy);
110        pcArray->setInitializer(pcInitData);
[4898]111        mPopcountBasePtr = iBuilder->CreateBitCast(pcArray, Type::getInt64PtrTy(iBuilder->getContext()));
[4720]112    }
[4715]113    // Carry Data area will have one extra bit block to store the block number.
[4898]114    GlobalVariable* blkNo = new GlobalVariable(*m, iBuilder->getIntNTy(64), /*isConstant=*/false, GlobalValue::CommonLinkage, 0, "blockNo");
[4733]115    blkNo->setAlignment(16);
[4898]116    blkNo->setInitializer(iBuilder->getInt64(0));
[4726]117    mBlockNoPtr = blkNo;
[4898]118    mBlockNo = iBuilder->CreateLoad(mBlockNoPtr);
[4690]119    /*  Set the current scope to PabloRoot */
120    mCurrentScope = mPabloRoot;
[4691]121    mCurrentFrameIndex = 0;
[4690]122    mCarryInfo = mCarryInfoVector[0];
[4644]123}
[4672]124   
[4644]125void CarryManager::generateBlockNoIncrement() {
[4898]126    iBuilder->CreateStore(iBuilder->CreateAdd(mBlockNo, iBuilder->getInt64(1)), mBlockNoPtr);
[4644]127}
128
129Value * CarryManager::getBlockNoPtr() {
130    return mBlockNoPtr;
131}
132
[4694]133
[4689]134unsigned CarryManager::enumerate(PabloBlock * blk, unsigned ifDepth, unsigned whileDepth) {
[4687]135    llvm::raw_os_ostream cerr(std::cerr);
136    unsigned idx = blk->getScopeIndex();
[4715]137    PabloBlockCarryData * cd = new PabloBlockCarryData(blk, mPACK_SIZE, mITEMS_PER_PACK);
[4687]138    mCarryInfoVector[idx] = cd;
139
140    cd->setIfDepth(ifDepth);
141    cd->setWhileDepth(whileDepth);
[4704]142    unsigned nestedOffset = cd->nested.frameOffset;
[4687]143 
144    for (Statement * stmt : *blk) {
[4720]145        if (Count * c = dyn_cast<Count>(stmt)) {
146            c->setGlobalCountIndex(mPabloCountCount);
147            mPabloCountCount++;
148        }
149        else if (If * ifStatement = dyn_cast<If>(stmt)) {
[4870]150            const unsigned ifCarryDataBits = enumerate(ifStatement->getBody(), ifDepth+1, whileDepth);
151            PabloBlockCarryData * nestedBlockData = mCarryInfoVector[ifStatement->getBody()->getScopeIndex()];
[4715]152            if (mITEMS_PER_PACK == mPACK_SIZE) {  // PACKING
[4714]153                if (cd->roomInFinalPack(nestedOffset) < ifCarryDataBits) {
[4715]154                    nestedOffset = alignCeiling(nestedOffset, mPACK_SIZE);
[4714]155                }
156            }
[4689]157            nestedBlockData->setFramePosition(nestedOffset);
158
[4687]159            nestedOffset += ifCarryDataBits;
160            if (cd->maxNestingDepth <= nestedBlockData->maxNestingDepth) cd->maxNestingDepth = nestedBlockData->maxNestingDepth + 1;
161            cd->nested.entries++;
[4732]162#ifdef CARRY_DEBUG
[4696]163            nestedBlockData->dumpCarryData(cerr);
164#endif
[4687]165        }
166        else if (While * whileStatement = dyn_cast<While>(stmt)) {
[4870]167            const unsigned whileCarryDataBits = enumerate(whileStatement->getBody(), ifDepth, whileDepth+1);
168            PabloBlockCarryData * nestedBlockData = mCarryInfoVector[whileStatement->getBody()->getScopeIndex()];
[4687]169            //if (whileStatement->isMultiCarry()) whileCarryDataBits *= whileStatement->getMaxIterations();
[4715]170            if (mITEMS_PER_PACK == mPACK_SIZE) {  // PACKING
[4714]171                if (cd->roomInFinalPack(nestedOffset) < whileCarryDataBits) {
[4715]172                    nestedOffset = alignCeiling(nestedOffset, mPACK_SIZE);
[4714]173                }
174            }
[4689]175            nestedBlockData->setFramePosition(nestedOffset);
[4687]176            nestedOffset += whileCarryDataBits;
177            if (cd->maxNestingDepth <= nestedBlockData->maxNestingDepth) cd->maxNestingDepth = nestedBlockData->maxNestingDepth + 1;
178            cd->nested.entries++;
[4732]179#ifdef CARRY_DEBUG
[4696]180            nestedBlockData->dumpCarryData(cerr);
181#endif
[4687]182        }
183    }
184   
[4704]185    cd->scopeCarryDataSize = nestedOffset;
[4687]186   
187    if (cd->explicitSummaryRequired()) {
188        // Need extra space for the summary variable, always the last
189        // entry within an if block.
[4715]190        if (mITEMS_PER_PACK == mPACK_SIZE) {  // PACKING
191            cd->scopeCarryDataSize = alignCeiling(cd->scopeCarryDataSize, mPACK_SIZE);
[4714]192        }
[4704]193        cd->summary.frameOffset = cd->scopeCarryDataSize;
[4715]194        cd->scopeCarryDataSize += mITEMS_PER_PACK;  //  computed summary is a full pack.
[4687]195    }
196    else {
[4704]197        cd->summary.frameOffset = 0;
[4687]198    }
[4732]199#ifdef CARRY_DEBUG
[4713]200    if (cd->ifDepth == 0) cd->dumpCarryData(cerr);
201#endif
[4704]202    return cd->scopeCarryDataSize;
[4687]203}
204
205
[4670]206/* Entering and leaving blocks. */
[4644]207
[4670]208void CarryManager::enterScope(PabloBlock * blk) {
209   
210    mCurrentScope = blk;
[4687]211    mCarryInfo = mCarryInfoVector[blk->getScopeIndex()];
[4691]212    mCurrentFrameIndex += mCarryInfo->getFrameIndex();
[4704]213    //std::cerr << "enterScope:  blk->getScopeIndex() = " << blk->getScopeIndex() << ", mCurrentFrameIndex = " << mCurrentFrameIndex << std::endl;
[4670]214}
215
216void CarryManager::leaveScope() {
[4691]217    mCurrentFrameIndex -= mCarryInfo->getFrameIndex();
[4703]218    if (mCurrentScope != mPabloRoot) {
219        mCurrentScope = mCurrentScope->getParent();
220        mCarryInfo = mCarryInfoVector[mCurrentScope->getScopeIndex()];
221    }
[4691]222    //std::cerr << "leaveScope:  mCurrentFrameIndex = " << mCurrentFrameIndex << std::endl;
[4670]223}
224
[4694]225
226/* Helper routines */
227
[4704]228unsigned CarryManager::absPosition(unsigned frameOffset, unsigned relPos) {
229    return mCurrentFrameIndex + frameOffset + relPos;
[4697]230}
[4694]231
[4697]232
233unsigned CarryManager::carryOpPosition(unsigned localIndex) {
[4704]234    //std::cerr << "carryOpPosition: addWithCarry.frameOffset = " << mCarryInfo->addWithCarry.frameOffset << ", localIndex = " <<localIndex << std::endl;
235    return absPosition(mCarryInfo->addWithCarry.frameOffset, localIndex);
[4697]236}
237
238unsigned CarryManager::advance1Position(unsigned localIndex) {
[4704]239    //std::cerr << "unsigned CarryManager::advance1Position: advance1.frameOffset = " << mCarryInfo->advance1.frameOffset << ", localIndex = " <<localIndex << std::endl;
240    return absPosition(mCarryInfo->advance1.frameOffset, localIndex);
[4697]241}
242
243unsigned CarryManager::shortAdvancePosition(unsigned localIndex) {
[4704]244    return absPosition(mCarryInfo->shortAdvance.frameOffset, localIndex);
[4697]245}
246
[4698]247unsigned CarryManager::longAdvanceBitBlockPosition(unsigned localIndex) {
[4715]248    return (mCurrentFrameIndex + mCarryInfo->longAdvance.frameOffset) / mITEMS_PER_PACK + localIndex;
[4697]249}
[4700]250   
251unsigned CarryManager::localBasePack() {
[4715]252    return (mCurrentFrameIndex + mCarryInfo->shortAdvance.frameOffset) / mITEMS_PER_PACK;
[4700]253}
254   
255unsigned CarryManager::scopeBasePack() {
[4715]256    return mCurrentFrameIndex / mITEMS_PER_PACK;
[4700]257}
258   
[4697]259
[4700]260
[4697]261unsigned CarryManager::summaryPosition() {
[4704]262    return absPosition(mCarryInfo->summary.frameOffset, 0);
[4697]263}
264
[4710]265
266unsigned CarryManager::summaryPackIndex() {
[4715]267    return summaryPosition()/mITEMS_PER_PACK;
[4710]268}
269
[4697]270unsigned CarryManager::summaryBits() {
[4715]271    if (mCarryInfo->scopeCarryDataSize > mITEMS_PER_PACK) return mPACK_SIZE;
[4704]272    else return mCarryInfo->scopeCarryDataSize;
[4697]273}
274
275
276
[4694]277Value * CarryManager::getCarryPack(unsigned packIndex) {
278    if (mCarryInPack[packIndex] == nullptr) {
[4898]279        Value * packPtr = iBuilder->CreateGEP(mCarryPackBasePtr, iBuilder->getInt64(packIndex));
[4710]280        // Save the computed pointer - so that it can be used in storeCarryPack.
[4694]281        mCarryPackPtr[packIndex] = packPtr;
[4898]282        mCarryInPack[packIndex] = iBuilder->CreateAlignedLoad(packPtr, mPACK_SIZE/8);
[4694]283    }
284    return mCarryInPack[packIndex];
285}
[4837]286   
[4696]287void CarryManager::storeCarryPack(unsigned packIndex) {
[4898]288    iBuilder->CreateAlignedStore(mCarryOutPack[packIndex], mCarryPackPtr[packIndex], mPACK_SIZE/8);
[4694]289}
290
[4708]291   
[4707]292/* maskSelectBitRange selects the bits of a pack from lo_bit through
[4708]293   lo_bit + bitCount - 1, setting all other bits to zero.  */
294   
[4707]295Value * CarryManager::maskSelectBitRange(Value * pack, unsigned lo_bit, unsigned bitCount) {
[4715]296    if (bitCount == mPACK_SIZE) {
[4707]297        assert(lo_bit == 0);
298        return pack;
[4694]299    }
[4709]300    uint64_t mask = ((((uint64_t) 1) << bitCount) - 1) << lo_bit;
[4898]301    return iBuilder->CreateAnd(pack, ConstantInt::get(mCarryPackType, mask));
[4694]302}
[4708]303   
[4707]304Value * CarryManager::getCarryInBits(unsigned carryBitPos, unsigned carryBitCount) {
[4715]305    unsigned packIndex = carryBitPos / mPACK_SIZE;
306    unsigned packOffset = carryBitPos % mPACK_SIZE;
[4707]307    Value * selected = maskSelectBitRange(getCarryPack(packIndex), packOffset, carryBitCount);
308    if (packOffset == 0) return selected;
[4898]309    return iBuilder->CreateLShr(selected, packOffset);
[4704]310}
311
[4707]312void CarryManager::extractAndSaveCarryOutBits(Value * bitblock, unsigned carryBit_pos, unsigned carryBitCount) {
[4715]313    unsigned packIndex = carryBit_pos / mPACK_SIZE;
314    unsigned packOffset = carryBit_pos % mPACK_SIZE;
315    unsigned rshift = mPACK_SIZE - packOffset - carryBitCount;
[4709]316    uint64_t mask = ((((uint64_t) 1) << carryBitCount) - 1)  << packOffset;
317    //std::cerr << "extractAndSaveCarryOutBits: packIndex =" << packIndex << ", packOffset = " << packOffset << ", mask = " << mask << std::endl;
[4827]318    Value * field = iBuilder->mvmd_extract(mPACK_SIZE, bitblock, mBITBLOCK_WIDTH/mPACK_SIZE - 1);
[4707]319    //Value * field = maskSelectBitRange(field, PACK_SIZE - carryBitCount, carryBitCount);
320    if (rshift != 0) {
[4898]321        field = iBuilder->CreateLShr(field, iBuilder->getInt64(rshift));
[4707]322    }
323    if (packOffset != 0) {
[4898]324        field = iBuilder->CreateAnd(field, iBuilder->getInt64(mask));
[4707]325    }
326    if (mCarryOutPack[packIndex] == nullptr) {
327        mCarryOutPack[packIndex] = field;
328    }
329    else {
[4898]330        mCarryOutPack[packIndex] = iBuilder->CreateOr(mCarryOutPack[packIndex], field);
[4707]331    }
[4694]332}
[4704]333
[4707]334Value * CarryManager::pack2bitblock(Value * pack) {
[4898]335    return iBuilder->bitCast(iBuilder->CreateZExt(pack, iBuilder->getIntNTy(mBITBLOCK_WIDTH)));
[4707]336}
337   
[4696]338   
339/* Methods for getting and setting individual carry values. */
340   
[4670]341Value * CarryManager::getCarryOpCarryIn(int localIndex) {
[4697]342    unsigned posn = carryOpPosition(localIndex);
[4715]343    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
344        return pack2bitblock(getCarryInBits(posn, 1));
345    }
346    else {
347        return getCarryPack(posn);
348    }
[4644]349}
[4705]350
[4881]351#if (BLOCK_SIZE==256)
352#define LONGADD 1
353#endif
354
[4696]355   
[4703]356void CarryManager::setCarryOpCarryOut(unsigned localIndex, Value * carry_out_strm) {
[4697]357    unsigned posn = carryOpPosition(localIndex);
[4715]358    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
359        extractAndSaveCarryOutBits(carry_out_strm, posn, 1);
[4647]360    }
[4715]361    else {
[4881]362#ifndef LONGADD
[4898]363        Value * carry_bit = iBuilder->CreateLShr(iBuilder->CreateBitCast(carry_out_strm, iBuilder->getIntNTy(mBITBLOCK_WIDTH)), mBITBLOCK_WIDTH-1);
364        mCarryOutPack[posn] = iBuilder->CreateBitCast(carry_bit, mBitBlockType);
[4881]365#else
366        mCarryOutPack[posn] = carry_out_strm;
367#endif
[4715]368        if (mCarryInfo->getWhileDepth() == 0) {
369            storeCarryPack(posn);
370        }
371    }
[4644]372}
373
[4708]374Value * CarryManager::addCarryInCarryOut(int localIndex, Value* e1, Value* e2) {
[4828]375    if (mBITBLOCK_WIDTH == 128) {
376        Value * carryq_value = getCarryOpCarryIn(localIndex);
377        //calculate carry through logical ops
[4837]378        Value* carrygen = iBuilder->simd_and(e1, e2);
379        Value* carryprop = iBuilder->simd_or(e1, e2);
[4828]380        Value* digitsum = iBuilder->simd_add(64, e1, e2);
381        Value* partial = iBuilder->simd_add(64, digitsum, carryq_value);
[4898]382        Value* digitcarry = iBuilder->simd_or(carrygen, iBuilder->simd_and(carryprop, iBuilder->CreateNot(partial)));
383        Value* mid_carry_in = iBuilder->simd_slli(128, iBuilder->CreateLShr(digitcarry, 63), 64);
384        Value* sum = iBuilder->simd_add(64, partial, iBuilder->CreateBitCast(mid_carry_in, mBitBlockType));
385        Value* carry_out_strm = iBuilder->simd_or(carrygen, iBuilder->simd_and(carryprop, iBuilder->CreateNot(sum)));
[4828]386        setCarryOpCarryOut(localIndex, carry_out_strm);
387        return sum;
388    }
389    else {
[4881]390#ifndef LONGADD
[4828]391        Value * carryq_value = getCarryOpCarryIn(localIndex);
[4837]392        Value* carrygen = iBuilder->simd_and(e1, e2);
393        Value* carryprop = iBuilder->simd_or(e1, e2);
[4828]394        Value * sum = iBuilder->simd_add(mBITBLOCK_WIDTH, iBuilder->simd_add(mBITBLOCK_WIDTH, e1, e2), carryq_value);
[4898]395        Value* carry_out_strm = iBuilder->simd_or(carrygen, iBuilder->simd_and(carryprop, iBuilder->CreateNot(sum)));
[4828]396        setCarryOpCarryOut(localIndex, carry_out_strm);
397        return sum;
[4881]398#else
399        Value * carryq_value = getCarryOpCarryIn(localIndex);
400        Value * carryin = iBuilder->mvmd_extract(32, carryq_value, 0);
401        Value * carrygen = iBuilder->simd_and(e1, e2);
402        Value * carryprop = iBuilder->simd_or(e1, e2);
403        Value * digitsum = iBuilder->simd_add(64, e1, e2);
[4898]404        Value * digitcarry = iBuilder->simd_or(carrygen, iBuilder->simd_and(carryprop, iBuilder->CreateNot(digitsum)));
[4881]405        Value * carryMask = iBuilder->hsimd_signmask(64, digitcarry);
[4898]406        Value * carryMask2 = iBuilder->CreateOr(iBuilder->CreateAdd(carryMask, carryMask), carryin);
[4881]407        Value * bubble = iBuilder->simd_eq(64, digitsum, iBuilder->allOnes());
408        Value * bubbleMask = iBuilder->hsimd_signmask(64, bubble);
[4898]409        Value * incrementMask = iBuilder->CreateXor(iBuilder->CreateAdd(bubbleMask, carryMask2), bubbleMask);
[4881]410        Value * increments = iBuilder->esimd_bitspread(64,incrementMask);
411        Value * sum = iBuilder->simd_add(64, digitsum, increments);
[4898]412        Value * carry_out_strm = iBuilder->mvmd_insert(32, iBuilder->allZeroes(), iBuilder->CreateLShr(incrementMask, iBuilder->getBitBlockWidth()/64), 0);
[4881]413        setCarryOpCarryOut(localIndex, carry_out_strm);
414        return sum;
415#endif
[4828]416    }
[4708]417}
418
419
[4750]420Value * CarryManager::advanceCarryInCarryOut(int localIndex, unsigned shift_amount, Value * strm) {
[4654]421    if (shift_amount == 1) {
[4670]422        return unitAdvanceCarryInCarryOut(localIndex, strm);
[4647]423    }
[4654]424    else if (shift_amount < LongAdvanceBase) {
[4670]425        return shortAdvanceCarryInCarryOut(localIndex, shift_amount, strm);
[4654]426    }
427    else {
[4670]428        return longAdvanceCarryInCarryOut(localIndex, shift_amount, strm);
[4654]429    }
[4644]430}
431
[4845]432#define DSSLI_FIELDWIDTH 64
433
[4670]434Value * CarryManager::unitAdvanceCarryInCarryOut(int localIndex, Value * strm) {
[4697]435    unsigned posn = advance1Position(localIndex);
[4715]436    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
437        extractAndSaveCarryOutBits(strm, posn, 1);
[4898]438        Value* carry_longint = iBuilder->CreateZExt(getCarryInBits(posn, 1), iBuilder->getIntNTy(mBITBLOCK_WIDTH));
439        Value* strm_longint = iBuilder->CreateBitCast(strm, iBuilder->getIntNTy(mBITBLOCK_WIDTH));
440        Value* adv_longint = iBuilder->CreateOr(iBuilder->CreateShl(strm_longint, 1), carry_longint);
441        Value* result_value = iBuilder->CreateBitCast(adv_longint, mBitBlockType);
[4715]442        return result_value;
443    }
444    mCarryOutPack[posn] = strm;
[4697]445    Value * carry_in = getCarryPack(posn);
[4670]446    if (mCarryInfo->getWhileDepth() == 0) {
[4697]447        storeCarryPack(posn);
[4647]448    }
[4845]449    Value * ahead = iBuilder->mvmd_dslli(DSSLI_FIELDWIDTH, strm, carry_in, iBuilder->getBitBlockWidth()/DSSLI_FIELDWIDTH -1);
450    return iBuilder->simd_or(iBuilder->simd_srli(DSSLI_FIELDWIDTH, ahead, DSSLI_FIELDWIDTH-1), iBuilder->simd_slli(DSSLI_FIELDWIDTH, strm, 1));
[4644]451}
452
[4750]453Value * CarryManager::shortAdvanceCarryInCarryOut(int localIndex, unsigned shift_amount, Value * strm) {
[4697]454    unsigned posn = shortAdvancePosition(localIndex);
[4715]455    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
456        extractAndSaveCarryOutBits(strm, posn, shift_amount);
457        //std::cerr << "shortAdvanceCarryInCarryOut: posn = " << posn << ", shift_amount = " << shift_amount << std::endl;
[4898]458        Value* carry_longint = iBuilder->CreateZExt(getCarryInBits(posn, shift_amount), iBuilder->getIntNTy(mBITBLOCK_WIDTH));
459        Value* strm_longint = iBuilder->CreateBitCast(strm, iBuilder->getIntNTy(mBITBLOCK_WIDTH));
460        Value* adv_longint = iBuilder->CreateOr(iBuilder->CreateShl(strm_longint, shift_amount), carry_longint);
461        Value* result_value = iBuilder->CreateBitCast(adv_longint, mBitBlockType);
[4715]462        return result_value;
463    }
464    mCarryOutPack[posn] = strm;
[4697]465    Value * carry_in = getCarryPack(posn);
[4670]466    if (mCarryInfo->getWhileDepth() == 0) {
[4697]467        storeCarryPack(posn);
[4647]468    }
[4845]469    // Use a single whole-byte shift, if possible.
470    if (shift_amount % 8 == 0) {
471        return iBuilder->mvmd_dslli(8, strm, carry_in, iBuilder->getBitBlockWidth()/8 - shift_amount/8);
472    }
473    else if (shift_amount < DSSLI_FIELDWIDTH) {
474        Value * ahead = iBuilder->mvmd_dslli(DSSLI_FIELDWIDTH, strm, carry_in, iBuilder->getBitBlockWidth()/DSSLI_FIELDWIDTH - 1);
475        return iBuilder->simd_or(iBuilder->simd_srli(DSSLI_FIELDWIDTH, ahead, DSSLI_FIELDWIDTH-shift_amount), iBuilder->simd_slli(DSSLI_FIELDWIDTH, strm, shift_amount));
476    }
[4898]477    Value* advanceq_longint = iBuilder->CreateBitCast(carry_in, iBuilder->getIntNTy(mBITBLOCK_WIDTH));
478    Value* strm_longint = iBuilder->CreateBitCast(strm, iBuilder->getIntNTy(mBITBLOCK_WIDTH));
479    Value* adv_longint = iBuilder->CreateOr(iBuilder->CreateShl(strm_longint, shift_amount), iBuilder->CreateLShr(advanceq_longint, mBITBLOCK_WIDTH - shift_amount), "advance");
480    return iBuilder->CreateBitCast(adv_longint, mBitBlockType);
[4644]481}
[4654]482   
[4647]483
[4654]484/*  currently defined in carry_data.h
485 
[4647]486 static unsigned power2ceil (unsigned v) {
487 unsigned ceil = 1;
488 while (ceil < v) ceil *= 2;
489 return ceil;
490 }
491 
492 unsigned longAdvanceEntries(unsigned shift_amount) const {
[4827]493 return (shift_amount + mBITBLOCK_WIDTH - 1)/mBITBLOCK_WIDTH;
[4647]494 }
495 
496 unsigned longAdvanceBufferSize(unsigned shift_amount)  const {
497 return power2ceil(longAdvanceEntries(shift_amount));
498 }
499 */
[4797]500
[4654]501   
[4750]502Value * CarryManager::longAdvanceCarryInCarryOut(int localIndex, unsigned shift_amount, Value * carry_out) {
[4698]503    unsigned carryDataIndex = longAdvanceBitBlockPosition(localIndex);
[4898]504    Value * advBaseIndex = iBuilder->getInt64(carryDataIndex);
[4827]505    if (shift_amount <= mBITBLOCK_WIDTH) {
[4647]506        // special case using a single buffer entry and the carry_out value.
[4898]507        Value * advanceDataPtr = iBuilder->CreateGEP(mCarryBitBlockPtr, advBaseIndex);
508        Value * carry_block0 = iBuilder->CreateAlignedLoad(advanceDataPtr, mBITBLOCK_WIDTH/8);
509        iBuilder->CreateAlignedStore(carry_out, advanceDataPtr, mBITBLOCK_WIDTH/8);
[4647]510        /* Very special case - no combine */
[4827]511        if (shift_amount == mBITBLOCK_WIDTH) return carry_block0;
[4898]512        Value* block0_shr = iBuilder->CreateLShr(iBuilder->CreateBitCast(carry_block0, iBuilder->getIntNTy(mBITBLOCK_WIDTH)), mBITBLOCK_WIDTH - shift_amount);
513        Value* block1_shl = iBuilder->CreateShl(iBuilder->CreateBitCast(carry_out, iBuilder->getIntNTy(mBITBLOCK_WIDTH)), shift_amount);
514        return iBuilder->CreateBitCast(iBuilder->CreateOr(block1_shl, block0_shr), mBitBlockType);
[4647]515    }
516    // We need a buffer of at least two elements for storing the advance data.
[4827]517    const unsigned block_shift = shift_amount % mBITBLOCK_WIDTH;
[4670]518    const unsigned advanceEntries = mCarryInfo->longAdvanceEntries(shift_amount);
519    const unsigned bufsize = mCarryInfo->longAdvanceBufferSize(shift_amount);
[4898]520    Value * indexMask = iBuilder->getInt64(bufsize - 1);  // A mask to implement circular buffer indexing
521    Value * loadIndex0 = iBuilder->CreateAdd(iBuilder->CreateAnd(iBuilder->CreateSub(mBlockNo, iBuilder->getInt64(advanceEntries)), indexMask), advBaseIndex);
522    Value * storeIndex = iBuilder->CreateAdd(iBuilder->CreateAnd(mBlockNo, indexMask), advBaseIndex);
523    Value * carry_block0 = iBuilder->CreateAlignedLoad(iBuilder->CreateGEP(mCarryBitBlockPtr, loadIndex0), mBITBLOCK_WIDTH/8);
[4827]524    // If the long advance is an exact multiple of mBITBLOCK_WIDTH, we simply return the oldest
[4647]525    // block in the long advance carry data area. 
526    if (block_shift == 0) {
[4898]527        iBuilder->CreateAlignedStore(carry_out, iBuilder->CreateGEP(mCarryBitBlockPtr, storeIndex), mBITBLOCK_WIDTH/8);
[4647]528        return carry_block0;
[4644]529    }
530    // Otherwise we need to combine data from the two oldest blocks.
[4898]531    Value * loadIndex1 = iBuilder->CreateAdd(iBuilder->CreateAnd(iBuilder->CreateSub(mBlockNo, iBuilder->getInt64(advanceEntries-1)), indexMask), advBaseIndex);
532    Value * carry_block1 = iBuilder->CreateAlignedLoad(iBuilder->CreateGEP(mCarryBitBlockPtr, loadIndex1), mBITBLOCK_WIDTH/8);
533    Value* block0_shr = iBuilder->CreateLShr(iBuilder->CreateBitCast(carry_block0, iBuilder->getIntNTy(mBITBLOCK_WIDTH)), mBITBLOCK_WIDTH - block_shift);
534    Value* block1_shl = iBuilder->CreateShl(iBuilder->CreateBitCast(carry_block1, iBuilder->getIntNTy(mBITBLOCK_WIDTH)), block_shift);
535    iBuilder->CreateAlignedStore(carry_out, iBuilder->CreateGEP(mCarryBitBlockPtr, storeIndex), mBITBLOCK_WIDTH/8);
536    return iBuilder->CreateBitCast(iBuilder->CreateOr(block1_shl, block0_shr), mBitBlockType);
[4644]537}
[4647]538   
[4644]539
540/* Methods for getting and setting carry summary values */
541   
[4670]542bool CarryManager::blockHasCarries(){
543    return mCarryInfo->blockHasCarries();
[4644]544} 
545
[4670]546
[4838]547Value * CarryManager::generateBitBlockOrSummaryTest(Value * bitblock) {
548    Value * test_expr = bitblock;
549    if (mCarryInfo->blockHasCarries()) {
550        Value * summary_pack = getCarryPack(summaryPackIndex());
551        if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
552            Value * summary_bits = maskSelectBitRange(summary_pack, summaryPosition() % mPACK_SIZE, summaryBits());
[4898]553            test_expr = iBuilder->simd_or(test_expr, iBuilder->CreateZExt(summary_bits, iBuilder->getIntNTy(mBITBLOCK_WIDTH)));
[4838]554        }
555        else {
556            test_expr = iBuilder->simd_or(test_expr, summary_pack);
557        }
[4715]558    }
[4838]559    return iBuilder->bitblock_any(test_expr);
[4644]560}
561
[4704]562void CarryManager::initializeCarryDataAtIfEntry() {
[4721]563    if (blockHasCarries()) {
564        if (mCarryOutPack[scopeBasePack()] == nullptr) {
[4897]565            mCarryInfo->ifEntryPack = Constant::getNullValue(mCarryPackType);
[4721]566        }
567        else {
568            mCarryInfo->ifEntryPack = mCarryOutPack[scopeBasePack()];
569        }
[4703]570    }
[4704]571}
[4703]572   
[4704]573void CarryManager::buildCarryDataPhisAfterIfBody(BasicBlock * ifEntryBlock, BasicBlock * ifBodyFinalBlock) {
[4813]574    if (mCarryInfo->getWhileDepth() > 0) {
575        // We need to phi out everything for the while carry accumulation process.
576        const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
577        const unsigned currentScopeBase = scopeBasePack();
578        for (unsigned index = currentScopeBase; index < currentScopeBase + scopeCarryPacks; ++index) {
[4898]579            PHINode * phi_out = iBuilder->CreatePHI(mCarryPackType, 2);
[4897]580            phi_out->addIncoming(Constant::getNullValue(mCarryPackType),ifEntryBlock);
581            phi_out->addIncoming(mCarryOutPack[index], ifBodyFinalBlock);
[4813]582            mCarryOutPack[index] = phi_out;
583        }
584        return;
585    }
[4704]586    unsigned const ifScopeCarrySize = mCarryInfo->scopeCarryDataSize;
587    if (ifScopeCarrySize == 0) {
588        // No carry data, therefore no phi nodes.
589        return;
[4703]590    }
[4715]591    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
592        if (ifScopeCarrySize <= mPACK_SIZE) {
593            unsigned const ifPackIndex = scopeBasePack();
[4898]594            PHINode * ifPack_phi = iBuilder->CreatePHI(mCarryPackType, 2, "ifPack");
[4715]595            ifPack_phi->addIncoming(mCarryInfo->ifEntryPack, ifEntryBlock);
[4897]596            ifPack_phi->addIncoming(mCarryOutPack[ifPackIndex], ifBodyFinalBlock);
[4715]597            mCarryOutPack[ifPackIndex] = ifPack_phi;
598            return;
599        }
[4704]600    }
[4706]601    if (mCarryInfo->getIfDepth() > 1) {
[4813]602        // Our parent block is also an if.  It needs access to our summary to compute
603        // its own summary.
[4710]604        const unsigned summaryIndex = summaryPackIndex();
[4898]605        PHINode * summary_phi = iBuilder->CreatePHI(mCarryPackType, 2, "summary");
[4897]606        summary_phi->addIncoming(Constant::getNullValue(mCarryPackType), ifEntryBlock);
607        summary_phi->addIncoming(mCarryOutPack[summaryIndex], ifBodyFinalBlock);
[4710]608        mCarryOutPack[summaryIndex] = summary_phi;
[4704]609    }
610}
[4703]611   
[4811]612void CarryManager::addSummaryPhiIfNeeded(BasicBlock * ifEntryBlock, BasicBlock * ifBodyFinalBlock) {
[4676]613    if ((mCarryInfo->getIfDepth() <= 1) || !mCarryInfo->blockHasCarries()){
614        // For ifDepth == 1, the parent does not need a summary as it is not itself within an if.
615        // Therefore, it doesn't need access to this block's summary in building its own.
616        return;
617    }
[4710]618    const unsigned carrySummaryIndex = summaryPackIndex();
[4898]619    PHINode * summary_phi = iBuilder->CreatePHI(mCarryPackType, 2, "summary");
[4897]620    summary_phi->addIncoming(Constant::getNullValue(mCarryPackType), ifEntryBlock);
621    summary_phi->addIncoming(mCarryOutPack[carrySummaryIndex], ifBodyFinalBlock);
[4696]622    mCarryOutPack[carrySummaryIndex] = summary_phi;
[4644]623}
[4703]624   
[4676]625void CarryManager::generateCarryOutSummaryCodeIfNeeded() {
[4644]626   
[4676]627    if (!mCarryInfo->explicitSummaryRequired()) {
628        // An explicit summary may not be required, if there is a single carry
629        // operation within the block, or the carries are packed and all carry
630        // bits fit within a single pack.
[4644]631        return;
632    }
633   
[4710]634    const unsigned carrySummaryIndex = summaryPackIndex();
[4676]635   
[4897]636    Value * carry_summary = Constant::getNullValue(mCarryPackType);
[4670]637    if (mCarryInfo->blockHasLongAdvances()) { // Force if entry
[4897]638        carry_summary = Constant::getAllOnesValue(mCarryPackType);
[4644]639    }
640    else {
[4750]641        unsigned localCarryIndex = localBasePack();
642        unsigned localCarryPacks = mCarryInfo->getLocalCarryPackCount();
[4644]643        if (localCarryPacks > 0) {
[4696]644            carry_summary = mCarryOutPack[localCarryIndex];
[4750]645            for (unsigned i = 1; i < localCarryPacks; i++) {
[4898]646                carry_summary = iBuilder->CreateOr(carry_summary, mCarryOutPack[localCarryIndex+i]);
[4644]647            }
[4647]648        }
[4670]649        for (Statement * stmt : *mCurrentScope) {
[4644]650            if (If * innerIf = dyn_cast<If>(stmt)) {
[4870]651                PabloBlock * inner_blk = innerIf->getBody();
[4670]652                enterScope(inner_blk);
653                if (blockHasCarries()) {
[4898]654                  carry_summary = iBuilder->CreateOr(carry_summary, mCarryOutPack[summaryPackIndex()]);
[4644]655                }
[4670]656                leaveScope();
[4644]657            }
658            else if (While * innerWhile = dyn_cast<While>(stmt)) {
[4870]659                PabloBlock * inner_blk = innerWhile->getBody();
[4670]660                enterScope(inner_blk);
661                if (blockHasCarries()) {
[4898]662                    carry_summary = iBuilder->CreateOr(carry_summary, mCarryOutPack[summaryPackIndex()]);
[4670]663                }
664                leaveScope();
[4644]665            }
666        }
667    }
668    // Calculation of the carry out summary is complete.   Store it and make it
669    // available in case it must included by parent blocks.
[4696]670    mCarryOutPack[carrySummaryIndex] = carry_summary;
671    storeCarryPack(carrySummaryIndex);
[4644]672}
673
[4670]674void CarryManager::ensureCarriesLoadedRecursive() {
[4696]675    const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
[4700]676    const unsigned currentScopeBase = scopeBasePack();
[4670]677    if (mCarryInfo->getWhileDepth() == 1) {
[4700]678        for (auto i = currentScopeBase; i < currentScopeBase + scopeCarryPacks; ++i) {
[4694]679            getCarryPack(i);
[4644]680        }
681    }
682}
683
684
[4670]685void CarryManager::initializeCarryDataPhisAtWhileEntry(BasicBlock * whileEntryBlock) {
[4696]686    const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
687    mCarryOutAccumPhis.resize(scopeCarryPacks);
[4644]688#ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
[4700]689    const unsigned currentScopeBase = scopeBasePack();
[4696]690    mCarryInPhis.resize(scopeCarryPacks);
691#endif
692    for (unsigned index = 0; index < scopeCarryPacks; ++index) {
693#ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
[4898]694        PHINode * phi_in = iBuilder->CreatePHI(mCarryPackType, 2);
[4700]695        phi_in->addIncoming(mCarryInPack[currentScopeBase+index], whileEntryBlock);
[4644]696        mCarryInPhis[index] = phi_in;
697#endif
[4898]698        PHINode * phi_out = iBuilder->CreatePHI(mCarryPackType, 2);
[4897]699        phi_out->addIncoming(Constant::getNullValue(mCarryPackType), whileEntryBlock);
[4644]700        mCarryOutAccumPhis[index] = phi_out;
701    }
702}
703
704
[4670]705void CarryManager::extendCarryDataPhisAtWhileBodyFinalBlock(BasicBlock * whileBodyFinalBlock) {
[4696]706    const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
[4700]707    const unsigned currentScopeBase = scopeBasePack();
[4696]708    for (unsigned index = 0; index < scopeCarryPacks; ++index) {
[4644]709#ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
[4897]710        mCarryInPhis[index]->addIncoming(Constant::getNullValue(mCarryPackType), whileBodyFinalBlock);
[4644]711#endif
712        PHINode * phi = mCarryOutAccumPhis[index];
[4898]713        Value * carryOut = iBuilder->CreateOr(phi, mCarryOutPack[currentScopeBase+index]);
[4897]714        phi->addIncoming(carryOut, whileBodyFinalBlock);
[4700]715        mCarryOutPack[currentScopeBase+index] = carryOut;
[4644]716    }
717}
718
[4670]719void CarryManager::ensureCarriesStoredRecursive() {
[4696]720    const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
[4700]721    const unsigned currentScopeBase = scopeBasePack();
[4670]722    if (mCarryInfo->getWhileDepth() == 1) {
[4700]723        for (auto i = currentScopeBase; i < currentScopeBase + scopeCarryPacks; ++i) {
[4696]724            storeCarryPack(i);
[4644]725        }
726    }
727}
728
[4713]729/* Store all the full carry packs generated locally in this scope or the
730   single full pack for this scope*/
[4710]731void CarryManager::ensureCarriesStoredLocal() {
[4715]732    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
733        const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
734        if ((scopeCarryPacks > 0) && ((mCurrentFrameIndex % mPACK_SIZE) == 0)) {
735            // We have carry data and we are not in the middle of a pack.
736            // Write out all local packs.
737            auto localCarryIndex = localBasePack();
738            auto localCarryPacks = mCarryInfo->getLocalCarryPackCount();
739            for (auto i = localCarryIndex; i < localCarryIndex + localCarryPacks; i++) {
740                storeCarryPack(i);
741            }
742            if ((localCarryPacks == 0) && (scopeCarryPacks == 1) && (mCarryInfo->nested.entries > 1)) {
743                storeCarryPack(localCarryIndex);
744            }
[4710]745        }
746    }
[4644]747}
748
[4720]749Value * CarryManager::popCount(Value * to_count, unsigned globalIdx) {
[4898]750    Value * countPtr = iBuilder->CreateGEP(mPopcountBasePtr, iBuilder->getInt64(globalIdx));
751    Value * countSoFar = iBuilder->CreateAlignedLoad(countPtr, 8);
[4720]752    Value * fieldCounts = iBuilder->simd_popcount(64, to_count);
[4827]753    for (int i = 0; i < mBITBLOCK_WIDTH/64; i++) {
[4898]754        countSoFar = iBuilder->CreateAdd(countSoFar, iBuilder->mvmd_extract(64, fieldCounts, i));
[4720]755    }
[4898]756    iBuilder->CreateAlignedStore(countSoFar, countPtr, 8);
757    return iBuilder->bitCast(iBuilder->CreateZExt(countSoFar, iBuilder->getIntNTy(mBITBLOCK_WIDTH)));
[4720]758}
[4726]759
[4712]760CarryManager::~CarryManager() {
761    for (auto * cd : mCarryInfoVector) {
762        delete cd;
763    }
[4710]764}
765
[4712]766}
767
Note: See TracBrowser for help on using the repository browser.