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

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

Progress on parenthesis matching example

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