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

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

Added the kernel instance class; removed original mmap file access in favour of the boost mmap system. corrected PrintRegister? routine.

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