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

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