source: icGREP/icgrep-devel/icgrep/kernels/block_kernel.cpp @ 6135

Last change on this file since 6135 was 5985, checked in by nmedfort, 12 months ago

Restructured MultiBlock? kernel. Removal of Swizzled buffers. Inclusion of PopCount? rates / non-linear access. Modifications to several kernels to better align them with the kernel and pipeline changes.

File size: 14.4 KB
Line 
1/*
2 *  Copyright (c) 2018 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#if LLVM_VERSION_INTEGER < LLVM_VERSION_CODE(4, 0, 0)
16#include <llvm/Bitcode/ReaderWriter.h>
17#else
18#include <llvm/Bitcode/BitcodeWriter.h>
19#endif
20#include <llvm/Transforms/Utils/Local.h>
21#include <kernels/streamset.h>
22#include <sstream>
23#include <kernels/kernel_builder.h>
24#include <boost/math/common_factor.hpp>
25#include <llvm/Support/Debug.h>
26
27using namespace llvm;
28using namespace parabix;
29using namespace boost::math;
30
31namespace kernel {
32
33const auto DO_BLOCK_SUFFIX = "_DoBlock";
34const auto FINAL_BLOCK_SUFFIX = "_FinalBlock";
35
36/** ------------------------------------------------------------------------------------------------------------- *
37 * @brief generateMultiBlockLogic
38 ** ------------------------------------------------------------------------------------------------------------- */
39void BlockOrientedKernel::generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> & b, Value * const numOfBlocks) {
40
41    if (LLVM_UNLIKELY(mStride != b->getBitBlockWidth())) {
42        report_fatal_error(getName() + ": the Stride (" + std::to_string(mStride) + ") of BlockOrientedKernel "
43                           "equal to the BitBlockWidth (" + std::to_string(b->getBitBlockWidth()) + ")");
44    }
45
46    BasicBlock * const entryBlock = b->GetInsertBlock();
47    mStrideLoopBody = b->CreateBasicBlock(getName() + "_strideLoopBody");
48    BasicBlock * const stridesDone = b->CreateBasicBlock(getName() + "_stridesDone");
49    BasicBlock * const doFinalBlock = b->CreateBasicBlock(getName() + "_doFinalBlock");
50    BasicBlock * const segmentDone = b->CreateBasicBlock(getName() + "_segmentDone");
51
52    b->CreateUnlikelyCondBr(mIsFinal, doFinalBlock, mStrideLoopBody);
53
54    /// BLOCK BODY
55
56    b->SetInsertPoint(mStrideLoopBody);
57
58    if (b->supportsIndirectBr()) {
59        Value * const baseTarget = BlockAddress::get(segmentDone);
60        mStrideLoopTarget = b->CreatePHI(baseTarget->getType(), 2, "strideTarget");
61        mStrideLoopTarget->addIncoming(baseTarget, entryBlock);
62    }
63
64    mStrideBlockIndex = b->CreatePHI(b->getSizeTy(), 2);
65    mStrideBlockIndex->addIncoming(b->getSize(0), entryBlock);
66
67    /// GENERATE DO BLOCK METHOD
68
69    writeDoBlockMethod(b);
70
71    Value * const nextStrideBlockIndex = b->CreateAdd(mStrideBlockIndex, b->getSize(1));
72
73    incrementDerivedItemCounts(b);
74
75    BasicBlock * const bodyEnd = b->GetInsertBlock();
76    if (mStrideLoopTarget) {
77        mStrideLoopTarget->addIncoming(mStrideLoopTarget, bodyEnd);
78    }
79    mStrideBlockIndex->addIncoming(nextStrideBlockIndex, bodyEnd);
80    Value * const notDone = b->CreateICmpULT(nextStrideBlockIndex, numOfBlocks);
81    b->CreateCondBr(notDone, mStrideLoopBody, stridesDone);
82
83    stridesDone->moveAfter(bodyEnd);
84
85    /// STRIDE DONE
86
87    b->SetInsertPoint(stridesDone);
88
89    // Now conditionally perform the final block processing depending on the doFinal parameter.
90    if (mStrideLoopTarget) {
91        mStrideLoopBranch = b->CreateIndirectBr(mStrideLoopTarget, 3);
92        mStrideLoopBranch->addDestination(doFinalBlock);
93        mStrideLoopBranch->addDestination(segmentDone);
94    } else {
95        b->CreateUnlikelyCondBr(mIsFinal, doFinalBlock, segmentDone);
96    }
97
98    doFinalBlock->moveAfter(stridesDone);
99
100    /// DO FINAL BLOCK
101
102    b->SetInsertPoint(doFinalBlock);
103
104    writeFinalBlockMethod(b, getRemainingItems(b));
105
106    b->CreateBr(segmentDone);
107
108    segmentDone->moveAfter(b->GetInsertBlock());
109
110    b->SetInsertPoint(segmentDone);
111
112    // Update the branch prediction metadata to indicate that the likely target will be segmentDone
113    if (mStrideLoopTarget) {
114        MDBuilder mdb(b->getContext());
115        const auto destinations = mStrideLoopBranch->getNumDestinations();
116        uint32_t weights[destinations];
117        for (unsigned i = 0; i < destinations; ++i) {
118            weights[i] = (mStrideLoopBranch->getDestination(i) == segmentDone) ? 100 : 1;
119        }
120        ArrayRef<uint32_t> bw(weights, destinations);
121        mStrideLoopBranch->setMetadata(LLVMContext::MD_prof, mdb.createBranchWeights(bw));
122    }
123
124}
125
126/** ------------------------------------------------------------------------------------------------------------- *
127 * @brief getRemainingItems
128 ** ------------------------------------------------------------------------------------------------------------- */
129Value * BlockOrientedKernel::incrementDerivedItemCounts(const std::unique_ptr<KernelBuilder> & b) {
130
131    Value * const nextIndex = b->CreateAdd(mStrideBlockIndex, b->getSize(1));
132
133    mTreatUnsafeKernelOperationsAsErrors = false;
134
135    // Update the processed item counts
136    for (unsigned i = 0; i < mStreamSetInputs.size(); ++i) {
137        const Binding & input = mStreamSetInputs[i];
138        if (hasDerivedItemCount(input)) {
139            const ProcessingRate & rate = input.getRate();
140            Value * offset = nullptr;
141            if (rate.isFixed()) {
142                offset = b->CreateMul(nextIndex, mInputStrideLength[i]);
143            } else { // if (rate.isPopCount() || rate.isNegatedPopCount())
144                offset = getPopCountRateItems(b, rate, nextIndex);
145            }
146            Value * const processed = b->CreateAdd(mInitialProcessedItemCount[i], offset);
147            b->setNonDeferredProcessedItemCount(input, processed);
148        }
149    }
150
151    // Update the produced item counts
152    for (unsigned i = 0; i < mStreamSetOutputs.size(); ++i) {
153        const Binding & output = mStreamSetOutputs[i];
154        if (hasDerivedItemCount(output)) {
155            const ProcessingRate & rate = output.getRate();
156            Value * offset = nullptr;
157            if (rate.isFixed()) {
158                offset = b->CreateMul(nextIndex, mOutputStrideLength[i]);
159            } else { // if (rate.isPopCount() || rate.isNegatedPopCount())
160                offset = getPopCountRateItems(b, rate, nextIndex);
161            }
162            Value * const produced = b->CreateAdd(mInitialProducedItemCount[i], offset);
163            b->setNonDeferredProducedItemCount(output, produced);
164        }
165    }
166
167    mTreatUnsafeKernelOperationsAsErrors = true;
168
169    return nextIndex;
170}
171
172/** ------------------------------------------------------------------------------------------------------------- *
173 * @brief getRemainingItems
174 ** ------------------------------------------------------------------------------------------------------------- */
175Value * BlockOrientedKernel::getRemainingItems(const std::unique_ptr<KernelBuilder> & b) {
176    Value * remainingItems = nullptr;
177    const auto count = mStreamSetInputs.size();
178    if (count == 1) {
179        return mAccessibleInputItems[0];
180    } else {
181        for (unsigned i = 0; i < count; i++) {
182            if (mStreamSetInputs[i].isPrincipal()) {
183                return mAccessibleInputItems[i];
184            }
185        }
186        for (unsigned i = 0; i < count; ++i) {
187            const ProcessingRate & r = mStreamSetInputs[i].getRate();
188            if (r.isFixed()) {
189                Value * ic = b->CreateCeilUDiv2(mAccessibleInputItems[i], r.getRate());
190                if (remainingItems) {
191                    remainingItems = b->CreateUMin(remainingItems, ic);
192                } else {
193                    remainingItems = ic;
194                }
195            }
196        }
197    }
198    return remainingItems;
199}
200
201/** ------------------------------------------------------------------------------------------------------------- *
202 * @brief writeDoBlockMethod
203 ** ------------------------------------------------------------------------------------------------------------- */
204inline void BlockOrientedKernel::writeDoBlockMethod(const std::unique_ptr<KernelBuilder> & b) {
205
206    Value * const self = getInstance();
207    Function * const cp = mCurrentMethod;
208    auto ip = b->saveIP();
209    std::vector<Value *> availableItemCount(0);
210
211    /// Check if the do block method is called and create the function if necessary
212    if (!b->supportsIndirectBr()) {
213
214        std::vector<Type *> params;
215        params.reserve(1 + mAccessibleInputItems.size());
216        params.push_back(self->getType());
217        for (Value * avail : mAccessibleInputItems) {
218            params.push_back(avail->getType());
219        }
220
221        FunctionType * const type = FunctionType::get(b->getVoidTy(), params, false);
222        mCurrentMethod = Function::Create(type, GlobalValue::InternalLinkage, getName() + DO_BLOCK_SUFFIX, b->getModule());
223        mCurrentMethod->setCallingConv(CallingConv::C);
224        mCurrentMethod->setDoesNotThrow();
225        auto args = mCurrentMethod->arg_begin();
226        args->setName("self");
227        setInstance(&*args);
228        availableItemCount.reserve(mAccessibleInputItems.size());
229        while (++args != mCurrentMethod->arg_end()) {
230            availableItemCount.push_back(&*args);
231        }
232        assert (availableItemCount.size() == mAccessibleInputItems.size());
233        mAccessibleInputItems.swap(availableItemCount);
234        b->SetInsertPoint(BasicBlock::Create(b->getContext(), "entry", mCurrentMethod));
235    }
236
237    generateDoBlockMethod(b); // must be implemented by the BlockOrientedKernelBuilder subtype
238
239    if (!b->supportsIndirectBr()) {
240        // Restore the DoSegment function state then call the DoBlock method
241        b->CreateRetVoid();
242        mDoBlockMethod = mCurrentMethod;
243        b->restoreIP(ip);
244        setInstance(self);
245        mCurrentMethod = cp;
246        mAccessibleInputItems.swap(availableItemCount);
247        CreateDoBlockMethodCall(b);
248    }
249
250}
251
252/** ------------------------------------------------------------------------------------------------------------- *
253 * @brief writeFinalBlockMethod
254 ** ------------------------------------------------------------------------------------------------------------- */
255inline void BlockOrientedKernel::writeFinalBlockMethod(const std::unique_ptr<KernelBuilder> & b, Value * remainingItems) {
256
257    Value * const self = getInstance();
258    Function * const cp = mCurrentMethod;
259    Value * const remainingItemCount = remainingItems;
260    auto ip = b->saveIP();
261    std::vector<Value *> availableItemCount(0);
262
263    if (!b->supportsIndirectBr()) {
264        std::vector<Type *> params;
265        params.reserve(2 + mAccessibleInputItems.size());
266        params.push_back(self->getType());
267        params.push_back(b->getSizeTy());
268        for (Value * avail : mAccessibleInputItems) {
269            params.push_back(avail->getType());
270        }
271        FunctionType * const type = FunctionType::get(b->getVoidTy(), params, false);
272        mCurrentMethod = Function::Create(type, GlobalValue::InternalLinkage, getName() + FINAL_BLOCK_SUFFIX, b->getModule());
273        mCurrentMethod->setCallingConv(CallingConv::C);
274        mCurrentMethod->setDoesNotThrow();
275        auto args = mCurrentMethod->arg_begin();
276        args->setName("self");
277        setInstance(&*args);
278        remainingItems = &*(++args);
279        remainingItems->setName("remainingItems");
280        availableItemCount.reserve(mAccessibleInputItems.size());
281        while (++args != mCurrentMethod->arg_end()) {
282            availableItemCount.push_back(&*args);
283        }
284        assert (availableItemCount.size() == mAccessibleInputItems.size());
285        mAccessibleInputItems.swap(availableItemCount);
286        b->SetInsertPoint(BasicBlock::Create(b->getContext(), "entry", mCurrentMethod));
287    }
288
289    generateFinalBlockMethod(b, remainingItems); // may be implemented by the BlockOrientedKernel subtype
290
291    if (!b->supportsIndirectBr()) {
292        b->CreateRetVoid();
293        b->restoreIP(ip);
294        setInstance(self);
295        mAccessibleInputItems.swap(availableItemCount);
296        // Restore the DoSegment function state then call the DoFinal method
297        std::vector<Value *> args;
298        args.reserve(2 + mAccessibleInputItems.size());
299        args.push_back(self);
300        args.push_back(remainingItemCount);
301        args.insert(args.end(), mAccessibleInputItems.begin(), mAccessibleInputItems.end());
302        b->CreateCall(mCurrentMethod, args);
303        mCurrentMethod = cp;
304    }
305
306}
307
308/** ------------------------------------------------------------------------------------------------------------- *
309 * @brief generateFinalBlockMethod
310 ** ------------------------------------------------------------------------------------------------------------- */
311void BlockOrientedKernel::generateFinalBlockMethod(const std::unique_ptr<KernelBuilder> & b, Value * /* remainingItems */) {
312    //  The default finalBlock method simply dispatches to the doBlock routine.
313    CreateDoBlockMethodCall(b);
314}
315
316/** ------------------------------------------------------------------------------------------------------------- *
317 * @brief CreateDoBlockMethodCall
318 ** ------------------------------------------------------------------------------------------------------------- */
319void BlockOrientedKernel::CreateDoBlockMethodCall(const std::unique_ptr<KernelBuilder> & b) {
320    if (b->supportsIndirectBr()) {
321        BasicBlock * const bb = b->CreateBasicBlock("resume");
322        mStrideLoopBranch->addDestination(bb);
323        BasicBlock * const current = b->GetInsertBlock();
324        mStrideLoopTarget->addIncoming(BlockAddress::get(bb), current);
325        mStrideBlockIndex->addIncoming(b->getSize(0), current);
326        b->CreateBr(mStrideLoopBody);
327        bb->moveAfter(current);
328        b->SetInsertPoint(bb);
329    } else {
330        std::vector<Value *> args;
331        args.reserve(1 + mAccessibleInputItems.size());
332        args.push_back(getInstance());
333        args.insert(args.end(), mAccessibleInputItems.begin(), mAccessibleInputItems.end());
334        b->CreateCall(mDoBlockMethod, args);
335    }
336}
337
338// CONSTRUCTOR
339BlockOrientedKernel::BlockOrientedKernel(std::string && kernelName,
340                                         Bindings && stream_inputs,
341                                         Bindings && stream_outputs,
342                                         Bindings && scalar_parameters,
343                                         Bindings && scalar_outputs,
344                                         Bindings && internal_scalars)
345: MultiBlockKernel(std::move(kernelName), std::move(stream_inputs), std::move(stream_outputs), std::move(scalar_parameters), std::move(scalar_outputs), std::move(internal_scalars))
346, mDoBlockMethod(nullptr)
347, mStrideLoopBody(nullptr)
348, mStrideLoopBranch(nullptr)
349, mStrideLoopTarget(nullptr)
350, mStrideBlockIndex(nullptr) {
351
352}
353
354
355}
Note: See TracBrowser for help on using the repository browser.