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

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