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

Last change on this file since 6132 was 6132, checked in by xwa163, 6 months ago
  1. More experiment on lz4 grep
  2. Improve performance of lzparabix grep
File size: 8.0 KB
Line 
1//
2// Created by wxy325 on 2018/7/19.
3//
4
5#include "lz4_i4_bytestream_aio.h"
6
7#include <kernels/kernel_builder.h>
8#include <iostream>
9#include <string>
10#include <llvm/Support/raw_ostream.h>
11#include <kernels/streamset.h>
12
13using namespace llvm;
14using namespace kernel;
15using namespace std;
16
17
18namespace kernel {
19    LZ4I4ByteStreamAioKernel::LZ4I4ByteStreamAioKernel(const std::unique_ptr<kernel::KernelBuilder> &b, unsigned blockSize)
20            : LZ4SequentialAioBaseKernel(b, "LZ4I4ByteStreamAioKernel", blockSize)
21    {
22        mStreamSetInputs.push_back(Binding{b->getStreamSetTy(1, 4), "inputI4Stream", RateEqualTo("byteStream")});
23        mStreamSetOutputs.push_back(Binding{b->getStreamSetTy(1, 4), "outputI4Stream", BoundedRate(0, 1)});
24    }
25
26    void LZ4I4ByteStreamAioKernel::doLiteralCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *literalStart,
27                               llvm::Value *literalLength, llvm::Value* blockStart) {
28        unsigned fw = 64;
29        Type* INT_FW_PTR = b->getIntNTy(fw)->getPointerTo();
30
31        Value* inputCapacity = b->getCapacity("inputI4Stream");
32        Value* outputCapacity = b->getCapacity("outputI4Stream");
33
34        Value* inputByteBasePtr = b->CreatePointerCast(b->getRawInputPointer("inputI4Stream", b->getSize(0)), b->getInt8PtrTy());
35        Value* outputByteBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputI4Stream", b->getSize(0)), b->getInt8PtrTy());
36
37        Value* outputPos = b->getScalarField("outputPos");
38//        b->CallPrintInt("literalCopy", outputPos);
39
40        // ---- EntryBlock
41        BasicBlock* entryBlock = b->GetInsertBlock();
42
43
44        BasicBlock* literalCopyCon = b->CreateBasicBlock("literalCopyCon");
45
46        b->CreateBr(literalCopyCon);
47
48        // ---- literalCopyCon
49        b->SetInsertPoint(literalCopyCon);
50        PHINode* phiCopiedLength = b->CreatePHI(b->getSizeTy(), 2);
51        phiCopiedLength->addIncoming(b->getSize(0), entryBlock);
52
53        BasicBlock* literalCopyBody = b->CreateBasicBlock("literalCopyBody");
54        BasicBlock* literalCopyExit = b->CreateBasicBlock("literalCopyExit");
55
56        b->CreateCondBr(b->CreateICmpULT(phiCopiedLength, literalLength), literalCopyBody, literalCopyExit);
57
58        // ---- literalCopyBody
59        b->SetInsertPoint(literalCopyBody);
60        Value* copyStart = b->CreateAdd(literalStart, phiCopiedLength);
61        Value* copyStartRem = b->CreateURem(copyStart, inputCapacity);
62        Value* copyStartRem2 = b->CreateURem(copyStart, b->getSize(2));
63        Value* copyStartByteRem = b->CreateUDiv(copyStartRem, b->getSize(2));
64        Value* remainingDataLength = b->CreateSub(inputCapacity, copyStartRem);
65
66        Value* inputTargetPtr = b->CreateGEP(inputByteBasePtr, copyStartByteRem);
67        inputTargetPtr = b->CreatePointerCast(inputTargetPtr, INT_FW_PTR);
68
69        Value* outputStart = b->CreateAdd(outputPos, phiCopiedLength);
70        Value* outputStartRem = b->CreateURem(outputStart, outputCapacity);
71        Value* outputStartRem2 = b->CreateURem(outputStartRem, b->getSize(2));
72        Value* outputStartByteRem = b->CreateUDiv(outputStartRem, b->getSize(2));
73        Value* outputTargetPtr = b->CreateGEP(outputByteBasePtr, outputStartByteRem);
74        outputTargetPtr = b->CreatePointerCast(outputTargetPtr, INT_FW_PTR);
75
76
77        Value* inputTargetValue = b->CreateLoad(inputTargetPtr);
78        inputTargetValue = b->CreateLShr(inputTargetValue, b->CreateMul(copyStartRem2, b->getIntN(fw, 4)));
79
80
81        Value* outputValue = b->CreateLoad(outputTargetPtr);
82        Value* outputMask = b->CreateSelect(
83                b->CreateICmpEQ(outputStartRem2, b->getSize(1)),
84                b->getIntN(fw, 0xf),
85                b->getIntN(fw, 0)
86        );
87        outputValue = b->CreateAnd(outputValue, outputMask);
88        inputTargetValue = b->CreateShl(inputTargetValue, b->CreateMul(outputStartRem2, b->getIntN(fw, 4)));
89        outputValue = b->CreateOr(outputValue, inputTargetValue);
90        b->CreateStore(outputValue, outputTargetPtr);
91
92        Value* newCopyLength = b->getSize(fw / 4);
93        newCopyLength = b->CreateSub(newCopyLength, b->CreateOr(outputStartRem2, copyStartRem2));
94        newCopyLength = b->CreateUMin(newCopyLength, remainingDataLength);
95
96        phiCopiedLength->addIncoming(b->CreateAdd(phiCopiedLength, newCopyLength), b->GetInsertBlock());
97
98        b->CreateBr(literalCopyCon);
99
100        // ---- literalCopyExit
101        b->SetInsertPoint(literalCopyExit);
102        b->setScalarField("outputPos", b->CreateAdd(outputPos, literalLength));
103    }
104
105    void LZ4I4ByteStreamAioKernel::doMatchCopy(const std::unique_ptr<KernelBuilder> &b, llvm::Value *matchOffset,
106                             llvm::Value *matchLength) {
107        unsigned fw = 64;
108        Type* INT_FW_PTR = b->getIntNTy(fw)->getPointerTo();
109
110        Value* outputCapacity = b->getCapacity("outputI4Stream");
111
112        Value* outputByteBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputI4Stream", b->getSize(0)), b->getInt8PtrTy());
113
114        Value* outputPos = b->getScalarField("outputPos");
115//        b->CallPrintInt("matchCopy", outputPos);
116        Value* outputPosRem = b->CreateURem(outputPos, outputCapacity);
117
118        // ---- EntryBlock
119        BasicBlock* entryBlock = b->GetInsertBlock();
120        BasicBlock* literalCopyCon = b->CreateBasicBlock("literalCopyCon");
121        b->CreateBr(literalCopyCon);
122
123        // ---- literalCopyCon
124        b->SetInsertPoint(literalCopyCon);
125        PHINode* phiCopiedLength = b->CreatePHI(b->getSizeTy(), 2);
126        phiCopiedLength->addIncoming(b->getSize(0), entryBlock);
127
128        BasicBlock* literalCopyBody = b->CreateBasicBlock("literalCopyBody");
129        BasicBlock* literalCopyExit = b->CreateBasicBlock("literalCopyExit");
130
131        b->CreateCondBr(b->CreateICmpULT(phiCopiedLength, matchLength), literalCopyBody, literalCopyExit);
132
133        // ---- literalCopyBody
134        b->SetInsertPoint(literalCopyBody);
135
136        Value* outputStartRem = b->CreateAdd(outputPosRem, phiCopiedLength);
137        Value* outputStartRem2 = b->CreateURem(outputStartRem, b->getSize(2));
138        Value* outputStartByteRem = b->CreateUDiv(outputStartRem, b->getSize(2));
139
140        Value* outputTargetPtr = b->CreateGEP(outputByteBasePtr, outputStartByteRem);
141        outputTargetPtr = b->CreatePointerCast(outputTargetPtr, INT_FW_PTR);
142
143
144        Value* copyStartRem = b->CreateSub(outputStartRem, matchOffset);
145        Value* copyStartRem2 = b->CreateURem(copyStartRem, b->getSize(2));
146        Value* copyStartByteRem = b->CreateUDiv(copyStartRem, b->getSize(2));
147
148        Value* inputTargetPtr = b->CreateGEP(outputByteBasePtr, copyStartByteRem);
149        inputTargetPtr = b->CreatePointerCast(inputTargetPtr, INT_FW_PTR);
150
151
152
153
154        Value* inputTargetValue = b->CreateLoad(inputTargetPtr);
155        inputTargetValue = b->CreateLShr(inputTargetValue, b->CreateMul(copyStartRem2, b->getIntN(fw, 4)));
156
157
158        Value* outputValue = b->CreateLoad(outputTargetPtr);
159        Value* outputMask = b->CreateSelect(
160                b->CreateICmpEQ(outputStartRem2, b->getSize(1)),
161                b->getIntN(fw, 0xf),
162                b->getIntN(fw, 0)
163        );
164        outputValue = b->CreateAnd(outputValue, outputMask);
165        inputTargetValue = b->CreateShl(inputTargetValue, b->CreateMul(outputStartRem2, b->getIntN(fw, 4)));
166        outputValue = b->CreateOr(outputValue, inputTargetValue);
167        b->CreateStore(outputValue, outputTargetPtr);
168
169
170
171        Value* newCopyLength = b->getSize(fw / 4);
172        newCopyLength = b->CreateSub(newCopyLength, b->CreateOr(outputStartRem2, copyStartRem2));
173        newCopyLength = b->CreateUMin(newCopyLength, matchOffset);
174
175        phiCopiedLength->addIncoming(b->CreateAdd(phiCopiedLength, newCopyLength), b->GetInsertBlock());
176
177        b->CreateBr(literalCopyCon);
178
179        // ---- literalCopyExit
180        b->SetInsertPoint(literalCopyExit);
181
182
183        b->setScalarField("outputPos", b->CreateAdd(outputPos, matchLength));
184    }
185
186    void LZ4I4ByteStreamAioKernel::setProducedOutputItemCount(const std::unique_ptr<KernelBuilder> &b, llvm::Value* produced) {
187        b->setProducedItemCount("outputI4Stream", produced);
188    }
189
190}
Note: See TracBrowser for help on using the repository browser.