source: icGREP/icgrep-devel/icgrep/grep/grep_engine.cpp @ 5934

Last change on this file since 5934 was 5934, checked in by cameron, 12 months ago

Multithreaded simple RE mode initial check-in

File size: 33.0 KB
Line 
1/*
2 *  Copyright (c) 2018 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6#include <set>
7#include "grep_engine.h"
8#include "grep_interface.h"
9#include <llvm/IR/Module.h>
10#include <boost/filesystem.hpp>
11#include <UCD/resolve_properties.h>
12#include <kernels/charclasses.h>
13#include <kernels/cc_kernel.h>
14#include <kernels/grep_kernel.h>
15#include <kernels/UCD_property_kernel.h>
16#include <kernels/grapheme_kernel.h>
17#include <kernels/linebreak_kernel.h>
18#include <kernels/streams_merge.h>
19#include <kernels/source_kernel.h>
20#include <kernels/s2p_kernel.h>
21#include <kernels/scanmatchgen.h>
22#include <kernels/streamset.h>
23#include <kernels/until_n.h>
24#include <kernels/kernel_builder.h>
25#include <pablo/pablo_kernel.h>
26#include <cc/alphabet.h>
27#include <re/re_cc.h>
28#include <re/re_name.h>
29#include <re/casing.h>
30#include <re/exclude_CC.h>
31#include <re/to_utf8.h>
32#include <re/re_toolchain.h>
33#include <toolchain/toolchain.h>
34#include <re/re_analysis.h>
35#include <re/re_name_resolve.h>
36#include <re/re_name_gather.h>
37#include <re/collect_ccs.h>
38#include <re/replaceCC.h>
39#include <re/re_multiplex.h>
40#include <re/grapheme_clusters.h>
41#include <re/printer_re.h>
42#include <toolchain/toolchain.h>
43#include <toolchain/cpudriver.h>
44#include <iostream>
45#include <cc/multiplex_CCs.h>
46#include <llvm/Support/raw_ostream.h>
47#include <util/aligned_allocator.h>
48#include <sys/stat.h>
49#include <fcntl.h>
50#include <errno.h>
51#include <llvm/ADT/STLExtras.h> // for make_unique
52#include <llvm/Support/CommandLine.h>
53#include <llvm/Support/Debug.h>
54#include <sched.h>
55
56using namespace parabix;
57using namespace llvm;
58using namespace cc;
59using namespace kernel;
60
61static cl::opt<int> Threads("t", cl::desc("Total number of threads."), cl::init(2));
62static cl::opt<bool> PabloTransposition("enable-pablo-s2p", cl::desc("Enable experimental pablo transposition."));
63static cl::opt<bool> CC_Multiplexing("CC-multiplexing", cl::desc("Enable CC multiplexing."), cl::init(false));
64static cl::opt<bool> PropertyKernels("enable-property-kernels", cl::desc("Enable Unicode property kernels."), cl::init(false));
65static cl::opt<bool> MultithreadedSimpleRE("enable-simple-RE-kernels", cl::desc("Enable individual CC kernels for simple REs."), cl::init(false));
66const unsigned DefaultByteCClimit = 6;
67
68static cl::opt<unsigned> ByteCClimit("byte-CC-limit", cl::desc("Max number of CCs for byte CC pipeline."), cl::init(DefaultByteCClimit));
69
70
71namespace grep {
72   
73
74extern "C" void accumulate_match_wrapper(intptr_t accum_addr, const size_t lineNum, char * line_start, char * line_end) {
75    reinterpret_cast<MatchAccumulator *>(accum_addr)->accumulate_match(lineNum, line_start, line_end);
76}
77
78extern "C" void finalize_match_wrapper(intptr_t accum_addr, char * buffer_end) {
79    reinterpret_cast<MatchAccumulator *>(accum_addr)->finalize_match(buffer_end);
80}
81
82void grepBuffer(re::RE * pattern, const char * search_buffer, size_t bufferLength, MatchAccumulator * accum) {
83    const unsigned segmentSize = codegen::BufferSegments * codegen::SegmentSize * codegen::ThreadNum;
84    auto segParallelModeSave = codegen::SegmentPipelineParallel;
85    codegen::SegmentPipelineParallel = false;
86   
87    pattern = resolveCaseInsensitiveMode(pattern, false);
88    pattern = regular_expression_passes(pattern);
89    pattern = re::exclude_CC(pattern, re::makeByte(0x0A));
90    pattern = resolveAnchors(pattern, re::makeByte(0x0A));
91
92    ParabixDriver pxDriver("codepointEngine");
93    auto & idb = pxDriver.getBuilder();
94    Module * M = idb->getModule();
95   
96    Function * mainFunc = cast<Function>(M->getOrInsertFunction("Main", idb->getVoidTy(), idb->getInt8PtrTy(), idb->getSizeTy(), nullptr));
97    mainFunc->setCallingConv(CallingConv::C);
98    auto args = mainFunc->arg_begin();
99    Value * const buffer = &*(args++);
100    buffer->setName("buffer");
101    Value * length = &*(args++);
102    length->setName("length");
103   
104    idb->SetInsertPoint(BasicBlock::Create(M->getContext(), "entry", mainFunc, 0));
105    StreamSetBuffer * ByteStream = pxDriver.addBuffer<SourceBuffer>(idb, idb->getStreamSetTy(1, 8));
106    kernel::Kernel * sourceK = pxDriver.addKernelInstance<kernel::MemorySourceKernel>(idb, idb->getInt8PtrTy());
107    sourceK->setInitialArguments({buffer, length});
108    pxDriver.makeKernelCall(sourceK, {}, {ByteStream});
109   
110   
111    StreamSetBuffer * BasisBits = pxDriver.addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(8, 1), segmentSize);
112    kernel::Kernel * s2pk = pxDriver.addKernelInstance<kernel::S2PKernel>(idb);
113    pxDriver.makeKernelCall(s2pk, {ByteStream}, {BasisBits});
114   
115    StreamSetBuffer * LineFeedStream = pxDriver.addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), segmentSize);
116    kernel::Kernel * linefeedK = pxDriver.addKernelInstance<kernel::LineFeedKernelBuilder>(idb, Binding{idb->getStreamSetTy(8), "basis", FixedRate(), Principal()});
117    pxDriver.makeKernelCall(linefeedK, {BasisBits}, {LineFeedStream});
118   
119    StreamSetBuffer * LineBreakStream = pxDriver.addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), segmentSize);
120   
121    kernel::Kernel * requiredStreamsK = pxDriver.addKernelInstance<kernel::RequiredStreams_UTF8>(idb);
122    StreamSetBuffer * RequiredStreams = pxDriver.addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), segmentSize);
123    pxDriver.makeKernelCall(requiredStreamsK, {BasisBits, LineFeedStream}, {RequiredStreams, LineBreakStream});
124   
125    StreamSetBuffer * MatchResults = pxDriver.addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), segmentSize);
126    kernel::Kernel * icgrepK = pxDriver.addKernelInstance<kernel::ICGrepKernel>(idb, pattern, std::vector<std::string>{"UTF8_LB", "UTF8_nonfinal"});
127    pxDriver.makeKernelCall(icgrepK, {BasisBits, LineBreakStream, RequiredStreams}, {MatchResults});
128   
129    StreamSetBuffer * MatchedLines = pxDriver.addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), segmentSize);
130    kernel::Kernel * matchedLinesK = pxDriver.addKernelInstance<kernel::MatchedLinesKernel>(idb);
131    pxDriver.makeKernelCall(matchedLinesK, {MatchResults, LineBreakStream}, {MatchedLines});
132   
133    kernel::Kernel * scanMatchK = pxDriver.addKernelInstance<kernel::ScanMatchKernel>(idb);
134    scanMatchK->setInitialArguments({ConstantInt::get(idb->getIntAddrTy(), reinterpret_cast<intptr_t>(accum))});
135    pxDriver.makeKernelCall(scanMatchK, {MatchedLines, LineBreakStream, ByteStream}, {});
136    pxDriver.LinkFunction(*scanMatchK, "accumulate_match_wrapper", &accumulate_match_wrapper);
137    pxDriver.LinkFunction(*scanMatchK, "finalize_match_wrapper", &finalize_match_wrapper);
138   
139    pxDriver.generatePipelineIR();
140    pxDriver.deallocateBuffers();
141    idb->CreateRetVoid();
142    pxDriver.finalizeObject();
143   
144    typedef void (*GrepFunctionType)(const char * buffer, const size_t length);
145    auto f = reinterpret_cast<GrepFunctionType>(pxDriver.getMain());
146    f(search_buffer, bufferLength);
147    codegen::SegmentPipelineParallel = segParallelModeSave;
148}
149
150
151
152// Grep Engine construction and initialization.
153
154GrepEngine::GrepEngine() :
155    mGrepDriver(nullptr),
156    mNextFileToGrep(0),
157    mNextFileToPrint(0),
158    grepMatchFound(false),
159    mGrepRecordBreak(GrepRecordBreakKind::LF),
160    mMoveMatchesToEOL(true),
161    mEngineThread(pthread_self()) {}
162
163GrepEngine::~GrepEngine() {
164    delete mGrepDriver;
165}
166
167QuietModeEngine::QuietModeEngine() : GrepEngine() {
168    mMoveMatchesToEOL = false;
169}
170
171MatchOnlyEngine::MatchOnlyEngine(bool showFilesWithoutMatch) :
172    GrepEngine(), mRequiredCount(showFilesWithoutMatch) {
173    mFileSuffix = NullFlag ? std::string("\0", 1) : "\n";
174    mMoveMatchesToEOL = false;
175}
176
177CountOnlyEngine::CountOnlyEngine() : GrepEngine() {
178    mFileSuffix = ":";
179}
180
181EmitMatchesEngine::EmitMatchesEngine() : GrepEngine() {
182    mFileSuffix = InitialTabFlag ? "\t:" : ":";
183    if (LineRegexpFlag) mMoveMatchesToEOL = false;
184}
185
186   
187void GrepEngine::setRecordBreak(GrepRecordBreakKind b) {
188    mGrepRecordBreak = b;
189}
190
191   
192
193   
194void GrepEngine::initFileResult(std::vector<std::string> & filenames) {
195    const unsigned n = filenames.size();
196    mResultStrs.resize(n);
197    mFileStatus.resize(n, FileStatus::Pending);
198    inputFiles = filenames;
199}
200
201void GrepEngine::initREs(std::vector<re::RE *> & REs) {
202    if (mGrepRecordBreak == GrepRecordBreakKind::Unicode) {
203        mBreakCC = re::makeCC(re::makeCC(0x0A, 0x0D), re::makeCC(re::makeCC(0x85), re::makeCC(0x2028, 0x2029)));
204    } else if (mGrepRecordBreak == GrepRecordBreakKind::Null) {
205        mBreakCC = re::makeByte(0);  // Null
206    } else {
207        mBreakCC = re::makeByte(0x0A); // LF
208    }
209    re::RE * anchorRE = mBreakCC;
210    if (mGrepRecordBreak == GrepRecordBreakKind::Unicode) {
211        re::Name * anchorName = re::makeName("UTF8_LB", re::Name::Type::Unicode);
212        anchorName->setDefinition(UCD::UnicodeBreakRE());
213        anchorRE = anchorName;
214    }
215   
216    mREs = REs;
217    bool allAnchored = true;
218    for(unsigned i = 0; i < mREs.size(); ++i) {
219        if (!hasEndAnchor(mREs[i])) allAnchored = false;
220        mREs[i] = resolveModesAndExternalSymbols(mREs[i]);
221        mREs[i] = re::exclude_CC(mREs[i], mBreakCC);
222        mREs[i] = resolveAnchors(mREs[i], anchorRE);
223        re::gatherUnicodeProperties(mREs[i], mUnicodeProperties);
224        mREs[i] = regular_expression_passes(mREs[i]);
225    }
226    if (allAnchored && (mGrepRecordBreak != GrepRecordBreakKind::Unicode)) mMoveMatchesToEOL = false;
227
228}
229
230
231   
232// Code Generation
233//
234// All engines share a common pipeline to compute a stream of Matches from a given input Bytestream.
235
236unsigned LLVM_READNONE calculateMaxCountRate(const std::unique_ptr<kernel::KernelBuilder> & b) {
237    const unsigned packSize = b->getSizeTy()->getBitWidth();
238    return (packSize * packSize) / b->getBitBlockWidth();
239}
240   
241std::pair<StreamSetBuffer *, StreamSetBuffer *> GrepEngine::grepPipeline(StreamSetBuffer * ByteStream) {
242    auto & idb = mGrepDriver->getBuilder();
243    const unsigned segmentSize = codegen::SegmentSize;
244    const unsigned bufferSegments = codegen::BufferSegments * codegen::ThreadNum;
245    // TODO: until we automate stream buffer sizing, use this calculation to determine how large our matches buffer needs to be.
246    const unsigned baseBufferSize = segmentSize * (MaxCountFlag > 0 ? (std::max(bufferSegments, calculateMaxCountRate(idb))) : bufferSegments);
247    const unsigned encodingBits = 8;
248   
249   
250    //  Regular Expression Processing and Analysis Phase
251    const auto nREs = mREs.size();
252    bool hasGCB[nREs];
253    bool anyGCB = false;
254
255    for(unsigned i = 0; i < nREs; ++i) {
256        hasGCB[i] = hasGraphemeClusterBoundary(mREs[i]);
257        anyGCB |= hasGCB[i];
258    }
259    StreamSetBuffer * LineBreakStream = mGrepDriver->addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
260    std::vector<StreamSetBuffer *> MatchResultsBufs(nREs);
261   
262    re::RE * prefixRE;
263    re::RE * suffixRE;
264    // For simple regular expressions with a small number of characters, we
265    // can bypass transposition and use the Direct CC compiler.
266    bool isSimple = (nREs == 1) && (mGrepRecordBreak != GrepRecordBreakKind::Unicode) && (!anyGCB);
267    if (isSimple) {
268        mREs[0] = toUTF8(mREs[0]);
269    }
270    if (isSimple && byteTestsWithinLimit(mREs[0], ByteCClimit)) {
271        std::vector<std::string> externalStreamNames;
272        std::vector<StreamSetBuffer *> icgrepInputSets = {ByteStream};
273        if (MultithreadedSimpleRE) {
274            auto CCs = re::collectCCs(mREs[0], &cc::Byte);
275            for (auto cc : CCs) {
276                auto ccName = makeName(cc);
277                mREs[0] = re::replaceCC(mREs[0], cc, ccName);
278                std::string ccNameStr = ccName->getFullName();
279                errs () << "Replacing: " << ccNameStr << "\n";
280                StreamSetBuffer * ccStream = mGrepDriver->addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
281                kernel::Kernel * ccK = mGrepDriver->addKernelInstance<kernel::DirectCharacterClassKernelBuilder>(idb, ccNameStr, std::vector<re::CC *>{cc}, 1);
282                mGrepDriver->makeKernelCall(ccK, {ByteStream}, {ccStream});
283                externalStreamNames.push_back(ccNameStr);
284                icgrepInputSets.push_back(ccStream);
285            }
286        }
287        StreamSetBuffer * MatchResults = mGrepDriver->addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
288        kernel::Kernel * icgrepK = mGrepDriver->addKernelInstance<kernel::ByteGrepKernel>(idb, mREs[0], externalStreamNames);
289        mGrepDriver->makeKernelCall(icgrepK, icgrepInputSets, {MatchResults});
290        MatchResultsBufs[0] = MatchResults;
291        kernel::Kernel * breakK = mGrepDriver->addKernelInstance<kernel::DirectCharacterClassKernelBuilder>(idb, "breakCC", std::vector<re::CC *>{mBreakCC}, 1);
292        mGrepDriver->makeKernelCall(breakK, {ByteStream}, {LineBreakStream});
293    } else if (isSimple && hasTriCCwithinLimit(mREs[0], ByteCClimit, prefixRE, suffixRE)) {
294        StreamSetBuffer * MatchResults = mGrepDriver->addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
295        kernel::Kernel * icgrepK = mGrepDriver->addKernelInstance<kernel::ByteBitGrepKernel>(idb, prefixRE, suffixRE);
296        mGrepDriver->makeKernelCall(icgrepK, {ByteStream}, {MatchResults});
297        MatchResultsBufs[0] = MatchResults;
298        kernel::Kernel * breakK = mGrepDriver->addKernelInstance<kernel::DirectCharacterClassKernelBuilder>(idb, "breakCC", std::vector<re::CC *>{mBreakCC}, 1);
299        mGrepDriver->makeKernelCall(breakK, {ByteStream}, {LineBreakStream});
300    } else {
301       
302        StreamSetBuffer * BasisBits = mGrepDriver->addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(encodingBits, 1), baseBufferSize);
303        kernel::Kernel * s2pk = nullptr;
304        if (PabloTransposition) {
305            s2pk = mGrepDriver->addKernelInstance<kernel::S2P_PabloKernel>(idb);
306        }
307        else {
308            s2pk = mGrepDriver->addKernelInstance<kernel::S2PKernel>(idb);
309        }
310        mGrepDriver->makeKernelCall(s2pk, {ByteStream}, {BasisBits});
311
312        StreamSetBuffer * RequiredStreams = mGrepDriver->addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
313        StreamSetBuffer * UnicodeLB = mGrepDriver->addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
314
315        StreamSetBuffer * LineFeedStream = mGrepDriver->addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
316        kernel::Kernel * linefeedK = mGrepDriver->addKernelInstance<kernel::LineFeedKernelBuilder>(idb, Binding{idb->getStreamSetTy(8), "basis", FixedRate(), Principal()});
317        mGrepDriver->makeKernelCall(linefeedK, {BasisBits}, {LineFeedStream});
318       
319        kernel::Kernel * requiredStreamsK = mGrepDriver->addKernelInstance<kernel::RequiredStreams_UTF8>(idb);
320        mGrepDriver->makeKernelCall(requiredStreamsK, {BasisBits, LineFeedStream}, {RequiredStreams, UnicodeLB});
321
322        if (mGrepRecordBreak == GrepRecordBreakKind::LF) {
323            LineBreakStream = LineFeedStream;
324        } else if (mGrepRecordBreak == GrepRecordBreakKind::Null) {
325            kernel::Kernel * breakK = mGrepDriver->addKernelInstance<kernel::ParabixCharacterClassKernelBuilder>(idb, "Null", std::vector<re::CC *>{mBreakCC}, 8);
326            mGrepDriver->makeKernelCall(breakK, {BasisBits}, {LineBreakStream});
327        } else {
328            LineBreakStream = UnicodeLB;
329        }
330       
331        std::map<std::string, StreamSetBuffer *> propertyStream;
332        if (PropertyKernels) {
333            for (auto p : mUnicodeProperties) {
334                auto name = p->getFullName();
335                StreamSetBuffer * s = mGrepDriver->addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
336                propertyStream.emplace(std::make_pair(name, s));
337                kernel::Kernel * propertyK = mGrepDriver->addKernelInstance<kernel::UnicodePropertyKernelBuilder>(idb, p);
338                mGrepDriver->makeKernelCall(propertyK, {BasisBits}, {s});
339            }
340        }
341        StreamSetBuffer * GCB_stream = nullptr;
342        if (anyGCB) {
343            GCB_stream = mGrepDriver->addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
344            kernel::Kernel * gcbK = mGrepDriver->addKernelInstance<kernel::GraphemeClusterBreakKernel>(idb);
345            mGrepDriver->makeKernelCall(gcbK, {BasisBits, RequiredStreams}, {GCB_stream});
346        }
347
348        for(unsigned i = 0; i < nREs; ++i) {
349            std::vector<std::string> externalStreamNames;
350            std::vector<StreamSetBuffer *> icgrepInputSets = {BasisBits};
351            if (mGrepRecordBreak == GrepRecordBreakKind::Unicode) {
352                externalStreamNames.push_back("UTF8_LB");
353                icgrepInputSets.push_back(LineBreakStream);
354                externalStreamNames.push_back("UTF8_nonfinal");
355                icgrepInputSets.push_back(RequiredStreams);
356            }
357            std::set<re::Name *> UnicodeProperties;
358            if (PropertyKernels) {
359                re::gatherUnicodeProperties(mREs[i], UnicodeProperties);
360                for (auto p : UnicodeProperties) {
361                    auto name = p->getFullName();
362                    auto f = propertyStream.find(name);
363                    if (f == propertyStream.end()) report_fatal_error(name + " not found\n");
364                    externalStreamNames.push_back(name);
365                    icgrepInputSets.push_back(f->second);
366                }
367            }
368            if (hasGCB[i]) {
369                externalStreamNames.push_back("\\b{g}");
370                icgrepInputSets.push_back(GCB_stream);
371            }
372            if (CC_Multiplexing) {
373                const auto UnicodeSets = re::collectCCs(mREs[i], &cc::Unicode, std::set<re::Name *>({re::makeZeroWidth("\\b{g}")}));
374                StreamSetBuffer * const MatchResults = mGrepDriver->addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
375                if (UnicodeSets.size() <= 1) {
376                    kernel::Kernel * icgrepK = mGrepDriver->addKernelInstance<kernel::ICGrepKernel>(idb, mREs[i], externalStreamNames);
377                    mGrepDriver->makeKernelCall(icgrepK, icgrepInputSets, {MatchResults});
378                    MatchResultsBufs[i] = MatchResults;
379                } else {
380                    mpx = make_unique<MultiplexedAlphabet>("mpx", UnicodeSets);
381                    mREs[i] = transformCCs(mpx.get(), mREs[i]);
382                    std::vector<re::CC *> mpx_basis = mpx->getMultiplexedCCs();
383                    auto numOfCharacterClasses = mpx_basis.size();
384                    StreamSetBuffer * CharClasses = mGrepDriver->addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(numOfCharacterClasses), baseBufferSize);
385                    kernel::Kernel * ccK = mGrepDriver->addKernelInstance<kernel::CharClassesKernel>(idb, std::move(mpx_basis));
386                    mGrepDriver->makeKernelCall(ccK, {BasisBits}, {CharClasses});
387    //                kernel::Kernel * ccK = mGrepDriver->addKernelInstance<kernel::CharClassesKernel>(idb, std::move(mpx_basis), true);
388    //                mGrepDriver->makeKernelCall(ccK, {ByteStream}, {CharClasses});
389                    kernel::Kernel * icgrepK = mGrepDriver->addKernelInstance<kernel::ICGrepKernel>(idb, mREs[i], externalStreamNames, std::vector<cc::Alphabet *>{mpx.get()});
390                    icgrepInputSets.push_back(CharClasses);
391                    mGrepDriver->makeKernelCall(icgrepK, icgrepInputSets, {MatchResults});
392                    MatchResultsBufs[i] = MatchResults;
393                }
394            } else {
395                StreamSetBuffer * MatchResults = mGrepDriver->addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
396                kernel::Kernel * icgrepK = mGrepDriver->addKernelInstance<kernel::ICGrepKernel>(idb, mREs[i], externalStreamNames);
397                mGrepDriver->makeKernelCall(icgrepK, icgrepInputSets, {MatchResults});
398                MatchResultsBufs[i] = MatchResults;
399            }
400        }
401    }
402
403    StreamSetBuffer * MergedResults = MatchResultsBufs[0];
404    if (mREs.size() > 1) {
405        MergedResults = mGrepDriver->addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
406        kernel::Kernel * streamsMergeK = mGrepDriver->addKernelInstance<kernel::StreamsMerge>(idb, 1, mREs.size());
407        mGrepDriver->makeKernelCall(streamsMergeK, MatchResultsBufs, {MergedResults});
408    }
409    StreamSetBuffer * Matches = MergedResults;
410    if (mMoveMatchesToEOL) {
411        StreamSetBuffer * OriginalMatches = Matches;
412        kernel::Kernel * matchedLinesK = mGrepDriver->addKernelInstance<kernel::MatchedLinesKernel>(idb);
413        Matches = mGrepDriver->addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
414        mGrepDriver->makeKernelCall(matchedLinesK, {OriginalMatches, LineBreakStream}, {Matches});
415    }
416    if (InvertMatchFlag) {
417        kernel::Kernel * invertK = mGrepDriver->addKernelInstance<kernel::InvertMatchesKernel>(idb);
418        StreamSetBuffer * OriginalMatches = Matches;
419        Matches = mGrepDriver->addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
420        mGrepDriver->makeKernelCall(invertK, {OriginalMatches, LineBreakStream}, {Matches});
421    }
422    if (MaxCountFlag > 0) {
423        kernel::Kernel * untilK = mGrepDriver->addKernelInstance<kernel::UntilNkernel>(idb);
424        untilK->setInitialArguments({idb->getSize(MaxCountFlag)});
425        StreamSetBuffer * const AllMatches = Matches;
426        Matches = mGrepDriver->addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), baseBufferSize);
427        mGrepDriver->makeKernelCall(untilK, {AllMatches}, {Matches});
428    }
429
430    return std::pair<StreamSetBuffer *, StreamSetBuffer *>(LineBreakStream, Matches);
431}
432
433// The QuietMode, MatchOnly and CountOnly engines share a common code generation main function,
434// which returns a count of the matches found (possibly subject to a MaxCount).
435//
436
437void GrepEngine::grepCodeGen() {
438
439    assert (mGrepDriver == nullptr);
440    mGrepDriver = new ParabixDriver("engine");
441    auto & idb = mGrepDriver->getBuilder();
442    Module * M = idb->getModule();
443
444    const unsigned encodingBits = 8;
445
446    Function * mainFunc = cast<Function>(M->getOrInsertFunction("Main", idb->getInt64Ty(), idb->getInt8Ty(), idb->getInt32Ty(), nullptr));
447    mainFunc->setCallingConv(CallingConv::C);
448    idb->SetInsertPoint(BasicBlock::Create(M->getContext(), "entry", mainFunc, 0));
449    auto args = mainFunc->arg_begin();
450
451    Value * const useMMap = &*(args++);
452    useMMap->setName("useMMap");
453    Value * const fileDescriptor = &*(args++);
454    fileDescriptor->setName("fileDescriptor");
455
456    StreamSetBuffer * ByteStream = mGrepDriver->addBuffer<SourceBuffer>(idb, idb->getStreamSetTy(1, encodingBits));
457    kernel::Kernel * sourceK = mGrepDriver->addKernelInstance<kernel::FDSourceKernel>(idb);
458    sourceK->setInitialArguments({useMMap, fileDescriptor});
459    mGrepDriver->makeKernelCall(sourceK, {}, {ByteStream});
460
461    StreamSetBuffer * LineBreakStream;
462    StreamSetBuffer * Matches;
463    std::tie(LineBreakStream, Matches) = grepPipeline(ByteStream);
464
465    kernel::Kernel * matchCountK = mGrepDriver->addKernelInstance<kernel::PopcountKernel>(idb);
466    mGrepDriver->makeKernelCall(matchCountK, {Matches}, {});
467    mGrepDriver->generatePipelineIR();
468    idb->setKernel(matchCountK);
469    Value * matchedLineCount = idb->getAccumulator("countResult");
470    matchedLineCount = idb->CreateZExt(matchedLineCount, idb->getInt64Ty());
471    mGrepDriver->deallocateBuffers();
472    idb->CreateRet(matchedLineCount);
473    mGrepDriver->finalizeObject();
474}
475
476//
477// The EmitMatches engine uses an EmitMatchesAccumulator object to concatenate together
478// matched lines.
479
480class EmitMatch : public MatchAccumulator {
481    friend class EmitMatchesEngine;
482public:
483    EmitMatch(std::string linePrefix, std::ostringstream & strm) : mLinePrefix(linePrefix), mLineCount(0), mTerminated(true), mResultStr(strm) {}
484    void accumulate_match(const size_t lineNum, char * line_start, char * line_end) override;
485    void finalize_match(char * buffer_end) override;
486protected:
487    std::string mLinePrefix;
488    size_t mLineCount;
489    bool mTerminated;
490    std::ostringstream & mResultStr;
491};
492
493//
494//  Default Report Match:  lines are emitted with whatever line terminators are found in the
495//  input.  However, if the final line is not terminated, a new line is appended.
496//
497void EmitMatch::accumulate_match (const size_t lineNum, char * line_start, char * line_end) {
498    if (WithFilenameFlag) {
499        mResultStr << mLinePrefix;
500    }
501    if (LineNumberFlag) {
502        // Internally line numbers are counted from 0.  For display, adjust
503        // the line number so that lines are numbered from 1.
504        if (InitialTabFlag) {
505            mResultStr << lineNum+1 << "\t:";
506        }
507        else {
508            mResultStr << lineNum+1 << ":";
509        }
510    }
511    size_t bytes = line_end - line_start + 1;
512    mResultStr.write(line_start, bytes);
513    mLineCount++;
514    unsigned last_byte = *line_end;
515    mTerminated = (last_byte >= 0x0A) && (last_byte <= 0x0D);
516    if (LLVM_UNLIKELY(!mTerminated)) {
517        if (last_byte == 0x85) {  //  Possible NEL terminator.
518            mTerminated = (bytes >= 2) && (static_cast<unsigned>(line_end[-1]) == 0xC2);
519        }
520        else {
521            // Possible LS or PS terminators.
522            mTerminated = (bytes >= 3) && (static_cast<unsigned>(line_end[-2]) == 0xE2)
523                                       && (static_cast<unsigned>(line_end[-1]) == 0x80)
524                                       && ((last_byte == 0xA8) || (last_byte == 0xA9));
525        }
526    }
527}
528
529void EmitMatch::finalize_match(char * buffer_end) {
530    if (!mTerminated) mResultStr << "\n";
531}
532
533void EmitMatchesEngine::grepCodeGen() {
534    assert (mGrepDriver == nullptr);
535    mGrepDriver = new ParabixDriver("engine");
536    auto & idb = mGrepDriver->getBuilder();
537    Module * M = idb->getModule();
538
539    const unsigned encodingBits = 8;
540
541    Function * mainFunc = cast<Function>(M->getOrInsertFunction("Main", idb->getInt64Ty(), idb->getInt8Ty(), idb->getInt32Ty(), idb->getIntAddrTy(), nullptr));
542    mainFunc->setCallingConv(CallingConv::C);
543    idb->SetInsertPoint(BasicBlock::Create(M->getContext(), "entry", mainFunc, 0));
544    auto args = mainFunc->arg_begin();
545
546    Value * const useMMap = &*(args++);
547    useMMap->setName("useMMap");
548    Value * const fileDescriptor = &*(args++);
549    fileDescriptor->setName("fileDescriptor");
550    Value * match_accumulator = &*(args++);
551    match_accumulator->setName("match_accumulator");
552
553    StreamSetBuffer * ByteStream = mGrepDriver->addBuffer<SourceBuffer>(idb, idb->getStreamSetTy(1, encodingBits));
554    kernel::Kernel * sourceK = mGrepDriver->addKernelInstance<kernel::FDSourceKernel>(idb);
555    sourceK->setInitialArguments({useMMap, fileDescriptor});
556    mGrepDriver->makeKernelCall(sourceK, {}, {ByteStream});
557
558    StreamSetBuffer * LineBreakStream;
559    StreamSetBuffer * Matches;
560    std::tie(LineBreakStream, Matches) = grepPipeline(ByteStream);
561
562    kernel::Kernel * scanMatchK = mGrepDriver->addKernelInstance<kernel::ScanMatchKernel>(idb);
563    scanMatchK->setInitialArguments({match_accumulator});
564    mGrepDriver->makeKernelCall(scanMatchK, {Matches, LineBreakStream, ByteStream}, {});
565    mGrepDriver->LinkFunction(*scanMatchK, "accumulate_match_wrapper", &accumulate_match_wrapper);
566    mGrepDriver->LinkFunction(*scanMatchK, "finalize_match_wrapper", &finalize_match_wrapper);
567
568    mGrepDriver->generatePipelineIR();
569    mGrepDriver->deallocateBuffers();
570    idb->CreateRet(idb->getInt64(0));
571    mGrepDriver->finalizeObject();
572}
573
574
575//
576//  The doGrep methods apply a GrepEngine to a single file, processing the results
577//  differently based on the engine type.
578
579uint64_t GrepEngine::doGrep(const std::string & fileName, const uint32_t fileIdx) {
580    typedef uint64_t (*GrepFunctionType)(bool useMMap, int32_t fileDescriptor);
581    using namespace boost::filesystem;
582    path p(fileName);
583    bool useMMap = grep::MmapFlag;
584    if (p == "-") useMMap = false;
585    if (!is_regular_file(p)) useMMap = false;
586
587    auto f = reinterpret_cast<GrepFunctionType>(mGrepDriver->getMain());
588
589    int32_t fileDescriptor = openFile(fileName, mResultStrs[fileIdx]);
590    if (fileDescriptor == -1) return 0;
591
592    uint64_t grepResult = f(useMMap, fileDescriptor);
593    close(fileDescriptor);
594    return grepResult;
595}
596
597uint64_t CountOnlyEngine::doGrep(const std::string & fileName, const uint32_t fileIdx) {
598    uint64_t grepResult = GrepEngine::doGrep(fileName, fileIdx);
599    if (WithFilenameFlag) mResultStrs[fileIdx] << linePrefix(fileName);
600    mResultStrs[fileIdx] << grepResult << "\n";
601    return grepResult;
602}
603
604std::string GrepEngine::linePrefix(std::string fileName) {
605    if (fileName == "-") {
606        return LabelFlag + mFileSuffix;
607    }
608    else {
609        return fileName + mFileSuffix;
610    }
611}
612
613uint64_t MatchOnlyEngine::doGrep(const std::string & fileName, const uint32_t fileIdx) {
614    uint64_t grepResult = GrepEngine::doGrep(fileName, fileIdx);
615    if (grepResult == mRequiredCount) {
616       mResultStrs[fileIdx] << linePrefix(fileName);
617    }
618    return grepResult;
619}
620
621uint64_t EmitMatchesEngine::doGrep(const std::string & fileName, const uint32_t fileIdx) {
622    typedef uint64_t (*GrepFunctionType)(bool useMMap, int32_t fileDescriptor, intptr_t accum_addr);
623    using namespace boost::filesystem;
624    path p(fileName);
625    bool useMMap = grep::MmapFlag;
626    if (p == "-") useMMap = false;
627    if (!is_regular_file(p)) useMMap = false;
628    auto f = reinterpret_cast<GrepFunctionType>(mGrepDriver->getMain());
629    int32_t fileDescriptor = openFile(fileName, mResultStrs[fileIdx]);
630    if (fileDescriptor == -1) return 0;
631    EmitMatch accum(linePrefix(fileName), mResultStrs[fileIdx]);
632    f(useMMap, fileDescriptor, reinterpret_cast<intptr_t>(&accum));
633    close(fileDescriptor);
634    if (accum.mLineCount > 0) grepMatchFound = true;
635    return accum.mLineCount;
636}
637
638// Open a file and return its file desciptor.
639int32_t GrepEngine::openFile(const std::string & fileName, std::ostringstream & msgstrm) {
640    if (fileName == "-") {
641        return STDIN_FILENO;
642    }
643    else {
644        struct stat sb;
645        int32_t fileDescriptor = open(fileName.c_str(), O_RDONLY);
646        if (LLVM_UNLIKELY(fileDescriptor == -1)) {
647            if (!NoMessagesFlag) {
648                if (errno == EACCES) {
649                    msgstrm << "icgrep: " << fileName << ": Permission denied.\n";
650                }
651                else if (errno == ENOENT) {
652                    msgstrm << "icgrep: " << fileName << ": No such file.\n";
653                }
654                else {
655                    msgstrm << "icgrep: " << fileName << ": Failed.\n";
656                }
657            }
658            return fileDescriptor;
659        }
660        if (stat(fileName.c_str(), &sb) == 0 && S_ISDIR(sb.st_mode)) {
661            if (!NoMessagesFlag) {
662                msgstrm << "icgrep: " << fileName << ": Is a directory.\n";
663            }
664            close(fileDescriptor);
665            return -1;
666        }
667        return fileDescriptor;
668    }
669}
670
671// The process of searching a group of files may use a sequential or a task
672// parallel approach.
673
674void * DoGrepThreadFunction(void *args) {
675    return reinterpret_cast<GrepEngine *>(args)->DoGrepThreadMethod();
676}
677
678bool GrepEngine::searchAllFiles() {
679    const unsigned numOfThreads = std::min(static_cast<unsigned>(Threads), static_cast<unsigned>(inputFiles.size())); 
680    std::vector<pthread_t> threads(numOfThreads);
681
682    for(unsigned long i = 1; i < numOfThreads; ++i) {
683        const int rc = pthread_create(&threads[i], nullptr, DoGrepThreadFunction, (void *)this);
684        if (rc) {
685            llvm::report_fatal_error("Failed to create thread: code " + std::to_string(rc));
686        }
687    }
688    // Main thread also does the work;
689    DoGrepThreadMethod();
690    for(unsigned i = 1; i < numOfThreads; ++i) {
691        void * status = nullptr;
692        const int rc = pthread_join(threads[i], &status);
693        if (rc) {
694            llvm::report_fatal_error("Failed to join thread: code " + std::to_string(rc));
695        }
696    }
697    return grepMatchFound;
698}
699
700
701// DoGrep thread function.
702void * GrepEngine::DoGrepThreadMethod() {
703
704    unsigned fileIdx = mNextFileToGrep++;
705    while (fileIdx < inputFiles.size()) {
706        const auto grepResult = doGrep(inputFiles[fileIdx], fileIdx);
707        mFileStatus[fileIdx] = FileStatus::GrepComplete;
708        if (grepResult > 0) {
709            grepMatchFound = true;
710        }
711        if (QuietMode && grepMatchFound) {
712            if (pthread_self() != mEngineThread) {
713                pthread_exit(nullptr);
714            }
715            return nullptr;
716        }
717        fileIdx = mNextFileToGrep++;
718    }
719
720    unsigned printIdx = mNextFileToPrint++;
721    while (printIdx < inputFiles.size()) {
722        const bool readyToPrint = ((printIdx == 0) || (mFileStatus[printIdx - 1] == FileStatus::PrintComplete)) && (mFileStatus[printIdx] == FileStatus::GrepComplete);
723        if (readyToPrint) {
724            const auto output = mResultStrs[printIdx].str();
725            if (!output.empty()) {
726                llvm::outs() << output;
727            }
728            mFileStatus[printIdx] = FileStatus::PrintComplete;
729            printIdx = mNextFileToPrint++;
730        } else {
731            mGrepDriver->performIncrementalCacheCleanupStep();
732        }
733        sched_yield();
734    }
735
736    if (pthread_self() != mEngineThread) {
737        pthread_exit(nullptr);
738    } else {
739        // Always perform one final cache cleanup step.
740        mGrepDriver->performIncrementalCacheCleanupStep();
741    }
742    return nullptr;
743}
744
745}
Note: See TracBrowser for help on using the repository browser.