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

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

new version using the kernels.

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