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

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

fix some warning in lz4 related kernels

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