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

Last change on this file since 4945 was 4945, checked in by lindanl, 4 years ago

Use kernel state methods.

File size: 29.1 KB
Line 
1/*
2 *  Copyright (c) 2015 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6
7#include <stdexcept>
8#include <pablo/carry_data.h>
9#include <pablo/codegenstate.h>
10#include <pablo/carry_manager.h>
11#include <pablo/pabloAST.h>
12#include <llvm/Support/CommandLine.h>
13#include <llvm/IR/BasicBlock.h>
14#include <llvm/IR/CallingConv.h>
15#include <llvm/IR/Function.h>
16
17#if (BLOCK_SIZE==256)
18#define USING_LONG_ADD
19#endif
20#define DSSLI_FIELDWIDTH 64
21
22namespace pablo {
23
24/** ------------------------------------------------------------------------------------------------------------- *
25 * @brief doScopeCount
26 ** ------------------------------------------------------------------------------------------------------------- */
27static unsigned doScopeCount(const PabloBlock * const pb) {
28    unsigned count = 1;
29    for (const Statement * stmt : *pb) {
30        if (LLVM_UNLIKELY(isa<If>(stmt))) {
31            count += doScopeCount(cast<If>(stmt)->getBody());
32        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
33            count += doScopeCount(cast<While>(stmt)->getBody());
34        }
35    }
36    return count;
37}
38
39/** ------------------------------------------------------------------------------------------------------------- *
40 * @brief initialize
41 ** ------------------------------------------------------------------------------------------------------------- */
42void CarryManager::initialize(PabloBlock * pb, KernelBuilder * kBuilder) {
43    mRootScope = pb;
44    mCarryInfoVector.resize(doScopeCount(pb));
45    mCarryPackType = mBitBlockType;
46
47    const unsigned totalCarryDataSize = enumerate(pb, 0, 0);
48
49    mCarryPackPtr.resize(totalCarryDataSize, nullptr);
50    mCarryInPack.resize(totalCarryDataSize, nullptr);
51    mCarryOutPack.resize(totalCarryDataSize, nullptr);
52
53    mTotalCarryDataBitBlocks = totalCarryDataSize;
54   
55    ArrayType* cdArrayTy = ArrayType::get(mBitBlockType, mTotalCarryDataBitBlocks);
56    mCdArrayIdx = kBuilder->extendKernelInternalStateType(cdArrayTy);
57   
58    if (mPabloCountCount > 0) {
59        ArrayType* pcArrayTy = ArrayType::get(iBuilder->getIntNTy(64), mPabloCountCount);
60        mPcArrayIdx = kBuilder->extendKernelInternalStateType(pcArrayTy);
61    }
62 
63    mCurrentScope = mRootScope;
64    mCurrentFrameIndex = 0;
65    mCarryInfo = mCarryInfoVector[0];
66    mCarryOutPack[summaryPack()] = Constant::getNullValue(mCarryPackType);
67}
68
69void CarryManager::initialize_setPtrs(KernelBuilder * kBuilder) {
70
71    Value * kernelStuctParam = kBuilder->getKernelStructParam();
72    Value * cdArrayPtr = kBuilder->getKernelInternalStatePtr(kernelStuctParam, mCdArrayIdx);
73 
74    mCarryPackBasePtr = iBuilder->CreateBitCast(cdArrayPtr, PointerType::get(mCarryPackType, 0));
75    mCarryBitBlockPtr = iBuilder->CreateBitCast(cdArrayPtr, PointerType::get(mBitBlockType, 0));   
76   
77    if (mPabloCountCount > 0) {
78        Value * pcArrayPtr = kBuilder->getKernelInternalStatePtr(kernelStuctParam, mPcArrayIdx);
79        mPopcountBasePtr = iBuilder->CreateBitCast(pcArrayPtr, Type::getInt64PtrTy(iBuilder->getContext()));
80    }
81 
82    mBlockNo = iBuilder->CreateUDiv(kBuilder->getKernelInternalState(kernelStuctParam, mFilePosIdx), iBuilder->getInt64(mBitBlockWidth));
83    mCurrentScope = mRootScope;
84    mCurrentFrameIndex = 0;
85    mCarryInfo = mCarryInfoVector[0];
86    mCarryOutPack[summaryPack()] = Constant::getNullValue(mCarryPackType);
87}
88
89void CarryManager::set_BlockNo(KernelBuilder * kBuilder){
90    Value * kernelStuctParam = kBuilder->getKernelStructParam();
91    mBlockNo = iBuilder->CreateUDiv(kBuilder->getKernelInternalState(kernelStuctParam, mFilePosIdx), iBuilder->getInt64(mBitBlockWidth));
92}
93
94/** ------------------------------------------------------------------------------------------------------------- *
95 * @brief enterScope
96 ** ------------------------------------------------------------------------------------------------------------- */
97void CarryManager::enterScope(PabloBlock * const scope) {
98    Value * summaryCarry = mCarryOutPack[summaryPack()];
99    mCarrySummary.push_back(summaryCarry);
100    mCurrentScope = scope;
101    mCarryInfo = mCarryInfoVector[scope->getScopeIndex()];
102    mCurrentFrameIndex += mCarryInfo->getFrameIndex();
103    mCarryOutPack[summaryPack()] = Constant::getNullValue(mCarryPackType);
104}
105
106/** ------------------------------------------------------------------------------------------------------------- *
107 * @brief leaveScope
108 ** ------------------------------------------------------------------------------------------------------------- */
109void CarryManager::leaveScope() {
110    Value * summaryCarry = mCarryOutPack[summaryPack()];
111    assert (mCurrentScope != mRootScope);
112    mCurrentFrameIndex -= mCarryInfo->getFrameIndex();
113    mCurrentScope = mCurrentScope->getParent();
114    mCarryInfo = mCarryInfoVector[mCurrentScope->getScopeIndex()];
115    mCarryOutPack[summaryPack()] = summaryCarry;
116    mCarrySummary.pop_back();
117}
118
119/** ------------------------------------------------------------------------------------------------------------- *
120 * @brief addCarryInCarryOut
121 ** ------------------------------------------------------------------------------------------------------------- */
122Value * CarryManager::addCarryInCarryOut(const unsigned localIndex, Value * const e1, Value * const e2) {
123    Value * sum = nullptr;
124    if (mBitBlockWidth == 128) {
125        Value * carryq_value = getCarryIn(localIndex);
126        //calculate carry through logical ops
127        Value * carrygen = iBuilder->simd_and(e1, e2);
128        Value * carryprop = iBuilder->simd_or(e1, e2);
129        Value * digitsum = iBuilder->simd_add(64, e1, e2);
130        Value * partial = iBuilder->simd_add(64, digitsum, carryq_value);
131        Value * digitcarry = iBuilder->simd_or(carrygen, iBuilder->simd_and(carryprop, iBuilder->CreateNot(partial)));
132        Value * mid_carry_in = iBuilder->simd_slli(128, iBuilder->CreateLShr(digitcarry, 63), 64);
133        sum = iBuilder->simd_add(64, partial, iBuilder->CreateBitCast(mid_carry_in, mBitBlockType));
134        Value * carry_out_strm = iBuilder->simd_or(carrygen, iBuilder->simd_and(carryprop, iBuilder->CreateNot(sum)));
135        setCarryOut(localIndex, carry_out_strm);
136    } else {
137        #ifndef USING_LONG_ADD
138        Value * carryq_value = getCarryIn(localIndex);
139        Value * carrygen = iBuilder->simd_and(e1, e2);
140        Value * carryprop = iBuilder->simd_or(e1, e2);
141        sum = iBuilder->simd_add(mBitBlockWidth, iBuilder->simd_add(mBitBlockWidth, e1, e2), carryq_value);
142        Value * carry_out_strm = iBuilder->simd_or(carrygen, iBuilder->simd_and(carryprop, iBuilder->CreateNot(sum)));
143        setCarryOut(localIndex, carry_out_strm);
144        #else
145        Value * carryq_value = getCarryIn(localIndex);
146        Value * carryin = iBuilder->mvmd_extract(32, carryq_value, 0);
147        Value * carrygen = iBuilder->simd_and(e1, e2);
148        Value * carryprop = iBuilder->simd_or(e1, e2);
149        Value * digitsum = iBuilder->simd_add(64, e1, e2);
150        Value * digitcarry = iBuilder->simd_or(carrygen, iBuilder->simd_and(carryprop, iBuilder->CreateNot(digitsum)));
151        Value * carryMask = iBuilder->hsimd_signmask(64, digitcarry);
152        Value * carryMask2 = iBuilder->CreateOr(iBuilder->CreateAdd(carryMask, carryMask), carryin);
153        Value * bubble = iBuilder->simd_eq(64, digitsum, iBuilder->allOnes());
154        Value * bubbleMask = iBuilder->hsimd_signmask(64, bubble);
155        Value * incrementMask = iBuilder->CreateXor(iBuilder->CreateAdd(bubbleMask, carryMask2), bubbleMask);
156        Value * increments = iBuilder->esimd_bitspread(64,incrementMask);
157        sum = iBuilder->simd_add(64, digitsum, increments);
158        Value * carry_out_strm = iBuilder->CreateZExt(iBuilder->CreateLShr(incrementMask, mBitBlockWidth / 64), iBuilder->getIntNTy(mBitBlockWidth));
159        setCarryOut(localIndex, iBuilder->bitCast(carry_out_strm));
160        #endif
161    }
162    return sum;
163}
164
165/** ------------------------------------------------------------------------------------------------------------- *
166 * @brief advanceCarryInCarryOut
167 ** ------------------------------------------------------------------------------------------------------------- */
168Value * CarryManager::advanceCarryInCarryOut(const unsigned localIndex, const unsigned shiftAmount, Value * const value) {
169    if (LLVM_LIKELY(shiftAmount == 1)) {
170        return shortAdvanceCarryInCarryOut(unitAdvancePosition(localIndex), shiftAmount, value);
171    } else if (shiftAmount < LongAdvanceBase) {
172        return shortAdvanceCarryInCarryOut(shortAdvancePosition(localIndex), shiftAmount, value);
173    } else {
174        return longAdvanceCarryInCarryOut(longAdvancePosition(localIndex), shiftAmount, value);
175    }
176}
177
178/** ------------------------------------------------------------------------------------------------------------- *
179 * @brief shortAdvanceCarryInCarryOut
180 ** ------------------------------------------------------------------------------------------------------------- */
181Value * CarryManager::shortAdvanceCarryInCarryOut(const unsigned index, const unsigned shiftAmount, Value * const value) {
182    Value * result = nullptr;
183    Value * const carryIn = getCarryPack(index);
184    mCarryOutPack[index] = value;
185    if (mCarryInfo->getWhileDepth() == 0) {
186        storeCarryOut(index);
187    }
188    if (LLVM_LIKELY(shiftAmount == 1)) {
189        Value * ahead = iBuilder->mvmd_dslli(DSSLI_FIELDWIDTH, value, carryIn, iBuilder->getBitBlockWidth()/DSSLI_FIELDWIDTH -1);
190        result = iBuilder->simd_or(iBuilder->simd_srli(DSSLI_FIELDWIDTH, ahead, DSSLI_FIELDWIDTH-1), iBuilder->simd_slli(DSSLI_FIELDWIDTH, value, 1));
191    } else if (shiftAmount % 8 == 0) { // Use a single whole-byte shift, if possible.
192        result = iBuilder->mvmd_dslli(8, value, carryIn, (iBuilder->getBitBlockWidth() / 8) - (shiftAmount / 8));
193    } else if (shiftAmount < DSSLI_FIELDWIDTH) {
194        Value * ahead = iBuilder->mvmd_dslli(DSSLI_FIELDWIDTH, value, carryIn, iBuilder->getBitBlockWidth()/DSSLI_FIELDWIDTH - 1);
195        result = iBuilder->simd_or(iBuilder->simd_srli(DSSLI_FIELDWIDTH, ahead, DSSLI_FIELDWIDTH-shiftAmount), iBuilder->simd_slli(DSSLI_FIELDWIDTH, value, shiftAmount));
196    } else {
197        Value* advanceq_longint = iBuilder->CreateBitCast(carryIn, iBuilder->getIntNTy(mBitBlockWidth));
198        Value* strm_longint = iBuilder->CreateBitCast(value, iBuilder->getIntNTy(mBitBlockWidth));
199        Value* adv_longint = iBuilder->CreateOr(iBuilder->CreateShl(strm_longint, shiftAmount), iBuilder->CreateLShr(advanceq_longint, mBitBlockWidth - shiftAmount), "advance");
200        result = iBuilder->CreateBitCast(adv_longint, mBitBlockType);
201    }
202    if (LLVM_LIKELY(hasSummary())) {
203        addToSummary(value);
204    }
205    return result;
206}
207
208/** ------------------------------------------------------------------------------------------------------------- *
209 * @brief longAdvanceCarryInCarryOut
210 ** ------------------------------------------------------------------------------------------------------------- */
211Value * CarryManager::longAdvanceCarryInCarryOut(const unsigned index, const unsigned shiftAmount, Value * const value) {
212    Value * advBaseIndex = iBuilder->getInt64(index);
213    if (shiftAmount <= mBitBlockWidth) {
214        // special case using a single buffer entry and the carry_out value.
215        Value * advanceDataPtr = iBuilder->CreateGEP(mCarryBitBlockPtr, advBaseIndex);
216        Value * carry_block0 = iBuilder->CreateAlignedLoad(advanceDataPtr, mBitBlockWidth/8);
217        iBuilder->CreateAlignedStore(value, advanceDataPtr, mBitBlockWidth/8);
218        /* Very special case - no combine */
219        if (shiftAmount == mBitBlockWidth) {
220            return carry_block0;
221        }
222        Value* block0_shr = iBuilder->CreateLShr(iBuilder->CreateBitCast(carry_block0, iBuilder->getIntNTy(mBitBlockWidth)), mBitBlockWidth - shiftAmount);
223        Value* block1_shl = iBuilder->CreateShl(iBuilder->CreateBitCast(value, iBuilder->getIntNTy(mBitBlockWidth)), shiftAmount);
224        return iBuilder->CreateBitCast(iBuilder->CreateOr(block1_shl, block0_shr), mBitBlockType);
225    }
226    // We need a buffer of at least two elements for storing the advance data.
227    const unsigned block_shift = shiftAmount % mBitBlockWidth;
228    const unsigned advanceEntries = mCarryInfo->longAdvanceEntries(shiftAmount);
229    const unsigned bufsize = mCarryInfo->longAdvanceBufferSize(shiftAmount);
230    Value * indexMask = iBuilder->getInt64(bufsize - 1);  // A mask to implement circular buffer indexing
231    Value * loadIndex0 = iBuilder->CreateAdd(iBuilder->CreateAnd(iBuilder->CreateSub(mBlockNo, iBuilder->getInt64(advanceEntries)), indexMask), advBaseIndex);
232    Value * storeIndex = iBuilder->CreateAdd(iBuilder->CreateAnd(mBlockNo, indexMask), advBaseIndex);
233    Value * carry_block0 = iBuilder->CreateAlignedLoad(iBuilder->CreateGEP(mCarryBitBlockPtr, loadIndex0), mBitBlockWidth/8);
234    // If the long advance is an exact multiple of mBITBLOCK_WIDTH, we simply return the oldest
235    // block in the long advance carry data area. 
236    if (block_shift == 0) {
237        iBuilder->CreateAlignedStore(value, iBuilder->CreateGEP(mCarryBitBlockPtr, storeIndex), mBitBlockWidth/8);
238        return carry_block0;
239    }
240    // Otherwise we need to combine data from the two oldest blocks.
241    Value * loadIndex1 = iBuilder->CreateAdd(iBuilder->CreateAnd(iBuilder->CreateSub(mBlockNo, iBuilder->getInt64(advanceEntries-1)), indexMask), advBaseIndex);
242    Value * carry_block1 = iBuilder->CreateAlignedLoad(iBuilder->CreateGEP(mCarryBitBlockPtr, loadIndex1), mBitBlockWidth/8);
243    Value* block0_shr = iBuilder->CreateLShr(iBuilder->CreateBitCast(carry_block0, iBuilder->getIntNTy(mBitBlockWidth)), mBitBlockWidth - block_shift);
244    Value* block1_shl = iBuilder->CreateShl(iBuilder->CreateBitCast(carry_block1, iBuilder->getIntNTy(mBitBlockWidth)), block_shift);
245    iBuilder->CreateAlignedStore(value, iBuilder->CreateGEP(mCarryBitBlockPtr, storeIndex), mBitBlockWidth/8);
246    return iBuilder->CreateBitCast(iBuilder->CreateOr(block1_shl, block0_shr), mBitBlockType);
247}
248
249/** ------------------------------------------------------------------------------------------------------------- *
250 * @brief generateSummaryTest
251 ** ------------------------------------------------------------------------------------------------------------- */
252Value * CarryManager::generateSummaryTest(Value * condition) {
253    if (mCarryInfo->hasCarries()) {
254        Value * summary_pack = getCarryPack(summaryPack());
255        condition = iBuilder->simd_or(condition, summary_pack);
256    }
257    return iBuilder->bitblock_any(condition);
258}
259
260/** ------------------------------------------------------------------------------------------------------------- *
261 * @brief storeCarryOutSummary
262 ** ------------------------------------------------------------------------------------------------------------- */
263void CarryManager::storeCarryOutSummary() {
264    if (LLVM_LIKELY(mCarryInfo->explicitSummaryRequired())) {
265        const unsigned carrySummaryIndex = summaryPack();
266        if (LLVM_UNLIKELY(mCarryInfo->hasLongAdvances())) { // Force if entry
267            mCarryOutPack[carrySummaryIndex] = Constant::getAllOnesValue(mCarryPackType);
268        }
269        storeCarryOut(carrySummaryIndex);
270    }
271}
272
273/** ------------------------------------------------------------------------------------------------------------- *
274 * @brief popCount
275 ** ------------------------------------------------------------------------------------------------------------- */
276Value * CarryManager::popCount(Value * to_count, unsigned globalIdx) {
277    Value * countPtr = iBuilder->CreateGEP(mPopcountBasePtr, iBuilder->getInt64(globalIdx));
278    Value * countSoFar = iBuilder->CreateAlignedLoad(countPtr, 8);
279    Value * fieldCounts = iBuilder->simd_popcount(64, to_count);
280    for (int i = 0; i < mBitBlockWidth/64; i++) {
281        countSoFar = iBuilder->CreateAdd(countSoFar, iBuilder->mvmd_extract(64, fieldCounts, i));
282    }
283    iBuilder->CreateAlignedStore(countSoFar, countPtr, 8);
284    return iBuilder->bitCast(iBuilder->CreateZExt(countSoFar, iBuilder->getIntNTy(mBitBlockWidth)));
285}
286
287/** ------------------------------------------------------------------------------------------------------------- *
288 * @brief addOuterSummaryToNestedSummary
289 ** ------------------------------------------------------------------------------------------------------------- */
290void CarryManager::addOuterSummaryToNestedSummary() {
291    if (LLVM_LIKELY(mCarrySummary.size() > 0)) {
292        addToSummary(mCarrySummary.back());
293    }
294}
295
296/** ------------------------------------------------------------------------------------------------------------- *
297 * @brief buildCarryDataPhisAfterIfBody
298 ** ------------------------------------------------------------------------------------------------------------- */
299void CarryManager::buildCarryDataPhisAfterIfBody(BasicBlock * const entry, BasicBlock * const end) {
300    if (mCarryInfo->getWhileDepth() > 0) {
301        // We need to phi out everything for the while carry accumulation process.
302        const unsigned scopeBaseOffset = scopeBasePack();
303        const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
304        for (unsigned i = scopeBaseOffset; i < scopeBaseOffset + scopeCarryPacks; ++i) {
305            Type * const type = mCarryOutPack[i]->getType();
306            PHINode * phi = iBuilder->CreatePHI(type, 2);
307            phi->addIncoming(Constant::getNullValue(type), entry);
308            phi->addIncoming(mCarryOutPack[i], end);
309            mCarryOutPack[i] = phi;
310        }
311    }
312    if (LLVM_LIKELY(mCarrySummary.size() > 0)) {
313        const unsigned summaryIndex = summaryPack();
314        Value * carrySummary = mCarryOutPack[summaryIndex];
315        if (mCarrySummary.back() != carrySummary) {
316            Value * outerCarrySummary = mCarrySummary.back();
317            Value * nestedCarrySummary = mCarryOutPack[summaryIndex];
318            assert (outerCarrySummary->getType() == nestedCarrySummary->getType());
319            PHINode * const phi = iBuilder->CreatePHI(outerCarrySummary->getType(), 2, "summary");
320            phi->addIncoming(outerCarrySummary, entry);
321            phi->addIncoming(nestedCarrySummary, end);
322            mCarryOutPack[summaryIndex] = phi;
323        }
324    }
325}
326
327/** ------------------------------------------------------------------------------------------------------------- *
328 * @brief initializeWhileEntryCarryDataPhis
329 ** ------------------------------------------------------------------------------------------------------------- */
330void CarryManager::initializeWhileEntryCarryDataPhis(BasicBlock * const end) {
331    const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
332    mCarryOutAccumPhis.resize(scopeCarryPacks);
333    #ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
334    const unsigned currentScopeBase = scopeBasePack();
335    mCarryInPhis.resize(scopeCarryPacks);
336    #endif
337    for (unsigned index = 0; index < scopeCarryPacks; ++index) {
338        #ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
339        PHINode * phi_in = iBuilder->CreatePHI(mCarryPackType, 2);
340        phi_in->addIncoming(mCarryInPack[currentScopeBase+index], whileEntryBlock);
341        mCarryInPhis[index] = phi_in;
342        #endif
343        PHINode * phi_out = iBuilder->CreatePHI(mCarryPackType, 2);
344        phi_out->addIncoming(Constant::getNullValue(mCarryPackType), end);
345        mCarryOutAccumPhis[index] = phi_out;
346    }
347}
348
349/** ------------------------------------------------------------------------------------------------------------- *
350 * @brief finalizeWhileBlockCarryDataPhis
351 ** ------------------------------------------------------------------------------------------------------------- */
352void CarryManager::finalizeWhileBlockCarryDataPhis(BasicBlock * const end) {
353    const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
354    const unsigned currentScopeBase = scopeBasePack();
355    for (unsigned index = 0; index < scopeCarryPacks; ++index) {
356        #ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
357        mCarryInPhis[index]->addIncoming(Constant::getNullValue(mCarryPackType), whileBodyFinalBlock);
358        #endif
359        PHINode * phi = mCarryOutAccumPhis[index];
360        Value * carryOut = iBuilder->CreateOr(phi, mCarryOutPack[currentScopeBase + index]);
361        phi->addIncoming(carryOut, end);
362        mCarryOutPack[currentScopeBase + index] = carryOut;
363    }
364}
365
366/** ------------------------------------------------------------------------------------------------------------- *
367 * @brief ensureCarriesLoadedRecursive
368 ** ------------------------------------------------------------------------------------------------------------- */
369void CarryManager::ensureCarriesLoadedRecursive() {
370    const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
371    const unsigned currentScopeBase = scopeBasePack();
372    if (mCarryInfo->getWhileDepth() == 1) {
373        for (auto i = currentScopeBase; i < currentScopeBase + scopeCarryPacks; ++i) {
374            getCarryPack(i);
375        }
376    }
377}
378
379/** ------------------------------------------------------------------------------------------------------------- *
380 * @brief ensureCarriesStoredRecursive
381 ** ------------------------------------------------------------------------------------------------------------- */
382void CarryManager::ensureCarriesStoredRecursive() {
383    const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
384    const unsigned currentScopeBase = scopeBasePack();
385    if (mCarryInfo->getWhileDepth() == 1) {
386        for (auto i = currentScopeBase; i < currentScopeBase + scopeCarryPacks; ++i) {
387            storeCarryOut(i);
388        }
389    }
390}
391
392/** ------------------------------------------------------------------------------------------------------------- *
393 * @brief getCarryIn
394 ** ------------------------------------------------------------------------------------------------------------- */
395Value * CarryManager::getCarryIn(const unsigned localIndex) {
396    return getCarryPack(addPosition(localIndex));
397}
398
399/** ------------------------------------------------------------------------------------------------------------- *
400 * @brief setCarryOut
401 ** ------------------------------------------------------------------------------------------------------------- */
402void CarryManager::setCarryOut(const unsigned localIndex, Value * carryOut) {
403    const unsigned index = addPosition(localIndex);
404    #ifndef USING_LONG_ADD
405    Value * carry_bit = iBuilder->CreateLShr(iBuilder->CreateBitCast(carryOut, iBuilder->getIntNTy(mBitBlockWidth)), mBitBlockWidth-1);
406    carryOut = iBuilder->CreateBitCast(carry_bit, mBitBlockType);
407    #endif
408    mCarryOutPack[index] = carryOut;
409    if (LLVM_LIKELY(hasSummary())) {
410        addToSummary(carryOut);
411    }
412    if (mCarryInfo->getWhileDepth() == 0) {
413        storeCarryOut(index);
414    }
415}
416
417/** ------------------------------------------------------------------------------------------------------------- *
418 * @brief enumerate
419 ** ------------------------------------------------------------------------------------------------------------- */
420unsigned CarryManager::enumerate(PabloBlock * blk, unsigned ifDepth, unsigned whileDepth) {
421    unsigned idx = blk->getScopeIndex();
422    CarryData * cd = new CarryData(blk, mBitBlockWidth, 1);
423    mCarryInfoVector[idx] = cd;
424
425    cd->setIfDepth(ifDepth);
426    cd->setWhileDepth(whileDepth);
427    unsigned nestedOffset = cd->nested.frameOffset;
428
429    for (Statement * stmt : *blk) {
430        if (Count * c = dyn_cast<Count>(stmt)) {
431            c->setGlobalCountIndex(mPabloCountCount);
432            mPabloCountCount++;
433        } else if (If * ifStatement = dyn_cast<If>(stmt)) {
434            const unsigned ifCarryDataBits = enumerate(ifStatement->getBody(), ifDepth + 1, whileDepth);
435            CarryData * nestedBlockData = mCarryInfoVector[ifStatement->getBody()->getScopeIndex()];
436            if (1 == mBitBlockWidth) {  // PACKING
437                if (cd->roomInFinalPack(nestedOffset) < ifCarryDataBits) {
438                    nestedOffset = alignCeiling(nestedOffset, mBitBlockWidth);
439                }
440            }
441            nestedBlockData->setFramePosition(nestedOffset);
442            nestedOffset += ifCarryDataBits;
443            if (cd->maxNestingDepth <= nestedBlockData->maxNestingDepth) {
444                cd->maxNestingDepth = nestedBlockData->maxNestingDepth + 1;
445            }
446            cd->nested.entries++;
447        } else if (While * whileStatement = dyn_cast<While>(stmt)) {
448            const unsigned whileCarryDataBits = enumerate(whileStatement->getBody(), ifDepth, whileDepth + 1);
449            CarryData * const nestedBlockData = mCarryInfoVector[whileStatement->getBody()->getScopeIndex()];
450            if (1 == mBitBlockWidth) {  // PACKING
451                if (cd->roomInFinalPack(nestedOffset) < whileCarryDataBits) {
452                    nestedOffset = alignCeiling(nestedOffset, mBitBlockWidth);
453                }
454            }
455            nestedBlockData->setFramePosition(nestedOffset);
456            nestedOffset += whileCarryDataBits;
457            if (cd->maxNestingDepth <= nestedBlockData->maxNestingDepth) {
458                cd->maxNestingDepth = nestedBlockData->maxNestingDepth + 1;
459            }
460            cd->nested.entries++;
461        }
462    }
463
464    cd->scopeCarryDataSize = nestedOffset;
465
466    if (cd->explicitSummaryRequired()) {
467        // Need extra space for the summary variable, always the last
468        // entry within an if block.
469        if (1 == mBitBlockWidth) {  // PACKING
470            cd->scopeCarryDataSize = alignCeiling(cd->scopeCarryDataSize, mBitBlockWidth);
471        }
472        cd->summary.frameOffset = cd->scopeCarryDataSize;
473        cd->scopeCarryDataSize += 1;  //  computed summary is a full pack.
474    } else {
475        cd->summary.frameOffset = 0;
476    }
477
478    return cd->scopeCarryDataSize;
479}
480
481/** ------------------------------------------------------------------------------------------------------------- *
482 * @brief addToSummary
483 ** ------------------------------------------------------------------------------------------------------------- */
484inline Value * CarryManager::addToSummary(Value * const value) {
485    const unsigned summaryIndex = summaryPack();
486    Value * summary = mCarryOutPack[summaryIndex];
487    assert (summary);
488    assert (value);
489    if (LLVM_UNLIKELY(isa<Constant>(summary))) {
490        if (LLVM_LIKELY(cast<Constant>(summary)->isZeroValue())) {
491            summary = value;
492            goto return_result;
493        } else if (cast<Constant>(summary)->isAllOnesValue()) {
494            goto return_result;
495        }
496    }
497    if (LLVM_UNLIKELY(isa<Constant>(value))) {
498        if (LLVM_LIKELY(cast<Constant>(value)->isZeroValue())) {
499            goto return_result;
500        } else if (cast<Constant>(summary)->isAllOnesValue()) {
501            summary = value;
502            goto return_result;
503        }
504    }
505    if (LLVM_LIKELY(summary != value)) {
506        summary = iBuilder->CreateOr(summary, value, "summary");
507    }
508return_result:
509    mCarryOutPack[summaryIndex] = summary;
510    return summary;
511}
512
513/** ------------------------------------------------------------------------------------------------------------- *
514 * @brief getCarryPack
515 ** ------------------------------------------------------------------------------------------------------------- */
516Value * CarryManager::getCarryPack(const unsigned packIndex) {
517    if (mCarryInPack[packIndex] == nullptr) {
518        Value * const packPtr = iBuilder->CreateGEP(mCarryPackBasePtr, iBuilder->getInt64(packIndex));
519        mCarryPackPtr[packIndex] = packPtr;
520        mCarryInPack[packIndex] = iBuilder->CreateAlignedLoad(packPtr, mBitBlockWidth / 8);
521    }
522    return mCarryInPack[packIndex];
523}
524
525/** ------------------------------------------------------------------------------------------------------------- *
526 * @brief storeCarryOut
527 ** ------------------------------------------------------------------------------------------------------------- */
528void CarryManager::storeCarryOut(const unsigned packIndex) {
529    assert (mCarryOutPack[packIndex]);
530    assert (mCarryPackPtr[packIndex]);
531    iBuilder->CreateAlignedStore(mCarryOutPack[packIndex], mCarryPackPtr[packIndex], mBitBlockWidth / 8);
532}
533
534/* Helper routines */
535
536inline unsigned CarryManager::relativeFrameOffset(const unsigned frameOffset, const unsigned index) const {
537    return mCurrentFrameIndex + frameOffset + index;
538}
539
540inline unsigned CarryManager::addPosition(const unsigned localIndex) const {
541    return relativeFrameOffset(mCarryInfo->addWithCarry.frameOffset, localIndex);
542}
543
544inline unsigned CarryManager::unitAdvancePosition(const unsigned localIndex) const {
545    return relativeFrameOffset(mCarryInfo->unitAdvance.frameOffset, localIndex);
546}
547
548inline unsigned CarryManager::shortAdvancePosition(const unsigned localIndex) const {
549    return relativeFrameOffset(mCarryInfo->shortAdvance.frameOffset, localIndex);
550}
551
552inline unsigned CarryManager::longAdvancePosition(const unsigned localIndex) const {
553    return (mCurrentFrameIndex + mCarryInfo->longAdvance.frameOffset) + localIndex;
554}
555
556inline unsigned CarryManager::localBasePack() const {
557    return (mCurrentFrameIndex + mCarryInfo->shortAdvance.frameOffset);
558}
559
560inline unsigned CarryManager::scopeBasePack() const {
561    return mCurrentFrameIndex;
562}
563
564inline unsigned CarryManager::summaryPack() const {
565    return relativeFrameOffset(mCarryInfo->summary.frameOffset, 0);
566}
567
568inline bool CarryManager::hasSummary() const {
569    return mCarryInfo->explicitSummaryRequired() && !(mCarryInfo->hasLongAdvances());
570}
571
572CarryManager::~CarryManager() {
573    for (auto * cd : mCarryInfoVector) {
574        delete cd;
575    }
576}
577
578}
579
Note: See TracBrowser for help on using the repository browser.