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

Last change on this file since 5298 was 5292, checked in by nmedfort, 2 years ago

Removed 'function' and 'self' parameters from generateXXXMethod() functions.

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