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

Last change on this file since 6297 was 6273, checked in by nmedfort, 7 months ago

More work on optimization branch. First stage of stateless kernel optimization

File size: 18.3 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 <kernels/kernel_builder.h>
10#include <llvm/IR/Constants.h>
11#include <llvm/IR/Function.h>
12#include <llvm/IR/Instructions.h>
13#include <llvm/IR/MDBuilder.h>
14#include <llvm/IR/Module.h>
15#include <llvm/Support/raw_ostream.h>
16#if LLVM_VERSION_INTEGER < LLVM_VERSION_CODE(4, 0, 0)
17#include <llvm/Bitcode/ReaderWriter.h>
18#else
19#include <llvm/Bitcode/BitcodeWriter.h>
20#endif
21#include <llvm/Transforms/Utils/Local.h>
22#include <llvm/Support/Debug.h>
23#include <boost/graph/adjacency_list.hpp>
24#include <util/extended_boost_graph_containers.h>
25#include <sstream>
26#include <functional>
27
28using namespace llvm;
29using namespace boost;
30using boost::container::flat_set;
31
32namespace kernel {
33
34using AttrId = Attribute::KindId;
35using RateId = ProcessingRate::KindId;
36
37// TODO: Break the BlockOrientedKernel into two classes, one with an explicit DoFinal block and another that
38// calls the DoBlock method with optional preamble and postamble hooks. By doing so, we can remove the indirect
39// branches (or function calls) from the following kernel and simplify the cognitive load for the kernel
40// programmer. This is less general than the current method but no evidence that being able to reenter the
41// DoBlock method multiple times from the DoFinal block would ever be useful.
42
43// Can we eliminate some of the kernel state (e.g., EOF) by having a general preamble that can create a stack-
44// allocated struct?
45
46const auto DO_BLOCK_SUFFIX = "_DoBlock";
47const auto FINAL_BLOCK_SUFFIX = "_FinalBlock";
48
49/** ------------------------------------------------------------------------------------------------------------- *
50 * @brief generateMultiBlockLogic
51 ** ------------------------------------------------------------------------------------------------------------- */
52void BlockOrientedKernel::generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> & b, Value * const numOfBlocks) {
53
54    if (LLVM_UNLIKELY(mStride != b->getBitBlockWidth())) {
55        report_fatal_error(getName() + ": the Stride (" + std::to_string(mStride) + ") of BlockOrientedKernel "
56                           "equal to the BitBlockWidth (" + std::to_string(b->getBitBlockWidth()) + ")");
57    }
58
59    BasicBlock * const entryBlock = b->GetInsertBlock();
60    mStrideLoopBody = b->CreateBasicBlock(getName() + "_strideLoopBody");
61    BasicBlock * const incrementCountableItems = b->CreateBasicBlock(getName() + "_incrementCountableItems");
62    BasicBlock * const stridesDone = b->CreateBasicBlock(getName() + "_stridesDone");
63    BasicBlock * const doFinalBlock = b->CreateBasicBlock(getName() + "_doFinalBlock");
64    BasicBlock * const segmentDone = b->CreateBasicBlock(getName() + "_segmentDone");
65
66    b->CreateUnlikelyCondBr(mIsFinal, doFinalBlock, mStrideLoopBody);
67
68    /// BLOCK BODY
69
70    b->SetInsertPoint(mStrideLoopBody);
71    if (b->supportsIndirectBr()) {
72        Value * const baseTarget = BlockAddress::get(segmentDone);
73        mStrideLoopTarget = b->CreatePHI(baseTarget->getType(), 2, "strideTarget");
74        mStrideLoopTarget->addIncoming(baseTarget, entryBlock);
75    }
76    mStrideBlockIndex = b->CreatePHI(b->getSizeTy(), 2);
77    mStrideBlockIndex->addIncoming(b->getSize(0), entryBlock);
78
79    /// GENERATE DO BLOCK METHOD
80
81    writeDoBlockMethod(b);
82
83    Value * const nextStrideBlockIndex = b->CreateAdd(mStrideBlockIndex, b->getSize(1));
84    Value * noMore = b->CreateICmpEQ(nextStrideBlockIndex, numOfBlocks);
85    if (canSetTerminateSignal()) {
86        noMore = b->CreateOr(noMore, b->getTerminationSignal());
87    }
88    b->CreateUnlikelyCondBr(noMore, stridesDone, incrementCountableItems);
89
90    b->SetInsertPoint(incrementCountableItems);
91    incrementCountableItemCounts(b);
92    BasicBlock * const bodyEnd = b->GetInsertBlock();
93    if (mStrideLoopTarget) {
94        mStrideLoopTarget->addIncoming(mStrideLoopTarget, bodyEnd);
95    }
96    mStrideBlockIndex->addIncoming(nextStrideBlockIndex, bodyEnd);
97
98    b->CreateBr(mStrideLoopBody);
99
100    stridesDone->moveAfter(bodyEnd);
101
102    /// STRIDE DONE
103
104    b->SetInsertPoint(stridesDone);
105
106    // Now conditionally perform the final block processing depending on the doFinal parameter.
107    if (mStrideLoopTarget) {
108        mStrideLoopBranch = b->CreateIndirectBr(mStrideLoopTarget, 3);
109        mStrideLoopBranch->addDestination(doFinalBlock);
110        mStrideLoopBranch->addDestination(segmentDone);
111    } else {
112        b->CreateUnlikelyCondBr(mIsFinal, doFinalBlock, segmentDone);
113    }
114
115    doFinalBlock->moveAfter(stridesDone);
116
117    /// DO FINAL BLOCK
118
119    b->SetInsertPoint(doFinalBlock);
120    writeFinalBlockMethod(b, getRemainingItems(b));
121    b->CreateBr(segmentDone);
122
123    segmentDone->moveAfter(b->GetInsertBlock());
124
125    b->SetInsertPoint(segmentDone);
126
127    // Update the branch prediction metadata to indicate that the likely target will be segmentDone
128    if (mStrideLoopTarget) {
129        MDBuilder mdb(b->getContext());
130        const auto destinations = mStrideLoopBranch->getNumDestinations();
131        uint32_t weights[destinations];
132        for (unsigned i = 0; i < destinations; ++i) {
133            weights[i] = (mStrideLoopBranch->getDestination(i) == segmentDone) ? 100 : 1;
134        }
135        ArrayRef<uint32_t> bw(weights, destinations);
136        mStrideLoopBranch->setMetadata(LLVMContext::MD_prof, mdb.createBranchWeights(bw));
137    }
138
139}
140
141/** ------------------------------------------------------------------------------------------------------------- *
142 * @brief incrementCountableItemCounts
143 ** ------------------------------------------------------------------------------------------------------------- */
144void BlockOrientedKernel::incrementCountableItemCounts(const std::unique_ptr<KernelBuilder> & b) {
145    // Update the processed item counts
146    for (const Binding & input : getInputStreamSetBindings()) {
147        if (isCountable(input)) {
148            const ProcessingRate & rate = input.getRate();
149            Value * offset = nullptr;
150            if (rate.isFixed()) {
151                offset = b->getSize(ceiling(getUpperBound(input) * getStride()));
152            } else { // if (rate.isPopCount() || rate.isNegatedPopCount())
153                offset = getPopCountRateItemCount(b, rate);
154            }
155            Value * const initial = b->getProcessedItemCount(input.getName());
156            Value * const processed = b->CreateAdd(initial, offset);
157            b->setProcessedItemCount(input.getName(), processed);
158        }
159    }
160    // Update the produced item counts
161    for (const Binding & output : getOutputStreamSetBindings()) {
162        if (isCountable(output)) {
163            const ProcessingRate & rate = output.getRate();
164            Value * offset = nullptr;
165            if (rate.isFixed()) {
166                offset = b->getSize(ceiling(getUpperBound(output) * getStride()));
167            } else { // if (rate.isPopCount() || rate.isNegatedPopCount())
168                offset = getPopCountRateItemCount(b, rate);
169            }
170            Value * const initial = b->getProducedItemCount(output.getName());
171            Value * const produced = b->CreateAdd(initial, offset);
172            b->setProducedItemCount(output.getName(), produced);
173        }
174    }
175}
176
177/** ------------------------------------------------------------------------------------------------------------- *
178 * @brief getPopCountRateItemCount
179 ** ------------------------------------------------------------------------------------------------------------- */
180Value * BlockOrientedKernel::getPopCountRateItemCount(const std::unique_ptr<KernelBuilder> & b,
181                                                      const ProcessingRate & rate) {
182    assert (rate.isPopCount() || rate.isNegatedPopCount());
183    Port refPort;
184    unsigned refIndex = 0;
185    std::tie(refPort, refIndex) = getStreamPort(rate.getReference());
186    assert (refPort == Port::Input);
187    Value * array = nullptr;
188    if (rate.isNegatedPopCount()) {
189        array = mNegatedPopCountRateArray[refIndex];
190    } else {
191        array = mPopCountRateArray[refIndex];
192    }
193    assert (array && "missing pop count array attribute");
194    Value * const currentSum = b->CreateLoad(b->CreateGEP(array, mStrideBlockIndex));
195    Value * const priorIndex = b->CreateSub(mStrideBlockIndex, b->getSize(1));
196    Value * const priorSum = b->CreateLoad(b->CreateGEP(array, priorIndex));
197    return b->CreateSub(currentSum, priorSum);
198}
199
200/** ------------------------------------------------------------------------------------------------------------- *
201 * @brief getRemainingItems
202 ** ------------------------------------------------------------------------------------------------------------- */
203Value * BlockOrientedKernel::getRemainingItems(const std::unique_ptr<KernelBuilder> & b) {
204    Value * remainingItems = nullptr;
205    const auto count = mInputStreamSets.size();
206    if (count == 1) {
207        return mAccessibleInputItems[0];
208    } else {
209        for (unsigned i = 0; i < count; i++) {
210            if (mInputStreamSets[i].isPrincipal()) {
211                return mAccessibleInputItems[i];
212            }
213        }
214        for (unsigned i = 0; i < count; ++i) {
215            const ProcessingRate & r = mInputStreamSets[i].getRate();
216            if (r.isFixed()) {
217                Value * ic = b->CreateCeilUDiv2(mAccessibleInputItems[i], r.getRate());
218                if (remainingItems) {
219                    remainingItems = b->CreateUMin(remainingItems, ic);
220                } else {
221                    remainingItems = ic;
222                }
223            }
224        }
225    }
226    return remainingItems;
227}
228
229/** ------------------------------------------------------------------------------------------------------------- *
230 * @brief writeDoBlockMethod
231 ** ------------------------------------------------------------------------------------------------------------- */
232inline void BlockOrientedKernel::writeDoBlockMethod(const std::unique_ptr<KernelBuilder> & b) {
233
234    Value * const self = getHandle();
235    Function * const cp = mCurrentMethod;
236    auto ip = b->saveIP();
237    std::vector<Value *> availableItemCount(0);
238
239    /// Check if the do block method is called and create the function if necessary
240    if (!b->supportsIndirectBr()) {
241
242        std::vector<Type *> params;
243        params.reserve(1 + mAccessibleInputItems.size());
244        params.push_back(self->getType());
245        for (Value * avail : mAccessibleInputItems) {
246            params.push_back(avail->getType());
247        }
248
249        FunctionType * const type = FunctionType::get(b->getVoidTy(), params, false);
250        mCurrentMethod = Function::Create(type, GlobalValue::InternalLinkage, getName() + DO_BLOCK_SUFFIX, b->getModule());
251        mCurrentMethod->setCallingConv(CallingConv::C);
252        mCurrentMethod->setDoesNotThrow();
253        auto args = mCurrentMethod->arg_begin();
254        args->setName("self");
255        setHandle(b, &*args);
256        availableItemCount.reserve(mAccessibleInputItems.size());
257        while (++args != mCurrentMethod->arg_end()) {
258            availableItemCount.push_back(&*args);
259        }
260        assert (availableItemCount.size() == mAccessibleInputItems.size());
261        mAccessibleInputItems.swap(availableItemCount);
262        b->SetInsertPoint(BasicBlock::Create(b->getContext(), "entry", mCurrentMethod));
263    }
264
265    generateDoBlockMethod(b); // must be implemented by the BlockOrientedKernelBuilder subtype
266
267    if (!b->supportsIndirectBr()) {
268        // Restore the DoSegment function state then call the DoBlock method
269        b->CreateRetVoid();
270        mDoBlockMethod = mCurrentMethod;
271        b->restoreIP(ip);
272        setHandle(b, self);
273        mCurrentMethod = cp;
274        mAccessibleInputItems.swap(availableItemCount);
275        CreateDoBlockMethodCall(b);
276    }
277
278}
279
280/** ------------------------------------------------------------------------------------------------------------- *
281 * @brief writeFinalBlockMethod
282 ** ------------------------------------------------------------------------------------------------------------- */
283inline void BlockOrientedKernel::writeFinalBlockMethod(const std::unique_ptr<KernelBuilder> & b, Value * remainingItems) {
284
285    Value * const self = getHandle();
286    Function * const cp = mCurrentMethod;
287    Value * const remainingItemCount = remainingItems;
288    auto ip = b->saveIP();
289    std::vector<Value *> availableItemCount(0);
290
291    if (!b->supportsIndirectBr()) {
292        std::vector<Type *> params;
293        params.reserve(2 + mAccessibleInputItems.size());
294        params.push_back(self->getType());
295        params.push_back(b->getSizeTy());
296        for (Value * avail : mAccessibleInputItems) {
297            params.push_back(avail->getType());
298        }
299        FunctionType * const type = FunctionType::get(b->getVoidTy(), params, false);
300        mCurrentMethod = Function::Create(type, GlobalValue::InternalLinkage, getName() + FINAL_BLOCK_SUFFIX, b->getModule());
301        mCurrentMethod->setCallingConv(CallingConv::C);
302        mCurrentMethod->setDoesNotThrow();
303        auto args = mCurrentMethod->arg_begin();
304        args->setName("self");
305        setHandle(b, &*args);
306        remainingItems = &*(++args);
307        remainingItems->setName("remainingItems");
308        availableItemCount.reserve(mAccessibleInputItems.size());
309        while (++args != mCurrentMethod->arg_end()) {
310            availableItemCount.push_back(&*args);
311        }
312        assert (availableItemCount.size() == mAccessibleInputItems.size());
313        mAccessibleInputItems.swap(availableItemCount);
314        b->SetInsertPoint(BasicBlock::Create(b->getContext(), "entry", mCurrentMethod));
315    }
316
317    generateFinalBlockMethod(b, remainingItems); // may be implemented by the BlockOrientedKernel subtype
318
319    if (!b->supportsIndirectBr()) {
320        b->CreateRetVoid();
321        b->restoreIP(ip);
322        setHandle(b, self);
323        mAccessibleInputItems.swap(availableItemCount);
324        // Restore the DoSegment function state then call the DoFinal method
325        std::vector<Value *> args;
326        args.reserve(2 + mAccessibleInputItems.size());
327        args.push_back(self);
328        args.push_back(remainingItemCount);
329        args.insert(args.end(), mAccessibleInputItems.begin(), mAccessibleInputItems.end());
330        b->CreateCall(mCurrentMethod, args);
331        mCurrentMethod = cp;
332    }
333
334}
335
336/** ------------------------------------------------------------------------------------------------------------- *
337 * @brief generateFinalBlockMethod
338 ** ------------------------------------------------------------------------------------------------------------- */
339void BlockOrientedKernel::generateFinalBlockMethod(const std::unique_ptr<KernelBuilder> & b, Value * /* remainingItems */) {
340    //  The default finalBlock method simply dispatches to the doBlock routine.
341    CreateDoBlockMethodCall(b);
342}
343
344/** ------------------------------------------------------------------------------------------------------------- *
345 * @brief CreateDoBlockMethodCall
346 ** ------------------------------------------------------------------------------------------------------------- */
347void BlockOrientedKernel::CreateDoBlockMethodCall(const std::unique_ptr<KernelBuilder> & b) {
348    if (b->supportsIndirectBr()) {
349        BasicBlock * const bb = b->CreateBasicBlock("resume");
350        mStrideLoopBranch->addDestination(bb);
351        BasicBlock * const current = b->GetInsertBlock();
352        mStrideLoopTarget->addIncoming(BlockAddress::get(bb), current);
353        mStrideBlockIndex->addIncoming(b->getSize(0), current);
354        b->CreateBr(mStrideLoopBody);
355        bb->moveAfter(current);
356        b->SetInsertPoint(bb);
357    } else {
358        std::vector<Value *> args;
359        args.reserve(1 + mAccessibleInputItems.size());
360        args.push_back(getHandle());
361        args.insert(args.end(), mAccessibleInputItems.begin(), mAccessibleInputItems.end());
362        b->CreateCall(mDoBlockMethod, args);
363    }
364}
365
366/** ------------------------------------------------------------------------------------------------------------- *
367 * @brief annotateInputBindingsWithPopCountArrayAttributes
368 ** ------------------------------------------------------------------------------------------------------------- */
369void BlockOrientedKernel::annotateInputBindingsWithPopCountArrayAttributes() {
370    const unsigned n = mInputStreamSets.size();
371    const unsigned m = mOutputStreamSets.size();
372
373    if (LLVM_UNLIKELY(n == 0 || (n + m) < 2)) {
374        return;
375    }
376
377    enum : int {
378        POSITIVE = 0
379        , NEGATIVE = 1
380    };
381
382    using Graph = adjacency_list<vecS, vecS, directedS>;
383
384    Graph G(std::max(n, 2U));
385
386    auto checkPopCount = [&](const Binding & binding) {
387        const ProcessingRate & rate = binding.getRate();
388        if (LLVM_UNLIKELY(rate.isPopCount() || rate.isNegatedPopCount())) {
389            Kernel::Port type;
390            unsigned refPort;
391            std::tie(type, refPort) = getStreamPort(rate.getReference());
392            assert ("pop count rate cannot refer to an output stream" && (type == Kernel::Port::Input));
393            const auto targetType = rate.isPopCount() ? POSITIVE : NEGATIVE;
394            add_edge(refPort, targetType, G);
395        }
396    };
397
398    for (unsigned i = 0; i < n; ++i) {
399        checkPopCount(mInputStreamSets[i]);
400    }
401    for (unsigned i = 0; i < m; ++i) {
402        checkPopCount(mOutputStreamSets[i]);
403    }
404
405    for (const auto e : make_iterator_range(edges(G))) {
406        const auto i = source(e, G);
407        assert (i < mInputStreamSets.size());
408        Binding & input = mInputStreamSets[i];
409        switch (target(e, G)) {
410            case POSITIVE:
411                input.addAttribute(RequiresPopCountArray());
412                break;
413            case NEGATIVE:
414                input.addAttribute(RequiresNegatedPopCountArray());
415                break;
416            default: llvm_unreachable("unhandled pop count type!");
417        }
418    }
419}
420
421
422// CONSTRUCTOR
423BlockOrientedKernel::BlockOrientedKernel(
424    const std::unique_ptr<KernelBuilder> & b,
425    std::string && kernelName,
426    Bindings && stream_inputs,
427    Bindings && stream_outputs,
428    Bindings && scalar_parameters,
429    Bindings && scalar_outputs,
430    Bindings && internal_scalars)
431: MultiBlockKernel(b,
432    TypeId::BlockOriented,
433    std::move(kernelName),
434    std::move(stream_inputs),
435    std::move(stream_outputs),
436    std::move(scalar_parameters),
437    std::move(scalar_outputs),
438    std::move(internal_scalars))
439, mDoBlockMethod(nullptr)
440, mStrideLoopBody(nullptr)
441, mStrideLoopBranch(nullptr)
442, mStrideLoopTarget(nullptr)
443, mStrideBlockIndex(nullptr) {
444    annotateInputBindingsWithPopCountArrayAttributes();
445}
446
447
448}
Note: See TracBrowser for help on using the repository browser.