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

Last change on this file since 6118 was 6118, checked in by xwa163, 10 months ago

Implement bitstream decompression version of LZ4 Aio Kernel

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