source: icGREP/icgrep-devel/icgrep/kernels/bitstream_pdep_kernel.cpp @ 6034

Last change on this file since 6034 was 6029, checked in by xwa163, 18 months ago

Init checkin for bitstream_pdep_kernel

File size: 9.4 KB
RevLine 
[6029]1/*
2 *  Copyright (c) 2017 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 */
5
6#include "bitstream_pdep_kernel.h"
7#include <kernels/kernel_builder.h>
8#include <llvm/Support/raw_ostream.h>
9#include <toolchain/toolchain.h>
10
11using namespace llvm;
12
13namespace kernel {
14
15    BitStreamPDEPKernel::BitStreamPDEPKernel(const std::unique_ptr<kernel::KernelBuilder> & b, const unsigned numberOfStream, std::string name)
16            : MultiBlockKernel(std::move(name),
17// input stream sets
18                               {Binding{b->getStreamSetTy(), "marker", FixedRate(), Principal()},
19                                Binding{b->getStreamSetTy(numberOfStream), "source", PopcountOf("marker")}},
20// output stream set
21                               {Binding{b->getStreamSetTy(numberOfStream), "output", FixedRate()}},
22                               {}, {}, {}),
23              mNumberOfStream(numberOfStream)
24             {
25
26    }
27
28    void BitStreamPDEPKernel::generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> & b, Value * const numOfBlocks) {
29        BasicBlock * const entry = b->GetInsertBlock();
30        BasicBlock * const processBlock = b->CreateBasicBlock("processBlock");
31        BasicBlock * const finishedStrides = b->CreateBasicBlock("finishedStrides");
32        const auto pdepWidth = 64; // TODO handle 32 bit machine
33        ConstantInt * const BLOCK_WIDTH = b->getSize(b->getBitBlockWidth());
34        ConstantInt * const PDEP_WIDTH = b->getSize(pdepWidth);
35
36        Function * pdep = nullptr;
37        if (pdepWidth == 64) {
38            pdep = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_bmi_pdep_64);
39        } else if (pdepWidth == 32) {
40            pdep = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_bmi_pdep_32);
41        } else {
42            report_fatal_error(getName() + ": PDEP width must be 32 or 64");
43        }
44
45        Constant * const ZERO = b->getSize(0);
46        Value * const sourceItemCount = b->getProcessedItemCount("source");
47
48        Value * const initialSourceOffset = b->CreateURem(sourceItemCount, BLOCK_WIDTH);
49        b->CreateBr(processBlock);
50
51        b->SetInsertPoint(processBlock);
52        PHINode * const strideIndex = b->CreatePHI(b->getSizeTy(), 2);
53        strideIndex->addIncoming(ZERO, entry);
54
55        std::vector<PHINode*> bufferPhiArray(mNumberOfStream, NULL);
56        std::vector<Value*> bufferArray(mNumberOfStream, NULL);
57        for (int iStreamIndex = 0; iStreamIndex < mNumberOfStream; iStreamIndex++) {
58            PHINode * const bufferPhi = b->CreatePHI(b->getIntNTy(pdepWidth), 2);
59            bufferPhi->addIncoming(Constant::getNullValue(b->getIntNTy(pdepWidth)), entry);
60            bufferPhiArray[iStreamIndex] = bufferPhi;
61            bufferArray[iStreamIndex] = bufferPhi;
62        }
63
64        PHINode * const sourceOffsetPhi = b->CreatePHI(b->getSizeTy(), 2);
65        sourceOffsetPhi->addIncoming(initialSourceOffset, entry);
66        PHINode * const bufferSizePhi = b->CreatePHI(b->getSizeTy(), 2);
67        bufferSizePhi->addIncoming(ZERO, entry);
68
69        // Extract the values we will use in the main processing loop
70        Value * const markerStream = b->getInputStreamBlockPtr("marker", ZERO, strideIndex);
71        Value * const markerValue = b->CreateBlockAlignedLoad(markerStream);
72        Value * const selectors = b->fwCast(pdepWidth, markerValue);
73        Value * const numOfSelectors = b->simd_popcount(pdepWidth, selectors);
74
75        // For each element of the marker block
76        Value * bufferSize = bufferSizePhi;
77        Value * sourceOffset = sourceOffsetPhi;
78
79
80        std::vector<llvm::Value*> resultArray(mNumberOfStream, UndefValue::get(b->getBitBlockType()));
81        /**
82         * TODO Assumed that the bitblocktype is always <4 * i64>
83         *                    The i < 4 here comes from  ^
84         */
85        for (unsigned i = 0; i < 4; i++) {
86
87            // How many bits will we deposit?
88            Value * const required = b->CreateExtractElement(numOfSelectors, b->getSize(i));
89
90            // Aggressively enqueue any additional bits
91            BasicBlock * const entry = b->GetInsertBlock();
92            BasicBlock * const enqueueBits = b->CreateBasicBlock();
93            b->CreateBr(enqueueBits);
94
95            b->SetInsertPoint(enqueueBits);
96            PHINode * const updatedBufferSize = b->CreatePHI(bufferSize->getType(), 2);
97            updatedBufferSize->addIncoming(bufferSize, entry);
98            PHINode * const updatedSourceOffset = b->CreatePHI(sourceOffset->getType(), 2);
99            updatedSourceOffset->addIncoming(sourceOffset, entry);
100
101            std::vector<PHINode * > updatedBufferArray(mNumberOfStream, NULL);
102            for (int iStreamIndex = 0; iStreamIndex < mNumberOfStream; iStreamIndex++) {
103                Value* buffer = bufferArray[iStreamIndex];
104                PHINode * const updatedBuffer = b->CreatePHI(buffer->getType(), 2);
105                updatedBuffer->addIncoming(buffer, entry);
106                updatedBufferArray[iStreamIndex] = updatedBuffer;
107            }
108
109            // Calculate the block and swizzle index of the current swizzle row
110            Value * const blockOffset = b->CreateUDiv(updatedSourceOffset, BLOCK_WIDTH);
111            Value * const swizzleIndex = b->CreateUDiv(b->CreateURem(updatedSourceOffset, BLOCK_WIDTH), PDEP_WIDTH);
112
113            Value * const swizzleOffset = b->CreateURem(updatedSourceOffset, PDEP_WIDTH);
114
115            for (int iStreamIndex = 0; iStreamIndex < mNumberOfStream; iStreamIndex++) {
116                // TODO improve the performance of these load instructions by gather
117                Value * const swizzleBlock = b->CreateBlockAlignedLoad(b->getInputStreamBlockPtr("source", b->getSize(iStreamIndex), blockOffset));
118
119                Value * const swizzle = b->CreateExtractElement(swizzleBlock, swizzleIndex);
120                // Shift the swizzle to the right to clear off any used bits ...
121                Value * const unreadBits = b->CreateSelect(b->CreateICmpEQ(swizzleOffset, b->getSize(0x40)), b->getInt64(0), b->CreateLShr(swizzle, swizzleOffset));
122                // ... then to the left to align the bits with the buffer and combine them.
123                Value * const pendingBits = b->CreateSelect(b->CreateICmpEQ(updatedBufferSize, b->getSize(0x40)), b->getInt64(0), b->CreateShl(unreadBits, updatedBufferSize));
124
125                bufferArray[iStreamIndex] = b->CreateOr(updatedBufferArray[iStreamIndex], pendingBits);
126                updatedBufferArray[iStreamIndex]->addIncoming(bufferArray[iStreamIndex], enqueueBits);
127            }
128
129            // Update the buffer size with the number of bits we have actually enqueued
130            Value * const maxBufferSize = b->CreateAdd(b->CreateSub(PDEP_WIDTH, swizzleOffset), updatedBufferSize);
131            bufferSize = b->CreateUMin(maxBufferSize, PDEP_WIDTH);
132            updatedBufferSize->addIncoming(bufferSize, enqueueBits);
133
134            // ... and increment the source offset by the number we actually inserted
135            Value * const inserted = b->CreateSub(bufferSize, updatedBufferSize);
136            sourceOffset = b->CreateAdd(updatedSourceOffset, inserted);
137            updatedSourceOffset->addIncoming(sourceOffset, enqueueBits);
138
139            // INVESTIGATE: we can branch at most once here. I'm not sure whether the potential
140            // branch misprediction is better or worse than always filling from two swizzles to
141            // ensure that we have enough bits to deposit.
142            BasicBlock * const depositBits = b->CreateBasicBlock();
143            b->CreateUnlikelyCondBr(b->CreateICmpULT(bufferSize, required), enqueueBits, depositBits);
144
145            b->SetInsertPoint(depositBits);
146
147            // Apply PDEP to each element of the combined swizzle using the current PDEP mask
148            Value * const mask = b->CreateExtractElement(selectors, i);
149            for (int iStreamIndex = 0; iStreamIndex < mNumberOfStream; iStreamIndex++) {
150                Value * source_field = bufferArray[iStreamIndex];
151
152                Value * PDEP_field = b->CreateCall(pdep, {source_field, mask});
153
154                resultArray[iStreamIndex] = b->CreateInsertElement(resultArray[iStreamIndex], PDEP_field, i);
155
156                // Shift away any used bits from the buffer and decrement our buffer size by the number we used
157                bufferArray[iStreamIndex] = b->CreateSelect(b->CreateICmpEQ(required, b->getInt64(0x40)), b->getInt64(0), b->CreateLShr(bufferArray[iStreamIndex], required));
158            }
159
160            bufferSize = b->CreateSub(bufferSize, required);
161        }
162
163        for (int iStreamIndex = 0; iStreamIndex < mNumberOfStream; iStreamIndex++) {
164            // Store the result
165            Value * const outputStreamPtr = b->getOutputStreamBlockPtr("output", b->getSize(iStreamIndex), strideIndex);
166            b->CreateBlockAlignedStore(resultArray[iStreamIndex], outputStreamPtr);
167        }
168
169        BasicBlock * const finishedBlock = b->GetInsertBlock();
170        sourceOffsetPhi->addIncoming(sourceOffset, finishedBlock);
171        bufferSizePhi->addIncoming(bufferSize, finishedBlock);
172        for (int iStreamIndex = 0; iStreamIndex < mNumberOfStream; iStreamIndex++) {
173            bufferPhiArray[iStreamIndex]->addIncoming(bufferArray[iStreamIndex], finishedBlock);
174        }
175
176        Value * const nextStrideIndex = b->CreateAdd(strideIndex, b->getSize(1));
177        strideIndex->addIncoming(nextStrideIndex, finishedBlock);
178        b->CreateLikelyCondBr(b->CreateICmpNE(nextStrideIndex, numOfBlocks), processBlock, finishedStrides);
179
180        b->SetInsertPoint(finishedStrides);
181    }
182
183}
Note: See TracBrowser for help on using the repository browser.