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

Last change on this file since 5245 was 5245, checked in by nmedfort, 22 months ago

Work on bracket matching problem

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