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

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

Work on parenthesis matching and expandable buffers. Changed CBuilder CreateMemZero? to zero n bytes rather than n units to conform to the built-in CreateMemSet? and CreateMemCpy? methods.

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