source: icGREP/icgrep-devel/icgrep/kernels/lzparabix/encoder/LZParabixCompressionKernel.cpp @ 6123

Last change on this file since 6123 was 6123, checked in by xwa163, 13 months ago

Encode BitStream? directly in LZParabix compressed file

File size: 36.2 KB
Line 
1
2#include "LZParabixCompressionKernel.h"
3
4#include <kernels/kernel_builder.h>
5#include <iostream>
6#include <string>
7#include <llvm/Support/raw_ostream.h>
8#include <kernels/streamset.h>
9#include <cstdint>
10
11
12
13
14
15using namespace llvm;
16using namespace kernel;
17using namespace std;
18
19namespace kernel{
20    LZParabixCompressionKernel::LZParabixCompressionKernel(const std::unique_ptr<kernel::KernelBuilder> &b)
21    :SegmentOrientedKernel("LZParabixAioKernel",
22            // Inputs
23                           {
24                                   Binding{b->getStreamSetTy(1, 8), "byteStream", FixedRate()},
25                                   Binding{b->getStreamSetTy(8, 1), "basisBits", RateEqualTo("byteStream")}
26                           },
27            //Outputs
28                           {
29                                   Binding{b->getStreamSetTy(1, 8), "outputStream", BoundedRate(0, 1)},
30
31
32                                   // TODO: workaround here, it seems that allocating large memory buffer in internal scalar fields will largely slow down
33                                   // the performance of JIT compiling, we temporarily use 4 output buffer as internal scalar field
34
35                                   // Two hashmap buffer to optimize the performance of matching
36                                   Binding{b->getStreamSetTy(1, 64), "strToBlockIndex", BoundedRate(0, 1)},
37                                   Binding{b->getStreamSetTy(1, 32), "strToMatchPos", BoundedRate(0, 1)},
38                                   // Two mLzParabixBlockSize helper buffer
39                                   Binding{b->getStreamSetTy(1, 8), "literalByteBuffer", BoundedRate(0, 1)},
40                                   Binding{b->getStreamSetTy(1, 8), "tokenByteBuffer", BoundedRate(0, 1)}
41
42                           },
43            //Arguments
44                           {
45                                   Binding{b->getSizeTy(), "fileSize"}
46                           },
47                           {},
48            //Internal states:
49                           {
50                                   Binding{ArrayType::get(b->getInt64Ty(), 8), "pendingLiteralOutput"},
51                                   Binding{b->getSizeTy(), "literalOutputPos"},
52
53                           }),
54     mLzParabixBlockSize(4 * 1024 * 1024)
55    {
56        this->setStride(mLzParabixBlockSize);
57        addAttribute(MustExplicitlyTerminate());
58    }
59
60    void LZParabixCompressionKernel::generateDoSegmentMethod(const std::unique_ptr<KernelBuilder> &b) {
61        Value* inputCursor = b->getProcessedItemCount("byteStream");
62        Value* inputEndPos = b->CreateAdd(inputCursor, b->getSize(mLzParabixBlockSize));
63        Value* fileSize = b->getScalarField("fileSize");
64        inputEndPos = b->CreateUMin(inputEndPos, fileSize);
65        Value* outputCursor = b->getProducedItemCount("outputStream");
66        this->encodeBlock(b, inputCursor, inputEndPos, outputCursor);
67
68        b->setTerminationSignal(b->CreateICmpEQ(inputEndPos, fileSize));
69        b->setProcessedItemCount("byteStream", inputEndPos);
70    }
71
72    void LZParabixCompressionKernel::encodeBlock(const std::unique_ptr<KernelBuilder> &b, llvm::Value *inputCursor,
73                                                 llvm::Value *inputEndPos, llvm::Value *outputPos) {
74        // Constant
75        ConstantInt* SIZE_64 = b->getSize(64);
76
77        // ---- EntryBlock
78        BasicBlock* entryBlock = b->GetInsertBlock();
79
80        BasicBlock* encodeBlockCon = b->CreateBasicBlock("encodeBlockCon");
81        BasicBlock* encodeBlockBody = b->CreateBasicBlock("encodeBlockBody");
82        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
83
84        Value* blockSizePos = outputPos;
85        Value* literalSizePos = b->CreateAdd(outputPos, b->getSize(4));
86
87        Value* initOutputCursor = b->CreateAdd(outputPos, b->getSize(8)); // blockSize takes 4 bytes, and literalSize takes 4 bytes
88        Value* initBlockIndex = b->CreateUDiv(inputCursor, b->getSize(64));
89        b->setScalarField("literalOutputPos", b->getSize(0));
90
91        b->CreateMemSet(b->getScalarFieldPtr("pendingLiteralOutput"), b->getInt8(0), b->getSize(64), 1);
92
93        b->CreateBr(encodeBlockCon);
94
95        // ---- encodeBlockCon
96        b->SetInsertPoint(encodeBlockCon);
97
98        PHINode* phiInputCursorPos = b->CreatePHI(b->getSizeTy(), 3);
99        phiInputCursorPos->addIncoming(inputCursor, entryBlock);
100        PHINode* phiPreviousInputCursorPos = b->CreatePHI(b->getSizeTy(), 3);
101        phiPreviousInputCursorPos->addIncoming(inputCursor, entryBlock);
102        PHINode* phiPreviousBlockIndex = b->CreatePHI(b->getSizeTy(), 3);
103        phiPreviousBlockIndex->addIncoming(initBlockIndex, entryBlock);
104
105        PHINode* phiTokenOutputCursorPos = b->CreatePHI(b->getSizeTy(), 3);
106        phiTokenOutputCursorPos->addIncoming(b->getSize(0), entryBlock);
107
108        b->CreateCondBr(
109                b->CreateICmpULT(phiInputCursorPos, inputEndPos),
110                encodeBlockBody,
111                exitBlock
112        );
113
114        // ---- encodeBlockBody
115        b->SetInsertPoint(encodeBlockBody);
116
117        BasicBlock* updateCacheBlock = b->CreateBasicBlock("updateCacheBlock");
118        BasicBlock* extractMatchInfoBlock = b->CreateBasicBlock("extractMatchInfoBlock");
119
120        Value* newBlockIndex = b->CreateUDiv(phiInputCursorPos, SIZE_64);
121        b->CreateCondBr(
122                b->CreateICmpNE(newBlockIndex, phiPreviousBlockIndex),
123                updateCacheBlock,
124                extractMatchInfoBlock
125        );
126
127        // ---- updateCacheBlock
128        b->SetInsertPoint(updateCacheBlock);
129
130        this->updateCache(b, phiPreviousBlockIndex, initBlockIndex);
131
132        b->CreateBr(extractMatchInfoBlock);
133
134        // ---- encodeProcessBlock
135        b->SetInsertPoint(extractMatchInfoBlock);
136
137        MatchInfo retMatchInfo = this->extractMatchInfo(b, phiInputCursorPos, initBlockIndex, inputEndPos, phiPreviousInputCursorPos);
138
139        BasicBlock* noAppendOutputBlock = b->CreateBasicBlock("noAppendOutputBlock");
140        BasicBlock* appendOutputBlock = b->CreateBasicBlock("appendOutputBlock");
141
142        b->CreateCondBr(
143                b->CreateICmpUGE(
144                    retMatchInfo.matchLength,
145                    b->getSize(9)
146                ),
147                appendOutputBlock,
148                noAppendOutputBlock
149        );
150
151        // ---- appendOutputBlock
152        b->SetInsertPoint(appendOutputBlock);
153        Value* tokenOutputPosAfterLiteralCopy = this->appendLiteralSequence(b, phiPreviousInputCursorPos, retMatchInfo.matchStart, phiTokenOutputCursorPos);
154
155        Value* tokenOutputCursorPosAfterMatchCopy = this->appendMatchSequence(b, retMatchInfo, tokenOutputPosAfterLiteralCopy);
156        Value* nextCursorPos = b->CreateAdd(retMatchInfo.matchStart, retMatchInfo.matchLength);
157
158        phiInputCursorPos->addIncoming(nextCursorPos, b->GetInsertBlock());
159        phiPreviousInputCursorPos->addIncoming(nextCursorPos, b->GetInsertBlock());
160        phiPreviousBlockIndex->addIncoming(newBlockIndex, b->GetInsertBlock());
161        phiTokenOutputCursorPos->addIncoming(tokenOutputCursorPosAfterMatchCopy, b->GetInsertBlock());
162        b->CreateBr(encodeBlockCon);
163
164
165        // ---- noAppendOutputBlock
166        b->SetInsertPoint(noAppendOutputBlock);
167
168        Value* newInputCursorPos = b->CreateSelect(
169                b->CreateICmpEQ(phiPreviousInputCursorPos, phiInputCursorPos),
170                b->CreateAdd(phiInputCursorPos, b->getSize(8)),
171                b->CreateAdd(phiInputCursorPos, b->getSize(1))
172        );
173        newInputCursorPos = b->CreateUMin(newInputCursorPos, inputEndPos);
174
175        phiInputCursorPos->addIncoming(newInputCursorPos, b->GetInsertBlock());
176        phiPreviousInputCursorPos->addIncoming(phiPreviousInputCursorPos, b->GetInsertBlock());
177        phiPreviousBlockIndex->addIncoming(newBlockIndex, b->GetInsertBlock());
178        phiTokenOutputCursorPos->addIncoming(phiTokenOutputCursorPos, b->GetInsertBlock());
179
180        b->CreateBr(encodeBlockCon);
181
182        // ---- exitBlock
183        b->SetInsertPoint(exitBlock);
184
185        Value* totalTokenLength = this->appendLiteralSequence(b, phiPreviousInputCursorPos, inputEndPos, phiTokenOutputCursorPos);
186        Value* totalLiteralLength = b->getScalarField("literalOutputPos");
187        this->storePendingLiteralData(b);
188        // total literal length will be wrap to bit block width (we use 256 temporarily, will be 512 in the future)
189        Value* SIZE_BIT_BLOCK_WIDTH = b->getSize(b->getBitBlockWidth());
190        totalLiteralLength = b->CreateMul(
191                b->CreateUDiv(
192                        b->CreateAdd(totalLiteralLength, b->CreateSub(SIZE_BIT_BLOCK_WIDTH, b->getSize(1))),
193                        SIZE_BIT_BLOCK_WIDTH
194                ),
195                SIZE_BIT_BLOCK_WIDTH
196        );
197
198//        b->CallPrintInt("totalLiteralLength", totalLiteralLength);
199        // Store Output
200
201        Value* blockSize = b->CreateAdd(b->CreateAdd(totalLiteralLength, totalTokenLength), b->getSize(4));
202
203        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", b->getSize(0)), b->getInt8Ty()->getPointerTo());
204        Value* outputCapacity = b->getCapacity("outputStream");
205
206        // TODO handle edge case when part of the block size or literal size is at the edge of output buffr
207        b->CreateStore(b->CreateTrunc(blockSize, b->getInt32Ty()), b->CreatePointerCast(b->CreateGEP(outputBasePtr, b->CreateURem(blockSizePos, outputCapacity)), b->getInt32Ty()->getPointerTo()));
208        b->CreateStore(b->CreateTrunc(totalLiteralLength, b->getInt32Ty()), b->CreatePointerCast(b->CreateGEP(outputBasePtr, b->CreateURem(literalSizePos, outputCapacity)), b->getInt32Ty()->getPointerTo()));
209
210
211        Value* SIZE_0 = b->getSize(0);
212        Type* i8PtrTy = b->getInt8PtrTy();
213
214        // Literal Part will be BitStream
215        // Copy Literal Part
216        // copy literal buffer to [initOutputCursor, initOutputCursor + literalLength)
217        Value* literalPartBeginPos = initOutputCursor;
218        Value* literalPartBeginPosRem = b->CreateURem(literalPartBeginPos, outputCapacity);
219        Value* literalOutputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("literalByteBuffer", SIZE_0), i8PtrTy);
220        Value* remainingBufferSize = b->CreateSub(outputCapacity, literalPartBeginPosRem);
221        Value* literalCopyLength1 = b->CreateUMin(remainingBufferSize, totalLiteralLength);
222        Value* literalCopyLength2 = b->CreateSub(totalLiteralLength, literalCopyLength1);
223
224        b->CreateMemCpy(
225                b->CreateGEP(outputBasePtr, literalPartBeginPosRem),
226                literalOutputBasePtr,
227                literalCopyLength1,
228                1
229        );
230
231        b->CreateMemCpy(
232                outputBasePtr,
233                b->CreateGEP(literalOutputBasePtr, literalCopyLength1),
234                literalCopyLength2,
235                1
236        );
237
238
239        // copy Token Part
240        // copy token buffer to [initOutputCursor + literalLength, initOutputCursor + literalLength + tokenLength)
241        Value* tokenPartBeginPos = b->CreateAdd(literalPartBeginPos, totalLiteralLength);
242        Value* tokenPartBeginPosRem = b->CreateURem(tokenPartBeginPos, outputCapacity);
243        Value* tokenOutputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("tokenByteBuffer", SIZE_0), i8PtrTy);
244        remainingBufferSize = b->CreateSub(outputCapacity, tokenPartBeginPosRem);
245        Value* tokenCopyLength1 = b->CreateUMin(remainingBufferSize, totalTokenLength);
246        Value* tokenCopyLength2 = b->CreateSub(totalTokenLength, tokenCopyLength1);
247
248        b->CreateMemCpy(
249                b->CreateGEP(outputBasePtr, tokenPartBeginPosRem),
250                tokenOutputBasePtr,
251                tokenCopyLength1,
252                1
253        );
254
255        b->CreateMemCpy(
256                outputBasePtr,
257                b->CreateGEP(tokenOutputBasePtr, tokenCopyLength1),
258                tokenCopyLength2,
259                1
260        );
261        b->setProducedItemCount("outputStream", b->CreateAdd(blockSizePos, b->CreateAdd(blockSize, b->getSize(4))));
262    }
263
264    void LZParabixCompressionKernel::updateCache(const std::unique_ptr<KernelBuilder> &b, llvm::Value *i64BlockGlobalIndex, llvm::Value *initBlockGlobalIndex) {
265        // Constant
266        ConstantInt* SIZE_64 = b->getSize(64);
267        ConstantInt* INT_64_16 = b->getInt64(16);
268        ConstantInt* INT_32_8 = b->getInt32(8);
269
270        // Type
271        Type* i64PtrTy = b->getInt64Ty()->getPointerTo();
272        Type* i32PtrTy = b->getInt32Ty()->getPointerTo();
273
274        Value* localI64BlockIndex = b->CreateSub(i64BlockGlobalIndex, initBlockGlobalIndex);
275
276
277        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
278
279        Value* startPos = b->CreateMul(i64BlockGlobalIndex, SIZE_64);
280        for (unsigned i = 0; i + 4 < 64; ++i) {
281            Value* targetPos = b->CreateAdd(startPos, b->getSize(i));
282            Value* valuePtr = b->CreatePointerCast(b->CreateGEP(inputBasePtr, targetPos), i32PtrTy);
283            Value* inputValue = b->CreateLoad(valuePtr);
284
285            Value* hashedKey = this->hashKey(b, inputValue);
286
287            // Update mStrToBlockIndex
288            Value* strToBlockIndexBasePtr = b->CreatePointerCast(b->getRawOutputPointer("strToBlockIndex", b->getSize(0)), i64PtrTy);
289            Value* strToBlockIndexTargetPtr = b->CreateGEP(strToBlockIndexBasePtr, hashedKey);
290            Value* newBlockIndexCacheValue = b->CreateOr(b->CreateShl(b->CreateLoad(strToBlockIndexTargetPtr), INT_64_16), localI64BlockIndex);
291            b->CreateStore(newBlockIndexCacheValue, strToBlockIndexTargetPtr);
292
293            // Update mStrToMatchPos
294            Value* strToMatchPosBasePtr = b->CreatePointerCast(b->getRawOutputPointer("strToMatchPos", b->getSize(0)), i32PtrTy);
295            Value* strToMatchPosTargetPtr = b->CreateGEP(strToMatchPosBasePtr, hashedKey);
296            Value* newMatchPosCacheValue = b->CreateOr(b->CreateShl(b->CreateLoad(strToMatchPosTargetPtr), INT_32_8), b->getInt32(i));
297            b->CreateStore(newMatchPosCacheValue, strToMatchPosTargetPtr);
298        }
299    }
300
301    llvm::Value *LZParabixCompressionKernel::hashKey(const std::unique_ptr<KernelBuilder> &b, llvm::Value *v) {
302        //  (((v) * 2654435761U) >> ((4 * 8) - HASHLOG))
303        ConstantInt* magicNumber = b->getInt32(2654435761); // 2654435761 here is a Magic Number for hash
304        return b->CreateLShr(
305                b->CreateMul(v, magicNumber),
306                b->getInt32(4 * 8 - HASHLOG)
307        );
308    }
309
310
311    MatchInfo
312    LZParabixCompressionKernel::extractMatchInfo(const std::unique_ptr<KernelBuilder> &b, llvm::Value *cursorPos,
313                                                 llvm::Value *initBlockGlobalIndex, llvm::Value *inputEndPos,
314                                                 llvm::Value *previousCursorPos) {
315        // ---- EntryBlock
316        Value* SIZE_0 = b->getSize(0);
317        MatchInfo retInfo = {SIZE_0, SIZE_0, SIZE_0, SIZE_0};
318
319        BasicBlock* entryBlock = b->GetInsertBlock();
320        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
321
322        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
323
324        auto retMatchInfo = this->getPossibleMatchInfo(b, cursorPos);
325
326        Value* possibleBlockIndexes = retMatchInfo.first;
327        Value* possibleMatchPos = retMatchInfo.second;
328
329        Value* currentGlobalInputBlockIndex = b->CreateUDiv(cursorPos, b->getSize(64));
330
331
332
333        for (unsigned i = 0; i < 4; i++) {
334            BasicBlock* extractMatchInfoEntryBlock = b->CreateBasicBlock("extractMatchInfoEntryBlock");
335            b->CreateBr(extractMatchInfoEntryBlock);
336
337            // ---- extractMatchInfoEntryBlock
338            b->SetInsertPoint(extractMatchInfoEntryBlock);
339
340
341            Value* localMatchBlockIndex = b->CreateAnd(b->CreateLShr(possibleBlockIndexes, b->getInt64(i * 16)), b->getInt64(0xffff));
342            Value* globalMatchBlockIndex = b->CreateAdd(localMatchBlockIndex, initBlockGlobalIndex);
343
344            Value* matchPos = b->CreateAnd(b->CreateLShr(possibleMatchPos, b->getInt32(i * 8)), b->getInt32(0xff));
345            matchPos = b->CreateZExt(matchPos, b->getInt64Ty());
346
347            Value* blockOffset = b->CreateSub(currentGlobalInputBlockIndex, globalMatchBlockIndex);
348
349            Value* isNoMatch = b->CreateOr(
350                    b->CreateICmpUGE(globalMatchBlockIndex, currentGlobalInputBlockIndex),
351                    b->CreateICmpUGE(blockOffset, b->getSize(128))
352            );
353
354//            b->CallPrintInt("isNoMatch", isNoMatch);
355
356            BasicBlock* scanForwardMatchConBlock = b->CreateBasicBlock("scanForwardMatchConBlock");
357            BasicBlock* scanForwardMatchBodyBlock = b->CreateBasicBlock("scanForwardMatchBodyBlock");
358            BasicBlock* scanForwardMatchExitBlock = b->CreateBasicBlock("scanForwardMatchExitBlock");
359
360//            b->CreateCondBr(isNoMatch, scanForwardMatchExitBlock, scanForwardMatchConBlock);
361            b->CreateBr(scanForwardMatchConBlock);
362
363            // ---- scanForwardMatchConBlock
364            b->SetInsertPoint(scanForwardMatchConBlock);
365
366            PHINode* phiForwardMatchLength = b->CreatePHI(b->getSizeTy(), 2);
367            phiForwardMatchLength->addIncoming(b->getSize(0), extractMatchInfoEntryBlock);
368            PHINode* phiMatchPos = b->CreatePHI(b->getSizeTy(), 2);
369            phiMatchPos->addIncoming(matchPos, extractMatchInfoEntryBlock);
370            PHINode* phiMatchMask = b->CreatePHI(b->getInt64Ty(), 2);
371            phiMatchMask->addIncoming(b->getInt64(0), extractMatchInfoEntryBlock);
372
373            b->CreateCondBr(
374                    b->CreateAnd(
375                            b->CreateAnd(
376                                    b->CreateICmpULT(phiMatchPos, b->getInt64(64)),
377                                    b->CreateICmpULT(b->CreateAdd(cursorPos, phiForwardMatchLength), inputEndPos)
378                            ),
379                            b->CreateNot(isNoMatch)
380                    ),
381                    scanForwardMatchBodyBlock,
382                    scanForwardMatchExitBlock
383            );
384
385            // ---- scanForwardMatchBodyBlock
386            b->SetInsertPoint(scanForwardMatchBodyBlock);
387
388            Value* isMatch = b->CreateICmpEQ(
389                    b->CreateLoad(b->CreateGEP(inputBasePtr, b->CreateAdd(b->CreateMul(globalMatchBlockIndex, b->getInt64(64)), phiMatchPos))),
390                    b->CreateLoad(b->CreateGEP(inputBasePtr, b->CreateAdd(cursorPos, phiForwardMatchLength)))
391            );
392
393
394            phiForwardMatchLength->addIncoming(
395                    b->CreateSelect(isMatch, b->CreateAdd(phiForwardMatchLength, b->getSize(1)), phiForwardMatchLength),
396                    b->GetInsertBlock()
397            );
398            phiMatchPos->addIncoming(
399                    b->CreateAdd(phiMatchPos, b->getSize(1)),
400                    b->GetInsertBlock()
401            );
402
403            phiMatchMask->addIncoming(
404                    b->CreateSelect(
405                            isMatch,
406                            b->CreateOr(phiMatchMask, b->CreateShl(b->getInt64(1), phiMatchPos)),
407                            phiMatchMask
408                    ),
409                    b->GetInsertBlock()
410            );
411
412            b->CreateBr(scanForwardMatchConBlock);
413
414            // ---- scanForwardMatchExitBlock
415            b->SetInsertPoint(scanForwardMatchExitBlock);
416
417
418            BasicBlock* scanBackwardMatchConBlock = b->CreateBasicBlock("scanBackwardMatchConBlock");
419            BasicBlock* scanBackwardMatchBodyBlock = b->CreateBasicBlock("scanBackwardMatchBodyBlock");
420            BasicBlock* scanBackwardMatchExitBlock = b->CreateBasicBlock("scanBackwardMatchExitBlock");
421
422            b->CreateBr(scanBackwardMatchConBlock);
423
424            // ---- scanBackwardMatchConBlock
425            b->SetInsertPoint(scanBackwardMatchConBlock);
426            PHINode* phiBackMatchLength = b->CreatePHI(b->getSizeTy(), 2);
427            phiBackMatchLength->addIncoming(b->getSize(0), scanForwardMatchExitBlock);
428            PHINode* phiBackMatchMask = b->CreatePHI(b->getInt64Ty(), 2);
429            phiBackMatchMask->addIncoming(b->getInt64(0), scanForwardMatchExitBlock);
430            PHINode* phiBackMatchPos = b->CreatePHI(b->getSizeTy(), 2);
431            phiBackMatchPos->addIncoming(matchPos, scanForwardMatchExitBlock);
432
433
434            Value* backMatchMinPos = b->CreateUMax(previousCursorPos, b->CreateMul(currentGlobalInputBlockIndex, b->getSize(64)));
435            b->CreateCondBr(
436                    b->CreateAnd(
437                            b->CreateAnd(
438                                    b->CreateICmpUGT(phiBackMatchPos, b->getSize(0)),
439                                    b->CreateICmpUGT(b->CreateSub(cursorPos, phiBackMatchLength), backMatchMinPos)
440                            ),
441                            b->CreateNot(isNoMatch)
442                    ),
443                    scanBackwardMatchBodyBlock,
444                    scanBackwardMatchExitBlock
445            );
446
447            // ---- scanBackwardMatchBodyBlock
448            b->SetInsertPoint(scanBackwardMatchBodyBlock);
449            Value* targetBackMatchPos = b->CreateSub(phiBackMatchPos, b->getSize(1));
450
451            Value* isBackMatch = b->CreateICmpEQ(
452                    b->CreateLoad(b->CreateGEP(inputBasePtr, b->CreateAdd(b->CreateMul(globalMatchBlockIndex, b->getInt64(64)), targetBackMatchPos))),
453                    b->CreateLoad(b->CreateGEP(inputBasePtr, b->CreateSub(cursorPos, b->CreateAdd(phiBackMatchLength, b->getSize(1)))))
454            );
455
456            phiBackMatchLength->addIncoming(
457                    b->CreateSelect(isBackMatch, b->CreateAdd(phiBackMatchLength, b->getSize(1)), phiBackMatchLength),
458                    b->GetInsertBlock()
459            );
460
461            phiBackMatchPos->addIncoming(
462                    b->CreateSub(phiBackMatchPos, b->getSize(1)),
463                    b->GetInsertBlock()
464            );
465
466            phiBackMatchMask->addIncoming(
467                    b->CreateSelect(
468                            isBackMatch,
469                            b->CreateOr(phiBackMatchMask, b->CreateShl(b->getInt64(1), targetBackMatchPos)),
470                            phiBackMatchMask
471                    ),
472                    b->GetInsertBlock()
473            );
474            b->CreateBr(scanBackwardMatchConBlock);
475
476            // ---- scanBackwardMatchExitBlock
477            b->SetInsertPoint(scanBackwardMatchExitBlock);
478
479            Value* newMatchLength = b->CreateAdd(phiForwardMatchLength, phiBackMatchLength);
480
481            Value* isBetterMatch = b->CreateICmpUGT(newMatchLength, retInfo.matchLength);
482            retInfo.matchLength = b->CreateSelect(isBetterMatch, newMatchLength, retInfo.matchLength);
483            retInfo.matchMask = b->CreateSelect(isBetterMatch, b->CreateOr(phiMatchMask, phiBackMatchMask), retInfo.matchMask);
484            retInfo.matchOffset = b->CreateSelect(isBetterMatch, blockOffset, retInfo.matchOffset);
485            retInfo.matchStart = b->CreateSelect(isBetterMatch, b->CreateSub(cursorPos, phiBackMatchLength), retInfo.matchStart);
486        }
487        b->CreateBr(exitBlock);
488        b->SetInsertPoint(exitBlock);
489
490        return retInfo;
491
492    }
493
494    std::pair<llvm::Value *, llvm::Value *>
495    LZParabixCompressionKernel::getPossibleMatchInfo(const std::unique_ptr<KernelBuilder> &b, llvm::Value *cursorPos) {
496        // Type
497        Type* i64PtrTy = b->getInt64Ty()->getPointerTo();
498        Type* i32PtrTy = b->getInt32Ty()->getPointerTo();
499
500        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
501        Value* targetPtr = b->CreateGEP(inputBasePtr, cursorPos);
502        targetPtr = b->CreatePointerCast(targetPtr, b->getInt32Ty()->getPointerTo());
503        Value* hashedKey = this->hashKey(b, b->CreateLoad(targetPtr));
504//        b->CallPrintInt("hashedKey", hashedKey);
505        Value* strToBlockIndexBasePtr = b->CreatePointerCast(b->getRawOutputPointer("strToBlockIndex", b->getSize(0)), i64PtrTy);
506        Value* strToBlockIndexTargetPtr = b->CreateGEP(strToBlockIndexBasePtr, hashedKey);
507
508        Value* strToMatchPosBasePtr = b->CreatePointerCast(b->getRawOutputPointer("strToMatchPos", b->getSize(0)), i32PtrTy);
509        Value* strToMatchPosTargetPtr = b->CreateGEP(strToMatchPosBasePtr, hashedKey);
510
511        return std::make_pair(
512                b->CreateLoad(strToBlockIndexTargetPtr),
513                b->CreateLoad(strToMatchPosTargetPtr)
514        );
515    }
516
517    llvm::Value* LZParabixCompressionKernel::appendLiteralSequence(const unique_ptr<KernelBuilder> &b, Value *literalStart,
518                                                             Value *literalEnd, llvm::Value *tokenOutputPos) {
519        // Constant
520        Value* SIZE_0 = b->getSize(0);
521        Value* SIZE_1 = b->getSize(1);
522        Value* SIZE_64 = b->getSize(64);
523        Type* i8PtrTy = b->getInt8PtrTy();
524
525        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", SIZE_0), i8PtrTy);
526        Value* tokenOutputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("tokenByteBuffer", SIZE_0), i8PtrTy);
527        Value* outputCapacity = b->getCapacity("outputStream");
528
529        // ---- EntryBlock
530        BasicBlock* entryBlock = b->GetInsertBlock();
531        BasicBlock* appendLiteralConBlock = b->CreateBasicBlock("AppendLiteralConBlock");
532        BasicBlock* appendLiteralBodyBlock = b->CreateBasicBlock("AppendLiteralBodyBlock");
533        BasicBlock* appendLiteralExitBlock = b->CreateBasicBlock("AppendLiteralExitBlock");
534
535        b->CreateBr(appendLiteralConBlock);
536
537        // ---- AppendLiteralConBlock
538        b->SetInsertPoint(appendLiteralConBlock);
539        PHINode* phiTokenOutputPos = b->CreatePHI(b->getSizeTy(), 2);
540        phiTokenOutputPos->addIncoming(tokenOutputPos, entryBlock);
541        PHINode* phiLiteralStart = b->CreatePHI(b->getSizeTy(), 2);
542        phiLiteralStart->addIncoming(literalStart, entryBlock);
543
544        Value* remainingLiteralLength = b->CreateSub(literalEnd, phiLiteralStart);
545        b->CreateCondBr(b->CreateICmpUGT(remainingLiteralLength, b->getSize(0)), appendLiteralBodyBlock, appendLiteralExitBlock);
546
547        // ---- AppendLiteralBodyBlock
548        b->SetInsertPoint(appendLiteralBodyBlock);
549
550        Value* maxLiteralLength = b->getSize(127);
551        Value* literalLength = b->CreateUMin(remainingLiteralLength, maxLiteralLength);
552
553        Value* literalToken = b->CreateOr(b->CreateTrunc(literalLength, b->getInt8Ty()), b->getInt8(1 << 7));
554
555        b->CreateStore(literalToken, b->CreateGEP(tokenOutputBasePtr, phiTokenOutputPos));
556
557        this->appendLiteralData(b, phiLiteralStart, literalLength);
558
559        phiLiteralStart->addIncoming(b->CreateAdd(phiLiteralStart, literalLength), b->GetInsertBlock());
560        phiTokenOutputPos->addIncoming(b->CreateAdd(phiTokenOutputPos, SIZE_1), b->GetInsertBlock());
561        b->CreateBr(appendLiteralConBlock);
562
563        // ---- AppendLiteralExitBlock
564        b->SetInsertPoint(appendLiteralExitBlock);
565        return phiTokenOutputPos;
566    }
567
568    Value* LZParabixCompressionKernel::appendMatchSequence(const unique_ptr<KernelBuilder> &b, const MatchInfo& matchInfo, Value* tokenOutputPos) {
569        // Constant
570        Value* SIZE_0 = b->getSize(0);
571        Value* SIZE_1 = b->getSize(1);
572        Value* SIZE_64 = b->getSize(64);
573        Type* i8PtrTy = b->getInt8PtrTy();
574
575        Value* tokenOutputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("tokenByteBuffer", SIZE_0), i8PtrTy);
576
577        // MatchOffset
578        b->CreateStore(b->CreateTrunc(matchInfo.matchOffset, b->getInt8Ty()), b->CreateGEP(tokenOutputBasePtr, tokenOutputPos));
579
580        Value* outputOneBitIndexPos = b->CreateAdd(tokenOutputPos, SIZE_1);
581        Value* outputZeroBitIndexPos = b->CreateAdd(outputOneBitIndexPos, SIZE_1);
582
583        Value* outputBitMaskPos = b->CreateAdd(outputZeroBitIndexPos, SIZE_1);
584
585        Value* oneBitIndex = b->getInt8(0);
586        Value* zeroBitIndex = b->getInt8(0);
587
588        for (unsigned i = 0; i < 8; i++) {
589            Value* currentBitIndex = b->CreateTrunc(b->CreateLShr(matchInfo.matchMask, b->getInt64(i * 8)), b->getInt8Ty());
590            Value* newOneBit = b->CreateICmpEQ(currentBitIndex, b->getInt8(0xff));
591            Value* newZeroBit = b->CreateICmpEQ(currentBitIndex, b->getInt8(0));
592
593            oneBitIndex = b->CreateSelect(
594                    newOneBit,
595                    b->CreateOr(oneBitIndex, b->getInt8(1 << i)),
596                    oneBitIndex
597            );
598
599            zeroBitIndex = b->CreateSelect(
600                    newZeroBit,
601                    b->CreateOr(zeroBitIndex, b->getInt8(1 << i)),
602                    zeroBitIndex
603            );
604            b->CreateStore(currentBitIndex, b->CreateGEP(tokenOutputBasePtr, outputBitMaskPos));
605            outputBitMaskPos = b->CreateSelect(
606                    b->CreateOr(newOneBit, newZeroBit),
607                    outputBitMaskPos,
608                    b->CreateAdd(outputBitMaskPos, SIZE_1)
609            );
610        }
611        b->CreateStore(oneBitIndex, b->CreateGEP(tokenOutputBasePtr, outputOneBitIndexPos));
612        b->CreateStore(zeroBitIndex, b->CreateGEP(tokenOutputBasePtr,outputZeroBitIndexPos));
613
614        return outputBitMaskPos;
615    }
616
617
618    void LZParabixCompressionKernel::appendLiteralData(const std::unique_ptr<KernelBuilder> &b, llvm::Value* literalStart, llvm::Value* literalLength) {
619        Value* SIZE_0 = b->getSize(0);
620        Value* SIZE_64 = b->getSize(64);
621        Value* shouldPrint = b->CreateICmpEQ(b->getScalarField("literalOutputPos"), b->getSize(0));
622
623        Value* literalStartRem = b->CreateURem(literalStart, b->getCapacity("basisBits"));
624        Value* literalEndRem = b->CreateAdd(literalStartRem, literalLength);
625
626
627        // ---- EntryBlock
628        BasicBlock* entryBlock = b->GetInsertBlock();
629        BasicBlock* literalCopyConBlock = b->CreateBasicBlock("literalCopyConBlock");
630        BasicBlock* literalCopyBodyBlock = b->CreateBasicBlock("literalCopyBodyBlock");
631        BasicBlock* literalCopyExitBlock = b->CreateBasicBlock("literalCopyExitBlock");
632        b->CreateBr(literalCopyConBlock);
633
634        // ---- literalCopyConBlock
635        b->SetInsertPoint(literalCopyConBlock);
636        PHINode* phiLiteralPos = b->CreatePHI(b->getSizeTy(), 2);
637        phiLiteralPos->addIncoming(literalStartRem, entryBlock);
638        b->CreateCondBr(b->CreateICmpULT(phiLiteralPos, literalEndRem), literalCopyBodyBlock, literalCopyExitBlock);
639
640        // ---- literalCopyBodyBlock
641        b->SetInsertPoint(literalCopyBodyBlock);
642
643
644        Value* remainingLiteralLength = b->CreateSub(literalEndRem, phiLiteralPos);
645        Value* copyLength = b->CreateSub(SIZE_64, b->CreateURem(phiLiteralPos, SIZE_64));
646        copyLength = b->CreateUMin(copyLength, remainingLiteralLength);
647
648        Value* cursorBlockIndex = b->CreateUDiv(phiLiteralPos, b->getSize(b->getBitBlockWidth()));
649        Value* cursorBlockRem = b->CreateURem(phiLiteralPos, b->getSize(b->getBitBlockWidth()));
650        Value* cursorI64BlockIndex = b->CreateUDiv(cursorBlockRem, b->getSize(64));
651        Value* cursorI64BlockRem = b->CreateURem(cursorBlockRem, b->getSize(64));
652        Value* literalMask = b->CreateSub(
653                b->CreateSelect(b->CreateICmpEQ(copyLength, b->getInt64(0x40)), b->getInt64(0), b->CreateShl(b->getInt64(1), copyLength)),
654                b->getInt64(1)
655        );
656
657        std::vector<llvm::Value*> extractValues;
658
659        Value* bitStreamBasePtr = b->CreatePointerCast(b->getRawInputPointer("basisBits", SIZE_0), b->getBitBlockType()->getPointerTo());
660        Value* targetBlockBasePtr = b->CreatePointerCast(b->CreateGEP(bitStreamBasePtr, b->CreateMul(cursorBlockIndex, b->getSize(8))), b->getInt64Ty()->getPointerTo());
661
662        for (unsigned j = 0; j < 8; j++) {
663            Value* ptr = b->CreateGEP(targetBlockBasePtr, b->CreateAdd(cursorI64BlockIndex, b->getSize(j * (b->getBitBlockWidth() / 64))));
664            Value* extractV = b->CreateLShr(b->CreateLoad(ptr), cursorI64BlockRem);
665            extractV = b->CreateAnd(extractV, literalMask);
666            extractValues.push_back(extractV);
667        }
668        this->appendLiteralData(b, extractValues, copyLength);
669
670        phiLiteralPos->addIncoming(b->CreateAdd(phiLiteralPos, copyLength), b->GetInsertBlock());
671        b->CreateBr(literalCopyConBlock);
672
673        // ---- literalCopyExitBlock
674        b->SetInsertPoint(literalCopyExitBlock);
675    }
676
677    void LZParabixCompressionKernel::appendLiteralData(const std::unique_ptr<KernelBuilder> &b, std::vector<llvm::Value*> literalData, llvm::Value* valueLength) {
678        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
679
680        Value* oldOutputPos = b->getScalarField("literalOutputPos");
681        Value* oldOutputPosRem64 = b->CreateURem(oldOutputPos, b->getSize(64));
682        Value* pendingOutputBasePtr = b->CreatePointerCast(b->getScalarFieldPtr("pendingLiteralOutput"), b->getInt64Ty()->getPointerTo());
683
684
685        std::vector<llvm::Value*> newOutputVec;
686
687        for (unsigned j = 0; j < 8; j++) {
688            Value* newValue = b->CreateOr(b->CreateLoad(b->CreateGEP(pendingOutputBasePtr, b->getSize(j))), b->CreateShl(literalData[j], oldOutputPosRem64));
689            newOutputVec.push_back(newValue);
690        }
691
692        BasicBlock* noStoreOutputBlock = b->CreateBasicBlock("noStoreOutputBlock");
693        BasicBlock* storeOutputBlock =b->CreateBasicBlock("storeOutputBlock");
694
695        b->CreateCondBr(b->CreateICmpULT(b->CreateAdd(oldOutputPosRem64, valueLength), b->getSize(64)), noStoreOutputBlock, storeOutputBlock);
696
697        // ---- noStoreOutputBlock
698        b->SetInsertPoint(noStoreOutputBlock);
699
700        for (unsigned j = 0; j < 8; j++) {
701            b->CreateStore(newOutputVec[j], b->CreateGEP(pendingOutputBasePtr, b->getSize(j)));
702        }
703
704        b->CreateBr(exitBlock);
705
706        // ---- storeOutputBlock
707        b->SetInsertPoint(storeOutputBlock);
708
709        Value* oldOutputPosRem = oldOutputPos; // we guarantee oldOutputPos will always inside buffer
710        Value* oldOutputPosBitBlockIndex = b->CreateUDiv(oldOutputPosRem, b->getSize(b->getBitBlockWidth()));
711        Value* oldOutputPosBitBlockRem = b->CreateURem(oldOutputPosRem, b->getSize(b->getBitBlockWidth()));
712
713        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("literalByteBuffer", b->getSize(0)), b->getBitBlockType()->getPointerTo());
714        Value* outputBitBlockBasePtr = b->CreateGEP(outputBasePtr, b->CreateMul(oldOutputPosBitBlockIndex, b->getSize(8)));
715        outputBitBlockBasePtr = b->CreatePointerCast(outputBitBlockBasePtr, b->getInt64Ty()->getPointerTo());
716
717        Value* oldOutputPosI64Index = b->CreateUDiv(oldOutputPosBitBlockRem, b->getSize(64));
718
719        for (unsigned j = 0; j < 8; j++) {
720            Value* targetPtr = b->CreateGEP(outputBitBlockBasePtr, b->CreateAdd(oldOutputPosI64Index, b->getSize(j * (b->getBitBlockWidth() / 64))));
721            b->CreateStore(newOutputVec[j], targetPtr);
722        }
723
724        Value* shiftAmount = b->CreateSub(b->getSize(0x40), oldOutputPosRem64);
725        Value* fullyShift = b->CreateICmpEQ(shiftAmount, b->getSize(0x40));
726
727        for (unsigned j = 0; j < 8; j++) {
728            b->CreateStore(b->CreateSelect(fullyShift, b->getInt64(0), b->CreateLShr(literalData[j], shiftAmount)), b->CreateGEP(pendingOutputBasePtr, b->getSize(j)));
729        }
730
731        b->CreateBr(exitBlock);
732
733        b->SetInsertPoint(exitBlock);
734        b->setScalarField("literalOutputPos", b->CreateAdd(oldOutputPos, valueLength));
735    }
736
737    void LZParabixCompressionKernel::storePendingLiteralData(const std::unique_ptr<KernelBuilder> &b) {
738        Value* oldOutputPos = b->getScalarField("literalOutputPos");
739        Value* oldOutputPosRem = oldOutputPos; // We guarantee output buffer will always be enough
740        Value* oldOutputPosBitBlockIndex = b->CreateUDiv(oldOutputPosRem, b->getSize(b->getBitBlockWidth()));
741        Value* oldOutputPosBitBlockRem = b->CreateURem(oldOutputPosRem, b->getSize(b->getBitBlockWidth()));
742        Value* oldOutputPosI64Index = b->CreateUDiv(oldOutputPosBitBlockRem, b->getSize(64));
743
744        Value* pendingOutputBasePtr = b->CreatePointerCast(b->getScalarFieldPtr("pendingLiteralOutput"), b->getInt64Ty()->getPointerTo());
745        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("literalByteBuffer", b->getSize(0)), b->getBitBlockType()->getPointerTo());
746        Value* outputBitBlockBasePtr = b->CreateGEP(outputBasePtr, b->CreateMul(oldOutputPosBitBlockIndex, b->getSize(8)));
747        outputBitBlockBasePtr = b->CreatePointerCast(outputBitBlockBasePtr, b->getInt64Ty()->getPointerTo());
748        for (unsigned j = 0; j < 8; j++) {
749            Value* targetPtr = b->CreateGEP(outputBitBlockBasePtr, b->CreateAdd(oldOutputPosI64Index, b->getSize(j * (b->getBitBlockWidth() / 64))));
750            b->CreateStore(b->CreateLoad(b->CreateGEP(pendingOutputBasePtr, b->getSize(j))), targetPtr);
751        }
752    }
753}
Note: See TracBrowser for help on using the repository browser.