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

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

Bug fix

File size: 28.2 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>
[5227]16#include <pablo/printer_pablos.h>
[4644]17
[4925]18namespace pablo {
[4715]19
[5227]20inline static unsigned nearest_pow2(const unsigned v) {
21    assert(v > 0 && v < (UINT32_MAX / 2));
22    return (v < 2) ? 1 : (1 << (32 - __builtin_clz(v - 1)));
23}
24
25inline static unsigned ceil_udiv(const unsigned x, const unsigned y) {
26    return (((x - 1) | (y - 1)) + 1) / y;
27}
28
[4925]29/** ------------------------------------------------------------------------------------------------------------- *
[5063]30 * @brief initializeCarryData
[4925]31 ** ------------------------------------------------------------------------------------------------------------- */
[5227]32void CarryManager::initializeCarryData(PabloKernel * const kernel) {
[5045]33
[5227]34    // Each scope constructs its own CarryData struct, which will be added to the final "carries" struct
35    // that is added to the Kernel. The scope index will indicate which struct to access.
[5045]36
[5227]37    // A CarryData struct either contains an array of CarryPackBlocks or an integer indicating the capacity of
38    // the variable length CarryData struct and pointer. A variable length CarryData struct is required whenever
39    // the streams accessed by a loop could vary between iterations. When resizing a CarryData struct for a
40    // particular loop, the current loop struct and all nested structs need to be resized. This accommodates
41    // the fact every pablo While loop must be executed at least once.
42
43    // A nested loop may also contain a variable length CarryData struct
44
45    // To determine whether we require a variable length CarryData struct, we test the escaped variables of
46    // each loop branch to see whether they are used as the index parameter of a nested Extract statement.
47    // Any scope that requires variable length CarryData, requires that all nested branches have a unique
48    // set of carries for that iteration.
49
50    mKernel = kernel;
51
52    mCurrentScope = kernel->getEntryBlock();
53
54    mCarryMetadata.resize(enumerate(mCurrentScope));
55
56    mKernel->addScalar(analyse(mCurrentScope), "carries");
[4939]57}
58
[4959]59/** ------------------------------------------------------------------------------------------------------------- *
[5063]60 * @brief initializeCodeGen
[4959]61 ** ------------------------------------------------------------------------------------------------------------- */
[5227]62void CarryManager::initializeCodeGen(Value * self, Function * function) {
63    // TODO: need to look into abstracting the Initialize creation function in KernelBuilder::generateKernel
64    // so that we can allocate the variable length buffers if needed.
65
66    mSelf = self;
67    mFunction = function;
68
69    assert(mCarryMetadata.size() > 0);
70    mCarryInfo = &mCarryMetadata[0];
71    assert (!mCarryInfo->hasSummary());
72
73    mCurrentFrame = iBuilder->CreateGEP(mSelf, {iBuilder->getInt32(0), mKernel->getScalarIndex("carries")}, "carries");
[4691]74    mCurrentFrameIndex = 0;
[5227]75
76    assert (mCarryFrame.empty());
[4970]77    assert (mCarrySummary.empty());
[4644]78}
79
[4959]80/** ------------------------------------------------------------------------------------------------------------- *
[5227]81 * @brief enterLoopScope
[4925]82 ** ------------------------------------------------------------------------------------------------------------- */
[5227]83void CarryManager::enterLoopScope(PabloBlock * const scope) {
84    assert (scope);
85    if (mLoopDepth++ == 0) {
86        Value * const blockNo = mKernel->getScalarField(mSelf, blockNoScalar);
87        mLoopSelector = iBuilder->CreateAnd(blockNo, ConstantInt::get(blockNo->getType(), 1));
88    }
89    enterScope(scope);
[4670]90}
91
[4925]92/** ------------------------------------------------------------------------------------------------------------- *
[5227]93 * @brief enterLoopBody
[4925]94 ** ------------------------------------------------------------------------------------------------------------- */
[5227]95void CarryManager::enterLoopBody(BasicBlock * const entryBlock) {
[4670]96
[5227]97    if (mCarryInfo->hasSummary()) {
98        PHINode * carrySummary = iBuilder->CreatePHI(mCarryPackType, 2, "summary");
99        assert (mCarrySummary.size() > 0);
100        carrySummary->addIncoming(mCarrySummary.back(), entryBlock);
101        // Replace the incoming carry summary with the phi node and add the phi node to the stack
102        // so that we can properly OR it into the outgoing summary value.
103        mCarrySummary.back() = carrySummary;
104        mCarrySummary.push_back(carrySummary);
105    }
[4708]106
[5227]107    if (LLVM_UNLIKELY(mCarryInfo->variableLength)) {
108        // Check whether we need to resize the carry state
109        PHINode * index = iBuilder->CreatePHI(iBuilder->getSizeTy(), 2);
110        mLoopIndicies.push_back(index);
111        index->addIncoming(iBuilder->getSize(0), entryBlock);
112        Value * capacityPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(0)});
113        Value * capacity = iBuilder->CreateLoad(capacityPtr, false, "carryCapacity");
114        Value * arrayPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(1)});
115
116        BasicBlock * resizeBlock = BasicBlock::Create(iBuilder->getContext(), "", mFunction);
117        BasicBlock * codeBlock = BasicBlock::Create(iBuilder->getContext(), "", mFunction);
118
119        Value * cond = iBuilder->CreateICmpULT(index, capacity);
120        iBuilder->CreateCondBr(cond, codeBlock, resizeBlock);
121        iBuilder->SetInsertPoint(resizeBlock);
122
123        Type * const carryStateType = arrayPtr->getType()->getPointerElementType()->getPointerElementType();
124        Value * newCapacity = iBuilder->CreateMul(iBuilder->CreateAdd(index, iBuilder->getSize(1)), iBuilder->getSize(2));
125        Value * newArrayPtr = iBuilder->CreateAlignedMalloc(carryStateType, newCapacity, iBuilder->getCacheAlignment());
126        iBuilder->CreateMemCpy(newArrayPtr, arrayPtr, capacity, iBuilder->getCacheAlignment());
127        iBuilder->CreateMemZero(iBuilder->CreateGEP(newArrayPtr, capacity), iBuilder->CreateSub(newCapacity, capacity), iBuilder->getCacheAlignment());
128        iBuilder->CreateAlignedFree(arrayPtr);
129        iBuilder->CreateStore(newCapacity, capacityPtr);
130        iBuilder->CreateStore(newArrayPtr, arrayPtr);
131        iBuilder->CreateBr(codeBlock);
132
133        // Load the appropriate carry stat block
134        iBuilder->SetInsertPoint(codeBlock);
135
136        mCurrentFrame = iBuilder->CreateGEP(iBuilder->CreateLoad(arrayPtr), index);
137
[4647]138    }
[4644]139}
140
[4925]141/** ------------------------------------------------------------------------------------------------------------- *
[5227]142 * @brief leaveLoopBody
[4925]143 ** ------------------------------------------------------------------------------------------------------------- */
[5227]144void CarryManager::leaveLoopBody(BasicBlock * const exitBlock) {
145    if (mCarryInfo->hasSummary()) {
146        const auto n = mCarrySummary.size(); assert (n > 1);
147        cast<PHINode>(mCarrySummary[n - 2])->addIncoming(mCarrySummary[n - 1], exitBlock);
148        mCarrySummary.pop_back();
[4647]149    }
[5227]150    if (LLVM_UNLIKELY(mCarryInfo->variableLength)) {
151        assert (mLoopIndicies.size() > 0);
152        PHINode * index = mLoopIndicies.back();
153        index->addIncoming(iBuilder->CreateAdd(index, iBuilder->getSize(1)), exitBlock);
154        mLoopIndicies.pop_back();
[4647]155    }
[4644]156}
[4647]157
[4925]158/** ------------------------------------------------------------------------------------------------------------- *
[5227]159 * @brief leaveLoopScope
[4925]160 ** ------------------------------------------------------------------------------------------------------------- */
[5227]161void CarryManager::leaveLoopScope(BasicBlock * const entryBlock, BasicBlock * const exitBlock) {
162    assert (mLoopDepth > 0);
163    if (--mLoopDepth == 0) {
164        mLoopSelector = nullptr;
[4647]165    }
[5227]166    leaveScope();
[4644]167}
168
[4925]169/** ------------------------------------------------------------------------------------------------------------- *
[5227]170 * @brief enterIfScope
[4925]171 ** ------------------------------------------------------------------------------------------------------------- */
[5227]172void CarryManager::enterIfScope(PabloBlock * const scope) {
173    ++mIfDepth;
174    enterScope(scope);
175    mCarrySummary.push_back(Constant::getNullValue(mCarryPackType));
[4644]176}
177
[4925]178/** ------------------------------------------------------------------------------------------------------------- *
[5227]179 * @brief generateSummaryTest
[4925]180 ** ------------------------------------------------------------------------------------------------------------- */
[5227]181Value * CarryManager::generateSummaryTest(Value * condition) {
182    if (LLVM_LIKELY(mCarryInfo->hasSummary())) {
183        ConstantInt * zero = iBuilder->getInt32(0);
184        std::vector<Value *> indicies;
185        // enter the (potentially nested) struct and extract the summary element (0)
186        unsigned count = 2;
187        if (LLVM_UNLIKELY(mCarryInfo->hasBorrowedSummary())) {
188            Type * frameTy = mCurrentFrame->getType()->getPointerElementType();
189            count = 1;
190            while (frameTy->isStructTy()) {
191                ++count;
192                frameTy = frameTy->getStructElementType(0);
193            }
[4721]194        }
[5227]195        indicies.assign(count, zero);
196        if (LLVM_UNLIKELY(mCarryInfo->hasImplicitSummary() && mLoopDepth > 0)) {
197            indicies.push_back(zero);
198            indicies.push_back(mLoopSelector);
199        }
200        Value * ptr = iBuilder->CreateGEP(mCurrentFrame, indicies);
201        // Sanity check: make sure we're accessing a summary value
202        assert (ptr->getType()->getPointerElementType()->canLosslesslyBitCastTo(condition->getType()));
203        Value * summary = iBuilder->CreateBlockAlignedLoad(ptr);
204        condition = iBuilder->simd_or(condition, summary);
[4703]205    }
[5227]206    return condition;
[4704]207}
[4925]208
209/** ------------------------------------------------------------------------------------------------------------- *
[5227]210 * @brief enterIfBody
[4925]211 ** ------------------------------------------------------------------------------------------------------------- */
[5227]212void CarryManager::enterIfBody(BasicBlock * const entryBlock) { assert (entryBlock);
213
[4644]214}
[4922]215
[4925]216/** ------------------------------------------------------------------------------------------------------------- *
[5227]217 * @brief leaveIfBody
[4925]218 ** ------------------------------------------------------------------------------------------------------------- */
[5227]219void CarryManager::leaveIfBody(BasicBlock * const exitBlock) { assert (exitBlock);
220    const auto n = mCarrySummary.size();
221    if (LLVM_LIKELY(mCarryInfo->hasExplicitSummary())) {
222        assert (mCarrySummary.size() > 0);
223        Value * ptr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(0)});
224        Value * const value = iBuilder->CreateBitCast(mCarrySummary.back(), mBitBlockType);
225        iBuilder->CreateBlockAlignedStore(value, ptr);
[4644]226    }
[5227]227    if (n > 1) {
228        mCarrySummary[n - 1] = iBuilder->CreateOr(mCarrySummary[n - 1], mCarrySummary[n - 2], "summary");
[4644]229    }
230}
231
[4925]232/** ------------------------------------------------------------------------------------------------------------- *
[5227]233 * @brief leaveIfScope
[4925]234 ** ------------------------------------------------------------------------------------------------------------- */
[5227]235void CarryManager::leaveIfScope(BasicBlock * const entryBlock, BasicBlock * const exitBlock) {
236    assert (mIfDepth > 0);
237    if (mCarryInfo->hasSummary()) {
238        const auto n = mCarrySummary.size(); assert (n > 0);
239        if (n > 1) {
240            // When leaving a nested If scope with a summary value, phi out the summary to ensure the
241            // appropriate summary is stored in the outer scope.
242            Value * nested = mCarrySummary[n - 1];
243            Value * outer = mCarrySummary[n - 2];
244            if (LLVM_LIKELY(nested != outer)) {
245                assert (nested->getType() == outer->getType());
246                PHINode * const phi = iBuilder->CreatePHI(nested->getType(), 2, "summary");
247                phi->addIncoming(outer, entryBlock);
248                phi->addIncoming(nested, exitBlock);
249                mCarrySummary[n - 2] = phi;
250            }
251        }       
[4644]252    }
[5227]253    --mIfDepth;
254    leaveScope();
255    mCarrySummary.pop_back();
[4644]256}
257
[5227]258/** ------------------------------------------------------------------------------------------------------------ *
259 * @brief enterScope
[4925]260 ** ------------------------------------------------------------------------------------------------------------- */
[5227]261void CarryManager::enterScope(PabloBlock * const scope) {
262    assert (scope);
263    // Store the state of the current frame and update the scope state
264    mCarryFrame.emplace_back(mCurrentFrame, mCurrentFrameIndex + 1);
265    mCurrentScope = scope;
266    mCarryInfo = &mCarryMetadata[scope->getScopeIndex()];
267    // Check whether we're still within our struct bounds; if this fails, either the Pablo program changed within
268    // compilation or a memory corruption has occured.
269    assert (mCurrentFrameIndex < mCurrentFrame->getType()->getPointerElementType()->getStructNumElements());
270    mCurrentFrame = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(mCurrentFrameIndex)});
271    // Verify we're pointing to a carry frame struct
272    assert(mCurrentFrame->getType()->getPointerElementType()->isStructTy());
273    // We always use the 0-th slot for the summary value, even when it's implicit
274    mCurrentFrameIndex = mCarryInfo->hasExplicitSummary() ? 1 : 0;
275
[4644]276}
277
[4925]278/** ------------------------------------------------------------------------------------------------------------- *
[5227]279 * @brief leaveScope
[4925]280 ** ------------------------------------------------------------------------------------------------------------- */
[5227]281void CarryManager::leaveScope() {
[4925]282
[5227]283    // Did we use all of the packs in this carry struct?
284    assert (mCurrentFrameIndex == mCurrentFrame->getType()->getPointerElementType()->getStructNumElements());
285    // Sanity test: are there remaining carry frames?
286    assert (mCarryFrame.size() > 0);
287
288    std::tie(mCurrentFrame, mCurrentFrameIndex) = mCarryFrame.back();
289
290    assert(mCurrentFrame->getType()->getPointerElementType()->isStructTy());
291
292    mCarryFrame.pop_back();
293
294    mCurrentScope = mCurrentScope->getPredecessor();
295    assert (mCurrentScope);
296    mCarryInfo = &mCarryMetadata[mCurrentScope->getScopeIndex()];   
[4644]297}
298
[4925]299/** ------------------------------------------------------------------------------------------------------------- *
[5227]300 * @brief addCarryInCarryOut
[4925]301 ** ------------------------------------------------------------------------------------------------------------- */
[5227]302Value * CarryManager::addCarryInCarryOut(const Statement * operation, Value * const e1, Value * const e2) {
303    Value * const carryIn = getNextCarryIn();
304    Value * carryOut, * result;
305    std::tie(carryOut, result) = iBuilder->bitblock_add_with_carry(e1, e2, carryIn);
306    setNextCarryOut(carryOut);
307    assert (result->getType() == mBitBlockType);
308    return result;
[4925]309}
310
311/** ------------------------------------------------------------------------------------------------------------- *
[5227]312 * @brief advanceCarryInCarryOut
[4925]313 ** ------------------------------------------------------------------------------------------------------------- */
[5227]314Value * CarryManager::advanceCarryInCarryOut(const Advance * advance, Value * const value) {
315    const auto shiftAmount = advance->getAmount();
316    if (LLVM_LIKELY(shiftAmount <= mBitBlockWidth)) {
317        Value * const carryIn = getNextCarryIn();
318        Value * carryOut, * result;
319        if (LLVM_UNLIKELY(shiftAmount == mBitBlockWidth)) {
320            result = carryIn;
321            carryOut = value;
322        } else {
323            std::tie(carryOut, result) = iBuilder->bitblock_advance(value, carryIn, shiftAmount);
324        }
325        setNextCarryOut(carryOut);
326        assert (result->getType() == mBitBlockType);
327        return result;
328    } else {
329        return longAdvanceCarryInCarryOut(shiftAmount, value);
[4925]330    }
331}
332
333/** ------------------------------------------------------------------------------------------------------------- *
[5227]334 * @brief longAdvanceCarryInCarryOut
[4925]335 ** ------------------------------------------------------------------------------------------------------------- */
[5227]336Value * CarryManager::longAdvanceCarryInCarryOut(const unsigned shiftAmount, Value * value) {
[4925]337
[5227]338    assert (shiftAmount > mBitBlockWidth);
[4925]339
[5227]340    Type * const streamVectorTy = iBuilder->getIntNTy(mBitBlockWidth);
341    value = iBuilder->CreateBitCast(value, mBitBlockType);
342    Value * buffer = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(mCurrentFrameIndex++), iBuilder->getInt32(0)});
343
344    const unsigned blockShift = shiftAmount % mBitBlockWidth;
345    const unsigned entries = ceil_udiv(shiftAmount, mBitBlockWidth);
346
347    if (LLVM_LIKELY(mCarryInfo->hasExplicitSummary())) {
348        Value * const summaryPtr = iBuilder->CreateGEP(buffer, iBuilder->getInt32(0));
349        assert (summaryPtr->getType()->getPointerElementType() == mBitBlockType);
350        Value * carry = iBuilder->CreateZExtOrBitCast(iBuilder->bitblock_any(value), streamVectorTy);
351        const auto limit = ceil_udiv(shiftAmount, std::pow(mBitBlockWidth, 2));
352        assert (limit == summaryPtr->getType()->getPointerElementType()->getArrayNumElements());
353        for (unsigned i = 0;;++i) {
354            Value * ptr = iBuilder->CreateGEP(summaryPtr, iBuilder->getInt32(i));
355            Value * prior = iBuilder->CreateBitCast(iBuilder->CreateBlockAlignedLoad(ptr), streamVectorTy);
356            Value * stream = iBuilder->CreateOr(iBuilder->CreateShl(prior, 1), carry);
357            if (LLVM_LIKELY(i == limit)) {
358                stream = iBuilder->CreateAnd(stream, iBuilder->bitblock_mask_from(iBuilder->getInt32(entries % mBitBlockWidth)));
359                addToSummary(stream);
360                iBuilder->CreateBlockAlignedStore(stream, ptr);               
361                buffer = iBuilder->CreateGEP(buffer, iBuilder->getInt32(1));
362                break;
[4715]363            }
[5227]364            addToSummary(stream);
365            iBuilder->CreateBlockAlignedStore(stream, ptr);
366            carry = iBuilder->CreateLShr(prior, mBitBlockWidth - 1);
[4710]367        }
368    }
[5227]369    assert (buffer->getType()->getPointerElementType() == mBitBlockType);
[4925]370
[5227]371    // Create a mask to implement circular buffer indexing
372    Value * indexMask = ConstantInt::get(iBuilder->getSizeTy(), nearest_pow2(entries) - 1);
373    Value * blockIndex = mKernel->getScalarField(mSelf, blockNoScalar);
374    Value * carryIndex0 = iBuilder->CreateSub(blockIndex, iBuilder->getSize(entries));
375    Value * loadIndex0 = iBuilder->CreateAnd(carryIndex0, indexMask);
376    Value * storeIndex = iBuilder->CreateAnd(blockIndex, indexMask);
377    Value * carryIn = iBuilder->CreateBlockAlignedLoad(iBuilder->CreateGEP(buffer, loadIndex0));
378    assert (carryIn->getType() == mBitBlockType);
379    // If the long advance is an exact multiple of mBitBlockWidth, we simply return the oldest
380    // block in the long advance carry data area. 
381    if (blockShift == 0) {
382        iBuilder->CreateBlockAlignedStore(value, iBuilder->CreateGEP(buffer, storeIndex));
383        return carryIn;
384    }
385    // Otherwise we need to combine data from the two oldest blocks.
386    Value * carryIndex1 = iBuilder->CreateSub(blockIndex, iBuilder->getSize(entries - 1));
387    Value * loadIndex1 = iBuilder->CreateAnd(carryIndex1, indexMask);
388    Value * carry_block1 = iBuilder->CreateBlockAlignedLoad(iBuilder->CreateGEP(buffer, loadIndex1));
389    Value * block0_shr = iBuilder->CreateLShr(iBuilder->CreateBitCast(carryIn, streamVectorTy), mBitBlockWidth - blockShift);
390    Value * block1_shl = iBuilder->CreateShl(iBuilder->CreateBitCast(carry_block1, streamVectorTy), blockShift);
391    iBuilder->CreateBlockAlignedStore(value, iBuilder->CreateGEP(buffer, storeIndex));
392    return iBuilder->CreateBitCast(iBuilder->CreateOr(block1_shl, block0_shr), mBitBlockType);
393}
[4925]394
[5227]395/** ------------------------------------------------------------------------------------------------------------- *
396 * @brief getNextCarryIn
397 ** ------------------------------------------------------------------------------------------------------------- */
398Value * CarryManager::getNextCarryIn() {
399    assert (mCurrentFrameIndex < mCurrentFrame->getType()->getPointerElementType()->getStructNumElements());
400    Value * carryInPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(mCurrentFrameIndex++)});
401    mCarryPackPtr = carryInPtr;
402    if (mLoopDepth > 0) {
403        carryInPtr = iBuilder->CreateGEP(carryInPtr, {iBuilder->getInt32(0), mLoopSelector});
[4925]404    }
[5227]405    assert (carryInPtr->getType()->getPointerElementType() == mCarryPackType);
406    return iBuilder->CreateBlockAlignedLoad(carryInPtr);
407}
[4925]408
[5227]409/** ------------------------------------------------------------------------------------------------------------- *
410 * @brief setNextCarryOut
411 ** ------------------------------------------------------------------------------------------------------------- */
412void CarryManager::setNextCarryOut(Value * carryOut) {
413    if (LLVM_LIKELY(mCarryInfo->hasExplicitSummary())) {       
414        addToSummary(carryOut);
415    }
416    Value * carryOutPtr = mCarryPackPtr;
417    if (mLoopDepth > 0) {
418        Value * selector = iBuilder->CreateXor(mLoopSelector, ConstantInt::get(mLoopSelector->getType(), 1));
419        carryOutPtr = iBuilder->CreateGEP(mCarryPackPtr, {iBuilder->getInt32(0), selector});
420    }
421    carryOut = iBuilder->CreateBitCast(carryOut, mCarryPackType);
422    if (inCollapsingCarryMode()) {
423        Value * accum = iBuilder->CreateBlockAlignedLoad(carryOutPtr);
424        carryOut = iBuilder->CreateOr(carryOut, accum);
425    }
426    assert (carryOutPtr->getType()->getPointerElementType() == mCarryPackType);
427    iBuilder->CreateBlockAlignedStore(carryOut, carryOutPtr);
[4644]428}
429
[4925]430/** ------------------------------------------------------------------------------------------------------------- *
431 * @brief addToSummary
432 ** ------------------------------------------------------------------------------------------------------------- */
[5227]433void CarryManager::addToSummary(Value * value) { assert (value);
434    assert (mIfDepth > 0 && mCarrySummary.size() > 0);
435    Value * const summary = mCarrySummary.back(); assert (summary);
436    if (LLVM_UNLIKELY(summary == value)) {
437        return;  //Nothing to add.
438    }
439    value = iBuilder->CreateBitCast(value, mCarryPackType);
[5115]440    if (LLVM_UNLIKELY(isa<Constant>(value))) {
[5227]441        if (LLVM_UNLIKELY(cast<Constant>(value)->isZeroValue())) {
[5115]442            return;
[5227]443        } else if (LLVM_UNLIKELY(cast<Constant>(value)->isAllOnesValue())) {
444            mCarrySummary.back() = value;
445            return;
[5115]446        }
[5227]447    } else if (LLVM_UNLIKELY(isa<Constant>(summary))) {
448        if (LLVM_UNLIKELY(cast<Constant>(summary)->isZeroValue())) {
449            mCarrySummary.back() = value;
[5115]450            return;
[5227]451        } else if (LLVM_UNLIKELY(cast<Constant>(summary)->isAllOnesValue())) {
[5115]452            return;
[4925]453        }
[5227]454    }   
455    mCarrySummary.back() = iBuilder->CreateOr(summary, value);
[4720]456}
[4726]457
[4925]458/** ------------------------------------------------------------------------------------------------------------- *
[5227]459 * @brief collapsingCarryMode
[4925]460 ** ------------------------------------------------------------------------------------------------------------- */
[5227]461bool CarryManager::inCollapsingCarryMode() const {
462    return (mCurrentScope->getBranch() && isa<While>(mCurrentScope->getBranch()) && !mCarryInfo->variableLength);
463}
464
465/** ------------------------------------------------------------------------------------------------------------- *
466 * @brief enumerate
467 ** ------------------------------------------------------------------------------------------------------------- */
468unsigned CarryManager::enumerate(PabloBlock * const scope, unsigned index) {
469    scope->setScopeIndex(index++);
470    for (Statement * stmt : *scope) {
471        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
472            index = enumerate(cast<Branch>(stmt)->getBody(), index);
473        }
[4925]474    }
[5227]475    return index;
[4925]476}
477
478/** ------------------------------------------------------------------------------------------------------------- *
[5227]479 * @brief requiresVariableLengthMode
[4925]480 ** ------------------------------------------------------------------------------------------------------------- */
[5227]481bool CarryManager::requiresVariableLengthMode(const PabloBlock * const scope) {
482    if (const Branch * const br = scope->getBranch()) {
483        for (const Var * var : br->getEscaped()) {
484            for (const PabloAST * user : var->users()) {
485                if (const Extract * e = dyn_cast<Extract>(user)) {
486                    if (LLVM_UNLIKELY(e->getIndex() == var)) {
487                        // If we assign this Var a value and read the value as the index parameter
488                        // of a nested Extract statement, then we cannot collapse the carries.
489                        const PabloBlock * parent = e->getParent();
490                        for (;;) {
491                            if (parent == scope) {
492                                return true;
493                            }
494                            parent = parent->getPredecessor();
495                            if (parent == nullptr) {
496                                break;
497                            }
498                        }
499                    }
500                }
501            }
502        }
503    }
504    return false;
[4925]505}
506
[5227]507/** ------------------------------------------------------------------------------------------------------------- *
508 * @brief analyse
509 ** ------------------------------------------------------------------------------------------------------------- */
510StructType * CarryManager::analyse(PabloBlock * const scope, const unsigned ifDepth, const unsigned loopDepth) {
[4925]511
[5227]512    std::vector<Type *> state;
[4925]513
[5227]514    assert (mCarryPackType);
[4925]515
[5227]516    Type * const carryPackType = (loopDepth == 0) ? mCarryPackType : ArrayType::get(mCarryPackType, 2);
[4925]517
[5227]518    bool hasLongAdvances = false;
519    for (Statement * stmt : *scope) {
520        if (LLVM_UNLIKELY(isa<Advance>(stmt))) {
521            const auto amount = cast<Advance>(stmt)->getAmount();
522            if (LLVM_LIKELY(amount <= mBitBlockWidth)) {
523                state.push_back(carryPackType);
524            } else {
525                const auto blocks = ceil_udiv(amount, mBitBlockWidth); assert (blocks > 1);
526                Type * type = ArrayType::get(mBitBlockType, nearest_pow2(blocks));
527                if (LLVM_UNLIKELY(ifDepth > 0)) {
528                    Type * carryType = ArrayType::get(mBitBlockType, ceil_udiv(amount, std::pow(mBitBlockWidth, 2)));
529                    type = StructType::get(carryType, type, nullptr);
530                    hasLongAdvances = true;
531                }
532                state.push_back(type);
533            }
534        } else if (LLVM_UNLIKELY(isa<ScanThru>(stmt) || isa<MatchStar>(stmt))) {
535            state.push_back(carryPackType);
536        } else if (LLVM_UNLIKELY(isa<If>(stmt))) {
537            state.push_back(analyse(cast<If>(stmt)->getBody(), ifDepth + 1, loopDepth));
538        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
539            state.push_back(analyse(cast<While>(stmt)->getBody(), ifDepth, loopDepth + 1));
540        }
541    }
[4925]542
[5227]543    assert (scope->getScopeIndex() < mCarryMetadata.size());
[4925]544
[5227]545    CarryData & cd = mCarryMetadata[scope->getScopeIndex()];
[4925]546
[5227]547    StructType * carryState = nullptr;
[4925]548
[5227]549    // Add the summary pack if needed.
550    cd.summaryType = CarryData::NoSummary;
551    if (LLVM_UNLIKELY(state.empty())) {
552        carryState = StructType::get(iBuilder->getContext());
553    } else {
554        cd.variableLength = loopDepth > 0 && requiresVariableLengthMode(scope);
555        if (ifDepth > 0) {
556            // A non-collapsing loop requires a unique summary for each iteration. Thus whenever
557            // we have a non-collapsing While within an If scope with an implicit summary, the If
558            // scope requires an explicit summary.
[4925]559
[5227]560            if (LLVM_LIKELY(state.size() > 1 || hasLongAdvances)) {
561                cd.summaryType = CarryData::ExplicitSummary;
562                state.insert(state.begin(), mCarryPackType);
563            } else {
564                cd.summaryType = CarryData::ImplicitSummary;
565                if (state[0]->isStructTy()) {
566                    cd.summaryType = CarryData::BorrowedSummary;
567                }
568            }
569        }
570        carryState = StructType::get(iBuilder->getContext(), state);
571        // If we in a loop and cannot use collapsing carry mode, convert the struct into a capacity and pointer pair.
572        if (LLVM_UNLIKELY(cd.variableLength)) {
573            carryState = StructType::get(iBuilder->getSizeTy(), carryState->getPointerTo(), nullptr);
574        }
[4712]575    }
[5227]576    return carryState;
[4710]577}
578
[4712]579}
580
Note: See TracBrowser for help on using the repository browser.