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

Last change on this file since 6065 was 6065, checked in by xwa163, 11 months ago
  1. Fix some typo in LZ4 Grep Extract and Deposit pipeline
  2. Small fix for LZ4ParallelByteStreamAIOKernel
File size: 47.0 KB
Line 
1//
2// Created by wxy325 on 2018/5/31.
3//
4
5#include "lz4_parallel_bytestream_aio.h"
6
7#include <kernels/kernel_builder.h>
8#include <iostream>
9#include <string>
10#include <llvm/Support/raw_ostream.h>
11#include <kernels/streamset.h>
12
13using namespace llvm;
14using namespace kernel;
15using namespace std;
16
17#define SIMD_WIDTH (64)
18
19
20namespace kernel{
21
22    LZ4ParallelByteStreamAioKernel::LZ4ParallelByteStreamAioKernel(const std::unique_ptr<kernel::KernelBuilder> &b)
23            :SegmentOrientedKernel("LZ4ParallelByteStreamAioKernel",
24            // Inputs
25                                   {
26                    Binding{b->getStreamSetTy(1, 8), "byteStream", BoundedRate(0, 1)},
27                    Binding{b->getStreamSetTy(1, 1), "extender", RateEqualTo("byteStream")},
28
29                    // block data
30                    Binding{b->getStreamSetTy(1, 1), "isCompressed", BoundedRate(0, 1), AlwaysConsume()},
31                    Binding{b->getStreamSetTy(1, 64), "blockStart", RateEqualTo("isCompressed"), AlwaysConsume()},
32                    Binding{b->getStreamSetTy(1, 64), "blockEnd", RateEqualTo("isCompressed"), AlwaysConsume()}
33
34            },
35            //Outputs
36                                   {
37                                           Binding{b->getStreamSetTy(1, 8), "outputStream", BoundedRate(0, 1)},
38                                   },
39            //Arguments
40                                   {
41                                           Binding{b->getSizeTy(), "fileSize"}
42                                   },
43                                   {},
44            //Internal states:
45                                   {
46                                           Binding{b->getInt64Ty(), "tempTimes"},
47                                           Binding{b->getIntNTy(SIMD_WIDTH), "outputPos"},
48
49                                   }){
50        this->setStride(4 * 1024 * 1024 * 4);
51        addAttribute(MustExplicitlyTerminate());
52    }
53
54    Value* LZ4ParallelByteStreamAioKernel::generateSimdAcceleration(const std::unique_ptr<KernelBuilder> &b, llvm::Value *beginTokenPosVec,
55                                  llvm::Value *blockEndVec) {
56        // TODO incomplete
57
58        // Constant
59        Function *gatherFunc = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx2_gather_d_q_256); // TODO find ret <4 * i32> version
60//        Function *gatherFunc2 = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx2_gather_d_q);
61
62        // ---- Entry Block
63        BasicBlock* entryBlock = b->GetInsertBlock();
64        Value* maskedTokenPosVec = b->CreateAnd(beginTokenPosVec, b->simd_fill(SIMD_WIDTH, b->CreateNot(b->CreateNeg(b->getCapacity("extender")))));
65        Value* maskBlockIndexVec = b->CreateLShr(beginTokenPosVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, std::log2(64))));
66        Value* maskBlockOffsetVec = b->CreateAnd(beginTokenPosVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 63)));
67        Value* extenderValueVec = b->CreateCall(
68                gatherFunc,
69                {
70                        UndefValue::get(b->getBitBlockType()),
71                        b->CreatePointerCast(b->getRawInputPointer("extender", b->getSize(0)), b->getInt8PtrTy()),
72                        b->CreateTrunc(maskBlockIndexVec, VectorType::get(b->getInt32Ty(), 4)),
73                        Constant::getAllOnesValue(b->getBitBlockType()),
74                        b->getInt8(8)
75                }
76        );
77
78        Value* extenderValueVec2 = b->CreateCall(
79                gatherFunc,
80                {
81                        UndefValue::get(VectorType::get(b->getInt8Ty(), 4)),
82                        b->CreatePointerCast(b->getRawInputPointer("extender", b->getSize(0)), b->getInt8PtrTy()),
83                        b->CreateTrunc(maskBlockIndexVec, VectorType::get(b->getInt32Ty(), 4)),
84                        Constant::getAllOnesValue(b->getBitBlockType()),
85                        b->getInt8(8)
86                }
87        );
88
89        Value* initTokeMarkersVec = b->CreateShl(b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 1)), maskBlockOffsetVec);
90
91//        b->CallPrintRegister("a", beginTokenPosVec);
92//        b->CallPrintRegister("maskedTokenPosVec", maskedTokenPosVec);
93//        b->CallPrintRegister("maskBlockIndexVec", maskBlockIndexVec);
94//        b->CallPrintRegister("gather_result", extenderValueVec);
95
96
97        BasicBlock* accelerationProcessBlock = b->CreateBasicBlock("accelerationProcessBlock");
98        BasicBlock* accelerationExitBlock = b->CreateBasicBlock("accelerationExitBlock");
99        b->CreateBr(accelerationProcessBlock);
100
101        // ---- AccelerationProcessBlock
102        b->SetInsertPoint(accelerationProcessBlock);
103        PHINode* phiTokenMarkersVec = b->CreatePHI(initTokeMarkersVec->getType(), 2);
104        phiTokenMarkersVec->addIncoming(initTokeMarkersVec, entryBlock);
105
106
107
108
109        return beginTokenPosVec;    //TODO
110    }
111
112
113    std::pair<Value *, Value *> LZ4ParallelByteStreamAioKernel::simdProcessBlockBoundary(
114            const std::unique_ptr<KernelBuilder> &b, Value *beginTokenPosVec, Value *lz4BlockEndVec, Value* initOutputPosVec
115    ) {
116        Function *gatherFunc = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx2_gather_d_q_256); // Maybe it will be better to use <4 * i32> version
117
118        // Constant
119        ConstantInt* SIZE_0 = b->getSize(0);
120        ConstantInt* SIZE_1 = b->getSize(1);
121        ConstantInt* BYTE_FF = b->getInt8(0xff);
122        Value* BIT_BLOCK_0 = ConstantVector::getNullValue(b->getBitBlockType());
123        Value* BIT_BLOCK_1 = b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0x1));
124        Value* BIT_BLOCK_F0 = b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0xf0));
125        Value* BIT_BLOCK_0F = b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0x0f));
126        Value* BIT_BLOCK_FF = b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0xff));
127        Value* BIT_BLOCK_FFFF = b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0xffff));
128        Type* i4Ty = b->getIntNTy(4);
129        Type* INT_BIT_BLOCK_TY = b->getIntNTy(b->getBitBlockWidth());
130        Constant* INT_BIT_BLOCK_TY_0 = b->getIntN(b->getBitBlockWidth(), 0);
131
132        // ---- EntryBlock
133        BasicBlock* entryBlock = b->GetInsertBlock();
134        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
135
136        Value* notFinishBlocksVec = b->CreateICmpULT(beginTokenPosVec, lz4BlockEndVec);
137        Value* notFinishBitBlock = b->CreateZExt(notFinishBlocksVec, b->getBitBlockType());
138        Value* notFinishMask = b->CreateNeg(notFinishBitBlock);
139
140
141        Value* byteRawInputPtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
142
143        Value* firstTokenPos = b->CreateExtractElement(beginTokenPosVec, (uint64_t)0);
144        Value* bytePtrBase = b->CreateGEP(byteRawInputPtr, firstTokenPos);
145
146
147
148        Value* tokenValuesVec = this->simdFetchByteData(b, byteRawInputPtr, beginTokenPosVec, notFinishMask);
149
150        Value* shouldExtendLiteralVec = b->CreateICmpEQ(b->CreateAnd(BIT_BLOCK_F0, tokenValuesVec), BIT_BLOCK_F0);
151        Value* shouldExtendLiteralBitBlockVec = b->CreateZExt(shouldExtendLiteralVec, b->getBitBlockType());
152        Value* shouldExtendLiteral = b->CreateICmpNE(b->CreateBitCast(shouldExtendLiteralBitBlockVec, INT_BIT_BLOCK_TY), INT_BIT_BLOCK_TY_0);
153
154        Value* shouldExtendMatchVec = b->CreateICmpEQ(b->CreateAnd(BIT_BLOCK_0F, tokenValuesVec), BIT_BLOCK_0F);
155        Value* shouldExtendMatchBitBlockVec = b->CreateZExt(shouldExtendMatchVec, b->getBitBlockType());
156        Value* shouldExtendMatch = b->CreateICmpNE(b->CreateBitCast(shouldExtendMatchBitBlockVec, INT_BIT_BLOCK_TY), INT_BIT_BLOCK_TY_0);
157
158        Value* initExtendLiteralPos = b->CreateAdd(beginTokenPosVec, shouldExtendLiteralBitBlockVec);
159
160
161        BasicBlock* extendLiteralCond = b->CreateBasicBlock("extendLiteralCond");
162        BasicBlock* extendLiteralEnd = b->CreateBasicBlock("extendLiteralEnd");
163
164        b->CreateCondBr(shouldExtendLiteral, extendLiteralCond, extendLiteralEnd);
165
166
167        // ---- extendLiteralCond
168        b->SetInsertPoint(extendLiteralCond);
169        PHINode* phiCurrentExtendLiteralPosVec = b->CreatePHI(initExtendLiteralPos->getType(), 2);
170        phiCurrentExtendLiteralPosVec->addIncoming(initExtendLiteralPos, entryBlock);
171
172        PHINode* phiExtendLiteralLengthVec = b->CreatePHI(b->getBitBlockType(), 2);
173        phiExtendLiteralLengthVec->addIncoming(BIT_BLOCK_0, entryBlock);
174
175        PHINode* phiShouldExtendLiteralBitBlockVec = b->CreatePHI(shouldExtendLiteralBitBlockVec->getType(), 2);
176        phiShouldExtendLiteralBitBlockVec->addIncoming(shouldExtendLiteralBitBlockVec, entryBlock);
177        Value* shouldExtendLiteralGatherMask = b->CreateNeg(phiShouldExtendLiteralBitBlockVec);
178        shouldExtendLiteralGatherMask = b->CreateAnd(shouldExtendLiteralGatherMask, notFinishMask);
179//        b->CallPrintInt("a", b->getSize(0));
180        // TODO maybe we can load i64 once and then consume 8 times
181        Value* currentLiteralLengthVec = this->simdFetchByteData(b, byteRawInputPtr, phiCurrentExtendLiteralPosVec, shouldExtendLiteralGatherMask);
182
183        Value* newExtendLiteralLengthVec = b->CreateAdd(phiExtendLiteralLengthVec, currentLiteralLengthVec);
184
185        Value* shouldContinueExtendVec = b->CreateICmpEQ(currentLiteralLengthVec, BIT_BLOCK_FF);
186        Value* shouldContinueExtendVecBitBlock = b->CreateZExt(shouldContinueExtendVec, b->getBitBlockType());
187
188        Value* newExtendLiteralPosVec = b->CreateAdd(phiCurrentExtendLiteralPosVec, b->CreateAnd(shouldExtendLiteralBitBlockVec, shouldContinueExtendVecBitBlock));
189
190
191        phiCurrentExtendLiteralPosVec->addIncoming(newExtendLiteralPosVec, b->GetInsertBlock());
192        phiExtendLiteralLengthVec->addIncoming(newExtendLiteralLengthVec, b->GetInsertBlock());
193
194
195        phiShouldExtendLiteralBitBlockVec->addIncoming(shouldContinueExtendVecBitBlock, b->GetInsertBlock());
196        Value* shouldContinueExtendLiteral = b->CreateICmpNE(b->CreateBitCast(shouldContinueExtendVecBitBlock, INT_BIT_BLOCK_TY), INT_BIT_BLOCK_TY_0);
197
198        b->CreateCondBr(shouldContinueExtendLiteral, extendLiteralCond, extendLiteralEnd);
199
200        // ---- extendLiteralEnd
201        b->SetInsertPoint(extendLiteralEnd);
202        PHINode* literalExtendValueVec = b->CreatePHI(b->getBitBlockType(), 2);
203        literalExtendValueVec->addIncoming(BIT_BLOCK_0, entryBlock);
204        literalExtendValueVec->addIncoming(newExtendLiteralLengthVec, extendLiteralCond);
205
206        PHINode* phiExtendLiteralEndPos = b->CreatePHI(b->getBitBlockType(), 2);
207        phiExtendLiteralEndPos->addIncoming(beginTokenPosVec, entryBlock);
208        phiExtendLiteralEndPos->addIncoming(phiCurrentExtendLiteralPosVec, extendLiteralCond);
209
210
211        Value* literalLengthVec = b->simd_add(SIMD_WIDTH, literalExtendValueVec, b->simd_srlv(SIMD_WIDTH, tokenValuesVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 4))));
212//        Value* literalLengthVec = b->CreateAdd(literalExtendValueVec, b->CreateLShr(tokenValuesVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 4))));
213
214        Value* literalStartPosVec = b->CreateAdd(phiExtendLiteralEndPos, BIT_BLOCK_1);
215        Value* literalEndPosVec = b->CreateAdd(literalStartPosVec, literalLengthVec);
216
217
218        this->handleSimdLiteralCopy(b, literalStartPosVec, literalLengthVec, initOutputPosVec);
219        Value* outputPosAfterLiteralCpy = b->CreateAdd(initOutputPosVec, literalLengthVec);
220
221
222        Value* matchOffsetBeginPosVec = literalEndPosVec;
223
224        Value* matchOffsetNextPosVec = b->CreateAdd(matchOffsetBeginPosVec, BIT_BLOCK_1);
225
226
227        BasicBlock* hasMatchPartBlock = b->CreateBasicBlock("hasMatchPartBlock");
228        BasicBlock* extendMatchCon = b->CreateBasicBlock("extendMatchCon");
229        BasicBlock* extendMatchExit = b->CreateBasicBlock("extendMatchExit");
230
231
232        BasicBlock* extendLiteralEndFinal = b->GetInsertBlock();
233
234        Value* hasMatchPartVec = b->CreateICmpULT(matchOffsetBeginPosVec, lz4BlockEndVec);
235        Value* hasMatchPartBitBlock = b->CreateZExt(hasMatchPartVec, b->getBitBlockType());
236        Value* hasMatchPartMask = b->CreateNeg(hasMatchPartBitBlock);
237
238        b->CreateLikelyCondBr(b->CreateICmpNE(b->CreateBitCast(hasMatchPartBitBlock, INT_BIT_BLOCK_TY), INT_BIT_BLOCK_TY_0), hasMatchPartBlock, exitBlock);
239
240        // ---- hasMatchPartBlock
241        b->SetInsertPoint(hasMatchPartBlock);
242        Value* initExtendMatchPosVec = b->CreateAdd(matchOffsetNextPosVec, shouldExtendMatchBitBlockVec);
243//        b->CallPrintRegister("initExtendMatchPosVec", initExtendMatchPosVec);
244        b->CreateCondBr(shouldExtendMatch, extendMatchCon, extendMatchExit);
245
246        // ---- extendMatchCon
247        b->SetInsertPoint(extendMatchCon);
248        PHINode* phiCurrentExtendMatchPosVec = b->CreatePHI(initExtendMatchPosVec->getType(), 2);
249        phiCurrentExtendMatchPosVec->addIncoming(initExtendMatchPosVec, hasMatchPartBlock);
250        PHINode* phiExtendMatchLengthVec = b->CreatePHI(b->getBitBlockType(), 2);
251        phiExtendMatchLengthVec->addIncoming(BIT_BLOCK_0, hasMatchPartBlock);
252
253        PHINode* phiShouldExtendMatchBitBlockVec = b->CreatePHI(shouldExtendMatchBitBlockVec->getType(), 2);
254        phiShouldExtendMatchBitBlockVec->addIncoming(shouldExtendMatchBitBlockVec, hasMatchPartBlock);
255        Value* shouldExtendMatchGatherMask = b->CreateNeg(phiShouldExtendMatchBitBlockVec);
256        shouldExtendMatchGatherMask = b->CreateAnd(shouldExtendMatchGatherMask, notFinishMask);
257        // TODO maybe we can load i64 once and then consume 8 times
258
259        Value* currentMatchLengthVec = this->simdFetchByteData(b, byteRawInputPtr, phiCurrentExtendMatchPosVec, shouldExtendMatchGatherMask);
260
261        Value* newExtendMatchLengthVec = b->CreateAdd(phiExtendMatchLengthVec, currentMatchLengthVec);
262
263
264        Value* shouldContinueExtendMatchVec = b->CreateICmpEQ(currentMatchLengthVec, BIT_BLOCK_FF);
265        Value* shouldContinueExtendMatchVecBitBlock = b->CreateZExt(shouldContinueExtendMatchVec, b->getBitBlockType());
266
267        Value* newExtendMatchPosVec = b->CreateAdd(phiCurrentExtendMatchPosVec, b->CreateAnd(shouldExtendMatchBitBlockVec, shouldContinueExtendMatchVecBitBlock));
268
269
270        phiCurrentExtendMatchPosVec->addIncoming(newExtendMatchPosVec, b->GetInsertBlock());
271        phiExtendMatchLengthVec->addIncoming(newExtendMatchLengthVec, b->GetInsertBlock());
272
273
274        phiShouldExtendMatchBitBlockVec->addIncoming(shouldContinueExtendMatchVecBitBlock, b->GetInsertBlock());
275        Value* shouldContinueExtendMatch = b->CreateICmpNE(b->CreateBitCast(shouldContinueExtendMatchVecBitBlock, INT_BIT_BLOCK_TY), INT_BIT_BLOCK_TY_0);
276
277        b->CreateCondBr(shouldContinueExtendMatch, extendMatchCon, extendMatchExit);
278
279
280        // ---- extendMatchExit
281        b->SetInsertPoint(extendMatchExit);
282
283        PHINode* matchExtendValueVec = b->CreatePHI(newExtendMatchLengthVec->getType(), 2);
284        matchExtendValueVec->addIncoming(BIT_BLOCK_0, hasMatchPartBlock);
285        matchExtendValueVec->addIncoming(newExtendMatchLengthVec, extendMatchCon);
286        PHINode* phiExtendMatchEndPos = b->CreatePHI(matchOffsetNextPosVec->getType(), 2);
287        phiExtendMatchEndPos->addIncoming(matchOffsetNextPosVec, hasMatchPartBlock);
288        phiExtendMatchEndPos->addIncoming(phiCurrentExtendMatchPosVec, extendMatchCon);
289
290
291        // matchLength = (size_t)token & 0xf + 4 + matchExtendValue
292        Value* matchLength = b->CreateAdd(
293                b->CreateAdd(matchExtendValueVec, b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 4))),
294                b->CreateAnd(tokenValuesVec, BIT_BLOCK_0F)
295        );
296        matchLength = b->CreateAnd(matchLength, hasMatchPartMask);
297
298
299        Value* matchOffsetVec =  b->CreateCall(
300                gatherFunc,
301                {
302                        UndefValue::get(b->getBitBlockType()),
303                        bytePtrBase,
304                        b->CreateTrunc(b->CreateSub(matchOffsetBeginPosVec, b->simd_fill(SIMD_WIDTH, firstTokenPos)), VectorType::get(b->getInt32Ty(), 4)),
305                        hasMatchPartMask,
306                        b->getInt8(1)
307                }
308        );
309        matchOffsetVec = b->CreateAnd(matchOffsetVec, notFinishMask);
310        matchOffsetVec = b->CreateAnd(matchOffsetVec, BIT_BLOCK_FFFF);
311
312//        Value* matchOffsetVec = this->simdFetchByteData(b, byteRawInputPtr, matchOffsetBeginPosVec, b->CreateAnd(hasMatchPartMask, notFinishMask));
313
314
315
316        this->handleSimdMatchCopy(b, matchOffsetVec, matchLength, outputPosAfterLiteralCpy);
317
318        Value* outputPosAfterMatchCpy = b->CreateAdd(outputPosAfterLiteralCpy, matchLength);
319
320        BasicBlock* extendMatchExitFinal = b->GetInsertBlock();
321
322        b->CreateBr(exitBlock);
323        // ---- exitBlock
324
325        b->SetInsertPoint(exitBlock);
326
327        PHINode* phiBeforeTokenPos = b->CreatePHI(matchOffsetNextPosVec->getType(), 2);
328        phiBeforeTokenPos->addIncoming(matchOffsetNextPosVec, extendLiteralEndFinal);
329        phiBeforeTokenPos->addIncoming(phiExtendMatchEndPos, extendMatchExitFinal);
330
331        PHINode* phiNewOutputPos = b->CreatePHI(outputPosAfterLiteralCpy->getType(), 2);
332        phiNewOutputPos->addIncoming(outputPosAfterLiteralCpy, extendLiteralEndFinal);
333        phiNewOutputPos->addIncoming(outputPosAfterMatchCpy, extendMatchExitFinal);
334//        b->CallPrintRegister("phiBeforeTokenPos", phiBeforeTokenPos);
335        Value* nextTokenPos = b->CreateAdd(phiBeforeTokenPos, BIT_BLOCK_1);
336//        b->CallPrintRegister("nextTokenPos", nextTokenPos);
337        return std::make_pair(nextTokenPos, phiNewOutputPos);
338    }
339
340    void LZ4ParallelByteStreamAioKernel::generateSimdDecompression(const std::unique_ptr<KernelBuilder> &b, Value* blockDataIndex) {
341        BasicBlock* entryBlock = b->GetInsertBlock();
342        BasicBlock* exitBlock = b->CreateBasicBlock("simdDecompressionExitBlock");
343        BasicBlock* processCon = b->CreateBasicBlock("simdDecompressionProcessConBlock");
344        BasicBlock* processBody = b->CreateBasicBlock("simdDecompressionProcessBodyBlock");
345
346        // ---- entryBlock
347        Value* blockStartVec = this->generateLoadSimdInt64NumberInput(b, "blockStart", blockDataIndex);
348        Value* blockEndVec = this->generateLoadSimdInt64NumberInput(b, "blockEnd", blockDataIndex);
349
350        Value* outputPos = b->getProducedItemCount("outputStream");
351        Value* initOutputPosVec = b->simd_fill(SIMD_WIDTH, outputPos);
352        initOutputPosVec = b->CreateAdd(
353                initOutputPosVec,
354                ConstantVector::get({
355                                            b->getIntN(SIMD_WIDTH, 0),
356                                            b->getIntN(SIMD_WIDTH, 1 * 4 * 1024 * 1024),
357                                            b->getIntN(SIMD_WIDTH, 2 * 4 * 1024 * 1024),
358                                            b->getIntN(SIMD_WIDTH, 3 * 4 * 1024 * 1024)
359                                    }));
360
361        // TODO handle uncompression blocks
362
363        b->CreateBr(processCon);
364
365        // ---- processCon
366        b->SetInsertPoint(processCon);
367        PHINode* phiCursorVec = b->CreatePHI(blockStartVec->getType(), 2);
368        phiCursorVec->addIncoming(blockStartVec, entryBlock);
369
370        PHINode* phiOutputPosVec = b->CreatePHI(initOutputPosVec->getType(), 2);
371        phiOutputPosVec->addIncoming(initOutputPosVec, entryBlock);
372
373
374        Value* hasRemaining = b->simd_ult(SIMD_WIDTH, phiCursorVec, blockEndVec);
375        hasRemaining = b->CreateICmpNE(b->CreateBitCast(hasRemaining, b->getIntNTy(256)), Constant::getNullValue(b->getIntNTy(256)));
376
377        b->CreateCondBr(hasRemaining, processBody, exitBlock);
378
379        // ---- processBody
380        b->SetInsertPoint(processBody);
381//        Value* newCursorVec = this->generateSimdAcceleration(b, phiCursorVec, blockEndVec);
382        auto ret = this->simdProcessBlockBoundary(b, phiCursorVec, blockEndVec, phiOutputPosVec);;
383        Value* newCursorVec = ret.first;
384        Value* newOutputPosVec = ret.second;
385//        b->CallPrintInt("newOutputPosVec", b->CreateExtractElement(newOutputPosVec, (uint64_t)0));
386
387        phiCursorVec->addIncoming(newCursorVec, b->GetInsertBlock());
388        phiOutputPosVec->addIncoming(newOutputPosVec, b->GetInsertBlock());
389
390        b->CreateBr(processCon);
391
392        // ---- exitBlock
393        b->SetInsertPoint(exitBlock);
394
395        uint64_t lastVecIndex = b->getBitBlockWidth() / SIMD_WIDTH - 1;
396        Value* lastBlockEnd = b->CreateExtractElement(blockEndVec, lastVecIndex);
397        b->setProcessedItemCount("byteStream", lastBlockEnd);
398
399        Value* lastOutputPos = b->CreateExtractElement(phiOutputPosVec, lastVecIndex);
400        b->setProducedItemCount("outputStream", lastOutputPos);
401//        b->CallPrintRegister("phiOutputPosVec", phiOutputPosVec);
402
403    }
404
405    void LZ4ParallelByteStreamAioKernel::generateDoSegmentMethod(const std::unique_ptr<KernelBuilder> &b) {
406        // Constant
407        Value* SIZE_1 = b->getSize(1);
408
409        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
410
411        Value * blockDataIndex = b->getProcessedItemCount("isCompressed");
412        Value * totalNumber = b->getAvailableItemCount("isCompressed");
413//        b->CallPrintInt("totalNumber", totalNumber);
414        Value * fileSize = b->getScalarField("fileSize");
415        Value * availableNumber = b->CreateSub(totalNumber, blockDataIndex);
416        Value * lastBlockEnd = this->generateLoadInt64NumberInput(b, "blockEnd", b->CreateSub(totalNumber, SIZE_1));
417        Value * isTerminal = b->CreateAnd(b->CreateICmpEQ(fileSize, lastBlockEnd), b->CreateICmpULE(availableNumber, b->getSize(b->getBitBlockWidth() / SIMD_WIDTH)));
418        b->setTerminationSignal(isTerminal);
419
420        BasicBlock* simdProcessEntryBlock = b->CreateBasicBlock("simdProcessEntryBlock");
421        BasicBlock* notEnoughSimdDataBlock = b->CreateBasicBlock("notEnoughSimdDataBlock");
422
423        b->CreateLikelyCondBr(b->CreateICmpUGE(availableNumber, b->getSize(b->getBitBlockWidth() / SIMD_WIDTH)), simdProcessEntryBlock, notEnoughSimdDataBlock);
424
425        // ---- simdProcessEntryBlock
426        b->SetInsertPoint(simdProcessEntryBlock);
427        this->generateSimdDecompression(b, blockDataIndex);
428        Value* newProcessedDataIndex = b->CreateAdd(blockDataIndex, b->getSize(b->getBitBlockWidth() / SIMD_WIDTH));
429        b->setProcessedItemCount("isCompressed", newProcessedDataIndex);
430
431        b->CreateBr(exitBlock);
432
433        // ---- notEnoughSimdDataBlock
434        b->SetInsertPoint(notEnoughSimdDataBlock);
435
436        BasicBlock* notSimdProcessBlock = b->CreateBasicBlock("notSimdProcessBlock");
437        b->CreateUnlikelyCondBr(isTerminal, notSimdProcessBlock, exitBlock);
438
439        // ---- notSimdProcessBlock
440        b->SetInsertPoint(notSimdProcessBlock);
441        // Use loop to process the remaining block in sequential approach (the number of the remaining block should be less than (b->getBitBlockWidth() / SIMD_WIDTH))
442        this->generateSequentialDecompression(b, blockDataIndex, totalNumber);
443        b->CreateBr(exitBlock);
444
445
446        // ---- ExitBlock
447        b->SetInsertPoint(exitBlock);
448    }
449
450    void LZ4ParallelByteStreamAioKernel::generateSequentialDecompression(const std::unique_ptr<KernelBuilder> &b, llvm::Value* startBlockDataIndex, llvm::Value* endBlockDataIndex) {
451
452        // ---- EntryBlock
453        BasicBlock* entryBlock = b->GetInsertBlock();
454
455        BasicBlock* SequentialConBlock = b->CreateBasicBlock("SequentialConBlock");
456        BasicBlock* SequentialBodyBlock = b->CreateBasicBlock("SequentialBodyBlock");
457        BasicBlock* SequentialExitBlock = b->CreateBasicBlock("SequentialExitBlock");
458
459
460        Value* initOutputPos = b->getProducedItemCount("outputStream");
461
462        b->CreateBr(SequentialConBlock);
463
464        // ---- SequentialConBlock
465        b->SetInsertPoint(SequentialConBlock);
466        PHINode* phiCurrentBlockDataIndex = b->CreatePHI(b->getSizeTy(), 2);
467        phiCurrentBlockDataIndex->addIncoming(startBlockDataIndex, entryBlock);
468        PHINode* phiOutputPos = b->CreatePHI(b->getSizeTy(), 2);
469        phiOutputPos->addIncoming(initOutputPos, entryBlock);
470
471        b->CreateCondBr(b->CreateICmpULT(phiCurrentBlockDataIndex, endBlockDataIndex), SequentialBodyBlock, SequentialExitBlock);
472
473        // ---- SequentialBodyBlock
474        b->SetInsertPoint(SequentialBodyBlock);
475        Value* lz4BlockStart = this->generateLoadInt64NumberInput(b, "blockStart", phiCurrentBlockDataIndex);
476        Value* lz4BlockEnd = this->generateLoadInt64NumberInput(b, "blockEnd", phiCurrentBlockDataIndex);
477        Value* newOutputPos = this->generateProcessCompressedBlock(b, lz4BlockStart, lz4BlockEnd, phiOutputPos);
478
479        b->setProcessedItemCount("byteStream", lz4BlockEnd);
480        b->setProducedItemCount("outputStream", newOutputPos);
481
482        phiCurrentBlockDataIndex->addIncoming(b->CreateAdd(phiCurrentBlockDataIndex, b->getSize(1)), b->GetInsertBlock());
483        phiOutputPos->addIncoming(newOutputPos, b->GetInsertBlock());
484
485        b->CreateBr(SequentialConBlock);
486
487        // ---- SequentialExitBlock
488        b->SetInsertPoint(SequentialExitBlock);
489        b->setProcessedItemCount("isCompressed", endBlockDataIndex);
490
491    }
492
493    llvm::Value *
494    LZ4ParallelByteStreamAioKernel::generateLoadSimdInt64NumberInput(const std::unique_ptr<KernelBuilder> &iBuilder, std::string inputBufferName,
495                                     llvm::Value *globalOffset) {
496        Value * capacity = iBuilder->getCapacity(inputBufferName);
497        Value * processed = iBuilder->getProcessedItemCount(inputBufferName);
498        processed = iBuilder->CreateAnd(processed, iBuilder->CreateNeg(capacity));
499        Value * offset = iBuilder->CreateSub(globalOffset, processed);
500        Value * valuePtr = iBuilder->getRawInputPointer(inputBufferName, offset);
501        valuePtr = iBuilder->CreatePointerCast(valuePtr, iBuilder->getBitBlockType()->getPointerTo());
502        return iBuilder->CreateLoad(valuePtr);
503    }
504
505    llvm::Value *LZ4ParallelByteStreamAioKernel::generateLoadInt64NumberInput(const std::unique_ptr<KernelBuilder> &iBuilder,
506                                                                      std::string inputBufferName, llvm::Value *globalOffset) {
507
508        Value * capacity = iBuilder->getCapacity(inputBufferName);
509        Value * processed = iBuilder->getProcessedItemCount(inputBufferName);
510        processed = iBuilder->CreateAnd(processed, iBuilder->CreateNeg(capacity));
511        Value * offset = iBuilder->CreateSub(globalOffset, processed);
512        Value * valuePtr = iBuilder->getRawInputPointer(inputBufferName, offset);
513        return iBuilder->CreateLoad(valuePtr);
514    }
515
516    llvm::Value*
517    LZ4ParallelByteStreamAioKernel::generateProcessCompressedBlock(const std::unique_ptr<KernelBuilder> &b, llvm::Value *lz4BlockStart,
518                                                           llvm::Value *lz4BlockEnd, llvm::Value* initOutputPos) {
519        BasicBlock* entryBlock = b->GetInsertBlock();
520
521        Value* isTerminal = b->CreateICmpEQ(lz4BlockEnd, b->getScalarField("fileSize"));
522        b->setTerminationSignal(isTerminal);
523
524        BasicBlock* exitBlock = b->CreateBasicBlock("processCompressedExitBlock");
525
526        BasicBlock* processCon = b->CreateBasicBlock("processCompressedConBlock");
527        BasicBlock* processBody = b->CreateBasicBlock("processCompressedBodyBlock");
528
529
530        BasicBlock* beforeProcessConBlock = b->GetInsertBlock();
531        b->CreateBr(processCon);
532        b->SetInsertPoint(processCon);
533        PHINode* phiOutputPos = b->CreatePHI(initOutputPos->getType(), 2);
534        phiOutputPos->addIncoming(initOutputPos, entryBlock);
535        PHINode* phiCursorValue = b->CreatePHI(b->getInt64Ty(), 2); // phiCursorValue should always be the position of next token except for the final sequence
536        phiCursorValue->addIncoming(lz4BlockStart, beforeProcessConBlock);
537
538        b->CreateCondBr(b->CreateICmpULT(phiCursorValue, lz4BlockEnd), processBody, exitBlock);
539
540        b->SetInsertPoint(processBody);
541
542
543        auto ret = this->processBlockBoundary(b, phiCursorValue, lz4BlockEnd, phiOutputPos);
544        Value* nextTokenGlobalPos = ret.first;
545        Value* nextOutputPos = ret.second;
546
547        phiOutputPos->addIncoming(nextOutputPos, b->GetInsertBlock());
548        phiCursorValue->addIncoming(nextTokenGlobalPos, b->GetInsertBlock());
549        b->CreateBr(processCon);
550
551        b->SetInsertPoint(exitBlock);
552        return phiOutputPos;
553    }
554
555
556    std::pair<llvm::Value *, llvm::Value *> LZ4ParallelByteStreamAioKernel::processBlockBoundary(const std::unique_ptr<KernelBuilder> &b, llvm::Value *beginTokenPos,
557                                                              llvm::Value *lz4BlockEnd, llvm::Value* initOutputPos) {
558        // Constant
559        ConstantInt* SIZE_0 = b->getSize(0);
560        ConstantInt* SIZE_1 = b->getSize(1);
561        ConstantInt* BYTE_FF = b->getInt8(0xff);
562        Value* BYTE_F0 = b->getInt8(0xf0);
563        Value* BYTE_0F = b->getInt8(0x0f);
564
565        // ---- EntryBlock
566        BasicBlock* entryBlock = b->GetInsertBlock();
567        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
568
569        Value* bytePtrBase = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
570
571        Value* tokenValue = b->CreateLoad(b->CreateGEP(bytePtrBase, beginTokenPos));
572
573        Value* shouldExtendLiteral = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_F0), BYTE_F0);
574
575        Value* shouldExtendMatch = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_0F), BYTE_0F);
576
577        BasicBlock* extendLiteralCond = b->CreateBasicBlock("extendLiteralCond");
578        BasicBlock* extendLiteralEnd = b->CreateBasicBlock("extendLiteralEnd");
579
580        Value* initExtendLiteralPos = b->CreateAdd(beginTokenPos, b->getSize(1));
581
582        b->CreateCondBr(shouldExtendLiteral, extendLiteralCond, extendLiteralEnd);
583
584        // ---- extendLiteralCond
585        b->SetInsertPoint(extendLiteralCond);
586        PHINode* phiCurrentExtendLiteralPos = b->CreatePHI(b->getSizeTy(), 2);
587        phiCurrentExtendLiteralPos->addIncoming(initExtendLiteralPos, entryBlock);
588        PHINode* phiExtendLiteralLength = b->CreatePHI(b->getSizeTy(), 2);
589        phiExtendLiteralLength->addIncoming(SIZE_0, entryBlock);
590
591        Value* currentLiteralLengthByte = b->CreateLoad(b->CreateGEP(bytePtrBase, phiCurrentExtendLiteralPos));
592        Value* newExtendLiteralLength = b->CreateAdd(phiExtendLiteralLength, b->CreateZExt(currentLiteralLengthByte, b->getSizeTy()));
593
594        phiCurrentExtendLiteralPos->addIncoming(b->CreateAdd(phiCurrentExtendLiteralPos, SIZE_1), b->GetInsertBlock());
595        phiExtendLiteralLength->addIncoming(newExtendLiteralLength, b->GetInsertBlock());
596
597        b->CreateCondBr(b->CreateICmpEQ(currentLiteralLengthByte, BYTE_FF), extendLiteralCond, extendLiteralEnd);
598
599        // ---- extendLiteralEnd
600        b->SetInsertPoint(extendLiteralEnd);
601        PHINode* literalExtendValue = b->CreatePHI(b->getSizeTy(), 2);
602        literalExtendValue->addIncoming(SIZE_0, entryBlock);
603        literalExtendValue->addIncoming(newExtendLiteralLength, extendLiteralCond);
604        PHINode* phiExtendLiteralEndPos = b->CreatePHI(b->getSizeTy(), 2);
605        phiExtendLiteralEndPos->addIncoming(beginTokenPos, entryBlock);
606        phiExtendLiteralEndPos->addIncoming(phiCurrentExtendLiteralPos, extendLiteralCond);
607
608        Value* literalLength = b->CreateAdd(literalExtendValue, b->CreateZExt(b->CreateLShr(tokenValue, b->getInt8(4)), b->getSizeTy()));
609
610        Value* literalStartPos = b->CreateAdd(phiExtendLiteralEndPos, SIZE_1);
611        Value* literalEndPos = b->CreateAdd(literalStartPos, literalLength);
612
613        Value* matchOffsetBeginPos = literalEndPos;
614        Value* matchOffsetNextPos = b->CreateAdd(matchOffsetBeginPos, SIZE_1);
615
616        BasicBlock* hasMatchPartBlock = b->CreateBasicBlock("hasMatchPartBlock");
617        BasicBlock* extendMatchCon = b->CreateBasicBlock("extendMatchCon");
618        BasicBlock* extendMatchExit = b->CreateBasicBlock("extendMatchExit");
619
620        // This literal copy will always cross 64 bits literal boundary
621        this->handleLiteralCopy(b, literalStartPos, literalLength, initOutputPos);
622
623        Value* outputPosAfterLiteralCpy = b->CreateAdd(literalLength, initOutputPos);
624
625        BasicBlock* extendLiteralEndFinal = b->GetInsertBlock();
626
627        b->CreateLikelyCondBr(b->CreateICmpULT(matchOffsetBeginPos, lz4BlockEnd), hasMatchPartBlock, exitBlock);
628
629        // ---- hasMatchPartBlock
630        b->SetInsertPoint(hasMatchPartBlock);
631        Value* initExtendMatchPos = b->CreateAdd(matchOffsetBeginPos, b->getSize(2));
632        b->CreateCondBr(shouldExtendMatch, extendMatchCon, extendMatchExit);
633
634        // ---- extendMatchCon
635        b->SetInsertPoint(extendMatchCon);
636        PHINode* phiCurrentExtendMatchPos = b->CreatePHI(b->getSizeTy(), 2);
637        phiCurrentExtendMatchPos->addIncoming(initExtendMatchPos, hasMatchPartBlock);
638        PHINode* phiExtendMatchLength = b->CreatePHI(b->getSizeTy(), 2);
639        phiExtendMatchLength->addIncoming(SIZE_0, hasMatchPartBlock);
640
641        Value* currentMatchLengthByte = b->CreateLoad(b->CreateGEP(bytePtrBase, phiCurrentExtendMatchPos));
642        Value* newExtendMatchLength = b->CreateAdd(phiExtendMatchLength, b->CreateZExt(currentMatchLengthByte, b->getSizeTy()));
643
644        phiCurrentExtendMatchPos->addIncoming(b->CreateAdd(phiCurrentExtendMatchPos, SIZE_1), b->GetInsertBlock());
645        phiExtendMatchLength->addIncoming(newExtendMatchLength, b->GetInsertBlock());
646
647        b->CreateCondBr(b->CreateICmpEQ(currentMatchLengthByte, BYTE_FF), extendMatchCon, extendMatchExit);
648
649        // ---- extendMatchExit
650        b->SetInsertPoint(extendMatchExit);
651        PHINode* matchExtendValue = b->CreatePHI(b->getSizeTy(), 2);
652        matchExtendValue->addIncoming(SIZE_0, hasMatchPartBlock);
653        matchExtendValue->addIncoming(newExtendMatchLength, extendMatchCon);
654        PHINode* phiExtendMatchEndPos = b->CreatePHI(b->getSizeTy(), 2);
655        phiExtendMatchEndPos->addIncoming(matchOffsetNextPos, hasMatchPartBlock);
656        phiExtendMatchEndPos->addIncoming(phiCurrentExtendMatchPos, extendMatchCon);
657
658        // matchLength = (size_t)token & 0xf + 4 + matchExtendValue
659        Value* matchLength = b->CreateAdd(
660                b->CreateAdd(matchExtendValue, b->getSize(4)),
661                b->CreateZExt(b->CreateAnd(tokenValue, BYTE_0F), b->getSizeTy())
662        );
663
664        Value* matchOffsetPtr = b->getRawInputPointer("byteStream", matchOffsetBeginPos);
665        // For now, it is safe to cast matchOffset pointer into i16 since the input byte stream is always linear available
666        matchOffsetPtr = b->CreatePointerCast(matchOffsetPtr, b->getInt16Ty()->getPointerTo());
667        Value* matchOffset = b->CreateZExt(b->CreateLoad(matchOffsetPtr), b->getSizeTy());
668        this->handleMatchCopy(b, matchOffset, matchLength, outputPosAfterLiteralCpy);
669        Value* outputPosAfterMatchCpy = b->CreateAdd(outputPosAfterLiteralCpy, matchLength);
670        BasicBlock* extendMatchExitFinal = b->GetInsertBlock();
671        b->CreateBr(exitBlock);
672
673        // ---- exitBlock
674        b->SetInsertPoint(exitBlock);
675        PHINode* phiBeforeTokenPos = b->CreatePHI(b->getSizeTy(), 2);
676        phiBeforeTokenPos->addIncoming(matchOffsetNextPos, extendLiteralEndFinal);
677        phiBeforeTokenPos->addIncoming(phiExtendMatchEndPos, extendMatchExitFinal);
678        PHINode* phiOutputPos = b->CreatePHI(b->getSizeTy(), 2);
679        phiOutputPos->addIncoming(outputPosAfterLiteralCpy, extendLiteralEndFinal);
680        phiOutputPos->addIncoming(outputPosAfterMatchCpy, extendMatchExitFinal);
681
682        Value* nextTokenPos = b->CreateAdd(phiBeforeTokenPos, SIZE_1);
683
684        return std::make_pair(nextTokenPos, phiOutputPos);
685    }
686
687
688    void LZ4ParallelByteStreamAioKernel::handleSimdMatchCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value* matchOffsetVec, llvm::Value* matchLengthVec, llvm::Value* outputPosVec) {
689        // TODO use memcpy first
690        Value* l = b->CreateExtractElement(matchLengthVec, (uint64_t)0);
691        Value* shouldPrint = b->CreateICmpNE(l, b->getSize(0));
692//        b->CallPrintIntCond("matchOffset", b->CreateExtractElement(matchOffsetVec, (uint64_t)0), shouldPrint);
693//        b->CallPrintIntCond("matchLength", l, shouldPrint);
694        BasicBlock* entryBlock = b->GetInsertBlock();
695        Value* outputCapacity = b->getCapacity("outputStream");
696        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", b->getSize(0)), b->getInt8PtrTy());
697
698        for (uint64_t i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
699            BasicBlock* matchCopyConBlock = b->CreateBasicBlock("matchCopyConBlock" + std::to_string(i));
700            BasicBlock* matchCopyBodyBlock = b->CreateBasicBlock("matchCopyBodyBlock" + std::to_string(i));
701            BasicBlock* matchCopyExitBlock = b->CreateBasicBlock("matchCopyExitBlock" + std::to_string(i));
702
703            BasicBlock* beforeConBlock = b->GetInsertBlock();
704
705            Value* matchOffset = b->CreateExtractElement(matchOffsetVec, i);
706            Value* initMatchLength = b->CreateExtractElement(matchLengthVec, i);
707            Value* initOutputPos = b->CreateExtractElement(outputPosVec, i);
708//            b->CreateLikelyCondBr(b->CreateICmpNE(matchOffset, b->getSize(0)), matchCopyConBlock, matchCopyExitBlock);
709            b->CreateBr(matchCopyConBlock);
710
711            // ---- matchCopyConBlock
712            b->SetInsertPoint(matchCopyConBlock);
713            PHINode* phiMatchLength = b->CreatePHI(initMatchLength->getType(), 2);
714            phiMatchLength->addIncoming(initMatchLength, beforeConBlock);
715            PHINode* phiOutputPos = b->CreatePHI(initOutputPos->getType(), 2);
716            phiOutputPos->addIncoming(initOutputPos, beforeConBlock);
717//            b->CallPrintInt("phiMatchLength", phiMatchLength);
718//            b->CallPrintInt("matchOffset", matchOffset);
719
720            b->CreateCondBr(b->CreateICmpUGT(phiMatchLength, b->getSize(0)), matchCopyBodyBlock, matchCopyExitBlock);
721
722            // ---- matchCopyBodyBlock
723            b->SetInsertPoint(matchCopyBodyBlock);
724            Value* copySize = b->CreateUMin(phiMatchLength, matchOffset);
725            Value* copyFromPos = b->CreateSub(phiOutputPos, matchOffset);
726
727            b->CreateMemCpy(
728                    b->CreateGEP(outputBasePtr, b->CreateURem(phiOutputPos, outputCapacity)),
729                    b->CreateGEP(outputBasePtr, b->CreateURem(copyFromPos, outputCapacity)),
730                    copySize,
731                    1
732            );
733
734            phiMatchLength->addIncoming(b->CreateSub(phiMatchLength, copySize), b->GetInsertBlock());
735            phiOutputPos->addIncoming(b->CreateAdd(phiOutputPos, copySize), b->GetInsertBlock());
736
737            b->CreateBr(matchCopyConBlock);
738
739            // ---- matchCopyExitBlock
740            b->SetInsertPoint(matchCopyExitBlock);
741        }
742    }
743
744    void LZ4ParallelByteStreamAioKernel::handleSimdLiteralCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value* literalStartVec, llvm::Value* literalLengthVec, llvm::Value* outputPosVec) {
745        Value* l = b->CreateExtractElement(literalLengthVec, (uint64_t)0);
746
747        Value* outputCapacity = b->getCapacity("outputStream");
748        Value* outputPosRemVec = b->simd_and(outputPosVec, b->simd_fill(SIMD_WIDTH, b->simd_not(b->CreateNeg(outputCapacity))));
749        // TODO use memcpy first
750
751        BasicBlock* entryBlock = b->GetInsertBlock();
752
753
754        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
755        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", b->getSize(0)), b->getInt8PtrTy());
756
757        for (uint64_t i = 0; i < b->getBitBlockWidth() / SIMD_WIDTH; i++) {
758            Value* literalStart = b->CreateExtractElement(literalStartVec, i);
759            Value* literalLength = b->CreateExtractElement(literalLengthVec, i);
760            Value* outputPosRem = b->CreateExtractElement(outputPosRemVec, i);;
761            b->CreateMemCpy(
762                    b->CreateGEP(outputBasePtr, outputPosRem),
763                    b->CreateGEP(inputBasePtr, literalStart),
764                    literalLength,
765                    1
766            );
767        }
768
769    }
770
771    void LZ4ParallelByteStreamAioKernel::handleLiteralCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *literalStart,
772                                                   llvm::Value *literalLength, llvm::Value* outputPos) {
773        unsigned fw = 64;
774        Type* INT_FW_PTR = b->getIntNTy(fw)->getPointerTo();
775
776        Value* inputBytePtr = b->getRawInputPointer("byteStream", literalStart);
777        Value* inputPtr = b->CreatePointerCast(inputBytePtr, INT_FW_PTR);
778
779        Value* outputBufferSize = b->getCapacity("outputStream");
780        Value* outputPtr = b->getRawOutputPointer("outputStream", b->CreateURem(outputPos, outputBufferSize));
781        outputPtr = b->CreatePointerCast(outputPtr, INT_FW_PTR);
782
783        // We can always assume that we have enough output buffer based on our output buffer allocation strategy (except in extract only case)
784
785        BasicBlock* entryBlock = b->GetInsertBlock();
786        BasicBlock* literalCopyCon = b->CreateBasicBlock("literalCopyCon");
787        BasicBlock* literalCopyBody = b->CreateBasicBlock("literalCopyBody");
788        BasicBlock* literalCopyExit = b->CreateBasicBlock("literalCopyExit");
789
790        b->CreateBr(literalCopyCon);
791
792        // ---- literalCopyCon
793        b->SetInsertPoint(literalCopyCon);
794        PHINode* phiOutputPtr = b->CreatePHI(outputPtr->getType(), 2);
795        phiOutputPtr->addIncoming(outputPtr, entryBlock);
796        PHINode* phiInputPtr = b->CreatePHI(inputPtr->getType(), 2);
797        phiInputPtr->addIncoming(inputPtr, entryBlock);
798        PHINode* phiCopiedLength = b->CreatePHI(literalLength->getType(), 2);
799        phiCopiedLength->addIncoming(b->getSize(0), entryBlock);
800        b->CreateCondBr(b->CreateICmpULT(phiCopiedLength, literalLength), literalCopyBody, literalCopyExit);
801
802        // ---- literalCopyBody
803        b->SetInsertPoint(literalCopyBody);
804        // Always copy fw bits to improve performance
805        b->CreateStore(b->CreateLoad(phiInputPtr), phiOutputPtr);
806
807        phiInputPtr->addIncoming(b->CreateGEP(phiInputPtr, b->getSize(1)), b->GetInsertBlock());
808        phiOutputPtr->addIncoming(b->CreateGEP(phiOutputPtr, b->getSize(1)), b->GetInsertBlock());
809        phiCopiedLength->addIncoming(b->CreateAdd(phiCopiedLength, b->getSize(fw / 8)), b->GetInsertBlock());
810        b->CreateBr(literalCopyCon);
811
812        // ---- literalCopyExit
813        b->SetInsertPoint(literalCopyExit);
814        b->setScalarField("outputPos", b->CreateAdd(outputPos, literalLength));
815    }
816
817    void LZ4ParallelByteStreamAioKernel::handleMatchCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *matchOffset,
818                                                 llvm::Value *matchLength, llvm::Value* outputPos) {
819        unsigned fw = 64;
820        Type* INT_FW_PTR = b->getIntNTy(fw)->getPointerTo();
821
822        BasicBlock* entryBlock = b->GetInsertBlock();
823
824        Value* outputBufferSize = b->getCapacity("outputStream");
825
826        Value* copyToPtr = b->getRawOutputPointer("outputStream", b->CreateURem(outputPos, outputBufferSize));
827        Value* copyFromPtr = b->getRawOutputPointer("outputStream", b->CreateURem(b->CreateSub(outputPos, matchOffset), outputBufferSize));
828
829        BasicBlock* matchCopyCon = b->CreateBasicBlock("matchCopyCon");
830        BasicBlock* matchCopyBody = b->CreateBasicBlock("matchCopyBody");
831        BasicBlock* matchCopyExit = b->CreateBasicBlock("matchCopyExit");
832
833        b->CreateBr(matchCopyCon);
834
835        // ---- matchCopyCon
836        b->SetInsertPoint(matchCopyCon);
837        PHINode* phiFromPtr = b->CreatePHI(b->getInt8PtrTy(), 2);
838        phiFromPtr->addIncoming(copyFromPtr, entryBlock);
839        PHINode* phiToPtr = b->CreatePHI(b->getInt8PtrTy(), 2);
840        phiToPtr->addIncoming(copyToPtr, entryBlock);
841        PHINode* phiCopiedSize = b->CreatePHI(b->getSizeTy(), 2);
842        phiCopiedSize->addIncoming(b->getSize(0), entryBlock);
843
844        b->CreateCondBr(b->CreateICmpULT(phiCopiedSize, matchLength), matchCopyBody, matchCopyExit);
845
846        // ---- matchCopyBody
847        b->SetInsertPoint(matchCopyBody);
848        b->CreateStore(
849                b->CreateLoad(b->CreatePointerCast(phiFromPtr, INT_FW_PTR)),
850                b->CreatePointerCast(phiToPtr, INT_FW_PTR)
851        );
852
853        Value* copySize = b->CreateUMin(matchOffset, b->getSize(fw / 8));
854        phiFromPtr->addIncoming(b->CreateGEP(phiFromPtr, copySize), b->GetInsertBlock());
855        phiToPtr->addIncoming(b->CreateGEP(phiToPtr, copySize), b->GetInsertBlock());
856        phiCopiedSize->addIncoming(b->CreateAdd(phiCopiedSize, copySize), b->GetInsertBlock());
857        b->CreateBr(matchCopyCon);
858
859        // ---- matchCopyExit
860        b->SetInsertPoint(matchCopyExit);
861        b->setScalarField("outputPos", b->CreateAdd(outputPos, matchLength));
862    }
863
864    llvm::Value* LZ4ParallelByteStreamAioKernel::simdFetchByteData(const std::unique_ptr<KernelBuilder> &b, llvm::Value* basePtr, llvm::Value* offsetVec, llvm::Value* mask) {
865        return this->simdFetchByteDataByGather(b, basePtr, offsetVec, mask);
866//        return this->simdFetchByteDataByLoop(b, basePtr, offsetVec, mask);
867    }
868
869    llvm::Value* LZ4ParallelByteStreamAioKernel::simdFetchByteDataByGather(const std::unique_ptr<KernelBuilder> &b, llvm::Value* basePtr, llvm::Value* offsetVec, llvm::Value* mask) {
870        Value* BIT_BLOCK_FF = b->simd_fill(SIMD_WIDTH, b->getIntN(SIMD_WIDTH, 0xff));
871        Function *gatherFunc = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx2_gather_d_q_256);
872        Function *gatherFunc2 = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_avx2_gather_d_d);
873
874        Value* firstOffset = b->CreateExtractElement(offsetVec, (uint64_t)0);
875
876        Type* i32BitBlockTy = VectorType::get(b->getInt32Ty(), 4);
877
878//        Value* tokenValuesVec =  b->CreateCall(
879//                gatherFunc,
880//                {
881//                        UndefValue::get(b->getBitBlockType()),
882//                        b->CreateGEP(basePtr, firstOffset),
883//                        b->CreateTrunc(b->CreateSub(offsetVec, b->simd_fill(SIMD_WIDTH, firstOffset)), VectorType::get(b->getInt32Ty(), 4)),
884//                        mask,
885//                        b->getInt8(1)
886//                }
887//        );
888
889        ////
890        Value* tokenValuesVec =  b->CreateCall(
891                gatherFunc2,
892                {
893                        UndefValue::get(i32BitBlockTy),
894                        b->CreateGEP(basePtr, firstOffset),
895                        b->CreateTrunc(b->CreateSub(offsetVec, b->simd_fill(SIMD_WIDTH, firstOffset)), VectorType::get(b->getInt32Ty(), 4)),
896                        b->CreateTrunc(mask, i32BitBlockTy),
897                        b->getInt8(1)
898                }
899        );
900        tokenValuesVec = b->CreateZExt(tokenValuesVec, b->getBitBlockType());
901        /////
902       
903        tokenValuesVec = b->CreateAnd(tokenValuesVec, mask);
904        tokenValuesVec = b->CreateAnd(tokenValuesVec, BIT_BLOCK_FF);
905        return tokenValuesVec;
906    }
907
908    llvm::Value* LZ4ParallelByteStreamAioKernel::simdFetchByteDataByLoop(const std::unique_ptr<KernelBuilder> &b, llvm::Value* basePtr, llvm::Value* offsetVec, llvm::Value* maskVec) {
909        Value* retVec = ConstantVector::getNullValue(b->getBitBlockType());
910
911        for (uint64_t i = 0; i < 4; i++){ //TODO 4 here is a hardcode for AVX2, it may need to be changed to (BitBlockWidth / 64)
912            Value* mask = b->CreateExtractElement(maskVec, i);
913            Value* shouldLoad = b->CreateICmpNE(mask, b->getInt64(0));
914            Value* loadPtr = b->CreateSelect(shouldLoad, b->CreateGEP(basePtr, b->CreateExtractElement(offsetVec, i)), basePtr);
915            Value* loadValue = b->CreateZExt(b->CreateLoad(loadPtr), b->getInt64Ty());
916
917            Value* finalValue = b->CreateSelect(shouldLoad, loadValue, b->getInt64(0));
918            retVec = b->CreateInsertElement(retVec, finalValue, i);
919        }
920
921        return retVec;
922    }
923
924}
Note: See TracBrowser for help on using the repository browser.