source: icGREP/icgrep-devel/icgrep/kernels/lz4/lz4_swizzled_aio.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: 53.3 KB
Line 
1
2#include "lz4_swizzled_aio.h"
3
4
5
6#include <kernels/kernel_builder.h>
7#include <iostream>
8#include <string>
9#include <llvm/Support/raw_ostream.h>
10#include <kernels/streamset.h>
11
12#define PHINotChange(b, phi) phi->addIncoming(phi, b->GetInsertBlock())
13
14using namespace llvm;
15using namespace kernel;
16using namespace std;
17
18
19namespace kernel{
20
21    LZ4SwizzledAioKernel::LZ4SwizzledAioKernel(const std::unique_ptr<kernel::KernelBuilder> &b, unsigned streamCount, unsigned streamSize, unsigned swizzleFactor)
22            :SegmentOrientedKernel("LZ4SwizzledAioKernel",
23            // Inputs
24                                   {
25                                           Binding{b->getStreamSetTy(1, 8), "byteStream", BoundedRate(0, 1)},
26                                           Binding{b->getStreamSetTy(1, 1), "extender", RateEqualTo("byteStream")},
27
28                                           // block data
29                                           Binding{b->getStreamSetTy(1, 1), "isCompressed", BoundedRate(0, 1), AlwaysConsume()},
30                                           Binding{b->getStreamSetTy(1, 64), "blockStart", RateEqualTo("isCompressed"), AlwaysConsume()},
31                                           Binding{b->getStreamSetTy(1, 64), "blockEnd", RateEqualTo("isCompressed"), AlwaysConsume()}
32
33                                   },
34            //Outputs
35                                   {
36//                                           Binding{b->getStreamSetTy(1, 8), "outputStream", BoundedRate(0, 1)},
37                                   },
38            //Arguments
39                                   {
40                                           Binding{b->getSizeTy(), "fileSize"}
41                                   },
42                                   {},
43            //Internal states:
44                                   {
45                                           Binding{b->getInt64Ty(), "tempTimes"},
46                                           Binding{b->getSizeTy(), "blockDataIndex"},
47                                           Binding{b->getInt64Ty(), "outputPos"},
48
49                                           // Temp array
50                                           Binding{ArrayType::get(b->getSizeTy(), 32), "literalStartArray"},
51                                           Binding{ArrayType::get(b->getSizeTy(), 32), "literalLengthArray"},
52                                           Binding{ArrayType::get(b->getSizeTy(), 32), "matchOffsetArray"},
53                                           Binding{ArrayType::get(b->getSizeTy(), 32), "matchLengthArray"},
54
55                                   }),
56             mStreamCount(streamCount),
57             mStreamSize(streamSize),
58             mSwizzleFactor(swizzleFactor),
59             mPDEPWidth(b->getBitBlockWidth() / mSwizzleFactor)
60    {
61//        assert((mPDEPWidth == 64 || mPDEPWidth == 32) && "PDEP width must be 32 or 64");
62
63        this->setStride(4 * 1024 * 1024);
64        addAttribute(MustExplicitlyTerminate());
65
66        mStreamSetInputs.push_back(Binding{b->getStreamSetTy(streamCount), "sourceStreamSet0", RateEqualTo("byteStream"), {Swizzled(), AlwaysConsume()}});
67        mStreamSetOutputs.push_back(Binding{b->getStreamSetTy(streamCount), "outputStreamSet0", BoundedRate(0, 1)});
68
69        for (unsigned i = 1; i < streamSize; i++) {
70            mStreamSetInputs.push_back(Binding{b->getStreamSetTy(streamCount), "sourceStreamSet" + std::to_string(i), RateEqualTo("sourceStreamSet0"), {Swizzled(), AlwaysConsume()}});
71            mStreamSetOutputs.push_back(Binding{b->getStreamSetTy(streamCount), "outputStreamSet" + std::to_string(i), RateEqualTo("outputStreamSet0")});
72        }
73
74    }
75
76    void LZ4SwizzledAioKernel::generateDoSegmentMethod(const std::unique_ptr<KernelBuilder> &b) {
77
78        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
79        BasicBlock* blockEndConBlock = b->CreateBasicBlock("blockEndConBlock");
80
81        Value * blockDataIndex = b->getScalarField("blockDataIndex");
82
83        // In MultiblockKernel, availableItemCount + processedItemCount == producedItemCount from previous kernel
84        // While in SegmentOrigentedKernel, availableItemCount == producedItemCount from previous kernel
85        Value * totalNumber = b->getAvailableItemCount("blockEnd");
86        Value * totalExtender = b->getAvailableItemCount("extender");
87        Value * totalSource = b->getAvailableItemCount("sourceStreamSet0");
88
89        Value * blockEnd = this->generateLoadInt64NumberInput(b, "blockEnd", blockDataIndex);
90
91//        b->CallPrintInt("blockEnd", blockEnd);
92//        b->CallPrintInt("processedSource", b->getProcessedItemCount("sourceStreamSet0"));
93//        b->CallPrintInt("totalSource", totalSource);
94//        b->CallPrintInt("fileSize", b->getScalarField("fileSize"));
95
96        b->CreateCondBr(b->CreateICmpULT(blockDataIndex, totalNumber), blockEndConBlock, exitBlock);
97
98        b->SetInsertPoint(blockEndConBlock);
99        Value * blockStart = this->generateLoadInt64NumberInput(b, "blockStart", blockDataIndex);
100        BasicBlock * processBlock = b->CreateBasicBlock("processBlock");
101        b->CreateCondBr(b->CreateICmpULE(blockEnd, b->CreateUMin(totalExtender, totalSource)), processBlock, exitBlock);
102
103        b->SetInsertPoint(processBlock);
104
105        //TODO handle uncompressed block
106        this->generateProcessCompressedBlock(b, blockStart, blockEnd);
107
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->setProducedItemCount("outputStreamSet0", b->getScalarField("outputPos"));
114
115        b->CreateBr(exitBlock);
116
117        b->SetInsertPoint(exitBlock);
118        b->CallPrintIntCond("time", b->getScalarField("tempTimes"), b->getTerminationSignal());
119    }
120
121    llvm::Value *LZ4SwizzledAioKernel::generateLoadInt64NumberInput(const std::unique_ptr<KernelBuilder> &iBuilder,
122                                                                      std::string inputBufferName, llvm::Value *globalOffset) {
123        Value * capacity = iBuilder->getCapacity(inputBufferName);
124        Value * processed = iBuilder->getProcessedItemCount(inputBufferName);
125        processed = iBuilder->CreateAnd(processed, iBuilder->CreateNeg(capacity));
126        Value * offset = iBuilder->CreateSub(globalOffset, processed);
127        Value * valuePtr = iBuilder->getRawInputPointer(inputBufferName, offset);
128        return iBuilder->CreateLoad(valuePtr);
129    }
130
131    void
132    LZ4SwizzledAioKernel::generateProcessCompressedBlock(const std::unique_ptr<KernelBuilder> &b, llvm::Value *lz4BlockStart,
133                                                           llvm::Value *lz4BlockEnd) {
134        BasicBlock* entryBlock = b->GetInsertBlock();
135
136        Value* isTerminal = b->CreateICmpEQ(lz4BlockEnd, b->getScalarField("fileSize"));
137        b->setTerminationSignal(isTerminal);
138
139        BasicBlock* exitBlock = b->CreateBasicBlock("processCompressedExitBlock");
140
141        BasicBlock* processCon = b->CreateBasicBlock("processCompressedConBlock");
142        BasicBlock* processBody = b->CreateBasicBlock("processCompressedBodyBlock");
143
144        BasicBlock* beforeProcessConBlock = b->GetInsertBlock();
145        b->CreateBr(processCon);
146        b->SetInsertPoint(processCon);
147
148
149        PHINode* phiCursorValue = b->CreatePHI(b->getInt64Ty(), 2, "phiCursorValue"); // phiCursorValue should always be the position of next token except for the final sequence
150        phiCursorValue->addIncoming(lz4BlockStart, beforeProcessConBlock);
151
152        b->CreateCondBr(b->CreateICmpULT(phiCursorValue, lz4BlockEnd), processBody, exitBlock);
153
154        b->SetInsertPoint(processBody);
155
156/*
157        auto accelerationRet = this->generateAcceleration(b, phiCursorValue, lz4BlockEnd);
158
159        Value* tokenMarkers = accelerationRet.first.first;
160
161        Value* cursorBlockPosBase = b->CreateSub(phiCursorValue, b->CreateURem(phiCursorValue, b->getSize(ACCELERATION_WIDTH)));
162        Value* nextTokenLocalPos = b->CreateSub(b->CreateSub(b->getSize(ACCELERATION_WIDTH), b->CreateCountReverseZeroes(tokenMarkers)), b->getSize(1));
163        Value* nextTokenGlobalPos = b->CreateAdd(cursorBlockPosBase, nextTokenLocalPos);
164
165        nextTokenGlobalPos = this->processBlockBoundary(b, nextTokenGlobalPos, lz4BlockEnd);
166*/
167        Value* nextTokenGlobalPos = this->processBlockBoundary(b, phiCursorValue, lz4BlockEnd);
168
169        phiCursorValue->addIncoming(nextTokenGlobalPos, b->GetInsertBlock());
170        b->CreateBr(processCon);
171
172        b->SetInsertPoint(exitBlock);
173    }
174
175    std::pair<std::pair<llvm::Value *, llvm::Value *>, llvm::Value *>
176    LZ4SwizzledAioKernel::generateAcceleration(const std::unique_ptr<KernelBuilder> &b, llvm::Value *beginTokenPos,
177                                                 llvm::Value *blockEnd) {
178
179        Value* time1 = b->CreateReadCycleCounter();
180        BasicBlock* entryBlock = b->GetInsertBlock();
181
182        BasicBlock* outputProducingBlock = b->CreateBasicBlock("outputProducingBlock");
183
184        // Constant
185        Value* SIZE_0 = b->getSize(0);
186        Value* SIZE_1 = b->getSize(1);
187        Value* SIZE_64 = b->getSize(64);
188        Value* SIZE_ACCELERATION_WIDTH = b->getSize(ACCELERATION_WIDTH);
189        Value* inputStreamSize = b->getCapacity("sourceStreamSet0");
190
191        Type* INT_ACCELERATION_TYPE = b->getIntNTy(ACCELERATION_WIDTH);
192        Type* BITBLOCK_PTR_TYPE = b->getBitBlockType()->getPointerTo();
193
194        Value* INT_ACCELERATION_0 = b->getIntN(ACCELERATION_WIDTH, 0);
195        Value* INT_ACCELERATION_1 = b->getIntN(ACCELERATION_WIDTH, 1);
196
197        Type* sizePtrTy = b->getSizeTy()->getPointerTo();
198
199        Value* literalStartArray = b->CreatePointerCast(b->getScalarFieldPtr("literalStartArray"), sizePtrTy);
200        Value* literalLengthArray = b->CreatePointerCast(b->getScalarFieldPtr("literalLengthArray"), sizePtrTy);
201        Value* matchOffsetArray = b->CreatePointerCast(b->getScalarFieldPtr("matchOffsetArray"), sizePtrTy);
202        Value* matchLengthArray = b->CreatePointerCast(b->getScalarFieldPtr("matchLengthArray"), sizePtrTy);
203
204        // ---- Entry Block
205
206        Value* literalBlockIndex = b->CreateUDiv(b->CreateURem(beginTokenPos, inputStreamSize), SIZE_64);
207        /*
208        std::vector<Value*> inputValuesVector = std::vector<Value*>();
209        for (unsigned i = 0; i < mStreamSize; i++) {
210            Value* sourceBasePtr = b->CreatePointerCast(b->getRawInputPointer("sourceStreamSet" + std::to_string(i), SIZE_0), BITBLOCK_PTR_TYPE);
211            Value* inputValue = b->CreateLoad(b->CreateGEP(sourceBasePtr, literalBlockIndex));
212            inputValuesVector.push_back(inputValue);
213        }
214        */
215
216        Value* maskedTokenPos = b->CreateURem(beginTokenPos, b->getCapacity("extender"));
217        Value* tokenPosRem = b->CreateURem(beginTokenPos, SIZE_ACCELERATION_WIDTH);
218        Value* blockPosBase = b->CreateSub(beginTokenPos, tokenPosRem);
219
220        Value* currentExtenderValue = b->CreateLoad(
221                b->CreateGEP(
222                        b->CreatePointerCast(b->getRawInputPointer("extender", SIZE_0), INT_ACCELERATION_TYPE->getPointerTo()),
223                        b->CreateUDiv(maskedTokenPos, SIZE_ACCELERATION_WIDTH)
224                )
225        );
226
227        Value* initTokenMarker = b->CreateShl(INT_ACCELERATION_1, tokenPosRem);
228        BasicBlock* accelerationProcessBlock = b->CreateBasicBlock("accelerationProcessBlock");
229        BasicBlock* accelerationExitBlock = b->CreateBasicBlock("accelerationExitBlock");
230        b->CreateBr(accelerationProcessBlock);
231
232        // ---- AccelerationProcessBlock
233        b->SetInsertPoint(accelerationProcessBlock);
234        PHINode* phiTokenMarkers = b->CreatePHI(INT_ACCELERATION_TYPE, 2);
235        phiTokenMarkers->addIncoming(initTokenMarker, entryBlock);
236        PHINode* phiLiteralMasks = b->CreatePHI(INT_ACCELERATION_TYPE, 2);
237        phiLiteralMasks->addIncoming(INT_ACCELERATION_0, entryBlock);
238        PHINode* phiMatchOffsetMarkers = b->CreatePHI(INT_ACCELERATION_TYPE, 2);
239        phiMatchOffsetMarkers->addIncoming(INT_ACCELERATION_0, entryBlock);
240        PHINode* phiOutputArrayPos = b->CreatePHI(b->getSizeTy(), 2);
241        phiOutputArrayPos->addIncoming(SIZE_0, entryBlock);
242
243
244        Value* tokenReverseZeros = b->CreateCountReverseZeroes(phiTokenMarkers);
245        Value* currentTokenLocalPos = b->CreateSub(b->CreateSub(SIZE_ACCELERATION_WIDTH, tokenReverseZeros), SIZE_1);
246        Value* currentTokenMarker = b->CreateShl(INT_ACCELERATION_1, currentTokenLocalPos); // 1 marker is in Token Pos
247        Value* currentTokenGlobalPos = b->CreateAdd(blockPosBase, currentTokenLocalPos);
248        Value* tokenValue = b->CreateLoad(b->getRawInputPointer("byteStream", currentTokenGlobalPos));
249
250        llvm::Value *literalLength, *literalLengthEndMarker;
251        std::tie(literalLength, literalLengthEndMarker) =
252                this->scanThruLiteralLength(b, currentTokenMarker, currentExtenderValue, tokenValue, blockPosBase,
253                                            currentTokenLocalPos);
254        Value* literalBeginMarker = b->CreateShl(literalLengthEndMarker, SIZE_1);
255        Value* literalStartLocalPos = b->CreateCountForwardZeroes(literalBeginMarker);
256        Value* literalStartGlobalPos = b->CreateAdd(blockPosBase, literalStartLocalPos);
257
258
259        Value* literalEndMarker = b->CreateSelect(b->CreateICmpULT(literalLength, SIZE_ACCELERATION_WIDTH), b->CreateShl(literalBeginMarker, literalLength), INT_ACCELERATION_0);
260
261        Value* newLiteralMask = b->CreateSub(literalEndMarker, literalBeginMarker);
262
263        Value* newMatchOffsetStartMarker = literalEndMarker;
264
265        Value *matchLength, *matchLengthEndMarker;
266        std::tie(matchLength, matchLengthEndMarker) =
267                this->scanThruMatchLength(b, b->CreateShl(newMatchOffsetStartMarker, SIZE_1), currentExtenderValue,
268                                          tokenValue, blockPosBase);
269        Value *newTokenMarker = b->CreateShl(matchLengthEndMarker, SIZE_1);
270        Value* newTokenMarkerLocalPos = b->CreateCountForwardZeroes(newTokenMarker);
271
272        Value* reachEnd = b->CreateOr(
273                b->CreateICmpEQ(newTokenMarker, b->getSize(0)),
274                b->CreateICmpUGE(b->CreateAdd(newTokenMarkerLocalPos, blockPosBase), blockEnd)
275        );
276
277        BasicBlock* dataProcessBlock = b->CreateBasicBlock("dataProcessBlock");
278        b->CreateUnlikelyCondBr(reachEnd, outputProducingBlock, dataProcessBlock);
279
280        // ---- dataProcessBlock
281        b->SetInsertPoint(dataProcessBlock);
282
283        Value* matchOffsetStartLocalPos = b->CreateCountForwardZeroes(newMatchOffsetStartMarker);
284        Value* matchOffsetStartGlobalPos = b->CreateAdd(matchOffsetStartLocalPos, blockPosBase);
285
286        Value* matchOffsetPtr = b->getRawInputPointer("byteStream", matchOffsetStartGlobalPos);
287        // For now, it is safe to cast matchOffset pointer into i16 since the input byte stream is always linear available
288        matchOffsetPtr = b->CreatePointerCast(matchOffsetPtr, b->getInt16Ty()->getPointerTo());
289        Value* matchOffset = b->CreateZExt(b->CreateLoad(matchOffsetPtr), b->getSizeTy());
290
291        b->CreateStore(literalStartGlobalPos, b->CreateGEP(literalStartArray, phiOutputArrayPos));
292        b->CreateStore(literalLength, b->CreateGEP(literalLengthArray, phiOutputArrayPos));
293        b->CreateStore(matchOffset, b->CreateGEP(matchOffsetArray, phiOutputArrayPos));
294        b->CreateStore(matchLength, b->CreateGEP(matchLengthArray, phiOutputArrayPos));
295
296//        this->handleAccelerationLiteralCopy(b, literalStartGlobalPos, literalLength, inputValuesVector);
297//        this->handleMatchCopy(b, matchOffset, matchLength);
298
299        phiTokenMarkers->addIncoming(b->CreateOr(phiTokenMarkers, newTokenMarker), b->GetInsertBlock());
300        phiLiteralMasks->addIncoming(b->CreateOr(phiLiteralMasks, newLiteralMask), b->GetInsertBlock());
301        phiMatchOffsetMarkers->addIncoming(b->CreateOr(phiMatchOffsetMarkers, newMatchOffsetStartMarker), b->GetInsertBlock());
302        phiOutputArrayPos->addIncoming(b->CreateAdd(phiOutputArrayPos, SIZE_1), b->GetInsertBlock());
303
304        b->CreateBr(accelerationProcessBlock);
305
306        // ---- outputProducingBlock
307
308        b->SetInsertPoint(outputProducingBlock);
309        Value* time2 = b->CreateReadCycleCounter();
310        b->setScalarField("tempTimes", b->CreateAdd(b->getScalarField("tempTimes"), b->CreateSub(time2, time1)));
311
312
313        this->handleAccelerationPdepOutput(
314                b,
315                literalBlockIndex,
316                phiLiteralMasks,
317                literalLengthArray,
318                matchOffsetArray,
319                matchLengthArray,
320                phiOutputArrayPos
321        );
322
323
324
325
326
327        this->handleAccelerationMatchCopyOutput(
328                b,
329                literalBlockIndex,
330                phiLiteralMasks,
331                literalLengthArray,
332                matchOffsetArray,
333                matchLengthArray,
334                phiOutputArrayPos
335        );
336
337        b->CreateBr(accelerationExitBlock);
338
339        // ---- AccelerationExitBlock
340        b->SetInsertPoint(accelerationExitBlock);
341//        b->CallPrintInt("outputPos", b->getScalarField("outputPos"));
342        return std::make_pair(std::make_pair(phiTokenMarkers, phiLiteralMasks), phiMatchOffsetMarkers);
343    }
344
345    void LZ4SwizzledAioKernel::handleAccelerationMatchCopyOutput(
346            const std::unique_ptr<KernelBuilder> &b,
347            llvm::Value *literalBlockIndex,
348            llvm::Value *literalMasks,
349            llvm::Value *literalLengthArray,
350            llvm::Value *matchOffsetArray,
351            llvm::Value *matchLengthArray,
352            llvm::Value *numOfElements
353    ) {
354        // Constant
355        Value* SIZE_0 = b->getSize(0);
356        Value* SIZE_1 = b->getSize(1);
357
358        Value* initOutputPos = b->getScalarField("outputPos");
359
360        // ---- EntryBlock
361        BasicBlock* entryBlock = b->GetInsertBlock();
362
363        BasicBlock* matchCopyConBlock = b->CreateBasicBlock("matchCopyConBlock");
364        BasicBlock* matchCopyBodyBlock = b->CreateBasicBlock("matchCopyBodyBlock");
365        BasicBlock* matchCopyExitBlock = b->CreateBasicBlock("matchCopyExitBlock");
366
367
368        b->CreateBr(matchCopyConBlock);
369
370        // ---- matchCopyConBlock
371        b->SetInsertPoint(matchCopyConBlock);
372
373        PHINode* phiMatchCopyDataIndex = b->CreatePHI(b->getSizeTy(), 2);
374        phiMatchCopyDataIndex->addIncoming(SIZE_0, entryBlock);
375        PHINode* phiMatchCopyOutputPos = b->CreatePHI(b->getSizeTy(), 2);
376        phiMatchCopyOutputPos->addIncoming(initOutputPos, entryBlock);
377
378        b->CreateCondBr(b->CreateICmpULT(phiMatchCopyDataIndex, numOfElements), matchCopyBodyBlock, matchCopyExitBlock);
379
380        // ---- matchCopyBodyBlock
381        b->SetInsertPoint(matchCopyBodyBlock);
382
383        Value* currentLiteralLength = b->CreateLoad(b->CreateGEP(literalLengthArray, phiMatchCopyDataIndex));
384        Value* currentMatchOffset = b->CreateLoad(b->CreateGEP(matchOffsetArray, phiMatchCopyDataIndex));
385        Value* currentMatchLength = b->CreateLoad(b->CreateGEP(matchLengthArray, phiMatchCopyDataIndex));
386        Value* matchPos = b->CreateAdd(phiMatchCopyOutputPos, currentLiteralLength);
387        this->handleMatchCopy(b, matchPos, currentMatchOffset, currentMatchLength, false);
388
389        phiMatchCopyDataIndex->addIncoming(b->CreateAdd(phiMatchCopyDataIndex, SIZE_1), b->GetInsertBlock());
390        phiMatchCopyOutputPos->addIncoming(b->CreateAdd(matchPos, currentMatchLength), b->GetInsertBlock());
391
392        b->CreateBr(matchCopyConBlock);
393
394        // ---- matchCopyExitBlock
395        b->SetInsertPoint(matchCopyExitBlock);
396        b->setScalarField("outputPos", phiMatchCopyOutputPos);
397
398    }
399
400    void LZ4SwizzledAioKernel::handleAccelerationPdepOutput(
401            const std::unique_ptr<KernelBuilder> &b,
402            Value *literalBlockIndex,
403            Value *literalMasks,
404            Value *literalLengthArray,
405            Value *matchOffsetArray,
406            Value *matchLengthArray,
407            Value *numOfElements
408    ) {
409        // Constant
410        Value* SIZE_0 = b->getSize(0);
411//        b->CallPrintInt("-------", SIZE_0);
412        Value* SIZE_1 = b->getSize(1);
413        Value* SIZE_64 = b->getSize(64);
414        Type* BITBLOCK_PTR_TYPE = b->getBitBlockType()->getPointerTo();
415        Value* SIZE_OUTPUT_BLOCKS_COUNT = b->CreateUDiv(b->getCapacity("outputStreamSet0"), SIZE_64);
416
417        // ---- EntryBlock
418        BasicBlock* entryBlock = b->GetInsertBlock();
419
420        std::vector<Value*> initExtractedLiteral = std::vector<Value*>();
421        for (unsigned i = 0; i < mStreamSize; i++) {
422            Value* sourceBasePtr = b->CreatePointerCast(b->getRawInputPointer("sourceStreamSet" + std::to_string(i), SIZE_0), BITBLOCK_PTR_TYPE);
423            Value* inputValue = b->CreateLoad(b->CreateGEP(sourceBasePtr, literalBlockIndex));
424            Value* extractedInputValue = b->simd_pext(64, inputValue, b->simd_fill(64, literalMasks));
425            initExtractedLiteral.push_back(extractedInputValue);
426        }
427        Value* initOutputPos = b->getScalarField("outputPos");
428        Value* initOutputBlockIndex = b->CreateUDiv(initOutputPos, SIZE_64);
429        Value* initOutputPosRem = b->CreateURem(initOutputPos, SIZE_64);
430        Value* initOutputPosMask = b->CreateSub(b->CreateShl(SIZE_1, initOutputPosRem), SIZE_1);
431        std::vector<Value*> initOutputValues = std::vector<Value*>();
432        for (unsigned i = 0; i < mStreamSize; i++) {
433            Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStreamSet" + std::to_string(i), SIZE_0), BITBLOCK_PTR_TYPE);
434            Value* outputValue = b->CreateLoad(b->CreateGEP(outputBasePtr, b->CreateURem(initOutputBlockIndex, SIZE_OUTPUT_BLOCKS_COUNT)));
435            initOutputValues.push_back(b->CreateAnd(outputValue, b->simd_fill(64, initOutputPosMask)));
436        }
437
438        // PDEP part will be responsible for clearing the output space
439
440        BasicBlock* pdepConBlock = b->CreateBasicBlock("pdepConBlock");
441        BasicBlock* pdepStoreOutputBlock = b->CreateBasicBlock("pdepStoreOutputBlock");
442        BasicBlock* pdepCheckAvailableDataBlock = b->CreateBasicBlock("pdepCheckAvailableDataBlock");
443        BasicBlock* pdepBuildMarkerBlock = b->CreateBasicBlock("pdepBuildMarkerBlock");
444        BasicBlock* pdepBuildMarkerReachNextBlock = b->CreateBasicBlock("pdepBuildMarkerReachNextBlock");
445        BasicBlock* pdepBuildMarkerNotReachNextBlock = b->CreateBasicBlock("pdepBuildMarkerNotReachNextBlock");
446        BasicBlock* pdepExitBlock = b->CreateBasicBlock("pdepExitBlock");
447
448        b->CreateBr(pdepConBlock);
449
450        // ---- pdepConBlock
451        b->SetInsertPoint(pdepConBlock);
452        std::vector<PHINode*> remainingExtractedLiteral = std::vector<PHINode*>();
453        for (unsigned i = 0; i < mStreamSize; i++) {
454            Value* initValue = initExtractedLiteral[i];
455            PHINode* n = b->CreatePHI(initValue->getType(), 4);
456            n->addIncoming(initValue, entryBlock);
457            remainingExtractedLiteral.push_back(n);
458        }
459        PHINode* phiPdepDataIndex = b->CreatePHI(b->getSizeTy(), 4);
460        phiPdepDataIndex->addIncoming(SIZE_0, entryBlock);
461        PHINode* phiPdepOutputPos = b->CreatePHI(b->getSizeTy(), 4);
462        phiPdepOutputPos->addIncoming(initOutputPos, entryBlock);
463        PHINode* phiCurrentOutputBlockIndex = b->CreatePHI(b->getSizeTy(), 4);
464        phiCurrentOutputBlockIndex->addIncoming(initOutputBlockIndex, entryBlock);
465        PHINode* phiPdepMarker = b->CreatePHI(b->getSizeTy(), 4);
466        phiPdepMarker->addIncoming(SIZE_0, entryBlock);
467        std::vector<PHINode*> phiOriginalOutputValues = std::vector<PHINode*>();
468        for (unsigned i = 0; i < mStreamSize; i++) {
469            Value* initOutputValue = initOutputValues[i];
470            PHINode* originalOutputValue = b->CreatePHI(initOutputValue->getType(), 4);
471            originalOutputValue->addIncoming(initOutputValue, entryBlock);
472            phiOriginalOutputValues.push_back(originalOutputValue);
473        }
474        PHINode* phiUseTemporaryLiteralLength = b->CreatePHI(b->getInt1Ty(), 4);
475        phiUseTemporaryLiteralLength->addIncoming(b->getInt1(false), entryBlock);
476        PHINode* phiTemporaryLiteralLength = b->CreatePHI(b->getSizeTy(), 4);
477        phiTemporaryLiteralLength->addIncoming(SIZE_0, entryBlock);
478
479
480        Value* pdepOutputPosBlockIndex = b->CreateUDiv(phiPdepOutputPos, SIZE_64);
481
482        b->CreateCondBr(b->CreateICmpEQ(pdepOutputPosBlockIndex, phiCurrentOutputBlockIndex), pdepCheckAvailableDataBlock, pdepStoreOutputBlock);
483
484        // ---- pdepStoreOutputBlock
485        b->SetInsertPoint(pdepStoreOutputBlock);
486        for (unsigned i = 0; i < mStreamSize; i++) {
487            Value* pdepResult = b->simd_pdep(64, remainingExtractedLiteral[i], b->simd_fill(64, phiPdepMarker));
488            Value* outputValue = b->CreateOr(pdepResult, phiOriginalOutputValues[i]);
489            Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStreamSet" + std::to_string(i), SIZE_0), BITBLOCK_PTR_TYPE);
490            b->CreateStore(outputValue, b->CreateGEP(outputBasePtr, b->CreateURem(phiCurrentOutputBlockIndex, SIZE_OUTPUT_BLOCKS_COUNT)));
491//            b->CallPrintRegister("pdepOutputValue" + std::to_string(i), outputValue);
492        }
493        Value* pdepMarkerPopcount = b->CreatePopcount(phiPdepMarker);
494        for (unsigned i = 0; i < mStreamSize; i++) {
495            remainingExtractedLiteral[i]->addIncoming(b->simd_srlv(64, remainingExtractedLiteral[i], b->simd_fill(64, pdepMarkerPopcount)), b->GetInsertBlock());
496            phiOriginalOutputValues[i]->addIncoming(Constant::getNullValue(b->getBitBlockType()), b->GetInsertBlock());
497        }
498        PHINotChange(b, phiPdepDataIndex);
499        PHINotChange(b, phiPdepOutputPos);
500        PHINotChange(b, phiUseTemporaryLiteralLength);
501        PHINotChange(b, phiTemporaryLiteralLength);
502        phiCurrentOutputBlockIndex->addIncoming(b->CreateAdd(phiCurrentOutputBlockIndex, SIZE_1), b->GetInsertBlock());
503        phiPdepMarker->addIncoming(SIZE_0, b->GetInsertBlock());
504        b->CreateBr(pdepConBlock);
505
506        // ---- pdepCheckAvailableDataBlock
507        b->SetInsertPoint(pdepCheckAvailableDataBlock);
508        b->CreateCondBr(b->CreateICmpULT(phiPdepDataIndex, numOfElements), pdepBuildMarkerBlock, pdepExitBlock);
509
510        // ---- pdepBuildMarkerBlock
511        b->SetInsertPoint(pdepBuildMarkerBlock);
512        Value* currentLiteralLength =  b->CreateSelect(
513                phiUseTemporaryLiteralLength,
514                phiTemporaryLiteralLength,
515                b->CreateLoad(b->CreateGEP(literalLengthArray, phiPdepDataIndex))
516        );
517
518        Value* currentMatchLength = b->CreateLoad(b->CreateGEP(matchLengthArray, phiPdepDataIndex));
519//        b->CallPrintInt("phiPdepOutputPos", phiPdepOutputPos);
520//        b->CallPrintInt("currentLiteralLength", currentLiteralLength);
521//        b->CallPrintInt("phiPdepOutputPos", phiPdepOutputPos);
522
523
524        Value* pdepOutputPosRem = b->CreateURem(phiPdepOutputPos, SIZE_64);
525        Value* literalEndRem = b->CreateAdd(pdepOutputPosRem, currentLiteralLength);
526        Value* pdepOutputRemainingLength = b->CreateSub(SIZE_64, pdepOutputPosRem);
527        Value* newPdepMarker = b->CreateOr(
528                phiPdepMarker,
529                b->CreateSub(
530                        b->CreateSelect(b->CreateICmpUGE(literalEndRem, SIZE_64), SIZE_0, b->CreateShl(SIZE_1, literalEndRem)),
531                        b->CreateShl(SIZE_1, pdepOutputPosRem)
532                )
533        );
534
535        b->CreateCondBr(b->CreateICmpUGT(literalEndRem, SIZE_64), pdepBuildMarkerReachNextBlock, pdepBuildMarkerNotReachNextBlock);
536
537        // ---- pdepBuildMarkerReachNextBlock
538        b->SetInsertPoint(pdepBuildMarkerReachNextBlock);
539        Value* remainingLiteralLength = b->CreateSub(currentLiteralLength, pdepOutputRemainingLength);
540        for (unsigned i = 0; i < mStreamSize; i++) {
541            PHINotChange(b, remainingExtractedLiteral[i]);
542            PHINotChange(b, phiOriginalOutputValues[i]);
543        }
544        PHINotChange(b, phiPdepDataIndex);
545        PHINotChange(b, phiCurrentOutputBlockIndex);
546        phiTemporaryLiteralLength->addIncoming(remainingLiteralLength, b->GetInsertBlock());
547        phiUseTemporaryLiteralLength->addIncoming(b->getInt1(true), b->GetInsertBlock());
548        phiPdepMarker->addIncoming(newPdepMarker, b->GetInsertBlock());
549        phiPdepOutputPos->addIncoming(b->CreateAdd(phiPdepOutputPos, pdepOutputRemainingLength), b->GetInsertBlock());
550        b->CreateBr(pdepConBlock);
551
552        // ---- pdepBuildMarkerNotReachNextBlock
553        b->SetInsertPoint(pdepBuildMarkerNotReachNextBlock);
554        for (unsigned i = 0; i < mStreamSize; i++) {
555            PHINotChange(b, remainingExtractedLiteral[i]);
556            PHINotChange(b, phiOriginalOutputValues[i]);
557        }
558        phiPdepDataIndex->addIncoming(b->CreateAdd(phiPdepDataIndex, SIZE_1), b->GetInsertBlock());
559        phiPdepOutputPos->addIncoming(b->CreateAdd(phiPdepOutputPos, b->CreateAdd(currentLiteralLength, currentMatchLength)), b->GetInsertBlock());
560        phiPdepMarker->addIncoming(newPdepMarker, b->GetInsertBlock());
561        PHINotChange(b, phiCurrentOutputBlockIndex);
562        phiTemporaryLiteralLength->addIncoming(SIZE_0, b->GetInsertBlock());
563        phiUseTemporaryLiteralLength->addIncoming(b->getInt1(false), b->GetInsertBlock());
564
565        b->CreateBr(pdepConBlock);
566
567        // ---- pdepExitBlock
568        b->SetInsertPoint(pdepExitBlock);
569        for (unsigned i = 0; i < mStreamSize; i++) {
570            Value* pdepResult = b->simd_pdep(64, remainingExtractedLiteral[i], b->simd_fill(64, phiPdepMarker));
571            Value* outputValue = b->CreateOr(pdepResult, phiOriginalOutputValues[i]);
572            Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStreamSet" + std::to_string(i), SIZE_0), BITBLOCK_PTR_TYPE);
573            b->CreateStore(outputValue, b->CreateGEP(outputBasePtr, b->CreateURem(phiCurrentOutputBlockIndex, SIZE_OUTPUT_BLOCKS_COUNT)));
574            b->CreateStore(outputValue, b->CreateGEP(outputBasePtr, b->CreateURem(phiCurrentOutputBlockIndex, SIZE_OUTPUT_BLOCKS_COUNT)));
575//            b->CallPrintRegister("pdepOutputValue" + std::to_string(i), outputValue);
576        }
577    }
578
579    llvm::Value *LZ4SwizzledAioKernel::processBlockBoundary(const std::unique_ptr<KernelBuilder> &b, llvm::Value *beginTokenPos,
580                                                              llvm::Value *lz4BlockEnd) {
581// Constant
582        ConstantInt* SIZE_0 = b->getSize(0);
583        ConstantInt* SIZE_1 = b->getSize(1);
584        ConstantInt* BYTE_FF = b->getInt8(0xff);
585        Value* BYTE_F0 = b->getInt8(0xf0);
586        Value* BYTE_0F = b->getInt8(0x0f);
587
588        // ---- EntryBlock
589        BasicBlock* entryBlock = b->GetInsertBlock();
590        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
591
592        Value* bytePtrBase = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
593
594        Value* tokenValue = b->CreateLoad(b->CreateGEP(bytePtrBase, beginTokenPos));
595
596        Value* shouldExtendLiteral = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_F0), BYTE_F0);
597
598        Value* shouldExtendMatch = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_0F), BYTE_0F);
599
600        BasicBlock* extendLiteralCond = b->CreateBasicBlock("extendLiteralCond");
601        BasicBlock* extendLiteralEnd = b->CreateBasicBlock("extendLiteralEnd");
602
603        Value* initExtendLiteralPos = b->CreateAdd(beginTokenPos, b->getSize(1));
604
605        b->CreateCondBr(shouldExtendLiteral, extendLiteralCond, extendLiteralEnd);
606
607        // ---- extendLiteralCond
608        b->SetInsertPoint(extendLiteralCond);
609        PHINode* phiCurrentExtendLiteralPos = b->CreatePHI(b->getSizeTy(), 2);
610        phiCurrentExtendLiteralPos->addIncoming(initExtendLiteralPos, entryBlock);
611        PHINode* phiExtendLiteralLength = b->CreatePHI(b->getSizeTy(), 2);
612        phiExtendLiteralLength->addIncoming(SIZE_0, entryBlock);
613
614        Value* currentLiteralLengthByte = b->CreateLoad(b->CreateGEP(bytePtrBase, phiCurrentExtendLiteralPos));
615        Value* newExtendLiteralLength = b->CreateAdd(phiExtendLiteralLength, b->CreateZExt(currentLiteralLengthByte, b->getSizeTy()));
616
617        phiCurrentExtendLiteralPos->addIncoming(b->CreateAdd(phiCurrentExtendLiteralPos, SIZE_1), b->GetInsertBlock());
618        phiExtendLiteralLength->addIncoming(newExtendLiteralLength, b->GetInsertBlock());
619
620        b->CreateCondBr(b->CreateICmpEQ(currentLiteralLengthByte, BYTE_FF), extendLiteralCond, extendLiteralEnd);
621
622        // ---- extendLiteralEnd
623        b->SetInsertPoint(extendLiteralEnd);
624        PHINode* literalExtendValue = b->CreatePHI(b->getSizeTy(), 2);
625        literalExtendValue->addIncoming(SIZE_0, entryBlock);
626        literalExtendValue->addIncoming(newExtendLiteralLength, extendLiteralCond);
627        PHINode* phiExtendLiteralEndPos = b->CreatePHI(b->getSizeTy(), 2);
628        phiExtendLiteralEndPos->addIncoming(beginTokenPos, entryBlock);
629        phiExtendLiteralEndPos->addIncoming(phiCurrentExtendLiteralPos, extendLiteralCond);
630
631        Value* literalLength = b->CreateAdd(literalExtendValue, b->CreateZExt(b->CreateLShr(tokenValue, b->getInt8(4)), b->getSizeTy()));
632
633        Value* literalStartPos = b->CreateAdd(phiExtendLiteralEndPos, SIZE_1);
634        Value* literalEndPos = b->CreateAdd(literalStartPos, literalLength);
635
636        Value* matchOffsetBeginPos = literalEndPos;
637        Value* matchOffsetNextPos = b->CreateAdd(matchOffsetBeginPos, SIZE_1);
638
639        BasicBlock* hasMatchPartBlock = b->CreateBasicBlock("hasMatchPartBlock");
640        BasicBlock* extendMatchCon = b->CreateBasicBlock("extendMatchCon");
641        BasicBlock* extendMatchExit = b->CreateBasicBlock("extendMatchExit");
642
643        // This literal copy will always cross 64 bits literal boundary
644        this->handleLiteralCopy(b, literalStartPos, literalLength);
645        BasicBlock* extendLiteralEndFinal = b->GetInsertBlock();
646
647        b->CreateLikelyCondBr(b->CreateICmpULT(matchOffsetBeginPos, lz4BlockEnd), hasMatchPartBlock, exitBlock);
648
649        // ---- hasMatchPartBlock
650        b->SetInsertPoint(hasMatchPartBlock);
651        Value* initExtendMatchPos = b->CreateAdd(matchOffsetBeginPos, b->getSize(2));
652        b->CreateCondBr(shouldExtendMatch, extendMatchCon, extendMatchExit);
653
654        // ---- extendMatchCon
655        b->SetInsertPoint(extendMatchCon);
656        PHINode* phiCurrentExtendMatchPos = b->CreatePHI(b->getSizeTy(), 2);
657        phiCurrentExtendMatchPos->addIncoming(initExtendMatchPos, hasMatchPartBlock);
658        PHINode* phiExtendMatchLength = b->CreatePHI(b->getSizeTy(), 2);
659        phiExtendMatchLength->addIncoming(SIZE_0, hasMatchPartBlock);
660
661        Value* currentMatchLengthByte = b->CreateLoad(b->CreateGEP(bytePtrBase, phiCurrentExtendMatchPos));
662        Value* newExtendMatchLength = b->CreateAdd(phiExtendMatchLength, b->CreateZExt(currentMatchLengthByte, b->getSizeTy()));
663
664        phiCurrentExtendMatchPos->addIncoming(b->CreateAdd(phiCurrentExtendMatchPos, SIZE_1), b->GetInsertBlock());
665        phiExtendMatchLength->addIncoming(newExtendMatchLength, b->GetInsertBlock());
666
667        b->CreateCondBr(b->CreateICmpEQ(currentMatchLengthByte, BYTE_FF), extendMatchCon, extendMatchExit);
668
669        // ---- extendMatchExit
670        b->SetInsertPoint(extendMatchExit);
671        PHINode* matchExtendValue = b->CreatePHI(b->getSizeTy(), 2);
672        matchExtendValue->addIncoming(SIZE_0, hasMatchPartBlock);
673        matchExtendValue->addIncoming(newExtendMatchLength, extendMatchCon);
674        PHINode* phiExtendMatchEndPos = b->CreatePHI(b->getSizeTy(), 2);
675        phiExtendMatchEndPos->addIncoming(matchOffsetNextPos, hasMatchPartBlock);
676        phiExtendMatchEndPos->addIncoming(phiCurrentExtendMatchPos, extendMatchCon);
677
678        // matchLength = (size_t)token & 0xf + 4 + matchExtendValue
679        Value* matchLength = b->CreateAdd(
680                b->CreateAdd(matchExtendValue, b->getSize(4)),
681                b->CreateZExt(b->CreateAnd(tokenValue, BYTE_0F), b->getSizeTy())
682        );
683
684        Value* matchOffsetPtr = b->getRawInputPointer("byteStream", matchOffsetBeginPos);
685        // For now, it is safe to cast matchOffset pointer into i16 since the input byte stream is always linear available
686        matchOffsetPtr = b->CreatePointerCast(matchOffsetPtr, b->getInt16Ty()->getPointerTo());
687        Value* matchOffset = b->CreateZExt(b->CreateLoad(matchOffsetPtr), b->getSizeTy());
688        this->handleMatchCopy(b, matchOffset, matchLength);
689        BasicBlock* extendMatchExitFinal = b->GetInsertBlock();
690        b->CreateBr(exitBlock);
691
692        // ---- exitBlock
693        b->SetInsertPoint(exitBlock);
694        PHINode* phiBeforeTokenPos = b->CreatePHI(b->getSizeTy(), 2);
695        phiBeforeTokenPos->addIncoming(matchOffsetNextPos, extendLiteralEndFinal);
696        phiBeforeTokenPos->addIncoming(phiExtendMatchEndPos, extendMatchExitFinal);
697        Value* nextTokenPos = b->CreateAdd(phiBeforeTokenPos, SIZE_1);
698
699
700
701        return nextTokenPos;
702    }
703
704    std::pair<llvm::Value *, llvm::Value *>
705    LZ4SwizzledAioKernel::scanThruLiteralLength(const std::unique_ptr<KernelBuilder> &b, llvm::Value *currentTokenMarker,
706                                                  llvm::Value *currentExtenderValue, llvm::Value *tokenValue,
707                                                  llvm::Value *blockPosBase, llvm::Value *currentTokenLocalPos) {
708        Value* SIZE_1 = b->getSize(1);
709        Value* BYTE_F0 = b->getInt8(0xf0);
710        Value* shouldExtendLiteral = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_F0), BYTE_F0);
711
712        // Extend Literal Length
713        Value* literalScanThruResult = this->scanThru(b, b->CreateShl(currentTokenMarker, SIZE_1), currentExtenderValue);
714        Value* literalScanThruLocalPos = b->CreateCountForwardZeroes(literalScanThruResult);
715        Value* literalScanThruGlobalPos = b->CreateAdd(literalScanThruLocalPos, blockPosBase);
716        Value* literalScanThruLastBit = b->CreateLoad(b->getRawInputPointer("byteStream", literalScanThruGlobalPos));
717        // literalExtendResult = 255 * (literalScanThruLocalPos - currentTokenLocalPos - 1) + (size_t)literalScanThruLastBit
718        Value* literalExtendResult = b->CreateAdd(
719                b->CreateMul(
720                        b->getSize(255),
721                        b->CreateSub(
722                                b->CreateSub(literalScanThruLocalPos, currentTokenLocalPos),
723                                SIZE_1
724                        )
725                ),
726                b->CreateZExt(literalScanThruLastBit, b->getSizeTy())
727        );
728
729        // literalLength = (size_t)token >> 4 + shouldExtendLiteral ? literalExtendResult : 0
730        Value* literalLength = b->CreateAdd(
731                b->CreateLShr(
732                        b->CreateZExt(tokenValue, b->getSizeTy()),
733                        b->getSize(4)
734                ),
735                b->CreateSelect(
736                        shouldExtendLiteral,
737                        literalExtendResult,
738                        b->getSize(0)
739                )
740        );
741        Value* retLiteralMarker = b->CreateSelect(shouldExtendLiteral, literalScanThruResult, currentTokenMarker);
742
743        return std::make_pair(literalLength, retLiteralMarker);
744    }
745
746    std::pair<llvm::Value *, llvm::Value *>
747    LZ4SwizzledAioKernel::scanThruMatchLength(const std::unique_ptr<KernelBuilder> &b, llvm::Value *matchOffsetEndMarker,
748                                                llvm::Value *currentExtenderValue, llvm::Value *tokenValue,
749                                                llvm::Value *blockPosBase) {
750        Value* SIZE_1 = b->getSize(1);
751        Value* BYTE_0F = b->getInt8(0x0f);
752        Value* shouldExtendMatch = b->CreateICmpEQ(b->CreateAnd(tokenValue, BYTE_0F), BYTE_0F);
753
754        // Extend Match Length
755        Value* matchScanThruResult = this->scanThru(b, b->CreateShl(matchOffsetEndMarker, SIZE_1), currentExtenderValue);
756        Value* matchScanThruLocalPos = b->CreateCountForwardZeroes(matchScanThruResult);
757        Value* matchScanThruGlobalPos = b->CreateAdd(matchScanThruLocalPos, blockPosBase);
758        Value* matchScanThruLastBit = b->CreateLoad(b->getRawInputPointer("byteStream", matchScanThruGlobalPos));
759        Value* matchOffsetEndLocalPos = b->CreateCountForwardZeroes(matchOffsetEndMarker);
760
761        // matchExtendResult = 255 * (matchScanThruLocalPos - matchOffsetEndLocalPos - 1) + (size_t)matchScanThruLastBit
762        Value* matchExtendResult = b->CreateAdd(
763                b->CreateMul(
764                        b->getSize(255),
765                        b->CreateSub(
766                                b->CreateSub(matchScanThruLocalPos, matchOffsetEndLocalPos),
767                                SIZE_1
768                        )
769                ),
770                b->CreateZExt(matchScanThruLastBit, b->getSizeTy())
771        );
772
773        // matchLength = (size_t)token & 0x0f + 4 + shouldExtendMatch ? matchExtendResult : 0
774        Value* matchLength = b->CreateAdd(
775                b->CreateAdd(
776                        b->CreateZExt(b->CreateAnd(tokenValue, BYTE_0F), b->getSizeTy()),
777                        b->getSize(4)
778                ),
779                b->CreateSelect(
780                        shouldExtendMatch,
781                        matchExtendResult,
782                        b->getSize(0)
783                )
784        );
785
786        Value* retMatchMarker = b->CreateSelect(shouldExtendMatch, matchScanThruResult, matchOffsetEndMarker);
787        return std::make_pair(matchLength, retMatchMarker);
788    }
789
790    llvm::Value *
791    LZ4SwizzledAioKernel::scanThru(const std::unique_ptr<KernelBuilder> &b, llvm::Value *from, llvm::Value *thru) {
792        return b->CreateAnd(
793                b->CreateAdd(from, thru),
794                b->CreateNot(thru)
795        );
796    }
797
798    void LZ4SwizzledAioKernel::handleAccelerationLiteralCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *literalStart,
799                                                 llvm::Value *literalLength, const std::vector<llvm::Value*>& inputLiteralValues) {
800        Value* SIZE_64  = b->getSize(64);
801        Value* SIZE_0 = b->getSize(0);
802        Value* SIZE_1 = b->getSize(1);
803
804
805        Value* inputStreamSize = b->getCapacity("sourceStreamSet0");
806        Value* outputStreamSize = b->getCapacity("outputStreamSet0");
807
808        Type* BITBLOCK_PTR_TYPE = b->getBitBlockType()->getPointerTo();
809
810
811        BasicBlock* entryBlock = b->GetInsertBlock();
812        Value* outputPos = b->getScalarField("outputPos");
813
814        BasicBlock* literalCopyConBlock = b->CreateBasicBlock("literalCopyConBlock");
815        BasicBlock* literalCopyBodyBlock = b->CreateBasicBlock("literalCopyBodyBlock");
816        BasicBlock* literalCopyExitBlock = b->CreateBasicBlock("literalCopyExitBlock");
817
818        vector<Value*> outputStreamBasePtrs; // <4 * i64>*
819        for (int i = 0; i < mStreamSize; i++) {
820            outputStreamBasePtrs.push_back(b->CreatePointerCast(b->getRawOutputPointer("outputStreamSet" + std::to_string(i), SIZE_0), BITBLOCK_PTR_TYPE));
821        }
822
823        b->CreateBr(literalCopyConBlock);
824
825        // ---- literalCopyConBlock
826        b->SetInsertPoint(literalCopyConBlock);
827
828        b->CreateCondBr(b->CreateICmpNE(literalLength, b->getSize(0)), literalCopyBodyBlock, literalCopyExitBlock);
829
830        // ---- literalCopyBodyBlock
831        b->SetInsertPoint(literalCopyBodyBlock);
832
833        Value* literalRem = b->CreateURem(literalStart, SIZE_64);
834        Value* literalBlockIndex = b->CreateUDiv(b->CreateURem(literalStart, inputStreamSize), SIZE_64);
835
836        Value* outputPosRem = b->CreateURem(outputPos, SIZE_64);
837        Value* remainingOutputPos = b->CreateSub(SIZE_64, outputPosRem);
838        Value* outputBlockIndex = b->CreateUDiv(b->CreateURem(outputPos, outputStreamSize), SIZE_64);
839
840        Value* copySize1 = b->CreateUMin(literalLength, remainingOutputPos);
841        Value* copySize2 = b->CreateSub(literalLength, copySize1);
842
843
844        Value* l1 = b->CreateSub(SIZE_64, b->CreateAdd(literalRem, copySize1));
845        Value* l1_1 = b->simd_fill(64, l1);
846        Value* r1_1 = b->simd_fill(64, b->CreateAdd(l1, literalRem));
847        Value* l1_2 = b->simd_fill(64, outputPosRem);
848        Value* clearMask1 = b->simd_fill(64, b->CreateSub(b->CreateShl(SIZE_1, outputPosRem), SIZE_1)); // It seems that we do not need to clear it every time
849
850        Value* literalRem2 = b->CreateAdd(literalRem, copySize1);
851        Value* l2 = b->CreateSub(SIZE_64, b->CreateAdd(literalRem2, copySize2));
852        Value* l2_1 = b->simd_fill(64, l2);
853        Value* r2_1 = b->simd_fill(64, b->CreateAdd(l2, literalRem2));
854        Value* l2_2 = b->simd_fill(64, SIZE_0);
855        Value* clearMask2 = b->simd_fill(64, b->CreateSub(b->CreateShl(SIZE_1, SIZE_0), SIZE_1));
856
857
858        for (int i = 0; i < mStreamSize; i++) {
859            Value* inputValue = inputLiteralValues[i];
860
861            Value* outputPtr1 = b->CreateGEP(outputStreamBasePtrs[i], outputBlockIndex);
862            Value* outputValue1 = b->CreateLoad(outputPtr1);
863            Value* inputValue1 = b->simd_sllv(64, inputValue, l1_1);
864            inputValue1 = b->simd_srlv(64, inputValue1, r1_1);
865            inputValue1 = b->simd_sllv(64, inputValue1, l1_2);
866            outputValue1 = b->CreateOr(b->CreateAnd(outputValue1, clearMask1), inputValue1);
867            b->CreateStore(outputValue1, outputPtr1);
868
869
870            // TODO test whether using branch for output2 will be better
871            Value* outputPtr2 = b->CreateGEP(outputPtr1, SIZE_1);
872            Value* outputValue2 = b->CreateLoad(outputPtr2);
873            Value* oldOutputValue2 = outputValue2;
874            Value* inputValue2 = b->simd_sllv(64, inputValue, l2_1);
875            inputValue2 = b->simd_srlv(64, inputValue2, r2_1);
876            inputValue2 = b->simd_sllv(64, inputValue2, l2_2);
877            outputValue2 = b->CreateOr(b->CreateAnd(outputValue2, clearMask2), inputValue2);
878            outputValue2 = b->CreateSelect(b->CreateICmpEQ(copySize2, SIZE_0), oldOutputValue2, outputValue2);
879            b->CreateStore(outputValue2, outputPtr2);
880        }
881
882        b->CreateBr(literalCopyExitBlock);
883
884        // ---- literalCopyExitBlock
885        b->SetInsertPoint(literalCopyExitBlock);
886        b->setScalarField("outputPos", b->CreateAdd(outputPos, literalLength));
887    }
888
889    void LZ4SwizzledAioKernel::handleLiteralCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *literalStart,
890                                                   llvm::Value *literalLength) {
891        Value* SIZE_64  = b->getSize(64);
892        Value* SIZE_0 = b->getSize(0);
893        Value* SIZE_1 = b->getSize(1);
894
895        Value* inputStreamSize = b->getCapacity("sourceStreamSet0");
896        Value* outputStreamSize = b->getCapacity("outputStreamSet0");
897
898        Type* BITBLOCK_PTR_TYPE = b->getBitBlockType()->getPointerTo();
899
900
901        BasicBlock* entryBlock = b->GetInsertBlock();
902        Value* outputPos = b->getScalarField("outputPos");
903
904        BasicBlock* literalCopyConBlock = b->CreateBasicBlock("literalCopyConBlock");
905        BasicBlock* literalCopyBodyBlock = b->CreateBasicBlock("literalCopyBodyBlock");
906        BasicBlock* literalCopyExitBlock = b->CreateBasicBlock("literalCopyExitBlock");
907
908        vector<Value*> sourceStreamBasePtrs, outputStreamBasePtrs; // <4 * i64>*
909        for (int i = 0; i < mStreamSize; i++) {
910            sourceStreamBasePtrs.push_back(b->CreatePointerCast(b->getRawInputPointer("sourceStreamSet" + std::to_string(i), SIZE_0), BITBLOCK_PTR_TYPE, "aa" + std::to_string(i)));
911            outputStreamBasePtrs.push_back(b->CreatePointerCast(b->getRawOutputPointer("outputStreamSet" + std::to_string(i), SIZE_0), BITBLOCK_PTR_TYPE));
912        }
913
914        b->CreateBr(literalCopyConBlock);
915
916        // ---- literalCopyConBlock
917        b->SetInsertPoint(literalCopyConBlock);
918        PHINode* phiLiteralStart = b->CreatePHI(b->getSizeTy(), 2);
919        phiLiteralStart->addIncoming(literalStart, entryBlock);
920        PHINode* phiLiteralLength = b->CreatePHI(b->getSizeTy(), 2);
921        phiLiteralLength->addIncoming(literalLength, entryBlock);
922        PHINode* phiOutputPos = b->CreatePHI(b->getSizeTy(), 2);
923        phiOutputPos->addIncoming(outputPos, entryBlock);
924
925        b->CreateCondBr(b->CreateICmpNE(phiLiteralLength, b->getSize(0)), literalCopyBodyBlock, literalCopyExitBlock);
926
927        // ---- literalCopyBodyBlock
928        b->SetInsertPoint(literalCopyBodyBlock);
929
930        Value* literalRem = b->CreateURem(phiLiteralStart, SIZE_64);
931        Value* literalBlockIndex = b->CreateUDiv(b->CreateURem(phiLiteralStart, inputStreamSize), SIZE_64);
932
933        Value* outputPosRem = b->CreateURem(phiOutputPos, SIZE_64);
934        Value* outputBlockIndex = b->CreateUDiv(b->CreateURem(phiOutputPos, outputStreamSize), SIZE_64);
935
936        Value* copySize = b->CreateSub(SIZE_64, b->CreateUMax(literalRem, outputPosRem));
937        copySize = b->CreateUMin(copySize, phiLiteralLength);
938
939        Value* l1 = b->CreateSub(SIZE_64, b->CreateAdd(literalRem, copySize));
940        Value* l1_ = b->simd_fill(64, l1);
941        Value* r1 = b->simd_fill(64, b->CreateAdd(l1, literalRem));
942        Value* l2 = b->simd_fill(64, outputPosRem);
943        Value* clearMask = b->simd_fill(64, b->CreateSub(b->CreateShl(SIZE_1, outputPosRem), SIZE_1));
944
945        for (int i = 0; i < mStreamSize; i++) {
946            Value* inputValue = b->CreateLoad(b->CreateGEP(sourceStreamBasePtrs[i], literalBlockIndex));
947            Value* outputValue = b->CreateLoad(b->CreateGEP(outputStreamBasePtrs[i], outputBlockIndex));
948
949            inputValue = b->simd_sllv(64, inputValue, l1_);
950            inputValue = b->simd_srlv(64, inputValue, r1);
951            inputValue = b->simd_sllv(64, inputValue, l2);
952            outputValue = b->CreateOr(b->CreateAnd(outputValue, clearMask), inputValue);
953            b->CreateStore(outputValue, b->CreateGEP(outputStreamBasePtrs[i], outputBlockIndex));
954        }
955
956        phiLiteralStart->addIncoming(b->CreateAdd(phiLiteralStart, copySize), b->GetInsertBlock());
957        phiLiteralLength->addIncoming(b->CreateSub(phiLiteralLength, copySize), b->GetInsertBlock());
958        phiOutputPos->addIncoming(b->CreateAdd(phiOutputPos, copySize), b->GetInsertBlock());
959        b->CreateBr(literalCopyConBlock);
960
961        // ---- literalCopyExitBlock
962        b->SetInsertPoint(literalCopyExitBlock);
963        b->setScalarField("outputPos", b->CreateAdd(outputPos, literalLength));
964    }
965
966    void LZ4SwizzledAioKernel::handleMatchCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value* outputPos, llvm::Value* matchOffset, llvm::Value* matchLength, bool clearBuffer) {
967        Value* SIZE_64  = b->getSize(64);
968        Value* SIZE_0 = b->getSize(0);
969        Value* SIZE_1 = b->getSize(1);
970
971        Value* outputStreamSize = b->getCapacity("outputStreamSet0");
972        Type* BITBLOCK_PTR_TYPE = b->getBitBlockType()->getPointerTo();
973
974        vector<Value*> outputStreamBasePtrs; // <4 * i64>*
975        for (int i = 0; i < mStreamSize; i++) {
976            outputStreamBasePtrs.push_back(b->CreatePointerCast(b->getRawOutputPointer("outputStreamSet" + std::to_string(i), SIZE_0), BITBLOCK_PTR_TYPE));
977        }
978
979        BasicBlock* entryBlock = b->GetInsertBlock();
980
981        BasicBlock* matchCopyCon = b->CreateBasicBlock("matchCopyCon");
982        BasicBlock* matchCopyBody = b->CreateBasicBlock("matchCopyBody");
983        BasicBlock* matchCopyExit = b->CreateBasicBlock("matchCopyExit");
984        b->CreateBr(matchCopyCon);
985
986        // ---- matchCopyCon
987        b->SetInsertPoint(matchCopyCon);
988        PHINode* phiMatchLength = b->CreatePHI(b->getSizeTy(), 2);
989        phiMatchLength->addIncoming(matchLength, entryBlock);
990        PHINode* phiOutputPos = b->CreatePHI(b->getSizeTy(), 2);
991        phiOutputPos->addIncoming(outputPos, entryBlock);
992
993        b->CreateCondBr(b->CreateICmpNE(phiMatchLength, b->getSize(0)), matchCopyBody, matchCopyExit);
994
995        // ---- matchCopyBody
996        b->SetInsertPoint(matchCopyBody);
997//        b->CallPrintInt("phiMatchLength", phiMatchLength);
998
999        Value* copyFromPos = b->CreateSub(phiOutputPos, matchOffset);
1000
1001        Value* outputFromPosBlockIndex = b->CreateUDiv(b->CreateURem(copyFromPos, outputStreamSize), SIZE_64);
1002        Value* outputFromPosRem = b->CreateURem(copyFromPos, SIZE_64);
1003
1004        Value* outputToPosBlockIndex = b->CreateUDiv(b->CreateURem(phiOutputPos, outputStreamSize), SIZE_64);
1005        Value* outputToPosRem = b->CreateURem(phiOutputPos, SIZE_64);
1006
1007        Value* copySize = b->CreateSub(SIZE_64, b->CreateUMax(outputFromPosRem, outputToPosRem));
1008        copySize = b->CreateUMin(copySize, matchOffset);
1009        copySize = b->CreateUMin(copySize, phiMatchLength);
1010
1011        for (int i = 0; i < mStreamSize; i++) {
1012            Value* inputValue = b->CreateLoad(b->CreateGEP(outputStreamBasePtrs[i], outputFromPosBlockIndex));
1013            Value* outputValue = b->CreateLoad(b->CreateGEP(outputStreamBasePtrs[i], outputToPosBlockIndex));
1014
1015            Value* l1 = b->CreateSub(SIZE_64, b->CreateAdd(outputFromPosRem, copySize));
1016            inputValue = b->simd_sllv(64, inputValue, b->simd_fill(64, l1));
1017            inputValue = b->simd_srlv(64, inputValue, b->simd_fill(64, b->CreateAdd(l1, outputFromPosRem)));
1018            inputValue = b->simd_sllv(64, inputValue, b->simd_fill(64,outputToPosRem));
1019
1020            if (clearBuffer) {
1021                Value* outputClearMask = b->simd_fill(64, b->CreateSub(b->CreateShl(SIZE_1, outputToPosRem), SIZE_1));
1022                outputValue = b->CreateAnd(outputValue, outputClearMask);
1023            }
1024
1025            outputValue = b->CreateOr(outputValue, inputValue);
1026
1027            b->CreateStore(outputValue, b->CreateGEP(outputStreamBasePtrs[i], outputToPosBlockIndex));
1028
1029        }
1030
1031
1032        phiMatchLength->addIncoming(b->CreateSub(phiMatchLength, copySize), b->GetInsertBlock());
1033        phiOutputPos->addIncoming(b->CreateAdd(phiOutputPos, copySize), b->GetInsertBlock());
1034        b->CreateBr(matchCopyCon);
1035
1036        // ---- matchCopyExit
1037        b->SetInsertPoint(matchCopyExit);
1038    }
1039
1040    void LZ4SwizzledAioKernel::handleMatchCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *matchOffset,
1041                                                 llvm::Value *matchLength) {
1042        Value* outputPos = b->getScalarField("outputPos");
1043        this->handleMatchCopy(b, outputPos, matchOffset, matchLength);
1044        b->setScalarField("outputPos", b->CreateAdd(outputPos, matchLength));
1045    }
1046
1047
1048}
Note: See TracBrowser for help on using the repository browser.