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

Last change on this file since 4712 was 4712, checked in by nmedfort, 4 years ago

Memory leak fix.

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