source: icGREP/icgrep-devel/icgrep/lz4/lz4_grep_generator.cpp @ 6140

Last change on this file since 6140 was 6140, checked in by xwa163, 15 months ago

UTF-8 support for Multiplexing LZ4 Grep

File size: 34.8 KB
Line 
1
2#include "lz4_grep_generator.h"
3
4#include <boost/iostreams/device/mapped_file.hpp>
5
6#include <llvm/Support/PrettyStackTrace.h>
7
8#include <cc/cc_compiler.h>
9
10#include <kernels/cc_kernel.h>
11#include <kernels/s2p_kernel.h>
12#include <kernels/p2s_kernel.h>
13#include <kernels/source_kernel.h>
14#include <kernels/stdout_kernel.h>
15#include <kernels/kernel_builder.h>
16#include <kernels/deletion.h>
17#include <kernels/swizzle.h>
18#include <kernels/pdep_kernel.h>
19#include <kernels/swizzled_multiple_pdep_kernel.h>
20#include <kernels/fake_stream_generating_kernel.h>
21#include <kernels/bitstream_pdep_kernel.h>
22#include <kernels/bitstream_gather_pdep_kernel.h>
23#include <re/re_toolchain.h>
24
25#include <re/collect_ccs.h>
26#include <re/replaceCC.h>
27
28#include <re/casing.h>
29#include <re/exclude_CC.h>
30#include <re/to_utf8.h>
31#include <re/re_analysis.h>
32#include <re/re_name_resolve.h>
33#include <re/re_name_gather.h>
34#include <re/re_multiplex.h>
35#include <re/re_utility.h>
36
37#include <UCD/resolve_properties.h>
38#include <kernels/charclasses.h>
39#include <kernels/grep_kernel.h>
40#include <kernels/UCD_property_kernel.h>
41#include <kernels/grapheme_kernel.h>
42#include <kernels/linebreak_kernel.h>
43#include <kernels/streams_merge.h>
44#include <kernels/scanmatchgen.h>
45#include <kernels/until_n.h>
46#include <re/grapheme_clusters.h>
47#include <re/printer_re.h>
48#include <llvm/Support/raw_ostream.h>
49#include <llvm/Support/Debug.h>
50#include <kernels/lz4/lz4_block_decoder.h>
51#include <kernels/lz4/decompression/lz4_swizzled_decompression.h>
52#include <kernels/lz4/decompression/lz4_bitstream_decompression.h>
53#include <re/re_seq.h>
54#include <kernels/lz4/decompression/lz4_bytestream_decompression.h>
55#include <kernels/lz4/twist_kernel.h>
56#include <kernels/lz4/decompression/lz4_twist_decompression.h>
57#include <kernels/lz4/untwist_kernel.h>
58
59namespace re { class CC; }
60
61using namespace llvm;
62using namespace parabix;
63using namespace kernel;
64using namespace grep;
65
66LZ4GrepGenerator::LZ4GrepGenerator(bool enableMultiplexing): LZ4BaseGenerator(), mEnableMultiplexing(enableMultiplexing) {
67    mGrepRecordBreak = grep::GrepRecordBreakKind::LF;
68    mMoveMatchesToEOL = true;
69}
70
71void LZ4GrepGenerator::initREs(std::vector<re::RE *> & REs) {
72    if (mGrepRecordBreak == GrepRecordBreakKind::Unicode) {
73        mBreakCC = re::makeCC(re::makeCC(0x0A, 0x0D), re::makeCC(re::makeCC(0x85), re::makeCC(0x2028, 0x2029)));
74    } else if (mGrepRecordBreak == GrepRecordBreakKind::Null) {
75        mBreakCC = re::makeByte(0);  // Null
76    } else {
77        mBreakCC = re::makeByte(0x0A); // LF
78    }
79    re::RE * anchorRE = mBreakCC;
80    if (mGrepRecordBreak == GrepRecordBreakKind::Unicode) {
81        re::Name * anchorName = re::makeName("UTF8_LB", re::Name::Type::Unicode);
82        anchorName->setDefinition(re::makeUnicodeBreak());
83        anchorRE = anchorName;
84    }
85
86    mREs = REs;
87    bool allAnchored = true;
88    for(unsigned i = 0; i < mREs.size(); ++i) {
89        if (!hasEndAnchor(mREs[i])) allAnchored = false;
90        mREs[i] = resolveModesAndExternalSymbols(mREs[i]);
91        mREs[i] = re::exclude_CC(mREs[i], mBreakCC);
92        mREs[i] = resolveAnchors(mREs[i], anchorRE);
93        re::gatherUnicodeProperties(mREs[i], mUnicodeProperties);
94        mREs[i] = regular_expression_passes(mREs[i]);
95    }
96    if (allAnchored && (mGrepRecordBreak != GrepRecordBreakKind::Unicode)) mMoveMatchesToEOL = false;
97
98}
99
100
101parabix::StreamSetBuffer * LZ4GrepGenerator::linefeedStreamFromUncompressedBits(
102        parabix::StreamSetBuffer *uncompressedBasisBits) {
103    auto & idb = mPxDriver.getBuilder();
104    const unsigned baseBufferSize = this->getDefaultBufferBlocks();
105    StreamSetBuffer * LineFeedStream = mPxDriver.addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
106    kernel::Kernel * linefeedK = mPxDriver.addKernelInstance<kernel::LineFeedKernelBuilder>(idb, Binding{idb->getStreamSetTy(8), "basis", FixedRate(), Principal()}, cc::BitNumbering::BigEndian);
107    mPxDriver.makeKernelCall(linefeedK, {uncompressedBasisBits}, {LineFeedStream});
108    return LineFeedStream;
109}
110
111parabix::StreamSetBuffer * LZ4GrepGenerator::convertCompressedBitsStreamWithTwistApproach(
112        parabix::StreamSetBuffer *compressedByteStream,
113        parabix::StreamSetBuffer *compressedBitStream,
114        std::string prefix
115) {
116    auto & b = mPxDriver.getBuilder();
117
118    LZ4BlockInfo blockInfo = this->getBlockInfo(compressedByteStream);
119
120    unsigned numOfStreams = compressedBitStream->getNumOfStreams();
121
122    if (numOfStreams == 1) {
123        StreamSetBuffer* uncompressedBitStream = mPxDriver.addBuffer<StaticBuffer>(b, b->getStreamSetTy(1, 1),
124                                                                                            this->getDefaultBufferBlocks());
125        Kernel* lz4I4AioK = mPxDriver.addKernelInstance<LZ4TwistDecompressionKernel>(b, 1);
126        lz4I4AioK->setInitialArguments({mFileSize});
127        mPxDriver.makeKernelCall(lz4I4AioK, {
128                compressedByteStream,
129
130                blockInfo.isCompress,
131                blockInfo.blockStart,
132                blockInfo.blockEnd,
133
134                compressedBitStream
135        }, {
136                uncompressedBitStream
137                                 });
138        return uncompressedBitStream;
139    }
140
141    if (numOfStreams <= 2) {
142        StreamSetBuffer* twistedCharClasses = mPxDriver.addBuffer<StaticBuffer>(b, b->getStreamSetTy(1, 2),
143                                                                                this->getDefaultBufferBlocks());
144        kernel::Kernel* twistK = mPxDriver.addKernelInstance<kernel::TwistByPDEPKernel>(b, numOfStreams, 2);
145        mPxDriver.makeKernelCall(twistK, {compressedBitStream}, {twistedCharClasses});
146
147
148        StreamSetBuffer* uncompressedTwistedCharClasses = mPxDriver.addBuffer<StaticBuffer>(b, b->getStreamSetTy(1, 2),
149                                                                                            this->getDefaultBufferBlocks());
150        Kernel* lz4I4AioK = mPxDriver.addKernelInstance<LZ4TwistDecompressionKernel>(b, 2);
151        lz4I4AioK->setInitialArguments({mFileSize});
152        mPxDriver.makeKernelCall(lz4I4AioK, {
153                compressedByteStream,
154
155                blockInfo.isCompress,
156                blockInfo.blockStart,
157                blockInfo.blockEnd,
158
159                twistedCharClasses
160        }, {
161                                         uncompressedTwistedCharClasses
162                                 });
163
164        StreamSetBuffer* untwistedCharClasses = mPxDriver.addBuffer<StaticBuffer>(b, b->getStreamSetTy(numOfStreams),
165                                                                                  this->getDefaultBufferBlocks());
166        kernel::Kernel* untwistK = mPxDriver.addKernelInstance<kernel::UntwistByPEXTKernel>(b, numOfStreams, 2);
167        mPxDriver.makeKernelCall(untwistK, {uncompressedTwistedCharClasses}, {untwistedCharClasses});
168        return untwistedCharClasses;
169    }
170
171    if (numOfStreams <= 4) {
172        StreamSetBuffer* twistedCharClasses = mPxDriver.addBuffer<StaticBuffer>(b, b->getStreamSetTy(1, 4),
173                                                                                this->getDefaultBufferBlocks());
174        kernel::Kernel* twistK = mPxDriver.addKernelInstance<kernel::TwistByPDEPKernel>(b, numOfStreams, 4);
175        mPxDriver.makeKernelCall(twistK, {compressedBitStream}, {twistedCharClasses});
176
177
178        StreamSetBuffer* uncompressedTwistedCharClasses = mPxDriver.addBuffer<StaticBuffer>(b, b->getStreamSetTy(1, 4),
179                                                                                            this->getDefaultBufferBlocks());
180
181        Kernel* lz4I4AioK = mPxDriver.addKernelInstance<LZ4TwistDecompressionKernel>(b, 4);
182        lz4I4AioK->setInitialArguments({mFileSize});
183        mPxDriver.makeKernelCall(lz4I4AioK, {
184                compressedByteStream,
185
186                blockInfo.isCompress,
187                blockInfo.blockStart,
188                blockInfo.blockEnd,
189
190                twistedCharClasses
191        }, {
192                                         uncompressedTwistedCharClasses
193                                 });
194
195        StreamSetBuffer* untwistedCharClasses = mPxDriver.addBuffer<StaticBuffer>(b, b->getStreamSetTy(numOfStreams),
196                                                                                  this->getDefaultBufferBlocks());
197        kernel::Kernel* untwistK = mPxDriver.addKernelInstance<kernel::UntwistByPEXTKernel>(b, numOfStreams, 4);
198        mPxDriver.makeKernelCall(untwistK, {uncompressedTwistedCharClasses}, {untwistedCharClasses});
199        return untwistedCharClasses;
200    }
201
202    // <= 8
203    StreamSetBuffer * const mtxByteStream = mPxDriver.addBuffer<StaticBuffer>(b, b->getStreamSetTy(1, 8),
204                                                                              this->getDefaultBufferBlocks());
205    Kernel * p2sK = mPxDriver.addKernelInstance<P2SKernel>(b, cc::BitNumbering::BigEndian, prefix, numOfStreams);
206    mPxDriver.makeKernelCall(p2sK, {compressedBitStream}, {mtxByteStream});
207
208    StreamSetBuffer * const decompressionMtxByteStream = mPxDriver.addBuffer<StaticBuffer>(b, b->getStreamSetTy(1, 8),
209                                                                                           this->getDefaultBufferBlocks(), 1);
210    Kernel* lz4AioK = mPxDriver.addKernelInstance<LZ4ByteStreamDecompressionKernel>(b, true);
211    lz4AioK->setInitialArguments({mFileSize});
212    mPxDriver.makeKernelCall(
213            lz4AioK,
214            {
215                    compressedByteStream,
216                    // Block Data
217                    blockInfo.isCompress,
218                    blockInfo.blockStart,
219                    blockInfo.blockEnd,
220                    mtxByteStream
221            }, {
222                    decompressionMtxByteStream
223            });
224
225    StreamSetBuffer * const uncompressedMtxBitStream = mPxDriver.addBuffer<StaticBuffer>(b, b->getStreamSetTy(numOfStreams),
226                                                                                         this->getDefaultBufferBlocks());
227
228    Kernel * s2pk = mPxDriver.addKernelInstance<S2PKernel>(b, cc::BitNumbering::BigEndian, true, prefix, numOfStreams);
229    mPxDriver.makeKernelCall(s2pk, {decompressionMtxByteStream}, {uncompressedMtxBitStream});
230    return uncompressedMtxBitStream;
231}
232
233StreamSetBuffer * LZ4GrepGenerator::convertCompressedBitsStreamWithSwizzledAioApproach(
234        StreamSetBuffer *compressedByteStream,
235        StreamSetBuffer *compressedBitStream,
236        std::string prefix
237) {
238    auto mGrepDriver = &mPxDriver;
239    auto & b = mGrepDriver->getBuilder();
240
241    LZ4BlockInfo blockInfo = this->getBlockInfo(compressedByteStream);
242
243    // Produce unswizzled bit streams
244    StreamSetBuffer * u16Swizzle0 = mPxDriver.addBuffer<StaticBuffer>(b, b->getStreamSetTy(4),
245                                                                      this->getDefaultBufferBlocks(), 1);
246    Kernel * unSwizzleK = mPxDriver.addKernelInstance<SwizzleGenerator>(b, 4, 1, 1, 64, "source");
247    mPxDriver.makeKernelCall(unSwizzleK, {compressedBitStream}, {u16Swizzle0});
248
249    StreamSetBuffer * uncompressedSwizzled0 = mPxDriver.addBuffer<StaticBuffer>(b, b->getStreamSetTy(4),
250                                                                                this->getDefaultBufferBlocks(), 1);
251
252
253    Kernel* lz4AioK = mPxDriver.addKernelInstance<LZ4SwizzledDecompressionKernel>(b, 4, 1, 4);
254    lz4AioK->setInitialArguments({mFileSize});
255    mPxDriver.makeKernelCall(
256            lz4AioK,
257            {
258                    compressedByteStream,
259
260                    // Block Data
261                    blockInfo.isCompress,
262                    blockInfo.blockStart,
263                    blockInfo.blockEnd,
264
265                    u16Swizzle0,
266            }, {
267                    uncompressedSwizzled0,
268            });
269
270
271
272    StreamSetBuffer * const decompressionBitStream = mPxDriver.addBuffer<StaticBuffer>(b, b->getStreamSetTy(8, 1),
273                                                                                       this->getDefaultBufferBlocks());
274    Kernel * unSwizzleK2 = mPxDriver.addKernelInstance<SwizzleGenerator>(b, 4, 1, 1, 64, "dst");
275    mPxDriver.makeKernelCall(unSwizzleK2, {uncompressedSwizzled0}, {decompressionBitStream});
276
277    return decompressionBitStream;
278
279}
280
281
282std::pair<parabix::StreamSetBuffer *, parabix::StreamSetBuffer *> LZ4GrepGenerator::multiplexingGrepPipeline(
283        std::vector<re::RE *> &REs,
284        parabix::StreamSetBuffer *compressedByteStream,
285        parabix::StreamSetBuffer *compressedBitStream,
286        bool useSwizzled,
287        bool useByteStream
288) {
289
290    this->initREs(REs);
291    auto mGrepDriver = &mPxDriver;
292
293    auto & idb = mGrepDriver->getBuilder();
294    const unsigned baseBufferSize = this->getDefaultBufferBlocks();
295    int MaxCountFlag = 0;
296
297    //  Regular Expression Processing and Analysis Phase
298    const auto nREs = mREs.size();
299
300    std::vector<StreamSetBuffer *> MatchResultsBufs(nREs);
301
302
303    std::map<std::string, StreamSetBuffer *> propertyStream;
304
305    std::vector<std::string> externalStreamNames;
306    std::set<re::Name *> UnicodeProperties;
307
308    re::CC* linefeedCC = re::makeByte(0x0A);
309
310    re::Seq* seq = re::makeSeq();
311    re::RE* targetRe = mREs[0];
312    re::RE* utf8Re = re::toUTF8(targetRe, true);
313
314
315    seq->push_back(utf8Re);
316    seq->push_back(std::move(linefeedCC));
317
318    std::vector<re::CC*> UnicodeSets = re::collectCCs(seq, &cc::Byte, std::set<re::Name *>({re::makeZeroWidth("\\b{g}")}));
319
320    StreamSetBuffer * const MatchResults = mGrepDriver->addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
321
322    mpx = make_unique<cc::MultiplexedAlphabet>("mpx", UnicodeSets);
323    re::RE* r = transformCCs(mpx.get(), utf8Re);
324    mREs[0] = r;
325
326
327    std::vector<re::CC *> mpx_basis = mpx->getMultiplexedCCs();
328    auto numOfCharacterClasses = mpx_basis.size();
329    StreamSetBuffer * CharClasses = mGrepDriver->addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(numOfCharacterClasses), baseBufferSize);
330
331
332    kernel::Kernel * ccK = mGrepDriver->addKernelInstance<kernel::ByteClassesKernel>(idb, std::move(mpx_basis), false, cc::BitNumbering::BigEndian);
333    mGrepDriver->makeKernelCall(ccK, {compressedBitStream}, {CharClasses});
334
335    StreamSetBuffer * uncompressedCharClasses = nullptr;
336    if (useSwizzled) {
337        uncompressedCharClasses = this->convertCompressedBitsStreamWithSwizzledAioApproach(compressedByteStream, CharClasses, "combined");
338    } else if (useByteStream){
339        uncompressedCharClasses = this->convertCompressedBitsStreamWithTwistApproach(compressedByteStream, CharClasses,
340                                                                                     "combined");
341    } else {
342        auto ret = this->convertCompressedBitsStreamWithBitStreamAioApproach(compressedByteStream, {CharClasses});
343        uncompressedCharClasses = ret[0];
344    }
345
346    StreamSetBuffer * fakeMatchCopiedBits = mPxDriver.addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(8),
347                                                                              this->getDefaultBufferBlocks());
348    StreamSetBuffer * u8NoFinalStream = mPxDriver.addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1),
349                                                                          this->getDefaultBufferBlocks(), 1);
350
351    Kernel* fakeStreamGeneratorK = mPxDriver.addKernelInstance<FakeStreamGeneratingKernel>(idb, numOfCharacterClasses, std::vector<unsigned>({8, 1}));
352    mPxDriver.makeKernelCall(fakeStreamGeneratorK, {uncompressedCharClasses}, {fakeMatchCopiedBits, u8NoFinalStream});
353
354    StreamSetBuffer * LineBreakStream = mPxDriver.addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), this->getDefaultBufferBlocks());
355    kernel::Kernel * lineFeedGrepK = mGrepDriver->addKernelInstance<kernel::ICGrepKernel>(idb, transformCCs(mpx.get(), linefeedCC), externalStreamNames, std::vector<cc::Alphabet *>{mpx.get()}, cc::BitNumbering::BigEndian);
356    mGrepDriver->makeKernelCall(lineFeedGrepK, {fakeMatchCopiedBits, uncompressedCharClasses}, {LineBreakStream});
357
358
359    externalStreamNames.push_back("UTF8_nonfinal");
360
361    kernel::Kernel * icgrepK = mGrepDriver->addKernelInstance<kernel::ICGrepKernel>(idb, mREs[0], externalStreamNames, std::vector<cc::Alphabet *>{mpx.get()}, cc::BitNumbering::BigEndian);
362    mGrepDriver->makeKernelCall(icgrepK, {fakeMatchCopiedBits, u8NoFinalStream, uncompressedCharClasses}, {MatchResults});
363    MatchResultsBufs[0] = MatchResults;
364
365    StreamSetBuffer * MergedResults = MatchResultsBufs[0];
366    if (mREs.size() > 1) {
367        MergedResults = mGrepDriver->addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
368        kernel::Kernel * streamsMergeK = mGrepDriver->addKernelInstance<kernel::StreamsMerge>(idb, 1, mREs.size());
369        mGrepDriver->makeKernelCall(streamsMergeK, MatchResultsBufs, {MergedResults});
370    }
371    StreamSetBuffer * Matches = MergedResults;
372    if (mMoveMatchesToEOL) {
373        StreamSetBuffer * OriginalMatches = Matches;
374        kernel::Kernel * matchedLinesK = mGrepDriver->addKernelInstance<kernel::MatchedLinesKernel>(idb);
375        Matches = mGrepDriver->addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
376        mGrepDriver->makeKernelCall(matchedLinesK, {OriginalMatches, LineBreakStream}, {Matches});
377    }
378
379    if (MaxCountFlag > 0) {
380        kernel::Kernel * untilK = mGrepDriver->addKernelInstance<kernel::UntilNkernel>(idb);
381        untilK->setInitialArguments({idb->getSize(MaxCountFlag)});
382        StreamSetBuffer * const AllMatches = Matches;
383        Matches = mGrepDriver->addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
384        mGrepDriver->makeKernelCall(untilK, {AllMatches}, {Matches});
385    }
386
387    return std::pair<StreamSetBuffer *, StreamSetBuffer *>(LineBreakStream, Matches);
388};
389
390std::pair<parabix::StreamSetBuffer *, parabix::StreamSetBuffer *> LZ4GrepGenerator::grepPipeline(
391        std::vector<re::RE *> &REs, parabix::StreamSetBuffer *uncompressedBasisBits) {
392
393    this->initREs(REs);
394    auto mGrepDriver = &mPxDriver;
395
396    auto & idb = mGrepDriver->getBuilder();
397    // TODO: until we automate stream buffer sizing, use this calculation to determine how large our matches buffer needs to be.
398    const unsigned baseBufferSize = this->getDefaultBufferBlocks();
399    int MaxCountFlag = 0;
400
401    //  Regular Expression Processing and Analysis Phase
402    const auto nREs = mREs.size();
403
404    std::vector<StreamSetBuffer *> MatchResultsBufs(nREs);
405
406    StreamSetBuffer * LineBreakStream = this->linefeedStreamFromUncompressedBits(uncompressedBasisBits);
407
408
409    std::map<std::string, StreamSetBuffer *> propertyStream;
410
411    for(unsigned i = 0; i < nREs; ++i) {
412        std::vector<std::string> externalStreamNames;
413        std::vector<StreamSetBuffer *> icgrepInputSets = {uncompressedBasisBits};
414
415        if (mEnableMultiplexing) {
416            const auto UnicodeSets = re::collectCCs(mREs[i], &cc::Unicode, std::set<re::Name *>({re::makeZeroWidth("\\b{g}")}));
417            StreamSetBuffer * const MatchResults = mGrepDriver->addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
418
419            mpx = make_unique<cc::MultiplexedAlphabet>("mpx", UnicodeSets);
420            mREs[i] = transformCCs(mpx.get(), mREs[i]);
421            std::vector<re::CC *> mpx_basis = mpx->getMultiplexedCCs();
422            auto numOfCharacterClasses = mpx_basis.size();
423            StreamSetBuffer * CharClasses = mGrepDriver->addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(numOfCharacterClasses), baseBufferSize);
424            kernel::Kernel * ccK = mGrepDriver->addKernelInstance<kernel::CharClassesKernel>(idb, std::move(mpx_basis), false, cc::BitNumbering::BigEndian);
425            mGrepDriver->makeKernelCall(ccK, {uncompressedBasisBits}, {CharClasses});
426
427            kernel::Kernel * icgrepK = mGrepDriver->addKernelInstance<kernel::ICGrepKernel>(idb, mREs[i], externalStreamNames, std::vector<cc::Alphabet *>{mpx.get()}, cc::BitNumbering::BigEndian);
428            icgrepInputSets.push_back(CharClasses);
429            mGrepDriver->makeKernelCall(icgrepK, icgrepInputSets, {MatchResults});
430            MatchResultsBufs[i] = MatchResults;
431        } else {
432            std::set<re::Name *> UnicodeProperties;
433
434            StreamSetBuffer * MatchResults = mGrepDriver->addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
435            kernel::Kernel * icgrepK = mGrepDriver->addKernelInstance<kernel::ICGrepKernel>(idb, mREs[i], externalStreamNames, std::vector<cc::Alphabet *>(), cc::BitNumbering::BigEndian);
436            mGrepDriver->makeKernelCall(icgrepK, icgrepInputSets, {MatchResults});
437            MatchResultsBufs[i] = MatchResults;
438        }
439    }
440
441    StreamSetBuffer * MergedResults = MatchResultsBufs[0];
442    if (mREs.size() > 1) {
443        MergedResults = mGrepDriver->addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
444        kernel::Kernel * streamsMergeK = mGrepDriver->addKernelInstance<kernel::StreamsMerge>(idb, 1, mREs.size());
445        mGrepDriver->makeKernelCall(streamsMergeK, MatchResultsBufs, {MergedResults});
446    }
447    StreamSetBuffer * Matches = MergedResults;
448    if (mMoveMatchesToEOL) {
449        StreamSetBuffer * OriginalMatches = Matches;
450        kernel::Kernel * matchedLinesK = mGrepDriver->addKernelInstance<kernel::MatchedLinesKernel>(idb);
451        Matches = mGrepDriver->addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
452        mGrepDriver->makeKernelCall(matchedLinesK, {OriginalMatches, LineBreakStream}, {Matches});
453    }
454
455    if (MaxCountFlag > 0) {
456        kernel::Kernel * untilK = mGrepDriver->addKernelInstance<kernel::UntilNkernel>(idb);
457        untilK->setInitialArguments({idb->getSize(MaxCountFlag)});
458        StreamSetBuffer * const AllMatches = Matches;
459        Matches = mGrepDriver->addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
460        mGrepDriver->makeKernelCall(untilK, {AllMatches}, {Matches});
461    }
462
463    return std::pair<StreamSetBuffer *, StreamSetBuffer *>(LineBreakStream, Matches);
464
465}
466
467void LZ4GrepGenerator::invokeScanMatchGrep(char* fileBuffer, size_t blockStart, size_t blockEnd, bool hasBlockChecksum) {
468    auto main = this->getScanMatchGrepMainFunction();
469    std::ostringstream s;
470    EmitMatch accum("", false, false, s);
471
472    main(fileBuffer, blockStart, blockEnd, hasBlockChecksum, reinterpret_cast<intptr_t>(&accum));
473    llvm::outs() << s.str();
474}
475
476void LZ4GrepGenerator::generateScanMatchGrepPipeline(re::RE* regex) {
477    auto & iBuilder = mPxDriver.getBuilder();
478    this->generateScanMatchMainFunc(iBuilder);
479
480    StreamSetBuffer* compressedByteStream = this->loadByteStream();
481
482    StreamSetBuffer * const uncompressedByteStream = this->byteStreamDecompression(compressedByteStream);
483
484    StreamSetBuffer * uncompressedBitStream = mPxDriver.addBuffer<StaticBuffer>(iBuilder, iBuilder->getStreamSetTy(8),
485                                                                                this->getDefaultBufferBlocks());
486    Kernel * s2pk = mPxDriver.addKernelInstance<S2PKernel>(iBuilder, cc::BitNumbering::BigEndian);
487    mPxDriver.makeKernelCall(s2pk, {uncompressedByteStream}, {uncompressedBitStream});
488
489    StreamSetBuffer * LineBreakStream;
490    StreamSetBuffer * Matches;
491    std::vector<re::RE*> res = {regex};
492    std::tie(LineBreakStream, Matches) = grepPipeline(res, uncompressedBitStream);
493
494    kernel::Kernel * scanMatchK = mPxDriver.addKernelInstance<kernel::ScanMatchKernel>(iBuilder);
495    scanMatchK->setInitialArguments({match_accumulator});
496    mPxDriver.makeKernelCall(scanMatchK, {Matches, LineBreakStream, uncompressedByteStream}, {});
497    mPxDriver.LinkFunction(*scanMatchK, "accumulate_match_wrapper", &accumulate_match_wrapper);
498    mPxDriver.LinkFunction(*scanMatchK, "finalize_match_wrapper", &finalize_match_wrapper);
499
500    mPxDriver.generatePipelineIR();
501    mPxDriver.deallocateBuffers();
502
503    iBuilder->CreateRetVoid();
504
505    mPxDriver.finalizeObject();
506}
507
508void LZ4GrepGenerator::generateMultiplexingSwizzledAioPipeline(re::RE *regex) {
509    auto & iBuilder = mPxDriver.getBuilder();
510    this->generateCountOnlyMainFunc(iBuilder);
511
512    // GeneratePipeline
513    StreamSetBuffer *compressedByteStream = nullptr, *compressedBasisBits = nullptr;
514    std::tie(compressedByteStream, compressedBasisBits) = this->loadByteStreamAndBitStream();
515
516    StreamSetBuffer * LineBreakStream;
517    StreamSetBuffer * Matches;
518    std::vector<re::RE*> res = {regex};
519    std::tie(LineBreakStream, Matches) = multiplexingGrepPipeline(res, compressedByteStream, compressedBasisBits, true);
520
521    kernel::Kernel * matchCountK = mPxDriver.addKernelInstance<kernel::PopcountKernel>(iBuilder);
522    mPxDriver.makeKernelCall(matchCountK, {Matches}, {});
523    mPxDriver.generatePipelineIR();
524
525    iBuilder->setKernel(matchCountK);
526    Value * matchedLineCount = iBuilder->getAccumulator("countResult");
527    matchedLineCount = iBuilder->CreateZExt(matchedLineCount, iBuilder->getInt64Ty());
528
529    mPxDriver.deallocateBuffers();
530
531    iBuilder->CreateRet(matchedLineCount);
532
533    mPxDriver.finalizeObject();
534}
535
536void LZ4GrepGenerator::generateByteStreamMultiplexingAioPipeline(re::RE* regex) {
537    auto & iBuilder = mPxDriver.getBuilder();
538    this->generateCountOnlyMainFunc(iBuilder);
539
540    StreamSetBuffer *compressedByteStream = nullptr, *compressedBasisBits = nullptr;
541    std::tie(compressedByteStream, compressedBasisBits) = this->loadByteStreamAndBitStream();
542
543    StreamSetBuffer * LineBreakStream;
544    StreamSetBuffer * Matches;
545    std::vector<re::RE*> res = {regex};
546    std::tie(LineBreakStream, Matches) = multiplexingGrepPipeline(res, compressedByteStream, compressedBasisBits, false, true);
547
548    kernel::Kernel * matchCountK = mPxDriver.addKernelInstance<kernel::PopcountKernel>(iBuilder);
549    mPxDriver.makeKernelCall(matchCountK, {Matches}, {});
550    mPxDriver.generatePipelineIR();
551
552    iBuilder->setKernel(matchCountK);
553    Value * matchedLineCount = iBuilder->getAccumulator("countResult");
554    matchedLineCount = iBuilder->CreateZExt(matchedLineCount, iBuilder->getInt64Ty());
555
556    mPxDriver.deallocateBuffers();
557
558    iBuilder->CreateRet(matchedLineCount);
559
560    mPxDriver.finalizeObject();
561}
562
563
564void LZ4GrepGenerator::generateMultiplexingBitStreamAioPipeline(re::RE* regex) {
565    auto & iBuilder = mPxDriver.getBuilder();
566    this->generateCountOnlyMainFunc(iBuilder);
567
568    StreamSetBuffer *compressedByteStream = nullptr, *compressedBasisBits = nullptr;
569    std::tie(compressedByteStream, compressedBasisBits) = this->loadByteStreamAndBitStream();
570
571    StreamSetBuffer * LineBreakStream;
572    StreamSetBuffer * Matches;
573    std::vector<re::RE*> res = {regex};
574    std::tie(LineBreakStream, Matches) = multiplexingGrepPipeline(res, compressedByteStream, compressedBasisBits, false);
575
576    kernel::Kernel * matchCountK = mPxDriver.addKernelInstance<kernel::PopcountKernel>(iBuilder);
577    mPxDriver.makeKernelCall(matchCountK, {Matches}, {});
578    mPxDriver.generatePipelineIR();
579
580    iBuilder->setKernel(matchCountK);
581    Value * matchedLineCount = iBuilder->getAccumulator("countResult");
582    matchedLineCount = iBuilder->CreateZExt(matchedLineCount, iBuilder->getInt64Ty());
583
584    mPxDriver.deallocateBuffers();
585
586    iBuilder->CreateRet(matchedLineCount);
587
588    mPxDriver.finalizeObject();
589}
590
591void LZ4GrepGenerator::generateBitStreamAioPipeline(re::RE* regex) {
592    auto & iBuilder = mPxDriver.getBuilder();
593    this->generateCountOnlyMainFunc(iBuilder);
594
595    StreamSetBuffer *compressedByteStream = nullptr, *compressedBasisBits = nullptr;
596    std::tie(compressedByteStream, compressedBasisBits) = this->loadByteStreamAndBitStream();
597
598    StreamSetBuffer * const decompressionBitStream = this->bitStreamDecompression(compressedByteStream, compressedBasisBits);
599
600    StreamSetBuffer * LineBreakStream;
601    StreamSetBuffer * Matches;
602    std::vector<re::RE*> res = {regex};
603    std::tie(LineBreakStream, Matches) = grepPipeline(res, decompressionBitStream);
604
605    kernel::Kernel * matchCountK = mPxDriver.addKernelInstance<kernel::PopcountKernel>(iBuilder);
606
607    mPxDriver.makeKernelCall(matchCountK, {Matches}, {});
608    mPxDriver.generatePipelineIR();
609
610    iBuilder->setKernel(matchCountK);
611    Value * matchedLineCount = iBuilder->getAccumulator("countResult");
612    matchedLineCount = iBuilder->CreateZExt(matchedLineCount, iBuilder->getInt64Ty());
613    mPxDriver.deallocateBuffers();
614
615    iBuilder->CreateRet(matchedLineCount);
616
617    mPxDriver.finalizeObject();
618}
619
620void LZ4GrepGenerator::generateSwizzledAioPipeline(re::RE* regex) {
621    auto & iBuilder = mPxDriver.getBuilder();
622    this->generateCountOnlyMainFunc(iBuilder);
623
624    StreamSetBuffer *compressedByteStream = nullptr, *compressedBasisBits = nullptr;
625    std::tie(compressedByteStream, compressedBasisBits) = this->loadByteStreamAndBitStream();
626
627    StreamSetBuffer * const decompressionBitStream = this->swizzledDecompression(compressedByteStream, compressedBasisBits);
628
629    StreamSetBuffer * LineBreakStream;
630    StreamSetBuffer * Matches;
631    std::vector<re::RE*> res = {regex};
632    std::tie(LineBreakStream, Matches) = grepPipeline(res, decompressionBitStream);
633
634    kernel::Kernel * matchCountK = mPxDriver.addKernelInstance<kernel::PopcountKernel>(iBuilder);
635
636    mPxDriver.makeKernelCall(matchCountK, {Matches}, {});
637    mPxDriver.generatePipelineIR();
638
639    iBuilder->setKernel(matchCountK);
640    Value * matchedLineCount = iBuilder->getAccumulator("countResult");
641    matchedLineCount = iBuilder->CreateZExt(matchedLineCount, iBuilder->getInt64Ty());
642    mPxDriver.deallocateBuffers();
643
644    iBuilder->CreateRet(matchedLineCount);
645
646    mPxDriver.finalizeObject();
647}
648
649void LZ4GrepGenerator::generateParallelAioPipeline(re::RE* regex, bool enableGather, bool enableScatter, int minParallelLevel) {
650    auto & iBuilder = mPxDriver.getBuilder();
651    this->generateCountOnlyMainFunc(iBuilder);
652
653    StreamSetBuffer* compressedByteStream = this->loadByteStream();
654    parabix::StreamSetBuffer * uncompressedByteStream = this->parallelByteStreamDecompression(compressedByteStream, enableGather,
655                                                                                              enableScatter,
656                                                                                              minParallelLevel);
657
658
659    StreamSetBuffer * const uncompressedBitStream = mPxDriver.addBuffer<StaticBuffer>(iBuilder, iBuilder->getStreamSetTy(8, 1),
660                                                                                       this->getDefaultBufferBlocks());
661    Kernel * s2pk = mPxDriver.addKernelInstance<S2PKernel>(iBuilder, cc::BitNumbering::BigEndian, /*aligned = */ true, "a");
662    mPxDriver.makeKernelCall(s2pk, {uncompressedByteStream}, {uncompressedBitStream});
663
664
665    StreamSetBuffer * LineBreakStream;
666    StreamSetBuffer * Matches;
667    std::vector<re::RE*> res = {regex};
668    std::tie(LineBreakStream, Matches) = grepPipeline(res, uncompressedBitStream);
669
670
671    kernel::Kernel * matchCountK = mPxDriver.addKernelInstance<kernel::PopcountKernel>(iBuilder);
672    mPxDriver.makeKernelCall(matchCountK, {Matches}, {});
673    mPxDriver.generatePipelineIR();
674
675    iBuilder->setKernel(matchCountK);
676    Value * matchedLineCount = iBuilder->getAccumulator("countResult");
677    matchedLineCount = iBuilder->CreateZExt(matchedLineCount, iBuilder->getInt64Ty());
678
679    mPxDriver.deallocateBuffers();
680
681    iBuilder->CreateRet(matchedLineCount);
682
683    mPxDriver.finalizeObject();
684}
685
686
687
688void LZ4GrepGenerator::generateAioPipeline(re::RE *regex) {
689    auto & iBuilder = mPxDriver.getBuilder();
690    this->generateCountOnlyMainFunc(iBuilder);
691
692    // GeneratePipeline
693    StreamSetBuffer* compressedByteStream = this->loadByteStream();
694//    this->loadByteStreamAndBitStream(iBuilder);
695
696    parabix::StreamSetBuffer * uncompressedByteStream = this->byteStreamDecompression(compressedByteStream);
697
698
699    StreamSetBuffer * const uncompressedBitStream = mPxDriver.addBuffer<StaticBuffer>(iBuilder, iBuilder->getStreamSetTy(8, 1),
700                                                                                       this->getDefaultBufferBlocks());
701    Kernel * s2pk = mPxDriver.addKernelInstance<S2PKernel>(iBuilder, cc::BitNumbering::BigEndian, /*aligned = */ true, "a");
702    mPxDriver.makeKernelCall(s2pk, {uncompressedByteStream}, {uncompressedBitStream});
703
704
705    StreamSetBuffer * LineBreakStream;
706    StreamSetBuffer * Matches;
707
708    std::vector<re::RE*> res = {regex};
709    std::tie(LineBreakStream, Matches) = grepPipeline(res, uncompressedBitStream);
710
711    kernel::Kernel * matchCountK = mPxDriver.addKernelInstance<kernel::PopcountKernel>(iBuilder);
712    mPxDriver.makeKernelCall(matchCountK, {Matches}, {});
713    mPxDriver.generatePipelineIR();
714
715    iBuilder->setKernel(matchCountK);
716    Value * matchedLineCount = iBuilder->getAccumulator("countResult");
717    matchedLineCount = iBuilder->CreateZExt(matchedLineCount, iBuilder->getInt64Ty());
718
719    mPxDriver.deallocateBuffers();
720
721    iBuilder->CreateRet(matchedLineCount);
722
723    mPxDriver.finalizeObject();
724
725}
726
727
728ScanMatchGrepMainFunctionType LZ4GrepGenerator::getScanMatchGrepMainFunction() {
729    return reinterpret_cast<ScanMatchGrepMainFunctionType>(mPxDriver.getMain());
730}
731CountOnlyGrepMainFunctionType LZ4GrepGenerator::getCountOnlyGrepMainFunction() {
732    return reinterpret_cast<CountOnlyGrepMainFunctionType>(mPxDriver.getMain());
733}
734
735void LZ4GrepGenerator::generateCountOnlyMainFunc(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) {
736    Module * M = iBuilder->getModule();
737    Type * const int64Ty = iBuilder->getInt64Ty();
738    Type * const sizeTy = iBuilder->getSizeTy();
739    Type * const boolTy = iBuilder->getIntNTy(sizeof(bool) * 8);
740//    Type * const voidTy = iBuilder->getVoidTy();
741    Type * const inputType = iBuilder->getInt8PtrTy();
742
743    Function * const main = cast<Function>(M->getOrInsertFunction("Main", int64Ty, inputType, sizeTy, sizeTy, boolTy, nullptr));
744    main->setCallingConv(CallingConv::C);
745    Function::arg_iterator args = main->arg_begin();
746    mInputStream = &*(args++);
747    mInputStream->setName("input");
748
749    mHeaderSize = &*(args++);
750    mHeaderSize->setName("mHeaderSize");
751
752    mFileSize = &*(args++);
753    mFileSize->setName("mFileSize");
754
755    mHasBlockChecksum = &*(args++);
756    mHasBlockChecksum->setName("mHasBlockChecksum");
757    // TODO for now, we do not handle blockCheckSum
758    mHasBlockChecksum = iBuilder->getInt1(false);
759
760    iBuilder->SetInsertPoint(BasicBlock::Create(M->getContext(), "entry", main, 0));
761}
762
763void LZ4GrepGenerator::generateScanMatchMainFunc(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) {
764    Module * M = iBuilder->getModule();
765    Type * const sizeTy = iBuilder->getSizeTy();
766    Type * const boolTy = iBuilder->getIntNTy(sizeof(bool) * 8);
767    Type * const voidTy = iBuilder->getVoidTy();
768    Type * const inputType = iBuilder->getInt8PtrTy();
769    Type * const intAddrTy = iBuilder->getIntAddrTy();
770
771    Function * const main = cast<Function>(M->getOrInsertFunction("Main", voidTy, inputType, sizeTy, sizeTy, boolTy, intAddrTy, nullptr));
772    main->setCallingConv(CallingConv::C);
773    Function::arg_iterator args = main->arg_begin();
774    mInputStream = &*(args++);
775    mInputStream->setName("input");
776
777    mHeaderSize = &*(args++);
778    mHeaderSize->setName("mHeaderSize");
779
780    mFileSize = &*(args++);
781    mFileSize->setName("mFileSize");
782
783    mHasBlockChecksum = &*(args++);
784    mHasBlockChecksum->setName("mHasBlockChecksum");
785
786    match_accumulator = &*(args++);
787    match_accumulator->setName("match_accumulator");
788
789    iBuilder->SetInsertPoint(BasicBlock::Create(M->getContext(), "entry", main, 0));
790}
Note: See TracBrowser for help on using the repository browser.