source: icGREP/icgrep-devel/icgrep/re/re_toolchain.cpp @ 6176

Last change on this file since 6176 was 6176, checked in by cameron, 7 months ago

Test case and bug fix for overaggressive memoization

File size: 15.0 KB
Line 
1/*
2 *  Copyright (c) 2017 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#include <toolchain/toolchain.h>
8#include <grep_interface.h>
9#include <re/re_toolchain.h>
10#include <re/re_any.h>
11#include <re/re_name.h>
12#include <re/re_cc.h>
13#include <re/re_start.h>
14#include <re/re_end.h>
15#include <re/re_alt.h>
16#include <re/re_seq.h>
17#include <re/re_diff.h>
18#include <re/re_intersect.h>
19#include <re/re_group.h>
20#include <re/re_range.h>
21#include <re/re_assertion.h>
22#include <cc/cc_compiler.h>            // for CC_Compiler
23#include <llvm/Support/CommandLine.h>  // for clEnumVal, clEnumValEnd, Optio...
24#include <re/re_compiler.h>            // for RE_Compiler
25#include <re/re_nullable.h>            // for RE_Nullable
26#include <re/re_star_normal.h>         // for RE_Star_Normal
27#include <re/re_simplifier.h>          // for RE_Simplifier
28#include <re/re_minimizer.h>
29#include <re/re_local.h>
30#include <re/printer_re.h>
31#include <re/re_analysis.h>
32#include <re/re_cc.h>
33#include <re/casing.h>
34#include <re/exclude_CC.h>
35#include <re/re_name_resolve.h>
36#include <re/grapheme_clusters.h>
37#include <llvm/Support/raw_ostream.h>
38#include <llvm/Support/ErrorHandling.h>
39#include <toolchain/toolchain.h>
40
41using namespace pablo;
42using namespace llvm;
43
44namespace re {
45
46static cl::OptionCategory RegexOptions("Regex Toolchain Options",
47                                              "These options control the regular expression transformation and compilation.");
48const cl::OptionCategory * LLVM_READONLY re_toolchain_flags() {
49    return &RegexOptions;
50}
51
52static cl::bits<RE_PrintFlags> 
53    PrintOptions(cl::values(clEnumVal(ShowREs, "Print parsed or generated regular expressions"),
54                            clEnumVal(ShowAllREs, "Print all regular expression passes"),
55                            clEnumVal(ShowStrippedREs, "Print REs with nullable prefixes/suffixes removed"),
56                            clEnumVal(ShowSimplifiedREs, "Print final simplified REs")
57                            CL_ENUM_VAL_SENTINEL), cl::cat(RegexOptions));
58
59static cl::bits<RE_AlgorithmFlags>
60    AlgorithmOptions(cl::values(clEnumVal(DisableLog2BoundedRepetition, "disable log2 optimizations for bounded repetition of bytes"),
61                              clEnumVal(DisableIfHierarchy, "disable nested if hierarchy for generated Unicode classes (not recommended)"), 
62                              clEnumVal(DisableMatchStar, "disable MatchStar optimization"), 
63                              clEnumVal(DisableUnicodeMatchStar, "disable Unicode MatchStar optimization"),
64                              clEnumVal(DisableUnicodeLineBreak, "disable Unicode line breaks - use LF only")
65                              CL_ENUM_VAL_SENTINEL), cl::cat(RegexOptions));
66
67bool LLVM_READONLY AlgorithmOptionIsSet(RE_AlgorithmFlags flag) {
68    return AlgorithmOptions.isSet(flag);
69}
70
71int IfInsertionGap;
72static cl::opt<int, true> 
73    IfInsertionGapOption("if-insertion-gap",  cl::location(IfInsertionGap), cl::init(3),
74                         cl::desc("minimum number of nonempty elements between inserted if short-circuit tests"), 
75                         cl::cat(RegexOptions));
76
77RE * resolveModesAndExternalSymbols(RE * r, bool globallyCaseInsensitive) {
78    if (PrintOptions.isSet(ShowAllREs) || PrintOptions.isSet(ShowREs)) {
79        errs() << "Parser:\n" << Printer_RE::PrintRE(r) << '\n';
80    }
81    r = resolveGraphemeMode(r, false /* not in grapheme mode at top level*/);
82    if (PrintOptions.isSet(ShowAllREs)) {
83        errs() << "resolveGraphemeMode:\n" << Printer_RE::PrintRE(r) << '\n';
84    }
85    r = re::resolveUnicodeNames(r);
86    r = resolveCaseInsensitiveMode(r, globallyCaseInsensitive);
87    return r;
88}
89
90RE * excludeUnicodeLineBreak(RE * r) {
91    r = exclude_CC(r, re::makeCC(re::makeCC(0x0A, 0x0D), re::makeCC(re::makeCC(0x85), re::makeCC(0x2028, 0x2029))));
92    if (PrintOptions.isSet(ShowAllREs)) {
93        errs() << "excludeUnicodeLineBreak:\n" << Printer_RE::PrintRE(r) << '\n';
94    }
95    return r;
96}
97
98RE * regular_expression_passes(RE * r) {
99
100    //Optimization passes to simplify the AST.
101    r = removeNullablePrefix(r);
102    r = removeNullableSuffix(r);
103    r = RE_Star_Normal().transformRE(r);
104    if (codegen::OptLevel > 1) {
105        r = RE_Minimizer::minimize(r);
106    } else {
107        r = RE_Simplifier::simplify(r);
108    }
109    if (!DefiniteLengthBackReferencesOnly(r)) {
110        llvm::report_fatal_error("Future back reference support: references must be within a fixed distance from a fixed-length capture.");
111    }
112    return r;
113}
114
115static bool compare(const RE * const lh, const RE * const rh);
116
117static bool lessThan(const Vector * const lh, const Vector * const rh) {
118    assert (lh->getClassTypeId() == rh->getClassTypeId());
119    assert (lh->getClassTypeId() == RE::ClassTypeId::Alt || lh->getClassTypeId() == RE::ClassTypeId::Seq);
120    if (LLVM_LIKELY(lh->size() != rh->size())) {
121        return lh->size() < rh->size();
122    }
123    for (auto i = lh->begin(), j = rh->begin(); i != lh->end(); ++i, ++j) {
124        assert (*i && *j);
125        if (compare(*i, *j)) {
126            return true;
127        } else if (compare(*j, *i)) {
128            return false;
129        }
130    }
131    return false;
132}
133
134inline bool lessThan(const Name * const lh, const Name * const rh) {
135    if (lh->getType() != rh->getType()) {
136        return lh->getType() < rh->getType();
137    } else if (lh->hasNamespace() != rh->hasNamespace()) {
138        return lh->hasNamespace();
139    } else if (lh->hasNamespace() && (lh->getNamespace() != rh->getNamespace())) {
140        return lh->getNamespace() < rh->getNamespace();
141    } else if (lh->getName() != rh->getName()) {
142        return lh->getName() < rh->getName();
143    } else if (lh->getDefinition() == nullptr) {
144        return rh->getDefinition() != nullptr;
145    } else if (rh->getDefinition() == nullptr) {
146        return false;
147    } else {
148        return compare(lh->getDefinition(), rh->getDefinition());
149    }
150}
151
152inline bool lessThan(const Assertion * const lh, const Assertion * const rh) {
153    if (lh->getKind() != rh->getKind()) {
154        return lh->getKind() < rh->getKind();
155    }
156    if (lh->getSense() != rh->getSense()) {
157        return lh->getSense() < rh->getSense();
158    }
159    return compare(lh->getAsserted(), rh->getAsserted());
160}
161
162inline bool lessThan(const Rep * const lh, const Rep * const rh) {
163    if (lh->getLB() != rh->getLB()) {
164        return lh->getLB() < rh->getLB();
165    }
166    if (lh->getUB() != rh->getUB()) {
167        return lh->getUB() < rh->getUB();
168    }
169    return compare(lh->getRE(), rh->getRE());
170}
171
172inline bool lessThan(const Diff * const lh, const Diff * const rh) {
173    if (compare(lh->getLH(), rh->getLH())) {
174        return true;
175    } else if (compare(rh->getLH(), lh->getLH())) {
176        return false;
177    } else if (compare(lh->getRH(), rh->getRH())) {
178        return true;
179    } else {
180        return !compare(rh->getRH(), lh->getRH());
181    }
182}
183
184inline bool lessThan(const Range * const lh, const Range * const rh) {
185    if (compare(lh->getLo(), rh->getLo())) {
186        return true;
187    } else if (compare(rh->getLo(), lh->getLo())) {
188        return false;
189    } else if (compare(lh->getHi(), rh->getHi())) {
190        return true;
191    } else {
192        return !compare(rh->getHi(), lh->getHi());
193    }
194}
195
196static bool lessThan(const Intersect * const lh, const Intersect * const rh) {
197    if (compare(lh->getLH(), rh->getLH())) {
198        return true;
199    } else if (compare(rh->getLH(), lh->getLH())) {
200        return false;
201    } else if (compare(lh->getRH(), rh->getRH())) {
202        return true;
203    } else {
204        return !compare(rh->getRH(), lh->getRH());
205    }
206}
207
208inline bool lessThan(const Group * const lh, const Group * const rh) {
209    if (lh->getMode() != rh->getMode()) {
210        return lh->getMode() < rh->getMode();
211    }
212    if (lh->getSense() != rh->getSense()) {
213        return lh->getSense() < rh->getSense();
214    }
215    return compare(lh->getRE(), rh->getRE());
216}
217
218inline bool compare(const RE * const lh, const RE * const rh) {
219    using Type = RE::ClassTypeId;
220    assert (lh && rh);
221    const auto typeL = lh->getClassTypeId();
222    const auto typeR = rh->getClassTypeId();
223    if (LLVM_LIKELY(typeL != typeR)) {
224        return typeL < typeR;
225    }
226    switch (typeL) {
227        case Type::Alt:
228        case Type::Seq:
229            return lessThan(cast<Vector>(lh), cast<Vector>(rh));
230        case Type::End: case Type::Start:
231            return false;
232        case Type::Assertion:
233            return lessThan(cast<Assertion>(lh), cast<Assertion>(rh));
234        case Type::CC:
235            return *cast<CC>(lh) < *cast<CC>(rh);
236        case Type::Name:
237            return lessThan(cast<Name>(lh), cast<Name>(rh));
238        case Type::Group:
239            return lessThan(cast<Group>(lh), cast<Group>(rh));
240        case Type::Range:
241            return lessThan(cast<Range>(lh), cast<Range>(rh));
242        case Type::Diff:
243            return lessThan(cast<Diff>(lh), cast<Diff>(rh));
244        case Type::Intersect:
245            return lessThan(cast<Intersect>(lh), cast<Intersect>(rh));
246        case Type::Rep:
247            return lessThan(cast<Rep>(lh), cast<Rep>(rh));
248        default:
249            llvm_unreachable("RE object of unknown type given to Memoizer");
250            return false;
251    }
252}
253
254inline bool RE_Transformer::MemoizerComparator::operator()(const RE * const lh, const RE * const rh) const {
255    return compare(lh, rh);
256}
257
258RE * RE_Transformer::transformRE(RE * re) {
259    RE * initialRE = re;
260    RE * finalRE = transform(re);
261    if (PrintOptions.isSet(ShowAllREs) && (initialRE != finalRE) && (mTransformationName != "")) {
262        errs() << mTransformationName << ":\n" << Printer_RE::PrintRE(finalRE) << '\n';
263    }
264    return finalRE;
265}
266
267RE * RE_Transformer::transform(RE * const from) {
268    using T = RE::ClassTypeId;
269    RE * to = from;
270    #define TRANSFORM(Type) \
271        case T::Type: to = transform##Type(llvm::cast<Type>(from)); break
272    switch (from->getClassTypeId()) {
273        TRANSFORM(Alt);
274        TRANSFORM(Assertion);
275        TRANSFORM(CC);
276        TRANSFORM(Range);
277        TRANSFORM(Diff);
278        TRANSFORM(End);
279        TRANSFORM(Intersect);
280        TRANSFORM(Name);
281        TRANSFORM(Group);
282        TRANSFORM(Rep);
283        TRANSFORM(Seq);
284        TRANSFORM(Start);
285        default: llvm_unreachable("Unknown RE type");
286    }
287    #undef TRANSFORM
288    assert (to);
289
290    // Do we already have a memoized version of the transformed RE?
291    if (from != to) {
292        const auto f = mMap.find(to);
293        if (LLVM_LIKELY(f == mMap.end())) {
294            mMap.emplace(to, to);
295        } else {
296            to = f->second;
297        }
298    }
299
300    return to;
301}
302
303RE * RE_Transformer::transformName(Name * nm) {
304    if (mNameTransform == NameTransformationMode::None) {
305        return nm;
306    }
307    RE * const d = nm->getDefinition();
308    if (LLVM_UNLIKELY(d == nullptr)) {
309        UndefinedNameError(nm);
310    }
311    return transform(d);
312}
313
314RE * RE_Transformer::transformCC(CC * cc) {
315    return cc;
316}
317
318RE * RE_Transformer::transformStart(Start * s) {
319    return s;
320}
321
322RE * RE_Transformer::transformEnd(End * e) {
323    return e;
324}
325
326RE * RE_Transformer::transformSeq(Seq * seq) {
327    std::vector<RE *> elems;
328    elems.reserve(seq->size());
329    bool any_changed = false;
330    for (RE * e : *seq) {
331        RE * e1 = transform(e);
332        if (e1 != e) any_changed = true;
333        elems.push_back(e1);
334    }
335    if (!any_changed) return seq;
336    return makeSeq(elems.begin(), elems.end());
337}
338
339RE * RE_Transformer::transformAlt(Alt * alt) {
340    std::vector<RE *> elems;
341    elems.reserve(alt->size());
342    bool any_changed = false;
343    for (RE * e : *alt) {
344        RE * e1 = transform(e);
345        if (e1 != e) any_changed = true;
346        elems.push_back(e1);
347    }
348    if (!any_changed) return alt;
349    return makeAlt(elems.begin(), elems.end());
350}
351
352RE * RE_Transformer::transformRep(Rep * r) {
353    RE * x0 = r->getRE();
354    RE * x = transform(x0);
355    if (x == x0) {
356        return r;
357    } else {
358        return makeRep(x, r->getLB(), r->getUB());
359    }
360}
361
362RE * RE_Transformer::transformIntersect(Intersect * ix) {
363    RE * x0 = ix->getLH();
364    RE * y0 = ix->getRH();
365    RE * x = transform(x0);
366    RE * y = transform(y0);
367    if ((x == x0) && (y == y0)) {
368        return ix;
369    } else {
370        return makeIntersect(x, y);
371    }
372}
373
374RE * RE_Transformer::transformDiff(Diff * d) {
375    RE * x0 = d->getLH();
376    RE * y0 = d->getRH();
377    RE * x = transform(x0);
378    RE * y = transform(y0);
379    if ((x == x0) && (y == y0)) {
380        return d;
381    } else {
382        return makeDiff(x, y);
383    }
384}
385
386RE * RE_Transformer::transformRange(Range * rg) {
387    RE * x0 = rg->getLo();
388    RE * y0 = rg->getHi();
389    RE * x = transform(x0);
390    RE * y = transform(y0);
391    if ((x == x0) && (y == y0)) {
392        return rg;
393    } else {
394        return makeRange(x, y);
395    }
396}
397
398RE * RE_Transformer::transformGroup(Group * g) {
399    RE * x0 = g->getRE();
400    RE * x = transform(x0);
401    if (x == x0) {
402        return g;
403    } else {
404        return makeGroup(g->getMode(), x, g->getSense());
405    }
406}
407
408RE * RE_Transformer::transformAssertion(Assertion * a) {
409    RE * x0 = a->getAsserted();
410    RE * x = transform(x0);
411    if (x == x0) {
412        return a;
413    } else {
414        return makeAssertion(x, a->getKind(), a->getSense());
415    }
416}
417
418inline bool RE_Inspector::MemoizerComparator::operator()(const RE * const lh, const RE * const rh) const {
419    return compare(lh, rh);
420}
421
422void RE_Inspector::inspectRE(RE * re) {
423    inspect(re);
424}
425
426void RE_Inspector::inspect(RE * const re) {
427    assert (re);
428    if (mIgnoreNonUnique == InspectionMode::IgnoreNonUnique) {
429        if (mMap.count(re)) return;
430        mMap.emplace(re);
431    }
432    using T = RE::ClassTypeId;
433    #define INSPECT(Type) \
434        case T::Type: inspect##Type(llvm::cast<Type>(re)); break
435    switch (re->getClassTypeId()) {
436        INSPECT(Alt);
437        INSPECT(Assertion);
438        INSPECT(CC);
439        INSPECT(Range);
440        INSPECT(Diff);
441        INSPECT(End);
442        INSPECT(Intersect);
443        INSPECT(Name);
444        INSPECT(Group);
445        INSPECT(Rep);
446        INSPECT(Seq);
447        INSPECT(Start);
448        default: llvm_unreachable("Unknown RE type");
449    }
450    #undef INSPECT
451}
452
453void RE_Inspector::inspectName(Name * nm) {
454    RE * const d = nm->getDefinition();
455    if (d) inspect(d);
456}
457
458void RE_Inspector::inspectCC(CC * cc) {
459
460}
461
462void RE_Inspector::inspectStart(Start * s) {
463
464}
465
466void RE_Inspector::inspectEnd(End * e) {
467
468}
469
470void RE_Inspector::inspectSeq(Seq * seq) {
471    for (RE * e : *seq) {
472        inspect(e);
473    }
474}
475
476void RE_Inspector::inspectAlt(Alt * alt) {
477    for (RE * e : *alt) {
478        inspect(e);
479    }
480}
481
482void RE_Inspector::inspectRep(Rep * r) {
483    inspect(r->getRE());
484}
485
486void RE_Inspector::inspectIntersect(Intersect * ix) {
487    inspect(ix->getLH());
488    inspect(ix->getRH());
489}
490
491void RE_Inspector::inspectDiff(Diff * d) {
492    inspect(d->getLH());
493    inspect(d->getRH());
494}
495
496void RE_Inspector::inspectRange(Range * rg) {
497    inspect(rg->getLo());
498    inspect(rg->getHi());
499}
500
501void RE_Inspector::inspectGroup(Group * g) {
502    inspect(g->getRE());
503}
504
505void RE_Inspector::inspectAssertion(Assertion * a) {
506    inspect(a->getAsserted());
507}
508
509}
Note: See TracBrowser for help on using the repository browser.