source: icGREP/icgrep-devel/icgrep/kernels/kernel.cpp @ 5852

Last change on this file since 5852 was 5852, checked in by xwa163, 15 months ago
  1. Use MemCpy? instead of streamCpy when handling buffer CopyBack?
  2. Rollback change of kernel_builder
  3. Fix bug of SwizzledDeleteByPEXTkernel when input data file is large
  4. Add large test cases for character_deletion
File size: 78.1 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
6#include "kernel.h"
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 <llvm/Support/Debug.h>
26
27using namespace llvm;
28using namespace parabix;
29using namespace boost::math;
30
31namespace kernel {
32
33const std::string Kernel::DO_BLOCK_SUFFIX = "_DoBlock";
34const std::string Kernel::FINAL_BLOCK_SUFFIX = "_FinalBlock";
35const std::string Kernel::MULTI_BLOCK_SUFFIX = "_MultiBlock";
36const std::string Kernel::LOGICAL_SEGMENT_NO_SCALAR = "logicalSegNo";
37const std::string Kernel::PROCESSED_ITEM_COUNT_SUFFIX = "_processedItemCount";
38const std::string Kernel::CONSUMED_ITEM_COUNT_SUFFIX = "_consumedItemCount";
39const std::string Kernel::PRODUCED_ITEM_COUNT_SUFFIX = "_producedItemCount";
40const std::string Kernel::TERMINATION_SIGNAL = "terminationSignal";
41const std::string Kernel::BUFFER_PTR_SUFFIX = "_bufferPtr";
42const std::string Kernel::CONSUMER_SUFFIX = "_consumerLocks";
43const std::string Kernel::CYCLECOUNT_SCALAR = "CPUcycles";
44
45/** ------------------------------------------------------------------------------------------------------------- *
46 * @brief addScalar
47 ** ------------------------------------------------------------------------------------------------------------- */
48unsigned Kernel::addScalar(Type * const type, const std::string & name) {
49    if (LLVM_UNLIKELY(mKernelStateType != nullptr)) {
50        report_fatal_error("Cannot add field " + name + " to " + getName() + " after kernel state finalized");
51    }
52    if (LLVM_UNLIKELY(mKernelFieldMap.count(name))) {
53        report_fatal_error(getName() + " already contains scalar field " + name);
54    }
55    const auto index = mKernelFields.size();
56    mKernelFieldMap.emplace(name, index);
57    mKernelFields.push_back(type);
58    return index;
59}
60
61
62/** ------------------------------------------------------------------------------------------------------------- *
63 * @brief addUnnamedScalar
64 ** ------------------------------------------------------------------------------------------------------------- */
65unsigned Kernel::addUnnamedScalar(Type * const type) {
66    if (LLVM_UNLIKELY(mKernelStateType != nullptr)) {
67        report_fatal_error("Cannot add unnamed field  to " + getName() + " after kernel state finalized");
68    }
69    const auto index = mKernelFields.size();
70    mKernelFields.push_back(type);
71    return index;
72}
73
74
75/** ------------------------------------------------------------------------------------------------------------- *
76 * @brief prepareStreamSetNameMap
77 ** ------------------------------------------------------------------------------------------------------------- */
78void Kernel::prepareStreamSetNameMap() {
79    for (unsigned i = 0; i < mStreamSetInputs.size(); i++) {
80        mStreamMap.emplace(mStreamSetInputs[i].getName(), std::make_pair(Port::Input, i));
81    }
82    for (unsigned i = 0; i < mStreamSetOutputs.size(); i++) {
83        mStreamMap.emplace(mStreamSetOutputs[i].getName(), std::make_pair(Port::Output, i));
84    }
85}
86
87
88/** ------------------------------------------------------------------------------------------------------------- *
89 * @brief bindPorts
90 ** ------------------------------------------------------------------------------------------------------------- */
91void Kernel::bindPorts(const StreamSetBuffers & inputs, const StreamSetBuffers & outputs) {
92    assert (mModule == nullptr);
93    assert (mStreamSetInputBuffers.empty());
94    assert (mStreamSetOutputBuffers.empty());
95
96    if (LLVM_UNLIKELY(mStreamSetInputs.size() != inputs.size())) {
97        report_fatal_error(getName() + ": expected " + std::to_string(mStreamSetInputs.size()) +
98                           " input stream sets but was given "
99                           + std::to_string(inputs.size()));
100    }
101
102    for (unsigned i = 0; i < inputs.size(); ++i) {
103        StreamSetBuffer * const buf = inputs[i];
104        if (LLVM_UNLIKELY(buf == nullptr)) {
105            report_fatal_error(getName() + ": input stream set " + std::to_string(i)
106                               + " cannot be null");
107        }
108        buf->addConsumer(this);
109    }
110
111    if (LLVM_UNLIKELY(mStreamSetOutputs.size() != outputs.size())) {
112        report_fatal_error(getName() + ": expected " + std::to_string(mStreamSetOutputs.size())
113                           + " output stream sets but was given "
114                           + std::to_string(outputs.size()));
115    }
116
117    for (unsigned i = 0; i < outputs.size(); ++i) {
118        StreamSetBuffer * const buf = outputs[i];
119        if (LLVM_UNLIKELY(buf == nullptr)) {
120            report_fatal_error(getName() + ": output stream set " + std::to_string(i) + " cannot be null");
121        }
122        if (LLVM_LIKELY(buf->getProducer() == nullptr)) {
123            buf->setProducer(this);
124        } else {
125            report_fatal_error(getName() + ": output stream set " + std::to_string(i)
126                               + " is already produced by kernel " + buf->getProducer()->getName());
127        }
128    }
129
130    mStreamSetInputBuffers.assign(inputs.begin(), inputs.end());
131    mStreamSetOutputBuffers.assign(outputs.begin(), outputs.end());
132}
133
134
135/** ------------------------------------------------------------------------------------------------------------- *
136 * @brief getCacheName
137 ** ------------------------------------------------------------------------------------------------------------- */
138std::string Kernel::getCacheName(const std::unique_ptr<KernelBuilder> & idb) const {
139    std::stringstream cacheName;
140    cacheName << getName() << '_' << idb->getBuilderUniqueName();
141    for (const StreamSetBuffer * b: mStreamSetInputBuffers) {
142        cacheName <<  ':' <<  b->getUniqueID();
143    }
144    for (const StreamSetBuffer * b: mStreamSetOutputBuffers) {
145        cacheName <<  ':' <<  b->getUniqueID();
146    }
147    return cacheName.str();
148}
149
150
151/** ------------------------------------------------------------------------------------------------------------- *
152 * @brief setModule
153 ** ------------------------------------------------------------------------------------------------------------- */
154Module * Kernel::setModule(Module * const module) {
155    assert (mModule == nullptr || mModule == module);
156    assert (module != nullptr);
157    mModule = module;
158    return mModule;
159}
160
161
162/** ------------------------------------------------------------------------------------------------------------- *
163 * @brief makeModule
164 ** ------------------------------------------------------------------------------------------------------------- */
165Module * Kernel::makeModule(const std::unique_ptr<kernel::KernelBuilder> & idb) {
166    Module * m = new Module(getCacheName(idb), idb->getContext());
167    m->setTargetTriple(idb->getModule()->getTargetTriple());
168    m->setDataLayout(idb->getModule()->getDataLayout());
169    return setModule(m);
170}
171
172
173/** ------------------------------------------------------------------------------------------------------------- *
174 * @brief prepareKernel
175 ** ------------------------------------------------------------------------------------------------------------- */
176void Kernel::prepareKernel(const std::unique_ptr<KernelBuilder> & idb) {
177    assert ("KernelBuilder does not have a valid IDISA Builder" && idb);
178    if (LLVM_UNLIKELY(mKernelStateType != nullptr)) {
179        report_fatal_error(getName() + ": cannot prepare kernel after kernel state finalized");
180    }
181    addBaseKernelProperties(idb);
182    addInternalKernelProperties(idb);
183    // NOTE: StructType::create always creates a new type even if an identical one exists.
184    if (LLVM_UNLIKELY(mModule == nullptr)) {
185        makeModule(idb);
186    }
187    mKernelStateType = mModule->getTypeByName(getName());
188    if (LLVM_LIKELY(mKernelStateType == nullptr)) {
189        mKernelStateType = StructType::create(idb->getContext(), mKernelFields, getName());
190        assert (mKernelStateType);
191    }
192}
193
194
195/** ------------------------------------------------------------------------------------------------------------- *
196 * @brief prepareCachedKernel
197 ** ------------------------------------------------------------------------------------------------------------- */
198void Kernel::prepareCachedKernel(const std::unique_ptr<KernelBuilder> & idb) {
199    assert ("KernelBuilder does not have a valid IDISA Builder" && idb);
200    if (LLVM_UNLIKELY(mKernelStateType != nullptr)) {
201        report_fatal_error(getName() + ": cannot prepare kernel after kernel state finalized");
202    }
203    assert (getModule());
204    addBaseKernelProperties(idb);
205    mKernelStateType = getModule()->getTypeByName(getName());
206    if (LLVM_UNLIKELY(mKernelStateType == nullptr)) {
207        report_fatal_error("Kernel definition for " + getName() + " could not be found in the cache object");
208    }
209}
210
211/** ------------------------------------------------------------------------------------------------------------- *
212 * @brief addBaseKernelProperties
213 ** ------------------------------------------------------------------------------------------------------------- */
214void Kernel::addBaseKernelProperties(const std::unique_ptr<KernelBuilder> & idb) {
215
216    if (mStreamMap.empty()) {
217        prepareStreamSetNameMap();
218    }
219
220    normalizeStreamProcessingRates();
221
222    const unsigned inputSetCount = mStreamSetInputs.size();
223    const unsigned outputSetCount = mStreamSetOutputs.size();
224
225    assert (inputSetCount == mStreamSetInputBuffers.size());
226    assert (outputSetCount == mStreamSetOutputBuffers.size());
227
228    if (mStride == 0) {
229        // Set the default kernel stride.
230        mStride = idb->getBitBlockWidth();
231    }
232
233    IntegerType * const sizeTy = idb->getSizeTy();
234
235    for (unsigned i = 0; i < inputSetCount; i++) {
236        const Binding & b = mStreamSetInputs[i];
237        //const ProcessingRate & rate = b.getRate();
238        //if (rate.isBounded() || rate.isUnknown()) {
239            addScalar(sizeTy, b.getName() + PROCESSED_ITEM_COUNT_SUFFIX);
240        //}
241    }
242
243    for (unsigned i = 0; i < outputSetCount; i++) {
244        const Binding & b = mStreamSetOutputs[i];
245        //const ProcessingRate & rate = b.getRate();
246        //if (rate.isBounded() || rate.isUnknown()) {
247            addScalar(sizeTy, b.getName() + PRODUCED_ITEM_COUNT_SUFFIX);
248        //}
249    }
250
251    for (unsigned i = 0; i < inputSetCount; i++) {
252        mScalarInputs.emplace_back(mStreamSetInputBuffers[i]->getStreamSetHandle()->getType(), mStreamSetInputs[i].getName() + BUFFER_PTR_SUFFIX);
253    }
254    for (unsigned i = 0; i < outputSetCount; i++) {
255        mScalarInputs.emplace_back(mStreamSetOutputBuffers[i]->getStreamSetHandle()->getType(), mStreamSetOutputs[i].getName() + BUFFER_PTR_SUFFIX);
256    }
257    for (const auto & binding : mScalarInputs) {
258        addScalar(binding.getType(), binding.getName());
259    }
260    for (const auto & binding : mScalarOutputs) {
261        addScalar(binding.getType(), binding.getName());
262    }
263    for (const auto & binding : mInternalScalars) {
264        addScalar(binding.getType(), binding.getName());
265    }
266    Type * const consumerSetTy = StructType::get(idb->getContext(), {sizeTy, sizeTy->getPointerTo()->getPointerTo()})->getPointerTo();
267    for (unsigned i = 0; i < mStreamSetOutputs.size(); i++) {
268        addScalar(consumerSetTy, mStreamSetOutputs[i].getName() + CONSUMER_SUFFIX);
269    }
270    addScalar(sizeTy, LOGICAL_SEGMENT_NO_SCALAR);
271    addScalar(sizeTy, TERMINATION_SIGNAL);
272    for (unsigned i = 0; i < mStreamSetOutputs.size(); i++) {
273        addScalar(sizeTy, mStreamSetOutputs[i].getName() + CONSUMED_ITEM_COUNT_SUFFIX);
274    }
275    // We compile in a 64-bit CPU cycle counter into every kernel.   It will remain unused
276    // in normal execution, but when codegen::EnableCycleCounter is specified, pipelines
277    // will be able to add instrumentation to cached modules without recompilation.
278    addScalar(idb->getInt64Ty(), CYCLECOUNT_SCALAR);
279
280}
281
282
283/** ------------------------------------------------------------------------------------------------------------- *
284 * @brief makeSignature
285 *
286 * Default kernel signature: generate the IR and emit as byte code.
287 ** ------------------------------------------------------------------------------------------------------------- */
288std::string Kernel::makeSignature(const std::unique_ptr<kernel::KernelBuilder> & idb) {
289    assert ("KernelBuilder does not have a valid IDISA Builder" && idb.get());
290    if (LLVM_UNLIKELY(hasSignature())) {
291        generateKernel(idb);
292        std::string signature;
293        raw_string_ostream OS(signature);
294        WriteBitcodeToFile(getModule(), OS);
295        return signature;
296    } else {
297        return getModule()->getModuleIdentifier();
298    }
299}
300
301
302/** ------------------------------------------------------------------------------------------------------------- *
303 * @brief generateKernel
304 ** ------------------------------------------------------------------------------------------------------------- */
305void Kernel::generateKernel(const std::unique_ptr<kernel::KernelBuilder> & idb) {
306    assert ("KernelBuilder does not have a valid IDISA Builder" && idb.get());
307    // If the module id cannot uniquely identify this kernel, "generateKernelSignature()" will have already
308    // generated the unoptimized IR.
309    if (!mIsGenerated) {
310        const auto m = idb->getModule();
311        const auto ip = idb->saveIP();
312        // const auto saveInstance = getInstance();
313        idb->setModule(mModule);
314        addKernelDeclarations(idb);
315        callGenerateInitializeMethod(idb);
316        callGenerateDoSegmentMethod(idb);
317        callGenerateFinalizeMethod(idb);
318        // setInstance(saveInstance);
319        idb->setModule(m);
320        idb->restoreIP(ip);
321        mIsGenerated = true;
322    }
323}
324
325
326/** ------------------------------------------------------------------------------------------------------------- *
327 * @brief callGenerateInitializeMethod
328 ** ------------------------------------------------------------------------------------------------------------- */
329inline void Kernel::callGenerateInitializeMethod(const std::unique_ptr<kernel::KernelBuilder> & idb) {
330    mCurrentMethod = getInitFunction(idb->getModule());
331    idb->SetInsertPoint(BasicBlock::Create(idb->getContext(), "entry", mCurrentMethod));
332    Function::arg_iterator args = mCurrentMethod->arg_begin();
333    setInstance(&*(args++));
334    idb->CreateStore(ConstantAggregateZero::get(mKernelStateType), getInstance());
335    for (const auto & binding : mScalarInputs) {
336        idb->setScalarField(binding.getName(), &*(args++));
337    }
338    for (const auto & binding : mStreamSetOutputs) {
339        idb->setConsumerLock(binding.getName(), &*(args++));
340    }
341    generateInitializeMethod(idb);
342    idb->CreateRetVoid();
343}
344
345/** ------------------------------------------------------------------------------------------------------------- *
346 * @brief callGenerateDoSegmentMethod
347 ** ------------------------------------------------------------------------------------------------------------- */
348inline void Kernel::callGenerateDoSegmentMethod(const std::unique_ptr<kernel::KernelBuilder> & idb) {
349    mCurrentMethod = getDoSegmentFunction(idb->getModule());
350    idb->SetInsertPoint(BasicBlock::Create(idb->getContext(), "entry", mCurrentMethod));
351    auto args = mCurrentMethod->arg_begin();
352    setInstance(&*(args++));
353    mIsFinal = &*(args++);
354    mAvailablePrincipalItemCount = nullptr;
355    const auto n = mStreamSetInputs.size();
356    mAvailableItemCount.resize(n, nullptr);
357    for (unsigned i = 0; i < n; i++) {
358        assert (args != mCurrentMethod->arg_end());
359        mAvailableItemCount[i] = &*(args++);
360    }
361    assert (args == mCurrentMethod->arg_end());
362    generateKernelMethod(idb); // must be overridden by the Kernel subtype
363    mIsFinal = nullptr;
364    mAvailableItemCount.clear();
365    idb->CreateRetVoid();
366}
367
368
369/** ------------------------------------------------------------------------------------------------------------- *
370 * @brief callGenerateFinalizeMethod
371 ** ------------------------------------------------------------------------------------------------------------- */
372inline void Kernel::callGenerateFinalizeMethod(const std::unique_ptr<KernelBuilder> & idb) {
373    mCurrentMethod = getTerminateFunction(idb->getModule());
374    idb->SetInsertPoint(BasicBlock::Create(idb->getContext(), "entry", mCurrentMethod));
375    auto args = mCurrentMethod->arg_begin();
376    setInstance(&*(args++));
377    generateFinalizeMethod(idb); // may be overridden by the Kernel subtype
378    const auto n = mScalarOutputs.size();
379    if (n == 0) {
380        idb->CreateRetVoid();
381    } else {
382        Value * outputs[n];
383        for (unsigned i = 0; i < n; ++i) {
384            outputs[i] = idb->getScalarField(mScalarOutputs[i].getName());
385        }
386        if (n == 1) {
387            idb->CreateRet(outputs[0]);
388        } else {
389            idb->CreateAggregateRet(outputs, n);
390        }
391    }
392}
393
394
395/** ------------------------------------------------------------------------------------------------------------- *
396 * @brief getScalarIndex
397 ** ------------------------------------------------------------------------------------------------------------- */
398unsigned Kernel::getScalarIndex(const std::string & name) const {
399    const auto f = mKernelFieldMap.find(name);
400    if (LLVM_UNLIKELY(f == mKernelFieldMap.end())) {
401        assert (false);
402        report_fatal_error(getName() + " does not contain scalar: " + name);
403    }
404    return f->second;
405}
406
407
408/** ------------------------------------------------------------------------------------------------------------- *
409 * @brief createInstance
410 ** ------------------------------------------------------------------------------------------------------------- */
411Value * Kernel::createInstance(const std::unique_ptr<KernelBuilder> & idb) {
412    assert ("KernelBuilder does not have a valid IDISA Builder" && idb);
413    if (LLVM_UNLIKELY(mKernelStateType == nullptr)) {
414        report_fatal_error("Cannot instantiate " + getName() + " before calling prepareKernel()");
415    }
416    setInstance(idb->CreateCacheAlignedAlloca(mKernelStateType));
417    return getInstance();
418}
419
420
421/** ------------------------------------------------------------------------------------------------------------- *
422 * @brief initializeInstance
423 ** ------------------------------------------------------------------------------------------------------------- */
424void Kernel::initializeInstance(const std::unique_ptr<KernelBuilder> & idb) {
425    assert ("KernelBuilder does not have a valid IDISA Builder" && idb);
426    if (LLVM_UNLIKELY(getInstance() == nullptr)) {
427        report_fatal_error("Cannot initialize " + getName() + " before calling createInstance()");
428    }
429    std::vector<Value *> args;
430    args.reserve(1 + mInitialArguments.size() + mStreamSetInputBuffers.size() + (mStreamSetOutputBuffers.size() * 2));
431    args.push_back(getInstance());
432    for (unsigned i = 0; i < mInitialArguments.size(); ++i) {
433        Value * arg = mInitialArguments[i];
434        if (LLVM_UNLIKELY(arg == nullptr)) {
435            report_fatal_error(getName() + ": initial argument " + std::to_string(i)
436                               + " cannot be null when calling createInstance()");
437        }
438        args.push_back(arg);
439    }
440    for (unsigned i = 0; i < mStreamSetInputBuffers.size(); ++i) {
441        assert (mStreamSetInputBuffers[i]);
442        Value * arg = mStreamSetInputBuffers[i]->getStreamSetHandle();
443        if (LLVM_UNLIKELY(arg == nullptr)) {
444            report_fatal_error(getName() + ": input stream set " + std::to_string(i)
445                               + " was not allocated prior to calling createInstance()");
446        }
447        args.push_back(arg);
448    }
449    assert (mStreamSetInputs.size() == mStreamSetInputBuffers.size());
450    for (unsigned i = 0; i < mStreamSetOutputBuffers.size(); ++i) {
451        assert (mStreamSetOutputBuffers[i]);
452        Value * arg = mStreamSetOutputBuffers[i]->getStreamSetHandle();
453        if (LLVM_UNLIKELY(arg == nullptr)) {
454            report_fatal_error(getName() + ": output stream set " + std::to_string(i)
455                               + " was not allocated prior to calling createInstance()");
456        }
457        args.push_back(arg);
458    }
459    assert (mStreamSetOutputs.size() == mStreamSetOutputBuffers.size());
460    IntegerType * const sizeTy = idb->getSizeTy();
461    PointerType * const sizePtrTy = sizeTy->getPointerTo();
462    PointerType * const sizePtrPtrTy = sizePtrTy->getPointerTo();
463    StructType * const consumerTy = StructType::get(idb->getContext(), {sizeTy, sizePtrPtrTy});
464    for (unsigned i = 0; i < mStreamSetOutputBuffers.size(); ++i) {
465        const auto output = mStreamSetOutputBuffers[i];
466        const auto & consumers = output->getConsumers();
467        const auto n = consumers.size();
468        AllocaInst * const outputConsumers = idb->CreateAlloca(consumerTy);
469        Value * const consumerSegNoArray = idb->CreateAlloca(ArrayType::get(sizePtrTy, n));
470        for (unsigned i = 0; i < n; ++i) {
471            Kernel * const consumer = consumers[i];
472            assert ("all instances must be created prior to initialization of any instance" && consumer->getInstance());
473            idb->setKernel(consumer);
474            Value * const segmentNoPtr = idb->getScalarFieldPtr(LOGICAL_SEGMENT_NO_SCALAR);
475            idb->CreateStore(segmentNoPtr, idb->CreateGEP(consumerSegNoArray, { idb->getInt32(0), idb->getInt32(i) }));
476        }
477        idb->setKernel(this);
478        Value * const consumerCountPtr = idb->CreateGEP(outputConsumers, {idb->getInt32(0), idb->getInt32(0)});
479        idb->CreateStore(idb->getSize(n), consumerCountPtr);
480        Value * const consumerSegNoArrayPtr = idb->CreateGEP(outputConsumers, {idb->getInt32(0), idb->getInt32(1)});
481        idb->CreateStore(idb->CreatePointerCast(consumerSegNoArray, sizePtrPtrTy), consumerSegNoArrayPtr);
482        args.push_back(outputConsumers);
483    }
484    idb->CreateCall(getInitFunction(idb->getModule()), args);
485}
486
487/** ------------------------------------------------------------------------------------------------------------- *
488 * @brief finalizeInstance
489 ** ------------------------------------------------------------------------------------------------------------- */
490void Kernel::finalizeInstance(const std::unique_ptr<KernelBuilder> & idb) {
491    assert ("KernelBuilder does not have a valid IDISA Builder" && idb);
492    mOutputScalarResult = idb->CreateCall(getTerminateFunction(idb->getModule()), { getInstance() });
493}
494
495/** ------------------------------------------------------------------------------------------------------------- *
496 * @brief getStreamPort
497 ** ------------------------------------------------------------------------------------------------------------- */
498Kernel::StreamPort Kernel::getStreamPort(const std::string & name) const {
499    const auto f = mStreamMap.find(name);
500    if (LLVM_UNLIKELY(f == mStreamMap.end())) {
501        report_fatal_error(getName() + " does not contain stream set " + name);
502    }
503    return f->second;
504}
505
506/** ------------------------------------------------------------------------------------------------------------- *
507 * @brief getStreamPort
508 ** ------------------------------------------------------------------------------------------------------------- */
509const Binding & Kernel::getBinding(const std::string & name) const {
510    Port port; unsigned index;
511    std::tie(port, index) = getStreamPort(name);
512    return (port == Port::Input) ? getStreamInput(index) : getStreamOutput(index);
513}
514
515/** ------------------------------------------------------------------------------------------------------------- *
516 * @brief getLowerBound
517 ** ------------------------------------------------------------------------------------------------------------- */
518ProcessingRate::RateValue Kernel::getLowerBound(const ProcessingRate & rate) const {
519    if (rate.isFixed() || rate.isBounded()) {
520        return rate.getLowerBound();
521    } else if (rate.isRelative()) {
522        return rate.getRate() * getLowerBound(getBinding(rate.getReference()).getRate());
523    } else { // if (rate.isUnknown())
524        return 0;
525    }
526}
527
528/** ------------------------------------------------------------------------------------------------------------- *
529 * @brief getUpperBound
530 ** ------------------------------------------------------------------------------------------------------------- */
531ProcessingRate::RateValue Kernel::getUpperBound(const ProcessingRate &rate) const {
532    if (rate.isFixed() || rate.isBounded()) {
533        return rate.getUpperBound();
534    } else if (rate.isRelative()) {
535        return rate.getRate() * getUpperBound(getBinding(rate.getReference()).getRate());
536    } else { // if (rate.isUnknown())
537        return 0;
538    }
539}
540
541/** ------------------------------------------------------------------------------------------------------------- *
542 * @brief normalizeRelativeToFixedProcessingRate
543 ** ------------------------------------------------------------------------------------------------------------- */
544bool Kernel::normalizeRelativeToFixedProcessingRate(const ProcessingRate & base, ProcessingRate & toUpdate) {
545    if (base.isFixed()) {
546        return true;
547    } else if (LLVM_UNLIKELY(base.isRelative())) {
548        const auto & ref = getBinding(base.getReference()).getRate();
549        if (normalizeRelativeToFixedProcessingRate(ref, toUpdate)) {
550            toUpdate.getRate() *= ref.getRate();
551            return true;
552        }
553    }
554    return false;
555}
556
557/** ------------------------------------------------------------------------------------------------------------- *
558 * @brief normalizeStreamProcessingRates
559 *
560 * If we allow a stream to be transitively relative to a fixed rate stream, it complicates detection of fixed
561 * rate streams later. Find any such occurance and transform them. This implies, however, that a fixed rate
562 * stream could have a rational processing rate (which should not occur normally.)
563 ** ------------------------------------------------------------------------------------------------------------- */
564inline void Kernel::normalizeStreamProcessingRates() {
565    for (Binding & input : mStreamSetInputs) {
566        normalizeRelativeToFixedProcessingRate(input.getRate(), input.getRate());
567    }
568    for (Binding & output : mStreamSetOutputs) {
569        normalizeRelativeToFixedProcessingRate(output.getRate(), output.getRate());
570    }
571    // TODO: we want to consume whole units. Once the pipeline is able to schedule kernels based on their stride
572    // and input/output rates, modify them here.
573}
574
575/** ------------------------------------------------------------------------------------------------------------- *
576 * @brief generateKernelMethod
577 ** ------------------------------------------------------------------------------------------------------------- */
578void SegmentOrientedKernel::generateKernelMethod(const std::unique_ptr<KernelBuilder> & b) {
579    const auto inputSetCount = mStreamSetInputs.size();
580    mStreamSetInputBaseAddress.resize(inputSetCount);
581    for (unsigned i = 0; i < inputSetCount; ++i) {
582        mStreamSetInputBaseAddress[i] = nullptr;
583    }
584    const auto outputSetCount = mStreamSetOutputs.size();
585    mStreamSetOutputBaseAddress.resize(outputSetCount);
586    for (unsigned i = 0; i < outputSetCount; ++i) {
587        mStreamSetOutputBaseAddress[i] = nullptr;
588    }
589    generateDoSegmentMethod(b);
590}
591
592/** ------------------------------------------------------------------------------------------------------------- *
593 * @brief requiresBufferedFinalStride
594 ** ------------------------------------------------------------------------------------------------------------- */
595inline bool LLVM_READNONE requiresBufferedFinalStride(const Binding & binding) {
596    if (LLVM_LIKELY(isa<ArrayType>(binding.getType()))) {
597        return binding.getType()->getArrayNumElements() == 1;
598    }
599    return true;
600}
601
602/** ------------------------------------------------------------------------------------------------------------- *
603 * @brief getItemWidth
604 ** ------------------------------------------------------------------------------------------------------------- */
605inline unsigned LLVM_READNONE getItemWidth(const Binding & b) {
606    Type * ty = b.getType();
607    if (LLVM_LIKELY(isa<ArrayType>(ty))) {
608        ty = ty->getArrayElementType();
609    }
610    return cast<IntegerType>(ty->getVectorElementType())->getBitWidth();
611}
612
613/** ------------------------------------------------------------------------------------------------------------- *
614 * @brief isTransitivelyUnknownRate
615 ** ------------------------------------------------------------------------------------------------------------- */
616bool LLVM_READNONE MultiBlockKernel::isTransitivelyUnknownRate(const ProcessingRate & rate) const {
617    if (rate.isUnknown()) {
618        return true;
619    } else if (rate.isDerived()) {
620        return isTransitivelyUnknownRate(getBinding(rate.getReference()).getRate());
621    }
622    return false;
623}
624
625/** ------------------------------------------------------------------------------------------------------------- *
626 * @brief requiresTemporaryInputBuffer
627 ** ------------------------------------------------------------------------------------------------------------- */
628inline bool LLVM_READNONE MultiBlockKernel::requiresTemporaryInputBuffer(const Binding & binding, const ProcessingRate & rate) const {
629    if (requiresBufferedFinalStride(binding)) {
630        return true;
631    } else if (LLVM_UNLIKELY(isTransitivelyUnknownRate(rate))) {
632        report_fatal_error("MultiBlock kernels do not support unknown rate input streams or streams relative to an unknown rate input.");
633    } else {
634        return !rate.isFixed();
635    }
636}
637
638/** ------------------------------------------------------------------------------------------------------------- *
639 * @brief requiresTemporaryOutputBuffer
640 ** ------------------------------------------------------------------------------------------------------------- */
641inline bool LLVM_READNONE MultiBlockKernel::requiresTemporaryOutputBuffer(const Binding & binding, const ProcessingRate & rate) const {
642    if (requiresBufferedFinalStride(binding)) {
643        return true;
644    } else {
645        return !(rate.isFixed() || isTransitivelyUnknownRate(rate));
646    }
647}
648
649/** ------------------------------------------------------------------------------------------------------------- *
650 * @brief getItemAlignment
651 ** ------------------------------------------------------------------------------------------------------------- */
652inline unsigned LLVM_READNONE MultiBlockKernel::getItemAlignment(const Binding & binding) const {
653    const auto & rate = binding.getRate();
654    if (rate.isFixed() && binding.nonDeferred() && !binding.isMisaligned()) {
655        const auto r = rate.getRate();
656        auto n = (r.numerator() * mStride);
657        if (LLVM_LIKELY(r.denominator() == 1)) {
658            return n;
659        } else if (LLVM_LIKELY((n % r.denominator()) == 0)) {
660            return n / r.denominator();
661        }
662    }
663    return 1; // ∀x GCD(x, x + 1) = 1
664}
665
666/** ------------------------------------------------------------------------------------------------------------- *
667 * @brief getCopyAlignment
668 ** ------------------------------------------------------------------------------------------------------------- */
669inline unsigned LLVM_READNONE MultiBlockKernel::getCopyAlignment(const Binding & binding) const {
670    return ((getItemAlignment(binding) * getItemWidth(binding)) + 7) / 8;
671}
672
673/** ------------------------------------------------------------------------------------------------------------- *
674 * @brief getStrideSize
675 ** ------------------------------------------------------------------------------------------------------------- */
676llvm::Value * LLVM_READNONE MultiBlockKernel::getStrideSize(const std::unique_ptr<KernelBuilder> & b, const ProcessingRate & rate) {
677    // NOTE: if we ever support feedback loops, using upper bound could lead to a deadlock due to data starvation
678    const auto r = getUpperBound(rate);
679    if (r.numerator() == 0) {
680        return nullptr;
681    } else {
682        assert ((r.numerator() * mStride) % r.denominator() == 0);
683        return b->getSize((r.numerator() * mStride) / r.denominator());
684    }
685}
686
687/** ------------------------------------------------------------------------------------------------------------- *
688 * @brief generateKernelMethod
689 ** ------------------------------------------------------------------------------------------------------------- */
690void MultiBlockKernel::generateKernelMethod(const std::unique_ptr<KernelBuilder> & b) {
691
692    if (LLVM_UNLIKELY((mStride % b->getBitBlockWidth()) != 0)) {
693        report_fatal_error(getName() + ": the Stride (" + std::to_string(mStride) + ") of MultiBlockKernel "
694                           "must be a multiple of the BitBlockWidth (" + std::to_string(b->getBitBlockWidth()) + ")");
695    }
696
697    using RateValue = ProcessingRate::RateValue;
698
699    const auto inputSetCount = mStreamSetInputs.size();
700    const auto outputSetCount = mStreamSetOutputs.size();
701
702    // Define and allocate the temporary buffer area in the prolog.   
703    const auto blockAlignment = b->getBitBlockWidth() / 8;
704    AllocaInst * temporaryInputBuffer[inputSetCount];
705    for (unsigned i = 0; i < inputSetCount; ++i) {       
706        const Binding & input = mStreamSetInputs[i];
707        const ProcessingRate & rate = input.getRate();
708        temporaryInputBuffer[i] = nullptr;
709        if (requiresTemporaryInputBuffer(input, rate)) {
710            Type * const ty = mStreamSetInputBuffers[i]->getStreamSetBlockType();
711            auto ub = getUpperBound(rate);
712            if (LLVM_UNLIKELY(input.hasLookahead())) {
713                ub += RateValue(input.getLookahead(), mStride);
714            }
715            Constant * const arraySize = b->getInt64(ceiling(ub));
716            AllocaInst * const ptr = b->CreateAlignedAlloca(ty, blockAlignment, arraySize);
717            assert (ptr->isStaticAlloca());
718            temporaryInputBuffer[i] = ptr;
719        }
720    }
721
722    AllocaInst * temporaryOutputBuffer[outputSetCount];
723    for (unsigned i = 0; i < outputSetCount; i++) {
724        const Binding & output = mStreamSetOutputs[i];
725        const ProcessingRate & rate = output.getRate();
726        temporaryOutputBuffer[i] = nullptr;
727        if (requiresTemporaryOutputBuffer(output, rate)) {
728            auto ub = getUpperBound(rate);
729            if (LLVM_UNLIKELY(mStreamSetOutputBuffers[i]->supportsCopyBack() && requiresCopyBack(rate))) {
730                ub += mStreamSetOutputBuffers[i]->overflowSize();
731            }
732            Type * const ty = mStreamSetOutputBuffers[i]->getStreamSetBlockType();
733            Constant * const arraySize = b->getInt64(ceiling(ub));
734            AllocaInst * const ptr = b->CreateAlignedAlloca(ty, blockAlignment, arraySize);
735            assert (ptr->isStaticAlloca());
736            temporaryOutputBuffer[i] = ptr;
737        }
738    }
739
740    Constant * const ZERO = b->getSize(0);
741    Constant * const ONE = b->getSize(1);
742    Constant * const LOG_2_BLOCK_WIDTH = b->getSize(std::log2(b->getBitBlockWidth()));
743    Constant * const BLOCK_WIDTH_MASK = b->getSize(b->getBitBlockWidth() - 1);
744
745    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
746        Value * terminatedTwice = b->CreateAnd(mIsFinal, b->getTerminationSignal());
747        Value * unprocessedData = nullptr;
748        for (unsigned i = 0; i < inputSetCount; i++) {
749            Value * processed = b->getProcessedItemCount(mStreamSetInputs[i].getName());
750            Value * const check = b->CreateICmpNE(processed, mAvailableItemCount[i]);
751            unprocessedData = unprocessedData ? b->CreateOr(unprocessedData, check) : check;
752        }
753        b->CreateAssertZero(b->CreateAnd(terminatedTwice, unprocessedData),
754                            getName() + " was called after its termination with additional input data");
755        b->CreateAssertZero(terminatedTwice,
756                            getName() + " was called after its termination");
757    }
758
759    mInitialAvailableItemCount.assign(mAvailableItemCount.begin(), mAvailableItemCount.end());
760    mInitialProcessedItemCount.resize(inputSetCount);
761    mStreamSetInputBaseAddress.resize(inputSetCount);
762
763    // Now proceed with creation of the doSegment method.
764    BasicBlock * const segmentLoop = b->CreateBasicBlock("SegmentLoop");
765
766    b->CreateBr(segmentLoop);
767
768    /// DO SEGMENT LOOP
769
770    b->SetInsertPoint(segmentLoop);
771
772    Value * numOfStrides = nullptr;
773
774    // TODO: we don't want the our available output space to limit how many conditional blocks we
775    // can check. When we have a conditional region, split computation of input/output strides and
776    // check as many input strides as possible but leave the kernel in a state that respects our
777    // available output space. NOTE: we know coming into this block that the pipeline or kernel has
778    // ensured there is at least one stride worth of space.
779
780
781    // For each input buffer, get the initial processed item count, base input pointer, and the number of
782    // linearly available strides.
783    Value * inputStrideSize[inputSetCount];
784    Value * linearlyAccessible[inputSetCount];
785    for (unsigned i = 0; i < inputSetCount; i++) {
786        const Binding & input = mStreamSetInputs[i];
787        const auto & name = input.getName();
788        Value * const processed = b->getProcessedItemCount(name);
789        mInitialProcessedItemCount[i] = processed;
790        mStreamSetInputBaseAddress[i] = b->getBlockAddress(name, b->CreateLShr(processed, LOG_2_BLOCK_WIDTH));
791        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
792            b->CreateAssert(b->CreateICmpULE(processed, mAvailableItemCount[i]),
793                            getName() + ": " + name + " processed item count exceeds its available item count");
794        }
795        Value * const unprocessed = b->CreateNUWSub(mAvailableItemCount[i], processed);
796        mAvailableItemCount[i] = unprocessed;
797        Value * const accessible = b->getLinearlyAccessibleItems(name, processed, unprocessed);
798        linearlyAccessible[i] = accessible;
799        inputStrideSize[i] = getStrideSize(b, input.getRate());
800        Value * const accessibleStrides = b->CreateUDiv(accessible, inputStrideSize[i]);
801        numOfStrides = b->CreateUMin(numOfStrides, accessibleStrides);
802    }
803
804    BasicBlock * const checkInputAvailability = b->CreateBasicBlock("CheckInputAvailability");
805    BasicBlock * const selectOutputBuffers = b->CreateBasicBlock("SelectOutputBuffers");
806    b->CreateLikelyCondBr(b->CreateICmpNE(numOfStrides, ZERO), selectOutputBuffers, checkInputAvailability);
807
808    // Ensure that everything between S⌈P/S⌉ and S⌈n*(P + L)/S⌉ is linearly available, where S is the stride size,
809    // P is the current processed position, L is the lookahead amount and n is our number of accessible strides ∈ â„€+.
810    b->SetInsertPoint(checkInputAvailability);
811    Value * const initiallyFinal = mIsFinal;
812    Value * linearlyCopyable[inputSetCount];
813    PHINode * selectedInputBuffer[inputSetCount];
814    for (unsigned i = 0; i < inputSetCount; i++) {
815        AllocaInst * const tempBuffer = temporaryInputBuffer[i];
816        selectedInputBuffer[i] = nullptr;
817        if (tempBuffer) {
818
819            const Binding & input = mStreamSetInputs[i];
820            const auto & name = input.getName();
821            Value * const processed = mInitialProcessedItemCount[i];
822            Value * const unprocessed = mAvailableItemCount[i];
823            Value * const accessible = linearlyAccessible[i];
824
825            BasicBlock * const entry = b->GetInsertBlock();
826            BasicBlock * const copyFromBack = b->CreateBasicBlock(name + "CopyFromBack");
827            BasicBlock * const copyFromFront = b->CreateBasicBlock(name + "CopyFromFront");
828            BasicBlock * const resume = b->CreateBasicBlock(name + "Resume");
829
830            Value * strideSize = inputStrideSize[i];
831            if (LLVM_UNLIKELY(input.hasLookahead())) {
832                Constant * const lookahead = b->getSize(input.getLookahead());
833                strideSize = b->CreateNUWAdd(strideSize, lookahead);
834            }
835            Value * const requiresCopy = b->CreateICmpULT(accessible, strideSize);
836            b->CreateUnlikelyCondBr(requiresCopy, copyFromBack, resume);
837
838            b->SetInsertPoint(copyFromBack);
839            Value * const arraySize = b->CreateZExt(tempBuffer->getArraySize(), b->getInt64Ty());
840            Value * const temporarySize = b->CreateTrunc(b->CreateMul(arraySize, b->getInt64(mStride)), accessible->getType());
841            Value * const copyable = b->CreateUMin(unprocessed, temporarySize); // <- we only really need strideSize items
842            Value * const offset = b->CreateAnd(processed, BLOCK_WIDTH_MASK);
843            Value * const bufferSize = b->CreateMul(ConstantExpr::getSizeOf(tempBuffer->getAllocatedType()), arraySize);
844            b->CreateMemZero(tempBuffer, bufferSize, blockAlignment);
845            b->CreateStreamCpy(name, tempBuffer, ZERO, mStreamSetInputBaseAddress[i], offset, accessible, getItemAlignment(input));
846            BasicBlock * const copyToBackEnd = b->GetInsertBlock();
847            b->CreateCondBr(b->CreateICmpNE(copyable, accessible), copyFromFront, resume);
848
849            b->SetInsertPoint(copyFromFront);
850            Value * const remaining = b->CreateSub(copyable, accessible);
851            Value * const baseAddress = b->getBaseAddress(name);
852            b->CreateStreamCpy(name, tempBuffer, accessible, baseAddress, ZERO, remaining, getItemAlignment(input));
853            Value * const isPartialStride = b->CreateICmpUGE(copyable, strideSize);
854            BasicBlock * const copyToFrontEnd = b->GetInsertBlock();
855            b->CreateBr(resume);
856
857            b->SetInsertPoint(resume);
858            PHINode * const address = b->CreatePHI(tempBuffer->getType(), 3);
859            address->addIncoming(mStreamSetInputBaseAddress[i], entry);
860            address->addIncoming(tempBuffer, copyToBackEnd);
861            address->addIncoming(tempBuffer, copyToFrontEnd);
862            selectedInputBuffer[i] = address;
863            PHINode * const available = b->CreatePHI(accessible->getType(), 3);
864            available->addIncoming(accessible, entry);
865            available->addIncoming(copyable, copyToBackEnd);
866            available->addIncoming(copyable, copyToFrontEnd);
867            linearlyCopyable[i] = available;
868            PHINode * const finalStride = b->CreatePHI(b->getInt1Ty(), 3);
869            finalStride->addIncoming(mIsFinal, entry);
870            finalStride->addIncoming(b->getTrue(), copyToBackEnd);
871            finalStride->addIncoming(isPartialStride, copyToFrontEnd);
872            mIsFinal = finalStride;
873            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
874                Value * const hasStride = b->CreateOr(initiallyFinal, b->CreateNot(finalStride));
875                b->CreateAssert(hasStride, getName() + ": " + name + " has insufficient input data for one stride");
876            }
877        }
878    }
879
880    BasicBlock * const endCheckInputAvailability = b->GetInsertBlock();
881    selectOutputBuffers->moveAfter(endCheckInputAvailability);
882    b->CreateBr(selectOutputBuffers);
883
884    b->SetInsertPoint(selectOutputBuffers);
885    PHINode * const final = b->CreatePHI(mIsFinal->getType(), 2);
886    final->addIncoming(b->getFalse(), segmentLoop);
887    final->addIncoming(mIsFinal, endCheckInputAvailability);
888    mIsFinal = final;
889    for (unsigned i = 0; i < inputSetCount; i++) {
890        if (selectedInputBuffer[i]) {
891            PHINode * const address = b->CreatePHI(selectedInputBuffer[i]->getType(), 2);
892            address->addIncoming(mStreamSetInputBaseAddress[i], segmentLoop);
893            address->addIncoming(selectedInputBuffer[i], endCheckInputAvailability);
894            mStreamSetInputBaseAddress[i] = address;
895            PHINode * const accessible = b->CreatePHI(linearlyAccessible[i]->getType(), 2);
896            accessible->addIncoming(linearlyAccessible[i], segmentLoop);
897            accessible->addIncoming(linearlyCopyable[i], endCheckInputAvailability);
898            linearlyAccessible[i] = accessible;
899        }
900    }
901    PHINode * const strides = b->CreatePHI(numOfStrides->getType(), 2);
902    strides->addIncoming(numOfStrides, segmentLoop);
903    strides->addIncoming(ONE, endCheckInputAvailability);
904    numOfStrides = strides;
905
906    // Now determine the linearly writeable strides
907    Value * outputStrideSize[outputSetCount];
908    Value * linearlyWritable[outputSetCount];
909    mInitialProducedItemCount.resize(outputSetCount);
910    mStreamSetOutputBaseAddress.resize(outputSetCount);
911    for (unsigned i = 0; i < outputSetCount; i++) {
912        const auto & output = mStreamSetOutputs[i];
913        const auto & name = output.getName();
914        Value * const produced = b->getProducedItemCount(name);
915        Value * baseBuffer = b->getBlockAddress(name, b->CreateLShr(produced, LOG_2_BLOCK_WIDTH));
916        mInitialProducedItemCount[i] = produced;
917        mStreamSetOutputBaseAddress[i] = baseBuffer;
918
919        // Is the number of linearly writable items sufficient for a stride?
920        outputStrideSize[i] = getStrideSize(b, output.getRate());
921        if (outputStrideSize[i]) {
922            linearlyWritable[i] = b->getLinearlyWritableItems(name, produced);
923            Value * writableStrides = b->CreateUDiv(linearlyWritable[i], outputStrideSize[i]);
924            numOfStrides = b->CreateUMin(numOfStrides, writableStrides);
925            // Do we require a temporary buffer to write to?
926            AllocaInst * const tempBuffer = temporaryOutputBuffer[i];
927            if (tempBuffer) {
928                assert (tempBuffer->getType() == baseBuffer->getType());
929                BasicBlock * const entry = b->GetInsertBlock();
930                BasicBlock * const prepareTempBuffer = b->CreateBasicBlock(name + "PrepareTempBuffer");
931                BasicBlock * const resume = b->CreateBasicBlock(name + "Resume");
932                Value * const requiresCopy = b->CreateICmpEQ(writableStrides, ZERO);
933                b->CreateUnlikelyCondBr(requiresCopy, prepareTempBuffer, resume);
934                // Clear the output buffer prior to using it
935                b->SetInsertPoint(prepareTempBuffer);
936                Value * const bufferSize = b->CreateMul(ConstantExpr::getSizeOf(tempBuffer->getAllocatedType()), tempBuffer->getArraySize());
937                b->CreateMemZero(tempBuffer, bufferSize, blockAlignment);
938                b->CreateBr(resume);
939                // Select the appropriate buffer / stride #
940                b->SetInsertPoint(resume);
941                PHINode * const phiBuffer = b->CreatePHI(baseBuffer->getType(), 3);
942                phiBuffer->addIncoming(baseBuffer, entry);
943                phiBuffer->addIncoming(tempBuffer, prepareTempBuffer);
944                baseBuffer = phiBuffer;
945                PHINode * const phiStrides = b->CreatePHI(b->getSizeTy(), 2);
946                phiStrides->addIncoming(numOfStrides, entry);
947                phiStrides->addIncoming(ONE, prepareTempBuffer);
948                numOfStrides = phiStrides;
949            }
950            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
951                b->CreateAssert(numOfStrides, getName() + ": " + name + " has insufficient output space for one stride");
952            }
953        }
954    }
955
956    // Update the locally available item count to reflect the current state
957    for (unsigned i = 0; i < inputSetCount; i++) {
958        const Binding & input = mStreamSetInputs[i];
959        if (input.getRate().isFixed() && input.nonDeferred()) {
960            Value * const processable = b->CreateMul(numOfStrides, inputStrideSize[i]);
961            linearlyAccessible[i] = b->CreateSelect(mIsFinal, linearlyAccessible[i], processable);
962        }
963        mAvailableItemCount[i] = linearlyAccessible[i];
964    }
965
966    //  We have one or more strides of input data and output buffer space for all stream sets.
967    generateMultiBlockLogic(b, numOfStrides);
968
969    for (unsigned i = 0; i < inputSetCount; ++i) {
970        const auto & input = mStreamSetInputs[i];
971        const ProcessingRate & rate = input.getRate();
972        if (rate.isFixed() && input.nonDeferred()) {
973            Value * const ic = b->CreateAdd(mInitialProcessedItemCount[i], mAvailableItemCount[i]);
974            b->setProcessedItemCount(input.getName(), ic);
975        }
976    }
977
978    for (unsigned i = 0; i < outputSetCount; ++i) {
979        const auto & output = mStreamSetOutputs[i];
980        const ProcessingRate & rate = output.getRate();
981        if (rate.isFixed()) {
982            Value * const produced = b->CreateMul(numOfStrides, outputStrideSize[i]);
983            Value * const ic = b->CreateNUWAdd(mInitialProducedItemCount[i], produced);
984            b->setProducedItemCount(output.getName(), ic);
985        }
986    }
987
988    BasicBlock * const handleFinalBlock = b->CreateBasicBlock("HandleFinalBlock");
989    BasicBlock * const temporaryBufferCopyBack = b->CreateBasicBlock("TemporaryBufferCopyBack");
990    BasicBlock * const strideDone = b->CreateBasicBlock("MultiBlockDone");
991
992    b->CreateUnlikelyCondBr(mIsFinal, handleFinalBlock, temporaryBufferCopyBack);
993
994
995    /// FINAL STRIDE ADJUSTMENT
996    b->SetInsertPoint(handleFinalBlock);
997
998    // If this is our final stride, adjust the Fixed output item counts. The main loop assumes that
999    // the ITEM COUNT % FIXED RATE = 0 for all Fixed Input and Output streams. We correct that here
1000    // to calculate them based on the actual input item counts.
1001
1002    reviseFinalProducedItemCounts(b);
1003
1004    b->CreateBr(temporaryBufferCopyBack);
1005
1006    /// TEMPORARY BUFFER COPY BACK
1007    b->SetInsertPoint(temporaryBufferCopyBack);
1008
1009    // Copy back data to the actual output buffers.
1010    for (unsigned i = 0; i < outputSetCount; i++) {
1011
1012        AllocaInst * const tempBuffer = temporaryOutputBuffer[i];
1013        if (LLVM_UNLIKELY(tempBuffer == nullptr)) {
1014            continue;
1015        }
1016
1017        const auto & name = mStreamSetOutputs[i].getName();
1018        Value * const produced = b->getProducedItemCount(name);
1019        Value * const baseBuffer = mStreamSetOutputBaseAddress[i];
1020        assert ("stack corruption likely" && (tempBuffer->getType() == baseBuffer->getType()));
1021        //const auto & name = mStreamSetOutputs[i].getName();
1022        BasicBlock * const copyToBack = b->CreateBasicBlock(name + "CopyToBack");
1023        BasicBlock * const copyToFront = b->CreateBasicBlock(name + "CopyToFront");
1024        BasicBlock * const resume = b->CreateBasicBlock(name + "ResumeCopyBack");
1025        // If we used a temporary buffer, copy it back to the original output buffer
1026        Value * const requiresCopy = b->CreateICmpEQ(tempBuffer, baseBuffer);
1027        b->CreateCondBr(requiresCopy, copyToBack, resume);
1028
1029        b->SetInsertPoint(copyToBack);       
1030        Value * const offset = b->CreateAnd(mInitialProducedItemCount[i], BLOCK_WIDTH_MASK);
1031        //Value * const newProducedItemCount = b->getProducedItemCount(name);
1032        Value * const newlyProduced = b->CreateNUWSub(produced, mInitialProducedItemCount[i]);
1033        Value * const toWrite = b->CreateUMin(newlyProduced, linearlyWritable[i]);
1034        const auto alignment = getItemAlignment(mStreamSetOutputs[i]);
1035        b->CreateStreamCpy(name, baseBuffer, offset, tempBuffer, ZERO, toWrite, alignment);
1036        // If we required a temporary output buffer, we will probably need to write to the beginning of the buffer as well.
1037        b->CreateLikelyCondBr(b->CreateICmpULT(toWrite, newlyProduced), copyToFront, resume);
1038
1039        b->SetInsertPoint(copyToFront);
1040        Value * const remaining = b->CreateNUWSub(newlyProduced, toWrite);
1041        Value * const baseAddress = b->getBaseAddress(name);
1042        b->CreateStreamCpy(name, baseAddress, ZERO, tempBuffer, toWrite, remaining, alignment);
1043        b->CreateBr(resume);
1044
1045        b->SetInsertPoint(resume);
1046    }
1047
1048    //  We've dealt with the partial block processing and copied information back into the
1049    //  actual buffers.  If this isn't the final block, loop back for more multiblock processing.
1050    BasicBlock * const setTermination = b->CreateBasicBlock("setTermination");
1051    b->CreateCondBr(mIsFinal, setTermination, strideDone);
1052    b->SetInsertPoint(setTermination);
1053    b->setTerminationSignal();
1054    BasicBlock * const segmentDone = b->CreateBasicBlock("SegmentDone");
1055    b->CreateBr(segmentDone);
1056
1057    /// STRIDE DONE
1058    strideDone->moveAfter(b->GetInsertBlock());
1059    b->SetInsertPoint(strideDone);
1060
1061    // do we have enough data for another stride?
1062    Value * hasMoreStrides = b->getTrue();
1063    for (unsigned i = 0; i < inputSetCount; ++i) {
1064        const Binding & input = mStreamSetInputs[i];
1065        const auto & name = input.getName();
1066        Value * const avail = mInitialAvailableItemCount[i];
1067        Value * const processed = b->getProcessedItemCount(name);
1068        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1069            b->CreateAssert(b->CreateICmpULE(processed, avail), getName() + ": " + name + " processed data exceeds available data");
1070        }
1071        Value * remaining = b->CreateSub(avail, processed);
1072        Value * strideSize = inputStrideSize[i];
1073        if (LLVM_UNLIKELY(input.hasLookahead())) {
1074            strideSize = b->CreateNUWAdd(strideSize, b->getSize(input.getLookahead()));
1075        }
1076        Value * const hasRemainingStrides = b->CreateICmpUGE(remaining, strideSize);
1077        hasMoreStrides = b->CreateAnd(hasMoreStrides, hasRemainingStrides);
1078    }
1079    // even if we do not have enough input data for a full stride, if this is our final stride, allow it ...
1080    hasMoreStrides = b->CreateOr(hasMoreStrides, initiallyFinal);
1081
1082    // do we have enough room for another stride?
1083    for (unsigned i = 0; i < outputSetCount; ++i) {
1084        const ProcessingRate & rate = mStreamSetOutputs[i].getRate();
1085        const auto & name = mStreamSetOutputs[i].getName();
1086        Value * const produced = b->getProducedItemCount(name);
1087        // If this output has a Fixed/Bounded rate, determine whether we have room for another stride.
1088        if (LLVM_LIKELY(outputStrideSize[i] != nullptr)) {
1089            Value * const consumed = b->getConsumedItemCount(name);
1090            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1091                b->CreateAssert(b->CreateICmpULE(consumed, produced),
1092                                getName() + ": " + name + " consumed data exceeds produced data");
1093            }
1094            Value * const unconsumed = b->CreateSub(produced, consumed);
1095            Value * const capacity = b->getCapacity(name);
1096            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1097                b->CreateAssert(b->CreateICmpULE(unconsumed, capacity),
1098                                getName() + ": " + name + " unconsumed data exceeds capacity");
1099            }
1100            Value * const remaining = b->CreateSub(capacity, unconsumed);
1101            Value * const hasRemainingStrides = b->CreateICmpUGE(remaining, outputStrideSize[i]);
1102            hasMoreStrides = b->CreateAnd(hasMoreStrides, hasRemainingStrides);
1103        }
1104        // Do copybacks if necessary.
1105        if (mStreamSetOutputBuffers[i]->supportsCopyBack() && requiresCopyBack(rate)) {
1106            BasicBlock * const copyBack = b->CreateBasicBlock(name + "CopyBack");
1107            BasicBlock * const done = b->CreateBasicBlock(name + "CopyBackDone");
1108
1109            Value * const bufferSize = b->getBufferedSize(name);
1110            Value * const prior = b->CreateURem(mInitialProducedItemCount[i], bufferSize);
1111            Value * const current = b->CreateURem(produced, bufferSize);
1112            b->CreateUnlikelyCondBr(b->CreateICmpUGT(prior, current), copyBack, done);
1113
1114            b->SetInsertPoint(copyBack);
1115            Value * const baseAddress = b->getBaseAddress(name);
1116            const StreamSetBuffer * const buf = this->getAnyStreamSetBuffer(name);
1117            const auto numOfStreams = buf->getNumOfStreams();
1118            const auto itemWidth = getItemWidth(this->getBinding(name));
1119
1120            const auto sizeByBit = b->CreateMul(b->CreateMul(b->getSize(itemWidth), bufferSize), b->getSize(numOfStreams));
1121            const auto sizeByByte = b->CreateUDiv(sizeByBit, b->getSize(8));
1122            const auto sourcePtr = b->CreateGEP(b->CreatePointerCast(baseAddress, b->getInt8PtrTy()), sizeByByte);
1123            const auto targetPtr = b->CreatePointerCast(baseAddress, b->getInt8PtrTy());
1124
1125            const auto itemsToBeCopyByBit = b->CreateMul(b->CreateMul(b->getSize(itemWidth), current), b->getSize(numOfStreams));
1126            const auto itemsToBeCopyByByte = b->CreateUDiv(itemsToBeCopyByBit, b->getSize(8));
1127            b->CreateMemCpy(targetPtr, sourcePtr, itemsToBeCopyByByte, 8);
1128
1129            b->CreateBr(done);
1130
1131            b->SetInsertPoint(done);
1132        }
1133    }
1134
1135    b->CreateCondBr(hasMoreStrides, segmentLoop, segmentDone);
1136
1137    /// SEGMENT DONE
1138    segmentDone->moveAfter(b->GetInsertBlock());
1139    b->SetInsertPoint(segmentDone);
1140
1141}
1142
1143/** ------------------------------------------------------------------------------------------------------------- *
1144 * @brief requiresCopyBack
1145 ** ------------------------------------------------------------------------------------------------------------- */
1146bool MultiBlockKernel::requiresCopyBack(const ProcessingRate & rate) const {
1147    if (rate.isBounded() || rate.isUnknown()) {
1148        return true;
1149    } else if (rate.isRelative()) {
1150        return requiresCopyBack(getBinding(rate.getReference()).getRate());
1151    }
1152    return false;
1153}
1154
1155/** ------------------------------------------------------------------------------------------------------------- *
1156 * @brief CreateUDivCeil
1157 ** ------------------------------------------------------------------------------------------------------------- */
1158inline Value * CreateUDivCeil(const std::unique_ptr<KernelBuilder> & b, Value * const number, const ProcessingRate::RateValue divisor, const Twine & Name = "") {
1159    Constant * const n = ConstantInt::get(number->getType(), divisor.numerator());
1160    if (LLVM_LIKELY(divisor.denominator() == 1)) {
1161        return b->CreateUDivCeil(number, n, Name);
1162    } else {
1163        //   âŒŠ(num + ratio - 1) / ratio⌋
1164        // = ⌊(num - 1) / (n/d)⌋ + (ratio/ratio)
1165        // = ⌊(d * (num - 1)) / n⌋ + 1
1166        Constant * const ONE = ConstantInt::get(number->getType(), 1);
1167        Constant * const d = ConstantInt::get(number->getType(), divisor.denominator());
1168        return b->CreateAdd(b->CreateUDiv(b->CreateMul(b->CreateSub(number, ONE), d), n), ONE, Name);
1169    }
1170}
1171
1172
1173/** ------------------------------------------------------------------------------------------------------------- *
1174 * @brief reviseFinalProducedItemCounts
1175 ** ------------------------------------------------------------------------------------------------------------- */
1176void MultiBlockKernel::reviseFinalProducedItemCounts(const std::unique_ptr<KernelBuilder> & b) {
1177
1178    if (LLVM_UNLIKELY(mStreamSetInputs.empty())) {
1179        return;
1180    }
1181
1182    const auto inputSetCount = mStreamSetInputs.size();
1183
1184    ProcessingRate::RateValue rateLCM(1);
1185    unsigned first = 0;
1186    unsigned last = inputSetCount;
1187
1188    for (unsigned i = 0; i < inputSetCount; ++i) {
1189        const ProcessingRate & pr = mStreamSetInputs[i].getRate();
1190        if (pr.isFixed()) {
1191            rateLCM = lcm(rateLCM, pr.getRate());
1192            if (mStreamSetInputs[i].isPrincipal()) {
1193                assert ("A kernel cannot have multiple principle input streams" && (first == 0 && last == inputSetCount));
1194                first = i;
1195                last = i + 1;
1196            }
1197        }       
1198    }
1199
1200    bool noFixedRateOutput = true;
1201
1202    for (const Binding & output : mStreamSetOutputs) {
1203        const ProcessingRate & pr = output.getRate();
1204        if (pr.isFixed()) {
1205            rateLCM = lcm(rateLCM, pr.getRate());
1206            noFixedRateOutput = false;
1207        }
1208    }
1209
1210    if (noFixedRateOutput) {
1211        return;
1212    }
1213
1214    Value * baseInitialProcessedItemCount = nullptr;
1215    Value * scaledInverseOfAvailItemCount = nullptr;
1216
1217    // For each Fixed output stream, this calculates:
1218
1219    //    CEILING(MIN(Available Item Count / Fixed Input Rate) * Fixed Output Rate)
1220
1221    // But avoids the possibility of overflow errors (assuming that each processed item count does not overflow)
1222
1223    for (unsigned i = first; i < last; ++i) {
1224        const ProcessingRate & pr = mStreamSetInputs[i].getRate();
1225        if (pr.isFixed()) {
1226            Value * p = mInitialProcessedItemCount[i];
1227            Value * a = b->CreateSub(mInitialAvailableItemCount[i], p);
1228            const auto & rate = pr.getRate();
1229            if (LLVM_UNLIKELY(rateLCM != rate)) {
1230                const auto factor = rateLCM / rate;
1231                if (LLVM_UNLIKELY(factor.numerator() > 1)) {
1232                    a = b->CreateMul(a, b->getSize(factor.numerator()));
1233                }
1234                if (LLVM_UNLIKELY(factor.denominator() > 1)) {
1235                    a = b->CreateUDiv(a, b->getSize(factor.denominator()));
1236                }
1237            }
1238            if (LLVM_UNLIKELY(rate.denominator() > 1)) {
1239                p = b->CreateMul(p, b->getSize(rate.denominator()));
1240            }
1241            if (LLVM_UNLIKELY(rate.numerator() > 1)) {
1242                p = b->CreateUDiv(p, b->getSize(rate.numerator()));
1243            }
1244            if (scaledInverseOfAvailItemCount) {
1245                scaledInverseOfAvailItemCount = b->CreateUMin(scaledInverseOfAvailItemCount, a);
1246                baseInitialProcessedItemCount = b->CreateUMin(baseInitialProcessedItemCount, p);
1247            } else {
1248                scaledInverseOfAvailItemCount = a;
1249                baseInitialProcessedItemCount = p;
1250            }
1251        }
1252    }
1253
1254    for (const Binding & output : mStreamSetOutputs) {
1255        const auto name = output.getName();
1256        const ProcessingRate & pr = output.getRate();
1257        Value * produced = nullptr;
1258        if (pr.isFixed() && output.nonDeferred()) {
1259            assert (baseInitialProcessedItemCount && scaledInverseOfAvailItemCount);
1260            const auto rate = pr.getRate();
1261            Value * p = baseInitialProcessedItemCount;
1262            if (LLVM_UNLIKELY(rate.numerator() != 1)) {
1263                p = b->CreateMul(p, b->getSize(rate.numerator()));
1264            }
1265            if (LLVM_UNLIKELY(rate.denominator() != 1)) {
1266                p = b->CreateUDiv(p, b->getSize(rate.denominator()));
1267            }
1268            Value * const ic = CreateUDivCeil(b, scaledInverseOfAvailItemCount, rateLCM / pr.getRate());
1269            produced = b->CreateAdd(p, ic);
1270        } else { // check if we have an attribute; if so, get the current produced count and adjust it
1271            bool noAttributes = true;
1272            for (const Attribute & attr : output.getAttributes()) {
1273                if (attr.isAdd() || attr.isRoundUpTo()) {
1274                    noAttributes = false;
1275                    break;
1276                }
1277            }
1278            if (noAttributes) {
1279                continue;
1280            }
1281            produced = b->getProducedItemCount(name);
1282        }
1283        for (const Attribute & attr : output.getAttributes()) {
1284            if (attr.isAdd()) {
1285                produced = b->CreateAdd(produced, b->getSize(attr.amount()));
1286            } else if (attr.isRoundUpTo()) {
1287                produced = b->CreateRoundUp(produced, b->getSize(attr.amount()));
1288            }
1289        }
1290        b->setProducedItemCount(name, produced);
1291    }
1292
1293}
1294
1295/** ------------------------------------------------------------------------------------------------------------- *
1296 * @brief generateMultiBlockLogic
1297 ** ------------------------------------------------------------------------------------------------------------- */
1298void BlockOrientedKernel::generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> & b, Value * const numOfBlocks) {
1299
1300    if (LLVM_UNLIKELY(mStride != b->getBitBlockWidth())) {
1301        report_fatal_error(getName() + ": the Stride (" + std::to_string(mStride) + ") of BlockOrientedKernel "
1302                           "equal to the BitBlockWidth (" + std::to_string(b->getBitBlockWidth()) + ")");
1303    }
1304
1305    Constant * const LOG_2_BLOCK_WIDTH = b->getSize(std::log2(b->getBitBlockWidth()));
1306
1307    BasicBlock * const entryBlock = b->GetInsertBlock();
1308    mStrideLoopBody = b->CreateBasicBlock(getName() + "_strideLoopBody");
1309    BasicBlock * const stridesDone = b->CreateBasicBlock(getName() + "_stridesDone");
1310    BasicBlock * const doFinalBlock = b->CreateBasicBlock(getName() + "_doFinalBlock");
1311    BasicBlock * const segmentDone = b->CreateBasicBlock(getName() + "_segmentDone");
1312
1313    const auto inputSetCount = mStreamSetInputs.size();
1314    Value * baseProcessedIndex[inputSetCount];
1315    Value * baseInputAddress[inputSetCount];
1316    for (unsigned i = 0; i < inputSetCount; i++) {
1317        const ProcessingRate & rate = mStreamSetInputs[i].getRate();
1318        if (LLVM_UNLIKELY(!rate.isFixed())) {
1319            Value * const ic = mInitialProcessedItemCount[i];
1320            baseProcessedIndex[i] = b->CreateLShr(ic, LOG_2_BLOCK_WIDTH);
1321        }
1322        baseInputAddress[i] = mStreamSetInputBaseAddress[i];
1323    }
1324
1325    const auto outputSetCount = mStreamSetOutputs.size();
1326    Value * baseProducedIndex[outputSetCount];
1327    Value * baseOutputAddress[inputSetCount];
1328    for (unsigned i = 0; i < outputSetCount; i++) {
1329        const ProcessingRate & rate = mStreamSetOutputs[i].getRate();
1330        if (LLVM_UNLIKELY(!rate.isFixed())) {
1331            Value * const ic = b->getProducedItemCount(mStreamSetOutputs[i].getName());
1332            baseProducedIndex[i] = b->CreateLShr(ic, LOG_2_BLOCK_WIDTH);
1333        }
1334        baseOutputAddress[i] = mStreamSetOutputBaseAddress[i];
1335    }
1336
1337    b->CreateUnlikelyCondBr(mIsFinal, doFinalBlock, mStrideLoopBody);
1338
1339    /// BLOCK BODY
1340
1341    b->SetInsertPoint(mStrideLoopBody);
1342
1343    if (b->supportsIndirectBr()) {
1344        Value * const baseTarget = BlockAddress::get(segmentDone);
1345        mStrideLoopTarget = b->CreatePHI(baseTarget->getType(), 2, "strideTarget");
1346        mStrideLoopTarget->addIncoming(baseTarget, entryBlock);
1347    }
1348
1349    mStrideBlockIndex = b->CreatePHI(b->getSizeTy(), 2);
1350    mStrideBlockIndex->addIncoming(b->getSize(0), entryBlock);
1351
1352    /// GENERATE DO BLOCK METHOD
1353
1354    for (unsigned i = 0; i < inputSetCount; ++i) {
1355        Value * index = mStrideBlockIndex;
1356        const ProcessingRate & rate = mStreamSetInputs[i].getRate();
1357        if (LLVM_UNLIKELY(!rate.isFixed())) {
1358            Value * ic = b->getProcessedItemCount(mStreamSetInputs[i].getName());
1359            index = b->CreateSub(b->CreateLShr(ic, LOG_2_BLOCK_WIDTH), baseProcessedIndex[i]);
1360        }
1361        mStreamSetInputBaseAddress[i] = b->CreateGEP(mStreamSetInputBaseAddress[i], index);
1362    }
1363
1364    for (unsigned i = 0; i < outputSetCount; ++i) {
1365        Value * index = mStrideBlockIndex;
1366        const ProcessingRate & rate = mStreamSetOutputs[i].getRate();
1367        if (LLVM_UNLIKELY(!rate.isFixed())) {
1368            Value * ic = b->getProducedItemCount(mStreamSetOutputs[i].getName());
1369            index = b->CreateSub(b->CreateLShr(ic, LOG_2_BLOCK_WIDTH), baseProducedIndex[i]);
1370        }
1371        mStreamSetOutputBaseAddress[i] = b->CreateGEP(mStreamSetOutputBaseAddress[i], index);
1372    }
1373
1374    writeDoBlockMethod(b);
1375
1376    BasicBlock * const bodyEnd = b->GetInsertBlock();
1377    if (mStrideLoopTarget) {
1378        mStrideLoopTarget->addIncoming(mStrideLoopTarget, bodyEnd);
1379    }
1380
1381    Value * const nextIndex = b->CreateAdd(mStrideBlockIndex, b->getSize(1));
1382    mStrideBlockIndex->addIncoming(nextIndex, bodyEnd);
1383    Value * const notDone = b->CreateICmpULT(nextIndex, numOfBlocks);
1384    b->CreateCondBr(notDone, mStrideLoopBody, stridesDone);
1385
1386    stridesDone->moveAfter(bodyEnd);
1387
1388    /// STRIDE DONE
1389
1390    b->SetInsertPoint(stridesDone);
1391
1392    // Now conditionally perform the final block processing depending on the doFinal parameter.
1393    if (mStrideLoopTarget) {
1394        mStrideLoopBranch = b->CreateIndirectBr(mStrideLoopTarget, 3);
1395        mStrideLoopBranch->addDestination(doFinalBlock);
1396        mStrideLoopBranch->addDestination(segmentDone);
1397    } else {
1398        b->CreateUnlikelyCondBr(mIsFinal, doFinalBlock, segmentDone);
1399    }
1400
1401    doFinalBlock->moveAfter(stridesDone);
1402
1403    /// DO FINAL BLOCK
1404
1405    b->SetInsertPoint(doFinalBlock);
1406    for (unsigned i = 0; i < inputSetCount; ++i) {
1407        mStreamSetInputBaseAddress[i] = baseInputAddress[i];
1408    }
1409
1410    for (unsigned i = 0; i < outputSetCount; ++i) {
1411        mStreamSetOutputBaseAddress[i] = baseOutputAddress[i];
1412    }
1413
1414    writeFinalBlockMethod(b, getRemainingItems(b));
1415
1416    b->CreateBr(segmentDone);
1417
1418    segmentDone->moveAfter(b->GetInsertBlock());
1419
1420    b->SetInsertPoint(segmentDone);
1421
1422    // Update the branch prediction metadata to indicate that the likely target will be segmentDone
1423    if (mStrideLoopTarget) {
1424        MDBuilder mdb(b->getContext());
1425        const auto destinations = mStrideLoopBranch->getNumDestinations();
1426        uint32_t weights[destinations];
1427        for (unsigned i = 0; i < destinations; ++i) {
1428            weights[i] = (mStrideLoopBranch->getDestination(i) == segmentDone) ? 100 : 1;
1429        }
1430        ArrayRef<uint32_t> bw(weights, destinations);
1431        mStrideLoopBranch->setMetadata(LLVMContext::MD_prof, mdb.createBranchWeights(bw));
1432    }
1433
1434}
1435
1436/** ------------------------------------------------------------------------------------------------------------- *
1437 * @brief getRemainingItems
1438 ** ------------------------------------------------------------------------------------------------------------- */
1439Value * BlockOrientedKernel::getRemainingItems(const std::unique_ptr<KernelBuilder> & b) {
1440    Value * remainingItems = nullptr;
1441    const auto count = mStreamSetInputs.size();
1442    if (count == 1) {
1443        return mAvailableItemCount[0];
1444    } else {
1445        for (unsigned i = 0; i < count; i++) {
1446            if (mStreamSetInputs[i].isPrincipal()) {
1447                return mAvailableItemCount[i];
1448            }
1449        }
1450        for (unsigned i = 0; i < count; ++i) {
1451            const ProcessingRate & r = mStreamSetInputs[i].getRate();
1452            if (r.isFixed()) {
1453                Value * ic = CreateUDivCeil(b, mAvailableItemCount[i], r.getRate());
1454                if (remainingItems) {
1455                    remainingItems = b->CreateUMin(remainingItems, ic);
1456                } else {
1457                    remainingItems = ic;
1458                }
1459            }
1460        }
1461    }
1462    return remainingItems;
1463}
1464
1465/** ------------------------------------------------------------------------------------------------------------- *
1466 * @brief writeDoBlockMethod
1467 ** ------------------------------------------------------------------------------------------------------------- */
1468inline void BlockOrientedKernel::writeDoBlockMethod(const std::unique_ptr<KernelBuilder> & b) {
1469
1470    Value * const self = getInstance();
1471    Function * const cp = mCurrentMethod;
1472    auto ip = b->saveIP();
1473    std::vector<Value *> availableItemCount(0);
1474
1475    /// Check if the do block method is called and create the function if necessary
1476    if (!b->supportsIndirectBr()) {
1477
1478        std::vector<Type *> params;
1479        params.reserve(1 + mAvailableItemCount.size());
1480        params.push_back(self->getType());
1481        for (Value * avail : mAvailableItemCount) {
1482            params.push_back(avail->getType());
1483        }
1484
1485        FunctionType * const type = FunctionType::get(b->getVoidTy(), params, false);
1486        mCurrentMethod = Function::Create(type, GlobalValue::InternalLinkage, getName() + DO_BLOCK_SUFFIX, b->getModule());
1487        mCurrentMethod->setCallingConv(CallingConv::C);
1488        mCurrentMethod->setDoesNotThrow();
1489        auto args = mCurrentMethod->arg_begin();
1490        args->setName("self");
1491        setInstance(&*args);
1492        availableItemCount.reserve(mAvailableItemCount.size());
1493        while (++args != mCurrentMethod->arg_end()) {
1494            availableItemCount.push_back(&*args);
1495        }
1496        assert (availableItemCount.size() == mAvailableItemCount.size());
1497        mAvailableItemCount.swap(availableItemCount);
1498        b->SetInsertPoint(BasicBlock::Create(b->getContext(), "entry", mCurrentMethod));
1499    }
1500
1501    generateDoBlockMethod(b); // must be implemented by the BlockOrientedKernelBuilder subtype
1502
1503    if (!b->supportsIndirectBr()) {
1504        // Restore the DoSegment function state then call the DoBlock method
1505        b->CreateRetVoid();
1506        mDoBlockMethod = mCurrentMethod;
1507        b->restoreIP(ip);
1508        setInstance(self);
1509        mCurrentMethod = cp;
1510        mAvailableItemCount.swap(availableItemCount);
1511        CreateDoBlockMethodCall(b);
1512    }
1513
1514}
1515
1516/** ------------------------------------------------------------------------------------------------------------- *
1517 * @brief writeFinalBlockMethod
1518 ** ------------------------------------------------------------------------------------------------------------- */
1519inline void BlockOrientedKernel::writeFinalBlockMethod(const std::unique_ptr<KernelBuilder> & b, Value * remainingItems) {
1520
1521    Value * const self = getInstance();
1522    Function * const cp = mCurrentMethod;
1523    Value * const remainingItemCount = remainingItems;
1524    auto ip = b->saveIP();
1525    std::vector<Value *> availableItemCount(0);
1526
1527    if (!b->supportsIndirectBr()) {
1528        std::vector<Type *> params;
1529        params.reserve(2 + mAvailableItemCount.size());
1530        params.push_back(self->getType());
1531        params.push_back(b->getSizeTy());
1532        for (Value * avail : mAvailableItemCount) {
1533            params.push_back(avail->getType());
1534        }
1535        FunctionType * const type = FunctionType::get(b->getVoidTy(), params, false);
1536        mCurrentMethod = Function::Create(type, GlobalValue::InternalLinkage, getName() + FINAL_BLOCK_SUFFIX, b->getModule());
1537        mCurrentMethod->setCallingConv(CallingConv::C);
1538        mCurrentMethod->setDoesNotThrow();
1539        auto args = mCurrentMethod->arg_begin();
1540        args->setName("self");
1541        setInstance(&*args);
1542        remainingItems = &*(++args);
1543        remainingItems->setName("remainingItems");
1544        availableItemCount.reserve(mAvailableItemCount.size());
1545        while (++args != mCurrentMethod->arg_end()) {
1546            availableItemCount.push_back(&*args);
1547        }
1548        assert (availableItemCount.size() == mAvailableItemCount.size());
1549        mAvailableItemCount.swap(availableItemCount);
1550        b->SetInsertPoint(BasicBlock::Create(b->getContext(), "entry", mCurrentMethod));
1551    }
1552
1553    generateFinalBlockMethod(b, remainingItems); // may be implemented by the BlockOrientedKernel subtype
1554
1555    if (!b->supportsIndirectBr()) {
1556        b->CreateRetVoid();
1557        b->restoreIP(ip);
1558        setInstance(self);
1559        mAvailableItemCount.swap(availableItemCount);
1560        // Restore the DoSegment function state then call the DoFinal method
1561        std::vector<Value *> args;
1562        args.reserve(2 + mAvailableItemCount.size());
1563        args.push_back(self);
1564        args.push_back(remainingItemCount);
1565        args.insert(args.end(), mAvailableItemCount.begin(), mAvailableItemCount.end());
1566        b->CreateCall(mCurrentMethod, args);
1567        mCurrentMethod = cp;
1568    }
1569
1570}
1571
1572/** ------------------------------------------------------------------------------------------------------------- *
1573 * @brief generateFinalBlockMethod
1574 ** ------------------------------------------------------------------------------------------------------------- */
1575void BlockOrientedKernel::generateFinalBlockMethod(const std::unique_ptr<KernelBuilder> & b, Value * /* remainingItems */) {
1576    //  The default finalBlock method simply dispatches to the doBlock routine.
1577    CreateDoBlockMethodCall(b);
1578}
1579
1580void BlockOrientedKernel::CreateDoBlockMethodCall(const std::unique_ptr<KernelBuilder> & b) {
1581    if (b->supportsIndirectBr()) {
1582        BasicBlock * const bb = b->CreateBasicBlock("resume");
1583        mStrideLoopBranch->addDestination(bb);
1584        BasicBlock * const current = b->GetInsertBlock();
1585        mStrideLoopTarget->addIncoming(BlockAddress::get(bb), current);
1586        mStrideBlockIndex->addIncoming(b->getSize(0), current);
1587        b->CreateBr(mStrideLoopBody);
1588        bb->moveAfter(current);
1589        b->SetInsertPoint(bb);
1590    } else {
1591        std::vector<Value *> args;
1592        args.reserve(1 + mAvailableItemCount.size());
1593        args.push_back(getInstance());
1594        args.insert(args.end(), mAvailableItemCount.begin(), mAvailableItemCount.end());
1595        b->CreateCall(mDoBlockMethod, args);
1596    }
1597}
1598
1599static inline std::string annotateKernelNameWithDebugFlags(std::string && name) {
1600    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1601        name += "_EA";
1602    }
1603    name += "_O" + std::to_string((int)codegen::OptLevel);
1604    return name;
1605}
1606
1607// CONSTRUCTOR
1608Kernel::Kernel(std::string && kernelName,
1609               Bindings && stream_inputs,
1610               Bindings && stream_outputs,
1611               Bindings && scalar_parameters,
1612               Bindings && scalar_outputs,
1613               Bindings && internal_scalars)
1614: KernelInterface(annotateKernelNameWithDebugFlags(std::move(kernelName))
1615                  , std::move(stream_inputs), std::move(stream_outputs)
1616                  , std::move(scalar_parameters), std::move(scalar_outputs)
1617                  , std::move(internal_scalars))
1618, mCurrentMethod(nullptr)
1619, mAvailablePrincipalItemCount(nullptr)
1620, mIsGenerated(false)
1621, mStride(0)
1622, mIsFinal(nullptr)
1623, mOutputScalarResult(nullptr) {
1624
1625}
1626
1627Kernel::~Kernel() {
1628
1629}
1630
1631// MULTI-BLOCK KERNEL CONSTRUCTOR
1632MultiBlockKernel::MultiBlockKernel(std::string && kernelName,
1633                                   Bindings && stream_inputs,
1634                                   Bindings && stream_outputs,
1635                                   Bindings && scalar_parameters,
1636                                   Bindings && scalar_outputs,
1637                                   Bindings && internal_scalars)
1638: Kernel(std::move(kernelName), std::move(stream_inputs), std::move(stream_outputs), std::move(scalar_parameters), std::move(scalar_outputs), std::move(internal_scalars)) {
1639
1640}
1641
1642// CONSTRUCTOR
1643BlockOrientedKernel::BlockOrientedKernel(std::string && kernelName,
1644                                         Bindings && stream_inputs,
1645                                         Bindings && stream_outputs,
1646                                         Bindings && scalar_parameters,
1647                                         Bindings && scalar_outputs,
1648                                         Bindings && internal_scalars)
1649: MultiBlockKernel(std::move(kernelName), std::move(stream_inputs), std::move(stream_outputs), std::move(scalar_parameters), std::move(scalar_outputs), std::move(internal_scalars))
1650, mDoBlockMethod(nullptr)
1651, mStrideLoopBody(nullptr)
1652, mStrideLoopBranch(nullptr)
1653, mStrideLoopTarget(nullptr)
1654, mStrideBlockIndex(nullptr) {
1655
1656}
1657
1658// CONSTRUCTOR
1659SegmentOrientedKernel::SegmentOrientedKernel(std::string && kernelName,
1660                                             Bindings && stream_inputs,
1661                                             Bindings && stream_outputs,
1662                                             Bindings && scalar_parameters,
1663                                             Bindings && scalar_outputs,
1664                                             Bindings && internal_scalars)
1665: Kernel(std::move(kernelName), std::move(stream_inputs), std::move(stream_outputs), std::move(scalar_parameters), std::move(scalar_outputs), std::move(internal_scalars)) {
1666
1667}
1668
1669
1670}
Note: See TracBrowser for help on using the repository browser.