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

Last change on this file since 4942 was 4942, checked in by lindanl, 3 years ago

Remove simd-lib. Print register implemented in LLVM IR.

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