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

Last change on this file since 5885 was 5885, checked in by xwa163, 12 months ago

Implement lz4_numbers_to_bitstream_kernel in new kernel infrastructure, fix bug of extract and deposit processes of lz4_ext_dep in large data.

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