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

Last change on this file since 5646 was 5646, checked in by nmedfort, 21 months ago

Minor clean up. Bug fix for object cache when the same cached kernel is used twice in a single run. Improvement to RE Minimizer.

File size: 61.8 KB
Line 
1/*
2 *  Copyright (c) 2016-7 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#include <llvm/Bitcode/ReaderWriter.h>
16#include <llvm/Transforms/Utils/Local.h>
17#include <kernels/streamset.h>
18#include <sstream>
19#include <kernels/kernel_builder.h>
20#include <llvm/Support/Debug.h>
21
22using namespace llvm;
23using namespace parabix;
24
25namespace kernel {
26
27const std::string Kernel::DO_BLOCK_SUFFIX = "_DoBlock";
28const std::string Kernel::FINAL_BLOCK_SUFFIX = "_FinalBlock";
29const std::string Kernel::MULTI_BLOCK_SUFFIX = "_MultiBlock";
30const std::string Kernel::LOGICAL_SEGMENT_NO_SCALAR = "logicalSegNo";
31const std::string Kernel::PROCESSED_ITEM_COUNT_SUFFIX = "_processedItemCount";
32const std::string Kernel::CONSUMED_ITEM_COUNT_SUFFIX = "_consumedItemCount";
33const std::string Kernel::PRODUCED_ITEM_COUNT_SUFFIX = "_producedItemCount";
34const std::string Kernel::TERMINATION_SIGNAL = "terminationSignal";
35const std::string Kernel::BUFFER_PTR_SUFFIX = "_bufferPtr";
36const std::string Kernel::CONSUMER_SUFFIX = "_consumerLocks";
37const std::string Kernel::CYCLECOUNT_SCALAR = "CPUcycles";
38
39unsigned Kernel::addScalar(Type * const type, const std::string & name) {
40    if (LLVM_UNLIKELY(mKernelStateType != nullptr)) {
41        report_fatal_error("Cannot add field " + name + " to " + getName() + " after kernel state finalized");
42    }
43    if (LLVM_UNLIKELY(mKernelMap.count(name))) {
44        report_fatal_error(getName() + " already contains scalar field " + name);
45    }
46    const auto index = mKernelFields.size();
47    mKernelMap.emplace(name, index);
48    mKernelFields.push_back(type);
49    return index;
50}
51
52unsigned Kernel::addUnnamedScalar(Type * const type) {
53    if (LLVM_UNLIKELY(mKernelStateType != nullptr)) {
54        report_fatal_error("Cannot add unnamed field  to " + getName() + " after kernel state finalized");
55    }
56    const auto index = mKernelFields.size();
57    mKernelFields.push_back(type);
58    return index;
59}
60
61void Kernel::prepareStreamSetNameMap() {
62    for (unsigned i = 0; i < mStreamSetInputs.size(); i++) {
63        mStreamMap.emplace(mStreamSetInputs[i].name, std::make_pair(Port::Input, i));
64    }
65    for (unsigned i = 0; i < mStreamSetOutputs.size(); i++) {
66        mStreamMap.emplace(mStreamSetOutputs[i].name, std::make_pair(Port::Output, i));
67    }
68}
69
70void Kernel::bindPorts(const StreamSetBuffers & inputs, const StreamSetBuffers & outputs) {
71    assert (mModule == nullptr);
72    assert (mStreamSetInputBuffers.empty());
73    assert (mStreamSetOutputBuffers.empty());
74
75    if (LLVM_UNLIKELY(mStreamSetInputs.size() != inputs.size())) {
76        report_fatal_error(getName() + ": expected " + std::to_string(mStreamSetInputs.size()) +
77                           " input stream sets but was given "
78                           + std::to_string(inputs.size()));
79    }
80
81    for (unsigned i = 0; i < inputs.size(); ++i) {
82        StreamSetBuffer * const buf = inputs[i];
83        if (LLVM_UNLIKELY(buf == nullptr)) {
84            report_fatal_error(getName() + ": input stream set " + std::to_string(i)
85                               + " cannot be null");
86        }
87        buf->addConsumer(this);
88    }
89
90    if (LLVM_UNLIKELY(mStreamSetOutputs.size() != outputs.size())) {
91        report_fatal_error(getName() + ": expected " + std::to_string(mStreamSetOutputs.size())
92                           + " output stream sets but was given "
93                           + std::to_string(outputs.size()));
94    }
95
96    for (unsigned i = 0; i < outputs.size(); ++i) {
97        StreamSetBuffer * const buf = outputs[i];
98        if (LLVM_UNLIKELY(buf == nullptr)) {
99            report_fatal_error(getName() + ": output stream set " + std::to_string(i) + " cannot be null");
100        }
101        if (LLVM_LIKELY(buf->getProducer() == nullptr)) {
102            buf->setProducer(this);
103        } else {
104            report_fatal_error(getName() + ": output stream set " + std::to_string(i)
105                               + " is already produced by kernel " + buf->getProducer()->getName());
106        }
107    }
108
109    mStreamSetInputBuffers.assign(inputs.begin(), inputs.end());
110    mStreamSetOutputBuffers.assign(outputs.begin(), outputs.end());
111}
112
113std::string Kernel::getCacheName(const std::unique_ptr<KernelBuilder> & idb) const {
114    std::stringstream cacheName;
115    cacheName << getName() << '_' << idb->getBuilderUniqueName();
116    for (const StreamSetBuffer * b: mStreamSetInputBuffers) {
117        cacheName <<  ':' <<  b->getUniqueID();
118    }
119    for (const StreamSetBuffer * b: mStreamSetOutputBuffers) {
120        cacheName <<  ':' <<  b->getUniqueID();
121    }
122    return cacheName.str();
123}
124
125Module * Kernel::setModule(Module * const module) {
126    assert (mModule == nullptr || mModule == module);
127    assert (module != nullptr);
128    mModule = module;
129    return mModule;
130}
131
132Module * Kernel::makeModule(const std::unique_ptr<kernel::KernelBuilder> & idb) {
133    return setModule(new Module(getCacheName(idb), idb->getContext()));
134}
135
136void Kernel::prepareKernel(const std::unique_ptr<KernelBuilder> & idb) {
137    assert ("KernelBuilder does not have a valid IDISA Builder" && idb);
138    if (LLVM_UNLIKELY(mKernelStateType != nullptr)) {
139        report_fatal_error(getName() + ": cannot prepare kernel after kernel state finalized");
140    }
141    const auto blockSize = idb->getBitBlockWidth();
142    if (mStride == 0) {
143        // Set the default kernel stride.
144        mStride = blockSize;
145    }
146    IntegerType * const sizeTy = idb->getSizeTy();
147
148    assert (mStreamSetInputs.size() == mStreamSetInputBuffers.size());
149//    assert (mStreamSetInputs.size() == mStreamSetInputLookahead.size());
150
151    for (unsigned i = 0; i < mStreamSetInputs.size(); i++) {
152//        const auto requiredBlocks = codegen::SegmentSize + ((mStreamSetInputLookahead[i] + blockSize - 1) / blockSize);
153//        if ((mStreamSetInputBuffers[i]->getBufferBlocks() != 0) && (mStreamSetInputBuffers[i]->getBufferBlocks() < requiredBlocks)) {
154//            report_fatal_error(getName() + ": " + mStreamSetInputs[i].name + " requires buffer size " + std::to_string(requiredBlocks));
155//        }
156        mScalarInputs.emplace_back(mStreamSetInputBuffers[i]->getStreamSetHandle()->getType(), mStreamSetInputs[i].name + BUFFER_PTR_SUFFIX);
157        if ((i == 0) || !mStreamSetInputs[i].rate.isExact()) {
158            addScalar(sizeTy, mStreamSetInputs[i].name + PROCESSED_ITEM_COUNT_SUFFIX);
159        }
160    }
161
162    assert (mStreamSetOutputs.size() == mStreamSetOutputBuffers.size());
163
164    for (unsigned i = 0; i < mStreamSetOutputs.size(); i++) {
165        mScalarInputs.emplace_back(mStreamSetOutputBuffers[i]->getStreamSetHandle()->getType(), mStreamSetOutputs[i].name + BUFFER_PTR_SUFFIX);
166        if ((mStreamSetInputs.empty() && (i == 0)) || !mStreamSetOutputs[i].rate.isExact()) {
167            addScalar(sizeTy, mStreamSetOutputs[i].name + PRODUCED_ITEM_COUNT_SUFFIX);
168        }
169    }
170    for (const auto & binding : mScalarInputs) {
171        addScalar(binding.type, binding.name);
172    }
173    for (const auto & binding : mScalarOutputs) {
174        addScalar(binding.type, binding.name);
175    }
176    if (mStreamMap.empty()) {
177        prepareStreamSetNameMap();
178    }
179    for (const auto & binding : mInternalScalars) {
180        addScalar(binding.type, binding.name);
181    }
182
183    Type * const consumerSetTy = StructType::get(sizeTy, sizeTy->getPointerTo()->getPointerTo(), nullptr)->getPointerTo();
184    for (unsigned i = 0; i < mStreamSetOutputs.size(); i++) {
185        addScalar(consumerSetTy, mStreamSetOutputs[i].name + CONSUMER_SUFFIX);
186    }
187
188    addScalar(sizeTy, LOGICAL_SEGMENT_NO_SCALAR);
189    addScalar(idb->getInt1Ty(), TERMINATION_SIGNAL);
190
191    for (unsigned i = 0; i < mStreamSetOutputs.size(); i++) {
192        addScalar(sizeTy, mStreamSetOutputs[i].name + CONSUMED_ITEM_COUNT_SUFFIX);
193    }
194
195    // We compile in a 64-bit CPU cycle counter into every kernel.   It will remain unused
196    // in normal execution, but when codegen::EnableCycleCounter is specified, pipelines
197    // will be able to add instrumentation to cached modules without recompilation.
198    addScalar(idb->getInt64Ty(), CYCLECOUNT_SCALAR);
199    addInternalKernelProperties(idb);
200    // NOTE: StructType::create always creates a new type even if an identical one exists.
201    if (LLVM_UNLIKELY(mModule == nullptr)) {
202        setModule(new Module(getCacheName(idb), idb->getContext()));
203    }
204    mKernelStateType = mModule->getTypeByName(getName());
205    if (LLVM_LIKELY(mKernelStateType == nullptr)) {
206        mKernelStateType = StructType::create(idb->getContext(), mKernelFields, getName());
207        assert (mKernelStateType);
208    }
209    processingRateAnalysis();
210}
211
212void Kernel::prepareCachedKernel(const std::unique_ptr<KernelBuilder> & idb) {
213
214    assert ("KernelBuilder does not have a valid IDISA Builder" && idb);
215    if (LLVM_UNLIKELY(mKernelStateType != nullptr)) {
216        report_fatal_error(getName() + ": cannot prepare kernel after kernel state finalized");
217    }
218    assert (getModule());
219    const auto blockSize = idb->getBitBlockWidth();
220    if (mStride == 0) {
221        // Set the default kernel stride.
222        mStride = blockSize;
223    }
224    IntegerType * const sizeTy = idb->getSizeTy();
225
226    assert (mStreamSetInputs.size() == mStreamSetInputBuffers.size());
227//    assert (mStreamSetInputs.size() == mStreamSetInputLookahead.size());
228
229    for (unsigned i = 0; i < mStreamSetInputs.size(); i++) {
230//        const auto requiredBlocks = codegen::SegmentSize + ((mStreamSetInputLookahead[i] + blockSize - 1) / blockSize);
231//        if ((mStreamSetInputBuffers[i]->getBufferBlocks() != 0) && (mStreamSetInputBuffers[i]->getBufferBlocks() < requiredBlocks)) {
232//            report_fatal_error(getName() + ": " + mStreamSetInputs[i].name + " requires buffer size " + std::to_string(requiredBlocks));
233//        }
234        mScalarInputs.emplace_back(mStreamSetInputBuffers[i]->getStreamSetHandle()->getType(), mStreamSetInputs[i].name + BUFFER_PTR_SUFFIX);
235        if ((i == 0) || !mStreamSetInputs[i].rate.isExact()) {
236            addScalar(sizeTy, mStreamSetInputs[i].name + PROCESSED_ITEM_COUNT_SUFFIX);
237        }
238    }
239
240    assert (mStreamSetOutputs.size() == mStreamSetOutputBuffers.size());
241
242    for (unsigned i = 0; i < mStreamSetOutputs.size(); i++) {
243        mScalarInputs.emplace_back(mStreamSetOutputBuffers[i]->getStreamSetHandle()->getType(), mStreamSetOutputs[i].name + BUFFER_PTR_SUFFIX);
244        if ((mStreamSetInputs.empty() && (i == 0)) || !mStreamSetOutputs[i].rate.isExact()) {
245            addScalar(sizeTy, mStreamSetOutputs[i].name + PRODUCED_ITEM_COUNT_SUFFIX);
246        }
247    }
248    for (const auto & binding : mScalarInputs) {
249        addScalar(binding.type, binding.name);
250    }
251    for (const auto & binding : mScalarOutputs) {
252        addScalar(binding.type, binding.name);
253    }
254    if (mStreamMap.empty()) {
255        prepareStreamSetNameMap();
256    }
257    for (const auto & binding : mInternalScalars) {
258        addScalar(binding.type, binding.name);
259    }
260    Type * const consumerSetTy = StructType::get(sizeTy, sizeTy->getPointerTo()->getPointerTo(), nullptr)->getPointerTo();
261    for (unsigned i = 0; i < mStreamSetOutputs.size(); i++) {
262        addScalar(consumerSetTy, mStreamSetOutputs[i].name + CONSUMER_SUFFIX);
263    }
264    addScalar(sizeTy, LOGICAL_SEGMENT_NO_SCALAR);
265    addScalar(idb->getInt1Ty(), TERMINATION_SIGNAL);
266    for (unsigned i = 0; i < mStreamSetOutputs.size(); i++) {
267        addScalar(sizeTy, mStreamSetOutputs[i].name + CONSUMED_ITEM_COUNT_SUFFIX);
268    }
269    // We compile in a 64-bit CPU cycle counter into every kernel.   It will remain unused
270    // in normal execution, but when codegen::EnableCycleCounter is specified, pipelines
271    // will be able to add instrumentation to cached modules without recompilation.
272    addScalar(idb->getInt64Ty(), CYCLECOUNT_SCALAR);
273
274    mKernelStateType = getModule()->getTypeByName(getName());
275    if (LLVM_UNLIKELY(mKernelStateType == nullptr)) {
276        report_fatal_error("Kernel " + getName() + " definition could not be found in the cache object");
277    }
278    processingRateAnalysis();
279}
280   
281void Kernel::processingRateAnalysis() {
282   
283    const unsigned inputSetCount = mStreamSetInputs.size();
284    const unsigned outputSetCount = mStreamSetOutputs.size();
285    const unsigned totalSetCount = inputSetCount + outputSetCount;
286   
287    mItemsPerStride.resize(totalSetCount);
288    mIsDerived.resize(totalSetCount);
289
290    mItemsPerStride[0] = mStride;
291    mIsDerived[0] = true;
292   
293    for (unsigned i = 0; i < inputSetCount; i++) {
294        // Default reference stream set is the principal input stream set.
295        auto & rate = mStreamSetInputs[i].rate;
296        if (rate.referenceStreamSet() == "") {
297            rate.setReferenceStreamSet(mStreamSetInputs[0].name);
298        }
299        Port port; unsigned ssIdx;
300        std::tie(port, ssIdx) = getStreamPort(rate.referenceStreamSet());
301        if ((port == Port::Output) || (ssIdx > i) || ((ssIdx == i) && (i > 0))) {
302            report_fatal_error(getName() + ": input set " + mStreamSetInputs[i].name + ": forward or circular rate dependency");
303        }
304        if ((rate.isExact() || rate.isMaxRatio()) && mIsDerived[ssIdx]) {
305            if ((mItemsPerStride[ssIdx] % rate.getRatioDenominator()) != 0) {
306                report_fatal_error(getName() + ": " + mStreamSetInputs[i].name + " processing rate denominator does not exactly divide items per stride.");
307            }
308            mItemsPerStride[i] = rate.calculateRatio(mItemsPerStride[ssIdx]);
309            mIsDerived[i] = rate.isExact();
310        }
311        else {
312            mIsDerived[i] = false;
313            mItemsPerStride[i] = 0;  // For unknown input rate, no items will be copied to temp buffers.
314        }
315    }
316   
317    for (unsigned i = inputSetCount; i < totalSetCount; i++) {
318        auto & rate = mStreamSetOutputs[i-inputSetCount].rate;
319        // Default reference stream set is the principal input stream set for the principal output stream set.
320        // Default reference stream set is the principal output stream set for other output stream sets.
321        if (rate.referenceStreamSet() == "") {
322            if ((mStreamSetInputs.size() > 0) && (i == inputSetCount)) {
323                rate.setReferenceStreamSet(mStreamSetInputs[0].name);
324            }
325            else {
326                rate.setReferenceStreamSet(mStreamSetOutputs[0].name);
327            }
328        }
329        Port port; unsigned ssIdx;
330        std::tie(port, ssIdx) = getStreamPort(rate.referenceStreamSet());
331        if (port == Port::Output) ssIdx += inputSetCount;
332        if ((ssIdx > i) || ((ssIdx == i) && (i > 0))) {
333            report_fatal_error(getName() + ": output set " + mStreamSetOutputs[i].name + ": forward or circular rate dependency");
334        }
335        if ((rate.isExact() || rate.isMaxRatio()) && mIsDerived[ssIdx]) {
336            if ((mItemsPerStride[ssIdx] % rate.getRatioDenominator()) != 0) {
337                report_fatal_error(getName() + ": " + mStreamSetOutputs[i-inputSetCount].name + " processing rate denominator does not exactly divide items per stride.");
338            }
339            mItemsPerStride[i] = rate.calculateRatio(mItemsPerStride[ssIdx]);
340            mIsDerived[i] = rate.isExact();
341        }
342        else {
343            mIsDerived[i] = false;
344            mItemsPerStride[i] = 0;  // For unknown output rate, no items will be copied to temp buffers.
345        }
346    }
347}
348
349   
350
351// Default kernel signature: generate the IR and emit as byte code.
352std::string Kernel::makeSignature(const std::unique_ptr<kernel::KernelBuilder> & idb) {
353    assert ("KernelBuilder does not have a valid IDISA Builder" && idb.get());
354    if (LLVM_UNLIKELY(hasSignature())) {
355        generateKernel(idb);
356        std::string signature;
357        raw_string_ostream OS(signature);
358        WriteBitcodeToFile(getModule(), OS);
359        return signature;
360    } else {
361        return getModule()->getModuleIdentifier();
362    }
363}
364
365void Kernel::generateKernel(const std::unique_ptr<kernel::KernelBuilder> & idb) {
366    assert ("KernelBuilder does not have a valid IDISA Builder" && idb.get());
367    // If the module id cannot uniquely identify this kernel, "generateKernelSignature()" will have already
368    // generated the unoptimized IR.
369    if (!mIsGenerated) {
370        const auto m = idb->getModule();
371        const auto ip = idb->saveIP();
372        // const auto saveInstance = getInstance();
373        idb->setModule(mModule);
374        addKernelDeclarations(idb);
375        callGenerateInitializeMethod(idb);
376        callGenerateDoSegmentMethod(idb);
377        callGenerateFinalizeMethod(idb);
378        // setInstance(saveInstance);
379        idb->setModule(m);
380        idb->restoreIP(ip);
381        mIsGenerated = true;
382    }
383}
384
385inline void Kernel::callGenerateInitializeMethod(const std::unique_ptr<kernel::KernelBuilder> & idb) {
386    mCurrentMethod = getInitFunction(idb->getModule());
387    idb->SetInsertPoint(BasicBlock::Create(idb->getContext(), "entry", mCurrentMethod));
388    Function::arg_iterator args = mCurrentMethod->arg_begin();
389    setInstance(&*(args++));
390    idb->CreateStore(ConstantAggregateZero::get(mKernelStateType), getInstance());
391    for (const auto & binding : mScalarInputs) {
392        idb->setScalarField(binding.name, &*(args++));
393    }
394    for (const auto & binding : mStreamSetOutputs) {
395        idb->setConsumerLock(binding.name, &*(args++));
396    }
397    generateInitializeMethod(idb);
398    idb->CreateRetVoid();
399}
400
401inline void Kernel::callGenerateDoSegmentMethod(const std::unique_ptr<kernel::KernelBuilder> & idb) {
402    mCurrentMethod = getDoSegmentFunction(idb->getModule());
403    idb->SetInsertPoint(BasicBlock::Create(idb->getContext(), "entry", mCurrentMethod));
404    auto args = mCurrentMethod->arg_begin();
405    setInstance(&*(args++));
406    mIsFinal = &*(args++);
407    const auto n = mStreamSetInputs.size();
408    mAvailableItemCount.resize(n, nullptr);
409    for (unsigned i = 0; i < mStreamSetInputs.size(); i++) {
410        mAvailableItemCount[i] = &*(args++);
411    }
412    generateDoSegmentMethod(idb); // must be overridden by the KernelBuilder subtype
413    mIsFinal = nullptr;
414    mAvailableItemCount.clear();
415    idb->CreateRetVoid();
416}
417
418inline void Kernel::callGenerateFinalizeMethod(const std::unique_ptr<KernelBuilder> & idb) {
419    mCurrentMethod = getTerminateFunction(idb->getModule());
420    idb->SetInsertPoint(BasicBlock::Create(idb->getContext(), "entry", mCurrentMethod));
421    auto args = mCurrentMethod->arg_begin();
422    setInstance(&*(args++));
423    generateFinalizeMethod(idb); // may be overridden by the KernelBuilder subtype
424    const auto n = mScalarOutputs.size();
425    if (n == 0) {
426        idb->CreateRetVoid();
427    } else {
428        Value * outputs[n];
429        for (unsigned i = 0; i < n; ++i) {
430            outputs[i] = idb->getScalarField(mScalarOutputs[i].name);
431        }
432        if (n == 1) {
433            idb->CreateRet(outputs[0]);
434        } else {
435            idb->CreateAggregateRet(outputs, n);
436        }
437    }
438}
439
440unsigned Kernel::getScalarIndex(const std::string & name) const {
441    const auto f = mKernelMap.find(name);
442    if (LLVM_UNLIKELY(f == mKernelMap.end())) {
443        report_fatal_error(getName() + " does not contain scalar: " + name);
444    }
445    return f->second;
446}
447
448Value * Kernel::createInstance(const std::unique_ptr<KernelBuilder> & idb) {
449    assert ("KernelBuilder does not have a valid IDISA Builder" && idb);
450    if (LLVM_UNLIKELY(mKernelStateType == nullptr)) {
451        report_fatal_error("Cannot instantiate " + getName() + " before calling prepareKernel()");
452    }
453    setInstance(idb->CreateCacheAlignedAlloca(mKernelStateType));
454    return getInstance();
455}
456
457void Kernel::initializeInstance(const std::unique_ptr<KernelBuilder> & idb) {
458    assert ("KernelBuilder does not have a valid IDISA Builder" && idb);
459    if (LLVM_UNLIKELY(getInstance() == nullptr)) {
460        report_fatal_error("Cannot initialize " + getName() + " before calling createInstance()");
461    }
462    std::vector<Value *> args;
463    args.reserve(1 + mInitialArguments.size() + mStreamSetInputBuffers.size() + (mStreamSetOutputBuffers.size() * 2));
464    args.push_back(getInstance());
465    for (unsigned i = 0; i < mInitialArguments.size(); ++i) {
466        Value * arg = mInitialArguments[i];
467        if (LLVM_UNLIKELY(arg == nullptr)) {
468            report_fatal_error(getName() + ": initial argument " + std::to_string(i)
469                               + " cannot be null when calling createInstance()");
470        }
471        args.push_back(arg);
472    }
473    for (unsigned i = 0; i < mStreamSetInputBuffers.size(); ++i) {
474        assert (mStreamSetInputBuffers[i]);
475        Value * arg = mStreamSetInputBuffers[i]->getStreamSetHandle();
476        if (LLVM_UNLIKELY(arg == nullptr)) {
477            report_fatal_error(getName() + ": input stream set " + std::to_string(i)
478                               + " was not allocated prior to calling createInstance()");
479        }
480        args.push_back(arg);
481    }
482    assert (mStreamSetInputs.size() == mStreamSetInputBuffers.size());
483    for (unsigned i = 0; i < mStreamSetOutputBuffers.size(); ++i) {
484        assert (mStreamSetOutputBuffers[i]);
485        Value * arg = mStreamSetOutputBuffers[i]->getStreamSetHandle();
486        if (LLVM_UNLIKELY(arg == nullptr)) {
487            report_fatal_error(getName() + ": output stream set " + std::to_string(i)
488                               + " was not allocated prior to calling createInstance()");
489        }
490        args.push_back(arg);
491    }
492    assert (mStreamSetOutputs.size() == mStreamSetOutputBuffers.size());
493    IntegerType * const sizeTy = idb->getSizeTy();
494    PointerType * const sizePtrTy = sizeTy->getPointerTo();
495    PointerType * const sizePtrPtrTy = sizePtrTy->getPointerTo();
496    StructType * const consumerTy = StructType::get(sizeTy, sizePtrPtrTy, nullptr);
497    for (unsigned i = 0; i < mStreamSetOutputBuffers.size(); ++i) {
498        const auto output = mStreamSetOutputBuffers[i];
499        const auto & consumers = output->getConsumers();
500        const auto n = consumers.size();
501        AllocaInst * const outputConsumers = idb->CreateAlloca(consumerTy);
502        Value * const consumerSegNoArray = idb->CreateAlloca(ArrayType::get(sizePtrTy, n));
503        for (unsigned i = 0; i < n; ++i) {
504            Kernel * const consumer = consumers[i];
505            assert ("all instances must be created prior to initialization of any instance" && consumer->getInstance());
506            idb->setKernel(consumer);
507            Value * const segmentNoPtr = idb->getScalarFieldPtr(LOGICAL_SEGMENT_NO_SCALAR);
508            idb->CreateStore(segmentNoPtr, idb->CreateGEP(consumerSegNoArray, { idb->getInt32(0), idb->getInt32(i) }));
509        }
510        idb->setKernel(this);
511        Value * const consumerCountPtr = idb->CreateGEP(outputConsumers, {idb->getInt32(0), idb->getInt32(0)});
512        idb->CreateStore(idb->getSize(n), consumerCountPtr);
513        Value * const consumerSegNoArrayPtr = idb->CreateGEP(outputConsumers, {idb->getInt32(0), idb->getInt32(1)});
514        idb->CreateStore(idb->CreatePointerCast(consumerSegNoArray, sizePtrPtrTy), consumerSegNoArrayPtr);
515        args.push_back(outputConsumers);
516    }
517    idb->CreateCall(getInitFunction(idb->getModule()), args);
518}
519
520//  The default doSegment method dispatches to the doBlock routine for
521//  each block of the given number of blocksToDo, and then updates counts.
522
523void BlockOrientedKernel::generateDoSegmentMethod(const std::unique_ptr<KernelBuilder> & idb) {
524    BasicBlock * const entryBlock = idb->GetInsertBlock();
525    BasicBlock * const strideLoopCond = idb->CreateBasicBlock(getName() + "_strideLoopCond");
526    mStrideLoopBody = idb->CreateBasicBlock(getName() + "_strideLoopBody");
527    BasicBlock * const stridesDone = idb->CreateBasicBlock(getName() + "_stridesDone");
528    BasicBlock * const doFinalBlock = idb->CreateBasicBlock(getName() + "_doFinalBlock");
529    BasicBlock * const segmentDone = idb->CreateBasicBlock(getName() + "_segmentDone");
530
531    Value * baseTarget = nullptr;
532    if (idb->supportsIndirectBr()) {
533        baseTarget = idb->CreateSelect(mIsFinal, BlockAddress::get(doFinalBlock), BlockAddress::get(segmentDone));
534    }
535
536    ConstantInt * stride = idb->getSize(idb->getStride());
537    Value * availablePos = mAvailableItemCount[0];
538    Value * processed = idb->getProcessedItemCount(mStreamSetInputs[0].name);
539    Value * itemsAvail = idb->CreateSub(availablePos, processed);
540    Value * stridesToDo = idb->CreateUDiv(itemsAvail, stride);
541
542    idb->CreateBr(strideLoopCond);
543
544    idb->SetInsertPoint(strideLoopCond);
545
546    PHINode * branchTarget = nullptr;
547    if (idb->supportsIndirectBr()) {
548        branchTarget = idb->CreatePHI(baseTarget->getType(), 2, "branchTarget");
549        branchTarget->addIncoming(baseTarget, entryBlock);
550    }
551
552    PHINode * const stridesRemaining = idb->CreatePHI(idb->getSizeTy(), 2, "stridesRemaining");
553    stridesRemaining->addIncoming(stridesToDo, entryBlock);
554    // NOTE: stridesRemaining may go to a negative number in the final block if the generateFinalBlockMethod(...)
555    // calls CreateDoBlockMethodCall(). Do *not* replace the comparator with an unsigned one!
556    Value * notDone = idb->CreateICmpSGT(stridesRemaining, idb->getSize(0));
557    idb->CreateLikelyCondBr(notDone, mStrideLoopBody, stridesDone);
558
559    idb->SetInsertPoint(mStrideLoopBody);
560
561    if (idb->supportsIndirectBr()) {
562        mStrideLoopTarget = idb->CreatePHI(baseTarget->getType(), 2, "strideTarget");
563        mStrideLoopTarget->addIncoming(branchTarget, strideLoopCond);
564    }
565
566    /// GENERATE DO BLOCK METHOD
567
568    writeDoBlockMethod(idb);
569
570    /// UPDATE PROCESSED COUNTS
571
572    processed = idb->getProcessedItemCount(mStreamSetInputs[0].name);
573    Value * itemsDone = idb->CreateAdd(processed, stride);
574    idb->setProcessedItemCount(mStreamSetInputs[0].name, itemsDone);
575
576    stridesRemaining->addIncoming(idb->CreateSub(stridesRemaining, idb->getSize(1)), idb->GetInsertBlock());
577
578    BasicBlock * bodyEnd = idb->GetInsertBlock();
579    if (idb->supportsIndirectBr()) {
580        branchTarget->addIncoming(mStrideLoopTarget, bodyEnd);
581    }
582    idb->CreateBr(strideLoopCond);
583
584    stridesDone->moveAfter(bodyEnd);
585
586    idb->SetInsertPoint(stridesDone);
587
588    // Now conditionally perform the final block processing depending on the doFinal parameter.
589    if (idb->supportsIndirectBr()) {
590        mStrideLoopBranch = idb->CreateIndirectBr(branchTarget, 3);
591        mStrideLoopBranch->addDestination(doFinalBlock);
592        mStrideLoopBranch->addDestination(segmentDone);
593    } else {
594        idb->CreateUnlikelyCondBr(mIsFinal, doFinalBlock, segmentDone);
595    }
596
597    doFinalBlock->moveAfter(stridesDone);
598
599    idb->SetInsertPoint(doFinalBlock);
600
601    Value * remainingItems = idb->CreateSub(mAvailableItemCount[0], idb->getProcessedItemCount(mStreamSetInputs[0].name));
602
603    writeFinalBlockMethod(idb, remainingItems);
604
605    itemsDone = mAvailableItemCount[0];
606    idb->setProcessedItemCount(mStreamSetInputs[0].name, itemsDone);
607    idb->setTerminationSignal();
608    idb->CreateBr(segmentDone);
609
610    segmentDone->moveAfter(idb->GetInsertBlock());
611
612    idb->SetInsertPoint(segmentDone);
613
614    // Update the branch prediction metadata to indicate that the likely target will be segmentDone
615    if (idb->supportsIndirectBr()) {
616        MDBuilder mdb(idb->getContext());
617        const auto destinations = mStrideLoopBranch->getNumDestinations();
618        uint32_t weights[destinations];
619        for (unsigned i = 0; i < destinations; ++i) {
620            weights[i] = (mStrideLoopBranch->getDestination(i) == segmentDone) ? 100 : 1;
621        }
622        ArrayRef<uint32_t> bw(weights, destinations);
623        mStrideLoopBranch->setMetadata(LLVMContext::MD_prof, mdb.createBranchWeights(bw));
624    }
625
626}
627
628inline void BlockOrientedKernel::writeDoBlockMethod(const std::unique_ptr<KernelBuilder> & idb) {
629
630    Value * const self = getInstance();
631    Function * const cp = mCurrentMethod;
632    auto ip = idb->saveIP();
633    std::vector<Value *> availableItemCount(0);
634
635    /// Check if the do block method is called and create the function if necessary   
636    if (!idb->supportsIndirectBr()) {
637
638        std::vector<Type *> params;
639        params.reserve(1 + mAvailableItemCount.size());
640        params.push_back(self->getType());
641        for (Value * avail : mAvailableItemCount) {
642            params.push_back(avail->getType());
643        }
644
645        FunctionType * const type = FunctionType::get(idb->getVoidTy(), params, false);
646        mCurrentMethod = Function::Create(type, GlobalValue::InternalLinkage, getName() + DO_BLOCK_SUFFIX, idb->getModule());
647        mCurrentMethod->setCallingConv(CallingConv::C);
648        mCurrentMethod->setDoesNotThrow();
649        mCurrentMethod->setDoesNotCapture(1);
650        auto args = mCurrentMethod->arg_begin();
651        args->setName("self");
652        setInstance(&*args);
653        availableItemCount.reserve(mAvailableItemCount.size());
654        while (++args != mCurrentMethod->arg_end()) {
655            availableItemCount.push_back(&*args);
656        }
657        assert (availableItemCount.size() == mAvailableItemCount.size());
658        mAvailableItemCount.swap(availableItemCount);
659        idb->SetInsertPoint(BasicBlock::Create(idb->getContext(), "entry", mCurrentMethod));
660    }
661
662    std::vector<Value *> priorProduced;
663    for (unsigned i = 0; i < mStreamSetOutputs.size(); i++) {
664        if (mStreamSetOutputBuffers[i]->supportsCopyBack())  {
665            priorProduced.push_back(idb->getProducedItemCount(mStreamSetOutputs[i].name));
666        }
667    }
668
669    generateDoBlockMethod(idb); // must be implemented by the BlockOrientedKernelBuilder subtype
670
671    unsigned priorIdx = 0;
672    for (unsigned i = 0; i < mStreamSetOutputs.size(); i++) {
673        if (mStreamSetOutputBuffers[i]->supportsCopyBack()) {
674            Value * newProduced = idb->getProducedItemCount(mStreamSetOutputs[i].name);
675            Value * handle = idb->getStreamSetBufferPtr(mStreamSetOutputs[i].name);
676            mStreamSetOutputBuffers[i]->genCopyBackLogic(idb.get(), handle, priorProduced[priorIdx], newProduced, mStreamSetOutputs[i].name);
677            priorIdx++;
678        }
679    }
680
681    if (!idb->supportsIndirectBr()) {
682        // Restore the DoSegment function state then call the DoBlock method
683        idb->CreateRetVoid();
684        mDoBlockMethod = mCurrentMethod;
685        idb->restoreIP(ip);
686        setInstance(self);
687        mCurrentMethod = cp;
688        mAvailableItemCount.swap(availableItemCount);
689        CreateDoBlockMethodCall(idb);
690    }
691
692}
693
694inline void BlockOrientedKernel::writeFinalBlockMethod(const std::unique_ptr<KernelBuilder> & idb, Value * remainingItems) {
695
696    Value * const self = getInstance();
697    Function * const cp = mCurrentMethod;
698    Value * const remainingItemCount = remainingItems;
699    auto ip = idb->saveIP();
700    std::vector<Value *> availableItemCount(0);
701
702    if (!idb->supportsIndirectBr()) {
703        std::vector<Type *> params;
704        params.reserve(2 + mAvailableItemCount.size());
705        params.push_back(self->getType());
706        params.push_back(idb->getSizeTy());
707        for (Value * avail : mAvailableItemCount) {
708            params.push_back(avail->getType());
709        }
710        FunctionType * const type = FunctionType::get(idb->getVoidTy(), params, false);
711        mCurrentMethod = Function::Create(type, GlobalValue::InternalLinkage, getName() + FINAL_BLOCK_SUFFIX, idb->getModule());
712        mCurrentMethod->setCallingConv(CallingConv::C);
713        mCurrentMethod->setDoesNotThrow();
714        mCurrentMethod->setDoesNotCapture(1);
715        auto args = mCurrentMethod->arg_begin();
716        args->setName("self");
717        setInstance(&*args);
718        remainingItems = &*(++args);
719        remainingItems->setName("remainingItems");
720        availableItemCount.reserve(mAvailableItemCount.size());
721        while (++args != mCurrentMethod->arg_end()) {
722            availableItemCount.push_back(&*args);
723        }
724        assert (availableItemCount.size() == mAvailableItemCount.size());
725        mAvailableItemCount.swap(availableItemCount);
726        idb->SetInsertPoint(BasicBlock::Create(idb->getContext(), "entry", mCurrentMethod));
727    }
728
729    generateFinalBlockMethod(idb, remainingItems); // may be implemented by the BlockOrientedKernel subtype
730
731    RecursivelyDeleteTriviallyDeadInstructions(remainingItems); // if remainingItems was not used, this will eliminate it.
732
733    if (!idb->supportsIndirectBr()) {
734        idb->CreateRetVoid();
735        idb->restoreIP(ip);
736        setInstance(self);
737        mAvailableItemCount.swap(availableItemCount);
738        // Restore the DoSegment function state then call the DoFinal method
739        std::vector<Value *> args;
740        args.reserve(2 + mAvailableItemCount.size());
741        args.push_back(self);
742        args.push_back(remainingItemCount);
743        for (Value * avail : mAvailableItemCount) {
744            args.push_back(avail);
745        }
746        idb->CreateCall(mCurrentMethod, args);
747        mCurrentMethod = cp;
748    }
749
750}
751
752//  The default finalBlock method simply dispatches to the doBlock routine.
753void BlockOrientedKernel::generateFinalBlockMethod(const std::unique_ptr<KernelBuilder> & idb, Value * /* remainingItems */) {
754    CreateDoBlockMethodCall(idb);
755}
756
757void BlockOrientedKernel::CreateDoBlockMethodCall(const std::unique_ptr<KernelBuilder> & idb) {
758    if (idb->supportsIndirectBr()) {
759        BasicBlock * bb = idb->CreateBasicBlock("resume");
760        mStrideLoopBranch->addDestination(bb);
761        mStrideLoopTarget->addIncoming(BlockAddress::get(bb), idb->GetInsertBlock());
762        idb->CreateBr(mStrideLoopBody);
763        bb->moveAfter(idb->GetInsertBlock());
764        idb->SetInsertPoint(bb);
765    } else {
766        std::vector<Value *> args;
767        args.reserve(1 + mAvailableItemCount.size());
768        args.push_back(getInstance());
769        for (Value * avail : mAvailableItemCount) {
770            args.push_back(avail);
771        }
772        idb->CreateCall(mDoBlockMethod, args);
773    }
774}
775
776void MultiBlockKernel::generateDoSegmentMethod(const std::unique_ptr<KernelBuilder> & kb) {
777
778    // Stream set and buffer analysis.  When near the end of buffers
779    // or for final block processing, data for each streamset may need
780    // to be copied into temporary buffers to ensure linear access.
781    // Data is always copied as a number of whole blocks, dependent
782    // on the stream set processing rate.
783   
784    const unsigned bitBlockWidth = kb->getBitBlockWidth();
785    const unsigned inputSetCount = mStreamSetInputs.size();
786    const unsigned outputSetCount = mStreamSetOutputs.size();
787    const unsigned totalSetCount = inputSetCount + outputSetCount;
788   
789    int maxBlocksToCopy[totalSetCount];
790    for (unsigned i = 0; i < totalSetCount; i++) {
791        if (mIsDerived[i]) {
792            if (mItemsPerStride[i] % bitBlockWidth == 0) {
793                maxBlocksToCopy[i] = mItemsPerStride[i] / bitBlockWidth;
794            }
795            else {
796                // May not be block aligned, can overlap partial blocks at both ends.
797                maxBlocksToCopy[i] = mItemsPerStride[i]/bitBlockWidth + 2;
798            }
799        }
800        else {
801            // For variable input stream sets, we make a single stride of items
802            // available, if possible, but this stride could be nonaligned.
803            maxBlocksToCopy[i] = mStride / bitBlockWidth + 2;
804        }
805    }
806    auto ip = kb->saveIP();
807    Function * const cp = mCurrentMethod;
808    const auto saveInstance = getInstance();
809
810    // First prepare the multi-block method that will be used.
811
812    std::vector<Type *> multiBlockParmTypes;
813    multiBlockParmTypes.push_back(mKernelStateType->getPointerTo());
814    multiBlockParmTypes.push_back(kb->getSizeTy());
815    for (unsigned i = 1; i < mStreamSetInputs.size(); i++) {
816        if (!mIsDerived[i]) multiBlockParmTypes.push_back(kb->getSizeTy());
817    }
818    for (auto buffer : mStreamSetInputBuffers) {
819        multiBlockParmTypes.push_back(buffer->getPointerType());
820    }
821    for (auto buffer : mStreamSetOutputBuffers) {
822        multiBlockParmTypes.push_back(buffer->getPointerType());
823    }
824
825    FunctionType * const type = FunctionType::get(kb->getVoidTy(), multiBlockParmTypes, false);
826    Function * multiBlockFunction = Function::Create(type, GlobalValue::InternalLinkage, getName() + MULTI_BLOCK_SUFFIX, kb->getModule());
827    multiBlockFunction->setCallingConv(CallingConv::C);
828    multiBlockFunction->setDoesNotThrow();
829    mCurrentMethod = multiBlockFunction;
830    kb->SetInsertPoint(BasicBlock::Create(kb->getContext(), "multiBlockEntry", multiBlockFunction, 0));
831
832    auto args = multiBlockFunction->arg_begin();
833    args->setName("self");
834    setInstance(&*args);
835    (++args)->setName("itemsToDo");
836    for (unsigned i = 1; i < mStreamSetInputs.size(); i++) {
837        if (!mIsDerived[i]) (++args)->setName(mStreamSetInputs[i].name + "_availItems");
838    }
839    for (auto binding : mStreamSetInputs) {
840        (++args)->setName(binding.name + "BufPtr");
841    }
842    for (auto binding : mStreamSetOutputs) {
843        (++args)->setName(binding.name + "BufPtr");
844    }
845
846    // Now use the generateMultiBlockLogic method of the MultiBlockKernelBuilder subtype to
847    // provide the required multi-block kernel logic.
848    generateMultiBlockLogic(kb);
849
850    kb->CreateRetVoid();
851
852    kb->restoreIP(ip);
853    mCurrentMethod = cp;
854    setInstance(saveInstance);
855
856    // Now proceed with creation of the doSegment method.
857
858    BasicBlock * const entry = kb->GetInsertBlock();
859    BasicBlock * const doSegmentOuterLoop = kb->CreateBasicBlock(getName() + "_doSegmentOuterLoop");
860    BasicBlock * const doMultiBlockCall = kb->CreateBasicBlock(getName() + "_doMultiBlockCall");
861    BasicBlock * const tempBlockCheck = kb->CreateBasicBlock(getName() + "_tempBlockCheck");
862    BasicBlock * const doTempBufferBlock = kb->CreateBasicBlock(getName() + "_doTempBufferBlock");
863    BasicBlock * const segmentDone = kb->CreateBasicBlock(getName() + "_segmentDone");
864
865    Value * blockBaseMask = kb->CreateNot(kb->getSize(kb->getBitBlockWidth() - 1));
866    ConstantInt * blockSize = kb->getSize(kb->getBitBlockWidth());
867    ConstantInt * strideSize = kb->getSize(mStride);
868   
869    Value * availablePos = mAvailableItemCount[0];
870    Value * itemsAvail = availablePos;
871
872    //  Make sure that corresponding data is available depending on processing rate
873    //  for all derived input stream sets.
874    for (unsigned i = 1; i < mStreamSetInputs.size(); i++) {
875        Value * a = mAvailableItemCount[i];
876        auto & rate = mStreamSetInputs[i].rate;
877        if (mIsDerived[i]) {
878            Value * maxItems = rate.CreateMaxReferenceItemsCalculation(kb.get(), a);
879            itemsAvail = kb->CreateSelect(kb->CreateICmpULT(itemsAvail, maxItems), itemsAvail, maxItems);
880        }
881    }
882
883    Value * processed = kb->getProcessedItemCount(mStreamSetInputs[0].name);
884    Value * itemsToDo = kb->CreateSub(itemsAvail, processed);
885    Value * fullStridesToDo = kb->CreateUDiv(itemsToDo, strideSize);
886
887    //  Now we iteratively process these blocks using the doMultiBlock method.
888    //  In each iteration, we process the maximum number of linearly accessible
889    //  blocks on the principal input, reduced to ensure that the corresponding
890    //  data is linearly available at the specified processing rates for the other inputs,
891    //  and that each of the output buffers has sufficient linearly available space
892    //  (using overflow areas, if necessary) for the maximum output that can be
893    //  produced.
894
895    kb->CreateBr(doSegmentOuterLoop);
896    kb->SetInsertPoint(doSegmentOuterLoop);
897    PHINode * const stridesRemaining = kb->CreatePHI(kb->getSizeTy(), 2, "stridesRemaining");
898    stridesRemaining->addIncoming(fullStridesToDo, entry);
899
900    // For each input buffer, determine the processedItemCount, the block pointer for the
901    // buffer block containing the next item, and the number of linearly available items.
902
903    Value * processedItemCount[inputSetCount];
904    Value * inputBlockPtr[inputSetCount];
905    Value * linearlyAvailItems[inputSetCount];
906
907    Value * linearlyAvailStrides = stridesRemaining;
908    for (unsigned i = 0; i < inputSetCount; i++) {
909        processedItemCount[i] = kb->getProcessedItemCount(mStreamSetInputs[i].name);
910        inputBlockPtr[i] = kb->getInputStreamBlockPtr(mStreamSetInputs[i].name, kb->getInt32(0));
911        Value * avail = kb->CreateSub(mAvailableItemCount[i], processedItemCount[i]);
912        Value * linearlyAvail = kb->getLinearlyAccessibleItems(mStreamSetInputs[i].name, processedItemCount[i]);
913        linearlyAvailItems[i] = kb->CreateSelect(kb->CreateICmpULT(avail, linearlyAvail), avail, linearlyAvail);
914        auto & rate = mStreamSetInputs[i].rate;
915        if (rate.isUnknownRate()) continue;  // No calculation possible for unknown rates.
916        Value * maxReferenceItems = rate.CreateMaxReferenceItemsCalculation(kb.get(), linearlyAvailItems[i]);
917        Value * maxStrides = kb->CreateUDiv(maxReferenceItems, strideSize);
918        linearlyAvailStrides = kb->CreateSelect(kb->CreateICmpULT(maxStrides, linearlyAvailStrides), maxStrides, linearlyAvailStrides);
919    }
920
921    Value * producedItemCount[outputSetCount];
922    Value * outputBlockPtr[outputSetCount];
923    //  Now determine the linearly writeable blocks, based on available blocks reduced
924    //  by limitations of output buffer space.
925    Value * linearlyWritableStrides = linearlyAvailStrides;
926    for (unsigned i = 0; i < outputSetCount; i++) {
927        producedItemCount[i] = kb->getProducedItemCount(mStreamSetOutputs[i].name);
928        outputBlockPtr[i] = kb->getOutputStreamBlockPtr(mStreamSetOutputs[i].name, kb->getInt32(0));
929       
930        auto & rate = mStreamSetOutputs[i].rate;
931        if (rate.isUnknownRate()) continue;  // No calculation possible for unknown rates.
932        Value * writableItems = kb->getLinearlyWritableItems(mStreamSetOutputs[i].name, producedItemCount[i]);
933        Value * maxReferenceItems = rate.CreateMaxReferenceItemsCalculation(kb.get(), writableItems);
934        Value * maxStrides = kb->CreateUDiv(maxReferenceItems, strideSize);
935        linearlyWritableStrides = kb->CreateSelect(kb->CreateICmpULT(maxStrides, linearlyWritableStrides), maxStrides, linearlyWritableStrides);
936    }
937    Value * const haveFullStrides = kb->CreateICmpUGT(linearlyWritableStrides, kb->getSize(0));
938    kb->CreateCondBr(haveFullStrides, doMultiBlockCall, tempBlockCheck);
939
940    //  At this point we have verified the availability of one or more blocks of input data and output buffer space for all stream sets.
941    //  Now prepare the doMultiBlock call.
942    kb->SetInsertPoint(doMultiBlockCall);
943
944    Value * principalItemsToDo = kb->CreateMul(linearlyWritableStrides, strideSize);
945
946    std::vector<Value *> doMultiBlockArgs;
947    doMultiBlockArgs.push_back(getInstance());
948    doMultiBlockArgs.push_back(principalItemsToDo);
949    for (unsigned i = 1; i < mStreamSetInputs.size(); i++) {
950        if (!mIsDerived[i]) {
951            doMultiBlockArgs.push_back(linearlyAvailItems[i]);
952        }
953    }
954    for (unsigned i = 0; i < mStreamSetInputs.size(); i++) {
955        Value * bufPtr = kb->CreatePointerCast(inputBlockPtr[i], mStreamSetInputBuffers[i]->getPointerType());
956        doMultiBlockArgs.push_back(bufPtr);
957    }
958    for (unsigned i = 0; i < mStreamSetOutputs.size(); i++) {
959        Value * bufPtr = kb->CreatePointerCast(outputBlockPtr[i], mStreamSetOutputBuffers[i]->getPointerType());
960        doMultiBlockArgs.push_back(bufPtr);
961    }
962
963    kb->CreateCall(multiBlockFunction, doMultiBlockArgs);
964
965    // Do copybacks if necessary.
966    for (unsigned i = 0; i < mStreamSetOutputs.size(); i++) {
967        if (mStreamSetOutputBuffers[i]->supportsCopyBack()) {
968            Value * newProduced = kb->getProducedItemCount(mStreamSetOutputs[i].name);
969            Value * handle = mStreamSetOutputBuffers[i]->getStreamSetHandle();
970            mStreamSetOutputBuffers[i]->genCopyBackLogic(kb.get(), handle, producedItemCount[i], newProduced, mStreamSetOutputs[i].name);
971        }
972    }
973
974    if (mIsDerived[0]) {
975        Value * reducedStridesToDo = kb->CreateSub(stridesRemaining, linearlyWritableStrides);
976        stridesRemaining->addIncoming(reducedStridesToDo, kb->GetInsertBlock());
977        Value * nowProcessed = kb->CreateAdd(processedItemCount[0], principalItemsToDo);
978        kb->setProcessedItemCount(mStreamSetInputs[0].name, nowProcessed);
979        kb->CreateBr(doSegmentOuterLoop);
980    }
981    else {
982        // Processed item count updated by the kernel itself.
983        Value * nowProcessed = kb->getProcessedItemCount(mStreamSetInputs[0].name);
984        Value * remainingItemsToDo = kb->CreateSub(itemsAvail, nowProcessed);
985        Value * reducedStridesToDo = kb->CreateUDiv(remainingItemsToDo, nowProcessed);
986        stridesRemaining->addIncoming(reducedStridesToDo, kb->GetInsertBlock());
987        // If we didn't make progress, we have gone as far as we can in this segment.
988        kb->CreateCondBr(kb->CreateICmpUGT(nowProcessed, processedItemCount[0]), doSegmentOuterLoop, segmentDone);
989    }
990
991    //
992    // We use temporary buffers in 3 different cases that preclude full block processing.
993    // (a) One or more input buffers does not have a sufficient number of input items linearly available.
994    // (b) One or more output buffers does not have sufficient linearly available buffer space.
995    // (c) We have processed all the full blocks of input and only the excessItems remain.
996    // In each case we set up temporary buffers for input and output and then
997    // call the Multiblock routine.
998    //
999
1000    kb->SetInsertPoint(tempBlockCheck);
1001    Value * const haveStrides = kb->CreateICmpUGT(stridesRemaining, kb->getSize(0));
1002    kb->CreateCondBr(kb->CreateOr(mIsFinal, haveStrides), doTempBufferBlock, segmentDone);
1003
1004    kb->SetInsertPoint(doTempBufferBlock);
1005    Value * excessItems = kb->CreateSub(itemsAvail, kb->getProcessedItemCount(mStreamSetInputs[0].name));
1006    Value * tempBlockItems = kb->CreateSelect(haveStrides, strideSize, excessItems);
1007    Value * doFinal = kb->CreateNot(haveStrides);
1008
1009    // Begin constructing the doMultiBlock args.
1010    std::vector<Value *> tempArgs;
1011    tempArgs.push_back(getInstance());
1012    tempArgs.push_back(tempBlockItems);
1013    // For non-derived inputs, add the available items.
1014    for (unsigned i = 1; i < mStreamSetInputs.size(); i++) {
1015        if (!mIsDerived[i]) {
1016            Value * avail = kb->CreateSub(mAvailableItemCount[i], processedItemCount[i]);
1017            tempArgs.push_back(kb->CreateSelect(kb->CreateICmpULT(avail, strideSize), avail, strideSize));
1018        }
1019    }
1020    //
1021    // Define and allocate the temporary buffer area.
1022    //
1023    Type * tempBuffers[totalSetCount];
1024    for (unsigned i = 0; i < inputSetCount; ++i) {
1025        Type * bufType = mStreamSetInputBuffers[i]->getStreamSetBlockType();
1026        tempBuffers[i] = ArrayType::get(bufType, maxBlocksToCopy[i]);
1027    }
1028    for (unsigned i = 0; i < outputSetCount; i++) {
1029        Type * bufType = mStreamSetOutputBuffers[i]->getStreamSetBlockType();
1030        tempBuffers[i + inputSetCount] = ArrayType::get(bufType, maxBlocksToCopy[i + inputSetCount]);
1031    }
1032    Type * tempParameterStructType = StructType::create(kb->getContext(), ArrayRef<Type *>(tempBuffers, totalSetCount), "tempBuf");
1033    // Prepare the temporary buffer area.
1034    Value * tempParameterArea = kb->CreateCacheAlignedAlloca(tempParameterStructType);
1035    kb->CreateMemZero(tempParameterArea, ConstantExpr::getSizeOf(tempParameterStructType));
1036    // For each input and output buffer, copy over necessary data starting from the last block boundary.
1037    Value * itemCountNeeded[inputSetCount];
1038    itemCountNeeded[0] = tempBlockItems;
1039    Value * finalItemCountNeeded[inputSetCount];
1040
1041    for (unsigned i = 0; i < inputSetCount; i++) {
1042        Type * bufPtrType = mStreamSetInputBuffers[i]->getPointerType();
1043        if (mItemsPerStride[i] != 0) {
1044            Value * tempBufPtr = kb->CreateGEP(tempParameterArea, {kb->getInt32(0), kb->getInt32(i)});
1045            tempBufPtr = kb->CreatePointerCast(tempBufPtr, bufPtrType);
1046            ConstantInt * strideItems = kb->getSize(mItemsPerStride[i]);
1047            Value * strideBasePos = kb->CreateSub(processedItemCount[i], kb->CreateURem(processedItemCount[i], strideItems));
1048            Value * blockBasePos = strideBasePos;
1049            if (mItemsPerStride[i] & (bitBlockWidth - 1)) {
1050                blockBasePos = kb->CreateAnd(strideBasePos, blockBaseMask);
1051            }
1052
1053            // The number of items to copy is determined by the processing rate requirements.
1054            if (i >= 1) {
1055                auto & rate = mStreamSetInputs[i].rate;
1056                std::string refSet = mStreamSetInputs[i].rate.referenceStreamSet();
1057                Port port; unsigned ssIdx;
1058                std::tie(port, ssIdx) = getStreamPort(refSet);
1059                itemCountNeeded[i] = rate.CreateRatioCalculation(kb.get(), itemCountNeeded[ssIdx], doFinal);
1060            }
1061            finalItemCountNeeded[i] = kb->CreateAdd(itemCountNeeded[i], processedItemCount[i]);
1062
1063            Value * inputPtr = kb->CreatePointerCast(kb->getRawInputPointer(mStreamSetInputs[i].name, kb->getInt32(0), blockBasePos), bufPtrType);
1064           
1065            if (maxBlocksToCopy[i] == 1) {
1066                // copy one block
1067                mStreamSetInputBuffers[i]->createBlockCopy(kb.get(), tempBufPtr, inputPtr, kb->getSize(1));
1068            }
1069            else {
1070                Value * neededItems = kb->CreateSub(finalItemCountNeeded[i], blockBasePos);
1071                Value * availFromBase = kb->getLinearlyAccessibleItems(mStreamSetInputs[i].name, blockBasePos);
1072                Value * allAvail = kb->CreateICmpULE(neededItems, availFromBase);
1073                Value * copyItems1 = kb->CreateSelect(allAvail, neededItems, availFromBase);
1074                //mStreamSetInputBuffers[i]->createBlockAlignedCopy(kb.get(), tempBufPtr, inputPtr, copyItems1);
1075                Value * copyBlocks1 = kb->CreateUDivCeil(copyItems1, blockSize);
1076                mStreamSetInputBuffers[i]->createBlockCopy(kb.get(), tempBufPtr, inputPtr, copyBlocks1);
1077                BasicBlock * copyRemaining = kb->CreateBasicBlock("copyRemaining");
1078                BasicBlock * copyDone = kb->CreateBasicBlock("copyDone");
1079                kb->CreateCondBr(allAvail, copyDone, copyRemaining);
1080                kb->SetInsertPoint(copyRemaining);
1081                Value * copyItems2 = kb->CreateSub(neededItems, copyItems1);
1082                Value * copyBlocks2 = kb->CreateUDivCeil(copyItems2, blockSize);
1083                //Value * nextBasePos = kb->CreateAdd(blockBasePos, copyItems1);
1084                Value * nextBasePos = kb->CreateAdd(blockBasePos, kb->CreateMul(copyBlocks2, blockSize));
1085                Value * nextInputPtr = kb->CreatePointerCast(kb->getRawInputPointer(mStreamSetInputs[i].name, kb->getInt32(0), nextBasePos), bufPtrType);
1086                Value * nextBufPtr = kb->CreateGEP(tempBufPtr, kb->CreateUDiv(copyItems1, blockSize));
1087                //mStreamSetInputBuffers[i]->createBlockAlignedCopy(kb.get(), nextBufPtr, nextInputPtr, copyItems2);
1088                mStreamSetInputBuffers[i]->createBlockCopy(kb.get(), nextBufPtr, nextInputPtr, copyBlocks2);
1089                kb->CreateBr(copyDone);
1090                kb->SetInsertPoint(copyDone);
1091            }
1092            tempArgs.push_back(tempBufPtr);
1093        } else {
1094            Value * bufPtr = kb->getInputStreamBlockPtr(mStreamSetInputs[i].name, kb->getInt32(0));
1095            bufPtr = kb->CreatePointerCast(bufPtr, mStreamSetInputBuffers[i]->getPointerType());
1096            tempArgs.push_back(bufPtr);           
1097        }
1098    }
1099    Value * outputBasePos[outputSetCount];
1100    for (unsigned i = 0; i < outputSetCount; i++) {
1101        Value * tempBufPtr = kb->CreateGEP(tempParameterArea,  {kb->getInt32(0), kb->getInt32(inputSetCount + i)});
1102        Type * bufPtrType = mStreamSetOutputBuffers[i]->getPointerType();
1103        tempBufPtr = kb->CreatePointerCast(tempBufPtr, bufPtrType);
1104        producedItemCount[i] = kb->getProducedItemCount(mStreamSetOutputs[i].name);
1105        outputBasePos[i] = kb->CreateAnd(producedItemCount[i], blockBaseMask);
1106        //mStreamSetOutputBuffers[i]->createBlockAlignedCopy(kb.get(), tempBufPtr, outputBlockPtr[i], kb->CreateSub(producedItemCount[i], outputBasePos[i]));
1107        Value * copyBlocks = kb->CreateUDivCeil(kb->CreateSub(producedItemCount[i], outputBasePos[i]), blockSize);
1108        mStreamSetOutputBuffers[i]->createBlockCopy(kb.get(), tempBufPtr, outputBlockPtr[i], copyBlocks);
1109        tempArgs.push_back(tempBufPtr);
1110    }
1111
1112    kb->CreateCall(multiBlockFunction, tempArgs);
1113   
1114    //  The items have been processed and output generated to the temporary areas.
1115    //  Update the processed item count (and hence all the counts derived automatically
1116    //  therefrom).
1117    if (mIsDerived[0]) {
1118        kb->setProcessedItemCount(mStreamSetInputs[0].name, finalItemCountNeeded[0]);
1119    }
1120   
1121    // Copy back data to the actual output buffers.
1122    for (unsigned i = 0; i < mStreamSetOutputBuffers.size(); i++) {
1123        Value * tempBufPtr = kb->CreateGEP(tempParameterArea,  {kb->getInt32(0), kb->getInt32(mStreamSetInputs.size() + i)});
1124        tempBufPtr = kb->CreatePointerCast(tempBufPtr, mStreamSetOutputBuffers[i]->getPointerType());
1125        Value * finalOutputItems = kb->getProducedItemCount(mStreamSetOutputs[i].name);
1126        Value * copyItems = kb->CreateSub(finalOutputItems, outputBasePos[i]);
1127        // Round up to exact multiple of block size.
1128        //copyItems = kb->CreateAnd(kb->CreateAdd(copyItems, kb->getSize(bitBlockWidth - 1)), blockBaseMask);
1129        Value * writableFromBase = kb->getLinearlyWritableItems(mStreamSetOutputs[i].name, outputBasePos[i]); // must be a whole number of blocks.
1130        Value * allWritable = kb->CreateICmpULE(copyItems, writableFromBase);
1131        Value * copyItems1 = kb->CreateSelect(allWritable, copyItems, writableFromBase);
1132        //mStreamSetOutputBuffers[i]->createBlockAlignedCopy(kb.get(), outputBlockPtr[i], tempBufPtr, copyItems1);
1133        Value * copyBlocks1 = kb->CreateUDivCeil(copyItems1, blockSize);
1134        mStreamSetOutputBuffers[i]->createBlockCopy(kb.get(), outputBlockPtr[i], tempBufPtr, copyBlocks1);
1135        BasicBlock * copyBackRemaining = kb->CreateBasicBlock("copyBackRemaining");
1136        BasicBlock * copyBackDone = kb->CreateBasicBlock("copyBackDone");
1137        kb->CreateCondBr(allWritable, copyBackDone, copyBackRemaining);
1138        kb->SetInsertPoint(copyBackRemaining);
1139        Value * copyItems2 = kb->CreateSub(copyItems, copyItems1);
1140        Value * nextBasePos = kb->CreateAdd(outputBasePos[i], copyItems1);
1141        Type * bufPtrType = mStreamSetOutputBuffers[i]->getPointerType();
1142        Value * nextOutputPtr = kb->CreatePointerCast(kb->getRawOutputPointer(mStreamSetOutputs[i].name, kb->getInt32(0), nextBasePos), bufPtrType);
1143        tempBufPtr = kb->CreateGEP(tempBufPtr, kb->CreateUDiv(copyItems1, blockSize));
1144        //mStreamSetOutputBuffers[i]->createBlockAlignedCopy(kb.get(), nextOutputPtr, tempBufPtr, copyItems2);
1145        Value * copyBlocks2 = kb->CreateUDivCeil(copyItems2, blockSize);
1146        mStreamSetOutputBuffers[i]->createBlockCopy(kb.get(), nextOutputPtr, tempBufPtr, copyBlocks2);
1147        kb->CreateBr(copyBackDone);
1148        kb->SetInsertPoint(copyBackDone);
1149    }
1150
1151    //  We've dealt with the partial block processing and copied information back into the
1152    //  actual buffers.  If this isn't the final block, loop back for more multiblock processing.
1153    //
1154    BasicBlock * setTermination = kb->CreateBasicBlock("mBsetTermination");
1155    if (mIsDerived[0]) {
1156        stridesRemaining->addIncoming(kb->CreateSub(stridesRemaining, kb->CreateZExt(haveStrides, kb->getSizeTy())), kb->GetInsertBlock());
1157        kb->CreateCondBr(haveStrides, doSegmentOuterLoop, setTermination);
1158    }
1159    else {
1160        Value * nowProcessed = kb->getProcessedItemCount(mStreamSetInputs[0].name);
1161        Value * remainingItemsToDo = kb->CreateSub(itemsAvail, nowProcessed);
1162        Value * reducedStridesToDo = kb->CreateUDiv(remainingItemsToDo, nowProcessed);
1163        stridesRemaining->addIncoming(reducedStridesToDo, kb->GetInsertBlock());
1164        Value * haveStrides = kb->CreateICmpUGT(reducedStridesToDo, kb->getSize(0));
1165        kb->CreateCondBr(haveStrides, doSegmentOuterLoop, setTermination);
1166    }   
1167    kb->SetInsertPoint(setTermination);
1168    kb->setTerminationSignal();
1169    kb->CreateBr(segmentDone);
1170    kb->SetInsertPoint(segmentDone);
1171}
1172
1173void Kernel::finalizeInstance(const std::unique_ptr<KernelBuilder> & idb) {
1174    assert ("KernelBuilder does not have a valid IDISA Builder" && idb);
1175    mOutputScalarResult = idb->CreateCall(getTerminateFunction(idb->getModule()), { getInstance() });
1176}
1177
1178Kernel::StreamPort Kernel::getStreamPort(const std::string & name) const {
1179    const auto f = mStreamMap.find(name);
1180    if (LLVM_UNLIKELY(f == mStreamMap.end())) {
1181        report_fatal_error(getName() + " does not contain stream set " + name);
1182    }
1183    return f->second;
1184}
1185
1186static inline std::string annotateKernelNameWithDebugFlags(std::string && name) {
1187    if (codegen::EnableAsserts) {
1188        name += "_EA";
1189    }
1190    name += "_O" + std::to_string((int)codegen::OptLevel);
1191    return name;
1192}
1193
1194// CONSTRUCTOR
1195Kernel::Kernel(std::string && kernelName,
1196               std::vector<Binding> && stream_inputs,
1197               std::vector<Binding> && stream_outputs,
1198               std::vector<Binding> && scalar_parameters,
1199               std::vector<Binding> && scalar_outputs,
1200               std::vector<Binding> && internal_scalars)
1201: KernelInterface(annotateKernelNameWithDebugFlags(std::move(kernelName))
1202                  , std::move(stream_inputs), std::move(stream_outputs)
1203                  , std::move(scalar_parameters), std::move(scalar_outputs)
1204                  , std::move(internal_scalars))
1205, mCurrentMethod(nullptr)
1206, mNoTerminateAttribute(false)
1207, mIsGenerated(false)
1208, mIsFinal(nullptr)
1209, mOutputScalarResult(nullptr)
1210, mStride(0) {
1211
1212}
1213
1214Kernel::~Kernel() {
1215
1216}
1217
1218// CONSTRUCTOR
1219BlockOrientedKernel::BlockOrientedKernel(std::string && kernelName,
1220                                         std::vector<Binding> && stream_inputs,
1221                                         std::vector<Binding> && stream_outputs,
1222                                         std::vector<Binding> && scalar_parameters,
1223                                         std::vector<Binding> && scalar_outputs,
1224                                         std::vector<Binding> && internal_scalars)
1225: Kernel(std::move(kernelName), std::move(stream_inputs), std::move(stream_outputs), std::move(scalar_parameters), std::move(scalar_outputs), std::move(internal_scalars))
1226, mDoBlockMethod(nullptr)
1227, mStrideLoopBody(nullptr)
1228, mStrideLoopBranch(nullptr)
1229, mStrideLoopTarget(nullptr) {
1230
1231}
1232
1233// CONSTRUCTOR
1234MultiBlockKernel::MultiBlockKernel(std::string && kernelName,
1235                                   std::vector<Binding> && stream_inputs,
1236                                   std::vector<Binding> && stream_outputs,
1237                                   std::vector<Binding> && scalar_parameters,
1238                                   std::vector<Binding> && scalar_outputs,
1239                                   std::vector<Binding> && internal_scalars)
1240: Kernel(std::move(kernelName), std::move(stream_inputs), std::move(stream_outputs), std::move(scalar_parameters), std::move(scalar_outputs), std::move(internal_scalars)) {
1241}
1242
1243// CONSTRUCTOR
1244SegmentOrientedKernel::SegmentOrientedKernel(std::string && kernelName,
1245                                             std::vector<Binding> && stream_inputs,
1246                                             std::vector<Binding> && stream_outputs,
1247                                             std::vector<Binding> && scalar_parameters,
1248                                             std::vector<Binding> && scalar_outputs,
1249                                             std::vector<Binding> && internal_scalars)
1250: Kernel(std::move(kernelName), std::move(stream_inputs), std::move(stream_outputs), std::move(scalar_parameters), std::move(scalar_outputs), std::move(internal_scalars)) {
1251   
1252}
1253 
1254   
1255void applyOutputBufferExpansions(const std::unique_ptr<KernelBuilder> & kb,
1256                                 std::vector<Value *> inputAvailable,
1257                                 Value * doFinal) {
1258    auto kernel = kb->getKernel();
1259    const unsigned inputSetCount = inputAvailable.size();
1260    if (inputSetCount == 0) return;  //  Cannot calculate buffer items expected from input.
1261    auto & outputs = kernel->getStreamSetOutputBuffers();
1262    const unsigned outputSetCount = outputs.size();
1263
1264    Constant * blockSize = kb->getSize(kb->getBitBlockWidth());
1265    Value * newlyAvailInputItems[inputSetCount];
1266    Value * requiredOutputBufferSpace[outputSetCount];
1267    for (unsigned i = 0; i < inputSetCount; i++) {
1268        Value * processed = kb->getProcessedItemCount(kernel->getStreamInput(i).name);
1269        newlyAvailInputItems[i] = kb->CreateSub(inputAvailable[i], processed);
1270    }
1271    //kb->GetInsertBlock()->dump();
1272    for (unsigned i = 0; i < outputSetCount; i++) {
1273        const auto & rate = kernel->getStreamOutput(i).rate;
1274        if (rate.isUnknownRate()) continue;  // No calculations possible.
1275        Kernel::Port port; unsigned ssIdx;
1276        std::tie(port, ssIdx) = kernel->getStreamPort(rate.referenceStreamSet());
1277        Value * base = nullptr;
1278        if (port == Kernel::Port::Output) {
1279            base = requiredOutputBufferSpace[ssIdx]; assert (base);
1280        } else {
1281            base = newlyAvailInputItems[ssIdx]; assert (base);
1282        }
1283        requiredOutputBufferSpace[i] = rate.CreateRatioCalculation(kb.get(), base, doFinal);
1284        if (auto db = dyn_cast<DynamicBuffer>(outputs[i])) {
1285            Value * handle = db->getStreamSetHandle();
1286            // This buffer can be expanded.
1287            Value * producedBlock = kb->CreateUDivCeil(kb->getProducedItemCount(kernel->getStreamOutput(i).name), blockSize);
1288            Value * consumedBlock = kb->CreateUDiv(kb->getConsumedItemCount(kernel->getStreamOutput(i).name), blockSize);
1289            Value * blocksInUse = kb->CreateSub(producedBlock, consumedBlock);
1290            Value * blocksRequired = kb->CreateAdd(blocksInUse, kb->CreateUDivCeil(requiredOutputBufferSpace[i], blockSize));
1291            Value * spaceRequired = kb->CreateMul(blocksRequired, blockSize);
1292            Value * expansionNeeded = kb->CreateICmpUGT(spaceRequired, db->getBufferedSize(kb.get(), handle));
1293            BasicBlock * doExpand = kb->CreateBasicBlock("doExpand");
1294            BasicBlock * bufferReady = kb->CreateBasicBlock("bufferReady");
1295            kb->CreateCondBr(expansionNeeded, doExpand, bufferReady);
1296            kb->SetInsertPoint(doExpand);
1297            db->doubleCapacity(kb.get(), handle);
1298            // Ensure that capacity is sufficient by successive doubling, if necessary.
1299            expansionNeeded = kb->CreateICmpUGT(spaceRequired, db->getBufferedSize(kb.get(), handle));
1300            kb->CreateCondBr(expansionNeeded, doExpand, bufferReady);
1301            kb->SetInsertPoint(bufferReady);
1302        }
1303    }
1304
1305}
1306
1307}
Note: See TracBrowser for help on using the repository browser.