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

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

Small fix

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