source: icGREP/icgrep-devel/icgrep/kernels/lz4/decompression/lz4_parallel_bytestream_decompression.cpp @ 6136

Last change on this file since 6136 was 6136, checked in by xwa163, 12 months ago
  1. Cleanup legacy slow LZ4 related kernels
  2. Rename lz4d_ext_dep to lz4_decompression
  3. Rename LZ4 AIO related kernels to LZ4 Decompression Kernel
File size: 104.2 KB
Line 
1
2#include "lz4_parallel_bytestream_decompression.h"
3
4#include <kernels/kernel_builder.h>
5#include <iostream>
6#include <string>
7#include <llvm/Support/raw_ostream.h>
8#include <kernels/streamset.h>
9#include <IR_Gen/idisa_target.h>
10
11using namespace llvm;
12using namespace kernel;
13using namespace std;
14
15
16#define SIMD_WIDTH (64)
17
18
19namespace kernel{
20
21    LZ4ParallelByteStreamDecompressionKernel::LZ4ParallelByteStreamDecompressionKernel(const std::unique_ptr<kernel::KernelBuilder> &b, unsigned lz4BlockSize, bool enableGather, bool enableScatter, int minParallelLevel)
22            :SegmentOrientedKernel("LZ4ParallelByteStreamDecompressionKernel",
23            // Inputs
24                                   {
25                    Binding{b->getStreamSetTy(1, 8), "byteStream", BoundedRate(0, 1)},
26
27                    // block data
28                    Binding{b->getStreamSetTy(1, 8), "isCompressed", BoundedRate(0, 1), AlwaysConsume()},
29                    Binding{b->getStreamSetTy(1, 64), "blockStart", RateEqualTo("isCompressed"), AlwaysConsume()},
30                    Binding{b->getStreamSetTy(1, 64), "blockEnd", RateEqualTo("isCompressed"), AlwaysConsume()}
31
32            },
33            //Outputs
34                                   {
35                                           Binding{b->getStreamSetTy(1, 8), "outputStream", BoundedRate(0, 1)},
36                                   },
37            //Arguments
38                                   {
39                                           Binding{b->getSizeTy(), "fileSize"}
40                                   },
41                                   {},
42            //Internal states:
43                                   {
44                                           Binding{b->getInt64Ty(), "tempTimes"},
45                                           Binding{b->getIntNTy(SIMD_WIDTH), "outputPos"},
46                                           Binding{b->getBitBlockType(), "placeholder"},
47
48                                   }),
49             mLz4BlockSize(lz4BlockSize),
50             mEnableGather(enableGather),
51             mEnableScatter(enableScatter),
52             mMininumParallelLevel(minParallelLevel)
53    {
54        this->setStride(mLz4BlockSize * b->getBitBlockWidth() / SIMD_WIDTH);
55        addAttribute(MustExplicitlyTerminate());
56//        this->initParallelLevelMeasurement(b);
57    }
58
59    // Kernel Methods
60    void LZ4ParallelByteStreamDecompressionKernel::generateDoSegmentMethod(const std::unique_ptr<KernelBuilder> &b) {
61        this->initializeConstantsAndTypes(b);
62
63        // Constant
64        Value* SIZE_1 = b->getSize(1);
65
66        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
67
68        Value * blockDataIndex = b->getProcessedItemCount("isCompressed");
69        Value * totalNumber = b->getAvailableItemCount("isCompressed");
70//        b->CallPrintInt("totalNumber", totalNumber);
71        Value * fileSize = b->getScalarField("fileSize");
72        Value * availableNumber = b->CreateSub(totalNumber, blockDataIndex);
73        Value * lastBlockEnd = this->generateLoadInt64NumberInput(b, "blockEnd", b->CreateSub(totalNumber, SIZE_1));
74        Value * isTerminal = b->CreateAnd(b->CreateICmpEQ(fileSize, lastBlockEnd), b->CreateICmpULE(availableNumber, b->getSize(b->getBitBlockWidth() / SIMD_WIDTH)));
75        b->setTerminationSignal(isTerminal);
76
77        BasicBlock* simdProcessEntryBlock = b->CreateBasicBlock("simdProcessEntryBlock");
78        BasicBlock* notEnoughSimdDataBlock = b->CreateBasicBlock("notEnoughSimdDataBlock");
79
80        b->CreateLikelyCondBr(b->CreateICmpUGE(availableNumber, b->getSize(b->getBitBlockWidth() / SIMD_WIDTH)), simdProcessEntryBlock, notEnoughSimdDataBlock);
81
82        // ---- simdProcessEntryBlock
83        b->SetInsertPoint(simdProcessEntryBlock);
84        this->generateSimdDecompression2(b, blockDataIndex);
85        Value* newProcessedDataIndex = b->CreateAdd(blockDataIndex, b->getSize(b->getBitBlockWidth() / SIMD_WIDTH));
86        b->setProcessedItemCount("isCompressed", newProcessedDataIndex);
87
88        b->CreateBr(exitBlock);
89
90        // ---- notEnoughSimdDataBlock
91        b->SetInsertPoint(notEnoughSimdDataBlock);
92
93        BasicBlock* notSimdProcessBlock = b->CreateBasicBlock("notSimdProcessBlock");
94        b->CreateUnlikelyCondBr(isTerminal, notSimdProcessBlock, exitBlock);
95
96        // ---- notSimdProcessBlock
97        b->SetInsertPoint(notSimdProcessBlock);
98        // Use loop to process the remaining block in sequential approach (the number of the remaining block should be less than (b->getBitBlockWidth() / SIMD_WIDTH))
99        this->generateSequentialDecompression(b, blockDataIndex, totalNumber);
100        b->CreateBr(exitBlock);
101
102
103        // ---- ExitBlock
104        b->SetInsertPoint(exitBlock);
105
106        BasicBlock* printBlock = b->CreateBasicBlock("printBlock");
107        BasicBlock* realExitBlock = b->CreateBasicBlock("realExitBlock");
108        b->CreateCondBr(b->getTerminationSignal(), printBlock, realExitBlock);
109
110        b->SetInsertPoint(printBlock);
111//        this->printParallelLevelResult(b);
112//        b->CallPrintInt("tempTimes", b->getScalarField("tempTimes"));
113        b->CreateBr(realExitBlock);
114
115        b->SetInsertPoint(realExitBlock);
116    }
117
118    // ---- SIMD Processing
119
120
121    // ---- Sequential Processing
122
123
124
125
126
127
128    Value* LZ4ParallelByteStreamDecompressionKernel::generateSimdAcceleration(const std::unique_ptr<KernelBuilder> &b, llvm::Value *beginTokenPosVec,
129                                  llvm::Value *blockEndVec) {
130
131        /*
132        // TODO incomplete
133        // Constant
134        Function *gatherFunc = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx2_gather_d_q_256); // TODO find ret <4 * i32> version
135//        Function *gatherFunc2 = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx2_gather_d_q);
136
137        // ---- Entry Block
138        BasicBlock* entryBlock = b->GetInsertBlock();
139        Value* maskedTokenPosVec = b->CreateAnd(beginTokenPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(b->getCapacity("extender")))));
140        Value* maskBlockIndexVec = b->CreateLShr(beginTokenPosVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, std::log2(64))));
141        Value* maskBlockOffsetVec = b->CreateAnd(beginTokenPosVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 63)));
142        Value* extenderValueVec = b->CreateCall(
143                gatherFunc,
144                {
145                        UndefValue::get(b->getBitBlockType()),
146                        b->CreatePointerCast(b->getRawInputPointer("extender", b->getSize(0)), b->getInt8PtrTy()),
147                        b->CreateTrunc(maskBlockIndexVec, VectorType::get(b->getInt32Ty(), 4)),
148                        Constant::getAllOnesValue(b->getBitBlockType()),
149                        b->getInt8(8)
150                }
151        );
152
153        Value* extenderValueVec2 = b->CreateCall(
154                gatherFunc,
155                {
156                        UndefValue::get(VectorType::get(b->getInt8Ty(), 4)),
157                        b->CreatePointerCast(b->getRawInputPointer("extender", b->getSize(0)), b->getInt8PtrTy()),
158                        b->CreateTrunc(maskBlockIndexVec, VectorType::get(b->getInt32Ty(), 4)),
159                        Constant::getAllOnesValue(b->getBitBlockType()),
160                        b->getInt8(8)
161                }
162        );
163
164        Value* initTokeMarkersVec = b->CreateShl(b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 1)), maskBlockOffsetVec);
165
166//        b->CallPrintRegister("a", beginTokenPosVec);
167//        b->CallPrintRegister("maskedTokenPosVec", maskedTokenPosVec);
168//        b->CallPrintRegister("maskBlockIndexVec", maskBlockIndexVec);
169//        b->CallPrintRegister("gather_result", extenderValueVec);
170
171
172        BasicBlock* accelerationProcessBlock = b->CreateBasicBlock("accelerationProcessBlock");
173        BasicBlock* accelerationExitBlock = b->CreateBasicBlock("accelerationExitBlock");
174        b->CreateBr(accelerationProcessBlock);
175
176        // ---- AccelerationProcessBlock
177        b->SetInsertPoint(accelerationProcessBlock);
178        PHINode* phiTokenMarkersVec = b->CreatePHI(initTokeMarkersVec->getType(), 2);
179        phiTokenMarkersVec->addIncoming(initTokeMarkersVec, entryBlock);
180*/
181        return beginTokenPosVec;    //TODO
182
183    }
184
185    void LZ4ParallelByteStreamDecompressionKernel::initializeConstantsAndTypes(const std::unique_ptr<KernelBuilder> &b) {
186        // Constants
187        BIT_BLOCK_0 = ConstantVector::getNullValue(b->getBitBlockType());
188        BIT_BLOCK_1 = b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0x1));
189        BIT_BLOCK_F0 = b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0xf0));
190        BIT_BLOCK_0F = b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0x0f));
191        BIT_BLOCK_FF = b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0xff));
192        BIT_BLOCK_FFFF = b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0xffff));
193        INT_BIT_BLOCK_TY_0 = b->getIntN(b->getBitBlockWidth(), 0);
194        SIZE_0 = b->getSize(0);
195        SIZE_1 = b->getSize(1);
196        BYTE_FF = b->getInt8(0xff);
197        BYTE_F0 = b->getInt8(0xf0);
198        BYTE_0F = b->getInt8(0x0f);
199
200
201        // Types
202        INT_BIT_BLOCK_TY = b->getIntNTy(b->getBitBlockWidth());
203        BIT_BLOCK_TY = b->getBitBlockType();
204
205    }
206
207    std::pair<llvm::Value*, llvm::Value*> LZ4ParallelByteStreamDecompressionKernel::parallelParseLiteralInfo(const std::unique_ptr<KernelBuilder> &b, llvm::Value *tokenPosVec, llvm::Value* tokenValuesVec, llvm::Value* notFinishMask) {
208
209        Value* shouldExtendLiteralBitBlockVec = b->simd_eq(SIMD_WIDTH, b->simd_and(BIT_BLOCK_F0, tokenValuesVec), BIT_BLOCK_F0);
210        Value* extendLiteralParallelLevel = b->CreatePopcount(b->hsimd_signmask(SIMD_WIDTH, shouldExtendLiteralBitBlockVec));
211        BasicBlock* simdBlock = b->CreateBasicBlock("simdBlock");
212        BasicBlock* loopBlock = b->CreateBasicBlock("loopBlock");
213        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
214
215        b->CreateUnlikelyCondBr(b->CreateICmpUGE(extendLiteralParallelLevel, b->getInt32(mMininumParallelLevel)), simdBlock, loopBlock);
216
217        b->SetInsertPoint(simdBlock);
218        auto ret1 = this->simdParseLiteralInfo(b, tokenPosVec, tokenValuesVec, notFinishMask);
219        BasicBlock* simdBlockFinal = b->GetInsertBlock();
220        b->CreateBr(exitBlock);
221
222        b->SetInsertPoint(loopBlock);
223        auto ret2 = this->parseMultipleLiteralInfoByLoop(b, tokenPosVec, tokenValuesVec, notFinishMask);
224        BasicBlock* loopBlockFinal = b->GetInsertBlock();
225        b->CreateBr(exitBlock);
226
227        b->SetInsertPoint(exitBlock);
228        PHINode* phiLiteralStartVec = b->CreatePHI(BIT_BLOCK_TY, 2);
229        phiLiteralStartVec->addIncoming(ret1.first, simdBlockFinal);
230        phiLiteralStartVec->addIncoming(ret2.first, loopBlockFinal);
231
232        PHINode* phiLiteralLengthVec = b->CreatePHI(BIT_BLOCK_TY, 2);
233        phiLiteralLengthVec->addIncoming(ret1.second, simdBlockFinal);
234        phiLiteralLengthVec->addIncoming(ret2.second, loopBlockFinal);
235
236        return std::make_pair(phiLiteralStartVec, phiLiteralLengthVec);
237    };
238
239    std::pair<llvm::Value*, llvm::Value*> LZ4ParallelByteStreamDecompressionKernel::parseMultipleLiteralInfoByLoop(const std::unique_ptr<KernelBuilder> &b, llvm::Value *tokenPosVec, llvm::Value* tokenValuesVec, llvm::Value* notFinishMask) {
240        // ---- EntryBlock
241        BasicBlock* entryBlock = b->GetInsertBlock();
242        Value* initLiteralLengthVec = b->simd_srlv(SIMD_WIDTH, tokenValuesVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 4)));
243        Value* initLiteralStartVec = b->simd_add(SIMD_WIDTH, tokenPosVec, BIT_BLOCK_1);
244
245        Value* shouldExtendLiteralBitBlockVec = b->simd_and(b->simd_eq(SIMD_WIDTH, initLiteralLengthVec, BIT_BLOCK_0F), notFinishMask);
246        Value* extendLiteralSignMask = b->hsimd_signmask(SIMD_WIDTH, shouldExtendLiteralBitBlockVec);
247
248        BasicBlock* conBlock = b->CreateBasicBlock("conBlock");
249        BasicBlock* bodyBlock = b->CreateBasicBlock("bodyBlock");
250        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
251
252        b->CreateBr(conBlock);
253
254        // ---- ConBlock
255        b->SetInsertPoint(conBlock);
256        PHINode* phiSignMask = b->CreatePHI(extendLiteralSignMask->getType(), 2);
257        phiSignMask->addIncoming(extendLiteralSignMask, entryBlock);
258        PHINode* phiLiteralLengthVec = b->CreatePHI(initLiteralLengthVec->getType(), 2);
259        phiLiteralLengthVec->addIncoming(initLiteralLengthVec, entryBlock);
260        PHINode* phiLiteralStartVec = b->CreatePHI(initLiteralStartVec->getType(), 2);
261        phiLiteralStartVec->addIncoming(initLiteralStartVec, entryBlock);
262
263//        b->CallPrintInt("phiSignMask", phiSignMask);
264        b->CreateCondBr(b->CreateICmpNE(phiSignMask, b->getInt32(0)), bodyBlock, exitBlock);
265
266        // ---- BodyBlock
267        b->SetInsertPoint(bodyBlock);
268        Value* targetIndex = b->CreateCountForwardZeroes(phiSignMask);
269        Value* targetTokenPos = b->CreateExtractElement(tokenPosVec, targetIndex);
270        Value* targetTokenValue = b->CreateTrunc(b->CreateExtractElement(tokenValuesVec, targetIndex), b->getInt8Ty());
271
272        Value *newLiteralStart = nullptr, *newLiteralLength = nullptr;
273        std::tie(newLiteralStart, newLiteralLength) = this->parseLiteralInfo(b, targetTokenPos, targetTokenValue);
274        phiLiteralLengthVec->addIncoming(b->CreateInsertElement(phiLiteralLengthVec, newLiteralLength, targetIndex), b->GetInsertBlock());
275        phiLiteralStartVec->addIncoming(b->CreateInsertElement(phiLiteralStartVec, newLiteralStart, targetIndex), b->GetInsertBlock());
276        phiSignMask->addIncoming(b->CreateSub(phiSignMask, b->CreateShl(b->getInt32(1), targetIndex)), b->GetInsertBlock());
277        b->CreateBr(conBlock);
278
279        // ---- ExitBlock
280        b->SetInsertPoint(exitBlock);
281
282        return std::make_pair(phiLiteralStartVec, b->simd_and(phiLiteralLengthVec, notFinishMask));
283    };
284
285    std::pair<llvm::Value*, llvm::Value*> LZ4ParallelByteStreamDecompressionKernel::simdParseLiteralInfo(const std::unique_ptr<KernelBuilder> &b, Value *tokenPosVec, Value* tokenValuesVec, Value* notFinishMask) {
286        // ---- EntryBlock
287        BasicBlock* entryBlock = b->GetInsertBlock();
288        Value* byteRawInputPtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
289
290
291        Value* shouldExtendLiteralBitBlockVec = b->CreateZExt(b->CreateICmpEQ(b->CreateAnd(BIT_BLOCK_F0, tokenValuesVec), BIT_BLOCK_F0), b->getBitBlockType());
292        Value* shouldExtendLiteral = b->CreateICmpNE(b->CreateBitCast(shouldExtendLiteralBitBlockVec, INT_BIT_BLOCK_TY), INT_BIT_BLOCK_TY_0);
293
294        Value* initExtendLiteralPos = b->simd_add(SIMD_WIDTH, tokenPosVec, shouldExtendLiteralBitBlockVec);
295
296
297        BasicBlock* extendLiteralCond = b->CreateBasicBlock("extendLiteralCond");
298        BasicBlock* extendLiteralEnd = b->CreateBasicBlock("extendLiteralEnd");
299
300        b->CreateUnlikelyCondBr(shouldExtendLiteral, extendLiteralCond, extendLiteralEnd); //extend literal will not happen quite often
301
302        // ---- extendLiteralCond
303        b->SetInsertPoint(extendLiteralCond);
304        PHINode* phiCurrentExtendLiteralPosVec = b->CreatePHI(initExtendLiteralPos->getType(), 2);
305        phiCurrentExtendLiteralPosVec->addIncoming(initExtendLiteralPos, entryBlock);
306
307        PHINode* phiExtendLiteralLengthVec = b->CreatePHI(BIT_BLOCK_TY, 2);
308        phiExtendLiteralLengthVec->addIncoming(BIT_BLOCK_0, entryBlock);
309
310        PHINode* phiShouldExtendLiteralBitBlockVec = b->CreatePHI(shouldExtendLiteralBitBlockVec->getType(), 2);
311        phiShouldExtendLiteralBitBlockVec->addIncoming(shouldExtendLiteralBitBlockVec, entryBlock);
312        Value* shouldExtendLiteralGatherMask = b->CreateNeg(phiShouldExtendLiteralBitBlockVec);
313        shouldExtendLiteralGatherMask = b->simd_and(shouldExtendLiteralGatherMask, notFinishMask);
314
315        // TODO maybe we can load i64 once and then consume 8 times
316//        b->CallPrintRegister("shouldExtendLiteralGatherMask", shouldExtendLiteralGatherMask);
317//        b->CallPrintInt("popcount", b->CreatePopcount(b->hsimd_signmask(SIMD_WIDTH, shouldExtendLiteralGatherMask)));
318
319        Value* currentLiteralLengthVec = this->simdFetchByteData(b, byteRawInputPtr, phiCurrentExtendLiteralPosVec, shouldExtendLiteralGatherMask);
320
321        Value* newExtendLiteralLengthVec = b->simd_add(SIMD_WIDTH, phiExtendLiteralLengthVec, currentLiteralLengthVec);
322        Value* shouldContinueExtendVecBitBlock = b->CreateZExt(b->CreateICmpEQ(currentLiteralLengthVec, BIT_BLOCK_FF), BIT_BLOCK_TY);
323        Value* newExtendLiteralPosVec = b->CreateAdd(phiCurrentExtendLiteralPosVec, b->CreateAnd(shouldExtendLiteralBitBlockVec, shouldContinueExtendVecBitBlock));
324
325        phiCurrentExtendLiteralPosVec->addIncoming(newExtendLiteralPosVec, b->GetInsertBlock());
326        phiExtendLiteralLengthVec->addIncoming(newExtendLiteralLengthVec, b->GetInsertBlock());
327        phiShouldExtendLiteralBitBlockVec->addIncoming(shouldContinueExtendVecBitBlock, b->GetInsertBlock());
328
329        Value* shouldContinueExtendLiteral = b->CreateICmpNE(b->CreateBitCast(shouldContinueExtendVecBitBlock, INT_BIT_BLOCK_TY), INT_BIT_BLOCK_TY_0);
330
331        b->CreateUnlikelyCondBr(shouldContinueExtendLiteral, extendLiteralCond, extendLiteralEnd);  //extend literal will not happen quite often
332
333        // ---- extendLiteralEnd
334        b->SetInsertPoint(extendLiteralEnd);
335        PHINode* literalExtendValueVec = b->CreatePHI(b->getBitBlockType(), 2);
336        literalExtendValueVec->addIncoming(BIT_BLOCK_0, entryBlock);
337        literalExtendValueVec->addIncoming(newExtendLiteralLengthVec, extendLiteralCond);
338
339        PHINode* phiExtendLiteralEndPos = b->CreatePHI(b->getBitBlockType(), 2);
340        phiExtendLiteralEndPos->addIncoming(tokenPosVec, entryBlock);
341        phiExtendLiteralEndPos->addIncoming(phiCurrentExtendLiteralPosVec, extendLiteralCond);
342
343
344        Value* literalLengthVec = b->simd_add(SIMD_WIDTH, literalExtendValueVec, b->simd_srlv(SIMD_WIDTH, tokenValuesVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 4))));
345        Value* literalStartPosVec = b->simd_add(SIMD_WIDTH, phiExtendLiteralEndPos, BIT_BLOCK_1);
346
347
348        return std::make_pair(literalStartPosVec, literalLengthVec);
349
350    }
351
352    // TODO for now, this method only handle fast step (extension length <= 8)
353    std::pair<llvm::Value*, llvm::Value*> LZ4ParallelByteStreamDecompressionKernel::simdParseLiteralInfo2(const std::unique_ptr<KernelBuilder> &b, llvm::Value *tokenPosVec, llvm::Value* tokenValuesVec, llvm::Value* notFinishMask) {
354        // ---- entryBlock
355        BasicBlock* entryBlock = b->GetInsertBlock();
356        Value* baseLiteralLength = b->simd_srlv(SIMD_WIDTH, tokenValuesVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 4)));
357
358        Value* shouldExtendLiteralGatherMask = b->simd_eq(SIMD_WIDTH, baseLiteralLength, BIT_BLOCK_0F);
359        shouldExtendLiteralGatherMask = b->simd_and(shouldExtendLiteralGatherMask, notFinishMask);
360        Value* shouldExtension = b->CreateICmpNE(b->hsimd_signmask(SIMD_WIDTH, shouldExtendLiteralGatherMask), b->getInt32(0));
361
362        BasicBlock* extensionBlock = b->CreateBasicBlock("extensionBlock");
363        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
364
365        Value* notExtensionLiteralStart = b->simd_add(SIMD_WIDTH, tokenPosVec, BIT_BLOCK_1);
366
367        b->CreateUnlikelyCondBr(shouldExtension, extensionBlock, exitBlock);
368
369        // ---- extensionBlock
370        b->SetInsertPoint(extensionBlock);
371        Value* shouldExtendLiteralBitBlockVec = b->CreateZExt(b->CreateICmpEQ(baseLiteralLength, BIT_BLOCK_0F), BIT_BLOCK_TY);
372
373        Value* initExtendLiteralPos = b->simd_add(SIMD_WIDTH, tokenPosVec, shouldExtendLiteralBitBlockVec);
374        Value* byteRawInputPtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", SIZE_0), b->getInt8PtrTy());
375
376        Value* i64ExtensionValue = this->simdFetchI64DataByGather(b, byteRawInputPtr, initExtendLiteralPos, shouldExtendLiteralGatherMask);
377
378        Value* forwardZeros = b->simd_cttz(SIMD_WIDTH, b->simd_not(i64ExtensionValue));
379        Value* BIT_BLOCK_LOG2_8 = b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, std::log2(8)));
380        Value* extensionLength = b->simd_srlv(SIMD_WIDTH, forwardZeros, BIT_BLOCK_LOG2_8);
381        Value* shiftedExtensionValue = b->simd_srlv(SIMD_WIDTH, i64ExtensionValue, b->simd_sllv(SIMD_WIDTH, extensionLength, BIT_BLOCK_LOG2_8));
382        shiftedExtensionValue = b->simd_and(shiftedExtensionValue, BIT_BLOCK_FF);
383        Value* i64ExtensionLength = b->simd_add(SIMD_WIDTH, b->simd_mult(SIMD_WIDTH, extensionLength, BIT_BLOCK_FF), shiftedExtensionValue);
384        Value* newLiteralLength = b->simd_add(SIMD_WIDTH, b->simd_and(i64ExtensionLength, shouldExtendLiteralGatherMask), baseLiteralLength);
385
386        Value* newLiteralStartPos = b->simd_add(
387                SIMD_WIDTH,
388                b->simd_add(SIMD_WIDTH, notExtensionLiteralStart, shouldExtendLiteralBitBlockVec),
389                b->simd_and(extensionLength, shouldExtendLiteralGatherMask)
390        );
391
392        BasicBlock* extensionFinalBlock = b->GetInsertBlock();
393        b->CreateBr(exitBlock);
394
395        // ---- exitBlock
396        b->SetInsertPoint(exitBlock);
397        PHINode* phiLiteralStartPos = b->CreatePHI(b->getBitBlockType(), 2);
398        phiLiteralStartPos->addIncoming(notExtensionLiteralStart, entryBlock);
399        phiLiteralStartPos->addIncoming(newLiteralStartPos, extensionFinalBlock);
400
401        PHINode* phiLiteralLength = b->CreatePHI(b->getBitBlockType(), 2);
402        phiLiteralLength->addIncoming(baseLiteralLength, entryBlock);
403        phiLiteralLength->addIncoming(newLiteralLength, extensionFinalBlock);
404
405        return std::make_pair(phiLiteralStartPos, phiLiteralLength);
406    };
407
408    std::pair<llvm::Value*, llvm::Value*> LZ4ParallelByteStreamDecompressionKernel::parseMultipleMatchInfoByLoop(const std::unique_ptr<KernelBuilder> &b, llvm::Value *matchOffsetPosVec, llvm::Value* tokenValuesVec, llvm::Value* notFinishMask) {
409        // ---- EntryBlock
410        BasicBlock* entryBlock = b->GetInsertBlock();
411        Value* initMatchLengthVec = b->simd_add(SIMD_WIDTH, b->simd_and(tokenValuesVec, BIT_BLOCK_0F), b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 4)));
412        Value* initMatchEndPosVec = b->simd_add(SIMD_WIDTH, matchOffsetPosVec, BIT_BLOCK_1);
413
414        Value* shouldExtendLiteralBitBlockVec = b->simd_and(b->simd_eq(SIMD_WIDTH, b->simd_and(tokenValuesVec, BIT_BLOCK_0F), BIT_BLOCK_0F), notFinishMask);
415        Value* extendMatchSignMask = b->hsimd_signmask(SIMD_WIDTH, shouldExtendLiteralBitBlockVec);
416
417        BasicBlock* conBlock = b->CreateBasicBlock("conBlock");
418        BasicBlock* bodyBlock = b->CreateBasicBlock("bodyBlock");
419        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
420
421        b->CreateBr(conBlock);
422
423        b->SetInsertPoint(conBlock);
424        PHINode* phiSignMask = b->CreatePHI(extendMatchSignMask->getType(), 2);
425        phiSignMask->addIncoming(extendMatchSignMask, entryBlock);
426        PHINode* phiMatchEndPosVec = b->CreatePHI(initMatchEndPosVec->getType(), 2);
427        phiMatchEndPosVec->addIncoming(initMatchEndPosVec, entryBlock);
428        PHINode* phiMatchLengthVec = b->CreatePHI(initMatchLengthVec->getType(), 2);
429        phiMatchLengthVec->addIncoming(initMatchLengthVec, entryBlock);
430
431        b->CreateCondBr(b->CreateICmpNE(phiSignMask, b->getInt32(0)), bodyBlock, exitBlock);
432
433        // ---- BodyBlock
434        b->SetInsertPoint(bodyBlock);
435        Value* targetIndex = b->CreateCountForwardZeroes(phiSignMask);
436        Value* targetMatchOffsetPos = b->CreateExtractElement(matchOffsetPosVec, targetIndex);
437        Value* targetTokenValue = b->CreateTrunc(b->CreateExtractElement(tokenValuesVec, targetIndex), b->getInt8Ty());
438
439        Value *newMatchEndPos = nullptr, *newMatchLength = nullptr;
440        std::tie(newMatchEndPos, newMatchLength) = this->parseMatchInfo(b, targetMatchOffsetPos, targetTokenValue);
441        phiMatchEndPosVec->addIncoming(b->CreateInsertElement(phiMatchEndPosVec, newMatchEndPos, targetIndex), b->GetInsertBlock());
442        phiMatchLengthVec->addIncoming(b->CreateInsertElement(phiMatchLengthVec, newMatchLength, targetIndex), b->GetInsertBlock());
443        phiSignMask->addIncoming(b->CreateSub(phiSignMask, b->CreateShl(b->getInt32(1), targetIndex)), b->GetInsertBlock());
444        b->CreateBr(conBlock);
445
446        // ---- ExitBlock
447        b->SetInsertPoint(exitBlock);
448
449        return std::make_pair(phiMatchEndPosVec, b->simd_and(phiMatchLengthVec, notFinishMask));
450    }
451
452    std::pair<llvm::Value*, llvm::Value*> LZ4ParallelByteStreamDecompressionKernel::parallelParseMatchInfo(const std::unique_ptr<KernelBuilder> &b, llvm::Value *matchOffsetPosVec, llvm::Value* tokenValuesVec, llvm::Value* notFinishMask) {
453
454        Value* shouldExtendMatchBitBlockVec = b->simd_eq(SIMD_WIDTH, b->simd_and(BIT_BLOCK_0F, tokenValuesVec), BIT_BLOCK_0F);
455        Value* extendMatchParallelLevel = b->CreatePopcount(b->hsimd_signmask(SIMD_WIDTH, shouldExtendMatchBitBlockVec));
456        BasicBlock* simdBlock = b->CreateBasicBlock("simdBlock");
457        BasicBlock* loopBlock = b->CreateBasicBlock("loopBlock");
458        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
459
460        b->CreateUnlikelyCondBr(b->CreateICmpUGE(extendMatchParallelLevel, b->getInt32(mMininumParallelLevel)), simdBlock, loopBlock);
461
462        b->SetInsertPoint(simdBlock);
463        auto ret1 = this->simdParseMatchInfo(b, matchOffsetPosVec, tokenValuesVec, notFinishMask);
464        BasicBlock* simdBlockFinal = b->GetInsertBlock();
465        b->CreateBr(exitBlock);
466
467        b->SetInsertPoint(loopBlock);
468        auto ret2 = this->parseMultipleMatchInfoByLoop(b, matchOffsetPosVec, tokenValuesVec, notFinishMask);
469        BasicBlock* loopBlockFinal = b->GetInsertBlock();
470        b->CreateBr(exitBlock);
471
472        b->SetInsertPoint(exitBlock);
473        PHINode* phiFirst = b->CreatePHI(BIT_BLOCK_TY, 2);
474        phiFirst->addIncoming(ret1.first, simdBlockFinal);
475        phiFirst->addIncoming(ret2.first, loopBlockFinal);
476
477        PHINode* phiSecond = b->CreatePHI(BIT_BLOCK_TY, 2);
478        phiSecond->addIncoming(ret1.second, simdBlockFinal);
479        phiSecond->addIncoming(ret2.second, loopBlockFinal);
480
481        return std::make_pair(phiFirst, phiSecond);
482
483    }
484
485    std::pair<llvm::Value*, llvm::Value*> LZ4ParallelByteStreamDecompressionKernel::simdParseMatchInfo2(const std::unique_ptr<KernelBuilder> &b, llvm::Value *matchOffsetPosVec, llvm::Value* tokenValuesVec, llvm::Value* notFinishMask) {
486        // ---- entryBlock
487        BasicBlock* entryBlock = b->GetInsertBlock();
488
489        Value* matchOffsetNextPosVec = b->simd_add(SIMD_WIDTH, matchOffsetPosVec, BIT_BLOCK_1);
490
491        Value* baseMatchLength = b->simd_and(tokenValuesVec, BIT_BLOCK_0F);
492
493        Value* shouldExtendMatchGatherMask = b->simd_eq(SIMD_WIDTH, baseMatchLength, BIT_BLOCK_0F);
494        shouldExtendMatchGatherMask = b->simd_and(shouldExtendMatchGatherMask, notFinishMask);
495        Value* shouldExtendMatchBitBlockVec = b->CreateZExt(b->CreateICmpEQ(baseMatchLength, BIT_BLOCK_0F), BIT_BLOCK_TY);
496
497        Value* shouldExtension = b->CreateICmpNE(b->hsimd_signmask(SIMD_WIDTH, shouldExtendMatchGatherMask), b->getInt32(0));
498
499        Value* initExtendMatchPosVec = b->simd_add(SIMD_WIDTH, matchOffsetNextPosVec, shouldExtendMatchBitBlockVec);
500
501        baseMatchLength = b->simd_add(SIMD_WIDTH, baseMatchLength, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 4)));
502
503
504        BasicBlock* extensionBlock = b->CreateBasicBlock("extensionBlock");
505        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
506
507        b->CreateLikelyCondBr(shouldExtension, extensionBlock, exitBlock);
508
509        // ---- extensionBlock
510        b->SetInsertPoint(extensionBlock);
511
512        PHINode* phiExtendMatchPos = b->CreatePHI(initExtendMatchPosVec->getType(), 2);
513        phiExtendMatchPos->addIncoming(initExtendMatchPosVec, entryBlock);
514        PHINode* phiExtendMatchLength = b->CreatePHI(BIT_BLOCK_TY, 2);
515        phiExtendMatchLength->addIncoming(BIT_BLOCK_0, entryBlock);
516        PHINode* phiGatherMask = b->CreatePHI(shouldExtendMatchGatherMask->getType(), 2);
517        phiGatherMask->addIncoming(shouldExtendMatchGatherMask, entryBlock);
518
519
520        Value* byteRawInputPtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", SIZE_0), b->getInt8PtrTy());
521        Value* i64ExtensionValue = this->simdFetchI64DataByGather(b, byteRawInputPtr, phiExtendMatchPos, phiGatherMask);
522
523        Value* forwardZeros = b->simd_cttz(SIMD_WIDTH, b->simd_not(i64ExtensionValue));
524        Value* BIT_BLOCK_LOG2_8 = b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, std::log2(8)));
525        Value* extensionLength = b->simd_srlv(SIMD_WIDTH, forwardZeros, BIT_BLOCK_LOG2_8);
526
527        Value* shiftedExtensionValue = b->simd_srlv(SIMD_WIDTH, i64ExtensionValue, b->simd_sllv(SIMD_WIDTH, extensionLength, BIT_BLOCK_LOG2_8));
528        shiftedExtensionValue = b->simd_and(shiftedExtensionValue, BIT_BLOCK_FF);
529
530        Value* i64ExtensionLength = b->simd_add(SIMD_WIDTH, b->simd_mult(SIMD_WIDTH, extensionLength, BIT_BLOCK_FF), shiftedExtensionValue);
531
532        Value* newExtendMatchLength = b->simd_add(SIMD_WIDTH, phiExtendMatchLength, b->simd_and(i64ExtensionLength, phiGatherMask));
533        Value* newExtendMatchPos = b->simd_add(SIMD_WIDTH, phiExtendMatchPos, b->simd_and(extensionLength, phiGatherMask));
534
535
536        Value* newMatchLength = b->simd_add(SIMD_WIDTH, newExtendMatchLength, baseMatchLength);
537        Value* newMatchEndPos = newExtendMatchPos;
538
539        Value* shouldContinueExtendMask = b->simd_eq(SIMD_WIDTH, extensionLength, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 8)));
540        Value* shouldContinue = b->CreateICmpNE(b->CreateBitCast(shouldContinueExtendMask, INT_BIT_BLOCK_TY), INT_BIT_BLOCK_TY_0);
541
542        BasicBlock* extensionFinalBlock = b->GetInsertBlock();
543
544
545        phiExtendMatchLength->addIncoming(newExtendMatchLength, b->GetInsertBlock());
546        phiExtendMatchPos->addIncoming(newExtendMatchPos, b->GetInsertBlock());
547        phiGatherMask->addIncoming(shouldContinueExtendMask, b->GetInsertBlock());
548
549        b->CreateUnlikelyCondBr(shouldContinue, extensionBlock, exitBlock);
550
551//        b->CreateBr(exitBlock);
552
553        // ---- exitBlock
554        b->SetInsertPoint(exitBlock);
555
556
557        PHINode* phiExtendMatchEndPos = b->CreatePHI(b->getBitBlockType(), 2);
558        phiExtendMatchEndPos->addIncoming(matchOffsetNextPosVec, entryBlock);
559        phiExtendMatchEndPos->addIncoming(newMatchEndPos, extensionFinalBlock);
560
561        PHINode* phiMatchLength = b->CreatePHI(b->getBitBlockType(), 2);
562        phiMatchLength->addIncoming(baseMatchLength, entryBlock);
563        phiMatchLength->addIncoming(newMatchLength, extensionFinalBlock);
564
565
566        return std::make_pair(phiExtendMatchEndPos, b->simd_and(phiMatchLength, notFinishMask));
567
568    }
569
570    std::pair<llvm::Value*, llvm::Value*> LZ4ParallelByteStreamDecompressionKernel::simdParseMatchInfo(const std::unique_ptr<KernelBuilder> &b, llvm::Value *matchOffsetPosVec, llvm::Value* tokenValuesVec, llvm::Value* hasMatchPartMask) {
571        // ---- entryBlock
572        BasicBlock* entryBlock = b->GetInsertBlock();
573        Value* byteRawInputPtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
574        Value* matchOffsetNextPosVec = b->simd_add(SIMD_WIDTH, matchOffsetPosVec, BIT_BLOCK_1);
575        Value* shouldExtendMatchBitBlockVec = b->CreateZExt(b->CreateICmpEQ(b->CreateAnd(BIT_BLOCK_0F, tokenValuesVec), BIT_BLOCK_0F), b->getBitBlockType());
576        Value* shouldExtendMatch = b->CreateICmpNE(b->CreateBitCast(shouldExtendMatchBitBlockVec, INT_BIT_BLOCK_TY), INT_BIT_BLOCK_TY_0);
577
578        BasicBlock* extendMatchCon = b->CreateBasicBlock("extendMatchCon");
579        BasicBlock* extendMatchExit = b->CreateBasicBlock("extendMatchExit");
580
581        Value* initExtendMatchPosVec = b->simd_add(SIMD_WIDTH, matchOffsetNextPosVec, shouldExtendMatchBitBlockVec);
582        b->CreateLikelyCondBr(shouldExtendMatch, extendMatchCon, extendMatchExit); // Match Extension will happen quite often
583
584        // ---- extendMatchCon
585        b->SetInsertPoint(extendMatchCon);
586        PHINode* phiCurrentExtendMatchPosVec = b->CreatePHI(initExtendMatchPosVec->getType(), 2);
587        phiCurrentExtendMatchPosVec->addIncoming(initExtendMatchPosVec, entryBlock);
588        PHINode* phiExtendMatchLengthVec = b->CreatePHI(b->getBitBlockType(), 2);
589        phiExtendMatchLengthVec->addIncoming(BIT_BLOCK_0, entryBlock);
590
591        PHINode* phiShouldExtendMatchBitBlockVec = b->CreatePHI(shouldExtendMatchBitBlockVec->getType(), 2);
592        phiShouldExtendMatchBitBlockVec->addIncoming(shouldExtendMatchBitBlockVec, entryBlock);
593        Value* shouldExtendMatchGatherMask = b->CreateNeg(phiShouldExtendMatchBitBlockVec);
594        shouldExtendMatchGatherMask = b->simd_and(shouldExtendMatchGatherMask, hasMatchPartMask);
595//        shouldExtendMatchGatherMask = b->simd_and(shouldExtendMatchGatherMask, notFinishMask);
596
597        // TODO maybe we can load i64 once and then consume 8 times
598//        this->recordParallelLevel(b, b->CreatePopcount(b->hsimd_signmask(SIMD_WIDTH, shouldExtendMatchGatherMask)));
599        Value* currentMatchLengthVec = this->simdFetchByteData(b, byteRawInputPtr, phiCurrentExtendMatchPosVec, shouldExtendMatchGatherMask);
600
601        Value* newExtendMatchLengthVec = b->simd_add(SIMD_WIDTH, phiExtendMatchLengthVec, currentMatchLengthVec);
602
603        Value* shouldContinueExtendMatchVecBitBlock = b->CreateZExt(b->CreateICmpEQ(currentMatchLengthVec, BIT_BLOCK_FF), b->getBitBlockType());
604        Value* newExtendMatchPosVec = b->simd_add(SIMD_WIDTH, phiCurrentExtendMatchPosVec, b->simd_and(shouldExtendMatchBitBlockVec, shouldContinueExtendMatchVecBitBlock));
605
606        phiCurrentExtendMatchPosVec->addIncoming(newExtendMatchPosVec, b->GetInsertBlock());
607        phiExtendMatchLengthVec->addIncoming(newExtendMatchLengthVec, b->GetInsertBlock());
608
609        phiShouldExtendMatchBitBlockVec->addIncoming(shouldContinueExtendMatchVecBitBlock, b->GetInsertBlock());
610        Value* shouldContinueExtendMatch = b->CreateICmpNE(b->CreateBitCast(shouldContinueExtendMatchVecBitBlock, INT_BIT_BLOCK_TY), INT_BIT_BLOCK_TY_0);
611
612        b->CreateUnlikelyCondBr(shouldContinueExtendMatch, extendMatchCon, extendMatchExit); // Usually it will be enough for only 1 match extension
613
614
615        // ---- extendMatchExit
616        b->SetInsertPoint(extendMatchExit);
617
618        PHINode* matchExtendValueVec = b->CreatePHI(newExtendMatchLengthVec->getType(), 2);
619        matchExtendValueVec->addIncoming(BIT_BLOCK_0, entryBlock);
620        matchExtendValueVec->addIncoming(newExtendMatchLengthVec, extendMatchCon);
621        PHINode* phiExtendMatchEndPos = b->CreatePHI(matchOffsetNextPosVec->getType(), 2);
622        phiExtendMatchEndPos->addIncoming(matchOffsetNextPosVec, entryBlock);
623        phiExtendMatchEndPos->addIncoming(phiCurrentExtendMatchPosVec, extendMatchCon);
624
625
626        // matchLength = (size_t)token & 0xf + 4 + matchExtendValue
627        Value* matchLength = b->simd_add(
628                SIMD_WIDTH,
629                b->simd_add(SIMD_WIDTH, matchExtendValueVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 4))),
630                b->simd_and(tokenValuesVec, BIT_BLOCK_0F)
631        );
632        matchLength = b->simd_and(matchLength, hasMatchPartMask);
633
634        return std::make_pair(phiExtendMatchEndPos, matchLength);
635    };
636
637
638    std::pair<llvm::Value*, llvm::Value*> LZ4ParallelByteStreamDecompressionKernel::simdProcessBlockBoundaryByLoop(const std::unique_ptr<KernelBuilder> &b,
639                                                                         llvm::Value *tokenPosVec, llvm::Value *lz4BlockEnd, llvm::Value* outputPosVec) {
640        Value* retNextTokenPos = ConstantVector::getNullValue(b->getBitBlockType());
641        Value* retNewOutputPos = ConstantVector::getNullValue(b->getBitBlockType());
642
643        for (unsigned i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
644            auto ret = this->processBlockBoundary(
645                    b,
646                    b->CreateExtractElement(tokenPosVec, i),
647                    b->CreateExtractElement(lz4BlockEnd, i),
648                    b->CreateExtractElement(outputPosVec, i)
649            );
650            retNextTokenPos = b->CreateInsertElement(retNextTokenPos, ret.first, i);
651            retNewOutputPos = b->CreateInsertElement(retNewOutputPos, ret.second, i);
652        }
653        return std::make_pair(retNextTokenPos, retNewOutputPos);
654    };
655
656    std::pair<Value *, Value *> LZ4ParallelByteStreamDecompressionKernel::simdProcessBlockBoundary(
657            const std::unique_ptr<KernelBuilder> &b, Value *tokenPosVec, Value *lz4BlockEndVec, Value* initOutputPosVec
658    ) {
659        // ---- EntryBlock
660        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
661
662        Value* notFinishMask = b->simd_ult(SIMD_WIDTH, tokenPosVec, lz4BlockEndVec);
663
664        Value* byteRawInputPtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
665
666        Value* tokenValuesVec = this->simdFetchByteData(b, byteRawInputPtr, tokenPosVec, notFinishMask);
667
668        Value *literalStartPosVec = nullptr, *literalLengthVec = nullptr;
669
670
671//        std::tie(literalStartPosVec, literalLengthVec) = this->simdParseLiteralInfo(b, tokenPosVec, tokenValuesVec, notFinishMask);
672        std::tie(literalStartPosVec, literalLengthVec) = this->simdParseLiteralInfo2(b, tokenPosVec, tokenValuesVec, notFinishMask);
673
674        Value* literalEndPosVec = b->simd_add(SIMD_WIDTH, literalStartPosVec, literalLengthVec);
675
676
677        this->handleSimdLiteralCopy(b, literalStartPosVec, literalLengthVec, initOutputPosVec);
678
679
680        Value* outputPosAfterLiteralCpy = b->simd_add(SIMD_WIDTH, initOutputPosVec, literalLengthVec);
681
682
683        Value* matchOffsetBeginPosVec = literalEndPosVec;
684
685        Value* matchOffsetNextPosVec = b->simd_add(SIMD_WIDTH, matchOffsetBeginPosVec, BIT_BLOCK_1);
686
687
688        BasicBlock* hasMatchPartBlock = b->CreateBasicBlock("hasMatchPartBlock");
689
690
691        BasicBlock* extendLiteralEndFinal = b->GetInsertBlock();
692
693        Value* hasMatchPartMask = b->simd_ult(SIMD_WIDTH, matchOffsetBeginPosVec, lz4BlockEndVec);
694        b->CreateLikelyCondBr(b->CreateICmpNE(b->CreateBitCast(hasMatchPartMask, INT_BIT_BLOCK_TY), INT_BIT_BLOCK_TY_0), hasMatchPartBlock, exitBlock);
695
696        // ---- hasMatchPartBlock
697        b->SetInsertPoint(hasMatchPartBlock);
698
699        Value *matchLength = nullptr, *extendMatchEndPos = nullptr;
700
701//        std::tie(extendMatchEndPos, matchLength) = this->simdParseMatchInfo(b, matchOffsetBeginPosVec, tokenValuesVec, hasMatchPartMask);
702        std::tie(extendMatchEndPos, matchLength) = this->simdParseMatchInfo2(b, matchOffsetBeginPosVec, tokenValuesVec, hasMatchPartMask);
703
704        Value* matchOffsetVec = this->simdFetchData(
705                b,
706                byteRawInputPtr,
707                matchOffsetBeginPosVec,
708                hasMatchPartMask
709        );
710        matchOffsetVec = b->simd_and(matchOffsetVec, BIT_BLOCK_FFFF);
711
712//        Value* t1 = b->CreateReadCycleCounter();
713        this->handleSimdMatchCopy(b, matchOffsetVec, matchLength, outputPosAfterLiteralCpy);
714//        Value* t2 = b->CreateReadCycleCounter();
715//        b->setScalarField("tempTimes", b->CreateAdd(b->getScalarField("tempTimes"), b->CreateSub(t2 ,t1)));
716
717        Value* outputPosAfterMatchCpy = b->simd_add(SIMD_WIDTH, outputPosAfterLiteralCpy, matchLength);
718
719        BasicBlock* extendMatchExitFinal = b->GetInsertBlock();
720
721        b->CreateBr(exitBlock);
722        // ---- exitBlock
723
724        b->SetInsertPoint(exitBlock);
725
726        PHINode* phiBeforeTokenPos = b->CreatePHI(matchOffsetNextPosVec->getType(), 2);
727        phiBeforeTokenPos->addIncoming(matchOffsetNextPosVec, extendLiteralEndFinal);
728        phiBeforeTokenPos->addIncoming(extendMatchEndPos, extendMatchExitFinal);
729
730        PHINode* phiNewOutputPos = b->CreatePHI(outputPosAfterLiteralCpy->getType(), 2);
731        phiNewOutputPos->addIncoming(outputPosAfterLiteralCpy, extendLiteralEndFinal);
732        phiNewOutputPos->addIncoming(outputPosAfterMatchCpy, extendMatchExitFinal);
733        Value* nextTokenPos = b->simd_add(SIMD_WIDTH, phiBeforeTokenPos, BIT_BLOCK_1);
734        return std::make_pair(nextTokenPos, phiNewOutputPos);
735    }
736
737    void LZ4ParallelByteStreamDecompressionKernel::generateSimdDecompression1(const std::unique_ptr<KernelBuilder> &b, Value* blockDataIndex) {
738        BasicBlock* entryBlock = b->GetInsertBlock();
739        BasicBlock* exitBlock = b->CreateBasicBlock("simdDecompressionExitBlock");
740        BasicBlock* processCon = b->CreateBasicBlock("simdDecompressionProcessConBlock");
741        BasicBlock* processBody = b->CreateBasicBlock("simdDecompressionProcessBodyBlock");
742        BasicBlock* sequentialProcessBlock = b->CreateBasicBlock("simdDecompressionSequentialProcessBlock");
743
744
745        // ---- entryBlock
746        Value* blockStartVec = this->generateLoadSimdInt64NumberInput(b, "blockStart", blockDataIndex);
747        Value* blockEndVec = this->generateLoadSimdInt64NumberInput(b, "blockEnd", blockDataIndex);
748
749        Value* outputPos = b->getProducedItemCount("outputStream");
750        Value* initOutputPosVec = b->simd_fill(SIMD_WIDTH, outputPos);
751        std::vector<Constant*> initOutputOffset;
752        for (unsigned i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
753            initOutputOffset.push_back(b->getIntN(SIMD_WIDTH, i * mLz4BlockSize));
754        }
755
756        initOutputPosVec = b->simd_add(SIMD_WIDTH, initOutputPosVec, ConstantVector::get(initOutputOffset));
757
758        // TODO handle uncompression blocks
759
760        b->CreateBr(processCon);
761
762        // ---- processCon
763        b->SetInsertPoint(processCon);
764        PHINode* phiCursorVec = b->CreatePHI(blockStartVec->getType(), 3);
765        phiCursorVec->addIncoming(blockStartVec, entryBlock);
766
767        PHINode* phiOutputPosVec = b->CreatePHI(initOutputPosVec->getType(), 3);
768        phiOutputPosVec->addIncoming(initOutputPosVec, entryBlock);
769
770
771        Value* hasRemaining = b->simd_ult(SIMD_WIDTH, phiCursorVec, blockEndVec);
772        Value* signMask = b->hsimd_signmask(SIMD_WIDTH, hasRemaining);
773        Value* maskPopcount = b->CreatePopcount(signMask);
774        Value* shouldSimdProcess = b->CreateICmpUGE(maskPopcount, b->getInt32(mMininumParallelLevel));
775
776        hasRemaining = b->CreateICmpNE(b->CreateBitCast(hasRemaining, b->getIntNTy(b->getBitBlockWidth())), Constant::getNullValue(b->getIntNTy(b->getBitBlockWidth())));
777
778        b->CreateLikelyCondBr(shouldSimdProcess, processBody, sequentialProcessBlock);
779
780        // ---- processBody
781        b->SetInsertPoint(processBody);
782
783        Value* notFinishMask = b->simd_ult(SIMD_WIDTH, phiCursorVec, blockEndVec);
784        Value* byteRawInputPtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
785        Value* tokenValuesVec = this->simdFetchByteData(b, byteRawInputPtr, phiCursorVec, notFinishMask);
786
787        Value* literalN = b->CreatePopcount(b->hsimd_signmask(SIMD_WIDTH, b->simd_eq(SIMD_WIDTH, b->simd_and(tokenValuesVec, BIT_BLOCK_F0), BIT_BLOCK_F0)));
788        Value* matchN = b->CreatePopcount(b->hsimd_signmask(SIMD_WIDTH, b->simd_eq(SIMD_WIDTH, b->simd_and(tokenValuesVec, BIT_BLOCK_0F), BIT_BLOCK_0F)));
789
790//        Value* shouldSimdProcess2 = b->CreateAnd(
791//                b->CreateOr(b->CreateICmpEQ(literalN, b->getInt32(0)), b->CreateICmpUGE(literalN, b->getInt32(mMininumParallelLevel))),
792//                b->CreateOr(b->CreateICmpEQ(matchN, b->getInt32(0)), b->CreateICmpUGE(matchN, b->getInt32(mMininumParallelLevel)))
793//        );
794
795        Value* shouldSimdProcess2 = b->CreateAnd(b->CreateICmpEQ(literalN, b->getInt32(0)), b->CreateICmpUGE(matchN, b->getInt32(mMininumParallelLevel)));
796
797        BasicBlock* loopProcessBody = b->CreateBasicBlock("loopProcessBody");
798        BasicBlock* simdProcessBody = b->CreateBasicBlock("simdProcessBody");
799
800
801        b->CreateCondBr(shouldSimdProcess2, simdProcessBody, loopProcessBody);
802
803        // ---- simdProcessBody
804        {
805            b->SetInsertPoint(simdProcessBody);
806            Value *newCursorVec = nullptr, *newOutputPosVec = nullptr;
807//            std::tie(newCursorVec, newOutputPosVec) = this->simdProcessBlockBoundary(b, phiCursorVec, blockEndVec, phiOutputPosVec);
808            std::tie(newCursorVec, newOutputPosVec) = this->simdProcessBlockBoundaryByLoop(b, phiCursorVec, blockEndVec, phiOutputPosVec);
809
810            phiCursorVec->addIncoming(newCursorVec, b->GetInsertBlock());
811            phiOutputPosVec->addIncoming(newOutputPosVec, b->GetInsertBlock());
812
813            b->CreateBr(processCon);
814        }
815
816        // ---- loopProcessBody
817        {
818            b->SetInsertPoint(loopProcessBody);
819            Value *newCursorVec = nullptr, *newOutputPosVec = nullptr;
820            std::tie(newCursorVec, newOutputPosVec) = this->simdProcessBlockBoundaryByLoop(b, phiCursorVec, blockEndVec, phiOutputPosVec);
821
822            phiCursorVec->addIncoming(newCursorVec, b->GetInsertBlock());
823            phiOutputPosVec->addIncoming(newOutputPosVec, b->GetInsertBlock());
824
825            b->CreateBr(processCon);
826        }
827
828
829        // ---- sequentialProcessBlock
830        b->SetInsertPoint(sequentialProcessBlock);
831
832        for (unsigned i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
833
834            BasicBlock* conBlock = b->CreateBasicBlock("conBlock");
835            BasicBlock* bodyBlock = b->CreateBasicBlock("bodyBlock");
836            BasicBlock* innerExitBlock = b->CreateBasicBlock("exitBlock");
837
838            b->CreateBr(conBlock);
839
840            // ---- conBlock
841            b->SetInsertPoint(conBlock);
842            Value* shouldProcessSequentially = b->CreateICmpNE(b->CreateAnd(b->CreateLShr(signMask, b->getInt32(i)), b->getInt32(1)), b->getInt32(0));
843            Value* originalOutputPos = b->CreateExtractElement(phiOutputPosVec, i);
844
845            b->CreateCondBr(shouldProcessSequentially, bodyBlock, innerExitBlock);
846
847            // ---- bodyBlock
848            b->SetInsertPoint(bodyBlock);
849
850            // TODO need to handle blockEnd here when doing overwriting memcpy
851            Value* newOutputPos = this->generateProcessCompressedBlock(
852                    b,
853                    b->CreateExtractElement(phiCursorVec, i),
854                    b->CreateExtractElement(blockEndVec, i),
855                    originalOutputPos
856            );
857
858            if (i == b->getBitBlockWidth() / SIMD_WIDTH - 1) {
859                b->setProducedItemCount("outputStream", newOutputPos);
860            }
861
862            b->CreateBr(innerExitBlock);
863
864            // ---- exitBlock
865            b->SetInsertPoint(innerExitBlock);
866        }
867
868
869        b->CreateBr(exitBlock);
870
871        // ---- exitBlock
872        b->SetInsertPoint(exitBlock);
873
874        uint64_t lastVecIndex = b->getBitBlockWidth() / SIMD_WIDTH - 1;
875        Value* lastBlockEnd = b->CreateExtractElement(blockEndVec, lastVecIndex);
876        b->setProcessedItemCount("byteStream", lastBlockEnd);
877        Value* lastOutputPos = b->CreateExtractElement(phiOutputPosVec, lastVecIndex);
878        b->setProducedItemCount("outputStream", b->CreateUMax(b->getProducedItemCount("outputStream"), lastOutputPos));
879//        b->CallPrintInt("produced", b->getProducedItemCount("outputStream"));
880
881    }
882
883    void LZ4ParallelByteStreamDecompressionKernel::generateSimdDecompression2(const std::unique_ptr<KernelBuilder> &b, llvm::Value* blockDataIndex) {
884        BasicBlock* entryBlock = b->GetInsertBlock();
885        BasicBlock* exitBlock = b->CreateBasicBlock("simdDecompressionExitBlock");
886        BasicBlock* processCon = b->CreateBasicBlock("simdDecompressionProcessConBlock");
887        BasicBlock* processBody = b->CreateBasicBlock("simdDecompressionProcessBodyBlock");
888        BasicBlock* sequentialProcessBlock = b->CreateBasicBlock("simdDecompressionSequentialProcessBlock");
889
890        // ---- entryBlock
891        Value* blockStartVec = this->generateLoadSimdInt64NumberInput(b, "blockStart", blockDataIndex);
892        Value* blockEndVec = this->generateLoadSimdInt64NumberInput(b, "blockEnd", blockDataIndex);
893
894        Value* outputPos = b->getProducedItemCount("outputStream");
895        Value* initOutputPosVec = b->simd_fill(SIMD_WIDTH, outputPos);
896        std::vector<Constant*> initOutputOffset;
897        for (unsigned i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
898            initOutputOffset.push_back(b->getIntN(SIMD_WIDTH, i * 4 * 1024 * 1024));
899        }
900
901        initOutputPosVec = b->simd_add(SIMD_WIDTH, initOutputPosVec, ConstantVector::get(initOutputOffset));
902
903        // TODO handle uncompression blocks
904
905        b->CreateBr(processCon);
906
907        // ---- processCon
908        b->SetInsertPoint(processCon);
909        PHINode* phiCursorVec = b->CreatePHI(blockStartVec->getType(), 2);
910        phiCursorVec->addIncoming(blockStartVec, entryBlock);
911
912        PHINode* phiOutputPosVec = b->CreatePHI(initOutputPosVec->getType(), 2);
913        phiOutputPosVec->addIncoming(initOutputPosVec, entryBlock);
914
915        Value* hasRemaining = b->simd_ult(SIMD_WIDTH, phiCursorVec, blockEndVec);
916        Value* signMask = b->hsimd_signmask(SIMD_WIDTH, hasRemaining);
917        Value* maskPopcount = b->CreatePopcount(signMask);
918        Value* shouldSimdProcess = b->CreateICmpUGE(maskPopcount, b->getInt32(mMininumParallelLevel));
919        b->CreateLikelyCondBr(shouldSimdProcess, processBody, sequentialProcessBlock);
920
921        // ---- processBody
922        b->SetInsertPoint(processBody);
923//        Value* newCursorVec = this->generateSimdAcceleration(b, phiCursorVec, blockEndVec);
924
925        Value *newCursorVec = nullptr, *newOutputPosVec = nullptr;
926        std::tie(newCursorVec, newOutputPosVec) = this->simdProcessBlockBoundary(b, phiCursorVec, blockEndVec, phiOutputPosVec);
927//        std::tie(newCursorVec, newOutputPosVec) = this->simdProcessBlockBoundaryByLoop(b, phiCursorVec, blockEndVec, phiOutputPosVec);
928
929        phiCursorVec->addIncoming(newCursorVec, b->GetInsertBlock());
930        phiOutputPosVec->addIncoming(newOutputPosVec, b->GetInsertBlock());
931
932        b->CreateBr(processCon);
933
934        // ---- sequentialProcessBlock
935        b->SetInsertPoint(sequentialProcessBlock);
936
937        for (unsigned i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
938
939            BasicBlock* conBlock = b->CreateBasicBlock("conBlock");
940            BasicBlock* bodyBlock = b->CreateBasicBlock("bodyBlock");
941            BasicBlock* innerExitBlock = b->CreateBasicBlock("exitBlock");
942
943            b->CreateBr(conBlock);
944
945            // ---- conBlock
946            b->SetInsertPoint(conBlock);
947            Value* shouldProcessSequentially = b->CreateICmpNE(b->CreateAnd(b->CreateLShr(signMask, b->getInt32(i)), b->getInt32(1)), b->getInt32(0));
948            Value* originalOutputPos = b->CreateExtractElement(phiOutputPosVec, i);
949
950            b->CreateCondBr(shouldProcessSequentially, bodyBlock, innerExitBlock);
951
952            // ---- bodyBlock
953            b->SetInsertPoint(bodyBlock);
954
955            // TODO need to handle blockEnd here when doing overwriting memcpy
956            Value* newOutputPos = this->generateProcessCompressedBlock(
957                    b,
958                    b->CreateExtractElement(phiCursorVec, i),
959                    b->CreateExtractElement(blockEndVec, i),
960                    originalOutputPos
961            );
962
963            if (i == b->getBitBlockWidth() / SIMD_WIDTH - 1) {
964                b->setProducedItemCount("outputStream", newOutputPos);
965            }
966
967            b->CreateBr(innerExitBlock);
968
969            // ---- exitBlock
970            b->SetInsertPoint(innerExitBlock);
971        }
972
973
974        b->CreateBr(exitBlock);
975
976        // ---- exitBlock
977        b->SetInsertPoint(exitBlock);
978
979        uint64_t lastVecIndex = b->getBitBlockWidth() / SIMD_WIDTH - 1;
980        Value* lastBlockEnd = b->CreateExtractElement(blockEndVec, lastVecIndex);
981        b->setProcessedItemCount("byteStream", lastBlockEnd);
982        Value* lastOutputPos = b->CreateExtractElement(phiOutputPosVec, lastVecIndex);
983        b->setProducedItemCount("outputStream", b->CreateUMax(b->getProducedItemCount("outputStream"), lastOutputPos));
984//        b->CallPrintInt("produced", b->getProducedItemCount("outputStream"));
985    }
986
987
988    void LZ4ParallelByteStreamDecompressionKernel::generateSimdDecompression(const std::unique_ptr<KernelBuilder> &b, Value* blockDataIndex) {
989        BasicBlock* entryBlock = b->GetInsertBlock();
990        BasicBlock* exitBlock = b->CreateBasicBlock("simdDecompressionExitBlock");
991        BasicBlock* processCon = b->CreateBasicBlock("simdDecompressionProcessConBlock");
992        BasicBlock* processBody = b->CreateBasicBlock("simdDecompressionProcessBodyBlock");
993        BasicBlock* sequentialProcessBlock = b->CreateBasicBlock("simdDecompressionSequentialProcessBlock");
994
995
996        // ---- entryBlock
997        Value* blockStartVec = this->generateLoadSimdInt64NumberInput(b, "blockStart", blockDataIndex);
998        Value* blockEndVec = this->generateLoadSimdInt64NumberInput(b, "blockEnd", blockDataIndex);
999
1000        Value* outputPos = b->getProducedItemCount("outputStream");
1001        Value* initOutputPosVec = b->simd_fill(SIMD_WIDTH, outputPos);
1002        std::vector<Constant*> initOutputOffset;
1003        for (unsigned i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
1004            initOutputOffset.push_back(b->getIntN(SIMD_WIDTH, i * 4 * 1024 * 1024));
1005        }
1006
1007        initOutputPosVec = b->simd_add(SIMD_WIDTH, initOutputPosVec, ConstantVector::get(initOutputOffset));
1008
1009        // TODO handle uncompression blocks
1010
1011        b->CreateBr(processCon);
1012
1013        // ---- processCon
1014        b->SetInsertPoint(processCon);
1015        PHINode* phiCursorVec = b->CreatePHI(blockStartVec->getType(), 2);
1016        phiCursorVec->addIncoming(blockStartVec, entryBlock);
1017
1018        PHINode* phiOutputPosVec = b->CreatePHI(initOutputPosVec->getType(), 2);
1019        phiOutputPosVec->addIncoming(initOutputPosVec, entryBlock);
1020
1021
1022        Value* hasRemaining = b->simd_ult(SIMD_WIDTH, phiCursorVec, blockEndVec);
1023        Value* signMask = b->hsimd_signmask(SIMD_WIDTH, hasRemaining);
1024
1025        Value* notFinishMask = b->simd_ult(SIMD_WIDTH, phiCursorVec, blockEndVec);
1026        Value* byteRawInputPtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
1027        Value* tokenValuesVec = this->simdFetchByteData(b, byteRawInputPtr, phiCursorVec, notFinishMask);
1028
1029        Value* literalN = b->CreatePopcount(b->hsimd_signmask(SIMD_WIDTH, b->simd_eq(SIMD_WIDTH, b->simd_and(tokenValuesVec, BIT_BLOCK_F0), BIT_BLOCK_F0)));
1030        Value* matchN = b->CreatePopcount(b->hsimd_signmask(SIMD_WIDTH, b->simd_eq(SIMD_WIDTH, b->simd_and(tokenValuesVec, BIT_BLOCK_0F), BIT_BLOCK_0F)));
1031
1032        Value* shouldSimdProcess = b->CreateAnd(
1033                b->CreateOr(b->CreateICmpEQ(literalN, b->getInt32(0)), b->CreateICmpUGE(literalN, b->getInt32(mMininumParallelLevel))),
1034                b->CreateOr(b->CreateICmpEQ(matchN, b->getInt32(0)), b->CreateICmpUGE(matchN, b->getInt32(mMininumParallelLevel)))
1035        );
1036        this->recordParallelLevel(b, b->CreateZExt(shouldSimdProcess, b->getInt32Ty()));
1037//        shouldSimdProcess = b->getInt1(false);
1038
1039
1040        b->CreateLikelyCondBr(shouldSimdProcess, processBody, sequentialProcessBlock);
1041
1042        // ---- processBody
1043        b->SetInsertPoint(processBody);
1044//        Value* newCursorVec = this->generateSimdAcceleration(b, phiCursorVec, blockEndVec);
1045
1046        Value *newCursorVec = nullptr, *newOutputPosVec = nullptr;
1047        std::tie(newCursorVec, newOutputPosVec) = this->simdProcessBlockBoundary(b, phiCursorVec, blockEndVec, phiOutputPosVec);
1048
1049        phiCursorVec->addIncoming(newCursorVec, b->GetInsertBlock());
1050        phiOutputPosVec->addIncoming(newOutputPosVec, b->GetInsertBlock());
1051
1052        b->CreateBr(processCon);
1053
1054        // ---- sequentialProcessBlock
1055        b->SetInsertPoint(sequentialProcessBlock);
1056
1057        for (unsigned i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
1058
1059            BasicBlock* conBlock = b->CreateBasicBlock("conBlock");
1060            BasicBlock* bodyBlock = b->CreateBasicBlock("bodyBlock");
1061            BasicBlock* innerExitBlock = b->CreateBasicBlock("exitBlock");
1062
1063            b->CreateBr(conBlock);
1064
1065            // ---- conBlock
1066            b->SetInsertPoint(conBlock);
1067            Value* shouldProcessSequentially = b->CreateICmpNE(b->CreateAnd(b->CreateLShr(signMask, b->getInt32(i)), b->getInt32(1)), b->getInt32(0));
1068            Value* originalOutputPos = b->CreateExtractElement(phiOutputPosVec, i);
1069
1070            b->CreateCondBr(shouldProcessSequentially, bodyBlock, innerExitBlock);
1071
1072            // ---- bodyBlock
1073            b->SetInsertPoint(bodyBlock);
1074
1075            // TODO need to handle blockEnd here when doing overwriting memcpy
1076            Value* newOutputPos = this->generateProcessCompressedBlock(
1077                    b,
1078                    b->CreateExtractElement(phiCursorVec, i),
1079                    b->CreateExtractElement(blockEndVec, i),
1080                    originalOutputPos
1081            );
1082
1083            if (i == b->getBitBlockWidth() / SIMD_WIDTH - 1) {
1084                b->setProducedItemCount("outputStream", newOutputPos);
1085            }
1086
1087            b->CreateBr(innerExitBlock);
1088
1089            // ---- exitBlock
1090            b->SetInsertPoint(innerExitBlock);
1091        }
1092
1093
1094        b->CreateBr(exitBlock);
1095
1096        // ---- exitBlock
1097        b->SetInsertPoint(exitBlock);
1098
1099        uint64_t lastVecIndex = b->getBitBlockWidth() / SIMD_WIDTH - 1;
1100        Value* lastBlockEnd = b->CreateExtractElement(blockEndVec, lastVecIndex);
1101        b->setProcessedItemCount("byteStream", lastBlockEnd);
1102        Value* lastOutputPos = b->CreateExtractElement(phiOutputPosVec, lastVecIndex);
1103        b->setProducedItemCount("outputStream", b->CreateUMax(b->getProducedItemCount("outputStream"), lastOutputPos));
1104//        b->CallPrintInt("produced", b->getProducedItemCount("outputStream"));
1105    }
1106
1107
1108
1109    void LZ4ParallelByteStreamDecompressionKernel::generateSequentialDecompression(const std::unique_ptr<KernelBuilder> &b, llvm::Value* startBlockDataIndex, llvm::Value* endBlockDataIndex) {
1110
1111        // ---- EntryBlock
1112        BasicBlock* entryBlock = b->GetInsertBlock();
1113
1114        BasicBlock* SequentialConBlock = b->CreateBasicBlock("SequentialConBlock");
1115        BasicBlock* SequentialBodyBlock = b->CreateBasicBlock("SequentialBodyBlock");
1116        BasicBlock* SequentialExitBlock = b->CreateBasicBlock("SequentialExitBlock");
1117
1118
1119        Value* initOutputPos = b->getProducedItemCount("outputStream");
1120
1121        b->CreateBr(SequentialConBlock);
1122
1123        // ---- SequentialConBlock
1124        b->SetInsertPoint(SequentialConBlock);
1125        PHINode* phiCurrentBlockDataIndex = b->CreatePHI(b->getSizeTy(), 2);
1126        phiCurrentBlockDataIndex->addIncoming(startBlockDataIndex, entryBlock);
1127        PHINode* phiOutputPos = b->CreatePHI(b->getSizeTy(), 2);
1128        phiOutputPos->addIncoming(initOutputPos, entryBlock);
1129
1130        b->CreateCondBr(b->CreateICmpULT(phiCurrentBlockDataIndex, endBlockDataIndex), SequentialBodyBlock, SequentialExitBlock);
1131
1132        // ---- SequentialBodyBlock
1133        b->SetInsertPoint(SequentialBodyBlock);
1134        Value* lz4BlockStart = this->generateLoadInt64NumberInput(b, "blockStart", phiCurrentBlockDataIndex);
1135        Value* lz4BlockEnd = this->generateLoadInt64NumberInput(b, "blockEnd", phiCurrentBlockDataIndex);
1136        Value* newOutputPos = this->generateProcessCompressedBlock(b, lz4BlockStart, lz4BlockEnd, phiOutputPos);
1137
1138        b->setProcessedItemCount("byteStream", lz4BlockEnd);
1139        b->setProducedItemCount("outputStream", newOutputPos);
1140
1141        phiCurrentBlockDataIndex->addIncoming(b->CreateAdd(phiCurrentBlockDataIndex, b->getSize(1)), b->GetInsertBlock());
1142        phiOutputPos->addIncoming(newOutputPos, b->GetInsertBlock());
1143
1144        b->CreateBr(SequentialConBlock);
1145
1146        // ---- SequentialExitBlock
1147        b->SetInsertPoint(SequentialExitBlock);
1148        b->setProcessedItemCount("isCompressed", endBlockDataIndex);
1149
1150    }
1151
1152    llvm::Value *
1153    LZ4ParallelByteStreamDecompressionKernel::generateLoadSimdInt64NumberInput(const std::unique_ptr<KernelBuilder> &iBuilder, std::string inputBufferName,
1154                                     llvm::Value *globalOffset) {
1155        Value * capacity = iBuilder->getCapacity(inputBufferName);
1156        Value * processed = iBuilder->getProcessedItemCount(inputBufferName);
1157        processed = iBuilder->CreateAnd(processed, iBuilder->CreateNeg(capacity));
1158        Value * offset = iBuilder->CreateSub(globalOffset, processed);
1159        Value * valuePtr = iBuilder->getRawInputPointer(inputBufferName, offset);
1160        valuePtr = iBuilder->CreatePointerCast(valuePtr, iBuilder->getBitBlockType()->getPointerTo());
1161        return iBuilder->CreateLoad(valuePtr);
1162    }
1163
1164    llvm::Value *LZ4ParallelByteStreamDecompressionKernel::generateLoadInt64NumberInput(const std::unique_ptr<KernelBuilder> &iBuilder,
1165                                                                      std::string inputBufferName, llvm::Value *globalOffset) {
1166
1167        Value * capacity = iBuilder->getCapacity(inputBufferName);
1168        Value * processed = iBuilder->getProcessedItemCount(inputBufferName);
1169        processed = iBuilder->CreateAnd(processed, iBuilder->CreateNeg(capacity));
1170        Value * offset = iBuilder->CreateSub(globalOffset, processed);
1171        Value * valuePtr = iBuilder->getRawInputPointer(inputBufferName, offset);
1172        return iBuilder->CreateLoad(valuePtr);
1173    }
1174
1175    llvm::Value*
1176    LZ4ParallelByteStreamDecompressionKernel::generateProcessCompressedBlock(const std::unique_ptr<KernelBuilder> &b, llvm::Value *lz4BlockStart,
1177                                                           llvm::Value *lz4BlockEnd, llvm::Value* initOutputPos) {
1178        BasicBlock* entryBlock = b->GetInsertBlock();
1179
1180        Value* isTerminal = b->CreateICmpEQ(lz4BlockEnd, b->getScalarField("fileSize"));
1181        b->setTerminationSignal(isTerminal);
1182
1183        BasicBlock* exitBlock = b->CreateBasicBlock("processCompressedExitBlock");
1184
1185        BasicBlock* processCon = b->CreateBasicBlock("processCompressedConBlock");
1186        BasicBlock* processBody = b->CreateBasicBlock("processCompressedBodyBlock");
1187
1188
1189        BasicBlock* beforeProcessConBlock = b->GetInsertBlock();
1190        b->CreateBr(processCon);
1191        b->SetInsertPoint(processCon);
1192        PHINode* phiOutputPos = b->CreatePHI(initOutputPos->getType(), 2);
1193        phiOutputPos->addIncoming(initOutputPos, entryBlock);
1194        PHINode* phiCursorValue = b->CreatePHI(b->getInt64Ty(), 2); // phiCursorValue should always be the position of next token except for the final sequence
1195        phiCursorValue->addIncoming(lz4BlockStart, beforeProcessConBlock);
1196
1197        b->CreateCondBr(b->CreateICmpULT(phiCursorValue, lz4BlockEnd), processBody, exitBlock);
1198
1199        b->SetInsertPoint(processBody);
1200
1201
1202        auto ret = this->processBlockBoundary(b, phiCursorValue, lz4BlockEnd, phiOutputPos);
1203        Value* nextTokenGlobalPos = ret.first;
1204        Value* nextOutputPos = ret.second;
1205
1206        phiOutputPos->addIncoming(nextOutputPos, b->GetInsertBlock());
1207        phiCursorValue->addIncoming(nextTokenGlobalPos, b->GetInsertBlock());
1208        b->CreateBr(processCon);
1209
1210        b->SetInsertPoint(exitBlock);
1211        return phiOutputPos;
1212    }
1213
1214    pair<Value*, Value*> LZ4ParallelByteStreamDecompressionKernel::parseLiteralInfo(const std::unique_ptr<KernelBuilder> &b, llvm::Value *tokenPos, llvm::Value* tokenValue) {
1215        BasicBlock* entryBlock = b->GetInsertBlock();
1216
1217        Value* bytePtrBase = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
1218
1219        Value* shouldExtendLiteral = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_F0), BYTE_F0);
1220        BasicBlock* extendLiteralCond = b->CreateBasicBlock("extendLiteralCond");
1221        BasicBlock* extendLiteralEnd = b->CreateBasicBlock("extendLiteralEnd");
1222
1223        Value* initExtendLiteralPos = b->CreateAdd(tokenPos, b->getSize(1));
1224
1225        b->CreateCondBr(shouldExtendLiteral, extendLiteralCond, extendLiteralEnd);
1226
1227        // ---- extendLiteralCond
1228        b->SetInsertPoint(extendLiteralCond);
1229        PHINode* phiCurrentExtendLiteralPos = b->CreatePHI(b->getSizeTy(), 2);
1230        phiCurrentExtendLiteralPos->addIncoming(initExtendLiteralPos, entryBlock);
1231        PHINode* phiExtendLiteralLength = b->CreatePHI(b->getSizeTy(), 2);
1232        phiExtendLiteralLength->addIncoming(SIZE_0, entryBlock);
1233
1234        Value* currentLiteralLengthByte = b->CreateLoad(b->CreateGEP(bytePtrBase, phiCurrentExtendLiteralPos));
1235        Value* newExtendLiteralLength = b->CreateAdd(phiExtendLiteralLength, b->CreateZExt(currentLiteralLengthByte, b->getSizeTy()));
1236
1237        phiCurrentExtendLiteralPos->addIncoming(b->CreateAdd(phiCurrentExtendLiteralPos, SIZE_1), b->GetInsertBlock());
1238        phiExtendLiteralLength->addIncoming(newExtendLiteralLength, b->GetInsertBlock());
1239
1240        b->CreateCondBr(b->CreateICmpEQ(currentLiteralLengthByte, BYTE_FF), extendLiteralCond, extendLiteralEnd);
1241
1242        // ---- extendLiteralEnd
1243        b->SetInsertPoint(extendLiteralEnd);
1244        PHINode* literalExtendValue = b->CreatePHI(b->getSizeTy(), 2);
1245        literalExtendValue->addIncoming(SIZE_0, entryBlock);
1246        literalExtendValue->addIncoming(newExtendLiteralLength, extendLiteralCond);
1247        PHINode* phiExtendLiteralEndPos = b->CreatePHI(b->getSizeTy(), 2);
1248        phiExtendLiteralEndPos->addIncoming(tokenPos, entryBlock);
1249        phiExtendLiteralEndPos->addIncoming(phiCurrentExtendLiteralPos, extendLiteralCond);
1250
1251        Value* literalLength = b->CreateAdd(literalExtendValue, b->CreateZExt(b->CreateLShr(tokenValue, b->getInt8(4)), b->getSizeTy()));
1252
1253        Value* literalStartPos = b->CreateAdd(phiExtendLiteralEndPos, SIZE_1);
1254        return std::make_pair(literalStartPos, literalLength);
1255    }
1256
1257    std::pair<llvm::Value *, llvm::Value *> LZ4ParallelByteStreamDecompressionKernel::parseMatchInfo(const std::unique_ptr<KernelBuilder> &b, llvm::Value *matchOffsetPos, llvm::Value* tokenValue) {
1258        Value* bytePtrBase = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
1259
1260        Value* shouldExtendMatch = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_0F), BYTE_0F);
1261        BasicBlock* entryBlock = b->GetInsertBlock();
1262        BasicBlock* extendMatchCon = b->CreateBasicBlock("extendMatchCon");
1263        BasicBlock* extendMatchExit = b->CreateBasicBlock("extendMatchExit");
1264
1265        Value* matchOffsetNextPos = b->CreateAdd(matchOffsetPos, SIZE_1);
1266        Value* initExtendMatchPos = b->CreateAdd(matchOffsetPos, b->getSize(2));
1267
1268        b->CreateCondBr(shouldExtendMatch, extendMatchCon, extendMatchExit);
1269
1270        // ---- extendMatchCon
1271        b->SetInsertPoint(extendMatchCon);
1272        PHINode* phiCurrentExtendMatchPos = b->CreatePHI(b->getSizeTy(), 2);
1273        phiCurrentExtendMatchPos->addIncoming(initExtendMatchPos, entryBlock);
1274        PHINode* phiExtendMatchLength = b->CreatePHI(b->getSizeTy(), 2);
1275        phiExtendMatchLength->addIncoming(SIZE_0, entryBlock);
1276
1277        Value* currentMatchLengthByte = b->CreateLoad(b->CreateGEP(bytePtrBase, phiCurrentExtendMatchPos));
1278        Value* newExtendMatchLength = b->CreateAdd(phiExtendMatchLength, b->CreateZExt(currentMatchLengthByte, b->getSizeTy()));
1279
1280        phiCurrentExtendMatchPos->addIncoming(b->CreateAdd(phiCurrentExtendMatchPos, SIZE_1), b->GetInsertBlock());
1281        phiExtendMatchLength->addIncoming(newExtendMatchLength, b->GetInsertBlock());
1282
1283        b->CreateCondBr(b->CreateICmpEQ(currentMatchLengthByte, BYTE_FF), extendMatchCon, extendMatchExit);
1284
1285        // ---- extendMatchExit
1286        b->SetInsertPoint(extendMatchExit);
1287        PHINode* matchExtendValue = b->CreatePHI(b->getSizeTy(), 2);
1288        matchExtendValue->addIncoming(SIZE_0, entryBlock);
1289        matchExtendValue->addIncoming(newExtendMatchLength, extendMatchCon);
1290        PHINode* phiExtendMatchEndPos = b->CreatePHI(b->getSizeTy(), 2);
1291        phiExtendMatchEndPos->addIncoming(matchOffsetNextPos, entryBlock);
1292        phiExtendMatchEndPos->addIncoming(phiCurrentExtendMatchPos, extendMatchCon);
1293
1294        // matchLength = (size_t)token & 0xf + 4 + matchExtendValue
1295        Value* matchLength = b->CreateAdd(
1296                b->CreateAdd(matchExtendValue, b->getSize(4)),
1297                b->CreateZExt(b->CreateAnd(tokenValue, BYTE_0F), b->getSizeTy())
1298        );
1299        return std::make_pair(phiExtendMatchEndPos, matchLength);
1300
1301    };
1302
1303    pair<Value*, Value*> LZ4ParallelByteStreamDecompressionKernel::processBlockBoundary(const std::unique_ptr<KernelBuilder> &b, llvm::Value *beginTokenPos,
1304                                                              llvm::Value *lz4BlockEnd, llvm::Value* initOutputPos) {
1305        // ---- EntryBlock
1306        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
1307        Value* bytePtrBase = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
1308        Value* tokenValue = b->CreateLoad(b->CreateGEP(bytePtrBase, beginTokenPos));
1309
1310
1311        // Literal
1312        Value *literalStartPos = nullptr, *literalLength = nullptr;
1313        std::tie(literalStartPos, literalLength) = this->parseLiteralInfo(b, beginTokenPos, tokenValue);
1314        this->handleLiteralCopy(b, literalStartPos, literalLength, initOutputPos);
1315        Value* literalEndPos = b->CreateAdd(literalStartPos, literalLength);
1316        Value* outputPosAfterLiteralCpy = b->CreateAdd(literalLength, initOutputPos);
1317
1318
1319        Value* matchOffsetBeginPos = literalEndPos;
1320        Value* matchOffsetNextPos = b->CreateAdd(matchOffsetBeginPos, SIZE_1);
1321        BasicBlock* hasMatchPartBlock = b->CreateBasicBlock("hasMatchPartBlock");
1322        BasicBlock* extendLiteralEndFinal = b->GetInsertBlock();
1323        b->CreateLikelyCondBr(b->CreateICmpULT(matchOffsetBeginPos, lz4BlockEnd), hasMatchPartBlock, exitBlock);
1324
1325
1326        // ---- hasMatchPartBlock
1327        b->SetInsertPoint(hasMatchPartBlock);
1328        // Match
1329        // For now, it is safe to cast matchOffset pointer into i16 since the input byte stream is always linear available
1330        Value* matchOffsetPtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", matchOffsetBeginPos), b->getInt16Ty()->getPointerTo());
1331        Value* matchOffset = b->CreateZExt(b->CreateLoad(matchOffsetPtr), b->getSizeTy());
1332
1333        Value *matchLengthEndPos = nullptr, *matchLength = nullptr;
1334        std::tie(matchLengthEndPos, matchLength) = this->parseMatchInfo(b, matchOffsetBeginPos, tokenValue);
1335        this->handleMatchCopy(b, matchOffset, matchLength, outputPosAfterLiteralCpy);
1336        Value* outputPosAfterMatchCpy = b->CreateAdd(outputPosAfterLiteralCpy, matchLength);
1337        BasicBlock* extendMatchExitFinal = b->GetInsertBlock();
1338        b->CreateBr(exitBlock);
1339
1340
1341        // ---- exitBlock
1342        b->SetInsertPoint(exitBlock);
1343        PHINode* phiBeforeTokenPos = b->CreatePHI(b->getSizeTy(), 2);
1344        phiBeforeTokenPos->addIncoming(matchOffsetNextPos, extendLiteralEndFinal);
1345        phiBeforeTokenPos->addIncoming(matchLengthEndPos, extendMatchExitFinal);
1346        PHINode* phiOutputPos = b->CreatePHI(b->getSizeTy(), 2);
1347        phiOutputPos->addIncoming(outputPosAfterLiteralCpy, extendLiteralEndFinal);
1348        phiOutputPos->addIncoming(outputPosAfterMatchCpy, extendMatchExitFinal);
1349
1350        Value* nextTokenPos = b->CreateAdd(phiBeforeTokenPos, SIZE_1);
1351
1352        return std::make_pair(nextTokenPos, phiOutputPos);
1353    }
1354
1355    void LZ4ParallelByteStreamDecompressionKernel::generateSimdMatchCopyByScatter(const std::unique_ptr<KernelBuilder> &b, llvm::Value* matchOffsetVec, llvm::Value* matchLengthVec, llvm::Value* outputPosVec) {
1356        // ---- EntryBlock
1357        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
1358        BasicBlock* i64MatchCopyBlock = b->CreateBasicBlock("i64MatchCopyBlock");
1359        BasicBlock* i8MatchCopyBlock = b->CreateBasicBlock("i8MatchCopyBlock");
1360
1361        llvm::Value* initCopiedLength = ConstantVector::getNullValue(matchLengthVec->getType());
1362
1363//        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
1364        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", b->getSize(0)), b->getInt8PtrTy());
1365
1366        Value* outputCapacity = b->getCapacity("outputStream");
1367        Value* outputPosRemVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(outputCapacity))));
1368        Value* outputPosRemBlockSizeVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(b->getIntN(SIMD_WIDTH, mLz4BlockSize)))));
1369        Value* remainingBlockSizeVec = b->simd_sub(SIMD_WIDTH, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, mLz4BlockSize)), outputPosRemBlockSizeVec);
1370
1371        Value* possibleExceedBuffer = b->simd_uge(SIMD_WIDTH, b->simd_add(SIMD_WIDTH, matchLengthVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 8))), remainingBlockSizeVec);
1372        // true ffff, false 0000
1373
1374        // TODO handle matchLengthVec == 0
1375
1376        b->CreateUnlikelyCondBr(
1377                b->CreateICmpNE(b->CreateBitCast(possibleExceedBuffer, b->getIntNTy(b->getBitBlockWidth())), b->getIntN(b->getBitBlockWidth(), 0)),
1378                i8MatchCopyBlock,
1379                i64MatchCopyBlock
1380        );
1381
1382        // ---- i8MatchCopyBlock
1383        b->SetInsertPoint(i8MatchCopyBlock);
1384        this->generateSimdSequentialMatchCopy(b, matchOffsetVec, matchLengthVec, outputPosVec);
1385        b->CreateBr(exitBlock);
1386
1387        // ---- i64MatchCopyBlock
1388        b->SetInsertPoint(i64MatchCopyBlock);
1389
1390        BasicBlock* i64MatchCopyConBlock = b->CreateBasicBlock("i64MatchCopyConBlock");
1391        BasicBlock* i64MatchCopyBodyBlock = b->CreateBasicBlock("i64MatchCopyBodyBlock");
1392
1393        b->CreateBr(i64MatchCopyConBlock);
1394
1395        // ---- i64MatchCopyConBlock
1396        b->SetInsertPoint(i64MatchCopyConBlock);
1397        PHINode* phiCopiedLength = b->CreatePHI(initCopiedLength->getType(), 2);
1398        phiCopiedLength->addIncoming(initCopiedLength, i64MatchCopyBlock);
1399
1400        Value* shouldCopiedBitBlock = b->simd_ult(SIMD_WIDTH, phiCopiedLength, matchLengthVec);
1401//        b->CallPrintRegister("phiCopiedLength", phiCopiedLength);
1402//        b->CallPrintRegister("literalLengthVec", literalLengthVec);
1403//        b->CallPrintRegister("shouldCopiedBitBlock", shouldCopiedBitBlock);
1404        Value* shouldCopiedI1 = b->CreateICmpNE(
1405                b->CreateBitCast(shouldCopiedBitBlock, b->getIntNTy(b->getBitBlockWidth())),
1406                b->getIntN(b->getBitBlockWidth(), 0)
1407        );
1408
1409
1410        b->CreateCondBr(shouldCopiedI1, i64MatchCopyBodyBlock, exitBlock);
1411
1412        // ---- i64MatchCopyBodyBlock
1413        b->SetInsertPoint(i64MatchCopyBodyBlock);
1414        Value* currentOutputPosVec = b->simd_add(SIMD_WIDTH, outputPosRemVec, phiCopiedLength);
1415        Value* copyFromPosVec = b->simd_sub(SIMD_WIDTH, currentOutputPosVec, matchOffsetVec);
1416
1417        Value* literalData = this->simdFetchI64DataByGather(b, outputBasePtr, copyFromPosVec, shouldCopiedBitBlock);
1418
1419        this->simdPutData(
1420                b,
1421                outputBasePtr,
1422                currentOutputPosVec,
1423                literalData,
1424                shouldCopiedBitBlock
1425        );
1426        phiCopiedLength->addIncoming(
1427                b->simd_add(
1428                        SIMD_WIDTH,
1429                        phiCopiedLength,
1430                        b->simd_and(
1431                                b->simd_umin(SIMD_WIDTH, matchOffsetVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 8))),
1432                                shouldCopiedBitBlock
1433                        )
1434
1435                ),
1436                b->GetInsertBlock()
1437        );
1438
1439        b->CreateBr(i64MatchCopyConBlock);
1440        b->SetInsertPoint(exitBlock);
1441
1442    }
1443
1444    void LZ4ParallelByteStreamDecompressionKernel::generateSimdSequentialMatchCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value* matchOffsetVec, llvm::Value* matchLengthVec, llvm::Value* outputPosVec) {
1445        // Constant
1446        Constant * SIZE_8 = b->getSize(8);
1447        // Type
1448        PointerType* i64PtrTy = b->getInt64Ty()->getPointerTo();
1449        PointerType* i8PtrTy = b->getInt8PtrTy();
1450
1451        Value* outputCapacity = b->getCapacity("outputStream");
1452        Value* outputPosRemVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(outputCapacity))));
1453        Value* outputPosRemBlockSizeVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(b->getIntN(SIMD_WIDTH, mLz4BlockSize)))));
1454        Value* remainingBlockSizeVec = b->simd_sub(SIMD_WIDTH, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, mLz4BlockSize)), outputPosRemBlockSizeVec);
1455        Value* copyFromPosRemVec = b->simd_sub(SIMD_WIDTH, outputPosRemVec, matchOffsetVec);
1456
1457
1458        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", b->getSize(0)), b->getInt8PtrTy());
1459
1460
1461        for (unsigned i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
1462
1463            BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
1464            BasicBlock* i64MatchCopyBlock = b->CreateBasicBlock("i64LiteralCopyBlock");
1465            BasicBlock* i8MatchCopyBlock = b->CreateBasicBlock("i8LiteralCopyBlock");
1466
1467            // ---- entryBlock
1468            Value* matchOffset = b->CreateExtractElement(matchOffsetVec, i);
1469            Value* matchLength = b->CreateExtractElement(matchLengthVec, i);
1470            Value* outputPosRem = b->CreateExtractElement(outputPosRemVec, i);
1471            Value* remainingBlockSize = b->CreateExtractElement(remainingBlockSizeVec, i);
1472            Value* outputFromRem = b->CreateExtractElement(copyFromPosRemVec, i);
1473
1474            Value* inputInitPtr = b->CreateGEP(outputBasePtr, outputFromRem);
1475            Value* outputInitPtr = b->CreateGEP(outputBasePtr, outputPosRem);
1476
1477            b->CreateLikelyCondBr(b->CreateICmpUGE(b->CreateSub(remainingBlockSize, matchLength), SIZE_8), i64MatchCopyBlock, i8MatchCopyBlock);
1478
1479            //// i64 Match Copy
1480            // ---- i64MatchCopyBlock
1481            b->SetInsertPoint(i64MatchCopyBlock);
1482
1483            this->generateOverwritingMemcpy(b, inputInitPtr, outputInitPtr, matchLength, i64PtrTy, b->CreateUMin(matchOffset, SIZE_8));
1484            b->CreateBr(exitBlock);
1485
1486            //// i8 Match Copy
1487            // ---- i8MatchCopyBlock
1488            b->SetInsertPoint(i8MatchCopyBlock);
1489            this->generateOverwritingMemcpy(b, inputInitPtr, outputInitPtr, matchLength, i8PtrTy, 1);
1490            b->CreateBr(exitBlock);
1491
1492            // ---- exitBlock
1493            b->SetInsertPoint(exitBlock);
1494
1495        }
1496
1497    }
1498
1499    void LZ4ParallelByteStreamDecompressionKernel::handleSimdMatchCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value* matchOffsetVec, llvm::Value* matchLengthVec, llvm::Value* outputPosVec) {
1500        if (AVX512BW_available() && mEnableScatter) {
1501            this->generateSimdMatchCopyByScatter(b, matchOffsetVec, matchLengthVec, outputPosVec);
1502        } else {
1503            this->generateSimdSequentialMatchCopy(b, matchOffsetVec, matchLengthVec, outputPosVec);
1504        }
1505    }
1506
1507    void LZ4ParallelByteStreamDecompressionKernel::handleSimdLiteralCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value* literalStartVec, llvm::Value* literalLengthVec, llvm::Value* outputPosVec) {
1508//        this->recordParallelLevel(b, b->hsimd_signmask(SIMD_WIDTH, b->simd_gt(SIMD_WIDTH, literalLengthVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 32)))));
1509        if (AVX512BW_available() && mEnableScatter) {
1510            this->generateSimdLiteralCopyByScatter(b, literalStartVec, literalLengthVec, outputPosVec);
1511        } else {
1512            this->generateSimdSequentialLiteralCopy(b, literalStartVec, literalLengthVec, outputPosVec);
1513        }
1514    }
1515
1516    void LZ4ParallelByteStreamDecompressionKernel::generateSimdSequentialLiteralCopy(const std::unique_ptr<KernelBuilder> &b,
1517                                                                           llvm::Value *literalStartVec,
1518                                                                           llvm::Value *literalLengthVec,
1519                                                                           llvm::Value *outputPosVec) {
1520        // Constant
1521        Constant * SIZE_8 = b->getSize(8);
1522        // Type
1523        PointerType* i64PtrTy = b->getInt64Ty()->getPointerTo();
1524        PointerType* i8PtrTy = b->getInt8PtrTy();
1525
1526        Value* outputCapacity = b->getCapacity("outputStream");
1527        Value* outputPosRemVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(outputCapacity))));
1528        Value* outputPosRemBlockSizeVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(b->getIntN(SIMD_WIDTH, mLz4BlockSize)))));
1529        Value* remainingBlockSizeVec = b->simd_sub(SIMD_WIDTH, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, mLz4BlockSize)), outputPosRemBlockSizeVec);
1530
1531        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
1532        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", b->getSize(0)), b->getInt8PtrTy());
1533
1534
1535        for (unsigned i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
1536            BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
1537            BasicBlock* i64LiteralCopyBlock = b->CreateBasicBlock("i64LiteralCopyBlock");
1538            BasicBlock* i8LiteralCopyBlock = b->CreateBasicBlock("i8LiteralCopyBlock");
1539
1540            // ---- entryBlock
1541            Value* literalStart = b->CreateExtractElement(literalStartVec, i);
1542            Value* literalLength = b->CreateExtractElement(literalLengthVec, i);
1543            Value* outputPosRem = b->CreateExtractElement(outputPosRemVec, i);
1544            Value* remainingBlockSize = b->CreateExtractElement(remainingBlockSizeVec, i);
1545
1546            Value* inputInitPtr = b->CreateGEP(inputBasePtr, literalStart);
1547            Value* outputInitPtr = b->CreateGEP(outputBasePtr, outputPosRem);
1548
1549            b->CreateLikelyCondBr(b->CreateICmpUGE(b->CreateSub(remainingBlockSize, literalLength), SIZE_8), i64LiteralCopyBlock, i8LiteralCopyBlock);
1550
1551            //// i64 Literal Copy
1552            // ---- i64LiteralCopyBlock
1553            b->SetInsertPoint(i64LiteralCopyBlock);
1554            this->generateOverwritingMemcpy(b, inputInitPtr, outputInitPtr, literalLength, i64PtrTy, 8);
1555            b->CreateBr(exitBlock);
1556
1557            //// i8 Literal Copy
1558            // ---- i8LiteralCopyBlock
1559            b->SetInsertPoint(i8LiteralCopyBlock);
1560            this->generateOverwritingMemcpy(b, inputInitPtr, outputInitPtr, literalLength, i8PtrTy, 1);
1561            b->CreateBr(exitBlock);
1562
1563            // ---- exitBlock
1564            b->SetInsertPoint(exitBlock);
1565        }
1566    }
1567
1568    void LZ4ParallelByteStreamDecompressionKernel::generateOverwritingMemcpy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *inputBasePtr,
1569                                   llvm::Value *outputBasePtr, llvm::Value *copyBytes, llvm::PointerType *targetPtrTy,
1570                                   llvm::Value* stepSize) {
1571//        unsigned targetPtrBitWidth = targetPtrTy->getElementType()->getIntegerBitWidth();
1572
1573        Constant * SIZE_0 = b->getSize(0);
1574//        Constant * SIZE_1 = b->getSize(1);
1575        PointerType* i8PtrTy = b->getInt8PtrTy();
1576
1577        BasicBlock* entryBlock = b->GetInsertBlock();
1578        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
1579        BasicBlock* conBlock = b->CreateBasicBlock("conBlock");
1580        BasicBlock* bodyBlock = b->CreateBasicBlock("bodyBlock");
1581
1582        Value* inputInitPtr = b->CreatePointerCast(inputBasePtr, targetPtrTy);
1583        Value* outputInitPtr = b->CreatePointerCast(outputBasePtr, targetPtrTy);
1584
1585        b->CreateBr(conBlock);
1586        // ---- conBlock
1587        b->SetInsertPoint(conBlock);
1588
1589        PHINode *phiCopiedSize = b->CreatePHI(b->getSizeTy(), 2);
1590        phiCopiedSize->addIncoming(SIZE_0, entryBlock);
1591        PHINode *phiInputPtr = b->CreatePHI(targetPtrTy, 2);
1592        phiInputPtr->addIncoming(inputInitPtr, entryBlock);
1593        PHINode *phiOutputPtr = b->CreatePHI(targetPtrTy, 2);
1594        phiOutputPtr->addIncoming(outputInitPtr, entryBlock);
1595
1596        b->CreateCondBr(b->CreateICmpULT(phiCopiedSize, copyBytes), bodyBlock, exitBlock);
1597
1598        // ---- bodyBlock
1599        b->SetInsertPoint(bodyBlock);
1600        b->CreateStore(b->CreateLoad(phiInputPtr), phiOutputPtr);
1601
1602        phiCopiedSize->addIncoming(b->CreateAdd(phiCopiedSize, stepSize), b->GetInsertBlock());
1603
1604        Value *newInputPtr = nullptr, *newOutputPtr = nullptr;
1605
1606        newInputPtr = b->CreatePointerCast(
1607                b->CreateGEP(b->CreatePointerCast(phiInputPtr, i8PtrTy), stepSize),
1608                targetPtrTy
1609        );
1610
1611        newOutputPtr = b->CreatePointerCast(
1612                b->CreateGEP(b->CreatePointerCast(phiOutputPtr, i8PtrTy), stepSize),
1613                targetPtrTy
1614        );
1615
1616        phiInputPtr->addIncoming(newInputPtr, b->GetInsertBlock());
1617        phiOutputPtr->addIncoming(newOutputPtr, b->GetInsertBlock());
1618        b->CreateBr(conBlock);
1619
1620        // ---- exitBlock
1621        b->SetInsertPoint(exitBlock);
1622    }
1623
1624    void LZ4ParallelByteStreamDecompressionKernel::generateOverwritingMemcpy(const std::unique_ptr<KernelBuilder> &b,
1625                                                                   llvm::Value *inputBasePtr,
1626                                                                   llvm::Value *outputBasePtr,
1627                                                                   llvm::Value *copyBytes, llvm::PointerType *targetPtrTy,
1628                                                                   size_t stepSize) {
1629        unsigned targetPtrBitWidth = targetPtrTy->getElementType()->getIntegerBitWidth();
1630
1631        Constant * SIZE_0 = b->getSize(0);
1632        Constant * SIZE_1 = b->getSize(1);
1633        PointerType* i8PtrTy = b->getInt8PtrTy();
1634
1635        BasicBlock* entryBlock = b->GetInsertBlock();
1636        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
1637        BasicBlock* conBlock = b->CreateBasicBlock("conBlock");
1638        BasicBlock* bodyBlock = b->CreateBasicBlock("bodyBlock");
1639
1640        Value* inputInitPtr = b->CreatePointerCast(inputBasePtr, targetPtrTy);
1641        Value* outputInitPtr = b->CreatePointerCast(outputBasePtr, targetPtrTy);
1642
1643        b->CreateBr(conBlock);
1644        // ---- conBlock
1645        b->SetInsertPoint(conBlock);
1646
1647        PHINode *phiCopiedSize = b->CreatePHI(b->getSizeTy(), 2);
1648        phiCopiedSize->addIncoming(SIZE_0, entryBlock);
1649        PHINode *phiInputPtr = b->CreatePHI(targetPtrTy, 2);
1650        phiInputPtr->addIncoming(inputInitPtr, entryBlock);
1651        PHINode *phiOutputPtr = b->CreatePHI(targetPtrTy, 2);
1652        phiOutputPtr->addIncoming(outputInitPtr, entryBlock);
1653
1654        b->CreateCondBr(b->CreateICmpULT(phiCopiedSize, copyBytes), bodyBlock, exitBlock); //TODO 2 cond brs (one likely br here, the other unlikely br at the end of body) may be better
1655
1656        // ---- bodyBlock
1657        b->SetInsertPoint(bodyBlock);
1658        b->CreateStore(b->CreateLoad(phiInputPtr), phiOutputPtr);
1659
1660        phiCopiedSize->addIncoming(b->CreateAdd(phiCopiedSize, b->getSize(stepSize)), b->GetInsertBlock());
1661
1662        Value *newInputPtr = nullptr, *newOutputPtr = nullptr;
1663
1664        if (targetPtrBitWidth / 8 == stepSize) {
1665            newInputPtr = b->CreateGEP(phiInputPtr, SIZE_1);
1666            newOutputPtr = b->CreateGEP(phiOutputPtr, SIZE_1);
1667        } else {
1668            newInputPtr = b->CreatePointerCast(
1669                    b->CreateGEP(b->CreatePointerCast(phiInputPtr, i8PtrTy), b->getSize(stepSize)),
1670                    targetPtrTy
1671            );
1672
1673            newOutputPtr = b->CreatePointerCast(
1674                    b->CreateGEP(b->CreatePointerCast(phiOutputPtr, i8PtrTy), b->getSize(stepSize)),
1675                    targetPtrTy
1676            );
1677
1678        }
1679
1680        phiInputPtr->addIncoming(newInputPtr, b->GetInsertBlock());
1681        phiOutputPtr->addIncoming(newOutputPtr, b->GetInsertBlock());
1682        b->CreateBr(conBlock);
1683
1684        // ---- exitBlock
1685        b->SetInsertPoint(exitBlock);
1686    }
1687
1688    void LZ4ParallelByteStreamDecompressionKernel::generateSimdLiteralCopyByScatter(const std::unique_ptr<KernelBuilder> &b,
1689                                                                          llvm::Value *literalStartVec,
1690                                                                          llvm::Value *literalLengthVec,
1691                                                                          llvm::Value *outputPosVec) {
1692        // ---- EntryBlock
1693        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
1694        BasicBlock* i64LiteralCopyBlock = b->CreateBasicBlock("i64LiteralCopyBlock");
1695        BasicBlock* i8LiteralCopyBlock = b->CreateBasicBlock("i8LiteralCopyBlock");
1696
1697        llvm::Value* initCopiedLength = ConstantVector::getNullValue(literalLengthVec->getType());
1698
1699        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
1700        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", b->getSize(0)), b->getInt8PtrTy());
1701
1702        Value* outputCapacity = b->getCapacity("outputStream");
1703        Value* outputPosRemVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(outputCapacity))));
1704        Value* outputPosRemBlockSizeVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(b->getIntN(SIMD_WIDTH, mLz4BlockSize)))));
1705        Value* remainingBlockSizeVec = b->simd_sub(SIMD_WIDTH, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, mLz4BlockSize)), outputPosRemBlockSizeVec);
1706
1707        Value* possibleExceedBuffer = b->simd_uge(SIMD_WIDTH, b->simd_add(SIMD_WIDTH, literalLengthVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 8))), remainingBlockSizeVec);
1708        // true ffff, false 0000
1709
1710        // TODO handle literalLengthVec == 0
1711
1712        b->CreateUnlikelyCondBr(
1713                b->CreateICmpNE(b->CreateBitCast(possibleExceedBuffer, b->getIntNTy(b->getBitBlockWidth())), b->getIntN(b->getBitBlockWidth(), 0)),
1714                i8LiteralCopyBlock,
1715                i64LiteralCopyBlock
1716        );
1717
1718        // ---- i8LiteralCopyBlock
1719        b->SetInsertPoint(i8LiteralCopyBlock);
1720        this->generateSimdSequentialLiteralCopy(b, literalStartVec, literalLengthVec, outputPosVec);
1721        b->CreateBr(exitBlock);
1722
1723        // ---- i64LiteralCopyBlock
1724        b->SetInsertPoint(i64LiteralCopyBlock);
1725
1726        BasicBlock* i64LiteralCopyConBlock = b->CreateBasicBlock("i64LiteralCopyConBlock");
1727        BasicBlock* i64LiteralCopyBodyBlock = b->CreateBasicBlock("i64LiteralCopyBodyBlock");
1728
1729
1730        b->CreateBr(i64LiteralCopyConBlock);
1731
1732        // ---- i64LiteralCopyConBlock
1733        b->SetInsertPoint(i64LiteralCopyConBlock);
1734        PHINode* phiCopiedLength = b->CreatePHI(initCopiedLength->getType(), 2);
1735        phiCopiedLength->addIncoming(initCopiedLength, i64LiteralCopyBlock);
1736
1737        Value* shouldCopiedBitBlock = b->simd_ult(SIMD_WIDTH, phiCopiedLength, literalLengthVec);
1738//        b->CallPrintRegister("phiCopiedLength", phiCopiedLength);
1739//        b->CallPrintRegister("literalLengthVec", literalLengthVec);
1740//        b->CallPrintRegister("shouldCopiedBitBlock", shouldCopiedBitBlock);
1741        Value* shouldCopiedI1 = b->CreateICmpNE(
1742                b->CreateBitCast(shouldCopiedBitBlock, b->getIntNTy(b->getBitBlockWidth())),
1743                b->getIntN(b->getBitBlockWidth(), 0)
1744        );
1745
1746
1747        b->CreateCondBr(shouldCopiedI1, i64LiteralCopyBodyBlock, exitBlock);
1748
1749
1750        // ---- i64LiteralCopyBodyBlock
1751        b->SetInsertPoint(i64LiteralCopyBodyBlock);
1752        Value* literalData = this->simdFetchI64DataByGather(b, inputBasePtr, b->simd_add(SIMD_WIDTH, literalStartVec, phiCopiedLength), shouldCopiedBitBlock);
1753
1754        this->simdPutData(
1755                b,
1756                outputBasePtr,
1757                b->simd_add(SIMD_WIDTH, outputPosRemVec, phiCopiedLength),
1758                literalData,
1759                shouldCopiedBitBlock
1760        );
1761//        b->CallPrintRegister("phiCopiedLength", phiCopiedLength);
1762        phiCopiedLength->addIncoming(
1763                b->simd_add(
1764                        SIMD_WIDTH,
1765                        phiCopiedLength,
1766                        b->simd_and(
1767                                b->simd_fill(
1768                                        SIMD_WIDTH,
1769                                        b->getIntN(SIMD_WIDTH, 8)
1770                                ),
1771                                shouldCopiedBitBlock
1772                        )
1773
1774                ),
1775                b->GetInsertBlock()
1776        );
1777
1778        b->CreateBr(i64LiteralCopyConBlock);
1779
1780        b->SetInsertPoint(exitBlock);
1781    }
1782
1783
1784    void LZ4ParallelByteStreamDecompressionKernel::handleLiteralCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *literalStart,
1785                                                   llvm::Value *literalLength, llvm::Value* outputPos) {
1786        unsigned fw = 64;
1787        Type* INT_FW_PTR = b->getIntNTy(fw)->getPointerTo();
1788
1789        Value* inputBytePtr = b->getRawInputPointer("byteStream", literalStart);
1790        Value* inputPtr = b->CreatePointerCast(inputBytePtr, INT_FW_PTR);
1791
1792        Value* outputBufferSize = b->getCapacity("outputStream");
1793        Value* outputPtr = b->getRawOutputPointer("outputStream", b->CreateURem(outputPos, outputBufferSize));
1794        outputPtr = b->CreatePointerCast(outputPtr, INT_FW_PTR);
1795
1796        // We can always assume that we have enough output buffer based on our output buffer allocation strategy (except in extract only case)
1797
1798        BasicBlock* entryBlock = b->GetInsertBlock();
1799        BasicBlock* literalCopyCon = b->CreateBasicBlock("literalCopyCon");
1800        BasicBlock* literalCopyBody = b->CreateBasicBlock("literalCopyBody");
1801        BasicBlock* literalCopyExit = b->CreateBasicBlock("literalCopyExit");
1802
1803        b->CreateBr(literalCopyCon);
1804
1805        // ---- literalCopyCon
1806        b->SetInsertPoint(literalCopyCon);
1807        PHINode* phiOutputPtr = b->CreatePHI(outputPtr->getType(), 2);
1808        phiOutputPtr->addIncoming(outputPtr, entryBlock);
1809        PHINode* phiInputPtr = b->CreatePHI(inputPtr->getType(), 2);
1810        phiInputPtr->addIncoming(inputPtr, entryBlock);
1811        PHINode* phiCopiedLength = b->CreatePHI(literalLength->getType(), 2);
1812        phiCopiedLength->addIncoming(b->getSize(0), entryBlock);
1813        b->CreateCondBr(b->CreateICmpULT(phiCopiedLength, literalLength), literalCopyBody, literalCopyExit);
1814
1815        // ---- literalCopyBody
1816        b->SetInsertPoint(literalCopyBody);
1817        // Always copy fw bits to improve performance
1818        b->CreateStore(b->CreateLoad(phiInputPtr), phiOutputPtr);
1819
1820        phiInputPtr->addIncoming(b->CreateGEP(phiInputPtr, b->getSize(1)), b->GetInsertBlock());
1821        phiOutputPtr->addIncoming(b->CreateGEP(phiOutputPtr, b->getSize(1)), b->GetInsertBlock());
1822        phiCopiedLength->addIncoming(b->CreateAdd(phiCopiedLength, b->getSize(fw / 8)), b->GetInsertBlock());
1823        b->CreateBr(literalCopyCon);
1824
1825        // ---- literalCopyExit
1826        b->SetInsertPoint(literalCopyExit);
1827        b->setScalarField("outputPos", b->CreateAdd(outputPos, literalLength));
1828    }
1829
1830    void LZ4ParallelByteStreamDecompressionKernel::handleMatchCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *matchOffset,
1831                                                 llvm::Value *matchLength, llvm::Value* outputPos) {
1832        unsigned fw = 64;
1833        Type* INT_FW_PTR = b->getIntNTy(fw)->getPointerTo();
1834
1835        BasicBlock* entryBlock = b->GetInsertBlock();
1836
1837        Value* outputBufferSize = b->getCapacity("outputStream");
1838
1839        Value* copyToPtr = b->getRawOutputPointer("outputStream", b->CreateURem(outputPos, outputBufferSize));
1840        Value* copyFromPtr = b->getRawOutputPointer("outputStream", b->CreateURem(b->CreateSub(outputPos, matchOffset), outputBufferSize));
1841
1842        BasicBlock* matchCopyCon = b->CreateBasicBlock("matchCopyCon");
1843        BasicBlock* matchCopyBody = b->CreateBasicBlock("matchCopyBody");
1844        BasicBlock* matchCopyExit = b->CreateBasicBlock("matchCopyExit");
1845
1846        b->CreateBr(matchCopyCon);
1847
1848        // ---- matchCopyCon
1849        b->SetInsertPoint(matchCopyCon);
1850        PHINode* phiFromPtr = b->CreatePHI(b->getInt8PtrTy(), 2);
1851        phiFromPtr->addIncoming(copyFromPtr, entryBlock);
1852        PHINode* phiToPtr = b->CreatePHI(b->getInt8PtrTy(), 2);
1853        phiToPtr->addIncoming(copyToPtr, entryBlock);
1854        PHINode* phiCopiedSize = b->CreatePHI(b->getSizeTy(), 2);
1855        phiCopiedSize->addIncoming(b->getSize(0), entryBlock);
1856
1857        b->CreateCondBr(b->CreateICmpULT(phiCopiedSize, matchLength), matchCopyBody, matchCopyExit);
1858
1859        // ---- matchCopyBody
1860        b->SetInsertPoint(matchCopyBody);
1861        b->CreateStore(
1862                b->CreateLoad(b->CreatePointerCast(phiFromPtr, INT_FW_PTR)),
1863                b->CreatePointerCast(phiToPtr, INT_FW_PTR)
1864        );
1865
1866        Value* copySize = b->CreateUMin(matchOffset, b->getSize(fw / 8));
1867        phiFromPtr->addIncoming(b->CreateGEP(phiFromPtr, copySize), b->GetInsertBlock());
1868        phiToPtr->addIncoming(b->CreateGEP(phiToPtr, copySize), b->GetInsertBlock());
1869        phiCopiedSize->addIncoming(b->CreateAdd(phiCopiedSize, copySize), b->GetInsertBlock());
1870        b->CreateBr(matchCopyCon);
1871
1872        // ---- matchCopyExit
1873        b->SetInsertPoint(matchCopyExit);
1874        b->setScalarField("outputPos", b->CreateAdd(outputPos, matchLength));
1875    }
1876
1877    llvm::Value* LZ4ParallelByteStreamDecompressionKernel::simdFetchData(const std::unique_ptr<KernelBuilder> &b, llvm::Value* basePtr, llvm::Value* offsetVec, llvm::Value* mask) {
1878//        return this->simdFetchDataByLoop(b, basePtr, offsetVec, mask);
1879        if (AVX2_available() && mEnableGather) {
1880            return this->simdFetchI32DataByGather(b, basePtr, offsetVec, mask);
1881        } else {
1882            return this->simdFetchDataByLoop(b, basePtr, offsetVec, mask);
1883        }
1884    }
1885
1886
1887
1888    llvm::Value* LZ4ParallelByteStreamDecompressionKernel::simdFetchByteData(const std::unique_ptr<KernelBuilder> &b, llvm::Value* basePtr, llvm::Value* offsetVec, llvm::Value* mask) {
1889        if (AVX2_available() && mEnableGather) {
1890            return b->simd_and(this->simdFetchI32DataByGather(b, basePtr, offsetVec, mask), b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0xff)));
1891        } else {
1892            return this->simdFetchDataByLoop(b, basePtr, offsetVec, mask, 8);
1893        }
1894    }
1895
1896    llvm::Value* LZ4ParallelByteStreamDecompressionKernel::simdFetchI32DataByGather(const std::unique_ptr<KernelBuilder> &b,
1897                                                                          llvm::Value *basePtr, llvm::Value *offsetVec,
1898                                                                          llvm::Value *mask) {
1899
1900        Function *gatherFunc2 = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx2_gather_d_d);
1901        Function *gatherFunc3 = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx2_gather_d_d_256);
1902
1903        Function *gatherFunc = AVX512BW_available() ? gatherFunc3 : gatherFunc2;
1904
1905        Type* i32BitBlockTy = VectorType::get(b->getInt32Ty(), b->getBitBlockWidth() / SIMD_WIDTH);
1906
1907
1908        Value* tokenValuesVec =  b->CreateCall(
1909                gatherFunc,
1910                {
1911                        UndefValue::get(i32BitBlockTy),
1912                        basePtr,
1913                        b->CreateTrunc(offsetVec, i32BitBlockTy),
1914                        b->CreateTrunc(mask, i32BitBlockTy),
1915                        b->getInt8(1)
1916                }
1917        );
1918        tokenValuesVec = b->CreateZExt(tokenValuesVec, b->getBitBlockType());
1919        tokenValuesVec = b->CreateAnd(tokenValuesVec, mask);
1920
1921        return tokenValuesVec;
1922    }
1923
1924    llvm::Value* LZ4ParallelByteStreamDecompressionKernel::simdFetchI64DataByGather(const std::unique_ptr<KernelBuilder> &b,
1925                                                                          llvm::Value *basePtr, llvm::Value *offsetVec,
1926                                                                          llvm::Value *mask) {
1927        Type* i32BitBlockTy = VectorType::get(b->getInt32Ty(), b->getBitBlockWidth() / SIMD_WIDTH);
1928        if (AVX512BW_available()) {
1929            // AVX512 gather use i8 mask
1930            //declare <8 x int> @llvm.x86.avx512.gather.dpq.512(<8 x i64>, i8*, <8 x i32>, i8, i32) #1
1931            Function *gatherFunc512 = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx512_gather_dpq_512);
1932            return b->CreateCall(
1933                    gatherFunc512,
1934                    {
1935                            UndefValue::get(b->getBitBlockType()),
1936                            basePtr,
1937                            b->CreateTrunc(offsetVec, i32BitBlockTy),
1938                            b->CreateTruncOrBitCast(b->hsimd_signmask(SIMD_WIDTH, mask), b->getInt8Ty()),
1939                            b->getInt32(1)
1940                    });
1941            // return result & i512Mask ?
1942        } else {
1943            // AVX2 gather use i256 mask
1944            Function *gatherFunc = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx2_gather_d_q_256);
1945            Value* tokenValuesVec =  b->CreateCall(
1946                    gatherFunc,
1947                    {
1948                            UndefValue::get(b->getBitBlockType()),
1949                            basePtr,
1950                            b->CreateTrunc(offsetVec, VectorType::get(b->getInt32Ty(), 4)),
1951                            mask,
1952                            b->getInt8(1)
1953                    }
1954            );
1955            tokenValuesVec = b->CreateAnd(tokenValuesVec, mask);
1956            return tokenValuesVec;
1957        }
1958    }
1959
1960    llvm::Value* LZ4ParallelByteStreamDecompressionKernel::simdFetchDataByLoop(const std::unique_ptr<KernelBuilder> &b,
1961                                                                     llvm::Value *basePtr, llvm::Value *offsetVec,
1962                                                                     llvm::Value *maskVec, unsigned resultBitWidth) {
1963        Type* INT_TY = b->getIntNTy(resultBitWidth);
1964        Type* INT_PTR_TY = INT_TY->getPointerTo();
1965
1966        Value* placeHolderPtr = b->CreatePointerCast(b->getScalarFieldPtr("placeholder"), INT_PTR_TY);
1967        Value* retVec = ConstantVector::getNullValue(b->getBitBlockType());
1968
1969        for (uint64_t i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++){
1970            Value* mask = b->CreateExtractElement(maskVec, i);
1971            Value* shouldLoad = b->CreateICmpNE(mask, b->getInt64(0));
1972            Value* loadPtr = b->CreateSelect(shouldLoad, b->CreatePointerCast(b->CreateGEP(basePtr, b->CreateExtractElement(offsetVec, i)), INT_PTR_TY), placeHolderPtr);
1973//            Value* loadPtr = b->CreateGEP(basePtr, b->CreateExtractElement(offsetVec, i));
1974            Value* loadValue = b->CreateZExt(b->CreateLoad(loadPtr), b->getInt64Ty());
1975            Value* finalValue = b->CreateSelect(shouldLoad, loadValue, b->getInt64(0));
1976            retVec = b->CreateInsertElement(retVec, finalValue, i);
1977        }
1978
1979        return retVec;
1980    }
1981
1982    void LZ4ParallelByteStreamDecompressionKernel::simdPutData(const std::unique_ptr<KernelBuilder> &b, llvm::Value* basePtr, llvm::Value* offsetVec,llvm::Value* values, llvm::Value* mask) {
1983        if (AVX512BW_available()) {
1984            this->simdPutDataByScatter(b, basePtr, offsetVec, values, mask);
1985        } else {
1986            this->simdPutDataByLoop(b, basePtr, offsetVec, values, mask);
1987        }
1988
1989
1990    }
1991
1992    void LZ4ParallelByteStreamDecompressionKernel::simdPutDataByLoop(const std::unique_ptr<KernelBuilder> &b, llvm::Value* basePtr, llvm::Value* offsetVec,llvm::Value* values, llvm::Value* mask) {
1993
1994        Value* shouldStoreVec = b->CreateICmpNE(mask, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0)));
1995
1996        for (unsigned i = 0 ; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
1997            BasicBlock* conBlock = b->CreateBasicBlock("simdPutDataByLoopCon");
1998            BasicBlock* bodyBlock = b->CreateBasicBlock("simdPutDataByLoopBody");
1999            BasicBlock* exitBlock = b->CreateBasicBlock("simdPutDataByLoopExit");
2000
2001            b->CreateBr(conBlock);
2002
2003            // ---- ConBlock
2004            b->SetInsertPoint(conBlock);
2005            Value* shouldStore = b->CreateExtractElement(shouldStoreVec, i);
2006            b->CreateCondBr(shouldStore, bodyBlock, exitBlock);
2007
2008            // ---- BodyBlock
2009            b->SetInsertPoint(bodyBlock);
2010            b->CreateStore(
2011                    b->CreateExtractElement(values, i),
2012                    b->CreatePointerCast(b->CreateGEP(basePtr, b->CreateExtractElement(offsetVec, i)), b->getIntNTy(SIMD_WIDTH)->getPointerTo())
2013            );
2014
2015            b->CreateBr(exitBlock);
2016
2017            // ---- ExitBlock
2018            b->SetInsertPoint(exitBlock);
2019
2020        }
2021    }
2022    void LZ4ParallelByteStreamDecompressionKernel::simdPutDataByScatter(const std::unique_ptr<KernelBuilder> &b, llvm::Value* basePtr, llvm::Value* offsetVec,llvm::Value* values, llvm::Value* mask) {
2023        Function *scatterFunc = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx512_scatter_dpq_512);
2024        //declare void @llvm.x86.avx512.scatter.dpq.512(i8*, i8, <8 x i32>, <8 x i64>, i32)
2025
2026        Value* i8Mask = b->CreateTruncOrBitCast(b->hsimd_signmask(SIMD_WIDTH, mask), b->getIntNTy(b->getBitBlockWidth() / SIMD_WIDTH));
2027
2028        b->CreateCall(scatterFunc, {
2029                basePtr,
2030                i8Mask,
2031                b->CreateTrunc(offsetVec, VectorType::get(b->getInt32Ty(), b->getBitBlockWidth() / SIMD_WIDTH)),
2032                values,
2033                b->getInt32(1)
2034        });
2035
2036    }
2037
2038
2039    void LZ4ParallelByteStreamDecompressionKernel::initParallelLevelMeasurement(const std::unique_ptr<KernelBuilder> &b) {
2040        for (unsigned i = 0; i <= b->getBitBlockWidth() / SIMD_WIDTH; i++) {
2041            addScalar(b->getSizeTy(), "ParallelLevel" + std::to_string(i));
2042        }
2043    }
2044    void LZ4ParallelByteStreamDecompressionKernel::recordParallelLevel(const std::unique_ptr<KernelBuilder> &b, llvm::Value* v) {
2045        for (unsigned i = 0; i <= b->getBitBlockWidth() / SIMD_WIDTH; i++) {
2046            auto name = "ParallelLevel" + std::to_string(i);
2047            Value* addValue = b->CreateZExt(b->CreateICmpEQ(v, b->getInt32(i)), b->getSizeTy());
2048            b->setScalarField(name, b->CreateAdd(b->getScalarField(name), addValue));
2049        }
2050    }
2051    void LZ4ParallelByteStreamDecompressionKernel::printParallelLevelResult(const std::unique_ptr<KernelBuilder> &b) {
2052        for (unsigned i = 0; i <= b->getBitBlockWidth() / SIMD_WIDTH; i++) {
2053            auto name = "ParallelLevel" + std::to_string(i);
2054            b->CallPrintInt(name, b->getScalarField(name));
2055        }
2056    }
2057
2058}
Note: See TracBrowser for help on using the repository browser.