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

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

Embed carry data in compiled LLVM module; eliminate passing of carry data pointers/size

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