Changeset 6171


Ignore:
Timestamp:
Oct 4, 2018, 3:37:35 PM (2 months ago)
Author:
cameron
Message:

NullablePrefix/Suffix? removal using RE_Transformer; clean out some setters

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

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/re/re_assertion.h

    r5896 r6171  
    5555
    5656inline RE * makeAssertion(RE * asserted, Assertion::Kind k, Assertion::Sense s) {
    57     if (RE_Nullable::isNullable(asserted)) {
     57    if (isNullable(asserted)) {
    5858        if (k == Assertion::Kind::Boundary) {
    5959            if (s == Assertion::Sense::Positive) return makeAlt();
  • icGREP/icgrep-devel/icgrep/re/re_intersect.h

    r4516 r6171  
    1717        return mLh;
    1818    }
    19     void setLH(RE * lh) {
    20         mLh = lh;
    21     }
    2219    RE * getRH() const {
    2320        return mRh;
    24     }
    25     void setRH(RE * rh) {
    26         mRh = rh;
    2721    }
    2822protected:
  • icGREP/icgrep-devel/icgrep/re/re_local.cpp

    r6170 r6171  
    4343        for (auto & si : *seq) {
    4444            cc = combine(cc, first(si));
    45             if (!RE_Nullable::isNullable(si)) {
     45            if (!isNullable(si)) {
    4646                break;
    4747            }
     
    8585        for (auto & si : boost::adaptors::reverse(*seq)) {
    8686            cc = combine(cc, final(si));
    87             if (!RE_Nullable::isNullable(si)) {
     87            if (!isNullable(si)) {
    8888                break;
    8989            }
  • icGREP/icgrep-devel/icgrep/re/re_nullable.cpp

    r5891 r6171  
    99#include <re/re_seq.h>             // for Seq, makeSeq
    1010#include <re/re_group.h>             // for Seq, makeSeq
     11#include <re/re_toolchain.h>
    1112#include <vector>                  // for vector, allocator
    1213#include <llvm/Support/Casting.h>  // for dyn_cast, isa
     
    2425namespace re {
    2526
    26    
    27 RE * RE_Nullable::excludeNullable(RE * re) {
    28     if (!isNullable(re)) return re;
    29     if (Seq * seq = dyn_cast<Seq>(re)) {
    30         // All items in the seq must be nullable.  We must allow
    31         // all possibilities that all but one continue to match empty.
    32         std::vector<RE*> alts;
    33         for (auto i = 0; i < seq->size(); i++) {
    34             std::vector<RE*> list;
    35             for (auto j = 0; j < seq->size(); j++) {
    36                 if (i == j) {
    37                     list.push_back(excludeNullable(&seq[j]));
    38                 } else {
    39                     list.push_back(&seq[j]);
    40                 }
    41             }
    42             alts.push_back(makeSeq(list.begin(), list.end()));
    43         }
    44         return makeAlt(alts.begin(), alts.end());
    45     } else if (Alt * alt = dyn_cast<Alt>(re)) {
    46         std::vector<RE*> list;
    47         for (auto i = alt->begin(); i != alt->end(); ++i) {
    48             list.push_back(excludeNullable(*i));
    49         }
    50         return makeAlt(list.begin(), list.end());
    51     } else if (Rep * rep = dyn_cast<Rep>(re)) {
    52         auto lb = rep->getLB();
    53         auto ub = rep->getUB();
    54         auto e = rep->getRE();
    55         if (!isNullable(e)) {
    56             assert (lb == 0);  // because isNullable(re) is true
    57             return makeRep(e, 1, ub);
    58         }
    59         auto e1 = excludeNullable(e);
    60         if (ub == 1) {
    61             return e1;
    62         } else {
    63             return makeSeq({e1, makeRep(e, lb == 0 ? 0 : lb - 1, ub == Rep::UNBOUNDED_REP ? ub : ub - 1)});
    64         }
    65     } else if (Group * g = dyn_cast<Group>(re)) {
    66         return makeGroup(g->getMode(), excludeNullable(g->getRE()), g->getSense());
    67     } else if (Name * name = dyn_cast<Name>(re)) {
    68         return excludeNullable(name->getDefinition());
    69     }
    70     return re;
    71 }
    72 
    73    
    74 RE * RE_Nullable::removeNullablePrefix(RE * re) {
    75     if (!hasNullablePrefix(re)) return re;
    76     if (Seq * seq = dyn_cast<Seq>(re)) {
    77         std::vector<RE*> list;
    78         for (auto i = seq->begin(); i != seq->end(); ++i) {
    79             if (!isNullable(*i)) {
    80                 list.push_back(removeNullablePrefix(*i));
    81                 std::copy(++i, seq->end(), std::back_inserter(list));
    82                 break;
    83             }
    84         }
    85         return makeSeq(list.begin(), list.end());
    86     } else if (Alt * alt = dyn_cast<Alt>(re)) {
    87         std::vector<RE*> list;
    88         for (auto i = alt->begin(); i != alt->end(); ++i) {
    89             list.push_back(removeNullablePrefix(*i));
    90         }
    91         return makeAlt(list.begin(), list.end());
    92     } else if (Rep * rep = dyn_cast<Rep>(re)) {
    93         auto lb = rep->getLB();
    94         auto e = rep->getRE();
    95         if ((lb == 0) || isNullable(e)) {
    96             return makeSeq();
    97         }
    98         else if (hasNullablePrefix(e)) {
    99             return makeSeq({removeNullablePrefix(e), makeRep(e, lb - 1, lb - 1)});
    100         }
    101         else {
    102             return makeRep(e, lb, lb);
    103         }
    104     } else if (Name * name = dyn_cast<Name>(re)) {
    105         auto def = name->getDefinition();
    106         if (hasNullablePrefix(def)) {
    107             return removeNullablePrefix(def);
    108         }
    109     }
    110     return re;
    111 }
    112 
    113 RE * RE_Nullable::removeNullableSuffix(RE * re) {
    114     if (Seq * seq = dyn_cast<Seq>(re)) {
    115         std::vector<RE*> list;
    116         for (auto i = seq->rbegin(); i != seq->rend(); ++i) {
    117             if (!isNullable(*i)) {
    118                 std::copy(seq->begin(), (i + 1).base(), std::back_inserter(list));
    119                 list.push_back(removeNullableSuffix(*i));
    120                 break;
    121             }
    122         }
    123         return makeSeq(list.begin(), list.end());
    124     } else if (Alt* alt = dyn_cast<Alt>(re)) {
    125         std::vector<RE*> list;
    126         for (auto i = alt->begin(); i != alt->end(); ++i) {
    127             list.push_back(removeNullableSuffix(*i));
    128         }
    129         return makeAlt(list.begin(), list.end());
    130     } else if (Rep * rep = dyn_cast<Rep>(re)) {
    131         auto lb = rep->getLB();
    132         auto e = rep->getRE();
    133         if ((lb == 0) || isNullable(e)) {
    134             return makeSeq();
    135         }
    136         else if (hasNullableSuffix(e)) {
    137             return makeSeq({makeRep(e, lb - 1, lb - 1), removeNullableSuffix(e)});
    138         }
    139         else {
    140             return makeRep(e, lb, lb);
    141         }
    142     } else if (Name * name = dyn_cast<Name>(re)) {
    143         auto def = name->getDefinition();
    144         if (hasNullableSuffix(def)) {
    145             return removeNullableSuffix(def);
    146         }
    147     }
    148     return re;
    149 }
    150 
    151 bool RE_Nullable::isNullable(const RE * re) {
     27bool isNullable(const RE * re) {
    15228    if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
    15329        for (const RE * re : *re_seq) {
     
    17652}
    17753
    178 bool RE_Nullable::hasNullablePrefix(const RE * re) {
    179     if (const Seq * seq = dyn_cast<const Seq>(re)) {
    180         if (seq->empty()) return false;
    181         return isNullable(seq->front()) || hasNullablePrefix(seq->front());
    182     } else if (const Alt * alt = dyn_cast<const Alt>(re)) {
    183         for (const RE * a : *alt) {
    184             if (hasNullablePrefix(a)) {
    185                 return true;
    186             }
    187         }
    188         return false;
    189     } else if (const Rep * rep = dyn_cast<const Rep>(re)) {
    190         return (rep->getLB() != rep->getUB()) || hasNullablePrefix(rep->getRE());
    191     } else if (const Group * g = dyn_cast<const Group>(re)) {
    192         return hasNullablePrefix(g->getRE());
     54
     55class NullablePrefixRemover: public RE_Transformer {
     56protected:
     57    RE * transformSeq(Seq * seq) override;
     58    RE * transformRep(Rep * rep) override;
     59    RE * transformAssertion(Assertion * a) override;
     60public:
     61    NullablePrefixRemover() : RE_Transformer("NullablePrefixRemoval") {}
     62};
     63
     64RE * NullablePrefixRemover::transformSeq(Seq * seq) {
     65    std::vector<RE*> list;
     66    // if the sequence is empty, return it unmodified.
     67    if (isNullable(seq)) return seq;
     68    // Process the first element.
     69    auto i = seq->begin();
     70    auto e = transform(*i);
     71    while (isNullable(e)) {
     72        // Skip empty elements.
     73        i++;
     74        e = transform(*i);
    19375    }
    194     return false;
     76    // Special case: nothing skipped and first element unchanged.
     77    if ((i == seq->begin()) && (e == *i)) return seq;
     78    list.push_back(e);
     79    i++;
     80    while (i != seq->end()) {
     81        list.push_back(*i);
     82        i++;
     83    }
     84    return makeSeq(list.begin(), list.end());
    19585}
    19686
    197 bool RE_Nullable::hasNullableSuffix(const RE * re) {
    198     if (const Seq * seq = dyn_cast<const Seq>(re)) {
    199         if (seq->empty()) return false;
    200         return isNullable(seq->back()) || hasNullableSuffix(seq->back());
    201     } else if (const Alt * alt = dyn_cast<const Alt>(re)) {
    202         for (const RE * a : *alt) {
    203             if (hasNullableSuffix(a)) {
    204                 return true;
    205             }
    206         }
    207         return false;
    208     } else if (const Rep * rep = dyn_cast<const Rep>(re)) {
    209         return (rep->getLB() != rep->getUB()) || hasNullableSuffix(rep->getRE());
    210     } else if (const Group * g = dyn_cast<const Group>(re)) {
    211         return hasNullableSuffix(g->getRE());
     87RE * NullablePrefixRemover::transformRep(Rep * rep) {
     88    auto lb = rep->getLB();
     89    auto r = rep->getRE();
     90    if ((lb == 0) || isNullable(r)) {
     91        return makeSeq();
    21292    }
    213     return false;
     93    auto s = transform(r);
     94    if ((s == r) && (lb == rep->getUB())) return rep; // special case.  No transformation required.
     95    if (lb == 1) return s;
     96    if (lb == 2) return makeSeq({s, r});
     97    return makeSeq({s, makeRep(r, lb - 1, lb - 1)});
    21498}
    21599
     100RE * NullablePrefixRemover::transformAssertion(Assertion * a) {
     101    return a;
    216102}
     103
     104RE * removeNullablePrefix(RE * r) {
     105    return NullablePrefixRemover().transformRE(r);
     106}
     107
     108class NullableSuffixRemover: public RE_Transformer {
     109protected:
     110    RE * transformSeq(Seq * seq) override;
     111    RE * transformRep(Rep * rep) override;
     112    RE * transformAssertion(Assertion * a) override;
     113public:
     114    NullableSuffixRemover() : RE_Transformer("NullableSuffixRemoval") {}
     115};
     116
     117RE * NullableSuffixRemover::transformSeq(Seq * seq) {
     118    std::vector<RE*> list;
     119    // if the sequence is empty, return it unmodified.
     120    if (isNullable(seq)) return seq;
     121    // Process the last element.
     122    auto ri = seq->rbegin();
     123    auto r = transform(*ri);
     124    while (isNullable(r)) {
     125        // Skip empty elements.
     126        ri++;
     127        r = transform(*ri);
     128    }
     129    // Special case: nothing skipped and first element unchanged.
     130    if ((ri == seq->rbegin()) && (r == *ri)) return seq;
     131    std::copy(seq->begin(), (ri + 1).base(), std::back_inserter(list));
     132    list.push_back(r);
     133    return makeSeq(list.begin(), list.end());
     134}
     135
     136RE * NullableSuffixRemover::transformRep(Rep * rep) {
     137    auto lb = rep->getLB();
     138    auto r = rep->getRE();
     139    if ((lb == 0) || isNullable(r)) {
     140        return makeSeq();
     141    }
     142    auto s = transform(r);
     143    if ((s == r) && (lb == rep->getUB())) return rep; // special case.  No transformation required.
     144    if (lb == 1) return s;
     145    if (lb == 2) return makeSeq({r, s});
     146    return makeSeq({makeRep(r, lb - 1, lb - 1), s});
     147}
     148
     149RE * NullableSuffixRemover::transformAssertion(Assertion * a) {
     150    return a;
     151}
     152RE * removeNullableSuffix(RE * r) {
     153    return NullableSuffixRemover().transformRE(r);
     154}
     155   
     156
     157}
  • icGREP/icgrep-devel/icgrep/re/re_nullable.h

    r5869 r6171  
    66
    77namespace re {
    8 
    9 class RE_Nullable {
    10 public:
    11     static RE * excludeNullable(RE * re);
    12     static RE * removeNullablePrefix(RE * re);
    13     static RE * removeNullableSuffix(RE * re);
    14     static bool isNullable(const RE * re);
    15     static bool hasNullablePrefix(const RE * re);
    16     static bool hasNullableSuffix(const RE * re);
    17 private:
    18     static bool isNullable(const Vector * vec);
    19 };
    20 
     8    bool isNullable(const RE * re);
     9    RE * removeNullablePrefix(RE * re);
     10    RE * removeNullableSuffix(RE * re);
    2111}
    2212
  • icGREP/icgrep-devel/icgrep/re/re_range.h

    r5764 r6171  
    2121        return mLo;
    2222    }
    23     void setLo(RE * lh) {
    24         mLo = lh;
    25     }
    2623    RE * getHi() const {
    2724        return mHi;
    28     }
    29     void setHi(RE * rh) {
    30         mHi = rh;
    3125    }
    3226protected:
  • icGREP/icgrep-devel/icgrep/re/re_rep.cpp

    r5725 r6171  
    3333        report_fatal_error("lower bound cannot exceed upper bound");
    3434    }
    35     if (RE_Nullable::isNullable(re)) {
     35    if (isNullable(re)) {
    3636        if (ub == 1) {
    3737            return re;
  • icGREP/icgrep-devel/icgrep/re/re_star_normal.cpp

    r6160 r6171  
    2020RE * star_rule(RE * re) {
    2121    if (Seq * seq = dyn_cast<Seq>(re)) {
    22         if (RE_Nullable::isNullable(re)) {
     22        if (isNullable(re)) {
    2323            std::vector<RE *> list;
    2424            list.reserve(seq->size());
  • icGREP/icgrep-devel/icgrep/re/re_toolchain.cpp

    r6170 r6171  
    9999
    100100    //Optimization passes to simplify the AST.
    101     r = RE_Nullable::removeNullablePrefix(r);
    102     if (PrintOptions.isSet(ShowAllREs) || PrintOptions.isSet(ShowStrippedREs)) {
    103         errs() << "RemoveNullablePrefix:\n" << Printer_RE::PrintRE(r) << '\n';
    104     }
    105     r = RE_Nullable::removeNullableSuffix(r);
    106     if (PrintOptions.isSet(ShowAllREs) || PrintOptions.isSet(ShowStrippedREs)) {
    107         errs() << "RemoveNullableSuffix:\n" << Printer_RE::PrintRE(r) << '\n';
    108     }
     101    r = removeNullablePrefix(r);
     102    r = removeNullableSuffix(r);
    109103    r = RE_Star_Normal().transformRE(r);
    110104    if (codegen::OptLevel > 1) {
Note: See TracChangeset for help on using the changeset viewer.