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

Last change on this file since 6055 was 6055, checked in by cameron, 11 months ago

Various small fixes

File size: 9.4 KB
Line 
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#include <llvm/IR/Intrinsics.h>
11
12using namespace llvm;
13
14namespace kernel {
15
16    BitStreamPDEPKernel::BitStreamPDEPKernel(const std::unique_ptr<kernel::KernelBuilder> & b, const unsigned numberOfStream, std::string name)
17            : MultiBlockKernel(std::move(name),
18// input stream sets
19                               {Binding{b->getStreamSetTy(), "marker", FixedRate(), Principal()},
20                                Binding{b->getStreamSetTy(numberOfStream), "source", PopcountOf("marker")}},
21// output stream set
22                               {Binding{b->getStreamSetTy(numberOfStream), "output", FixedRate()}},
23                               {}, {}, {}),
24              mNumberOfStream(numberOfStream)
25             {
26
27    }
28
29    void BitStreamPDEPKernel::generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> & b, Value * const numOfBlocks) {
30        BasicBlock * const entry = b->GetInsertBlock();
31        BasicBlock * const processBlock = b->CreateBasicBlock("processBlock");
32        BasicBlock * const finishedStrides = b->CreateBasicBlock("finishedStrides");
33        const auto pdepWidth = 64; // TODO handle 32 bit machine
34        ConstantInt * const BLOCK_WIDTH = b->getSize(b->getBitBlockWidth());
35        ConstantInt * const PDEP_WIDTH = b->getSize(pdepWidth);
36
37        Function * pdep = nullptr;
38        if (pdepWidth == 64) {
39            pdep = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_bmi_pdep_64);
40        } else if (pdepWidth == 32) {
41            pdep = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_bmi_pdep_32);
42        } else {
43            report_fatal_error(getName() + ": PDEP width must be 32 or 64");
44        }
45
46        Constant * const ZERO = b->getSize(0);
47        Value * const sourceItemCount = b->getProcessedItemCount("source");
48
49        Value * const initialSourceOffset = b->CreateURem(sourceItemCount, BLOCK_WIDTH);
50        b->CreateBr(processBlock);
51
52        b->SetInsertPoint(processBlock);
53        PHINode * const strideIndex = b->CreatePHI(b->getSizeTy(), 2);
54        strideIndex->addIncoming(ZERO, entry);
55
56        std::vector<PHINode*> bufferPhiArray(mNumberOfStream, NULL);
57        std::vector<Value*> bufferArray(mNumberOfStream, NULL);
58        for (int iStreamIndex = 0; iStreamIndex < mNumberOfStream; iStreamIndex++) {
59            PHINode * const bufferPhi = b->CreatePHI(b->getIntNTy(pdepWidth), 2);
60            bufferPhi->addIncoming(Constant::getNullValue(b->getIntNTy(pdepWidth)), entry);
61            bufferPhiArray[iStreamIndex] = bufferPhi;
62            bufferArray[iStreamIndex] = bufferPhi;
63        }
64
65        PHINode * const sourceOffsetPhi = b->CreatePHI(b->getSizeTy(), 2);
66        sourceOffsetPhi->addIncoming(initialSourceOffset, entry);
67        PHINode * const bufferSizePhi = b->CreatePHI(b->getSizeTy(), 2);
68        bufferSizePhi->addIncoming(ZERO, entry);
69
70        // Extract the values we will use in the main processing loop
71        Value * const markerStream = b->getInputStreamBlockPtr("marker", ZERO, strideIndex);
72        Value * const markerValue = b->CreateBlockAlignedLoad(markerStream);
73        Value * const selectors = b->fwCast(pdepWidth, markerValue);
74        Value * const numOfSelectors = b->simd_popcount(pdepWidth, selectors);
75
76        // For each element of the marker block
77        Value * bufferSize = bufferSizePhi;
78        Value * sourceOffset = sourceOffsetPhi;
79
80
81        std::vector<llvm::Value*> resultArray(mNumberOfStream, UndefValue::get(b->getBitBlockType()));
82        /**
83         * TODO Assumed that the bitblocktype is always <4 * i64>
84         *                    The i < 4 here comes from  ^
85         */
86        for (unsigned i = 0; i < 4; i++) {
87
88            // How many bits will we deposit?
89            Value * const required = b->CreateExtractElement(numOfSelectors, b->getSize(i));
90
91            // Aggressively enqueue any additional bits
92            BasicBlock * const entry = b->GetInsertBlock();
93            BasicBlock * const enqueueBits = b->CreateBasicBlock();
94            b->CreateBr(enqueueBits);
95
96            b->SetInsertPoint(enqueueBits);
97            PHINode * const updatedBufferSize = b->CreatePHI(bufferSize->getType(), 2);
98            updatedBufferSize->addIncoming(bufferSize, entry);
99            PHINode * const updatedSourceOffset = b->CreatePHI(sourceOffset->getType(), 2);
100            updatedSourceOffset->addIncoming(sourceOffset, entry);
101
102            std::vector<PHINode * > updatedBufferArray(mNumberOfStream, NULL);
103            for (int iStreamIndex = 0; iStreamIndex < mNumberOfStream; iStreamIndex++) {
104                Value* buffer = bufferArray[iStreamIndex];
105                PHINode * const updatedBuffer = b->CreatePHI(buffer->getType(), 2);
106                updatedBuffer->addIncoming(buffer, entry);
107                updatedBufferArray[iStreamIndex] = updatedBuffer;
108            }
109
110            // Calculate the block and swizzle index of the current swizzle row
111            Value * const blockOffset = b->CreateUDiv(updatedSourceOffset, BLOCK_WIDTH);
112            Value * const swizzleIndex = b->CreateUDiv(b->CreateURem(updatedSourceOffset, BLOCK_WIDTH), PDEP_WIDTH);
113
114            Value * const swizzleOffset = b->CreateURem(updatedSourceOffset, PDEP_WIDTH);
115
116            for (int iStreamIndex = 0; iStreamIndex < mNumberOfStream; iStreamIndex++) {
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.