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

Last change on this file since 4992 was 4992, checked in by nmedfort, 3 years ago

Continued work on symbol table.

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