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

Last change on this file since 4927 was 4927, checked in by nmedfort, 4 years ago

Bug fixes

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