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

Last change on this file since 5967 was 5967, checked in by nmedfort, 12 months ago

Updated LZ4SwizzledMatchCopy + minor changes

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