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

Last change on this file since 5058 was 5058, checked in by nmedfort, 3 years ago

Potential bug fix for short advances

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