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

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

Some fixes for threading and kernel builder.

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