source: icGREP/icgrep-devel/icgrep/lzparabix/LZParabixGrepGenerator.cpp @ 6128

Last change on this file since 6128 was 6128, checked in by xwa163, 12 months ago

lzparabix_grep: Improve the performance by merging LineFeed? stream into multiplexing alphabet

File size: 14.4 KB
Line 
1//
2// Created by wxy325 on 2018/6/19.
3//
4
5#include "LZParabixGrepGenerator.h"
6
7
8#include <boost/iostreams/device/mapped_file.hpp>
9
10#include <llvm/Support/PrettyStackTrace.h>
11
12#include <cc/cc_compiler.h>
13
14#include <kernels/cc_kernel.h>
15#include <kernels/s2p_kernel.h>
16#include <kernels/p2s_kernel.h>
17#include <kernels/source_kernel.h>
18#include <kernels/stdout_kernel.h>
19#include <kernels/kernel_builder.h>
20#include <kernels/swizzle.h>
21#include <re/re_toolchain.h>
22
23#include <re/collect_ccs.h>
24#include <re/replaceCC.h>
25#include <re/re_seq.h>
26#include <re/re_cc.h>
27
28#include <UCD/resolve_properties.h>
29#include <kernels/charclasses.h>
30#include <kernels/grep_kernel.h>
31#include <kernels/UCD_property_kernel.h>
32#include <kernels/grapheme_kernel.h>
33#include <kernels/linebreak_kernel.h>
34#include <kernels/streams_merge.h>
35#include <kernels/scanmatchgen.h>
36#include <kernels/until_n.h>
37#include <re/casing.h>
38#include <re/exclude_CC.h>
39#include <re/to_utf8.h>
40#include <re/re_analysis.h>
41#include <re/re_name_resolve.h>
42#include <re/re_name_gather.h>
43#include <re/re_multiplex.h>
44#include <re/re_utility.h>
45#include <re/grapheme_clusters.h>
46#include <re/printer_re.h>
47#include <llvm/Support/raw_ostream.h>
48#include <llvm/Support/Debug.h>
49#include <kernels/fake_stream_generating_kernel.h>
50
51namespace re { class CC; }
52
53using namespace llvm;
54using namespace parabix;
55using namespace kernel;
56using namespace grep;
57
58
59LZParabixGrepGenerator::LZParabixGrepGenerator(bool enableMultiplexing): LZParabixGenerator(), mEnableMultiplexing(enableMultiplexing) {
60    mGrepRecordBreak = grep::GrepRecordBreakKind::LF;
61    mMoveMatchesToEOL = true;
62}
63
64void LZParabixGrepGenerator::initREs(std::vector<re::RE *> &REs) {
65    if (mGrepRecordBreak == GrepRecordBreakKind::Unicode) {
66        mBreakCC = re::makeCC(re::makeCC(0x0A, 0x0D), re::makeCC(re::makeCC(0x85), re::makeCC(0x2028, 0x2029)));
67    } else if (mGrepRecordBreak == GrepRecordBreakKind::Null) {
68        mBreakCC = re::makeByte(0);  // Null
69    } else {
70        mBreakCC = re::makeByte(0x0A); // LF
71    }
72    re::RE * anchorRE = mBreakCC;
73    if (mGrepRecordBreak == GrepRecordBreakKind::Unicode) {
74        re::Name * anchorName = re::makeName("UTF8_LB", re::Name::Type::Unicode);
75        anchorName->setDefinition(re::makeUnicodeBreak());
76        anchorRE = anchorName;
77    }
78
79    mREs = REs;
80    bool allAnchored = true;
81    for(unsigned i = 0; i < mREs.size(); ++i) {
82        if (!hasEndAnchor(mREs[i])) allAnchored = false;
83        mREs[i] = resolveModesAndExternalSymbols(mREs[i]);
84        mREs[i] = re::exclude_CC(mREs[i], mBreakCC);
85        mREs[i] = resolveAnchors(mREs[i], anchorRE);
86        re::gatherUnicodeProperties(mREs[i], mUnicodeProperties);
87        mREs[i] = regular_expression_passes(mREs[i]);
88    }
89    if (allAnchored && (mGrepRecordBreak != GrepRecordBreakKind::Unicode)) mMoveMatchesToEOL = false;
90}
91
92void LZParabixGrepGenerator::generateCountOnlyMainFunc(const std::unique_ptr<kernel::KernelBuilder> &iBuilder) {
93    Module * M = iBuilder->getModule();
94    Type * const int64Ty = iBuilder->getInt64Ty();
95    Type * const sizeTy = iBuilder->getSizeTy();
96    Type * const boolTy = iBuilder->getIntNTy(sizeof(bool) * 8);
97//    Type * const voidTy = iBuilder->getVoidTy();
98    Type * const inputType = iBuilder->getInt8PtrTy();
99
100    Function * const main = cast<Function>(M->getOrInsertFunction("Main", int64Ty, inputType, sizeTy, sizeTy, boolTy, nullptr));
101    main->setCallingConv(CallingConv::C);
102    Function::arg_iterator args = main->arg_begin();
103    mInputStream = &*(args++);
104    mInputStream->setName("input");
105
106    mHeaderSize = &*(args++);
107    mHeaderSize->setName("mHeaderSize");
108
109    mFileSize = &*(args++);
110    mFileSize->setName("mFileSize");
111
112    mHasBlockChecksum = &*(args++);
113    mHasBlockChecksum->setName("mHasBlockChecksum");
114    // TODO for now, we do not handle blockCheckSum
115    mHasBlockChecksum = iBuilder->getInt1(false);
116
117    iBuilder->SetInsertPoint(BasicBlock::Create(M->getContext(), "entry", main, 0));
118}
119
120void LZParabixGrepGenerator::generateCountOnlyAioPipeline(re::RE *regex) {
121    auto & iBuilder = mPxDriver.getBuilder();
122    this->generateCountOnlyMainFunc(iBuilder);
123
124    this->generateLoadByteStreamAndBitStream(iBuilder);
125
126
127    StreamSetBuffer * LineBreakStream;
128    StreamSetBuffer * Matches;
129    std::vector<re::RE*> res = {regex};
130    if (mEnableMultiplexing) {
131        std::tie(LineBreakStream, Matches) = multiplexingGrepPipeline(res);
132    } else {
133        std::tie(LineBreakStream, Matches) = grepPipeline(res);
134    }
135
136//    Kernel * outK = mPxDriver.addKernelInstance<FileSink>(iBuilder, 8);
137//    outK->setInitialArguments({iBuilder->GetString("/Users/wxy325/developer/LZ4-sample-files/workspace/lz4d-normal/8k_.txt")});
138//    mPxDriver.makeKernelCall(outK, {decompressedStream}, {});
139
140    kernel::Kernel * matchCountK = mPxDriver.addKernelInstance<kernel::PopcountKernel>(iBuilder);
141    mPxDriver.makeKernelCall(matchCountK, {Matches}, {});
142    mPxDriver.generatePipelineIR();
143
144    iBuilder->setKernel(matchCountK);
145    Value * matchedLineCount = iBuilder->getAccumulator("countResult");
146    matchedLineCount = iBuilder->CreateZExt(matchedLineCount, iBuilder->getInt64Ty());
147
148    mPxDriver.deallocateBuffers();
149
150    iBuilder->CreateRet(matchedLineCount);
151
152    mPxDriver.finalizeObject();
153}
154
155
156std::pair<parabix::StreamSetBuffer *, parabix::StreamSetBuffer *> LZParabixGrepGenerator::multiplexingGrepPipeline(std::vector<re::RE *> &REs) {
157
158    this->initREs(REs);
159    auto mGrepDriver = &mPxDriver;
160
161    auto & idb = mGrepDriver->getBuilder();
162    // TODO: until we automate stream buffer sizing, use this calculation to determine how large our matches buffer needs to be.
163    const unsigned baseBufferSize = this->getInputBufferBlocks(idb);
164    int MaxCountFlag = 0;
165
166    //  Regular Expression Processing and Analysis Phase
167    const auto nREs = mREs.size();
168
169    std::vector<StreamSetBuffer *> MatchResultsBufs(nREs);
170
171
172    std::map<std::string, StreamSetBuffer *> propertyStream;
173
174    std::vector<std::string> externalStreamNames;
175    std::set<re::Name *> UnicodeProperties;
176
177    re::CC* linefeedCC = re::makeCC(0x0A);
178
179    re::Seq* seq = re::makeSeq();
180    seq->push_back(mREs[0]);
181    seq->push_back(std::move(linefeedCC));
182
183    const auto UnicodeSets = re::collectCCs(seq, &cc::Unicode, std::set<re::Name *>({re::makeZeroWidth("\\b{g}")}));
184    StreamSetBuffer * const MatchResults = mGrepDriver->addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize, 1);
185
186    this->generateBlockData(idb);
187    StreamSetBuffer * const LiteralBitStream = this->extractLiteralBitStream(idb);
188
189    mpx = make_unique<cc::MultiplexedAlphabet>("mpx", UnicodeSets);
190    mREs[0] = transformCCs(mpx.get(), mREs[0]);
191
192    std::vector<re::CC *> mpx_basis = mpx->getMultiplexedCCs();
193    auto numOfCharacterClasses = mpx_basis.size();
194//    llvm::outs() << "numOfCharacterClasses:" << numOfCharacterClasses << "\n";
195    StreamSetBuffer * CharClasses = mGrepDriver->addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(numOfCharacterClasses), baseBufferSize, 1);
196
197    kernel::Kernel * ccK = mGrepDriver->addKernelInstance<kernel::CharClassesKernel>(idb, std::move(mpx_basis), false, cc::BitNumbering::BigEndian);
198    mGrepDriver->makeKernelCall(ccK, {LiteralBitStream}, {CharClasses});
199
200//    StreamSetBuffer * CompressedLineFeedStream = mPxDriver.addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize, 1);
201//    kernel::Kernel * linefeedK = mPxDriver.addKernelInstance<kernel::LineFeedKernelBuilder>(idb, Binding{idb->getStreamSetTy(8), "basis", FixedRate(), Principal()}, cc::BitNumbering::BigEndian);
202//    mPxDriver.makeKernelCall(linefeedK, {LiteralBitStream}, {CompressedLineFeedStream});
203
204//    auto ret = this->generateBitStreamDecompression(idb, {CharClasses, CompressedLineFeedStream});
205    auto ret = this->generateBitStreamDecompression(idb, {CharClasses});
206
207    StreamSetBuffer * decompressedCharClasses = ret[0];
208//    StreamSetBuffer * LineBreakStream = ret[1];
209
210
211    StreamSetBuffer * fakeMatchCopiedBits = mPxDriver.addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(8), this->getInputBufferBlocks(idb), 1);
212    Kernel* fakeStreamGeneratorK = mPxDriver.addKernelInstance<FakeStreamGeneratingKernel>(idb, numOfCharacterClasses, 8);
213    mPxDriver.makeKernelCall(fakeStreamGeneratorK, {decompressedCharClasses}, {fakeMatchCopiedBits});
214
215    kernel::Kernel * icgrepK = mGrepDriver->addKernelInstance<kernel::ICGrepKernel>(idb, mREs[0], externalStreamNames, std::vector<cc::Alphabet *>{mpx.get()}, cc::BitNumbering::BigEndian, true);
216    mGrepDriver->makeKernelCall(icgrepK, {fakeMatchCopiedBits, decompressedCharClasses}, {MatchResults});
217    MatchResultsBufs[0] = MatchResults;
218
219    StreamSetBuffer * newLineBreak = mPxDriver.addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), this->getInputBufferBlocks(idb));
220    kernel::Kernel * lineFeedGrepK = mGrepDriver->addKernelInstance<kernel::ICGrepKernel>(idb, transformCCs(mpx.get(), linefeedCC), externalStreamNames, std::vector<cc::Alphabet *>{mpx.get()}, cc::BitNumbering::BigEndian, true);
221    mGrepDriver->makeKernelCall(lineFeedGrepK, {fakeMatchCopiedBits, decompressedCharClasses}, {newLineBreak});
222
223
224    StreamSetBuffer * MergedResults = MatchResultsBufs[0];
225    if (mREs.size() > 1) {
226        MergedResults = mGrepDriver->addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
227        kernel::Kernel * streamsMergeK = mGrepDriver->addKernelInstance<kernel::StreamsMerge>(idb, 1, mREs.size());
228        mGrepDriver->makeKernelCall(streamsMergeK, MatchResultsBufs, {MergedResults});
229    }
230    StreamSetBuffer * Matches = MergedResults;
231    if (mMoveMatchesToEOL) {
232        StreamSetBuffer * OriginalMatches = Matches;
233        kernel::Kernel * matchedLinesK = mGrepDriver->addKernelInstance<kernel::MatchedLinesKernel>(idb);
234        Matches = mGrepDriver->addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
235        mGrepDriver->makeKernelCall(matchedLinesK, {OriginalMatches, newLineBreak}, {Matches});
236    }
237
238    if (MaxCountFlag > 0) {
239        kernel::Kernel * untilK = mGrepDriver->addKernelInstance<kernel::UntilNkernel>(idb);
240        untilK->setInitialArguments({idb->getSize(MaxCountFlag)});
241        StreamSetBuffer * const AllMatches = Matches;
242        Matches = mGrepDriver->addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
243        mGrepDriver->makeKernelCall(untilK, {AllMatches}, {Matches});
244    }
245
246    return std::pair<StreamSetBuffer *, StreamSetBuffer *>(newLineBreak, Matches);
247};
248
249
250std::pair<parabix::StreamSetBuffer *, parabix::StreamSetBuffer *>
251LZParabixGrepGenerator::grepPipeline(std::vector<re::RE *> &REs) {
252
253    this->initREs(REs);
254    auto mGrepDriver = &mPxDriver;
255
256    auto & idb = mGrepDriver->getBuilder();
257    // TODO: until we automate stream buffer sizing, use this calculation to determine how large our matches buffer needs to be.
258    const unsigned baseBufferSize = this->getInputBufferBlocks(idb);
259    int MaxCountFlag = 0;
260
261    //  Regular Expression Processing and Analysis Phase
262    const auto nREs = mREs.size();
263
264    std::vector<StreamSetBuffer *> MatchResultsBufs(nREs);
265
266
267    this->generateBlockData(idb);
268    StreamSetBuffer * const LiteralBitStream = this->extractLiteralBitStream(idb);
269//    auto compressedLineBreakStream = this->linefeedStreamFromDecompressedBits(LiteralBitStream);
270
271
272    auto ret = this->generateBitStreamDecompression(idb, {LiteralBitStream/*, compressedLineBreakStream*/});
273    StreamSetBuffer * decompressedBasisBits = ret[0];
274//    StreamSetBuffer * LineBreakStream = ret[1];
275
276//    StreamSetBuffer * decompressedBasisBits = this->generateAioBitStreamDecompressoin(idb, {mCompressedBasisBits})[0];
277    StreamSetBuffer * LineBreakStream = this->linefeedStreamFromDecompressedBits(decompressedBasisBits);
278
279    std::map<std::string, StreamSetBuffer *> propertyStream;
280
281    for(unsigned i = 0; i < nREs; ++i) {
282        std::vector<std::string> externalStreamNames;
283        std::vector<StreamSetBuffer *> icgrepInputSets = {decompressedBasisBits};
284
285        std::set<re::Name *> UnicodeProperties;
286
287        StreamSetBuffer * MatchResults = mGrepDriver->addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
288        kernel::Kernel * icgrepK = mGrepDriver->addKernelInstance<kernel::ICGrepKernel>(idb, mREs[i], externalStreamNames, std::vector<cc::Alphabet *>(), cc::BitNumbering::BigEndian);
289        mGrepDriver->makeKernelCall(icgrepK, icgrepInputSets, {MatchResults});
290        MatchResultsBufs[i] = MatchResults;
291    }
292
293    StreamSetBuffer * MergedResults = MatchResultsBufs[0];
294    if (mREs.size() > 1) {
295        MergedResults = mGrepDriver->addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
296        kernel::Kernel * streamsMergeK = mGrepDriver->addKernelInstance<kernel::StreamsMerge>(idb, 1, mREs.size());
297        mGrepDriver->makeKernelCall(streamsMergeK, MatchResultsBufs, {MergedResults});
298    }
299    StreamSetBuffer * Matches = MergedResults;
300    if (mMoveMatchesToEOL) {
301        StreamSetBuffer * OriginalMatches = Matches;
302        kernel::Kernel * matchedLinesK = mGrepDriver->addKernelInstance<kernel::MatchedLinesKernel>(idb);
303        Matches = mGrepDriver->addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
304        mGrepDriver->makeKernelCall(matchedLinesK, {OriginalMatches, LineBreakStream}, {Matches});
305    }
306
307    if (MaxCountFlag > 0) {
308        kernel::Kernel * untilK = mGrepDriver->addKernelInstance<kernel::UntilNkernel>(idb);
309        untilK->setInitialArguments({idb->getSize(MaxCountFlag)});
310        StreamSetBuffer * const AllMatches = Matches;
311        Matches = mGrepDriver->addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
312        mGrepDriver->makeKernelCall(untilK, {AllMatches}, {Matches});
313    }
314
315    return std::pair<StreamSetBuffer *, StreamSetBuffer *>(LineBreakStream, Matches);
316}
317
318parabix::StreamSetBuffer *
319LZParabixGrepGenerator::linefeedStreamFromDecompressedBits(parabix::StreamSetBuffer *decompressedBasisBits) {
320    auto & idb = mPxDriver.getBuilder();
321    const unsigned baseBufferSize = this->getInputBufferBlocks(idb);
322    StreamSetBuffer * LineFeedStream = mPxDriver.addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
323    kernel::Kernel * linefeedK = mPxDriver.addKernelInstance<kernel::LineFeedKernelBuilder>(idb, Binding{idb->getStreamSetTy(8), "basis", FixedRate(), Principal()}, cc::BitNumbering::BigEndian);
324    mPxDriver.makeKernelCall(linefeedK, {decompressedBasisBits}, {LineFeedStream});
325    return LineFeedStream;
326}
327
328CountOnlyGrepMainFunctionType LZParabixGrepGenerator::getCountOnlyGrepMainFunction() {
329    return reinterpret_cast<CountOnlyGrepMainFunctionType>(mPxDriver.getMain());
330}
Note: See TracBrowser for help on using the repository browser.