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

Last change on this file since 5620 was 5620, checked in by nmedfort, 19 months ago

Bug fixes for multigrep mode. Optional PabloKernel? branch hit counter added. Minor optimizations.

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