source: icGREP/icgrep-devel/icgrep/kernels/lz4/aio/lz4_bitstream_aio.cpp @ 6135

Last change on this file since 6135 was 6132, checked in by xwa163, 11 months ago
  1. More experiment on lz4 grep
  2. Improve performance of lzparabix grep
File size: 15.1 KB
Line 
1
2#include "lz4_bitstream_aio.h"
3
4#include <kernels/kernel_builder.h>
5#include <iostream>
6#include <string>
7#include <llvm/Support/raw_ostream.h>
8#include <kernels/streamset.h>
9
10using namespace llvm;
11using namespace kernel;
12using namespace std;
13
14namespace kernel{
15
16    LZ4BitStreamAioKernel::LZ4BitStreamAioKernel(const std::unique_ptr<kernel::KernelBuilder> &b,
17                                                 std::vector<unsigned> numsOfBitStreams,
18                                                 unsigned blockSize)
19    : LZ4SequentialAioBaseKernel(b, "LZ4BitStreamAioKernel", blockSize),
20      mNumsOfBitStreams(numsOfBitStreams)
21    {
22        mStreamSetInputs.push_back(Binding{b->getStreamSetTy(numsOfBitStreams[0], 1), "inputBitStream0", RateEqualTo("byteStream")});
23        mStreamSetOutputs.push_back(Binding{b->getStreamSetTy(numsOfBitStreams[0], 1), "outputStream0", BoundedRate(0, 1)});
24
25        for (unsigned i = 1; i < numsOfBitStreams.size(); i++) {
26            mStreamSetInputs.push_back(Binding{b->getStreamSetTy(numsOfBitStreams[i], 1), "inputBitStream" + std::to_string(i), RateEqualTo("byteStream")});
27            mStreamSetOutputs.push_back(Binding{b->getStreamSetTy(numsOfBitStreams[i], 1), "outputStream" + std::to_string(i), RateEqualTo("outputStream0")});
28        }
29
30        this->initPendingOutputScalar(b);
31    }
32
33    void LZ4BitStreamAioKernel::initPendingOutputScalar(const std::unique_ptr<kernel::KernelBuilder> &b) {
34        for (unsigned i = 0; i < mNumsOfBitStreams.size(); i++) {
35            for (unsigned j = 0; j < mNumsOfBitStreams[i]; j++) {
36                this->addScalar(b->getInt64Ty(), "pendingOutput" + std::to_string(i) + "_" + std::to_string(j));
37            }
38        }
39    }
40
41    void LZ4BitStreamAioKernel::doLiteralCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *literalStart,
42                                              llvm::Value *literalLength, llvm::Value* blockStart) {
43        // Constant
44        ConstantInt* INT_64_0 = b->getInt64(0);
45        ConstantInt* INT_64_1 = b->getInt64(1);
46
47        // ---- EntryBlock
48        BasicBlock* entryBlock = b->GetInsertBlock();
49        Value* remLiteralStart = b->CreateURem(literalStart, b->getCapacity("inputBitStream0"));
50        Value* remLiteralEnd = b->CreateAdd(remLiteralStart, literalLength);
51
52
53        BasicBlock* literalCopyCon = b->CreateBasicBlock("literalCopyCon");
54        BasicBlock* literalCopyBody = b->CreateBasicBlock("literalCopyBody");
55        BasicBlock* literalCopyExit = b->CreateBasicBlock("literalCopyExit");
56
57        b->CreateBr(literalCopyCon);
58
59        // ---- literalCopyCon
60        b->SetInsertPoint(literalCopyCon);
61        PHINode* phiLiteralPos = b->CreatePHI(b->getSizeTy(), 2);
62        phiLiteralPos->addIncoming(remLiteralStart, entryBlock);
63        b->CreateCondBr(b->CreateICmpULT(phiLiteralPos, remLiteralEnd), literalCopyBody, literalCopyExit);
64
65        // ---- literalCopyBody
66        b->SetInsertPoint(literalCopyBody);
67
68        Value* cursorBlockIndex = b->CreateUDiv(phiLiteralPos, b->getSize(b->getBitBlockWidth()));
69        Value* cursorBlockRem = b->CreateURem(phiLiteralPos, b->getSize(b->getBitBlockWidth()));
70        Value* cursorI64BlockIndex = b->CreateUDiv(cursorBlockRem, b->getSize(64));
71        Value* cursorI64BlockRem = b->CreateURem(cursorBlockRem, b->getSize(64));
72
73        Value* remainingLiteralLength = b->CreateSub(remLiteralEnd, phiLiteralPos);
74        Value* copyLength = b->CreateSub(b->getSize(64), cursorI64BlockRem);
75        copyLength = b->CreateUMin(copyLength, remainingLiteralLength);
76        Value* copyMask = b->CreateSub(
77                b->CreateSelect(b->CreateICmpEQ(copyLength, b->getInt64(0x40)), INT_64_0, b->CreateShl(INT_64_1, copyLength)),
78                INT_64_1
79        );
80
81        std::vector<llvm::Value*> extractValues;
82
83        for (unsigned i = 0; i < mNumsOfBitStreams.size(); i++) {
84            Value* bitStreamBasePtr = b->CreatePointerCast(b->getRawInputPointer("inputBitStream" + std::to_string(i), b->getSize(0)), b->getBitBlockType()->getPointerTo());
85            Value* targetBlockBasePtr = b->CreatePointerCast(b->CreateGEP(bitStreamBasePtr, b->CreateMul(cursorBlockIndex, b->getSize(mNumsOfBitStreams[i]))), b->getInt64Ty()->getPointerTo());
86
87            for (unsigned j = 0; j < mNumsOfBitStreams[i]; j++) {
88                Value* ptr = b->CreateGEP(targetBlockBasePtr, b->CreateAdd(cursorI64BlockIndex, b->getSize(j * (b->getBitBlockWidth() / 64))));
89                Value* extractV = b->CreateLShr(b->CreateLoad(ptr), cursorI64BlockRem);
90                extractV = b->CreateAnd(extractV, copyMask);
91                extractValues.push_back(extractV);
92            }
93        }
94        this->appendBitStreamOutput(b, extractValues, copyLength);
95
96        phiLiteralPos->addIncoming(b->CreateAdd(phiLiteralPos, copyLength), b->GetInsertBlock());
97        b->CreateBr(literalCopyCon);
98
99        // ---- literalCopyExit
100        b->SetInsertPoint(literalCopyExit);
101    }
102
103    void LZ4BitStreamAioKernel::doMatchCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *matchOffset,
104                                            llvm::Value *matchLength) {
105        // Constant
106        ConstantInt* INT_64_0 = b->getInt64(0);
107        ConstantInt* INT_64_1 = b->getInt64(1);
108
109        // ---- EntryBlock
110        BasicBlock* entryBlock = b->GetInsertBlock();
111        Value* outputPos = b->getScalarField("outputPos");
112        Value* outputBufferSize = b->getCapacity("outputStream0");
113        Value* matchPos = b->CreateSub(outputPos, matchOffset);
114
115        Value* remMatchPos = b->CreateURem(matchPos, outputBufferSize);
116        Value* remMatchEndPos = b->CreateAdd(remMatchPos, matchLength);
117
118        BasicBlock* matchCopyCon = b->CreateBasicBlock("matchCopyCon");
119        BasicBlock* matchCopyBody = b->CreateBasicBlock("matchCopyBody");
120        BasicBlock* matchCopyExit = b->CreateBasicBlock("matchCopyExit");
121
122        b->CreateBr(matchCopyCon);
123
124        // ---- matchCopyCon
125        b->SetInsertPoint(matchCopyCon);
126        PHINode* phiMatchPos = b->CreatePHI(b->getSizeTy(), 2);
127        phiMatchPos->addIncoming(remMatchPos, entryBlock);
128        b->CreateCondBr(b->CreateICmpULT(phiMatchPos, remMatchEndPos), matchCopyBody, matchCopyExit);
129
130        // ---- matchCopyBody
131        b->SetInsertPoint(matchCopyBody);
132
133        Value* matchPosBlockIndex = b->CreateUDiv(phiMatchPos, b->getSize(b->getBitBlockWidth()));
134        Value* matchPosBlockRem = b->CreateURem(phiMatchPos, b->getSize(b->getBitBlockWidth()));
135        Value* matchPosI64BlockIndex = b->CreateUDiv(matchPosBlockRem, b->getSize(64));
136        Value* matchPosI64BlockRem = b->CreateURem(matchPosBlockRem, b->getSize(64));
137
138        Value* remainingMatchLength = b->CreateSub(remMatchEndPos, phiMatchPos);
139        Value* copyLength = b->CreateSub(b->getSize(64), matchPosI64BlockRem);
140        copyLength = b->CreateUMin(copyLength, remainingMatchLength);
141        copyLength = b->CreateUMin(copyLength, matchOffset);
142
143        Value* copyMask = b->CreateSub(
144                b->CreateSelect(b->CreateICmpEQ(copyLength, b->getInt64(0x40)), INT_64_0, b->CreateShl(INT_64_1, copyLength)),
145                INT_64_1
146        );
147
148
149        Value* sameBlock = b->CreateICmpEQ(
150                b->CreateUDiv(b->CreateAdd(phiMatchPos, matchOffset), b->getSize(64)),
151                b->CreateUDiv(phiMatchPos, b->getSize(64))
152        );
153//        b->CallPrintInt("sameBlock", sameBlock);
154
155        std::vector<llvm::Value*> extractValues;
156//        b->CallPrintInt("matchPosI64BlockRem", matchPosI64BlockRem);
157        unsigned iStreamIndex = 0;
158        for (unsigned i = 0; i < mNumsOfBitStreams.size(); i++) {
159            Value* bitStreamBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream" + std::to_string(i), b->getSize(0)), b->getBitBlockType()->getPointerTo());
160            Value* targetBlockBasePtr = b->CreatePointerCast(b->CreateGEP(bitStreamBasePtr, b->CreateMul(matchPosBlockIndex, b->getSize(mNumsOfBitStreams[i]))), b->getInt64Ty()->getPointerTo());
161
162            for (unsigned j = 0; j < mNumsOfBitStreams[i]; j++) {
163                Value* ptr = b->CreateGEP(targetBlockBasePtr, b->CreateAdd(matchPosI64BlockIndex, b->getSize(j * (b->getBitBlockWidth() / 64))));
164                Value* extractV = b->CreateLoad(ptr);
165
166                extractV = b->CreateSelect(sameBlock, b->getScalarField("pendingOutput" + std::to_string(i) + "_" + std::to_string(j)), extractV);
167                extractV = b->CreateLShr(extractV, matchPosI64BlockRem);
168                extractV = b->CreateAnd(extractV, copyMask);
169
170                extractValues.push_back(extractV);
171
172                ++iStreamIndex;
173            }
174            for (unsigned j = 0; j < mNumsOfBitStreams[i]; j++) {
175//                b->CallPrintRegister("e" + std::to_string(j), b->CreateZExt(extractValues[mNumsOfBitStreams[i] - j], b->getIntNTy(256)));
176            }
177
178        }
179
180        this->appendBitStreamOutput(b, extractValues, copyLength);
181
182        phiMatchPos->addIncoming(b->CreateAdd(phiMatchPos, copyLength), b->GetInsertBlock());
183        b->CreateBr(matchCopyCon);
184
185        // ---- matchCopyExit
186        b->SetInsertPoint(matchCopyExit);
187    }
188
189    void
190    LZ4BitStreamAioKernel::setProducedOutputItemCount(const std::unique_ptr<KernelBuilder> &b, llvm::Value *produced) {
191        b->setProducedItemCount("outputStream0", produced);
192    }
193
194    void LZ4BitStreamAioKernel::appendBitStreamOutput(const std::unique_ptr<KernelBuilder> &b, std::vector<llvm::Value*>& extractedValues, llvm::Value* valueLength) {
195        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
196
197        Value* oldOutputPos = b->getScalarField("outputPos");
198        Value* oldOutputPosRem64 = b->CreateURem(oldOutputPos, b->getSize(64));
199
200        std::vector<llvm::Value*> newOutputVec;
201
202        unsigned iStreamIndex = 0;
203        for (unsigned i = 0; i < mNumsOfBitStreams.size(); i++) {
204            for (unsigned j = 0; j < mNumsOfBitStreams[i]; j++) {
205                Value* newValue = b->CreateOr(b->getScalarField("pendingOutput" + std::to_string(i) + "_" + std::to_string(j)), b->CreateShl(extractedValues[iStreamIndex], oldOutputPosRem64));
206                newOutputVec.push_back(newValue);
207                ++iStreamIndex;
208            }
209        }
210
211        BasicBlock* noStoreOutputBlock = b->CreateBasicBlock("noStoreOutputBlock");
212        BasicBlock* storeOutputBlock =b->CreateBasicBlock("storeOutputBlock");
213
214        b->CreateCondBr(b->CreateICmpULT(b->CreateAdd(oldOutputPosRem64, valueLength), b->getSize(64)), noStoreOutputBlock, storeOutputBlock);
215
216        // ---- noStoreOutputBlock
217        b->SetInsertPoint(noStoreOutputBlock);
218
219        iStreamIndex = 0;
220        for (unsigned i = 0; i < mNumsOfBitStreams.size(); i++) {
221            for (unsigned j = 0; j < mNumsOfBitStreams[i]; j++) {
222                b->setScalarField("pendingOutput" + std::to_string(i) + "_" + std::to_string(j), newOutputVec[iStreamIndex]);
223                ++iStreamIndex;
224            }
225        }
226
227        b->CreateBr(exitBlock);
228
229        // ---- storeOutputBlock
230        b->SetInsertPoint(storeOutputBlock);
231
232        Value* oldOutputPosRem = b->CreateURem(oldOutputPos, b->getCapacity("outputStream0"));
233        Value* oldOutputPosBitBlockIndex = b->CreateUDiv(oldOutputPosRem, b->getSize(b->getBitBlockWidth()));
234        Value* oldOutputPosBitBlockRem = b->CreateURem(oldOutputPosRem, b->getSize(b->getBitBlockWidth()));
235
236        iStreamIndex = 0;
237        for (unsigned i = 0; i < mNumsOfBitStreams.size(); i++) {
238            Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream" + std::to_string(i), b->getSize(0)), b->getBitBlockType()->getPointerTo());
239            Value* outputBitBlockBasePtr = b->CreateGEP(outputBasePtr, b->CreateMul(oldOutputPosBitBlockIndex, b->getSize(mNumsOfBitStreams[i])));
240            outputBitBlockBasePtr = b->CreatePointerCast(outputBitBlockBasePtr, b->getInt64Ty()->getPointerTo());
241
242            Value* oldOutputPosI64Index = b->CreateUDiv(oldOutputPosBitBlockRem, b->getSize(64));
243
244            for (unsigned j = 0; j < mNumsOfBitStreams[i]; j++) {
245                Value* targetPtr = b->CreateGEP(outputBitBlockBasePtr, b->CreateAdd(oldOutputPosI64Index, b->getSize(j * (b->getBitBlockWidth() / 64))));
246                b->CreateStore(newOutputVec[iStreamIndex], targetPtr);
247                ++iStreamIndex;
248            }
249        }
250
251        Value* shiftAmount = b->CreateSub(b->getSize(0x40), oldOutputPosRem64);
252        Value* fullyShift = b->CreateICmpEQ(shiftAmount, b->getSize(0x40));
253
254        iStreamIndex = 0;
255        for (unsigned i = 0; i < mNumsOfBitStreams.size(); i++) {
256            for (unsigned j = 0; j < mNumsOfBitStreams[i]; j++) {
257                b->setScalarField("pendingOutput" + std::to_string(i) + "_" + std::to_string(j), b->CreateSelect(fullyShift, b->getInt64(0), b->CreateLShr(extractedValues[iStreamIndex], shiftAmount)));
258                ++iStreamIndex;
259            }
260        }
261
262        b->CreateBr(exitBlock);
263
264        b->SetInsertPoint(exitBlock);
265        b->setScalarField("outputPos", b->CreateAdd(oldOutputPos, valueLength));
266    }
267
268    void LZ4BitStreamAioKernel::storePendingOutput(const std::unique_ptr<KernelBuilder> &b) {
269        BasicBlock* storePendingOutputBlock = b->CreateBasicBlock("storePendingOutputBlock");
270        BasicBlock* storePendingOutputExitBlock = b->CreateBasicBlock("storePendingOutputExitBlock");
271
272        Value* oldOutputPos = b->getScalarField("outputPos");
273        b->CreateCondBr(
274                b->CreateICmpNE(b->CreateURem(oldOutputPos, b->getSize(64)), b->getSize(0)),
275                storePendingOutputBlock,
276                storePendingOutputExitBlock
277        );
278
279        b->SetInsertPoint(storePendingOutputBlock);
280        this->storePendingOutput_BitStream(b);
281//        this->storePendingOutput_Swizzled(b);
282        b->CreateBr(storePendingOutputExitBlock);
283
284        b->SetInsertPoint(storePendingOutputExitBlock);
285    }
286
287    void LZ4BitStreamAioKernel::storePendingOutput_BitStream(const std::unique_ptr<KernelBuilder> &b) {
288
289        Value* oldOutputPos = b->getScalarField("outputPos");
290        Value* oldOutputPosRem = b->CreateURem(oldOutputPos, b->getCapacity("outputStream0"));
291        Value* oldOutputPosBitBlockIndex = b->CreateUDiv(oldOutputPosRem, b->getSize(b->getBitBlockWidth()));
292        Value* oldOutputPosBitBlockRem = b->CreateURem(oldOutputPosRem, b->getSize(b->getBitBlockWidth()));
293        Value* oldOutputPosI64Index = b->CreateUDiv(oldOutputPosBitBlockRem, b->getSize(64));
294
295        unsigned iStreamIndex = 0;
296        for (unsigned i = 0; i < mNumsOfBitStreams.size(); i++) {
297            Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream" + std::to_string(i), b->getSize(0)), b->getBitBlockType()->getPointerTo());
298            Value* outputBitBlockBasePtr = b->CreateGEP(outputBasePtr, b->CreateMul(oldOutputPosBitBlockIndex, b->getSize(mNumsOfBitStreams[i])));
299            outputBitBlockBasePtr = b->CreatePointerCast(outputBitBlockBasePtr, b->getInt64Ty()->getPointerTo());
300            for (unsigned j = 0; j < mNumsOfBitStreams[i]; j++) {
301                Value* targetPtr = b->CreateGEP(outputBitBlockBasePtr, b->CreateAdd(oldOutputPosI64Index, b->getSize(j * (b->getBitBlockWidth() / 64))));
302                b->CreateStore(b->getScalarField("pendingOutput" + std::to_string(i) + "_" + std::to_string(j)), targetPtr);
303                ++iStreamIndex;
304            }
305        }
306    }
307
308}
Note: See TracBrowser for help on using the repository browser.