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

Last change on this file since 5505 was 5505, checked in by cameron, 2 years ago

Multi block bug fix

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