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

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

fix some warning in lz4 related kernels

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