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

Last change on this file since 6132 was 6132, checked in by xwa163, 9 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.