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

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

Fix to generate summary-phi nodes only when ifDepth > 1.

File size: 25.7 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#ifdef PACKING
163    if ((mCurrentFrameIndex % PACK_SIZE) == 0) {
164        // Write out all local packs.
165        auto localCarryIndex = localBasePack();
166        auto localCarryPacks = mCarryInfo->getLocalCarryPackCount();
167        for (auto i = localCarryIndex; i < localCarryIndex + localCarryPacks; i++) {
168            storeCarryPack(i);
169        }
170    }
171#endif
172    mCurrentFrameIndex -= mCarryInfo->getFrameIndex();
173    if (mCurrentScope != mPabloRoot) {
174        mCurrentScope = mCurrentScope->getParent();
175        mCarryInfo = mCarryInfoVector[mCurrentScope->getScopeIndex()];
176    }
177    //std::cerr << "leaveScope:  mCurrentFrameIndex = " << mCurrentFrameIndex << std::endl;
178}
179
180
181/* Helper routines */
182
183unsigned CarryManager::absPosition(unsigned frameOffset, unsigned relPos) {
184    return mCurrentFrameIndex + frameOffset + relPos;
185}
186
187
188unsigned CarryManager::carryOpPosition(unsigned localIndex) {
189    //std::cerr << "carryOpPosition: addWithCarry.frameOffset = " << mCarryInfo->addWithCarry.frameOffset << ", localIndex = " <<localIndex << std::endl;
190    return absPosition(mCarryInfo->addWithCarry.frameOffset, localIndex);
191}
192
193unsigned CarryManager::advance1Position(unsigned localIndex) {
194    //std::cerr << "unsigned CarryManager::advance1Position: advance1.frameOffset = " << mCarryInfo->advance1.frameOffset << ", localIndex = " <<localIndex << std::endl;
195    return absPosition(mCarryInfo->advance1.frameOffset, localIndex);
196}
197
198unsigned CarryManager::shortAdvancePosition(unsigned localIndex) {
199    return absPosition(mCarryInfo->shortAdvance.frameOffset, localIndex);
200}
201
202unsigned CarryManager::longAdvanceBitBlockPosition(unsigned localIndex) {
203#ifdef PACKING
204    return (mCurrentFrameIndex + mCarryInfo->longAdvance.frameOffset) / BLOCK_SIZE + localIndex;
205#else
206    return mCurrentFrameIndex + mCarryInfo->longAdvance.frameOffset + localIndex;
207#endif
208}
209   
210unsigned CarryManager::localBasePack() {
211#ifdef PACKING
212    return (mCurrentFrameIndex + mCarryInfo->shortAdvance.frameOffset) / PACK_SIZE;
213#else
214    return mCurrentFrameIndex + mCarryInfo->shortAdvance.frameOffset;
215#endif
216}
217   
218unsigned CarryManager::scopeBasePack() {
219#ifdef PACKING
220    return mCurrentFrameIndex / PACK_SIZE;
221#else
222    return mCurrentFrameIndex;
223#endif
224}
225   
226
227
228unsigned CarryManager::summaryPosition() {
229    return absPosition(mCarryInfo->summary.frameOffset, 0);
230}
231
232unsigned CarryManager::summaryBits() {
233#ifdef PACKING
234    if (mCarryInfo->scopeCarryDataSize > PACK_SIZE) return PACK_SIZE;
235    else return mCarryInfo->scopeCarryDataSize;
236#else
237    if (mCarryInfo->scopeCarryDataSize > 1) return PACK_SIZE;
238    else return mCarryInfo->scopeCarryDataSize;
239#endif
240}
241
242
243
244Value * CarryManager::getCarryPack(unsigned packIndex) {
245    if (mCarryInPack[packIndex] == nullptr) {
246        Value * packPtr = mBuilder->CreateGEP(mCarryPackBasePtr, mBuilder->getInt64(packIndex));
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    //std::cerr << "storeCarryPack , pack = " << packIndex << std::endl;
255    mBuilder->CreateAlignedStore(mCarryOutPack[packIndex], mCarryPackPtr[packIndex], PACK_SIZE/8);
256}
257
258Value * CarryManager::getCarryRange(unsigned carryBit_lo, unsigned carryRangeSize) {
259
260    unsigned packIndex = carryBit_lo / PACK_SIZE;
261    unsigned carryOffset = carryBit_lo % PACK_SIZE;
262   
263    Value * carryItem = getCarryPack(packIndex);
264    if (carryRangeSize == PACK_SIZE) {
265        assert(carryOffset == 0);
266        return carryItem;
267    }
268    unsigned mask = (1 << carryRangeSize) - 1;
269    return mBuilder->CreateAnd(carryItem, mBuilder->getInt64(mask << carryOffset));
270}
271   
272Value * CarryManager::getCarryBits(unsigned carryBitPos, unsigned carryBitCount) {
273   
274    unsigned carryOffset = carryBitPos % PACK_SIZE;
275
276    Value * carryRange = getCarryRange(carryBitPos, carryBitCount);
277    if (carryOffset == 0) return carryRange;
278    return mBuilder->CreateLShr(carryRange, carryOffset);
279}
280
281Value * CarryManager::getCarryBit(unsigned carryBitPos) {
282    return getCarryBits(carryBitPos, 1);
283}
284
285/*  NOTE: In the following the mCarryOutPack is an accumulator.
286    It must be created at the appropriate outer level.  */
287void CarryManager::setCarryBits(unsigned carryBit_lo, unsigned carryRangeSize, Value * bits) {
288   
289    unsigned packIndex = carryBit_lo / PACK_SIZE;
290    unsigned carryOffset = carryBit_lo % PACK_SIZE;
291    if (carryOffset > 0) {
292        bits = mBuilder->CreateShl(bits, mBuilder->getInt64(carryOffset));
293    }
294    if (mCarryOutPack[packIndex] == nullptr) {
295        mCarryOutPack[packIndex] = bits;
296        //std::cerr << "setCarryBits/initial , pack = " << packIndex << ", offset = " << carryOffset << ", count = " << carryRangeSize << std::endl;
297    }
298    else {
299        //std::cerr << "setCarryBits/combine , pack = " << packIndex << ", offset = " << carryOffset << ", count = " << carryRangeSize << std::endl;
300        mCarryOutPack[packIndex] = mBuilder->CreateOr(mCarryOutPack[packIndex], bits);
301    }
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  mBuilder->CreateBitCast(mBuilder->CreateZExt(getCarryBit(posn), mBuilder->getIntNTy(BLOCK_SIZE)), mBitBlockType);
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    Value * field = iBuilder->mvmd_extract(PACK_SIZE, carry_out_strm, 0);
321    //setCarryBits(posn, mBuilder->CreateLShr(field, mBuilder->getInt64(PACK_SIZE - 1)));
322    setCarryBits(posn, 1, field);
323#else
324    mCarryOutPack[posn] = carry_out_strm;
325    if (mCarryInfo->getWhileDepth() == 0) {
326        storeCarryPack(posn);
327    }
328#endif
329}
330
331   
332Value * CarryManager::advanceCarryInCarryOut(int localIndex, int shift_amount, Value * strm) {
333    if (shift_amount == 1) {
334        return unitAdvanceCarryInCarryOut(localIndex, strm);
335    }
336    else if (shift_amount < LongAdvanceBase) {
337        return shortAdvanceCarryInCarryOut(localIndex, shift_amount, strm);
338    }
339    else {
340        return longAdvanceCarryInCarryOut(localIndex, shift_amount, strm);
341    }
342}
343
344Value * CarryManager::unitAdvanceCarryInCarryOut(int localIndex, Value * strm) {
345    unsigned posn = advance1Position(localIndex);
346#ifdef PACKING
347    unsigned offset = posn % PACK_SIZE;
348    unsigned rshift = PACK_SIZE - offset - 1;
349    Value * field = iBuilder->mvmd_extract(PACK_SIZE, strm, BLOCK_SIZE/PACK_SIZE - 1);
350    if (rshift != 0) {
351        field = mBuilder->CreateLShr(field, mBuilder->getInt64(rshift));
352    }
353    if (offset != 0) {
354        field = mBuilder->CreateAnd(field, mBuilder->getInt64(1<<offset));
355    }
356    setCarryBits(posn - offset, 1, field);
357    Value* carry_longint = mBuilder->CreateZExt(getCarryBit(posn), mBuilder->getIntNTy(BLOCK_SIZE));
358    Value* strm_longint = mBuilder->CreateBitCast(strm, mBuilder->getIntNTy(BLOCK_SIZE));
359    Value* adv_longint = mBuilder->CreateOr(mBuilder->CreateShl(strm_longint, 1), carry_longint);
360    Value* result_value = mBuilder->CreateBitCast(adv_longint, mBitBlockType);
361    return result_value;
362#else
363    mCarryOutPack[posn] = strm; 
364    Value * carry_in = getCarryPack(posn);
365    if (mCarryInfo->getWhileDepth() == 0) {
366        storeCarryPack(posn);
367    }
368    Value* result_value;
369   
370#if (BLOCK_SIZE == 128) && !defined(USE_LONG_INTEGER_SHIFT)
371    Value * ahead64 = iBuilder->mvmd_dslli(64, carry_in, strm, 1);
372    result_value = mBuilder->CreateOr(iBuilder->simd_srli(64, ahead64, 63), iBuilder->simd_slli(64, strm, 1));
373#else
374    Value* advanceq_longint = mBuilder->CreateBitCast(carry_in, mBuilder->getIntNTy(BLOCK_SIZE));
375    Value* strm_longint = mBuilder->CreateBitCast(strm, mBuilder->getIntNTy(BLOCK_SIZE));
376    Value* adv_longint = mBuilder->CreateOr(mBuilder->CreateShl(strm_longint, 1), mBuilder->CreateLShr(advanceq_longint, BLOCK_SIZE - 1), "advance");
377    result_value = mBuilder->CreateBitCast(adv_longint, mBitBlockType);
378   
379#endif
380    return result_value;
381#endif
382}
383
384Value * CarryManager::shortAdvanceCarryInCarryOut(int localIndex, int shift_amount, Value * strm) {
385    unsigned posn = shortAdvancePosition(localIndex);
386#ifdef PACKING
387    unsigned offset = posn % PACK_SIZE;
388    unsigned rshift = PACK_SIZE - offset - shift_amount;
389    Value * field = iBuilder->mvmd_extract(PACK_SIZE, strm, BLOCK_SIZE/PACK_SIZE - 1);
390    if (rshift != 0) {
391        field = mBuilder->CreateLShr(field, mBuilder->getInt64(rshift));
392    }
393    if (offset != 0) {
394        field = mBuilder->CreateAnd(field, mBuilder->getInt64(((1<<shift_amount) - 1) << offset));
395    }   
396    setCarryBits(posn - offset, shift_amount, field);
397    Value* carry_longint = mBuilder->CreateZExt(getCarryBits(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#else
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#endif
413}
414   
415
416/*  currently defined in carry_data.h
417 
418 static unsigned power2ceil (unsigned v) {
419 unsigned ceil = 1;
420 while (ceil < v) ceil *= 2;
421 return ceil;
422 }
423 
424 unsigned longAdvanceEntries(unsigned shift_amount) const {
425 return (shift_amount + BLOCK_SIZE - 1)/BLOCK_SIZE;
426 }
427 
428 unsigned longAdvanceBufferSize(unsigned shift_amount)  const {
429 return power2ceil(longAdvanceEntries(shift_amount));
430 }
431 */
432
433   
434Value * CarryManager::longAdvanceCarryInCarryOut(int localIndex, int shift_amount, Value * carry_out) {
435    unsigned carryDataIndex = longAdvanceBitBlockPosition(localIndex);
436    Value * advBaseIndex = mBuilder->getInt64(carryDataIndex);
437    if (shift_amount <= BLOCK_SIZE) {
438        // special case using a single buffer entry and the carry_out value.
439        Value * advanceDataPtr = mBuilder->CreateGEP(mCarryBitBlockPtr, advBaseIndex);
440        Value * carry_block0 = mBuilder->CreateAlignedLoad(advanceDataPtr, BLOCK_SIZE/8);
441        mBuilder->CreateAlignedStore(carry_out, advanceDataPtr, BLOCK_SIZE/8);
442        /* Very special case - no combine */
443        if (shift_amount == BLOCK_SIZE) return carry_block0;
444        Value* block0_shr = mBuilder->CreateLShr(mBuilder->CreateBitCast(carry_block0, mBuilder->getIntNTy(BLOCK_SIZE)), BLOCK_SIZE - shift_amount);
445        Value* block1_shl = mBuilder->CreateShl(mBuilder->CreateBitCast(carry_out, mBuilder->getIntNTy(BLOCK_SIZE)), shift_amount);
446        return mBuilder->CreateBitCast(mBuilder->CreateOr(block1_shl, block0_shr), mBitBlockType);
447    }
448    // We need a buffer of at least two elements for storing the advance data.
449    const unsigned block_shift = shift_amount % BLOCK_SIZE;
450    const unsigned advanceEntries = mCarryInfo->longAdvanceEntries(shift_amount);
451    const unsigned bufsize = mCarryInfo->longAdvanceBufferSize(shift_amount);
452    Value * indexMask = mBuilder->getInt64(bufsize - 1);  // A mask to implement circular buffer indexing
453    Value * loadIndex0 = mBuilder->CreateAdd(mBuilder->CreateAnd(mBuilder->CreateSub(mBlockNo, mBuilder->getInt64(advanceEntries)), indexMask), advBaseIndex);
454    Value * storeIndex = mBuilder->CreateAdd(mBuilder->CreateAnd(mBlockNo, indexMask), advBaseIndex);
455    Value * carry_block0 = mBuilder->CreateAlignedLoad(mBuilder->CreateGEP(mCarryBitBlockPtr, loadIndex0), BLOCK_SIZE/8);
456    // If the long advance is an exact multiple of BLOCK_SIZE, we simply return the oldest
457    // block in the long advance carry data area. 
458    if (block_shift == 0) {
459        mBuilder->CreateAlignedStore(carry_out, mBuilder->CreateGEP(mCarryBitBlockPtr, storeIndex), BLOCK_SIZE/8);
460        return carry_block0;
461    }
462    // Otherwise we need to combine data from the two oldest blocks.
463    Value * loadIndex1 = mBuilder->CreateAdd(mBuilder->CreateAnd(mBuilder->CreateSub(mBlockNo, mBuilder->getInt64(advanceEntries-1)), indexMask), advBaseIndex);
464    Value * carry_block1 = mBuilder->CreateAlignedLoad(mBuilder->CreateGEP(mCarryBitBlockPtr, loadIndex1), BLOCK_SIZE/8);
465    Value* block0_shr = mBuilder->CreateLShr(mBuilder->CreateBitCast(carry_block0, mBuilder->getIntNTy(BLOCK_SIZE)), BLOCK_SIZE - block_shift);
466    Value* block1_shl = mBuilder->CreateShl(mBuilder->CreateBitCast(carry_block1, mBuilder->getIntNTy(BLOCK_SIZE)), block_shift);
467    mBuilder->CreateAlignedStore(carry_out, mBuilder->CreateGEP(mCarryBitBlockPtr, storeIndex), BLOCK_SIZE/8);
468    return mBuilder->CreateBitCast(mBuilder->CreateOr(block1_shl, block0_shr), mBitBlockType);
469}
470   
471
472/* Methods for getting and setting carry summary values */
473   
474bool CarryManager::blockHasCarries(){
475    return mCarryInfo->blockHasCarries();
476} 
477
478
479Value * CarryManager::getCarrySummaryExpr() {
480    unsigned summary_posn = summaryPosition();
481#ifdef PACKING
482    return mBuilder->CreateBitCast(mBuilder->CreateZExt(getCarryRange(summary_posn, summaryBits()), mBuilder->getIntNTy(BLOCK_SIZE)), mBitBlockType);
483#else
484    return getCarryPack(summary_posn);
485#endif
486}
487
488void CarryManager::initializeCarryDataAtIfEntry() {
489    if (mCarryOutPack[scopeBasePack()] == nullptr) {
490        mCarryInfo->ifEntryPack = mZeroInitializer;
491    }
492    else {
493        mCarryInfo->ifEntryPack = mCarryOutPack[scopeBasePack()];
494    }
495}
496   
497void CarryManager::buildCarryDataPhisAfterIfBody(BasicBlock * ifEntryBlock, BasicBlock * ifBodyFinalBlock) {
498    unsigned const ifScopeCarrySize = mCarryInfo->scopeCarryDataSize;
499    if (ifScopeCarrySize == 0) {
500        // No carry data, therefore no phi nodes.
501        return;
502    }
503#ifdef PACKING
504    if (ifScopeCarrySize < PACK_SIZE) {
505        unsigned const ifPackIndex = scopeBasePack();
506        PHINode * ifPack_phi = mBuilder->CreatePHI(mCarryPackType, 2, "ifPack");
507        ifPack_phi->addIncoming(mCarryInfo->ifEntryPack, ifEntryBlock);
508        ifPack_phi->addIncoming(mCarryOutPack[ifPackIndex], ifBodyFinalBlock);
509        mCarryOutPack[ifPackIndex] = ifPack_phi;
510    }
511#endif
512    if (mCarryInfo->getIfDepth() > 1) {
513        const unsigned summaryPackIndex = summaryPosition();
514        PHINode * summary_phi = mBuilder->CreatePHI(mCarryPackType, 2, "summary");
515        summary_phi->addIncoming(mZeroInitializer, ifEntryBlock);
516        summary_phi->addIncoming(mCarryOutPack[summaryPackIndex], ifBodyFinalBlock);
517        mCarryOutPack[summaryPackIndex] = summary_phi;
518    }
519}
520   
521void CarryManager::addSummaryPhiIfNeeded(BasicBlock * ifEntryBlock, BasicBlock * ifBodyFinalBlock) {
522    if ((mCarryInfo->getIfDepth() <= 1) || !mCarryInfo->blockHasCarries()){
523        // For ifDepth == 1, the parent does not need a summary as it is not itself within an if.
524        // Therefore, it doesn't need access to this block's summary in building its own.
525        return;
526    }
527    const unsigned carrySummaryIndex = summaryPosition();
528    PHINode * summary_phi = mBuilder->CreatePHI(mCarryPackType, 2, "summary");
529    summary_phi->addIncoming(mZeroInitializer, ifEntryBlock);
530    summary_phi->addIncoming(mCarryOutPack[carrySummaryIndex], ifBodyFinalBlock);
531    mCarryOutPack[carrySummaryIndex] = summary_phi;
532}
533   
534void CarryManager::generateCarryOutSummaryCodeIfNeeded() {
535   
536    if (!mCarryInfo->explicitSummaryRequired()) {
537        // An explicit summary may not be required, if there is a single carry
538        // operation within the block, or the carries are packed and all carry
539        // bits fit within a single pack.
540        return;
541    }
542   
543    const unsigned carrySummaryIndex = summaryPosition();
544   
545    Value * carry_summary = mZeroInitializer;
546    if (mCarryInfo->blockHasLongAdvances()) { // Force if entry
547        carry_summary = mOneInitializer;
548    }
549    else {
550        auto localCarryIndex = localBasePack();
551        auto localCarryPacks = mCarryInfo->getLocalCarryPackCount();
552        if (localCarryPacks > 0) {
553            carry_summary = mCarryOutPack[localCarryIndex];
554            for (auto i = 1; i < localCarryPacks; i++) {
555                //carry_summary = mBuilder->CreateOr(carry_summary, mPabloBlock->mCarryOutPack[i]);           
556                carry_summary = mBuilder->CreateOr(carry_summary, mCarryOutPack[localCarryIndex+i]);
557            }
558        }
559        for (Statement * stmt : *mCurrentScope) {
560            if (If * innerIf = dyn_cast<If>(stmt)) {
561                PabloBlock * inner_blk = & innerIf->getBody();
562                enterScope(inner_blk);
563                if (blockHasCarries()) {
564                  carry_summary = mBuilder->CreateOr(carry_summary, mCarryOutPack[summaryPosition()]);
565                }
566                leaveScope();
567            }
568            else if (While * innerWhile = dyn_cast<While>(stmt)) {
569                PabloBlock * inner_blk = & innerWhile->getBody();
570                enterScope(inner_blk);
571                if (blockHasCarries()) {
572                    carry_summary = mBuilder->CreateOr(carry_summary, mCarryOutPack[summaryPosition()]);
573                }
574                leaveScope();
575            }
576        }
577    }
578    // Calculation of the carry out summary is complete.   Store it and make it
579    // available in case it must included by parent blocks.
580    mCarryOutPack[carrySummaryIndex] = carry_summary;
581    storeCarryPack(carrySummaryIndex);
582}
583
584void CarryManager::ensureCarriesLoadedRecursive() {
585    const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
586    const unsigned currentScopeBase = scopeBasePack();
587    if (mCarryInfo->getWhileDepth() == 1) {
588        for (auto i = currentScopeBase; i < currentScopeBase + scopeCarryPacks; ++i) {
589            getCarryPack(i);
590        }
591    }
592}
593
594
595void CarryManager::initializeCarryDataPhisAtWhileEntry(BasicBlock * whileEntryBlock) {
596    const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
597    mCarryOutAccumPhis.resize(scopeCarryPacks);
598#ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
599    const unsigned currentScopeBase = scopeBasePack();
600    mCarryInPhis.resize(scopeCarryPacks);
601#endif
602    for (unsigned index = 0; index < scopeCarryPacks; ++index) {
603#ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
604        PHINode * phi_in = mBuilder->CreatePHI(mCarryPackType, 2);
605        phi_in->addIncoming(mCarryInPack[currentScopeBase+index], whileEntryBlock);
606        mCarryInPhis[index] = phi_in;
607#endif
608        PHINode * phi_out = mBuilder->CreatePHI(mCarryPackType, 2);
609        phi_out->addIncoming(mZeroInitializer, whileEntryBlock);
610        mCarryOutAccumPhis[index] = phi_out;
611    }
612}
613
614
615void CarryManager::extendCarryDataPhisAtWhileBodyFinalBlock(BasicBlock * whileBodyFinalBlock) {
616    const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
617    const unsigned currentScopeBase = scopeBasePack();
618    for (unsigned index = 0; index < scopeCarryPacks; ++index) {
619#ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
620        mCarryInPhis[index]->addIncoming(mZeroInitializer, whileBodyFinalBlock);
621#endif
622        PHINode * phi = mCarryOutAccumPhis[index];
623        Value * carryOut = mBuilder->CreateOr(phi, mCarryOutPack[currentScopeBase+index]);
624        phi->addIncoming(carryOut, whileBodyFinalBlock);
625        mCarryOutPack[currentScopeBase+index] = carryOut;
626    }
627}
628
629void CarryManager::ensureCarriesStoredRecursive() {
630    const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
631    const unsigned currentScopeBase = scopeBasePack();
632    if (mCarryInfo->getWhileDepth() == 1) {
633        for (auto i = currentScopeBase; i < currentScopeBase + scopeCarryPacks; ++i) {
634            storeCarryPack(i);
635        }
636    }
637}
638
639}
640
Note: See TracBrowser for help on using the repository browser.