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

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

Carry manager with bit packing now passes make check; cleanup

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