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

Last change on this file since 6084 was 6084, checked in by xwa163, 11 months ago

Use scatter for match copy in LZ4ParallelByteStreamAIOKernel

File size: 65.9 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, bool enableGather, bool enableScatter, size_t outputBlockSize)
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                                   }), mEnableGather(enableGather), mEnableScatter(enableScatter), mOutputBlockSize(outputBlockSize) {
49        this->setStride(4 * 1024 * 1024 * 4);
50        addAttribute(MustExplicitlyTerminate());
51    }
52
53    Value* LZ4ParallelByteStreamAioKernel::generateSimdAcceleration(const std::unique_ptr<KernelBuilder> &b, llvm::Value *beginTokenPosVec,
54                                  llvm::Value *blockEndVec) {
55        /*
56        // TODO incomplete
57        // Constant
58        Function *gatherFunc = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx2_gather_d_q_256); // TODO find ret <4 * i32> version
59//        Function *gatherFunc2 = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx2_gather_d_q);
60
61        // ---- Entry Block
62        BasicBlock* entryBlock = b->GetInsertBlock();
63        Value* maskedTokenPosVec = b->CreateAnd(beginTokenPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(b->getCapacity("extender")))));
64        Value* maskBlockIndexVec = b->CreateLShr(beginTokenPosVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, std::log2(64))));
65        Value* maskBlockOffsetVec = b->CreateAnd(beginTokenPosVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 63)));
66        Value* extenderValueVec = b->CreateCall(
67                gatherFunc,
68                {
69                        UndefValue::get(b->getBitBlockType()),
70                        b->CreatePointerCast(b->getRawInputPointer("extender", b->getSize(0)), b->getInt8PtrTy()),
71                        b->CreateTrunc(maskBlockIndexVec, VectorType::get(b->getInt32Ty(), 4)),
72                        Constant::getAllOnesValue(b->getBitBlockType()),
73                        b->getInt8(8)
74                }
75        );
76
77        Value* extenderValueVec2 = b->CreateCall(
78                gatherFunc,
79                {
80                        UndefValue::get(VectorType::get(b->getInt8Ty(), 4)),
81                        b->CreatePointerCast(b->getRawInputPointer("extender", b->getSize(0)), b->getInt8PtrTy()),
82                        b->CreateTrunc(maskBlockIndexVec, VectorType::get(b->getInt32Ty(), 4)),
83                        Constant::getAllOnesValue(b->getBitBlockType()),
84                        b->getInt8(8)
85                }
86        );
87
88        Value* initTokeMarkersVec = b->CreateShl(b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 1)), maskBlockOffsetVec);
89
90//        b->CallPrintRegister("a", beginTokenPosVec);
91//        b->CallPrintRegister("maskedTokenPosVec", maskedTokenPosVec);
92//        b->CallPrintRegister("maskBlockIndexVec", maskBlockIndexVec);
93//        b->CallPrintRegister("gather_result", extenderValueVec);
94
95
96        BasicBlock* accelerationProcessBlock = b->CreateBasicBlock("accelerationProcessBlock");
97        BasicBlock* accelerationExitBlock = b->CreateBasicBlock("accelerationExitBlock");
98        b->CreateBr(accelerationProcessBlock);
99
100        // ---- AccelerationProcessBlock
101        b->SetInsertPoint(accelerationProcessBlock);
102        PHINode* phiTokenMarkersVec = b->CreatePHI(initTokeMarkersVec->getType(), 2);
103        phiTokenMarkersVec->addIncoming(initTokeMarkersVec, entryBlock);
104*/
105        return beginTokenPosVec;    //TODO
106
107    }
108
109
110    std::pair<Value *, Value *> LZ4ParallelByteStreamAioKernel::simdProcessBlockBoundary(
111            const std::unique_ptr<KernelBuilder> &b, Value *beginTokenPosVec, Value *lz4BlockEndVec, Value* initOutputPosVec
112    ) {
113        // Constant
114        Value* const BIT_BLOCK_0 = ConstantVector::getNullValue(b->getBitBlockType());
115        Value* const BIT_BLOCK_1 = b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0x1));
116        Value* const BIT_BLOCK_F0 = b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0xf0));
117        Value* const BIT_BLOCK_0F = b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0x0f));
118        Value* const BIT_BLOCK_FF = b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0xff));
119        Value* const BIT_BLOCK_FFFF = b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0xffff));
120        Constant* const INT_BIT_BLOCK_TY_0 = b->getIntN(b->getBitBlockWidth(), 0);
121
122        // Type
123        Type* const BIT_BLOCK_TY = b->getBitBlockType();
124        Type* const INT_BIT_BLOCK_TY = b->getIntNTy(b->getBitBlockWidth());
125
126        // ---- EntryBlock
127        BasicBlock* entryBlock = b->GetInsertBlock();
128        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
129
130        Value* notFinishMask = b->simd_ult(SIMD_WIDTH, beginTokenPosVec, lz4BlockEndVec);
131
132        Value* byteRawInputPtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
133
134        Value* tokenValuesVec = this->simdFetchByteData(b, byteRawInputPtr, beginTokenPosVec, notFinishMask);
135
136        Value* shouldExtendLiteralBitBlockVec = b->CreateZExt(b->CreateICmpEQ(b->CreateAnd(BIT_BLOCK_F0, tokenValuesVec), BIT_BLOCK_F0), b->getBitBlockType());
137        Value* shouldExtendLiteral = b->CreateICmpNE(b->CreateBitCast(shouldExtendLiteralBitBlockVec, INT_BIT_BLOCK_TY), INT_BIT_BLOCK_TY_0);
138
139        Value* shouldExtendMatchBitBlockVec = b->CreateZExt(b->CreateICmpEQ(b->CreateAnd(BIT_BLOCK_0F, tokenValuesVec), BIT_BLOCK_0F), b->getBitBlockType());
140        Value* shouldExtendMatch = b->CreateICmpNE(b->CreateBitCast(shouldExtendMatchBitBlockVec, INT_BIT_BLOCK_TY), INT_BIT_BLOCK_TY_0);
141
142        Value* initExtendLiteralPos = b->simd_add(SIMD_WIDTH, beginTokenPosVec, shouldExtendLiteralBitBlockVec);
143
144        BasicBlock* extendLiteralCond = b->CreateBasicBlock("extendLiteralCond");
145        BasicBlock* extendLiteralEnd = b->CreateBasicBlock("extendLiteralEnd");
146
147        b->CreateCondBr(shouldExtendLiteral, extendLiteralCond, extendLiteralEnd);
148
149        // ---- extendLiteralCond
150        b->SetInsertPoint(extendLiteralCond);
151        PHINode* phiCurrentExtendLiteralPosVec = b->CreatePHI(initExtendLiteralPos->getType(), 2);
152        phiCurrentExtendLiteralPosVec->addIncoming(initExtendLiteralPos, entryBlock);
153
154        PHINode* phiExtendLiteralLengthVec = b->CreatePHI(BIT_BLOCK_TY, 2);
155        phiExtendLiteralLengthVec->addIncoming(BIT_BLOCK_0, entryBlock);
156
157        PHINode* phiShouldExtendLiteralBitBlockVec = b->CreatePHI(shouldExtendLiteralBitBlockVec->getType(), 2);
158        phiShouldExtendLiteralBitBlockVec->addIncoming(shouldExtendLiteralBitBlockVec, entryBlock);
159        Value* shouldExtendLiteralGatherMask = b->CreateNeg(phiShouldExtendLiteralBitBlockVec);
160        shouldExtendLiteralGatherMask = b->simd_and(shouldExtendLiteralGatherMask, notFinishMask);
161
162        // TODO maybe we can load i64 once and then consume 8 times
163        Value* currentLiteralLengthVec = this->simdFetchByteData(b, byteRawInputPtr, phiCurrentExtendLiteralPosVec, shouldExtendLiteralGatherMask);
164
165        Value* newExtendLiteralLengthVec = b->simd_add(SIMD_WIDTH, phiExtendLiteralLengthVec, currentLiteralLengthVec);
166        Value* shouldContinueExtendVecBitBlock = b->CreateZExt(b->CreateICmpEQ(currentLiteralLengthVec, BIT_BLOCK_FF), BIT_BLOCK_TY);
167        Value* newExtendLiteralPosVec = b->CreateAdd(phiCurrentExtendLiteralPosVec, b->CreateAnd(shouldExtendLiteralBitBlockVec, shouldContinueExtendVecBitBlock));
168
169        phiCurrentExtendLiteralPosVec->addIncoming(newExtendLiteralPosVec, b->GetInsertBlock());
170        phiExtendLiteralLengthVec->addIncoming(newExtendLiteralLengthVec, b->GetInsertBlock());
171        phiShouldExtendLiteralBitBlockVec->addIncoming(shouldContinueExtendVecBitBlock, b->GetInsertBlock());
172
173        Value* shouldContinueExtendLiteral = b->CreateICmpNE(b->CreateBitCast(shouldContinueExtendVecBitBlock, INT_BIT_BLOCK_TY), INT_BIT_BLOCK_TY_0);
174
175        b->CreateCondBr(shouldContinueExtendLiteral, extendLiteralCond, extendLiteralEnd);
176
177        // ---- extendLiteralEnd
178        b->SetInsertPoint(extendLiteralEnd);
179        PHINode* literalExtendValueVec = b->CreatePHI(b->getBitBlockType(), 2);
180        literalExtendValueVec->addIncoming(BIT_BLOCK_0, entryBlock);
181        literalExtendValueVec->addIncoming(newExtendLiteralLengthVec, extendLiteralCond);
182
183        PHINode* phiExtendLiteralEndPos = b->CreatePHI(b->getBitBlockType(), 2);
184        phiExtendLiteralEndPos->addIncoming(beginTokenPosVec, entryBlock);
185        phiExtendLiteralEndPos->addIncoming(phiCurrentExtendLiteralPosVec, extendLiteralCond);
186
187
188        Value* literalLengthVec = b->simd_add(SIMD_WIDTH, literalExtendValueVec, b->simd_srlv(SIMD_WIDTH, tokenValuesVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 4))));
189        Value* literalStartPosVec = b->simd_add(SIMD_WIDTH, phiExtendLiteralEndPos, BIT_BLOCK_1);
190        Value* literalEndPosVec = b->simd_add(SIMD_WIDTH, literalStartPosVec, literalLengthVec);
191
192        this->handleSimdLiteralCopy(b, literalStartPosVec, literalLengthVec, initOutputPosVec);
193        Value* outputPosAfterLiteralCpy = b->simd_add(SIMD_WIDTH, initOutputPosVec, literalLengthVec);
194
195
196        Value* matchOffsetBeginPosVec = literalEndPosVec;
197
198        Value* matchOffsetNextPosVec = b->simd_add(SIMD_WIDTH, matchOffsetBeginPosVec, BIT_BLOCK_1);
199
200
201        BasicBlock* hasMatchPartBlock = b->CreateBasicBlock("hasMatchPartBlock");
202        BasicBlock* extendMatchCon = b->CreateBasicBlock("extendMatchCon");
203        BasicBlock* extendMatchExit = b->CreateBasicBlock("extendMatchExit");
204
205        BasicBlock* extendLiteralEndFinal = b->GetInsertBlock();
206
207        Value* hasMatchPartMask = b->simd_ult(SIMD_WIDTH, matchOffsetBeginPosVec, lz4BlockEndVec);
208        b->CreateLikelyCondBr(b->CreateICmpNE(b->CreateBitCast(hasMatchPartMask, INT_BIT_BLOCK_TY), INT_BIT_BLOCK_TY_0), hasMatchPartBlock, exitBlock);
209
210        // ---- hasMatchPartBlock
211        b->SetInsertPoint(hasMatchPartBlock);
212        Value* initExtendMatchPosVec = b->simd_add(SIMD_WIDTH, matchOffsetNextPosVec, shouldExtendMatchBitBlockVec);
213        b->CreateCondBr(shouldExtendMatch, extendMatchCon, extendMatchExit);
214
215        // ---- extendMatchCon
216        b->SetInsertPoint(extendMatchCon);
217        PHINode* phiCurrentExtendMatchPosVec = b->CreatePHI(initExtendMatchPosVec->getType(), 2);
218        phiCurrentExtendMatchPosVec->addIncoming(initExtendMatchPosVec, hasMatchPartBlock);
219        PHINode* phiExtendMatchLengthVec = b->CreatePHI(b->getBitBlockType(), 2);
220        phiExtendMatchLengthVec->addIncoming(BIT_BLOCK_0, hasMatchPartBlock);
221
222        PHINode* phiShouldExtendMatchBitBlockVec = b->CreatePHI(shouldExtendMatchBitBlockVec->getType(), 2);
223        phiShouldExtendMatchBitBlockVec->addIncoming(shouldExtendMatchBitBlockVec, hasMatchPartBlock);
224        Value* shouldExtendMatchGatherMask = b->CreateNeg(phiShouldExtendMatchBitBlockVec);
225        shouldExtendMatchGatherMask = b->simd_and(shouldExtendMatchGatherMask, notFinishMask);
226        // TODO maybe we can load i64 once and then consume 8 times
227
228        Value* currentMatchLengthVec = this->simdFetchByteData(b, byteRawInputPtr, phiCurrentExtendMatchPosVec, shouldExtendMatchGatherMask);
229
230        Value* newExtendMatchLengthVec = b->simd_add(SIMD_WIDTH, phiExtendMatchLengthVec, currentMatchLengthVec);
231
232        Value* shouldContinueExtendMatchVecBitBlock = b->CreateZExt(b->CreateICmpEQ(currentMatchLengthVec, BIT_BLOCK_FF), b->getBitBlockType());
233        Value* newExtendMatchPosVec = b->simd_add(SIMD_WIDTH, phiCurrentExtendMatchPosVec, b->simd_and(shouldExtendMatchBitBlockVec, shouldContinueExtendMatchVecBitBlock));
234
235        phiCurrentExtendMatchPosVec->addIncoming(newExtendMatchPosVec, b->GetInsertBlock());
236        phiExtendMatchLengthVec->addIncoming(newExtendMatchLengthVec, b->GetInsertBlock());
237
238        phiShouldExtendMatchBitBlockVec->addIncoming(shouldContinueExtendMatchVecBitBlock, b->GetInsertBlock());
239        Value* shouldContinueExtendMatch = b->CreateICmpNE(b->CreateBitCast(shouldContinueExtendMatchVecBitBlock, INT_BIT_BLOCK_TY), INT_BIT_BLOCK_TY_0);
240
241        b->CreateCondBr(shouldContinueExtendMatch, extendMatchCon, extendMatchExit);
242
243
244        // ---- extendMatchExit
245        b->SetInsertPoint(extendMatchExit);
246
247        PHINode* matchExtendValueVec = b->CreatePHI(newExtendMatchLengthVec->getType(), 2);
248        matchExtendValueVec->addIncoming(BIT_BLOCK_0, hasMatchPartBlock);
249        matchExtendValueVec->addIncoming(newExtendMatchLengthVec, extendMatchCon);
250        PHINode* phiExtendMatchEndPos = b->CreatePHI(matchOffsetNextPosVec->getType(), 2);
251        phiExtendMatchEndPos->addIncoming(matchOffsetNextPosVec, hasMatchPartBlock);
252        phiExtendMatchEndPos->addIncoming(phiCurrentExtendMatchPosVec, extendMatchCon);
253
254
255        // matchLength = (size_t)token & 0xf + 4 + matchExtendValue
256        Value* matchLength = b->simd_add(
257                SIMD_WIDTH,
258                b->simd_add(SIMD_WIDTH, matchExtendValueVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 4))),
259                b->simd_and(tokenValuesVec, BIT_BLOCK_0F)
260        );
261        matchLength = b->simd_and(matchLength, hasMatchPartMask);
262
263        Value* matchOffsetVec = this->simdFetchData(
264                b,
265                byteRawInputPtr,
266                matchOffsetBeginPosVec,
267                hasMatchPartMask
268        );
269        matchOffsetVec = b->simd_and(matchOffsetVec, BIT_BLOCK_FFFF);
270
271        this->handleSimdMatchCopy(b, matchOffsetVec, matchLength, outputPosAfterLiteralCpy);
272
273        Value* outputPosAfterMatchCpy = b->simd_add(SIMD_WIDTH, outputPosAfterLiteralCpy, matchLength);
274
275        BasicBlock* extendMatchExitFinal = b->GetInsertBlock();
276
277        b->CreateBr(exitBlock);
278        // ---- exitBlock
279
280        b->SetInsertPoint(exitBlock);
281
282        PHINode* phiBeforeTokenPos = b->CreatePHI(matchOffsetNextPosVec->getType(), 2);
283        phiBeforeTokenPos->addIncoming(matchOffsetNextPosVec, extendLiteralEndFinal);
284        phiBeforeTokenPos->addIncoming(phiExtendMatchEndPos, extendMatchExitFinal);
285
286        PHINode* phiNewOutputPos = b->CreatePHI(outputPosAfterLiteralCpy->getType(), 2);
287        phiNewOutputPos->addIncoming(outputPosAfterLiteralCpy, extendLiteralEndFinal);
288        phiNewOutputPos->addIncoming(outputPosAfterMatchCpy, extendMatchExitFinal);
289        Value* nextTokenPos = b->simd_add(SIMD_WIDTH, phiBeforeTokenPos, BIT_BLOCK_1);
290        return std::make_pair(nextTokenPos, phiNewOutputPos);
291    }
292
293    void LZ4ParallelByteStreamAioKernel::generateSimdDecompression(const std::unique_ptr<KernelBuilder> &b, Value* blockDataIndex) {
294        BasicBlock* entryBlock = b->GetInsertBlock();
295        BasicBlock* exitBlock = b->CreateBasicBlock("simdDecompressionExitBlock");
296        BasicBlock* processCon = b->CreateBasicBlock("simdDecompressionProcessConBlock");
297        BasicBlock* processBody = b->CreateBasicBlock("simdDecompressionProcessBodyBlock");
298
299        // ---- entryBlock
300        Value* blockStartVec = this->generateLoadSimdInt64NumberInput(b, "blockStart", blockDataIndex);
301        Value* blockEndVec = this->generateLoadSimdInt64NumberInput(b, "blockEnd", blockDataIndex);
302
303        Value* outputPos = b->getProducedItemCount("outputStream");
304        Value* initOutputPosVec = b->simd_fill(SIMD_WIDTH, outputPos);
305        std::vector<Constant*> initOutputOffset;
306        for (unsigned i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
307            initOutputOffset.push_back(b->getIntN(SIMD_WIDTH, i * 4 * 1024 * 1024));
308        }
309
310        initOutputPosVec = b->simd_add(SIMD_WIDTH, initOutputPosVec, ConstantVector::get(initOutputOffset));
311
312        // TODO handle uncompression blocks
313
314        b->CreateBr(processCon);
315
316        // ---- processCon
317        b->SetInsertPoint(processCon);
318        PHINode* phiCursorVec = b->CreatePHI(blockStartVec->getType(), 2);
319        phiCursorVec->addIncoming(blockStartVec, entryBlock);
320
321        PHINode* phiOutputPosVec = b->CreatePHI(initOutputPosVec->getType(), 2);
322        phiOutputPosVec->addIncoming(initOutputPosVec, entryBlock);
323
324
325        Value* hasRemaining = b->simd_ult(SIMD_WIDTH, phiCursorVec, blockEndVec);
326
327        hasRemaining = b->CreateICmpNE(b->CreateBitCast(hasRemaining, b->getIntNTy(b->getBitBlockWidth())), Constant::getNullValue(b->getIntNTy(b->getBitBlockWidth())));
328
329        b->CreateCondBr(hasRemaining, processBody, exitBlock);
330
331        // ---- processBody
332        b->SetInsertPoint(processBody);
333//        Value* newCursorVec = this->generateSimdAcceleration(b, phiCursorVec, blockEndVec);
334
335        Value *newCursorVec = nullptr, *newOutputPosVec = nullptr;
336        std::tie(newCursorVec, newOutputPosVec) = this->simdProcessBlockBoundary(b, phiCursorVec, blockEndVec, phiOutputPosVec);
337
338        phiCursorVec->addIncoming(newCursorVec, b->GetInsertBlock());
339        phiOutputPosVec->addIncoming(newOutputPosVec, b->GetInsertBlock());
340
341        b->CreateBr(processCon);
342
343        // ---- exitBlock
344        b->SetInsertPoint(exitBlock);
345
346        uint64_t lastVecIndex = b->getBitBlockWidth() / SIMD_WIDTH - 1;
347        Value* lastBlockEnd = b->CreateExtractElement(blockEndVec, lastVecIndex);
348        b->setProcessedItemCount("byteStream", lastBlockEnd);
349        Value* lastOutputPos = b->CreateExtractElement(phiOutputPosVec, lastVecIndex);
350        b->setProducedItemCount("outputStream", lastOutputPos);
351    }
352
353    void LZ4ParallelByteStreamAioKernel::generateDoSegmentMethod(const std::unique_ptr<KernelBuilder> &b) {
354        // Constant
355        Value* SIZE_1 = b->getSize(1);
356
357        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
358
359        Value * blockDataIndex = b->getProcessedItemCount("isCompressed");
360        Value * totalNumber = b->getAvailableItemCount("isCompressed");
361//        b->CallPrintInt("totalNumber", totalNumber);
362        Value * fileSize = b->getScalarField("fileSize");
363        Value * availableNumber = b->CreateSub(totalNumber, blockDataIndex);
364        Value * lastBlockEnd = this->generateLoadInt64NumberInput(b, "blockEnd", b->CreateSub(totalNumber, SIZE_1));
365        Value * isTerminal = b->CreateAnd(b->CreateICmpEQ(fileSize, lastBlockEnd), b->CreateICmpULE(availableNumber, b->getSize(b->getBitBlockWidth() / SIMD_WIDTH)));
366        b->setTerminationSignal(isTerminal);
367
368        BasicBlock* simdProcessEntryBlock = b->CreateBasicBlock("simdProcessEntryBlock");
369        BasicBlock* notEnoughSimdDataBlock = b->CreateBasicBlock("notEnoughSimdDataBlock");
370
371        b->CreateLikelyCondBr(b->CreateICmpUGE(availableNumber, b->getSize(b->getBitBlockWidth() / SIMD_WIDTH)), simdProcessEntryBlock, notEnoughSimdDataBlock);
372
373        // ---- simdProcessEntryBlock
374        b->SetInsertPoint(simdProcessEntryBlock);
375        this->generateSimdDecompression(b, blockDataIndex);
376        Value* newProcessedDataIndex = b->CreateAdd(blockDataIndex, b->getSize(b->getBitBlockWidth() / SIMD_WIDTH));
377        b->setProcessedItemCount("isCompressed", newProcessedDataIndex);
378
379        b->CreateBr(exitBlock);
380
381        // ---- notEnoughSimdDataBlock
382        b->SetInsertPoint(notEnoughSimdDataBlock);
383
384        BasicBlock* notSimdProcessBlock = b->CreateBasicBlock("notSimdProcessBlock");
385        b->CreateUnlikelyCondBr(isTerminal, notSimdProcessBlock, exitBlock);
386
387        // ---- notSimdProcessBlock
388        b->SetInsertPoint(notSimdProcessBlock);
389        // Use loop to process the remaining block in sequential approach (the number of the remaining block should be less than (b->getBitBlockWidth() / SIMD_WIDTH))
390        this->generateSequentialDecompression(b, blockDataIndex, totalNumber);
391        b->CreateBr(exitBlock);
392
393
394        // ---- ExitBlock
395        b->SetInsertPoint(exitBlock);
396    }
397
398    void LZ4ParallelByteStreamAioKernel::generateSequentialDecompression(const std::unique_ptr<KernelBuilder> &b, llvm::Value* startBlockDataIndex, llvm::Value* endBlockDataIndex) {
399
400        // ---- EntryBlock
401        BasicBlock* entryBlock = b->GetInsertBlock();
402
403        BasicBlock* SequentialConBlock = b->CreateBasicBlock("SequentialConBlock");
404        BasicBlock* SequentialBodyBlock = b->CreateBasicBlock("SequentialBodyBlock");
405        BasicBlock* SequentialExitBlock = b->CreateBasicBlock("SequentialExitBlock");
406
407
408        Value* initOutputPos = b->getProducedItemCount("outputStream");
409
410        b->CreateBr(SequentialConBlock);
411
412        // ---- SequentialConBlock
413        b->SetInsertPoint(SequentialConBlock);
414        PHINode* phiCurrentBlockDataIndex = b->CreatePHI(b->getSizeTy(), 2);
415        phiCurrentBlockDataIndex->addIncoming(startBlockDataIndex, entryBlock);
416        PHINode* phiOutputPos = b->CreatePHI(b->getSizeTy(), 2);
417        phiOutputPos->addIncoming(initOutputPos, entryBlock);
418
419        b->CreateCondBr(b->CreateICmpULT(phiCurrentBlockDataIndex, endBlockDataIndex), SequentialBodyBlock, SequentialExitBlock);
420
421        // ---- SequentialBodyBlock
422        b->SetInsertPoint(SequentialBodyBlock);
423        Value* lz4BlockStart = this->generateLoadInt64NumberInput(b, "blockStart", phiCurrentBlockDataIndex);
424        Value* lz4BlockEnd = this->generateLoadInt64NumberInput(b, "blockEnd", phiCurrentBlockDataIndex);
425        Value* newOutputPos = this->generateProcessCompressedBlock(b, lz4BlockStart, lz4BlockEnd, phiOutputPos);
426
427        b->setProcessedItemCount("byteStream", lz4BlockEnd);
428        b->setProducedItemCount("outputStream", newOutputPos);
429
430        phiCurrentBlockDataIndex->addIncoming(b->CreateAdd(phiCurrentBlockDataIndex, b->getSize(1)), b->GetInsertBlock());
431        phiOutputPos->addIncoming(newOutputPos, b->GetInsertBlock());
432
433        b->CreateBr(SequentialConBlock);
434
435        // ---- SequentialExitBlock
436        b->SetInsertPoint(SequentialExitBlock);
437        b->setProcessedItemCount("isCompressed", endBlockDataIndex);
438
439    }
440
441    llvm::Value *
442    LZ4ParallelByteStreamAioKernel::generateLoadSimdInt64NumberInput(const std::unique_ptr<KernelBuilder> &iBuilder, std::string inputBufferName,
443                                     llvm::Value *globalOffset) {
444        Value * capacity = iBuilder->getCapacity(inputBufferName);
445        Value * processed = iBuilder->getProcessedItemCount(inputBufferName);
446        processed = iBuilder->CreateAnd(processed, iBuilder->CreateNeg(capacity));
447        Value * offset = iBuilder->CreateSub(globalOffset, processed);
448        Value * valuePtr = iBuilder->getRawInputPointer(inputBufferName, offset);
449        valuePtr = iBuilder->CreatePointerCast(valuePtr, iBuilder->getBitBlockType()->getPointerTo());
450        return iBuilder->CreateLoad(valuePtr);
451    }
452
453    llvm::Value *LZ4ParallelByteStreamAioKernel::generateLoadInt64NumberInput(const std::unique_ptr<KernelBuilder> &iBuilder,
454                                                                      std::string inputBufferName, llvm::Value *globalOffset) {
455
456        Value * capacity = iBuilder->getCapacity(inputBufferName);
457        Value * processed = iBuilder->getProcessedItemCount(inputBufferName);
458        processed = iBuilder->CreateAnd(processed, iBuilder->CreateNeg(capacity));
459        Value * offset = iBuilder->CreateSub(globalOffset, processed);
460        Value * valuePtr = iBuilder->getRawInputPointer(inputBufferName, offset);
461        return iBuilder->CreateLoad(valuePtr);
462    }
463
464    llvm::Value*
465    LZ4ParallelByteStreamAioKernel::generateProcessCompressedBlock(const std::unique_ptr<KernelBuilder> &b, llvm::Value *lz4BlockStart,
466                                                           llvm::Value *lz4BlockEnd, llvm::Value* initOutputPos) {
467        BasicBlock* entryBlock = b->GetInsertBlock();
468
469        Value* isTerminal = b->CreateICmpEQ(lz4BlockEnd, b->getScalarField("fileSize"));
470        b->setTerminationSignal(isTerminal);
471
472        BasicBlock* exitBlock = b->CreateBasicBlock("processCompressedExitBlock");
473
474        BasicBlock* processCon = b->CreateBasicBlock("processCompressedConBlock");
475        BasicBlock* processBody = b->CreateBasicBlock("processCompressedBodyBlock");
476
477
478        BasicBlock* beforeProcessConBlock = b->GetInsertBlock();
479        b->CreateBr(processCon);
480        b->SetInsertPoint(processCon);
481        PHINode* phiOutputPos = b->CreatePHI(initOutputPos->getType(), 2);
482        phiOutputPos->addIncoming(initOutputPos, entryBlock);
483        PHINode* phiCursorValue = b->CreatePHI(b->getInt64Ty(), 2); // phiCursorValue should always be the position of next token except for the final sequence
484        phiCursorValue->addIncoming(lz4BlockStart, beforeProcessConBlock);
485
486        b->CreateCondBr(b->CreateICmpULT(phiCursorValue, lz4BlockEnd), processBody, exitBlock);
487
488        b->SetInsertPoint(processBody);
489
490
491        auto ret = this->processBlockBoundary(b, phiCursorValue, lz4BlockEnd, phiOutputPos);
492        Value* nextTokenGlobalPos = ret.first;
493        Value* nextOutputPos = ret.second;
494
495        phiOutputPos->addIncoming(nextOutputPos, b->GetInsertBlock());
496        phiCursorValue->addIncoming(nextTokenGlobalPos, b->GetInsertBlock());
497        b->CreateBr(processCon);
498
499        b->SetInsertPoint(exitBlock);
500        return phiOutputPos;
501    }
502
503
504    std::pair<llvm::Value *, llvm::Value *> LZ4ParallelByteStreamAioKernel::processBlockBoundary(const std::unique_ptr<KernelBuilder> &b, llvm::Value *beginTokenPos,
505                                                              llvm::Value *lz4BlockEnd, llvm::Value* initOutputPos) {
506        // Constant
507        ConstantInt* SIZE_0 = b->getSize(0);
508        ConstantInt* SIZE_1 = b->getSize(1);
509        ConstantInt* BYTE_FF = b->getInt8(0xff);
510        Value* BYTE_F0 = b->getInt8(0xf0);
511        Value* BYTE_0F = b->getInt8(0x0f);
512
513        // ---- EntryBlock
514        BasicBlock* entryBlock = b->GetInsertBlock();
515        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
516
517        Value* bytePtrBase = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
518
519        Value* tokenValue = b->CreateLoad(b->CreateGEP(bytePtrBase, beginTokenPos));
520
521        Value* shouldExtendLiteral = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_F0), BYTE_F0);
522
523        Value* shouldExtendMatch = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_0F), BYTE_0F);
524
525        BasicBlock* extendLiteralCond = b->CreateBasicBlock("extendLiteralCond");
526        BasicBlock* extendLiteralEnd = b->CreateBasicBlock("extendLiteralEnd");
527
528        Value* initExtendLiteralPos = b->CreateAdd(beginTokenPos, b->getSize(1));
529
530        b->CreateCondBr(shouldExtendLiteral, extendLiteralCond, extendLiteralEnd);
531
532        // ---- extendLiteralCond
533        b->SetInsertPoint(extendLiteralCond);
534        PHINode* phiCurrentExtendLiteralPos = b->CreatePHI(b->getSizeTy(), 2);
535        phiCurrentExtendLiteralPos->addIncoming(initExtendLiteralPos, entryBlock);
536        PHINode* phiExtendLiteralLength = b->CreatePHI(b->getSizeTy(), 2);
537        phiExtendLiteralLength->addIncoming(SIZE_0, entryBlock);
538
539        Value* currentLiteralLengthByte = b->CreateLoad(b->CreateGEP(bytePtrBase, phiCurrentExtendLiteralPos));
540        Value* newExtendLiteralLength = b->CreateAdd(phiExtendLiteralLength, b->CreateZExt(currentLiteralLengthByte, b->getSizeTy()));
541
542        phiCurrentExtendLiteralPos->addIncoming(b->CreateAdd(phiCurrentExtendLiteralPos, SIZE_1), b->GetInsertBlock());
543        phiExtendLiteralLength->addIncoming(newExtendLiteralLength, b->GetInsertBlock());
544
545        b->CreateCondBr(b->CreateICmpEQ(currentLiteralLengthByte, BYTE_FF), extendLiteralCond, extendLiteralEnd);
546
547        // ---- extendLiteralEnd
548        b->SetInsertPoint(extendLiteralEnd);
549        PHINode* literalExtendValue = b->CreatePHI(b->getSizeTy(), 2);
550        literalExtendValue->addIncoming(SIZE_0, entryBlock);
551        literalExtendValue->addIncoming(newExtendLiteralLength, extendLiteralCond);
552        PHINode* phiExtendLiteralEndPos = b->CreatePHI(b->getSizeTy(), 2);
553        phiExtendLiteralEndPos->addIncoming(beginTokenPos, entryBlock);
554        phiExtendLiteralEndPos->addIncoming(phiCurrentExtendLiteralPos, extendLiteralCond);
555
556        Value* literalLength = b->CreateAdd(literalExtendValue, b->CreateZExt(b->CreateLShr(tokenValue, b->getInt8(4)), b->getSizeTy()));
557
558        Value* literalStartPos = b->CreateAdd(phiExtendLiteralEndPos, SIZE_1);
559        Value* literalEndPos = b->CreateAdd(literalStartPos, literalLength);
560
561        Value* matchOffsetBeginPos = literalEndPos;
562        Value* matchOffsetNextPos = b->CreateAdd(matchOffsetBeginPos, SIZE_1);
563
564        BasicBlock* hasMatchPartBlock = b->CreateBasicBlock("hasMatchPartBlock");
565        BasicBlock* extendMatchCon = b->CreateBasicBlock("extendMatchCon");
566        BasicBlock* extendMatchExit = b->CreateBasicBlock("extendMatchExit");
567
568        // This literal copy will always cross 64 bits literal boundary
569        this->handleLiteralCopy(b, literalStartPos, literalLength, initOutputPos);
570
571        Value* outputPosAfterLiteralCpy = b->CreateAdd(literalLength, initOutputPos);
572
573        BasicBlock* extendLiteralEndFinal = b->GetInsertBlock();
574
575        b->CreateLikelyCondBr(b->CreateICmpULT(matchOffsetBeginPos, lz4BlockEnd), hasMatchPartBlock, exitBlock);
576
577        // ---- hasMatchPartBlock
578        b->SetInsertPoint(hasMatchPartBlock);
579        Value* initExtendMatchPos = b->CreateAdd(matchOffsetBeginPos, b->getSize(2));
580        b->CreateCondBr(shouldExtendMatch, extendMatchCon, extendMatchExit);
581
582        // ---- extendMatchCon
583        b->SetInsertPoint(extendMatchCon);
584        PHINode* phiCurrentExtendMatchPos = b->CreatePHI(b->getSizeTy(), 2);
585        phiCurrentExtendMatchPos->addIncoming(initExtendMatchPos, hasMatchPartBlock);
586        PHINode* phiExtendMatchLength = b->CreatePHI(b->getSizeTy(), 2);
587        phiExtendMatchLength->addIncoming(SIZE_0, hasMatchPartBlock);
588
589        Value* currentMatchLengthByte = b->CreateLoad(b->CreateGEP(bytePtrBase, phiCurrentExtendMatchPos));
590        Value* newExtendMatchLength = b->CreateAdd(phiExtendMatchLength, b->CreateZExt(currentMatchLengthByte, b->getSizeTy()));
591
592        phiCurrentExtendMatchPos->addIncoming(b->CreateAdd(phiCurrentExtendMatchPos, SIZE_1), b->GetInsertBlock());
593        phiExtendMatchLength->addIncoming(newExtendMatchLength, b->GetInsertBlock());
594
595        b->CreateCondBr(b->CreateICmpEQ(currentMatchLengthByte, BYTE_FF), extendMatchCon, extendMatchExit);
596
597        // ---- extendMatchExit
598        b->SetInsertPoint(extendMatchExit);
599        PHINode* matchExtendValue = b->CreatePHI(b->getSizeTy(), 2);
600        matchExtendValue->addIncoming(SIZE_0, hasMatchPartBlock);
601        matchExtendValue->addIncoming(newExtendMatchLength, extendMatchCon);
602        PHINode* phiExtendMatchEndPos = b->CreatePHI(b->getSizeTy(), 2);
603        phiExtendMatchEndPos->addIncoming(matchOffsetNextPos, hasMatchPartBlock);
604        phiExtendMatchEndPos->addIncoming(phiCurrentExtendMatchPos, extendMatchCon);
605
606        // matchLength = (size_t)token & 0xf + 4 + matchExtendValue
607        Value* matchLength = b->CreateAdd(
608                b->CreateAdd(matchExtendValue, b->getSize(4)),
609                b->CreateZExt(b->CreateAnd(tokenValue, BYTE_0F), b->getSizeTy())
610        );
611
612        Value* matchOffsetPtr = b->getRawInputPointer("byteStream", matchOffsetBeginPos);
613        // For now, it is safe to cast matchOffset pointer into i16 since the input byte stream is always linear available
614        matchOffsetPtr = b->CreatePointerCast(matchOffsetPtr, b->getInt16Ty()->getPointerTo());
615        Value* matchOffset = b->CreateZExt(b->CreateLoad(matchOffsetPtr), b->getSizeTy());
616        this->handleMatchCopy(b, matchOffset, matchLength, outputPosAfterLiteralCpy);
617        Value* outputPosAfterMatchCpy = b->CreateAdd(outputPosAfterLiteralCpy, matchLength);
618        BasicBlock* extendMatchExitFinal = b->GetInsertBlock();
619        b->CreateBr(exitBlock);
620
621        // ---- exitBlock
622        b->SetInsertPoint(exitBlock);
623        PHINode* phiBeforeTokenPos = b->CreatePHI(b->getSizeTy(), 2);
624        phiBeforeTokenPos->addIncoming(matchOffsetNextPos, extendLiteralEndFinal);
625        phiBeforeTokenPos->addIncoming(phiExtendMatchEndPos, extendMatchExitFinal);
626        PHINode* phiOutputPos = b->CreatePHI(b->getSizeTy(), 2);
627        phiOutputPos->addIncoming(outputPosAfterLiteralCpy, extendLiteralEndFinal);
628        phiOutputPos->addIncoming(outputPosAfterMatchCpy, extendMatchExitFinal);
629
630        Value* nextTokenPos = b->CreateAdd(phiBeforeTokenPos, SIZE_1);
631
632        return std::make_pair(nextTokenPos, phiOutputPos);
633    }
634
635    void LZ4ParallelByteStreamAioKernel::generateSimdMatchCopyByScatter(const std::unique_ptr<KernelBuilder> &b, llvm::Value* matchOffsetVec, llvm::Value* matchLengthVec, llvm::Value* outputPosVec) {
636        // ---- EntryBlock
637        BasicBlock* entryBlock = b->GetInsertBlock();
638        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
639        BasicBlock* i64MatchCopyBlock = b->CreateBasicBlock("i64MatchCopyBlock");
640        BasicBlock* i8MatchCopyBlock = b->CreateBasicBlock("i8MatchCopyBlock");
641
642        llvm::Value* initCopiedLength = ConstantVector::getNullValue(matchLengthVec->getType());
643
644//        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
645        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", b->getSize(0)), b->getInt8PtrTy());
646
647        Value* outputCapacity = b->getCapacity("outputStream");
648        Value* outputPosRemVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(outputCapacity))));
649        Value* outputPosRemBlockSizeVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(b->getIntN(SIMD_WIDTH, mOutputBlockSize)))));
650        Value* remainingBlockSizeVec = b->simd_sub(SIMD_WIDTH, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, mOutputBlockSize)), outputPosRemBlockSizeVec);
651
652        Value* possibleExceedBuffer = b->simd_uge(SIMD_WIDTH, b->simd_add(SIMD_WIDTH, matchLengthVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 8))), remainingBlockSizeVec);
653        // true ffff, false 0000
654
655        // TODO handle matchLengthVec == 0
656
657        b->CreateUnlikelyCondBr(
658                b->CreateICmpNE(b->CreateBitCast(possibleExceedBuffer, b->getIntNTy(b->getBitBlockWidth())), b->getIntN(b->getBitBlockWidth(), 0)),
659                i8MatchCopyBlock,
660                i64MatchCopyBlock
661        );
662
663        // ---- i8MatchCopyBlock
664        b->SetInsertPoint(i8MatchCopyBlock);
665        this->generateSimdSequentialMatchCopy(b, matchOffsetVec, matchLengthVec, outputPosVec);
666        b->CreateBr(exitBlock);
667
668        // ---- i64MatchCopyBlock
669        b->SetInsertPoint(i64MatchCopyBlock);
670
671        BasicBlock* i64MatchCopyConBlock = b->CreateBasicBlock("i64MatchCopyConBlock");
672        BasicBlock* i64MatchCopyBodyBlock = b->CreateBasicBlock("i64MatchCopyBodyBlock");
673
674        b->CreateBr(i64MatchCopyConBlock);
675
676        // ---- i64MatchCopyConBlock
677        b->SetInsertPoint(i64MatchCopyConBlock);
678        PHINode* phiCopiedLength = b->CreatePHI(initCopiedLength->getType(), 2);
679        phiCopiedLength->addIncoming(initCopiedLength, i64MatchCopyBlock);
680
681        Value* shouldCopiedBitBlock = b->simd_ult(SIMD_WIDTH, phiCopiedLength, matchLengthVec);
682//        b->CallPrintRegister("phiCopiedLength", phiCopiedLength);
683//        b->CallPrintRegister("literalLengthVec", literalLengthVec);
684//        b->CallPrintRegister("shouldCopiedBitBlock", shouldCopiedBitBlock);
685        Value* shouldCopiedI1 = b->CreateICmpNE(
686                b->CreateBitCast(shouldCopiedBitBlock, b->getIntNTy(b->getBitBlockWidth())),
687                b->getIntN(b->getBitBlockWidth(), 0)
688        );
689
690
691        b->CreateCondBr(shouldCopiedI1, i64MatchCopyBodyBlock, exitBlock);
692
693        // ---- i64MatchCopyBodyBlock
694        b->SetInsertPoint(i64MatchCopyBodyBlock);
695        Value* currentOutputPosVec = b->simd_add(SIMD_WIDTH, outputPosRemVec, phiCopiedLength);
696        Value* copyFromPosVec = b->simd_sub(SIMD_WIDTH, currentOutputPosVec, matchOffsetVec);
697
698        Value* literalData = this->simdFetchI64DataByGather(b, outputBasePtr, copyFromPosVec, shouldCopiedBitBlock);
699
700        this->simdPutData(
701                b,
702                outputBasePtr,
703                currentOutputPosVec,
704                literalData,
705                shouldCopiedBitBlock
706        );
707        phiCopiedLength->addIncoming(
708                b->simd_add(
709                        SIMD_WIDTH,
710                        phiCopiedLength,
711                        b->simd_and(
712                                b->simd_umin(SIMD_WIDTH, matchOffsetVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 8))),
713                                shouldCopiedBitBlock
714                        )
715
716                ),
717                b->GetInsertBlock()
718        );
719
720        b->CreateBr(i64MatchCopyConBlock);
721        b->SetInsertPoint(exitBlock);
722
723    }
724
725    void LZ4ParallelByteStreamAioKernel::generateSimdSequentialMatchCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value* matchOffsetVec, llvm::Value* matchLengthVec, llvm::Value* outputPosVec) {
726        // Constant
727        Constant * SIZE_8 = b->getSize(8);
728        // Type
729        PointerType* i64PtrTy = b->getInt64Ty()->getPointerTo();
730        PointerType* i8PtrTy = b->getInt8PtrTy();
731
732        Value* outputCapacity = b->getCapacity("outputStream");
733        Value* outputPosRemVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(outputCapacity))));
734        Value* outputPosRemBlockSizeVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(b->getIntN(SIMD_WIDTH, mOutputBlockSize)))));
735        Value* remainingBlockSizeVec = b->simd_sub(SIMD_WIDTH, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, mOutputBlockSize)), outputPosRemBlockSizeVec);
736        Value* copyFromPosRemVec = b->simd_sub(SIMD_WIDTH, outputPosRemVec, matchOffsetVec);
737
738
739        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", b->getSize(0)), b->getInt8PtrTy());
740
741
742        for (unsigned i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
743
744            BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
745            BasicBlock* i64MatchCopyBlock = b->CreateBasicBlock("i64LiteralCopyBlock");
746            BasicBlock* i8MatchCopyBlock = b->CreateBasicBlock("i8LiteralCopyBlock");
747
748            // ---- entryBlock
749            Value* matchOffset = b->CreateExtractElement(matchOffsetVec, i);
750            Value* matchLength = b->CreateExtractElement(matchLengthVec, i);
751            Value* outputPosRem = b->CreateExtractElement(outputPosRemVec, i);
752            Value* remainingBlockSize = b->CreateExtractElement(remainingBlockSizeVec, i);
753            Value* outputFromRem = b->CreateExtractElement(copyFromPosRemVec, i);
754
755            Value* inputInitPtr = b->CreateGEP(outputBasePtr, outputFromRem);
756            Value* outputInitPtr = b->CreateGEP(outputBasePtr, outputPosRem);
757
758            b->CreateLikelyCondBr(b->CreateICmpUGE(b->CreateSub(remainingBlockSize, matchLength), SIZE_8), i64MatchCopyBlock, i8MatchCopyBlock);
759
760            //// i64 Match Copy
761            // ---- i64MatchCopyBlock
762            b->SetInsertPoint(i64MatchCopyBlock);
763
764            this->generateOverwritingMemcpy(b, inputInitPtr, outputInitPtr, matchLength, i64PtrTy, b->CreateUMin(matchOffset, SIZE_8));
765            b->CreateBr(exitBlock);
766
767            //// i8 Match Copy
768            // ---- i8MatchCopyBlock
769            b->SetInsertPoint(i8MatchCopyBlock);
770            this->generateOverwritingMemcpy(b, inputInitPtr, outputInitPtr, matchLength, i8PtrTy, 1);
771            b->CreateBr(exitBlock);
772
773            // ---- exitBlock
774            b->SetInsertPoint(exitBlock);
775
776        }
777
778    }
779
780    void LZ4ParallelByteStreamAioKernel::handleSimdMatchCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value* matchOffsetVec, llvm::Value* matchLengthVec, llvm::Value* outputPosVec) {
781        if (AVX512BW_available() && mEnableScatter) {
782            this->generateSimdMatchCopyByScatter(b, matchOffsetVec, matchLengthVec, outputPosVec);
783        } else {
784            this->generateSimdSequentialMatchCopy(b, matchOffsetVec, matchLengthVec, outputPosVec);
785        }
786    }
787
788    void LZ4ParallelByteStreamAioKernel::handleSimdLiteralCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value* literalStartVec, llvm::Value* literalLengthVec, llvm::Value* outputPosVec) {
789        if (AVX512BW_available() && mEnableScatter) {
790            this->generateSimdLiteralCopyByScatter(b, literalStartVec, literalLengthVec, outputPosVec);
791        } else {
792            this->generateSimdSequentialLiteralCopy(b, literalStartVec, literalLengthVec, outputPosVec);
793        }
794    }
795
796    void LZ4ParallelByteStreamAioKernel::generateSimdSequentialLiteralCopy(const std::unique_ptr<KernelBuilder> &b,
797                                                                           llvm::Value *literalStartVec,
798                                                                           llvm::Value *literalLengthVec,
799                                                                           llvm::Value *outputPosVec) {
800        // Constant
801        Constant * SIZE_8 = b->getSize(8);
802        // Type
803        PointerType* i64PtrTy = b->getInt64Ty()->getPointerTo();
804        PointerType* i8PtrTy = b->getInt8PtrTy();
805
806        Value* outputCapacity = b->getCapacity("outputStream");
807        Value* outputPosRemVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(outputCapacity))));
808        Value* outputPosRemBlockSizeVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(b->getIntN(SIMD_WIDTH, mOutputBlockSize)))));
809        Value* remainingBlockSizeVec = b->simd_sub(SIMD_WIDTH, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, mOutputBlockSize)), outputPosRemBlockSizeVec);
810
811        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
812        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", b->getSize(0)), b->getInt8PtrTy());
813
814
815        for (unsigned i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
816            BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
817            BasicBlock* i64LiteralCopyBlock = b->CreateBasicBlock("i64LiteralCopyBlock");
818            BasicBlock* i8LiteralCopyBlock = b->CreateBasicBlock("i8LiteralCopyBlock");
819
820            // ---- entryBlock
821            Value* literalStart = b->CreateExtractElement(literalStartVec, i);
822            Value* literalLength = b->CreateExtractElement(literalLengthVec, i);
823            Value* outputPosRem = b->CreateExtractElement(outputPosRemVec, i);
824            Value* remainingBlockSize = b->CreateExtractElement(remainingBlockSizeVec, i);
825
826            Value* inputInitPtr = b->CreateGEP(inputBasePtr, literalStart);
827            Value* outputInitPtr = b->CreateGEP(outputBasePtr, outputPosRem);
828
829            b->CreateLikelyCondBr(b->CreateICmpUGE(b->CreateSub(remainingBlockSize, literalLength), SIZE_8), i64LiteralCopyBlock, i8LiteralCopyBlock);
830
831            //// i64 Literal Copy
832            // ---- i64LiteralCopyBlock
833            b->SetInsertPoint(i64LiteralCopyBlock);
834            this->generateOverwritingMemcpy(b, inputInitPtr, outputInitPtr, literalLength, i64PtrTy, 8);
835            b->CreateBr(exitBlock);
836
837            //// i8 Literal Copy
838            // ---- i8LiteralCopyBlock
839            b->SetInsertPoint(i8LiteralCopyBlock);
840            this->generateOverwritingMemcpy(b, inputInitPtr, outputInitPtr, literalLength, i8PtrTy, 1);
841            b->CreateBr(exitBlock);
842
843            // ---- exitBlock
844            b->SetInsertPoint(exitBlock);
845        }
846    }
847
848    void LZ4ParallelByteStreamAioKernel::generateOverwritingMemcpy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *inputBasePtr,
849                                   llvm::Value *outputBasePtr, llvm::Value *copyBytes, llvm::PointerType *targetPtrTy,
850                                   llvm::Value* stepSize) {
851//        unsigned targetPtrBitWidth = targetPtrTy->getElementType()->getIntegerBitWidth();
852
853        Constant * SIZE_0 = b->getSize(0);
854//        Constant * SIZE_1 = b->getSize(1);
855        PointerType* i8PtrTy = b->getInt8PtrTy();
856
857        BasicBlock* entryBlock = b->GetInsertBlock();
858        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
859        BasicBlock* conBlock = b->CreateBasicBlock("conBlock");
860        BasicBlock* bodyBlock = b->CreateBasicBlock("bodyBlock");
861
862        Value* inputInitPtr = b->CreatePointerCast(inputBasePtr, targetPtrTy);
863        Value* outputInitPtr = b->CreatePointerCast(outputBasePtr, targetPtrTy);
864
865        b->CreateBr(conBlock);
866        // ---- conBlock
867        b->SetInsertPoint(conBlock);
868
869        PHINode *phiCopiedSize = b->CreatePHI(b->getSizeTy(), 2);
870        phiCopiedSize->addIncoming(SIZE_0, entryBlock);
871        PHINode *phiInputPtr = b->CreatePHI(targetPtrTy, 2);
872        phiInputPtr->addIncoming(inputInitPtr, entryBlock);
873        PHINode *phiOutputPtr = b->CreatePHI(targetPtrTy, 2);
874        phiOutputPtr->addIncoming(outputInitPtr, entryBlock);
875
876        b->CreateCondBr(b->CreateICmpULT(phiCopiedSize, copyBytes), bodyBlock, exitBlock);
877
878        // ---- bodyBlock
879        b->SetInsertPoint(bodyBlock);
880        b->CreateStore(b->CreateLoad(phiInputPtr), phiOutputPtr);
881
882        phiCopiedSize->addIncoming(b->CreateAdd(phiCopiedSize, stepSize), b->GetInsertBlock());
883
884        Value *newInputPtr = nullptr, *newOutputPtr = nullptr;
885
886        newInputPtr = b->CreatePointerCast(
887                b->CreateGEP(b->CreatePointerCast(phiInputPtr, i8PtrTy), stepSize),
888                targetPtrTy
889        );
890
891        newOutputPtr = b->CreatePointerCast(
892                b->CreateGEP(b->CreatePointerCast(phiOutputPtr, i8PtrTy), stepSize),
893                targetPtrTy
894        );
895
896        phiInputPtr->addIncoming(newInputPtr, b->GetInsertBlock());
897        phiOutputPtr->addIncoming(newOutputPtr, b->GetInsertBlock());
898        b->CreateBr(conBlock);
899
900        // ---- exitBlock
901        b->SetInsertPoint(exitBlock);
902    }
903
904    void LZ4ParallelByteStreamAioKernel::generateOverwritingMemcpy(const std::unique_ptr<KernelBuilder> &b,
905                                                                   llvm::Value *inputBasePtr,
906                                                                   llvm::Value *outputBasePtr,
907                                                                   llvm::Value *copyBytes, llvm::PointerType *targetPtrTy,
908                                                                   size_t stepSize) {
909        unsigned targetPtrBitWidth = targetPtrTy->getElementType()->getIntegerBitWidth();
910
911        Constant * SIZE_0 = b->getSize(0);
912        Constant * SIZE_1 = b->getSize(1);
913        PointerType* i8PtrTy = b->getInt8PtrTy();
914
915        BasicBlock* entryBlock = b->GetInsertBlock();
916        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
917        BasicBlock* conBlock = b->CreateBasicBlock("conBlock");
918        BasicBlock* bodyBlock = b->CreateBasicBlock("bodyBlock");
919
920        Value* inputInitPtr = b->CreatePointerCast(inputBasePtr, targetPtrTy);
921        Value* outputInitPtr = b->CreatePointerCast(outputBasePtr, targetPtrTy);
922
923        b->CreateBr(conBlock);
924        // ---- conBlock
925        b->SetInsertPoint(conBlock);
926
927        PHINode *phiCopiedSize = b->CreatePHI(b->getSizeTy(), 2);
928        phiCopiedSize->addIncoming(SIZE_0, entryBlock);
929        PHINode *phiInputPtr = b->CreatePHI(targetPtrTy, 2);
930        phiInputPtr->addIncoming(inputInitPtr, entryBlock);
931        PHINode *phiOutputPtr = b->CreatePHI(targetPtrTy, 2);
932        phiOutputPtr->addIncoming(outputInitPtr, entryBlock);
933
934        b->CreateCondBr(b->CreateICmpULT(phiCopiedSize, copyBytes), bodyBlock, exitBlock);
935
936        // ---- bodyBlock
937        b->SetInsertPoint(bodyBlock);
938        b->CreateStore(b->CreateLoad(phiInputPtr), phiOutputPtr);
939
940        phiCopiedSize->addIncoming(b->CreateAdd(phiCopiedSize, b->getSize(stepSize)), b->GetInsertBlock());
941
942        Value *newInputPtr = nullptr, *newOutputPtr = nullptr;
943
944        if (targetPtrBitWidth / 8 == stepSize) {
945            newInputPtr = b->CreateGEP(phiInputPtr, SIZE_1);
946            newOutputPtr = b->CreateGEP(phiOutputPtr, SIZE_1);
947        } else {
948            newInputPtr = b->CreatePointerCast(
949                    b->CreateGEP(b->CreatePointerCast(phiInputPtr, i8PtrTy), b->getSize(stepSize)),
950                    targetPtrTy
951            );
952
953            newOutputPtr = b->CreatePointerCast(
954                    b->CreateGEP(b->CreatePointerCast(phiOutputPtr, i8PtrTy), b->getSize(stepSize)),
955                    targetPtrTy
956            );
957
958        }
959
960        phiInputPtr->addIncoming(newInputPtr, b->GetInsertBlock());
961        phiOutputPtr->addIncoming(newOutputPtr, b->GetInsertBlock());
962        b->CreateBr(conBlock);
963
964        // ---- exitBlock
965        b->SetInsertPoint(exitBlock);
966    }
967
968    void LZ4ParallelByteStreamAioKernel::generateSimdLiteralCopyByScatter(const std::unique_ptr<KernelBuilder> &b,
969                                                                          llvm::Value *literalStartVec,
970                                                                          llvm::Value *literalLengthVec,
971                                                                          llvm::Value *outputPosVec) {
972        // ---- EntryBlock
973        BasicBlock* entryBlock = b->GetInsertBlock();
974        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
975        BasicBlock* i64LiteralCopyBlock = b->CreateBasicBlock("i64LiteralCopyBlock");
976        BasicBlock* i8LiteralCopyBlock = b->CreateBasicBlock("i8LiteralCopyBlock");
977
978        llvm::Value* initCopiedLength = ConstantVector::getNullValue(literalLengthVec->getType());
979
980        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
981        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", b->getSize(0)), b->getInt8PtrTy());
982
983        Value* outputCapacity = b->getCapacity("outputStream");
984        Value* outputPosRemVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(outputCapacity))));
985        Value* outputPosRemBlockSizeVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(b->getIntN(SIMD_WIDTH, mOutputBlockSize)))));
986        Value* remainingBlockSizeVec = b->simd_sub(SIMD_WIDTH, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, mOutputBlockSize)), outputPosRemBlockSizeVec);
987
988        Value* possibleExceedBuffer = b->simd_uge(SIMD_WIDTH, b->simd_add(SIMD_WIDTH, literalLengthVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 8))), remainingBlockSizeVec);
989        // true ffff, false 0000
990
991        // TODO handle literalLengthVec == 0
992
993        b->CreateUnlikelyCondBr(
994                b->CreateICmpNE(b->CreateBitCast(possibleExceedBuffer, b->getIntNTy(b->getBitBlockWidth())), b->getIntN(b->getBitBlockWidth(), 0)),
995                i8LiteralCopyBlock,
996                i64LiteralCopyBlock
997        );
998
999        // ---- i8LiteralCopyBlock
1000        b->SetInsertPoint(i8LiteralCopyBlock);
1001        this->generateSimdSequentialLiteralCopy(b, literalStartVec, literalLengthVec, outputPosVec);
1002        b->CreateBr(exitBlock);
1003
1004        // ---- i64LiteralCopyBlock
1005        b->SetInsertPoint(i64LiteralCopyBlock);
1006
1007        BasicBlock* i64LiteralCopyConBlock = b->CreateBasicBlock("i64LiteralCopyConBlock");
1008        BasicBlock* i64LiteralCopyBodyBlock = b->CreateBasicBlock("i64LiteralCopyBodyBlock");
1009
1010
1011        b->CreateBr(i64LiteralCopyConBlock);
1012
1013        // ---- i64LiteralCopyConBlock
1014        b->SetInsertPoint(i64LiteralCopyConBlock);
1015        PHINode* phiCopiedLength = b->CreatePHI(initCopiedLength->getType(), 2);
1016        phiCopiedLength->addIncoming(initCopiedLength, i64LiteralCopyBlock);
1017
1018        Value* shouldCopiedBitBlock = b->simd_ult(SIMD_WIDTH, phiCopiedLength, literalLengthVec);
1019//        b->CallPrintRegister("phiCopiedLength", phiCopiedLength);
1020//        b->CallPrintRegister("literalLengthVec", literalLengthVec);
1021//        b->CallPrintRegister("shouldCopiedBitBlock", shouldCopiedBitBlock);
1022        Value* shouldCopiedI1 = b->CreateICmpNE(
1023                b->CreateBitCast(shouldCopiedBitBlock, b->getIntNTy(b->getBitBlockWidth())),
1024                b->getIntN(b->getBitBlockWidth(), 0)
1025        );
1026
1027
1028        b->CreateCondBr(shouldCopiedI1, i64LiteralCopyBodyBlock, exitBlock);
1029
1030
1031        // ---- i64LiteralCopyBodyBlock
1032        b->SetInsertPoint(i64LiteralCopyBodyBlock);
1033        Value* literalData = this->simdFetchI64DataByGather(b, inputBasePtr, b->simd_add(SIMD_WIDTH, literalStartVec, phiCopiedLength), shouldCopiedBitBlock);
1034
1035        this->simdPutData(
1036                b,
1037                outputBasePtr,
1038                b->simd_add(SIMD_WIDTH, outputPosRemVec, phiCopiedLength),
1039                literalData,
1040                shouldCopiedBitBlock
1041        );
1042//        b->CallPrintRegister("phiCopiedLength", phiCopiedLength);
1043        phiCopiedLength->addIncoming(
1044                b->simd_add(
1045                        SIMD_WIDTH,
1046                        phiCopiedLength,
1047                        b->simd_and(
1048                                b->simd_fill(
1049                                        SIMD_WIDTH,
1050                                        b->getIntN(SIMD_WIDTH, 8)
1051                                ),
1052                                shouldCopiedBitBlock
1053                        )
1054
1055                ),
1056                b->GetInsertBlock()
1057        );
1058
1059        b->CreateBr(i64LiteralCopyConBlock);
1060
1061        b->SetInsertPoint(exitBlock);
1062    }
1063
1064
1065    void LZ4ParallelByteStreamAioKernel::handleLiteralCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *literalStart,
1066                                                   llvm::Value *literalLength, llvm::Value* outputPos) {
1067        unsigned fw = 64;
1068        Type* INT_FW_PTR = b->getIntNTy(fw)->getPointerTo();
1069
1070        Value* inputBytePtr = b->getRawInputPointer("byteStream", literalStart);
1071        Value* inputPtr = b->CreatePointerCast(inputBytePtr, INT_FW_PTR);
1072
1073        Value* outputBufferSize = b->getCapacity("outputStream");
1074        Value* outputPtr = b->getRawOutputPointer("outputStream", b->CreateURem(outputPos, outputBufferSize));
1075        outputPtr = b->CreatePointerCast(outputPtr, INT_FW_PTR);
1076
1077        // We can always assume that we have enough output buffer based on our output buffer allocation strategy (except in extract only case)
1078
1079        BasicBlock* entryBlock = b->GetInsertBlock();
1080        BasicBlock* literalCopyCon = b->CreateBasicBlock("literalCopyCon");
1081        BasicBlock* literalCopyBody = b->CreateBasicBlock("literalCopyBody");
1082        BasicBlock* literalCopyExit = b->CreateBasicBlock("literalCopyExit");
1083
1084        b->CreateBr(literalCopyCon);
1085
1086        // ---- literalCopyCon
1087        b->SetInsertPoint(literalCopyCon);
1088        PHINode* phiOutputPtr = b->CreatePHI(outputPtr->getType(), 2);
1089        phiOutputPtr->addIncoming(outputPtr, entryBlock);
1090        PHINode* phiInputPtr = b->CreatePHI(inputPtr->getType(), 2);
1091        phiInputPtr->addIncoming(inputPtr, entryBlock);
1092        PHINode* phiCopiedLength = b->CreatePHI(literalLength->getType(), 2);
1093        phiCopiedLength->addIncoming(b->getSize(0), entryBlock);
1094        b->CreateCondBr(b->CreateICmpULT(phiCopiedLength, literalLength), literalCopyBody, literalCopyExit);
1095
1096        // ---- literalCopyBody
1097        b->SetInsertPoint(literalCopyBody);
1098        // Always copy fw bits to improve performance
1099        b->CreateStore(b->CreateLoad(phiInputPtr), phiOutputPtr);
1100
1101        phiInputPtr->addIncoming(b->CreateGEP(phiInputPtr, b->getSize(1)), b->GetInsertBlock());
1102        phiOutputPtr->addIncoming(b->CreateGEP(phiOutputPtr, b->getSize(1)), b->GetInsertBlock());
1103        phiCopiedLength->addIncoming(b->CreateAdd(phiCopiedLength, b->getSize(fw / 8)), b->GetInsertBlock());
1104        b->CreateBr(literalCopyCon);
1105
1106        // ---- literalCopyExit
1107        b->SetInsertPoint(literalCopyExit);
1108        b->setScalarField("outputPos", b->CreateAdd(outputPos, literalLength));
1109    }
1110
1111    void LZ4ParallelByteStreamAioKernel::handleMatchCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *matchOffset,
1112                                                 llvm::Value *matchLength, llvm::Value* outputPos) {
1113        unsigned fw = 64;
1114        Type* INT_FW_PTR = b->getIntNTy(fw)->getPointerTo();
1115
1116        BasicBlock* entryBlock = b->GetInsertBlock();
1117
1118        Value* outputBufferSize = b->getCapacity("outputStream");
1119
1120        Value* copyToPtr = b->getRawOutputPointer("outputStream", b->CreateURem(outputPos, outputBufferSize));
1121        Value* copyFromPtr = b->getRawOutputPointer("outputStream", b->CreateURem(b->CreateSub(outputPos, matchOffset), outputBufferSize));
1122
1123        BasicBlock* matchCopyCon = b->CreateBasicBlock("matchCopyCon");
1124        BasicBlock* matchCopyBody = b->CreateBasicBlock("matchCopyBody");
1125        BasicBlock* matchCopyExit = b->CreateBasicBlock("matchCopyExit");
1126
1127        b->CreateBr(matchCopyCon);
1128
1129        // ---- matchCopyCon
1130        b->SetInsertPoint(matchCopyCon);
1131        PHINode* phiFromPtr = b->CreatePHI(b->getInt8PtrTy(), 2);
1132        phiFromPtr->addIncoming(copyFromPtr, entryBlock);
1133        PHINode* phiToPtr = b->CreatePHI(b->getInt8PtrTy(), 2);
1134        phiToPtr->addIncoming(copyToPtr, entryBlock);
1135        PHINode* phiCopiedSize = b->CreatePHI(b->getSizeTy(), 2);
1136        phiCopiedSize->addIncoming(b->getSize(0), entryBlock);
1137
1138        b->CreateCondBr(b->CreateICmpULT(phiCopiedSize, matchLength), matchCopyBody, matchCopyExit);
1139
1140        // ---- matchCopyBody
1141        b->SetInsertPoint(matchCopyBody);
1142        b->CreateStore(
1143                b->CreateLoad(b->CreatePointerCast(phiFromPtr, INT_FW_PTR)),
1144                b->CreatePointerCast(phiToPtr, INT_FW_PTR)
1145        );
1146
1147        Value* copySize = b->CreateUMin(matchOffset, b->getSize(fw / 8));
1148        phiFromPtr->addIncoming(b->CreateGEP(phiFromPtr, copySize), b->GetInsertBlock());
1149        phiToPtr->addIncoming(b->CreateGEP(phiToPtr, copySize), b->GetInsertBlock());
1150        phiCopiedSize->addIncoming(b->CreateAdd(phiCopiedSize, copySize), b->GetInsertBlock());
1151        b->CreateBr(matchCopyCon);
1152
1153        // ---- matchCopyExit
1154        b->SetInsertPoint(matchCopyExit);
1155        b->setScalarField("outputPos", b->CreateAdd(outputPos, matchLength));
1156    }
1157
1158    llvm::Value* LZ4ParallelByteStreamAioKernel::simdFetchData(const std::unique_ptr<KernelBuilder> &b, llvm::Value* basePtr, llvm::Value* offsetVec, llvm::Value* mask) {
1159//        return this->simdFetchDataByLoop(b, basePtr, offsetVec, mask);
1160        if (AVX2_available() && mEnableGather) {
1161            return this->simdFetchI32DataByGather(b, basePtr, offsetVec, mask);
1162        } else {
1163            return this->simdFetchDataByLoop(b, basePtr, offsetVec, mask);
1164        }
1165    }
1166
1167
1168
1169    llvm::Value* LZ4ParallelByteStreamAioKernel::simdFetchByteData(const std::unique_ptr<KernelBuilder> &b, llvm::Value* basePtr, llvm::Value* offsetVec, llvm::Value* mask) {
1170        return b->CreateAnd(
1171                this->simdFetchData(b, basePtr, offsetVec, mask),
1172                b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0xff))
1173        );
1174    }
1175
1176    llvm::Value* LZ4ParallelByteStreamAioKernel::simdFetchI32DataByGather(const std::unique_ptr<KernelBuilder> &b,
1177                                                                          llvm::Value *basePtr, llvm::Value *offsetVec,
1178                                                                          llvm::Value *mask) {
1179
1180        Function *gatherFunc2 = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx2_gather_d_d);
1181        Function *gatherFunc3 = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx2_gather_d_d_256);
1182
1183        Function *gatherFunc = AVX512BW_available() ? gatherFunc3 : gatherFunc2;
1184
1185        Type* i32BitBlockTy = VectorType::get(b->getInt32Ty(), b->getBitBlockWidth() / SIMD_WIDTH);
1186
1187
1188        Value* tokenValuesVec =  b->CreateCall(
1189                gatherFunc,
1190                {
1191                        UndefValue::get(i32BitBlockTy),
1192                        basePtr,
1193                        b->CreateTrunc(offsetVec, i32BitBlockTy),
1194                        b->CreateTrunc(mask, i32BitBlockTy),
1195                        b->getInt8(1)
1196                }
1197        );
1198        tokenValuesVec = b->CreateZExt(tokenValuesVec, b->getBitBlockType());
1199        tokenValuesVec = b->CreateAnd(tokenValuesVec, mask);
1200
1201        return tokenValuesVec;
1202    }
1203
1204    llvm::Value* LZ4ParallelByteStreamAioKernel::simdFetchI64DataByGather(const std::unique_ptr<KernelBuilder> &b,
1205                                                                          llvm::Value *basePtr, llvm::Value *offsetVec,
1206                                                                          llvm::Value *mask) {
1207        Type* i32BitBlockTy = VectorType::get(b->getInt32Ty(), b->getBitBlockWidth() / SIMD_WIDTH);
1208        if (AVX512BW_available()) {
1209            // AVX512 gather use i8 mask
1210            //declare <8 x int> @llvm.x86.avx512.gather.dpq.512(<8 x i64>, i8*, <8 x i32>, i8, i32) #1
1211            Function *gatherFunc512 = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx512_gather_dpq_512);
1212            return b->CreateCall(
1213                    gatherFunc512,
1214                    {
1215                            UndefValue::get(b->getBitBlockType()),
1216                            basePtr,
1217                            b->CreateTrunc(offsetVec, i32BitBlockTy),
1218                            b->CreateTruncOrBitCast(b->hsimd_signmask(SIMD_WIDTH, mask), b->getInt8Ty()),
1219                            b->getInt32(1)
1220                    });
1221            // return result & i512Mask ?
1222        } else {
1223            // AVX2 gather use i256 mask
1224            Function *gatherFunc = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx2_gather_d_q_256);
1225            Value* tokenValuesVec =  b->CreateCall(
1226                    gatherFunc,
1227                    {
1228                            UndefValue::get(b->getBitBlockType()),
1229                            basePtr,
1230                            b->CreateTrunc(offsetVec, VectorType::get(b->getInt32Ty(), 4)),
1231                            mask,
1232                            b->getInt8(1)
1233                    }
1234            );
1235            tokenValuesVec = b->CreateAnd(tokenValuesVec, mask);
1236            return tokenValuesVec;
1237        }
1238    }
1239
1240    llvm::Value* LZ4ParallelByteStreamAioKernel::simdFetchDataByLoop(const std::unique_ptr<KernelBuilder> &b,
1241                                                                     llvm::Value *basePtr, llvm::Value *offsetVec,
1242                                                                     llvm::Value *maskVec) {
1243        Value* placeHolderPtr = b->CreatePointerCast(b->getScalarFieldPtr("placeholder"), basePtr->getType());
1244
1245        Value* retVec = ConstantVector::getNullValue(b->getBitBlockType());
1246
1247        for (uint64_t i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++){
1248            Value* mask = b->CreateExtractElement(maskVec, i);
1249            Value* shouldLoad = b->CreateICmpNE(mask, b->getInt64(0));
1250            Value* loadPtr = b->CreateSelect(shouldLoad, b->CreateGEP(basePtr, b->CreateExtractElement(offsetVec, i)), placeHolderPtr);
1251//            Value* loadPtr = b->CreateGEP(basePtr, b->CreateExtractElement(offsetVec, i));
1252            Value* loadValue = b->CreateZExt(b->CreateLoad(b->CreatePointerCast(loadPtr, b->getInt64Ty()->getPointerTo())), b->getInt64Ty());
1253            Value* finalValue = b->CreateSelect(shouldLoad, loadValue, b->getInt64(0));
1254            retVec = b->CreateInsertElement(retVec, finalValue, i);
1255        }
1256
1257        return retVec;
1258    }
1259
1260    void LZ4ParallelByteStreamAioKernel::simdPutData(const std::unique_ptr<KernelBuilder> &b, llvm::Value* basePtr, llvm::Value* offsetVec,llvm::Value* values, llvm::Value* mask) {
1261        if (AVX512BW_available()) {
1262            this->simdPutDataByScatter(b, basePtr, offsetVec, values, mask);
1263        } else {
1264            this->simdPutDataByLoop(b, basePtr, offsetVec, values, mask);
1265        }
1266
1267
1268    }
1269
1270    void LZ4ParallelByteStreamAioKernel::simdPutDataByLoop(const std::unique_ptr<KernelBuilder> &b, llvm::Value* basePtr, llvm::Value* offsetVec,llvm::Value* values, llvm::Value* mask) {
1271
1272        Value* shouldStoreVec = b->CreateICmpNE(mask, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0)));
1273
1274        for (unsigned i = 0 ; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
1275            BasicBlock* conBlock = b->CreateBasicBlock("simdPutDataByLoopCon");
1276            BasicBlock* bodyBlock = b->CreateBasicBlock("simdPutDataByLoopBody");
1277            BasicBlock* exitBlock = b->CreateBasicBlock("simdPutDataByLoopExit");
1278
1279            b->CreateBr(conBlock);
1280
1281            // ---- ConBlock
1282            b->SetInsertPoint(conBlock);
1283            Value* shouldStore = b->CreateExtractElement(shouldStoreVec, i);
1284            b->CreateCondBr(shouldStore, bodyBlock, exitBlock);
1285
1286            // ---- BodyBlock
1287            b->SetInsertPoint(bodyBlock);
1288            b->CreateStore(
1289                    b->CreateExtractElement(values, i),
1290                    b->CreatePointerCast(b->CreateGEP(basePtr, b->CreateExtractElement(offsetVec, i)), b->getIntNTy(SIMD_WIDTH)->getPointerTo())
1291            );
1292
1293            b->CreateBr(exitBlock);
1294
1295            // ---- ExitBlock
1296            b->SetInsertPoint(exitBlock);
1297
1298        }
1299    }
1300    void LZ4ParallelByteStreamAioKernel::simdPutDataByScatter(const std::unique_ptr<KernelBuilder> &b, llvm::Value* basePtr, llvm::Value* offsetVec,llvm::Value* values, llvm::Value* mask) {
1301        Function *scatterFunc = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx512_scatter_dpq_512);
1302        //declare void @llvm.x86.avx512.scatter.dpq.512(i8*, i8, <8 x i32>, <8 x i64>, i32)
1303
1304        Value* i8Mask = b->CreateTruncOrBitCast(b->hsimd_signmask(SIMD_WIDTH, mask), b->getIntNTy(b->getBitBlockWidth() / SIMD_WIDTH));
1305
1306        b->CreateCall(scatterFunc, {
1307                basePtr,
1308                i8Mask,
1309                b->CreateTrunc(offsetVec, VectorType::get(b->getInt32Ty(), b->getBitBlockWidth() / SIMD_WIDTH)),
1310                values,
1311                b->getInt32(1)
1312        });
1313
1314    }
1315
1316}
Note: See TracBrowser for help on using the repository browser.