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

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