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

Last change on this file since 5589 was 5553, checked in by cameron, 23 months ago

mStride must be initialized

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