source: icGREP/icgrep-devel/icgrep/kernels/lz4/decompression/lz4_bytestream_decompression.cpp @ 6136

Last change on this file since 6136 was 6136, checked in by xwa163, 13 months ago
  1. Cleanup legacy slow LZ4 related kernels
  2. Rename lz4d_ext_dep to lz4_decompression
  3. Rename LZ4 AIO related kernels to LZ4 Decompression Kernel
File size: 10.9 KB
Line 
1
2#include "lz4_bytestream_decompression.h"
3
4
5#include <kernels/kernel_builder.h>
6#include <iostream>
7#include <string>
8#include <llvm/Support/raw_ostream.h>
9#include <kernels/streamset.h>
10
11using namespace llvm;
12using namespace kernel;
13using namespace std;
14
15
16namespace kernel{
17    std::string LZ4ByteStreamDecompressionKernel::getCopyByteStreamName() {
18        return mCopyOtherByteStream ? "targetByteStream" : "byteStream";
19    }
20
21    LZ4ByteStreamDecompressionKernel::LZ4ByteStreamDecompressionKernel(const std::unique_ptr<kernel::KernelBuilder> &b, bool copyOtherByteStream, unsigned blockSize)
22            : LZ4SequentialDecompressionKernel(b, "LZ4ByteStreamDecompressionKernel", blockSize),
23              mCopyOtherByteStream(copyOtherByteStream) {
24        mStreamSetOutputs.push_back(Binding{b->getStreamSetTy(1, 8), "outputStream", BoundedRate(0, 1)});
25        this->addScalar(b->getInt8PtrTy(), "temporaryInputPtr");
26        if (copyOtherByteStream) {
27            mStreamSetInputs.push_back(Binding{b->getStreamSetTy(1, 8), "targetByteStream", RateEqualTo("byteStream")});
28        }
29    }
30
31    void LZ4ByteStreamDecompressionKernel::doLiteralCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *literalStart,
32                                               llvm::Value *literalLength, llvm::Value* blockStart) {
33        Value* LZ4_BLOCK_SIZE = b->getSize(mBlockSize);
34        Value* INT_FW_1 = b->getIntN(COPY_FW, 1);
35        Value* SIZE_FW_BYTE = b->getSize(COPY_FW / BYTE_WIDTH);
36
37        Type* INT_FW_PTR = b->getIntNTy(COPY_FW)->getPointerTo();
38
39        Value* inputBytePtr = b->getScalarField("temporaryInputPtr");
40        inputBytePtr = b->CreateGEP(inputBytePtr, b->CreateSub(literalStart, blockStart));
41
42        Value* inputPtr = b->CreatePointerCast(inputBytePtr, INT_FW_PTR);
43
44        Value* outputPos = b->getScalarField("outputPos");
45        Value* outputBufferSize = b->getCapacity("outputStream");
46        Value* outputPosRem = b->CreateURem(outputPos, outputBufferSize);
47        Value* outputPosRemBlockSize = b->CreateURem(outputPos, b->getSize(mBlockSize));
48        Value* outputPtr = b->getRawOutputPointer("outputStream", outputPosRem);
49        outputPtr = b->CreatePointerCast(outputPtr, INT_FW_PTR);
50
51        BasicBlock* entryBlock = b->GetInsertBlock();
52        BasicBlock* literalCopyCon = b->CreateBasicBlock("literalCopyCon");
53        BasicBlock* literalCopyBody = b->CreateBasicBlock("literalCopyBody");
54        BasicBlock* literalCopyExit = b->CreateBasicBlock("literalCopyExit");
55
56        b->CreateBr(literalCopyCon);
57
58        // ---- literalCopyCon
59        b->SetInsertPoint(literalCopyCon);
60        PHINode* phiOutputPtr = b->CreatePHI(outputPtr->getType(), 2);
61        phiOutputPtr->addIncoming(outputPtr, entryBlock);
62        PHINode* phiInputPtr = b->CreatePHI(inputPtr->getType(), 2);
63        phiInputPtr->addIncoming(inputPtr, entryBlock);
64        PHINode* phiCopiedLength = b->CreatePHI(literalLength->getType(), 2);
65        phiCopiedLength->addIncoming(b->getSize(0), entryBlock);
66        b->CreateCondBr(b->CreateICmpULT(phiCopiedLength, literalLength), literalCopyBody, literalCopyExit);
67
68        // ---- literalCopyBody
69        b->SetInsertPoint(literalCopyBody);
70
71        Value* remBufferSize = b->CreateSub(LZ4_BLOCK_SIZE, b->CreateAdd(phiCopiedLength, outputPosRemBlockSize));
72        Value* fullCopy = b->CreateICmpULE(SIZE_FW_BYTE, remBufferSize);
73
74
75        BasicBlock* fullCopyBlock = b->CreateBasicBlock("fullCopyBlock");
76        BasicBlock* partCopyBlock = b->CreateBasicBlock("partCopyBlock");
77
78        BasicBlock* literalCopyEnd = b->CreateBasicBlock("literalCopyEnd");
79
80        b->CreateLikelyCondBr(fullCopy, fullCopyBlock, partCopyBlock);
81
82        // ---- fullCopyBlock
83        b->SetInsertPoint(fullCopyBlock);
84        b->CreateStore(b->CreateLoad(phiInputPtr), phiOutputPtr);
85        b->CreateBr(literalCopyEnd);
86        // ---- partCopyBlock
87        b->SetInsertPoint(partCopyBlock);
88        Value* oldOutputValue = b->CreateLoad(phiOutputPtr);
89        Value* inputValue = b->CreateLoad(phiInputPtr);
90
91        Value* actualCopyLength = b->CreateUMin(SIZE_FW_BYTE, remBufferSize);
92
93        Value* mask = b->CreateSub(
94                b->CreateShl(INT_FW_1, b->CreateMul(actualCopyLength, b->getIntN(COPY_FW, 8))),
95                INT_FW_1
96        );
97        mask = b->CreateSelect(
98                b->CreateICmpEQ(actualCopyLength, SIZE_FW_BYTE),
99                b->CreateNot(b->getIntN(COPY_FW, 0)),
100                mask
101        );
102
103        Value* actualOutput = b->CreateOr(
104                b->CreateAnd(inputValue, mask),
105                b->CreateAnd(oldOutputValue, b->CreateNot(mask))
106        );
107
108        b->CreateStore(actualOutput, phiOutputPtr);
109
110        b->CreateBr(literalCopyEnd);
111        // ---- literalCopyEnd
112        b->SetInsertPoint(literalCopyEnd);
113
114
115        phiInputPtr->addIncoming(b->CreateGEP(phiInputPtr, b->getSize(1)), b->GetInsertBlock());
116        phiOutputPtr->addIncoming(b->CreateGEP(phiOutputPtr, b->getSize(1)), b->GetInsertBlock());
117        phiCopiedLength->addIncoming(b->CreateAdd(phiCopiedLength, b->getSize(COPY_FW / BYTE_WIDTH)), b->GetInsertBlock());
118        b->CreateBr(literalCopyCon);
119
120        // ---- literalCopyExit
121        b->SetInsertPoint(literalCopyExit);
122        b->setScalarField("outputPos", b->CreateAdd(outputPos, literalLength));
123    }
124
125    void LZ4ByteStreamDecompressionKernel::doMatchCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *matchOffset,
126                                             llvm::Value *matchLength) {
127
128        Value* LZ4_BLOCK_SIZE = b->getSize(mBlockSize);
129        Type* INT_FW_PTR = b->getIntNTy(COPY_FW)->getPointerTo();
130        Value* INT_FW_1 = b->getIntN(COPY_FW, 1);
131        Value* SIZE_FW_BYTE = b->getSize(COPY_FW / BYTE_WIDTH);
132
133
134        BasicBlock* entryBlock = b->GetInsertBlock();
135
136        Value* outputPos = b->getScalarField("outputPos");
137        Value* outputBufferSize = b->getCapacity("outputStream");
138        Value* outputPosRemBlockSize = b->CreateURem(outputPos, b->getSize(mBlockSize));
139
140        Value* copyToPtr = b->getRawOutputPointer("outputStream", b->CreateURem(outputPos, outputBufferSize));
141        Value* copyFromPtr = b->getRawOutputPointer("outputStream", b->CreateURem(b->CreateSub(outputPos, matchOffset), outputBufferSize));
142
143        BasicBlock* matchCopyCon = b->CreateBasicBlock("matchCopyCon");
144        BasicBlock* matchCopyBody = b->CreateBasicBlock("matchCopyBody");
145        BasicBlock* matchCopyExit = b->CreateBasicBlock("matchCopyExit");
146
147        b->CreateBr(matchCopyCon);
148
149        // ---- matchCopyCon
150        b->SetInsertPoint(matchCopyCon);
151        PHINode* phiFromPtr = b->CreatePHI(b->getInt8PtrTy(), 2);
152        phiFromPtr->addIncoming(copyFromPtr, entryBlock);
153        PHINode* phiToPtr = b->CreatePHI(b->getInt8PtrTy(), 2);
154        phiToPtr->addIncoming(copyToPtr, entryBlock);
155        PHINode* phiCopiedSize = b->CreatePHI(b->getSizeTy(), 2);
156        phiCopiedSize->addIncoming(b->getSize(0), entryBlock);
157
158        b->CreateCondBr(b->CreateICmpULT(phiCopiedSize, matchLength), matchCopyBody, matchCopyExit);
159
160        // ---- matchCopyBody
161        b->SetInsertPoint(matchCopyBody);
162
163        Value* remBufferSize = b->CreateSub(LZ4_BLOCK_SIZE, b->CreateAdd(phiCopiedSize, outputPosRemBlockSize));
164        Value* fullCopy = b->CreateICmpULE(SIZE_FW_BYTE, remBufferSize);
165        Value* copyFromFwPtr = b->CreatePointerCast(phiFromPtr, INT_FW_PTR);
166        Value* copyToFwPtr = b->CreatePointerCast(phiToPtr, INT_FW_PTR);
167
168        BasicBlock* fullMatchCopyBlock = b->CreateBasicBlock("fullMatchCopyBlock");
169        BasicBlock* partMatchCopyBlock = b->CreateBasicBlock("partMatchCopyBlock");
170        BasicBlock* matchCopyEndBlock = b->CreateBasicBlock("matchCopyEndBlock");
171
172        b->CreateLikelyCondBr(fullCopy, fullMatchCopyBlock, partMatchCopyBlock);
173
174        // ---- fullMatchCopyBlock
175        b->SetInsertPoint(fullMatchCopyBlock);
176        b->CreateStore(b->CreateLoad(copyFromFwPtr), copyToFwPtr);
177        b->CreateBr(matchCopyEndBlock);
178
179        // ---- partMatchCopyBlock
180        b->SetInsertPoint(partMatchCopyBlock);
181        Value* oldOutputValue = b->CreateLoad(copyToFwPtr);
182        Value* actualCopyLength = b->CreateUMin(SIZE_FW_BYTE, remBufferSize);
183        Value* mask = b->CreateSub(
184                b->CreateShl(INT_FW_1, b->CreateMul(actualCopyLength, b->getIntN(COPY_FW, 8))),
185                INT_FW_1
186        );
187        mask = b->CreateSelect(
188                b->CreateICmpEQ(actualCopyLength, SIZE_FW_BYTE),
189                b->CreateNot(b->getIntN(COPY_FW, 0)),
190                mask
191        );
192
193        Value* actualOutput = b->CreateOr(
194                b->CreateAnd(b->CreateLoad(copyFromFwPtr), mask),
195                b->CreateAnd(oldOutputValue, b->CreateNot(mask))
196        );
197
198        b->CreateStore(
199                actualOutput,
200                copyToFwPtr
201        );
202
203        b->CreateBr(matchCopyEndBlock);
204
205        // ---- matchCopyEndBlock
206        b->SetInsertPoint(matchCopyEndBlock);
207
208
209        Value* copySize = b->CreateUMin(matchOffset, b->getSize(COPY_FW / 8));
210        phiFromPtr->addIncoming(b->CreateGEP(phiFromPtr, copySize), b->GetInsertBlock());
211        phiToPtr->addIncoming(b->CreateGEP(phiToPtr, copySize), b->GetInsertBlock());
212        phiCopiedSize->addIncoming(b->CreateAdd(phiCopiedSize, copySize), b->GetInsertBlock());
213        b->CreateBr(matchCopyCon);
214
215        // ---- matchCopyExit
216        b->SetInsertPoint(matchCopyExit);
217        b->setScalarField("outputPos", b->CreateAdd(outputPos, matchLength));
218    }
219
220    void LZ4ByteStreamDecompressionKernel::setProducedOutputItemCount(const std::unique_ptr<KernelBuilder> &b, llvm::Value* produced) {
221        b->setProducedItemCount("outputStream", produced);
222    }
223
224    void LZ4ByteStreamDecompressionKernel::initializationMethod(const std::unique_ptr<KernelBuilder> &b) {
225        b->setScalarField("temporaryInputPtr", b->CreateMalloc(b->getSize(mBlockSize)));
226    }
227
228    void LZ4ByteStreamDecompressionKernel::prepareProcessBlock(const std::unique_ptr<KernelBuilder> &b, llvm::Value* blockStart, llvm::Value* blockEnd) {
229        Value* rawInputPtr = b->CreatePointerCast(b->getRawInputPointer(this->getCopyByteStreamName(), b->getSize(0)), b->getInt8PtrTy());
230        Value* inputCapacity = b->getCapacity(this->getCopyByteStreamName());
231
232        Value* blockStartRem = b->CreateURem(blockStart, inputCapacity);
233        Value* remSize = b->CreateSub(inputCapacity, blockStartRem);
234
235        Value* blockSize = b->CreateSub(blockEnd, blockStart);
236
237        Value* copySize1 = b->CreateUMin(remSize, blockSize);
238        Value* copySize2 = b->CreateSub(blockSize, copySize1);
239
240        Value* temporayInputPtr = b->getScalarField("temporaryInputPtr");
241
242        b->CreateMemCpy(temporayInputPtr, b->CreateGEP(rawInputPtr, blockStartRem), copySize1, 1);
243        b->CreateMemCpy(b->CreateGEP(temporayInputPtr, copySize1), rawInputPtr, copySize2, 1);
244    }
245
246    void LZ4ByteStreamDecompressionKernel::beforeTermination(const std::unique_ptr<KernelBuilder> &b) {
247        b->CreateFree(b->getScalarField("temporaryInputPtr"));
248    }
249
250}
Note: See TracBrowser for help on using the repository browser.