source: icGREP/icgrep-devel/icgrep/kernels/lz4/lz4_bytestream_aio.cpp @ 6061

Last change on this file since 6061 was 6061, checked in by xwa163, 13 months ago

Improve the output performance of LZ4ByteStreamAIO kernel by using load/store instruction directly instead of memcpy. The performance of LZ4_Grep pipeline with LZ4BytestreamAio kernel now is slightly better than the standard LZ4 implementation in large file.

File size: 31.7 KB
Line 
1
2#include "lz4_bytestream_aio.h"
3
4
5#include <kernels/kernel_builder.h>
6#include <iostream>
7#include <string>
8#include <llvm/Support/raw_ostream.h>
9#include <kernels/streamset.h>
10
11using namespace llvm;
12using namespace kernel;
13using namespace std;
14
15
16namespace kernel{
17
18    LZ4ByteStreamAioKernel::LZ4ByteStreamAioKernel(const std::unique_ptr<kernel::KernelBuilder> &b)
19            :SegmentOrientedKernel("LZ4ByteStreamAioKernel",
20            // Inputs
21                                   {
22                                           Binding{b->getStreamSetTy(1, 8), "byteStream", BoundedRate(0, 1)},
23                                           Binding{b->getStreamSetTy(1, 1), "extender", RateEqualTo("byteStream")},
24
25                                           // block data
26                                           Binding{b->getStreamSetTy(1, 1), "isCompressed", BoundedRate(0, 1), AlwaysConsume()},
27                                           Binding{b->getStreamSetTy(1, 64), "blockStart", RateEqualTo("isCompressed"), AlwaysConsume()},
28                                           Binding{b->getStreamSetTy(1, 64), "blockEnd", RateEqualTo("isCompressed"), AlwaysConsume()}
29
30                                   },
31            //Outputs
32                                   {
33                                           Binding{b->getStreamSetTy(1, 8), "outputStream", BoundedRate(0, 1)},
34                                   },
35            //Arguments
36                                   {
37                                           Binding{b->getSizeTy(), "fileSize"}
38                                   },
39                                   {},
40            //Internal states:
41                                   {
42                    Binding{b->getInt64Ty(), "tempTimes"},
43                    Binding{b->getSizeTy(), "blockDataIndex"},
44                    Binding{b->getInt64Ty(), "outputPos"},
45
46
47            }){
48        this->setStride(4 * 1024 * 1024);
49        addAttribute(MustExplicitlyTerminate());
50    }
51
52    void LZ4ByteStreamAioKernel::generateDoSegmentMethod(const std::unique_ptr<KernelBuilder> &b) {
53        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
54        BasicBlock* blockEndConBlock = b->CreateBasicBlock("blockEndConBlock");
55
56        Value * blockDataIndex = b->getScalarField("blockDataIndex");
57
58        // In MultiblockKernel, availableItemCount + processedItemCount == producedItemCount from previous kernel
59        // While in SegmentOrigentedKernel, availableItemCount == producedItemCount from previous kernel
60        Value * totalNumber = b->getAvailableItemCount("blockEnd");
61        Value * totalExtender = b->getAvailableItemCount("extender");
62
63        Value * blockEnd = this->generateLoadInt64NumberInput(b, "blockEnd", blockDataIndex);
64
65        b->CreateCondBr(b->CreateICmpULT(blockDataIndex, totalNumber), blockEndConBlock, exitBlock);
66
67        b->SetInsertPoint(blockEndConBlock);
68        Value * blockStart = this->generateLoadInt64NumberInput(b, "blockStart", blockDataIndex);
69        BasicBlock * processBlock = b->CreateBasicBlock("processBlock");
70        b->CreateCondBr(b->CreateICmpULE(blockEnd, totalExtender), processBlock, exitBlock);
71
72        b->SetInsertPoint(processBlock);
73
74        //TODO handle uncompressed block
75        this->generateProcessCompressedBlock(b, blockStart, blockEnd);
76        // TODO store pending value
77//        this->storePendingM0(b);
78//        this->storePendingLiteralMask(b);
79//        this->storePendingMatchOffsetMarker(b);
80        Value * newBlockDataIndex = b->CreateAdd(blockDataIndex, b->getInt64(1));
81        b->setScalarField("blockDataIndex", newBlockDataIndex);
82        b->setProcessedItemCount("isCompressed", newBlockDataIndex);
83        b->setProcessedItemCount("byteStream", blockEnd);
84        b->setProducedItemCount("outputStream", b->getScalarField("outputPos"));
85        b->CreateBr(exitBlock);
86
87        b->SetInsertPoint(exitBlock);
88//        b->CallPrintIntCond("time", b->getScalarField("tempTimes"), b->getTerminationSignal());
89    }
90
91    llvm::Value *LZ4ByteStreamAioKernel::generateLoadInt64NumberInput(const std::unique_ptr<KernelBuilder> &iBuilder,
92                                                            std::string inputBufferName, llvm::Value *globalOffset) {
93
94        Value * capacity = iBuilder->getCapacity(inputBufferName);
95        Value * processed = iBuilder->getProcessedItemCount(inputBufferName);
96        processed = iBuilder->CreateAnd(processed, iBuilder->CreateNeg(capacity));
97        Value * offset = iBuilder->CreateSub(globalOffset, processed);
98        Value * valuePtr = iBuilder->getRawInputPointer(inputBufferName, offset);
99        return iBuilder->CreateLoad(valuePtr);
100    }
101
102    void
103    LZ4ByteStreamAioKernel::generateProcessCompressedBlock(const std::unique_ptr<KernelBuilder> &b, llvm::Value *lz4BlockStart,
104                                                 llvm::Value *lz4BlockEnd) {
105        BasicBlock* entryBlock = b->GetInsertBlock();
106
107        Value* isTerminal = b->CreateICmpEQ(lz4BlockEnd, b->getScalarField("fileSize"));
108        b->setTerminationSignal(isTerminal);
109
110        BasicBlock* exitBlock = b->CreateBasicBlock("processCompressedExitBlock");
111
112        BasicBlock* processCon = b->CreateBasicBlock("processCompressedConBlock");
113        BasicBlock* processBody = b->CreateBasicBlock("processCompressedBodyBlock");
114
115
116        // TODO
117        // We store all of the pending data before the parabixBlock of lz4BlockStart to make sure the current pending
118        // block will be the same as the block we process during the acceleration
119//        this->storePendingLiteralMasksUntilPos(b, lz4BlockStart);
120        // TODO handle matchOffsetMarker, and maybe we also need to handle M0Marker here
121
122
123
124        BasicBlock* beforeProcessConBlock = b->GetInsertBlock();
125        b->CreateBr(processCon);
126        b->SetInsertPoint(processCon);
127
128
129        PHINode* phiCursorValue = b->CreatePHI(b->getInt64Ty(), 2, "phiCursorValue"); // phiCursorValue should always be the position of next token except for the final sequence
130        phiCursorValue->addIncoming(lz4BlockStart, beforeProcessConBlock);
131
132        b->CreateCondBr(b->CreateICmpULT(phiCursorValue, lz4BlockEnd), processBody, exitBlock);
133
134        b->SetInsertPoint(processBody);
135
136        /*
137        auto accelerationRet = this->generateAcceleration(b, phiCursorValue, lz4BlockEnd);
138        Value* tokenMarkers = accelerationRet.first.first;
139
140        Value* cursorBlockPosBase = b->CreateSub(phiCursorValue, b->CreateURem(phiCursorValue, b->getSize(ACCELERATION_WIDTH)));
141        Value* nextTokenLocalPos = b->CreateSub(b->CreateSub(b->getSize(ACCELERATION_WIDTH), b->CreateCountReverseZeroes(tokenMarkers)), b->getSize(1));
142        Value* nextTokenGlobalPos = b->CreateAdd(cursorBlockPosBase, nextTokenLocalPos);
143
144        nextTokenGlobalPos = this->processBlockBoundary(b, nextTokenGlobalPos, lz4BlockEnd);
145        */
146
147        Value* nextTokenGlobalPos = this->processBlockBoundary(b, phiCursorValue, lz4BlockEnd);
148        phiCursorValue->addIncoming(nextTokenGlobalPos, b->GetInsertBlock());
149        b->CreateBr(processCon);
150
151        b->SetInsertPoint(exitBlock);
152    }
153
154    std::pair<std::pair<llvm::Value *, llvm::Value *>, llvm::Value *>
155    LZ4ByteStreamAioKernel::generateAcceleration(const std::unique_ptr<KernelBuilder> &b, llvm::Value *beginTokenPos,
156                                       llvm::Value *blockEnd) {
157        BasicBlock* entryBlock = b->GetInsertBlock();
158
159        // Constant
160        Value* SIZE_ACCELERATION_WIDTH = b->getSize(ACCELERATION_WIDTH);
161        Value* SIZE_1 = b->getSize(1);
162        Value* SIZE_0 = b->getSize(0);
163
164        Type* INT_ACCELERATION_TYPE = b->getIntNTy(ACCELERATION_WIDTH);
165        Value* INT_ACCELERATION_0 = b->getIntN(ACCELERATION_WIDTH, 0);
166        Value* INT_ACCELERATION_1 = b->getIntN(ACCELERATION_WIDTH, 1);
167
168        // ---- Entry Block
169        Value* maskedTokenPos = b->CreateURem(beginTokenPos, b->getCapacity("extender"));
170        Value* tokenPosRem = b->CreateURem(beginTokenPos, SIZE_ACCELERATION_WIDTH);
171        Value* blockPosBase = b->CreateSub(beginTokenPos, tokenPosRem);
172
173        Value* currentExtenderValue = b->CreateLoad(
174                b->CreateGEP(
175                        b->CreatePointerCast(b->getRawInputPointer("extender", SIZE_0), INT_ACCELERATION_TYPE->getPointerTo()),
176                        b->CreateUDiv(maskedTokenPos, SIZE_ACCELERATION_WIDTH)
177                )
178        );
179
180        Value* initTokenMarker = b->CreateShl(INT_ACCELERATION_1, tokenPosRem);
181        BasicBlock* accelerationProcessBlock = b->CreateBasicBlock("accelerationProcessBlock");
182        BasicBlock* accelerationExitBlock = b->CreateBasicBlock("accelerationExitBlock");
183        b->CreateBr(accelerationProcessBlock);
184
185        // ---- AccelerationProcessBlock
186        b->SetInsertPoint(accelerationProcessBlock);
187        PHINode* phiTokenMarkers = b->CreatePHI(INT_ACCELERATION_TYPE, 2);
188        phiTokenMarkers->addIncoming(initTokenMarker, entryBlock);
189        PHINode* phiLiteralMasks = b->CreatePHI(INT_ACCELERATION_TYPE, 2);
190        phiLiteralMasks->addIncoming(INT_ACCELERATION_0, entryBlock);
191        PHINode* phiMatchOffsetMarkers = b->CreatePHI(INT_ACCELERATION_TYPE, 2);
192        phiMatchOffsetMarkers->addIncoming(INT_ACCELERATION_0, entryBlock);
193
194
195        Value* tokenReverseZeros = b->CreateCountReverseZeroes(phiTokenMarkers);
196        Value* currentTokenLocalPos = b->CreateSub(b->CreateSub(SIZE_ACCELERATION_WIDTH, tokenReverseZeros), SIZE_1);
197        Value* currentTokenMarker = b->CreateShl(INT_ACCELERATION_1, currentTokenLocalPos); // 1 marker is in Token Pos
198        Value* currentTokenGlobalPos = b->CreateAdd(blockPosBase, currentTokenLocalPos);
199        Value* tokenValue = b->CreateLoad(b->getRawInputPointer("byteStream", currentTokenGlobalPos));
200
201        llvm::Value *literalLength, *literalLengthEndMarker;
202        std::tie(literalLength, literalLengthEndMarker) =
203//                this->scanThruLiteralLength(b, currentTokenMarker, currentExtenderValue, tokenValue, blockPosBase,
204//                                            currentTokenLocalPos);
205                this->noExtensionLiteralLength(b, currentTokenMarker, currentExtenderValue, tokenValue, blockPosBase,
206                                    currentTokenLocalPos);
207        Value* literalBeginMarker = b->CreateShl(literalLengthEndMarker, SIZE_1);
208        Value* literalStartLocalPos = b->CreateCountForwardZeroes(literalBeginMarker);
209        Value* literalStartGlobalPos = b->CreateAdd(blockPosBase, literalStartLocalPos);
210
211
212        Value* literalEndMarker = b->CreateSelect(b->CreateICmpULT(literalLength, SIZE_ACCELERATION_WIDTH), b->CreateShl(literalBeginMarker, literalLength), INT_ACCELERATION_0);
213
214        Value* newLiteralMask = b->CreateSub(literalEndMarker, literalBeginMarker);
215
216        Value* newMatchOffsetStartMarker = literalEndMarker;
217
218        Value *matchLength, *matchLengthEndMarker;
219//        std::tie(matchLength, matchLengthEndMarker) =
220//                this->scanThruMatchLength(b, b->CreateShl(newMatchOffsetStartMarker, SIZE_1), currentExtenderValue,
221//                                          tokenValue, blockPosBase);
222
223        std::tie(matchLength, matchLengthEndMarker) =
224                this->noExtensionMatchLength(b, b->CreateShl(newMatchOffsetStartMarker, SIZE_1), currentExtenderValue,
225                                          tokenValue, blockPosBase);
226
227        Value *newTokenMarker = b->CreateShl(matchLengthEndMarker, SIZE_1);
228        Value* newTokenMarkerLocalPos = b->CreateCountForwardZeroes(newTokenMarker);
229
230        Value* reachEnd = b->CreateOr(
231                b->CreateICmpEQ(newTokenMarker, b->getSize(0)),
232                b->CreateICmpUGE(b->CreateAdd(newTokenMarkerLocalPos, blockPosBase), blockEnd)
233        );
234
235        BasicBlock* dataProcessBlock = b->CreateBasicBlock("dataProcessBlock");
236        b->CreateUnlikelyCondBr(reachEnd, accelerationExitBlock, dataProcessBlock);
237
238        // ---- dataProcessBlock
239        b->SetInsertPoint(dataProcessBlock);
240
241        Value* matchOffsetStartLocalPos = b->CreateCountForwardZeroes(newMatchOffsetStartMarker);
242        Value* matchOffsetStartGlobalPos = b->CreateAdd(matchOffsetStartLocalPos, blockPosBase);
243
244        Value* matchOffsetPtr = b->getRawInputPointer("byteStream", matchOffsetStartGlobalPos);
245        // For now, it is safe to cast matchOffset pointer into i16 since the input byte stream is always linear available
246        matchOffsetPtr = b->CreatePointerCast(matchOffsetPtr, b->getInt16Ty()->getPointerTo());
247        Value* matchOffset = b->CreateZExt(b->CreateLoad(matchOffsetPtr), b->getSizeTy());
248
249        // TODO all of the literal data here will always be in the same 64-bit literal block, it may be better if we provide
250        //      this information to the literal copy method, especially when we are working with swizzled form
251        this->handleLiteralCopy(b, literalStartGlobalPos, literalLength);
252        this->handleMatchCopy(b, matchOffset, matchLength);
253
254        phiTokenMarkers->addIncoming(b->CreateOr(phiTokenMarkers, newTokenMarker), b->GetInsertBlock());
255        phiLiteralMasks->addIncoming(b->CreateOr(phiLiteralMasks, newLiteralMask), b->GetInsertBlock());
256        phiMatchOffsetMarkers->addIncoming(b->CreateOr(phiMatchOffsetMarkers, newMatchOffsetStartMarker), b->GetInsertBlock());
257
258        b->CreateBr(accelerationProcessBlock);
259
260        // ---- AccelerationExitBlock
261        b->SetInsertPoint(accelerationExitBlock);
262
263        return std::make_pair(std::make_pair(phiTokenMarkers, phiLiteralMasks), phiMatchOffsetMarkers);
264    }
265
266    llvm::Value *LZ4ByteStreamAioKernel::processBlockBoundary(const std::unique_ptr<KernelBuilder> &b, llvm::Value *beginTokenPos,
267                                                    llvm::Value *lz4BlockEnd) {
268// Constant
269        ConstantInt* SIZE_0 = b->getSize(0);
270        ConstantInt* SIZE_1 = b->getSize(1);
271        ConstantInt* BYTE_FF = b->getInt8(0xff);
272        Value* BYTE_F0 = b->getInt8(0xf0);
273        Value* BYTE_0F = b->getInt8(0x0f);
274
275        // ---- EntryBlock
276        BasicBlock* entryBlock = b->GetInsertBlock();
277        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
278
279        Value* bytePtrBase = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
280
281        Value* tokenValue = b->CreateLoad(b->CreateGEP(bytePtrBase, beginTokenPos));
282
283        Value* shouldExtendLiteral = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_F0), BYTE_F0);
284
285        Value* shouldExtendMatch = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_0F), BYTE_0F);
286
287        BasicBlock* extendLiteralCond = b->CreateBasicBlock("extendLiteralCond");
288        BasicBlock* extendLiteralEnd = b->CreateBasicBlock("extendLiteralEnd");
289
290        Value* initExtendLiteralPos = b->CreateAdd(beginTokenPos, b->getSize(1));
291
292        b->CreateCondBr(shouldExtendLiteral, extendLiteralCond, extendLiteralEnd);
293
294        // ---- extendLiteralCond
295        b->SetInsertPoint(extendLiteralCond);
296        PHINode* phiCurrentExtendLiteralPos = b->CreatePHI(b->getSizeTy(), 2);
297        phiCurrentExtendLiteralPos->addIncoming(initExtendLiteralPos, entryBlock);
298        PHINode* phiExtendLiteralLength = b->CreatePHI(b->getSizeTy(), 2);
299        phiExtendLiteralLength->addIncoming(SIZE_0, entryBlock);
300
301        Value* currentLiteralLengthByte = b->CreateLoad(b->CreateGEP(bytePtrBase, phiCurrentExtendLiteralPos));
302        Value* newExtendLiteralLength = b->CreateAdd(phiExtendLiteralLength, b->CreateZExt(currentLiteralLengthByte, b->getSizeTy()));
303
304        phiCurrentExtendLiteralPos->addIncoming(b->CreateAdd(phiCurrentExtendLiteralPos, SIZE_1), b->GetInsertBlock());
305        phiExtendLiteralLength->addIncoming(newExtendLiteralLength, b->GetInsertBlock());
306
307        b->CreateCondBr(b->CreateICmpEQ(currentLiteralLengthByte, BYTE_FF), extendLiteralCond, extendLiteralEnd);
308
309        // ---- extendLiteralEnd
310        b->SetInsertPoint(extendLiteralEnd);
311        PHINode* literalExtendValue = b->CreatePHI(b->getSizeTy(), 2);
312        literalExtendValue->addIncoming(SIZE_0, entryBlock);
313        literalExtendValue->addIncoming(newExtendLiteralLength, extendLiteralCond);
314        PHINode* phiExtendLiteralEndPos = b->CreatePHI(b->getSizeTy(), 2);
315        phiExtendLiteralEndPos->addIncoming(beginTokenPos, entryBlock);
316        phiExtendLiteralEndPos->addIncoming(phiCurrentExtendLiteralPos, extendLiteralCond);
317
318        Value* literalLength = b->CreateAdd(literalExtendValue, b->CreateZExt(b->CreateLShr(tokenValue, b->getInt8(4)), b->getSizeTy()));
319
320        Value* literalStartPos = b->CreateAdd(phiExtendLiteralEndPos, SIZE_1);
321        Value* literalEndPos = b->CreateAdd(literalStartPos, literalLength);
322
323        Value* matchOffsetBeginPos = literalEndPos;
324        Value* matchOffsetNextPos = b->CreateAdd(matchOffsetBeginPos, SIZE_1);
325
326        BasicBlock* hasMatchPartBlock = b->CreateBasicBlock("hasMatchPartBlock");
327        BasicBlock* extendMatchCon = b->CreateBasicBlock("extendMatchCon");
328        BasicBlock* extendMatchExit = b->CreateBasicBlock("extendMatchExit");
329
330        // This literal copy will always cross 64 bits literal boundary
331        this->handleLiteralCopy(b, literalStartPos, literalLength);
332        BasicBlock* extendLiteralEndFinal = b->GetInsertBlock();
333
334        b->CreateLikelyCondBr(b->CreateICmpULT(matchOffsetBeginPos, lz4BlockEnd), hasMatchPartBlock, exitBlock);
335
336        // ---- hasMatchPartBlock
337        b->SetInsertPoint(hasMatchPartBlock);
338        Value* initExtendMatchPos = b->CreateAdd(matchOffsetBeginPos, b->getSize(2));
339        b->CreateCondBr(shouldExtendMatch, extendMatchCon, extendMatchExit);
340
341        // ---- extendMatchCon
342        b->SetInsertPoint(extendMatchCon);
343        PHINode* phiCurrentExtendMatchPos = b->CreatePHI(b->getSizeTy(), 2);
344        phiCurrentExtendMatchPos->addIncoming(initExtendMatchPos, hasMatchPartBlock);
345        PHINode* phiExtendMatchLength = b->CreatePHI(b->getSizeTy(), 2);
346        phiExtendMatchLength->addIncoming(SIZE_0, hasMatchPartBlock);
347
348        Value* currentMatchLengthByte = b->CreateLoad(b->CreateGEP(bytePtrBase, phiCurrentExtendMatchPos));
349        Value* newExtendMatchLength = b->CreateAdd(phiExtendMatchLength, b->CreateZExt(currentMatchLengthByte, b->getSizeTy()));
350
351        phiCurrentExtendMatchPos->addIncoming(b->CreateAdd(phiCurrentExtendMatchPos, SIZE_1), b->GetInsertBlock());
352        phiExtendMatchLength->addIncoming(newExtendMatchLength, b->GetInsertBlock());
353
354        b->CreateCondBr(b->CreateICmpEQ(currentMatchLengthByte, BYTE_FF), extendMatchCon, extendMatchExit);
355
356        // ---- extendMatchExit
357        b->SetInsertPoint(extendMatchExit);
358        PHINode* matchExtendValue = b->CreatePHI(b->getSizeTy(), 2);
359        matchExtendValue->addIncoming(SIZE_0, hasMatchPartBlock);
360        matchExtendValue->addIncoming(newExtendMatchLength, extendMatchCon);
361        PHINode* phiExtendMatchEndPos = b->CreatePHI(b->getSizeTy(), 2);
362        phiExtendMatchEndPos->addIncoming(matchOffsetNextPos, hasMatchPartBlock);
363        phiExtendMatchEndPos->addIncoming(phiCurrentExtendMatchPos, extendMatchCon);
364
365        // matchLength = (size_t)token & 0xf + 4 + matchExtendValue
366        Value* matchLength = b->CreateAdd(
367                b->CreateAdd(matchExtendValue, b->getSize(4)),
368                b->CreateZExt(b->CreateAnd(tokenValue, BYTE_0F), b->getSizeTy())
369        );
370
371        Value* matchOffsetPtr = b->getRawInputPointer("byteStream", matchOffsetBeginPos);
372        // For now, it is safe to cast matchOffset pointer into i16 since the input byte stream is always linear available
373        matchOffsetPtr = b->CreatePointerCast(matchOffsetPtr, b->getInt16Ty()->getPointerTo());
374        Value* matchOffset = b->CreateZExt(b->CreateLoad(matchOffsetPtr), b->getSizeTy());
375        this->handleMatchCopy(b, matchOffset, matchLength);
376        BasicBlock* extendMatchExitFinal = b->GetInsertBlock();
377        b->CreateBr(exitBlock);
378
379        // ---- exitBlock
380        b->SetInsertPoint(exitBlock);
381        PHINode* phiBeforeTokenPos = b->CreatePHI(b->getSizeTy(), 2);
382        phiBeforeTokenPos->addIncoming(matchOffsetNextPos, extendLiteralEndFinal);
383        phiBeforeTokenPos->addIncoming(phiExtendMatchEndPos, extendMatchExitFinal);
384        Value* nextTokenPos = b->CreateAdd(phiBeforeTokenPos, SIZE_1);
385
386
387
388        return nextTokenPos;
389    }
390
391    std::pair<llvm::Value *, llvm::Value *> LZ4ByteStreamAioKernel::noExtensionLiteralLength(const std::unique_ptr<KernelBuilder> &b,
392                                                                            llvm::Value *currentTokenMarker,
393                                                                            llvm::Value *currentExtenderValue,
394                                                                            llvm::Value *tokenValue,
395                                                                            llvm::Value *blockPosBase,
396                                                                            llvm::Value *currentTokenLocalPos
397    ) {
398        Value* SIZE_1 = b->getSize(1);
399        Value* BYTE_F0 = b->getInt8(0xf0);
400        Value* shouldExtendLiteral = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_F0), BYTE_F0);
401
402        Value* literalLength =
403                b->CreateLShr(
404                        b->CreateZExt(tokenValue, b->getSizeTy()),
405                        b->getSize(4)
406                );
407
408        Value* retLiteralMarker = b->CreateSelect(shouldExtendLiteral, b->getInt64(0), currentTokenMarker);
409
410        return std::make_pair(literalLength, retLiteralMarker);
411    };
412
413    std::pair<llvm::Value *, llvm::Value *>
414    LZ4ByteStreamAioKernel::scanThruLiteralLength(const std::unique_ptr<KernelBuilder> &b, llvm::Value *currentTokenMarker,
415                                        llvm::Value *currentExtenderValue, llvm::Value *tokenValue,
416                                        llvm::Value *blockPosBase, llvm::Value *currentTokenLocalPos) {
417        Value* SIZE_1 = b->getSize(1);
418        Value* BYTE_F0 = b->getInt8(0xf0);
419        Value* shouldExtendLiteral = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_F0), BYTE_F0);
420
421        // Extend Literal Length
422        Value* literalScanThruResult = this->scanThru(b, b->CreateShl(currentTokenMarker, SIZE_1), currentExtenderValue);
423        Value* literalScanThruLocalPos = b->CreateCountForwardZeroes(literalScanThruResult);
424        Value* literalScanThruGlobalPos = b->CreateAdd(literalScanThruLocalPos, blockPosBase);
425        Value* literalScanThruLastBit = b->CreateLoad(b->getRawInputPointer("byteStream", literalScanThruGlobalPos));
426        // literalExtendResult = 255 * (literalScanThruLocalPos - currentTokenLocalPos - 1) + (size_t)literalScanThruLastBit
427        Value* literalExtendResult = b->CreateAdd(
428                b->CreateMul(
429                        b->getSize(255),
430                        b->CreateSub(
431                                b->CreateSub(literalScanThruLocalPos, currentTokenLocalPos),
432                                SIZE_1
433                        )
434                ),
435                b->CreateZExt(literalScanThruLastBit, b->getSizeTy())
436        );
437
438        // literalLength = (size_t)token >> 4 + shouldExtendLiteral ? literalExtendResult : 0
439        Value* literalLength = b->CreateAdd(
440                b->CreateLShr(
441                        b->CreateZExt(tokenValue, b->getSizeTy()),
442                        b->getSize(4)
443                ),
444                b->CreateSelect(
445                        shouldExtendLiteral,
446                        literalExtendResult,
447                        b->getSize(0)
448                )
449        );
450        Value* retLiteralMarker = b->CreateSelect(shouldExtendLiteral, literalScanThruResult, currentTokenMarker);
451
452        return std::make_pair(literalLength, retLiteralMarker);
453    }
454
455    inline std::pair<llvm::Value *, llvm::Value *> LZ4ByteStreamAioKernel::noExtensionMatchLength(const std::unique_ptr<KernelBuilder> &b,
456                                                                          llvm::Value *matchOffsetEndMarker,
457                                                                          llvm::Value *currentExtenderValue,
458                                                                          llvm::Value *tokenValue,
459                                                                          llvm::Value *blockPosBase
460    ) {
461        Value* SIZE_1 = b->getSize(1);
462        Value* BYTE_0F = b->getInt8(0x0f);
463        Value* shouldExtendMatch = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_0F), BYTE_0F);
464
465        // Extend Match Length
466        Value* matchLength =
467                b->CreateAdd(
468                        b->CreateZExt(b->CreateAnd(tokenValue, BYTE_0F), b->getSizeTy()),
469                        b->getSize(4)
470                );
471
472        Value* retMatchMarker = b->CreateSelect(shouldExtendMatch, b->getInt64(0), matchOffsetEndMarker);
473        return std::make_pair(matchLength, retMatchMarker);
474    };
475
476    std::pair<llvm::Value *, llvm::Value *>
477    LZ4ByteStreamAioKernel::scanThruMatchLength(const std::unique_ptr<KernelBuilder> &b, llvm::Value *matchOffsetEndMarker,
478                                      llvm::Value *currentExtenderValue, llvm::Value *tokenValue,
479                                      llvm::Value *blockPosBase) {
480        Value* SIZE_1 = b->getSize(1);
481        Value* BYTE_0F = b->getInt8(0x0f);
482        Value* shouldExtendMatch = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_0F), BYTE_0F);
483
484        // Extend Match Length
485        Value* matchScanThruResult = this->scanThru(b, b->CreateShl(matchOffsetEndMarker, SIZE_1), currentExtenderValue);
486        Value* matchScanThruLocalPos = b->CreateCountForwardZeroes(matchScanThruResult);
487        Value* matchScanThruGlobalPos = b->CreateAdd(matchScanThruLocalPos, blockPosBase);
488        Value* matchScanThruLastBit = b->CreateLoad(b->getRawInputPointer("byteStream", matchScanThruGlobalPos));
489        Value* matchOffsetEndLocalPos = b->CreateCountForwardZeroes(matchOffsetEndMarker);
490
491        // matchExtendResult = 255 * (matchScanThruLocalPos - matchOffsetEndLocalPos - 1) + (size_t)matchScanThruLastBit
492        Value* matchExtendResult = b->CreateAdd(
493                b->CreateMul(
494                        b->getSize(255),
495                        b->CreateSub(
496                                b->CreateSub(matchScanThruLocalPos, matchOffsetEndLocalPos),
497                                SIZE_1
498                        )
499                ),
500                b->CreateZExt(matchScanThruLastBit, b->getSizeTy())
501        );
502
503        // matchLength = (size_t)token & 0x0f + 4 + shouldExtendMatch ? matchExtendResult : 0
504        Value* matchLength = b->CreateAdd(
505                b->CreateAdd(
506                        b->CreateZExt(b->CreateAnd(tokenValue, BYTE_0F), b->getSizeTy()),
507                        b->getSize(4)
508                ),
509                b->CreateSelect(
510                        shouldExtendMatch,
511                        matchExtendResult,
512                        b->getSize(0)
513                )
514        );
515
516        Value* retMatchMarker = b->CreateSelect(shouldExtendMatch, matchScanThruResult, matchOffsetEndMarker);
517        return std::make_pair(matchLength, retMatchMarker);
518    }
519
520    llvm::Value *
521    LZ4ByteStreamAioKernel::scanThru(const std::unique_ptr<KernelBuilder> &b, llvm::Value *from, llvm::Value *thru) {
522        return b->CreateAnd(
523                b->CreateAdd(from, thru),
524                b->CreateNot(thru)
525        );
526    }
527
528    void LZ4ByteStreamAioKernel::handleLiteralCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *literalStart,
529                                         llvm::Value *literalLength) {
530        unsigned fw = 64;
531        Type* INT_FW_PTR = b->getIntNTy(fw)->getPointerTo();
532
533        Value* inputBytePtr = b->getRawInputPointer("byteStream", literalStart);
534        Value* inputPtr = b->CreatePointerCast(inputBytePtr, INT_FW_PTR);
535
536        Value* outputPos = b->getScalarField("outputPos");
537        Value* outputBufferSize = b->getCapacity("outputStream");
538        Value* outputPtr = b->getRawOutputPointer("outputStream", b->CreateURem(outputPos, outputBufferSize));
539        outputPtr = b->CreatePointerCast(outputPtr, INT_FW_PTR);
540
541        // We can always assume that we have enough output buffer based on our output buffer allocation strategy (except in extract only case)
542
543        BasicBlock* entryBlock = b->GetInsertBlock();
544        BasicBlock* literalCopyCon = b->CreateBasicBlock("literalCopyCon");
545        BasicBlock* literalCopyBody = b->CreateBasicBlock("literalCopyBody");
546        BasicBlock* literalCopyExit = b->CreateBasicBlock("literalCopyExit");
547
548        b->CreateBr(literalCopyCon);
549
550        // ---- literalCopyCon
551        b->SetInsertPoint(literalCopyCon);
552        PHINode* phiOutputPtr = b->CreatePHI(outputPtr->getType(), 2);
553        phiOutputPtr->addIncoming(outputPtr, entryBlock);
554        PHINode* phiInputPtr = b->CreatePHI(inputPtr->getType(), 2);
555        phiInputPtr->addIncoming(inputPtr, entryBlock);
556        PHINode* phiCopiedLength = b->CreatePHI(literalLength->getType(), 2);
557        phiCopiedLength->addIncoming(b->getSize(0), entryBlock);
558        b->CreateCondBr(b->CreateICmpULT(phiCopiedLength, literalLength), literalCopyBody, literalCopyExit);
559
560        // ---- literalCopyBody
561        b->SetInsertPoint(literalCopyBody);
562        // Always copy fw bits to improve performance
563        // TODO sometime it will crash because of overflow copy in the end of the buffer, need to add 4 bytes of
564        //      extra buffer in order to make sure it does not crash.
565        b->CreateStore(b->CreateLoad(phiInputPtr), phiOutputPtr);
566
567        phiInputPtr->addIncoming(b->CreateGEP(phiInputPtr, b->getSize(1)), b->GetInsertBlock());
568        phiOutputPtr->addIncoming(b->CreateGEP(phiOutputPtr, b->getSize(1)), b->GetInsertBlock());
569        phiCopiedLength->addIncoming(b->CreateAdd(phiCopiedLength, b->getSize(fw / 8)), b->GetInsertBlock());
570        b->CreateBr(literalCopyCon);
571
572        // ---- literalCopyExit
573        b->SetInsertPoint(literalCopyExit);
574        b->setScalarField("outputPos", b->CreateAdd(outputPos, literalLength));
575    }
576
577    void LZ4ByteStreamAioKernel::handleMatchCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *matchOffset,
578                                       llvm::Value *matchLength) {
579        unsigned fw = 64;
580        Type* INT_FW_PTR = b->getIntNTy(fw)->getPointerTo();
581
582        BasicBlock* entryBlock = b->GetInsertBlock();
583
584        Value* outputPos = b->getScalarField("outputPos");
585        Value* outputBufferSize = b->getCapacity("outputStream");
586
587        Value* copyToPtr = b->getRawOutputPointer("outputStream", b->CreateURem(outputPos, outputBufferSize));
588        Value* copyFromPtr = b->getRawOutputPointer("outputStream", b->CreateURem(b->CreateSub(outputPos, matchOffset), outputBufferSize));
589
590        BasicBlock* matchCopyCon = b->CreateBasicBlock("matchCopyCon");
591        BasicBlock* matchCopyBody = b->CreateBasicBlock("matchCopyBody");
592        BasicBlock* matchCopyExit = b->CreateBasicBlock("matchCopyExit");
593
594        b->CreateBr(matchCopyCon);
595
596        // ---- matchCopyCon
597        b->SetInsertPoint(matchCopyCon);
598        PHINode* phiFromPtr = b->CreatePHI(b->getInt8PtrTy(), 2);
599        phiFromPtr->addIncoming(copyFromPtr, entryBlock);
600        PHINode* phiToPtr = b->CreatePHI(b->getInt8PtrTy(), 2);
601        phiToPtr->addIncoming(copyToPtr, entryBlock);
602        PHINode* phiCopiedSize = b->CreatePHI(b->getSizeTy(), 2);
603        phiCopiedSize->addIncoming(b->getSize(0), entryBlock);
604
605        b->CreateCondBr(b->CreateICmpULT(phiCopiedSize, matchLength), matchCopyBody, matchCopyExit);
606
607        // ---- matchCopyBody
608        b->SetInsertPoint(matchCopyBody);
609        b->CreateStore(
610                b->CreateLoad(b->CreatePointerCast(phiFromPtr, INT_FW_PTR)),
611        b->CreatePointerCast(phiToPtr, INT_FW_PTR)
612        );
613
614        Value* copySize = b->CreateUMin(matchOffset, b->getSize(fw / 8));
615        phiFromPtr->addIncoming(b->CreateGEP(phiFromPtr, copySize), b->GetInsertBlock());
616        phiToPtr->addIncoming(b->CreateGEP(phiToPtr, copySize), b->GetInsertBlock());
617        phiCopiedSize->addIncoming(b->CreateAdd(phiCopiedSize, copySize), b->GetInsertBlock());
618        b->CreateBr(matchCopyCon);
619
620        // ---- matchCopyExit
621        b->SetInsertPoint(matchCopyExit);
622        b->setScalarField("outputPos", b->CreateAdd(outputPos, matchLength));
623    }
624
625
626}
Note: See TracBrowser for help on using the repository browser.