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

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

fix some warning in lz4 related kernels

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