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

Last change on this file since 6132 was 6132, checked in by xwa163, 8 months ago
  1. More experiment on lz4 grep
  2. Improve performance of lzparabix grep
File size: 30.4 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,
22                                               unsigned streamSize, unsigned swizzleFactor,
23                                               unsigned blockSize):
24    LZ4SequentialAioBaseKernel(b, "LZ4SwizzledAioKernel", blockSize),
25    mStreamCount(streamCount),
26    mStreamSize(streamSize),
27    mSwizzleFactor(swizzleFactor),
28    mPDEPWidth(b->getBitBlockWidth() / mSwizzleFactor)
29    {
30//        assert((mPDEPWidth == 64 || mPDEPWidth == 32) && "PDEP width must be 32 or 64");
31        mStreamSetInputs.push_back(Binding{b->getStreamSetTy(streamCount), "sourceStreamSet0", RateEqualTo("byteStream"), {Swizzled(), AlwaysConsume()}});
32        mStreamSetOutputs.push_back(Binding{b->getStreamSetTy(streamCount), "outputStreamSet0", BoundedRate(0, 1)});
33
34        for (unsigned i = 1; i < streamSize; i++) {
35            mStreamSetInputs.push_back(Binding{b->getStreamSetTy(streamCount), "sourceStreamSet" + std::to_string(i), RateEqualTo("sourceStreamSet0"), {Swizzled(), AlwaysConsume()}});
36            mStreamSetOutputs.push_back(Binding{b->getStreamSetTy(streamCount), "outputStreamSet" + std::to_string(i), RateEqualTo("outputStreamSet0")});
37        }
38
39        this->addScalar(b->getSizeTy(), "accelerationOutputIndex");
40        this->addScalar(ArrayType::get(b->getSizeTy(), 48), "literalStartArray");
41        this->addScalar(ArrayType::get(b->getSizeTy(), 48), "literalLengthArray");
42        this->addScalar(ArrayType::get(b->getSizeTy(), 48), "matchOffsetArray");
43        this->addScalar(ArrayType::get(b->getSizeTy(), 48), "matchLengthArray");
44    }
45
46    void LZ4SwizzledAioKernel::prepareAcceleration(const std::unique_ptr<KernelBuilder> &b, llvm::Value* beginTokenPos) {
47        b->setScalarField("accelerationOutputIndex", b->getSize(0));
48        /*
49        std::vector<Value*> inputValuesVector = std::vector<Value*>();
50        for (unsigned i = 0; i < mStreamSize; i++) {
51            Value* sourceBasePtr = b->CreatePointerCast(b->getRawInputPointer("sourceStreamSet" + std::to_string(i), SIZE_0), BITBLOCK_PTR_TYPE);
52            Value* inputValue = b->CreateLoad(b->CreateGEP(sourceBasePtr, literalBlockIndex));
53            inputValuesVector.push_back(inputValue);
54        }
55        */
56    }
57
58    void LZ4SwizzledAioKernel::doAccelerationLiteralCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *literalStart,
59                                           llvm::Value *literalLength, llvm::Value* blockStart) {
60//        this->handleAccelerationLiteralCopy(b, literalStart, literalLength, inputValuesVector);
61
62        Type* sizePtrTy = b->getSizeTy()->getPointerTo();
63        Value* outputIndex = b->getScalarField("accelerationOutputIndex");
64
65        Value* literalStartArray = b->CreatePointerCast(b->getScalarFieldPtr("literalStartArray"), sizePtrTy);
66        Value* literalLengthArray = b->CreatePointerCast(b->getScalarFieldPtr("literalLengthArray"), sizePtrTy);
67        b->CreateStore(literalStart, b->CreateGEP(literalStartArray, outputIndex));
68        b->CreateStore(literalLength, b->CreateGEP(literalLengthArray, outputIndex));
69
70        b->setScalarField("accelerationOutputIndex", b->CreateAdd(outputIndex, b->getSize(1)));
71    }
72
73    void LZ4SwizzledAioKernel::doAccelerationMatchCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *matchOffset,
74                                         llvm::Value *matchLength) {
75//        this->handleMatchCopy(b, matchOffset, matchLength);
76
77        Type* sizePtrTy = b->getSizeTy()->getPointerTo();
78        Value* outputIndex = b->getScalarField("accelerationOutputIndex");
79        Value* matchOffsetArray = b->CreatePointerCast(b->getScalarFieldPtr("matchOffsetArray"), sizePtrTy);
80        Value* matchLengthArray = b->CreatePointerCast(b->getScalarFieldPtr("matchLengthArray"), sizePtrTy);
81        b->CreateStore(matchOffset, b->CreateGEP(matchOffsetArray, outputIndex));
82        b->CreateStore(matchLength, b->CreateGEP(matchLengthArray, outputIndex));
83        b->setScalarField("accelerationOutputIndex", b->CreateAdd(outputIndex, b->getSize(1)));
84    }
85
86    void LZ4SwizzledAioKernel::finishAcceleration(const std::unique_ptr<KernelBuilder> &b, llvm::Value* beginTokenPos, llvm::Value* literalMask) {
87        Value* inputStreamSize = b->getCapacity("sourceStreamSet0");
88        Value* SIZE_64 = b->getSize(64);
89        Value* literalBlockIndex = b->CreateUDiv(b->CreateURem(beginTokenPos, inputStreamSize), SIZE_64);
90
91        Value* outputIndex = b->getScalarField("accelerationOutputIndex");
92        Type* sizePtrTy = b->getSizeTy()->getPointerTo();
93        Value* literalStartArray = b->CreatePointerCast(b->getScalarFieldPtr("literalStartArray"), sizePtrTy);
94        Value* literalLengthArray = b->CreatePointerCast(b->getScalarFieldPtr("literalLengthArray"), sizePtrTy);
95        Value* matchOffsetArray = b->CreatePointerCast(b->getScalarFieldPtr("matchOffsetArray"), sizePtrTy);
96        Value* matchLengthArray = b->CreatePointerCast(b->getScalarFieldPtr("matchLengthArray"), sizePtrTy);
97        this->handleAccelerationPdepOutput(
98                b,
99                literalBlockIndex,
100                literalMask,
101                literalLengthArray,
102                matchOffsetArray,
103                matchLengthArray,
104                outputIndex
105        );
106
107        this->handleAccelerationMatchCopyOutput(
108                b,
109                literalLengthArray,
110                matchOffsetArray,
111                matchLengthArray,
112                outputIndex
113        );
114    }
115
116    void LZ4SwizzledAioKernel::handleAccelerationMatchCopyOutput(
117            const std::unique_ptr<KernelBuilder> &b,
118            llvm::Value *literalLengthArray,
119            llvm::Value *matchOffsetArray,
120            llvm::Value *matchLengthArray,
121            llvm::Value *numOfElements
122    ) {
123        // Constant
124        Value* SIZE_0 = b->getSize(0);
125        Value* SIZE_1 = b->getSize(1);
126
127        Value* initOutputPos = b->getScalarField("outputPos");
128
129        // ---- EntryBlock
130        BasicBlock* entryBlock = b->GetInsertBlock();
131
132        BasicBlock* matchCopyConBlock = b->CreateBasicBlock("matchCopyConBlock");
133        BasicBlock* matchCopyBodyBlock = b->CreateBasicBlock("matchCopyBodyBlock");
134        BasicBlock* matchCopyExitBlock = b->CreateBasicBlock("matchCopyExitBlock");
135
136
137        b->CreateBr(matchCopyConBlock);
138
139        // ---- matchCopyConBlock
140        b->SetInsertPoint(matchCopyConBlock);
141
142        PHINode* phiMatchCopyDataIndex = b->CreatePHI(b->getSizeTy(), 2);
143        phiMatchCopyDataIndex->addIncoming(SIZE_0, entryBlock);
144        PHINode* phiMatchCopyOutputPos = b->CreatePHI(b->getSizeTy(), 2);
145        phiMatchCopyOutputPos->addIncoming(initOutputPos, entryBlock);
146
147//        b->CallPrintInt("phiMatchCopyDataIndex", phiMatchCopyDataIndex);
148        b->CreateCondBr(b->CreateICmpULT(phiMatchCopyDataIndex, numOfElements), matchCopyBodyBlock, matchCopyExitBlock);
149
150        // ---- matchCopyBodyBlock
151        b->SetInsertPoint(matchCopyBodyBlock);
152
153        Value* currentLiteralLength = b->CreateLoad(b->CreateGEP(literalLengthArray, phiMatchCopyDataIndex));
154        Value* currentMatchOffset = b->CreateLoad(b->CreateGEP(matchOffsetArray, phiMatchCopyDataIndex));
155        Value* currentMatchLength = b->CreateLoad(b->CreateGEP(matchLengthArray, phiMatchCopyDataIndex));
156        Value* matchPos = b->CreateAdd(phiMatchCopyOutputPos, currentLiteralLength);
157        this->handleMatchCopy(b, matchPos, currentMatchOffset, currentMatchLength, false);
158
159        phiMatchCopyDataIndex->addIncoming(b->CreateAdd(phiMatchCopyDataIndex, SIZE_1), b->GetInsertBlock());
160        phiMatchCopyOutputPos->addIncoming(b->CreateAdd(matchPos, currentMatchLength), b->GetInsertBlock());
161
162        b->CreateBr(matchCopyConBlock);
163
164        // ---- matchCopyExitBlock
165        b->SetInsertPoint(matchCopyExitBlock);
166        b->setScalarField("outputPos", phiMatchCopyOutputPos);
167
168    }
169
170    void LZ4SwizzledAioKernel::handleAccelerationPdepOutput(
171            const std::unique_ptr<KernelBuilder> &b,
172            Value *literalBlockIndex,
173            Value *literalMasks,
174            Value *literalLengthArray,
175            Value *matchOffsetArray,
176            Value *matchLengthArray,
177            Value *numOfElements
178    ) {
179        // Constant
180        Value* SIZE_0 = b->getSize(0);
181        Value* SIZE_1 = b->getSize(1);
182        Value* SIZE_64 = b->getSize(64);
183        Type* BITBLOCK_PTR_TYPE = b->getBitBlockType()->getPointerTo();
184        Value* SIZE_OUTPUT_BLOCKS_COUNT = b->CreateUDiv(b->getCapacity("outputStreamSet0"), SIZE_64);
185
186        // ---- EntryBlock
187        BasicBlock* entryBlock = b->GetInsertBlock();
188
189        std::vector<Value*> initExtractedLiteral = std::vector<Value*>();
190        for (unsigned i = 0; i < mStreamSize; i++) {
191            Value* sourceBasePtr = b->CreatePointerCast(b->getRawInputPointer("sourceStreamSet" + std::to_string(i), SIZE_0), BITBLOCK_PTR_TYPE);
192            Value* inputValue = b->CreateLoad(b->CreateGEP(sourceBasePtr, literalBlockIndex));
193            Value* extractedInputValue = b->simd_pext(64, inputValue, b->simd_fill(64, literalMasks));
194            initExtractedLiteral.push_back(extractedInputValue);
195        }
196        Value* initOutputPos = b->getScalarField("outputPos");
197        Value* initOutputBlockIndex = b->CreateUDiv(initOutputPos, SIZE_64);
198        Value* initOutputPosRem = b->CreateURem(initOutputPos, SIZE_64);
199        Value* initOutputPosMask = b->CreateSub(b->CreateShl(SIZE_1, initOutputPosRem), SIZE_1);
200        std::vector<Value*> initOutputValues = std::vector<Value*>();
201        for (unsigned i = 0; i < mStreamSize; i++) {
202            Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStreamSet" + std::to_string(i), SIZE_0), BITBLOCK_PTR_TYPE);
203            Value* outputValue = b->CreateLoad(b->CreateGEP(outputBasePtr, b->CreateURem(initOutputBlockIndex, SIZE_OUTPUT_BLOCKS_COUNT)));
204            initOutputValues.push_back(b->CreateAnd(outputValue, b->simd_fill(64, initOutputPosMask)));
205        }
206
207        // PDEP part will be responsible for clearing the output space
208
209        BasicBlock* pdepConBlock = b->CreateBasicBlock("pdepConBlock");
210        BasicBlock* pdepStoreOutputBlock = b->CreateBasicBlock("pdepStoreOutputBlock");
211        BasicBlock* pdepCheckAvailableDataBlock = b->CreateBasicBlock("pdepCheckAvailableDataBlock");
212        BasicBlock* pdepBuildMarkerBlock = b->CreateBasicBlock("pdepBuildMarkerBlock");
213        BasicBlock* pdepBuildMarkerReachNextBlock = b->CreateBasicBlock("pdepBuildMarkerReachNextBlock");
214        BasicBlock* pdepBuildMarkerNotReachNextBlock = b->CreateBasicBlock("pdepBuildMarkerNotReachNextBlock");
215        BasicBlock* pdepExitBlock = b->CreateBasicBlock("pdepExitBlock");
216
217        b->CreateBr(pdepConBlock);
218
219        // ---- pdepConBlock
220        b->SetInsertPoint(pdepConBlock);
221        std::vector<PHINode*> remainingExtractedLiteral = std::vector<PHINode*>();
222        for (unsigned i = 0; i < mStreamSize; i++) {
223            Value* initValue = initExtractedLiteral[i];
224            PHINode* n = b->CreatePHI(initValue->getType(), 4);
225            n->addIncoming(initValue, entryBlock);
226            remainingExtractedLiteral.push_back(n);
227        }
228        PHINode* phiPdepDataIndex = b->CreatePHI(b->getSizeTy(), 4);
229        phiPdepDataIndex->addIncoming(SIZE_0, entryBlock);
230        PHINode* phiPdepOutputPos = b->CreatePHI(b->getSizeTy(), 4);
231        phiPdepOutputPos->addIncoming(initOutputPos, entryBlock);
232        PHINode* phiCurrentOutputBlockIndex = b->CreatePHI(b->getSizeTy(), 4);
233        phiCurrentOutputBlockIndex->addIncoming(initOutputBlockIndex, entryBlock);
234        PHINode* phiPdepMarker = b->CreatePHI(b->getSizeTy(), 4);
235        phiPdepMarker->addIncoming(SIZE_0, entryBlock);
236        std::vector<PHINode*> phiOriginalOutputValues = std::vector<PHINode*>();
237        for (unsigned i = 0; i < mStreamSize; i++) {
238            Value* initOutputValue = initOutputValues[i];
239            PHINode* originalOutputValue = b->CreatePHI(initOutputValue->getType(), 4);
240            originalOutputValue->addIncoming(initOutputValue, entryBlock);
241            phiOriginalOutputValues.push_back(originalOutputValue);
242        }
243        PHINode* phiUseTemporaryLiteralLength = b->CreatePHI(b->getInt1Ty(), 4);
244        phiUseTemporaryLiteralLength->addIncoming(b->getInt1(false), entryBlock);
245        PHINode* phiTemporaryLiteralLength = b->CreatePHI(b->getSizeTy(), 4);
246        phiTemporaryLiteralLength->addIncoming(SIZE_0, entryBlock);
247
248
249        Value* pdepOutputPosBlockIndex = b->CreateUDiv(phiPdepOutputPos, SIZE_64);
250
251        b->CreateCondBr(b->CreateICmpEQ(pdepOutputPosBlockIndex, phiCurrentOutputBlockIndex), pdepCheckAvailableDataBlock, pdepStoreOutputBlock);
252
253        // ---- pdepStoreOutputBlock
254        b->SetInsertPoint(pdepStoreOutputBlock);
255        for (unsigned i = 0; i < mStreamSize; i++) {
256            Value* pdepResult = b->simd_pdep(64, remainingExtractedLiteral[i], b->simd_fill(64, phiPdepMarker));
257            Value* outputValue = b->CreateOr(pdepResult, phiOriginalOutputValues[i]);
258            Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStreamSet" + std::to_string(i), SIZE_0), BITBLOCK_PTR_TYPE);
259            b->CreateStore(outputValue, b->CreateGEP(outputBasePtr, b->CreateURem(phiCurrentOutputBlockIndex, SIZE_OUTPUT_BLOCKS_COUNT)));
260        }
261        Value* pdepMarkerPopcount = b->CreatePopcount(phiPdepMarker);
262        for (unsigned i = 0; i < mStreamSize; i++) {
263            remainingExtractedLiteral[i]->addIncoming(b->simd_srlv(64, remainingExtractedLiteral[i], b->simd_fill(64, pdepMarkerPopcount)), b->GetInsertBlock());
264            phiOriginalOutputValues[i]->addIncoming(Constant::getNullValue(b->getBitBlockType()), b->GetInsertBlock());
265        }
266        PHINotChange(b, phiPdepDataIndex);
267        PHINotChange(b, phiPdepOutputPos);
268        PHINotChange(b, phiUseTemporaryLiteralLength);
269        PHINotChange(b, phiTemporaryLiteralLength);
270        phiCurrentOutputBlockIndex->addIncoming(b->CreateAdd(phiCurrentOutputBlockIndex, SIZE_1), b->GetInsertBlock());
271        phiPdepMarker->addIncoming(SIZE_0, b->GetInsertBlock());
272        b->CreateBr(pdepConBlock);
273
274        // ---- pdepCheckAvailableDataBlock
275        b->SetInsertPoint(pdepCheckAvailableDataBlock);
276        b->CreateCondBr(b->CreateICmpULT(phiPdepDataIndex, numOfElements), pdepBuildMarkerBlock, pdepExitBlock);
277
278        // ---- pdepBuildMarkerBlock
279        b->SetInsertPoint(pdepBuildMarkerBlock);
280        Value* currentLiteralLength =  b->CreateSelect(
281                phiUseTemporaryLiteralLength,
282                phiTemporaryLiteralLength,
283                b->CreateLoad(b->CreateGEP(literalLengthArray, phiPdepDataIndex))
284        );
285
286        Value* currentMatchLength = b->CreateLoad(b->CreateGEP(matchLengthArray, phiPdepDataIndex));
287
288        Value* pdepOutputPosRem = b->CreateURem(phiPdepOutputPos, SIZE_64);
289        Value* literalEndRem = b->CreateAdd(pdepOutputPosRem, currentLiteralLength);
290        Value* pdepOutputRemainingLength = b->CreateSub(SIZE_64, pdepOutputPosRem);
291        Value* newPdepMarker = b->CreateOr(
292                phiPdepMarker,
293                b->CreateSub(
294                        b->CreateSelect(b->CreateICmpUGE(literalEndRem, SIZE_64), SIZE_0, b->CreateShl(SIZE_1, literalEndRem)),
295                        b->CreateShl(SIZE_1, pdepOutputPosRem)
296                )
297        );
298
299        b->CreateCondBr(b->CreateICmpUGT(literalEndRem, SIZE_64), pdepBuildMarkerReachNextBlock, pdepBuildMarkerNotReachNextBlock);
300
301        // ---- pdepBuildMarkerReachNextBlock
302        b->SetInsertPoint(pdepBuildMarkerReachNextBlock);
303        Value* remainingLiteralLength = b->CreateSub(currentLiteralLength, pdepOutputRemainingLength);
304        for (unsigned i = 0; i < mStreamSize; i++) {
305            PHINotChange(b, remainingExtractedLiteral[i]);
306            PHINotChange(b, phiOriginalOutputValues[i]);
307        }
308        PHINotChange(b, phiPdepDataIndex);
309        PHINotChange(b, phiCurrentOutputBlockIndex);
310        phiTemporaryLiteralLength->addIncoming(remainingLiteralLength, b->GetInsertBlock());
311        phiUseTemporaryLiteralLength->addIncoming(b->getInt1(true), b->GetInsertBlock());
312        phiPdepMarker->addIncoming(newPdepMarker, b->GetInsertBlock());
313        phiPdepOutputPos->addIncoming(b->CreateAdd(phiPdepOutputPos, pdepOutputRemainingLength), b->GetInsertBlock());
314        b->CreateBr(pdepConBlock);
315
316        // ---- pdepBuildMarkerNotReachNextBlock
317        b->SetInsertPoint(pdepBuildMarkerNotReachNextBlock);
318        for (unsigned i = 0; i < mStreamSize; i++) {
319            PHINotChange(b, remainingExtractedLiteral[i]);
320            PHINotChange(b, phiOriginalOutputValues[i]);
321        }
322        phiPdepDataIndex->addIncoming(b->CreateAdd(phiPdepDataIndex, SIZE_1), b->GetInsertBlock());
323        phiPdepOutputPos->addIncoming(b->CreateAdd(phiPdepOutputPos, b->CreateAdd(currentLiteralLength, currentMatchLength)), b->GetInsertBlock());
324        phiPdepMarker->addIncoming(newPdepMarker, b->GetInsertBlock());
325        PHINotChange(b, phiCurrentOutputBlockIndex);
326        phiTemporaryLiteralLength->addIncoming(SIZE_0, b->GetInsertBlock());
327        phiUseTemporaryLiteralLength->addIncoming(b->getInt1(false), b->GetInsertBlock());
328
329        b->CreateBr(pdepConBlock);
330
331        // ---- pdepExitBlock
332        b->SetInsertPoint(pdepExitBlock);
333        for (unsigned i = 0; i < mStreamSize; i++) {
334            Value* pdepResult = b->simd_pdep(64, remainingExtractedLiteral[i], b->simd_fill(64, phiPdepMarker));
335            Value* outputValue = b->CreateOr(pdepResult, phiOriginalOutputValues[i]);
336            Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStreamSet" + std::to_string(i), SIZE_0), BITBLOCK_PTR_TYPE);
337            b->CreateStore(outputValue, b->CreateGEP(outputBasePtr, b->CreateURem(phiCurrentOutputBlockIndex, SIZE_OUTPUT_BLOCKS_COUNT)));
338            b->CreateStore(outputValue, b->CreateGEP(outputBasePtr, b->CreateURem(phiCurrentOutputBlockIndex, SIZE_OUTPUT_BLOCKS_COUNT)));
339//            b->CallPrintRegister("pdepOutputValue" + std::to_string(i), outputValue);
340        }
341    }
342
343    void LZ4SwizzledAioKernel::handleAccelerationLiteralCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *literalStart,
344                                                 llvm::Value *literalLength, const std::vector<llvm::Value*>& inputLiteralValues) {
345        Value* SIZE_64  = b->getSize(64);
346        Value* SIZE_0 = b->getSize(0);
347        Value* SIZE_1 = b->getSize(1);
348
349//        Value* inputStreamSize = b->getCapacity("sourceStreamSet0");
350        Value* outputStreamSize = b->getCapacity("outputStreamSet0");
351
352        Type* BITBLOCK_PTR_TYPE = b->getBitBlockType()->getPointerTo();
353
354
355        Value* outputPos = b->getScalarField("outputPos");
356
357        BasicBlock* literalCopyConBlock = b->CreateBasicBlock("literalCopyConBlock");
358        BasicBlock* literalCopyBodyBlock = b->CreateBasicBlock("literalCopyBodyBlock");
359        BasicBlock* literalCopyExitBlock = b->CreateBasicBlock("literalCopyExitBlock");
360
361        vector<Value*> outputStreamBasePtrs; // <4 * i64>*
362        for (unsigned i = 0; i < mStreamSize; i++) {
363            outputStreamBasePtrs.push_back(b->CreatePointerCast(b->getRawOutputPointer("outputStreamSet" + std::to_string(i), SIZE_0), BITBLOCK_PTR_TYPE));
364        }
365
366        b->CreateBr(literalCopyConBlock);
367
368        // ---- literalCopyConBlock
369        b->SetInsertPoint(literalCopyConBlock);
370
371        b->CreateCondBr(b->CreateICmpNE(literalLength, b->getSize(0)), literalCopyBodyBlock, literalCopyExitBlock);
372
373        // ---- literalCopyBodyBlock
374        b->SetInsertPoint(literalCopyBodyBlock);
375
376        Value* literalRem = b->CreateURem(literalStart, SIZE_64);
377
378        Value* outputPosRem = b->CreateURem(outputPos, SIZE_64);
379        Value* remainingOutputPos = b->CreateSub(SIZE_64, outputPosRem);
380        Value* outputBlockIndex = b->CreateUDiv(b->CreateURem(outputPos, outputStreamSize), SIZE_64);
381
382        Value* copySize1 = b->CreateUMin(literalLength, remainingOutputPos);
383        Value* copySize2 = b->CreateSub(literalLength, copySize1);
384
385
386        Value* l1 = b->CreateSub(SIZE_64, b->CreateAdd(literalRem, copySize1));
387        Value* l1_1 = b->simd_fill(64, l1);
388        Value* r1_1 = b->simd_fill(64, b->CreateAdd(l1, literalRem));
389        Value* l1_2 = b->simd_fill(64, outputPosRem);
390        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
391
392        Value* literalRem2 = b->CreateAdd(literalRem, copySize1);
393        Value* l2 = b->CreateSub(SIZE_64, b->CreateAdd(literalRem2, copySize2));
394        Value* l2_1 = b->simd_fill(64, l2);
395        Value* r2_1 = b->simd_fill(64, b->CreateAdd(l2, literalRem2));
396        Value* l2_2 = b->simd_fill(64, SIZE_0);
397        Value* clearMask2 = b->simd_fill(64, b->CreateSub(b->CreateShl(SIZE_1, SIZE_0), SIZE_1));
398
399
400        for (unsigned i = 0; i < mStreamSize; i++) {
401            Value* inputValue = inputLiteralValues[i];
402
403            Value* outputPtr1 = b->CreateGEP(outputStreamBasePtrs[i], outputBlockIndex);
404            Value* outputValue1 = b->CreateLoad(outputPtr1);
405            Value* inputValue1 = b->simd_sllv(64, inputValue, l1_1);
406            inputValue1 = b->simd_srlv(64, inputValue1, r1_1);
407            inputValue1 = b->simd_sllv(64, inputValue1, l1_2);
408            outputValue1 = b->CreateOr(b->CreateAnd(outputValue1, clearMask1), inputValue1);
409            b->CreateStore(outputValue1, outputPtr1);
410
411            Value* outputPtr2 = b->CreateGEP(outputPtr1, SIZE_1);
412            Value* outputValue2 = b->CreateLoad(outputPtr2);
413            Value* oldOutputValue2 = outputValue2;
414            Value* inputValue2 = b->simd_sllv(64, inputValue, l2_1);
415            inputValue2 = b->simd_srlv(64, inputValue2, r2_1);
416            inputValue2 = b->simd_sllv(64, inputValue2, l2_2);
417            outputValue2 = b->CreateOr(b->CreateAnd(outputValue2, clearMask2), inputValue2);
418            outputValue2 = b->CreateSelect(b->CreateICmpEQ(copySize2, SIZE_0), oldOutputValue2, outputValue2);
419            b->CreateStore(outputValue2, outputPtr2);
420        }
421
422        b->CreateBr(literalCopyExitBlock);
423
424        // ---- literalCopyExitBlock
425        b->SetInsertPoint(literalCopyExitBlock);
426        b->setScalarField("outputPos", b->CreateAdd(outputPos, literalLength));
427    }
428
429    void LZ4SwizzledAioKernel::handleMatchCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value* outputPos, llvm::Value* matchOffset, llvm::Value* matchLength, bool clearBuffer) {
430        Value* SIZE_64  = b->getSize(64);
431        Value* SIZE_0 = b->getSize(0);
432        Value* SIZE_1 = b->getSize(1);
433
434        Value* outputStreamSize = b->getCapacity("outputStreamSet0");
435        Type* BITBLOCK_PTR_TYPE = b->getBitBlockType()->getPointerTo();
436
437        vector<Value*> outputStreamBasePtrs; // <4 * i64>*
438        for (unsigned i = 0; i < mStreamSize; i++) {
439            outputStreamBasePtrs.push_back(b->CreatePointerCast(b->getRawOutputPointer("outputStreamSet" + std::to_string(i), SIZE_0), BITBLOCK_PTR_TYPE));
440        }
441
442        BasicBlock* entryBlock = b->GetInsertBlock();
443
444        BasicBlock* matchCopyCon = b->CreateBasicBlock("matchCopyCon");
445        BasicBlock* matchCopyBody = b->CreateBasicBlock("matchCopyBody");
446        BasicBlock* matchCopyExit = b->CreateBasicBlock("matchCopyExit");
447        b->CreateBr(matchCopyCon);
448
449        // ---- matchCopyCon
450        b->SetInsertPoint(matchCopyCon);
451        PHINode* phiMatchLength = b->CreatePHI(b->getSizeTy(), 2);
452        phiMatchLength->addIncoming(matchLength, entryBlock);
453        PHINode* phiOutputPos = b->CreatePHI(b->getSizeTy(), 2);
454        phiOutputPos->addIncoming(outputPos, entryBlock);
455
456        b->CreateCondBr(b->CreateICmpNE(phiMatchLength, b->getSize(0)), matchCopyBody, matchCopyExit);
457
458        // ---- matchCopyBody
459        b->SetInsertPoint(matchCopyBody);
460//        b->CallPrintInt("phiMatchLength", phiMatchLength);
461
462        Value* copyFromPos = b->CreateSub(phiOutputPos, matchOffset);
463
464        Value* outputFromPosBlockIndex = b->CreateUDiv(b->CreateURem(copyFromPos, outputStreamSize), SIZE_64);
465        Value* outputFromPosRem = b->CreateURem(copyFromPos, SIZE_64);
466
467        Value* outputToPosBlockIndex = b->CreateUDiv(b->CreateURem(phiOutputPos, outputStreamSize), SIZE_64);
468        Value* outputToPosRem = b->CreateURem(phiOutputPos, SIZE_64);
469
470        Value* copySize = b->CreateSub(SIZE_64, b->CreateUMax(outputFromPosRem, outputToPosRem));
471        copySize = b->CreateUMin(copySize, matchOffset);
472        copySize = b->CreateUMin(copySize, phiMatchLength);
473
474        for (unsigned i = 0; i < mStreamSize; i++) {
475            Value* inputValue = b->CreateLoad(b->CreateGEP(outputStreamBasePtrs[i], outputFromPosBlockIndex));
476            Value* outputValue = b->CreateLoad(b->CreateGEP(outputStreamBasePtrs[i], outputToPosBlockIndex));
477
478            Value* l1 = b->CreateSub(SIZE_64, b->CreateAdd(outputFromPosRem, copySize));
479            inputValue = b->simd_sllv(64, inputValue, b->simd_fill(64, l1));
480            inputValue = b->simd_srlv(64, inputValue, b->simd_fill(64, b->CreateAdd(l1, outputFromPosRem)));
481            inputValue = b->simd_sllv(64, inputValue, b->simd_fill(64,outputToPosRem));
482
483            if (clearBuffer) {
484                Value* outputClearMask = b->simd_fill(64, b->CreateSub(b->CreateShl(SIZE_1, outputToPosRem), SIZE_1));
485                outputValue = b->CreateAnd(outputValue, outputClearMask);
486            }
487
488            outputValue = b->CreateOr(outputValue, inputValue);
489
490            b->CreateStore(outputValue, b->CreateGEP(outputStreamBasePtrs[i], outputToPosBlockIndex));
491
492        }
493
494        phiMatchLength->addIncoming(b->CreateSub(phiMatchLength, copySize), b->GetInsertBlock());
495        phiOutputPos->addIncoming(b->CreateAdd(phiOutputPos, copySize), b->GetInsertBlock());
496        b->CreateBr(matchCopyCon);
497
498        // ---- matchCopyExit
499        b->SetInsertPoint(matchCopyExit);
500    }
501
502    void LZ4SwizzledAioKernel::setProducedOutputItemCount(const std::unique_ptr<KernelBuilder> &b, llvm::Value* produced) {
503        b->setProducedItemCount("outputStreamSet0", produced);
504    }
505
506    void LZ4SwizzledAioKernel::doMatchCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *matchOffset,
507                             llvm::Value *matchLength) {
508        Value* outputPos = b->getScalarField("outputPos");
509        this->handleMatchCopy(b, outputPos, matchOffset, matchLength);
510        b->setScalarField("outputPos", b->CreateAdd(outputPos, matchLength));
511    }
512
513    void LZ4SwizzledAioKernel::doLiteralCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *literalStart,
514                                             llvm::Value *literalLength, llvm::Value* blockStart) {
515        Value* SIZE_64  = b->getSize(64);
516        Value* SIZE_0 = b->getSize(0);
517        Value* SIZE_1 = b->getSize(1);
518
519        Value* inputStreamSize = b->getCapacity("sourceStreamSet0");
520        Value* outputStreamSize = b->getCapacity("outputStreamSet0");
521
522        Type* BITBLOCK_PTR_TYPE = b->getBitBlockType()->getPointerTo();
523
524
525        BasicBlock* entryBlock = b->GetInsertBlock();
526        Value* outputPos = b->getScalarField("outputPos");
527
528        BasicBlock* literalCopyConBlock = b->CreateBasicBlock("literalCopyConBlock");
529        BasicBlock* literalCopyBodyBlock = b->CreateBasicBlock("literalCopyBodyBlock");
530        BasicBlock* literalCopyExitBlock = b->CreateBasicBlock("literalCopyExitBlock");
531
532        vector<Value*> sourceStreamBasePtrs, outputStreamBasePtrs; // <4 * i64>*
533        for (unsigned i = 0; i < mStreamSize; i++) {
534            sourceStreamBasePtrs.push_back(b->CreatePointerCast(b->getRawInputPointer("sourceStreamSet" + std::to_string(i), SIZE_0), BITBLOCK_PTR_TYPE, "aa" + std::to_string(i)));
535            outputStreamBasePtrs.push_back(b->CreatePointerCast(b->getRawOutputPointer("outputStreamSet" + std::to_string(i), SIZE_0), BITBLOCK_PTR_TYPE));
536        }
537
538        b->CreateBr(literalCopyConBlock);
539
540        // ---- literalCopyConBlock
541        b->SetInsertPoint(literalCopyConBlock);
542        PHINode* phiLiteralStart = b->CreatePHI(b->getSizeTy(), 2);
543        phiLiteralStart->addIncoming(literalStart, entryBlock);
544        PHINode* phiLiteralLength = b->CreatePHI(b->getSizeTy(), 2);
545        phiLiteralLength->addIncoming(literalLength, entryBlock);
546        PHINode* phiOutputPos = b->CreatePHI(b->getSizeTy(), 2);
547        phiOutputPos->addIncoming(outputPos, entryBlock);
548
549        b->CreateCondBr(b->CreateICmpNE(phiLiteralLength, b->getSize(0)), literalCopyBodyBlock, literalCopyExitBlock);
550
551        // ---- literalCopyBodyBlock
552        b->SetInsertPoint(literalCopyBodyBlock);
553
554        Value* literalRem = b->CreateURem(phiLiteralStart, SIZE_64);
555        Value* literalBlockIndex = b->CreateUDiv(b->CreateURem(phiLiteralStart, inputStreamSize), SIZE_64);
556
557        Value* outputPosRem = b->CreateURem(phiOutputPos, SIZE_64);
558        Value* outputBlockIndex = b->CreateUDiv(b->CreateURem(phiOutputPos, outputStreamSize), SIZE_64);
559
560        Value* copySize = b->CreateSub(SIZE_64, b->CreateUMax(literalRem, outputPosRem));
561        copySize = b->CreateUMin(copySize, phiLiteralLength);
562
563        Value* l1 = b->CreateSub(SIZE_64, b->CreateAdd(literalRem, copySize));
564        Value* l1_ = b->simd_fill(64, l1);
565        Value* r1 = b->simd_fill(64, b->CreateAdd(l1, literalRem));
566        Value* l2 = b->simd_fill(64, outputPosRem);
567        Value* clearMask = b->simd_fill(64, b->CreateSub(b->CreateShl(SIZE_1, outputPosRem), SIZE_1));
568
569        for (unsigned i = 0; i < mStreamSize; i++) {
570            Value* inputValue = b->CreateLoad(b->CreateGEP(sourceStreamBasePtrs[i], literalBlockIndex));
571            Value* outputValue = b->CreateLoad(b->CreateGEP(outputStreamBasePtrs[i], outputBlockIndex));
572
573            inputValue = b->simd_sllv(64, inputValue, l1_);
574            inputValue = b->simd_srlv(64, inputValue, r1);
575            inputValue = b->simd_sllv(64, inputValue, l2);
576            outputValue = b->CreateOr(b->CreateAnd(outputValue, clearMask), inputValue);
577            b->CreateStore(outputValue, b->CreateGEP(outputStreamBasePtrs[i], outputBlockIndex));
578        }
579
580        phiLiteralStart->addIncoming(b->CreateAdd(phiLiteralStart, copySize), b->GetInsertBlock());
581        phiLiteralLength->addIncoming(b->CreateSub(phiLiteralLength, copySize), b->GetInsertBlock());
582        phiOutputPos->addIncoming(b->CreateAdd(phiOutputPos, copySize), b->GetInsertBlock());
583        b->CreateBr(literalCopyConBlock);
584
585        // ---- literalCopyExitBlock
586        b->SetInsertPoint(literalCopyExitBlock);
587        b->setScalarField("outputPos", b->CreateAdd(outputPos, literalLength));
588    }
589
590}
Note: See TracBrowser for help on using the repository browser.