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

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