source: icGREP/icgrep-devel/icgrep/re/re_compiler.cpp

Last change on this file was 5872, checked in by cameron, 6 days ago

Decoupling CC compilers from Pablo Kernel

File size: 28.4 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
7
8
9#include "re_compiler.h"
10#include <pablo/pe_ones.h>          // for Ones
11#include <pablo/pe_var.h>           // for Var
12#include <pablo/pe_zeroes.h>        // for Zeroes
13#include <re/printer_re.h>
14#include <re/re_alt.h>
15#include <re/re_analysis.h>         // for isByteLength, isUnicodeUnitLength
16#include <re/re_any.h>
17#include <re/re_assertion.h>        // for Assertion, Assertion::Sense, Asse...
18#include <re/re_cc.h>               // for makeCC
19#include <re/re_diff.h>             // for Diff
20#include <re/re_end.h>
21#include <re/re_intersect.h>        // for Intersect
22#include <re/re_name.h>             // for Name, Name::Type, Name::Type::Zer...
23#include <re/re_rep.h>              // for Rep, Rep::::UNBOUNDED_REP
24#include <re/re_seq.h>              // for Seq
25#include <re/re_start.h>
26#include <re/re_local.h>
27#include <re/to_utf8.h>
28#include <re/re_toolchain.h>        // for AlgorithmOptionIsSet, RE_Algorith...
29#include <cc/alphabet.h>
30#include <cc/cc_compiler.h>
31#include "pablo/builder.hpp"        // for PabloBuilder
32#include <IR_Gen/idisa_target.h>    // for AVX2_available
33#include <llvm/ADT/STLExtras.h> // for make_unique
34#include <llvm/Support/raw_ostream.h>
35#include <llvm/Support/ErrorHandling.h>
36
37namespace pablo { class PabloAST; }
38namespace pablo { class Var; }
39namespace pablo { class PabloKernel; }
40namespace re { class Alt; }
41namespace re { class RE; }
42
43using namespace pablo;
44using namespace llvm;
45
46namespace re {
47
48   
49void RE_Compiler::addAlphabet(cc::Alphabet * a, std::vector<pablo::PabloAST *> basis_set) {
50    mAlphabets.push_back(a);
51    mAlphabetCompilers.push_back(make_unique<cc::Parabix_CC_Compiler>(mEntryScope, basis_set));
52}
53
54using MarkerType = RE_Compiler::MarkerType;
55
56PabloAST * RE_Compiler::compile(RE * const re, PabloAST * const initialCursors) {
57    pablo::PabloBuilder mPB(mEntryScope);
58    const auto markers = initialCursors ? compile(re, initialCursors, mPB) : compile(re, mPB);
59    return markerVar(AdvanceMarker(markers, FinalPostPositionUnit, mPB));
60}
61
62inline MarkerType RE_Compiler::compile(RE * const re, PabloAST * const cursors, PabloBuilder & pb) {
63    //  An important use case for an initial set of cursors to be passed in
64    //  is that the initial cursors are computed from a prefix of an RE such
65    //  that there is a high probability of all cursors remaining in a block
66    //  are zeroed.   We therefore embed processing logic in an if-test,
67    //  dependent on the initial cursors.
68    Var * m = pb.createVar("m", pb.createZeroes());
69    NameMap nestedMap(mCompiledName);
70    mCompiledName = &nestedMap;
71    auto nested = pb.createScope();
72    MarkerType m1 = process(re, makeMarker(FinalPostPositionUnit, cursors), nested);
73    nested.createAssign(m, markerVar(m1));
74    pb.createIf(cursors, nested);
75    mCompiledName = nestedMap.getParent();
76    return makeMarker(m1.pos, m);
77}
78
79inline MarkerType RE_Compiler::compile(RE * const re, PabloBuilder & pb) {
80    return process(re, makeMarker(FinalPostPositionUnit, pb.createOnes()), pb);
81}
82   
83MarkerType RE_Compiler::process(RE * const re, MarkerType marker, PabloBuilder & pb) {
84    if (isa<Name>(re)) {
85        return compileName(cast<Name>(re), marker, pb);
86    } else if (isa<Seq>(re)) {
87        return compileSeq(cast<Seq>(re), marker, pb);
88    } else if (isa<Alt>(re)) {
89        return compileAlt(cast<Alt>(re), marker, pb);
90    } else if (isa<Rep>(re)) {
91        return compileRep(cast<Rep>(re), marker, pb);
92    } else if (isa<Assertion>(re)) {
93        return compileAssertion(cast<Assertion>(re), marker, pb);
94    } else if (isa<Any>(re)) {
95        return compileAny(marker, pb);
96    } else if (isa<Diff>(re)) {
97        return compileDiff(cast<Diff>(re), marker, pb);
98    } else if (isa<Intersect>(re)) {
99        return compileIntersect(cast<Intersect>(re), marker, pb);
100    } else if (isa<Start>(re)) {
101        return compileStart(marker, pb);
102    } else if (isa<End>(re)) {
103        return compileEnd(marker, pb);
104    } else if (isa<CC>(re)) {
105        // CCs may be passed through the toolchain directly to the compiler.
106        return compileCC(cast<CC>(re), marker, pb);
107    } else {
108        UnsupportedRE("RE Compiler failed to process " + Printer_RE::PrintRE(re));
109    }
110}
111
112inline MarkerType RE_Compiler::compileAny(const MarkerType m, PabloBuilder & pb) {
113    PabloAST * const nextFinalByte = markerVar(AdvanceMarker(m, FinalPostPositionUnit, pb));
114    return makeMarker(FinalMatchUnit, nextFinalByte);
115}
116
117MarkerType RE_Compiler::compileCC(CC * const cc, MarkerType marker, PabloBuilder & pb) {
118    PabloAST * nextPos = markerVar(marker);
119    const cc::Alphabet * a = cc->getAlphabet();
120    if (a == &cc::Byte) {
121        if (marker.pos == FinalMatchUnit) {
122            nextPos = pb.createAdvance(nextPos, 1);
123        }
124        return makeMarker(FinalMatchUnit, pb.createAnd(nextPos, mCCCompiler.compileCC(cc, pb)));
125    } else if (a == &cc::Unicode) {
126        MarkerType m = compile(toUTF8(cc), pb);
127        nextPos = markerVar(AdvanceMarker(marker, FinalPostPositionUnit, pb));
128        return makeMarker(FinalMatchUnit, pb.createAnd(markerVar(m), nextPos));
129    } else {
130        if (isByteLength(cc)) {
131            if (marker.pos == FinalMatchUnit) {
132                nextPos = pb.createAdvance(nextPos, 1);
133            }
134        } else {
135            nextPos = markerVar(AdvanceMarker(marker, FinalPostPositionUnit, pb));
136        }
137        unsigned i = 0;
138        while (i < mAlphabets.size() && (a != mAlphabets[i])) i++;
139        if (i == mAlphabets.size()) llvm::report_fatal_error("Alphabet " + a->getName() + " has no CC compiler");
140        return makeMarker(FinalMatchUnit, pb.createAnd(nextPos, mAlphabetCompilers[i]->compileCC(cc, pb)));
141    }
142}
143
144inline MarkerType RE_Compiler::compileName(Name * const name, MarkerType marker, PabloBuilder & pb) {
145    const auto & nameString = name->getName();
146    if (nameString == ".") {
147        return compileAny(marker, pb);
148    } else if (nameString == "^"){
149        return compileStart(marker, pb);
150    } else if (nameString == "$"){
151        return compileEnd(marker, pb);
152    } else if (isUnicodeUnitLength(name)) {
153        MarkerType nameMarker = compileName(name, pb);
154        MarkerType nextPos = AdvanceMarker(marker, FinalPostPositionUnit, pb);
155        nameMarker.stream = pb.createAnd(markerVar(nextPos), markerVar(nameMarker), name->getName());
156        return nameMarker;
157    } else if (name->getType() == Name::Type::ZeroWidth) {
158        RE * zerowidth = name->getDefinition();
159        MarkerType zero = compile(zerowidth, pb);
160        AlignMarkers(marker, zero, pb);
161        PabloAST * ze = markerVar(zero);
162        if (nameString == "\\B{g}") {
163            ze = pb.createNot(ze);
164        }
165        return makeMarker(markerPos(marker), pb.createAnd(markerVar(marker), ze, "zerowidth"));
166    } else {
167        return process(name->getDefinition(), marker, pb);
168    }
169}
170
171inline MarkerType RE_Compiler::compileName(Name * const name, PabloBuilder & pb) {
172    MarkerType m;
173    if (LLVM_LIKELY(mCompiledName->get(name, m))) {
174        return m;
175    } else if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
176        m = compile(name->getDefinition(), pb);
177        mCompiledName->add(name, m);
178        return m;
179    }
180    UnsupportedRE("Unresolved name " + name->getName());
181}
182
183MarkerType RE_Compiler::compileSeq(Seq * const seq, MarkerType marker, PabloBuilder & pb) {
184    // if-hierarchies are not inserted within unbounded repetitions
185    if (mStarDepth > 0) {
186        for (RE * re : *seq) {
187            marker = process(re, marker, pb);
188        }
189        return marker;
190    } else {
191        return compileSeqTail(seq->cbegin(), seq->cend(), 0, marker, pb);
192    }
193}
194
195MarkerType RE_Compiler::compileSeqTail(Seq::const_iterator current, const Seq::const_iterator end, const int matchLenSoFar, MarkerType marker, PabloBuilder & pb) {
196    if (current == end) {
197        return marker;
198    } else if (matchLenSoFar < IfInsertionGap) {
199        RE * r = *current;
200        marker = process(r, marker, pb);
201        return compileSeqTail(++current, end, matchLenSoFar + minMatchLength(r), marker, pb);
202    } else {
203        Var * m = pb.createVar("m", pb.createZeroes());
204        NameMap nestedMap(mCompiledName);
205        mCompiledName = &nestedMap;
206        auto nested = pb.createScope();
207        MarkerType m1 = compileSeqTail(current, end, 0, marker, nested);
208        nested.createAssign(m, markerVar(m1));
209        pb.createIf(markerVar(marker), nested);
210        mCompiledName = nestedMap.getParent();
211        return makeMarker(m1.pos, m);
212    }
213}
214
215MarkerType RE_Compiler::compileAlt(Alt * const alt, const MarkerType base, PabloBuilder & pb) {
216    std::vector<PabloAST *>  accum(3, pb.createZeroes());
217    // The following may be useful to force a common Advance rather than separate
218    // Advances in each alternative.
219    for (RE * re : *alt) {
220        MarkerType m = process(re, base, pb);
221        const MarkerPosition p = markerPos(m);
222        accum[p] = pb.createOr(accum[p], markerVar(m), "alt");
223    }
224    if (isa<Zeroes>(accum[InitialPostPositionUnit]) && isa<Zeroes>(accum[FinalPostPositionUnit])) {
225        return makeMarker(FinalMatchUnit, accum[FinalMatchUnit]);
226    }
227
228    PabloAST * combine = pb.createOr(accum[InitialPostPositionUnit], pb.createAdvance(accum[FinalMatchUnit], 1), "alt");
229    if (isa<Zeroes>(accum[FinalPostPositionUnit])) {
230        return makeMarker(InitialPostPositionUnit, combine);
231    }
232    combine = pb.createOr(pb.createOr(pb.createAnd(combine, mFinal), pb.createScanThru(pb.createAnd(mNonFinal, combine), mNonFinal)), accum[FinalPostPositionUnit], "alt");
233    return makeMarker(FinalPostPositionUnit, combine);
234}
235
236MarkerType RE_Compiler::compileAssertion(Assertion * const a, MarkerType marker, PabloBuilder & pb) {
237    RE * asserted = a->getAsserted();
238    if (a->getKind() == Assertion::Kind::Lookbehind) {
239        MarkerType lookback = compile(asserted, pb);
240        AlignMarkers(marker, lookback, pb);
241        PabloAST * lb = markerVar(lookback);
242        if (a->getSense() == Assertion::Sense::Negative) {
243            lb = pb.createNot(lb);
244        }
245        return makeMarker(markerPos(marker), pb.createAnd(markerVar(marker), lb, "lookback"));
246    } else if (a->getKind() == Assertion::Kind::Boundary) {
247        MarkerType cond = compile(asserted, pb);
248        if (LLVM_LIKELY(markerPos(cond) == FinalMatchUnit)) {
249            MarkerType postCond = AdvanceMarker(cond, FinalPostPositionUnit, pb);
250            PabloAST * boundaryCond = pb.createXor(markerVar(cond), markerVar(postCond));
251            if (a->getSense() == Assertion::Sense::Negative) {
252                boundaryCond = pb.createNot(boundaryCond);
253            }
254            MarkerType fbyte = AdvanceMarker(marker, FinalPostPositionUnit, pb);
255            return makeMarker(FinalPostPositionUnit, pb.createAnd(markerVar(fbyte), boundaryCond, "boundary"));
256        }
257        else UnsupportedRE("Unsupported boundary assertion");
258    } else if (isUnicodeUnitLength(asserted)) {
259        MarkerType lookahead = compile(asserted, pb);
260        if (LLVM_LIKELY(markerPos(lookahead) == FinalMatchUnit)) {
261            PabloAST * la = markerVar(lookahead);
262            if (a->getSense() == Assertion::Sense::Negative) {
263                la = pb.createNot(la);
264            }
265            MarkerType fbyte = AdvanceMarker(marker, FinalPostPositionUnit, pb);
266            return makeMarker(FinalPostPositionUnit, pb.createAnd(markerVar(fbyte), la, "lookahead"));
267        }
268    }
269    UnsupportedRE("Unsupported lookahead assertion.");
270}
271
272inline bool alignedUnicodeLength(const RE * const lh, const RE * const rh) {
273    const auto lhl = getUnicodeUnitLengthRange(lh);
274    const auto rhl = getUnicodeUnitLengthRange(rh);
275    return (lhl.first == lhl.second && lhl.first == rhl.first && lhl.second == rhl.second);
276}
277
278MarkerType RE_Compiler::compileDiff(Diff * diff, MarkerType marker, PabloBuilder & pb) {
279    RE * const lh = diff->getLH();
280    RE * const rh = diff->getRH();
281    if (alignedUnicodeLength(lh, rh)) {
282        MarkerType t1 = process(lh, marker, pb);
283        MarkerType t2 = process(rh, marker, pb);
284        AlignMarkers(t1, t2, pb);
285        return makeMarker(markerPos(t1), pb.createAnd(markerVar(t1), pb.createNot(markerVar(t2)), "diff"));
286    }
287    UnsupportedRE("Unsupported Diff operands: " + Printer_RE::PrintRE(diff));
288}
289
290MarkerType RE_Compiler::compileIntersect(Intersect * const x, MarkerType marker, PabloBuilder & pb) {
291    RE * const lh = x->getLH();
292    RE * const rh = x->getRH();
293    if (alignedUnicodeLength(lh, rh)) {
294        MarkerType t1 = process(lh, marker, pb);
295        MarkerType t2 = process(rh, marker, pb);
296        AlignMarkers(t1, t2, pb);
297        return makeMarker(markerPos(t1), pb.createAnd(markerVar(t1), markerVar(t2), "intersect"));
298    }
299    UnsupportedRE("Unsupported Intersect operands: " + Printer_RE::PrintRE(x));
300}
301
302MarkerType RE_Compiler::compileRep(Rep * const rep, MarkerType marker, PabloBuilder & pb) {
303    const auto lb = rep->getLB();
304    const auto ub = rep->getUB();
305    if (lb > 0) {
306        marker = processLowerBound(rep->getRE(), lb, marker, IfInsertionGap, pb);
307    }
308    if (ub == Rep::UNBOUNDED_REP) {
309        marker = processUnboundedRep(rep->getRE(), marker, pb);
310    } else if (lb < ub) {
311        marker = processBoundedRep(rep->getRE(), ub - lb, marker, IfInsertionGap, pb);
312    }
313    return marker;
314}
315
316/*
317   Given a stream |repeated_j| marking positions associated with |j| conecutive matches to an item
318   compute a stream marking |repeat_count| consecutive occurrences of such items.
319*/
320   
321PabloAST * RE_Compiler::consecutive_matches(PabloAST * const repeated_j, const int j, const int repeat_count, PabloAST * const indexStream, PabloBuilder & pb) {
322    if (j == repeat_count) {
323        return repeated_j;
324    }
325    const int i = std::min(j, repeat_count - j);
326    const int k = j + i;
327    if (/*j > IfInsertionGap*/ false) {
328        Var * repeated = pb.createVar("repeated", pb.createZeroes());
329        auto nested = pb.createScope();
330        NameMap nestedMap(mCompiledName);
331        mCompiledName = &nestedMap;
332        PabloAST * adv_i = nested.createIndexedAdvance(repeated_j, indexStream, i);
333        PabloAST * repeated_k = nested.createAnd(repeated_j, adv_i, "at" + std::to_string(k) + "of" + std::to_string(repeat_count));
334        nested.createAssign(repeated, consecutive_matches(repeated_k, k, repeat_count, indexStream, nested));
335        pb.createIf(repeated_j, nested);
336        mCompiledName = nestedMap.getParent();
337        return repeated;
338    } else {
339        PabloAST * adv_i = pb.createIndexedAdvance(repeated_j, indexStream, i);
340        PabloAST * repeated_k = pb.createAnd(repeated_j, adv_i, "at" + std::to_string(k) + "of" + std::to_string(repeat_count));
341        return consecutive_matches(repeated_k, k, repeat_count, indexStream, pb);
342    }
343}
344
345
346inline PabloAST * RE_Compiler::reachable(PabloAST *  const repeated, const int length, const int repeat_count, PabloAST * const indexStream, PabloBuilder & pb) {
347    if (repeat_count == 0) {
348        return repeated;
349    }   
350    const int total_length = repeat_count * length;
351    PabloAST * const v2 = pb.createIndexedAdvance(repeated, indexStream, 1);
352    PabloAST * reachable = pb.createOr(repeated, v2, "within1");
353    int i = length;
354    while ((i * 2) < total_length) {
355        PabloAST * const extension = pb.createIndexedAdvance(reachable, indexStream, i);
356        i *= 2;
357        reachable = pb.createOr(reachable, extension, "within" + std::to_string(i));
358    }
359    if (LLVM_LIKELY(i < total_length)) {
360        PabloAST * const extension = pb.createIndexedAdvance(reachable, indexStream, total_length - i);
361        reachable = pb.createOr(reachable, extension, "within" + std::to_string(total_length));
362    }
363    return reachable;
364}
365
366MarkerType RE_Compiler::processLowerBound(RE * const repeated, const int lb, MarkerType marker, const int ifGroupSize, PabloBuilder & pb) {
367    if (LLVM_UNLIKELY(lb == 0)) {
368        return marker;
369    } else if (LLVM_UNLIKELY(lb == 1)) {
370        return process(repeated, marker, pb);
371    }
372    //
373    // A bounded repetition with an upper bound of at least 2.
374    if (LLVM_LIKELY(!AlgorithmOptionIsSet(DisableLog2BoundedRepetition))) {
375        // Check for a regular expression that satisfies on of the special conditions that
376        // allow implementation using the log2 technique.
377        if (isByteLength(repeated)) {
378            PabloAST * cc = markerVar(compile(repeated, pb));
379            PabloAST * cc_lb = consecutive_matches(cc, 1, lb, nullptr, pb);
380            const auto pos = markerPos(marker) == FinalMatchUnit ? lb : lb - 1;
381            PabloAST * marker_fwd = pb.createAdvance(markerVar(marker), pos);
382            return makeMarker(FinalMatchUnit, pb.createAnd(marker_fwd, cc_lb, "lowerbound"));
383        }
384        else if (isUnicodeUnitLength(repeated)) {
385            PabloAST * cc = markerVar(compile(repeated, pb));
386            PabloAST * cc_lb = consecutive_matches(cc, 1, lb, mFinal, pb);
387            const auto pos = markerPos(marker) == FinalMatchUnit ? lb : lb - 1;
388            PabloAST * marker_fwd = pb.createIndexedAdvance(markerVar(marker), mFinal, pos);
389            return makeMarker(FinalMatchUnit, pb.createAnd(marker_fwd, cc_lb, "lowerbound"));
390        }
391        else if (isTypeForLocal(repeated)) {
392            CC * const first = RE_Local::getFirstUniqueSymbol(repeated);
393            if (first) { // if the first symbol is unique, we can use it as an index stream.
394                PabloAST * firstCCstream = markerVar(compile(first, pb));
395                // Find all matches to the repeated regexp.
396                PabloAST * submatch = markerVar(AdvanceMarker(compile(repeated, pb), FinalPostPositionUnit, pb));
397                // Consecutive submatches require that the symbol following the end of one submatch is the first symbol for
398                // the next submatch.   lb-1 such submatches are required.
399                PabloAST * consecutive_submatch = consecutive_matches(submatch, 1, lb-1, firstCCstream, pb);
400                // Find submatch positions which are lb-2 start symbols forward from the current marker position.
401                PabloAST * base = markerVar(AdvanceMarker(marker, FinalPostPositionUnit, pb));
402                PabloAST * marker_fwd = pb.createIndexedAdvance(base, firstCCstream, lb - 1);
403                PabloAST * consecutive_lb_1 = pb.createAnd(marker_fwd, consecutive_submatch);
404                // From any of these positions, any position reachable by one more occurrence of the
405                // regexp is a match.
406                return process(repeated, makeMarker(FinalPostPositionUnit, consecutive_lb_1), pb);
407            }
408        }
409    }
410    // Fall through to general case.  Process the first item and insert the rest into an if-structure.
411    const auto group = ifGroupSize < lb ? ifGroupSize : lb;
412    for (auto i = 0; i < group; i++) {
413        marker = process(repeated, marker, pb);
414    }
415    if (lb == group) {
416        return marker;
417    }
418    Var * m = pb.createVar("m", pb.createZeroes());
419    auto nested = pb.createScope();
420    NameMap nestedMap(mCompiledName);
421    mCompiledName = &nestedMap;
422    MarkerType m1 = processLowerBound(repeated, lb - group, marker, ifGroupSize * 2, nested);
423    nested.createAssign(m, markerVar(m1));
424    pb.createIf(markerVar(marker), nested);
425    mCompiledName = nestedMap.getParent();
426    return makeMarker(m1.pos, m);
427}
428   
429MarkerType RE_Compiler::processBoundedRep(RE * const repeated, const int ub, MarkerType marker, const int ifGroupSize,  PabloBuilder & pb) {
430    if (LLVM_UNLIKELY(ub == 0)) {
431        return marker;
432    }
433    //
434    // A bounded repetition with an upper bound of at least 2.
435    if ((ub > 1) && LLVM_LIKELY(!AlgorithmOptionIsSet(DisableLog2BoundedRepetition))) {
436        // Check for a regular expression that satisfies on of the special conditions that
437        // allow implementation using the log2 technique.
438        if (isByteLength(repeated)) {
439            // log2 upper bound for fixed length (=1) class
440            // Create a mask of positions reachable within ub from current marker.
441            // Use matchstar, then apply filter.
442            PabloAST * cursor = markerVar(AdvanceMarker(marker, InitialPostPositionUnit, pb));
443            // If we've advanced the cursor to the post position unit, cursor begins on the first masked bit of the bounded mask.
444            // Extend the mask by ub - 1 byte positions to ensure the mask ends on the FinalMatchUnit of the repeated region.
445            PabloAST * upperLimitMask = reachable(cursor, 1, ub - 1, nullptr, pb);
446            PabloAST * masked = pb.createAnd(markerVar(compile(repeated, pb)), upperLimitMask);
447            // MatchStar deposits any cursors on the post position. However those cursors may may land on the initial "byte" of a
448            // "multi-byte" character. Combine the masked range with any nonFinals.
449            PabloAST * bounded = pb.createMatchStar(cursor, pb.createOr(masked, mNonFinal), "bounded");
450            return makeMarker(FinalPostPositionUnit, bounded);
451        }
452        else if (isUnicodeUnitLength(repeated)) {
453            // For a regexp which represent a single Unicode codepoint, we can use the mFinal stream
454            // as an index stream for an indexed advance operation.
455            PabloAST * cursor = markerVar(AdvanceMarker(marker, FinalPostPositionUnit, pb));
456            PabloAST * upperLimitMask = reachable(cursor, 1, ub - 1, mFinal, pb);
457            PabloAST * masked = pb.createAnd(markerVar(compile(repeated, pb)), upperLimitMask, "masked");
458            PabloAST * bounded = pb.createMatchStar(cursor, pb.createOr(masked, mNonFinal), "bounded");
459            return makeMarker(FinalPostPositionUnit, bounded);
460        }
461        else if (isTypeForLocal(repeated)) {
462            CC * const first = RE_Local::getFirstUniqueSymbol(repeated);
463            if (first) { // if the first symbol is unique, we can use it as an index stream.
464                PabloAST * firstCCstream = markerVar(compile(first, pb));
465                PabloAST * cursor = markerVar(AdvanceMarker(marker, FinalPostPositionUnit, pb));
466                PabloAST * upperLimitMask = reachable(cursor, 1, ub - 1, firstCCstream, pb);
467                PabloAST * masked = pb.createAnd(markerVar(AdvanceMarker(compile(repeated, pb), FinalPostPositionUnit, pb)), upperLimitMask, "masked");
468                PabloAST * bounded = pb.createMatchStar(cursor, pb.createOr(masked, mNonFinal), "bounded");
469                return makeMarker(FinalPostPositionUnit, bounded);
470            }
471        }
472    }
473    // Fall through to general case.  Process the first item and insert the rest into an if-structure.
474    const auto group = ifGroupSize < ub ? ifGroupSize : ub;
475    for (auto i = 0; i < group; i++) {
476        MarkerType a = process(repeated, marker, pb);
477        MarkerType m = marker;
478        AlignMarkers(a, m, pb);
479        marker = makeMarker(markerPos(a), pb.createOr(markerVar(a), markerVar(m)));
480    }
481    if (ub == group) {
482        return marker;
483    }
484    Var * const m1a = pb.createVar("m", pb.createZeroes());
485    auto nested = pb.createScope();
486    NameMap nestedMap(mCompiledName);
487    mCompiledName = &nestedMap;
488    MarkerType m1 = processBoundedRep(repeated, ub - group, marker, ifGroupSize * 2, nested);
489    nested.createAssign(m1a, markerVar(m1));
490    pb.createIf(markerVar(marker), nested);
491    mCompiledName = nestedMap.getParent();
492    return makeMarker(markerPos(m1), m1a);
493}
494
495MarkerType RE_Compiler::processUnboundedRep(RE * const repeated, MarkerType marker, PabloBuilder & pb) {
496    // always use PostPosition markers for unbounded repetition.
497    PabloAST * base = markerVar(AdvanceMarker(marker, InitialPostPositionUnit, pb));
498    if (isByteLength(repeated) && LLVM_LIKELY(!AlgorithmOptionIsSet(DisableMatchStar))) {
499        PabloAST * mask = markerVar(compile(repeated, pb));
500        // The post position character may land on the initial byte of a multi-byte character. Combine them with the masked range.
501        mask = pb.createOr(mask, mNonFinal);
502        PabloAST * unbounded = pb.createMatchStar(base, mask, "unbounded");
503        return makeMarker(FinalPostPositionUnit, unbounded);
504    } else if (isUnicodeUnitLength(repeated) && LLVM_LIKELY(!AlgorithmOptionIsSet(DisableMatchStar) && !AlgorithmOptionIsSet(DisableUnicodeMatchStar))) {
505        PabloAST * mask = markerVar(compile(repeated, pb));
506        mask = pb.createOr(mask, mNonFinal);
507        PabloAST * unbounded = pb.createMatchStar(base, mask);
508        return makeMarker(FinalPostPositionUnit, pb.createAnd(unbounded, mFinal, "unbounded"));
509    } else if (mStarDepth > 0){
510        PabloBuilder * const outer = pb.getParent();
511        Var * starPending = outer->createVar("pending", outer->createZeroes());
512        Var * starAccum = outer->createVar("accum", outer->createZeroes());
513        mStarDepth++;
514        PabloAST * m1 = pb.createOr(base, starPending);
515        PabloAST * m2 = pb.createOr(base, starAccum);
516        MarkerType result = process(repeated, makeMarker(InitialPostPositionUnit, m1), pb);
517        result = AdvanceMarker(result, InitialPostPositionUnit, pb);
518        PabloAST * loopComputation = markerVar(result);
519        pb.createAssign(starPending, pb.createAnd(loopComputation, pb.createNot(m2)));
520        pb.createAssign(starAccum, pb.createOr(loopComputation, m2));
521        mWhileTest = pb.createOr(mWhileTest, starPending);
522        mStarDepth--;
523        return makeMarker(markerPos(result), pb.createOr(base, starAccum, "unbounded"));
524    } else {
525        Var * whileTest = pb.createVar("test", base);
526        Var * whilePending = pb.createVar("pending", base);
527        Var * whileAccum = pb.createVar("accum", base);
528        mWhileTest = pb.createZeroes();
529        auto wb = pb.createScope();
530        NameMap nestedMap(mCompiledName);
531        mCompiledName = &nestedMap;
532        mStarDepth++;
533        MarkerType result = process(repeated, makeMarker(InitialPostPositionUnit, whilePending), wb);
534        result = AdvanceMarker(result, InitialPostPositionUnit, wb);
535        PabloAST * loopComputation = markerVar(result);
536        wb.createAssign(whilePending, wb.createAnd(loopComputation, wb.createNot(whileAccum)));
537        wb.createAssign(whileAccum, wb.createOr(loopComputation, whileAccum));
538        wb.createAssign(whileTest, wb.createOr(mWhileTest, whilePending));
539        pb.createWhile(whileTest, wb);
540        mStarDepth--;
541        mCompiledName = nestedMap.getParent();
542        return makeMarker(markerPos(result), whileAccum);
543    }
544}
545
546inline MarkerType RE_Compiler::compileStart(MarkerType marker, pablo::PabloBuilder & pb) {
547    PabloAST * const sol = pb.createNot(pb.createAdvance(pb.createNot(mLineBreak), 1));
548    MarkerType m = AdvanceMarker(marker, InitialPostPositionUnit, pb);
549    return makeMarker(InitialPostPositionUnit, pb.createAnd(markerVar(m), sol, "sol"));
550}
551
552inline MarkerType RE_Compiler::compileEnd(MarkerType marker, pablo::PabloBuilder & pb) {
553    PabloAST * const nextPos = markerVar(AdvanceMarker(marker, FinalPostPositionUnit, pb));
554    PabloAST * const atEOL = pb.createAnd(mLineBreak, nextPos, "eol");
555    //PabloAST * const atEOL = pb.createOr(pb.createAnd(mLineBreak, nextPos), pb.createAdvance(pb.createAnd(nextPos, mCRLF), 1), "eol");
556    return makeMarker(FinalPostPositionUnit, atEOL);
557}
558
559inline MarkerType RE_Compiler::AdvanceMarker(MarkerType marker, const MarkerPosition newpos, PabloBuilder & pb) {
560    if (marker.pos != newpos) {
561        if (marker.pos == FinalMatchUnit) {
562            marker.stream = pb.createAdvance(marker.stream, 1, "ipp");
563            marker.pos = InitialPostPositionUnit;
564        }
565        if (newpos == FinalPostPositionUnit) {
566            marker.stream = pb.createOr(pb.createAnd(marker.stream, mFinal), pb.createScanThru(pb.createAnd(mNonFinal, marker.stream), mNonFinal, "fpp"));
567            marker.pos = FinalPostPositionUnit;
568        }
569    }
570    return marker;
571}
572
573inline void RE_Compiler::AlignMarkers(MarkerType & m1, MarkerType & m2, PabloBuilder & pb) {
574    if (m1.pos < m2.pos) {
575        m1 = AdvanceMarker(m1, m2.pos, pb);
576    } else if (m2.pos < m1.pos) {
577        m2 = AdvanceMarker(m2, m1.pos, pb);
578    }
579}
580   
581LLVM_ATTRIBUTE_NORETURN void RE_Compiler::UnsupportedRE(std::string errmsg) {
582    llvm::report_fatal_error(errmsg);
583}
584
585RE_Compiler::RE_Compiler(PabloKernel * kernel, cc::CC_Compiler & ccCompiler)
586: mEntryScope(kernel->getEntryScope())
587, mCCCompiler(ccCompiler)
588, mLineBreak(nullptr)
589, mNonFinal(nullptr)
590, mFinal(nullptr)
591, mWhileTest(nullptr)
592, mStarDepth(0)
593, mCompiledName(&mBaseMap) {
594    PabloBuilder mPB(mEntryScope);
595    Var * const linebreak = kernel->getInputStreamVar("linebreak");
596    mLineBreak = mPB.createExtract(linebreak, 0);
597    Var * const required = kernel->getInputStreamVar("required");
598    mNonFinal = mPB.createExtract(required, 0);
599    mFinal = mPB.createNot(mNonFinal);
600}
601
602} // end of namespace re
Note: See TracBrowser for help on using the repository browser.