source: icGREP/icgrep-devel/icgrep/kernels/lz4/lz4_index_builder_new.cpp @ 6059

Last change on this file since 6059 was 6059, checked in by xwa163, 11 months ago
  1. Enable swizzled match copy in multiplexing lz4_grep for some special case
  2. Implement some lz4 AIO (all-in-one) pipeline and related kernel
File size: 35.2 KB
Line 
1
2#include "lz4_index_builder_new.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
10using namespace llvm;
11using namespace kernel;
12using namespace std;
13
14namespace kernel{
15
16
17    LZ4IndexBuilderNewKernel::LZ4IndexBuilderNewKernel(const std::unique_ptr<kernel::KernelBuilder> &b)
18    :SegmentOrientedKernel("LZ4IndexBuilderNewKernel",
19            // Inputs
20                           {
21                                   Binding{b->getStreamSetTy(1, 8), "byteStream", BoundedRate(0, 1)},
22                                   Binding{b->getStreamSetTy(1, 1), "extender", RateEqualTo("byteStream")},
23
24                                   // block data
25                                   Binding{b->getStreamSetTy(1, 1), "isCompressed", BoundedRate(0, 1), AlwaysConsume()},
26                                   Binding{b->getStreamSetTy(1, 64), "blockStart", RateEqualTo("isCompressed"), AlwaysConsume()},
27                                   Binding{b->getStreamSetTy(1, 64), "blockEnd", RateEqualTo("isCompressed"), AlwaysConsume()}
28
29                           },
30            //Outputs
31                           {
32                                   // Uncompressed_data
33                                   Binding{b->getStreamSetTy(1, 64), "uncompressedStartPos",
34                                           BoundedRate(0, 1)},
35                                   Binding{b->getStreamSetTy(1, 64), "uncompressedLength",
36                                           BoundedRate(0, 1)},
37                                   Binding{b->getStreamSetTy(1, 64), "uncompressedOutputPos",
38                                           BoundedRate(0, 1)},
39
40                                   Binding{b->getStreamSetTy(1, 1), "deletionMarker", RateEqualTo("byteStream")},
41                                   Binding{b->getStreamSetTy(1, 1), "M0Marker", BoundedRate(0, 1)},
42                                   Binding{b->getStreamSetTy(1, 1), "MatchOffsetMarker", RateEqualTo("byteStream")}
43                           },
44            //Arguments
45                           {
46                                   Binding{b->getSizeTy(), "fileSize"}
47                           },
48                           {},
49            //Internal states:
50                           {
51                                Binding{b->getInt64Ty(), "tempTimes"},
52                                   Binding{b->getSizeTy(), "blockDataIndex"},
53//                                   Binding{b->getInt64Ty(), "m0OutputPos"},
54//
55//                                   // For MatchOffset Output
56//                                   Binding{b->getIntNTy(64), "pendingMatchOffsetMarkerBits"},
57//                                   Binding{b->getInt64Ty(), "pendingMarchOffsetMarkerIndex"},
58//
59//                                   // For deletionMarker output
60                                    //pendingDeletionMarker = (EndBits - StartBits - CarryBit) | FullBits
61                                   Binding{b->getIntNTy(64), "pendingLiteralMarkerStartBits"},
62                                   Binding{b->getIntNTy(64), "pendingLiteralMarkerEndBits"},
63                                   Binding{b->getIntNTy(64), "pendingLiteralMarkerCarryBit"},
64                                   Binding{b->getIntNTy(64), "pendingLiteralMarkerFullBits"},
65                                   Binding{b->getInt64Ty(), "pendingLiteralMarkerIndex"},
66
67//                                   // For M0 Output
68//                                   Binding{b->getIntNTy(64), "pendingM0StartBits"},
69//                                   Binding{b->getIntNTy(64), "pendingM0EndBits"},
70//                                   Binding{b->getIntNTy(64), "pendingM0CarryBit"},
71//                                   Binding{b->getInt64Ty(), "pendingM0Index"},
72
73
74                           }){
75        this->setStride(4 * 1024 * 1024);
76        addAttribute(MustExplicitlyTerminate());
77    }
78
79    void LZ4IndexBuilderNewKernel::generateDoSegmentMethod(const std::unique_ptr<KernelBuilder> &b) {
80        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
81        BasicBlock* blockEndConBlock = b->CreateBasicBlock("blockEndConBlock");
82
83        Value * blockDataIndex = b->getScalarField("blockDataIndex");
84
85        // In MultiblockKernel, availableItemCount + processedItemCount == producedItemCount from previous kernel
86        // While in SegmentOrigentedKernel, availableItemCount == producedItemCount from previous kernel
87        Value * totalNumber = b->getAvailableItemCount("blockEnd");
88        Value * totalExtender = b->getAvailableItemCount("extender");
89
90        Value * blockEnd = this->generateLoadInt64NumberInput(b, "blockEnd", blockDataIndex);
91
92        b->CreateCondBr(b->CreateICmpULT(blockDataIndex, totalNumber), blockEndConBlock, exitBlock);
93
94        b->SetInsertPoint(blockEndConBlock);
95        Value * blockStart = this->generateLoadInt64NumberInput(b, "blockStart", blockDataIndex);
96        BasicBlock * processBlock = b->CreateBasicBlock("processBlock");
97        b->CreateCondBr(b->CreateICmpULE(blockEnd, totalExtender), processBlock, exitBlock);
98
99        b->SetInsertPoint(processBlock);
100
101        //TODO handle uncompressed block
102
103        this->generateProcessCompressedBlock(b, blockStart, blockEnd);
104        // TODO store pending value
105//        this->storePendingM0(b);
106        this->storePendingLiteralMask(b);
107//        this->storePendingMatchOffsetMarker(b);
108        Value * newBlockDataIndex = b->CreateAdd(blockDataIndex, b->getInt64(1));
109        b->setScalarField("blockDataIndex", newBlockDataIndex);
110        b->setProcessedItemCount("isCompressed", newBlockDataIndex);
111        b->setProcessedItemCount("byteStream", blockEnd);
112
113        b->CreateBr(exitBlock);
114
115        b->SetInsertPoint(exitBlock);
116        b->CallPrintIntCond("time", b->getScalarField("tempTimes"), b->getTerminationSignal());
117    }
118
119    llvm::Value *LZ4IndexBuilderNewKernel::generateLoadInt64NumberInput(const std::unique_ptr<KernelBuilder> &iBuilder,
120                                                                        std::string inputBufferName,
121                                                                        llvm::Value *globalOffset) {
122        Value * capacity = iBuilder->getCapacity(inputBufferName);
123        Value * processed = iBuilder->getProcessedItemCount(inputBufferName);
124        processed = iBuilder->CreateAnd(processed, iBuilder->CreateNeg(capacity));
125        Value * offset = iBuilder->CreateSub(globalOffset, processed);
126        Value * valuePtr = iBuilder->getRawInputPointer(inputBufferName, offset);
127        return iBuilder->CreateLoad(valuePtr);
128    }
129
130    void LZ4IndexBuilderNewKernel::generateProcessCompressedBlock(const std::unique_ptr<KernelBuilder> &b,
131                                                                  llvm::Value *lz4BlockStart, llvm::Value *lz4BlockEnd) {
132        BasicBlock* entryBlock = b->GetInsertBlock();
133
134        Value* isTerminal = b->CreateICmpEQ(lz4BlockEnd, b->getScalarField("fileSize"));
135        b->setTerminationSignal(isTerminal);
136
137        BasicBlock* exitBlock = b->CreateBasicBlock("processCompressedExitBlock");
138
139        BasicBlock* processCon = b->CreateBasicBlock("processCompressedConBlock");
140        BasicBlock* processBody = b->CreateBasicBlock("processCompressedBodyBlock");
141
142        // We store all of the pending data before the parabixBlock of lz4BlockStart to make sure the current pending
143        // block will be the same as the block we process during the acceleration
144        this->storePendingLiteralMasksUntilPos(b, lz4BlockStart);
145        // TODO handle matchOffsetMarker, and maybe we also need to handle M0Marker here
146
147
148        BasicBlock* beforeProcessConBlock = b->GetInsertBlock();
149        b->CreateBr(processCon);
150        b->SetInsertPoint(processCon);
151
152        PHINode* phiCursorValue = b->CreatePHI(b->getInt64Ty(), 2, "phiCursorValue"); // phiCursorValue should always be the position of next token except for the final sequence
153        phiCursorValue->addIncoming(lz4BlockStart, beforeProcessConBlock);
154
155        b->CreateCondBr(b->CreateICmpULT(phiCursorValue, lz4BlockEnd), processBody, exitBlock);
156
157        b->SetInsertPoint(processBody);
158
159        Value* time1 = b->CreateReadCycleCounter();
160        auto accelerationRet = this->generateAcceleration(b, phiCursorValue, lz4BlockEnd);
161        Value* time2 = b->CreateReadCycleCounter();
162        b->setScalarField("tempTimes", b->CreateAdd(b->getScalarField("tempTimes"), b->CreateSub(time2, time1)));
163
164
165        Value* tokenMarkers = accelerationRet.first.first;
166        Value* literalMasks = accelerationRet.first.second;
167//        b->CallPrintInt("phiCursorValue", phiCursorValue);
168//        b->CallPrintInt("literalMasks", literalMasks);
169        Value* matchOffsetMarkers = accelerationRet.second;
170
171        // The pending data block index (for compression space) will be the same as the block index of current acceleration block
172        b->setScalarField("pendingLiteralMarkerFullBits", b->CreateOr(literalMasks, b->getScalarField("pendingLiteralMarkerFullBits")));
173
174
175        Value* cursorBlockPosBase = b->CreateSub(phiCursorValue, b->CreateURem(phiCursorValue, b->getSize(ACCELERATION_WIDTH)));
176        Value* nextTokenLocalPos = b->CreateSub(b->CreateSub(b->getSize(ACCELERATION_WIDTH), b->CreateCountReverseZeroes(tokenMarkers)), b->getSize(1));
177        Value* nextTokenGlobalPos = b->CreateAdd(cursorBlockPosBase, nextTokenLocalPos);
178
179        nextTokenGlobalPos = this->processBlockBoundary(b, nextTokenGlobalPos, lz4BlockEnd);
180
181        phiCursorValue->addIncoming(nextTokenGlobalPos, b->GetInsertBlock());
182        b->CreateBr(processCon);
183
184        b->SetInsertPoint(exitBlock);
185    }
186
187    llvm::Value* LZ4IndexBuilderNewKernel::processBlockBoundary(const std::unique_ptr<KernelBuilder> &b,
188                              llvm::Value *beginTokenPos, llvm::Value* lz4BlockEnd) {
189        // Constant
190        ConstantInt* SIZE_0 = b->getSize(0);
191        ConstantInt* SIZE_1 = b->getSize(1);
192        ConstantInt* BYTE_FF = b->getInt8(0xff);
193        Value* BYTE_F0 = b->getInt8(0xf0);
194        Value* BYTE_0F = b->getInt8(0x0f);
195
196        // ---- EntryBlock
197        BasicBlock* entryBlock = b->GetInsertBlock();
198        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
199
200        Value* bytePtrBase = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
201
202        Value* tokenValue = b->CreateLoad(b->CreateGEP(bytePtrBase, beginTokenPos));
203
204        Value* shouldExtendLiteral = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_F0), BYTE_F0);
205
206        Value* shouldExtendMatch = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_0F), BYTE_0F);
207
208        BasicBlock* extendLiteralCond = b->CreateBasicBlock("extendLiteralCond");
209        BasicBlock* extendLiteralEnd = b->CreateBasicBlock("extendLiteralEnd");
210
211        Value* initExtendLiteralPos = b->CreateAdd(beginTokenPos, b->getSize(1));
212
213        b->CreateCondBr(shouldExtendLiteral, extendLiteralCond, extendLiteralEnd);
214
215        // ---- extendLiteralCond
216        b->SetInsertPoint(extendLiteralCond);
217        PHINode* phiCurrentExtendLiteralPos = b->CreatePHI(b->getSizeTy(), 2);
218        phiCurrentExtendLiteralPos->addIncoming(initExtendLiteralPos, entryBlock);
219        PHINode* phiExtendLiteralLength = b->CreatePHI(b->getSizeTy(), 2);
220        phiExtendLiteralLength->addIncoming(SIZE_0, entryBlock);
221
222        Value* currentLiteralLengthByte = b->CreateLoad(b->CreateGEP(bytePtrBase, phiCurrentExtendLiteralPos));
223        Value* newExtendLiteralLength = b->CreateAdd(phiExtendLiteralLength, b->CreateZExt(currentLiteralLengthByte, b->getSizeTy()));
224
225        phiCurrentExtendLiteralPos->addIncoming(b->CreateAdd(phiCurrentExtendLiteralPos, SIZE_1), b->GetInsertBlock());
226        phiExtendLiteralLength->addIncoming(newExtendLiteralLength, b->GetInsertBlock());
227
228        b->CreateCondBr(b->CreateICmpEQ(currentLiteralLengthByte, BYTE_FF), extendLiteralCond, extendLiteralEnd);
229
230        // ---- extendLiteralEnd
231        b->SetInsertPoint(extendLiteralEnd);
232        PHINode* literalExtendValue = b->CreatePHI(b->getSizeTy(), 2);
233        literalExtendValue->addIncoming(SIZE_0, entryBlock);
234        literalExtendValue->addIncoming(newExtendLiteralLength, extendLiteralCond);
235        PHINode* phiExtendLiteralEndPos = b->CreatePHI(b->getSizeTy(), 2);
236        phiExtendLiteralEndPos->addIncoming(beginTokenPos, entryBlock);
237        phiExtendLiteralEndPos->addIncoming(phiCurrentExtendLiteralPos, extendLiteralCond);
238
239        Value* literalLength = b->CreateAdd(literalExtendValue, b->CreateZExt(b->CreateLShr(tokenValue, b->getInt8(4)), b->getSizeTy()));
240
241        Value* literalStartPos = b->CreateAdd(phiExtendLiteralEndPos, SIZE_1);
242        Value* literalEndPos = b->CreateAdd(literalStartPos, literalLength);
243
244        Value* matchOffsetBeginPos = literalEndPos;
245        Value* matchOffsetNextPos = b->CreateAdd(matchOffsetBeginPos, SIZE_1);
246
247        BasicBlock* hasMatchPartBlock = b->CreateBasicBlock("hasMatchPartBlock");
248        BasicBlock* extendMatchCon = b->CreateBasicBlock("extendMatchCon");
249        BasicBlock* extendMatchExit = b->CreateBasicBlock("extendMatchExit");
250
251        b->CreateLikelyCondBr(b->CreateICmpULT(matchOffsetBeginPos, lz4BlockEnd), hasMatchPartBlock, exitBlock);
252
253        // ---- hasMatchPartBlock
254        b->SetInsertPoint(hasMatchPartBlock);
255        Value* initExtendMatchPos = b->CreateAdd(matchOffsetBeginPos, b->getSize(2));
256        b->CreateCondBr(shouldExtendMatch, extendMatchCon, extendMatchExit);
257
258        // ---- extendMatchCon
259        b->SetInsertPoint(extendMatchCon);
260        PHINode* phiCurrentExtendMatchPos = b->CreatePHI(b->getSizeTy(), 2);
261        phiCurrentExtendMatchPos->addIncoming(initExtendMatchPos, hasMatchPartBlock);
262        PHINode* phiExtendMatchLength = b->CreatePHI(b->getSizeTy(), 2);
263        phiExtendMatchLength->addIncoming(SIZE_0, hasMatchPartBlock);
264
265        Value* currentMatchLengthByte = b->CreateLoad(b->CreateGEP(bytePtrBase, phiCurrentExtendMatchPos));
266        Value* newExtendMatchLength = b->CreateAdd(phiExtendMatchLength, b->CreateZExt(currentMatchLengthByte, b->getSizeTy()));
267
268        phiCurrentExtendMatchPos->addIncoming(b->CreateAdd(phiCurrentExtendMatchPos, SIZE_1), b->GetInsertBlock());
269        phiExtendMatchLength->addIncoming(newExtendMatchLength, b->GetInsertBlock());
270
271        b->CreateCondBr(b->CreateICmpEQ(currentMatchLengthByte, BYTE_FF), extendMatchCon, extendMatchExit);
272
273        // ---- extendMatchExit
274        b->SetInsertPoint(extendMatchExit);
275        PHINode* matchExtendValue = b->CreatePHI(b->getSizeTy(), 2);
276        matchExtendValue->addIncoming(SIZE_0, hasMatchPartBlock);
277        matchExtendValue->addIncoming(newExtendMatchLength, extendMatchCon);
278        PHINode* phiExtendMatchEndPos = b->CreatePHI(b->getSizeTy(), 2);
279        phiExtendMatchEndPos->addIncoming(matchOffsetNextPos, hasMatchPartBlock);
280        phiExtendMatchEndPos->addIncoming(phiCurrentExtendMatchPos, extendMatchCon);
281
282        // matchLength = (size_t)token & 0xf + 4 + matchExtendValue
283        Value* matchLength = b->CreateAdd(
284                b->CreateAdd(matchExtendValue, b->getSize(4)),
285                b->CreateZExt(b->CreateAnd(tokenValue, BYTE_0F), b->getSizeTy())
286        );
287        // TODO mark MatchOffset : matchOffsetBeginPos, and matchLength: matchLength
288        b->CreateBr(exitBlock);
289
290        // ---- exitBlock
291        b->SetInsertPoint(exitBlock);
292        PHINode* phiBeforeTokenPos = b->CreatePHI(b->getSizeTy(), 2);
293        phiBeforeTokenPos->addIncoming(matchOffsetNextPos, extendLiteralEnd);
294        phiBeforeTokenPos->addIncoming(phiExtendMatchEndPos, extendMatchExit);
295        Value* nextTokenPos = b->CreateAdd(phiBeforeTokenPos, SIZE_1);
296
297        this->appendBoundaryLiteralMaskOutput(b, literalStartPos, literalEndPos, nextTokenPos);
298
299        return nextTokenPos;
300    }
301
302    std::pair<std::pair<llvm::Value*, llvm::Value*>, llvm::Value*> LZ4IndexBuilderNewKernel::generateAcceleration(const std::unique_ptr<KernelBuilder> &b,
303                                                        llvm::Value *beginTokenPos, llvm::Value* blockEnd) {
304        BasicBlock* entryBlock = b->GetInsertBlock();
305
306        // Constant
307        Value* SIZE_ACCELERATION_WIDTH = b->getSize(ACCELERATION_WIDTH);
308        Value* SIZE_1 = b->getSize(1);
309        Value* SIZE_0 = b->getSize(0);
310
311        Type* INT_ACCELERATION_TYPE = b->getIntNTy(ACCELERATION_WIDTH);
312        Value* INT_ACCELERATION_0 = b->getIntN(ACCELERATION_WIDTH, 0);
313        Value* INT_ACCELERATION_1 = b->getIntN(ACCELERATION_WIDTH, 1);
314
315        // ---- Entry Block
316        Value* maskedTokenPos = b->CreateURem(beginTokenPos, b->getCapacity("extender"));
317        Value* tokenPosRem = b->CreateURem(beginTokenPos, SIZE_ACCELERATION_WIDTH);
318        Value* blockPosBase = b->CreateSub(beginTokenPos, tokenPosRem);
319
320        Value* currentExtenderValue = b->CreateLoad(
321                b->CreateGEP(
322                        b->CreatePointerCast(b->getRawInputPointer("extender", SIZE_0), INT_ACCELERATION_TYPE->getPointerTo()),
323                        b->CreateUDiv(maskedTokenPos, SIZE_ACCELERATION_WIDTH)
324                )
325        );
326
327        Value* extenderPtrBase = b->CreatePointerCast(b->getRawInputPointer("extender", SIZE_0), INT_ACCELERATION_TYPE->getPointerTo());
328        Value* actualPtr = b->CreateGEP(
329                b->CreatePointerCast(b->getRawInputPointer("extender", SIZE_0), INT_ACCELERATION_TYPE->getPointerTo()),
330                b->CreateUDiv(maskedTokenPos, SIZE_ACCELERATION_WIDTH)
331        );
332        Value* initTokenMarker = b->CreateShl(INT_ACCELERATION_1, tokenPosRem);
333        BasicBlock* accelerationProcessBlock = b->CreateBasicBlock("accelerationProcessBlock");
334        BasicBlock* accelerationExitBlock = b->CreateBasicBlock("accelerationExitBlock");
335        b->CreateBr(accelerationProcessBlock);
336
337        // ---- AccelerationProcessBlock
338        b->SetInsertPoint(accelerationProcessBlock);
339        PHINode* phiTokenMarkers = b->CreatePHI(INT_ACCELERATION_TYPE, 2);
340        phiTokenMarkers->addIncoming(initTokenMarker, entryBlock);
341        PHINode* phiLiteralMasks = b->CreatePHI(INT_ACCELERATION_TYPE, 2);
342        phiLiteralMasks->addIncoming(INT_ACCELERATION_0, entryBlock);
343        PHINode* phiMatchOffsetMarkers = b->CreatePHI(INT_ACCELERATION_TYPE, 2);
344        phiMatchOffsetMarkers->addIncoming(INT_ACCELERATION_0, entryBlock);
345
346
347        Value* tokenReverseZeros = b->CreateCountReverseZeroes(phiTokenMarkers);
348        Value* currentTokenLocalPos = b->CreateSub(b->CreateSub(SIZE_ACCELERATION_WIDTH, tokenReverseZeros), SIZE_1);
349        Value* currentTokenMarker = b->CreateShl(INT_ACCELERATION_1, currentTokenLocalPos); // 1 marker is in Token Pos
350        Value* currentTokenGlobalPos = b->CreateAdd(blockPosBase, currentTokenLocalPos);
351        Value* tokenValue = b->CreateLoad(b->getRawInputPointer("byteStream", currentTokenGlobalPos));
352
353        llvm::Value *literalLength, *literalLengthEndMarker;
354        std::tie(literalLength, literalLengthEndMarker) =
355                this->scanThruLiteralLength(b, currentTokenMarker, currentExtenderValue, tokenValue, blockPosBase,
356                                            currentTokenLocalPos);
357        Value* literalBeginMarker = b->CreateShl(literalLengthEndMarker, SIZE_1);
358        Value* literalEndMarker = b->CreateSelect(b->CreateICmpULT(literalLength, SIZE_ACCELERATION_WIDTH), b->CreateShl(literalBeginMarker, literalLength), INT_ACCELERATION_0);
359
360        Value* newLiteralMask = b->CreateSub(literalEndMarker, literalBeginMarker);
361
362        Value* newMatchOffsetStartMarker = literalEndMarker; // TODO It is possible that we reach block end here in final block
363
364        Value *matchLength, *matchLengthEndMarker;
365        std::tie(matchLength, matchLengthEndMarker) =
366                this->scanThruMatchLength(b, b->CreateShl(newMatchOffsetStartMarker, SIZE_1), currentExtenderValue,
367                                          tokenValue, blockPosBase);
368        Value *newTokenMarker = b->CreateShl(matchLengthEndMarker, SIZE_1);
369        Value* newTokenMarkerLocalPos = b->CreateCountForwardZeroes(newTokenMarker);
370
371        Value* reachEnd = b->CreateOr(
372                b->CreateICmpEQ(newTokenMarker, b->getSize(0)),
373                b->CreateICmpUGE(b->CreateAdd(newTokenMarkerLocalPos, blockPosBase), blockEnd)
374        );
375
376        phiTokenMarkers->addIncoming(b->CreateOr(phiTokenMarkers, newTokenMarker), b->GetInsertBlock());
377        phiLiteralMasks->addIncoming(b->CreateOr(phiLiteralMasks, newLiteralMask), b->GetInsertBlock());
378        phiMatchOffsetMarkers->addIncoming(b->CreateOr(phiMatchOffsetMarkers, newMatchOffsetStartMarker), b->GetInsertBlock());
379
380        b->CreateCondBr(reachEnd, accelerationExitBlock, accelerationProcessBlock);
381
382        // ---- AccelerationExitBlock
383        b->SetInsertPoint(accelerationExitBlock);
384        // TODO handle m0 output
385
386        return std::make_pair(std::make_pair(phiTokenMarkers, phiLiteralMasks), phiMatchOffsetMarkers);
387    }
388
389    std::pair<llvm::Value *, llvm::Value *>
390    LZ4IndexBuilderNewKernel::scanThruLiteralLength(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* SIZE_1 = b->getSize(1);
398        Value* BYTE_F0 = b->getInt8(0xf0);
399        Value* shouldExtendLiteral = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_F0), BYTE_F0);
400
401        // Extend Literal Length
402        Value* literalScanThruResult = this->scanThru(b, b->CreateShl(currentTokenMarker, SIZE_1), currentExtenderValue);
403        Value* literalScanThruLocalPos = b->CreateCountForwardZeroes(literalScanThruResult);
404        Value* literalScanThruGlobalPos = b->CreateAdd(literalScanThruLocalPos, blockPosBase);
405        Value* literalScanThruLastBit = b->CreateLoad(b->getRawInputPointer("byteStream", literalScanThruGlobalPos));
406        // literalExtendResult = 255 * (literalScanThruLocalPos - currentTokenLocalPos - 1) + (size_t)literalScanThruLastBit
407        Value* literalExtendResult = b->CreateAdd(
408                b->CreateMul(
409                        b->getSize(255),
410                        b->CreateSub(
411                                b->CreateSub(literalScanThruLocalPos, currentTokenLocalPos),
412                                SIZE_1
413                        )
414                ),
415                b->CreateZExt(literalScanThruLastBit, b->getSizeTy())
416        );
417
418        // literalLength = (size_t)token >> 4 + shouldExtendLiteral ? literalExtendResult : 0
419        Value* literalLength = b->CreateAdd(
420                b->CreateLShr(
421                        b->CreateZExt(tokenValue, b->getSizeTy()),
422                        b->getSize(4)
423                ),
424                b->CreateSelect(
425                        shouldExtendLiteral,
426                        literalExtendResult,
427                        b->getSize(0)
428                )
429        );
430        Value* retLiteralMarker = b->CreateSelect(shouldExtendLiteral, literalScanThruResult, currentTokenMarker);
431
432        return std::make_pair(literalLength, retLiteralMarker);
433    }
434
435    std::pair<llvm::Value *, llvm::Value *>
436    LZ4IndexBuilderNewKernel::scanThruMatchLength(const std::unique_ptr<KernelBuilder> &b,
437                                                    llvm::Value *matchOffsetEndMarker,
438                                                    llvm::Value *currentExtenderValue,
439                                                    llvm::Value *tokenValue,
440                                                    llvm::Value *blockPosBase
441    ){
442        Value* SIZE_1 = b->getSize(1);
443        Value* BYTE_0F = b->getInt8(0x0f);
444        Value* shouldExtendMatch = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_0F), BYTE_0F);
445
446        // Extend Match Length
447        Value* matchScanThruResult = this->scanThru(b, b->CreateShl(matchOffsetEndMarker, SIZE_1), currentExtenderValue);
448        Value* matchScanThruLocalPos = b->CreateCountForwardZeroes(matchScanThruResult);
449        Value* matchScanThruGlobalPos = b->CreateAdd(matchScanThruLocalPos, blockPosBase);
450        Value* matchScanThruLastBit = b->CreateLoad(b->getRawInputPointer("byteStream", matchScanThruGlobalPos));
451        Value* matchOffsetEndLocalPos = b->CreateCountForwardZeroes(matchOffsetEndMarker);
452
453        // matchExtendResult = 255 * (matchScanThruLocalPos - matchOffsetEndLocalPos - 1) + (size_t)matchScanThruLastBit
454        Value* matchExtendResult = b->CreateAdd(
455                b->CreateMul(
456                        b->getSize(255),
457                        b->CreateSub(
458                                b->CreateSub(matchScanThruLocalPos, matchOffsetEndLocalPos),
459                                SIZE_1
460                        )
461                ),
462                b->CreateZExt(matchScanThruLastBit, b->getSizeTy())
463        );
464
465        // matchLength = (size_t)token & 0x0f + 4 + shouldExtendMatch ? matchExtendResult : 0
466        Value* matchLength = b->CreateAdd(
467                b->CreateAdd(
468                        b->CreateZExt(b->CreateAnd(tokenValue, BYTE_0F), b->getSizeTy()),
469                        b->getSize(4)
470                ),
471                b->CreateSelect(
472                        shouldExtendMatch,
473                        matchExtendResult,
474                        b->getSize(0)
475                )
476        );
477
478        Value* retMatchMarker = b->CreateSelect(shouldExtendMatch, matchScanThruResult, matchOffsetEndMarker);
479        return std::make_pair(matchLength, retMatchMarker);
480    };
481
482    llvm::Value *LZ4IndexBuilderNewKernel::scanThru(const std::unique_ptr<KernelBuilder> &b, llvm::Value *from,
483                                                    llvm::Value *thru) {
484        return b->CreateAnd(
485                b->CreateAdd(from, thru),
486                b->CreateNot(thru)
487        );
488    }
489
490
491    void LZ4IndexBuilderNewKernel::appendBoundaryLiteralMaskOutput(const std::unique_ptr<KernelBuilder> &b,
492                                                                   llvm::Value *globalLiteralStartPos,
493                                                                   llvm::Value *globalLiteralEndPos,
494                                                                   llvm::Value *outputUntilPos) {
495        // block index of globalStartPos will always equal to pending block index,
496        // and outputUntilPos will be equal to nextTokenPos,
497        // after this method, the pendingIndex will always be equal to the block index
498        // of next acceleration
499
500        // ---- Entry
501        // Constant
502        unsigned fw = 64;
503        Type* INT_FW_TY = b->getIntNTy(fw);
504        Value* SIZE_1 = b->getSize(1);
505        Value* SIZE_FW = b->getSize(fw);
506        Value* INT_FW_0 = b->getIntN(fw, 0);
507        Value* INT_FW_1 = b->getIntN(fw, 1);
508
509
510
511        Value* startBlockIndex = b->CreateUDiv(globalLiteralStartPos, SIZE_FW);
512        Value* startOffset = b->CreateZExt(b->CreateURem(globalLiteralStartPos, SIZE_FW), b->getIntNTy(fw));
513        Value* endBlockIndex = b->CreateUDiv(globalLiteralEndPos, SIZE_FW);
514        Value* endOffset = b->CreateZExt(b->CreateURem(globalLiteralEndPos, SIZE_FW), b->getIntNTy(fw));
515        Value* finishBlockIndex = b->CreateUDiv(outputUntilPos, SIZE_FW);
516
517
518        BasicBlock* appendLiteralMaskCon = b->CreateBasicBlock("appendLiteralMaskCon");
519        BasicBlock* appendLiteralMaskBody = b->CreateBasicBlock("appendLiteralMaskBody");
520        BasicBlock* appendLiteralMaskExit = b->CreateBasicBlock("appendLiteralMaskExit1");
521
522        Value* pendingLiteralMarkerIndex = b->getScalarField("pendingLiteralMarkerIndex");
523        Value* pendingLiteralMarkerStartBits = b->getScalarField("pendingLiteralMarkerStartBits");
524        Value* pendingLiteralMarkerEndBits = b->getScalarField("pendingLiteralMarkerEndBits");
525        Value* pendingLiteralMarkerCarryBit = b->getScalarField("pendingLiteralMarkerCarryBit");
526        Value* pendingLiteralMarkerFullBits = b->getScalarField("pendingLiteralMarkerFullBits");
527
528        BasicBlock* beforeCondBlock = b->GetInsertBlock();
529        b->CreateBr(appendLiteralMaskCon);
530
531        // ---- appendLiteralMaskCon
532        b->SetInsertPoint(appendLiteralMaskCon);
533        PHINode* phiCurrentIndex = b->CreatePHI(b->getSizeTy(), 2);
534        phiCurrentIndex->addIncoming(pendingLiteralMarkerIndex, beforeCondBlock);
535        PHINode* phiStartBits = b->CreatePHI(INT_FW_TY, 2);
536        phiStartBits->addIncoming(pendingLiteralMarkerStartBits, beforeCondBlock);
537        PHINode* phiEndBits = b->CreatePHI(INT_FW_TY, 2);
538        phiEndBits->addIncoming(pendingLiteralMarkerEndBits, beforeCondBlock);
539        PHINode* phiCarryBit = b->CreatePHI(INT_FW_TY, 2);
540        phiCarryBit->addIncoming(pendingLiteralMarkerCarryBit, beforeCondBlock);
541        PHINode* phiFullBits = b->CreatePHI(INT_FW_TY, 2);
542        phiFullBits->addIncoming(pendingLiteralMarkerFullBits, beforeCondBlock);
543
544        b->CreateUnlikelyCondBr(b->CreateICmpULT(phiCurrentIndex, finishBlockIndex), appendLiteralMaskBody, appendLiteralMaskExit);
545
546        // ---- appendLiteralMaskBody
547        b->SetInsertPoint(appendLiteralMaskBody);
548        Value* actualStartBits = b->CreateSelect(b->CreateICmpEQ(phiCurrentIndex, startBlockIndex), b->CreateOr(phiStartBits, b->CreateShl(INT_FW_1, startOffset)), phiStartBits);
549        Value* actualEndBits = b->CreateSelect(b->CreateICmpEQ(phiCurrentIndex, endBlockIndex), b->CreateOr(phiEndBits, b->CreateShl(INT_FW_1, endOffset)), phiEndBits);
550        Value* outputValue = b->CreateOr(b->CreateSub(b->CreateSub(actualEndBits, actualStartBits), phiCarryBit), phiFullBits);
551        Value* newCarryBit = b->CreateZExt(b->CreateICmpUGT(b->CreateAdd(actualStartBits, phiCarryBit), actualEndBits), b->getIntNTy(fw));
552        this->storeLiteralMask(b, phiCurrentIndex, outputValue);
553
554        phiCurrentIndex->addIncoming(b->CreateAdd(phiCurrentIndex, SIZE_1), b->GetInsertBlock());
555        phiStartBits->addIncoming(INT_FW_0, b->GetInsertBlock());
556        phiEndBits->addIncoming(INT_FW_0, b->GetInsertBlock());
557        phiFullBits->addIncoming(INT_FW_0, b->GetInsertBlock());
558        phiCarryBit->addIncoming(newCarryBit, b->GetInsertBlock());
559
560        b->CreateBr(appendLiteralMaskCon);
561
562        // ---- appendLiteralMaskExit
563        b->SetInsertPoint(appendLiteralMaskExit);
564        Value* finalStartBits = b->CreateSelect(b->CreateICmpEQ(phiCurrentIndex, startBlockIndex), b->CreateOr(phiStartBits, b->CreateShl(INT_FW_1, startOffset)), phiStartBits);
565        Value* finalEndBits = b->CreateSelect(b->CreateICmpEQ(phiCurrentIndex, endBlockIndex), b->CreateOr(phiEndBits, b->CreateShl(INT_FW_1, endOffset)), phiEndBits);
566        b->setScalarField("pendingLiteralMarkerIndex", phiCurrentIndex);
567        b->setScalarField("pendingLiteralMarkerStartBits", finalStartBits);
568        b->setScalarField("pendingLiteralMarkerEndBits", finalEndBits);
569        b->setScalarField("pendingLiteralMarkerFullBits", phiFullBits);
570        b->setScalarField("pendingLiteralMarkerCarryBit", phiCarryBit);
571    }
572
573    void
574    LZ4IndexBuilderNewKernel::storeLiteralMask(const std::unique_ptr<KernelBuilder> &b, llvm::Value *blockIndex,
575                                               llvm::Value *value) {
576        unsigned fw = 64;
577        Value* m0BufferBlocks = b->CreateUDiv(b->getCapacity("deletionMarker"), b->getSize(fw));
578        Value* indexRem = b->CreateURem(blockIndex, m0BufferBlocks);
579
580        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("deletionMarker", b->getSize(0)), b->getIntNTy(fw)->getPointerTo());
581        b->CreateStore(value, b->CreateGEP(outputBasePtr, indexRem));
582
583    }
584
585    void LZ4IndexBuilderNewKernel::storePendingLiteralMask(const std::unique_ptr<KernelBuilder> &b) {
586        Value* outputValue = b->CreateSub(
587                b->CreateSub(
588                        b->getScalarField("pendingLiteralMarkerEndBits"),
589                        b->getScalarField("pendingLiteralMarkerStartBits")
590                ),
591                b->getScalarField("pendingLiteralMarkerCarryBit")
592        );
593        this->storeLiteralMask(b, b->getScalarField("pendingLiteralMarkerIndex"), outputValue);
594    }
595
596    void LZ4IndexBuilderNewKernel::storePendingLiteralMasksUntilPos(const std::unique_ptr<KernelBuilder> &b,
597                                                                    llvm::Value *targetGlobalPos) {
598        unsigned fw = 64;
599        Type* INT_FW_TY = b->getIntNTy(fw);
600        Value* SIZE_1 = b->getSize(1);
601        Value* SIZE_FW = b->getSize(fw);
602        Value* INT_FW_0 = b->getIntN(fw, 0);
603
604
605        Value* targetBlockIndex = b->CreateUDiv(targetGlobalPos, SIZE_FW);
606//        Value* targetOffset = b->CreateZExt(b->CreateURem(targetPos, SIZE_FW), INT_FW_TY);
607
608        BasicBlock* appendLiteralMaskCon = b->CreateBasicBlock("appendLiteralMaskCon2");
609        BasicBlock* appendLiteralMaskBody = b->CreateBasicBlock("appendLiteralMaskBody2");
610        BasicBlock* appendLiteralMaskExit = b->CreateBasicBlock("appendLiteralMaskExit2");
611
612        Value* pendingLiteralMarkerIndex = b->getScalarField("pendingLiteralMarkerIndex");
613        Value* pendingLiteralMarkerStartBits = b->getScalarField("pendingLiteralMarkerStartBits");
614        Value* pendingLiteralMarkerEndBits = b->getScalarField("pendingLiteralMarkerEndBits");
615        Value* pendingLiteralMarkerCarryBit = b->getScalarField("pendingLiteralMarkerCarryBit");
616        Value* pendingLiteralMarkerFullBits = b->getScalarField("pendingLiteralMarkerFullBits");
617
618
619        BasicBlock* entryBlock = b->GetInsertBlock();
620
621        b->CreateBr(appendLiteralMaskCon);
622
623        // ---- appendLiteralMaskCon
624        b->SetInsertPoint(appendLiteralMaskCon);
625        PHINode* phiCurrentIndex = b->CreatePHI(b->getSizeTy(), 2);
626        phiCurrentIndex->addIncoming(pendingLiteralMarkerIndex, entryBlock);
627        PHINode* phiStartBits = b->CreatePHI(INT_FW_TY, 2);
628        phiStartBits->addIncoming(pendingLiteralMarkerStartBits, entryBlock);
629        PHINode* phiEndBits = b->CreatePHI(INT_FW_TY, 2);
630        phiEndBits->addIncoming(pendingLiteralMarkerEndBits, entryBlock);
631        PHINode* phiCarryBit = b->CreatePHI(INT_FW_TY, 2);
632        phiCarryBit->addIncoming(pendingLiteralMarkerCarryBit, entryBlock);
633        PHINode* phiFullBits = b->CreatePHI(INT_FW_TY, 2);
634        phiFullBits->addIncoming(pendingLiteralMarkerFullBits, entryBlock);
635
636        b->CreateUnlikelyCondBr(b->CreateICmpULT(phiCurrentIndex, targetBlockIndex), appendLiteralMaskBody, appendLiteralMaskExit);
637
638        // ---- appendLiteralMaskBody
639        b->SetInsertPoint(appendLiteralMaskBody);
640        Value* outputValue = b->CreateOr(b->CreateSub(b->CreateSub(phiEndBits, phiStartBits), phiCarryBit), phiFullBits);
641        Value* newCarryBit = b->CreateZExt(b->CreateICmpUGT(b->CreateAdd(phiStartBits, phiCarryBit), phiEndBits), b->getIntNTy(fw));
642        this->storeLiteralMask(b, phiCurrentIndex, outputValue);
643
644        phiCurrentIndex->addIncoming(b->CreateAdd(phiCurrentIndex, SIZE_1), b->GetInsertBlock());
645        phiStartBits->addIncoming(INT_FW_0, b->GetInsertBlock());
646        phiEndBits->addIncoming(INT_FW_0, b->GetInsertBlock());
647        phiCarryBit->addIncoming(newCarryBit, b->GetInsertBlock());
648        phiFullBits->addIncoming(INT_FW_0, b->GetInsertBlock());
649
650        b->CreateBr(appendLiteralMaskCon);
651
652        // ---- appendLiteralMaskExit
653        b->SetInsertPoint(appendLiteralMaskExit);
654        b->setScalarField("pendingLiteralMarkerIndex", phiCurrentIndex);
655        b->setScalarField("pendingLiteralMarkerStartBits", phiStartBits);
656        b->setScalarField("pendingLiteralMarkerEndBits", phiEndBits);
657        b->setScalarField("pendingLiteralMarkerCarryBit", phiCarryBit);
658        b->setScalarField("pendingLiteralMarkerFullBits", phiFullBits);
659
660    }
661}
Note: See TracBrowser for help on using the repository browser.