source: icGREP/icgrep-devel/icgrep/kernels/lz4/aio/lz4_parallel_bytestream_aio.cpp @ 6132

Last change on this file since 6132 was 6111, checked in by xwa163, 9 months ago
  1. Cleanup LZ4 AIO related kernels
  2. Improve LZ4ParallelByteStreamAIOKernel
  3. Implement simd_cttz
File size: 104.1 KB
Line 
1
2#include "lz4_parallel_bytestream_aio.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    LZ4ParallelByteStreamAioKernel::LZ4ParallelByteStreamAioKernel(const std::unique_ptr<kernel::KernelBuilder> &b, unsigned lz4BlockSize, bool enableGather, bool enableScatter, int minParallelLevel)
22            :SegmentOrientedKernel("LZ4ParallelByteStreamAioKernel",
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 LZ4ParallelByteStreamAioKernel::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* LZ4ParallelByteStreamAioKernel::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 LZ4ParallelByteStreamAioKernel::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*> LZ4ParallelByteStreamAioKernel::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*> LZ4ParallelByteStreamAioKernel::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*> LZ4ParallelByteStreamAioKernel::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*> LZ4ParallelByteStreamAioKernel::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*> LZ4ParallelByteStreamAioKernel::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*> LZ4ParallelByteStreamAioKernel::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*> LZ4ParallelByteStreamAioKernel::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*> LZ4ParallelByteStreamAioKernel::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*> LZ4ParallelByteStreamAioKernel::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 *> LZ4ParallelByteStreamAioKernel::simdProcessBlockBoundary(
657            const std::unique_ptr<KernelBuilder> &b, Value *tokenPosVec, Value *lz4BlockEndVec, Value* initOutputPosVec
658    ) {
659        // ---- EntryBlock
660        BasicBlock* entryBlock = b->GetInsertBlock();
661        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
662
663        Value* notFinishMask = b->simd_ult(SIMD_WIDTH, tokenPosVec, lz4BlockEndVec);
664
665        Value* byteRawInputPtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
666
667        Value* tokenValuesVec = this->simdFetchByteData(b, byteRawInputPtr, tokenPosVec, notFinishMask);
668
669        Value *literalStartPosVec = nullptr, *literalLengthVec = nullptr;
670
671
672//        std::tie(literalStartPosVec, literalLengthVec) = this->simdParseLiteralInfo(b, tokenPosVec, tokenValuesVec, notFinishMask);
673        std::tie(literalStartPosVec, literalLengthVec) = this->simdParseLiteralInfo2(b, tokenPosVec, tokenValuesVec, notFinishMask);
674
675        Value* literalEndPosVec = b->simd_add(SIMD_WIDTH, literalStartPosVec, literalLengthVec);
676
677
678        this->handleSimdLiteralCopy(b, literalStartPosVec, literalLengthVec, initOutputPosVec);
679
680
681        Value* outputPosAfterLiteralCpy = b->simd_add(SIMD_WIDTH, initOutputPosVec, literalLengthVec);
682
683
684        Value* matchOffsetBeginPosVec = literalEndPosVec;
685
686        Value* matchOffsetNextPosVec = b->simd_add(SIMD_WIDTH, matchOffsetBeginPosVec, BIT_BLOCK_1);
687
688
689        BasicBlock* hasMatchPartBlock = b->CreateBasicBlock("hasMatchPartBlock");
690
691
692        BasicBlock* extendLiteralEndFinal = b->GetInsertBlock();
693
694        Value* hasMatchPartMask = b->simd_ult(SIMD_WIDTH, matchOffsetBeginPosVec, lz4BlockEndVec);
695        b->CreateLikelyCondBr(b->CreateICmpNE(b->CreateBitCast(hasMatchPartMask, INT_BIT_BLOCK_TY), INT_BIT_BLOCK_TY_0), hasMatchPartBlock, exitBlock);
696
697        // ---- hasMatchPartBlock
698        b->SetInsertPoint(hasMatchPartBlock);
699
700        Value *matchLength = nullptr, *extendMatchEndPos = nullptr;
701
702//        std::tie(extendMatchEndPos, matchLength) = this->simdParseMatchInfo(b, matchOffsetBeginPosVec, tokenValuesVec, hasMatchPartMask);
703        std::tie(extendMatchEndPos, matchLength) = this->simdParseMatchInfo2(b, matchOffsetBeginPosVec, tokenValuesVec, hasMatchPartMask);
704
705        Value* matchOffsetVec = this->simdFetchData(
706                b,
707                byteRawInputPtr,
708                matchOffsetBeginPosVec,
709                hasMatchPartMask
710        );
711        matchOffsetVec = b->simd_and(matchOffsetVec, BIT_BLOCK_FFFF);
712
713//        Value* t1 = b->CreateReadCycleCounter();
714        this->handleSimdMatchCopy(b, matchOffsetVec, matchLength, outputPosAfterLiteralCpy);
715//        Value* t2 = b->CreateReadCycleCounter();
716//        b->setScalarField("tempTimes", b->CreateAdd(b->getScalarField("tempTimes"), b->CreateSub(t2 ,t1)));
717
718        Value* outputPosAfterMatchCpy = b->simd_add(SIMD_WIDTH, outputPosAfterLiteralCpy, matchLength);
719
720        BasicBlock* extendMatchExitFinal = b->GetInsertBlock();
721
722        b->CreateBr(exitBlock);
723        // ---- exitBlock
724
725        b->SetInsertPoint(exitBlock);
726
727        PHINode* phiBeforeTokenPos = b->CreatePHI(matchOffsetNextPosVec->getType(), 2);
728        phiBeforeTokenPos->addIncoming(matchOffsetNextPosVec, extendLiteralEndFinal);
729        phiBeforeTokenPos->addIncoming(extendMatchEndPos, extendMatchExitFinal);
730
731        PHINode* phiNewOutputPos = b->CreatePHI(outputPosAfterLiteralCpy->getType(), 2);
732        phiNewOutputPos->addIncoming(outputPosAfterLiteralCpy, extendLiteralEndFinal);
733        phiNewOutputPos->addIncoming(outputPosAfterMatchCpy, extendMatchExitFinal);
734        Value* nextTokenPos = b->simd_add(SIMD_WIDTH, phiBeforeTokenPos, BIT_BLOCK_1);
735        return std::make_pair(nextTokenPos, phiNewOutputPos);
736    }
737
738    void LZ4ParallelByteStreamAioKernel::generateSimdDecompression1(const std::unique_ptr<KernelBuilder> &b, Value* blockDataIndex) {
739        BasicBlock* entryBlock = b->GetInsertBlock();
740        BasicBlock* exitBlock = b->CreateBasicBlock("simdDecompressionExitBlock");
741        BasicBlock* processCon = b->CreateBasicBlock("simdDecompressionProcessConBlock");
742        BasicBlock* processBody = b->CreateBasicBlock("simdDecompressionProcessBodyBlock");
743        BasicBlock* sequentialProcessBlock = b->CreateBasicBlock("simdDecompressionSequentialProcessBlock");
744
745
746        // ---- entryBlock
747        Value* blockStartVec = this->generateLoadSimdInt64NumberInput(b, "blockStart", blockDataIndex);
748        Value* blockEndVec = this->generateLoadSimdInt64NumberInput(b, "blockEnd", blockDataIndex);
749
750        Value* outputPos = b->getProducedItemCount("outputStream");
751        Value* initOutputPosVec = b->simd_fill(SIMD_WIDTH, outputPos);
752        std::vector<Constant*> initOutputOffset;
753        for (unsigned i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
754            initOutputOffset.push_back(b->getIntN(SIMD_WIDTH, i * mLz4BlockSize));
755        }
756
757        initOutputPosVec = b->simd_add(SIMD_WIDTH, initOutputPosVec, ConstantVector::get(initOutputOffset));
758
759        // TODO handle uncompression blocks
760
761        b->CreateBr(processCon);
762
763        // ---- processCon
764        b->SetInsertPoint(processCon);
765        PHINode* phiCursorVec = b->CreatePHI(blockStartVec->getType(), 3);
766        phiCursorVec->addIncoming(blockStartVec, entryBlock);
767
768        PHINode* phiOutputPosVec = b->CreatePHI(initOutputPosVec->getType(), 3);
769        phiOutputPosVec->addIncoming(initOutputPosVec, entryBlock);
770
771
772        Value* hasRemaining = b->simd_ult(SIMD_WIDTH, phiCursorVec, blockEndVec);
773        Value* signMask = b->hsimd_signmask(SIMD_WIDTH, hasRemaining);
774        Value* maskPopcount = b->CreatePopcount(signMask);
775        Value* shouldSimdProcess = b->CreateICmpUGE(maskPopcount, b->getInt32(mMininumParallelLevel));
776
777        hasRemaining = b->CreateICmpNE(b->CreateBitCast(hasRemaining, b->getIntNTy(b->getBitBlockWidth())), Constant::getNullValue(b->getIntNTy(b->getBitBlockWidth())));
778
779        b->CreateLikelyCondBr(shouldSimdProcess, processBody, sequentialProcessBlock);
780
781        // ---- processBody
782        b->SetInsertPoint(processBody);
783
784        Value* notFinishMask = b->simd_ult(SIMD_WIDTH, phiCursorVec, blockEndVec);
785        Value* byteRawInputPtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
786        Value* tokenValuesVec = this->simdFetchByteData(b, byteRawInputPtr, phiCursorVec, notFinishMask);
787
788        Value* literalN = b->CreatePopcount(b->hsimd_signmask(SIMD_WIDTH, b->simd_eq(SIMD_WIDTH, b->simd_and(tokenValuesVec, BIT_BLOCK_F0), BIT_BLOCK_F0)));
789        Value* matchN = b->CreatePopcount(b->hsimd_signmask(SIMD_WIDTH, b->simd_eq(SIMD_WIDTH, b->simd_and(tokenValuesVec, BIT_BLOCK_0F), BIT_BLOCK_0F)));
790
791//        Value* shouldSimdProcess2 = b->CreateAnd(
792//                b->CreateOr(b->CreateICmpEQ(literalN, b->getInt32(0)), b->CreateICmpUGE(literalN, b->getInt32(mMininumParallelLevel))),
793//                b->CreateOr(b->CreateICmpEQ(matchN, b->getInt32(0)), b->CreateICmpUGE(matchN, b->getInt32(mMininumParallelLevel)))
794//        );
795
796        Value* shouldSimdProcess2 = b->CreateAnd(b->CreateICmpEQ(literalN, b->getInt32(0)), b->CreateICmpUGE(matchN, b->getInt32(mMininumParallelLevel)));
797
798        BasicBlock* loopProcessBody = b->CreateBasicBlock("loopProcessBody");
799        BasicBlock* simdProcessBody = b->CreateBasicBlock("simdProcessBody");
800
801
802        b->CreateCondBr(shouldSimdProcess2, simdProcessBody, loopProcessBody);
803
804        // ---- simdProcessBody
805        {
806            b->SetInsertPoint(simdProcessBody);
807            Value *newCursorVec = nullptr, *newOutputPosVec = nullptr;
808//            std::tie(newCursorVec, newOutputPosVec) = this->simdProcessBlockBoundary(b, phiCursorVec, blockEndVec, phiOutputPosVec);
809            std::tie(newCursorVec, newOutputPosVec) = this->simdProcessBlockBoundaryByLoop(b, phiCursorVec, blockEndVec, phiOutputPosVec);
810
811            phiCursorVec->addIncoming(newCursorVec, b->GetInsertBlock());
812            phiOutputPosVec->addIncoming(newOutputPosVec, b->GetInsertBlock());
813
814            b->CreateBr(processCon);
815        }
816
817        // ---- loopProcessBody
818        {
819            b->SetInsertPoint(loopProcessBody);
820            Value *newCursorVec = nullptr, *newOutputPosVec = nullptr;
821            std::tie(newCursorVec, newOutputPosVec) = this->simdProcessBlockBoundaryByLoop(b, phiCursorVec, blockEndVec, phiOutputPosVec);
822
823            phiCursorVec->addIncoming(newCursorVec, b->GetInsertBlock());
824            phiOutputPosVec->addIncoming(newOutputPosVec, b->GetInsertBlock());
825
826            b->CreateBr(processCon);
827        }
828
829
830        // ---- sequentialProcessBlock
831        b->SetInsertPoint(sequentialProcessBlock);
832
833        for (unsigned i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
834
835            BasicBlock* conBlock = b->CreateBasicBlock("conBlock");
836            BasicBlock* bodyBlock = b->CreateBasicBlock("bodyBlock");
837            BasicBlock* innerExitBlock = b->CreateBasicBlock("exitBlock");
838
839            b->CreateBr(conBlock);
840
841            // ---- conBlock
842            b->SetInsertPoint(conBlock);
843            Value* shouldProcessSequentially = b->CreateICmpNE(b->CreateAnd(b->CreateLShr(signMask, b->getInt32(i)), b->getInt32(1)), b->getInt32(0));
844            Value* originalOutputPos = b->CreateExtractElement(phiOutputPosVec, i);
845
846            b->CreateCondBr(shouldProcessSequentially, bodyBlock, innerExitBlock);
847
848            // ---- bodyBlock
849            b->SetInsertPoint(bodyBlock);
850
851            // TODO need to handle blockEnd here when doing overwriting memcpy
852            Value* newOutputPos = this->generateProcessCompressedBlock(
853                    b,
854                    b->CreateExtractElement(phiCursorVec, i),
855                    b->CreateExtractElement(blockEndVec, i),
856                    originalOutputPos
857            );
858
859            if (i == b->getBitBlockWidth() / SIMD_WIDTH - 1) {
860                b->setProducedItemCount("outputStream", newOutputPos);
861            }
862
863            b->CreateBr(innerExitBlock);
864
865            // ---- exitBlock
866            b->SetInsertPoint(innerExitBlock);
867        }
868
869
870        b->CreateBr(exitBlock);
871
872        // ---- exitBlock
873        b->SetInsertPoint(exitBlock);
874
875        uint64_t lastVecIndex = b->getBitBlockWidth() / SIMD_WIDTH - 1;
876        Value* lastBlockEnd = b->CreateExtractElement(blockEndVec, lastVecIndex);
877        b->setProcessedItemCount("byteStream", lastBlockEnd);
878        Value* lastOutputPos = b->CreateExtractElement(phiOutputPosVec, lastVecIndex);
879        b->setProducedItemCount("outputStream", b->CreateUMax(b->getProducedItemCount("outputStream"), lastOutputPos));
880//        b->CallPrintInt("produced", b->getProducedItemCount("outputStream"));
881
882    }
883
884    void LZ4ParallelByteStreamAioKernel::generateSimdDecompression2(const std::unique_ptr<KernelBuilder> &b, llvm::Value* blockDataIndex) {
885        BasicBlock* entryBlock = b->GetInsertBlock();
886        BasicBlock* exitBlock = b->CreateBasicBlock("simdDecompressionExitBlock");
887        BasicBlock* processCon = b->CreateBasicBlock("simdDecompressionProcessConBlock");
888        BasicBlock* processBody = b->CreateBasicBlock("simdDecompressionProcessBodyBlock");
889        BasicBlock* sequentialProcessBlock = b->CreateBasicBlock("simdDecompressionSequentialProcessBlock");
890
891        // ---- entryBlock
892        Value* blockStartVec = this->generateLoadSimdInt64NumberInput(b, "blockStart", blockDataIndex);
893        Value* blockEndVec = this->generateLoadSimdInt64NumberInput(b, "blockEnd", blockDataIndex);
894
895        Value* outputPos = b->getProducedItemCount("outputStream");
896        Value* initOutputPosVec = b->simd_fill(SIMD_WIDTH, outputPos);
897        std::vector<Constant*> initOutputOffset;
898        for (unsigned i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
899            initOutputOffset.push_back(b->getIntN(SIMD_WIDTH, i * 4 * 1024 * 1024));
900        }
901
902        initOutputPosVec = b->simd_add(SIMD_WIDTH, initOutputPosVec, ConstantVector::get(initOutputOffset));
903
904        // TODO handle uncompression blocks
905
906        b->CreateBr(processCon);
907
908        // ---- processCon
909        b->SetInsertPoint(processCon);
910        PHINode* phiCursorVec = b->CreatePHI(blockStartVec->getType(), 2);
911        phiCursorVec->addIncoming(blockStartVec, entryBlock);
912
913        PHINode* phiOutputPosVec = b->CreatePHI(initOutputPosVec->getType(), 2);
914        phiOutputPosVec->addIncoming(initOutputPosVec, entryBlock);
915
916        Value* hasRemaining = b->simd_ult(SIMD_WIDTH, phiCursorVec, blockEndVec);
917        Value* signMask = b->hsimd_signmask(SIMD_WIDTH, hasRemaining);
918        Value* maskPopcount = b->CreatePopcount(signMask);
919        Value* shouldSimdProcess = b->CreateICmpUGE(maskPopcount, b->getInt32(mMininumParallelLevel));
920        b->CreateLikelyCondBr(shouldSimdProcess, processBody, sequentialProcessBlock);
921
922        // ---- processBody
923        b->SetInsertPoint(processBody);
924//        Value* newCursorVec = this->generateSimdAcceleration(b, phiCursorVec, blockEndVec);
925
926        Value *newCursorVec = nullptr, *newOutputPosVec = nullptr;
927        std::tie(newCursorVec, newOutputPosVec) = this->simdProcessBlockBoundary(b, phiCursorVec, blockEndVec, phiOutputPosVec);
928//        std::tie(newCursorVec, newOutputPosVec) = this->simdProcessBlockBoundaryByLoop(b, phiCursorVec, blockEndVec, phiOutputPosVec);
929
930        phiCursorVec->addIncoming(newCursorVec, b->GetInsertBlock());
931        phiOutputPosVec->addIncoming(newOutputPosVec, b->GetInsertBlock());
932
933        b->CreateBr(processCon);
934
935        // ---- sequentialProcessBlock
936        b->SetInsertPoint(sequentialProcessBlock);
937
938        for (unsigned i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
939
940            BasicBlock* conBlock = b->CreateBasicBlock("conBlock");
941            BasicBlock* bodyBlock = b->CreateBasicBlock("bodyBlock");
942            BasicBlock* innerExitBlock = b->CreateBasicBlock("exitBlock");
943
944            b->CreateBr(conBlock);
945
946            // ---- conBlock
947            b->SetInsertPoint(conBlock);
948            Value* shouldProcessSequentially = b->CreateICmpNE(b->CreateAnd(b->CreateLShr(signMask, b->getInt32(i)), b->getInt32(1)), b->getInt32(0));
949            Value* originalOutputPos = b->CreateExtractElement(phiOutputPosVec, i);
950
951            b->CreateCondBr(shouldProcessSequentially, bodyBlock, innerExitBlock);
952
953            // ---- bodyBlock
954            b->SetInsertPoint(bodyBlock);
955
956            // TODO need to handle blockEnd here when doing overwriting memcpy
957            Value* newOutputPos = this->generateProcessCompressedBlock(
958                    b,
959                    b->CreateExtractElement(phiCursorVec, i),
960                    b->CreateExtractElement(blockEndVec, i),
961                    originalOutputPos
962            );
963
964            if (i == b->getBitBlockWidth() / SIMD_WIDTH - 1) {
965                b->setProducedItemCount("outputStream", newOutputPos);
966            }
967
968            b->CreateBr(innerExitBlock);
969
970            // ---- exitBlock
971            b->SetInsertPoint(innerExitBlock);
972        }
973
974
975        b->CreateBr(exitBlock);
976
977        // ---- exitBlock
978        b->SetInsertPoint(exitBlock);
979
980        uint64_t lastVecIndex = b->getBitBlockWidth() / SIMD_WIDTH - 1;
981        Value* lastBlockEnd = b->CreateExtractElement(blockEndVec, lastVecIndex);
982        b->setProcessedItemCount("byteStream", lastBlockEnd);
983        Value* lastOutputPos = b->CreateExtractElement(phiOutputPosVec, lastVecIndex);
984        b->setProducedItemCount("outputStream", b->CreateUMax(b->getProducedItemCount("outputStream"), lastOutputPos));
985//        b->CallPrintInt("produced", b->getProducedItemCount("outputStream"));
986    }
987
988
989    void LZ4ParallelByteStreamAioKernel::generateSimdDecompression(const std::unique_ptr<KernelBuilder> &b, Value* blockDataIndex) {
990        BasicBlock* entryBlock = b->GetInsertBlock();
991        BasicBlock* exitBlock = b->CreateBasicBlock("simdDecompressionExitBlock");
992        BasicBlock* processCon = b->CreateBasicBlock("simdDecompressionProcessConBlock");
993        BasicBlock* processBody = b->CreateBasicBlock("simdDecompressionProcessBodyBlock");
994        BasicBlock* sequentialProcessBlock = b->CreateBasicBlock("simdDecompressionSequentialProcessBlock");
995
996
997        // ---- entryBlock
998        Value* blockStartVec = this->generateLoadSimdInt64NumberInput(b, "blockStart", blockDataIndex);
999        Value* blockEndVec = this->generateLoadSimdInt64NumberInput(b, "blockEnd", blockDataIndex);
1000
1001        Value* outputPos = b->getProducedItemCount("outputStream");
1002        Value* initOutputPosVec = b->simd_fill(SIMD_WIDTH, outputPos);
1003        std::vector<Constant*> initOutputOffset;
1004        for (unsigned i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
1005            initOutputOffset.push_back(b->getIntN(SIMD_WIDTH, i * 4 * 1024 * 1024));
1006        }
1007
1008        initOutputPosVec = b->simd_add(SIMD_WIDTH, initOutputPosVec, ConstantVector::get(initOutputOffset));
1009
1010        // TODO handle uncompression blocks
1011
1012        b->CreateBr(processCon);
1013
1014        // ---- processCon
1015        b->SetInsertPoint(processCon);
1016        PHINode* phiCursorVec = b->CreatePHI(blockStartVec->getType(), 2);
1017        phiCursorVec->addIncoming(blockStartVec, entryBlock);
1018
1019        PHINode* phiOutputPosVec = b->CreatePHI(initOutputPosVec->getType(), 2);
1020        phiOutputPosVec->addIncoming(initOutputPosVec, entryBlock);
1021
1022
1023        Value* hasRemaining = b->simd_ult(SIMD_WIDTH, phiCursorVec, blockEndVec);
1024        Value* signMask = b->hsimd_signmask(SIMD_WIDTH, hasRemaining);
1025        Value* maskPopcount = b->CreatePopcount(signMask);
1026
1027
1028        hasRemaining = b->CreateICmpNE(b->CreateBitCast(hasRemaining, b->getIntNTy(b->getBitBlockWidth())), Constant::getNullValue(b->getIntNTy(b->getBitBlockWidth())));
1029
1030        Value* notFinishMask = b->simd_ult(SIMD_WIDTH, phiCursorVec, blockEndVec);
1031        Value* byteRawInputPtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
1032        Value* tokenValuesVec = this->simdFetchByteData(b, byteRawInputPtr, phiCursorVec, notFinishMask);
1033
1034        Value* literalN = b->CreatePopcount(b->hsimd_signmask(SIMD_WIDTH, b->simd_eq(SIMD_WIDTH, b->simd_and(tokenValuesVec, BIT_BLOCK_F0), BIT_BLOCK_F0)));
1035        Value* matchN = b->CreatePopcount(b->hsimd_signmask(SIMD_WIDTH, b->simd_eq(SIMD_WIDTH, b->simd_and(tokenValuesVec, BIT_BLOCK_0F), BIT_BLOCK_0F)));
1036
1037        Value* shouldSimdProcess = b->CreateAnd(
1038                b->CreateOr(b->CreateICmpEQ(literalN, b->getInt32(0)), b->CreateICmpUGE(literalN, b->getInt32(mMininumParallelLevel))),
1039                b->CreateOr(b->CreateICmpEQ(matchN, b->getInt32(0)), b->CreateICmpUGE(matchN, b->getInt32(mMininumParallelLevel)))
1040        );
1041        this->recordParallelLevel(b, b->CreateZExt(shouldSimdProcess, b->getInt32Ty()));
1042//        shouldSimdProcess = b->getInt1(false);
1043
1044
1045        b->CreateLikelyCondBr(shouldSimdProcess, processBody, sequentialProcessBlock);
1046
1047        // ---- processBody
1048        b->SetInsertPoint(processBody);
1049//        Value* newCursorVec = this->generateSimdAcceleration(b, phiCursorVec, blockEndVec);
1050
1051        Value *newCursorVec = nullptr, *newOutputPosVec = nullptr;
1052        std::tie(newCursorVec, newOutputPosVec) = this->simdProcessBlockBoundary(b, phiCursorVec, blockEndVec, phiOutputPosVec);
1053
1054        phiCursorVec->addIncoming(newCursorVec, b->GetInsertBlock());
1055        phiOutputPosVec->addIncoming(newOutputPosVec, b->GetInsertBlock());
1056
1057        b->CreateBr(processCon);
1058
1059        // ---- sequentialProcessBlock
1060        b->SetInsertPoint(sequentialProcessBlock);
1061
1062        for (unsigned i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
1063
1064            BasicBlock* conBlock = b->CreateBasicBlock("conBlock");
1065            BasicBlock* bodyBlock = b->CreateBasicBlock("bodyBlock");
1066            BasicBlock* innerExitBlock = b->CreateBasicBlock("exitBlock");
1067
1068            b->CreateBr(conBlock);
1069
1070            // ---- conBlock
1071            b->SetInsertPoint(conBlock);
1072            Value* shouldProcessSequentially = b->CreateICmpNE(b->CreateAnd(b->CreateLShr(signMask, b->getInt32(i)), b->getInt32(1)), b->getInt32(0));
1073            Value* originalOutputPos = b->CreateExtractElement(phiOutputPosVec, i);
1074
1075            b->CreateCondBr(shouldProcessSequentially, bodyBlock, innerExitBlock);
1076
1077            // ---- bodyBlock
1078            b->SetInsertPoint(bodyBlock);
1079
1080            // TODO need to handle blockEnd here when doing overwriting memcpy
1081            Value* newOutputPos = this->generateProcessCompressedBlock(
1082                    b,
1083                    b->CreateExtractElement(phiCursorVec, i),
1084                    b->CreateExtractElement(blockEndVec, i),
1085                    originalOutputPos
1086            );
1087
1088            if (i == b->getBitBlockWidth() / SIMD_WIDTH - 1) {
1089                b->setProducedItemCount("outputStream", newOutputPos);
1090            }
1091
1092            b->CreateBr(innerExitBlock);
1093
1094            // ---- exitBlock
1095            b->SetInsertPoint(innerExitBlock);
1096        }
1097
1098
1099        b->CreateBr(exitBlock);
1100
1101        // ---- exitBlock
1102        b->SetInsertPoint(exitBlock);
1103
1104        uint64_t lastVecIndex = b->getBitBlockWidth() / SIMD_WIDTH - 1;
1105        Value* lastBlockEnd = b->CreateExtractElement(blockEndVec, lastVecIndex);
1106        b->setProcessedItemCount("byteStream", lastBlockEnd);
1107        Value* lastOutputPos = b->CreateExtractElement(phiOutputPosVec, lastVecIndex);
1108        b->setProducedItemCount("outputStream", b->CreateUMax(b->getProducedItemCount("outputStream"), lastOutputPos));
1109//        b->CallPrintInt("produced", b->getProducedItemCount("outputStream"));
1110    }
1111
1112
1113
1114    void LZ4ParallelByteStreamAioKernel::generateSequentialDecompression(const std::unique_ptr<KernelBuilder> &b, llvm::Value* startBlockDataIndex, llvm::Value* endBlockDataIndex) {
1115
1116        // ---- EntryBlock
1117        BasicBlock* entryBlock = b->GetInsertBlock();
1118
1119        BasicBlock* SequentialConBlock = b->CreateBasicBlock("SequentialConBlock");
1120        BasicBlock* SequentialBodyBlock = b->CreateBasicBlock("SequentialBodyBlock");
1121        BasicBlock* SequentialExitBlock = b->CreateBasicBlock("SequentialExitBlock");
1122
1123
1124        Value* initOutputPos = b->getProducedItemCount("outputStream");
1125
1126        b->CreateBr(SequentialConBlock);
1127
1128        // ---- SequentialConBlock
1129        b->SetInsertPoint(SequentialConBlock);
1130        PHINode* phiCurrentBlockDataIndex = b->CreatePHI(b->getSizeTy(), 2);
1131        phiCurrentBlockDataIndex->addIncoming(startBlockDataIndex, entryBlock);
1132        PHINode* phiOutputPos = b->CreatePHI(b->getSizeTy(), 2);
1133        phiOutputPos->addIncoming(initOutputPos, entryBlock);
1134
1135        b->CreateCondBr(b->CreateICmpULT(phiCurrentBlockDataIndex, endBlockDataIndex), SequentialBodyBlock, SequentialExitBlock);
1136
1137        // ---- SequentialBodyBlock
1138        b->SetInsertPoint(SequentialBodyBlock);
1139        Value* lz4BlockStart = this->generateLoadInt64NumberInput(b, "blockStart", phiCurrentBlockDataIndex);
1140        Value* lz4BlockEnd = this->generateLoadInt64NumberInput(b, "blockEnd", phiCurrentBlockDataIndex);
1141        Value* newOutputPos = this->generateProcessCompressedBlock(b, lz4BlockStart, lz4BlockEnd, phiOutputPos);
1142
1143        b->setProcessedItemCount("byteStream", lz4BlockEnd);
1144        b->setProducedItemCount("outputStream", newOutputPos);
1145
1146        phiCurrentBlockDataIndex->addIncoming(b->CreateAdd(phiCurrentBlockDataIndex, b->getSize(1)), b->GetInsertBlock());
1147        phiOutputPos->addIncoming(newOutputPos, b->GetInsertBlock());
1148
1149        b->CreateBr(SequentialConBlock);
1150
1151        // ---- SequentialExitBlock
1152        b->SetInsertPoint(SequentialExitBlock);
1153        b->setProcessedItemCount("isCompressed", endBlockDataIndex);
1154
1155    }
1156
1157    llvm::Value *
1158    LZ4ParallelByteStreamAioKernel::generateLoadSimdInt64NumberInput(const std::unique_ptr<KernelBuilder> &iBuilder, std::string inputBufferName,
1159                                     llvm::Value *globalOffset) {
1160        Value * capacity = iBuilder->getCapacity(inputBufferName);
1161        Value * processed = iBuilder->getProcessedItemCount(inputBufferName);
1162        processed = iBuilder->CreateAnd(processed, iBuilder->CreateNeg(capacity));
1163        Value * offset = iBuilder->CreateSub(globalOffset, processed);
1164        Value * valuePtr = iBuilder->getRawInputPointer(inputBufferName, offset);
1165        valuePtr = iBuilder->CreatePointerCast(valuePtr, iBuilder->getBitBlockType()->getPointerTo());
1166        return iBuilder->CreateLoad(valuePtr);
1167    }
1168
1169    llvm::Value *LZ4ParallelByteStreamAioKernel::generateLoadInt64NumberInput(const std::unique_ptr<KernelBuilder> &iBuilder,
1170                                                                      std::string inputBufferName, llvm::Value *globalOffset) {
1171
1172        Value * capacity = iBuilder->getCapacity(inputBufferName);
1173        Value * processed = iBuilder->getProcessedItemCount(inputBufferName);
1174        processed = iBuilder->CreateAnd(processed, iBuilder->CreateNeg(capacity));
1175        Value * offset = iBuilder->CreateSub(globalOffset, processed);
1176        Value * valuePtr = iBuilder->getRawInputPointer(inputBufferName, offset);
1177        return iBuilder->CreateLoad(valuePtr);
1178    }
1179
1180    llvm::Value*
1181    LZ4ParallelByteStreamAioKernel::generateProcessCompressedBlock(const std::unique_ptr<KernelBuilder> &b, llvm::Value *lz4BlockStart,
1182                                                           llvm::Value *lz4BlockEnd, llvm::Value* initOutputPos) {
1183        BasicBlock* entryBlock = b->GetInsertBlock();
1184
1185        Value* isTerminal = b->CreateICmpEQ(lz4BlockEnd, b->getScalarField("fileSize"));
1186        b->setTerminationSignal(isTerminal);
1187
1188        BasicBlock* exitBlock = b->CreateBasicBlock("processCompressedExitBlock");
1189
1190        BasicBlock* processCon = b->CreateBasicBlock("processCompressedConBlock");
1191        BasicBlock* processBody = b->CreateBasicBlock("processCompressedBodyBlock");
1192
1193
1194        BasicBlock* beforeProcessConBlock = b->GetInsertBlock();
1195        b->CreateBr(processCon);
1196        b->SetInsertPoint(processCon);
1197        PHINode* phiOutputPos = b->CreatePHI(initOutputPos->getType(), 2);
1198        phiOutputPos->addIncoming(initOutputPos, entryBlock);
1199        PHINode* phiCursorValue = b->CreatePHI(b->getInt64Ty(), 2); // phiCursorValue should always be the position of next token except for the final sequence
1200        phiCursorValue->addIncoming(lz4BlockStart, beforeProcessConBlock);
1201
1202        b->CreateCondBr(b->CreateICmpULT(phiCursorValue, lz4BlockEnd), processBody, exitBlock);
1203
1204        b->SetInsertPoint(processBody);
1205
1206
1207        auto ret = this->processBlockBoundary(b, phiCursorValue, lz4BlockEnd, phiOutputPos);
1208        Value* nextTokenGlobalPos = ret.first;
1209        Value* nextOutputPos = ret.second;
1210
1211        phiOutputPos->addIncoming(nextOutputPos, b->GetInsertBlock());
1212        phiCursorValue->addIncoming(nextTokenGlobalPos, b->GetInsertBlock());
1213        b->CreateBr(processCon);
1214
1215        b->SetInsertPoint(exitBlock);
1216        return phiOutputPos;
1217    }
1218
1219    pair<Value*, Value*> LZ4ParallelByteStreamAioKernel::parseLiteralInfo(const std::unique_ptr<KernelBuilder> &b, llvm::Value *tokenPos, llvm::Value* tokenValue) {
1220        BasicBlock* entryBlock = b->GetInsertBlock();
1221
1222        Value* bytePtrBase = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
1223
1224        Value* shouldExtendLiteral = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_F0), BYTE_F0);
1225        BasicBlock* extendLiteralCond = b->CreateBasicBlock("extendLiteralCond");
1226        BasicBlock* extendLiteralEnd = b->CreateBasicBlock("extendLiteralEnd");
1227
1228        Value* initExtendLiteralPos = b->CreateAdd(tokenPos, b->getSize(1));
1229
1230        b->CreateCondBr(shouldExtendLiteral, extendLiteralCond, extendLiteralEnd);
1231
1232        // ---- extendLiteralCond
1233        b->SetInsertPoint(extendLiteralCond);
1234        PHINode* phiCurrentExtendLiteralPos = b->CreatePHI(b->getSizeTy(), 2);
1235        phiCurrentExtendLiteralPos->addIncoming(initExtendLiteralPos, entryBlock);
1236        PHINode* phiExtendLiteralLength = b->CreatePHI(b->getSizeTy(), 2);
1237        phiExtendLiteralLength->addIncoming(SIZE_0, entryBlock);
1238
1239        Value* currentLiteralLengthByte = b->CreateLoad(b->CreateGEP(bytePtrBase, phiCurrentExtendLiteralPos));
1240        Value* newExtendLiteralLength = b->CreateAdd(phiExtendLiteralLength, b->CreateZExt(currentLiteralLengthByte, b->getSizeTy()));
1241
1242        phiCurrentExtendLiteralPos->addIncoming(b->CreateAdd(phiCurrentExtendLiteralPos, SIZE_1), b->GetInsertBlock());
1243        phiExtendLiteralLength->addIncoming(newExtendLiteralLength, b->GetInsertBlock());
1244
1245        b->CreateCondBr(b->CreateICmpEQ(currentLiteralLengthByte, BYTE_FF), extendLiteralCond, extendLiteralEnd);
1246
1247        // ---- extendLiteralEnd
1248        b->SetInsertPoint(extendLiteralEnd);
1249        PHINode* literalExtendValue = b->CreatePHI(b->getSizeTy(), 2);
1250        literalExtendValue->addIncoming(SIZE_0, entryBlock);
1251        literalExtendValue->addIncoming(newExtendLiteralLength, extendLiteralCond);
1252        PHINode* phiExtendLiteralEndPos = b->CreatePHI(b->getSizeTy(), 2);
1253        phiExtendLiteralEndPos->addIncoming(tokenPos, entryBlock);
1254        phiExtendLiteralEndPos->addIncoming(phiCurrentExtendLiteralPos, extendLiteralCond);
1255
1256        Value* literalLength = b->CreateAdd(literalExtendValue, b->CreateZExt(b->CreateLShr(tokenValue, b->getInt8(4)), b->getSizeTy()));
1257
1258        Value* literalStartPos = b->CreateAdd(phiExtendLiteralEndPos, SIZE_1);
1259        return std::make_pair(literalStartPos, literalLength);
1260    }
1261
1262    std::pair<llvm::Value *, llvm::Value *> LZ4ParallelByteStreamAioKernel::parseMatchInfo(const std::unique_ptr<KernelBuilder> &b, llvm::Value *matchOffsetPos, llvm::Value* tokenValue) {
1263        Value* bytePtrBase = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
1264
1265        Value* shouldExtendMatch = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_0F), BYTE_0F);
1266        BasicBlock* entryBlock = b->GetInsertBlock();
1267        BasicBlock* extendMatchCon = b->CreateBasicBlock("extendMatchCon");
1268        BasicBlock* extendMatchExit = b->CreateBasicBlock("extendMatchExit");
1269
1270        Value* matchOffsetNextPos = b->CreateAdd(matchOffsetPos, SIZE_1);
1271        Value* initExtendMatchPos = b->CreateAdd(matchOffsetPos, b->getSize(2));
1272
1273        b->CreateCondBr(shouldExtendMatch, extendMatchCon, extendMatchExit);
1274
1275        // ---- extendMatchCon
1276        b->SetInsertPoint(extendMatchCon);
1277        PHINode* phiCurrentExtendMatchPos = b->CreatePHI(b->getSizeTy(), 2);
1278        phiCurrentExtendMatchPos->addIncoming(initExtendMatchPos, entryBlock);
1279        PHINode* phiExtendMatchLength = b->CreatePHI(b->getSizeTy(), 2);
1280        phiExtendMatchLength->addIncoming(SIZE_0, entryBlock);
1281
1282        Value* currentMatchLengthByte = b->CreateLoad(b->CreateGEP(bytePtrBase, phiCurrentExtendMatchPos));
1283        Value* newExtendMatchLength = b->CreateAdd(phiExtendMatchLength, b->CreateZExt(currentMatchLengthByte, b->getSizeTy()));
1284
1285        phiCurrentExtendMatchPos->addIncoming(b->CreateAdd(phiCurrentExtendMatchPos, SIZE_1), b->GetInsertBlock());
1286        phiExtendMatchLength->addIncoming(newExtendMatchLength, b->GetInsertBlock());
1287
1288        b->CreateCondBr(b->CreateICmpEQ(currentMatchLengthByte, BYTE_FF), extendMatchCon, extendMatchExit);
1289
1290        // ---- extendMatchExit
1291        b->SetInsertPoint(extendMatchExit);
1292        PHINode* matchExtendValue = b->CreatePHI(b->getSizeTy(), 2);
1293        matchExtendValue->addIncoming(SIZE_0, entryBlock);
1294        matchExtendValue->addIncoming(newExtendMatchLength, extendMatchCon);
1295        PHINode* phiExtendMatchEndPos = b->CreatePHI(b->getSizeTy(), 2);
1296        phiExtendMatchEndPos->addIncoming(matchOffsetNextPos, entryBlock);
1297        phiExtendMatchEndPos->addIncoming(phiCurrentExtendMatchPos, extendMatchCon);
1298
1299        // matchLength = (size_t)token & 0xf + 4 + matchExtendValue
1300        Value* matchLength = b->CreateAdd(
1301                b->CreateAdd(matchExtendValue, b->getSize(4)),
1302                b->CreateZExt(b->CreateAnd(tokenValue, BYTE_0F), b->getSizeTy())
1303        );
1304        return std::make_pair(phiExtendMatchEndPos, matchLength);
1305
1306    };
1307
1308    pair<Value*, Value*> LZ4ParallelByteStreamAioKernel::processBlockBoundary(const std::unique_ptr<KernelBuilder> &b, llvm::Value *beginTokenPos,
1309                                                              llvm::Value *lz4BlockEnd, llvm::Value* initOutputPos) {
1310        // ---- EntryBlock
1311        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
1312        Value* bytePtrBase = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
1313        Value* tokenValue = b->CreateLoad(b->CreateGEP(bytePtrBase, beginTokenPos));
1314
1315
1316        // Literal
1317        Value *literalStartPos = nullptr, *literalLength = nullptr;
1318        std::tie(literalStartPos, literalLength) = this->parseLiteralInfo(b, beginTokenPos, tokenValue);
1319        this->handleLiteralCopy(b, literalStartPos, literalLength, initOutputPos);
1320        Value* literalEndPos = b->CreateAdd(literalStartPos, literalLength);
1321        Value* outputPosAfterLiteralCpy = b->CreateAdd(literalLength, initOutputPos);
1322
1323
1324        Value* matchOffsetBeginPos = literalEndPos;
1325        Value* matchOffsetNextPos = b->CreateAdd(matchOffsetBeginPos, SIZE_1);
1326        BasicBlock* hasMatchPartBlock = b->CreateBasicBlock("hasMatchPartBlock");
1327        BasicBlock* extendLiteralEndFinal = b->GetInsertBlock();
1328        b->CreateLikelyCondBr(b->CreateICmpULT(matchOffsetBeginPos, lz4BlockEnd), hasMatchPartBlock, exitBlock);
1329
1330
1331        // ---- hasMatchPartBlock
1332        b->SetInsertPoint(hasMatchPartBlock);
1333        // Match
1334        // For now, it is safe to cast matchOffset pointer into i16 since the input byte stream is always linear available
1335        Value* matchOffsetPtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", matchOffsetBeginPos), b->getInt16Ty()->getPointerTo());
1336        Value* matchOffset = b->CreateZExt(b->CreateLoad(matchOffsetPtr), b->getSizeTy());
1337
1338        Value *matchLengthEndPos = nullptr, *matchLength = nullptr;
1339        std::tie(matchLengthEndPos, matchLength) = this->parseMatchInfo(b, matchOffsetBeginPos, tokenValue);
1340        this->handleMatchCopy(b, matchOffset, matchLength, outputPosAfterLiteralCpy);
1341        Value* outputPosAfterMatchCpy = b->CreateAdd(outputPosAfterLiteralCpy, matchLength);
1342        BasicBlock* extendMatchExitFinal = b->GetInsertBlock();
1343        b->CreateBr(exitBlock);
1344
1345
1346        // ---- exitBlock
1347        b->SetInsertPoint(exitBlock);
1348        PHINode* phiBeforeTokenPos = b->CreatePHI(b->getSizeTy(), 2);
1349        phiBeforeTokenPos->addIncoming(matchOffsetNextPos, extendLiteralEndFinal);
1350        phiBeforeTokenPos->addIncoming(matchLengthEndPos, extendMatchExitFinal);
1351        PHINode* phiOutputPos = b->CreatePHI(b->getSizeTy(), 2);
1352        phiOutputPos->addIncoming(outputPosAfterLiteralCpy, extendLiteralEndFinal);
1353        phiOutputPos->addIncoming(outputPosAfterMatchCpy, extendMatchExitFinal);
1354
1355        Value* nextTokenPos = b->CreateAdd(phiBeforeTokenPos, SIZE_1);
1356
1357        return std::make_pair(nextTokenPos, phiOutputPos);
1358    }
1359
1360    void LZ4ParallelByteStreamAioKernel::generateSimdMatchCopyByScatter(const std::unique_ptr<KernelBuilder> &b, llvm::Value* matchOffsetVec, llvm::Value* matchLengthVec, llvm::Value* outputPosVec) {
1361        // ---- EntryBlock
1362        BasicBlock* entryBlock = b->GetInsertBlock();
1363        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
1364        BasicBlock* i64MatchCopyBlock = b->CreateBasicBlock("i64MatchCopyBlock");
1365        BasicBlock* i8MatchCopyBlock = b->CreateBasicBlock("i8MatchCopyBlock");
1366
1367        llvm::Value* initCopiedLength = ConstantVector::getNullValue(matchLengthVec->getType());
1368
1369//        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
1370        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", b->getSize(0)), b->getInt8PtrTy());
1371
1372        Value* outputCapacity = b->getCapacity("outputStream");
1373        Value* outputPosRemVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(outputCapacity))));
1374        Value* outputPosRemBlockSizeVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(b->getIntN(SIMD_WIDTH, mLz4BlockSize)))));
1375        Value* remainingBlockSizeVec = b->simd_sub(SIMD_WIDTH, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, mLz4BlockSize)), outputPosRemBlockSizeVec);
1376
1377        Value* possibleExceedBuffer = b->simd_uge(SIMD_WIDTH, b->simd_add(SIMD_WIDTH, matchLengthVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 8))), remainingBlockSizeVec);
1378        // true ffff, false 0000
1379
1380        // TODO handle matchLengthVec == 0
1381
1382        b->CreateUnlikelyCondBr(
1383                b->CreateICmpNE(b->CreateBitCast(possibleExceedBuffer, b->getIntNTy(b->getBitBlockWidth())), b->getIntN(b->getBitBlockWidth(), 0)),
1384                i8MatchCopyBlock,
1385                i64MatchCopyBlock
1386        );
1387
1388        // ---- i8MatchCopyBlock
1389        b->SetInsertPoint(i8MatchCopyBlock);
1390        this->generateSimdSequentialMatchCopy(b, matchOffsetVec, matchLengthVec, outputPosVec);
1391        b->CreateBr(exitBlock);
1392
1393        // ---- i64MatchCopyBlock
1394        b->SetInsertPoint(i64MatchCopyBlock);
1395
1396        BasicBlock* i64MatchCopyConBlock = b->CreateBasicBlock("i64MatchCopyConBlock");
1397        BasicBlock* i64MatchCopyBodyBlock = b->CreateBasicBlock("i64MatchCopyBodyBlock");
1398
1399        b->CreateBr(i64MatchCopyConBlock);
1400
1401        // ---- i64MatchCopyConBlock
1402        b->SetInsertPoint(i64MatchCopyConBlock);
1403        PHINode* phiCopiedLength = b->CreatePHI(initCopiedLength->getType(), 2);
1404        phiCopiedLength->addIncoming(initCopiedLength, i64MatchCopyBlock);
1405
1406        Value* shouldCopiedBitBlock = b->simd_ult(SIMD_WIDTH, phiCopiedLength, matchLengthVec);
1407//        b->CallPrintRegister("phiCopiedLength", phiCopiedLength);
1408//        b->CallPrintRegister("literalLengthVec", literalLengthVec);
1409//        b->CallPrintRegister("shouldCopiedBitBlock", shouldCopiedBitBlock);
1410        Value* shouldCopiedI1 = b->CreateICmpNE(
1411                b->CreateBitCast(shouldCopiedBitBlock, b->getIntNTy(b->getBitBlockWidth())),
1412                b->getIntN(b->getBitBlockWidth(), 0)
1413        );
1414
1415
1416        b->CreateCondBr(shouldCopiedI1, i64MatchCopyBodyBlock, exitBlock);
1417
1418        // ---- i64MatchCopyBodyBlock
1419        b->SetInsertPoint(i64MatchCopyBodyBlock);
1420        Value* currentOutputPosVec = b->simd_add(SIMD_WIDTH, outputPosRemVec, phiCopiedLength);
1421        Value* copyFromPosVec = b->simd_sub(SIMD_WIDTH, currentOutputPosVec, matchOffsetVec);
1422
1423        Value* literalData = this->simdFetchI64DataByGather(b, outputBasePtr, copyFromPosVec, shouldCopiedBitBlock);
1424
1425        this->simdPutData(
1426                b,
1427                outputBasePtr,
1428                currentOutputPosVec,
1429                literalData,
1430                shouldCopiedBitBlock
1431        );
1432        phiCopiedLength->addIncoming(
1433                b->simd_add(
1434                        SIMD_WIDTH,
1435                        phiCopiedLength,
1436                        b->simd_and(
1437                                b->simd_umin(SIMD_WIDTH, matchOffsetVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 8))),
1438                                shouldCopiedBitBlock
1439                        )
1440
1441                ),
1442                b->GetInsertBlock()
1443        );
1444
1445        b->CreateBr(i64MatchCopyConBlock);
1446        b->SetInsertPoint(exitBlock);
1447
1448    }
1449
1450    void LZ4ParallelByteStreamAioKernel::generateSimdSequentialMatchCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value* matchOffsetVec, llvm::Value* matchLengthVec, llvm::Value* outputPosVec) {
1451        // Constant
1452        Constant * SIZE_8 = b->getSize(8);
1453        // Type
1454        PointerType* i64PtrTy = b->getInt64Ty()->getPointerTo();
1455        PointerType* i8PtrTy = b->getInt8PtrTy();
1456
1457        Value* outputCapacity = b->getCapacity("outputStream");
1458        Value* outputPosRemVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(outputCapacity))));
1459        Value* outputPosRemBlockSizeVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(b->getIntN(SIMD_WIDTH, mLz4BlockSize)))));
1460        Value* remainingBlockSizeVec = b->simd_sub(SIMD_WIDTH, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, mLz4BlockSize)), outputPosRemBlockSizeVec);
1461        Value* copyFromPosRemVec = b->simd_sub(SIMD_WIDTH, outputPosRemVec, matchOffsetVec);
1462
1463
1464        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", b->getSize(0)), b->getInt8PtrTy());
1465
1466
1467        for (unsigned i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
1468
1469            BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
1470            BasicBlock* i64MatchCopyBlock = b->CreateBasicBlock("i64LiteralCopyBlock");
1471            BasicBlock* i8MatchCopyBlock = b->CreateBasicBlock("i8LiteralCopyBlock");
1472
1473            // ---- entryBlock
1474            Value* matchOffset = b->CreateExtractElement(matchOffsetVec, i);
1475            Value* matchLength = b->CreateExtractElement(matchLengthVec, i);
1476            Value* outputPosRem = b->CreateExtractElement(outputPosRemVec, i);
1477            Value* remainingBlockSize = b->CreateExtractElement(remainingBlockSizeVec, i);
1478            Value* outputFromRem = b->CreateExtractElement(copyFromPosRemVec, i);
1479
1480            Value* inputInitPtr = b->CreateGEP(outputBasePtr, outputFromRem);
1481            Value* outputInitPtr = b->CreateGEP(outputBasePtr, outputPosRem);
1482
1483            b->CreateLikelyCondBr(b->CreateICmpUGE(b->CreateSub(remainingBlockSize, matchLength), SIZE_8), i64MatchCopyBlock, i8MatchCopyBlock);
1484
1485            //// i64 Match Copy
1486            // ---- i64MatchCopyBlock
1487            b->SetInsertPoint(i64MatchCopyBlock);
1488
1489            this->generateOverwritingMemcpy(b, inputInitPtr, outputInitPtr, matchLength, i64PtrTy, b->CreateUMin(matchOffset, SIZE_8));
1490            b->CreateBr(exitBlock);
1491
1492            //// i8 Match Copy
1493            // ---- i8MatchCopyBlock
1494            b->SetInsertPoint(i8MatchCopyBlock);
1495            this->generateOverwritingMemcpy(b, inputInitPtr, outputInitPtr, matchLength, i8PtrTy, 1);
1496            b->CreateBr(exitBlock);
1497
1498            // ---- exitBlock
1499            b->SetInsertPoint(exitBlock);
1500
1501        }
1502
1503    }
1504
1505    void LZ4ParallelByteStreamAioKernel::handleSimdMatchCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value* matchOffsetVec, llvm::Value* matchLengthVec, llvm::Value* outputPosVec) {
1506        if (AVX512BW_available() && mEnableScatter) {
1507            this->generateSimdMatchCopyByScatter(b, matchOffsetVec, matchLengthVec, outputPosVec);
1508        } else {
1509            this->generateSimdSequentialMatchCopy(b, matchOffsetVec, matchLengthVec, outputPosVec);
1510        }
1511    }
1512
1513    void LZ4ParallelByteStreamAioKernel::handleSimdLiteralCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value* literalStartVec, llvm::Value* literalLengthVec, llvm::Value* outputPosVec) {
1514//        this->recordParallelLevel(b, b->hsimd_signmask(SIMD_WIDTH, b->simd_gt(SIMD_WIDTH, literalLengthVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 32)))));
1515        if (AVX512BW_available() && mEnableScatter) {
1516            this->generateSimdLiteralCopyByScatter(b, literalStartVec, literalLengthVec, outputPosVec);
1517        } else {
1518            this->generateSimdSequentialLiteralCopy(b, literalStartVec, literalLengthVec, outputPosVec);
1519        }
1520    }
1521
1522    void LZ4ParallelByteStreamAioKernel::generateSimdSequentialLiteralCopy(const std::unique_ptr<KernelBuilder> &b,
1523                                                                           llvm::Value *literalStartVec,
1524                                                                           llvm::Value *literalLengthVec,
1525                                                                           llvm::Value *outputPosVec) {
1526        // Constant
1527        Constant * SIZE_8 = b->getSize(8);
1528        // Type
1529        PointerType* i64PtrTy = b->getInt64Ty()->getPointerTo();
1530        PointerType* i8PtrTy = b->getInt8PtrTy();
1531
1532        Value* outputCapacity = b->getCapacity("outputStream");
1533        Value* outputPosRemVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(outputCapacity))));
1534        Value* outputPosRemBlockSizeVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(b->getIntN(SIMD_WIDTH, mLz4BlockSize)))));
1535        Value* remainingBlockSizeVec = b->simd_sub(SIMD_WIDTH, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, mLz4BlockSize)), outputPosRemBlockSizeVec);
1536
1537        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
1538        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", b->getSize(0)), b->getInt8PtrTy());
1539
1540
1541        for (unsigned i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
1542            BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
1543            BasicBlock* i64LiteralCopyBlock = b->CreateBasicBlock("i64LiteralCopyBlock");
1544            BasicBlock* i8LiteralCopyBlock = b->CreateBasicBlock("i8LiteralCopyBlock");
1545
1546            // ---- entryBlock
1547            Value* literalStart = b->CreateExtractElement(literalStartVec, i);
1548            Value* literalLength = b->CreateExtractElement(literalLengthVec, i);
1549            Value* outputPosRem = b->CreateExtractElement(outputPosRemVec, i);
1550            Value* remainingBlockSize = b->CreateExtractElement(remainingBlockSizeVec, i);
1551
1552            Value* inputInitPtr = b->CreateGEP(inputBasePtr, literalStart);
1553            Value* outputInitPtr = b->CreateGEP(outputBasePtr, outputPosRem);
1554
1555            b->CreateLikelyCondBr(b->CreateICmpUGE(b->CreateSub(remainingBlockSize, literalLength), SIZE_8), i64LiteralCopyBlock, i8LiteralCopyBlock);
1556
1557            //// i64 Literal Copy
1558            // ---- i64LiteralCopyBlock
1559            b->SetInsertPoint(i64LiteralCopyBlock);
1560            this->generateOverwritingMemcpy(b, inputInitPtr, outputInitPtr, literalLength, i64PtrTy, 8);
1561            b->CreateBr(exitBlock);
1562
1563            //// i8 Literal Copy
1564            // ---- i8LiteralCopyBlock
1565            b->SetInsertPoint(i8LiteralCopyBlock);
1566            this->generateOverwritingMemcpy(b, inputInitPtr, outputInitPtr, literalLength, i8PtrTy, 1);
1567            b->CreateBr(exitBlock);
1568
1569            // ---- exitBlock
1570            b->SetInsertPoint(exitBlock);
1571        }
1572    }
1573
1574    void LZ4ParallelByteStreamAioKernel::generateOverwritingMemcpy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *inputBasePtr,
1575                                   llvm::Value *outputBasePtr, llvm::Value *copyBytes, llvm::PointerType *targetPtrTy,
1576                                   llvm::Value* stepSize) {
1577//        unsigned targetPtrBitWidth = targetPtrTy->getElementType()->getIntegerBitWidth();
1578
1579        Constant * SIZE_0 = b->getSize(0);
1580//        Constant * SIZE_1 = b->getSize(1);
1581        PointerType* i8PtrTy = b->getInt8PtrTy();
1582
1583        BasicBlock* entryBlock = b->GetInsertBlock();
1584        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
1585        BasicBlock* conBlock = b->CreateBasicBlock("conBlock");
1586        BasicBlock* bodyBlock = b->CreateBasicBlock("bodyBlock");
1587
1588        Value* inputInitPtr = b->CreatePointerCast(inputBasePtr, targetPtrTy);
1589        Value* outputInitPtr = b->CreatePointerCast(outputBasePtr, targetPtrTy);
1590
1591        b->CreateBr(conBlock);
1592        // ---- conBlock
1593        b->SetInsertPoint(conBlock);
1594
1595        PHINode *phiCopiedSize = b->CreatePHI(b->getSizeTy(), 2);
1596        phiCopiedSize->addIncoming(SIZE_0, entryBlock);
1597        PHINode *phiInputPtr = b->CreatePHI(targetPtrTy, 2);
1598        phiInputPtr->addIncoming(inputInitPtr, entryBlock);
1599        PHINode *phiOutputPtr = b->CreatePHI(targetPtrTy, 2);
1600        phiOutputPtr->addIncoming(outputInitPtr, entryBlock);
1601
1602        b->CreateCondBr(b->CreateICmpULT(phiCopiedSize, copyBytes), bodyBlock, exitBlock);
1603
1604        // ---- bodyBlock
1605        b->SetInsertPoint(bodyBlock);
1606        b->CreateStore(b->CreateLoad(phiInputPtr), phiOutputPtr);
1607
1608        phiCopiedSize->addIncoming(b->CreateAdd(phiCopiedSize, stepSize), b->GetInsertBlock());
1609
1610        Value *newInputPtr = nullptr, *newOutputPtr = nullptr;
1611
1612        newInputPtr = b->CreatePointerCast(
1613                b->CreateGEP(b->CreatePointerCast(phiInputPtr, i8PtrTy), stepSize),
1614                targetPtrTy
1615        );
1616
1617        newOutputPtr = b->CreatePointerCast(
1618                b->CreateGEP(b->CreatePointerCast(phiOutputPtr, i8PtrTy), stepSize),
1619                targetPtrTy
1620        );
1621
1622        phiInputPtr->addIncoming(newInputPtr, b->GetInsertBlock());
1623        phiOutputPtr->addIncoming(newOutputPtr, b->GetInsertBlock());
1624        b->CreateBr(conBlock);
1625
1626        // ---- exitBlock
1627        b->SetInsertPoint(exitBlock);
1628    }
1629
1630    void LZ4ParallelByteStreamAioKernel::generateOverwritingMemcpy(const std::unique_ptr<KernelBuilder> &b,
1631                                                                   llvm::Value *inputBasePtr,
1632                                                                   llvm::Value *outputBasePtr,
1633                                                                   llvm::Value *copyBytes, llvm::PointerType *targetPtrTy,
1634                                                                   size_t stepSize) {
1635        unsigned targetPtrBitWidth = targetPtrTy->getElementType()->getIntegerBitWidth();
1636
1637        Constant * SIZE_0 = b->getSize(0);
1638        Constant * SIZE_1 = b->getSize(1);
1639        PointerType* i8PtrTy = b->getInt8PtrTy();
1640
1641        BasicBlock* entryBlock = b->GetInsertBlock();
1642        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
1643        BasicBlock* conBlock = b->CreateBasicBlock("conBlock");
1644        BasicBlock* bodyBlock = b->CreateBasicBlock("bodyBlock");
1645
1646        Value* inputInitPtr = b->CreatePointerCast(inputBasePtr, targetPtrTy);
1647        Value* outputInitPtr = b->CreatePointerCast(outputBasePtr, targetPtrTy);
1648
1649        b->CreateBr(conBlock);
1650        // ---- conBlock
1651        b->SetInsertPoint(conBlock);
1652
1653        PHINode *phiCopiedSize = b->CreatePHI(b->getSizeTy(), 2);
1654        phiCopiedSize->addIncoming(SIZE_0, entryBlock);
1655        PHINode *phiInputPtr = b->CreatePHI(targetPtrTy, 2);
1656        phiInputPtr->addIncoming(inputInitPtr, entryBlock);
1657        PHINode *phiOutputPtr = b->CreatePHI(targetPtrTy, 2);
1658        phiOutputPtr->addIncoming(outputInitPtr, entryBlock);
1659
1660        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
1661
1662        // ---- bodyBlock
1663        b->SetInsertPoint(bodyBlock);
1664        b->CreateStore(b->CreateLoad(phiInputPtr), phiOutputPtr);
1665
1666        phiCopiedSize->addIncoming(b->CreateAdd(phiCopiedSize, b->getSize(stepSize)), b->GetInsertBlock());
1667
1668        Value *newInputPtr = nullptr, *newOutputPtr = nullptr;
1669
1670        if (targetPtrBitWidth / 8 == stepSize) {
1671            newInputPtr = b->CreateGEP(phiInputPtr, SIZE_1);
1672            newOutputPtr = b->CreateGEP(phiOutputPtr, SIZE_1);
1673        } else {
1674            newInputPtr = b->CreatePointerCast(
1675                    b->CreateGEP(b->CreatePointerCast(phiInputPtr, i8PtrTy), b->getSize(stepSize)),
1676                    targetPtrTy
1677            );
1678
1679            newOutputPtr = b->CreatePointerCast(
1680                    b->CreateGEP(b->CreatePointerCast(phiOutputPtr, i8PtrTy), b->getSize(stepSize)),
1681                    targetPtrTy
1682            );
1683
1684        }
1685
1686        phiInputPtr->addIncoming(newInputPtr, b->GetInsertBlock());
1687        phiOutputPtr->addIncoming(newOutputPtr, b->GetInsertBlock());
1688        b->CreateBr(conBlock);
1689
1690        // ---- exitBlock
1691        b->SetInsertPoint(exitBlock);
1692    }
1693
1694    void LZ4ParallelByteStreamAioKernel::generateSimdLiteralCopyByScatter(const std::unique_ptr<KernelBuilder> &b,
1695                                                                          llvm::Value *literalStartVec,
1696                                                                          llvm::Value *literalLengthVec,
1697                                                                          llvm::Value *outputPosVec) {
1698        // ---- EntryBlock
1699        BasicBlock* entryBlock = b->GetInsertBlock();
1700        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
1701        BasicBlock* i64LiteralCopyBlock = b->CreateBasicBlock("i64LiteralCopyBlock");
1702        BasicBlock* i8LiteralCopyBlock = b->CreateBasicBlock("i8LiteralCopyBlock");
1703
1704        llvm::Value* initCopiedLength = ConstantVector::getNullValue(literalLengthVec->getType());
1705
1706        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
1707        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", b->getSize(0)), b->getInt8PtrTy());
1708
1709        Value* outputCapacity = b->getCapacity("outputStream");
1710        Value* outputPosRemVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(outputCapacity))));
1711        Value* outputPosRemBlockSizeVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(b->getIntN(SIMD_WIDTH, mLz4BlockSize)))));
1712        Value* remainingBlockSizeVec = b->simd_sub(SIMD_WIDTH, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, mLz4BlockSize)), outputPosRemBlockSizeVec);
1713
1714        Value* possibleExceedBuffer = b->simd_uge(SIMD_WIDTH, b->simd_add(SIMD_WIDTH, literalLengthVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 8))), remainingBlockSizeVec);
1715        // true ffff, false 0000
1716
1717        // TODO handle literalLengthVec == 0
1718
1719        b->CreateUnlikelyCondBr(
1720                b->CreateICmpNE(b->CreateBitCast(possibleExceedBuffer, b->getIntNTy(b->getBitBlockWidth())), b->getIntN(b->getBitBlockWidth(), 0)),
1721                i8LiteralCopyBlock,
1722                i64LiteralCopyBlock
1723        );
1724
1725        // ---- i8LiteralCopyBlock
1726        b->SetInsertPoint(i8LiteralCopyBlock);
1727        this->generateSimdSequentialLiteralCopy(b, literalStartVec, literalLengthVec, outputPosVec);
1728        b->CreateBr(exitBlock);
1729
1730        // ---- i64LiteralCopyBlock
1731        b->SetInsertPoint(i64LiteralCopyBlock);
1732
1733        BasicBlock* i64LiteralCopyConBlock = b->CreateBasicBlock("i64LiteralCopyConBlock");
1734        BasicBlock* i64LiteralCopyBodyBlock = b->CreateBasicBlock("i64LiteralCopyBodyBlock");
1735
1736
1737        b->CreateBr(i64LiteralCopyConBlock);
1738
1739        // ---- i64LiteralCopyConBlock
1740        b->SetInsertPoint(i64LiteralCopyConBlock);
1741        PHINode* phiCopiedLength = b->CreatePHI(initCopiedLength->getType(), 2);
1742        phiCopiedLength->addIncoming(initCopiedLength, i64LiteralCopyBlock);
1743
1744        Value* shouldCopiedBitBlock = b->simd_ult(SIMD_WIDTH, phiCopiedLength, literalLengthVec);
1745//        b->CallPrintRegister("phiCopiedLength", phiCopiedLength);
1746//        b->CallPrintRegister("literalLengthVec", literalLengthVec);
1747//        b->CallPrintRegister("shouldCopiedBitBlock", shouldCopiedBitBlock);
1748        Value* shouldCopiedI1 = b->CreateICmpNE(
1749                b->CreateBitCast(shouldCopiedBitBlock, b->getIntNTy(b->getBitBlockWidth())),
1750                b->getIntN(b->getBitBlockWidth(), 0)
1751        );
1752
1753
1754        b->CreateCondBr(shouldCopiedI1, i64LiteralCopyBodyBlock, exitBlock);
1755
1756
1757        // ---- i64LiteralCopyBodyBlock
1758        b->SetInsertPoint(i64LiteralCopyBodyBlock);
1759        Value* literalData = this->simdFetchI64DataByGather(b, inputBasePtr, b->simd_add(SIMD_WIDTH, literalStartVec, phiCopiedLength), shouldCopiedBitBlock);
1760
1761        this->simdPutData(
1762                b,
1763                outputBasePtr,
1764                b->simd_add(SIMD_WIDTH, outputPosRemVec, phiCopiedLength),
1765                literalData,
1766                shouldCopiedBitBlock
1767        );
1768//        b->CallPrintRegister("phiCopiedLength", phiCopiedLength);
1769        phiCopiedLength->addIncoming(
1770                b->simd_add(
1771                        SIMD_WIDTH,
1772                        phiCopiedLength,
1773                        b->simd_and(
1774                                b->simd_fill(
1775                                        SIMD_WIDTH,
1776                                        b->getIntN(SIMD_WIDTH, 8)
1777                                ),
1778                                shouldCopiedBitBlock
1779                        )
1780
1781                ),
1782                b->GetInsertBlock()
1783        );
1784
1785        b->CreateBr(i64LiteralCopyConBlock);
1786
1787        b->SetInsertPoint(exitBlock);
1788    }
1789
1790
1791    void LZ4ParallelByteStreamAioKernel::handleLiteralCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *literalStart,
1792                                                   llvm::Value *literalLength, llvm::Value* outputPos) {
1793        unsigned fw = 64;
1794        Type* INT_FW_PTR = b->getIntNTy(fw)->getPointerTo();
1795
1796        Value* inputBytePtr = b->getRawInputPointer("byteStream", literalStart);
1797        Value* inputPtr = b->CreatePointerCast(inputBytePtr, INT_FW_PTR);
1798
1799        Value* outputBufferSize = b->getCapacity("outputStream");
1800        Value* outputPtr = b->getRawOutputPointer("outputStream", b->CreateURem(outputPos, outputBufferSize));
1801        outputPtr = b->CreatePointerCast(outputPtr, INT_FW_PTR);
1802
1803        // We can always assume that we have enough output buffer based on our output buffer allocation strategy (except in extract only case)
1804
1805        BasicBlock* entryBlock = b->GetInsertBlock();
1806        BasicBlock* literalCopyCon = b->CreateBasicBlock("literalCopyCon");
1807        BasicBlock* literalCopyBody = b->CreateBasicBlock("literalCopyBody");
1808        BasicBlock* literalCopyExit = b->CreateBasicBlock("literalCopyExit");
1809
1810        b->CreateBr(literalCopyCon);
1811
1812        // ---- literalCopyCon
1813        b->SetInsertPoint(literalCopyCon);
1814        PHINode* phiOutputPtr = b->CreatePHI(outputPtr->getType(), 2);
1815        phiOutputPtr->addIncoming(outputPtr, entryBlock);
1816        PHINode* phiInputPtr = b->CreatePHI(inputPtr->getType(), 2);
1817        phiInputPtr->addIncoming(inputPtr, entryBlock);
1818        PHINode* phiCopiedLength = b->CreatePHI(literalLength->getType(), 2);
1819        phiCopiedLength->addIncoming(b->getSize(0), entryBlock);
1820        b->CreateCondBr(b->CreateICmpULT(phiCopiedLength, literalLength), literalCopyBody, literalCopyExit);
1821
1822        // ---- literalCopyBody
1823        b->SetInsertPoint(literalCopyBody);
1824        // Always copy fw bits to improve performance
1825        b->CreateStore(b->CreateLoad(phiInputPtr), phiOutputPtr);
1826
1827        phiInputPtr->addIncoming(b->CreateGEP(phiInputPtr, b->getSize(1)), b->GetInsertBlock());
1828        phiOutputPtr->addIncoming(b->CreateGEP(phiOutputPtr, b->getSize(1)), b->GetInsertBlock());
1829        phiCopiedLength->addIncoming(b->CreateAdd(phiCopiedLength, b->getSize(fw / 8)), b->GetInsertBlock());
1830        b->CreateBr(literalCopyCon);
1831
1832        // ---- literalCopyExit
1833        b->SetInsertPoint(literalCopyExit);
1834        b->setScalarField("outputPos", b->CreateAdd(outputPos, literalLength));
1835    }
1836
1837    void LZ4ParallelByteStreamAioKernel::handleMatchCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *matchOffset,
1838                                                 llvm::Value *matchLength, llvm::Value* outputPos) {
1839        unsigned fw = 64;
1840        Type* INT_FW_PTR = b->getIntNTy(fw)->getPointerTo();
1841
1842        BasicBlock* entryBlock = b->GetInsertBlock();
1843
1844        Value* outputBufferSize = b->getCapacity("outputStream");
1845
1846        Value* copyToPtr = b->getRawOutputPointer("outputStream", b->CreateURem(outputPos, outputBufferSize));
1847        Value* copyFromPtr = b->getRawOutputPointer("outputStream", b->CreateURem(b->CreateSub(outputPos, matchOffset), outputBufferSize));
1848
1849        BasicBlock* matchCopyCon = b->CreateBasicBlock("matchCopyCon");
1850        BasicBlock* matchCopyBody = b->CreateBasicBlock("matchCopyBody");
1851        BasicBlock* matchCopyExit = b->CreateBasicBlock("matchCopyExit");
1852
1853        b->CreateBr(matchCopyCon);
1854
1855        // ---- matchCopyCon
1856        b->SetInsertPoint(matchCopyCon);
1857        PHINode* phiFromPtr = b->CreatePHI(b->getInt8PtrTy(), 2);
1858        phiFromPtr->addIncoming(copyFromPtr, entryBlock);
1859        PHINode* phiToPtr = b->CreatePHI(b->getInt8PtrTy(), 2);
1860        phiToPtr->addIncoming(copyToPtr, entryBlock);
1861        PHINode* phiCopiedSize = b->CreatePHI(b->getSizeTy(), 2);
1862        phiCopiedSize->addIncoming(b->getSize(0), entryBlock);
1863
1864        b->CreateCondBr(b->CreateICmpULT(phiCopiedSize, matchLength), matchCopyBody, matchCopyExit);
1865
1866        // ---- matchCopyBody
1867        b->SetInsertPoint(matchCopyBody);
1868        b->CreateStore(
1869                b->CreateLoad(b->CreatePointerCast(phiFromPtr, INT_FW_PTR)),
1870                b->CreatePointerCast(phiToPtr, INT_FW_PTR)
1871        );
1872
1873        Value* copySize = b->CreateUMin(matchOffset, b->getSize(fw / 8));
1874        phiFromPtr->addIncoming(b->CreateGEP(phiFromPtr, copySize), b->GetInsertBlock());
1875        phiToPtr->addIncoming(b->CreateGEP(phiToPtr, copySize), b->GetInsertBlock());
1876        phiCopiedSize->addIncoming(b->CreateAdd(phiCopiedSize, copySize), b->GetInsertBlock());
1877        b->CreateBr(matchCopyCon);
1878
1879        // ---- matchCopyExit
1880        b->SetInsertPoint(matchCopyExit);
1881        b->setScalarField("outputPos", b->CreateAdd(outputPos, matchLength));
1882    }
1883
1884    llvm::Value* LZ4ParallelByteStreamAioKernel::simdFetchData(const std::unique_ptr<KernelBuilder> &b, llvm::Value* basePtr, llvm::Value* offsetVec, llvm::Value* mask) {
1885//        return this->simdFetchDataByLoop(b, basePtr, offsetVec, mask);
1886        if (AVX2_available() && mEnableGather) {
1887            return this->simdFetchI32DataByGather(b, basePtr, offsetVec, mask);
1888        } else {
1889            return this->simdFetchDataByLoop(b, basePtr, offsetVec, mask);
1890        }
1891    }
1892
1893
1894
1895    llvm::Value* LZ4ParallelByteStreamAioKernel::simdFetchByteData(const std::unique_ptr<KernelBuilder> &b, llvm::Value* basePtr, llvm::Value* offsetVec, llvm::Value* mask) {
1896        if (AVX2_available() && mEnableGather) {
1897            return b->simd_and(this->simdFetchI32DataByGather(b, basePtr, offsetVec, mask), b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0xff)));
1898        } else {
1899            return this->simdFetchDataByLoop(b, basePtr, offsetVec, mask, 8);
1900        }
1901    }
1902
1903    llvm::Value* LZ4ParallelByteStreamAioKernel::simdFetchI32DataByGather(const std::unique_ptr<KernelBuilder> &b,
1904                                                                          llvm::Value *basePtr, llvm::Value *offsetVec,
1905                                                                          llvm::Value *mask) {
1906
1907        Function *gatherFunc2 = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx2_gather_d_d);
1908        Function *gatherFunc3 = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx2_gather_d_d_256);
1909
1910        Function *gatherFunc = AVX512BW_available() ? gatherFunc3 : gatherFunc2;
1911
1912        Type* i32BitBlockTy = VectorType::get(b->getInt32Ty(), b->getBitBlockWidth() / SIMD_WIDTH);
1913
1914
1915        Value* tokenValuesVec =  b->CreateCall(
1916                gatherFunc,
1917                {
1918                        UndefValue::get(i32BitBlockTy),
1919                        basePtr,
1920                        b->CreateTrunc(offsetVec, i32BitBlockTy),
1921                        b->CreateTrunc(mask, i32BitBlockTy),
1922                        b->getInt8(1)
1923                }
1924        );
1925        tokenValuesVec = b->CreateZExt(tokenValuesVec, b->getBitBlockType());
1926        tokenValuesVec = b->CreateAnd(tokenValuesVec, mask);
1927
1928        return tokenValuesVec;
1929    }
1930
1931    llvm::Value* LZ4ParallelByteStreamAioKernel::simdFetchI64DataByGather(const std::unique_ptr<KernelBuilder> &b,
1932                                                                          llvm::Value *basePtr, llvm::Value *offsetVec,
1933                                                                          llvm::Value *mask) {
1934        Type* i32BitBlockTy = VectorType::get(b->getInt32Ty(), b->getBitBlockWidth() / SIMD_WIDTH);
1935        if (AVX512BW_available()) {
1936            // AVX512 gather use i8 mask
1937            //declare <8 x int> @llvm.x86.avx512.gather.dpq.512(<8 x i64>, i8*, <8 x i32>, i8, i32) #1
1938            Function *gatherFunc512 = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx512_gather_dpq_512);
1939            return b->CreateCall(
1940                    gatherFunc512,
1941                    {
1942                            UndefValue::get(b->getBitBlockType()),
1943                            basePtr,
1944                            b->CreateTrunc(offsetVec, i32BitBlockTy),
1945                            b->CreateTruncOrBitCast(b->hsimd_signmask(SIMD_WIDTH, mask), b->getInt8Ty()),
1946                            b->getInt32(1)
1947                    });
1948            // return result & i512Mask ?
1949        } else {
1950            // AVX2 gather use i256 mask
1951            Function *gatherFunc = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx2_gather_d_q_256);
1952            Value* tokenValuesVec =  b->CreateCall(
1953                    gatherFunc,
1954                    {
1955                            UndefValue::get(b->getBitBlockType()),
1956                            basePtr,
1957                            b->CreateTrunc(offsetVec, VectorType::get(b->getInt32Ty(), 4)),
1958                            mask,
1959                            b->getInt8(1)
1960                    }
1961            );
1962            tokenValuesVec = b->CreateAnd(tokenValuesVec, mask);
1963            return tokenValuesVec;
1964        }
1965    }
1966
1967    llvm::Value* LZ4ParallelByteStreamAioKernel::simdFetchDataByLoop(const std::unique_ptr<KernelBuilder> &b,
1968                                                                     llvm::Value *basePtr, llvm::Value *offsetVec,
1969                                                                     llvm::Value *maskVec, unsigned resultBitWidth) {
1970        Type* INT_TY = b->getIntNTy(resultBitWidth);
1971        Type* INT_PTR_TY = INT_TY->getPointerTo();
1972
1973        Value* placeHolderPtr = b->CreatePointerCast(b->getScalarFieldPtr("placeholder"), INT_PTR_TY);
1974        Value* retVec = ConstantVector::getNullValue(b->getBitBlockType());
1975
1976        for (uint64_t i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++){
1977            Value* mask = b->CreateExtractElement(maskVec, i);
1978            Value* shouldLoad = b->CreateICmpNE(mask, b->getInt64(0));
1979            Value* loadPtr = b->CreateSelect(shouldLoad, b->CreatePointerCast(b->CreateGEP(basePtr, b->CreateExtractElement(offsetVec, i)), INT_PTR_TY), placeHolderPtr);
1980//            Value* loadPtr = b->CreateGEP(basePtr, b->CreateExtractElement(offsetVec, i));
1981            Value* loadValue = b->CreateZExt(b->CreateLoad(loadPtr), b->getInt64Ty());
1982            Value* finalValue = b->CreateSelect(shouldLoad, loadValue, b->getInt64(0));
1983            retVec = b->CreateInsertElement(retVec, finalValue, i);
1984        }
1985
1986        return retVec;
1987    }
1988
1989    void LZ4ParallelByteStreamAioKernel::simdPutData(const std::unique_ptr<KernelBuilder> &b, llvm::Value* basePtr, llvm::Value* offsetVec,llvm::Value* values, llvm::Value* mask) {
1990        if (AVX512BW_available()) {
1991            this->simdPutDataByScatter(b, basePtr, offsetVec, values, mask);
1992        } else {
1993            this->simdPutDataByLoop(b, basePtr, offsetVec, values, mask);
1994        }
1995
1996
1997    }
1998
1999    void LZ4ParallelByteStreamAioKernel::simdPutDataByLoop(const std::unique_ptr<KernelBuilder> &b, llvm::Value* basePtr, llvm::Value* offsetVec,llvm::Value* values, llvm::Value* mask) {
2000
2001        Value* shouldStoreVec = b->CreateICmpNE(mask, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0)));
2002
2003        for (unsigned i = 0 ; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
2004            BasicBlock* conBlock = b->CreateBasicBlock("simdPutDataByLoopCon");
2005            BasicBlock* bodyBlock = b->CreateBasicBlock("simdPutDataByLoopBody");
2006            BasicBlock* exitBlock = b->CreateBasicBlock("simdPutDataByLoopExit");
2007
2008            b->CreateBr(conBlock);
2009
2010            // ---- ConBlock
2011            b->SetInsertPoint(conBlock);
2012            Value* shouldStore = b->CreateExtractElement(shouldStoreVec, i);
2013            b->CreateCondBr(shouldStore, bodyBlock, exitBlock);
2014
2015            // ---- BodyBlock
2016            b->SetInsertPoint(bodyBlock);
2017            b->CreateStore(
2018                    b->CreateExtractElement(values, i),
2019                    b->CreatePointerCast(b->CreateGEP(basePtr, b->CreateExtractElement(offsetVec, i)), b->getIntNTy(SIMD_WIDTH)->getPointerTo())
2020            );
2021
2022            b->CreateBr(exitBlock);
2023
2024            // ---- ExitBlock
2025            b->SetInsertPoint(exitBlock);
2026
2027        }
2028    }
2029    void LZ4ParallelByteStreamAioKernel::simdPutDataByScatter(const std::unique_ptr<KernelBuilder> &b, llvm::Value* basePtr, llvm::Value* offsetVec,llvm::Value* values, llvm::Value* mask) {
2030        Function *scatterFunc = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx512_scatter_dpq_512);
2031        //declare void @llvm.x86.avx512.scatter.dpq.512(i8*, i8, <8 x i32>, <8 x i64>, i32)
2032
2033        Value* i8Mask = b->CreateTruncOrBitCast(b->hsimd_signmask(SIMD_WIDTH, mask), b->getIntNTy(b->getBitBlockWidth() / SIMD_WIDTH));
2034
2035        b->CreateCall(scatterFunc, {
2036                basePtr,
2037                i8Mask,
2038                b->CreateTrunc(offsetVec, VectorType::get(b->getInt32Ty(), b->getBitBlockWidth() / SIMD_WIDTH)),
2039                values,
2040                b->getInt32(1)
2041        });
2042
2043    }
2044
2045
2046    void LZ4ParallelByteStreamAioKernel::initParallelLevelMeasurement(const std::unique_ptr<KernelBuilder> &b) {
2047        for (unsigned i = 0; i <= b->getBitBlockWidth() / SIMD_WIDTH; i++) {
2048            addScalar(b->getSizeTy(), "ParallelLevel" + std::to_string(i));
2049        }
2050    }
2051    void LZ4ParallelByteStreamAioKernel::recordParallelLevel(const std::unique_ptr<KernelBuilder> &b, llvm::Value* v) {
2052        for (unsigned i = 0; i <= b->getBitBlockWidth() / SIMD_WIDTH; i++) {
2053            auto name = "ParallelLevel" + std::to_string(i);
2054            Value* addValue = b->CreateZExt(b->CreateICmpEQ(v, b->getInt32(i)), b->getSizeTy());
2055            b->setScalarField(name, b->CreateAdd(b->getScalarField(name), addValue));
2056        }
2057    }
2058    void LZ4ParallelByteStreamAioKernel::printParallelLevelResult(const std::unique_ptr<KernelBuilder> &b) {
2059        for (unsigned i = 0; i <= b->getBitBlockWidth() / SIMD_WIDTH; i++) {
2060            auto name = "ParallelLevel" + std::to_string(i);
2061            b->CallPrintInt(name, b->getScalarField(name));
2062        }
2063    }
2064
2065}
Note: See TracBrowser for help on using the repository browser.