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

Last change on this file since 5873 was 5873, checked in by xwa163, 14 months ago
  1. Implement LZ4MultiplePdepKernel, which can do PDEP for more than one input streamset
  2. Add attributed Swizzled in StreamSet?, copy at least one whole block when doing temporary buffer copy for Swizzled InputStreamSet?
  3. Bug fixing for character_deposit pipeline
  4. Add more test files for character_deposit pipeline
File size: 82.5 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    assert (mStreamMap.empty());
217
218    prepareStreamSetNameMap();
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 tmp;
293        raw_string_ostream signature(tmp);
294        WriteBitcodeToFile(getModule(), signature);
295        return signature.str();
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 ("Kernel does not have a valid IDISA Builder" && idb.get());
307    if (LLVM_UNLIKELY(mIsGenerated)) return;
308    idb->setModule(mModule);
309    addKernelDeclarations(idb);
310    callGenerateInitializeMethod(idb);
311    callGenerateDoSegmentMethod(idb);
312    callGenerateFinalizeMethod(idb);
313    mIsGenerated = true;
314}
315
316
317/** ------------------------------------------------------------------------------------------------------------- *
318 * @brief callGenerateInitializeMethod
319 ** ------------------------------------------------------------------------------------------------------------- */
320inline void Kernel::callGenerateInitializeMethod(const std::unique_ptr<kernel::KernelBuilder> & idb) {
321    mCurrentMethod = getInitFunction(idb->getModule());
322    idb->SetInsertPoint(BasicBlock::Create(idb->getContext(), "entry", mCurrentMethod));
323    Function::arg_iterator args = mCurrentMethod->arg_begin();
324    setInstance(&*(args++));
325    idb->CreateStore(ConstantAggregateZero::get(mKernelStateType), getInstance());
326    for (const auto & binding : mScalarInputs) {
327        idb->setScalarField(binding.getName(), &*(args++));
328    }
329    for (const auto & binding : mStreamSetOutputs) {
330        idb->setConsumerLock(binding.getName(), &*(args++));
331    }
332    generateInitializeMethod(idb);
333    idb->CreateRetVoid();
334}
335
336/** ------------------------------------------------------------------------------------------------------------- *
337 * @brief callGenerateDoSegmentMethod
338 ** ------------------------------------------------------------------------------------------------------------- */
339inline void Kernel::callGenerateDoSegmentMethod(const std::unique_ptr<kernel::KernelBuilder> & idb) {
340    mCurrentMethod = getDoSegmentFunction(idb->getModule());
341    idb->SetInsertPoint(BasicBlock::Create(idb->getContext(), "entry", mCurrentMethod));
342    auto args = mCurrentMethod->arg_begin();
343    setInstance(&*(args++));
344    mIsFinal = &*(args++);
345    mAvailablePrincipalItemCount = nullptr;
346    const auto n = mStreamSetInputs.size();
347    mAvailableItemCount.resize(n, nullptr);
348    for (unsigned i = 0; i < n; i++) {
349        assert (args != mCurrentMethod->arg_end());
350        mAvailableItemCount[i] = &*(args++);
351    }
352    assert (args == mCurrentMethod->arg_end());
353    generateKernelMethod(idb); // must be overridden by the Kernel subtype
354    mIsFinal = nullptr;
355    mAvailableItemCount.clear();
356    idb->CreateRetVoid();
357}
358
359
360/** ------------------------------------------------------------------------------------------------------------- *
361 * @brief callGenerateFinalizeMethod
362 ** ------------------------------------------------------------------------------------------------------------- */
363inline void Kernel::callGenerateFinalizeMethod(const std::unique_ptr<KernelBuilder> & idb) {
364    mCurrentMethod = getTerminateFunction(idb->getModule());
365    idb->SetInsertPoint(BasicBlock::Create(idb->getContext(), "entry", mCurrentMethod));
366    auto args = mCurrentMethod->arg_begin();
367    setInstance(&*(args++));
368    generateFinalizeMethod(idb); // may be overridden by the Kernel subtype
369    const auto n = mScalarOutputs.size();
370    if (n == 0) {
371        idb->CreateRetVoid();
372    } else {
373        Value * outputs[n];
374        for (unsigned i = 0; i < n; ++i) {
375            outputs[i] = idb->getScalarField(mScalarOutputs[i].getName());
376        }
377        if (n == 1) {
378            idb->CreateRet(outputs[0]);
379        } else {
380            idb->CreateAggregateRet(outputs, n);
381        }
382    }
383}
384
385
386/** ------------------------------------------------------------------------------------------------------------- *
387 * @brief getScalarIndex
388 ** ------------------------------------------------------------------------------------------------------------- */
389unsigned Kernel::getScalarIndex(const std::string & name) const {
390    const auto f = mKernelFieldMap.find(name);
391    if (LLVM_UNLIKELY(f == mKernelFieldMap.end())) {
392        assert (false);
393        report_fatal_error(getName() + " does not contain scalar: " + name);
394    }
395    return f->second;
396}
397
398
399/** ------------------------------------------------------------------------------------------------------------- *
400 * @brief createInstance
401 ** ------------------------------------------------------------------------------------------------------------- */
402Value * Kernel::createInstance(const std::unique_ptr<KernelBuilder> & idb) {
403    assert ("KernelBuilder does not have a valid IDISA Builder" && idb);
404    if (LLVM_UNLIKELY(mKernelStateType == nullptr)) {
405        report_fatal_error("Cannot instantiate " + getName() + " before calling prepareKernel()");
406    }
407    setInstance(idb->CreateCacheAlignedAlloca(mKernelStateType));
408    return getInstance();
409}
410
411
412/** ------------------------------------------------------------------------------------------------------------- *
413 * @brief initializeInstance
414 ** ------------------------------------------------------------------------------------------------------------- */
415void Kernel::initializeInstance(const std::unique_ptr<KernelBuilder> & idb) {
416    assert ("KernelBuilder does not have a valid IDISA Builder" && idb);
417    if (LLVM_UNLIKELY(getInstance() == nullptr)) {
418        report_fatal_error("Cannot initialize " + getName() + " before calling createInstance()");
419    }
420    std::vector<Value *> args;
421    args.reserve(1 + mInitialArguments.size() + mStreamSetInputBuffers.size() + (mStreamSetOutputBuffers.size() * 2));
422    args.push_back(getInstance());
423    for (unsigned i = 0; i < mInitialArguments.size(); ++i) {
424        Value * arg = mInitialArguments[i];
425        if (LLVM_UNLIKELY(arg == nullptr)) {
426            report_fatal_error(getName() + ": initial argument " + std::to_string(i)
427                               + " cannot be null when calling createInstance()");
428        }
429        args.push_back(arg);
430    }
431    for (unsigned i = 0; i < mStreamSetInputBuffers.size(); ++i) {
432        assert (mStreamSetInputBuffers[i]);
433        Value * arg = mStreamSetInputBuffers[i]->getStreamSetHandle();
434        if (LLVM_UNLIKELY(arg == nullptr)) {
435            report_fatal_error(getName() + ": input stream set " + std::to_string(i)
436                               + " was not allocated prior to calling createInstance()");
437        }
438        args.push_back(arg);
439    }
440    assert (mStreamSetInputs.size() == mStreamSetInputBuffers.size());
441    for (unsigned i = 0; i < mStreamSetOutputBuffers.size(); ++i) {
442        assert (mStreamSetOutputBuffers[i]);
443        Value * arg = mStreamSetOutputBuffers[i]->getStreamSetHandle();
444        if (LLVM_UNLIKELY(arg == nullptr)) {
445            report_fatal_error(getName() + ": output stream set " + std::to_string(i)
446                               + " was not allocated prior to calling createInstance()");
447        }
448        args.push_back(arg);
449    }
450    assert (mStreamSetOutputs.size() == mStreamSetOutputBuffers.size());
451    IntegerType * const sizeTy = idb->getSizeTy();
452    PointerType * const sizePtrTy = sizeTy->getPointerTo();
453    PointerType * const sizePtrPtrTy = sizePtrTy->getPointerTo();
454    StructType * const consumerTy = StructType::get(idb->getContext(), {sizeTy, sizePtrPtrTy});
455    for (unsigned i = 0; i < mStreamSetOutputBuffers.size(); ++i) {
456        const auto output = mStreamSetOutputBuffers[i];
457        const auto & consumers = output->getConsumers();
458        const auto n = consumers.size();
459        AllocaInst * const outputConsumers = idb->CreateAlloca(consumerTy);
460        Value * const consumerSegNoArray = idb->CreateAlloca(ArrayType::get(sizePtrTy, n));
461        for (unsigned i = 0; i < n; ++i) {
462            Kernel * const consumer = consumers[i];
463            assert ("all instances must be created prior to initialization of any instance" && consumer->getInstance());
464            idb->setKernel(consumer);
465            Value * const segmentNoPtr = idb->getScalarFieldPtr(LOGICAL_SEGMENT_NO_SCALAR);
466            idb->CreateStore(segmentNoPtr, idb->CreateGEP(consumerSegNoArray, { idb->getInt32(0), idb->getInt32(i) }));
467        }
468        idb->setKernel(this);
469        Value * const consumerCountPtr = idb->CreateGEP(outputConsumers, {idb->getInt32(0), idb->getInt32(0)});
470        idb->CreateStore(idb->getSize(n), consumerCountPtr);
471        Value * const consumerSegNoArrayPtr = idb->CreateGEP(outputConsumers, {idb->getInt32(0), idb->getInt32(1)});
472        idb->CreateStore(idb->CreatePointerCast(consumerSegNoArray, sizePtrPtrTy), consumerSegNoArrayPtr);
473        args.push_back(outputConsumers);
474    }
475    idb->CreateCall(getInitFunction(idb->getModule()), args);
476}
477
478/** ------------------------------------------------------------------------------------------------------------- *
479 * @brief finalizeInstance
480 ** ------------------------------------------------------------------------------------------------------------- */
481void Kernel::finalizeInstance(const std::unique_ptr<KernelBuilder> & idb) {
482    assert ("KernelBuilder does not have a valid IDISA Builder" && idb);
483    mOutputScalarResult = idb->CreateCall(getTerminateFunction(idb->getModule()), { getInstance() });
484}
485
486/** ------------------------------------------------------------------------------------------------------------- *
487 * @brief getStreamPort
488 ** ------------------------------------------------------------------------------------------------------------- */
489Kernel::StreamPort Kernel::getStreamPort(const std::string & name) const {
490    const auto f = mStreamMap.find(name);
491    if (LLVM_UNLIKELY(f == mStreamMap.end())) {
492        report_fatal_error(getName() + " does not contain stream set " + name);
493    }
494    return f->second;
495}
496
497/** ------------------------------------------------------------------------------------------------------------- *
498 * @brief getStreamPort
499 ** ------------------------------------------------------------------------------------------------------------- */
500const Binding & Kernel::getBinding(const std::string & name) const {
501    Port port; unsigned index;
502    std::tie(port, index) = getStreamPort(name);
503    return (port == Port::Input) ? getStreamInput(index) : getStreamOutput(index);
504}
505
506/** ------------------------------------------------------------------------------------------------------------- *
507 * @brief getLowerBound
508 ** ------------------------------------------------------------------------------------------------------------- */
509ProcessingRate::RateValue Kernel::getLowerBound(const ProcessingRate & rate) const {
510    if (rate.isFixed() || rate.isBounded()) {
511        return rate.getLowerBound();
512    } else if (rate.isRelative()) {
513        return rate.getRate() * getLowerBound(getBinding(rate.getReference()).getRate());
514    } else { // if (rate.isUnknown())
515        return 0;
516    }
517}
518
519/** ------------------------------------------------------------------------------------------------------------- *
520 * @brief getUpperBound
521 ** ------------------------------------------------------------------------------------------------------------- */
522ProcessingRate::RateValue Kernel::getUpperBound(const ProcessingRate &rate) const {
523    if (rate.isFixed() || rate.isBounded()) {
524        return rate.getUpperBound();
525    } else if (rate.isRelative()) {
526        return rate.getRate() * getUpperBound(getBinding(rate.getReference()).getRate());
527    } else { // if (rate.isUnknown())
528        return 0;
529    }
530}
531
532/** ------------------------------------------------------------------------------------------------------------- *
533 * @brief normalizeRelativeToFixedProcessingRate
534 ** ------------------------------------------------------------------------------------------------------------- */
535bool Kernel::normalizeRelativeToFixedProcessingRate(const ProcessingRate & base, ProcessingRate & toUpdate) {
536    if (base.isFixed()) {
537        return true;
538    } else if (LLVM_UNLIKELY(base.isRelative())) {
539        const auto & ref = getBinding(base.getReference()).getRate();
540        if (normalizeRelativeToFixedProcessingRate(ref, toUpdate)) {
541            toUpdate.getRate() *= ref.getRate();
542            return true;
543        }
544    }
545    return false;
546}
547
548/** ------------------------------------------------------------------------------------------------------------- *
549 * @brief normalizeStreamProcessingRates
550 *
551 * If we allow a stream to be transitively relative to a fixed rate stream, it complicates detection of fixed
552 * rate streams later. Find any such occurance and transform them. This implies, however, that a fixed rate
553 * stream could have a rational processing rate (which should not occur normally.)
554 ** ------------------------------------------------------------------------------------------------------------- */
555inline void Kernel::normalizeStreamProcessingRates() {
556    for (Binding & input : mStreamSetInputs) {
557        normalizeRelativeToFixedProcessingRate(input.getRate(), input.getRate());
558    }
559    for (Binding & output : mStreamSetOutputs) {
560        normalizeRelativeToFixedProcessingRate(output.getRate(), output.getRate());
561    }
562    // TODO: we want to consume whole units. Once the pipeline is able to schedule kernels based on their stride
563    // and input/output rates, modify them here.
564}
565
566/** ------------------------------------------------------------------------------------------------------------- *
567 * @brief generateKernelMethod
568 ** ------------------------------------------------------------------------------------------------------------- */
569void SegmentOrientedKernel::generateKernelMethod(const std::unique_ptr<KernelBuilder> & b) {
570    const auto inputSetCount = mStreamSetInputs.size();
571    mStreamSetInputBaseAddress.resize(inputSetCount);
572    for (unsigned i = 0; i < inputSetCount; ++i) {
573        mStreamSetInputBaseAddress[i] = nullptr;
574    }
575    const auto outputSetCount = mStreamSetOutputs.size();
576    mStreamSetOutputBaseAddress.resize(outputSetCount);
577    for (unsigned i = 0; i < outputSetCount; ++i) {
578        mStreamSetOutputBaseAddress[i] = nullptr;
579    }
580    generateDoSegmentMethod(b);
581}
582
583/** ------------------------------------------------------------------------------------------------------------- *
584 * @brief requiresBufferedFinalStride
585 ** ------------------------------------------------------------------------------------------------------------- */
586inline bool LLVM_READNONE requiresBufferedFinalStride(const Binding & binding) {
587    if (LLVM_LIKELY(isa<ArrayType>(binding.getType()))) {
588        return binding.getType()->getArrayNumElements() == 1;
589    }
590    return true;
591}
592
593/** ------------------------------------------------------------------------------------------------------------- *
594 * @brief getItemWidth
595 ** ------------------------------------------------------------------------------------------------------------- */
596inline unsigned LLVM_READNONE getItemWidth(const Binding & b) {
597    Type * ty = b.getType();
598    if (LLVM_LIKELY(isa<ArrayType>(ty))) {
599        ty = ty->getArrayElementType();
600    }
601    return cast<IntegerType>(ty->getVectorElementType())->getBitWidth();
602}
603
604/** ------------------------------------------------------------------------------------------------------------- *
605 * @brief isTransitivelyUnknownRate
606 ** ------------------------------------------------------------------------------------------------------------- */
607bool LLVM_READNONE MultiBlockKernel::isTransitivelyUnknownRate(const ProcessingRate & rate) const {
608    if (rate.isUnknown()) {
609        return true;
610    } else if (rate.isDerived()) {
611        return isTransitivelyUnknownRate(getBinding(rate.getReference()).getRate());
612    }
613    return false;
614}
615
616/** ------------------------------------------------------------------------------------------------------------- *
617 * @brief requiresTemporaryInputBuffer
618 ** ------------------------------------------------------------------------------------------------------------- */
619inline bool LLVM_READNONE MultiBlockKernel::requiresTemporaryInputBuffer(const Binding & binding, const ProcessingRate & rate) const {
620    if (requiresBufferedFinalStride(binding)) {
621        return true;
622    } else if (LLVM_UNLIKELY(isTransitivelyUnknownRate(rate))) {
623        report_fatal_error("MultiBlock kernels do not support unknown rate input streams or streams relative to an unknown rate input.");
624    } else {
625        return !rate.isFixed();
626    }
627}
628
629/** ------------------------------------------------------------------------------------------------------------- *
630 * @brief requiresTemporaryOutputBuffer
631 ** ------------------------------------------------------------------------------------------------------------- */
632inline bool LLVM_READNONE MultiBlockKernel::requiresTemporaryOutputBuffer(const Binding & binding, const ProcessingRate & rate) const {
633    if (requiresBufferedFinalStride(binding)) {
634        return true;
635    } else {
636        return !(rate.isFixed() || isTransitivelyUnknownRate(rate));
637    }
638}
639
640/** ------------------------------------------------------------------------------------------------------------- *
641 * @brief getItemAlignment
642 ** ------------------------------------------------------------------------------------------------------------- */
643inline unsigned LLVM_READNONE MultiBlockKernel::getItemAlignment(const Binding & binding) const {
644    const auto & rate = binding.getRate();
645    if (rate.isFixed() && binding.nonDeferred() && !binding.isMisaligned()) {
646        const auto r = rate.getRate();
647        auto n = (r.numerator() * mStride);
648        if (LLVM_LIKELY(r.denominator() == 1)) {
649            return n;
650        } else if (LLVM_LIKELY((n % r.denominator()) == 0)) {
651            return n / r.denominator();
652        }
653    }
654    return 1; // ∀x GCD(x, x + 1) = 1
655}
656
657/** ------------------------------------------------------------------------------------------------------------- *
658 * @brief getCopyAlignment
659 ** ------------------------------------------------------------------------------------------------------------- */
660inline unsigned LLVM_READNONE MultiBlockKernel::getCopyAlignment(const Binding & binding) const {
661    return ((getItemAlignment(binding) * getItemWidth(binding)) + 7) / 8;
662}
663
664/** ------------------------------------------------------------------------------------------------------------- *
665 * @brief getStrideSize
666 ** ------------------------------------------------------------------------------------------------------------- */
667llvm::Value * LLVM_READNONE MultiBlockKernel::getStrideSize(const std::unique_ptr<KernelBuilder> & b, const ProcessingRate & rate) {
668    // NOTE: if we ever support feedback loops, using upper bound could lead to a deadlock due to data starvation
669    const auto r = getUpperBound(rate);
670    if (r.numerator() == 0) {
671        return nullptr;
672    } else {
673        assert ((r.numerator() * mStride) % r.denominator() == 0);
674        return b->getSize((r.numerator() * mStride) / r.denominator());
675    }
676}
677
678// #define DEBUG_LOG
679
680/** ------------------------------------------------------------------------------------------------------------- *
681 * @brief generateKernelMethod
682 ** ------------------------------------------------------------------------------------------------------------- */
683void MultiBlockKernel::generateKernelMethod(const std::unique_ptr<KernelBuilder> & b) {
684
685    if (LLVM_UNLIKELY((mStride % b->getBitBlockWidth()) != 0)) {
686        report_fatal_error(getName() + ": the Stride (" + std::to_string(mStride) + ") of MultiBlockKernel "
687                           "must be a multiple of the BitBlockWidth (" + std::to_string(b->getBitBlockWidth()) + ")");
688    }
689
690    using RateValue = ProcessingRate::RateValue;
691
692    const auto inputSetCount = mStreamSetInputs.size();
693    const auto outputSetCount = mStreamSetOutputs.size();
694
695    // Define and allocate the temporary buffer area in the prolog.   
696    const auto blockAlignment = b->getBitBlockWidth() / 8;
697    AllocaInst * temporaryInputBuffer[inputSetCount];
698    for (unsigned i = 0; i < inputSetCount; ++i) {       
699        const Binding & input = mStreamSetInputs[i];
700        const ProcessingRate & rate = input.getRate();
701        temporaryInputBuffer[i] = nullptr;
702        if (requiresTemporaryInputBuffer(input, rate)) {
703            Type * const ty = mStreamSetInputBuffers[i]->getStreamSetBlockType();
704            auto ub = getUpperBound(rate);
705            assert (ub != 0);
706            if (LLVM_UNLIKELY(input.hasLookahead())) {
707                ub += RateValue(input.getLookahead(), mStride);
708            }
709            Value * arraySize = b->getInt64(ceiling(ub));
710
711            auto name = input.getName();
712            if (input.isSwizzled()) {
713                // TODO workaround to use larger temporary buffer size for swizzled buffer
714                arraySize = b->CreateMul(arraySize, b->getSize(codegen::BufferSegments * codegen::ThreadNum * codegen::SegmentSize));
715            }
716
717            AllocaInst * const ptr = b->CreateAlignedAlloca(ty, blockAlignment, arraySize);
718            assert (ptr->isStaticAlloca());
719            temporaryInputBuffer[i] = ptr;
720        }
721    }
722
723    AllocaInst * temporaryOutputBuffer[outputSetCount];
724    for (unsigned i = 0; i < outputSetCount; i++) {
725        const Binding & output = mStreamSetOutputs[i];
726        const ProcessingRate & rate = output.getRate();
727        temporaryOutputBuffer[i] = nullptr;
728        if (requiresTemporaryOutputBuffer(output, rate)) {
729            auto ub = getUpperBound(rate);
730            if (ub > 0) {
731                if (LLVM_UNLIKELY(mStreamSetOutputBuffers[i]->supportsCopyBack() && requiresCopyBack(rate))) {
732                    ub += mStreamSetOutputBuffers[i]->overflowSize();
733                }
734                Type * const ty = mStreamSetOutputBuffers[i]->getStreamSetBlockType();
735                Constant * const arraySize = b->getInt64(ceiling(ub));
736                AllocaInst * const ptr = b->CreateAlignedAlloca(ty, blockAlignment, arraySize);
737                assert (ptr->isStaticAlloca());
738                temporaryOutputBuffer[i] = ptr;
739            }
740        }
741    }
742
743    Constant * const ZERO = b->getSize(0);
744    Constant * const ONE = b->getSize(1);
745    Constant * const LOG_2_BLOCK_WIDTH = b->getSize(std::log2(b->getBitBlockWidth()));
746    Constant * const BLOCK_WIDTH_MASK = b->getSize(b->getBitBlockWidth() - 1);
747
748    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
749        Value * terminatedTwice = b->CreateAnd(mIsFinal, b->getTerminationSignal());
750        Value * unprocessedData = nullptr;
751        for (unsigned i = 0; i < inputSetCount; i++) {
752            Value * processed = b->getProcessedItemCount(mStreamSetInputs[i].getName());
753            Value * const check = b->CreateICmpNE(processed, mAvailableItemCount[i]);
754            unprocessedData = unprocessedData ? b->CreateOr(unprocessedData, check) : check;
755        }
756        b->CreateAssertZero(b->CreateAnd(terminatedTwice, unprocessedData),
757                            getName() + " was called after its termination with additional input data");
758        b->CreateAssertZero(terminatedTwice,
759                            getName() + " was called after its termination");
760    }
761
762    mInitialAvailableItemCount.assign(mAvailableItemCount.begin(), mAvailableItemCount.end());
763    mInitialProcessedItemCount.resize(inputSetCount);
764    mStreamSetInputBaseAddress.resize(inputSetCount);
765
766    Value * const initiallyFinal = mIsFinal;
767    #ifdef DEBUG_LOG
768    b->CallPrintInt(getName() + "_initiallyFinal", initiallyFinal);
769    #endif
770    // Now proceed with creation of the doSegment method.
771    BasicBlock * const segmentLoop = b->CreateBasicBlock("SegmentLoop");
772
773    b->CreateBr(segmentLoop);
774
775    /// DO SEGMENT LOOP
776
777    b->SetInsertPoint(segmentLoop);
778
779    Value * numOfStrides = nullptr;
780
781    // TODO: we don't want the our available output space to limit how many conditional blocks we
782    // can check. When we have a conditional region, split computation of input/output strides and
783    // check as many input strides as possible but leave the kernel in a state that respects our
784    // available output space. NOTE: we know coming into this block that the pipeline or kernel has
785    // ensured there is at least one stride worth of space.
786
787
788    // For each input buffer, get the initial processed item count, base input pointer, and the number of
789    // linearly available strides.
790    Value * inputStrideSize[inputSetCount];
791    Value * linearlyAccessible[inputSetCount];
792    for (unsigned i = 0; i < inputSetCount; i++) {
793        const Binding & input = mStreamSetInputs[i];
794        const auto & name = input.getName();
795        Value * const processed = b->getProcessedItemCount(name);
796        #ifdef DEBUG_LOG
797        b->CallPrintInt(getName() + "_" + name + "_avail", mAvailableItemCount[i]);
798        b->CallPrintInt(getName() + "_" + name + "_processed", processed);
799        #endif
800        mInitialProcessedItemCount[i] = processed;
801        mStreamSetInputBaseAddress[i] = b->getBlockAddress(name, b->CreateLShr(processed, LOG_2_BLOCK_WIDTH));
802        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
803            b->CreateAssert(b->CreateICmpULE(processed, mAvailableItemCount[i]),
804                            getName() + ": " + name + " processed item count exceeds its available item count");
805        }
806
807        Value * const unprocessed = b->CreateSub(mAvailableItemCount[i], processed);
808        #ifdef DEBUG_LOG
809        b->CallPrintInt(getName() + "_" + name + "_unprocessed", unprocessed);
810        #endif
811        Value * const accessible = b->getLinearlyAccessibleItems(name, processed, unprocessed);
812        #ifdef DEBUG_LOG
813        b->CallPrintInt(getName() + "_" + name + "_accessible", accessible);
814        #endif
815        mAvailableItemCount[i] = unprocessed;
816        linearlyAccessible[i] = accessible;
817        inputStrideSize[i] = getStrideSize(b, input.getRate());
818        Value * const accessibleStrides = b->CreateUDiv(accessible, inputStrideSize[i]);
819        numOfStrides = b->CreateUMin(numOfStrides, accessibleStrides);
820    }
821
822    BasicBlock * const checkInputAvailability = b->CreateBasicBlock("CheckInputAvailability");
823    BasicBlock * const selectOutputBuffers = b->CreateBasicBlock("SelectOutputBuffers");
824    b->CreateLikelyCondBr(b->CreateICmpNE(numOfStrides, ZERO), selectOutputBuffers, checkInputAvailability);
825
826    // Ensure that everything between S⌈P/S⌉ and S⌈n*(P + L)/S⌉ is linearly available, where S is the stride size,
827    // P is the current processed position, L is the lookahead amount and n is our number of accessible strides ∈ â„€+.
828    b->SetInsertPoint(checkInputAvailability);
829    Value * linearlyCopyable[inputSetCount];
830    PHINode * selectedInputBuffer[inputSetCount];
831    for (unsigned i = 0; i < inputSetCount; i++) {
832        AllocaInst * const tempBuffer = temporaryInputBuffer[i];
833        selectedInputBuffer[i] = nullptr;
834        if (tempBuffer) {
835
836            const Binding & input = mStreamSetInputs[i];
837            const auto & name = input.getName();
838            Value * const processed = mInitialProcessedItemCount[i];
839            Value * const unprocessed = mAvailableItemCount[i];
840            Value * const accessible = linearlyAccessible[i];
841
842            BasicBlock * const entry = b->GetInsertBlock();
843
844            Value * strideSize = inputStrideSize[i];
845            if (LLVM_UNLIKELY(input.hasLookahead())) {
846                Constant * const lookahead = b->getSize(input.getLookahead());
847                strideSize = b->CreateAdd(strideSize, lookahead);
848            }
849
850            Value * const requiresCopy = b->CreateICmpULT(accessible, strideSize);
851
852            BasicBlock * const resume = b->CreateBasicBlock(name + "Resume");
853
854            BasicBlock * copyToBackEnd = NULL;
855            BasicBlock * copyToFrontEnd = NULL;
856            Value * isPartialStride = NULL;
857            Value * newAvailable = NULL;
858
859            if (input.isSwizzled()) {
860                // Copy at least one whole block for Swizzled input stream
861                BasicBlock * const copyFromBack = b->CreateBasicBlock(name + "CopyFromBack");
862                BasicBlock * const copyFromFront = b->CreateBasicBlock(name + "CopyFromFront");
863
864                b->CreateUnlikelyCondBr(requiresCopy, copyFromBack, resume);
865
866                b->SetInsertPoint(copyFromBack);
867
868
869                Value * const arraySize = b->CreateZExt(tempBuffer->getArraySize(), b->getInt64Ty());
870                Value * const temporarySize = b->CreateTrunc(b->CreateMul(arraySize, b->getInt64(mStride)), accessible->getType());
871
872                Value * const processedOffset = b->CreateAnd(processed, BLOCK_WIDTH_MASK);
873                Value * const copyable = b->CreateUMin(b->CreateAdd(unprocessed, processedOffset), temporarySize); // <- we only really need strideSize items
874                newAvailable = b->CreateSub(copyable, processedOffset);
875//                b->CallPrintInt("newAvailable", newAvailable);
876
877                Value * const bufferSize = b->CreateMul(ConstantExpr::getSizeOf(tempBuffer->getAllocatedType()), arraySize);
878                b->CreateMemZero(tempBuffer, bufferSize, blockAlignment);
879
880//                b->CallPrintInt("temporarySize", temporarySize);
881//                b->CallPrintInt("processed", processed);
882//                b->CallPrintInt("unprocessed", unprocessed);
883//                b->CallPrintInt("processedOffset", processedOffset);
884//                b->CallPrintInt("copyable", copyable);
885
886//                b->CallPrintInt("streamCpy1", b->getSize(0));
887                Value* BIT_BLOCK_WIDTH = b->getSize(b->getBitBlockWidth());
888
889                Value* copyAmount1 = b->CreateAdd(accessible, processedOffset);
890                Value* roundCopyAmount = b->CreateMul(b->CreateUDivCeil(copyAmount1, BIT_BLOCK_WIDTH), BIT_BLOCK_WIDTH);
891                b->CreateStreamCpy(name, tempBuffer, ZERO, mStreamSetInputBaseAddress[i], ZERO, roundCopyAmount, getItemAlignment(input));
892
893                copyToBackEnd = b->GetInsertBlock();
894
895                b->CreateCondBr(b->CreateICmpNE(copyable, b->CreateAdd(accessible, processedOffset)), copyFromFront, resume);
896
897                b->SetInsertPoint(copyFromFront);
898                Value * const remaining = b->CreateSub(copyable, b->CreateAdd(accessible, processedOffset));
899                Value * const baseAddress = b->getBaseAddress(name);
900//                b->CallPrintInt("streamCpy2", b->getSize(0));
901
902                auto castedTempBuffer = b->CreatePointerCast(tempBuffer, b->getBitBlockType()->getPointerTo());
903
904                auto p = b->CreateGEP(
905                        castedTempBuffer,
906                        b->CreateMul(
907                                b->CreateUDiv(b->CreateAdd(accessible, processedOffset), BIT_BLOCK_WIDTH),
908                                b->getSize(this->getAnyStreamSetBuffer(name)->getNumOfStreams())
909                        )
910                );
911//                b->CreateStreamCpy(name, tempBuffer, b->CreateAdd(accessible, processedOffset), baseAddress, ZERO, remaining, getItemAlignment(input));
912
913
914                b->CreateStreamCpy(name, p, ZERO, baseAddress, ZERO, b->CreateMul(b->CreateUDivCeil(remaining, BIT_BLOCK_WIDTH), BIT_BLOCK_WIDTH), getItemAlignment(input));
915                isPartialStride = b->CreateICmpUGE(copyable, strideSize);
916                copyToFrontEnd = b->GetInsertBlock();
917
918
919
920                b->CreateBr(resume);
921            } else {
922                BasicBlock * const copyFromBack = b->CreateBasicBlock(name + "CopyFromBack");
923                BasicBlock * const copyFromFront = b->CreateBasicBlock(name + "CopyFromFront");
924
925                b->CreateUnlikelyCondBr(requiresCopy, copyFromBack, resume);
926
927                b->SetInsertPoint(copyFromBack);
928                Value * const arraySize = b->CreateZExt(tempBuffer->getArraySize(), b->getInt64Ty());
929                Value * const temporarySize = b->CreateTrunc(b->CreateMul(arraySize, b->getInt64(mStride)), accessible->getType());
930                Value * const copyable = b->CreateUMin(unprocessed, temporarySize); // <- we only really need strideSize items
931                newAvailable = copyable;
932                Value * const offset = b->CreateAnd(processed, BLOCK_WIDTH_MASK);
933
934                Value * const bufferSize = b->CreateMul(ConstantExpr::getSizeOf(tempBuffer->getAllocatedType()), arraySize);
935                b->CreateMemZero(tempBuffer, bufferSize, blockAlignment);
936
937                b->CreateStreamCpy(name, tempBuffer, ZERO, mStreamSetInputBaseAddress[i], offset, accessible, getItemAlignment(input));
938//            b->CallPrintInt("gep", b->CreateGEP(mStreamSetInputBaseAddress[i], b->CreateUDiv(offset, b->getSize(this->getAnyStreamSetBuffer(name)->getNumOfStreams()))));
939//            b->CallPrintRegister(name + "_tempBuffer", b->CreateLoad(tempBuffer));
940                copyToBackEnd = b->GetInsertBlock();
941                b->CreateCondBr(b->CreateICmpNE(copyable, accessible), copyFromFront, resume);
942
943                b->SetInsertPoint(copyFromFront);
944                Value * const remaining = b->CreateSub(copyable, accessible);
945                Value * const baseAddress = b->getBaseAddress(name);
946                b->CreateStreamCpy(name, tempBuffer, accessible, baseAddress, ZERO, remaining, getItemAlignment(input));
947                isPartialStride = b->CreateICmpUGE(copyable, strideSize);
948                copyToFrontEnd = b->GetInsertBlock();
949                b->CreateBr(resume);
950            }
951
952            b->SetInsertPoint(resume);
953            PHINode * const address = b->CreatePHI(tempBuffer->getType(), 3);
954            address->addIncoming(mStreamSetInputBaseAddress[i], entry);
955            address->addIncoming(tempBuffer, copyToBackEnd);
956            address->addIncoming(tempBuffer, copyToFrontEnd);
957            selectedInputBuffer[i] = address;
958            PHINode * const available = b->CreatePHI(accessible->getType(), 3);
959            available->addIncoming(accessible, entry);
960            available->addIncoming(newAvailable, copyToBackEnd);
961            available->addIncoming(newAvailable, copyToFrontEnd);
962            linearlyCopyable[i] = available;
963            PHINode * const finalStride = b->CreatePHI(b->getInt1Ty(), 3);
964            finalStride->addIncoming(mIsFinal, entry);
965            finalStride->addIncoming(b->getTrue(), copyToBackEnd);
966            finalStride->addIncoming(isPartialStride, copyToFrontEnd);
967            mIsFinal = finalStride;
968            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
969                Value * const hasStride = b->CreateOr(initiallyFinal, b->CreateNot(finalStride));
970                b->CreateAssert(hasStride, getName() + ": " + name + " has insufficient input data for one stride");
971            }
972        }
973    }
974
975    BasicBlock * const endCheckInputAvailability = b->GetInsertBlock();
976    selectOutputBuffers->moveAfter(endCheckInputAvailability);
977    b->CreateBr(selectOutputBuffers);
978
979    b->SetInsertPoint(selectOutputBuffers);
980    PHINode * const final = b->CreatePHI(mIsFinal->getType(), 2);
981    final->addIncoming(b->getFalse(), segmentLoop);
982    final->addIncoming(mIsFinal, endCheckInputAvailability);
983    mIsFinal = final;
984    for (unsigned i = 0; i < inputSetCount; i++) {
985        if (selectedInputBuffer[i]) {
986            PHINode * const address = b->CreatePHI(selectedInputBuffer[i]->getType(), 2);
987            address->addIncoming(mStreamSetInputBaseAddress[i], segmentLoop);
988            address->addIncoming(selectedInputBuffer[i], endCheckInputAvailability);
989            mStreamSetInputBaseAddress[i] = address;
990            PHINode * const accessible = b->CreatePHI(linearlyAccessible[i]->getType(), 2);
991            accessible->addIncoming(linearlyAccessible[i], segmentLoop);
992            accessible->addIncoming(linearlyCopyable[i], endCheckInputAvailability);
993            linearlyAccessible[i] = accessible;
994        }
995    }
996    PHINode * const strides = b->CreatePHI(numOfStrides->getType(), 2);
997    strides->addIncoming(numOfStrides, segmentLoop);
998    strides->addIncoming(ONE, endCheckInputAvailability);
999    numOfStrides = strides;
1000
1001    // Now determine the linearly writeable strides
1002    Value * outputStrideSize[outputSetCount];
1003    Value * linearlyWritable[outputSetCount];
1004    mInitialProducedItemCount.resize(outputSetCount);
1005    mStreamSetOutputBaseAddress.resize(outputSetCount);
1006    for (unsigned i = 0; i < outputSetCount; i++) {
1007        const auto & output = mStreamSetOutputs[i];
1008        const auto & name = output.getName();
1009        Value * const produced = b->getProducedItemCount(name);
1010        #ifdef DEBUG_LOG
1011        b->CallPrintInt(getName() + "_" + name + "_produced", produced);
1012        #endif
1013        Value * baseBuffer = b->getBlockAddress(name, b->CreateLShr(produced, LOG_2_BLOCK_WIDTH));
1014        mInitialProducedItemCount[i] = produced;
1015        mStreamSetOutputBaseAddress[i] = baseBuffer;
1016        linearlyWritable[i] = nullptr;
1017        // Is the number of linearly writable items sufficient for a stride?
1018        outputStrideSize[i] = getStrideSize(b, output.getRate());
1019        if (outputStrideSize[i]) {
1020            linearlyWritable[i] = b->getLinearlyWritableItems(name, produced);
1021            Value * writableStrides = b->CreateUDiv(linearlyWritable[i], outputStrideSize[i]);
1022            numOfStrides = b->CreateUMin(numOfStrides, writableStrides);
1023            // Do we require a temporary buffer to write to?
1024            AllocaInst * const tempBuffer = temporaryOutputBuffer[i];
1025            if (tempBuffer) {
1026                assert (tempBuffer->getType() == baseBuffer->getType());
1027                BasicBlock * const entry = b->GetInsertBlock();
1028                BasicBlock * const prepareTempBuffer = b->CreateBasicBlock(name + "PrepareTempBuffer");
1029                BasicBlock * const resume = b->CreateBasicBlock(name + "Resume");
1030                Value * const requiresCopy = b->CreateICmpEQ(writableStrides, ZERO);
1031                b->CreateUnlikelyCondBr(requiresCopy, prepareTempBuffer, resume);
1032                // Clear the output buffer prior to using it
1033                b->SetInsertPoint(prepareTempBuffer);
1034                Value * const bufferSize = b->CreateMul(ConstantExpr::getSizeOf(tempBuffer->getAllocatedType()), tempBuffer->getArraySize());
1035                b->CreateMemZero(tempBuffer, bufferSize, blockAlignment);               
1036                b->CreateBr(resume);
1037                // Select the appropriate buffer / stride #
1038                b->SetInsertPoint(resume);
1039                PHINode * const phiBuffer = b->CreatePHI(baseBuffer->getType(), 3);
1040                phiBuffer->addIncoming(baseBuffer, entry);
1041                phiBuffer->addIncoming(tempBuffer, prepareTempBuffer);
1042                baseBuffer = phiBuffer;
1043                PHINode * const phiStrides = b->CreatePHI(b->getSizeTy(), 2);
1044                phiStrides->addIncoming(numOfStrides, entry);
1045                phiStrides->addIncoming(ONE, prepareTempBuffer);
1046                numOfStrides = phiStrides;
1047            }
1048            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1049                b->CreateAssert(numOfStrides, getName() + ": " + name + " has insufficient output space for one stride");
1050            }
1051        }
1052    }
1053
1054    // Update the locally available item count to reflect the current state
1055    for (unsigned i = 0; i < inputSetCount; i++) {
1056        const Binding & input = mStreamSetInputs[i];
1057        if (input.getRate().isFixed() && input.nonDeferred()) {
1058            Value * const processable = b->CreateMul(numOfStrides, inputStrideSize[i]);
1059            linearlyAccessible[i] = b->CreateSelect(mIsFinal, linearlyAccessible[i], processable);
1060        }
1061        mAvailableItemCount[i] = linearlyAccessible[i];
1062    }
1063
1064    //  We have one or more strides of input data and output buffer space for all stream sets.
1065    generateMultiBlockLogic(b, numOfStrides);
1066
1067    for (unsigned i = 0; i < inputSetCount; ++i) {
1068        const auto & input = mStreamSetInputs[i];
1069        const ProcessingRate & rate = input.getRate();
1070        if (rate.isFixed() && input.nonDeferred()) {
1071            Value * const ic = b->CreateAdd(mInitialProcessedItemCount[i], mAvailableItemCount[i]);
1072            b->setProcessedItemCount(input.getName(), ic);
1073        }
1074    }
1075
1076    for (unsigned i = 0; i < outputSetCount; ++i) {
1077        const auto & output = mStreamSetOutputs[i];
1078        const ProcessingRate & rate = output.getRate();
1079        if (rate.isFixed()) {
1080            Value * const produced = b->CreateMul(numOfStrides, outputStrideSize[i]);
1081            Value * const ic = b->CreateAdd(mInitialProducedItemCount[i], produced);
1082            b->setProducedItemCount(output.getName(), ic);
1083        }
1084    }
1085
1086    BasicBlock * const handleFinalBlock = b->CreateBasicBlock("HandleFinalBlock");
1087    BasicBlock * const temporaryBufferCopyBack = b->CreateBasicBlock("TemporaryBufferCopyBack");
1088    BasicBlock * const strideDone = b->CreateBasicBlock("MultiBlockDone");
1089
1090    b->CreateUnlikelyCondBr(mIsFinal, handleFinalBlock, temporaryBufferCopyBack);
1091
1092
1093    /// FINAL STRIDE ADJUSTMENT
1094    b->SetInsertPoint(handleFinalBlock);
1095
1096    // If this is our final stride, adjust the Fixed output item counts. The main loop assumes that
1097    // the ITEM COUNT % FIXED RATE = 0 for all Fixed Input and Output streams. We correct that here
1098    // to calculate them based on the actual input item counts.
1099
1100    reviseFinalProducedItemCounts(b);
1101
1102    b->CreateBr(temporaryBufferCopyBack);
1103
1104    /// TEMPORARY BUFFER COPY BACK
1105    b->SetInsertPoint(temporaryBufferCopyBack);
1106
1107    // Copy back data to the actual output buffers.
1108    for (unsigned i = 0; i < outputSetCount; i++) {
1109        AllocaInst * const tempBuffer = temporaryOutputBuffer[i];
1110        if (LLVM_UNLIKELY(tempBuffer == nullptr)) {
1111            continue;
1112        }
1113        const auto & name = mStreamSetOutputs[i].getName();
1114        Value * const produced = b->getProducedItemCount(name);
1115        Value * const baseBuffer = mStreamSetOutputBaseAddress[i];
1116        assert ("stack corruption likely" && (tempBuffer->getType() == baseBuffer->getType()));
1117        //const auto & name = mStreamSetOutputs[i].getName();
1118        BasicBlock * const copyToBack = b->CreateBasicBlock(name + "CopyToBack");
1119        BasicBlock * const copyToFront = b->CreateBasicBlock(name + "CopyToFront");
1120        BasicBlock * const resume = b->CreateBasicBlock(name + "ResumeCopyBack");
1121        // If we used a temporary buffer, copy it back to the original output buffer
1122        Value * const requiresCopy = b->CreateICmpEQ(tempBuffer, baseBuffer);
1123        b->CreateCondBr(requiresCopy, copyToBack, resume);
1124
1125        b->SetInsertPoint(copyToBack);       
1126        Value * const offset = b->CreateAnd(mInitialProducedItemCount[i], BLOCK_WIDTH_MASK);
1127        //Value * const newProducedItemCount = b->getProducedItemCount(name);
1128        Value * const newlyProduced = b->CreateSub(produced, mInitialProducedItemCount[i]);
1129
1130
1131        Value * const toWrite = b->CreateUMin(newlyProduced, linearlyWritable[i]);
1132        const auto alignment = getItemAlignment(mStreamSetOutputs[i]);
1133        b->CreateStreamCpy(name, baseBuffer, offset, tempBuffer, ZERO, toWrite, alignment);
1134        // If we required a temporary output buffer, we will probably need to write to the beginning of the buffer as well.
1135        b->CreateLikelyCondBr(b->CreateICmpULT(toWrite, newlyProduced), copyToFront, resume);
1136
1137        b->SetInsertPoint(copyToFront);
1138        Value * const remaining = b->CreateSub(newlyProduced, toWrite);
1139        Value * const baseAddress = b->getBaseAddress(name);
1140        b->CreateStreamCpy(name, baseAddress, ZERO, tempBuffer, toWrite, remaining, alignment);
1141        b->CreateBr(resume);
1142
1143        b->SetInsertPoint(resume);
1144    }
1145
1146    //  We've dealt with the partial block processing and copied information back into the
1147    //  actual buffers.  If this isn't the final block, loop back for more multiblock processing.
1148    BasicBlock * const segmentDone = b->CreateBasicBlock("SegmentDone");
1149    if (canTerminateEarly()) {
1150        mIsFinal = b->CreateOr(mIsFinal, b->getTerminationSignal());
1151    }
1152    b->CreateCondBr(mIsFinal, segmentDone, strideDone);
1153
1154    /// STRIDE DONE
1155    strideDone->moveAfter(b->GetInsertBlock());
1156    b->SetInsertPoint(strideDone);
1157
1158    // do we have enough data for another stride?
1159    Value * hasMoreStrides = b->getTrue();
1160    for (unsigned i = 0; i < inputSetCount; ++i) {
1161        const Binding & input = mStreamSetInputs[i];
1162        const auto & name = input.getName();
1163        Value * const avail = mInitialAvailableItemCount[i];
1164        Value * const processed = b->getProcessedItemCount(name);
1165//        b->CallPrintInt(getName() + "_" + name + "_processed'", processed);
1166
1167        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1168            b->CreateAssert(b->CreateICmpULE(processed, avail), getName() + ": " + name + " processed data exceeds available data");
1169        }
1170        Value * const remaining = b->CreateSub(avail, processed);
1171        Value * strideSize = inputStrideSize[i];
1172        if (LLVM_UNLIKELY(input.hasLookahead())) {
1173            strideSize = b->CreateAdd(strideSize, b->getSize(input.getLookahead()));
1174        }
1175        Value * const hasRemainingStrides = b->CreateICmpUGE(remaining, strideSize);
1176        hasMoreStrides = b->CreateAnd(hasMoreStrides, hasRemainingStrides);
1177    }
1178
1179    // even if we do not have enough input data for a full stride, if this is our final stride, allow it ...
1180    hasMoreStrides = b->CreateOr(hasMoreStrides, initiallyFinal);
1181
1182    // do we have enough room for another stride?
1183    for (unsigned i = 0; i < outputSetCount; ++i) {
1184        const ProcessingRate & rate = mStreamSetOutputs[i].getRate();
1185        const auto & name = mStreamSetOutputs[i].getName();
1186        Value * const produced = b->getProducedItemCount(name);
1187
1188        // If this output has a Fixed/Bounded rate, determine whether we have room for another stride.
1189        if (LLVM_LIKELY(outputStrideSize[i] != nullptr)) {
1190            Value * const consumed = b->getConsumedItemCount(name);
1191            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1192                b->CreateAssert(b->CreateICmpULE(consumed, produced),
1193                                getName() + ": " + name + " consumed data exceeds produced data");
1194            }
1195            Value * const unconsumed = b->CreateSub(produced, consumed);
1196
1197//            b->CallPrintInt(getName() + "_" + name + "_unconsumed", unconsumed);
1198
1199            Value * const capacity = b->getBufferedSize(name);
1200
1201//            b->CallPrintInt(getName() + "_" + name + "_capacity", capacity);
1202
1203            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1204                b->CreateAssert(b->CreateICmpULE(unconsumed, capacity),
1205                                getName() + ": " + name + " more data was written than its capacity allows");
1206            }
1207
1208
1209
1210            Value * const remaining = b->CreateSub(capacity, unconsumed);
1211            Value * const hasRemainingStrides = b->CreateICmpUGE(remaining, outputStrideSize[i]);
1212            hasMoreStrides = b->CreateAnd(hasMoreStrides, hasRemainingStrides);
1213        }
1214        // Do copybacks if necessary.
1215        if (mStreamSetOutputBuffers[i]->supportsCopyBack() && requiresCopyBack(rate)) {
1216            BasicBlock * const copyBack = b->CreateBasicBlock(name + "CopyBack");
1217            BasicBlock * const done = b->CreateBasicBlock(name + "CopyBackDone");
1218
1219            Value * const bufferSize = b->getBufferedSize(name);
1220            Value * const prior = b->CreateURem(mInitialProducedItemCount[i], bufferSize);
1221            Value * const current = b->CreateURem(produced, bufferSize);
1222            b->CreateUnlikelyCondBr(b->CreateICmpUGT(prior, current), copyBack, done);
1223
1224            b->SetInsertPoint(copyBack);
1225            const auto copyAlignment = getItemAlignment(mStreamSetOutputs[i]);
1226            Value * const startOfBuffer = b->getBaseAddress(name);
1227            Value * const offset = b->CreateUDiv(bufferSize, b->getSize(b->getBitBlockWidth()));
1228            Value * const endOfBuffer = b->CreateGEP(startOfBuffer, offset);
1229            b->CreateStreamCpy(name, startOfBuffer, ZERO, endOfBuffer, ZERO, current, copyAlignment);
1230            b->CreateBr(done);
1231
1232            b->SetInsertPoint(done);
1233        }
1234    }
1235
1236    b->CreateCondBr(hasMoreStrides, segmentLoop, segmentDone);
1237
1238    /// SEGMENT DONE
1239    segmentDone->moveAfter(b->GetInsertBlock());
1240    b->SetInsertPoint(segmentDone);
1241
1242}
1243
1244/** ------------------------------------------------------------------------------------------------------------- *
1245 * @brief requiresCopyBack
1246 ** ------------------------------------------------------------------------------------------------------------- */
1247bool MultiBlockKernel::requiresCopyBack(const ProcessingRate & rate) const {
1248    if (rate.isBounded() || rate.isUnknown()) {
1249        return true;
1250    } else if (rate.isRelative()) {
1251        return requiresCopyBack(getBinding(rate.getReference()).getRate());
1252    }
1253    return false;
1254}
1255
1256/** ------------------------------------------------------------------------------------------------------------- *
1257 * @brief CreateUDivCeil
1258 ** ------------------------------------------------------------------------------------------------------------- */
1259inline Value * CreateUDivCeil(const std::unique_ptr<KernelBuilder> & b, Value * const number, const ProcessingRate::RateValue divisor, const Twine & Name = "") {
1260    Constant * const n = ConstantInt::get(number->getType(), divisor.numerator());
1261    if (LLVM_LIKELY(divisor.denominator() == 1)) {
1262        return b->CreateUDivCeil(number, n, Name);
1263    } else {
1264        //   âŒŠ(num + ratio - 1) / ratio⌋
1265        // = ⌊(num - 1) / (n/d)⌋ + (ratio/ratio)
1266        // = ⌊(d * (num - 1)) / n⌋ + 1
1267        Constant * const ONE = ConstantInt::get(number->getType(), 1);
1268        Constant * const d = ConstantInt::get(number->getType(), divisor.denominator());
1269        return b->CreateAdd(b->CreateUDiv(b->CreateMul(b->CreateSub(number, ONE), d), n), ONE, Name);
1270    }
1271}
1272
1273
1274/** ------------------------------------------------------------------------------------------------------------- *
1275 * @brief reviseFinalProducedItemCounts
1276 ** ------------------------------------------------------------------------------------------------------------- */
1277void MultiBlockKernel::reviseFinalProducedItemCounts(const std::unique_ptr<KernelBuilder> & b) {
1278
1279    if (LLVM_UNLIKELY(mStreamSetInputs.empty())) {
1280        return;
1281    }
1282
1283    const auto inputSetCount = mStreamSetInputs.size();
1284
1285    ProcessingRate::RateValue rateLCM(1);
1286    unsigned first = 0;
1287    unsigned last = inputSetCount;
1288
1289    for (unsigned i = 0; i < inputSetCount; ++i) {
1290        const ProcessingRate & pr = mStreamSetInputs[i].getRate();
1291        if (pr.isFixed()) {
1292            rateLCM = lcm(rateLCM, pr.getRate());
1293            if (mStreamSetInputs[i].isPrincipal()) {
1294                assert ("A kernel cannot have multiple principle input streams" && (first == 0 && last == inputSetCount));
1295                first = i;
1296                last = i + 1;
1297            }
1298        }       
1299    }
1300
1301    bool noFixedRateOutput = true;
1302
1303    for (const Binding & output : mStreamSetOutputs) {
1304        const ProcessingRate & pr = output.getRate();
1305        if (pr.isFixed()) {
1306            rateLCM = lcm(rateLCM, pr.getRate());
1307            noFixedRateOutput = false;
1308        }
1309    }
1310
1311    if (noFixedRateOutput) {
1312        return;
1313    }
1314
1315    Value * baseInitialProcessedItemCount = nullptr;
1316    Value * scaledInverseOfAvailItemCount = nullptr;
1317
1318    // For each Fixed output stream, this calculates:
1319
1320    //    CEILING(MIN(Available Item Count / Fixed Input Rate) * Fixed Output Rate)
1321
1322    // But avoids the possibility of overflow errors (assuming that each processed item count does not overflow)
1323
1324    for (unsigned i = first; i < last; ++i) {
1325        const ProcessingRate & pr = mStreamSetInputs[i].getRate();
1326        if (pr.isFixed()) {
1327            Value * p = mInitialProcessedItemCount[i];
1328            Value * a = b->CreateSub(mInitialAvailableItemCount[i], p);
1329            const auto & rate = pr.getRate();
1330            if (LLVM_UNLIKELY(rateLCM != rate)) {
1331                const auto factor = rateLCM / rate;
1332                if (LLVM_UNLIKELY(factor.numerator() > 1)) {
1333                    a = b->CreateMul(a, b->getSize(factor.numerator()));
1334                }
1335                if (LLVM_UNLIKELY(factor.denominator() > 1)) {
1336                    a = b->CreateUDiv(a, b->getSize(factor.denominator()));
1337                }
1338            }
1339            if (LLVM_UNLIKELY(rate.denominator() > 1)) {
1340                p = b->CreateMul(p, b->getSize(rate.denominator()));
1341            }
1342            if (LLVM_UNLIKELY(rate.numerator() > 1)) {
1343                p = b->CreateUDiv(p, b->getSize(rate.numerator()));
1344            }
1345            if (scaledInverseOfAvailItemCount) {
1346                scaledInverseOfAvailItemCount = b->CreateUMin(scaledInverseOfAvailItemCount, a);
1347                baseInitialProcessedItemCount = b->CreateUMin(baseInitialProcessedItemCount, p);
1348            } else {
1349                scaledInverseOfAvailItemCount = a;
1350                baseInitialProcessedItemCount = p;
1351            }
1352        }
1353    }
1354
1355    for (const Binding & output : mStreamSetOutputs) {
1356        const auto name = output.getName();
1357        const ProcessingRate & pr = output.getRate();
1358        Value * produced = nullptr;
1359        if (pr.isFixed() && output.nonDeferred()) {
1360            assert (baseInitialProcessedItemCount && scaledInverseOfAvailItemCount);
1361            const auto rate = pr.getRate();
1362            Value * p = baseInitialProcessedItemCount;
1363            if (LLVM_UNLIKELY(rate.numerator() != 1)) {
1364                p = b->CreateMul(p, b->getSize(rate.numerator()));
1365            }
1366            if (LLVM_UNLIKELY(rate.denominator() != 1)) {
1367                p = b->CreateUDiv(p, b->getSize(rate.denominator()));
1368            }
1369            Value * const ic = CreateUDivCeil(b, scaledInverseOfAvailItemCount, rateLCM / pr.getRate());
1370            produced = b->CreateAdd(p, ic);
1371        } else { // check if we have an attribute; if so, get the current produced count and adjust it
1372            bool noAttributes = true;
1373            for (const Attribute & attr : output.getAttributes()) {
1374                if (attr.isAdd() || attr.isRoundUpTo()) {
1375                    noAttributes = false;
1376                    break;
1377                }
1378            }
1379            if (noAttributes) {
1380                continue;
1381            }
1382            produced = b->getProducedItemCount(name);
1383        }
1384        for (const Attribute & attr : output.getAttributes()) {
1385            if (attr.isAdd()) {
1386                produced = b->CreateAdd(produced, b->getSize(attr.amount()));
1387            } else if (attr.isRoundUpTo()) {
1388                produced = b->CreateRoundUp(produced, b->getSize(attr.amount()));
1389            }
1390        }
1391        b->setProducedItemCount(name, produced);
1392    }
1393
1394}
1395
1396/** ------------------------------------------------------------------------------------------------------------- *
1397 * @brief generateMultiBlockLogic
1398 ** ------------------------------------------------------------------------------------------------------------- */
1399void BlockOrientedKernel::generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> & b, Value * const numOfBlocks) {
1400
1401    if (LLVM_UNLIKELY(mStride != b->getBitBlockWidth())) {
1402        report_fatal_error(getName() + ": the Stride (" + std::to_string(mStride) + ") of BlockOrientedKernel "
1403                           "equal to the BitBlockWidth (" + std::to_string(b->getBitBlockWidth()) + ")");
1404    }
1405
1406    Constant * const LOG_2_BLOCK_WIDTH = b->getSize(std::log2(b->getBitBlockWidth()));
1407
1408    BasicBlock * const entryBlock = b->GetInsertBlock();
1409    mStrideLoopBody = b->CreateBasicBlock(getName() + "_strideLoopBody");
1410    BasicBlock * const stridesDone = b->CreateBasicBlock(getName() + "_stridesDone");
1411    BasicBlock * const doFinalBlock = b->CreateBasicBlock(getName() + "_doFinalBlock");
1412    BasicBlock * const segmentDone = b->CreateBasicBlock(getName() + "_segmentDone");
1413
1414    const auto inputSetCount = mStreamSetInputs.size();
1415    Value * baseProcessedIndex[inputSetCount];
1416    Value * baseInputAddress[inputSetCount];
1417    for (unsigned i = 0; i < inputSetCount; i++) {
1418        const ProcessingRate & rate = mStreamSetInputs[i].getRate();
1419        if (LLVM_UNLIKELY(!rate.isFixed())) {
1420            Value * const ic = mInitialProcessedItemCount[i];
1421            baseProcessedIndex[i] = b->CreateLShr(ic, LOG_2_BLOCK_WIDTH);
1422        }
1423        baseInputAddress[i] = mStreamSetInputBaseAddress[i];
1424    }
1425
1426    const auto outputSetCount = mStreamSetOutputs.size();
1427    Value * baseProducedIndex[outputSetCount];
1428    Value * baseOutputAddress[inputSetCount];
1429    for (unsigned i = 0; i < outputSetCount; i++) {
1430        const ProcessingRate & rate = mStreamSetOutputs[i].getRate();
1431        if (LLVM_UNLIKELY(!rate.isFixed())) {
1432            Value * const ic = b->getProducedItemCount(mStreamSetOutputs[i].getName());
1433            baseProducedIndex[i] = b->CreateLShr(ic, LOG_2_BLOCK_WIDTH);
1434        }
1435        baseOutputAddress[i] = mStreamSetOutputBaseAddress[i];
1436    }
1437
1438    b->CreateUnlikelyCondBr(mIsFinal, doFinalBlock, mStrideLoopBody);
1439
1440    /// BLOCK BODY
1441
1442    b->SetInsertPoint(mStrideLoopBody);
1443
1444    if (b->supportsIndirectBr()) {
1445        Value * const baseTarget = BlockAddress::get(segmentDone);
1446        mStrideLoopTarget = b->CreatePHI(baseTarget->getType(), 2, "strideTarget");
1447        mStrideLoopTarget->addIncoming(baseTarget, entryBlock);
1448    }
1449
1450    mStrideBlockIndex = b->CreatePHI(b->getSizeTy(), 2);
1451    mStrideBlockIndex->addIncoming(b->getSize(0), entryBlock);
1452
1453    /// GENERATE DO BLOCK METHOD
1454
1455    for (unsigned i = 0; i < inputSetCount; ++i) {
1456        Value * index = mStrideBlockIndex;
1457        const ProcessingRate & rate = mStreamSetInputs[i].getRate();
1458        if (LLVM_UNLIKELY(!rate.isFixed())) {
1459            Value * ic = b->getProcessedItemCount(mStreamSetInputs[i].getName());
1460            index = b->CreateSub(b->CreateLShr(ic, LOG_2_BLOCK_WIDTH), baseProcessedIndex[i]);
1461        }
1462        mStreamSetInputBaseAddress[i] = b->CreateGEP(mStreamSetInputBaseAddress[i], index);
1463    }
1464
1465    for (unsigned i = 0; i < outputSetCount; ++i) {
1466        Value * index = mStrideBlockIndex;
1467        const ProcessingRate & rate = mStreamSetOutputs[i].getRate();
1468        if (LLVM_UNLIKELY(!rate.isFixed())) {
1469            Value * ic = b->getProducedItemCount(mStreamSetOutputs[i].getName());
1470            index = b->CreateSub(b->CreateLShr(ic, LOG_2_BLOCK_WIDTH), baseProducedIndex[i]);
1471        }
1472        mStreamSetOutputBaseAddress[i] = b->CreateGEP(mStreamSetOutputBaseAddress[i], index);
1473    }
1474
1475    writeDoBlockMethod(b);
1476
1477    BasicBlock * const bodyEnd = b->GetInsertBlock();
1478    if (mStrideLoopTarget) {
1479        mStrideLoopTarget->addIncoming(mStrideLoopTarget, bodyEnd);
1480    }
1481
1482    Value * const nextIndex = b->CreateAdd(mStrideBlockIndex, b->getSize(1));
1483    mStrideBlockIndex->addIncoming(nextIndex, bodyEnd);
1484    Value * const notDone = b->CreateICmpULT(nextIndex, numOfBlocks);
1485    b->CreateCondBr(notDone, mStrideLoopBody, stridesDone);
1486
1487    stridesDone->moveAfter(bodyEnd);
1488
1489    /// STRIDE DONE
1490
1491    b->SetInsertPoint(stridesDone);
1492
1493    // Now conditionally perform the final block processing depending on the doFinal parameter.
1494    if (mStrideLoopTarget) {
1495        mStrideLoopBranch = b->CreateIndirectBr(mStrideLoopTarget, 3);
1496        mStrideLoopBranch->addDestination(doFinalBlock);
1497        mStrideLoopBranch->addDestination(segmentDone);
1498    } else {
1499        b->CreateUnlikelyCondBr(mIsFinal, doFinalBlock, segmentDone);
1500    }
1501
1502    doFinalBlock->moveAfter(stridesDone);
1503
1504    /// DO FINAL BLOCK
1505
1506    b->SetInsertPoint(doFinalBlock);
1507    for (unsigned i = 0; i < inputSetCount; ++i) {
1508        mStreamSetInputBaseAddress[i] = baseInputAddress[i];
1509    }
1510
1511    for (unsigned i = 0; i < outputSetCount; ++i) {
1512        mStreamSetOutputBaseAddress[i] = baseOutputAddress[i];
1513    }
1514
1515    writeFinalBlockMethod(b, getRemainingItems(b));
1516
1517    b->CreateBr(segmentDone);
1518
1519    segmentDone->moveAfter(b->GetInsertBlock());
1520
1521    b->SetInsertPoint(segmentDone);
1522
1523    // Update the branch prediction metadata to indicate that the likely target will be segmentDone
1524    if (mStrideLoopTarget) {
1525        MDBuilder mdb(b->getContext());
1526        const auto destinations = mStrideLoopBranch->getNumDestinations();
1527        uint32_t weights[destinations];
1528        for (unsigned i = 0; i < destinations; ++i) {
1529            weights[i] = (mStrideLoopBranch->getDestination(i) == segmentDone) ? 100 : 1;
1530        }
1531        ArrayRef<uint32_t> bw(weights, destinations);
1532        mStrideLoopBranch->setMetadata(LLVMContext::MD_prof, mdb.createBranchWeights(bw));
1533    }
1534
1535}
1536
1537/** ------------------------------------------------------------------------------------------------------------- *
1538 * @brief getRemainingItems
1539 ** ------------------------------------------------------------------------------------------------------------- */
1540Value * BlockOrientedKernel::getRemainingItems(const std::unique_ptr<KernelBuilder> & b) {
1541    Value * remainingItems = nullptr;
1542    const auto count = mStreamSetInputs.size();
1543    if (count == 1) {
1544        return mAvailableItemCount[0];
1545    } else {
1546        for (unsigned i = 0; i < count; i++) {
1547            if (mStreamSetInputs[i].isPrincipal()) {
1548                return mAvailableItemCount[i];
1549            }
1550        }
1551        for (unsigned i = 0; i < count; ++i) {
1552            const ProcessingRate & r = mStreamSetInputs[i].getRate();
1553            if (r.isFixed()) {
1554                Value * ic = CreateUDivCeil(b, mAvailableItemCount[i], r.getRate());
1555                if (remainingItems) {
1556                    remainingItems = b->CreateUMin(remainingItems, ic);
1557                } else {
1558                    remainingItems = ic;
1559                }
1560            }
1561        }
1562    }
1563    return remainingItems;
1564}
1565
1566/** ------------------------------------------------------------------------------------------------------------- *
1567 * @brief writeDoBlockMethod
1568 ** ------------------------------------------------------------------------------------------------------------- */
1569inline void BlockOrientedKernel::writeDoBlockMethod(const std::unique_ptr<KernelBuilder> & b) {
1570
1571    Value * const self = getInstance();
1572    Function * const cp = mCurrentMethod;
1573    auto ip = b->saveIP();
1574    std::vector<Value *> availableItemCount(0);
1575
1576    /// Check if the do block method is called and create the function if necessary
1577    if (!b->supportsIndirectBr()) {
1578
1579        std::vector<Type *> params;
1580        params.reserve(1 + mAvailableItemCount.size());
1581        params.push_back(self->getType());
1582        for (Value * avail : mAvailableItemCount) {
1583            params.push_back(avail->getType());
1584        }
1585
1586        FunctionType * const type = FunctionType::get(b->getVoidTy(), params, false);
1587        mCurrentMethod = Function::Create(type, GlobalValue::InternalLinkage, getName() + DO_BLOCK_SUFFIX, b->getModule());
1588        mCurrentMethod->setCallingConv(CallingConv::C);
1589        mCurrentMethod->setDoesNotThrow();
1590        auto args = mCurrentMethod->arg_begin();
1591        args->setName("self");
1592        setInstance(&*args);
1593        availableItemCount.reserve(mAvailableItemCount.size());
1594        while (++args != mCurrentMethod->arg_end()) {
1595            availableItemCount.push_back(&*args);
1596        }
1597        assert (availableItemCount.size() == mAvailableItemCount.size());
1598        mAvailableItemCount.swap(availableItemCount);
1599        b->SetInsertPoint(BasicBlock::Create(b->getContext(), "entry", mCurrentMethod));
1600    }
1601
1602    generateDoBlockMethod(b); // must be implemented by the BlockOrientedKernelBuilder subtype
1603
1604    if (!b->supportsIndirectBr()) {
1605        // Restore the DoSegment function state then call the DoBlock method
1606        b->CreateRetVoid();
1607        mDoBlockMethod = mCurrentMethod;
1608        b->restoreIP(ip);
1609        setInstance(self);
1610        mCurrentMethod = cp;
1611        mAvailableItemCount.swap(availableItemCount);
1612        CreateDoBlockMethodCall(b);
1613    }
1614
1615}
1616
1617/** ------------------------------------------------------------------------------------------------------------- *
1618 * @brief writeFinalBlockMethod
1619 ** ------------------------------------------------------------------------------------------------------------- */
1620inline void BlockOrientedKernel::writeFinalBlockMethod(const std::unique_ptr<KernelBuilder> & b, Value * remainingItems) {
1621
1622    Value * const self = getInstance();
1623    Function * const cp = mCurrentMethod;
1624    Value * const remainingItemCount = remainingItems;
1625    auto ip = b->saveIP();
1626    std::vector<Value *> availableItemCount(0);
1627
1628    if (!b->supportsIndirectBr()) {
1629        std::vector<Type *> params;
1630        params.reserve(2 + mAvailableItemCount.size());
1631        params.push_back(self->getType());
1632        params.push_back(b->getSizeTy());
1633        for (Value * avail : mAvailableItemCount) {
1634            params.push_back(avail->getType());
1635        }
1636        FunctionType * const type = FunctionType::get(b->getVoidTy(), params, false);
1637        mCurrentMethod = Function::Create(type, GlobalValue::InternalLinkage, getName() + FINAL_BLOCK_SUFFIX, b->getModule());
1638        mCurrentMethod->setCallingConv(CallingConv::C);
1639        mCurrentMethod->setDoesNotThrow();
1640        auto args = mCurrentMethod->arg_begin();
1641        args->setName("self");
1642        setInstance(&*args);
1643        remainingItems = &*(++args);
1644        remainingItems->setName("remainingItems");
1645        availableItemCount.reserve(mAvailableItemCount.size());
1646        while (++args != mCurrentMethod->arg_end()) {
1647            availableItemCount.push_back(&*args);
1648        }
1649        assert (availableItemCount.size() == mAvailableItemCount.size());
1650        mAvailableItemCount.swap(availableItemCount);
1651        b->SetInsertPoint(BasicBlock::Create(b->getContext(), "entry", mCurrentMethod));
1652    }
1653
1654    generateFinalBlockMethod(b, remainingItems); // may be implemented by the BlockOrientedKernel subtype
1655
1656    if (!b->supportsIndirectBr()) {
1657        b->CreateRetVoid();
1658        b->restoreIP(ip);
1659        setInstance(self);
1660        mAvailableItemCount.swap(availableItemCount);
1661        // Restore the DoSegment function state then call the DoFinal method
1662        std::vector<Value *> args;
1663        args.reserve(2 + mAvailableItemCount.size());
1664        args.push_back(self);
1665        args.push_back(remainingItemCount);
1666        args.insert(args.end(), mAvailableItemCount.begin(), mAvailableItemCount.end());
1667        b->CreateCall(mCurrentMethod, args);
1668        mCurrentMethod = cp;
1669    }
1670
1671}
1672
1673/** ------------------------------------------------------------------------------------------------------------- *
1674 * @brief generateFinalBlockMethod
1675 ** ------------------------------------------------------------------------------------------------------------- */
1676void BlockOrientedKernel::generateFinalBlockMethod(const std::unique_ptr<KernelBuilder> & b, Value * /* remainingItems */) {
1677    //  The default finalBlock method simply dispatches to the doBlock routine.
1678    CreateDoBlockMethodCall(b);
1679}
1680
1681void BlockOrientedKernel::CreateDoBlockMethodCall(const std::unique_ptr<KernelBuilder> & b) {
1682    if (b->supportsIndirectBr()) {
1683        BasicBlock * const bb = b->CreateBasicBlock("resume");
1684        mStrideLoopBranch->addDestination(bb);
1685        BasicBlock * const current = b->GetInsertBlock();
1686        mStrideLoopTarget->addIncoming(BlockAddress::get(bb), current);
1687        mStrideBlockIndex->addIncoming(b->getSize(0), current);
1688        b->CreateBr(mStrideLoopBody);
1689        bb->moveAfter(current);
1690        b->SetInsertPoint(bb);
1691    } else {
1692        std::vector<Value *> args;
1693        args.reserve(1 + mAvailableItemCount.size());
1694        args.push_back(getInstance());
1695        args.insert(args.end(), mAvailableItemCount.begin(), mAvailableItemCount.end());
1696        b->CreateCall(mDoBlockMethod, args);
1697    }
1698}
1699
1700static inline std::string annotateKernelNameWithDebugFlags(std::string && name) {
1701    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1702        name += "_EA";
1703    }
1704    name += "_O" + std::to_string((int)codegen::OptLevel);
1705    return name;
1706}
1707
1708// CONSTRUCTOR
1709Kernel::Kernel(std::string && kernelName,
1710               Bindings && stream_inputs,
1711               Bindings && stream_outputs,
1712               Bindings && scalar_parameters,
1713               Bindings && scalar_outputs,
1714               Bindings && internal_scalars)
1715: KernelInterface(annotateKernelNameWithDebugFlags(std::move(kernelName))
1716                  , std::move(stream_inputs), std::move(stream_outputs)
1717                  , std::move(scalar_parameters), std::move(scalar_outputs)
1718                  , std::move(internal_scalars))
1719, mCurrentMethod(nullptr)
1720, mAvailablePrincipalItemCount(nullptr)
1721, mStride(0)
1722, mIsFinal(nullptr)
1723, mOutputScalarResult(nullptr)
1724, mIsGenerated(false) {
1725
1726}
1727
1728Kernel::~Kernel() {
1729
1730}
1731
1732// MULTI-BLOCK KERNEL CONSTRUCTOR
1733MultiBlockKernel::MultiBlockKernel(std::string && kernelName,
1734                                   Bindings && stream_inputs,
1735                                   Bindings && stream_outputs,
1736                                   Bindings && scalar_parameters,
1737                                   Bindings && scalar_outputs,
1738                                   Bindings && internal_scalars)
1739: Kernel(std::move(kernelName), std::move(stream_inputs), std::move(stream_outputs), std::move(scalar_parameters), std::move(scalar_outputs), std::move(internal_scalars)) {
1740
1741}
1742
1743// CONSTRUCTOR
1744BlockOrientedKernel::BlockOrientedKernel(std::string && kernelName,
1745                                         Bindings && stream_inputs,
1746                                         Bindings && stream_outputs,
1747                                         Bindings && scalar_parameters,
1748                                         Bindings && scalar_outputs,
1749                                         Bindings && internal_scalars)
1750: MultiBlockKernel(std::move(kernelName), std::move(stream_inputs), std::move(stream_outputs), std::move(scalar_parameters), std::move(scalar_outputs), std::move(internal_scalars))
1751, mDoBlockMethod(nullptr)
1752, mStrideLoopBody(nullptr)
1753, mStrideLoopBranch(nullptr)
1754, mStrideLoopTarget(nullptr)
1755, mStrideBlockIndex(nullptr) {
1756
1757}
1758
1759// CONSTRUCTOR
1760SegmentOrientedKernel::SegmentOrientedKernel(std::string && kernelName,
1761                                             Bindings && stream_inputs,
1762                                             Bindings && stream_outputs,
1763                                             Bindings && scalar_parameters,
1764                                             Bindings && scalar_outputs,
1765                                             Bindings && internal_scalars)
1766: Kernel(std::move(kernelName), std::move(stream_inputs), std::move(stream_outputs), std::move(scalar_parameters), std::move(scalar_outputs), std::move(internal_scalars)) {
1767
1768}
1769
1770
1771}
Note: See TracBrowser for help on using the repository browser.