source: icGREP/icgrep-devel/icgrep/grep/grep_kernel.cpp

Last change on this file was 6297, checked in by cameron, 4 months ago

Merge branch 'master' of https://cs-git-research.cs.surrey.sfu.ca/cameron/parabix-devel

File size: 31.1 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 */
5
6#include "grep_kernel.h"
7#include <cc/alphabet.h>
8#include <re/printer_re.h>
9#include <re/re_cc.h>
10#include <re/re_name.h>
11#include <re/re_toolchain.h>
12#include <re/re_reverse.h>
13#include <grep/grep_engine.h>
14#include <pablo/codegenstate.h>
15#include <pablo/pablo_toolchain.h>
16#include <kernels/kernel_builder.h>
17#include <pablo/builder.hpp>
18#include <pablo/pe_ones.h>          // for Ones
19#include <pablo/pe_var.h>           // for Var
20#include <pablo/pe_zeroes.h>        // for Zeroes
21#include <pablo/pe_infile.h>
22#include <pablo/boolean.h>
23#include <pablo/pe_count.h>
24#include <pablo/pe_matchstar.h>
25#include <pablo/pe_pack.h>
26#include <cc/cc_compiler.h>         // for CC_Compiler
27#include <cc/alphabet.h>
28#include <cc/multiplex_CCs.h>
29#include <re/re_compiler.h>
30#include <UCD/ucd_compiler.hpp>
31#include <llvm/IR/Module.h>
32#include <llvm/Support/raw_ostream.h>
33
34using namespace kernel;
35using namespace pablo;
36using namespace re;
37using namespace llvm;
38
39UnicodeLineBreakKernel::UnicodeLineBreakKernel(const std::unique_ptr<kernel::KernelBuilder> & kb)
40: PabloKernel(kb,
41              "UTF8_LB",
42              {Binding{kb->getStreamSetTy(8), "basis"}, Binding{kb->getStreamSetTy(1), "lf", FixedRate(), LookAhead(1)}},
43              {Binding{kb->getStreamSetTy(1, 1), "UTF8_LB", FixedRate()}}) {
44}
45
46void UnicodeLineBreakKernel::generatePabloMethod() {
47    PabloBuilder pb(getEntryScope());
48    cc::Parabix_CC_Compiler ccc(getEntryScope(), getInputStreamSet("basis"));
49    UCD::UCDCompiler ucdCompiler(ccc);
50    Name * breakChars = re::makeName("breakChars", makeCC(makeCC(makeCC(0x0A, 0x0D), makeCC(0x85)), makeCC(0x2028,0x2029)));
51    UCD::UCDCompiler::NameMap nameMap;
52    nameMap.emplace(breakChars, nullptr);
53    ucdCompiler.generateWithDefaultIfHierarchy(nameMap, pb);
54    auto f = nameMap.find(breakChars);
55    if (f == nameMap.end()) llvm::report_fatal_error("UnicodeLineBreakKernel compilation failure");
56    PabloAST * breakStream = f-> second;
57    PabloAST * const LF = pb.createExtract(getInput(1), pb.getInteger(0), "LF");
58    PabloAST * const CR = ccc.compileCC(makeByte(0x0D));
59    Var * const CR_before_LF = pb.createVar("CR_before_LF", pb.createZeroes());
60    auto crb = pb.createScope();
61    pb.createIf(CR, crb);
62    PabloAST * const lookaheadLF = crb.createLookahead(LF, 1, "lookaheadLF");
63    crb.createAssign(CR_before_LF, crb.createAnd(CR, lookaheadLF));
64    breakStream = pb.createXor(breakStream, CR_before_LF);  // Remove CR_before_LF from breakStream
65    Var * const UTF8_LB = getOutputStreamVar("UTF8_LB");
66    pb.createAssign(pb.createExtract(UTF8_LB, pb.getInteger(0)), breakStream);
67}
68
69void UTF8_nonFinal::generatePabloMethod() {
70    PabloBuilder pb(getEntryScope());
71    std::unique_ptr<cc::CC_Compiler> ccc;
72    bool useDirectCC = getInput(0)->getType()->getArrayNumElements() == 1;
73    if (useDirectCC) {
74        ccc = make_unique<cc::Direct_CC_Compiler>(getEntryScope(), pb.createExtract(getInput(0), pb.getInteger(0)));
75    } else {
76        ccc = make_unique<cc::Parabix_CC_Compiler>(getEntryScope(), getInputStreamSet("source"));
77    }
78
79    Zeroes * const ZEROES = pb.createZeroes();
80    PabloAST * const u8pfx = ccc->compileCC(makeByte(0xC0, 0xFF));
81
82
83    Var * const nonFinal = pb.createVar("nonFinal", u8pfx);
84    Var * const u8invalid = pb.createVar("u8invalid", ZEROES);
85    Var * const valid_pfx = pb.createVar("valid_pfx", u8pfx);
86
87    auto it = pb.createScope();
88    pb.createIf(u8pfx, it);
89    PabloAST * const u8pfx2 = ccc->compileCC(makeByte(0xC2, 0xDF), it);
90    PabloAST * const u8pfx3 = ccc->compileCC(makeByte(0xE0, 0xEF), it);
91    PabloAST * const u8pfx4 = ccc->compileCC(makeByte(0xF0, 0xF4), it);
92    PabloAST * const u8suffix = ccc->compileCC("u8suffix", makeByte(0x80, 0xBF), it);
93
94    //
95    // Two-byte sequences
96    Var * const anyscope = it.createVar("anyscope", ZEROES);
97    auto it2 = it.createScope();
98    it.createIf(u8pfx2, it2);
99    it2.createAssign(anyscope, it2.createAdvance(u8pfx2, 1));
100
101
102    //
103    // Three-byte sequences
104    Var * const EF_invalid = it.createVar("EF_invalid", ZEROES);
105    auto it3 = it.createScope();
106    it.createIf(u8pfx3, it3);
107    PabloAST * const u8scope32 = it3.createAdvance(u8pfx3, 1);
108    it3.createAssign(nonFinal, it3.createOr(nonFinal, u8scope32));
109    PabloAST * const u8scope33 = it3.createAdvance(u8pfx3, 2);
110    PabloAST * const u8scope3X = it3.createOr(u8scope32, u8scope33);
111    it3.createAssign(anyscope, it3.createOr(anyscope, u8scope3X));
112    PabloAST * const E0_invalid = it3.createAnd(it3.createAdvance(ccc->compileCC(makeByte(0xE0), it3), 1), ccc->compileCC(makeByte(0x80, 0x9F), it3));
113    PabloAST * const ED_invalid = it3.createAnd(it3.createAdvance(ccc->compileCC(makeByte(0xED), it3), 1), ccc->compileCC(makeByte(0xA0, 0xBF), it3));
114    PabloAST * const EX_invalid = it3.createOr(E0_invalid, ED_invalid);
115    it3.createAssign(EF_invalid, EX_invalid);
116
117    //
118    // Four-byte sequences
119    auto it4 = it.createScope();
120    it.createIf(u8pfx4, it4);
121    PabloAST * const u8scope42 = it4.createAdvance(u8pfx4, 1, "u8scope42");
122    PabloAST * const u8scope43 = it4.createAdvance(u8scope42, 1, "u8scope43");
123    PabloAST * const u8scope44 = it4.createAdvance(u8scope43, 1, "u8scope44");
124    PabloAST * const u8scope4nonfinal = it4.createOr(u8scope42, u8scope43);
125    it4.createAssign(nonFinal, it4.createOr(nonFinal, u8scope4nonfinal));
126    PabloAST * const u8scope4X = it4.createOr(u8scope4nonfinal, u8scope44);
127    it4.createAssign(anyscope, it4.createOr(anyscope, u8scope4X));
128    PabloAST * const F0_invalid = it4.createAnd(it4.createAdvance(ccc->compileCC(makeByte(0xF0), it4), 1), ccc->compileCC(makeByte(0x80, 0x8F), it4));
129    PabloAST * const F4_invalid = it4.createAnd(it4.createAdvance(ccc->compileCC(makeByte(0xF4), it4), 1), ccc->compileCC(makeByte(0x90, 0xBF), it4));
130    PabloAST * const FX_invalid = it4.createOr(F0_invalid, F4_invalid);
131    it4.createAssign(EF_invalid, it4.createOr(EF_invalid, FX_invalid));
132
133    //
134    // Invalid cases
135    PabloAST * const legalpfx = it.createOr(it.createOr(u8pfx2, u8pfx3), u8pfx4);
136    //  Any scope that does not have a suffix byte, and any suffix byte that is not in
137    //  a scope is a mismatch, i.e., invalid UTF-8.
138    PabloAST * const mismatch = it.createXor(anyscope, u8suffix);
139    //
140    PabloAST * const pfx_invalid = it.createXor(valid_pfx, legalpfx);
141    it.createAssign(u8invalid, it.createOr(pfx_invalid, it.createOr(mismatch, EF_invalid)));
142    PabloAST * const u8valid = it.createNot(u8invalid, "u8valid");
143    //
144    //
145    it.createAssign(nonFinal, it.createAnd(nonFinal, u8valid));
146    //pb.createAssign(nonFinal, pb.createOr(nonFinal, CRLF));
147    //PabloAST * unterminatedLineAtEOF = pb.createAtEOF(pb.createAdvance(pb.createNot(LineBreak), 1), "unterminatedLineAtEOF");
148
149    Var * const required = getOutputStreamVar("nonFinal");
150    pb.createAssign(pb.createExtract(required, pb.getInteger(0)), nonFinal);
151}
152
153UTF8_nonFinal::UTF8_nonFinal(const std::unique_ptr<kernel::KernelBuilder> & kb, StreamSet * Source, StreamSet * u8nonFinal)
154: PabloKernel(kb, "UTF8_nonFinal" + std::to_string(Source->getNumElements()) + "x" + std::to_string(Source->getFieldWidth()),
155// input
156{Binding{"source", Source}},
157// output
158{Binding{"nonFinal", u8nonFinal}}) {
159
160}
161
162void RequiredStreams_UTF8::generatePabloMethod() {
163    PabloBuilder pb(getEntryScope());
164    std::unique_ptr<cc::CC_Compiler> ccc;
165    bool useDirectCC = getInput(0)->getType()->getArrayNumElements() == 1;
166    if (useDirectCC) {
167        ccc = make_unique<cc::Direct_CC_Compiler>(getEntryScope(), pb.createExtract(getInput(0), pb.getInteger(0)));
168    } else {
169        ccc = make_unique<cc::Parabix_CC_Compiler>(getEntryScope(), getInputStreamSet("source"));
170    }
171
172    PabloAST * const LF = pb.createExtract(getInput(1), pb.getInteger(0), "LF");
173    PabloAST * const CR = ccc->compileCC(makeByte(0x0D));
174    PabloAST * const LF_VT_FF_CR = ccc->compileCC("LF,VT,FF,CR", makeByte(0x0A, 0x0D), pb);
175    Var * const LineBreak = pb.createVar("LineBreak", LF_VT_FF_CR);
176
177    // Remove the CR of any CR+LF
178    Var * const CRLF = pb.createVar("CRLF", pb.createZeroes());
179    auto crb = pb.createScope();
180    pb.createIf(CR, crb);
181    PabloAST * const lookaheadLF = crb.createLookahead(LF, 1, "lookaheadLF");
182    PabloAST * const crlf = crb.createAnd(CR, lookaheadLF);
183    crb.createAssign(CRLF, crlf);
184    PabloAST * removedCRLF = crb.createAnd(LineBreak, crb.createNot(CRLF));
185    crb.createAssign(LineBreak, removedCRLF);
186
187
188    Zeroes * const ZEROES = pb.createZeroes();
189    PabloAST * const u8pfx = ccc->compileCC(makeByte(0xC0, 0xFF));
190
191
192    Var * const nonFinal = pb.createVar("nonFinal", u8pfx);
193    Var * const u8invalid = pb.createVar("u8invalid", ZEROES);
194    Var * const valid_pfx = pb.createVar("valid_pfx", u8pfx);
195
196    auto it = pb.createScope();
197    pb.createIf(u8pfx, it);
198    PabloAST * const u8pfx2 = ccc->compileCC(makeByte(0xC2, 0xDF), it);
199    PabloAST * const u8pfx3 = ccc->compileCC(makeByte(0xE0, 0xEF), it);
200    PabloAST * const u8pfx4 = ccc->compileCC(makeByte(0xF0, 0xF4), it);
201    PabloAST * const u8suffix = ccc->compileCC("u8suffix", makeByte(0x80, 0xBF), it);
202
203    //
204    // Two-byte sequences
205    Var * const anyscope = it.createVar("anyscope", ZEROES);
206    auto it2 = it.createScope();
207    it.createIf(u8pfx2, it2);
208    it2.createAssign(anyscope, it2.createAdvance(u8pfx2, 1));
209    PabloAST * NEL = it2.createAnd(it2.createAdvance(ccc->compileCC(makeByte(0xC2), it2), 1), ccc->compileCC(makeByte(0x85), it2), "NEL");
210    it2.createAssign(LineBreak, it2.createOr(LineBreak, NEL));
211
212
213    //
214    // Three-byte sequences
215    Var * const EF_invalid = it.createVar("EF_invalid", ZEROES);
216    auto it3 = it.createScope();
217    it.createIf(u8pfx3, it3);
218    PabloAST * const u8scope32 = it3.createAdvance(u8pfx3, 1);
219    it3.createAssign(nonFinal, it3.createOr(nonFinal, u8scope32));
220    PabloAST * const u8scope33 = it3.createAdvance(u8pfx3, 2);
221    PabloAST * const u8scope3X = it3.createOr(u8scope32, u8scope33);
222    it3.createAssign(anyscope, it3.createOr(anyscope, u8scope3X));
223    PabloAST * const E0_invalid = it3.createAnd(it3.createAdvance(ccc->compileCC(makeByte(0xE0), it3), 1), ccc->compileCC(makeByte(0x80, 0x9F), it3));
224    PabloAST * const ED_invalid = it3.createAnd(it3.createAdvance(ccc->compileCC(makeByte(0xED), it3), 1), ccc->compileCC(makeByte(0xA0, 0xBF), it3));
225    PabloAST * const EX_invalid = it3.createOr(E0_invalid, ED_invalid);
226    it3.createAssign(EF_invalid, EX_invalid);
227    PabloAST * E2_80 = it3.createAnd(it3.createAdvance(ccc->compileCC(makeByte(0xE2), it3), 1), ccc->compileCC(makeByte(0x80), it3));
228    PabloAST * LS_PS = it3.createAnd(it3.createAdvance(E2_80, 1), ccc->compileCC(makeByte(0xA8,0xA9), it3), "LS_PS");
229    it3.createAssign(LineBreak, it3.createOr(LineBreak, LS_PS));
230
231    //
232    // Four-byte sequences
233    auto it4 = it.createScope();
234    it.createIf(u8pfx4, it4);
235    PabloAST * const u8scope42 = it4.createAdvance(u8pfx4, 1, "u8scope42");
236    PabloAST * const u8scope43 = it4.createAdvance(u8scope42, 1, "u8scope43");
237    PabloAST * const u8scope44 = it4.createAdvance(u8scope43, 1, "u8scope44");
238    PabloAST * const u8scope4nonfinal = it4.createOr(u8scope42, u8scope43);
239    it4.createAssign(nonFinal, it4.createOr(nonFinal, u8scope4nonfinal));
240    PabloAST * const u8scope4X = it4.createOr(u8scope4nonfinal, u8scope44);
241    it4.createAssign(anyscope, it4.createOr(anyscope, u8scope4X));
242    PabloAST * const F0_invalid = it4.createAnd(it4.createAdvance(ccc->compileCC(makeByte(0xF0), it4), 1), ccc->compileCC(makeByte(0x80, 0x8F), it4));
243    PabloAST * const F4_invalid = it4.createAnd(it4.createAdvance(ccc->compileCC(makeByte(0xF4), it4), 1), ccc->compileCC(makeByte(0x90, 0xBF), it4));
244    PabloAST * const FX_invalid = it4.createOr(F0_invalid, F4_invalid);
245    it4.createAssign(EF_invalid, it4.createOr(EF_invalid, FX_invalid));
246
247    //
248    // Invalid cases
249    PabloAST * const legalpfx = it.createOr(it.createOr(u8pfx2, u8pfx3), u8pfx4);
250    //  Any scope that does not have a suffix byte, and any suffix byte that is not in
251    //  a scope is a mismatch, i.e., invalid UTF-8.
252    PabloAST * const mismatch = it.createXor(anyscope, u8suffix);
253    //
254    PabloAST * const pfx_invalid = it.createXor(valid_pfx, legalpfx);
255    it.createAssign(u8invalid, it.createOr(pfx_invalid, it.createOr(mismatch, EF_invalid)));
256    PabloAST * const u8valid = it.createNot(u8invalid, "u8valid");
257    //
258    //
259    it.createAssign(nonFinal, it.createAnd(nonFinal, u8valid));
260    pb.createAssign(nonFinal, pb.createOr(nonFinal, CRLF));
261
262    Var * const required = getOutputStreamVar("nonFinal");
263    pb.createAssign(pb.createExtract(required, pb.getInteger(0)), nonFinal);
264    pb.createAssign(pb.createExtract(getOutputStreamVar("UnicodeLB"), pb.getInteger(0)), LineBreak);
265}
266
267RequiredStreams_UTF8::RequiredStreams_UTF8(const std::unique_ptr<kernel::KernelBuilder> & kb, StreamSet * Source, StreamSet * LineFeedStream, StreamSet * RequiredStreams, StreamSet * UnicodeLB)
268: PabloKernel(kb, "RequiredStreams_UTF8" + std::to_string(Source->getNumElements()) + "x" + std::to_string(Source->getFieldWidth()),
269// input
270{Binding{"source", Source},
271 Binding{"lf", LineFeedStream, FixedRate(), LookAhead(1)}},
272// output
273{Binding{"nonFinal", RequiredStreams, FixedRate()},
274 Binding{"UnicodeLB", UnicodeLB, FixedRate()}}) {
275
276}
277
278void RequiredStreams_UTF16::generatePabloMethod() {
279    PabloBuilder pb(getEntryScope());
280    cc::Parabix_CC_Compiler ccc(getEntryScope(), getInputStreamSet("basis"));
281
282    PabloAST * u16hi_hi_surrogate = ccc.compileCC(makeCC(0xD800, 0xDBFF, &cc::UTF16));    //u16hi_hi_surrogate = [\xD8-\xDB]
283    PabloAST * u16hi_lo_surrogate = ccc.compileCC(makeCC(0xDC00, 0xDFFF, &cc::UTF16));    //u16hi_lo_surrogate = [\xDC-\xDF]
284
285    PabloAST * invalidTemp = pb.createAdvance(u16hi_hi_surrogate, 1, "InvalidTemp");
286    PabloAST * u16invalid = pb.createXor(invalidTemp, u16hi_lo_surrogate, "u16invalid");
287
288    PabloAST * u16valid = pb.createNot(u16invalid, "u16valid");
289    PabloAST * nonFinal = pb.createAnd(u16hi_hi_surrogate, u16valid, "nonfinal");
290
291    PabloAST * u16single_temp = pb.createOr(ccc.compileCC(makeCC(0x0000, 0xD7FF, &cc::UTF16)), ccc.compileCC(makeCC(0xE000, 0xFFFF, &cc::UTF16)));
292    PabloAST * u16single = pb.createAnd(u16single_temp, pb.createNot(u16invalid));
293
294    PabloAST * const nonFinalCodeUnits = pb.createExtract(getInput(1), pb.getInteger(0));
295    PabloAST * const initial = pb.createOr(u16single, u16hi_hi_surrogate, "initial");
296    PabloAST * const final = pb.createNot(pb.createOr(pb.createOr(u16hi_hi_surrogate, u16invalid), nonFinalCodeUnits), "final");
297
298    Var * const required = getOutputStreamVar("required");
299    pb.createAssign(pb.createExtract(required, pb.getInteger(0)), initial);
300    pb.createAssign(pb.createExtract(required, pb.getInteger(1)), nonFinal);
301    pb.createAssign(pb.createExtract(required, pb.getInteger(2)), final);
302
303}
304
305RequiredStreams_UTF16::RequiredStreams_UTF16(const std::unique_ptr<kernel::KernelBuilder> & kb)
306: PabloKernel(kb, "RequiredStreams_UTF16",
307// inputs
308{Binding{kb->getStreamSetTy(8), "basis"}},
309// output
310{Binding{kb->getStreamSetTy(3), "required", FixedRate(), Add1()}}) {
311
312}
313
314void GrepKernelOptions::setNumbering(cc::BitNumbering numbering) {mBasisSetNumbering = numbering;}
315void GrepKernelOptions::setIndexingAlphabet(const cc::Alphabet * a) {mIndexingAlphabet = a;}
316void GrepKernelOptions::setRE(RE * e) {mRE = e;}
317void GrepKernelOptions::setPrefixRE(RE * e) {mPrefixRE = e;}
318void GrepKernelOptions::setSource(StreamSet * s) {mSource = s;}
319void GrepKernelOptions::setResults(StreamSet * r) {mResults = r;}
320void GrepKernelOptions::addExternal(std::string name, StreamSet * strm) {
321    mExternals.emplace_back(name, strm);
322}
323void GrepKernelOptions::addAlphabet(std::shared_ptr<cc::Alphabet> a, StreamSet * basis) {
324    mAlphabets.emplace_back(a, basis);
325}
326
327Bindings GrepKernelOptions::streamSetInputBindings() {
328    Bindings inputs;
329    inputs.emplace_back("basis", mSource);
330    for (const auto & e : mExternals) {
331        inputs.emplace_back(e.first, e.second);
332    }
333    for (const auto & a : mAlphabets) {
334        inputs.emplace_back(a.first->getName() + "_basis", a.second);
335    }
336    return inputs;
337}
338
339Bindings GrepKernelOptions::streamSetOutputBindings() {
340    return {Binding{"matches", mResults, FixedRate(), Add1()}};
341}
342
343Bindings GrepKernelOptions::scalarInputBindings() {
344    return {};
345}
346
347Bindings GrepKernelOptions::scalarOutputBindings() {
348    return {};
349}
350
351std::string GrepKernelOptions::getSignature() {
352    if (mSignature == "") {
353        mSignature = std::to_string(mSource->getNumElements()) + "x" + std::to_string(mSource->getFieldWidth());
354        mSignature += "/" + mIndexingAlphabet->getName();
355        for (auto e: mExternals) {
356            mSignature += "_" + e.first;
357        }
358        for (auto a: mAlphabets) {
359            mSignature += "_" + a.first->getName();
360        }
361        if (mPrefixRE) {
362            mSignature += ":" + Printer_RE::PrintRE(mPrefixRE);
363        }
364        mSignature += ":" + Printer_RE::PrintRE(mRE);
365    }
366    return mSignature;
367}
368
369ICGrepKernel::ICGrepKernel(const std::unique_ptr<kernel::KernelBuilder> & b, std::unique_ptr<GrepKernelOptions> options)
370: PabloKernel(b, "ic" + getStringHash(options->getSignature()),
371    options->streamSetInputBindings(),
372    options->streamSetOutputBindings(),
373    options->scalarInputBindings(),
374    options->scalarOutputBindings()), mOptions(std::move(options)) {
375}
376
377std::string ICGrepKernel::makeSignature(const std::unique_ptr<kernel::KernelBuilder> &) {
378    return mOptions->getSignature();
379}
380
381void ICGrepKernel::generatePabloMethod() {
382    PabloBuilder pb(getEntryScope());
383    std::unique_ptr<cc::CC_Compiler> ccc;
384    bool useDirectCC = getInput(0)->getType()->getArrayNumElements() == 1;
385    if (useDirectCC) {
386        ccc = make_unique<cc::Direct_CC_Compiler>(getEntryScope(), pb.createExtract(getInput(0), pb.getInteger(0)));
387    } else {
388        ccc = make_unique<cc::Parabix_CC_Compiler>(getEntryScope(), getInputStreamSet("basis"), mOptions->mBasisSetNumbering);
389    }
390    //cc::Parabix_CC_Compiler ccc(getEntryScope(), getInputStreamSet("basis"), mOptions->mBasisSetNumbering);
391    RE_Compiler re_compiler(getEntryScope(), *ccc.get(), *(mOptions->mIndexingAlphabet), mOptions->mBasisSetNumbering);
392    for (const auto & e : mOptions->mExternals) {
393        re_compiler.addPrecompiled(e.first, pb.createExtract(getInputStreamVar(e.first), pb.getInteger(0)));
394    }
395    for (const auto & a : mOptions->mAlphabets) {
396        auto & alpha = a.first;
397        auto mpx_basis = getInputStreamSet(alpha->getName() + "_basis");
398        re_compiler.addAlphabet(alpha, mpx_basis);
399    }
400    if (mOptions->mPrefixRE) {
401        PabloAST * const prefixMatches = re_compiler.compile(mOptions->mPrefixRE);
402        Var * const final_matches = pb.createVar("final_matches", pb.createZeroes());
403        PabloBlock * scope1 = getEntryScope()->createScope();
404        pb.createIf(prefixMatches, scope1);
405
406        PabloAST * u8bytes = pb.createExtract(getInput(0), pb.getInteger(0));
407        PabloAST * nybbles[2];
408        nybbles[0] = scope1->createPackL(scope1->getInteger(8), u8bytes);
409        nybbles[1] = scope1->createPackH(scope1->getInteger(8), u8bytes);
410
411        PabloAST * bitpairs[4];
412        for (unsigned i = 0; i < 2; i++) {
413            bitpairs[2*i] = scope1->createPackL(scope1->getInteger(4), nybbles[i]);
414            bitpairs[2*i + 1] = scope1->createPackH(scope1->getInteger(4), nybbles[i]);
415        }
416
417        std::vector<PabloAST *> basis(8);
418        for (unsigned i = 0; i < 4; i++) {
419            basis[2*i] = scope1->createPackL(scope1->getInteger(2), bitpairs[i]);
420            basis[2*i + 1] = scope1->createPackH(scope1->getInteger(2), bitpairs[i]);
421        }
422
423        cc::Parabix_CC_Compiler ccc(scope1, basis);
424        RE_Compiler re_compiler(scope1, ccc, *(mOptions->mIndexingAlphabet), mOptions->mBasisSetNumbering);
425        scope1->createAssign(final_matches, re_compiler.compile(mOptions->mRE, prefixMatches));
426        Var * const output = getOutputStreamVar("matches");
427        pb.createAssign(pb.createExtract(output, pb.getInteger(0)), final_matches);
428    } else {
429        PabloAST * const matches = re_compiler.compile(mOptions->mRE);
430        Var * const output = getOutputStreamVar("matches");
431        pb.createAssign(pb.createExtract(output, pb.getInteger(0)), matches);
432    }
433}
434
435// Helper to compute stream set inputs to pass into PabloKernel constructor.
436Bindings ByteBitGrepKernel::makeInputBindings(StreamSet * const basis, const Externals & externals) {
437    Bindings inputs;
438    inputs.emplace_back("basis", basis);
439    for (const auto & e : externals) {
440        inputs.emplace_back(e.first, e.second);
441    }
442    return inputs;
443}
444
445
446ByteBitGrepSignature::ByteBitGrepSignature(RE * prefix, RE * suffix)
447: mPrefixRE(prefix)
448, mSuffixRE(suffix)
449, mSignature(Printer_RE::PrintRE(mPrefixRE) + Printer_RE::PrintRE(mSuffixRE) ) {
450}
451
452ByteBitGrepKernel::ByteBitGrepKernel(const std::unique_ptr<kernel::KernelBuilder> & b, RE * const prefixRE, RE * const suffixRE, StreamSet * const Source, StreamSet * const matches, const Externals externals)
453: ByteBitGrepSignature(prefixRE, suffixRE)
454, PabloKernel(b, "bBc" + getStringHash(mSignature),
455// inputs
456makeInputBindings(Source, externals),
457// output
458{Binding{"matches", matches, FixedRate(), Add1()}}) {
459
460}
461
462std::string ByteBitGrepKernel::makeSignature(const std::unique_ptr<kernel::KernelBuilder> &) {
463    return mSignature;
464}
465
466
467void ByteBitGrepKernel::generatePabloMethod() {
468    PabloBuilder pb(getEntryScope());
469    PabloAST * u8bytes = pb.createExtract(getInput(0), pb.getInteger(0));
470    cc::Direct_CC_Compiler dcc(getEntryScope(), u8bytes);
471    RE_Compiler re_byte_compiler(getEntryScope(), dcc);
472
473    const auto numOfInputs = getNumOfInputs();
474    for (unsigned i = 1; i < numOfInputs; ++i) {
475        const Binding & input = getInputStreamSetBinding(i);
476        re_byte_compiler.addPrecompiled(input.getName(), pb.createExtract(getInputStreamVar(input.getName()), pb.getInteger(0)));
477    }
478
479    PabloAST * const prefixMatches = re_byte_compiler.compile(mPrefixRE);
480    Var * const final_matches = pb.createVar("final_matches", pb.createZeroes());
481    PabloBlock * scope1 = getEntryScope()->createScope();
482    pb.createIf(prefixMatches, scope1);
483
484    PabloAST * nybbles[2];
485    nybbles[0] = scope1->createPackL(scope1->getInteger(8), u8bytes);
486    nybbles[1] = scope1->createPackH(scope1->getInteger(8), u8bytes);
487
488    PabloAST * bitpairs[4];
489    for (unsigned i = 0; i < 2; i++) {
490        bitpairs[2*i] = scope1->createPackL(scope1->getInteger(4), nybbles[i]);
491        bitpairs[2*i + 1] = scope1->createPackH(scope1->getInteger(4), nybbles[i]);
492    }
493
494    std::vector<PabloAST *> basis(8);
495    for (unsigned i = 0; i < 4; i++) {
496        basis[2*i] = scope1->createPackL(scope1->getInteger(2), bitpairs[i]);
497        basis[2*i + 1] = scope1->createPackH(scope1->getInteger(2), bitpairs[i]);
498    }
499
500    cc::Parabix_CC_Compiler ccc(scope1, basis);
501    RE_Compiler re_compiler(scope1, ccc);
502    scope1->createAssign(final_matches, re_compiler.compile(mSuffixRE, prefixMatches));
503    Var * const output = getOutputStreamVar("matches");
504    pb.createAssign(pb.createExtract(output, pb.getInteger(0)), final_matches);
505}
506
507
508void MatchedLinesKernel::generatePabloMethod() {
509    PabloBuilder pb(getEntryScope());
510    PabloAST * matchResults = pb.createExtract(getInputStreamVar("matchResults"), pb.getInteger(0));
511    PabloAST * lineBreaks = pb.createExtract(getInputStreamVar("lineBreaks"), pb.getInteger(0));
512    PabloAST * notLB = pb.createNot(lineBreaks);
513    PabloAST * match_follow = pb.createMatchStar(matchResults, notLB);
514    PabloAST * unterminatedLineAtEOF = pb.createAtEOF(pb.createAdvance(notLB, 1), "unterminatedLineAtEOF");
515    Var * const matchedLines = getOutputStreamVar("matchedLines");
516    pb.createAssign(pb.createExtract(matchedLines, pb.getInteger(0)), pb.createAnd(match_follow, pb.createOr(lineBreaks, unterminatedLineAtEOF)));
517}
518
519MatchedLinesKernel::MatchedLinesKernel (const std::unique_ptr<kernel::KernelBuilder> & iBuilder, StreamSet * OriginalMatches, StreamSet * LineBreakStream, StreamSet * Matches)
520: PabloKernel(iBuilder, "MatchedLines",
521// inputs
522{Binding{"matchResults", OriginalMatches}
523,Binding{"lineBreaks", LineBreakStream}},
524// output
525{Binding{"matchedLines", Matches, FixedRate(), Add1()}}) {
526
527}
528
529
530void InvertMatchesKernel::generateDoBlockMethod(const std::unique_ptr<KernelBuilder> & iBuilder) {
531    Value * input = iBuilder->loadInputStreamBlock("matchedLines", iBuilder->getInt32(0));
532    Value * lbs = iBuilder->loadInputStreamBlock("lineBreaks", iBuilder->getInt32(0));
533    Value * inverted = iBuilder->CreateXor(input, lbs);
534    iBuilder->storeOutputStreamBlock("nonMatches", iBuilder->getInt32(0), inverted);
535}
536
537InvertMatchesKernel::InvertMatchesKernel(const std::unique_ptr<kernel::KernelBuilder> & b, StreamSet * OriginalMatches, StreamSet * LineBreakStream, StreamSet * Matches)
538: BlockOrientedKernel(b, "Invert",
539// Inputs
540{Binding{"matchedLines", OriginalMatches},
541 Binding{"lineBreaks", LineBreakStream}},
542// Outputs
543{Binding{"nonMatches", Matches}},
544// Input/Output Scalars and internal state
545{}, {}, {}) {
546
547}
548
549
550void PopcountKernel::generatePabloMethod() {
551    auto pb = getEntryScope();
552    const auto toCount = pb->createExtract(getInputStreamVar("toCount"), pb->getInteger(0));
553    pablo::Var * countResult = getOutputScalarVar("countResult");
554
555    pb->createAssign(countResult, pb->createCount(pb->createInFile(toCount)));
556}
557
558PopcountKernel::PopcountKernel (const std::unique_ptr<kernel::KernelBuilder> & iBuilder, StreamSet * const toCount, Scalar * countResult)
559: PabloKernel(iBuilder, "Popcount",
560{Binding{"toCount", toCount}},
561{},
562{},
563{Binding{"countResult", countResult}}) {
564
565}
566
567
568void AbortOnNull::generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> & b, llvm::Value * const numOfStrides) {
569    Module * const m = b->getModule();
570    DataLayout DL(m);
571    IntegerType * const intPtrTy = DL.getIntPtrType(m->getContext());
572    Type * voidPtrTy = b->getVoidPtrTy();
573    const auto blocksPerStride = getStride() / b->getBitBlockWidth();
574    Constant * const BLOCKS_PER_STRIDE = b->getSize(blocksPerStride);
575    BasicBlock * const entry = b->GetInsertBlock();
576    BasicBlock * const strideLoop = b->CreateBasicBlock("strideLoop");
577    BasicBlock * const stridesDone = b->CreateBasicBlock("stridesDone");
578    BasicBlock * const nullByteDetection = b->CreateBasicBlock("nullByteDetection");
579    BasicBlock * const nullByteFound = b->CreateBasicBlock("nullByteFound");
580    BasicBlock * const finalStride = b->CreateBasicBlock("finalStride");
581    BasicBlock * const segmentDone = b->CreateBasicBlock("segmentDone");
582
583    Value * const numOfBlocks = b->CreateMul(numOfStrides, BLOCKS_PER_STRIDE);
584    Value * itemsToDo = b->getAccessibleItemCount("byteData");
585    //
586    // Fast loop to prove that there are no null bytes in a multiblock region.
587    // We repeatedly combine byte packs using a SIMD unsigned min operation
588    // (implemented as a Select/ICmpULT combination).
589    //
590    Value * byteStreamBasePtr = b->getInputStreamBlockPtr("byteData", b->getSize(0), b->getSize(0));
591    Value * outputStreamBasePtr = b->getOutputStreamBlockPtr("untilNull", b->getSize(0), b->getSize(0));
592
593    //
594    // We set up a a set of eight accumulators to accumulate the minimum byte
595    // values seen at each position in a block.   The initial min value at
596    // each position is 0xFF (all ones).
597    Value * blockMin[8];
598    for (unsigned i = 0; i < 8; i++) {
599        blockMin[i] = b->fwCast(8, b->allOnes());
600    }
601    // If we're in the final block bypass the fast loop.
602    b->CreateCondBr(mIsFinal, finalStride, strideLoop);
603
604    b->SetInsertPoint(strideLoop);
605    PHINode * const baseBlockIndex = b->CreatePHI(b->getSizeTy(), 2);
606    baseBlockIndex->addIncoming(ConstantInt::get(baseBlockIndex->getType(), 0), entry);
607    PHINode * const blocksRemaining = b->CreatePHI(b->getSizeTy(), 2);
608    blocksRemaining->addIncoming(numOfBlocks, entry);
609    for (unsigned i = 0; i < 8; i++) {
610        Value * next = b->CreateBlockAlignedLoad(b->CreateGEP(byteStreamBasePtr, {baseBlockIndex, b->getSize(i)}));
611        b->CreateBlockAlignedStore(next, b->CreateGEP(outputStreamBasePtr, {baseBlockIndex, b->getSize(i)}));
612        next = b->fwCast(8, next);
613        blockMin[i] = b->CreateSelect(b->CreateICmpULT(next, blockMin[i]), next, blockMin[i]);
614    }
615    Value * nextBlockIndex = b->CreateAdd(baseBlockIndex, ConstantInt::get(baseBlockIndex->getType(), 1));
616    Value * nextRemaining = b->CreateSub(blocksRemaining, ConstantInt::get(blocksRemaining->getType(), 1));
617    baseBlockIndex->addIncoming(nextBlockIndex, strideLoop);
618    blocksRemaining->addIncoming(nextRemaining, strideLoop);
619    b->CreateCondBr(b->CreateICmpUGT(nextRemaining, ConstantInt::getNullValue(blocksRemaining->getType())), strideLoop, stridesDone);
620
621    b->SetInsertPoint(stridesDone);
622    // Combine the 8 blockMin values.
623    for (unsigned i = 0; i < 4; i++) {
624        blockMin[i] = b->CreateSelect(b->CreateICmpULT(blockMin[i], blockMin[i+4]), blockMin[i], blockMin[i+4]);
625    }
626    for (unsigned i = 0; i < 2; i++) {
627        blockMin[i] = b->CreateSelect(b->CreateICmpULT(blockMin[i], blockMin[i+4]), blockMin[i], blockMin[i+2]);
628    }
629    blockMin[0] = b->CreateSelect(b->CreateICmpULT(blockMin[0], blockMin[1]), blockMin[0], blockMin[1]);
630    Value * anyNull = b->bitblock_any(b->simd_eq(8, blockMin[0], b->allZeroes()));
631
632    b->CreateCondBr(anyNull, nullByteDetection, segmentDone);
633
634
635    b->SetInsertPoint(finalStride);
636    b->CreateMemCpy(b->CreatePointerCast(outputStreamBasePtr, voidPtrTy), b->CreatePointerCast(byteStreamBasePtr, voidPtrTy), itemsToDo, 1);
637    b->CreateBr(nullByteDetection);
638
639    b->SetInsertPoint(nullByteDetection);
640    //  Find the exact location using memchr, which should be fast enough.
641    //
642    Value * ptrToNull = b->CreateMemChr(b->CreatePointerCast(byteStreamBasePtr, voidPtrTy), b->getInt32(0), itemsToDo);
643    Value * ptrAddr = b->CreatePtrToInt(ptrToNull, intPtrTy);
644    b->CreateCondBr(b->CreateICmpEQ(ptrAddr, ConstantInt::getNullValue(intPtrTy)), segmentDone, nullByteFound);
645
646    // A null byte has been located; set the termination code and call the signal handler.
647    b->SetInsertPoint(nullByteFound);
648    Value * nullPosn = b->CreateSub(b->CreatePtrToInt(ptrToNull, intPtrTy), b->CreatePtrToInt(byteStreamBasePtr, intPtrTy));
649    b->setTerminationSignal();
650    Function * const dispatcher = m->getFunction("signal_dispatcher"); assert (dispatcher);
651    Value * handler = b->getScalarField("handler_address");
652    b->CreateCall(dispatcher, {handler, ConstantInt::get(b->getInt32Ty(), static_cast<unsigned>(grep::GrepSignal::BinaryFile))});
653    b->CreateBr(segmentDone);
654
655    b->SetInsertPoint(segmentDone);
656    PHINode * const produced = b->CreatePHI(b->getSizeTy(), 3);
657    produced->addIncoming(nullPosn, nullByteFound);
658    produced->addIncoming(itemsToDo, stridesDone);
659    produced->addIncoming(itemsToDo, nullByteDetection);
660    Value * producedCount = b->getProducedItemCount("untilNull");
661    producedCount = b->CreateAdd(producedCount, produced);
662    b->setProducedItemCount("untilNull", producedCount);
663}
664
665AbortOnNull::AbortOnNull(const std::unique_ptr<kernel::KernelBuilder> & b, StreamSet * const InputStream, StreamSet * const OutputStream, Scalar * callbackObject)
666: MultiBlockKernel(b, "AbortOnNull",
667// inputs
668{Binding{"byteData", InputStream, FixedRate(), Principal()}},
669// outputs
670{Binding{ "untilNull", OutputStream, FixedRate(), Deferred()}},
671// input scalars
672{Binding{"handler_address", callbackObject}},
673{}, {}) {
674    addAttribute(CanTerminateEarly());
675}
Note: See TracBrowser for help on using the repository browser.