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

Last change on this file since 5856 was 5856, checked in by nmedfort, 18 months ago

Revised pipeline structure to better control I/O rates

File size: 78.3 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    Value * const initiallyFinal = mIsFinal;
764
765//    b->CallPrintInt(getName() + "_initiallyFinal", initiallyFinal);
766
767    // Now proceed with creation of the doSegment method.
768    BasicBlock * const segmentLoop = b->CreateBasicBlock("SegmentLoop");
769
770    b->CreateBr(segmentLoop);
771
772    /// DO SEGMENT LOOP
773
774    b->SetInsertPoint(segmentLoop);
775
776    Value * numOfStrides = nullptr;
777
778    // TODO: we don't want the our available output space to limit how many conditional blocks we
779    // can check. When we have a conditional region, split computation of input/output strides and
780    // check as many input strides as possible but leave the kernel in a state that respects our
781    // available output space. NOTE: we know coming into this block that the pipeline or kernel has
782    // ensured there is at least one stride worth of space.
783
784
785    // For each input buffer, get the initial processed item count, base input pointer, and the number of
786    // linearly available strides.
787    Value * inputStrideSize[inputSetCount];
788    Value * linearlyAccessible[inputSetCount];
789    for (unsigned i = 0; i < inputSetCount; i++) {
790        const Binding & input = mStreamSetInputs[i];
791        const auto & name = input.getName();
792        Value * const processed = b->getProcessedItemCount(name);
793
794//        b->CallPrintInt(getName() + "_" + name + "_avail", mAvailableItemCount[i]);
795//        b->CallPrintInt(getName() + "_" + name + "_processed", processed);
796
797        mInitialProcessedItemCount[i] = processed;
798        mStreamSetInputBaseAddress[i] = b->getBlockAddress(name, b->CreateLShr(processed, LOG_2_BLOCK_WIDTH));
799        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
800            b->CreateAssert(b->CreateICmpULE(processed, mAvailableItemCount[i]),
801                            getName() + ": " + name + " processed item count exceeds its available item count");
802        }
803
804        Value * const unprocessed = b->CreateSub(mAvailableItemCount[i], processed);       
805//        b->CallPrintInt(getName() + "_" + name + "_unprocessed", unprocessed);
806
807        Value * const accessible = b->getLinearlyAccessibleItems(name, processed, unprocessed);
808//        b->CallPrintInt(getName() + "_" + name + "_accessible", accessible);
809
810        mAvailableItemCount[i] = unprocessed;
811
812        linearlyAccessible[i] = accessible;
813        inputStrideSize[i] = getStrideSize(b, input.getRate());
814        Value * const accessibleStrides = b->CreateUDiv(accessible, inputStrideSize[i]);
815        numOfStrides = b->CreateUMin(numOfStrides, accessibleStrides);
816    }
817
818    BasicBlock * const checkInputAvailability = b->CreateBasicBlock("CheckInputAvailability");
819    BasicBlock * const selectOutputBuffers = b->CreateBasicBlock("SelectOutputBuffers");
820    b->CreateLikelyCondBr(b->CreateICmpNE(numOfStrides, ZERO), selectOutputBuffers, checkInputAvailability);
821
822    // Ensure that everything between S⌈P/S⌉ and S⌈n*(P + L)/S⌉ is linearly available, where S is the stride size,
823    // P is the current processed position, L is the lookahead amount and n is our number of accessible strides ∈ â„€+.
824    b->SetInsertPoint(checkInputAvailability);
825    Value * linearlyCopyable[inputSetCount];
826    PHINode * selectedInputBuffer[inputSetCount];
827    for (unsigned i = 0; i < inputSetCount; i++) {
828        AllocaInst * const tempBuffer = temporaryInputBuffer[i];
829        selectedInputBuffer[i] = nullptr;
830        if (tempBuffer) {
831
832            const Binding & input = mStreamSetInputs[i];
833            const auto & name = input.getName();
834            Value * const processed = mInitialProcessedItemCount[i];
835            Value * const unprocessed = mAvailableItemCount[i];
836            Value * const accessible = linearlyAccessible[i];
837
838            BasicBlock * const entry = b->GetInsertBlock();
839            BasicBlock * const copyFromBack = b->CreateBasicBlock(name + "CopyFromBack");
840            BasicBlock * const copyFromFront = b->CreateBasicBlock(name + "CopyFromFront");
841            BasicBlock * const resume = b->CreateBasicBlock(name + "Resume");
842
843            Value * strideSize = inputStrideSize[i];
844            if (LLVM_UNLIKELY(input.hasLookahead())) {
845                Constant * const lookahead = b->getSize(input.getLookahead());
846                strideSize = b->CreateAdd(strideSize, lookahead);
847            }
848            Value * const requiresCopy = b->CreateICmpULT(accessible, strideSize);
849            b->CreateUnlikelyCondBr(requiresCopy, copyFromBack, resume);
850
851            b->SetInsertPoint(copyFromBack);
852            Value * const arraySize = b->CreateZExt(tempBuffer->getArraySize(), b->getInt64Ty());
853            Value * const temporarySize = b->CreateTrunc(b->CreateMul(arraySize, b->getInt64(mStride)), accessible->getType());
854            Value * const copyable = b->CreateUMin(unprocessed, temporarySize); // <- we only really need strideSize items
855            Value * const offset = b->CreateAnd(processed, BLOCK_WIDTH_MASK);
856            Value * const bufferSize = b->CreateMul(ConstantExpr::getSizeOf(tempBuffer->getAllocatedType()), arraySize);
857            b->CreateMemZero(tempBuffer, bufferSize, blockAlignment);
858            b->CreateStreamCpy(name, tempBuffer, ZERO, mStreamSetInputBaseAddress[i], offset, accessible, getItemAlignment(input));
859            BasicBlock * const copyToBackEnd = b->GetInsertBlock();
860            b->CreateCondBr(b->CreateICmpNE(copyable, accessible), copyFromFront, resume);
861
862            b->SetInsertPoint(copyFromFront);
863            Value * const remaining = b->CreateSub(copyable, accessible);
864            Value * const baseAddress = b->getBaseAddress(name);
865            b->CreateStreamCpy(name, tempBuffer, accessible, baseAddress, ZERO, remaining, getItemAlignment(input));
866            Value * const isPartialStride = b->CreateICmpUGE(copyable, strideSize);
867            BasicBlock * const copyToFrontEnd = b->GetInsertBlock();
868            b->CreateBr(resume);
869
870            b->SetInsertPoint(resume);
871            PHINode * const address = b->CreatePHI(tempBuffer->getType(), 3);
872            address->addIncoming(mStreamSetInputBaseAddress[i], entry);
873            address->addIncoming(tempBuffer, copyToBackEnd);
874            address->addIncoming(tempBuffer, copyToFrontEnd);
875            selectedInputBuffer[i] = address;
876            PHINode * const available = b->CreatePHI(accessible->getType(), 3);
877            available->addIncoming(accessible, entry);
878            available->addIncoming(copyable, copyToBackEnd);
879            available->addIncoming(copyable, copyToFrontEnd);
880            linearlyCopyable[i] = available;
881            PHINode * const finalStride = b->CreatePHI(b->getInt1Ty(), 3);
882            finalStride->addIncoming(mIsFinal, entry);
883            finalStride->addIncoming(b->getTrue(), copyToBackEnd);
884            finalStride->addIncoming(isPartialStride, copyToFrontEnd);
885            mIsFinal = finalStride;
886            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
887                Value * const hasStride = b->CreateOr(initiallyFinal, b->CreateNot(finalStride));
888                b->CreateAssert(hasStride, getName() + ": " + name + " has insufficient input data for one stride");
889            }
890        }
891    }
892
893    BasicBlock * const endCheckInputAvailability = b->GetInsertBlock();
894    selectOutputBuffers->moveAfter(endCheckInputAvailability);
895    b->CreateBr(selectOutputBuffers);
896
897    b->SetInsertPoint(selectOutputBuffers);
898    PHINode * const final = b->CreatePHI(mIsFinal->getType(), 2);
899    final->addIncoming(b->getFalse(), segmentLoop);
900    final->addIncoming(mIsFinal, endCheckInputAvailability);
901    mIsFinal = final;
902    for (unsigned i = 0; i < inputSetCount; i++) {
903        if (selectedInputBuffer[i]) {
904            PHINode * const address = b->CreatePHI(selectedInputBuffer[i]->getType(), 2);
905            address->addIncoming(mStreamSetInputBaseAddress[i], segmentLoop);
906            address->addIncoming(selectedInputBuffer[i], endCheckInputAvailability);
907            mStreamSetInputBaseAddress[i] = address;
908            PHINode * const accessible = b->CreatePHI(linearlyAccessible[i]->getType(), 2);
909            accessible->addIncoming(linearlyAccessible[i], segmentLoop);
910            accessible->addIncoming(linearlyCopyable[i], endCheckInputAvailability);
911            linearlyAccessible[i] = accessible;
912        }
913    }
914    PHINode * const strides = b->CreatePHI(numOfStrides->getType(), 2);
915    strides->addIncoming(numOfStrides, segmentLoop);
916    strides->addIncoming(ONE, endCheckInputAvailability);
917    numOfStrides = strides;
918
919    // Now determine the linearly writeable strides
920    Value * outputStrideSize[outputSetCount];
921    Value * linearlyWritable[outputSetCount];
922    mInitialProducedItemCount.resize(outputSetCount);
923    mStreamSetOutputBaseAddress.resize(outputSetCount);
924    for (unsigned i = 0; i < outputSetCount; i++) {
925        const auto & output = mStreamSetOutputs[i];
926        const auto & name = output.getName();
927        Value * const produced = b->getProducedItemCount(name);
928//        b->CallPrintInt(getName() + "_" + name + "_produced", produced);
929
930        Value * baseBuffer = b->getBlockAddress(name, b->CreateLShr(produced, LOG_2_BLOCK_WIDTH));
931        mInitialProducedItemCount[i] = produced;
932        mStreamSetOutputBaseAddress[i] = baseBuffer;
933
934        // Is the number of linearly writable items sufficient for a stride?
935        outputStrideSize[i] = getStrideSize(b, output.getRate());
936        if (outputStrideSize[i]) {
937            linearlyWritable[i] = b->getLinearlyWritableItems(name, produced);
938            Value * writableStrides = b->CreateUDiv(linearlyWritable[i], outputStrideSize[i]);
939            numOfStrides = b->CreateUMin(numOfStrides, writableStrides);
940            // Do we require a temporary buffer to write to?
941            AllocaInst * const tempBuffer = temporaryOutputBuffer[i];
942            if (tempBuffer) {
943                assert (tempBuffer->getType() == baseBuffer->getType());
944                BasicBlock * const entry = b->GetInsertBlock();
945                BasicBlock * const prepareTempBuffer = b->CreateBasicBlock(name + "PrepareTempBuffer");
946                BasicBlock * const resume = b->CreateBasicBlock(name + "Resume");
947                Value * const requiresCopy = b->CreateICmpEQ(writableStrides, ZERO);
948                b->CreateUnlikelyCondBr(requiresCopy, prepareTempBuffer, resume);
949                // Clear the output buffer prior to using it
950                b->SetInsertPoint(prepareTempBuffer);
951                Value * const bufferSize = b->CreateMul(ConstantExpr::getSizeOf(tempBuffer->getAllocatedType()), tempBuffer->getArraySize());
952                b->CreateMemZero(tempBuffer, bufferSize, blockAlignment);               
953                b->CreateBr(resume);
954                // Select the appropriate buffer / stride #
955                b->SetInsertPoint(resume);
956                PHINode * const phiBuffer = b->CreatePHI(baseBuffer->getType(), 3);
957                phiBuffer->addIncoming(baseBuffer, entry);
958                phiBuffer->addIncoming(tempBuffer, prepareTempBuffer);
959                baseBuffer = phiBuffer;
960                PHINode * const phiStrides = b->CreatePHI(b->getSizeTy(), 2);
961                phiStrides->addIncoming(numOfStrides, entry);
962                phiStrides->addIncoming(ONE, prepareTempBuffer);
963                numOfStrides = phiStrides;
964            }
965            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
966                b->CreateAssert(numOfStrides, getName() + ": " + name + " has insufficient output space for one stride");
967            }
968        }
969    }
970
971    // Update the locally available item count to reflect the current state
972    for (unsigned i = 0; i < inputSetCount; i++) {
973        const Binding & input = mStreamSetInputs[i];
974        if (input.getRate().isFixed() && input.nonDeferred()) {
975            Value * const processable = b->CreateMul(numOfStrides, inputStrideSize[i]);
976            linearlyAccessible[i] = b->CreateSelect(mIsFinal, linearlyAccessible[i], processable);
977        }
978        mAvailableItemCount[i] = linearlyAccessible[i];
979    }
980
981    //  We have one or more strides of input data and output buffer space for all stream sets.
982    generateMultiBlockLogic(b, numOfStrides);
983
984    for (unsigned i = 0; i < inputSetCount; ++i) {
985        const auto & input = mStreamSetInputs[i];
986        const ProcessingRate & rate = input.getRate();
987        if (rate.isFixed() && input.nonDeferred()) {
988//            b->CallPrintInt(getName() + "_" + input.getName() + "_processed (+)", mAvailableItemCount[i]);
989            Value * const ic = b->CreateAdd(mInitialProcessedItemCount[i], mAvailableItemCount[i]);
990            b->setProcessedItemCount(input.getName(), ic);
991        }
992    }
993
994    for (unsigned i = 0; i < outputSetCount; ++i) {
995        const auto & output = mStreamSetOutputs[i];
996        const ProcessingRate & rate = output.getRate();
997        if (rate.isFixed()) {
998            Value * const produced = b->CreateMul(numOfStrides, outputStrideSize[i]);
999            Value * const ic = b->CreateAdd(mInitialProducedItemCount[i], produced);
1000//            b->CallPrintInt(getName() + "_" + output.getName() + "_produced (+)", produced);
1001            b->setProducedItemCount(output.getName(), ic);
1002        }
1003    }
1004
1005    BasicBlock * const handleFinalBlock = b->CreateBasicBlock("HandleFinalBlock");
1006    BasicBlock * const temporaryBufferCopyBack = b->CreateBasicBlock("TemporaryBufferCopyBack");
1007    BasicBlock * const strideDone = b->CreateBasicBlock("MultiBlockDone");
1008
1009    b->CreateUnlikelyCondBr(mIsFinal, handleFinalBlock, temporaryBufferCopyBack);
1010
1011
1012    /// FINAL STRIDE ADJUSTMENT
1013    b->SetInsertPoint(handleFinalBlock);
1014
1015    // If this is our final stride, adjust the Fixed output item counts. The main loop assumes that
1016    // the ITEM COUNT % FIXED RATE = 0 for all Fixed Input and Output streams. We correct that here
1017    // to calculate them based on the actual input item counts.
1018
1019    reviseFinalProducedItemCounts(b);
1020
1021    b->CreateBr(temporaryBufferCopyBack);
1022
1023    /// TEMPORARY BUFFER COPY BACK
1024    b->SetInsertPoint(temporaryBufferCopyBack);
1025
1026    // Copy back data to the actual output buffers.
1027    for (unsigned i = 0; i < outputSetCount; i++) {
1028
1029        AllocaInst * const tempBuffer = temporaryOutputBuffer[i];
1030        if (LLVM_UNLIKELY(tempBuffer == nullptr)) {
1031            continue;
1032        }
1033
1034        const auto & name = mStreamSetOutputs[i].getName();
1035        Value * const produced = b->getProducedItemCount(name);
1036        Value * const baseBuffer = mStreamSetOutputBaseAddress[i];
1037        assert ("stack corruption likely" && (tempBuffer->getType() == baseBuffer->getType()));
1038        //const auto & name = mStreamSetOutputs[i].getName();
1039        BasicBlock * const copyToBack = b->CreateBasicBlock(name + "CopyToBack");
1040        BasicBlock * const copyToFront = b->CreateBasicBlock(name + "CopyToFront");
1041        BasicBlock * const resume = b->CreateBasicBlock(name + "ResumeCopyBack");
1042        // If we used a temporary buffer, copy it back to the original output buffer
1043        Value * const requiresCopy = b->CreateICmpEQ(tempBuffer, baseBuffer);
1044        b->CreateCondBr(requiresCopy, copyToBack, resume);
1045
1046        b->SetInsertPoint(copyToBack);       
1047        Value * const offset = b->CreateAnd(mInitialProducedItemCount[i], BLOCK_WIDTH_MASK);
1048        //Value * const newProducedItemCount = b->getProducedItemCount(name);
1049        Value * const newlyProduced = b->CreateSub(produced, mInitialProducedItemCount[i]);
1050        Value * const toWrite = b->CreateUMin(newlyProduced, linearlyWritable[i]);
1051        const auto alignment = getItemAlignment(mStreamSetOutputs[i]);
1052        b->CreateStreamCpy(name, baseBuffer, offset, tempBuffer, ZERO, toWrite, alignment);
1053        // If we required a temporary output buffer, we will probably need to write to the beginning of the buffer as well.
1054        b->CreateLikelyCondBr(b->CreateICmpULT(toWrite, newlyProduced), copyToFront, resume);
1055
1056        b->SetInsertPoint(copyToFront);
1057        Value * const remaining = b->CreateSub(newlyProduced, toWrite);
1058        Value * const baseAddress = b->getBaseAddress(name);
1059        b->CreateStreamCpy(name, baseAddress, ZERO, tempBuffer, toWrite, remaining, alignment);
1060        b->CreateBr(resume);
1061
1062        b->SetInsertPoint(resume);
1063    }
1064
1065    //  We've dealt with the partial block processing and copied information back into the
1066    //  actual buffers.  If this isn't the final block, loop back for more multiblock processing.
1067    BasicBlock * const segmentDone = b->CreateBasicBlock("SegmentDone");
1068    if (canTerminateEarly()) {
1069        mIsFinal = b->CreateOr(mIsFinal, b->getTerminationSignal());
1070    }
1071    b->CreateCondBr(mIsFinal, segmentDone, strideDone);
1072
1073    /// STRIDE DONE
1074    strideDone->moveAfter(b->GetInsertBlock());
1075    b->SetInsertPoint(strideDone);
1076
1077    // do we have enough data for another stride?
1078    Value * hasMoreStrides = b->getTrue();
1079    for (unsigned i = 0; i < inputSetCount; ++i) {
1080        const Binding & input = mStreamSetInputs[i];
1081        const auto & name = input.getName();
1082        Value * const avail = mInitialAvailableItemCount[i];
1083        Value * const processed = b->getProcessedItemCount(name);
1084//        b->CallPrintInt(getName() + "_" + name + "_processed'", processed);
1085
1086        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1087            b->CreateAssert(b->CreateICmpULE(processed, avail), getName() + ": " + name + " processed data exceeds available data");
1088        }
1089        Value * const remaining = b->CreateSub(avail, processed);
1090        Value * strideSize = inputStrideSize[i];
1091        if (LLVM_UNLIKELY(input.hasLookahead())) {
1092            strideSize = b->CreateAdd(strideSize, b->getSize(input.getLookahead()));
1093        }
1094        Value * const hasRemainingStrides = b->CreateICmpUGE(remaining, strideSize);
1095        hasMoreStrides = b->CreateAnd(hasMoreStrides, hasRemainingStrides);
1096    }
1097
1098    // even if we do not have enough input data for a full stride, if this is our final stride, allow it ...
1099    hasMoreStrides = b->CreateOr(hasMoreStrides, initiallyFinal);
1100
1101    // do we have enough room for another stride?
1102    for (unsigned i = 0; i < outputSetCount; ++i) {
1103        const ProcessingRate & rate = mStreamSetOutputs[i].getRate();
1104        const auto & name = mStreamSetOutputs[i].getName();
1105        Value * const produced = b->getProducedItemCount(name);
1106        // If this output has a Fixed/Bounded rate, determine whether we have room for another stride.
1107        if (LLVM_LIKELY(outputStrideSize[i] != nullptr)) {
1108            Value * const consumed = b->getConsumedItemCount(name);
1109            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1110                b->CreateAssert(b->CreateICmpULE(consumed, produced),
1111                                getName() + ": " + name + " consumed data exceeds produced data");
1112            }
1113            Value * const unconsumed = b->CreateSub(produced, consumed);
1114            Value * const capacity = b->getBufferedSize(name);
1115            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1116                b->CreateAssert(b->CreateICmpULE(unconsumed, capacity),
1117                                getName() + ": " + name + " unconsumed data exceeds capacity");
1118            }
1119            Value * const remaining = b->CreateSub(capacity, unconsumed);
1120            Value * const hasRemainingStrides = b->CreateICmpUGE(remaining, outputStrideSize[i]);
1121            hasMoreStrides = b->CreateAnd(hasMoreStrides, hasRemainingStrides);
1122        }
1123        // Do copybacks if necessary.
1124        if (mStreamSetOutputBuffers[i]->supportsCopyBack() && requiresCopyBack(rate)) {
1125            BasicBlock * const copyBack = b->CreateBasicBlock(name + "CopyBack");
1126            BasicBlock * const done = b->CreateBasicBlock(name + "CopyBackDone");
1127
1128            Value * const bufferSize = b->getBufferedSize(name);
1129            Value * const prior = b->CreateURem(mInitialProducedItemCount[i], bufferSize);
1130            Value * const current = b->CreateURem(produced, bufferSize);
1131            b->CreateUnlikelyCondBr(b->CreateICmpUGT(prior, current), copyBack, done);
1132
1133            b->SetInsertPoint(copyBack);
1134            const auto copyAlignment = getItemAlignment(mStreamSetOutputs[i]);
1135            Value * const startOfBuffer = b->getBaseAddress(name);
1136            Value * const offset = b->CreateUDiv(bufferSize, b->getSize(b->getBitBlockWidth()));
1137            Value * const endOfBuffer = b->CreateGEP(startOfBuffer, offset);
1138            b->CreateStreamCpy(name, startOfBuffer, ZERO, endOfBuffer, ZERO, current, copyAlignment);
1139            b->CreateBr(done);
1140
1141            b->SetInsertPoint(done);
1142        }
1143    }
1144
1145    b->CreateCondBr(hasMoreStrides, segmentLoop, segmentDone);
1146
1147    /// SEGMENT DONE
1148    segmentDone->moveAfter(b->GetInsertBlock());
1149    b->SetInsertPoint(segmentDone);
1150
1151}
1152
1153/** ------------------------------------------------------------------------------------------------------------- *
1154 * @brief requiresCopyBack
1155 ** ------------------------------------------------------------------------------------------------------------- */
1156bool MultiBlockKernel::requiresCopyBack(const ProcessingRate & rate) const {
1157    if (rate.isBounded() || rate.isUnknown()) {
1158        return true;
1159    } else if (rate.isRelative()) {
1160        return requiresCopyBack(getBinding(rate.getReference()).getRate());
1161    }
1162    return false;
1163}
1164
1165/** ------------------------------------------------------------------------------------------------------------- *
1166 * @brief CreateUDivCeil
1167 ** ------------------------------------------------------------------------------------------------------------- */
1168inline Value * CreateUDivCeil(const std::unique_ptr<KernelBuilder> & b, Value * const number, const ProcessingRate::RateValue divisor, const Twine & Name = "") {
1169    Constant * const n = ConstantInt::get(number->getType(), divisor.numerator());
1170    if (LLVM_LIKELY(divisor.denominator() == 1)) {
1171        return b->CreateUDivCeil(number, n, Name);
1172    } else {
1173        //   âŒŠ(num + ratio - 1) / ratio⌋
1174        // = ⌊(num - 1) / (n/d)⌋ + (ratio/ratio)
1175        // = ⌊(d * (num - 1)) / n⌋ + 1
1176        Constant * const ONE = ConstantInt::get(number->getType(), 1);
1177        Constant * const d = ConstantInt::get(number->getType(), divisor.denominator());
1178        return b->CreateAdd(b->CreateUDiv(b->CreateMul(b->CreateSub(number, ONE), d), n), ONE, Name);
1179    }
1180}
1181
1182
1183/** ------------------------------------------------------------------------------------------------------------- *
1184 * @brief reviseFinalProducedItemCounts
1185 ** ------------------------------------------------------------------------------------------------------------- */
1186void MultiBlockKernel::reviseFinalProducedItemCounts(const std::unique_ptr<KernelBuilder> & b) {
1187
1188    if (LLVM_UNLIKELY(mStreamSetInputs.empty())) {
1189        return;
1190    }
1191
1192    const auto inputSetCount = mStreamSetInputs.size();
1193
1194    ProcessingRate::RateValue rateLCM(1);
1195    unsigned first = 0;
1196    unsigned last = inputSetCount;
1197
1198    for (unsigned i = 0; i < inputSetCount; ++i) {
1199        const ProcessingRate & pr = mStreamSetInputs[i].getRate();
1200        if (pr.isFixed()) {
1201            rateLCM = lcm(rateLCM, pr.getRate());
1202            if (mStreamSetInputs[i].isPrincipal()) {
1203                assert ("A kernel cannot have multiple principle input streams" && (first == 0 && last == inputSetCount));
1204                first = i;
1205                last = i + 1;
1206            }
1207        }       
1208    }
1209
1210    bool noFixedRateOutput = true;
1211
1212    for (const Binding & output : mStreamSetOutputs) {
1213        const ProcessingRate & pr = output.getRate();
1214        if (pr.isFixed()) {
1215            rateLCM = lcm(rateLCM, pr.getRate());
1216            noFixedRateOutput = false;
1217        }
1218    }
1219
1220    if (noFixedRateOutput) {
1221        return;
1222    }
1223
1224    Value * baseInitialProcessedItemCount = nullptr;
1225    Value * scaledInverseOfAvailItemCount = nullptr;
1226
1227    // For each Fixed output stream, this calculates:
1228
1229    //    CEILING(MIN(Available Item Count / Fixed Input Rate) * Fixed Output Rate)
1230
1231    // But avoids the possibility of overflow errors (assuming that each processed item count does not overflow)
1232
1233    for (unsigned i = first; i < last; ++i) {
1234        const ProcessingRate & pr = mStreamSetInputs[i].getRate();
1235        if (pr.isFixed()) {
1236            Value * p = mInitialProcessedItemCount[i];
1237            Value * a = b->CreateSub(mInitialAvailableItemCount[i], p);
1238            const auto & rate = pr.getRate();
1239            if (LLVM_UNLIKELY(rateLCM != rate)) {
1240                const auto factor = rateLCM / rate;
1241                if (LLVM_UNLIKELY(factor.numerator() > 1)) {
1242                    a = b->CreateMul(a, b->getSize(factor.numerator()));
1243                }
1244                if (LLVM_UNLIKELY(factor.denominator() > 1)) {
1245                    a = b->CreateUDiv(a, b->getSize(factor.denominator()));
1246                }
1247            }
1248            if (LLVM_UNLIKELY(rate.denominator() > 1)) {
1249                p = b->CreateMul(p, b->getSize(rate.denominator()));
1250            }
1251            if (LLVM_UNLIKELY(rate.numerator() > 1)) {
1252                p = b->CreateUDiv(p, b->getSize(rate.numerator()));
1253            }
1254            if (scaledInverseOfAvailItemCount) {
1255                scaledInverseOfAvailItemCount = b->CreateUMin(scaledInverseOfAvailItemCount, a);
1256                baseInitialProcessedItemCount = b->CreateUMin(baseInitialProcessedItemCount, p);
1257            } else {
1258                scaledInverseOfAvailItemCount = a;
1259                baseInitialProcessedItemCount = p;
1260            }
1261        }
1262    }
1263
1264    for (const Binding & output : mStreamSetOutputs) {
1265        const auto name = output.getName();
1266        const ProcessingRate & pr = output.getRate();
1267        Value * produced = nullptr;
1268        if (pr.isFixed() && output.nonDeferred()) {
1269            assert (baseInitialProcessedItemCount && scaledInverseOfAvailItemCount);
1270            const auto rate = pr.getRate();
1271            Value * p = baseInitialProcessedItemCount;
1272            if (LLVM_UNLIKELY(rate.numerator() != 1)) {
1273                p = b->CreateMul(p, b->getSize(rate.numerator()));
1274            }
1275            if (LLVM_UNLIKELY(rate.denominator() != 1)) {
1276                p = b->CreateUDiv(p, b->getSize(rate.denominator()));
1277            }
1278            Value * const ic = CreateUDivCeil(b, scaledInverseOfAvailItemCount, rateLCM / pr.getRate());
1279            produced = b->CreateAdd(p, ic);
1280        } else { // check if we have an attribute; if so, get the current produced count and adjust it
1281            bool noAttributes = true;
1282            for (const Attribute & attr : output.getAttributes()) {
1283                if (attr.isAdd() || attr.isRoundUpTo()) {
1284                    noAttributes = false;
1285                    break;
1286                }
1287            }
1288            if (noAttributes) {
1289                continue;
1290            }
1291            produced = b->getProducedItemCount(name);
1292        }
1293        for (const Attribute & attr : output.getAttributes()) {
1294            if (attr.isAdd()) {
1295                produced = b->CreateAdd(produced, b->getSize(attr.amount()));
1296            } else if (attr.isRoundUpTo()) {
1297                produced = b->CreateRoundUp(produced, b->getSize(attr.amount()));
1298            }
1299        }
1300        b->setProducedItemCount(name, produced);
1301    }
1302
1303}
1304
1305/** ------------------------------------------------------------------------------------------------------------- *
1306 * @brief generateMultiBlockLogic
1307 ** ------------------------------------------------------------------------------------------------------------- */
1308void BlockOrientedKernel::generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> & b, Value * const numOfBlocks) {
1309
1310    if (LLVM_UNLIKELY(mStride != b->getBitBlockWidth())) {
1311        report_fatal_error(getName() + ": the Stride (" + std::to_string(mStride) + ") of BlockOrientedKernel "
1312                           "equal to the BitBlockWidth (" + std::to_string(b->getBitBlockWidth()) + ")");
1313    }
1314
1315    Constant * const LOG_2_BLOCK_WIDTH = b->getSize(std::log2(b->getBitBlockWidth()));
1316
1317    BasicBlock * const entryBlock = b->GetInsertBlock();
1318    mStrideLoopBody = b->CreateBasicBlock(getName() + "_strideLoopBody");
1319    BasicBlock * const stridesDone = b->CreateBasicBlock(getName() + "_stridesDone");
1320    BasicBlock * const doFinalBlock = b->CreateBasicBlock(getName() + "_doFinalBlock");
1321    BasicBlock * const segmentDone = b->CreateBasicBlock(getName() + "_segmentDone");
1322
1323    const auto inputSetCount = mStreamSetInputs.size();
1324    Value * baseProcessedIndex[inputSetCount];
1325    Value * baseInputAddress[inputSetCount];
1326    for (unsigned i = 0; i < inputSetCount; i++) {
1327        const ProcessingRate & rate = mStreamSetInputs[i].getRate();
1328        if (LLVM_UNLIKELY(!rate.isFixed())) {
1329            Value * const ic = mInitialProcessedItemCount[i];
1330            baseProcessedIndex[i] = b->CreateLShr(ic, LOG_2_BLOCK_WIDTH);
1331        }
1332        baseInputAddress[i] = mStreamSetInputBaseAddress[i];
1333    }
1334
1335    const auto outputSetCount = mStreamSetOutputs.size();
1336    Value * baseProducedIndex[outputSetCount];
1337    Value * baseOutputAddress[inputSetCount];
1338    for (unsigned i = 0; i < outputSetCount; i++) {
1339        const ProcessingRate & rate = mStreamSetOutputs[i].getRate();
1340        if (LLVM_UNLIKELY(!rate.isFixed())) {
1341            Value * const ic = b->getProducedItemCount(mStreamSetOutputs[i].getName());
1342            baseProducedIndex[i] = b->CreateLShr(ic, LOG_2_BLOCK_WIDTH);
1343        }
1344        baseOutputAddress[i] = mStreamSetOutputBaseAddress[i];
1345    }
1346
1347    b->CreateUnlikelyCondBr(mIsFinal, doFinalBlock, mStrideLoopBody);
1348
1349    /// BLOCK BODY
1350
1351    b->SetInsertPoint(mStrideLoopBody);
1352
1353    if (b->supportsIndirectBr()) {
1354        Value * const baseTarget = BlockAddress::get(segmentDone);
1355        mStrideLoopTarget = b->CreatePHI(baseTarget->getType(), 2, "strideTarget");
1356        mStrideLoopTarget->addIncoming(baseTarget, entryBlock);
1357    }
1358
1359    mStrideBlockIndex = b->CreatePHI(b->getSizeTy(), 2);
1360    mStrideBlockIndex->addIncoming(b->getSize(0), entryBlock);
1361
1362    /// GENERATE DO BLOCK METHOD
1363
1364    for (unsigned i = 0; i < inputSetCount; ++i) {
1365        Value * index = mStrideBlockIndex;
1366        const ProcessingRate & rate = mStreamSetInputs[i].getRate();
1367        if (LLVM_UNLIKELY(!rate.isFixed())) {
1368            Value * ic = b->getProcessedItemCount(mStreamSetInputs[i].getName());
1369            index = b->CreateSub(b->CreateLShr(ic, LOG_2_BLOCK_WIDTH), baseProcessedIndex[i]);
1370        }
1371        mStreamSetInputBaseAddress[i] = b->CreateGEP(mStreamSetInputBaseAddress[i], index);
1372    }
1373
1374    for (unsigned i = 0; i < outputSetCount; ++i) {
1375        Value * index = mStrideBlockIndex;
1376        const ProcessingRate & rate = mStreamSetOutputs[i].getRate();
1377        if (LLVM_UNLIKELY(!rate.isFixed())) {
1378            Value * ic = b->getProducedItemCount(mStreamSetOutputs[i].getName());
1379            index = b->CreateSub(b->CreateLShr(ic, LOG_2_BLOCK_WIDTH), baseProducedIndex[i]);
1380        }
1381        mStreamSetOutputBaseAddress[i] = b->CreateGEP(mStreamSetOutputBaseAddress[i], index);
1382    }
1383
1384    writeDoBlockMethod(b);
1385
1386    BasicBlock * const bodyEnd = b->GetInsertBlock();
1387    if (mStrideLoopTarget) {
1388        mStrideLoopTarget->addIncoming(mStrideLoopTarget, bodyEnd);
1389    }
1390
1391    Value * const nextIndex = b->CreateAdd(mStrideBlockIndex, b->getSize(1));
1392    mStrideBlockIndex->addIncoming(nextIndex, bodyEnd);
1393    Value * const notDone = b->CreateICmpULT(nextIndex, numOfBlocks);
1394    b->CreateCondBr(notDone, mStrideLoopBody, stridesDone);
1395
1396    stridesDone->moveAfter(bodyEnd);
1397
1398    /// STRIDE DONE
1399
1400    b->SetInsertPoint(stridesDone);
1401
1402    // Now conditionally perform the final block processing depending on the doFinal parameter.
1403    if (mStrideLoopTarget) {
1404        mStrideLoopBranch = b->CreateIndirectBr(mStrideLoopTarget, 3);
1405        mStrideLoopBranch->addDestination(doFinalBlock);
1406        mStrideLoopBranch->addDestination(segmentDone);
1407    } else {
1408        b->CreateUnlikelyCondBr(mIsFinal, doFinalBlock, segmentDone);
1409    }
1410
1411    doFinalBlock->moveAfter(stridesDone);
1412
1413    /// DO FINAL BLOCK
1414
1415    b->SetInsertPoint(doFinalBlock);
1416    for (unsigned i = 0; i < inputSetCount; ++i) {
1417        mStreamSetInputBaseAddress[i] = baseInputAddress[i];
1418    }
1419
1420    for (unsigned i = 0; i < outputSetCount; ++i) {
1421        mStreamSetOutputBaseAddress[i] = baseOutputAddress[i];
1422    }
1423
1424    writeFinalBlockMethod(b, getRemainingItems(b));
1425
1426    b->CreateBr(segmentDone);
1427
1428    segmentDone->moveAfter(b->GetInsertBlock());
1429
1430    b->SetInsertPoint(segmentDone);
1431
1432    // Update the branch prediction metadata to indicate that the likely target will be segmentDone
1433    if (mStrideLoopTarget) {
1434        MDBuilder mdb(b->getContext());
1435        const auto destinations = mStrideLoopBranch->getNumDestinations();
1436        uint32_t weights[destinations];
1437        for (unsigned i = 0; i < destinations; ++i) {
1438            weights[i] = (mStrideLoopBranch->getDestination(i) == segmentDone) ? 100 : 1;
1439        }
1440        ArrayRef<uint32_t> bw(weights, destinations);
1441        mStrideLoopBranch->setMetadata(LLVMContext::MD_prof, mdb.createBranchWeights(bw));
1442    }
1443
1444}
1445
1446/** ------------------------------------------------------------------------------------------------------------- *
1447 * @brief getRemainingItems
1448 ** ------------------------------------------------------------------------------------------------------------- */
1449Value * BlockOrientedKernel::getRemainingItems(const std::unique_ptr<KernelBuilder> & b) {
1450    Value * remainingItems = nullptr;
1451    const auto count = mStreamSetInputs.size();
1452    if (count == 1) {
1453        return mAvailableItemCount[0];
1454    } else {
1455        for (unsigned i = 0; i < count; i++) {
1456            if (mStreamSetInputs[i].isPrincipal()) {
1457                return mAvailableItemCount[i];
1458            }
1459        }
1460        for (unsigned i = 0; i < count; ++i) {
1461            const ProcessingRate & r = mStreamSetInputs[i].getRate();
1462            if (r.isFixed()) {
1463                Value * ic = CreateUDivCeil(b, mAvailableItemCount[i], r.getRate());
1464                if (remainingItems) {
1465                    remainingItems = b->CreateUMin(remainingItems, ic);
1466                } else {
1467                    remainingItems = ic;
1468                }
1469            }
1470        }
1471    }
1472    return remainingItems;
1473}
1474
1475/** ------------------------------------------------------------------------------------------------------------- *
1476 * @brief writeDoBlockMethod
1477 ** ------------------------------------------------------------------------------------------------------------- */
1478inline void BlockOrientedKernel::writeDoBlockMethod(const std::unique_ptr<KernelBuilder> & b) {
1479
1480    Value * const self = getInstance();
1481    Function * const cp = mCurrentMethod;
1482    auto ip = b->saveIP();
1483    std::vector<Value *> availableItemCount(0);
1484
1485    /// Check if the do block method is called and create the function if necessary
1486    if (!b->supportsIndirectBr()) {
1487
1488        std::vector<Type *> params;
1489        params.reserve(1 + mAvailableItemCount.size());
1490        params.push_back(self->getType());
1491        for (Value * avail : mAvailableItemCount) {
1492            params.push_back(avail->getType());
1493        }
1494
1495        FunctionType * const type = FunctionType::get(b->getVoidTy(), params, false);
1496        mCurrentMethod = Function::Create(type, GlobalValue::InternalLinkage, getName() + DO_BLOCK_SUFFIX, b->getModule());
1497        mCurrentMethod->setCallingConv(CallingConv::C);
1498        mCurrentMethod->setDoesNotThrow();
1499        auto args = mCurrentMethod->arg_begin();
1500        args->setName("self");
1501        setInstance(&*args);
1502        availableItemCount.reserve(mAvailableItemCount.size());
1503        while (++args != mCurrentMethod->arg_end()) {
1504            availableItemCount.push_back(&*args);
1505        }
1506        assert (availableItemCount.size() == mAvailableItemCount.size());
1507        mAvailableItemCount.swap(availableItemCount);
1508        b->SetInsertPoint(BasicBlock::Create(b->getContext(), "entry", mCurrentMethod));
1509    }
1510
1511    generateDoBlockMethod(b); // must be implemented by the BlockOrientedKernelBuilder subtype
1512
1513    if (!b->supportsIndirectBr()) {
1514        // Restore the DoSegment function state then call the DoBlock method
1515        b->CreateRetVoid();
1516        mDoBlockMethod = mCurrentMethod;
1517        b->restoreIP(ip);
1518        setInstance(self);
1519        mCurrentMethod = cp;
1520        mAvailableItemCount.swap(availableItemCount);
1521        CreateDoBlockMethodCall(b);
1522    }
1523
1524}
1525
1526/** ------------------------------------------------------------------------------------------------------------- *
1527 * @brief writeFinalBlockMethod
1528 ** ------------------------------------------------------------------------------------------------------------- */
1529inline void BlockOrientedKernel::writeFinalBlockMethod(const std::unique_ptr<KernelBuilder> & b, Value * remainingItems) {
1530
1531    Value * const self = getInstance();
1532    Function * const cp = mCurrentMethod;
1533    Value * const remainingItemCount = remainingItems;
1534    auto ip = b->saveIP();
1535    std::vector<Value *> availableItemCount(0);
1536
1537    if (!b->supportsIndirectBr()) {
1538        std::vector<Type *> params;
1539        params.reserve(2 + mAvailableItemCount.size());
1540        params.push_back(self->getType());
1541        params.push_back(b->getSizeTy());
1542        for (Value * avail : mAvailableItemCount) {
1543            params.push_back(avail->getType());
1544        }
1545        FunctionType * const type = FunctionType::get(b->getVoidTy(), params, false);
1546        mCurrentMethod = Function::Create(type, GlobalValue::InternalLinkage, getName() + FINAL_BLOCK_SUFFIX, b->getModule());
1547        mCurrentMethod->setCallingConv(CallingConv::C);
1548        mCurrentMethod->setDoesNotThrow();
1549        auto args = mCurrentMethod->arg_begin();
1550        args->setName("self");
1551        setInstance(&*args);
1552        remainingItems = &*(++args);
1553        remainingItems->setName("remainingItems");
1554        availableItemCount.reserve(mAvailableItemCount.size());
1555        while (++args != mCurrentMethod->arg_end()) {
1556            availableItemCount.push_back(&*args);
1557        }
1558        assert (availableItemCount.size() == mAvailableItemCount.size());
1559        mAvailableItemCount.swap(availableItemCount);
1560        b->SetInsertPoint(BasicBlock::Create(b->getContext(), "entry", mCurrentMethod));
1561    }
1562
1563    generateFinalBlockMethod(b, remainingItems); // may be implemented by the BlockOrientedKernel subtype
1564
1565    if (!b->supportsIndirectBr()) {
1566        b->CreateRetVoid();
1567        b->restoreIP(ip);
1568        setInstance(self);
1569        mAvailableItemCount.swap(availableItemCount);
1570        // Restore the DoSegment function state then call the DoFinal method
1571        std::vector<Value *> args;
1572        args.reserve(2 + mAvailableItemCount.size());
1573        args.push_back(self);
1574        args.push_back(remainingItemCount);
1575        args.insert(args.end(), mAvailableItemCount.begin(), mAvailableItemCount.end());
1576        b->CreateCall(mCurrentMethod, args);
1577        mCurrentMethod = cp;
1578    }
1579
1580}
1581
1582/** ------------------------------------------------------------------------------------------------------------- *
1583 * @brief generateFinalBlockMethod
1584 ** ------------------------------------------------------------------------------------------------------------- */
1585void BlockOrientedKernel::generateFinalBlockMethod(const std::unique_ptr<KernelBuilder> & b, Value * /* remainingItems */) {
1586    //  The default finalBlock method simply dispatches to the doBlock routine.
1587    CreateDoBlockMethodCall(b);
1588}
1589
1590void BlockOrientedKernel::CreateDoBlockMethodCall(const std::unique_ptr<KernelBuilder> & b) {
1591    if (b->supportsIndirectBr()) {
1592        BasicBlock * const bb = b->CreateBasicBlock("resume");
1593        mStrideLoopBranch->addDestination(bb);
1594        BasicBlock * const current = b->GetInsertBlock();
1595        mStrideLoopTarget->addIncoming(BlockAddress::get(bb), current);
1596        mStrideBlockIndex->addIncoming(b->getSize(0), current);
1597        b->CreateBr(mStrideLoopBody);
1598        bb->moveAfter(current);
1599        b->SetInsertPoint(bb);
1600    } else {
1601        std::vector<Value *> args;
1602        args.reserve(1 + mAvailableItemCount.size());
1603        args.push_back(getInstance());
1604        args.insert(args.end(), mAvailableItemCount.begin(), mAvailableItemCount.end());
1605        b->CreateCall(mDoBlockMethod, args);
1606    }
1607}
1608
1609static inline std::string annotateKernelNameWithDebugFlags(std::string && name) {
1610    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1611        name += "_EA";
1612    }
1613    name += "_O" + std::to_string((int)codegen::OptLevel);
1614    return name;
1615}
1616
1617// CONSTRUCTOR
1618Kernel::Kernel(std::string && kernelName,
1619               Bindings && stream_inputs,
1620               Bindings && stream_outputs,
1621               Bindings && scalar_parameters,
1622               Bindings && scalar_outputs,
1623               Bindings && internal_scalars)
1624: KernelInterface(annotateKernelNameWithDebugFlags(std::move(kernelName))
1625                  , std::move(stream_inputs), std::move(stream_outputs)
1626                  , std::move(scalar_parameters), std::move(scalar_outputs)
1627                  , std::move(internal_scalars))
1628, mCurrentMethod(nullptr)
1629, mAvailablePrincipalItemCount(nullptr)
1630, mStride(0)
1631, mIsFinal(nullptr)
1632, mOutputScalarResult(nullptr)
1633, mIsGenerated(false) {
1634
1635}
1636
1637Kernel::~Kernel() {
1638
1639}
1640
1641// MULTI-BLOCK KERNEL CONSTRUCTOR
1642MultiBlockKernel::MultiBlockKernel(std::string && kernelName,
1643                                   Bindings && stream_inputs,
1644                                   Bindings && stream_outputs,
1645                                   Bindings && scalar_parameters,
1646                                   Bindings && scalar_outputs,
1647                                   Bindings && internal_scalars)
1648: Kernel(std::move(kernelName), std::move(stream_inputs), std::move(stream_outputs), std::move(scalar_parameters), std::move(scalar_outputs), std::move(internal_scalars)) {
1649
1650}
1651
1652// CONSTRUCTOR
1653BlockOrientedKernel::BlockOrientedKernel(std::string && kernelName,
1654                                         Bindings && stream_inputs,
1655                                         Bindings && stream_outputs,
1656                                         Bindings && scalar_parameters,
1657                                         Bindings && scalar_outputs,
1658                                         Bindings && internal_scalars)
1659: MultiBlockKernel(std::move(kernelName), std::move(stream_inputs), std::move(stream_outputs), std::move(scalar_parameters), std::move(scalar_outputs), std::move(internal_scalars))
1660, mDoBlockMethod(nullptr)
1661, mStrideLoopBody(nullptr)
1662, mStrideLoopBranch(nullptr)
1663, mStrideLoopTarget(nullptr)
1664, mStrideBlockIndex(nullptr) {
1665
1666}
1667
1668// CONSTRUCTOR
1669SegmentOrientedKernel::SegmentOrientedKernel(std::string && kernelName,
1670                                             Bindings && stream_inputs,
1671                                             Bindings && stream_outputs,
1672                                             Bindings && scalar_parameters,
1673                                             Bindings && scalar_outputs,
1674                                             Bindings && internal_scalars)
1675: Kernel(std::move(kernelName), std::move(stream_inputs), std::move(stream_outputs), std::move(scalar_parameters), std::move(scalar_outputs), std::move(internal_scalars)) {
1676
1677}
1678
1679
1680}
Note: See TracBrowser for help on using the repository browser.