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

Last change on this file since 4991 was 4991, checked in by nmedfort, 4 years ago

Symbol table work and untested kernel instatiate method for multiple input streams

File size: 21.2 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 <pablo/function.h>
8#include <IDISA/idisa_builder.h>
9#include <kernels/instance.h>
10#include <tuple>
11#include <boost/functional/hash_fwd.hpp>
12#include <unordered_map>
13
14using namespace llvm;
15using namespace pablo;
16
17inline bool isPowerOfTwo(const unsigned x) {
18    return (x != 0) && (x & (x - 1)) == 0;
19}
20
21namespace kernel {
22
23enum : unsigned {
24    INTERNAL_STATE = 0
25    , INPUT_STREAM_SET = 1
26    , OUTPUT_STREAM_SET = 2
27    , OUTPUT_SCALAR_SET = 3
28};
29
30// sets name & sets internal state to the kernel superclass state
31KernelBuilder::KernelBuilder(std::string name, Module * m, IDISA::IDISA_Builder * b, const unsigned bufferSize)
32: mMod(m)
33, iBuilder(b)
34, mKernelName(name)
35, mBitBlockType(b->getBitBlockType())
36, mBufferSize(bufferSize)
37, mBlockNoIndex(0) {
38    assert (mBufferSize > 0);
39    mBlockNoIndex = addInternalState(b->getInt64Ty(), "BlockNo");
40}
41
42SlabAllocator<Instance> Instance::mAllocator; // static allocator declaration; should probably be in a "instance.cpp"
43
44/** ------------------------------------------------------------------------------------------------------------- *
45 * @brief addInternalState
46 ** ------------------------------------------------------------------------------------------------------------- */
47unsigned KernelBuilder::addInternalState(Type * const type) {
48    assert (type);
49    const unsigned index = mInternalState.size();
50    mInternalState.push_back(type);
51    return index;
52}
53
54unsigned KernelBuilder::addInternalState(llvm::Type * const type, std::string && name) {
55    if (LLVM_UNLIKELY(mInternalStateNameMap.count(name) != 0)) {
56        throw std::runtime_error("Kernel already contains internal state '" + name + "'");
57    }
58    const unsigned index = addInternalState(type);
59    mInternalStateNameMap.emplace(name, index);
60    return index;
61}
62
63/** ------------------------------------------------------------------------------------------------------------- *
64 * @brief getInternalState
65 ** ------------------------------------------------------------------------------------------------------------- */
66Value * KernelBuilder::getInternalState(Value * const instance, const unsigned index) {
67    Value* indices[] = {iBuilder->getInt64(0),
68                        iBuilder->getInt32(INTERNAL_STATE),
69                        iBuilder->getInt32(index)};
70    return iBuilder->CreateGEP(instance, indices);
71}
72
73Value * KernelBuilder::getInternalState(Value * const instance, const std::string & name) {
74    const auto f = mInternalStateNameMap.find(name);
75    if (LLVM_UNLIKELY(f == mInternalStateNameMap.end())) {
76        throw std::runtime_error("Kernel does not contain internal state " + name);
77    }
78    return getInternalState(instance, f->second);
79}
80
81/** ------------------------------------------------------------------------------------------------------------- *
82 * @brief setInternalState
83 ** ------------------------------------------------------------------------------------------------------------- */
84void KernelBuilder::setInternalState(Value * const instance, const std::string & name, Value * const value) {
85    Value * ptr = getInternalState(instance, name);
86    assert (ptr->getType()->getPointerElementType() == value->getType());
87    if (value->getType() == iBuilder->getBitBlockType()) {
88        iBuilder->CreateBlockAlignedStore(value, ptr);
89    } else {
90        iBuilder->CreateStore(value, ptr);
91    }
92}
93
94void KernelBuilder::setInternalState(Value * const instance, const unsigned index, Value * const value) {
95    Value * ptr = getInternalState(instance, index);
96    assert (ptr->getType()->getPointerElementType() == value->getType());
97    if (value->getType() == iBuilder->getBitBlockType()) {
98        iBuilder->CreateBlockAlignedStore(value, ptr);
99    } else {
100        iBuilder->CreateStore(value, ptr);
101    }
102}
103
104/** ------------------------------------------------------------------------------------------------------------- *
105 * @brief addInputStream
106 ** ------------------------------------------------------------------------------------------------------------- */
107void KernelBuilder::addInputStream(const unsigned fields, std::string && name) {
108    assert (fields > 0 && !name.empty());
109    mInputStreamName.push_back(name);
110    if (fields == 1) {
111        mInputStream.push_back(mBitBlockType);
112    } else {
113        mInputStream.push_back(ArrayType::get(mBitBlockType, fields));
114    }
115}
116
117void KernelBuilder::addInputStream(const unsigned fields) {
118    addInputStream(fields, std::move(mKernelName + "_InputStream_" + std::to_string(mInputStream.size())));
119}
120
121/** ------------------------------------------------------------------------------------------------------------- *
122 * @brief getInputStream
123 ** ------------------------------------------------------------------------------------------------------------- */
124Value * KernelBuilder::getInputStream(Value * const instance, const unsigned index, const unsigned streamOffset) {
125    assert (instance);
126    assert (index < mInputStream.size());
127    Value * inputStream = iBuilder->CreateLoad(iBuilder->CreateGEP(instance,
128        {iBuilder->getInt32(0), iBuilder->getInt32(INPUT_STREAM_SET), iBuilder->getInt32(0)}));
129    Value * modFunction = iBuilder->CreateLoad(iBuilder->CreateGEP(instance,
130        {iBuilder->getInt32(0), iBuilder->getInt32(INPUT_STREAM_SET), iBuilder->getInt32(1)}));
131    Value * offset = iBuilder->CreateLoad(getBlockNo(instance));
132    if (streamOffset) {
133        offset = iBuilder->CreateAdd(offset, ConstantInt::get(offset->getType(), streamOffset));
134    }   
135    return iBuilder->CreateGEP(inputStream, { iBuilder->CreateCall(modFunction, offset), iBuilder->getInt32(index) });
136}
137
138/** ------------------------------------------------------------------------------------------------------------- *
139 * @brief addInputScalar
140 ** ------------------------------------------------------------------------------------------------------------- */
141void KernelBuilder::addInputScalar(Type * const type, std::string && name) {
142    assert (type && !name.empty());
143    mInputScalarName.push_back(name);
144    mInputScalar.push_back(type);
145}
146
147void KernelBuilder::addInputScalar(Type * const type) {
148    addInputScalar(type, std::move(mKernelName + "_InputScalar_" + std::to_string(mInputScalar.size())));
149}
150
151/** ------------------------------------------------------------------------------------------------------------- *
152 * @brief getInputScalar
153 ** ------------------------------------------------------------------------------------------------------------- */
154Value * KernelBuilder::getInputScalar(Value * const instance, const unsigned) {
155    throw std::runtime_error("currently not supported!");
156}
157
158/** ------------------------------------------------------------------------------------------------------------- *
159 * @brief addOutputStream
160 ** ------------------------------------------------------------------------------------------------------------- */
161unsigned KernelBuilder::addOutputStream(const unsigned fields) {
162    assert (fields > 0);
163    const unsigned index = mOutputStream.size();
164    mOutputStream.push_back((fields == 1) ? mBitBlockType : ArrayType::get(mBitBlockType, fields));
165    return index;
166}
167
168/** ------------------------------------------------------------------------------------------------------------- *
169 * @brief addOutputScalar
170 ** ------------------------------------------------------------------------------------------------------------- */
171unsigned KernelBuilder::addOutputScalar(Type * const type) {
172    assert (type);
173    const unsigned index = mOutputScalar.size();
174    mOutputScalar.push_back(type);
175    return index;
176}
177
178/** ------------------------------------------------------------------------------------------------------------- *
179 * @brief getOutputStream
180 ** ------------------------------------------------------------------------------------------------------------- */
181Value * KernelBuilder::getOutputStream(Value * const instance, const unsigned index, const unsigned streamOffset) {
182    assert (instance);
183    Value * const offset = getOffset(instance, streamOffset);
184    Value * const indices[] = {iBuilder->getInt32(0), iBuilder->getInt32(OUTPUT_STREAM_SET), offset, iBuilder->getInt32(index)};
185    return iBuilder->CreateGEP(instance, indices);
186}
187
188/** ------------------------------------------------------------------------------------------------------------- *
189 * @brief getOutputScalar
190 ** ------------------------------------------------------------------------------------------------------------- */
191Value * KernelBuilder::getOutputScalar(Value * const instance, const unsigned) {
192    throw std::runtime_error("currently not supported!");
193}
194
195/** ------------------------------------------------------------------------------------------------------------- *
196 * @brief prepareFunction
197 ** ------------------------------------------------------------------------------------------------------------- */
198Function * KernelBuilder::prepareFunction() {
199
200    PointerType * modFunctionType = PointerType::get(FunctionType::get(iBuilder->getInt64Ty(), {iBuilder->getInt64Ty()}, false), 0);
201    mInputStreamType = PointerType::get(StructType::get(mMod->getContext(), mInputStream), 0);
202    mInputScalarType = PointerType::get(StructType::get(mMod->getContext(), mInputScalar), 0);
203    mOutputStreamType = StructType::get(mMod->getContext(), mOutputStream);
204    Type * outputScalarType = StructType::get(mMod->getContext(), mOutputScalar);
205    Type * internalStateType = StructType::create(mMod->getContext(), mInternalState);
206    Type * inputStateType = StructType::create(mMod->getContext(), { mInputStreamType, modFunctionType});
207
208    Type * outputBufferType = ArrayType::get(mOutputStreamType, mBufferSize);
209    mKernelStateType = StructType::create(mMod->getContext(), {internalStateType, inputStateType, outputBufferType, outputScalarType}, mKernelName);
210
211    FunctionType * const functionType = FunctionType::get(iBuilder->getVoidTy(), {PointerType::get(mKernelStateType, 0)}, false);
212    mDoBlock = Function::Create(functionType, GlobalValue::ExternalLinkage, mKernelName + "_DoBlock", mMod);
213    mDoBlock->setCallingConv(CallingConv::C);   
214    mDoBlock->setDoesNotCapture(1);
215    mDoBlock->setDoesNotThrow();
216
217    Function::arg_iterator args = mDoBlock->arg_begin();
218    mKernelState = args++;
219    mKernelState->setName("this");
220
221    iBuilder->SetInsertPoint(BasicBlock::Create(mMod->getContext(), "entry", mDoBlock, 0));
222
223    return mDoBlock;
224}
225
226/** ------------------------------------------------------------------------------------------------------------- *
227 * @brief finalize
228 ** ------------------------------------------------------------------------------------------------------------- */
229void KernelBuilder::finalize() {
230
231    // Finish the actual function
232    Value * blockNo = getBlockNo();
233    Value * value = iBuilder->CreateLoad(blockNo);
234    value = iBuilder->CreateAdd(value, ConstantInt::get(value->getType(), 1));
235    iBuilder->CreateStore(value, blockNo);
236    iBuilder->CreateRetVoid();
237
238    eliminateRedundantMemoryOperations(mDoBlock);
239
240    // Generate the zero initializer
241    PointerType * modFunctionType = PointerType::get(FunctionType::get(iBuilder->getInt64Ty(), {iBuilder->getInt64Ty()}, false), 0);
242    FunctionType * constructorType = FunctionType::get(iBuilder->getVoidTy(), {PointerType::get(mKernelStateType, 0), mInputStreamType, modFunctionType}, false);
243
244    mConstructor = Function::Create(constructorType, GlobalValue::ExternalLinkage, mKernelName + "_Constructor", mMod);
245    mConstructor->setCallingConv(CallingConv::C);
246    mDoBlock->setDoesNotCapture(1);
247    mConstructor->addAttribute(AttributeSet::FunctionIndex, Attribute::InlineHint);
248    mDoBlock->setDoesNotThrow();
249
250    auto args = mConstructor->arg_begin();
251    mKernelState = args++;
252    mKernelState->setName("this");
253    Value * const inputStream = args++;
254    inputStream->setName("inputStream");
255    Value * const modFunction = args++;
256    modFunction->setName("modFunction");
257
258    iBuilder->SetInsertPoint(BasicBlock::Create(mMod->getContext(), "entry", mConstructor, 0));
259    for (unsigned i = 0; i < mInternalState.size(); ++i) {
260        Type * const type = mInternalState[i];
261        if (type->isIntegerTy() || type->isArrayTy() || type->isVectorTy()) {
262            setInternalState(i, Constant::getNullValue(type));
263        } else {
264            Value * const ptr = getInternalState(i);
265            Value * const size = iBuilder->CreatePtrDiff(iBuilder->CreateGEP(ptr, iBuilder->getInt32(1)), ptr);
266            iBuilder->CreateMemSet(ptr, iBuilder->getInt8(0), size, 4);
267        }
268    }
269
270    Value * const input = iBuilder->CreateGEP(mKernelState, {iBuilder->getInt32(0), iBuilder->getInt32(INPUT_STREAM_SET)});
271    iBuilder->CreateStore(inputStream, iBuilder->CreateGEP(input, {iBuilder->getInt32(0), iBuilder->getInt32(0)}));
272    iBuilder->CreateStore(modFunction, iBuilder->CreateGEP(input, {iBuilder->getInt32(0), iBuilder->getInt32(1)}));
273    iBuilder->CreateRetVoid();
274
275//    if (mOutputStreamType->getStructNumElements()) {
276//        PointerType * outputStreamType = PointerType::get(mOutputStreamType, 0);
277//        FunctionType * type = FunctionType::get(outputStreamType, {outputStreamType, PointerType::get(blockNo->getType(), 0)}, false);
278//        mStreamSetFunction = Function::Create(type, Function::ExternalLinkage, mKernelName + "_StreamSet", mMod);
279//        auto arg = mStreamSetFunction->arg_begin();
280//        Value * stream = arg++;
281//        stream->setName("stream");
282//        mStreamSetFunction->addAttribute(1, Attribute::NoCapture);
283//        mStreamSetFunction->addAttribute(2, Attribute::NoCapture);
284//        mStreamSetFunction->addAttribute(AttributeSet::FunctionIndex, Attribute::InlineHint);
285//        mStreamSetFunction->addAttribute(AttributeSet::FunctionIndex, Attribute::NoUnwind);
286//        Value * offset = arg;
287//        BasicBlock * entry = BasicBlock::Create(mMod->getContext(), "entry", mStreamSetFunction);
288//        iBuilder->SetInsertPoint(entry);
289//        if (mBufferSize != 1) {
290//            offset = iBuilder->CreateLoad(offset);
291//            if (isPowerOfTwo(mBufferSize)) {
292//                offset = iBuilder->CreateAnd(offset, iBuilder->getInt64(mBufferSize - 1));
293//            } else if (mBufferSize > 2) {
294//                offset = iBuilder->CreateURem(offset, iBuilder->getInt64(mBufferSize));
295//            }
296//            stream = iBuilder->CreateGEP(stream, offset);
297//        }
298//        iBuilder->CreateRet(stream);
299//    }
300
301    iBuilder->ClearInsertionPoint();
302}
303
304/** ------------------------------------------------------------------------------------------------------------- *
305 * @brief eliminateRedundantMemoryOperations
306 ** ------------------------------------------------------------------------------------------------------------- */
307inline void KernelBuilder::eliminateRedundantMemoryOperations(Function * const function) {
308
309
310}
311
312/** ------------------------------------------------------------------------------------------------------------- *
313 * @brief instantiate
314 *
315 * Generate a new instance of this kernel and call the default constructor to initialize it
316 ** ------------------------------------------------------------------------------------------------------------- */
317Instance * KernelBuilder::instantiate(std::pair<Value *, unsigned> && inputStream) {
318    AllocaInst * const memory = iBuilder->CreateAlloca(mKernelStateType);
319    Value * const indices[] = {iBuilder->getInt32(0), iBuilder->getInt32(OUTPUT_STREAM_SET)};
320    Value * ptr = iBuilder->CreateGEP(std::get<0>(inputStream), indices);
321    iBuilder->CreateCall3(mConstructor, memory, iBuilder->CreatePointerCast(ptr, mInputStreamType), CreateModFunction(std::get<1>(inputStream)));
322    return new Instance(this, memory);
323}
324
325/** ------------------------------------------------------------------------------------------------------------- *
326 * @brief instantiate
327 *
328 * Generate a new instance of this kernel and call the default constructor to initialize it
329 ** ------------------------------------------------------------------------------------------------------------- */
330Instance * KernelBuilder::instantiate(llvm::Value * const inputStream) {
331    AllocaInst * const memory = iBuilder->CreateAlloca(mKernelStateType);
332    iBuilder->CreateCall3(mConstructor, memory, iBuilder->CreatePointerCast(inputStream, mInputStreamType), CreateModFunction(0));
333    return new Instance(this, memory);
334}
335
336/** ------------------------------------------------------------------------------------------------------------- *
337 * @brief instantiate
338 *
339 * Generate a new instance of this kernel and call the default constructor to initialize it
340 ** ------------------------------------------------------------------------------------------------------------- */
341Instance * KernelBuilder::instantiate(std::initializer_list<llvm::Value *> inputStreams) {
342    if (mInputStreamType->getStructNumElements() != inputStreams.size()) {
343        throw std::runtime_error(mKernelName + ".instantiate expected " + std::to_string(inputStreams.size()) +
344                                 "elements but was given " + std::to_string(mInputStreamType->getStructNumElements()));
345    }
346    AllocaInst * const memory = iBuilder->CreateAlloca(mKernelStateType);
347    AllocaInst * inputStruct = iBuilder->CreateAlloca(mInputStreamType, 0);
348    unsigned i = 0;
349    for (Value * inputStream : inputStreams) {
350        Value * ptr = iBuilder->CreateGEP(inputStruct, { iBuilder->getInt32(0), iBuilder->getInt32(i++)});
351        iBuilder->CreateStore(inputStream, ptr);
352    }
353    iBuilder->CreateCall3(mConstructor, memory, iBuilder->CreatePointerCast(inputStruct, mInputStreamType), CreateModFunction(0));
354    return new Instance(this, memory);
355}
356
357/** ------------------------------------------------------------------------------------------------------------- *
358 * @brief CreateDoBlockCall
359 ** ------------------------------------------------------------------------------------------------------------- */
360void KernelBuilder::CreateDoBlockCall(Value * const instance) {
361    assert (mDoBlock && instance);
362    iBuilder->CreateCall(mDoBlock, instance);
363}
364
365/** ------------------------------------------------------------------------------------------------------------- *
366 * @brief clearOutputStreamSet
367 *
368 * Zero out the i + streamOffset stream set memory, where i is the current stream set indicated by the BlockNo.
369 ** ------------------------------------------------------------------------------------------------------------- */
370void KernelBuilder::clearOutputStreamSet(Value * const instance, const unsigned streamOffset) {
371    Value * const indices[] = {iBuilder->getInt32(0), iBuilder->getInt32(OUTPUT_STREAM_SET), getOffset(instance, streamOffset)};
372    Value * ptr = iBuilder->CreateGEP(instance, indices);
373    unsigned size = 0;
374    for (unsigned i = 0; i < mOutputStreamType->getStructNumElements(); ++i) {
375        size += mOutputStreamType->getStructElementType(i)->getPrimitiveSizeInBits();
376    }
377    iBuilder->CreateMemSet(ptr, iBuilder->getInt8(0), size / 8, 4);
378}
379
380/** ------------------------------------------------------------------------------------------------------------- *
381 * @brief offset
382 *
383 * Compute the stream index of the given offset value.
384 ** ------------------------------------------------------------------------------------------------------------- */
385Value * KernelBuilder::getOffset(Value * const instance, const unsigned value) {
386    Value * offset = nullptr;
387    if (mBufferSize > 1) {
388        offset = iBuilder->CreateLoad(getBlockNo(instance));
389        if (value) {
390            offset = iBuilder->CreateAdd(offset, iBuilder->getInt64(value));
391        }
392        if (isPowerOfTwo(mBufferSize)) {
393            offset = iBuilder->CreateAnd(offset, iBuilder->getInt64(mBufferSize - 1));
394        } else {
395            offset = iBuilder->CreateURem(offset, iBuilder->getInt64(mBufferSize));
396        }
397    } else {
398        offset = iBuilder->getInt64(value);
399    }
400    return offset;
401}
402
403/** ------------------------------------------------------------------------------------------------------------- *
404 * @brief CreateModFunction
405 *
406 * Generate a "modulo" function that dictates the local offset of a given blockNo
407 ** ------------------------------------------------------------------------------------------------------------- */
408inline Function * KernelBuilder::CreateModFunction(const unsigned size) {
409    const std::string name((size == 0) ? "continuous" : "finite" + std::to_string(size));
410    Function * function = mMod->getFunction(name);
411    if (function) {
412        return function;
413    }
414    const auto ip = iBuilder->saveIP();
415    FunctionType * type = FunctionType::get(iBuilder->getInt64Ty(), {iBuilder->getInt64Ty()}, false);
416    function = Function::Create(type, Function::ExternalLinkage, name, mMod);
417    Value * offset = function->arg_begin();
418    offset->setName("index");
419    BasicBlock * entry = BasicBlock::Create(mMod->getContext(), "entry", function);
420    iBuilder->SetInsertPoint(entry);
421    if (size) {
422        if (size == 1) {
423            offset = iBuilder->getInt64(0);
424        } else if (isPowerOfTwo(size)) {
425            offset = iBuilder->CreateAnd(offset, iBuilder->getInt64(size - 1));
426        } else {
427            offset = iBuilder->CreateURem(offset, iBuilder->getInt64(size));
428        }
429    }
430    iBuilder->CreateRet(offset);
431    iBuilder->restoreIP(ip);
432    return function;
433}
434
435} // end of namespace kernel
Note: See TracBrowser for help on using the repository browser.