source: icGREP/icgrep-devel/icgrep/kernels/lzparabix/decoder/LZParabixAioBaseKernel.cpp @ 6133

Last change on this file since 6133 was 6133, checked in by xwa163, 12 months ago
  1. Add sourceCC in multiplexed CC
  2. Remove workaround FakeBasisBits? from ICGrep
  3. Implement Swizzled version of LZParabix
  4. Init checkin for SwizzleByGather? Kernel
File size: 10.5 KB
Line 
1
2#include "LZParabixAioBaseKernel.h"
3
4#include <kernels/kernel_builder.h>
5#include <iostream>
6#include <llvm/Support/raw_ostream.h>
7#include <kernels/streamset.h>
8
9using namespace llvm;
10using namespace kernel;
11using namespace std;
12
13namespace kernel{
14    LZParabixAioBaseKernel::LZParabixAioBaseKernel(const std::unique_ptr<kernel::KernelBuilder> &b, std::string &&name)
15            : SegmentOrientedKernel(std::move(name),
16            // Inputs
17                                    {
18                                            Binding{b->getStreamSetTy(1, 8), "byteStream", BoundedRate(0, 1)},
19
20                                            // block data
21                                            Binding{b->getStreamSetTy(1, 64), "blockStart", BoundedRate(0, 1),
22                                                    AlwaysConsume()},
23                                            Binding{b->getStreamSetTy(1, 64), "blockEnd", RateEqualTo("blockStart"),
24                                                    AlwaysConsume()}
25                                    },
26            //Outputs
27                                    {},
28            //Arguments
29                                    {
30                                            Binding{b->getSizeTy(), "fileSize"}
31                                    },
32                                    {},
33            //Internal states:
34                                    {
35                                            Binding{b->getSizeTy(), "blockDataIndex"},
36                                            Binding{b->getInt64Ty(), "outputPos"}
37
38                                    }) {
39        this->setStride(4 * 1024 * 1024);
40        addAttribute(MustExplicitlyTerminate());
41    }
42
43    void LZParabixAioBaseKernel::generateDoSegmentMethod(const std::unique_ptr<KernelBuilder> &b) {
44        this->initDoSegmentMethod(b);
45
46
47        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
48        BasicBlock* blockEndConBlock = b->CreateBasicBlock("blockEndConBlock");
49
50        Value * blockDataIndex = b->getScalarField("blockDataIndex");
51        Value * totalNumber = b->getAvailableItemCount("blockEnd");
52
53        Value * blockEnd = this->generateLoadInt64NumberInput(b, "blockEnd", blockDataIndex);
54
55        b->CreateCondBr(b->CreateICmpULT(blockDataIndex, totalNumber), blockEndConBlock, exitBlock);
56
57        b->SetInsertPoint(blockEndConBlock);
58
59        Value * blockStart = this->generateLoadInt64NumberInput(b, "blockStart", blockDataIndex);
60
61        Value* literalLengthPtr = b->getRawInputPointer("byteStream", blockStart);
62        literalLengthPtr = b->CreatePointerCast(literalLengthPtr, b->getInt32Ty()->getPointerTo());
63
64        Value* totalLiteralLength = b->CreateZExtOrBitCast(b->CreateLoad(literalLengthPtr), b->getSizeTy());
65
66        BasicBlock * processBlock = b->CreateBasicBlock("processBlock");
67        b->CreateCondBr(this->isAllItemAvailable(b, totalLiteralLength), processBlock, exitBlock);
68
69        b->SetInsertPoint(processBlock);
70
71        this->generateProcessCompressedBlock(b, blockStart, blockEnd);
72
73        Value * newBlockDataIndex = b->CreateAdd(blockDataIndex, b->getInt64(1));
74        b->setScalarField("blockDataIndex", newBlockDataIndex);
75        b->setProcessedItemCount("blockStart", newBlockDataIndex);
76        b->setProcessedItemCount("byteStream", blockEnd);
77
78        this->setProducedOutputItemCount(b, b->getScalarField("outputPos"));
79        b->CreateBr(exitBlock);
80
81        b->SetInsertPoint(exitBlock);
82    }
83
84
85    llvm::Value *LZParabixAioBaseKernel::generateLoadInt64NumberInput(const std::unique_ptr<KernelBuilder> &iBuilder,
86                                                                      std::string inputBufferName, llvm::Value *globalOffset) {
87
88        Value * capacity = iBuilder->getCapacity(inputBufferName);
89        Value * processed = iBuilder->getProcessedItemCount(inputBufferName);
90        processed = iBuilder->CreateAnd(processed, iBuilder->CreateNeg(capacity));
91        Value * offset = iBuilder->CreateSub(globalOffset, processed);
92        Value * valuePtr = iBuilder->getRawInputPointer(inputBufferName, offset);
93        return iBuilder->CreateLoad(valuePtr);
94    }
95
96    void LZParabixAioBaseKernel::generateProcessCompressedBlock(const std::unique_ptr<KernelBuilder> &b,
97                                                            llvm::Value *lz4BlockStart, llvm::Value *lz4BlockEnd) {
98        Value* literalLengthPtr = b->getRawInputPointer("byteStream", lz4BlockStart);
99        literalLengthPtr = b->CreatePointerCast(literalLengthPtr, b->getInt32Ty()->getPointerTo());
100        Value* totalLiteralLength = b->CreateZExtOrBitCast(b->CreateLoad(literalLengthPtr), b->getSizeTy());
101
102        Value* literalStartPos = this->getProcessedInputItemCount(b);
103
104        Value* tokenStartPos = b->CreateAdd(b->CreateAdd(lz4BlockStart, b->getSize(4)), totalLiteralLength);
105
106        Value* isTerminal = b->CreateICmpEQ(lz4BlockEnd, b->getScalarField("fileSize"));
107        b->setTerminationSignal(isTerminal);
108
109        BasicBlock* exitBlock = b->CreateBasicBlock("processCompressedExitBlock");
110
111        BasicBlock* processCon = b->CreateBasicBlock("processCompressedConBlock");
112        BasicBlock* processBody = b->CreateBasicBlock("processCompressedBodyBlock");
113
114        BasicBlock* beforeProcessConBlock = b->GetInsertBlock();
115        b->CreateBr(processCon);
116        b->SetInsertPoint(processCon);
117
118        PHINode* phiLiteralCursorValue = b->CreatePHI(b->getInt64Ty(), 2);
119        phiLiteralCursorValue->addIncoming(literalStartPos, beforeProcessConBlock);
120
121        PHINode* phiTokenCursorValue = b->CreatePHI(b->getInt64Ty(), 2); // phiCursorValue should always be the position of next token except for the final sequence
122        phiTokenCursorValue->addIncoming(tokenStartPos, beforeProcessConBlock);
123
124        b->CreateCondBr(b->CreateICmpULT(phiTokenCursorValue, lz4BlockEnd), processBody, exitBlock);
125
126        b->SetInsertPoint(processBody);
127
128        auto ret = this->processSequence(b, phiLiteralCursorValue, phiTokenCursorValue, lz4BlockEnd);
129
130        Value* nextLiteralGlobalPos = ret.first;
131        Value* nextTokenGlobalPos = ret.second;
132
133        phiLiteralCursorValue->addIncoming(nextLiteralGlobalPos, b->GetInsertBlock());
134        phiTokenCursorValue->addIncoming(nextTokenGlobalPos, b->GetInsertBlock());
135        b->CreateBr(processCon);
136
137        b->SetInsertPoint(exitBlock);
138        this->setProcessedInputItemCount(b, b->CreateAdd(literalStartPos, totalLiteralLength));
139    }
140
141    std::pair<llvm::Value *, llvm::Value *>
142    LZParabixAioBaseKernel::processSequence(const std::unique_ptr<KernelBuilder> &b, llvm::Value *literalCursorPos,
143                                        llvm::Value *tokenCursorPos,
144                                        llvm::Value *lz4BlockEnd) {
145
146        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
147
148        Value* sequenceBasePtr = b->getRawInputPointer("byteStream", tokenCursorPos);
149        Value* sequenceToken = b->CreateLoad(sequenceBasePtr);
150
151        Value* highestTokenBit = b->CreateAnd(sequenceToken, b->getInt8((uint8_t)1 << 7));
152        Value* isLiteral = b->CreateICmpNE(highestTokenBit, b->getInt8(0));
153        Value* tokenNumValue = b->CreateZExt(b->CreateSub(sequenceToken, highestTokenBit), b->getSizeTy());
154
155
156        BasicBlock* literalProcessBlock = b->CreateBasicBlock("literalProcessBlock");
157        BasicBlock* matchProcessBlock = b->CreateBasicBlock("matchProcessBlock");
158        b->CreateCondBr(isLiteral, literalProcessBlock, matchProcessBlock);
159
160        // ---- literalProcessBlock
161        b->SetInsertPoint(literalProcessBlock);
162        this->doLiteralCopy(b, literalCursorPos, tokenNumValue);
163        Value* newTokenCursorPosAfterLiteral = b->CreateAdd(tokenCursorPos, b->getSize(1));
164        Value* newLiteralCursorPosAfterLiteral = b->CreateAdd(literalCursorPos, tokenNumValue);
165
166
167        BasicBlock* literalProcessFinalBlock = b->GetInsertBlock();
168        b->CreateBr(exitBlock);
169
170        // ---- matchProcessBlock
171        b->SetInsertPoint(matchProcessBlock);
172        Value* tokenCursorNextPos = b->CreateAdd(tokenCursorPos, b->getSize(1));
173        Value* matchIndexBytes = this->processMatch(b, tokenCursorNextPos, tokenNumValue, sequenceBasePtr);
174        Value* newTokenCursorPosAfterMatch = b->CreateAdd(tokenCursorNextPos, matchIndexBytes);
175
176        BasicBlock* matchProcessFinalBlock = b->GetInsertBlock();
177        b->CreateBr(exitBlock);
178
179        // ---- exitBlock
180        b->SetInsertPoint(exitBlock);
181        PHINode* phiTokenCursorValue = b->CreatePHI(b->getSizeTy(), 2);
182        phiTokenCursorValue->addIncoming(newTokenCursorPosAfterLiteral, literalProcessFinalBlock);
183        phiTokenCursorValue->addIncoming(newTokenCursorPosAfterMatch, matchProcessFinalBlock);
184
185        PHINode* phiLiteralCursorValue = b->CreatePHI(b->getSizeTy(), 2);
186        phiLiteralCursorValue->addIncoming(newLiteralCursorPosAfterLiteral, literalProcessFinalBlock);
187        phiLiteralCursorValue->addIncoming(literalCursorPos, matchProcessFinalBlock);
188
189        return std::make_pair(phiLiteralCursorValue, phiTokenCursorValue);
190    }
191
192    llvm::Value* LZParabixAioBaseKernel::processMatch(const std::unique_ptr<KernelBuilder> &b, llvm::Value* cursorPos, llvm::Value* matchOffset, llvm::Value* sequenceBasePtr) {
193        Function* pdep = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_bmi_pdep_64);
194
195
196        Value* pdepMask = b->getInt64(0x0101010101010101);
197
198        Value* oneBitIndex = b->CreateZExt(b->CreateLoad(b->CreateGEP(sequenceBasePtr, b->getSize(1))), b->getInt64Ty());
199        Value* zeroBitIndex = b->CreateZExt(b->CreateLoad(b->CreateGEP(sequenceBasePtr, b->getSize(2))), b->getInt64Ty());
200        Value* matchMaskPtr = b->CreatePointerCast(b->CreateGEP(sequenceBasePtr, b->getSize(3)), b->getInt64Ty()->getPointerTo());
201        Value* matchMask = b->CreateLoad(matchMaskPtr);
202
203        Value* fullOneBitIndex = b->CreateCall(pdep, {oneBitIndex, pdepMask});
204        Value* fullZeroBitIndex = b->CreateCall(pdep, {zeroBitIndex, pdepMask});
205
206
207        Value* remainingMask = b->CreateNot(b->CreateMul(b->CreateOr(fullOneBitIndex, fullZeroBitIndex), b->getInt64(0xff)));
208        Value* fullMatchMask = b->CreateOr(
209                b->CreateMul(fullOneBitIndex, b->getInt64(0xff)),
210                b->CreateCall(pdep, {matchMask, remainingMask})
211        );
212
213        this->doMatchCopy(b, cursorPos, matchOffset, fullMatchMask);
214
215        return b->CreateAdd(b->CreateSub(b->getSize(8), b->CreatePopcount(b->CreateOr(oneBitIndex, zeroBitIndex))), b->getSize(2));
216    }
217
218    llvm::Value* LZParabixAioBaseKernel::isAllItemAvailable(const std::unique_ptr<KernelBuilder> &b, llvm::Value* literalLength) {
219        return b->getInt1(true);
220    }
221
222
223}
Note: See TracBrowser for help on using the repository browser.