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

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

Fix for last check in for 32-bit

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