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

Last change on this file since 5782 was 5782, checked in by nmedfort, 14 months ago

Initial check-in of LookAhead? support; modified LineBreakKernel? to compute CR+LF using LookAhead?(1) + misc. fixes.

File size: 74.0 KB
RevLine 
[4924]1/*
[5641]2 *  Copyright (c) 2016-7 International Characters.
[4924]3 *  This software is licensed to the public under the Open Software License 3.0.
4 */
5
6#include "kernel.h"
[5425]7#include <toolchain/toolchain.h>
[5297]8#include <kernels/streamset.h>
9#include <llvm/IR/Constants.h>
10#include <llvm/IR/Function.h>
11#include <llvm/IR/Instructions.h>
[5350]12#include <llvm/IR/MDBuilder.h>
[5267]13#include <llvm/IR/Module.h>
14#include <llvm/Support/raw_ostream.h>
[5732]15#if LLVM_VERSION_INTEGER < LLVM_4_0_0
[5392]16#include <llvm/Bitcode/ReaderWriter.h>
[5732]17#else
18#include <llvm/Bitcode/BitcodeWriter.h>
19#endif
[5350]20#include <llvm/Transforms/Utils/Local.h>
[5408]21#include <kernels/streamset.h>
22#include <sstream>
[5436]23#include <kernels/kernel_builder.h>
[5755]24#include <boost/math/common_factor.hpp>
[5522]25#include <llvm/Support/Debug.h>
[4924]26
[5435]27using namespace llvm;
28using namespace parabix;
[5706]29using namespace boost::math;
[5287]30
[5435]31namespace kernel {
[5287]32
[5435]33const std::string Kernel::DO_BLOCK_SUFFIX = "_DoBlock";
34const std::string Kernel::FINAL_BLOCK_SUFFIX = "_FinalBlock";
[5439]35const std::string Kernel::MULTI_BLOCK_SUFFIX = "_MultiBlock";
[5435]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";
[5456]43const std::string Kernel::CYCLECOUNT_SCALAR = "CPUcycles";
[5292]44
[5706]45/** ------------------------------------------------------------------------------------------------------------- *
46 * @brief addScalar
47 ** ------------------------------------------------------------------------------------------------------------- */
[5435]48unsigned Kernel::addScalar(Type * const type, const std::string & name) {
[5063]49    if (LLVM_UNLIKELY(mKernelStateType != nullptr)) {
[5320]50        report_fatal_error("Cannot add field " + name + " to " + getName() + " after kernel state finalized");
[4924]51    }
[5755]52    if (LLVM_UNLIKELY(mKernelFieldMap.count(name))) {
[5320]53        report_fatal_error(getName() + " already contains scalar field " + name);
[5283]54    }
[5227]55    const auto index = mKernelFields.size();
[5755]56    mKernelFieldMap.emplace(name, index);
[5227]57    mKernelFields.push_back(type);
58    return index;
[4924]59}
[4968]60
[5706]61
62/** ------------------------------------------------------------------------------------------------------------- *
63 * @brief addUnnamedScalar
64 ** ------------------------------------------------------------------------------------------------------------- */
[5435]65unsigned Kernel::addUnnamedScalar(Type * const type) {
[5283]66    if (LLVM_UNLIKELY(mKernelStateType != nullptr)) {
[5418]67        report_fatal_error("Cannot add unnamed field  to " + getName() + " after kernel state finalized");
[5283]68    }
69    const auto index = mKernelFields.size();
70    mKernelFields.push_back(type);
71    return index;
72}
73
[5706]74
75/** ------------------------------------------------------------------------------------------------------------- *
76 * @brief prepareStreamSetNameMap
77 ** ------------------------------------------------------------------------------------------------------------- */
[5435]78void Kernel::prepareStreamSetNameMap() {
[5299]79    for (unsigned i = 0; i < mStreamSetInputs.size(); i++) {
[5706]80        mStreamMap.emplace(mStreamSetInputs[i].getName(), std::make_pair(Port::Input, i));
[5299]81    }
82    for (unsigned i = 0; i < mStreamSetOutputs.size(); i++) {
[5706]83        mStreamMap.emplace(mStreamSetOutputs[i].getName(), std::make_pair(Port::Output, i));
[5299]84    }
85}
[5440]86
[5706]87
88/** ------------------------------------------------------------------------------------------------------------- *
89 * @brief bindPorts
90 ** ------------------------------------------------------------------------------------------------------------- */
[5446]91void Kernel::bindPorts(const StreamSetBuffers & inputs, const StreamSetBuffers & outputs) {
[5440]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());
[5446]132}
133
[5706]134
135/** ------------------------------------------------------------------------------------------------------------- *
136 * @brief getCacheName
137 ** ------------------------------------------------------------------------------------------------------------- */
[5630]138std::string Kernel::getCacheName(const std::unique_ptr<KernelBuilder> & idb) const {
139    std::stringstream cacheName;
[5446]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    }
[5630]147    return cacheName.str();
[5440]148}
149
[5706]150
151/** ------------------------------------------------------------------------------------------------------------- *
152 * @brief setModule
153 ** ------------------------------------------------------------------------------------------------------------- */
[5630]154Module * Kernel::setModule(Module * const module) {
155    assert (mModule == nullptr || mModule == module);
156    assert (module != nullptr);
[5446]157    mModule = module;
158    return mModule;
159}
160
[5706]161
162/** ------------------------------------------------------------------------------------------------------------- *
163 * @brief makeModule
164 ** ------------------------------------------------------------------------------------------------------------- */
[5630]165Module * Kernel::makeModule(const std::unique_ptr<kernel::KernelBuilder> & idb) {
[5743]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);
[5630]170}
171
[5706]172
173/** ------------------------------------------------------------------------------------------------------------- *
174 * @brief prepareKernel
175 ** ------------------------------------------------------------------------------------------------------------- */
[5440]176void Kernel::prepareKernel(const std::unique_ptr<KernelBuilder> & idb) {
177    assert ("KernelBuilder does not have a valid IDISA Builder" && idb);
[5246]178    if (LLVM_UNLIKELY(mKernelStateType != nullptr)) {
[5646]179        report_fatal_error(getName() + ": cannot prepare kernel after kernel state finalized");
[5246]180    }
[5706]181    addBaseKernelProperties(idb);
[5630]182    addInternalKernelProperties(idb);
[5620]183    // NOTE: StructType::create always creates a new type even if an identical one exists.
[5630]184    if (LLVM_UNLIKELY(mModule == nullptr)) {
[5743]185        makeModule(idb);
[5630]186    }
187    mKernelStateType = mModule->getTypeByName(getName());
[5620]188    if (LLVM_LIKELY(mKernelStateType == nullptr)) {
189        mKernelStateType = StructType::create(idb->getContext(), mKernelFields, getName());
[5646]190        assert (mKernelStateType);
[5755]191    }
[4970]192}
[5630]193
[5706]194
195/** ------------------------------------------------------------------------------------------------------------- *
196 * @brief prepareCachedKernel
197 ** ------------------------------------------------------------------------------------------------------------- */
[5630]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)) {
[5646]201        report_fatal_error(getName() + ": cannot prepare kernel after kernel state finalized");
[5630]202    }
203    assert (getModule());
[5706]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) {
[5755]215
216    if (mStreamMap.empty()) {
217        prepareStreamSetNameMap();
218    }
219
220    normalizeStreamProcessingRates();
221
[5706]222    const unsigned inputSetCount = mStreamSetInputs.size();
223    const unsigned outputSetCount = mStreamSetOutputs.size();
[5755]224
[5706]225    assert (inputSetCount == mStreamSetInputBuffers.size());
226    assert (outputSetCount == mStreamSetOutputBuffers.size());
227
[5630]228    if (mStride == 0) {
229        // Set the default kernel stride.
[5706]230        mStride = idb->getBitBlockWidth();
[5630]231    }
[5706]232
[5646]233    IntegerType * const sizeTy = idb->getSizeTy();
[5630]234
[5706]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    }
[5646]242
[5706]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        //}
[5630]249    }
250
[5706]251    for (unsigned i = 0; i < inputSetCount; i++) {
252        mScalarInputs.emplace_back(mStreamSetInputBuffers[i]->getStreamSetHandle()->getType(), mStreamSetInputs[i].getName() + BUFFER_PTR_SUFFIX);
[5630]253    }
[5706]254    for (unsigned i = 0; i < outputSetCount; i++) {
255        mScalarInputs.emplace_back(mStreamSetOutputBuffers[i]->getStreamSetHandle()->getType(), mStreamSetOutputs[i].getName() + BUFFER_PTR_SUFFIX);
256    }
[5630]257    for (const auto & binding : mScalarInputs) {
[5706]258        addScalar(binding.getType(), binding.getName());
[5630]259    }
260    for (const auto & binding : mScalarOutputs) {
[5706]261        addScalar(binding.getType(), binding.getName());
[5630]262    }
263    for (const auto & binding : mInternalScalars) {
[5706]264        addScalar(binding.getType(), binding.getName());
[5630]265    }
[5733]266    Type * const consumerSetTy = StructType::get(idb->getContext(), {sizeTy, sizeTy->getPointerTo()->getPointerTo()})->getPointerTo();
[5630]267    for (unsigned i = 0; i < mStreamSetOutputs.size(); i++) {
[5706]268        addScalar(consumerSetTy, mStreamSetOutputs[i].getName() + CONSUMER_SUFFIX);
[5630]269    }
270    addScalar(sizeTy, LOGICAL_SEGMENT_NO_SCALAR);
271    addScalar(idb->getInt1Ty(), TERMINATION_SIGNAL);
272    for (unsigned i = 0; i < mStreamSetOutputs.size(); i++) {
[5706]273        addScalar(sizeTy, mStreamSetOutputs[i].getName() + CONSUMED_ITEM_COUNT_SUFFIX);
[5630]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);
[5646]279
[5630]280}
[4970]281
[5552]282
[5706]283/** ------------------------------------------------------------------------------------------------------------- *
284 * @brief makeSignature
285 *
286 * Default kernel signature: generate the IR and emit as byte code.
287 ** ------------------------------------------------------------------------------------------------------------- */
[5440]288std::string Kernel::makeSignature(const std::unique_ptr<kernel::KernelBuilder> & idb) {
289    assert ("KernelBuilder does not have a valid IDISA Builder" && idb.get());
[5464]290    if (LLVM_UNLIKELY(hasSignature())) {
[5440]291        generateKernel(idb);
[5401]292        std::string signature;
293        raw_string_ostream OS(signature);
[5431]294        WriteBitcodeToFile(getModule(), OS);
[5401]295        return signature;
[5464]296    } else {
297        return getModule()->getModuleIdentifier();
[5401]298    }
[5392]299}
300
[5706]301
302/** ------------------------------------------------------------------------------------------------------------- *
303 * @brief generateKernel
304 ** ------------------------------------------------------------------------------------------------------------- */
[5440]305void Kernel::generateKernel(const std::unique_ptr<kernel::KernelBuilder> & idb) {
306    assert ("KernelBuilder does not have a valid IDISA Builder" && idb.get());
[5411]307    // If the module id cannot uniquely identify this kernel, "generateKernelSignature()" will have already
[5401]308    // generated the unoptimized IR.
309    if (!mIsGenerated) {
[5440]310        const auto m = idb->getModule();
311        const auto ip = idb->saveIP();
[5630]312        // const auto saveInstance = getInstance();
[5440]313        idb->setModule(mModule);
314        addKernelDeclarations(idb);
315        callGenerateInitializeMethod(idb);
316        callGenerateDoSegmentMethod(idb);
317        callGenerateFinalizeMethod(idb);
[5630]318        // setInstance(saveInstance);
[5440]319        idb->setModule(m);
320        idb->restoreIP(ip);
[5431]321        mIsGenerated = true;
[4995]322    }
[5250]323}
[5246]324
[5706]325
326/** ------------------------------------------------------------------------------------------------------------- *
327 * @brief callGenerateInitializeMethod
328 ** ------------------------------------------------------------------------------------------------------------- */
[5440]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));
[5347]332    Function::arg_iterator args = mCurrentMethod->arg_begin();
[5408]333    setInstance(&*(args++));
[5440]334    idb->CreateStore(ConstantAggregateZero::get(mKernelStateType), getInstance());
[5436]335    for (const auto & binding : mScalarInputs) {
[5706]336        idb->setScalarField(binding.getName(), &*(args++));
[5051]337    }
[5436]338    for (const auto & binding : mStreamSetOutputs) {
[5706]339        idb->setConsumerLock(binding.getName(), &*(args++));
[5408]340    }
[5440]341    generateInitializeMethod(idb);
342    idb->CreateRetVoid();
[5051]343}
344
[5706]345/** ------------------------------------------------------------------------------------------------------------- *
346 * @brief callGenerateDoSegmentMethod
347 ** ------------------------------------------------------------------------------------------------------------- */
[5440]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));
[5411]351    auto args = mCurrentMethod->arg_begin();
352    setInstance(&*(args++));
[5418]353    mIsFinal = &*(args++);
[5755]354    mAvailablePrincipalItemCount = nullptr;
[5418]355    const auto n = mStreamSetInputs.size();
356    mAvailableItemCount.resize(n, nullptr);
[5706]357    for (unsigned i = 0; i < n; i++) {
358        assert (args != mCurrentMethod->arg_end());
[5418]359        mAvailableItemCount[i] = &*(args++);
360    }
[5706]361    assert (args == mCurrentMethod->arg_end());
362    generateKernelMethod(idb); // must be overridden by the Kernel subtype
[5418]363    mIsFinal = nullptr;
364    mAvailableItemCount.clear();
[5440]365    idb->CreateRetVoid();
[5411]366}
367
[5706]368
369/** ------------------------------------------------------------------------------------------------------------- *
370 * @brief callGenerateFinalizeMethod
371 ** ------------------------------------------------------------------------------------------------------------- */
[5440]372inline void Kernel::callGenerateFinalizeMethod(const std::unique_ptr<KernelBuilder> & idb) {
373    mCurrentMethod = getTerminateFunction(idb->getModule());
374    idb->SetInsertPoint(BasicBlock::Create(idb->getContext(), "entry", mCurrentMethod));
[5418]375    auto args = mCurrentMethod->arg_begin();
376    setInstance(&*(args++));
[5706]377    generateFinalizeMethod(idb); // may be overridden by the Kernel subtype
[5418]378    const auto n = mScalarOutputs.size();
379    if (n == 0) {
[5440]380        idb->CreateRetVoid();
[5418]381    } else {
382        Value * outputs[n];
383        for (unsigned i = 0; i < n; ++i) {
[5706]384            outputs[i] = idb->getScalarField(mScalarOutputs[i].getName());
[5418]385        }
386        if (n == 1) {
[5440]387            idb->CreateRet(outputs[0]);
[5418]388        } else {
[5440]389            idb->CreateAggregateRet(outputs, n);
[5418]390        }
391    }
392}
393
[5706]394
395/** ------------------------------------------------------------------------------------------------------------- *
396 * @brief getScalarIndex
397 ** ------------------------------------------------------------------------------------------------------------- */
[5435]398unsigned Kernel::getScalarIndex(const std::string & name) const {
[5755]399    const auto f = mKernelFieldMap.find(name);
400    if (LLVM_UNLIKELY(f == mKernelFieldMap.end())) {
[5706]401        assert (false);
[5320]402        report_fatal_error(getName() + " does not contain scalar: " + name);
[5000]403    }
[5435]404    return f->second;
[4959]405}
[4924]406
[5706]407
408/** ------------------------------------------------------------------------------------------------------------- *
409 * @brief createInstance
410 ** ------------------------------------------------------------------------------------------------------------- */
[5440]411Value * Kernel::createInstance(const std::unique_ptr<KernelBuilder> & idb) {
412    assert ("KernelBuilder does not have a valid IDISA Builder" && idb);
[5246]413    if (LLVM_UNLIKELY(mKernelStateType == nullptr)) {
[5320]414        report_fatal_error("Cannot instantiate " + getName() + " before calling prepareKernel()");
[5246]415    }
[5440]416    setInstance(idb->CreateCacheAlignedAlloca(mKernelStateType));
[5408]417    return getInstance();
418}
[5320]419
[5706]420
421/** ------------------------------------------------------------------------------------------------------------- *
422 * @brief initializeInstance
423 ** ------------------------------------------------------------------------------------------------------------- */
[5440]424void Kernel::initializeInstance(const std::unique_ptr<KernelBuilder> & idb) {
425    assert ("KernelBuilder does not have a valid IDISA Builder" && idb);
[5408]426    if (LLVM_UNLIKELY(getInstance() == nullptr)) {
427        report_fatal_error("Cannot initialize " + getName() + " before calling createInstance()");
428    }
[5320]429    std::vector<Value *> args;
[5408]430    args.reserve(1 + mInitialArguments.size() + mStreamSetInputBuffers.size() + (mStreamSetOutputBuffers.size() * 2));
431    args.push_back(getInstance());
[5320]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);
[5133]439    }
[5320]440    for (unsigned i = 0; i < mStreamSetInputBuffers.size(); ++i) {
441        assert (mStreamSetInputBuffers[i]);
[5542]442        Value * arg = mStreamSetInputBuffers[i]->getStreamSetHandle();
[5320]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);
[5133]448    }
[5320]449    assert (mStreamSetInputs.size() == mStreamSetInputBuffers.size());
450    for (unsigned i = 0; i < mStreamSetOutputBuffers.size(); ++i) {
451        assert (mStreamSetOutputBuffers[i]);
[5542]452        Value * arg = mStreamSetOutputBuffers[i]->getStreamSetHandle();
[5320]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);
[5133]458    }
[5320]459    assert (mStreamSetOutputs.size() == mStreamSetOutputBuffers.size());
[5440]460    IntegerType * const sizeTy = idb->getSizeTy();
[5408]461    PointerType * const sizePtrTy = sizeTy->getPointerTo();
462    PointerType * const sizePtrPtrTy = sizePtrTy->getPointerTo();
[5733]463    StructType * const consumerTy = StructType::get(idb->getContext(), {sizeTy, sizePtrPtrTy});
[5408]464    for (unsigned i = 0; i < mStreamSetOutputBuffers.size(); ++i) {
[5418]465        const auto output = mStreamSetOutputBuffers[i];
466        const auto & consumers = output->getConsumers();
[5411]467        const auto n = consumers.size();
[5440]468        AllocaInst * const outputConsumers = idb->CreateAlloca(consumerTy);
469        Value * const consumerSegNoArray = idb->CreateAlloca(ArrayType::get(sizePtrTy, n));
[5408]470        for (unsigned i = 0; i < n; ++i) {
[5435]471            Kernel * const consumer = consumers[i];
[5418]472            assert ("all instances must be created prior to initialization of any instance" && consumer->getInstance());
[5440]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) }));
[5408]476        }
[5440]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);
[5408]482        args.push_back(outputConsumers);
483    }
[5440]484    idb->CreateCall(getInitFunction(idb->getModule()), args);
[5133]485}
[5104]486
[5706]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/** ------------------------------------------------------------------------------------------------------------- *
[5755]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/** ------------------------------------------------------------------------------------------------------------- *
[5757]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/** ------------------------------------------------------------------------------------------------------------- *
[5755]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/** ------------------------------------------------------------------------------------------------------------- *
[5706]576 * @brief generateKernelMethod
577 ** ------------------------------------------------------------------------------------------------------------- */
578void SegmentOrientedKernel::generateKernelMethod(const std::unique_ptr<KernelBuilder> & b) {
579    const auto inputSetCount = mStreamSetInputs.size();
[5755]580    mStreamSetInputBaseAddress.resize(inputSetCount);
[5706]581    for (unsigned i = 0; i < inputSetCount; ++i) {
[5755]582        mStreamSetInputBaseAddress[i] = nullptr;
[5706]583    }
584    const auto outputSetCount = mStreamSetOutputs.size();
[5755]585    mStreamSetOutputBaseAddress.resize(outputSetCount);
[5706]586    for (unsigned i = 0; i < outputSetCount; ++i) {
[5755]587        mStreamSetOutputBaseAddress[i] = nullptr;
[5706]588    }
589    generateDoSegmentMethod(b);
[5755]590}
[5706]591
[5755]592/** ------------------------------------------------------------------------------------------------------------- *
593 * @brief requiresBufferedFinalStride
594 ** ------------------------------------------------------------------------------------------------------------- */
[5757]595inline bool requiresBufferedFinalStride(const Binding & binding) {
596    if (LLVM_LIKELY(isa<ArrayType>(binding.getType()))) {
597        return binding.getType()->getArrayNumElements() == 1;
[5755]598    }
599    return true;
[5706]600}
601
602/** ------------------------------------------------------------------------------------------------------------- *
[5755]603 * @brief getItemWidth
604 ** ------------------------------------------------------------------------------------------------------------- */
605inline unsigned 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 getUpperBound
615 ** ------------------------------------------------------------------------------------------------------------- */
616bool 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 getItemAlignment
627 ** ------------------------------------------------------------------------------------------------------------- */
628inline unsigned MultiBlockKernel::getItemAlignment(const Binding & binding) const {
629    const auto & rate = binding.getRate();
[5782]630    if (rate.isFixed() && binding.nonDeferred()) {
631        const auto r = rate.getRate();
632        auto n = (r.numerator() * mStride);
[5755]633        if (LLVM_LIKELY(r.denominator() == 1)) {
634            return n;
635        } else if (LLVM_LIKELY((n % r.denominator()) == 0)) {
636            return n / r.denominator();
637        }
638    }
639    return 1; // ∀x GCD(x, x + 1) = 1
640}
641
642/** ------------------------------------------------------------------------------------------------------------- *
643 * @brief getStrideSize
644 ** ------------------------------------------------------------------------------------------------------------- */
645llvm::Value * MultiBlockKernel::getStrideSize(const std::unique_ptr<KernelBuilder> & b, const ProcessingRate & rate) {
646    // NOTE: if we ever support feedback loops, using upper bound could lead to a deadlock due to data starvation
647    const auto r = getUpperBound(rate);
648    if (r.numerator() == 0) {
649        return nullptr;
650    } else {
651        assert ((r.numerator() * mStride) % r.denominator() == 0);
652        return b->getSize((r.numerator() * mStride) / r.denominator());
653    }
654}
655
656/** ------------------------------------------------------------------------------------------------------------- *
[5706]657 * @brief generateKernelMethod
658 ** ------------------------------------------------------------------------------------------------------------- */
[5755]659void MultiBlockKernel::generateKernelMethod(const std::unique_ptr<KernelBuilder> & b) {
[5706]660
[5755]661    if (LLVM_UNLIKELY((mStride % b->getBitBlockWidth()) != 0)) {
662        report_fatal_error(getName() + ": the Stride (" + std::to_string(mStride) + ") of MultiBlockKernel "
663                           "must be a multiple of the BitBlockWidth (" + std::to_string(b->getBitBlockWidth()) + ")");
664    }
665
[5782]666    using AttributeId = kernel::Attribute::KindId;
667    using RateValue = ProcessingRate::RateValue;
668
[5706]669    const auto inputSetCount = mStreamSetInputs.size();
670    const auto outputSetCount = mStreamSetOutputs.size();
671
[5755]672    // Define and allocate the temporary buffer area in the prolog.
[5757]673    const auto blockAlignment = b->getBitBlockWidth() / 8;
[5771]674    AllocaInst * temporaryInputBuffer[inputSetCount];
[5755]675    for (unsigned i = 0; i < inputSetCount; ++i) {
[5782]676        const Binding & input = mStreamSetInputs[i];
[5771]677        const ProcessingRate & rate = input.getRate();
678        if (isTransitivelyUnknownRate(rate)) {
[5755]679            report_fatal_error("MultiBlock kernels do not support unknown rate input streams or streams relative to an unknown rate input.");
[5782]680        } else if (rate.isFixed() && !requiresBufferedFinalStride(input)) {
[5771]681            temporaryInputBuffer[i] = nullptr;
682        } else {
683            Type * const ty = mStreamSetInputBuffers[i]->getStreamSetBlockType();
[5782]684            auto ub = getUpperBound(rate);
685            if (LLVM_UNLIKELY(input.hasLookahead())) {
686                ub += RateValue(input.getLookahead(), mStride);
687            }
688            Constant * const arraySize = b->getInt64(ceiling(ub));
[5771]689            AllocaInst * const ptr = b->CreateAlignedAlloca(ty, blockAlignment, arraySize);
690            assert (ptr->isStaticAlloca());
691            temporaryInputBuffer[i] = ptr;
692        }
[5755]693    }
694
[5771]695    AllocaInst * temporaryOutputBuffer[outputSetCount];
[5755]696    for (unsigned i = 0; i < outputSetCount; i++) {
[5782]697        const Binding & output = mStreamSetOutputs[i];
[5771]698        const ProcessingRate & rate = output.getRate();
[5782]699        if (LLVM_UNLIKELY(isTransitivelyUnknownRate(rate) || (rate.isFixed() && !requiresBufferedFinalStride(output)))) {
[5755]700            temporaryOutputBuffer[i] = nullptr;
701        } else {           
702            auto ub = getUpperBound(rate);
703            if (LLVM_UNLIKELY(mStreamSetOutputBuffers[i]->supportsCopyBack() && requiresCopyBack(rate))) {
704                ub += mStreamSetOutputBuffers[i]->overflowSize();
[5706]705            }
[5771]706            Type * const ty = mStreamSetOutputBuffers[i]->getStreamSetBlockType();
[5782]707            Constant * const arraySize = b->getInt64(ceiling(ub));
[5771]708            AllocaInst * const ptr = b->CreateAlignedAlloca(ty, blockAlignment, arraySize);
709            assert (ptr->isStaticAlloca());
710            temporaryOutputBuffer[i] = ptr;
[5706]711        }
712    }
713
714    // Now we iteratively process these blocks using the doMultiBlock method.
715    // In each iteration, we check how many linearly accessible / writable
716    // items can be processed with our current input / output buffers. If we
717    // cannot support an full stride, we check whether (a) there is enough
718    // input data to process but it is not linearly accessible, in which case
719    // we move the data into temporary buffers or (b) there is not enough data
720    // to process, in which case we abort unless IsFinal was set.
721
[5755]722    Constant * const ZERO = b->getSize(0);
723    Constant * const ONE = b->getSize(1);
724    Constant * const LOG_2_BLOCK_WIDTH = b->getSize(std::log2(b->getBitBlockWidth()));
725    Constant * const BLOCK_WIDTH_MASK = b->getSize(b->getBitBlockWidth() - 1);
726
[5706]727    // Now proceed with creation of the doSegment method.
[5755]728    BasicBlock * const segmentLoop = b->CreateBasicBlock("SegmentLoop");
[5706]729
[5755]730    b->CreateBr(segmentLoop);
731
[5706]732    /// DO SEGMENT LOOP
733
[5755]734    b->SetInsertPoint(segmentLoop);
[5706]735
[5755]736    // For each input buffer, get the initial processed item count, base input pointer, and the number of
737    // linearly available strides.
[5706]738    Value * numOfStrides = nullptr;
[5782]739    mInitialAvailableItemCount.assign(mAvailableItemCount.begin(), mAvailableItemCount.end());
[5755]740    mInitialProcessedItemCount.resize(inputSetCount);
741    mStreamSetInputBaseAddress.resize(inputSetCount);
742    Value * inputStrideSize[inputSetCount];
[5706]743    for (unsigned i = 0; i < inputSetCount; i++) {
[5782]744        const Binding & input = mStreamSetInputs[i];
[5755]745        const auto & name = input.getName();
746        const ProcessingRate & rate = input.getRate();
[5782]747        Value * processed = b->getProcessedItemCount(name);
748        //b->CallPrintInt(getName() + "_" + name + "_processed", processed);
749
750        mInitialProcessedItemCount[i] = processed;
751        Value * baseBuffer  = b->getBlockAddress(name, b->CreateLShr(processed, LOG_2_BLOCK_WIDTH));
752
[5771]753        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
[5782]754            b->CreateAssert(b->CreateICmpULT(processed, mAvailableItemCount[i]), "processed item count must be less than the available item count");
[5771]755        }
[5757]756
[5782]757        Value * const unprocessed = b->CreateSub(mAvailableItemCount[i], processed);
758        //b->CallPrintInt(getName() + "_" + name + "_unprocessed", unprocessed);
759
760        Value * avail = b->getLinearlyAccessibleItems(name, processed, unprocessed);
761        //b->CallPrintInt(getName() + "_" + name + "_avail", avail);
762
763
764        // Ensure that everything between S⌈P/S⌉, and S⌈n*(P + L)/S⌉ is linearly available, where S is
765        // the stride size, P is the current processed position, L is the lookahead amount and n ∈ â„€+.
766
767        Value * remaining = avail;
768        if (LLVM_UNLIKELY(input.hasLookahead())) {
769            Constant * const lookahead = b->getSize(input.getLookahead());
770            remaining = b->CreateSelect(b->CreateICmpULT(lookahead, remaining), b->CreateSub(remaining, lookahead), ZERO);
771            //b->CallPrintInt(getName() + "_" + name + "_remaining", remaining);
772        }
773
[5755]774        inputStrideSize[i] = getStrideSize(b, rate);
[5782]775
776        Value * accessibleStrides = b->CreateUDiv(remaining, inputStrideSize[i]);
777
778        //b->CallPrintInt(getName() + "_" + name + "_accessibleStrides", accessibleStrides);
779
[5771]780        AllocaInst * const tempBuffer = temporaryInputBuffer[i];
781        if (tempBuffer) {
[5706]782
[5755]783            // Since we trust that the pipeline won't call this kernel unless there is enough data to process a stride, whenever
784            // we discover that there isn't enough linearly available data, optimistically copy the data to the temporary buffer.
[5706]785
[5755]786            BasicBlock * const entry = b->GetInsertBlock();
787            BasicBlock * const copyFromBack = b->CreateBasicBlock(name + "CopyFromBack");
788            BasicBlock * const copyFromFront = b->CreateBasicBlock(name + "CopyFromFront");
789            BasicBlock * const resume = b->CreateBasicBlock(name + "Resume");
[5706]790
[5755]791            b->CreateUnlikelyCondBr(b->CreateICmpEQ(accessibleStrides, ZERO), copyFromBack, resume);
[5706]792
[5755]793            b->SetInsertPoint(copyFromBack);
[5782]794            Value * const temporarySize = b->CreateMul(tempBuffer->getArraySize(), b->getSize(mStride));
795            Value * const temporaryAvailable = b->CreateUMin(unprocessed, temporarySize);
[5771]796            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
[5782]797                b->CreateAssert(b->CreateICmpULE(avail, temporaryAvailable),
798                                "linearly available item count cannot exceed the temporarily available item count");
[5771]799            }
[5782]800            Value * const offset = b->CreateAnd(processed, BLOCK_WIDTH_MASK);
[5771]801            Value * const bufferSize = b->CreateMul(ConstantExpr::getSizeOf(tempBuffer->getAllocatedType()), tempBuffer->getArraySize());
802            b->CreateMemZero(tempBuffer, bufferSize, blockAlignment);
[5757]803            const auto copyAlignment = getItemAlignment(mStreamSetInputs[i]);
[5782]804            b->CreateStreamCpy(name, tempBuffer, ZERO, baseBuffer, offset, avail, copyAlignment);
[5755]805            Value * const temporaryStrides = b->CreateSelect(b->CreateICmpULT(unprocessed, inputStrideSize[i]), ZERO, ONE);
806            BasicBlock * const copyToBackEnd = b->GetInsertBlock();
[5782]807            b->CreateCondBr(b->CreateICmpNE(temporaryAvailable, unprocessed), copyFromFront, resume);
[5706]808
[5755]809            b->SetInsertPoint(copyFromFront);
[5782]810            Value * const remaining = b->CreateSub(temporaryAvailable, avail);
[5755]811            Value * const baseAddress = b->getBaseAddress(name);
[5782]812            b->CreateStreamCpy(name, tempBuffer, avail, baseAddress, ZERO, remaining, copyAlignment);
[5755]813            BasicBlock * const copyToFrontEnd = b->GetInsertBlock();
814            b->CreateBr(resume);
[5706]815
[5755]816            b->SetInsertPoint(resume);
[5771]817            PHINode * const bufferPtr = b->CreatePHI(baseBuffer->getType(), 3);
818            bufferPtr->addIncoming(baseBuffer , entry);
819            bufferPtr->addIncoming(tempBuffer, copyToBackEnd);
820            bufferPtr->addIncoming(tempBuffer, copyToFrontEnd);
821            baseBuffer = bufferPtr;
[5706]822
[5755]823            PHINode * const phiAvailItemCount = b->CreatePHI(b->getSizeTy(), 3);
[5782]824            phiAvailItemCount->addIncoming(avail, entry);
[5755]825            phiAvailItemCount->addIncoming(temporaryAvailable, copyToBackEnd);
826            phiAvailItemCount->addIncoming(temporaryAvailable, copyToFrontEnd);
[5782]827            avail = phiAvailItemCount;
[5706]828
[5771]829            PHINode * const phiStrides = b->CreatePHI(b->getSizeTy(), 2);
830            phiStrides->addIncoming(accessibleStrides, entry);
831            phiStrides->addIncoming(temporaryStrides, copyToBackEnd);
832            phiStrides->addIncoming(temporaryStrides, copyToFrontEnd);
833            accessibleStrides = phiStrides;
[5706]834        }
[5782]835        mAvailableItemCount[i] = avail;
[5771]836        mStreamSetInputBaseAddress[i] = baseBuffer;
[5755]837        numOfStrides = b->CreateUMin(numOfStrides, accessibleStrides);
[5706]838    }
839
[5755]840    // Now determine the linearly writeable strides
841    Value * linearlyWritable[outputSetCount];
842    Value * outputStrideSize[outputSetCount];
843    mInitialProducedItemCount.resize(outputSetCount);
844    mStreamSetOutputBaseAddress.resize(outputSetCount);
[5706]845    for (unsigned i = 0; i < outputSetCount; i++) {
[5755]846        const auto & output = mStreamSetOutputs[i];
847        const auto & name = output.getName();
848        const ProcessingRate & rate = output.getRate();
[5782]849        Value * const produced = b->getProducedItemCount(name);
850
851        //b->CallPrintInt(getName() + "_" + name + "_produced", produced);
852
853        Value * baseBuffer = b->getBlockAddress(name, b->CreateLShr(produced, LOG_2_BLOCK_WIDTH));
[5771]854        assert (baseBuffer->getType()->isPointerTy());
[5782]855        linearlyWritable[i] = b->getLinearlyWritableItems(name, produced);
856
857        //b->CallPrintInt(getName() + "_" + name + "_linearlyWritable", linearlyWritable[i]);
858
[5771]859        outputStrideSize[i] = getStrideSize(b, rate);
860        // Is the number of linearly writable items sufficient for a stride?
861        if (outputStrideSize[i]) {
862            AllocaInst * const tempBuffer = temporaryOutputBuffer[i];
[5755]863            Value * writableStrides = b->CreateUDiv(linearlyWritable[i], outputStrideSize[i]);
[5782]864            //b->CallPrintInt(getName() + "_" + name + "_writableStrides", writableStrides);
865
866
[5771]867            // Do we require a temporary buffer to write to?
868            if (tempBuffer) {
869                assert (tempBuffer->getType() == baseBuffer->getType());
870                BasicBlock * const entry = b->GetInsertBlock();
[5782]871                BasicBlock * const clearBuffer = b->CreateBasicBlock(name + "ClearTemporaryBuffer");
[5771]872                BasicBlock * const resume = b->CreateBasicBlock(name + "Resume");
[5755]873                Value * const requiresCopy = b->CreateICmpEQ(writableStrides, ZERO);
[5782]874                b->CreateUnlikelyCondBr(requiresCopy, clearBuffer, resume);
875                // Clear the output buffer prior to using it
876                b->SetInsertPoint(clearBuffer);
[5771]877                Value * const bufferSize = b->CreateMul(ConstantExpr::getSizeOf(tempBuffer->getAllocatedType()), tempBuffer->getArraySize());
878                b->CreateMemZero(tempBuffer, bufferSize, blockAlignment);
879                b->CreateBr(resume);
[5782]880                // Select the appropriate buffer / stride #
[5771]881                b->SetInsertPoint(resume);
882                PHINode * const phiBuffer = b->CreatePHI(baseBuffer->getType(), 3);
883                phiBuffer->addIncoming(baseBuffer, entry);
[5782]884                phiBuffer->addIncoming(tempBuffer, clearBuffer);
[5771]885                baseBuffer = phiBuffer;
886                PHINode * const phiStrides = b->CreatePHI(b->getSizeTy(), 2);
887                phiStrides->addIncoming(writableStrides, entry);
[5782]888                phiStrides->addIncoming(ONE, clearBuffer);
[5771]889                writableStrides = phiStrides;
[5706]890            }
[5755]891            numOfStrides = b->CreateUMin(numOfStrides, writableStrides);
[5706]892        }
[5782]893        mInitialProducedItemCount[i] = produced;
[5771]894        mStreamSetOutputBaseAddress[i] = baseBuffer;
[5706]895    }
896
[5757]897    BasicBlock * const segmentDone = b->CreateBasicBlock("SegmentDone");
898
[5755]899    Value * const initiallyFinal = mIsFinal;
900    if (LLVM_LIKELY(numOfStrides != nullptr)) {
901        mIsFinal = b->CreateAnd(mIsFinal, b->CreateICmpEQ(numOfStrides, ZERO));
[5771]902        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
903            Value * const hasStride = b->CreateOr(b->CreateICmpNE(numOfStrides, ZERO), mIsFinal);
904            b->CreateAssert(hasStride, getName() + " has insufficient input data or output space for one stride");
905        }
[5755]906        for (unsigned i = 0; i < inputSetCount; ++i) {
[5782]907            const auto & input = mStreamSetInputs[i];
908            const ProcessingRate & rate = input.getRate();
909            if (rate.isFixed() && input.nonDeferred()) {
[5755]910                mAvailableItemCount[i] = b->CreateSelect(mIsFinal, mAvailableItemCount[i], b->CreateMul(numOfStrides, inputStrideSize[i]));
911            }
[5706]912        }
913    }
914
[5755]915    //  We have one or more blocks of input data and output buffer space for all stream sets.
916    generateMultiBlockLogic(b, numOfStrides);
917
[5706]918    for (unsigned i = 0; i < inputSetCount; ++i) {
[5782]919        const auto & input = mStreamSetInputs[i];
920        const ProcessingRate & rate = input.getRate();
921        if (rate.isFixed() && input.nonDeferred()) {
[5755]922            Value * const ic = b->CreateAdd(mInitialProcessedItemCount[i], mAvailableItemCount[i]);
[5782]923            b->setProcessedItemCount(input.getName(), ic);
[5706]924        }
925    }
[5755]926
927    for (unsigned i = 0; i < outputSetCount; ++i) {
[5782]928        const auto & output = mStreamSetOutputs[i];
929        const ProcessingRate & rate = output.getRate();
[5706]930        if (rate.isFixed()) {
[5782]931            assert (output.nonDeferred());
[5755]932            Value * const produced = b->CreateMul(numOfStrides, outputStrideSize[i]);
933            Value * const ic = b->CreateAdd(mInitialProducedItemCount[i], produced);
[5782]934            b->setProducedItemCount(output.getName(), ic);
[5706]935        }
936    }
937
[5755]938    BasicBlock * const handleFinalBlock = b->CreateBasicBlock("HandleFinalBlock");
939    BasicBlock * const temporaryBufferCopyBack = b->CreateBasicBlock("TemporaryBufferCopyBack");
940    BasicBlock * const strideDone = b->CreateBasicBlock("MultiBlockDone");
[5706]941
[5757]942    b->CreateUnlikelyCondBr(mIsFinal, handleFinalBlock, temporaryBufferCopyBack);
[5706]943
944
[5755]945    /// FINAL STRIDE ADJUSTMENT
946    b->SetInsertPoint(handleFinalBlock);
[5706]947
[5755]948    // If this is our final stride, adjust the Fixed output item counts. The main loop assumes that
949    // the ITEM COUNT % FIXED RATE = 0 for all Fixed Input and Output streams. We correct that here
950    // to calculate them based on the actual input item counts.
[5706]951
[5755]952    reviseFinalProducedItemCounts(b);
[5706]953
[5755]954    b->CreateBr(temporaryBufferCopyBack);
[5706]955
[5755]956    /// TEMPORARY BUFFER COPY BACK
957    b->SetInsertPoint(temporaryBufferCopyBack);
958
959    // Copy back data to the actual output buffers.
960    for (unsigned i = 0; i < outputSetCount; i++) {
[5771]961        AllocaInst * const tempBuffer = temporaryOutputBuffer[i];
[5755]962        if (LLVM_UNLIKELY(tempBuffer == nullptr)) {
963            continue;
[5706]964        }
[5771]965        Value * const baseBuffer = mStreamSetOutputBaseAddress[i];
[5757]966        assert ("stack corruption likely" && (tempBuffer->getType() == baseBuffer->getType()));
[5755]967        const auto & name = mStreamSetOutputs[i].getName();
968        BasicBlock * const copyToBack = b->CreateBasicBlock(name + "CopyToBack");
969        BasicBlock * const copyToFront = b->CreateBasicBlock(name + "CopyToFront");
970        BasicBlock * const resume = b->CreateBasicBlock(name + "ResumeCopyBack");
971        // If we used a temporary buffer, copy it back to the original output buffer
972        b->CreateCondBr(b->CreateICmpEQ(tempBuffer, baseBuffer), copyToBack, resume);
[5706]973
[5755]974        b->SetInsertPoint(copyToBack);       
975        Value * const offset = b->CreateAnd(mInitialProducedItemCount[i], BLOCK_WIDTH_MASK);
976        Value * const newProducedItemCount = b->getProducedItemCount(name);
977        Value * const newlyProduced = b->CreateSub(newProducedItemCount, mInitialProducedItemCount[i]);
978        Value * const toWrite = b->CreateUMin(newlyProduced, linearlyWritable[i]);
979        const auto alignment = getItemAlignment(mStreamSetOutputs[i]);
980        b->CreateStreamCpy(name, baseBuffer, offset, tempBuffer, ZERO, toWrite, alignment);
981        // If we required a temporary output buffer, we will probably need to write to the beginning of the buffer as well.
[5771]982        b->CreateLikelyCondBr(b->CreateICmpULT(toWrite, newlyProduced), copyToFront, resume);
[5706]983
[5755]984        b->SetInsertPoint(copyToFront);
985        Value * const remaining = b->CreateSub(newlyProduced, toWrite);
986        Value * const baseAddress = b->getBaseAddress(name);
987        b->CreateStreamCpy(name, baseAddress, ZERO, tempBuffer, toWrite, remaining, alignment);
988        b->CreateBr(resume);
[5706]989
[5755]990        b->SetInsertPoint(resume);
991    }
[5706]992
[5755]993    //  We've dealt with the partial block processing and copied information back into the
994    //  actual buffers.  If this isn't the final block, loop back for more multiblock processing.
995    if (hasNoTerminateAttribute()) {
996        b->CreateCondBr(mIsFinal, segmentDone, strideDone);
997    } else {
998        BasicBlock * const setTermination = b->CreateBasicBlock("setTermination");
999        b->CreateCondBr(mIsFinal, setTermination, strideDone);
[5706]1000
[5755]1001        b->SetInsertPoint(setTermination);
1002        b->setTerminationSignal();
1003        b->CreateBr(segmentDone);       
1004    }
[5706]1005
[5755]1006    /// STRIDE DONE
[5757]1007    strideDone->moveAfter(b->GetInsertBlock());
[5755]1008    b->SetInsertPoint(strideDone);
[5706]1009
[5757]1010    b->CreateAssertZero(mIsFinal, "stride done cannot process the final block");
1011
[5755]1012    // do we have enough data for another stride?
[5757]1013    Value * hasMoreStrides = b->getTrue();
[5755]1014    for (unsigned i = 0; i < inputSetCount; ++i) {
[5782]1015        const Binding & input = mStreamSetInputs[i];
1016        const auto & name = input.getName();
[5757]1017        Value * const avail = mInitialAvailableItemCount[i];
1018        Value * const processed = b->getProcessedItemCount(name);
[5771]1019        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
[5782]1020            b->CreateAssert(b->CreateICmpULE(processed, avail), getName() + "." + name + ": processed data exceeds available data");
[5771]1021        }
[5782]1022        Value * remaining = b->CreateSub(avail, processed);
1023        if (LLVM_UNLIKELY(input.hasAttribute(AttributeId::LookAhead))) {
1024            Constant * const lookahead = b->getSize(input.findAttribute(AttributeId::LookAhead).amount());
1025            remaining = b->CreateSelect(b->CreateICmpULT(lookahead, remaining), b->CreateSub(remaining, lookahead), ZERO);
1026        }
[5755]1027        Value * const remainingStrides = b->CreateUDiv(remaining, inputStrideSize[i]);
[5761]1028        Value * const hasRemainingStrides = b->CreateICmpNE(remainingStrides, ZERO);
1029        hasMoreStrides = b->CreateAnd(hasMoreStrides, hasRemainingStrides);
[5755]1030    }
[5757]1031    // even if we do not have enough input data for a full stride, if this is our final stride, allow it ...
1032    hasMoreStrides = b->CreateOr(hasMoreStrides, initiallyFinal);
[5706]1033
[5755]1034    // do we have enough room for another stride?
1035    for (unsigned i = 0; i < outputSetCount; ++i) {
1036        const ProcessingRate & rate = mStreamSetOutputs[i].getRate();
1037        const auto & name = mStreamSetOutputs[i].getName();
[5757]1038        Value * const produced = b->getProducedItemCount(name);
[5755]1039        // If this output has a Fixed/Bounded rate, determine whether we have room for another stride.
1040        if (LLVM_LIKELY(outputStrideSize[i] != nullptr)) {
[5757]1041            Value * const consumed = b->getConsumedItemCount(name);
[5771]1042            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
[5782]1043                b->CreateAssert(b->CreateICmpULE(consumed, produced), getName() + "." + name + ": consumed data exceeds produced data");
[5771]1044            }
[5757]1045            Value * const unconsumed = b->CreateSub(produced, consumed);
1046            Value * const capacity = b->getCapacity(name);
[5771]1047            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
[5782]1048                b->CreateAssert(b->CreateICmpULE(unconsumed, capacity), getName() + "." + name + ": unconsumed data exceeds capacity");
[5771]1049            }
[5757]1050            Value * const remaining = b->CreateSub(capacity, unconsumed);
[5755]1051            Value * const remainingStrides = b->CreateUDiv(remaining, outputStrideSize[i]);
[5761]1052            Value * const hasRemainingStrides = b->CreateICmpNE(remainingStrides, ZERO);
1053            hasMoreStrides = b->CreateAnd(hasMoreStrides, hasRemainingStrides);
[5706]1054        }
[5755]1055        // Do copybacks if necessary.
1056        if (mStreamSetOutputBuffers[i]->supportsCopyBack() && requiresCopyBack(rate)) {
[5757]1057            b->CreateCopyBack(name, mInitialProducedItemCount[i], produced);
[5755]1058        }
[5706]1059    }
[5761]1060
1061    // b->CreateAssertZero(b->CreateOr(b->CreateNot(initiallyFinal), hasMoreStrides), getName() + " does not have enough output space for the final stride");
1062
[5755]1063    b->CreateCondBr(hasMoreStrides, segmentLoop, segmentDone);
[5706]1064
[5755]1065    /// SEGMENT DONE
1066    segmentDone->moveAfter(b->GetInsertBlock());
1067    b->SetInsertPoint(segmentDone);
[5706]1068
[5755]1069}
[5706]1070
[5755]1071/** ------------------------------------------------------------------------------------------------------------- *
1072 * @brief requiresCopyBack
1073 ** ------------------------------------------------------------------------------------------------------------- */
1074bool MultiBlockKernel::requiresCopyBack(const ProcessingRate & rate) const {
1075    if (rate.isBounded() || rate.isUnknown()) {
1076        return true;
1077    } else if (rate.isRelative()) {
1078        return requiresCopyBack(getBinding(rate.getReference()).getRate());
1079    }
1080    return false;
1081}
[5706]1082
[5755]1083/** ------------------------------------------------------------------------------------------------------------- *
1084 * @brief CreateUDivCeil
1085 ** ------------------------------------------------------------------------------------------------------------- */
1086inline Value * CreateUDivCeil(const std::unique_ptr<KernelBuilder> & b, Value * const number, const ProcessingRate::RateValue divisor, const Twine & Name = "") {
1087    Constant * const n = ConstantInt::get(number->getType(), divisor.numerator());
1088    if (LLVM_LIKELY(divisor.denominator() == 1)) {
1089        return b->CreateUDivCeil(number, n, Name);
1090    } else {
1091        //   âŒŠ(num + ratio - 1) / ratio⌋
1092        // = ⌊(num - 1) / (n/d)⌋ + (ratio/ratio)
1093        // = ⌊(d * (num - 1)) / n⌋ + 1
1094        Constant * const ONE = ConstantInt::get(number->getType(), 1);
1095        Constant * const d = ConstantInt::get(number->getType(), divisor.denominator());
1096        return b->CreateAdd(b->CreateUDiv(b->CreateMul(b->CreateSub(number, ONE), d), n), ONE, Name);
[5706]1097    }
[5755]1098}
[5706]1099
1100
[5755]1101/** ------------------------------------------------------------------------------------------------------------- *
1102 * @brief reviseFinalProducedItemCounts
1103 ** ------------------------------------------------------------------------------------------------------------- */
1104void MultiBlockKernel::reviseFinalProducedItemCounts(const std::unique_ptr<KernelBuilder> & b) {
[5706]1105
[5755]1106    if (LLVM_UNLIKELY(mStreamSetInputs.empty())) {
1107        return;
1108    }
[5706]1109
[5755]1110    const auto inputSetCount = mStreamSetInputs.size();
[5706]1111
[5755]1112    ProcessingRate::RateValue rateLCM(1);
1113    unsigned first = 0;
1114    unsigned last = inputSetCount;
1115
[5706]1116    for (unsigned i = 0; i < inputSetCount; ++i) {
[5755]1117        const ProcessingRate & pr = mStreamSetInputs[i].getRate();
1118        if (pr.isFixed()) {
1119            rateLCM = lcm(rateLCM, pr.getRate());
1120            if (mStreamSetInputs[i].isPrincipal()) {
1121                assert ("A kernel cannot have multiple principle input streams" && (first == 0 && last == inputSetCount));
1122                first = i;
1123                last = i + 1;
1124            }
1125        }       
[5706]1126    }
1127
[5755]1128    bool noFixedRateOutput = true;
[5706]1129
[5755]1130    for (const Binding & output : mStreamSetOutputs) {
1131        const ProcessingRate & pr = output.getRate();
1132        if (pr.isFixed()) {
1133            rateLCM = lcm(rateLCM, pr.getRate());
1134            noFixedRateOutput = false;
[5706]1135        }
1136    }
1137
[5755]1138    if (noFixedRateOutput) {
1139        return;
[5706]1140    }
1141
[5755]1142    Value * baseInitialProcessedItemCount = nullptr;
1143    Value * scaledInverseOfAvailItemCount = nullptr;
[5706]1144
[5755]1145    // For each Fixed output stream, this calculates:
[5706]1146
[5755]1147    //    CEILING(MIN(Available Item Count / Fixed Input Rate) * Fixed Output Rate)
[5706]1148
[5755]1149    // But avoids the possibility of overflow errors (assuming that each processed item count does not overflow)
[5706]1150
[5755]1151    for (unsigned i = first; i < last; ++i) {
1152        const ProcessingRate & pr = mStreamSetInputs[i].getRate();
1153        if (pr.isFixed()) {
1154            Value * p = mInitialProcessedItemCount[i];
1155            Value * a = b->CreateSub(mInitialAvailableItemCount[i], p);
1156            const auto & rate = pr.getRate();
1157            if (LLVM_UNLIKELY(rateLCM != rate)) {
1158                const auto factor = rateLCM / rate;
1159                if (LLVM_UNLIKELY(factor.numerator() > 1)) {
1160                    a = b->CreateMul(a, b->getSize(factor.numerator()));
1161                }
1162                if (LLVM_UNLIKELY(factor.denominator() > 1)) {
1163                    a = b->CreateUDiv(a, b->getSize(factor.denominator()));
1164                }
1165            }
1166            if (LLVM_UNLIKELY(rate.denominator() > 1)) {
1167                p = b->CreateMul(p, b->getSize(rate.denominator()));
1168            }
1169            if (LLVM_UNLIKELY(rate.numerator() > 1)) {
1170                p = b->CreateUDiv(p, b->getSize(rate.numerator()));
1171            }
1172            if (scaledInverseOfAvailItemCount) {
1173                scaledInverseOfAvailItemCount = b->CreateUMin(scaledInverseOfAvailItemCount, a);
1174                baseInitialProcessedItemCount = b->CreateUMin(baseInitialProcessedItemCount, p);
[5706]1175            } else {
[5755]1176                scaledInverseOfAvailItemCount = a;
1177                baseInitialProcessedItemCount = p;
[5706]1178            }
1179        }
1180    }
1181
[5755]1182    for (const Binding & output : mStreamSetOutputs) {
1183        const auto name = output.getName();
1184        const ProcessingRate & pr = output.getRate();
[5706]1185        Value * produced = nullptr;
[5757]1186        if (pr.isFixed() && output.nonDeferred()) {
[5755]1187            assert (baseInitialProcessedItemCount && scaledInverseOfAvailItemCount);
1188            const auto rate = pr.getRate();
1189            Value * p = baseInitialProcessedItemCount;
1190            if (LLVM_UNLIKELY(rate.numerator() != 1)) {
1191                p = b->CreateMul(p, b->getSize(rate.numerator()));
1192            }
1193            if (LLVM_UNLIKELY(rate.denominator() != 1)) {
1194                p = b->CreateUDiv(p, b->getSize(rate.denominator()));
1195            }
1196            Value * const ic = CreateUDivCeil(b, scaledInverseOfAvailItemCount, rateLCM / pr.getRate());
1197            produced = b->CreateAdd(p, ic);
[5706]1198        } else { // check if we have an attribute; if so, get the current produced count and adjust it
1199            bool noAttributes = true;
[5755]1200            for (const Attribute & attr : output.getAttributes()) {
[5706]1201                if (attr.isAdd() || attr.isRoundUpTo()) {
1202                    noAttributes = false;
1203                    break;
1204                }
1205            }
1206            if (noAttributes) {
1207                continue;
1208            }
[5755]1209            produced = b->getProducedItemCount(name);
[5706]1210        }
[5755]1211        for (const Attribute & attr : output.getAttributes()) {
[5706]1212            if (attr.isAdd()) {
[5782]1213                produced = b->CreateAdd(produced, b->getSize(attr.amount()));
[5706]1214            } else if (attr.isRoundUpTo()) {
[5782]1215                produced = b->CreateRoundUp(produced, b->getSize(attr.amount()));
[5706]1216            }
1217        }
[5755]1218        b->setProducedItemCount(name, produced);
[5706]1219    }
1220
1221}
1222
[5755]1223/** ------------------------------------------------------------------------------------------------------------- *
1224 * @brief generateMultiBlockLogic
1225 ** ------------------------------------------------------------------------------------------------------------- */
1226Value * BlockOrientedKernel::generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> & b, Value * const numOfBlocks) {
[5706]1227
[5755]1228    if (LLVM_UNLIKELY(mStride != b->getBitBlockWidth())) {
1229        report_fatal_error(getName() + ": the Stride (" + std::to_string(mStride) + ") of BlockOrientedKernel "
1230                           "equal to the BitBlockWidth (" + std::to_string(b->getBitBlockWidth()) + ")");
[5351]1231    }
1232
[5755]1233    Constant * const LOG_2_BLOCK_WIDTH = b->getSize(std::log2(b->getBitBlockWidth()));
[5350]1234
[5755]1235    BasicBlock * const entryBlock = b->GetInsertBlock();
1236    mStrideLoopBody = b->CreateBasicBlock(getName() + "_strideLoopBody");
1237    BasicBlock * const stridesDone = b->CreateBasicBlock(getName() + "_stridesDone");
1238    BasicBlock * const doFinalBlock = b->CreateBasicBlock(getName() + "_doFinalBlock");
1239    BasicBlock * const segmentDone = b->CreateBasicBlock(getName() + "_segmentDone");
[5771]1240    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1241        b->CreateAssert(b->CreateXor(b->CreateIsNotNull(numOfBlocks), mIsFinal),
1242                        "numOfStrides cannot be 0 unless this is the final stride and must be 0 if it is");
1243    }
[5706]1244    const auto inputSetCount = mStreamSetInputs.size();
1245    Value * baseProcessedIndex[inputSetCount];
[5755]1246    Value * baseInputAddress[inputSetCount];
1247    for (unsigned i = 0; i < inputSetCount; i++) {
[5706]1248        const ProcessingRate & rate = mStreamSetInputs[i].getRate();
[5755]1249        if (LLVM_UNLIKELY(!rate.isFixed())) {
1250            Value * const ic = mInitialProcessedItemCount[i];
1251            baseProcessedIndex[i] = b->CreateLShr(ic, LOG_2_BLOCK_WIDTH);
[5706]1252        }
[5755]1253        baseInputAddress[i] = mStreamSetInputBaseAddress[i];
[5706]1254    }
1255
1256    const auto outputSetCount = mStreamSetOutputs.size();
1257    Value * baseProducedIndex[outputSetCount];
[5755]1258    Value * baseOutputAddress[inputSetCount];
1259    for (unsigned i = 0; i < outputSetCount; i++) {
[5706]1260        const ProcessingRate & rate = mStreamSetOutputs[i].getRate();
[5755]1261        if (LLVM_UNLIKELY(!rate.isFixed())) {
1262            Value * const ic = b->getProducedItemCount(mStreamSetOutputs[i].getName());
1263            baseProducedIndex[i] = b->CreateLShr(ic, LOG_2_BLOCK_WIDTH);
[5706]1264        }
[5755]1265        baseOutputAddress[i] = mStreamSetOutputBaseAddress[i];
[5706]1266    }
1267
[5755]1268    b->CreateUnlikelyCondBr(mIsFinal, doFinalBlock, mStrideLoopBody);
[5706]1269
[5755]1270    /// BLOCK BODY
[5285]1271
[5755]1272    b->SetInsertPoint(mStrideLoopBody);
[5706]1273
[5755]1274    if (b->supportsIndirectBr()) {
1275        Value * const baseTarget = BlockAddress::get(segmentDone);
1276        mStrideLoopTarget = b->CreatePHI(baseTarget->getType(), 2, "strideTarget");
1277        mStrideLoopTarget->addIncoming(baseTarget, entryBlock);
[5351]1278    }
1279
[5755]1280    mStrideBlockIndex = b->CreatePHI(b->getSizeTy(), 2);
1281    mStrideBlockIndex->addIncoming(b->getSize(0), entryBlock);
[5706]1282
[5755]1283    /// GENERATE DO BLOCK METHOD
1284
[5706]1285    for (unsigned i = 0; i < inputSetCount; ++i) {
[5755]1286        Value * index = mStrideBlockIndex;
1287        const ProcessingRate & rate = mStreamSetInputs[i].getRate();
1288        if (LLVM_UNLIKELY(!rate.isFixed())) {
1289            Value * ic = b->getProcessedItemCount(mStreamSetInputs[i].getName());
1290            index = b->CreateSub(b->CreateLShr(ic, LOG_2_BLOCK_WIDTH), baseProcessedIndex[i]);
[5706]1291        }
[5755]1292        mStreamSetInputBaseAddress[i] = b->CreateGEP(mStreamSetInputBaseAddress[i], index);
[5706]1293    }
1294
1295    for (unsigned i = 0; i < outputSetCount; ++i) {
[5755]1296        Value * index = mStrideBlockIndex;
1297        const ProcessingRate & rate = mStreamSetOutputs[i].getRate();
1298        if (LLVM_UNLIKELY(!rate.isFixed())) {
1299            Value * ic = b->getProducedItemCount(mStreamSetOutputs[i].getName());
1300            index = b->CreateSub(b->CreateLShr(ic, LOG_2_BLOCK_WIDTH), baseProducedIndex[i]);
[5706]1301        }
[5755]1302        mStreamSetOutputBaseAddress[i] = b->CreateGEP(mStreamSetOutputBaseAddress[i], index);
[5706]1303    }
1304
[5755]1305    writeDoBlockMethod(b);
[5285]1306
[5755]1307    BasicBlock * const bodyEnd = b->GetInsertBlock();
1308    if (mStrideLoopTarget) {
1309        mStrideLoopTarget->addIncoming(mStrideLoopTarget, bodyEnd);
[5350]1310    }
1311
[5755]1312    Value * const nextIndex = b->CreateAdd(mStrideBlockIndex, b->getSize(1));
1313    mStrideBlockIndex->addIncoming(nextIndex, bodyEnd);
1314    Value * const notDone = b->CreateICmpULT(nextIndex, numOfBlocks);
1315    b->CreateCondBr(notDone, mStrideLoopBody, stridesDone);
[5285]1316
[5351]1317    stridesDone->moveAfter(bodyEnd);
1318
[5706]1319    /// STRIDE DONE
1320
[5755]1321    b->SetInsertPoint(stridesDone);
[5297]1322
[5285]1323    // Now conditionally perform the final block processing depending on the doFinal parameter.
[5755]1324    if (mStrideLoopTarget) {
1325        mStrideLoopBranch = b->CreateIndirectBr(mStrideLoopTarget, 3);
[5351]1326        mStrideLoopBranch->addDestination(doFinalBlock);
1327        mStrideLoopBranch->addDestination(segmentDone);
1328    } else {
[5755]1329        b->CreateUnlikelyCondBr(mIsFinal, doFinalBlock, segmentDone);
[5351]1330    }
1331
1332    doFinalBlock->moveAfter(stridesDone);
1333
[5755]1334    /// DO FINAL BLOCK
[5285]1335
[5755]1336    b->SetInsertPoint(doFinalBlock);
[5706]1337    for (unsigned i = 0; i < inputSetCount; ++i) {
[5755]1338        mStreamSetInputBaseAddress[i] = baseInputAddress[i];
[5706]1339    }
[5285]1340
[5755]1341    for (unsigned i = 0; i < outputSetCount; ++i) {
1342        mStreamSetOutputBaseAddress[i] = baseOutputAddress[i];
1343    }
[5440]1344
[5755]1345    writeFinalBlockMethod(b, getRemainingItems(b));
[5285]1346
[5755]1347    b->CreateBr(segmentDone);
[5351]1348
[5755]1349    segmentDone->moveAfter(b->GetInsertBlock());
[5351]1350
[5755]1351    b->SetInsertPoint(segmentDone);
1352
[5351]1353    // Update the branch prediction metadata to indicate that the likely target will be segmentDone
[5755]1354    if (mStrideLoopTarget) {
1355        MDBuilder mdb(b->getContext());
[5350]1356        const auto destinations = mStrideLoopBranch->getNumDestinations();
[5351]1357        uint32_t weights[destinations];
1358        for (unsigned i = 0; i < destinations; ++i) {
1359            weights[i] = (mStrideLoopBranch->getDestination(i) == segmentDone) ? 100 : 1;
[5350]1360        }
[5351]1361        ArrayRef<uint32_t> bw(weights, destinations);
1362        mStrideLoopBranch->setMetadata(LLVMContext::MD_prof, mdb.createBranchWeights(bw));
[5350]1363    }
1364
[5755]1365    return numOfBlocks;
[5285]1366}
1367
[5755]1368/** ------------------------------------------------------------------------------------------------------------- *
1369 * @brief getRemainingItems
1370 ** ------------------------------------------------------------------------------------------------------------- */
1371Value * BlockOrientedKernel::getRemainingItems(const std::unique_ptr<KernelBuilder> & b) {
1372    Value * remainingItems = nullptr;
1373    const auto count = mStreamSetInputs.size();
1374    if (count == 1) {
1375        return mAvailableItemCount[0];
1376    } else {
1377        for (unsigned i = 0; i < count; i++) {
1378            if (mStreamSetInputs[i].isPrincipal()) {
1379                return mAvailableItemCount[i];
1380            }
1381        }
1382        for (unsigned i = 0; i < count; ++i) {
1383            const ProcessingRate & r = mStreamSetInputs[i].getRate();
1384            if (r.isFixed()) {
1385                Value * ic = CreateUDivCeil(b, mAvailableItemCount[i], r.getRate());
1386                if (remainingItems) {
1387                    remainingItems = b->CreateUMin(remainingItems, ic);
1388                } else {
1389                    remainingItems = ic;
1390                }
1391            }
1392        }
1393    }
1394    return remainingItems;
1395}
[5292]1396
[5755]1397/** ------------------------------------------------------------------------------------------------------------- *
1398 * @brief writeDoBlockMethod
1399 ** ------------------------------------------------------------------------------------------------------------- */
1400inline void BlockOrientedKernel::writeDoBlockMethod(const std::unique_ptr<KernelBuilder> & b) {
1401
[5408]1402    Value * const self = getInstance();
[5347]1403    Function * const cp = mCurrentMethod;
[5755]1404    auto ip = b->saveIP();
[5454]1405    std::vector<Value *> availableItemCount(0);
[5292]1406
[5706]1407    /// Check if the do block method is called and create the function if necessary
[5755]1408    if (!b->supportsIndirectBr()) {
[5454]1409
1410        std::vector<Type *> params;
1411        params.reserve(1 + mAvailableItemCount.size());
1412        params.push_back(self->getType());
1413        for (Value * avail : mAvailableItemCount) {
1414            params.push_back(avail->getType());
1415        }
1416
[5755]1417        FunctionType * const type = FunctionType::get(b->getVoidTy(), params, false);
1418        mCurrentMethod = Function::Create(type, GlobalValue::InternalLinkage, getName() + DO_BLOCK_SUFFIX, b->getModule());
[5347]1419        mCurrentMethod->setCallingConv(CallingConv::C);
1420        mCurrentMethod->setDoesNotThrow();
1421        auto args = mCurrentMethod->arg_begin();
[5408]1422        args->setName("self");
1423        setInstance(&*args);
[5454]1424        availableItemCount.reserve(mAvailableItemCount.size());
1425        while (++args != mCurrentMethod->arg_end()) {
1426            availableItemCount.push_back(&*args);
1427        }
1428        assert (availableItemCount.size() == mAvailableItemCount.size());
1429        mAvailableItemCount.swap(availableItemCount);
[5755]1430        b->SetInsertPoint(BasicBlock::Create(b->getContext(), "entry", mCurrentMethod));
[5347]1431    }
1432
[5755]1433    generateDoBlockMethod(b); // must be implemented by the BlockOrientedKernelBuilder subtype
[5347]1434
[5755]1435    if (!b->supportsIndirectBr()) {
[5454]1436        // Restore the DoSegment function state then call the DoBlock method
[5755]1437        b->CreateRetVoid();
[5350]1438        mDoBlockMethod = mCurrentMethod;
[5755]1439        b->restoreIP(ip);
[5408]1440        setInstance(self);
[5350]1441        mCurrentMethod = cp;
[5454]1442        mAvailableItemCount.swap(availableItemCount);
[5755]1443        CreateDoBlockMethodCall(b);
[5350]1444    }
1445
[5285]1446}
1447
[5755]1448/** ------------------------------------------------------------------------------------------------------------- *
1449 * @brief writeFinalBlockMethod
1450 ** ------------------------------------------------------------------------------------------------------------- */
1451inline void BlockOrientedKernel::writeFinalBlockMethod(const std::unique_ptr<KernelBuilder> & b, Value * remainingItems) {
[5292]1452
[5408]1453    Value * const self = getInstance();
[5347]1454    Function * const cp = mCurrentMethod;
1455    Value * const remainingItemCount = remainingItems;
[5755]1456    auto ip = b->saveIP();
[5454]1457    std::vector<Value *> availableItemCount(0);
[5285]1458
[5755]1459    if (!b->supportsIndirectBr()) {
[5454]1460        std::vector<Type *> params;
1461        params.reserve(2 + mAvailableItemCount.size());
1462        params.push_back(self->getType());
[5755]1463        params.push_back(b->getSizeTy());
[5454]1464        for (Value * avail : mAvailableItemCount) {
1465            params.push_back(avail->getType());
1466        }
[5755]1467        FunctionType * const type = FunctionType::get(b->getVoidTy(), params, false);
1468        mCurrentMethod = Function::Create(type, GlobalValue::InternalLinkage, getName() + FINAL_BLOCK_SUFFIX, b->getModule());
[5347]1469        mCurrentMethod->setCallingConv(CallingConv::C);
1470        mCurrentMethod->setDoesNotThrow();
1471        auto args = mCurrentMethod->arg_begin();
[5408]1472        args->setName("self");
1473        setInstance(&*args);
[5347]1474        remainingItems = &*(++args);
1475        remainingItems->setName("remainingItems");
[5454]1476        availableItemCount.reserve(mAvailableItemCount.size());
1477        while (++args != mCurrentMethod->arg_end()) {
1478            availableItemCount.push_back(&*args);
1479        }
1480        assert (availableItemCount.size() == mAvailableItemCount.size());
1481        mAvailableItemCount.swap(availableItemCount);
[5755]1482        b->SetInsertPoint(BasicBlock::Create(b->getContext(), "entry", mCurrentMethod));
[5292]1483    }
[5347]1484
[5755]1485    generateFinalBlockMethod(b, remainingItems); // may be implemented by the BlockOrientedKernel subtype
[5347]1486
[5755]1487    if (!b->supportsIndirectBr()) {
1488        b->CreateRetVoid();
1489        b->restoreIP(ip);
[5454]1490        setInstance(self);
1491        mAvailableItemCount.swap(availableItemCount);
1492        // Restore the DoSegment function state then call the DoFinal method
1493        std::vector<Value *> args;
1494        args.reserve(2 + mAvailableItemCount.size());
1495        args.push_back(self);
1496        args.push_back(remainingItemCount);
[5755]1497        args.insert(args.end(), mAvailableItemCount.begin(), mAvailableItemCount.end());
1498        b->CreateCall(mCurrentMethod, args);
[5347]1499        mCurrentMethod = cp;
1500    }
1501
[5285]1502}
1503
[5755]1504/** ------------------------------------------------------------------------------------------------------------- *
1505 * @brief generateFinalBlockMethod
1506 ** ------------------------------------------------------------------------------------------------------------- */
1507void BlockOrientedKernel::generateFinalBlockMethod(const std::unique_ptr<KernelBuilder> & b, Value * /* remainingItems */) {
1508    //  The default finalBlock method simply dispatches to the doBlock routine.
1509    CreateDoBlockMethodCall(b);
[5292]1510}
1511
[5755]1512void BlockOrientedKernel::CreateDoBlockMethodCall(const std::unique_ptr<KernelBuilder> & b) {
1513    if (b->supportsIndirectBr()) {
1514        BasicBlock * const bb = b->CreateBasicBlock("resume");
[5350]1515        mStrideLoopBranch->addDestination(bb);
[5755]1516        BasicBlock * const current = b->GetInsertBlock();
1517        mStrideLoopTarget->addIncoming(BlockAddress::get(bb), current);
1518        mStrideBlockIndex->addIncoming(b->getSize(0), current);
1519        b->CreateBr(mStrideLoopBody);
1520        bb->moveAfter(current);
1521        b->SetInsertPoint(bb);
[5350]1522    } else {
[5454]1523        std::vector<Value *> args;
1524        args.reserve(1 + mAvailableItemCount.size());
1525        args.push_back(getInstance());
[5755]1526        args.insert(args.end(), mAvailableItemCount.begin(), mAvailableItemCount.end());
1527        b->CreateCall(mDoBlockMethod, args);
[5292]1528    }
[5285]1529}
1530
[5454]1531static inline std::string annotateKernelNameWithDebugFlags(std::string && name) {
[5755]1532    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
[5454]1533        name += "_EA";
1534    }
[5620]1535    name += "_O" + std::to_string((int)codegen::OptLevel);
[5454]1536    return name;
1537}
1538
[5285]1539// CONSTRUCTOR
[5435]1540Kernel::Kernel(std::string && kernelName,
[5755]1541               Bindings && stream_inputs,
1542               Bindings && stream_outputs,
1543               Bindings && scalar_parameters,
1544               Bindings && scalar_outputs,
1545               Bindings && internal_scalars)
[5493]1546: KernelInterface(annotateKernelNameWithDebugFlags(std::move(kernelName))
[5454]1547                  , std::move(stream_inputs), std::move(stream_outputs)
1548                  , std::move(scalar_parameters), std::move(scalar_outputs)
1549                  , std::move(internal_scalars))
[5350]1550, mCurrentMethod(nullptr)
[5755]1551, mAvailablePrincipalItemCount(nullptr)
[5408]1552, mNoTerminateAttribute(false)
[5418]1553, mIsGenerated(false)
[5706]1554, mStride(0)
[5418]1555, mIsFinal(nullptr)
[5706]1556, mOutputScalarResult(nullptr) {
[5283]1557
1558}
1559
[5435]1560Kernel::~Kernel() {
[5283]1561
[5408]1562}
1563
[5755]1564// MULTI-BLOCK KERNEL CONSTRUCTOR
1565MultiBlockKernel::MultiBlockKernel(std::string && kernelName,
1566                                   Bindings && stream_inputs,
1567                                   Bindings && stream_outputs,
1568                                   Bindings && scalar_parameters,
1569                                   Bindings && scalar_outputs,
1570                                   Bindings && internal_scalars)
1571: Kernel(std::move(kernelName), std::move(stream_inputs), std::move(stream_outputs), std::move(scalar_parameters), std::move(scalar_outputs), std::move(internal_scalars)) {
1572
1573}
1574
[5285]1575// CONSTRUCTOR
[5435]1576BlockOrientedKernel::BlockOrientedKernel(std::string && kernelName,
[5755]1577                                         Bindings && stream_inputs,
1578                                         Bindings && stream_outputs,
1579                                         Bindings && scalar_parameters,
1580                                         Bindings && scalar_outputs,
1581                                         Bindings && internal_scalars)
[5706]1582: MultiBlockKernel(std::move(kernelName), std::move(stream_inputs), std::move(stream_outputs), std::move(scalar_parameters), std::move(scalar_outputs), std::move(internal_scalars))
[5408]1583, mDoBlockMethod(nullptr)
1584, mStrideLoopBody(nullptr)
1585, mStrideLoopBranch(nullptr)
[5755]1586, mStrideLoopTarget(nullptr)
1587, mStrideBlockIndex(nullptr) {
[5408]1588
1589}
1590
[5441]1591// CONSTRUCTOR
[5435]1592SegmentOrientedKernel::SegmentOrientedKernel(std::string && kernelName,
[5755]1593                                             Bindings && stream_inputs,
1594                                             Bindings && stream_outputs,
1595                                             Bindings && scalar_parameters,
1596                                             Bindings && scalar_outputs,
1597                                             Bindings && internal_scalars)
[5435]1598: Kernel(std::move(kernelName), std::move(stream_inputs), std::move(stream_outputs), std::move(scalar_parameters), std::move(scalar_outputs), std::move(internal_scalars)) {
[5706]1599
[5283]1600}
[5615]1601
1602
[5435]1603}
Note: See TracBrowser for help on using the repository browser.