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

Last change on this file since 5941 was 5941, checked in by xwa163, 18 months ago
  1. Add attributes to disable some features of multiblock kernel
  2. Fix bug for lz4d new approach in large data, pass all test cases
  3. Disable lz4d related test cases for old approach
File size: 84.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 (binding.isDisableTemporaryBuffer()) {
621        return false;
622    }
623    if (requiresBufferedFinalStride(binding)) {
624        return true;
625    } else if (LLVM_UNLIKELY(isTransitivelyUnknownRate(rate))) {
626        report_fatal_error("MultiBlock kernels do not support unknown rate input streams or streams relative to an unknown rate input.");
627    } else {
628        return !rate.isFixed();
629    }
630}
631
632/** ------------------------------------------------------------------------------------------------------------- *
633 * @brief requiresTemporaryOutputBuffer
634 ** ------------------------------------------------------------------------------------------------------------- */
635inline bool LLVM_READNONE MultiBlockKernel::requiresTemporaryOutputBuffer(const Binding & binding, const ProcessingRate & rate) const {
636    if (binding.isDisableTemporaryBuffer()) {
637        return false;
638    }
639    if (requiresBufferedFinalStride(binding)) {
640        return true;
641    } else {
642        return !(rate.isFixed() || isTransitivelyUnknownRate(rate));
643    }
644}
645
646/** ------------------------------------------------------------------------------------------------------------- *
647 * @brief getItemAlignment
648 ** ------------------------------------------------------------------------------------------------------------- */
649inline unsigned LLVM_READNONE MultiBlockKernel::getItemAlignment(const Binding & binding) const {
650    const auto & rate = binding.getRate();
651    if (rate.isFixed() && binding.nonDeferred() && !binding.isMisaligned()) {
652        const auto r = rate.getRate();
653        auto n = (r.numerator() * mStride);
654        if (LLVM_LIKELY(r.denominator() == 1)) {
655            return n;
656        } else if (LLVM_LIKELY((n % r.denominator()) == 0)) {
657            return n / r.denominator();
658        }
659    }
660    return 1; // ∀x GCD(x, x + 1) = 1
661}
662
663/** ------------------------------------------------------------------------------------------------------------- *
664 * @brief getCopyAlignment
665 ** ------------------------------------------------------------------------------------------------------------- */
666inline unsigned LLVM_READNONE MultiBlockKernel::getCopyAlignment(const Binding & binding) const {
667    return ((getItemAlignment(binding) * getItemWidth(binding)) + 7) / 8;
668}
669
670/** ------------------------------------------------------------------------------------------------------------- *
671 * @brief getStrideSize
672 ** ------------------------------------------------------------------------------------------------------------- */
673llvm::Value * LLVM_READNONE MultiBlockKernel::getStrideSize(const std::unique_ptr<KernelBuilder> & b, const ProcessingRate & rate) {
674    // NOTE: if we ever support feedback loops, using upper bound could lead to a deadlock due to data starvation
675    const auto r = getUpperBound(rate);
676    if (r.numerator() == 0) {
677        return nullptr;
678    } else {
679        assert ((r.numerator() * mStride) % r.denominator() == 0);
680        return b->getSize((r.numerator() * mStride) / r.denominator());
681    }
682}
683
684// #define DEBUG_LOG
685
686/** ------------------------------------------------------------------------------------------------------------- *
687 * @brief generateKernelMethod
688 ** ------------------------------------------------------------------------------------------------------------- */
689void MultiBlockKernel::generateKernelMethod(const std::unique_ptr<KernelBuilder> & b) {
690
691    if (LLVM_UNLIKELY((mStride % b->getBitBlockWidth()) != 0)) {
692        report_fatal_error(getName() + ": the Stride (" + std::to_string(mStride) + ") of MultiBlockKernel "
693                           "must be a multiple of the BitBlockWidth (" + std::to_string(b->getBitBlockWidth()) + ")");
694    }
695
696    using RateValue = ProcessingRate::RateValue;
697
698    const auto inputSetCount = mStreamSetInputs.size();
699    const auto outputSetCount = mStreamSetOutputs.size();
700
701    // Define and allocate the temporary buffer area in the prolog.   
702    const auto blockAlignment = b->getBitBlockWidth() / 8;
703    AllocaInst * temporaryInputBuffer[inputSetCount];
704    for (unsigned i = 0; i < inputSetCount; ++i) {       
705        const Binding & input = mStreamSetInputs[i];
706        const ProcessingRate & rate = input.getRate();
707        temporaryInputBuffer[i] = nullptr;
708        if (requiresTemporaryInputBuffer(input, rate)) {
709            Type * const ty = mStreamSetInputBuffers[i]->getStreamSetBlockType();
710            auto ub = getUpperBound(rate);
711            assert (ub != 0);
712            if (LLVM_UNLIKELY(input.hasLookahead())) {
713                ub += RateValue(input.getLookahead(), mStride);
714            }
715            Value * arraySize = b->getInt64(ceiling(ub));
716            if (input.isSwizzled()) {
717                // TODO workaround to use larger temporary buffer size for swizzled buffer
718                arraySize = b->CreateMul(arraySize, b->getSize(codegen::BufferSegments * codegen::ThreadNum * codegen::SegmentSize));
719            }
720
721            AllocaInst * const ptr = b->CreateAlignedAlloca(ty, blockAlignment, arraySize);
722            assert (ptr->isStaticAlloca());
723            temporaryInputBuffer[i] = ptr;
724        }
725    }
726
727    AllocaInst * temporaryOutputBuffer[outputSetCount];
728    for (unsigned i = 0; i < outputSetCount; i++) {
729        const Binding & output = mStreamSetOutputs[i];
730        const ProcessingRate & rate = output.getRate();
731        temporaryOutputBuffer[i] = nullptr;
732        if (requiresTemporaryOutputBuffer(output, rate)) {
733            auto ub = getUpperBound(rate);
734            if (ub > 0) {
735                if (LLVM_UNLIKELY(mStreamSetOutputBuffers[i]->supportsCopyBack() && requiresCopyBack(rate))) {
736                    ub += mStreamSetOutputBuffers[i]->overflowSize();
737                }
738                Type * const ty = mStreamSetOutputBuffers[i]->getStreamSetBlockType();
739                Constant * const arraySize = b->getInt64(ceiling(ub));
740                AllocaInst * const ptr = b->CreateAlignedAlloca(ty, blockAlignment, arraySize);
741                assert (ptr->isStaticAlloca());
742                temporaryOutputBuffer[i] = ptr;
743            }
744        }
745    }
746
747    Constant * const ZERO = b->getSize(0);
748    Constant * const ONE = b->getSize(1);
749    Constant * const LOG_2_BLOCK_WIDTH = b->getSize(std::log2(b->getBitBlockWidth()));
750    Constant * const BLOCK_WIDTH_MASK = b->getSize(b->getBitBlockWidth() - 1);
751
752    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
753        Value * terminatedTwice = b->CreateAnd(mIsFinal, b->getTerminationSignal());
754        Value * unprocessedData = nullptr;
755        for (unsigned i = 0; i < inputSetCount; i++) {
756            Value * processed = b->getProcessedItemCount(mStreamSetInputs[i].getName());
757            Value * const check = b->CreateICmpNE(processed, mAvailableItemCount[i]);
758            unprocessedData = unprocessedData ? b->CreateOr(unprocessedData, check) : check;
759        }
760        b->CreateAssertZero(b->CreateAnd(terminatedTwice, unprocessedData),
761                            getName() + " was called after its termination with additional input data");
762        b->CreateAssertZero(terminatedTwice,
763                            getName() + " was called after its termination");
764    }
765
766    mInitialAvailableItemCount.assign(mAvailableItemCount.begin(), mAvailableItemCount.end());
767    mInitialProcessedItemCount.resize(inputSetCount);
768    mStreamSetInputBaseAddress.resize(inputSetCount);
769
770    Value * const initiallyFinal = mIsFinal;
771    #ifdef DEBUG_LOG
772    b->CallPrintInt(getName() + "_initiallyFinal", initiallyFinal);
773    #endif
774    // Now proceed with creation of the doSegment method.
775    BasicBlock * const segmentLoop = b->CreateBasicBlock("SegmentLoop");
776
777    b->CreateBr(segmentLoop);
778
779    /// DO SEGMENT LOOP
780
781    b->SetInsertPoint(segmentLoop);
782
783    Value * numOfStrides = nullptr;
784
785    // TODO: we don't want the our available output space to limit how many conditional blocks we
786    // can check. When we have a conditional region, split computation of input/output strides and
787    // check as many input strides as possible but leave the kernel in a state that respects our
788    // available output space. NOTE: we know coming into this block that the pipeline or kernel has
789    // ensured there is at least one stride worth of space.
790
791
792    // For each input buffer, get the initial processed item count, base input pointer, and the number of
793    // linearly available strides.
794    Value * inputStrideSize[inputSetCount];
795    Value * linearlyAccessible[inputSetCount];
796    for (unsigned i = 0; i < inputSetCount; i++) {
797        const Binding & input = mStreamSetInputs[i];
798        const auto & name = input.getName();
799        Value * const processed = b->getProcessedItemCount(name);
800        #ifdef DEBUG_LOG
801        b->CallPrintInt(getName() + "_" + name + "_avail", mAvailableItemCount[i]);
802        b->CallPrintInt(getName() + "_" + name + "_processed0", processed);
803        #endif
804        mInitialProcessedItemCount[i] = processed;
805        mStreamSetInputBaseAddress[i] = b->getBlockAddress(name, b->CreateLShr(processed, LOG_2_BLOCK_WIDTH));
806        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
807            b->CreateAssert(b->CreateICmpULE(processed, mAvailableItemCount[i]),
808                            getName() + ": " + name + " processed item count exceeds its available item count");
809        }
810
811        Value * const unprocessed = b->CreateSub(mAvailableItemCount[i], processed);
812        #ifdef DEBUG_LOG
813        b->CallPrintInt(getName() + "_" + name + "_unprocessed", unprocessed);
814        #endif
815        Value * const accessible = b->getLinearlyAccessibleItems(name, processed, unprocessed);
816        #ifdef DEBUG_LOG
817        b->CallPrintInt(getName() + "_" + name + "_accessible", accessible);
818        #endif
819        mAvailableItemCount[i] = unprocessed;
820        linearlyAccessible[i] = accessible;
821
822        const auto ub = getUpperBound(input.getRate());
823        inputStrideSize[i] = b->getSize(ceiling(ub * mStride));
824        Value * accessibleStrides = b->CreateUDiv(accessible, inputStrideSize[i]);
825
826        if (LLVM_UNLIKELY(input.hasAttribute(Attribute::KindId::AlwaysConsume))) {
827            const auto lb = getLowerBound(input.getRate());
828            Value * const lowerbound = b->getSize(ceiling(lb * mStride));
829            Value * const lowerboundStrides = b->CreateZExt(b->CreateICmpUGE(unprocessed, lowerbound), b->getSizeTy());
830            Value * const tryLowerbound = b->CreateICmpULT(accessibleStrides, lowerboundStrides);
831            inputStrideSize[i] = b->CreateSelect(tryLowerbound, lowerbound, inputStrideSize[i]);
832            accessibleStrides = b->CreateSelect(tryLowerbound, lowerboundStrides, accessibleStrides);
833        }
834
835        numOfStrides = b->CreateUMin(numOfStrides, accessibleStrides);
836    }
837
838    BasicBlock * const checkInputAvailability = b->CreateBasicBlock("CheckInputAvailability");
839    BasicBlock * const selectOutputBuffers = b->CreateBasicBlock("SelectOutputBuffers");
840    b->CreateLikelyCondBr(b->CreateICmpNE(numOfStrides, ZERO), selectOutputBuffers, checkInputAvailability);
841
842    // Ensure that everything between S⌈P/S⌉ and S⌈n*(P + L)/S⌉ is linearly available, where S is the stride size,
843    // P is the current processed position, L is the lookahead amount and n is our number of accessible strides ∈ â„€+.
844    b->SetInsertPoint(checkInputAvailability);
845    Value * linearlyCopyable[inputSetCount];
846    PHINode * selectedInputBuffer[inputSetCount];
847    for (unsigned i = 0; i < inputSetCount; i++) {
848        AllocaInst * const tempBuffer = temporaryInputBuffer[i];
849        selectedInputBuffer[i] = nullptr;
850        if (tempBuffer) {
851
852            const Binding & input = mStreamSetInputs[i];
853            const auto & name = input.getName();
854            Value * const processed = mInitialProcessedItemCount[i];
855            Value * const unprocessed = mAvailableItemCount[i];
856            Value * const accessible = linearlyAccessible[i];
857
858            BasicBlock * const entry = b->GetInsertBlock();
859
860            Value * strideSize = inputStrideSize[i];
861            if (LLVM_UNLIKELY(input.hasLookahead())) {
862                Constant * const lookahead = b->getSize(input.getLookahead());
863                strideSize = b->CreateAdd(strideSize, lookahead);
864            }
865
866            Value * const requiresCopy = b->CreateICmpULT(accessible, strideSize);
867
868            BasicBlock * const resume = b->CreateBasicBlock(name + "Resume");
869
870            BasicBlock * copyToBackEnd = NULL;
871            BasicBlock * copyToFrontEnd = NULL;
872            Value * isPartialStride = NULL;
873            Value * newAvailable = NULL;
874
875            if (input.isSwizzled()) {
876                // Copy at least one whole block for Swizzled input stream
877                BasicBlock * const copyFromBack = b->CreateBasicBlock(name + "CopyFromBack");
878                BasicBlock * const copyFromFront = b->CreateBasicBlock(name + "CopyFromFront");
879
880                b->CreateUnlikelyCondBr(requiresCopy, copyFromBack, resume);
881
882                b->SetInsertPoint(copyFromBack);
883
884
885                Value * const arraySize = b->CreateZExt(tempBuffer->getArraySize(), b->getInt64Ty());
886                Value * const temporarySize = b->CreateTrunc(b->CreateMul(arraySize, b->getInt64(mStride)), accessible->getType());
887
888                Value * const processedOffset = b->CreateAnd(processed, BLOCK_WIDTH_MASK);
889                Value * const copyable = b->CreateUMin(b->CreateAdd(unprocessed, processedOffset), temporarySize); // <- we only really need strideSize items
890                newAvailable = b->CreateSub(copyable, processedOffset);
891//                b->CallPrintInt("newAvailable", newAvailable);
892
893                Value * const bufferSize = b->CreateMul(ConstantExpr::getSizeOf(tempBuffer->getAllocatedType()), arraySize);
894                b->CreateMemZero(tempBuffer, bufferSize, blockAlignment);
895
896//                b->CallPrintInt("temporarySize", temporarySize);
897//                b->CallPrintInt("processed", processed);
898//                b->CallPrintInt("unprocessed", unprocessed);
899//                b->CallPrintInt("processedOffset", processedOffset);
900//                b->CallPrintInt("copyable", copyable);
901
902//                b->CallPrintInt("streamCpy1", b->getSize(0));
903                Value* BIT_BLOCK_WIDTH = b->getSize(b->getBitBlockWidth());
904
905                Value* copyAmount1 = b->CreateAdd(accessible, processedOffset);
906                Value* roundCopyAmount = b->CreateMul(b->CreateUDivCeil(copyAmount1, BIT_BLOCK_WIDTH), BIT_BLOCK_WIDTH);
907                b->CreateStreamCpy(name, tempBuffer, ZERO, mStreamSetInputBaseAddress[i], ZERO, roundCopyAmount, getItemAlignment(input));
908
909                copyToBackEnd = b->GetInsertBlock();
910
911                b->CreateCondBr(b->CreateICmpNE(copyable, b->CreateAdd(accessible, processedOffset)), copyFromFront, resume);
912
913                b->SetInsertPoint(copyFromFront);
914                Value * const remaining = b->CreateSub(copyable, b->CreateAdd(accessible, processedOffset));
915                Value * const baseAddress = b->getBaseAddress(name);
916//                b->CallPrintInt("streamCpy2", b->getSize(0));
917
918                auto castedTempBuffer = b->CreatePointerCast(tempBuffer, b->getBitBlockType()->getPointerTo());
919
920                auto p = b->CreateGEP(
921                        castedTempBuffer,
922                        b->CreateMul(
923                                b->CreateUDiv(b->CreateAdd(accessible, processedOffset), BIT_BLOCK_WIDTH),
924                                b->getSize(this->getAnyStreamSetBuffer(name)->getNumOfStreams())
925                        )
926                );
927//                b->CreateStreamCpy(name, tempBuffer, b->CreateAdd(accessible, processedOffset), baseAddress, ZERO, remaining, getItemAlignment(input));
928
929
930                b->CreateStreamCpy(name, p, ZERO, baseAddress, ZERO, b->CreateMul(b->CreateUDivCeil(remaining, BIT_BLOCK_WIDTH), BIT_BLOCK_WIDTH), getItemAlignment(input));
931                isPartialStride = b->CreateICmpUGE(copyable, strideSize);
932                copyToFrontEnd = b->GetInsertBlock();
933
934
935
936                b->CreateBr(resume);
937            } else {
938                BasicBlock * const copyFromBack = b->CreateBasicBlock(name + "CopyFromBack");
939                BasicBlock * const copyFromFront = b->CreateBasicBlock(name + "CopyFromFront");
940
941                b->CreateUnlikelyCondBr(requiresCopy, copyFromBack, resume);
942
943                b->SetInsertPoint(copyFromBack);
944                Value * const arraySize = b->CreateZExt(tempBuffer->getArraySize(), b->getInt64Ty());
945                Value * const temporarySize = b->CreateTrunc(b->CreateMul(arraySize, b->getInt64(mStride)), accessible->getType());
946                Value * const copyable = b->CreateUMin(unprocessed, temporarySize); // <- we only really need strideSize items
947                newAvailable = copyable;
948                Value * const offset = b->CreateAnd(processed, BLOCK_WIDTH_MASK);
949
950                Value * const bufferSize = b->CreateMul(ConstantExpr::getSizeOf(tempBuffer->getAllocatedType()), arraySize);
951                b->CreateMemZero(tempBuffer, bufferSize, blockAlignment);
952
953                b->CreateStreamCpy(name, tempBuffer, ZERO, mStreamSetInputBaseAddress[i], offset, accessible, getItemAlignment(input));
954//            b->CallPrintInt("gep", b->CreateGEP(mStreamSetInputBaseAddress[i], b->CreateUDiv(offset, b->getSize(this->getAnyStreamSetBuffer(name)->getNumOfStreams()))));
955//            b->CallPrintRegister(name + "_tempBuffer", b->CreateLoad(tempBuffer));
956                copyToBackEnd = b->GetInsertBlock();
957                b->CreateCondBr(b->CreateICmpNE(copyable, accessible), copyFromFront, resume);
958
959                b->SetInsertPoint(copyFromFront);
960                Value * const remaining = b->CreateSub(copyable, accessible);
961                Value * const baseAddress = b->getBaseAddress(name);
962                b->CreateStreamCpy(name, tempBuffer, accessible, baseAddress, ZERO, remaining, getItemAlignment(input));
963                isPartialStride = b->CreateICmpUGE(copyable, strideSize);
964                copyToFrontEnd = b->GetInsertBlock();
965                b->CreateBr(resume);
966            }
967
968            b->SetInsertPoint(resume);
969            PHINode * const address = b->CreatePHI(tempBuffer->getType(), 3);
970            address->addIncoming(mStreamSetInputBaseAddress[i], entry);
971            address->addIncoming(tempBuffer, copyToBackEnd);
972            address->addIncoming(tempBuffer, copyToFrontEnd);
973            selectedInputBuffer[i] = address;
974            PHINode * const available = b->CreatePHI(accessible->getType(), 3);
975            available->addIncoming(accessible, entry);
976            available->addIncoming(newAvailable, copyToBackEnd);
977            available->addIncoming(newAvailable, copyToFrontEnd);
978            linearlyCopyable[i] = available;
979            PHINode * const finalStride = b->CreatePHI(b->getInt1Ty(), 3);
980            finalStride->addIncoming(mIsFinal, entry);
981            finalStride->addIncoming(b->getTrue(), copyToBackEnd);
982            finalStride->addIncoming(isPartialStride, copyToFrontEnd);
983            mIsFinal = finalStride;
984            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
985                Value * const hasStride = b->CreateOr(initiallyFinal, b->CreateNot(finalStride));
986                b->CreateAssert(hasStride, getName() + ": " + name + " has insufficient input data for one stride");
987            }
988        }
989    }
990
991    BasicBlock * const endCheckInputAvailability = b->GetInsertBlock();
992    selectOutputBuffers->moveAfter(endCheckInputAvailability);
993    b->CreateBr(selectOutputBuffers);
994
995    b->SetInsertPoint(selectOutputBuffers);
996    PHINode * const final = b->CreatePHI(mIsFinal->getType(), 2);
997    final->addIncoming(b->getFalse(), segmentLoop);
998    final->addIncoming(mIsFinal, endCheckInputAvailability);
999    mIsFinal = final;
1000    for (unsigned i = 0; i < inputSetCount; i++) {
1001        if (selectedInputBuffer[i]) {
1002            PHINode * const address = b->CreatePHI(selectedInputBuffer[i]->getType(), 2);
1003            address->addIncoming(mStreamSetInputBaseAddress[i], segmentLoop);
1004            address->addIncoming(selectedInputBuffer[i], endCheckInputAvailability);
1005            mStreamSetInputBaseAddress[i] = address;
1006            PHINode * const accessible = b->CreatePHI(linearlyAccessible[i]->getType(), 2);
1007            accessible->addIncoming(linearlyAccessible[i], segmentLoop);
1008            accessible->addIncoming(linearlyCopyable[i], endCheckInputAvailability);
1009            linearlyAccessible[i] = accessible;
1010        }
1011    }
1012    PHINode * const strides = b->CreatePHI(numOfStrides->getType(), 2);
1013    strides->addIncoming(numOfStrides, segmentLoop);
1014    strides->addIncoming(ONE, endCheckInputAvailability);
1015    numOfStrides = strides;
1016
1017    // Now determine the linearly writeable strides
1018    Value * outputStrideSize[outputSetCount];
1019    Value * linearlyWritable[outputSetCount];
1020    mInitialProducedItemCount.resize(outputSetCount);
1021    mStreamSetOutputBaseAddress.resize(outputSetCount);
1022    for (unsigned i = 0; i < outputSetCount; i++) {
1023        const auto & output = mStreamSetOutputs[i];
1024        const auto & name = output.getName();
1025        Value * const produced = b->getProducedItemCount(name);
1026        #ifdef DEBUG_LOG
1027        b->CallPrintInt(getName() + "_" + name + "_produced0", produced);
1028        #endif
1029        Value * baseBuffer = b->getBlockAddress(name, b->CreateLShr(produced, LOG_2_BLOCK_WIDTH));
1030        mInitialProducedItemCount[i] = produced;
1031        mStreamSetOutputBaseAddress[i] = baseBuffer;
1032        linearlyWritable[i] = nullptr;
1033        // Is the number of linearly writable items sufficient for a stride?
1034        outputStrideSize[i] = getStrideSize(b, output.getRate());
1035        if (outputStrideSize[i]) {
1036            linearlyWritable[i] = b->getLinearlyWritableItems(name, produced);
1037            #ifdef DEBUG_LOG
1038            b->CallPrintInt(getName() + "_" + name + "_writable", linearlyWritable[i]);
1039            #endif
1040            Value * writableStrides = b->CreateUDiv(linearlyWritable[i], outputStrideSize[i]);
1041            numOfStrides = b->CreateUMin(numOfStrides, writableStrides);
1042            // Do we require a temporary buffer to write to?
1043            AllocaInst * const tempBuffer = temporaryOutputBuffer[i];
1044            if (tempBuffer) {
1045                assert (tempBuffer->getType() == baseBuffer->getType());
1046                BasicBlock * const entry = b->GetInsertBlock();
1047                BasicBlock * const prepareTempBuffer = b->CreateBasicBlock(name + "PrepareTempBuffer");
1048                BasicBlock * const resume = b->CreateBasicBlock(name + "Resume");
1049                Value * const requiresCopy = b->CreateICmpEQ(writableStrides, ZERO);
1050                b->CreateUnlikelyCondBr(requiresCopy, prepareTempBuffer, resume);
1051                // Clear the output buffer prior to using it
1052                b->SetInsertPoint(prepareTempBuffer);
1053                Value * const bufferSize = b->CreateMul(ConstantExpr::getSizeOf(tempBuffer->getAllocatedType()), tempBuffer->getArraySize());
1054                b->CreateMemZero(tempBuffer, bufferSize, blockAlignment);               
1055                b->CreateBr(resume);
1056                // Select the appropriate buffer / stride #
1057                b->SetInsertPoint(resume);
1058                PHINode * const phiBuffer = b->CreatePHI(baseBuffer->getType(), 3);
1059                phiBuffer->addIncoming(baseBuffer, entry);
1060                phiBuffer->addIncoming(tempBuffer, prepareTempBuffer);
1061                baseBuffer = phiBuffer;
1062                PHINode * const phiStrides = b->CreatePHI(b->getSizeTy(), 2);
1063                phiStrides->addIncoming(numOfStrides, entry);
1064                phiStrides->addIncoming(ONE, prepareTempBuffer);
1065                numOfStrides = phiStrides;
1066            }
1067            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1068                b->CreateAssert(numOfStrides, getName() + ": " + name + " has insufficient output space for one stride");
1069            }
1070        }
1071    }
1072
1073    // Update the locally available item count to reflect the current state
1074    for (unsigned i = 0; i < inputSetCount; i++) {
1075        const Binding & input = mStreamSetInputs[i];
1076        if (input.isDisableAvailableItemCountAdjustment()) {
1077            continue;
1078        }
1079
1080        if (input.getRate().isFixed() && input.nonDeferred()) {
1081            Value * const processable = b->CreateMul(numOfStrides, inputStrideSize[i]);
1082            linearlyAccessible[i] = b->CreateSelect(mIsFinal, linearlyAccessible[i], processable);
1083        }
1084        mAvailableItemCount[i] = linearlyAccessible[i];
1085        #ifdef DEBUG_LOG
1086        b->CallPrintInt(getName() + "_" + input.getName() + "_accessible", linearlyAccessible[i]);
1087        #endif
1088    }
1089
1090    //  We have one or more strides of input data and output buffer space for all stream sets.
1091    generateMultiBlockLogic(b, numOfStrides);
1092
1093    for (unsigned i = 0; i < inputSetCount; ++i) {
1094        const auto & input = mStreamSetInputs[i];
1095        const ProcessingRate & rate = input.getRate();
1096        if (rate.isFixed() && input.nonDeferred()) {
1097            Value * const ic = b->CreateAdd(mInitialProcessedItemCount[i], mAvailableItemCount[i]);
1098            b->setProcessedItemCount(input.getName(), ic);
1099        }
1100        #ifdef DEBUG_LOG
1101        b->CallPrintInt(getName() + "_" + input.getName() + "_processed", b->getProcessedItemCount(input.getName()));
1102        #endif
1103    }
1104
1105    for (unsigned i = 0; i < outputSetCount; ++i) {
1106        const auto & output = mStreamSetOutputs[i];
1107        const ProcessingRate & rate = output.getRate();
1108        if (rate.isFixed()) {
1109            Value * const produced = b->CreateMul(numOfStrides, outputStrideSize[i]);
1110            Value * const ic = b->CreateAdd(mInitialProducedItemCount[i], produced);
1111            b->setProducedItemCount(output.getName(), ic);
1112        }
1113        #ifdef DEBUG_LOG
1114        b->CallPrintInt(getName() + "_" + output.getName() + "_produced", b->getProducedItemCount(output.getName()));
1115        #endif
1116    }
1117
1118    BasicBlock * const handleFinalBlock = b->CreateBasicBlock("HandleFinalBlock");
1119    BasicBlock * const temporaryBufferCopyBack = b->CreateBasicBlock("TemporaryBufferCopyBack");
1120    BasicBlock * const strideDone = b->CreateBasicBlock("MultiBlockDone");
1121
1122    b->CreateUnlikelyCondBr(mIsFinal, handleFinalBlock, temporaryBufferCopyBack);
1123
1124
1125    /// FINAL STRIDE ADJUSTMENT
1126    b->SetInsertPoint(handleFinalBlock);
1127
1128    // If this is our final stride, adjust the Fixed output item counts. The main loop assumes that
1129    // the ITEM COUNT % FIXED RATE = 0 for all Fixed Input and Output streams. We correct that here
1130    // to calculate them based on the actual input item counts.
1131
1132    reviseFinalProducedItemCounts(b);
1133
1134    b->CreateBr(temporaryBufferCopyBack);
1135
1136    /// TEMPORARY BUFFER COPY BACK
1137    b->SetInsertPoint(temporaryBufferCopyBack);
1138
1139    // Copy back data to the actual output buffers.
1140    for (unsigned i = 0; i < outputSetCount; i++) {
1141        AllocaInst * const tempBuffer = temporaryOutputBuffer[i];
1142        if (LLVM_UNLIKELY(tempBuffer == nullptr)) {
1143            continue;
1144        }
1145        const auto & name = mStreamSetOutputs[i].getName();
1146        Value * const produced = b->getProducedItemCount(name);
1147        Value * const baseBuffer = mStreamSetOutputBaseAddress[i];
1148        assert ("stack corruption likely" && (tempBuffer->getType() == baseBuffer->getType()));
1149        //const auto & name = mStreamSetOutputs[i].getName();
1150        BasicBlock * const copyToBack = b->CreateBasicBlock(name + "CopyToBack");
1151        BasicBlock * const copyToFront = b->CreateBasicBlock(name + "CopyToFront");
1152        BasicBlock * const resume = b->CreateBasicBlock(name + "ResumeCopyBack");
1153        // If we used a temporary buffer, copy it back to the original output buffer
1154        Value * const requiresCopy = b->CreateICmpEQ(tempBuffer, baseBuffer);
1155        b->CreateCondBr(requiresCopy, copyToBack, resume);
1156
1157        b->SetInsertPoint(copyToBack);       
1158        Value * const offset = b->CreateAnd(mInitialProducedItemCount[i], BLOCK_WIDTH_MASK);
1159        //Value * const newProducedItemCount = b->getProducedItemCount(name);
1160        Value * const newlyProduced = b->CreateSub(produced, mInitialProducedItemCount[i]);
1161
1162
1163        Value * const toWrite = b->CreateUMin(newlyProduced, linearlyWritable[i]);
1164        const auto alignment = getItemAlignment(mStreamSetOutputs[i]);
1165        b->CreateStreamCpy(name, baseBuffer, offset, tempBuffer, ZERO, toWrite, alignment);
1166        // If we required a temporary output buffer, we will probably need to write to the beginning of the buffer as well.
1167        b->CreateLikelyCondBr(b->CreateICmpULT(toWrite, newlyProduced), copyToFront, resume);
1168
1169        b->SetInsertPoint(copyToFront);
1170        Value * const remaining = b->CreateSub(newlyProduced, toWrite);
1171        Value * const baseAddress = b->getBaseAddress(name);
1172        b->CreateStreamCpy(name, baseAddress, ZERO, tempBuffer, toWrite, remaining, alignment);
1173        b->CreateBr(resume);
1174
1175        b->SetInsertPoint(resume);
1176    }
1177
1178    //  We've dealt with the partial block processing and copied information back into the
1179    //  actual buffers.  If this isn't the final block, loop back for more multiblock processing.
1180    BasicBlock * const segmentDone = b->CreateBasicBlock("SegmentDone");
1181
1182    if (hasAttribute(Attribute::KindId::MustExplicitlyTerminate) || hasAttribute(Attribute::KindId::CanTerminateEarly)) {
1183        mIsFinal = b->CreateOr(mIsFinal, b->getTerminationSignal());
1184    }
1185
1186    b->CreateCondBr(mIsFinal, segmentDone, strideDone);
1187
1188    /// STRIDE DONE
1189    strideDone->moveAfter(b->GetInsertBlock());
1190    b->SetInsertPoint(strideDone);
1191
1192    // do we have enough data for another stride?
1193    Value * hasMoreStrides = b->getTrue();
1194    for (unsigned i = 0; i < inputSetCount; ++i) {
1195        const Binding & input = mStreamSetInputs[i];
1196        const auto & name = input.getName();
1197        Value * const avail = mInitialAvailableItemCount[i];
1198        Value * const processed = b->getProcessedItemCount(name);
1199//        b->CallPrintInt(getName() + "_" + name + "_processed'", processed);
1200
1201        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1202            b->CreateAssert(b->CreateICmpULE(processed, avail), getName() + ": " + name + " processed data exceeds available data");
1203        }
1204        Value * const remaining = b->CreateSub(avail, processed);
1205        Value * strideSize = inputStrideSize[i];
1206        if (LLVM_UNLIKELY(input.hasLookahead())) {
1207            strideSize = b->CreateAdd(strideSize, b->getSize(input.getLookahead()));
1208        }
1209        Value * const hasRemainingStrides = b->CreateICmpUGE(remaining, strideSize);
1210        hasMoreStrides = b->CreateAnd(hasMoreStrides, hasRemainingStrides);
1211    }
1212
1213    // even if we do not have enough input data for a full stride, if this is our final stride, allow it ...
1214    hasMoreStrides = b->CreateOr(hasMoreStrides, initiallyFinal);
1215
1216    // do we have enough room for another stride?
1217    for (unsigned i = 0; i < outputSetCount; ++i) {
1218        const ProcessingRate & rate = mStreamSetOutputs[i].getRate();
1219        const auto & name = mStreamSetOutputs[i].getName();
1220        Value * const produced = b->getProducedItemCount(name);
1221
1222        // If this output has a Fixed/Bounded rate, determine whether we have room for another stride.
1223        if (LLVM_LIKELY(outputStrideSize[i] != nullptr)) {
1224            Value * const consumed = b->getConsumedItemCount(name);
1225            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1226                b->CreateAssert(b->CreateICmpULE(consumed, produced),
1227                                getName() + ": " + name + " consumed data exceeds produced data");
1228            }
1229            Value * const unconsumed = b->CreateSub(produced, consumed);
1230
1231//            b->CallPrintInt(getName() + "_" + name + "_unconsumed", unconsumed);
1232
1233            Value * const capacity = b->getBufferedSize(name);
1234
1235//            b->CallPrintInt(getName() + "_" + name + "_capacity", capacity);
1236
1237            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1238                b->CreateAssert(b->CreateICmpULE(unconsumed, capacity),
1239                                getName() + ": " + name + " more data was written than its capacity allows");
1240            }
1241
1242
1243
1244            Value * const remaining = b->CreateSub(capacity, unconsumed);
1245            Value * const hasRemainingStrides = b->CreateICmpUGE(remaining, outputStrideSize[i]);
1246            hasMoreStrides = b->CreateAnd(hasMoreStrides, hasRemainingStrides);
1247        }
1248        // Do copybacks if necessary.
1249        if (mStreamSetOutputBuffers[i]->supportsCopyBack() && requiresCopyBack(rate)) {
1250            BasicBlock * const copyBack = b->CreateBasicBlock(name + "CopyBack");
1251            BasicBlock * const done = b->CreateBasicBlock(name + "CopyBackDone");
1252
1253            Value * const bufferSize = b->getBufferedSize(name);
1254            Value * const prior = b->CreateURem(mInitialProducedItemCount[i], bufferSize);
1255            Value * const current = b->CreateURem(produced, bufferSize);
1256            b->CreateUnlikelyCondBr(b->CreateICmpUGT(prior, current), copyBack, done);
1257
1258            b->SetInsertPoint(copyBack);
1259            const auto copyAlignment = getItemAlignment(mStreamSetOutputs[i]);
1260            Value * const startOfBuffer = b->getBaseAddress(name);
1261            Value * const offset = b->CreateUDiv(bufferSize, b->getSize(b->getBitBlockWidth()));
1262            Value * const endOfBuffer = b->CreateGEP(startOfBuffer, offset);
1263            b->CreateStreamCpy(name, startOfBuffer, ZERO, endOfBuffer, ZERO, current, copyAlignment);
1264            b->CreateBr(done);
1265
1266            b->SetInsertPoint(done);
1267        }
1268    }
1269
1270    b->CreateCondBr(hasMoreStrides, segmentLoop, segmentDone);
1271
1272    /// SEGMENT DONE
1273    segmentDone->moveAfter(b->GetInsertBlock());
1274    b->SetInsertPoint(segmentDone);
1275
1276}
1277
1278/** ------------------------------------------------------------------------------------------------------------- *
1279 * @brief requiresCopyBack
1280 ** ------------------------------------------------------------------------------------------------------------- */
1281bool MultiBlockKernel::requiresCopyBack(const ProcessingRate & rate) const {
1282    if (rate.isBounded() || rate.isUnknown()) {
1283        return true;
1284    } else if (rate.isRelative()) {
1285        return requiresCopyBack(getBinding(rate.getReference()).getRate());
1286    }
1287    return false;
1288}
1289
1290/** ------------------------------------------------------------------------------------------------------------- *
1291 * @brief CreateUDivCeil
1292 ** ------------------------------------------------------------------------------------------------------------- */
1293inline Value * CreateUDivCeil(const std::unique_ptr<KernelBuilder> & b, Value * const number, const ProcessingRate::RateValue divisor, const Twine & Name = "") {
1294    Constant * const n = ConstantInt::get(number->getType(), divisor.numerator());
1295    if (LLVM_LIKELY(divisor.denominator() == 1)) {
1296        return b->CreateUDivCeil(number, n, Name);
1297    } else {
1298        //   âŒŠ(num + ratio - 1) / ratio⌋
1299        // = ⌊(num - 1) / (n/d)⌋ + (ratio/ratio)
1300        // = ⌊(d * (num - 1)) / n⌋ + 1
1301        Constant * const ONE = ConstantInt::get(number->getType(), 1);
1302        Constant * const d = ConstantInt::get(number->getType(), divisor.denominator());
1303        return b->CreateAdd(b->CreateUDiv(b->CreateMul(b->CreateSub(number, ONE), d), n), ONE, Name);
1304    }
1305}
1306
1307
1308/** ------------------------------------------------------------------------------------------------------------- *
1309 * @brief reviseFinalProducedItemCounts
1310 ** ------------------------------------------------------------------------------------------------------------- */
1311void MultiBlockKernel::reviseFinalProducedItemCounts(const std::unique_ptr<KernelBuilder> & b) {
1312
1313    if (LLVM_UNLIKELY(mStreamSetInputs.empty())) {
1314        return;
1315    }
1316
1317    const auto inputSetCount = mStreamSetInputs.size();
1318
1319    ProcessingRate::RateValue rateLCM(1);
1320    unsigned first = 0;
1321    unsigned last = inputSetCount;
1322
1323    bool hasFixedRateInput = false; // <- temporary workaround
1324    for (unsigned i = 0; i < inputSetCount; ++i) {
1325        const ProcessingRate & pr = mStreamSetInputs[i].getRate();
1326        if (pr.isFixed()) {
1327            rateLCM = lcm(rateLCM, pr.getRate());
1328            hasFixedRateInput = true;
1329            if (mStreamSetInputs[i].isPrincipal()) {
1330                assert ("A kernel cannot have multiple principle input streams" && (first == 0 && last == inputSetCount));
1331                first = i;
1332                last = i + 1;
1333            }
1334        }       
1335    }
1336
1337    bool noFixedRateOutput = true;
1338
1339    for (const Binding & output : mStreamSetOutputs) {
1340        const ProcessingRate & pr = output.getRate();
1341        if (pr.isFixed()) {
1342            rateLCM = lcm(rateLCM, pr.getRate());
1343            noFixedRateOutput = false;
1344        }
1345    }
1346
1347    if (noFixedRateOutput) {
1348        return;
1349    }
1350
1351    Value * baseInitialProcessedItemCount = nullptr;
1352    Value * scaledInverseOfAvailItemCount = nullptr;
1353
1354    // For each Fixed output stream, this calculates:
1355
1356    //    CEILING(MIN(Available Item Count / Fixed Input Rate) * Fixed Output Rate)
1357
1358    // But avoids the possibility of overflow errors (assuming that each processed item count does not overflow)
1359
1360    for (unsigned i = first; i < last; ++i) {
1361        const ProcessingRate & pr = mStreamSetInputs[i].getRate();
1362        if (pr.isFixed()) {
1363            Value * p = mInitialProcessedItemCount[i];
1364            Value * a = b->CreateSub(mInitialAvailableItemCount[i], p);
1365            const auto & rate = pr.getRate();
1366            if (LLVM_UNLIKELY(rateLCM != rate)) {
1367                const auto factor = rateLCM / rate;
1368                if (LLVM_UNLIKELY(factor.numerator() > 1)) {
1369                    a = b->CreateMul(a, b->getSize(factor.numerator()));
1370                }
1371                if (LLVM_UNLIKELY(factor.denominator() > 1)) {
1372                    a = b->CreateUDiv(a, b->getSize(factor.denominator()));
1373                }
1374            }
1375            if (LLVM_UNLIKELY(rate.denominator() > 1)) {
1376                p = b->CreateMul(p, b->getSize(rate.denominator()));
1377            }
1378            if (LLVM_UNLIKELY(rate.numerator() > 1)) {
1379                p = b->CreateUDiv(p, b->getSize(rate.numerator()));
1380            }
1381            if (scaledInverseOfAvailItemCount) {
1382                scaledInverseOfAvailItemCount = b->CreateUMin(scaledInverseOfAvailItemCount, a);
1383                baseInitialProcessedItemCount = b->CreateUMin(baseInitialProcessedItemCount, p);
1384            } else {
1385                scaledInverseOfAvailItemCount = a;
1386                baseInitialProcessedItemCount = p;
1387            }
1388        }
1389    }
1390
1391    for (const Binding & output : mStreamSetOutputs) {
1392        const auto name = output.getName();
1393        const ProcessingRate & pr = output.getRate();
1394        Value * produced = nullptr;
1395        if (hasFixedRateInput && pr.isFixed() && output.nonDeferred()) {
1396            assert (baseInitialProcessedItemCount && scaledInverseOfAvailItemCount);
1397            const auto rate = pr.getRate();
1398            Value * p = baseInitialProcessedItemCount;
1399            if (LLVM_UNLIKELY(rate.numerator() != 1)) {
1400                p = b->CreateMul(p, b->getSize(rate.numerator()));
1401            }
1402            if (LLVM_UNLIKELY(rate.denominator() != 1)) {
1403                p = b->CreateUDiv(p, b->getSize(rate.denominator()));
1404            }
1405            Value * const ic = CreateUDivCeil(b, scaledInverseOfAvailItemCount, rateLCM / pr.getRate());
1406            produced = b->CreateAdd(p, ic);
1407            #ifdef DEBUG_LOG
1408            b->CallPrintInt(getName() + "_" + name + "_produced'", produced);
1409            #endif           
1410        } else { // check if we have an attribute; if so, get the current produced count and adjust it
1411            bool noAttributes = true;
1412            for (const Attribute & attr : output.getAttributes()) {
1413                if (attr.isAdd() || attr.isRoundUpTo()) {
1414                    noAttributes = false;
1415                    break;
1416                }
1417            }
1418            if (noAttributes) {
1419                continue;
1420            }
1421            produced = b->getProducedItemCount(name);
1422        }
1423        for (const Attribute & attr : output.getAttributes()) {
1424            if (attr.isAdd()) {
1425                produced = b->CreateAdd(produced, b->getSize(attr.amount()));
1426            } else if (attr.isRoundUpTo()) {
1427                produced = b->CreateRoundUp(produced, b->getSize(attr.amount()));
1428            }
1429        }
1430        #ifdef DEBUG_LOG
1431        b->CallPrintInt(getName() + "_" + name + "_produced\"", produced);
1432        #endif
1433        b->setProducedItemCount(name, produced);
1434    }
1435
1436}
1437
1438/** ------------------------------------------------------------------------------------------------------------- *
1439 * @brief generateMultiBlockLogic
1440 ** ------------------------------------------------------------------------------------------------------------- */
1441void BlockOrientedKernel::generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> & b, Value * const numOfBlocks) {
1442
1443    if (LLVM_UNLIKELY(mStride != b->getBitBlockWidth())) {
1444        report_fatal_error(getName() + ": the Stride (" + std::to_string(mStride) + ") of BlockOrientedKernel "
1445                           "equal to the BitBlockWidth (" + std::to_string(b->getBitBlockWidth()) + ")");
1446    }
1447
1448    Constant * const LOG_2_BLOCK_WIDTH = b->getSize(std::log2(b->getBitBlockWidth()));
1449
1450    BasicBlock * const entryBlock = b->GetInsertBlock();
1451    mStrideLoopBody = b->CreateBasicBlock(getName() + "_strideLoopBody");
1452    BasicBlock * const stridesDone = b->CreateBasicBlock(getName() + "_stridesDone");
1453    BasicBlock * const doFinalBlock = b->CreateBasicBlock(getName() + "_doFinalBlock");
1454    BasicBlock * const segmentDone = b->CreateBasicBlock(getName() + "_segmentDone");
1455
1456    const auto inputSetCount = mStreamSetInputs.size();
1457    Value * baseProcessedIndex[inputSetCount];
1458    Value * baseInputAddress[inputSetCount];
1459    for (unsigned i = 0; i < inputSetCount; i++) {
1460        const ProcessingRate & rate = mStreamSetInputs[i].getRate();
1461        if (LLVM_UNLIKELY(!rate.isFixed())) {
1462            Value * const ic = mInitialProcessedItemCount[i];
1463            baseProcessedIndex[i] = b->CreateLShr(ic, LOG_2_BLOCK_WIDTH);
1464        }
1465        baseInputAddress[i] = mStreamSetInputBaseAddress[i];
1466    }
1467
1468    const auto outputSetCount = mStreamSetOutputs.size();
1469    Value * baseProducedIndex[outputSetCount];
1470    Value * baseOutputAddress[inputSetCount];
1471    for (unsigned i = 0; i < outputSetCount; i++) {
1472        const ProcessingRate & rate = mStreamSetOutputs[i].getRate();
1473        if (LLVM_UNLIKELY(!rate.isFixed())) {
1474            Value * const ic = b->getProducedItemCount(mStreamSetOutputs[i].getName());
1475            baseProducedIndex[i] = b->CreateLShr(ic, LOG_2_BLOCK_WIDTH);
1476        }
1477        baseOutputAddress[i] = mStreamSetOutputBaseAddress[i];
1478    }
1479
1480    b->CreateUnlikelyCondBr(mIsFinal, doFinalBlock, mStrideLoopBody);
1481
1482    /// BLOCK BODY
1483
1484    b->SetInsertPoint(mStrideLoopBody);
1485
1486    if (b->supportsIndirectBr()) {
1487        Value * const baseTarget = BlockAddress::get(segmentDone);
1488        mStrideLoopTarget = b->CreatePHI(baseTarget->getType(), 2, "strideTarget");
1489        mStrideLoopTarget->addIncoming(baseTarget, entryBlock);
1490    }
1491
1492    mStrideBlockIndex = b->CreatePHI(b->getSizeTy(), 2);
1493    mStrideBlockIndex->addIncoming(b->getSize(0), entryBlock);
1494
1495    /// GENERATE DO BLOCK METHOD
1496
1497    for (unsigned i = 0; i < inputSetCount; ++i) {
1498        Value * index = mStrideBlockIndex;
1499        const ProcessingRate & rate = mStreamSetInputs[i].getRate();
1500        if (LLVM_UNLIKELY(!rate.isFixed())) {
1501            Value * ic = b->getProcessedItemCount(mStreamSetInputs[i].getName());
1502            index = b->CreateSub(b->CreateLShr(ic, LOG_2_BLOCK_WIDTH), baseProcessedIndex[i]);
1503        }
1504        mStreamSetInputBaseAddress[i] = b->CreateGEP(mStreamSetInputBaseAddress[i], index);
1505    }
1506
1507    for (unsigned i = 0; i < outputSetCount; ++i) {
1508        Value * index = mStrideBlockIndex;
1509        const ProcessingRate & rate = mStreamSetOutputs[i].getRate();
1510        if (LLVM_UNLIKELY(!rate.isFixed())) {
1511            Value * ic = b->getProducedItemCount(mStreamSetOutputs[i].getName());
1512            index = b->CreateSub(b->CreateLShr(ic, LOG_2_BLOCK_WIDTH), baseProducedIndex[i]);
1513        }
1514        mStreamSetOutputBaseAddress[i] = b->CreateGEP(mStreamSetOutputBaseAddress[i], index);
1515    }
1516
1517    writeDoBlockMethod(b);
1518
1519    BasicBlock * const bodyEnd = b->GetInsertBlock();
1520    if (mStrideLoopTarget) {
1521        mStrideLoopTarget->addIncoming(mStrideLoopTarget, bodyEnd);
1522    }
1523
1524    Value * const nextIndex = b->CreateAdd(mStrideBlockIndex, b->getSize(1));
1525    mStrideBlockIndex->addIncoming(nextIndex, bodyEnd);
1526    Value * const notDone = b->CreateICmpULT(nextIndex, numOfBlocks);
1527    b->CreateCondBr(notDone, mStrideLoopBody, stridesDone);
1528
1529    stridesDone->moveAfter(bodyEnd);
1530
1531    /// STRIDE DONE
1532
1533    b->SetInsertPoint(stridesDone);
1534
1535    // Now conditionally perform the final block processing depending on the doFinal parameter.
1536    if (mStrideLoopTarget) {
1537        mStrideLoopBranch = b->CreateIndirectBr(mStrideLoopTarget, 3);
1538        mStrideLoopBranch->addDestination(doFinalBlock);
1539        mStrideLoopBranch->addDestination(segmentDone);
1540    } else {
1541        b->CreateUnlikelyCondBr(mIsFinal, doFinalBlock, segmentDone);
1542    }
1543
1544    doFinalBlock->moveAfter(stridesDone);
1545
1546    /// DO FINAL BLOCK
1547
1548    b->SetInsertPoint(doFinalBlock);
1549    for (unsigned i = 0; i < inputSetCount; ++i) {
1550        mStreamSetInputBaseAddress[i] = baseInputAddress[i];
1551    }
1552
1553    for (unsigned i = 0; i < outputSetCount; ++i) {
1554        mStreamSetOutputBaseAddress[i] = baseOutputAddress[i];
1555    }
1556
1557    writeFinalBlockMethod(b, getRemainingItems(b));
1558
1559    b->CreateBr(segmentDone);
1560
1561    segmentDone->moveAfter(b->GetInsertBlock());
1562
1563    b->SetInsertPoint(segmentDone);
1564
1565    // Update the branch prediction metadata to indicate that the likely target will be segmentDone
1566    if (mStrideLoopTarget) {
1567        MDBuilder mdb(b->getContext());
1568        const auto destinations = mStrideLoopBranch->getNumDestinations();
1569        uint32_t weights[destinations];
1570        for (unsigned i = 0; i < destinations; ++i) {
1571            weights[i] = (mStrideLoopBranch->getDestination(i) == segmentDone) ? 100 : 1;
1572        }
1573        ArrayRef<uint32_t> bw(weights, destinations);
1574        mStrideLoopBranch->setMetadata(LLVMContext::MD_prof, mdb.createBranchWeights(bw));
1575    }
1576
1577}
1578
1579/** ------------------------------------------------------------------------------------------------------------- *
1580 * @brief getRemainingItems
1581 ** ------------------------------------------------------------------------------------------------------------- */
1582Value * BlockOrientedKernel::getRemainingItems(const std::unique_ptr<KernelBuilder> & b) {
1583    Value * remainingItems = nullptr;
1584    const auto count = mStreamSetInputs.size();
1585    if (count == 1) {
1586        return mAvailableItemCount[0];
1587    } else {
1588        for (unsigned i = 0; i < count; i++) {
1589            if (mStreamSetInputs[i].isPrincipal()) {
1590                return mAvailableItemCount[i];
1591            }
1592        }
1593        for (unsigned i = 0; i < count; ++i) {
1594            const ProcessingRate & r = mStreamSetInputs[i].getRate();
1595            if (r.isFixed()) {
1596                Value * ic = CreateUDivCeil(b, mAvailableItemCount[i], r.getRate());
1597                if (remainingItems) {
1598                    remainingItems = b->CreateUMin(remainingItems, ic);
1599                } else {
1600                    remainingItems = ic;
1601                }
1602            }
1603        }
1604    }
1605    return remainingItems;
1606}
1607
1608/** ------------------------------------------------------------------------------------------------------------- *
1609 * @brief writeDoBlockMethod
1610 ** ------------------------------------------------------------------------------------------------------------- */
1611inline void BlockOrientedKernel::writeDoBlockMethod(const std::unique_ptr<KernelBuilder> & b) {
1612
1613    Value * const self = getInstance();
1614    Function * const cp = mCurrentMethod;
1615    auto ip = b->saveIP();
1616    std::vector<Value *> availableItemCount(0);
1617
1618    /// Check if the do block method is called and create the function if necessary
1619    if (!b->supportsIndirectBr()) {
1620
1621        std::vector<Type *> params;
1622        params.reserve(1 + mAvailableItemCount.size());
1623        params.push_back(self->getType());
1624        for (Value * avail : mAvailableItemCount) {
1625            params.push_back(avail->getType());
1626        }
1627
1628        FunctionType * const type = FunctionType::get(b->getVoidTy(), params, false);
1629        mCurrentMethod = Function::Create(type, GlobalValue::InternalLinkage, getName() + DO_BLOCK_SUFFIX, b->getModule());
1630        mCurrentMethod->setCallingConv(CallingConv::C);
1631        mCurrentMethod->setDoesNotThrow();
1632        auto args = mCurrentMethod->arg_begin();
1633        args->setName("self");
1634        setInstance(&*args);
1635        availableItemCount.reserve(mAvailableItemCount.size());
1636        while (++args != mCurrentMethod->arg_end()) {
1637            availableItemCount.push_back(&*args);
1638        }
1639        assert (availableItemCount.size() == mAvailableItemCount.size());
1640        mAvailableItemCount.swap(availableItemCount);
1641        b->SetInsertPoint(BasicBlock::Create(b->getContext(), "entry", mCurrentMethod));
1642    }
1643
1644    generateDoBlockMethod(b); // must be implemented by the BlockOrientedKernelBuilder subtype
1645
1646    if (!b->supportsIndirectBr()) {
1647        // Restore the DoSegment function state then call the DoBlock method
1648        b->CreateRetVoid();
1649        mDoBlockMethod = mCurrentMethod;
1650        b->restoreIP(ip);
1651        setInstance(self);
1652        mCurrentMethod = cp;
1653        mAvailableItemCount.swap(availableItemCount);
1654        CreateDoBlockMethodCall(b);
1655    }
1656
1657}
1658
1659/** ------------------------------------------------------------------------------------------------------------- *
1660 * @brief writeFinalBlockMethod
1661 ** ------------------------------------------------------------------------------------------------------------- */
1662inline void BlockOrientedKernel::writeFinalBlockMethod(const std::unique_ptr<KernelBuilder> & b, Value * remainingItems) {
1663
1664    Value * const self = getInstance();
1665    Function * const cp = mCurrentMethod;
1666    Value * const remainingItemCount = remainingItems;
1667    auto ip = b->saveIP();
1668    std::vector<Value *> availableItemCount(0);
1669
1670    if (!b->supportsIndirectBr()) {
1671        std::vector<Type *> params;
1672        params.reserve(2 + mAvailableItemCount.size());
1673        params.push_back(self->getType());
1674        params.push_back(b->getSizeTy());
1675        for (Value * avail : mAvailableItemCount) {
1676            params.push_back(avail->getType());
1677        }
1678        FunctionType * const type = FunctionType::get(b->getVoidTy(), params, false);
1679        mCurrentMethod = Function::Create(type, GlobalValue::InternalLinkage, getName() + FINAL_BLOCK_SUFFIX, b->getModule());
1680        mCurrentMethod->setCallingConv(CallingConv::C);
1681        mCurrentMethod->setDoesNotThrow();
1682        auto args = mCurrentMethod->arg_begin();
1683        args->setName("self");
1684        setInstance(&*args);
1685        remainingItems = &*(++args);
1686        remainingItems->setName("remainingItems");
1687        availableItemCount.reserve(mAvailableItemCount.size());
1688        while (++args != mCurrentMethod->arg_end()) {
1689            availableItemCount.push_back(&*args);
1690        }
1691        assert (availableItemCount.size() == mAvailableItemCount.size());
1692        mAvailableItemCount.swap(availableItemCount);
1693        b->SetInsertPoint(BasicBlock::Create(b->getContext(), "entry", mCurrentMethod));
1694    }
1695
1696    #ifdef DEBUG_LOG
1697    b->CallPrintInt(getName() + "_remainingItems", remainingItems);
1698    #endif
1699    generateFinalBlockMethod(b, remainingItems); // may be implemented by the BlockOrientedKernel subtype
1700
1701    if (!b->supportsIndirectBr()) {
1702        b->CreateRetVoid();
1703        b->restoreIP(ip);
1704        setInstance(self);
1705        mAvailableItemCount.swap(availableItemCount);
1706        // Restore the DoSegment function state then call the DoFinal method
1707        std::vector<Value *> args;
1708        args.reserve(2 + mAvailableItemCount.size());
1709        args.push_back(self);
1710        args.push_back(remainingItemCount);
1711        args.insert(args.end(), mAvailableItemCount.begin(), mAvailableItemCount.end());
1712        b->CreateCall(mCurrentMethod, args);
1713        mCurrentMethod = cp;
1714    }
1715
1716}
1717
1718/** ------------------------------------------------------------------------------------------------------------- *
1719 * @brief generateFinalBlockMethod
1720 ** ------------------------------------------------------------------------------------------------------------- */
1721void BlockOrientedKernel::generateFinalBlockMethod(const std::unique_ptr<KernelBuilder> & b, Value * /* remainingItems */) {
1722    //  The default finalBlock method simply dispatches to the doBlock routine.
1723    CreateDoBlockMethodCall(b);
1724}
1725
1726void BlockOrientedKernel::CreateDoBlockMethodCall(const std::unique_ptr<KernelBuilder> & b) {
1727    if (b->supportsIndirectBr()) {
1728        BasicBlock * const bb = b->CreateBasicBlock("resume");
1729        mStrideLoopBranch->addDestination(bb);
1730        BasicBlock * const current = b->GetInsertBlock();
1731        mStrideLoopTarget->addIncoming(BlockAddress::get(bb), current);
1732        mStrideBlockIndex->addIncoming(b->getSize(0), current);
1733        b->CreateBr(mStrideLoopBody);
1734        bb->moveAfter(current);
1735        b->SetInsertPoint(bb);
1736    } else {
1737        std::vector<Value *> args;
1738        args.reserve(1 + mAvailableItemCount.size());
1739        args.push_back(getInstance());
1740        args.insert(args.end(), mAvailableItemCount.begin(), mAvailableItemCount.end());
1741        b->CreateCall(mDoBlockMethod, args);
1742    }
1743}
1744
1745static inline std::string annotateKernelNameWithDebugFlags(std::string && name) {
1746    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1747        name += "_EA";
1748    }
1749    name += "_O" + std::to_string((int)codegen::OptLevel);
1750    return name;
1751}
1752
1753// CONSTRUCTOR
1754Kernel::Kernel(std::string && kernelName,
1755               Bindings && stream_inputs,
1756               Bindings && stream_outputs,
1757               Bindings && scalar_parameters,
1758               Bindings && scalar_outputs,
1759               Bindings && internal_scalars)
1760: KernelInterface(annotateKernelNameWithDebugFlags(std::move(kernelName))
1761                  , std::move(stream_inputs), std::move(stream_outputs)
1762                  , std::move(scalar_parameters), std::move(scalar_outputs)
1763                  , std::move(internal_scalars))
1764, mCurrentMethod(nullptr)
1765, mAvailablePrincipalItemCount(nullptr)
1766, mStride(0)
1767, mIsFinal(nullptr)
1768, mOutputScalarResult(nullptr)
1769, mIsGenerated(false) {
1770
1771}
1772
1773Kernel::~Kernel() {
1774
1775}
1776
1777// MULTI-BLOCK KERNEL CONSTRUCTOR
1778MultiBlockKernel::MultiBlockKernel(std::string && kernelName,
1779                                   Bindings && stream_inputs,
1780                                   Bindings && stream_outputs,
1781                                   Bindings && scalar_parameters,
1782                                   Bindings && scalar_outputs,
1783                                   Bindings && internal_scalars)
1784: Kernel(std::move(kernelName), std::move(stream_inputs), std::move(stream_outputs), std::move(scalar_parameters), std::move(scalar_outputs), std::move(internal_scalars)) {
1785
1786}
1787
1788// CONSTRUCTOR
1789BlockOrientedKernel::BlockOrientedKernel(std::string && kernelName,
1790                                         Bindings && stream_inputs,
1791                                         Bindings && stream_outputs,
1792                                         Bindings && scalar_parameters,
1793                                         Bindings && scalar_outputs,
1794                                         Bindings && internal_scalars)
1795: MultiBlockKernel(std::move(kernelName), std::move(stream_inputs), std::move(stream_outputs), std::move(scalar_parameters), std::move(scalar_outputs), std::move(internal_scalars))
1796, mDoBlockMethod(nullptr)
1797, mStrideLoopBody(nullptr)
1798, mStrideLoopBranch(nullptr)
1799, mStrideLoopTarget(nullptr)
1800, mStrideBlockIndex(nullptr) {
1801
1802}
1803
1804// CONSTRUCTOR
1805SegmentOrientedKernel::SegmentOrientedKernel(std::string && kernelName,
1806                                             Bindings && stream_inputs,
1807                                             Bindings && stream_outputs,
1808                                             Bindings && scalar_parameters,
1809                                             Bindings && scalar_outputs,
1810                                             Bindings && internal_scalars)
1811: Kernel(std::move(kernelName), std::move(stream_inputs), std::move(stream_outputs), std::move(scalar_parameters), std::move(scalar_outputs), std::move(internal_scalars)) {
1812
1813}
1814
1815
1816}
Note: See TracBrowser for help on using the repository browser.