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

Last change on this file since 4721 was 4721, checked in by cameron, 4 years ago

Minor fixes

File size: 29.5 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>
[4644]15
[4715]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
23
[4644]24namespace pablo {
[4687]25 
26    unsigned doScopeCount(PabloBlock * pb) {
27        unsigned count = 1;
28       
29        for (Statement * stmt : *pb) {
30            if (If * ifStatement = dyn_cast<If>(stmt)) {
31                count += doScopeCount(&ifStatement->getBody());
32            }
33            else if (While * whileStatement = dyn_cast<While>(stmt)) {
34                count += doScopeCount(&whileStatement->getBody());
35            }
36        }
37        return count;
38       
39    }
[4644]40
41unsigned CarryManager::initialize(PabloBlock * pb, Value * carryPtr) {
42    mPabloRoot = pb;
[4715]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    }
[4687]59    unsigned scopeCount = doScopeCount(pb);
60    mCarryInfoVector.resize(scopeCount);
[4715]61    unsigned totalCarryDataSize = enumerate(pb, 0, 0);
[4687]62   
[4715]63    unsigned totalPackCount = (totalCarryDataSize + mITEMS_PER_PACK - 1)/mITEMS_PER_PACK;
64
[4703]65    mCarryPackPtr.resize(totalPackCount);
66    mCarryInPack.resize(totalPackCount);
67    mCarryOutPack.resize(totalPackCount);
68    for (auto i = 0; i < totalPackCount; i++) mCarryInPack[i]=nullptr;
[4715]69
70    if (Strategy == SequentialFullyPackedStrategy) {
71        mTotalCarryDataBitBlocks = (totalCarryDataSize + BLOCK_SIZE - 1)/BLOCK_SIZE;
72    }
73    else {
74        mTotalCarryDataBitBlocks = totalCarryDataSize;
75    }
[4720]76    // Popcount data is stored after all the carry data.
77    if (mPabloCountCount > 0) {
78        mPopcountBasePtr = mBuilder->CreateBitCast(mBuilder->CreateGEP(carryPtr, mBuilder->getInt64(mTotalCarryDataBitBlocks)), Type::getInt64PtrTy(mBuilder->getContext()));
79        mTotalCarryDataBitBlocks += (mPabloCountCount + BLOCK_SIZE/64 - 1) * 64/BLOCK_SIZE;
80    }
[4715]81    // Carry Data area will have one extra bit block to store the block number.
82    mBlockNoPtr = mBuilder->CreateBitCast(mBuilder->CreateGEP(carryPtr, mBuilder->getInt64(mTotalCarryDataBitBlocks)), Type::getInt64PtrTy(mBuilder->getContext()));
83    mBlockNo = mBuilder->CreateLoad(mBlockNoPtr);
[4690]84    /*  Set the current scope to PabloRoot */
85    mCurrentScope = mPabloRoot;
[4691]86    mCurrentFrameIndex = 0;
[4690]87    mCarryInfo = mCarryInfoVector[0];
[4694]88    return mTotalCarryDataBitBlocks + 1; // One extra element for the block no.
[4644]89}
[4672]90   
[4644]91void CarryManager::generateBlockNoIncrement() {
92    mBuilder->CreateStore(mBuilder->CreateAdd(mBlockNo, mBuilder->getInt64(1)), mBlockNoPtr);
93}
94
95Value * CarryManager::getBlockNoPtr() {
96    return mBlockNoPtr;
97}
98
[4694]99
[4689]100unsigned CarryManager::enumerate(PabloBlock * blk, unsigned ifDepth, unsigned whileDepth) {
[4687]101    llvm::raw_os_ostream cerr(std::cerr);
102    unsigned idx = blk->getScopeIndex();
[4715]103    PabloBlockCarryData * cd = new PabloBlockCarryData(blk, mPACK_SIZE, mITEMS_PER_PACK);
[4687]104    mCarryInfoVector[idx] = cd;
105
106    cd->setIfDepth(ifDepth);
107    cd->setWhileDepth(whileDepth);
[4704]108    unsigned nestedOffset = cd->nested.frameOffset;
[4687]109 
110    for (Statement * stmt : *blk) {
[4720]111        if (Count * c = dyn_cast<Count>(stmt)) {
112            c->setGlobalCountIndex(mPabloCountCount);
113            mPabloCountCount++;
114        }
115        else if (If * ifStatement = dyn_cast<If>(stmt)) {
[4689]116            const unsigned ifCarryDataBits = enumerate(&ifStatement->getBody(), ifDepth+1, whileDepth);
[4687]117            PabloBlockCarryData * nestedBlockData = mCarryInfoVector[ifStatement->getBody().getScopeIndex()];
[4715]118            if (mITEMS_PER_PACK == mPACK_SIZE) {  // PACKING
[4714]119                if (cd->roomInFinalPack(nestedOffset) < ifCarryDataBits) {
[4715]120                    nestedOffset = alignCeiling(nestedOffset, mPACK_SIZE);
[4714]121                }
122            }
[4689]123            nestedBlockData->setFramePosition(nestedOffset);
124
[4687]125            nestedOffset += ifCarryDataBits;
126            if (cd->maxNestingDepth <= nestedBlockData->maxNestingDepth) cd->maxNestingDepth = nestedBlockData->maxNestingDepth + 1;
127            cd->nested.entries++;
[4696]128#ifndef NDEBUG
129            nestedBlockData->dumpCarryData(cerr);
130#endif
[4687]131        }
132        else if (While * whileStatement = dyn_cast<While>(stmt)) {
[4689]133            const unsigned whileCarryDataBits = enumerate(&whileStatement->getBody(), ifDepth, whileDepth+1);
[4687]134            PabloBlockCarryData * nestedBlockData = mCarryInfoVector[whileStatement->getBody().getScopeIndex()];
135            //if (whileStatement->isMultiCarry()) whileCarryDataBits *= whileStatement->getMaxIterations();
[4715]136            if (mITEMS_PER_PACK == mPACK_SIZE) {  // PACKING
[4714]137                if (cd->roomInFinalPack(nestedOffset) < whileCarryDataBits) {
[4715]138                    nestedOffset = alignCeiling(nestedOffset, mPACK_SIZE);
[4714]139                }
140            }
[4689]141            nestedBlockData->setFramePosition(nestedOffset);
[4687]142            nestedOffset += whileCarryDataBits;
143            if (cd->maxNestingDepth <= nestedBlockData->maxNestingDepth) cd->maxNestingDepth = nestedBlockData->maxNestingDepth + 1;
144            cd->nested.entries++;
[4696]145#ifndef NDEBUG
146            nestedBlockData->dumpCarryData(cerr);
147#endif
[4687]148        }
149    }
150   
[4704]151    cd->scopeCarryDataSize = nestedOffset;
[4687]152   
153    if (cd->explicitSummaryRequired()) {
154        // Need extra space for the summary variable, always the last
155        // entry within an if block.
[4715]156        if (mITEMS_PER_PACK == mPACK_SIZE) {  // PACKING
157            cd->scopeCarryDataSize = alignCeiling(cd->scopeCarryDataSize, mPACK_SIZE);
[4714]158        }
[4704]159        cd->summary.frameOffset = cd->scopeCarryDataSize;
[4715]160        cd->scopeCarryDataSize += mITEMS_PER_PACK;  //  computed summary is a full pack.
[4687]161    }
162    else {
[4704]163        cd->summary.frameOffset = 0;
[4687]164    }
[4713]165#ifndef NDEBUG
166    if (cd->ifDepth == 0) cd->dumpCarryData(cerr);
167#endif
[4704]168    return cd->scopeCarryDataSize;
[4687]169}
170
171
[4670]172/* Entering and leaving blocks. */
[4644]173
[4670]174void CarryManager::enterScope(PabloBlock * blk) {
175   
176    mCurrentScope = blk;
[4687]177    mCarryInfo = mCarryInfoVector[blk->getScopeIndex()];
[4691]178    mCurrentFrameIndex += mCarryInfo->getFrameIndex();
[4704]179    //std::cerr << "enterScope:  blk->getScopeIndex() = " << blk->getScopeIndex() << ", mCurrentFrameIndex = " << mCurrentFrameIndex << std::endl;
[4670]180}
181
182void CarryManager::leaveScope() {
[4691]183    mCurrentFrameIndex -= mCarryInfo->getFrameIndex();
[4703]184    if (mCurrentScope != mPabloRoot) {
185        mCurrentScope = mCurrentScope->getParent();
186        mCarryInfo = mCarryInfoVector[mCurrentScope->getScopeIndex()];
187    }
[4691]188    //std::cerr << "leaveScope:  mCurrentFrameIndex = " << mCurrentFrameIndex << std::endl;
[4670]189}
190
[4694]191
192/* Helper routines */
193
[4704]194unsigned CarryManager::absPosition(unsigned frameOffset, unsigned relPos) {
195    return mCurrentFrameIndex + frameOffset + relPos;
[4697]196}
[4694]197
[4697]198
199unsigned CarryManager::carryOpPosition(unsigned localIndex) {
[4704]200    //std::cerr << "carryOpPosition: addWithCarry.frameOffset = " << mCarryInfo->addWithCarry.frameOffset << ", localIndex = " <<localIndex << std::endl;
201    return absPosition(mCarryInfo->addWithCarry.frameOffset, localIndex);
[4697]202}
203
204unsigned CarryManager::advance1Position(unsigned localIndex) {
[4704]205    //std::cerr << "unsigned CarryManager::advance1Position: advance1.frameOffset = " << mCarryInfo->advance1.frameOffset << ", localIndex = " <<localIndex << std::endl;
206    return absPosition(mCarryInfo->advance1.frameOffset, localIndex);
[4697]207}
208
209unsigned CarryManager::shortAdvancePosition(unsigned localIndex) {
[4704]210    return absPosition(mCarryInfo->shortAdvance.frameOffset, localIndex);
[4697]211}
212
[4698]213unsigned CarryManager::longAdvanceBitBlockPosition(unsigned localIndex) {
[4715]214    return (mCurrentFrameIndex + mCarryInfo->longAdvance.frameOffset) / mITEMS_PER_PACK + localIndex;
[4697]215}
[4700]216   
217unsigned CarryManager::localBasePack() {
[4715]218    return (mCurrentFrameIndex + mCarryInfo->shortAdvance.frameOffset) / mITEMS_PER_PACK;
[4700]219}
220   
221unsigned CarryManager::scopeBasePack() {
[4715]222    return mCurrentFrameIndex / mITEMS_PER_PACK;
[4700]223}
224   
[4697]225
[4700]226
[4697]227unsigned CarryManager::summaryPosition() {
[4704]228    return absPosition(mCarryInfo->summary.frameOffset, 0);
[4697]229}
230
[4710]231
232unsigned CarryManager::summaryPackIndex() {
[4715]233    return summaryPosition()/mITEMS_PER_PACK;
[4710]234}
235
[4697]236unsigned CarryManager::summaryBits() {
[4715]237    if (mCarryInfo->scopeCarryDataSize > mITEMS_PER_PACK) return mPACK_SIZE;
[4704]238    else return mCarryInfo->scopeCarryDataSize;
[4697]239}
240
241
242
[4694]243Value * CarryManager::getCarryPack(unsigned packIndex) {
244    if (mCarryInPack[packIndex] == nullptr) {
[4698]245        Value * packPtr = mBuilder->CreateGEP(mCarryPackBasePtr, mBuilder->getInt64(packIndex));
[4710]246        // Save the computed pointer - so that it can be used in storeCarryPack.
[4694]247        mCarryPackPtr[packIndex] = packPtr;
[4715]248        mCarryInPack[packIndex] = mBuilder->CreateAlignedLoad(packPtr, mPACK_SIZE/8);
[4694]249    }
250    return mCarryInPack[packIndex];
251}
252
[4696]253void CarryManager::storeCarryPack(unsigned packIndex) {
[4715]254    mBuilder->CreateAlignedStore(mCarryOutPack[packIndex], mCarryPackPtr[packIndex], mPACK_SIZE/8);
[4694]255}
256
[4708]257   
[4707]258/* maskSelectBitRange selects the bits of a pack from lo_bit through
[4708]259   lo_bit + bitCount - 1, setting all other bits to zero.  */
260   
[4707]261Value * CarryManager::maskSelectBitRange(Value * pack, unsigned lo_bit, unsigned bitCount) {
[4715]262    if (bitCount == mPACK_SIZE) {
[4707]263        assert(lo_bit == 0);
264        return pack;
[4694]265    }
[4709]266    uint64_t mask = ((((uint64_t) 1) << bitCount) - 1) << lo_bit;
267    return mBuilder->CreateAnd(pack, mBuilder->getInt64(mask));
[4694]268}
[4708]269   
[4707]270Value * CarryManager::getCarryInBits(unsigned carryBitPos, unsigned carryBitCount) {
[4715]271    unsigned packIndex = carryBitPos / mPACK_SIZE;
272    unsigned packOffset = carryBitPos % mPACK_SIZE;
[4707]273    Value * selected = maskSelectBitRange(getCarryPack(packIndex), packOffset, carryBitCount);
274    if (packOffset == 0) return selected;
275    return mBuilder->CreateLShr(selected, packOffset);
[4704]276}
277
[4707]278void CarryManager::extractAndSaveCarryOutBits(Value * bitblock, unsigned carryBit_pos, unsigned carryBitCount) {
[4715]279    unsigned packIndex = carryBit_pos / mPACK_SIZE;
280    unsigned packOffset = carryBit_pos % mPACK_SIZE;
281    unsigned rshift = mPACK_SIZE - packOffset - carryBitCount;
[4709]282    uint64_t mask = ((((uint64_t) 1) << carryBitCount) - 1)  << packOffset;
283    //std::cerr << "extractAndSaveCarryOutBits: packIndex =" << packIndex << ", packOffset = " << packOffset << ", mask = " << mask << std::endl;
[4715]284    Value * field = iBuilder->mvmd_extract(mPACK_SIZE, bitblock, BLOCK_SIZE/mPACK_SIZE - 1);
[4707]285    //Value * field = maskSelectBitRange(field, PACK_SIZE - carryBitCount, carryBitCount);
286    if (rshift != 0) {
287        field = mBuilder->CreateLShr(field, mBuilder->getInt64(rshift));
288    }
289    if (packOffset != 0) {
[4709]290        field = mBuilder->CreateAnd(field, mBuilder->getInt64(mask));
[4707]291    }
292    if (mCarryOutPack[packIndex] == nullptr) {
293        mCarryOutPack[packIndex] = field;
294    }
295    else {
296        mCarryOutPack[packIndex] = mBuilder->CreateOr(mCarryOutPack[packIndex], field);
297    }
[4694]298}
[4704]299
[4707]300Value * CarryManager::pack2bitblock(Value * pack) {
301    return mBuilder->CreateBitCast(mBuilder->CreateZExt(pack, mBuilder->getIntNTy(BLOCK_SIZE)), mBitBlockType);
302}
303   
[4696]304   
305/* Methods for getting and setting individual carry values. */
306   
[4670]307Value * CarryManager::getCarryOpCarryIn(int localIndex) {
[4697]308    unsigned posn = carryOpPosition(localIndex);
[4715]309    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
310        return pack2bitblock(getCarryInBits(posn, 1));
311    }
312    else {
313        return getCarryPack(posn);
314    }
[4644]315}
[4705]316
[4696]317   
[4703]318void CarryManager::setCarryOpCarryOut(unsigned localIndex, Value * carry_out_strm) {
[4697]319    unsigned posn = carryOpPosition(localIndex);
[4715]320    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
321        extractAndSaveCarryOutBits(carry_out_strm, posn, 1);
[4647]322    }
[4715]323    else {
324        Value * carry_bit = mBuilder->CreateLShr(mBuilder->CreateBitCast(carry_out_strm, mBuilder->getIntNTy(BLOCK_SIZE)), 127);
325        mCarryOutPack[posn] = mBuilder->CreateBitCast(carry_bit, mBitBlockType);
326        if (mCarryInfo->getWhileDepth() == 0) {
327            storeCarryPack(posn);
328        }
329    }
[4644]330}
331
[4708]332Value* CarryManager::genShiftLeft64(Value* e) {
333    Value* i128_val = mBuilder->CreateBitCast(e, mBuilder->getIntNTy(BLOCK_SIZE));
334    return mBuilder->CreateBitCast(mBuilder->CreateShl(i128_val, 64), mBitBlockType);
335}
336
337Value * CarryManager::addCarryInCarryOut(int localIndex, Value* e1, Value* e2) {
338    Value * carryq_value = getCarryOpCarryIn(localIndex);
339    #if (BLOCK_SIZE == 128)
340    //calculate carry through logical ops
341    Value* carrygen = mBuilder->CreateAnd(e1, e2, "carrygen");
342    Value* carryprop = mBuilder->CreateOr(e1, e2, "carryprop");
343    Value* digitsum = mBuilder->CreateAdd(e1, e2, "digitsum");
344    Value* partial = mBuilder->CreateAdd(digitsum, carryq_value, "partial");
345    Value* digitcarry = mBuilder->CreateOr(carrygen, mBuilder->CreateAnd(carryprop, mBuilder->CreateNot(partial)));
346    Value* mid_carry_in = genShiftLeft64(mBuilder->CreateLShr(digitcarry, 63));
347    Value* sum = mBuilder->CreateAdd(partial, mBuilder->CreateBitCast(mid_carry_in, mBitBlockType), "sum");
348    Value* carry_out_strm = mBuilder->CreateOr(carrygen, mBuilder->CreateAnd(carryprop, mBuilder->CreateNot(sum)));
349
350    #else
351    //BLOCK_SIZE == 256, there is no other implementation
352    static_assert(false, "Add with carry for 256-bit bitblock requires USE_UADD_OVERFLOW");
353    #endif         
354    setCarryOpCarryOut(localIndex, carry_out_strm);
355    return sum;
356}
357
358
[4670]359Value * CarryManager::advanceCarryInCarryOut(int localIndex, int shift_amount, Value * strm) {
[4654]360    if (shift_amount == 1) {
[4670]361        return unitAdvanceCarryInCarryOut(localIndex, strm);
[4647]362    }
[4654]363    else if (shift_amount < LongAdvanceBase) {
[4670]364        return shortAdvanceCarryInCarryOut(localIndex, shift_amount, strm);
[4654]365    }
366    else {
[4670]367        return longAdvanceCarryInCarryOut(localIndex, shift_amount, strm);
[4654]368    }
[4644]369}
370
[4670]371Value * CarryManager::unitAdvanceCarryInCarryOut(int localIndex, Value * strm) {
[4697]372    unsigned posn = advance1Position(localIndex);
[4715]373    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
374        extractAndSaveCarryOutBits(strm, posn, 1);
375        Value* carry_longint = mBuilder->CreateZExt(getCarryInBits(posn, 1), mBuilder->getIntNTy(BLOCK_SIZE));
376        Value* strm_longint = mBuilder->CreateBitCast(strm, mBuilder->getIntNTy(BLOCK_SIZE));
377        Value* adv_longint = mBuilder->CreateOr(mBuilder->CreateShl(strm_longint, 1), carry_longint);
378        Value* result_value = mBuilder->CreateBitCast(adv_longint, mBitBlockType);
379        return result_value;
380    }
381    mCarryOutPack[posn] = strm;
[4697]382    Value * carry_in = getCarryPack(posn);
[4670]383    if (mCarryInfo->getWhileDepth() == 0) {
[4697]384        storeCarryPack(posn);
[4647]385    }
[4654]386    Value* result_value;
387   
388#if (BLOCK_SIZE == 128) && !defined(USE_LONG_INTEGER_SHIFT)
[4663]389    Value * ahead64 = iBuilder->mvmd_dslli(64, carry_in, strm, 1);
390    result_value = mBuilder->CreateOr(iBuilder->simd_srli(64, ahead64, 63), iBuilder->simd_slli(64, strm, 1));
[4654]391#else
392    Value* advanceq_longint = mBuilder->CreateBitCast(carry_in, mBuilder->getIntNTy(BLOCK_SIZE));
393    Value* strm_longint = mBuilder->CreateBitCast(strm, mBuilder->getIntNTy(BLOCK_SIZE));
394    Value* adv_longint = mBuilder->CreateOr(mBuilder->CreateShl(strm_longint, 1), mBuilder->CreateLShr(advanceq_longint, BLOCK_SIZE - 1), "advance");
395    result_value = mBuilder->CreateBitCast(adv_longint, mBitBlockType);
396   
397#endif
398    return result_value;
[4644]399}
400
[4670]401Value * CarryManager::shortAdvanceCarryInCarryOut(int localIndex, int shift_amount, Value * strm) {
[4697]402    unsigned posn = shortAdvancePosition(localIndex);
[4715]403    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
404        extractAndSaveCarryOutBits(strm, posn, shift_amount);
405        //std::cerr << "shortAdvanceCarryInCarryOut: posn = " << posn << ", shift_amount = " << shift_amount << std::endl;
406        Value* carry_longint = mBuilder->CreateZExt(getCarryInBits(posn, shift_amount), mBuilder->getIntNTy(BLOCK_SIZE));
407        Value* strm_longint = mBuilder->CreateBitCast(strm, mBuilder->getIntNTy(BLOCK_SIZE));
408        Value* adv_longint = mBuilder->CreateOr(mBuilder->CreateShl(strm_longint, shift_amount), carry_longint);
409        Value* result_value = mBuilder->CreateBitCast(adv_longint, mBitBlockType);
410        return result_value;
411    }
412    mCarryOutPack[posn] = strm;
[4697]413    Value * carry_in = getCarryPack(posn);
[4670]414    if (mCarryInfo->getWhileDepth() == 0) {
[4697]415        storeCarryPack(posn);
[4647]416    }
[4654]417    Value* advanceq_longint = mBuilder->CreateBitCast(carry_in, mBuilder->getIntNTy(BLOCK_SIZE));
418    Value* strm_longint = mBuilder->CreateBitCast(strm, mBuilder->getIntNTy(BLOCK_SIZE));
419    Value* adv_longint = mBuilder->CreateOr(mBuilder->CreateShl(strm_longint, shift_amount), mBuilder->CreateLShr(advanceq_longint, BLOCK_SIZE - shift_amount), "advance");
420    return mBuilder->CreateBitCast(adv_longint, mBitBlockType);
[4644]421}
[4654]422   
[4647]423
[4654]424/*  currently defined in carry_data.h
425 
[4647]426 static unsigned power2ceil (unsigned v) {
427 unsigned ceil = 1;
428 while (ceil < v) ceil *= 2;
429 return ceil;
430 }
431 
432 unsigned longAdvanceEntries(unsigned shift_amount) const {
433 return (shift_amount + BLOCK_SIZE - 1)/BLOCK_SIZE;
434 }
435 
436 unsigned longAdvanceBufferSize(unsigned shift_amount)  const {
437 return power2ceil(longAdvanceEntries(shift_amount));
438 }
439 */
[4644]440
[4654]441   
[4670]442Value * CarryManager::longAdvanceCarryInCarryOut(int localIndex, int shift_amount, Value * carry_out) {
[4698]443    unsigned carryDataIndex = longAdvanceBitBlockPosition(localIndex);
[4670]444    Value * advBaseIndex = mBuilder->getInt64(carryDataIndex);
[4647]445    if (shift_amount <= BLOCK_SIZE) {
446        // special case using a single buffer entry and the carry_out value.
[4698]447        Value * advanceDataPtr = mBuilder->CreateGEP(mCarryBitBlockPtr, advBaseIndex);
[4647]448        Value * carry_block0 = mBuilder->CreateAlignedLoad(advanceDataPtr, BLOCK_SIZE/8);
449        mBuilder->CreateAlignedStore(carry_out, advanceDataPtr, BLOCK_SIZE/8);
450        /* Very special case - no combine */
451        if (shift_amount == BLOCK_SIZE) return carry_block0;
452        Value* block0_shr = mBuilder->CreateLShr(mBuilder->CreateBitCast(carry_block0, mBuilder->getIntNTy(BLOCK_SIZE)), BLOCK_SIZE - shift_amount);
453        Value* block1_shl = mBuilder->CreateShl(mBuilder->CreateBitCast(carry_out, mBuilder->getIntNTy(BLOCK_SIZE)), shift_amount);
454        return mBuilder->CreateBitCast(mBuilder->CreateOr(block1_shl, block0_shr), mBitBlockType);
455    }
456    // We need a buffer of at least two elements for storing the advance data.
[4644]457    const unsigned block_shift = shift_amount % BLOCK_SIZE;
[4670]458    const unsigned advanceEntries = mCarryInfo->longAdvanceEntries(shift_amount);
459    const unsigned bufsize = mCarryInfo->longAdvanceBufferSize(shift_amount);
[4644]460    Value * indexMask = mBuilder->getInt64(bufsize - 1);  // A mask to implement circular buffer indexing
461    Value * loadIndex0 = mBuilder->CreateAdd(mBuilder->CreateAnd(mBuilder->CreateSub(mBlockNo, mBuilder->getInt64(advanceEntries)), indexMask), advBaseIndex);
[4647]462    Value * storeIndex = mBuilder->CreateAdd(mBuilder->CreateAnd(mBlockNo, indexMask), advBaseIndex);
[4698]463    Value * carry_block0 = mBuilder->CreateAlignedLoad(mBuilder->CreateGEP(mCarryBitBlockPtr, loadIndex0), BLOCK_SIZE/8);
[4644]464    // If the long advance is an exact multiple of BLOCK_SIZE, we simply return the oldest
[4647]465    // block in the long advance carry data area. 
466    if (block_shift == 0) {
[4698]467        mBuilder->CreateAlignedStore(carry_out, mBuilder->CreateGEP(mCarryBitBlockPtr, storeIndex), BLOCK_SIZE/8);
[4647]468        return carry_block0;
[4644]469    }
470    // Otherwise we need to combine data from the two oldest blocks.
471    Value * loadIndex1 = mBuilder->CreateAdd(mBuilder->CreateAnd(mBuilder->CreateSub(mBlockNo, mBuilder->getInt64(advanceEntries-1)), indexMask), advBaseIndex);
[4698]472    Value * carry_block1 = mBuilder->CreateAlignedLoad(mBuilder->CreateGEP(mCarryBitBlockPtr, loadIndex1), BLOCK_SIZE/8);
[4647]473    Value* block0_shr = mBuilder->CreateLShr(mBuilder->CreateBitCast(carry_block0, mBuilder->getIntNTy(BLOCK_SIZE)), BLOCK_SIZE - block_shift);
[4644]474    Value* block1_shl = mBuilder->CreateShl(mBuilder->CreateBitCast(carry_block1, mBuilder->getIntNTy(BLOCK_SIZE)), block_shift);
[4698]475    mBuilder->CreateAlignedStore(carry_out, mBuilder->CreateGEP(mCarryBitBlockPtr, storeIndex), BLOCK_SIZE/8);
[4644]476    return mBuilder->CreateBitCast(mBuilder->CreateOr(block1_shl, block0_shr), mBitBlockType);
477}
[4647]478   
[4644]479
480/* Methods for getting and setting carry summary values */
481   
[4670]482bool CarryManager::blockHasCarries(){
483    return mCarryInfo->blockHasCarries();
[4644]484} 
485
[4670]486
487Value * CarryManager::getCarrySummaryExpr() {
[4710]488    unsigned summary_index = summaryPackIndex();
[4715]489    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
490        Value * pack = getCarryPack(summary_index);
491        Value * summary_bits = maskSelectBitRange(pack, summaryPosition() % mPACK_SIZE, summaryBits());
492        return mBuilder->CreateBitCast(mBuilder->CreateZExt(summary_bits, mBuilder->getIntNTy(BLOCK_SIZE)), mBitBlockType);
493    }
494    else {
495        return getCarryPack(summary_index);
496    }
[4644]497}
498
[4704]499void CarryManager::initializeCarryDataAtIfEntry() {
[4721]500    if (blockHasCarries()) {
501        if (mCarryOutPack[scopeBasePack()] == nullptr) {
502            mCarryInfo->ifEntryPack = mZeroInitializer;
503        }
504        else {
505            mCarryInfo->ifEntryPack = mCarryOutPack[scopeBasePack()];
506        }
[4703]507    }
[4704]508}
[4703]509   
[4704]510void CarryManager::buildCarryDataPhisAfterIfBody(BasicBlock * ifEntryBlock, BasicBlock * ifBodyFinalBlock) {
511    unsigned const ifScopeCarrySize = mCarryInfo->scopeCarryDataSize;
512    if (ifScopeCarrySize == 0) {
513        // No carry data, therefore no phi nodes.
514        return;
[4703]515    }
[4715]516    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
517        if (ifScopeCarrySize <= mPACK_SIZE) {
518            unsigned const ifPackIndex = scopeBasePack();
519            PHINode * ifPack_phi = mBuilder->CreatePHI(mCarryPackType, 2, "ifPack");
520            ifPack_phi->addIncoming(mCarryInfo->ifEntryPack, ifEntryBlock);
521            ifPack_phi->addIncoming(mCarryOutPack[ifPackIndex], ifBodyFinalBlock);
522            mCarryOutPack[ifPackIndex] = ifPack_phi;
523            return;
524        }
[4704]525    }
[4706]526    if (mCarryInfo->getIfDepth() > 1) {
[4710]527        const unsigned summaryIndex = summaryPackIndex();
[4704]528        PHINode * summary_phi = mBuilder->CreatePHI(mCarryPackType, 2, "summary");
529        summary_phi->addIncoming(mZeroInitializer, ifEntryBlock);
[4710]530        summary_phi->addIncoming(mCarryOutPack[summaryIndex], ifBodyFinalBlock);
531        mCarryOutPack[summaryIndex] = summary_phi;
[4704]532    }
533}
[4703]534   
[4676]535void CarryManager::addSummaryPhiIfNeeded(BasicBlock * ifEntryBlock, BasicBlock * ifBodyFinalBlock) {
536    if ((mCarryInfo->getIfDepth() <= 1) || !mCarryInfo->blockHasCarries()){
537        // For ifDepth == 1, the parent does not need a summary as it is not itself within an if.
538        // Therefore, it doesn't need access to this block's summary in building its own.
539        return;
540    }
[4710]541    const unsigned carrySummaryIndex = summaryPackIndex();
[4700]542    PHINode * summary_phi = mBuilder->CreatePHI(mCarryPackType, 2, "summary");
[4644]543    summary_phi->addIncoming(mZeroInitializer, ifEntryBlock);
[4696]544    summary_phi->addIncoming(mCarryOutPack[carrySummaryIndex], ifBodyFinalBlock);
545    mCarryOutPack[carrySummaryIndex] = summary_phi;
[4644]546}
[4703]547   
[4676]548void CarryManager::generateCarryOutSummaryCodeIfNeeded() {
[4644]549   
[4676]550    if (!mCarryInfo->explicitSummaryRequired()) {
551        // An explicit summary may not be required, if there is a single carry
552        // operation within the block, or the carries are packed and all carry
553        // bits fit within a single pack.
[4644]554        return;
555    }
556   
[4710]557    const unsigned carrySummaryIndex = summaryPackIndex();
[4676]558   
[4644]559    Value * carry_summary = mZeroInitializer;
[4670]560    if (mCarryInfo->blockHasLongAdvances()) { // Force if entry
[4644]561        carry_summary = mOneInitializer;
562    }
563    else {
[4700]564        auto localCarryIndex = localBasePack();
[4696]565        auto localCarryPacks = mCarryInfo->getLocalCarryPackCount();
[4644]566        if (localCarryPacks > 0) {
[4696]567            carry_summary = mCarryOutPack[localCarryIndex];
[4644]568            for (auto i = 1; i < localCarryPacks; i++) {
569                //carry_summary = mBuilder->CreateOr(carry_summary, mPabloBlock->mCarryOutPack[i]);           
[4696]570                carry_summary = mBuilder->CreateOr(carry_summary, mCarryOutPack[localCarryIndex+i]);
[4644]571            }
[4647]572        }
[4670]573        for (Statement * stmt : *mCurrentScope) {
[4644]574            if (If * innerIf = dyn_cast<If>(stmt)) {
[4670]575                PabloBlock * inner_blk = & innerIf->getBody();
576                enterScope(inner_blk);
577                if (blockHasCarries()) {
[4710]578                  carry_summary = mBuilder->CreateOr(carry_summary, mCarryOutPack[summaryPackIndex()]);
[4644]579                }
[4670]580                leaveScope();
[4644]581            }
582            else if (While * innerWhile = dyn_cast<While>(stmt)) {
[4670]583                PabloBlock * inner_blk = & innerWhile->getBody();
584                enterScope(inner_blk);
585                if (blockHasCarries()) {
[4710]586                    carry_summary = mBuilder->CreateOr(carry_summary, mCarryOutPack[summaryPackIndex()]);
[4670]587                }
588                leaveScope();
[4644]589            }
590        }
591    }
592    // Calculation of the carry out summary is complete.   Store it and make it
593    // available in case it must included by parent blocks.
[4696]594    mCarryOutPack[carrySummaryIndex] = carry_summary;
595    storeCarryPack(carrySummaryIndex);
[4644]596}
597
[4670]598void CarryManager::ensureCarriesLoadedRecursive() {
[4696]599    const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
[4700]600    const unsigned currentScopeBase = scopeBasePack();
[4670]601    if (mCarryInfo->getWhileDepth() == 1) {
[4700]602        for (auto i = currentScopeBase; i < currentScopeBase + scopeCarryPacks; ++i) {
[4694]603            getCarryPack(i);
[4644]604        }
605    }
606}
607
608
[4670]609void CarryManager::initializeCarryDataPhisAtWhileEntry(BasicBlock * whileEntryBlock) {
[4696]610    const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
611    mCarryOutAccumPhis.resize(scopeCarryPacks);
[4644]612#ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
[4700]613    const unsigned currentScopeBase = scopeBasePack();
[4696]614    mCarryInPhis.resize(scopeCarryPacks);
615#endif
616    for (unsigned index = 0; index < scopeCarryPacks; ++index) {
617#ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
[4700]618        PHINode * phi_in = mBuilder->CreatePHI(mCarryPackType, 2);
619        phi_in->addIncoming(mCarryInPack[currentScopeBase+index], whileEntryBlock);
[4644]620        mCarryInPhis[index] = phi_in;
621#endif
[4700]622        PHINode * phi_out = mBuilder->CreatePHI(mCarryPackType, 2);
[4644]623        phi_out->addIncoming(mZeroInitializer, whileEntryBlock);
624        mCarryOutAccumPhis[index] = phi_out;
625    }
626}
627
628
[4670]629void CarryManager::extendCarryDataPhisAtWhileBodyFinalBlock(BasicBlock * whileBodyFinalBlock) {
[4696]630    const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
[4700]631    const unsigned currentScopeBase = scopeBasePack();
[4696]632    for (unsigned index = 0; index < scopeCarryPacks; ++index) {
[4644]633#ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
634        mCarryInPhis[index]->addIncoming(mZeroInitializer, whileBodyFinalBlock);
635#endif
636        PHINode * phi = mCarryOutAccumPhis[index];
[4700]637        Value * carryOut = mBuilder->CreateOr(phi, mCarryOutPack[currentScopeBase+index]);
[4644]638        phi->addIncoming(carryOut, whileBodyFinalBlock);
[4700]639        mCarryOutPack[currentScopeBase+index] = carryOut;
[4644]640    }
641}
642
[4670]643void CarryManager::ensureCarriesStoredRecursive() {
[4696]644    const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
[4700]645    const unsigned currentScopeBase = scopeBasePack();
[4670]646    if (mCarryInfo->getWhileDepth() == 1) {
[4700]647        for (auto i = currentScopeBase; i < currentScopeBase + scopeCarryPacks; ++i) {
[4696]648            storeCarryPack(i);
[4644]649        }
650    }
651}
652
[4713]653/* Store all the full carry packs generated locally in this scope or the
654   single full pack for this scope*/
[4710]655void CarryManager::ensureCarriesStoredLocal() {
[4715]656    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
657        const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
658        if ((scopeCarryPacks > 0) && ((mCurrentFrameIndex % mPACK_SIZE) == 0)) {
659            // We have carry data and we are not in the middle of a pack.
660            // Write out all local packs.
661            auto localCarryIndex = localBasePack();
662            auto localCarryPacks = mCarryInfo->getLocalCarryPackCount();
663            for (auto i = localCarryIndex; i < localCarryIndex + localCarryPacks; i++) {
664                storeCarryPack(i);
665            }
666            if ((localCarryPacks == 0) && (scopeCarryPacks == 1) && (mCarryInfo->nested.entries > 1)) {
667                storeCarryPack(localCarryIndex);
668            }
[4710]669        }
670    }
[4644]671}
672
[4720]673Value * CarryManager::popCount(Value * to_count, unsigned globalIdx) {
674    Value * countPtr = mBuilder->CreateGEP(mPopcountBasePtr, mBuilder->getInt64(globalIdx));
675    Value * countSoFar = mBuilder->CreateAlignedLoad(countPtr, 8);
676    Value * fieldCounts = iBuilder->simd_popcount(64, to_count);
677    for (int i = 0; i < BLOCK_SIZE/64; i++) {
678        countSoFar = mBuilder->CreateAdd(countSoFar, iBuilder->mvmd_extract(64, fieldCounts, i));
679    }
680    mBuilder->CreateAlignedStore(countSoFar, countPtr, 8);
681    return mBuilder->CreateBitCast(mBuilder->CreateZExt(countSoFar, mBuilder->getIntNTy(BLOCK_SIZE)), mBitBlockType);
682}
683   
[4712]684CarryManager::~CarryManager() {
685    for (auto * cd : mCarryInfoVector) {
686        delete cd;
687    }
[4710]688}
689
[4712]690}
691
Note: See TracBrowser for help on using the repository browser.