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

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

Dynamic selection of carry strategy options

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