source: icGREP/icgrep-devel/icgrep/kernels/lz4/lz4_numbers_to_bitstream_kernel.cpp @ 5926

Last change on this file since 5926 was 5926, checked in by xwa163, 19 months ago

Fix lz4 related GEP instructions and TODO

File size: 17.5 KB
Line 
1
2#include "lz4_numbers_to_bitstream_kernel.h"
3#include <kernels/kernel_builder.h>
4#include <iostream>
5#include <string>
6#include <llvm/Support/raw_ostream.h>
7#include <kernels/streamset.h>
8
9#define START_NUM_STREAM_NAME ("startNumberStream")
10#define END_NUM_STREAM_NAME ("endNumberStream")
11#define OUTPUT_BIT_STREAM_NAME ("outputBitStream__")
12
13#define PENDING_START_DATA_KEY ("pendingStartData")
14#define PENDING_END_DATA_KEY ("pendingEndData")
15
16using namespace llvm;
17using namespace kernel;
18using namespace std;
19
20namespace kernel {
21
22    Value* LZ4NumbersToBitstreamKernel::loadInt64NumberInput(const unique_ptr<KernelBuilder> &iBuilder, string bufferName, Value* offset) {
23        // GEP here is safe
24        Value* SIZE_BIT_BLOCK_WIDTH = iBuilder->getSize(iBuilder->getBitBlockWidth());
25        Value* inputLocalBlockIndex = iBuilder->CreateUDiv(offset, SIZE_BIT_BLOCK_WIDTH);
26        Value* inputLocalBlockOffset = iBuilder->CreateURem(offset, SIZE_BIT_BLOCK_WIDTH);
27
28        Value* blockBasePtr = iBuilder->getInputStreamBlockPtr(bufferName, iBuilder->getSize(0), inputLocalBlockIndex);
29        blockBasePtr = iBuilder->CreatePointerCast(blockBasePtr, iBuilder->getInt64Ty()->getPointerTo());
30        // GEP here is safe
31        return iBuilder->CreateLoad(iBuilder->CreateGEP(blockBasePtr, inputLocalBlockOffset));
32    }
33
34    void LZ4NumbersToBitstreamKernel::generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> &iBuilder,
35                                                               llvm::Value *const numOfStrides) {
36        // Const
37        Constant *SIZE_ZERO = iBuilder->getSize(0);
38        Constant *SIZE_ONE = iBuilder->getSize(1);
39        Constant *INT64_ZERO = iBuilder->getInt64(0);
40        Constant *INT64_ONE = iBuilder->getInt64(1);
41
42        unsigned int BIT_BLOCK_WIDTH = iBuilder->getBitBlockWidth();
43        Type * const INT_BIT_BLOCK_TY = iBuilder->getIntNTy(BIT_BLOCK_WIDTH);
44        Constant *SIZE_BIT_BLOCK_WIDTH = iBuilder->getSize(BIT_BLOCK_WIDTH);
45        Constant* INT_BIT_BLOCK_ZERO = ConstantInt::get(INT_BIT_BLOCK_TY, 0);
46        Value* BIT_BLOCK_ZERO = iBuilder->CreateBitCast(INT_BIT_BLOCK_ZERO, iBuilder->getBitBlockType());
47
48
49        size_t outputBufferBlocks = this->getAnyBufferSize(iBuilder, OUTPUT_BIT_STREAM_NAME) / iBuilder->getStride();
50        Value *outputRawBeginPtr = iBuilder->CreatePointerCast(
51                iBuilder->getRawOutputPointer(OUTPUT_BIT_STREAM_NAME, SIZE_ZERO),
52                iBuilder->getBitBlockType()->getPointerTo());
53        Value *outputCurrentPtr = iBuilder->getOutputStreamBlockPtr(OUTPUT_BIT_STREAM_NAME, SIZE_ZERO);
54        Value *offset = iBuilder->CreatePtrDiff(outputCurrentPtr, outputRawBeginPtr);
55        Value *remainSpace = iBuilder->CreateSub(iBuilder->getSize(outputBufferBlocks), offset);
56//        iBuilder->CallPrintInt("remainSpace",
57//                               remainSpace); //TODO workaround here, kernel infrastructure should provide the information about how much data we can produced
58
59
60        BasicBlock *entryBlock = iBuilder->GetInsertBlock();
61
62
63        Value *itemsToDo = mAvailableItemCount[0];
64//        iBuilder->CallPrintInt("itemsToDo", itemsToDo);
65        Value *isFinalBlock = iBuilder->CreateICmpEQ(itemsToDo, iBuilder->getSize(0));
66        iBuilder->setTerminationSignal(isFinalBlock);
67
68        Value *itemProcessed = iBuilder->getProcessedItemCount(START_NUM_STREAM_NAME);
69        Value *oldProducedItemCount = iBuilder->getProducedItemCount(OUTPUT_BIT_STREAM_NAME);
70        Value *oldProducedOutputBlockIndex = iBuilder->CreateUDiv(oldProducedItemCount,
71                                                                  SIZE_BIT_BLOCK_WIDTH); // always produce full block except for final block
72
73        Value *initCurrentItemIndex = iBuilder->CreateURem(itemProcessed, SIZE_BIT_BLOCK_WIDTH);
74
75        Value *initOutputIndex = SIZE_ZERO;
76
77
78        Value *availableOutputBlocks = iBuilder->CreateUMin(remainSpace, numOfStrides);
79
80//        Value *inputStartBasePtr = iBuilder->getInputStreamBlockPtr(START_NUM_STREAM_NAME, SIZE_ZERO);
81//        inputStartBasePtr = iBuilder->CreatePointerCast(inputStartBasePtr, iBuilder->getInt64Ty()->getPointerTo());
82//        Value *inputEndBasePtr = iBuilder->getInputStreamBlockPtr(END_NUM_STREAM_NAME, SIZE_ZERO);
83//        inputEndBasePtr = iBuilder->CreatePointerCast(inputEndBasePtr, iBuilder->getInt64Ty()->getPointerTo());
84        Value *outputBasePtr = iBuilder->getOutputStreamBlockPtr(OUTPUT_BIT_STREAM_NAME, SIZE_ZERO);
85        Value *initCarryBit = iBuilder->getScalarField("carryBit");
86
87//        iBuilder->CallPrintInt("itemProcessed", itemProcessed);
88//        iBuilder->CallPrintInt("inputStartBasePtr", inputStartBasePtr);
89
90        Value *initCurrentBlockStartData = iBuilder->getScalarField(PENDING_START_DATA_KEY);
91        Value *initCurrentBlockEndData = iBuilder->getScalarField(PENDING_END_DATA_KEY);
92
93
94        BasicBlock *multiBlockLoopConBlock = iBuilder->CreateBasicBlock("multiBlockLoopConBlock");
95        BasicBlock *multiBlockLoopBodyBlock = iBuilder->CreateBasicBlock("multiBlockLoopBodyBlock");
96        BasicBlock *multiBlockLoopExitBlock = iBuilder->CreateBasicBlock("multiBlockLoopExitBlock");
97
98        iBuilder->CreateBr(multiBlockLoopConBlock);
99
100        // multiBlockLoopConBlock
101        iBuilder->SetInsertPoint(multiBlockLoopConBlock);
102        PHINode *phiCurrentItemIndex = iBuilder->CreatePHI(iBuilder->getSizeTy(), 2);
103        phiCurrentItemIndex->addIncoming(initCurrentItemIndex, entryBlock);
104
105        PHINode *phiCurrentOutputIndex = iBuilder->CreatePHI(iBuilder->getSizeTy(), 2);
106        phiCurrentOutputIndex->addIncoming(initOutputIndex, entryBlock);
107
108        PHINode *phiCurrentBlockStartData = iBuilder->CreatePHI(iBuilder->getBitBlockType(), 2);
109        phiCurrentBlockStartData->addIncoming(initCurrentBlockStartData, entryBlock);
110
111        PHINode *phiCurrentBlockEndData = iBuilder->CreatePHI(iBuilder->getBitBlockType(), 2);
112        phiCurrentBlockEndData->addIncoming(initCurrentBlockEndData, entryBlock);
113
114        PHINode *phiCarryBit = iBuilder->CreatePHI(iBuilder->getInt64Ty(), 2);
115        phiCarryBit->addIncoming(initCarryBit, entryBlock);
116
117        iBuilder->CreateCondBr(
118                iBuilder->CreateAnd(
119                        iBuilder->CreateICmpULT(phiCurrentItemIndex, iBuilder->CreateAdd(itemsToDo,
120                                                                                         initCurrentItemIndex)),
121                        iBuilder->CreateICmpULT(phiCurrentOutputIndex, availableOutputBlocks)
122                ),
123                multiBlockLoopBodyBlock,
124                multiBlockLoopExitBlock
125        );
126
127        // multiBlockLoopBodyBlock
128        iBuilder->SetInsertPoint(multiBlockLoopBodyBlock);
129
130        Value *currentOutputGlobalIndex = iBuilder->CreateAdd(phiCurrentOutputIndex, oldProducedOutputBlockIndex);
131        // StartBits
132        Value *currentStartPos = this->loadInt64NumberInput(iBuilder, START_NUM_STREAM_NAME, phiCurrentItemIndex);
133        Value *currentStartGlobalBlockIndex = iBuilder->CreateUDiv(currentStartPos, SIZE_BIT_BLOCK_WIDTH);
134
135        Value *currentStartLocalBlockOffset = iBuilder->CreateURem(currentStartPos,
136                                                                   SIZE_BIT_BLOCK_WIDTH); // 0 ~ BIT_BLOCK_WIDTH
137
138        Value *newBlockStartData = this->setIntVectorBitOne(iBuilder, phiCurrentBlockStartData,
139                                                            currentStartLocalBlockOffset,
140                                                            iBuilder->CreateICmpEQ(currentStartGlobalBlockIndex,
141                                                                                   currentOutputGlobalIndex));
142
143        // EndBits
144        Value *currentEndPos = this->loadInt64NumberInput(iBuilder, END_NUM_STREAM_NAME, phiCurrentItemIndex);
145        Value *currentEndGlobalBlockIndex = iBuilder->CreateUDiv(currentEndPos, SIZE_BIT_BLOCK_WIDTH);
146
147        Value *currentEndLocalBlockOffset = iBuilder->CreateURem(currentEndPos,
148                                                                 SIZE_BIT_BLOCK_WIDTH); // 0 ~ BIT_BLOCK_WIDTH
149
150
151        Value *newBlockEndData = this->setIntVectorBitOne(iBuilder, phiCurrentBlockEndData, currentEndLocalBlockOffset,
152                                                          iBuilder->CreateICmpEQ(currentEndGlobalBlockIndex,
153                                                                                 currentOutputGlobalIndex));
154
155        Value *enterNewOutputBlock = iBuilder->CreateOr(
156                iBuilder->CreateICmpUGT(currentStartGlobalBlockIndex, currentOutputGlobalIndex),
157                iBuilder->CreateICmpUGT(currentEndGlobalBlockIndex, currentOutputGlobalIndex)
158        );
159
160
161        Value *carryBitIntVec = iBuilder->CreateInsertElement(BIT_BLOCK_ZERO, phiCarryBit, (uint64_t) 0);
162        Value *newBlockStartWithCarry = iBuilder->simd_add(BIT_BLOCK_WIDTH, newBlockStartData, carryBitIntVec);
163
164
165        // Avoid branch mis-prediction by always storing output block
166        Value *outputData = iBuilder->simd_sub(BIT_BLOCK_WIDTH, newBlockEndData, newBlockStartWithCarry);
167
168        iBuilder->CreateBlockAlignedStore(outputData, iBuilder->getOutputStreamBlockPtr(OUTPUT_BIT_STREAM_NAME, SIZE_ZERO, phiCurrentOutputIndex));
169
170        // Handle PHINodes
171
172        // When currentStartLocalBlockIndex < phiCurrentOutputIndex && currentEndLocalBlockIndex < phiCurrentOutputIndex
173        // this round of loop will do nothing, and currentItemIndex += 1
174        phiCurrentItemIndex->addIncoming(
175                iBuilder->CreateSelect(
176                        enterNewOutputBlock,
177                        phiCurrentItemIndex,
178                        iBuilder->CreateAdd(phiCurrentItemIndex, SIZE_ONE)
179                ),
180                iBuilder->GetInsertBlock()
181        );
182
183        phiCurrentOutputIndex->addIncoming(
184                iBuilder->CreateSelect(
185                        enterNewOutputBlock,
186                        iBuilder->CreateAdd(phiCurrentOutputIndex, SIZE_ONE),
187                        phiCurrentOutputIndex
188                ),
189                iBuilder->GetInsertBlock()
190        );
191
192        phiCurrentBlockStartData->addIncoming(
193                iBuilder->CreateSelect(
194                        enterNewOutputBlock,
195                        BIT_BLOCK_ZERO,
196                        newBlockStartData
197                ),
198                iBuilder->GetInsertBlock()
199        );
200
201        phiCurrentBlockEndData->addIncoming(
202                iBuilder->CreateSelect(
203                        enterNewOutputBlock,
204                        BIT_BLOCK_ZERO,
205                        newBlockEndData
206                ),
207                iBuilder->GetInsertBlock()
208        );
209
210        Value *newCarryBit = iBuilder->CreateSelect(this->intVecGT(iBuilder, newBlockStartWithCarry, newBlockEndData),
211                                                    INT64_ONE, INT64_ZERO);
212
213//        iBuilder->CallPrintInt("newCarryBit", newCarryBit );
214
215        phiCarryBit->addIncoming(
216                iBuilder->CreateSelect(
217                        enterNewOutputBlock,
218                        newCarryBit,
219                        phiCarryBit
220                ),
221                iBuilder->GetInsertBlock()
222        );
223
224
225        iBuilder->CreateBr(multiBlockLoopConBlock);
226
227        // multiBlockLoopExitBlock
228        iBuilder->SetInsertPoint(multiBlockLoopExitBlock);
229
230        iBuilder->setScalarField(PENDING_START_DATA_KEY, phiCurrentBlockStartData);
231        iBuilder->setScalarField(PENDING_END_DATA_KEY, phiCurrentBlockEndData);
232        iBuilder->setScalarField("carryBit", phiCarryBit);
233
234        carryBitIntVec = iBuilder->CreateInsertElement(BIT_BLOCK_ZERO, phiCarryBit, (uint64_t) 0);
235        Value *finalOutputData = iBuilder->simd_sub(
236                BIT_BLOCK_WIDTH,
237                phiCurrentBlockEndData,
238                iBuilder->simd_add(BIT_BLOCK_WIDTH, phiCurrentBlockStartData, carryBitIntVec)
239        );
240
241        BasicBlock *storeFinalBlock = iBuilder->CreateBasicBlock("storeFinalBlock");
242        BasicBlock *storeFinalBlockEnd = iBuilder->CreateBasicBlock("storeFinalBlockEnd");
243
244        iBuilder->CreateUnlikelyCondBr(isFinalBlock, storeFinalBlock, storeFinalBlockEnd);
245        iBuilder->SetInsertPoint(storeFinalBlock);
246
247//        iBuilder->CallPrintRegister("finalOutputData", finalOutputData);
248        iBuilder->CreateBlockAlignedStore(finalOutputData, iBuilder->getOutputStreamBlockPtr(OUTPUT_BIT_STREAM_NAME, SIZE_ZERO, phiCurrentOutputIndex)); //Possible overflow here if this store always happen
249        iBuilder->CreateBr(storeFinalBlockEnd);
250        iBuilder->SetInsertPoint(storeFinalBlockEnd);
251
252        // Processed Item Count and Produced Item Count
253        Value *newProcessedItemCount = iBuilder->CreateAdd(iBuilder->getProcessedItemCount(START_NUM_STREAM_NAME),
254                                                           iBuilder->CreateSub(phiCurrentItemIndex,
255                                                                               initCurrentItemIndex));
256
257
258        iBuilder->setProcessedItemCount(START_NUM_STREAM_NAME, newProcessedItemCount);
259        iBuilder->setProcessedItemCount(END_NUM_STREAM_NAME, newProcessedItemCount);
260
261        Value *lastEndPos = this->loadInt64NumberInput(iBuilder, END_NUM_STREAM_NAME, iBuilder->CreateSub(phiCurrentItemIndex, SIZE_ONE));
262
263        iBuilder->setProducedItemCount(OUTPUT_BIT_STREAM_NAME,
264                                       iBuilder->CreateSelect(
265                                               isFinalBlock,
266                                               lastEndPos,
267                                               iBuilder->CreateAdd(
268                                                       iBuilder->CreateMul(phiCurrentOutputIndex, SIZE_BIT_BLOCK_WIDTH),
269                                                       iBuilder->getProducedItemCount(OUTPUT_BIT_STREAM_NAME)
270                                               )
271                                       )
272        );
273//        iBuilder->CallPrintInt("isFinalBlock", isFinalBlock);
274//        iBuilder->CallPrintInt("producedItemCount", iBuilder->getProducedItemCount(OUTPUT_BIT_STREAM_NAME));
275    }
276
277    size_t LZ4NumbersToBitstreamKernel::getAnyBufferSize(const std::unique_ptr<KernelBuilder> &iBuilder,
278                                                          std::string bufferName) {
279        return this->getAnyStreamSetBuffer(bufferName)->getBufferBlocks() * iBuilder->getStride();
280    }
281
282    /*
283     * iBuilder: kernel builder
284     * intVec: BitBlockType
285     * pos: size_t, 0 - bitBlockWidth, position of bit 1
286     * isSet: i1, when isSet == true, bit 1 will be set, otherwise this function do nothing
287     * */
288    Value *LZ4NumbersToBitstreamKernel::setIntVectorBitOne(const std::unique_ptr<KernelBuilder> &iBuilder,
289                                                            llvm::Value *intVec, llvm::Value *pos, llvm::Value *isSet) {
290        Type* BIT_BLOCK_TYPE = iBuilder->getBitBlockType();
291        Type* BIT_BLOCK_WIDTH_INT_TYPE = iBuilder->getIntNTy(iBuilder->getBitBlockWidth());
292
293        Value* sourceInt = iBuilder->CreateBitCast(intVec, BIT_BLOCK_WIDTH_INT_TYPE);
294        Value *oneBit = iBuilder->CreateShl(
295                iBuilder->CreateSelect(isSet, ConstantInt::get(BIT_BLOCK_WIDTH_INT_TYPE, 1),
296                                       ConstantInt::get(BIT_BLOCK_WIDTH_INT_TYPE, 0)),
297                iBuilder->CreateZExt(pos, BIT_BLOCK_WIDTH_INT_TYPE)
298        );
299        return iBuilder->CreateBitCast(iBuilder->CreateOr(sourceInt, oneBit), BIT_BLOCK_TYPE);
300    }
301
302    Value *LZ4NumbersToBitstreamKernel::intVecGT(const std::unique_ptr<KernelBuilder> &iBuilder, llvm::Value *intVec1,
303                                                  llvm::Value *intVec2) {
304        unsigned int BIT_BLOCK_WIDTH = iBuilder->getBitBlockWidth();
305        Value *gt = iBuilder->simd_ugt(BIT_BLOCK_WIDTH, intVec1, intVec2);
306        return iBuilder->CreateNot(iBuilder->CreateICmpEQ(iBuilder->CreateExtractElement(gt, (uint64_t) 0),
307                                                          iBuilder->getIntN(BIT_BLOCK_WIDTH, 0)));
308    }
309
310
311    LZ4NumbersToBitstreamKernel::LZ4NumbersToBitstreamKernel(std::string kernelName,
312                                                               const std::unique_ptr<kernel::KernelBuilder> &iBuilder)
313            : MultiBlockKernel(string(kernelName),
314            // Inputs
315                               {
316                                       Binding{iBuilder->getStreamSetTy(1, 64), START_NUM_STREAM_NAME,
317                                               BoundedRate(0, 1), AlwaysConsume()},
318                                       Binding{iBuilder->getStreamSetTy(1, 64), END_NUM_STREAM_NAME, BoundedRate(0, 1),
319                                               AlwaysConsume()}
320                               },
321            //Outputs
322                               {
323//                                       Binding{iBuilder->getStreamSetTy(1, 1), OUTPUT_BIT_STREAM_NAME,
324//                                           UnknownRate()}
325                                       Binding{iBuilder->getStreamSetTy(1, 1), OUTPUT_BIT_STREAM_NAME,
326                                                   BoundedRate(0, 1)}   //TODO BoundedRate is a workaround, it should be UnknownRate in the future
327                               },
328            //Arguments
329                               {
330                               },
331                               {},
332            //Internal states:
333                               {
334                    Binding(iBuilder->getBitBlockType(), PENDING_START_DATA_KEY),
335                    Binding(iBuilder->getBitBlockType(), PENDING_END_DATA_KEY),
336                    Binding(iBuilder->getIntNTy(64), "carryBit"),
337            }) {
338//        addAttribute(CanTerminateEarly());
339//        setNoTerminateAttribute(true);
340        addAttribute(MustExplicitlyTerminate());
341    }
342}
Note: See TracBrowser for help on using the repository browser.