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

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

Added a simple CreateAssert? function in CBuilder and ReadOnly? flag for getStreamSetBufferPtr method to prevent expanding input stream sets. Begun work on CarryManager? to preallocate variable-length carry data slots.

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