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, 10 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.