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

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

Rewrite of the CarryManager? to support non-carry-collapsing loops.

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