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

Last change on this file since 5905 was 5895, checked in by xwa163, 18 months ago
  1. Fix match copy kernel in large file for new infrastructure
  2. Enable testing for full LZ4 decode pipeline
File size: 19.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    void LZ4NumbersToBitstreamKernel::generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> &iBuilder,
23                                                               llvm::Value *const numOfStrides) {
24
25//        iBuilder->CallPrintInt("======Entry", iBuilder->getSize(0));
26//        iBuilder->CallPrintInt("mIsFinal", mIsFinal);
27//        iBuilder->CallPrintInt("numOfStrides", numOfStrides);
28
29        // Const
30        Constant *SIZE_ZERO = iBuilder->getSize(0);
31        Constant *SIZE_ONE = iBuilder->getSize(1);
32        Constant *INT64_ZERO = iBuilder->getInt64(0);
33        Constant *INT64_ONE = iBuilder->getInt64(1);
34        Constant *BIT_BLOCK_ZERO = llvm::ConstantVector::get(
35                {INT64_ZERO, INT64_ZERO, INT64_ZERO, INT64_ZERO}); // TODO Assumed bit block type is always <4 * i64>
36        unsigned int BIT_BLOCK_WIDTH = iBuilder->getBitBlockWidth();
37        Constant *SIZE_BIT_BLOCK_WIDTH = iBuilder->getSize(BIT_BLOCK_WIDTH);
38
39
40        size_t outputBufferBlocks = this->getAnyBufferSize(iBuilder, OUTPUT_BIT_STREAM_NAME) / iBuilder->getStride();
41        Value *outputRawBeginPtr = iBuilder->CreatePointerCast(
42                iBuilder->getRawOutputPointer(OUTPUT_BIT_STREAM_NAME, SIZE_ZERO),
43                iBuilder->getBitBlockType()->getPointerTo());
44        Value *outputCurrentPtr = iBuilder->getOutputStreamBlockPtr(OUTPUT_BIT_STREAM_NAME, SIZE_ZERO);
45        Value *offset = iBuilder->CreatePtrDiff(outputCurrentPtr, outputRawBeginPtr);
46        Value *remainSpace = iBuilder->CreateSub(iBuilder->getSize(outputBufferBlocks), offset);
47//        iBuilder->CallPrintInt("remainSpace",
48//                               remainSpace); //TODO workaround here, kernel infrastructure should provide the information about how much data we can produced
49
50
51        BasicBlock *entryBlock = iBuilder->GetInsertBlock();
52
53
54        Value *itemsToDo = mAvailableItemCount[0];
55//        iBuilder->CallPrintInt("itemsToDo", itemsToDo);
56        Value *isFinalBlock = iBuilder->CreateICmpEQ(itemsToDo, iBuilder->getSize(0));
57        iBuilder->setTerminationSignal(isFinalBlock);
58
59        Value *itemProcessed = iBuilder->getProcessedItemCount(START_NUM_STREAM_NAME);
60        Value *oldProducedItemCount = iBuilder->getProducedItemCount(OUTPUT_BIT_STREAM_NAME);
61        Value *oldProducedOutputBlockIndex = iBuilder->CreateUDiv(oldProducedItemCount,
62                                                                  SIZE_BIT_BLOCK_WIDTH); // always produce full block except for final block
63
64
65//        Value *initCurrentItemIndex = iBuilder->CreateSelect(
66//                isFinalBlock,
67//                SIZE_ZERO,
68//                iBuilder->CreateURem(itemProcessed, SIZE_BIT_BLOCK_WIDTH)
69//        );
70
71        Value *initCurrentItemIndex = iBuilder->CreateURem(itemProcessed, SIZE_BIT_BLOCK_WIDTH);
72
73        Value *initOutputIndex = SIZE_ZERO;
74
75//        Value *availableOutputBlocks = iBuilder->CreateSelect(mIsFinal, iBuilder->getSize(32), numOfStrides); //TODO workaround here
76//        Value *availableOutputBlocks = numOfStrides;
77//        Value *availableOutputBlocks = remainSpace;
78        Value *availableOutputBlocks = iBuilder->CreateUMin(remainSpace, numOfStrides);
79
80        // TODO handle input pointer
81        Value *inputStartBasePtr = iBuilder->getInputStreamBlockPtr(START_NUM_STREAM_NAME, SIZE_ZERO);
82        inputStartBasePtr = iBuilder->CreatePointerCast(inputStartBasePtr, iBuilder->getInt64Ty()->getPointerTo());
83        Value *inputEndBasePtr = iBuilder->getInputStreamBlockPtr(END_NUM_STREAM_NAME, SIZE_ZERO);
84        inputEndBasePtr = iBuilder->CreatePointerCast(inputEndBasePtr, iBuilder->getInt64Ty()->getPointerTo());
85        Value *outputBasePtr = iBuilder->getOutputStreamBlockPtr(OUTPUT_BIT_STREAM_NAME, SIZE_ZERO);
86        Value *initCarryBit = iBuilder->getScalarField("carryBit");
87
88//        iBuilder->CallPrintInt("itemProcessed", itemProcessed);
89//        iBuilder->CallPrintInt("inputStartBasePtr", inputStartBasePtr);
90
91        Value *initCurrentBlockStartData = iBuilder->getScalarField(PENDING_START_DATA_KEY);
92        Value *initCurrentBlockEndData = iBuilder->getScalarField(PENDING_END_DATA_KEY);
93
94
95        BasicBlock *multiBlockLoopConBlock = iBuilder->CreateBasicBlock("multiBlockLoopConBlock");
96        BasicBlock *multiBlockLoopBodyBlock = iBuilder->CreateBasicBlock("multiBlockLoopBodyBlock");
97        BasicBlock *multiBlockLoopExitBlock = iBuilder->CreateBasicBlock("multiBlockLoopExitBlock");
98
99        iBuilder->CreateBr(multiBlockLoopConBlock);
100
101        // multiBlockLoopConBlock
102        iBuilder->SetInsertPoint(multiBlockLoopConBlock);
103        PHINode *phiCurrentItemIndex = iBuilder->CreatePHI(iBuilder->getSizeTy(), 2);
104        phiCurrentItemIndex->addIncoming(initCurrentItemIndex, entryBlock);
105
106        PHINode *phiCurrentOutputIndex = iBuilder->CreatePHI(iBuilder->getSizeTy(), 2);
107        phiCurrentOutputIndex->addIncoming(initOutputIndex, entryBlock);
108
109        PHINode *phiCurrentBlockStartData = iBuilder->CreatePHI(iBuilder->getBitBlockType(), 2);
110        phiCurrentBlockStartData->addIncoming(initCurrentBlockStartData, entryBlock);
111
112        PHINode *phiCurrentBlockEndData = iBuilder->CreatePHI(iBuilder->getBitBlockType(), 2);
113        phiCurrentBlockEndData->addIncoming(initCurrentBlockEndData, entryBlock);
114
115        PHINode *phiCarryBit = iBuilder->CreatePHI(iBuilder->getInt64Ty(), 2);
116        phiCarryBit->addIncoming(initCarryBit, entryBlock);
117
118
119        // TODO It is possible that in final block, not all items have been processed, while the output buffer is not enough. This situation need to be verified later
120        // phiCurrentItemIndex < itemsToDo && currentOutputIndex < availableOutputBlocks
121//        iBuilder->CallPrintInt("phiCurrentItemIndex", phiCurrentItemIndex);
122//        iBuilder->CallPrintInt("aaa", iBuilder->CreateAdd(itemsToDo, initCurrentItemIndex));
123        iBuilder->CreateCondBr(
124                iBuilder->CreateAnd(
125                        iBuilder->CreateICmpULT(phiCurrentItemIndex, iBuilder->CreateAdd(itemsToDo,
126                                                                                         initCurrentItemIndex)), //TODO should not be itemsToDo here, may be itemsToDo + initCurrentItemIndex
127                        iBuilder->CreateICmpULT(phiCurrentOutputIndex, availableOutputBlocks)
128                ),
129                multiBlockLoopBodyBlock,
130                multiBlockLoopExitBlock
131        );
132
133        // multiBlockLoopBodyBlock
134        iBuilder->SetInsertPoint(multiBlockLoopBodyBlock);
135
136        Value *currentOutputGlobalIndex = iBuilder->CreateAdd(phiCurrentOutputIndex, oldProducedOutputBlockIndex);
137
138        // StartBits
139        Value *currentStartPos = iBuilder->CreateLoad(iBuilder->CreateGEP(inputStartBasePtr, phiCurrentItemIndex));
140        Value *currentStartGlobalBlockIndex = iBuilder->CreateUDiv(currentStartPos, SIZE_BIT_BLOCK_WIDTH);
141//        Value *currentStartLocalBlockIndex = iBuilder->CreateSub(currentStartGlobalBlockIndex,
142//                                                                 oldProducedOutputBlockIndex);
143//        iBuilder->CallPrintInt("currentStartLocalBlockIndex", currentStartLocalBlockIndex); //TODO overflow here
144
145
146        Value *currentStartLocalBlockOffset = iBuilder->CreateURem(currentStartPos,
147                                                                   SIZE_BIT_BLOCK_WIDTH); // 0 ~ BIT_BLOCK_WIDTH
148
149        Value *newBlockStartData = this->setIntVectorBitOne(iBuilder, phiCurrentBlockStartData,
150                                                            currentStartLocalBlockOffset,
151                                                            iBuilder->CreateICmpEQ(currentStartGlobalBlockIndex,
152                                                                                   currentOutputGlobalIndex));
153//        iBuilder->CallPrintRegister("phiCurrentBlockStartData", phiCurrentBlockStartData);
154//        iBuilder->CallPrintRegister("newBlockStartData", newBlockStartData);
155//        iBuilder->CallPrintInt("currentStartPos", currentStartPos);
156//        iBuilder->CallPrintInt("----", SIZE_ZERO);
157
158
159        // EndBits
160        Value *currentEndPos = iBuilder->CreateLoad(iBuilder->CreateGEP(inputEndBasePtr, phiCurrentItemIndex));
161        Value *currentEndGlobalBlockIndex = iBuilder->CreateUDiv(currentEndPos, SIZE_BIT_BLOCK_WIDTH);
162//        Value *currentEndLocalBlockIndex = iBuilder->CreateSub(currentEndGlobalBlockIndex, oldProducedOutputBlockIndex);
163
164        Value *currentEndLocalBlockOffset = iBuilder->CreateURem(currentEndPos,
165                                                                 SIZE_BIT_BLOCK_WIDTH); // 0 ~ BIT_BLOCK_WIDTH
166
167
168        Value *newBlockEndData = this->setIntVectorBitOne(iBuilder, phiCurrentBlockEndData, currentEndLocalBlockOffset,
169                                                          iBuilder->CreateICmpEQ(currentEndGlobalBlockIndex,
170                                                                                 currentOutputGlobalIndex));
171//            iBuilder->CallPrintInt("%%%currentEndPos", currentEndPos);
172//            iBuilder->CallPrintRegister("%%%newBlockEndData", newBlockEndData);
173//        iBuilder->CallPrintInt("currentEndPos", currentEndPos);
174
175        Value *enterNewOutputBlock = iBuilder->CreateOr(
176                iBuilder->CreateICmpUGT(currentStartGlobalBlockIndex, currentOutputGlobalIndex),
177                iBuilder->CreateICmpUGT(currentEndGlobalBlockIndex, currentOutputGlobalIndex)
178        );
179
180
181        Value *carryBitIntVec = iBuilder->CreateInsertElement(BIT_BLOCK_ZERO, phiCarryBit, (uint64_t) 0);
182        Value *newBlockStartWithCarry = iBuilder->simd_add(BIT_BLOCK_WIDTH, newBlockStartData, carryBitIntVec);
183
184
185        // Avoid branch mis-prediction by always storing output block
186        Value *outputData = iBuilder->simd_sub(BIT_BLOCK_WIDTH, newBlockEndData, newBlockStartWithCarry);
187//        iBuilder->CallPrintInt("----store", iBuilder->getSize(0));
188//        iBuilder->CallPrintInt("carry", phiCarryBit);
189//        iBuilder->CallPrintRegister("newBlockEndData", newBlockEndData);
190//        iBuilder->CallPrintRegister("newBlockStartWithCarry", newBlockStartWithCarry);
191//        iBuilder->CallPrintInt("----outputPtr", iBuilder->CreateGEP(outputBasePtr, phiCurrentOutputIndex));
192//        iBuilder->CallPrintRegister("outputData", outputData);
193        iBuilder->CreateBlockAlignedStore(outputData, iBuilder->CreateGEP(outputBasePtr, phiCurrentOutputIndex));
194
195        // Handle PHINodes
196
197        // When currentStartLocalBlockIndex < phiCurrentOutputIndex && currentEndLocalBlockIndex < phiCurrentOutputIndex
198        // this round of loop will do nothing, and currentItemIndex += 1
199        phiCurrentItemIndex->addIncoming(
200                iBuilder->CreateSelect(
201                        enterNewOutputBlock,
202                        phiCurrentItemIndex,
203                        iBuilder->CreateAdd(phiCurrentItemIndex, SIZE_ONE)
204                ),
205                iBuilder->GetInsertBlock()
206        );
207
208        phiCurrentOutputIndex->addIncoming(
209                iBuilder->CreateSelect(
210                        enterNewOutputBlock,
211                        iBuilder->CreateAdd(phiCurrentOutputIndex, SIZE_ONE),
212                        phiCurrentOutputIndex
213                ),
214                iBuilder->GetInsertBlock()
215        );
216
217        phiCurrentBlockStartData->addIncoming(
218                iBuilder->CreateSelect(
219                        enterNewOutputBlock,
220                        BIT_BLOCK_ZERO,
221                        newBlockStartData
222                ),
223                iBuilder->GetInsertBlock()
224        );
225
226        phiCurrentBlockEndData->addIncoming(
227                iBuilder->CreateSelect(
228                        enterNewOutputBlock,
229                        BIT_BLOCK_ZERO,
230                        newBlockEndData
231                ),
232                iBuilder->GetInsertBlock()
233        );
234
235        Value *newCarryBit = iBuilder->CreateSelect(this->intVecGT(iBuilder, newBlockStartWithCarry, newBlockEndData),
236                                                    INT64_ONE, INT64_ZERO);
237
238//        iBuilder->CallPrintInt("newCarryBit", newCarryBit );
239
240        phiCarryBit->addIncoming(
241                iBuilder->CreateSelect(
242                        enterNewOutputBlock,
243                        newCarryBit,
244                        phiCarryBit
245                ),
246                iBuilder->GetInsertBlock()
247        );
248
249
250        iBuilder->CreateBr(multiBlockLoopConBlock);
251
252        // multiBlockLoopExitBlock
253        iBuilder->SetInsertPoint(multiBlockLoopExitBlock);
254
255        iBuilder->setScalarField(PENDING_START_DATA_KEY, phiCurrentBlockStartData);
256        iBuilder->setScalarField(PENDING_END_DATA_KEY, phiCurrentBlockEndData);
257        iBuilder->setScalarField("carryBit", phiCarryBit);
258
259        carryBitIntVec = iBuilder->CreateInsertElement(BIT_BLOCK_ZERO, phiCarryBit, (uint64_t) 0);
260        Value *finalOutputData = iBuilder->simd_sub(
261                BIT_BLOCK_WIDTH,
262                phiCurrentBlockEndData,
263                iBuilder->simd_add(BIT_BLOCK_WIDTH, phiCurrentBlockStartData, carryBitIntVec)
264        );
265//        iBuilder->CallPrintRegister("%%%phiCurrentBlockEndData", phiCurrentBlockEndData);
266//            iBuilder->CallPrintInt("----outputPtrFinal", iBuilder->CreateGEP(outputBasePtr, phiCurrentOutputIndex));
267
268        BasicBlock *storeFinalBlock = iBuilder->CreateBasicBlock("storeFinalBlock");
269        BasicBlock *storeFinalBlockEnd = iBuilder->CreateBasicBlock("storeFinalBlockEnd");
270
271        iBuilder->CreateUnlikelyCondBr(isFinalBlock, storeFinalBlock, storeFinalBlockEnd);
272        iBuilder->SetInsertPoint(storeFinalBlock);
273
274//        iBuilder->CallPrintRegister("finalOutputData", finalOutputData);
275        iBuilder->CreateBlockAlignedStore(finalOutputData, iBuilder->CreateGEP(outputBasePtr,
276                                                                   phiCurrentOutputIndex)); //Possible overflow here if this store always happen
277        iBuilder->CreateBr(storeFinalBlockEnd);
278        iBuilder->SetInsertPoint(storeFinalBlockEnd);
279
280        // Processed Item Count and Produced Item Count
281        Value *newProcessedItemCount = iBuilder->CreateAdd(iBuilder->getProcessedItemCount(START_NUM_STREAM_NAME),
282                                                           iBuilder->CreateSub(phiCurrentItemIndex,
283                                                                               initCurrentItemIndex));
284
285
286        iBuilder->setProcessedItemCount(START_NUM_STREAM_NAME, newProcessedItemCount);
287        iBuilder->setProcessedItemCount(END_NUM_STREAM_NAME, newProcessedItemCount);
288
289        Value *lastEndPos = iBuilder->CreateLoad(
290                iBuilder->CreateGEP(inputEndBasePtr, iBuilder->CreateSub(phiCurrentItemIndex, SIZE_ONE)));
291//        iBuilder->CallPrintInt("lastEndPos", lastEndPos);
292
293        iBuilder->setProducedItemCount(OUTPUT_BIT_STREAM_NAME,
294                                       iBuilder->CreateSelect(
295                                               isFinalBlock,
296                                               lastEndPos,
297                                               iBuilder->CreateAdd(
298                                                       iBuilder->CreateMul(phiCurrentOutputIndex, SIZE_BIT_BLOCK_WIDTH),
299                                                       iBuilder->getProducedItemCount(OUTPUT_BIT_STREAM_NAME)
300                                               )
301                                       )
302        );
303//        iBuilder->CallPrintInt("isFinalBlock", isFinalBlock);
304//        iBuilder->CallPrintInt("producedItemCount", iBuilder->getProducedItemCount(OUTPUT_BIT_STREAM_NAME));
305    }
306
307    size_t LZ4NumbersToBitstreamKernel::getAnyBufferSize(const std::unique_ptr<KernelBuilder> &iBuilder,
308                                                          std::string bufferName) {
309        return this->getAnyStreamSetBuffer(bufferName)->getBufferBlocks() * iBuilder->getStride();
310    }
311
312    /*
313     * iBuilder: kernel builder
314     * intVec: BitBlockType, <4 * i64>
315     * pos: size_t, 0 - 256, position of bit 1
316     * isSet: i1, when isSet == true, bit 1 will be set, otherwise this function do nothing
317     * */
318    Value *LZ4NumbersToBitstreamKernel::setIntVectorBitOne(const std::unique_ptr<KernelBuilder> &iBuilder,
319                                                            llvm::Value *intVec, llvm::Value *pos, llvm::Value *isSet) {
320        Value *SIZE_64 = iBuilder->getSize(64); //TODO assume bit block type will always be <4 * i64>
321        Value *blockIndex = iBuilder->CreateUDiv(pos, SIZE_64);
322        Value *blockOffset = iBuilder->CreateURem(pos, SIZE_64);
323
324        Value *oldValue = iBuilder->CreateExtractElement(intVec, blockIndex);
325        // Use select to avoid branch misprediction
326        Value *bitOneValue = iBuilder->CreateShl(
327                iBuilder->CreateSelect(isSet, iBuilder->getInt64(1), iBuilder->getInt64(0)),
328                blockOffset
329        );
330        Value *newValue = iBuilder->CreateOr(oldValue, bitOneValue);
331        return iBuilder->CreateInsertElement(intVec, newValue, blockIndex);
332    }
333
334    Value *LZ4NumbersToBitstreamKernel::intVecGT(const std::unique_ptr<KernelBuilder> &iBuilder, llvm::Value *intVec1,
335                                                  llvm::Value *intVec2) {
336        unsigned int BIT_BLOCK_WIDTH = iBuilder->getBitBlockWidth();
337        Value *gt = iBuilder->simd_ugt(BIT_BLOCK_WIDTH, intVec1, intVec2);
338        return iBuilder->CreateNot(iBuilder->CreateICmpEQ(iBuilder->CreateExtractElement(gt, (uint64_t) 0),
339                                                          iBuilder->getIntN(BIT_BLOCK_WIDTH, 0)));
340    }
341
342
343    LZ4NumbersToBitstreamKernel::LZ4NumbersToBitstreamKernel(std::string kernelName,
344                                                               const std::unique_ptr<kernel::KernelBuilder> &iBuilder)
345            : MultiBlockKernel(string(kernelName),
346            // Inputs
347                               {
348                                       Binding{iBuilder->getStreamSetTy(1, 64), START_NUM_STREAM_NAME,
349                                               BoundedRate(0, 1), AlwaysConsume()},
350                                       Binding{iBuilder->getStreamSetTy(1, 64), END_NUM_STREAM_NAME, BoundedRate(0, 1),
351                                               AlwaysConsume()}
352                               },
353            //Outputs
354                               {
355//                                       Binding{iBuilder->getStreamSetTy(1, 1), OUTPUT_BIT_STREAM_NAME,
356//                                           UnknownRate()}
357                                       Binding{iBuilder->getStreamSetTy(1, 1), OUTPUT_BIT_STREAM_NAME,
358                                                   BoundedRate(0, 1)}   //TODO BoundedRate is a workaround, it should be UnknownRate in the future
359                               },
360            //Arguments
361                               {
362                               },
363                               {},
364            //Internal states:
365                               {
366                    Binding(iBuilder->getBitBlockType(), PENDING_START_DATA_KEY),
367                    Binding(iBuilder->getBitBlockType(), PENDING_END_DATA_KEY),
368                    Binding(iBuilder->getIntNTy(64), "carryBit"),
369            }) {
370//        addAttribute(CanTerminateEarly());
371//        setNoTerminateAttribute(true);
372        addAttribute(MustExplicitlyTerminate());
373    }
374}
Note: See TracBrowser for help on using the repository browser.