Changeset 6268


Ignore:
Timestamp:
Jan 4, 2019, 2:05:30 PM (2 weeks ago)
Author:
cameron
Message:

Contextual assertion simplification using more context and additional assertion types

Location:
icGREP/icgrep-devel/icgrep/re
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/re/re_contextual_simplification.cpp

    r6264 r6268  
    88#include <re/re_any.h>
    99#include <re/re_cc.h>
    10 #include <re/re_diff.h>
    1110#include <re/re_name.h>
    1211#include <re/re_seq.h>
     12#include <re/re_alt.h>
    1313#include <re/re_assertion.h>
    1414#include <re/re_start.h>
    1515#include <re/re_end.h>
    16 #include <re/re_reverse.h>
     16#include <re/re_diff.h>
     17#include <re/re_intersect.h>
     18#include <re/re_rep.h>
     19#include <re/re_analysis.h>
    1720#include <re/validation.h>
    1821#include <llvm/Support/Casting.h>
     
    2023#include <llvm/Support/raw_ostream.h>
    2124#include <re/printer_re.h>
    22 
     25#include <boost/range/adaptor/reversed.hpp>
     26
     27using namespace llvm;
    2328namespace re {
    2429   
     30class GCB_Any_Free_Validator: public RE_Validator {
     31public:
     32    GCB_Any_Free_Validator() : RE_Validator(""), mAnySeen(false), mGCBseen(false) {}
     33    bool validateName(const Name * n) override {
     34        std::string nm = n->getName();
     35        if (nm == ".") {
     36            if (mGCBseen) return false;
     37            mAnySeen = true;
     38        }
     39        if (nm == "\\b{g}") {
     40            if (mAnySeen) return false;
     41            mGCBseen = true;
     42        }
     43        return true;
     44    }
     45private:
     46    bool mAnySeen;
     47    bool mGCBseen;
     48};
     49
     50bool has_GCB_Any(RE * r) {
     51    return !GCB_Any_Free_Validator().validateRE(r);
     52}
     53
     54
     55RE * firstSym(RE * re) {
     56    if (Name * name = dyn_cast<Name>(re)) {
     57        if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
     58            return firstSym(name->getDefinition());
     59        } else {
     60            UndefinedNameError(name);
     61        }
     62    } else if (isa<CC>(re) || isa<Any>(re) || isa<Start>(re) || isa<End>(re)) {
     63        return re;
     64    } else if (Seq * seq = dyn_cast<Seq>(re)) {
     65        CC * cc = makeCC();
     66        for (auto & si : *seq) {
     67            RE * fi = firstSym(si);
     68            if (isa<Any>(fi)) return fi;
     69            cc = makeCC(cc, cast<CC>(fi));
     70            if (!isNullable(si)) {
     71                break;
     72            }
     73        }
     74        return cc;
     75    } else if (Alt * alt = dyn_cast<Alt>(re)) {
     76        CC * cc = makeCC();
     77        for (auto & ai : *alt) {
     78            RE * fi = firstSym(ai);
     79            if (isa<Any>(fi)) return fi;
     80            cc = makeCC(cc, cast<CC>(fi));
     81        }
     82        return cc;
     83    } else if (Rep * rep = dyn_cast<Rep>(re)) {
     84        return firstSym(rep->getRE());
     85    } else if (Diff * diff = dyn_cast<Diff>(re)) {
     86        RE * lh = firstSym(diff->getLH());
     87        RE * rh = firstSym(diff->getRH());
     88        if (isa<Any>(rh)) return makeCC();
     89        if (isa<Any>(lh)) lh = makeCC(0, 0x10FFFF);
     90        return subtractCC(cast<CC>(lh), cast<CC>(rh));
     91    } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
     92        RE * lh = firstSym(ix->getLH());
     93        RE * rh = firstSym(ix->getRH());
     94        if (isa<Any>(lh)) return rh;
     95        if (isa<Any>(rh)) return lh;
     96        return intersectCC(cast<CC>(lh), cast<CC>(rh));
     97    }
     98    return makeCC();
     99}
     100
     101RE * finalSym(RE * re) {
     102    if (Name * name = dyn_cast<Name>(re)) {
     103        if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
     104            return finalSym(name->getDefinition());
     105        } else {
     106            UndefinedNameError(name);
     107        }
     108    } else if (isa<CC>(re) || isa<Any>(re) || isa<Start>(re) || isa<End>(re)) {
     109        return re;
     110    } else if (Seq * seq = dyn_cast<Seq>(re)) {
     111        CC * cc = makeCC();
     112        for (auto & si : boost::adaptors::reverse(*seq)) {
     113            RE * fi = finalSym(si);
     114            if (isa<Any>(fi)) return fi;
     115            cc = makeCC(cc, cast<CC>(fi));
     116            if (!isNullable(si)) {
     117                break;
     118            }
     119        }
     120        return cc;
     121    } else if (Alt * alt = dyn_cast<Alt>(re)) {
     122        CC * cc = makeCC();
     123        for (auto & ai : *alt) {
     124            RE * fi = finalSym(ai);
     125            if (isa<Any>(fi)) return fi;
     126            cc = makeCC(cc, cast<CC>(fi));
     127        }
     128        return cc;
     129    } else if (Rep * rep = dyn_cast<Rep>(re)) {
     130        return finalSym(rep->getRE());
     131    } else if (Diff * diff = dyn_cast<Diff>(re)) {
     132        RE * lh = finalSym(diff->getLH());
     133        RE * rh = finalSym(diff->getRH());
     134        if (isa<Any>(rh)) return makeCC();
     135        if (isa<Any>(lh)) lh = makeCC(0, 0x10FFFF);
     136        return subtractCC(cast<CC>(lh), cast<CC>(rh));
     137    } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
     138        RE * lh = finalSym(ix->getLH());
     139        RE * rh = finalSym(ix->getRH());
     140        if (isa<Any>(lh)) return rh;
     141        if (isa<Any>(rh)) return lh;
     142        return intersectCC(cast<CC>(lh), cast<CC>(rh));
     143    }
     144    return makeCC();
     145}
     146
     147
    25148// RE_Context identifies the position of a regular expression in its
    26149// containing sequence, as well as the context of that containing sequence
     
    30153public:
    31154    RE_Context(RE_Context * c, Seq * s, unsigned pos) : parentContext(c), contextSeq(s), contextPos(pos) {}
     155    // Return the preceding context item.
     156    bool empty() {return contextSeq == nullptr;}
    32157    RE_Context priorContext();
     158    // Return the preceding Unicode CC item, if any.  Return a null context
     159    // if the current item is not a single Unicode unit length item, or if the
     160    // prior item is nullable.
     161    RE_Context priorCCorNull();
    33162    RE_Context followingContext();
     163    // Return the following Unicode CC item, if any.  Return a null context
     164    // if the current item is not a single Unicode unit length item, or if the
     165    // following item is nullable.
     166    RE_Context followingCCorNull();
    34167    RE * currentItem();
    35168   
     
    50183}
    51184
     185
     186RE_Context RE_Context::priorCCorNull() {
     187    if (!contextSeq || !isUnicodeUnitLength((*contextSeq)[contextPos])) return RE_Context{nullptr, nullptr, 0};
     188    RE_Context prior = priorContext();
     189    // Skip over zero width assertions which do not provide any matchable context.
     190    while ((prior.contextSeq) && isZeroWidth((*prior.contextSeq)[prior.contextPos]) && !isa<Start>((*prior.contextSeq)[prior.contextPos])) {
     191        prior = prior.priorContext();
     192    }
     193    if ((!prior.contextSeq) || isNullable((*prior.contextSeq)[prior.contextPos])) {
     194        return RE_Context{nullptr, nullptr, 0};
     195    }
     196    return prior;
     197}
     198
    52199RE_Context RE_Context::followingContext() {
    53200    if (!contextSeq) return RE_Context{nullptr, nullptr, 0};
     
    61208}
    62209
     210RE_Context RE_Context::followingCCorNull() {
     211    if (!contextSeq || !isUnicodeUnitLength((*contextSeq)[contextPos])) return RE_Context{nullptr, nullptr, 0};
     212    RE_Context following = followingContext();
     213    // Skip over zero width assertions which do not provide any matchable context.
     214    while ((following.contextSeq) && isZeroWidth((*following.contextSeq)[following.contextPos]) && !isa<End>((*following.contextSeq)[following.contextPos])) {
     215        following = following.followingContext();
     216    }
     217    if ((!following.contextSeq) || isNullable((*following.contextSeq)[following.contextPos])) {
     218        return RE_Context{nullptr, nullptr, 0};
     219    }
     220    return following;
     221}
     222
    63223RE * RE_Context::currentItem() {
    64224    if (contextSeq) return (*contextSeq)[contextPos];
     
    66226}
    67227
    68 RE * simplifyCC(CC * assertedCC, CC * contextCC) {
    69     //llvm::errs() << "assertedCC:" << Printer_RE::PrintRE(assertedCC) << "\n";
    70     //llvm::errs() << "contextCC:" << Printer_RE::PrintRE(contextCC) << "\n";
    71     if ((*contextCC).subset(*assertedCC)) return makeSeq();
    72     if ((*contextCC).intersects(*assertedCC)) return assertedCC;
    73     return makeAlt();
    74 }
    75 
    76 class SimplifyAsserted : public RE_Transformer {
    77 public:
    78     SimplifyAsserted(RE_Context & context, Assertion::Kind kind) :
    79         RE_Transformer("SimplifyAsserted"),
    80         mContext(context), mKind(kind) {}
    81        
    82     RE * transformName(Name * name) override {
    83         RE * defn = name->getDefinition();
    84         if (defn) {
    85             RE * s = transform(defn);
    86             if (s == defn) return name;
    87             else return s;
    88         }
    89         return name;
    90     }
    91    
    92     RE * transformSeq(Seq * s) override {
    93         RE_Context ctxt = mContext;
    94         bool allSatisfied = true;
    95         if (mKind == Assertion::Kind::Lookbehind) {
    96             for (unsigned i = s->size() - 1; i >= 0; i--) {
    97                 RE * simplifiedElem = SimplifyAsserted(ctxt, mKind).transform((*s)[i]);
    98                 if (isEmptySet(simplifiedElem)) {
    99                     return makeAlt();
    100                 } else if (!isEmptySeq(simplifiedElem)) {
    101                     allSatisfied = false;
    102                 } else if (allSatisfied && (i == 0)) {
    103                     return makeSeq();
    104                 }
    105                 ctxt = ctxt.priorContext();
    106                 RE * prev = ctxt.currentItem();
    107                 if (!prev || !llvm::isa<CC>(ctxt.currentItem())) {
    108                     return s;
    109                 }
    110             }
    111         } else if (mKind == Assertion::Kind::Lookahead) {
    112             for (unsigned i = 0; i < s->size(); i++) {
    113                 RE * simplifiedElem = SimplifyAsserted(ctxt, mKind).transform((*s)[i]);
    114                 if (isEmptySet(simplifiedElem)) {
    115                     return makeAlt();
    116                 } else if (!isEmptySeq(simplifiedElem)) {
    117                     allSatisfied = false;
    118                 } else if (allSatisfied && (i == s->size() - 1)) {
    119                     return makeSeq();
    120                 }
    121                 ctxt = ctxt.followingContext();
    122                 RE * next = ctxt.currentItem();
    123                 if (!next || !llvm::isa<CC>(next)) {
    124                     return s;
    125                 }
    126             }
    127         }
    128         return s;
    129     }
    130    
    131     RE * transformCC(CC * cc) override {
    132         RE * context = nullptr;
    133         if (mKind == Assertion::Kind::Lookbehind) {
    134             context = mContext.priorContext().currentItem();
    135         } else if (mKind == Assertion::Kind::Lookahead) {
    136             context = mContext.followingContext().currentItem();
    137         }
    138         if (context) {
    139             if (CC * contextCC = llvm::dyn_cast<CC>(context)) {
    140                 return simplifyCC(cc, contextCC);
    141             }
    142         }
    143         return cc;
    144     }
    145 private:
    146     RE_Context mContext;
    147     Assertion::Kind mKind;
     228enum class MatchResult {Fail, Possible, Success};
     229
     230struct ContextMatchCursor {
     231    RE_Context ctxt;
     232    MatchResult rslt;
    148233};
     234
     235ContextMatchCursor ctxt_match(RE * re, Assertion::Kind kind, ContextMatchCursor cursor) {
     236    if (cursor.ctxt.empty()) return ContextMatchCursor{cursor.ctxt, MatchResult::Possible};
     237    if (CC * cc = dyn_cast<CC>(re)) {
     238        RE_Context nextContext = cursor.ctxt;
     239        RE * item = cursor.ctxt.currentItem();
     240        if (isZeroWidth(item) || isNullable(item)) {
     241            return ContextMatchCursor{RE_Context{nullptr, nullptr, 0}, MatchResult::Possible};
     242        }
     243        RE * contextSym = nullptr;
     244        if (kind == Assertion::Kind::Lookbehind) {
     245            contextSym = finalSym(item);
     246            nextContext = cursor.ctxt.priorCCorNull();
     247        } else {
     248            contextSym = firstSym(item);
     249            nextContext = cursor.ctxt.followingCCorNull();
     250        }
     251        //errs() << "assertedCC:" << Printer_RE::PrintRE(cc) << "\n";
     252        //errs() << "contextSym:" << Printer_RE::PrintRE(contextSym) << "\n";
     253        if (CC * contextCC = dyn_cast<CC>(contextSym)) {
     254            if (!(*contextCC).intersects(*cc)) return ContextMatchCursor{cursor.ctxt, MatchResult::Fail};
     255            if ((cursor.rslt == MatchResult::Success) && ((*contextCC).subset(*cc))) {
     256                return ContextMatchCursor{nextContext, MatchResult::Success};
     257            }
     258        }
     259        if (isa<Start>(contextSym) || isa<End>(contextSym)) {
     260            return ContextMatchCursor{cursor.ctxt, MatchResult::Fail};
     261        }
     262        return ContextMatchCursor{nextContext, MatchResult::Possible};
     263    } else if (isa<Start>(re)) {
     264        if (kind == Assertion::Kind::Lookbehind) {
     265            RE * contextSym = finalSym(cursor.ctxt.currentItem());
     266            RE_Context nextContext = cursor.ctxt.priorCCorNull();
     267            if (isa<Start>(contextSym)) return ContextMatchCursor{nextContext, MatchResult::Success};
     268        }
     269        return ContextMatchCursor{cursor.ctxt, MatchResult::Fail};
     270    } else if (isa<End>(re)) {
     271        if (kind == Assertion::Kind::Lookahead) {
     272            RE * contextSym = firstSym(cursor.ctxt.currentItem());
     273            RE_Context nextContext = cursor.ctxt.followingCCorNull();
     274            if (isa<End>(contextSym)) return ContextMatchCursor{nextContext, MatchResult::Success};
     275        }
     276        return ContextMatchCursor{cursor.ctxt, MatchResult::Fail};
     277    } else if (Name * n = dyn_cast<Name>(re)) {
     278        RE * def = n->getDefinition();
     279        ContextMatchCursor submatch = ctxt_match(def, kind, cursor);
     280        if (submatch.rslt == MatchResult::Fail) return submatch;
     281        if (n->getType() == Name::Type::Reference) {
     282            return ContextMatchCursor{submatch.ctxt, MatchResult::Possible};
     283        } else {
     284            return submatch;
     285        }
     286    } else if (Alt * alt = dyn_cast<Alt>(re)) {
     287        ContextMatchCursor bestSoFar = ContextMatchCursor{cursor.ctxt, MatchResult::Fail};
     288        for (RE * a: *alt) {
     289            ContextMatchCursor a_match = ctxt_match(a, kind, cursor);
     290            if (a_match.rslt == cursor.rslt) return a_match;
     291            if (a_match.rslt == MatchResult::Possible) bestSoFar = a_match;
     292        }
     293        return bestSoFar;
     294    } else if (Seq * seq = dyn_cast<Seq>(re)) {
     295        ContextMatchCursor working = cursor;
     296        if (kind == Assertion::Kind::Lookahead) {
     297            for (RE * s: *seq) {
     298                working = ctxt_match(s, kind, working);
     299                if (working.rslt == MatchResult::Fail) return working;
     300            }
     301        } else {
     302            for (auto i = seq->rbegin(); i != seq->rend(); ++i) {
     303                working = ctxt_match(*i, kind, working);
     304                if (working.rslt == MatchResult::Fail) return working;
     305            }
     306        }
     307        return working;
     308    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
     309        int lb = rep->getLB();
     310        int ub = rep->getUB();
     311        RE * repeated = rep->getRE();
     312        ContextMatchCursor lb_cursor = cursor;
     313        for (int i = 0; i < lb; i++) {
     314            lb_cursor = ctxt_match(repeated, kind, lb_cursor);
     315            if (lb_cursor.rslt == MatchResult::Fail) return lb_cursor;
     316        }
     317        if (ub == Rep::UNBOUNDED_REP) {
     318            ContextMatchCursor star_rslt = lb_cursor;
     319            for (;;) {
     320                ContextMatchCursor next = ctxt_match(repeated, kind, star_rslt);
     321                if (next.rslt == MatchResult::Fail) return star_rslt;
     322                star_rslt = next;
     323            }
     324        } else {
     325            ContextMatchCursor ub_cursor = lb_cursor;
     326            for (int i = lb; i < ub; i++) {
     327                ContextMatchCursor next = ctxt_match(repeated, kind, ub_cursor);
     328                if (next.rslt == MatchResult::Fail) return ub_cursor;
     329                ub_cursor = next;
     330            }
     331            return ub_cursor;
     332        }
     333    } else if (const Diff * d = dyn_cast<Diff>(re)) {
     334        ContextMatchCursor lh_match = ctxt_match(d->getLH(), kind, cursor);
     335        ContextMatchCursor rh_match = ctxt_match(d->getRH(), kind, cursor);
     336        if (rh_match.rslt == MatchResult::Fail) return lh_match;
     337        if (rh_match.rslt == MatchResult::Success) return ContextMatchCursor{cursor.ctxt, MatchResult::Fail};
     338        if (lh_match.rslt == MatchResult::Fail) return lh_match;
     339        return ContextMatchCursor{lh_match.ctxt, MatchResult::Possible};
     340    } else if (const Intersect * x = dyn_cast<Intersect>(re)) {
     341        ContextMatchCursor lh_match = ctxt_match(x->getLH(), kind, cursor);
     342        ContextMatchCursor rh_match = ctxt_match(x->getRH(), kind, cursor);
     343        if (lh_match.rslt == MatchResult::Fail) return lh_match;
     344        if (rh_match.rslt == MatchResult::Fail) return rh_match;
     345        if (lh_match.rslt == MatchResult::Success) return rh_match;
     346        if (rh_match.rslt == MatchResult::Success) return lh_match;
     347        return lh_match;
     348    } else if (const Assertion * a = dyn_cast<Assertion>(re)) {
     349        if (a->getKind() == kind) {
     350            ContextMatchCursor assertResult = ctxt_match(a->getAsserted(), kind, cursor);
     351            if (assertResult.rslt == MatchResult::Possible) return ContextMatchCursor{cursor.ctxt, MatchResult::Possible};
     352            if ((assertResult.rslt == MatchResult::Success) == (a->getSense() == Assertion::Sense::Positive)) {
     353                return ContextMatchCursor{cursor.ctxt, MatchResult::Success};
     354            }
     355            return ContextMatchCursor{cursor.ctxt, MatchResult::Fail};
     356        }
     357        return ContextMatchCursor{cursor.ctxt, MatchResult::Possible};
     358    }
     359    return ContextMatchCursor{cursor.ctxt, MatchResult::Possible};
     360}
    149361
    150362class ContextualAssertionSimplifier : public RE_Transformer {
    151363public:
    152     ContextualAssertionSimplifier(RE_Context ctxt = RE_Context(nullptr, nullptr, 0)) :
     364    ContextualAssertionSimplifier() :
    153365        RE_Transformer("ContextualAssertionSimplifier", NameTransformationMode::TransformDefinition),
     366        mContext(RE_Context(nullptr, nullptr, 0)) {}
     367    ContextualAssertionSimplifier(RE_Context ctxt) :
     368        RE_Transformer("", NameTransformationMode::TransformDefinition),
    154369        mContext(ctxt) {}
    155370    RE * transformSeq(Seq * s) override {
     
    169384    RE * transformRep(Rep * r) override {
    170385        RE * repeated = r->getRE();
    171         RE * t = ContextualAssertionSimplifier().transformRE(repeated);
     386        // The repeated subexpression can be transformed, but only with an
     387        // empty context.
     388        RE * t = ContextualAssertionSimplifier(RE_Context(nullptr, nullptr, 0)).transformRE(repeated);
    172389        if (t == repeated) return r;
    173390        return makeRep(t, r->getLB(), r->getUB());
     
    177394        RE * prior = mContext.priorContext().currentItem();
    178395        if (prior) {
    179             if (llvm::isa<Start>(prior)) {
     396            if (isa<Start>(prior)) {
    180397                return makeSeq();
    181             } else if (llvm::isa<CC>(prior)) {
     398            } else if (isa<CC>(prior)) {
    182399                return makeAlt();
    183400            }
     
    189406        RE * following = mContext.followingContext().currentItem();
    190407        if (following) {
    191             if (llvm::isa<End>(following)) {
     408            if (isa<End>(following)) {
    192409                return makeSeq();
    193             } else if (llvm::isa<CC>(following)) {
     410            } else if (isa<CC>(following)) {
    194411                return makeAlt();
    195412            }
     
    202419        Assertion::Kind k = a->getKind();
    203420        Assertion::Sense s = a->getSense();
    204         RE * t = SimplifyAsserted(mContext, k).transformRE(asserted);
    205         if (t == asserted) return a;
    206         return makeAssertion(t, k, s);
     421        RE_Context ctxt = mContext;
     422        if (k == Assertion::Kind::Lookahead) {
     423            ctxt = mContext.followingContext();
     424        } else if (k == Assertion::Kind::Lookbehind) {
     425            ctxt = mContext.priorContext();
     426        } else {
     427            // BoundaryAssertion - TODO - evaluate if possible
     428            //RE * prior = mContext.priorContext().currentItem();
     429            //RE * following = mContext.followingContext().currentItem();
     430            return a;
     431        }
     432        ContextMatchCursor x = ctxt_match(asserted, k, ContextMatchCursor{ctxt, MatchResult::Success});
     433        if (x.rslt == MatchResult::Possible) return a;
     434        if ((x.rslt == MatchResult::Success) == (s == Assertion::Sense::Positive)) return makeSeq();
     435        return makeAlt();
    207436    }
    208437   
     
    213442   
    214443RE * simplifyAssertions(RE * r) {
     444    // If a regular expression has an Any and a GCB, it is unlikely
     445    // to be of much use to eliminate assertions and possibly very
     446    // costly to inline multiple partially optimized assertions.
     447    if (has_GCB_Any(r)) return r;
    215448    return ContextualAssertionSimplifier().transformRE(r);
    216449}
  • icGREP/icgrep-devel/icgrep/re/re_contextual_simplification.h

    r6264 r6268  
    1212namespace re {
    1313
    14 RE * simplifyAssertions(RE * r);
     14    RE * simplifyAssertions(RE * r);
     15class RE_ContextSimplifier : public RE_Transformer {
     16public:
     17    inline RE_ContextSimplifier() : RE_Transformer("ContextSimplification") {}
     18    RE * transformSeq(Seq * s) override;
     19};
     20
    1521}
    1622
  • icGREP/icgrep-devel/icgrep/re/re_toolchain.cpp

    r6264 r6268  
    101101    }
    102102    r = simplifyAssertions(r);
    103     r = lookaheadPromotion(r);
     103    //r = lookaheadPromotion(r);
    104104    return r;
    105105}
Note: See TracChangeset for help on using the changeset viewer.