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

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

Code clean-up. Removed Pablo Call, SetIthBit? and Prototype.

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