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

Last change on this file since 6064 was 6064, checked in by xwa163, 11 months ago

Init checkin for LZ4ParallelByteStreamAioKernel and related pipeline

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