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

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

Support for -BlockSize?=512 on AVX2

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