source: icGREP/icgrep-devel/icgrep/kernels/multiblock_kernel.cpp @ 6047

Last change on this file since 6047 was 6047, checked in by nmedfort, 12 months ago

Major refactoring of buffer types. Static buffers replace Circular and CircularCopyback?. External buffers unify Source/External?.

File size: 34.7 KB
Line 
1/*
2 *  Copyright (c) 2018 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 */
5#include <kernels/kernel.h>
6
7#include <toolchain/toolchain.h>
8#include <kernels/streamset.h>
9#include <llvm/IR/Constants.h>
10#include <llvm/IR/Function.h>
11#include <llvm/IR/Instructions.h>
12#include <llvm/IR/MDBuilder.h>
13#include <llvm/IR/Module.h>
14#include <llvm/Support/raw_ostream.h>
15#if LLVM_VERSION_INTEGER < LLVM_VERSION_CODE(4, 0, 0)
16#include <llvm/Bitcode/ReaderWriter.h>
17#else
18#include <llvm/Bitcode/BitcodeWriter.h>
19#endif
20#include <llvm/Transforms/Utils/Local.h>
21#include <kernels/streamset.h>
22#include <sstream>
23#include <kernels/kernel_builder.h>
24#include <boost/math/common_factor.hpp>
25#include <boost/graph/adjacency_list.hpp>
26#include <llvm/Support/Debug.h>
27
28using namespace llvm;
29using namespace parabix;
30using namespace boost;
31using namespace boost::math;
32
33// #define DEBUG_LOG
34
35#define POPCOUNT_RATE_MAX_STRIDES_PER_ROUND (31)
36
37namespace kernel {
38
39using RateValue = ProcessingRate::RateValue;
40
41/** ------------------------------------------------------------------------------------------------------------- *
42 * @brief generateKernelMethod
43 ** ------------------------------------------------------------------------------------------------------------- */
44void MultiBlockKernel::generateKernelMethod(const std::unique_ptr<KernelBuilder> & b) {
45
46    if (LLVM_UNLIKELY((mStride % b->getBitBlockWidth()) != 0)) {
47        report_fatal_error(getName() + ": the Stride (" + std::to_string(mStride) + ") of MultiBlockKernel "
48                           "must be a multiple of the BitBlockWidth (" + std::to_string(b->getBitBlockWidth()) + ")");
49    }
50
51    const auto inputSetCount = mStreamSetInputs.size();
52    const auto outputSetCount = mStreamSetOutputs.size();
53
54    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
55        Value * terminatedTwice = b->CreateAnd(mIsFinal, b->getTerminationSignal());
56        Value * unprocessedData = nullptr;
57        for (unsigned i = 0; i < inputSetCount; i++) {
58            Value * processed = b->getProcessedItemCount(mStreamSetInputs[i].getName());
59            Value * const check = b->CreateICmpNE(processed, mAvailableItemCount[i]);
60            unprocessedData = unprocessedData ? b->CreateOr(unprocessedData, check) : check;
61        }
62        b->CreateAssertZero(b->CreateAnd(terminatedTwice, unprocessedData),
63                            getName() + " was called after its termination with additional input data");
64        b->CreateAssertZero(terminatedTwice,
65                            getName() + " was called after its termination");
66    }
67
68    mInitialAvailableItemCount.assign(mAvailableItemCount.begin(), mAvailableItemCount.end());
69    mInitialProcessedItemCount.resize(inputSetCount, nullptr);
70    mAccessibleInputItems.resize(inputSetCount, nullptr);
71    mInputStrideLength.resize(inputSetCount, nullptr);
72    mPopCountRateArray.resize(inputSetCount, nullptr);
73
74    mInitialProducedItemCount.resize(outputSetCount, nullptr);
75    mWritableOutputItems.resize(outputSetCount, nullptr);
76    mOutputStrideLength.resize(outputSetCount, nullptr);
77
78    mInitiallyFinal = mIsFinal;
79    #ifdef DEBUG_LOG
80    for (unsigned i = 0; i < inputSetCount; ++i) {
81        b->CallPrintInt(getName() + "_" + mStreamSetInputs[i].getName() + "_available", mAvailableItemCount[i]);
82    }
83    b->CallPrintInt(getName() + "_initiallyFinal", mInitiallyFinal);
84    #endif
85    mTreatUnsafeKernelOperationsAsErrors = true;
86
87    // Now proceed with creation of the doSegment method.
88    BasicBlock * const segmentLoop = b->CreateBasicBlock("SegmentLoop");
89    b->CreateBr(segmentLoop);
90
91    b->SetInsertPoint(segmentLoop);
92    writeMultiBlockLogic(b);
93    writeCopyBackLogic(b);
94    BasicBlock * const handleFinalBlock = b->CreateBasicBlock("FinalBlock");
95    BasicBlock * const strideDone = b->CreateBasicBlock("StridesDone");
96    b->CreateUnlikelyCondBr(mIsFinal, handleFinalBlock, strideDone);
97
98
99    /// FINAL STRIDE ADJUSTMENT
100    handleFinalBlock->moveAfter(b->GetInsertBlock());
101    b->SetInsertPoint(handleFinalBlock);
102    updateFinalDerivedItemCounts(b);
103    b->setTerminationSignal(b->getTrue());
104    BasicBlock * const segmentDone = b->CreateBasicBlock("SegmentDone");
105    b->CreateBr(segmentDone);
106
107    /// CHECK FOR ANOTHER STRIDE
108    strideDone->moveAfter(b->GetInsertBlock());
109    b->SetInsertPoint(strideDone);
110    // TODO: don't bother computing this for block oriented kernels
111    updateDerivedItemCounts(b);
112    b->CreateCondBr(hasAnotherStride(b), segmentLoop, segmentDone);
113
114    /// SEGMENT DONE
115    segmentDone->moveAfter(b->GetInsertBlock());
116    b->SetInsertPoint(segmentDone);
117}
118
119/** ------------------------------------------------------------------------------------------------------------- *
120 * @brief writeMultiBlock
121 ** ------------------------------------------------------------------------------------------------------------- */
122inline void MultiBlockKernel::writeMultiBlockLogic(const std::unique_ptr<KernelBuilder> & b) {
123    mNumOfStrides = nullptr;
124    mNumOfStridesInFinalSegment = b->getSize(1);
125    for (unsigned i = 0; i < mStreamSetInputs.size(); i++) {
126        checkInputStream(b, i);
127    }
128    mIsFinal = b->CreateICmpEQ(mNumOfStrides, b->getSize(0));
129    mNumOfStrides = b->CreateSelect(mIsFinal, mNumOfStridesInFinalSegment, mNumOfStrides);
130    for (unsigned i = 0; i < mStreamSetOutputs.size(); i++) {
131        checkOutputStream(b, i);
132    }
133    #ifdef DEBUG_LOG
134    b->CallPrintInt(getName() + "_isFinal", mIsFinal);
135    b->CallPrintInt(getName() + "_numOfStrides", mNumOfStrides);
136    #endif
137    calculateDerivedItemCounts(b);
138    prepareOverflowBuffers(b);
139    generateMultiBlockLogic(b, mNumOfStrides);
140    checkTerminationSignal(b);
141}
142
143/** ------------------------------------------------------------------------------------------------------------- *
144 * @brief checkInputStream
145 ** ------------------------------------------------------------------------------------------------------------- */
146inline void MultiBlockKernel::checkInputStream(const std::unique_ptr<KernelBuilder> & b, const unsigned index) {
147    const Binding & input = mStreamSetInputs[index];
148    const auto & name = input.getName();
149    Value * const processed = b->getNonDeferredProcessedItemCount(input);
150    mInitialProcessedItemCount[index] = processed;
151    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
152        b->CreateAssert(b->CreateICmpULE(processed, mAvailableItemCount[index]),
153                        getName() + ": " + name + " processed item count exceeds available item count");
154    }
155    Value * accessible = b->CreateSub(mAvailableItemCount[index], processed);
156    if (LLVM_UNLIKELY(requiresLinearAccess(input))) {
157        accessible = b->getLinearlyAccessibleItems(name, processed, accessible);
158    }
159    // NOTE: mAccessibleInputItems must initially reflect the # of items PRIOR to any lookahead.
160    // This is so that we can use this number directly for any final stride calculations.
161    mAccessibleInputItems[index] = accessible;
162    if (input.hasLookahead()) {
163        Constant * const lookahead = b->getSize(input.getLookahead());
164        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
165            b->CreateAssert(b->CreateICmpULE(lookahead, accessible),
166                            getName() + ": " + name + " lookahead exceeds accessible item count");
167        }
168        accessible = b->CreateSub(accessible, lookahead);
169    }
170    Value * accessibleStrides = nullptr;
171    const ProcessingRate & rate = input.getRate();
172    if (LLVM_UNLIKELY(rate.isPopCount() || rate.isNegatedPopCount())) {
173        accessibleStrides = computePopCountRate(b, rate, accessible);
174    } else {
175        mInputStrideLength[index] = b->getSize(ceiling(getUpperBound(rate) * mStride));
176        accessibleStrides = b->CreateUDiv(accessible, mInputStrideLength[index]);
177    }
178    assert ("input cannot have an unknown number of strides" && accessibleStrides);
179    #ifdef DEBUG_LOG
180    b->CallPrintInt(getName() + "_" + name + "_availableStrides", accessibleStrides);
181    #endif
182    mNumOfStrides = b->CreateUMin(mNumOfStrides, accessibleStrides);
183    if (LLVM_UNLIKELY(input.hasAttribute(Attribute::KindId::Principal))) {
184        if (rate.isFixed()) {
185            accessibleStrides = b->CreateCeilUDiv(accessible, mInputStrideLength[index]);
186        }
187        mNumOfStridesInFinalSegment = b->CreateUMax(accessibleStrides, mNumOfStridesInFinalSegment);
188    }
189    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
190        Value * const hasData = b->CreateIsNotNull(accessibleStrides);
191        Value * const hasStride = b->CreateOr(mInitiallyFinal, hasData);
192        b->CreateAssert(hasStride, getName() + ": " + name + " has insufficient input data for one stride");
193    }
194}
195
196/** ------------------------------------------------------------------------------------------------------------- *
197 * @brief checkOutputStream
198 ** ------------------------------------------------------------------------------------------------------------- */
199inline void MultiBlockKernel::checkOutputStream(const std::unique_ptr<KernelBuilder> & b, const unsigned index) {
200    const Binding & output = mStreamSetOutputs[index];
201    const auto & name = output.getName();
202    Value * const produced = b->getNonDeferredProducedItemCount(output);
203    mInitialProducedItemCount[index] = produced;
204    Value * writable = nullptr;
205    if (LLVM_UNLIKELY(permitsNonLinearAccess(output))) {
206        Value * const consumed = b->getConsumedItemCount(name);
207        Value * const unconsumed = b->CreateSub(produced, consumed);
208        Value * const capacity = b->getCapacity(name);
209        writable = b->CreateSub(capacity, unconsumed);
210    } else {
211        writable = b->getLinearlyWritableItems(name, produced);
212    }
213    Value * writableStrides = nullptr;
214    const ProcessingRate & rate = output.getRate();
215    if (LLVM_UNLIKELY(rate.isPopCount() || rate.isNegatedPopCount())) {
216        writableStrides = computePopCountRate(b, rate, writable);
217    } else {
218        mOutputStrideLength[index] = b->getSize(ceiling(getUpperBound(rate) * getStride()));
219        writableStrides = b->CreateUDiv(writable, mOutputStrideLength[index]);
220    }
221    assert ("output cannot have an unknown number of strides" && writableStrides);
222    #ifdef DEBUG_LOG
223    b->CallPrintInt(getName() + "_" + name + "_writableStrides", writableStrides);
224    #endif
225    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
226        Value * const hasSpace = b->CreateIsNotNull(writableStrides);
227        b->CreateAssert(hasSpace, getName() + ": " + name + " has insufficient output space for one stride");
228    }
229    mNumOfStrides = b->CreateUMin(mNumOfStrides, writableStrides);
230    mWritableOutputItems[index] = writable;
231}
232
233/** ------------------------------------------------------------------------------------------------------------- *
234 * @brief computePopCountRate
235 ** ------------------------------------------------------------------------------------------------------------- */
236Value * MultiBlockKernel::computePopCountRate(const std::unique_ptr<KernelBuilder> & b, const ProcessingRate & rate, Value * const maxItems) {
237
238    // To auto increment a popcount rate stream, we need to store how many positions could be incremented per
239    // stride index since our final numOfStrides may be smaller than the current one.
240
241    Port refPort;
242    unsigned refIndex = 0;
243    std::tie(refPort, refIndex) = getStreamPort(rate.getReference());
244    assert (refPort == Port::Input);
245
246    if (mPopCountRateArray[refIndex]) {
247        // TODO: if we already have a popcount rate array for this reference stream, reuse it.
248
249        // NOTE: the maxItems of the first stream could be less than this one. To do this safely, the kernel must
250        // first check what the largest possible maxItem count is when initially creating the popcount stream
251
252        assert (false);
253        return nullptr;
254
255    } else {
256
257        const Binding & ref = mStreamSetInputs[refIndex];
258
259        // TODO: we can use 16-bit integers instead here but would need to make it safe for > 1024-bit block width
260
261        Constant * const ONE = b->getSize(1);
262        Constant * const MAX = b->getSize(POPCOUNT_RATE_MAX_STRIDES_PER_ROUND);
263        Value * const maxNumOfStrides = b->CreateUMin(mNumOfStrides, MAX);
264        Constant * const ARRAY_SIZE = b->getSize(POPCOUNT_RATE_MAX_STRIDES_PER_ROUND + 1);
265        AllocaInst * const partialSumArray = b->CreateAlloca(b->getSizeTy(), ARRAY_SIZE);
266
267        BasicBlock * const entry = b->GetInsertBlock();
268        BasicBlock * const popCountLoop = b->CreateBasicBlock();
269        BasicBlock * const popCountAppend = b->CreateBasicBlock();
270        BasicBlock * const popCountExit = b->CreateBasicBlock();
271
272        Constant * const ZERO = b->getSize(0);
273        b->CreateBr(popCountLoop);
274
275        b->SetInsertPoint(popCountLoop);
276        PHINode * const strideIndex = b->CreatePHI(b->getSizeTy(), 2);
277        strideIndex->addIncoming(ZERO, entry);
278        PHINode * const partialSum = b->CreatePHI(b->getSizeTy(), 2);
279        partialSum->addIncoming(ZERO, entry);
280        // TODO: what if we have a stream set of more than one stream element? or swizzled input?
281        Value * const ptr = b->getInputStreamBlockPtr(ref.getName(), ZERO, strideIndex);
282        Value * markers = b->CreateBlockAlignedLoad(ptr);
283        if (rate.isNegatedPopCount()) {
284            markers = b->CreateNot(markers);
285        }
286        Value * const count = b->bitblock_popcount(markers);
287        Value * const partialSum2 = b->CreateAdd(partialSum, count);
288        Value * const ptr2 = b->CreateGEP(partialSumArray, strideIndex);
289        b->CreateStore(partialSum2, ptr2);
290        Value * const hasEnoughSourceItems = b->CreateICmpULE(partialSum2, maxItems);
291        b->CreateCondBr(hasEnoughSourceItems, popCountAppend, popCountExit);
292
293        b->SetInsertPoint(popCountAppend);
294        partialSum->addIncoming(partialSum2, popCountAppend);
295        Value * const nextStrideIndex = b->CreateAdd(strideIndex, ONE);
296        Value * const hasMore = b->CreateICmpNE(nextStrideIndex, maxNumOfStrides);
297        strideIndex->addIncoming(nextStrideIndex, popCountAppend);
298        b->CreateCondBr(hasMore, popCountLoop, popCountExit);
299
300        b->SetInsertPoint(popCountExit);
301        PHINode * const strideCount = b->CreatePHI(b->getSizeTy(), 2);
302        strideCount->addIncoming(strideIndex, popCountLoop);
303        strideCount->addIncoming(nextStrideIndex, popCountAppend);
304        // add in a sentinal to simplify the "hasAnotherStride" logic
305        Value * const ptr3 = b->CreateGEP(partialSumArray, MAX);
306        b->CreateStore(ConstantInt::getAllOnesValue(b->getSizeTy()), ptr3);
307
308        mPopCountRateArray[refIndex] = partialSumArray;
309
310        return strideCount;
311    }
312
313}
314
315
316/** ------------------------------------------------------------------------------------------------------------- *
317 * @brief writeCopyBackLogic
318 ** ------------------------------------------------------------------------------------------------------------- */
319inline void MultiBlockKernel::writeCopyBackLogic(const std::unique_ptr<KernelBuilder> & b) {
320    // Do copybacks if necessary.
321    for (unsigned i = 0; i < mStreamSetOutputs.size(); ++i) {
322        const Binding & output = mStreamSetOutputs[i];
323        if (requiresCopyBack(output) && mStreamSetOutputBuffers[i]->supportsCopyBack()) {
324            const auto & name = output.getName();
325            BasicBlock * const copyBack = b->CreateBasicBlock(name + "CopyBack");
326            BasicBlock * const done = b->CreateBasicBlock(name + "CopyBackDone");
327            Value * const capacity = b->getCapacity(name);
328            Value * const priorOffset = b->CreateURem(mInitialProducedItemCount[i], capacity);
329            Value * const produced = b->getProducedItemCount(name);
330            Value * const currentOffset = b->CreateURem(produced, capacity);
331            b->CreateUnlikelyCondBr(b->CreateICmpULT(currentOffset, priorOffset), copyBack, done);
332
333            b->SetInsertPoint(copyBack);
334            Value * overflowOffset = nullptr;
335            if (permitsNonLinearAccess(output)) {
336                // if we can compute the overflowPosition, do so
337                const ProcessingRate & rate = output.getRate();
338                if (rate.isPopCount() || rate.isNegatedPopCount()) {
339                    Value * const limit = b->CreateSub(capacity, priorOffset);
340                    BasicBlock * const popCountLoop = b->CreateBasicBlock();
341                    BasicBlock * const popCountDone = b->CreateBasicBlock();
342                    b->CreateBr(popCountLoop);
343
344                    b->SetInsertPoint(popCountLoop);
345                    PHINode * const strideIndex = b->CreatePHI(b->getSizeTy(), 2);
346                    strideIndex->addIncoming(b->getSize(0), copyBack);
347                    Value * const accessible = getPopCountRateItems(b, rate, strideIndex);
348                    Value * const writesToOverflow = b->CreateICmpULT(accessible, limit);
349                    b->CreateCondBr(writesToOverflow, popCountDone, popCountLoop);
350
351                    b->SetInsertPoint(popCountDone);
352                    overflowOffset = b->CreateAdd(priorOffset, accessible);
353                }
354                b->CreateNonLinearCopyFromOverflow(output, currentOffset, overflowOffset);
355            } else {
356                b->CreateCopyFromOverflow(output, currentOffset);
357            }
358
359            b->CreateBr(done);
360
361            b->SetInsertPoint(done);
362        }
363    }
364}
365
366/** ------------------------------------------------------------------------------------------------------------- *
367 * @brief hasAnotherStride
368 ** ------------------------------------------------------------------------------------------------------------- */
369inline Value * MultiBlockKernel::hasAnotherStride(const std::unique_ptr<KernelBuilder> & b) {
370    // if any binding requires linear space, then it's possible we didn't fully consume all of the input
371    Value * hasMoreStrides = nullptr;
372    if (LLVM_UNLIKELY(anyBindingRequiresLinearSpace())) {
373        // do we have enough input data for another stride?
374        hasMoreStrides = b->getTrue();
375        for (unsigned i = 0; i < mStreamSetInputs.size(); ++i) {
376            const Binding & input = mStreamSetInputs[i];
377            const ProcessingRate & rate = input.getRate();
378            const auto & name = input.getName();
379            Value * const processed = b->getNonDeferredProcessedItemCount(input);
380            Value * const avail = mInitialAvailableItemCount[i];
381            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
382                b->CreateAssert(b->CreateICmpULE(processed, avail),
383                                getName() + ": " + name + " processed data exceeds available data");
384            }
385            Value * required = nullptr;
386            if (rate.isPopCount() || rate.isNegatedPopCount()) {
387                required = b->CreateSub(getPopCountRateItems(b, rate, mNumOfStrides), mAccessibleInputItems[i]);
388            } else {
389                required = mInputStrideLength[i];
390            }
391            if (LLVM_UNLIKELY(input.hasLookahead())) {
392                required = b->CreateAdd(required, b->getSize(input.getLookahead()));
393            }
394            Value * const remaining = b->CreateSub(avail, processed);
395            Value * const hasRemainingStrides = b->CreateICmpUGE(remaining, required);
396            hasMoreStrides = b->CreateAnd(hasMoreStrides, hasRemainingStrides);
397        }
398        // even if we do not have enough input data for a full stride but it is our final stride, allow it ...
399        hasMoreStrides = b->CreateOr(hasMoreStrides, mInitiallyFinal);
400    } else {
401        hasMoreStrides = mInitiallyFinal;
402    }
403    // do we have enough output space for another stride?
404    for (unsigned i = 0; i < mStreamSetOutputs.size(); ++i) {
405        const Binding & output = mStreamSetOutputs[i];
406        const ProcessingRate & rate = output.getRate();
407        if (LLVM_UNLIKELY(rate.isUnknown())) {
408            continue;
409        }
410        const auto & name = output.getName();
411        Value * const produced = b->getNonDeferredProducedItemCount(output);
412        Value * const consumed = b->getConsumedItemCount(name);
413        Value * const unconsumed = b->CreateSub(produced, consumed);
414        Value * const capacity = b->getCapacity(name);
415        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
416            b->CreateAssert(b->CreateICmpULE(consumed, produced),
417                            getName() + ": " + name + " consumed data exceeds produced data");
418            b->CreateAssert(b->CreateICmpULE(unconsumed, capacity),
419                            getName() + ": " + name + " more data was written than its capacity allows");
420        }
421        // compute the upperbound of how much output space is needed to store another stride ...
422        Value * required = nullptr;
423        if (rate.isPopCount() || rate.isNegatedPopCount()) {
424            required = b->CreateSub(getPopCountRateItems(b, rate, mNumOfStrides), mWritableOutputItems[i]);
425        } else {
426            required = mOutputStrideLength[i];
427        }
428        Value * const remaining = b->CreateSub(capacity, unconsumed);
429        Value * const hasRemainingStrides = b->CreateICmpUGE(remaining, required);
430        hasMoreStrides = b->CreateAnd(hasMoreStrides, hasRemainingStrides);
431    }
432    #ifdef DEBUG_LOG
433    b->CallPrintInt(getName() + "_hasMoreStrides", hasMoreStrides);
434    #endif
435    return hasMoreStrides;
436}
437
438
439/** ------------------------------------------------------------------------------------------------------------- *
440 * @brief calculateDerivedItemCounts
441 ** ------------------------------------------------------------------------------------------------------------- */
442inline void MultiBlockKernel::calculateDerivedItemCounts(const std::unique_ptr<KernelBuilder> & b) {
443
444    // Update the accessible and writable item count to reflect the # of strides
445    for (unsigned i = 0; i < mStreamSetInputs.size(); i++) {
446        const Binding & input = mStreamSetInputs[i];
447        const ProcessingRate & rate = input.getRate();
448        if (rate.isFixed()) {
449            Value * const processable = b->CreateMul(mInputStrideLength[i], mNumOfStrides);
450            mAccessibleInputItems[i] = b->CreateSelect(mIsFinal, mAccessibleInputItems[i], processable);
451        } else if (rate.isPopCount() || rate.isNegatedPopCount()) {
452            Value * const strideIndex = b->CreateSub(mNumOfStrides, b->getSize(1));
453            mAccessibleInputItems[i] = getPopCountRateItems(b, rate, strideIndex);
454        }
455        #ifdef DEBUG_LOG
456        b->CallPrintInt(getName() + "_" + input.getName() + "_accessible", mAccessibleInputItems[i]);
457        #endif
458        // TODO: make it so the available item count is never changed; anything that relies on it should use the accessible item count.
459        mAvailableItemCount[i] = mAccessibleInputItems[i];
460    }
461
462    for (unsigned i = 0; i < mStreamSetOutputs.size(); i++) {
463        const Binding & output = mStreamSetOutputs[i];
464        const ProcessingRate & rate = output.getRate();
465        if (rate.isFixed()) {
466            Value * const producable = b->CreateMul(mOutputStrideLength[i], mNumOfStrides);
467            mWritableOutputItems[i] = producable; // b->CreateSelect(mIsFinal, mWritableOutputItems[i], producable);
468        } else if (rate.isPopCount() || rate.isNegatedPopCount()) {
469            Value * const strideIndex = b->CreateSub(mNumOfStrides, b->getSize(1));
470            mWritableOutputItems[i] = getPopCountRateItems(b, rate, strideIndex);
471        }
472        #ifdef DEBUG_LOG
473        b->CallPrintInt(getName() + "_" + output.getName() + "_writable", mWritableOutputItems[i]);
474        #endif
475    }
476}
477
478/** ------------------------------------------------------------------------------------------------------------- *
479 * @brief updateDerivedItemCounts
480 ** ------------------------------------------------------------------------------------------------------------- */
481inline void MultiBlockKernel::updateDerivedItemCounts(const std::unique_ptr<KernelBuilder> & b) {
482    mTreatUnsafeKernelOperationsAsErrors = false;
483    // Update the processed item counts
484    for (unsigned i = 0; i < mStreamSetInputs.size(); ++i) {
485        const Binding & input = mStreamSetInputs[i];       
486        if (hasDerivedItemCount(input)) {
487            Value * const processed = b->CreateAdd(mInitialProcessedItemCount[i], mAccessibleInputItems[i]);
488            b->setNonDeferredProcessedItemCount(input, processed);
489        }
490        #ifdef DEBUG_LOG
491        b->CallPrintInt(getName() + "_" + input.getName() + "_processed'", b->getProcessedItemCount(input.getName()));
492        #endif
493        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
494            Value * const processed = b->getNonDeferredProcessedItemCount(input);
495            Value * const newlyProcessed = b->CreateSub(processed, mInitialProcessedItemCount[i]);
496            Value * const withinCapacity = b->CreateICmpULE(newlyProcessed, mAccessibleInputItems[i]);
497            std::string tmp;
498            raw_string_ostream out(tmp);
499            out << getName() << ": \"" << input.getName() << "\" has processed more items than accessible";
500            b->CreateAssert(withinCapacity, out.str());
501        }
502    }
503    // Update the produced item counts
504    for (unsigned i = 0; i < mStreamSetOutputs.size(); ++i) {
505        const Binding & output = mStreamSetOutputs[i];
506        if (hasDerivedItemCount(output)) {
507            Value * const produced = b->CreateAdd(mInitialProducedItemCount[i], mWritableOutputItems[i]);
508            b->setNonDeferredProducedItemCount(output, produced);
509        }
510        #ifdef DEBUG_LOG
511        b->CallPrintInt(getName() + "_" + output.getName() + "_produced'", b->getProducedItemCount(output.getName()));
512        #endif
513        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
514            Value * const produced = b->getProducedItemCount(output.getName());
515            Value * const newlyProduced = b->CreateSub(produced, mInitialProducedItemCount[i]);
516            Value * const withinCapacity = b->CreateICmpULE(newlyProduced, mWritableOutputItems[i]);
517            std::string tmp;
518            raw_string_ostream out(tmp);
519            out << getName() << ": \"" << output.getName() << "\" has produced more items than writable";
520            b->CreateAssert(withinCapacity, out.str());
521        }
522    }
523    mTreatUnsafeKernelOperationsAsErrors = true;
524}
525
526/** ------------------------------------------------------------------------------------------------------------- *
527 * @brief updateFinalDerivedItemCounts
528 ** ------------------------------------------------------------------------------------------------------------- */
529inline void MultiBlockKernel::updateFinalDerivedItemCounts(const std::unique_ptr<KernelBuilder> & b) {
530
531    ProcessingRate::RateValue rateLCM(1);
532
533    bool noPrincipalStream = true;
534    bool hasFixedRateInput = false;
535
536    for (const Binding & input : mStreamSetInputs) {
537        const ProcessingRate & rate = input.getRate();
538        if (rate.isFixed()) {
539            hasFixedRateInput = true;
540            if (LLVM_UNLIKELY(input.isPrincipal())) {
541                rateLCM = rate.getRate();
542                noPrincipalStream = false;
543                break;
544            }
545            rateLCM = lcm(rateLCM, rate.getRate());
546        }
547    }
548
549    mTreatUnsafeKernelOperationsAsErrors = false;
550
551    // Update the processed item counts
552    for (unsigned i = 0; i < mStreamSetInputs.size(); ++i) {
553        const Binding & input = mStreamSetInputs[i];
554        if (hasDerivedItemCount(input)) {
555            Value * const processed = b->CreateAdd(mInitialProcessedItemCount[i], mAccessibleInputItems[i]);
556            b->setNonDeferredProcessedItemCount(input, processed);
557        }
558    }
559
560    // Update the produced item counts
561    if (hasFixedRateInput) {
562
563        bool hasFixedRateOutput = false;
564        for (const Binding & output : mStreamSetOutputs) {
565            if (LLVM_UNLIKELY(output.isDeferred())) continue;
566            const ProcessingRate & rate = output.getRate();
567            if (rate.isFixed()) {
568                rateLCM = lcm(rateLCM, rate.getRate());
569                hasFixedRateOutput = true;
570            }
571        }
572
573        if (hasFixedRateOutput) {
574
575            Value * baseInitialProcessedItemCount = nullptr;
576            Value * scaledInverseOfAvailItemCount = nullptr;
577
578            // For each Fixed output stream, this calculates:
579
580            //    CEILING(MIN(Available Item Count / Fixed Input Rate) * Fixed Output Rate)
581
582            // But avoids the possibility of overflow errors (assuming that each processed item count does not overflow)
583
584            for (unsigned i = 0; i < mStreamSetInputs.size(); ++i) {
585                const Binding & input = mStreamSetInputs[i];
586                if (noPrincipalStream || input.isPrincipal()) {
587                    const ProcessingRate & rate = input.getRate();
588                    if (rate.isFixed()) {
589                        Value * const processed0 = mInitialProcessedItemCount[i];
590                        Value * const unprocessed0 = b->CreateSub(mInitialAvailableItemCount[i], processed0);
591                        Value * const unprocessed = b->CreateMul2(unprocessed0, rateLCM / rate.getRate());
592                        scaledInverseOfAvailItemCount = b->CreateUMin(scaledInverseOfAvailItemCount, unprocessed);
593                        Value * const processed = b->CreateUDiv2(processed0, rate.getRate());
594                        baseInitialProcessedItemCount = b->CreateUMin(baseInitialProcessedItemCount, processed);
595                    }
596                }
597            }
598
599            for (const Binding & output : mStreamSetOutputs) {
600                const ProcessingRate & rate = output.getRate();
601                if (rate.isFixed() && !output.isDeferred()) {
602                    assert (baseInitialProcessedItemCount && scaledInverseOfAvailItemCount);
603                    Value * const initial = b->CreateMul2(baseInitialProcessedItemCount, rate.getRate());
604                    Value * const produced = b->CreateCeilUDiv2(scaledInverseOfAvailItemCount, rateLCM / rate.getRate());
605                    b->setProducedItemCount(output.getName(), b->CreateAdd(initial, produced));
606                }
607            }
608        }
609    }
610
611    for (const Binding & output : mStreamSetOutputs) {
612        bool hasModifiers = false;
613        for (const Attribute & attr : output.getAttributes()) {
614            if (attr.isAdd() || attr.isRoundUpTo()) {
615                hasModifiers = true;
616                break;
617            }
618        }
619        if (LLVM_UNLIKELY(hasModifiers)) {
620            Value * produced = b->getProducedItemCount(output.getName());
621            for (const Attribute & attr : output.getAttributes()) {
622                if (attr.isAdd()) {
623                    produced = b->CreateAdd(produced, b->getSize(attr.amount()));
624                } else if (attr.isRoundUpTo()) {
625                    produced = b->CreateRoundUp(produced, b->getSize(attr.amount()));
626                }
627            }
628            b->setProducedItemCount(output.getName(), produced);
629        }
630        #ifdef DEBUG_LOG
631        b->CallPrintInt(getName() + "_" + output.getName() + "_produced\"", b->getProducedItemCount(output.getName()));
632        #endif
633    }
634
635    mTreatUnsafeKernelOperationsAsErrors = true;
636
637    // verify deferred input streams have fully processed all data
638    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
639        for (const Binding & input : mStreamSetInputs) {
640            if (LLVM_UNLIKELY(input.isDeferred())) {
641                Value * const processed = b->getProcessedItemCount(input.getName());
642                Value * const available = b->getNonDeferredProcessedItemCount(input);
643                std::string tmp;
644                raw_string_ostream out(tmp);
645                out << getName() << ": deferred stream \"" << input.getName() << "\" has not processed "
646                                    "all of its available input upon termination";
647                b->CreateAssert(b->CreateICmpEQ(processed, available), out.str());
648            }
649        }
650    }
651
652}
653
654/** ------------------------------------------------------------------------------------------------------------- *
655 * @brief checkTerminationSignal
656 ** ------------------------------------------------------------------------------------------------------------- */
657inline void MultiBlockKernel::checkTerminationSignal(const std::unique_ptr<KernelBuilder> & b) {
658    if (hasAttribute(Attribute::KindId::MustExplicitlyTerminate)) {
659        mIsFinal = b->getTerminationSignal();
660    } else if (hasAttribute(Attribute::KindId::CanTerminateEarly)) {
661        mIsFinal = b->CreateOr(mIsFinal, b->getTerminationSignal());
662    }
663}
664
665/** ------------------------------------------------------------------------------------------------------------- *
666 * @brief prepareOverflowBuffers
667 ** ------------------------------------------------------------------------------------------------------------- */
668inline void MultiBlockKernel::prepareOverflowBuffers(const std::unique_ptr<KernelBuilder> & b) {
669    for (unsigned i = 0; i < mStreamSetOutputs.size(); ++i) {
670        const Binding & output = mStreamSetOutputs[i];
671        if (mustClearOverflowPriorToCopyback(output) && mStreamSetOutputBuffers[i]->supportsCopyBack()) {
672            b->CreatePrepareOverflow(output.getName());
673        }
674    }
675}
676
677/** ------------------------------------------------------------------------------------------------------------- *
678 * @brief hasDerivedItemCount
679 ** ------------------------------------------------------------------------------------------------------------- */
680bool MultiBlockKernel::hasDerivedItemCount(const Binding & binding) {
681    const ProcessingRate & rate = binding.getRate();
682    return rate.isFixed() || rate.isPopCount() || rate.isNegatedPopCount();
683}
684
685/** ------------------------------------------------------------------------------------------------------------- *
686 * @brief getPopCountRateItems
687 ** ------------------------------------------------------------------------------------------------------------- */
688Value * MultiBlockKernel::getPopCountRateItems(const std::unique_ptr<KernelBuilder> & b, const ProcessingRate & rate, Value * const strideIndex) {
689    assert (rate.isPopCount() || rate.isNegatedPopCount());
690    Port refPort;
691    unsigned refIndex = 0;
692    std::tie(refPort, refIndex) = getStreamPort(rate.getReference());
693    assert (refPort == Port::Input);
694    return b->CreateLoad(b->CreateGEP(mPopCountRateArray[refIndex], strideIndex));
695}
696
697// MULTI-BLOCK KERNEL CONSTRUCTOR
698MultiBlockKernel::MultiBlockKernel(std::string && kernelName,
699                                   Bindings && stream_inputs,
700                                   Bindings && stream_outputs,
701                                   Bindings && scalar_parameters,
702                                   Bindings && scalar_outputs,
703                                   Bindings && internal_scalars)
704: Kernel(std::move(kernelName), std::move(stream_inputs), std::move(stream_outputs), std::move(scalar_parameters), std::move(scalar_outputs), std::move(internal_scalars))
705, mInitiallyFinal(nullptr)
706, mNumOfStrides(nullptr)
707, mNumOfStridesInFinalSegment(nullptr) {
708
709}
710
711}
Note: See TracBrowser for help on using the repository browser.