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

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

Restructured MultiBlock? kernel. Removal of Swizzled buffers. Inclusion of PopCount? rates / non-linear access. Modifications to several kernels to better align them with the kernel and pipeline changes.

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->getBufferedSize(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 bufferSize = b->getBufferedSize(name);
328            Value * const priorOffset = b->CreateURem(mInitialProducedItemCount[i], bufferSize);
329            Value * const produced = b->getProducedItemCount(name);
330            Value * const currentOffset = b->CreateURem(produced, bufferSize);
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(bufferSize, 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->getBufferedSize(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->getProcessedItemCount(input.getName());
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.