Changeset 5835 for icGREP/icgrep-devel


Ignore:
Timestamp:
Jan 15, 2018, 4:48:02 PM (14 months ago)
Author:
nmedfort
Message:

Revised RE_Minimizer to use alphabets + minor optimizations to RE functions

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

Legend:

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

    r5811 r5835  
    5252}
    5353   
    54 inline void add_CC(std::vector<CC *> & CCs_found, CC * cc) {
    55     for (unsigned j = 0; j < CCs_found.size(); j++) {
    56         if (CCs_found[j]->getAlphabet() == cc->getAlphabet()) {
    57             CCs_found[j] = makeCC(CCs_found[j], cc);
    58             return;
    59         }
    60     }
    61     CCs_found.push_back(cc);
    62 }
    63 
    6454template<typename iterator>
    6555RE * makeAlt(iterator begin, iterator end) {
    6656    Alt * newAlt = makeAlt();
    67     bool nullableAltFound = false;
    68     std::vector<CC *> CCs_found;  // CCs with possibly different alphabets
     57    if (LLVM_UNLIKELY(begin == end)) {
     58        return newAlt;
     59    }
     60
     61    llvm::SmallVector<CC *, 2> CCs(0); // CCs with possibly different alphabets
     62    auto combineCC = [&CCs] (CC * cc) {
     63        for (CC *& existing : CCs) {
     64            if (LLVM_LIKELY(existing->getAlphabet() == cc->getAlphabet())) {
     65                existing = makeCC(existing, cc);
     66                return;
     67            }
     68        }
     69        CCs.push_back(cc);
     70    };
     71
     72    bool nullable = false;
     73    RE * emptySeq = nullptr;
    6974    for (auto i = begin; i != end; ++i) {
    7075        if (CC * cc = llvm::dyn_cast<CC>(*i)) {
    71             add_CC(CCs_found, cc);
     76            combineCC(cc);
    7277        } else if (const Alt * alt = llvm::dyn_cast<Alt>(*i)) {
    7378            // We have an Alt to embed within the alt.  We extract the individual
     
    7681            for (RE * a : *alt) {
    7782                if (CC * cc = llvm::dyn_cast<CC>(a)) {
    78                     add_CC(CCs_found, cc);
     83                    combineCC(cc);
    7984                } else if (isEmptySeq(a)) {
    80                     nullableAltFound = true;
     85                    nullable = true;
     86                    emptySeq = a;
    8187                } else {
    8288                    newAlt->push_back(a);
     
    8591        } else if (const Rep * rep = llvm::dyn_cast<Rep>(*i)) {
    8692            if (rep->getLB() == 0) {
    87                 nullableAltFound = true;
     93                nullable = true;
    8894                newAlt->push_back(makeRep(rep->getRE(), 1, rep->getUB()));
    8995            } else {
     
    9197            }
    9298        } else if (isEmptySeq(*i)) {
    93             nullableAltFound = true;
     99            nullable = true;
     100            emptySeq = *i;
    94101        } else {
    95102            newAlt->push_back(*i);
    96103        }
    97104    }
    98     for (CC * cc : CCs_found) {
    99         newAlt->push_back(cc);
     105    newAlt->insert(newAlt->end(), CCs.begin(), CCs.end());
     106    if (nullable) {
     107        if (emptySeq == nullptr) {
     108            emptySeq = makeSeq();
     109        }
     110        newAlt->push_back(emptySeq);
    100111    }
    101     if (nullableAltFound) newAlt->push_back(makeSeq());
    102     if (newAlt->size() == 1) return newAlt->front();
    103     return newAlt;
     112    return newAlt->size() == 1 ? newAlt->front() : newAlt;
    104113}
    105114
  • icGREP/icgrep-devel/icgrep/re/re_analysis.cpp

    r5805 r5835  
    123123    } else if (const CC * cc = dyn_cast<CC>(re)) {
    124124        const cc::Alphabet * a = cc->getAlphabet();
    125         if (a == &cc::Unicode) return (cc->max_codepoint() <= 0x7F);
    126         else if (a == &cc::Byte) return true;
    127         else if (isa<cc::MultiplexedAlphabet>(a)) {
     125        if (a == &cc::Unicode) {
     126            return (cc->max_codepoint() <= 0x7F);
     127        } else if (a == &cc::Byte) {
     128            return true;
     129        } else if (isa<cc::MultiplexedAlphabet>(a)) {
    128130            const cc::Alphabet * srcA = cast<cc::MultiplexedAlphabet>(a)->getSourceAlphabet();
    129131            if (srcA == &cc::Byte) {
  • icGREP/icgrep-devel/icgrep/re/re_compiler.cpp

    r5821 r5835  
    487487    PabloAST * base = markerVar(AdvanceMarker(marker, InitialPostPositionUnit, pb));
    488488    if (isByteLength(repeated) && LLVM_LIKELY(!AlgorithmOptionIsSet(DisableMatchStar))) {
    489         PabloAST * mask = pb.createOr(markerVar(compile(repeated, pb)), mNonFinal);
     489        PabloAST * mask = markerVar(compile(repeated, pb));
    490490        // The post position character may land on the initial byte of a multi-byte character. Combine them with the masked range.
     491        mask = pb.createOr(mask, mNonFinal);
    491492        PabloAST * unbounded = pb.createMatchStar(base, mask, "unbounded");
    492493        return makeMarker(FinalPostPositionUnit, unbounded);
    493494    } else if (isUnicodeUnitLength(repeated) && LLVM_LIKELY(!AlgorithmOptionIsSet(DisableMatchStar) && !AlgorithmOptionIsSet(DisableUnicodeMatchStar))) {
    494         PabloAST * mask = pb.createOr(markerVar(compile(repeated, pb)), mNonFinal);
    495         PabloAST * mstar = pb.createMatchStar(base, mask);
    496         return makeMarker(FinalPostPositionUnit, pb.createAnd(mstar, mFinal, "unbounded"));
     495        PabloAST * mask = markerVar(compile(repeated, pb));
     496        mask = pb.createOr(mask, mNonFinal);
     497        PabloAST * unbounded = pb.createMatchStar(base, mask);
     498        return makeMarker(FinalPostPositionUnit, pb.createAnd(unbounded, mFinal, "unbounded"));
    497499    } else if (mStarDepth > 0){
    498500        PabloBuilder * const outer = pb.getParent();
     
    508510        pb.createAssign(starAccum, pb.createOr(loopComputation, m2));
    509511        mWhileTest = pb.createOr(mWhileTest, starPending);
    510         mStarDepth--;     
     512        mStarDepth--;
    511513        return makeMarker(markerPos(result), pb.createOr(base, starAccum, "unbounded"));
    512514    } else {
     
    583585, mCompiledName(&mBaseMap) {
    584586    Var * const linebreak = mKernel->getInputStreamVar("linebreak");
    585     mLineBreak = mPB.createExtract(linebreak, mPB.getInteger(0));
     587    mLineBreak = mPB.createExtract(linebreak, 0);
    586588    Var * const crlf = mKernel->getInputStreamVar("cr+lf");
    587     mCRLF = mPB.createExtract(crlf, mPB.getInteger(0));
     589    mCRLF = mPB.createExtract(crlf, 0);
    588590    Var * const required = mKernel->getInputStreamVar("required");
    589     mInitial = mPB.createExtract(required, mPB.getInteger(0));
    590     mNonFinal = mPB.createExtract(required, mPB.getInteger(1));
    591     mFinal = mPB.createExtract(required, mPB.getInteger(2));
     591    mInitial = mPB.createExtract(required, 0);
     592    mNonFinal = mPB.createExtract(required, 1);
     593    mFinal = mPB.createExtract(required, 2);
    592594}
    593595
  • icGREP/icgrep-devel/icgrep/re/re_minimizer.cpp

    r5755 r5835  
    1111#include <boost/container/flat_set.hpp>
    1212#include <boost/container/flat_map.hpp>
    13 
    14 #include <llvm/Support/raw_ostream.h>
    15 #include <re/printer_re.h>
     13#include <llvm/ADT/SmallVector.h>
     14
    1615
    1716using namespace llvm;
     17using namespace boost::container;
    1818
    1919namespace re {
    2020
    21 using Set = boost::container::flat_set<RE *>;
    22 using Map = boost::container::flat_map<RE *, RE *>;
     21using Set = flat_set<RE *>;
     22using Map = flat_map<RE *, RE *>;
    2323using List = std::vector<RE *>;
    2424
    2525struct PassContainer : private Memoizer {
    2626
    27     RE * minimize(RE * original) {
    28         const auto f = mMap.find(original);
    29         if (LLVM_UNLIKELY(f != mMap.end())) {
    30             return f->second;
    31         }
    32         RE * re = original;
    33 repeat: if (Alt * alt = dyn_cast<Alt>(re)) {
     27    RE * minimize(RE * re) {
     28        const auto f = find(re);
     29        if (LLVM_UNLIKELY(f != end())) {
     30            return *f;
     31        }
     32        if (Alt * const alt = dyn_cast<Alt>(re)) {
    3433            Set set;
    3534            set.reserve(alt->size());
    36             RE * namedCC = nullptr;
    37             bool repeat = false;
    3835            for (RE * item : *alt) {
    3936                item = minimize(item);
    4037                if (LLVM_UNLIKELY(isa<Alt>(item))) {
    41                     if (LLVM_UNLIKELY(cast<Alt>(item)->empty())) {
    42                         continue;
    43                     }
    44                     repeat = true;
    45                 } else { // if we have an alternation containing multiple CCs, combine them
    46                     CC * const cc = extractCC(item);
    47                     if (cc) {
    48                         namedCC = namedCC ? makeCC(extractCC(namedCC), cc) : item;
    49                         continue;
    50                     }
    51                 }
    52                 set.insert(item);
    53             }
    54             // Combine and/or insert any named CC object into the alternation
    55             if (namedCC) {
    56                 if (LLVM_UNLIKELY(isa<CC>(namedCC))) {
    57                     namedCC = memoize(cast<CC>(namedCC));
    58                 }
    59                 set.insert(cast<Name>(namedCC));
    60             }
     38                    for (RE * const innerItem : *cast<Alt>(item)) {
     39                        set.insert(innerItem);
     40                    }
     41                } else if (CC * const cc = extractCC(item)) {
     42                    combineCC(cc);
     43                } else {
     44                    set.insert(item);
     45                }
     46            }
     47            // insert any CC objects into the alternation
     48            for (auto cc : mCombine) {
     49                set.insert(memoize(cc));
     50            }
     51            mCombine.clear();
    6152            // Pablo CSE may identify common prefixes but cannot identify common suffixes.
    6253            extractCommonSuffixes(set);
    6354            extractCommonPrefixes(set);
    6455            re = makeAlt(set.begin(), set.end());
    65             if (LLVM_UNLIKELY(repeat)) {
    66                 goto repeat;
    67             }
    68         } else if (Seq * seq = dyn_cast<Seq>(re)) {
     56        } else if (Seq * const seq = dyn_cast<Seq>(re)) {
    6957            List list;
    7058            list.reserve(seq->size());
    71             bool repeat = false;
    7259            for (RE * item : *seq) {
    7360                item = minimize(item);
    7461                if (LLVM_UNLIKELY(isa<Seq>(item))) {
    75                     if (LLVM_UNLIKELY(cast<Seq>(item)->empty())) {
    76                         continue;
    77                     }
    78                     repeat = true;
    79                 }
    80                 list.push_back(item);
     62                    for (RE * const innerItem : *cast<Seq>(item)) {
     63                        list.push_back(innerItem);
     64                    }
     65                } else {
     66                    list.push_back(item);
     67                }
    8168            }
    8269            for (unsigned i = 1, run = 0; i < list.size(); ) {
     
    9279                    continue;
    9380                } else if (LLVM_UNLIKELY(isa<Rep>(list[i - 1]) && isa<Rep>(list[i]))){
    94                     // If we have adjacent repetitions of the same RE, we can merge them
     81                    // If we have adjacent repetitions of the same RE, merge them
    9582                    Rep * const r1 = cast<Rep>(list[i - 1]);
    9683                    Rep * const r2 = cast<Rep>(list[i]);
    9784                    if (LLVM_UNLIKELY(r1->getRE() == r2->getRE())) {
    98                         list[i - 1] = memoize(combineRep(r1, r2));
     85                        list[i - 1] = memoize(combineTwoReps(r1, r2));
    9986                        list.erase(list.begin() + i);
    10087                        continue;
     
    10491            }
    10592            re = makeSeq(list.begin(), list.end());
    106             if (LLVM_UNLIKELY(repeat)) {
    107                 goto repeat;
    108             }
    109         } else if (Assertion * a = dyn_cast<Assertion>(re)) {
     93        } else if (Assertion * const a = dyn_cast<Assertion>(re)) {
    11094            re = makeAssertion(minimize(a->getAsserted()), a->getKind(), a->getSense());
    111         } else if (Rep * rep = dyn_cast<Rep>(re)) {
     95        } else if (Rep * const rep = dyn_cast<Rep>(re)) {
    11296            re = makeRep(minimize(rep->getRE()), rep->getLB(), rep->getUB());
    113         } else if (Diff * diff = dyn_cast<Diff>(re)) {
     97        } else if (Diff * const diff = dyn_cast<Diff>(re)) {
    11498            re = makeDiff(minimize(diff->getLH()), minimize(diff->getRH()));
    115         } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
     99        } else if (Intersect * const ix = dyn_cast<Intersect>(re)) {
    116100            re = makeIntersect(minimize(ix->getLH()), minimize(ix->getRH()));
    117         } else if (Name * n = dyn_cast<Name>(re)) {
    118             RE * const def = n->getDefinition(); assert (def);
    119             if (LLVM_UNLIKELY(!isa<CC>(def))) {
     101        } else if (Name * const n = dyn_cast<Name>(re)) {
     102            RE * const def = n->getDefinition();
     103            if (LLVM_LIKELY(def != nullptr)) {
    120104                n->setDefinition(minimize(def));
    121105            }
    122106        }
    123         re = memoize(re);
    124         mMap.emplace(original, re);
    125         if (LLVM_LIKELY(original != re)) {
    126             mMap.emplace(re, re);
    127         }
    128         return re;
     107        return memoize(re);
    129108    }
    130109
    131110protected:
    132111
    133     void extractCommonPrefixes(Set & source) {
    134         List combine;
    135 repeat: if (LLVM_UNLIKELY(source.size() < 2)) {
    136             return;
    137         }
    138         for (auto i = source.begin(); i != source.end(); ++i) {
    139             assert (combine.empty());
    140             RE * const head = getHead(*i);
    141             for (auto j = i + 1; j != source.end(); ) {
    142                 if (LLVM_UNLIKELY(head == getHead(*j))) {
    143                     combine.push_back(*j);
    144                     j = source.erase(j);
    145                     continue;
    146                 }
    147                 ++j;
    148             }
    149 
    150             if (LLVM_UNLIKELY(!combine.empty())) {
    151                 combine.push_back(*i);
    152                 source.erase(i);
    153                 Set tailSet;
    154                 tailSet.reserve(combine.size());
    155                 bool isOptional = false;
    156                 for (RE * const re : combine) {
    157                     if (LLVM_LIKELY(isa<Seq>(re))) {
    158                         Seq * const seq = cast<Seq>(re);
    159                         if (LLVM_LIKELY(seq->size() > 1)) {
    160                             tailSet.insert(minimize(makeSeq(seq->begin() + 1, seq->end())));
    161                             continue;
     112    void extractCommonPrefixes(Set & alts) {       
     113        if (LLVM_LIKELY(alts.size() > 1)) {
     114            SmallVector<RE *, 8> optimized;
     115            for (auto i = alts.begin(); i != alts.end(); ) {
     116                assert ("combine list must be empty!" && mCombine.empty());
     117                RE * const head = headOf(*i);
     118                for (auto j = i + 1; j != alts.end(); ) {
     119                    if (LLVM_UNLIKELY(head == headOf(*j))) {
     120                        mCombine.push_back(*j);
     121                        j = alts.erase(j);
     122                    } else {
     123                        ++j;
     124                    }
     125                }
     126                if (LLVM_LIKELY(mCombine.empty())) {
     127                    ++i;
     128                } else {
     129                    mCombine.push_back(*i);
     130                    i = alts.erase(i);
     131                    Set tailSet;
     132                    tailSet.reserve(mCombine.size());
     133                    bool nullable = false;
     134                    for (RE * const re : mCombine) {
     135                        if (LLVM_LIKELY(isa<Seq>(re))) {
     136                            Seq * const seq = cast<Seq>(re);
     137                            if (LLVM_LIKELY(seq->size() > 1)) {
     138                                assert (head == seq->front());
     139                                tailSet.insert(memoize(makeSeq(seq->begin() + 1, seq->end())));
     140                                continue;
     141                            }
     142                        } else if (LLVM_UNLIKELY(isa<Rep>(re))) {
     143                            Rep * const rep = cast<Rep>(re);
     144                            if (head != rep) {
     145                                assert (head == rep->getRE());
     146                                tailSet.insert(memoize(makeRepWithOneFewerRepitition(rep)));
     147                                continue;
     148                            }
    162149                        }
    163                     } else if (LLVM_UNLIKELY(isa<Rep>(re))) {
    164                         Rep * const rep = cast<Rep>(re);
    165                         if (head != rep) {
    166                             assert (head == rep->getRE());
    167                             assert (rep->getLB() > 0);
    168                             const auto lb = rep->getLB() - 1;
    169                             const auto ub = rep->getUB() == Rep::UNBOUNDED_REP ? Rep::UNBOUNDED_REP : rep->getUB() - 1;
    170                             tailSet.insert(minimize(makeRep(rep->getRE(), lb, ub)));
    171                             continue;
     150                        nullable = true;
     151                    }
     152                    mCombine.clear();
     153                    if (LLVM_UNLIKELY(nullable)) {
     154                        tailSet.insert(memoize(makeSeq()));
     155                    }
     156                    RE * const tail = makeAlt(tailSet.begin(), tailSet.end());
     157                    optimized.push_back(minimize(makeSeq({ head, tail })));
     158                }
     159            }
     160            alts.insert(optimized.begin(), optimized.end());
     161        }       
     162    }
     163
     164    void extractCommonSuffixes(Set & alts) {
     165        if (LLVM_LIKELY(alts.size() > 1)) {
     166            SmallVector<RE *, 8> optimized;
     167            for (auto i = alts.begin(); i != alts.end(); ) {
     168                assert ("combine list must be empty!" && mCombine.empty());
     169                RE * const last = lastOf(*i);
     170                for (auto j = i + 1; j != alts.end(); ) {
     171                    if (LLVM_UNLIKELY(last == lastOf(*j))) {
     172                        mCombine.push_back(*j);
     173                        j = alts.erase(j);
     174                    } else {
     175                        ++j;
     176                    }
     177                }
     178                if (LLVM_LIKELY(mCombine.empty())) {
     179                    ++i;
     180                } else {
     181                    mCombine.push_back(*i);
     182                    i = alts.erase(i);
     183                    Set initSet;
     184                    initSet.reserve(mCombine.size());
     185                    bool nullable = false;
     186                    for (RE * const re : mCombine) {
     187                        if (LLVM_LIKELY(isa<Seq>(re))) {
     188                            Seq * const seq = cast<Seq>(re);
     189                            if (LLVM_LIKELY(seq->size() > 1)) {
     190                                assert (last == seq->back());
     191                                initSet.insert(memoize(makeSeq(seq->begin(), seq->end() - 1)));
     192                                continue;
     193                            }
     194                        } else if (LLVM_UNLIKELY(isa<Rep>(re))) {
     195                            Rep * const rep = cast<Rep>(re);
     196                            if (last != rep) {
     197                                assert (last == rep->getRE());
     198                                initSet.insert(memoize(makeRepWithOneFewerRepitition(rep)));
     199                                continue;
     200                            }
    172201                        }
    173                     }
    174                     isOptional = true;
    175                 }
    176                 combine.clear();
    177                 extractCommonPrefixes(tailSet);
    178                 RE * tail = makeAlt(tailSet.begin(), tailSet.end());
    179                 if (LLVM_UNLIKELY(isOptional)) {
    180                     tail = makeRep(tail, 0, 1);
    181                 }
    182                 source.insert(minimize(makeSeq({ head, tail })));
    183                 goto repeat;
    184             }
    185         }
    186     }
    187 
    188     void extractCommonSuffixes(Set & source) {
    189         List combine;
    190 repeat: if (LLVM_UNLIKELY(source.size() < 2)) {
    191             return;
    192         }
    193         for (auto i = source.begin(); i != source.end(); ++i) {
    194             assert (combine.empty());
    195             assert (*i);
    196             RE * const tail = getTail(*i);
    197             for (auto j = i + 1; j != source.end(); ) {
    198                 if (LLVM_UNLIKELY(tail == getTail(*j))) {
    199                     combine.push_back(*j);
    200                     j = source.erase(j);
    201                     continue;
    202                 }
    203                 ++j;
    204             }
    205             if (LLVM_UNLIKELY(!combine.empty())) {
    206                 combine.push_back(*i);
    207                 source.erase(i);
    208                 Set headSet;
    209                 headSet.reserve(combine.size());
    210                 bool isOptional = false;
    211                 for (RE * const re : combine) {
    212                     if (LLVM_LIKELY(isa<Seq>(re))) {
    213                         Seq * const seq = cast<Seq>(re);
    214                         if (LLVM_LIKELY(seq->size() > 1)) {
    215                             headSet.insert(minimize(makeSeq(seq->begin(), seq->end() - 1)));
    216                             continue;
    217                         }
    218                     } else if (LLVM_UNLIKELY(isa<Rep>(re))) {
    219                         Rep * const rep = cast<Rep>(re);
    220                         if (tail != rep) {
    221                             assert (tail == rep->getRE());
    222                             assert (rep->getUB() != 0);
    223                             assert (rep->getLB() > 0);
    224                             const auto lb = rep->getLB() - 1;
    225                             const auto ub = (rep->getUB() == Rep::UNBOUNDED_REP) ? Rep::UNBOUNDED_REP : rep->getUB() - 1;
    226                             headSet.insert(minimize(makeRep(rep->getRE(), lb, ub)));
    227                             continue;
    228                         }
    229                     }
    230                     isOptional = true;
    231                 }
    232                 combine.clear();
    233                 extractCommonSuffixes(headSet);
    234                 extractCommonPrefixes(headSet);
    235                 RE * head = makeAlt(headSet.begin(), headSet.end());
    236                 if (LLVM_UNLIKELY(isOptional)) {
    237                     head = makeRep(head, 0, 1);
    238                 }
    239                 source.insert(minimize(makeSeq({ head, tail })));
    240                 goto repeat;
    241             }
    242         }
     202                        nullable = true;
     203                    }
     204                    mCombine.clear();
     205                    if (LLVM_UNLIKELY(nullable)) {
     206                        initSet.insert(memoize(makeSeq()));
     207                    }
     208                    RE * const init = makeAlt(initSet.begin(), initSet.end());
     209                    optimized.push_back(minimize(makeSeq({ init, last })));
     210                }
     211            }
     212            alts.insert(optimized.begin(), optimized.end());
     213        }       
    243214    }
    244215
    245216    static CC * extractCC(RE * const re) {
    246         if (LLVM_UNLIKELY(isa<CC>(re))) {
     217        if (isa<CC>(re)) {
    247218            return cast<CC>(re);
    248219        } else if (isa<Name>(re)) {
     
    255226    }
    256227
    257     static RE * combineRep(Rep * const r1, Rep * const r2) {
     228    void combineCC(CC * const cc) {
     229        for (RE *& existing : mCombine) {
     230            if (LLVM_LIKELY(cast<CC>(existing)->getAlphabet() == cc->getAlphabet())) {
     231                existing = makeCC(cast<CC>(existing), cc);
     232                return;
     233            }
     234        }
     235        mCombine.push_back(cc);
     236    }
     237
     238    static RE * combineTwoReps(Rep * const r1, Rep * const r2) {
    258239        assert (r1->getRE() == r2->getRE());
    259240        assert (r1->getLB() != Rep::UNBOUNDED_REP);
     
    262243        int ub = Rep::UNBOUNDED_REP;
    263244        if ((r1->getUB() != Rep::UNBOUNDED_REP) && (r2->getUB() != Rep::UNBOUNDED_REP)) {
     245            assert (r1->getUB() < (std::numeric_limits<int>::max() - r2->getUB()));
    264246            ub = r1->getUB() + r2->getUB();
    265247        }
     
    267249    }
    268250
    269     static RE * getHead(RE * re) {
    270         assert (re);
    271         if (isa<Seq>(re)) {
    272             re = cast<Seq>(re)->front(); assert (re);
    273         } else if (isa<Rep>(re)) {
    274             Rep * const rep = cast<Rep>(re);
    275             assert (rep->getLB() != Rep::UNBOUNDED_REP);
     251    static RE * makeRepWithOneFewerRepitition(Rep * const re) {
     252        assert (re->getLB() > 0);
     253        const auto lb = re->getLB() - 1;
     254        assert (re->getUB() != 0);
     255        const auto ub = (re->getUB() == Rep::UNBOUNDED_REP) ? Rep::UNBOUNDED_REP : re->getUB() - 1;
     256        return makeRep(re->getRE(), lb, ub);
     257    }
     258
     259    static RE * headOf(RE * const re) {
     260        if (Seq * seq = dyn_cast<Seq>(re)) {
     261            if (LLVM_LIKELY(!seq->empty())) {
     262                return seq->front();
     263            }
     264        } else if (Rep * const rep = dyn_cast<Rep>(re)) {
    276265            if (rep->getLB() > 0) {
    277                 re = rep->getRE(); assert (re);
     266                return rep->getRE();
    278267            }
    279268        }
     
    281270    }
    282271
    283     static RE * getTail(RE * re) {
    284         assert (re);
    285         if (isa<Seq>(re)) {
    286             re = cast<Seq>(re)->back();
    287             assert (re);
    288         } else if (isa<Rep>(re)) {
    289             Rep * const rep = cast<Rep>(re);
    290             assert (rep->getLB() != Rep::UNBOUNDED_REP);
    291             assert (rep->getUB() == Rep::UNBOUNDED_REP || rep->getUB() >= rep->getLB());
     272    static RE * lastOf(RE * const re) {
     273        if (Seq * seq = dyn_cast<Seq>(re)) {
     274            if (LLVM_LIKELY(!seq->empty())) {
     275                return seq->back();
     276            }
     277        } else if (Rep * const rep = dyn_cast<Rep>(re)) {
    292278            if (rep->getLB() > 0) {
    293                 re = rep->getRE(); assert (re);
     279                return rep->getRE();
    294280            }
    295281        }
     
    297283    }
    298284
    299 private:
    300 
    301     Map mMap;
     285    SmallVector<RE *, 16> mCombine;
    302286};
    303287
  • icGREP/icgrep-devel/icgrep/re/re_name_resolve.cpp

    r5821 r5835  
    4848                    UndefinedNameError(name);
    4949                }
     50                re = mMemoizer.memoize(name);
    5051            } else {
    5152                return *f;
     
    8384                    UndefinedNameError(name);
    8485                }
     86                re = mMemoizer.memoize(name);
    8587            } else {
    8688                return *f;
  • icGREP/icgrep-devel/icgrep/re/re_parser.cpp

    r5816 r5835  
    6666    RE * re = parser->parse_RE();
    6767    if (re == nullptr) {
    68         ParseFailure("An unexpected parsing error occurred!");
     68        parser->ParseFailure("An unexpected parsing error occurred!");
    6969    }
    7070    return re;
    7171}
    7272
    73 RE_Parser::RE_Parser(const std::string & regular_expression)
    74 : fByteMode(false)
    75 , fModeFlagSet(MULTILINE_MODE_FLAG)
    76 , fNested(false)
    77 , mGroupsOpen(0)
    78 , mCursor(regular_expression)
    79 , mCaptureGroupCount(0)
    80 , mReSyntax(RE_Syntax::PCRE)
    81 {
    82 
    83 }
    84 
    85 RE * makeAtomicGroup(RE * r) {
    86     RE_Parser::ParseFailure("Atomic grouping not supported.");
    87 }
    88 
    89 RE * makeBranchResetGroup(RE * r) {
     73RE * RE_Parser::makeAtomicGroup(RE * r) {
     74    ParseFailure("Atomic grouping not supported.");
     75}
     76
     77RE * RE_Parser::makeBranchResetGroup(RE * r) {
    9078    // Branch reset groups only affect submatch numbering, but
    9179    // this has no effect in icgrep.
    92     RE_Parser::ParseFailure("Branch reset groups not supported.");
     80    ParseFailure("Branch reset groups not supported.");
    9381}
    9482
     
    457445    }
    458446}
    459    
    460 void InvalidUTF8Encoding() {
    461     RE_Parser::ParseFailure("Invalid UTF-8 encoding!");
    462 }
    463447
    464448codepoint_t RE_Parser::parse_literal_codepoint() {
     
    471455codepoint_t RE_Parser::parse_utf8_codepoint() {
    472456    // Must cast to unsigned char to avoid sign extension.
    473     unsigned char pfx = static_cast<unsigned char>(*mCursor++);
     457    const unsigned char pfx = static_cast<unsigned char>(*mCursor++);
    474458    codepoint_t cp = pfx;
    475459    if (pfx < 0x80) return cp;
     
    492476            InvalidUTF8Encoding();
    493477        }
    494         char_t sfx = *mCursor++;
     478        const char_t sfx = *mCursor++;
    495479        if ((sfx & 0xC0) != 0x80) {
    496480            InvalidUTF8Encoding();
     
    892876}
    893877
    894 LLVM_ATTRIBUTE_NORETURN void RE_Parser::ParseFailure(std::string errmsg) {
     878RE_Parser::RE_Parser(const std::string & regular_expression)
     879: fByteMode(false)
     880, fModeFlagSet(MULTILINE_MODE_FLAG)
     881, fNested(false)
     882, mGroupsOpen(0)
     883, mCursor(regular_expression)
     884, mCaptureGroupCount(0)
     885, mReSyntax(RE_Syntax::PCRE) {
     886
     887}
     888
     889LLVM_ATTRIBUTE_NORETURN void RE_Parser::InvalidUTF8Encoding() {
     890    ParseFailure("Invalid UTF-8 encoding!");
     891}
     892
     893LLVM_ATTRIBUTE_NORETURN void RE_Parser::Cursor::IncompleteRegularExpression() {
     894    ParseFailure("Incomplete regular expression!");
     895}
     896
     897LLVM_ATTRIBUTE_NORETURN void RE_Parser::Cursor::ParseFailure(const std::string & errmsg) {
     898#if 0
     899    // TODO: this ought to check if the cursor position is on a UTF-8 character
     900    raw_fd_ostream out(STDERR_FILENO, false);
     901    out.changeColor(raw_string_ostream::WHITE);
     902    out.write(mStart.base(), mCursor - mStart);
     903    out.changeColor(raw_string_ostream::BLUE, true);
     904    out << *mCursor;
     905    out.changeColor(raw_string_ostream::WHITE);
     906    out.write(mCursor.base() + 1, mEnd - mCursor - 1);
     907    out << "\n\n";
     908#endif
    895909    llvm::report_fatal_error(errmsg);
    896910}
  • icGREP/icgrep-devel/icgrep/re/re_parser.h

    r5814 r5835  
    3333public:
    3434
    35     static LLVM_ATTRIBUTE_NORETURN void ParseFailure(std::string errmsg);
    36 
    3735    static RE * parse(const std::string &input_string, ModeFlagSet initialFlags, RE_Syntax syntax = RE_Syntax::PCRE, bool ByteMode = false);
    3836
     
    4644
    4745    struct Cursor {
     46        friend class RE_Parser;
    4847
    4948        inline Cursor & operator++() {
    5049            if (LLVM_UNLIKELY(mCursor == mEnd)) {
    51                 ParseFailure("Incomplete regular expression!");
     50                IncompleteRegularExpression();
    5251            }
    5352            ++mCursor;
     
    5756        inline Cursor operator++(int) {
    5857            if (LLVM_UNLIKELY(mCursor == mEnd)) {
    59                 ParseFailure("Incomplete regular expression!");
     58                IncompleteRegularExpression();
    6059            }
    6160            Cursor tmp(*this);
     
    8685            return mCursor;
    8786        }
    88        
    89        
    90         Cursor(const std::string & expression) : mCursor(expression.cbegin()), mEnd(expression.cend()) {}
    91         Cursor(const Cursor & cursor) : mCursor(cursor.mCursor), mEnd(cursor.mEnd) {}
     87               
     88        Cursor(const std::string & expression) : mCursor(expression.cbegin()), mEnd(expression.cend()), mStart(expression.cbegin()) {}
     89        Cursor(const Cursor & cursor) : mCursor(cursor.mCursor), mEnd(cursor.mEnd), mStart(cursor.mStart) {}
    9290        inline Cursor & operator=(const Cursor & cursor) {
    9391            mCursor = cursor.mCursor;
     
    9593            return *this;
    9694        }
     95    private:       
     96        LLVM_ATTRIBUTE_NORETURN void IncompleteRegularExpression();
     97        LLVM_ATTRIBUTE_NORETURN void ParseFailure(const std::string & errmsg);
    9798    private:
    9899        cursor_t    mCursor;
    99100        cursor_t    mEnd;
     101        cursor_t    mStart;
    100102    };
    101103
     
    225227    RE * parse_escaped_char_item();
    226228   
     229    RE * makeAtomicGroup(RE * r);
     230    RE * makeBranchResetGroup(RE * r);
     231
    227232    codepoint_t parse_codepoint();
    228233
     
    236241
    237242    static std::string canonicalize(const cursor_t begin, const cursor_t end);
     243
    238244    bool isCharAhead(char c);
     245
     246    LLVM_ATTRIBUTE_NORETURN void InvalidUTF8Encoding();
     247
     248    LLVM_ATTRIBUTE_NORETURN void ParseFailure(const std::string & errmsg) {
     249        mCursor.ParseFailure(errmsg);
     250    }
    239251
    240252protected:
     
    245257    Cursor                      mCursor;
    246258    unsigned                    mCaptureGroupCount;
     259    RE_Syntax                   mReSyntax;
    247260    NameMap                     mNameMap;
    248261    Memoizer                    mMemoizer;
    249     RE_Syntax                   mReSyntax;
    250262};
    251263
  • icGREP/icgrep-devel/icgrep/re/re_seq.h

    r5810 r5835  
    2424protected:
    2525    friend Seq * makeSeq();
    26     template<typename iterator> friend RE * makeSeq(iterator, iterator);
     26    template<typename iterator> friend RE * makeSeq(const iterator, const iterator);
    2727    Seq()
    2828    : Vector(ClassTypeId::Seq) {
     
    3333
    3434    }
    35     template<typename itr> void flatten(itr begin, itr end);
    3635};
    3736
     
    4039}
    4140
    42 template<typename itr>
    43 void Seq::flatten(itr begin, itr end) {
     41template<typename iterator>
     42inline RE * makeSeq(const iterator begin, const iterator end) {
     43    Seq * seq = makeSeq();
    4444    for (auto i = begin; i != end; ++i) {
    45         if (LLVM_UNLIKELY(llvm::isa<Seq>(*i))) {
    46             flatten<Seq::iterator>(llvm::cast<Seq>(*i)->begin(), llvm::cast<Seq>(*i)->end());
     45        RE * const item = *i;
     46        if (LLVM_UNLIKELY(llvm::isa<Seq>(item))) {
     47            for (RE * const innerItem : *llvm::cast<Seq>(item)) {
     48                seq->push_back(innerItem);
     49            }
    4750        } else {
    48             push_back(*i);
     51            seq->push_back(item);
    4952        }
    5053    }
    51 }
    52 
    53 template<typename itr>
    54 inline RE * makeSeq(itr begin, itr end) {
    55     if (LLVM_UNLIKELY(std::distance(begin, end) == 0)) {
    56         return makeSeq();
    57     } else {
    58         Seq * seq = makeSeq();
    59         seq->flatten(begin, end);
    60         if (seq->size() == 1) {
    61             return seq->front();
    62         }
    63         return seq;
     54    if (seq->size() == 1) {
     55        return seq->front();
    6456    }
     57    return seq;
    6558}
    6659
  • icGREP/icgrep-devel/icgrep/re/re_star_normal.cpp

    r5646 r5835  
    1212#include <re/re_assertion.h>
    1313#include <re/re_analysis.h>
     14#include <re/re_nullable.h>
    1415
    1516using namespace llvm;
     
    1718namespace re {
    1819
     20RE * RE_Star_Normal::optimize(RE * re) {
     21    if (Alt * alt = dyn_cast<Alt>(re)) {
     22        std::vector<RE *> list;
     23        list.reserve(alt->size());
     24        for (RE * re : *alt) {
     25            list.push_back(optimize(re));
     26        }
     27        re = makeAlt(list.begin(), list.end());
     28    } else if (Seq * seq = dyn_cast<Seq>(re)) {
     29        RE * head = *(seq->begin());
     30        RE * tail = makeSeq(seq->begin() + 1, seq->end());
     31        const auto headNullable = RE_Nullable::isNullable(head);
     32        head = headNullable ? optimize(head) : star_normal(head);
     33        const auto tailNullable = RE_Nullable::isNullable(tail);
     34        tail = tailNullable ? optimize(tail) : star_normal(tail);
     35        if (LLVM_UNLIKELY(headNullable && tailNullable)) {
     36            re = makeAlt({head, tail});
     37        } else {
     38            re = makeSeq({head, tail});
     39        }
     40    } else if (Assertion * a = dyn_cast<Assertion>(re)) {
     41        re = makeAssertion(optimize(a->getAsserted()), a->getKind(), a->getSense());
     42    } else if (Rep * rep = dyn_cast<Rep>(re)) {
     43        RE * const expr = optimize(rep->getRE());
     44        if (rep->getLB() == 0 && rep->getUB() == Rep::UNBOUNDED_REP) {
     45            re = expr;
     46        } else {
     47            re = makeRep(expr, rep->getLB(), rep->getUB());
     48        }
     49    } else if (Diff * diff = dyn_cast<Diff>(re)) {
     50        re = makeDiff(optimize(diff->getLH()), optimize(diff->getRH()));
     51    } else if (Intersect * e = dyn_cast<Intersect>(re)) {
     52        re = makeIntersect(optimize(e->getLH()), optimize(e->getRH()));
     53    } else if (Name * name = dyn_cast<Name>(re)) {
     54        if (name->getDefinition()) {
     55            name->setDefinition(optimize(name->getDefinition()));
     56        }
     57    }
     58    return re;
     59}
     60
    1961RE * RE_Star_Normal::star_normal(RE * re) {
    20 
    2162    if (Alt * alt = dyn_cast<Alt>(re)) {
    2263        std::vector<RE *> list;
     
    3778    } else if (Rep * rep = dyn_cast<Rep>(re)) {
    3879         if (rep->getLB() == 0 && rep->getUB() == Rep::UNBOUNDED_REP) {
    39             RE * expr = helper(rep->getRE());
     80            RE * expr = optimize(rep->getRE());
    4081            re = makeRep(expr, 0, rep->getUB());
    4182        } else {
     
    5596}
    5697
    57 RE * RE_Star_Normal::helper(RE * re) {
    58     if (Alt * alt = dyn_cast<Alt>(re)) {
    59         std::vector<RE *> list;
    60         list.reserve(alt->size());
    61         for (RE * re : *alt) {
    62             list.push_back(helper(re));
    63         }
    64         re = makeAlt(list.begin(), list.end());
    65     } else if (Seq * seq = dyn_cast<Seq>(re)) {
    66         RE * const re_first = *(seq->begin());
    67         RE * const re_follow = makeSeq(seq->begin() + 1, seq->end());
    68         const auto isFirstNullable = isNullable(re_first);
    69         const auto isFollowNullable = isNullable(re_follow);
    70         if (LLVM_LIKELY(!isFirstNullable && !isFollowNullable)) {
    71             re = makeSeq({star_normal(re_first), star_normal(re_follow)});
    72         } else if (!isFirstNullable && isFollowNullable) {
    73             re = makeSeq({helper(re_first), star_normal(re_follow)});
    74         } else if (isFirstNullable && !isFollowNullable) {
    75             re = makeSeq({star_normal(re_first), helper(re_follow)});
    76         } else {
    77             re = makeAlt({helper(re_first), helper(re_follow)});
    78         }
    79     } else if (Assertion * a = dyn_cast<Assertion>(re)) {
    80         re = makeAssertion(helper(a->getAsserted()), a->getKind(), a->getSense());
    81     } else if (Rep * rep = dyn_cast<Rep>(re)) {
    82         RE * const expr = helper(rep->getRE());
    83         if (rep->getLB() == 0 && rep->getUB() == Rep::UNBOUNDED_REP) {
    84             re = expr;
    85         } else {
    86             re = makeRep(expr, rep->getLB(), rep->getUB());
    87         }
    88     } else if (Diff * diff = dyn_cast<Diff>(re)) {
    89         re = makeDiff(helper(diff->getLH()), helper(diff->getRH()));
    90     } else if (Intersect * e = dyn_cast<Intersect>(re)) {
    91         re = makeIntersect(helper(e->getLH()), helper(e->getRH()));
    92     } else if (Name * name = dyn_cast<Name>(re)) {
    93         if (name->getDefinition()) {
    94             name->setDefinition(helper(name->getDefinition()));
    95         }
    96     }
    97     return re;
    9898}
    99 
    100 bool RE_Star_Normal::isNullable(const RE * re) {
    101     if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
    102         for (const RE * re : *re_seq) {
    103             if (!isNullable(re)) {
    104                 return false;
    105             }
    106         }
    107         return true;
    108     } else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
    109         for (const RE * re : *re_alt) {
    110             if (isNullable(re)) {
    111                 return true;
    112             }
    113         }
    114     } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
    115         return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
    116     } else if (const Diff * diff = dyn_cast<const Diff>(re)) {
    117         return isNullable(diff->getLH()) && !isNullable(diff->getRH());
    118     } else if (const Intersect * e = dyn_cast<const Intersect>(re)) {
    119         return isNullable(e->getLH()) && isNullable(e->getRH());
    120     }
    121     return false;
    122 }
    123 
    124 
    125 }
  • icGREP/icgrep-devel/icgrep/re/re_star_normal.h

    r5493 r5835  
    1919public:
    2020        static RE * star_normal(RE * re);
    21         static RE * helper(RE * re);
    2221private:
    23         static bool isNullable(const RE * re);
     22    static RE * optimize(RE * re);
    2423};
    2524
  • icGREP/icgrep-devel/icgrep/re/re_toolchain.cpp

    r5817 r5835  
    2424#include <re/grapheme_clusters.h>
    2525#include <llvm/Support/raw_ostream.h>
     26#include <toolchain/toolchain.h>
    2627
    2728using namespace pablo;
     
    3233static cl::OptionCategory RegexOptions("Regex Toolchain Options",
    3334                                              "These options control the regular expression transformation and compilation.");
    34 const cl::OptionCategory * re_toolchain_flags() {
     35const cl::OptionCategory * LLVM_READONLY re_toolchain_flags() {
    3536    return &RegexOptions;
    3637}
     
    5152                              CL_ENUM_VAL_SENTINEL), cl::cat(RegexOptions));
    5253
    53 bool AlgorithmOptionIsSet(RE_AlgorithmFlags flag) {
     54bool LLVM_READONLY AlgorithmOptionIsSet(RE_AlgorithmFlags flag) {
    5455    return AlgorithmOptions.isSet(flag);
    5556}
     
    8990
    9091RE * regular_expression_passes(RE * r) {
    91     std::vector<re::CC *> charclasses;
     92
    9293    //Optimization passes to simplify the AST.
    9394    r = RE_Nullable::removeNullablePrefix(r);
     
    106107    r = re::resolveNames(r);
    107108    if (PrintOptions.isSet(ShowAllREs)) {
    108         errs() << "resolveNames:\n" << Printer_RE::PrintRE(r) << '\n';
     109        errs() << "Resolve Names:\n" << Printer_RE::PrintRE(r) << '\n';
    109110    }
    110 
    111     r = RE_Simplifier::simplify(r);
     111    if (codegen::OptLevel > 1) {
     112        r = RE_Minimizer::minimize(r);
     113    } else {
     114        r = RE_Simplifier::simplify(r);
     115    }
    112116    if (PrintOptions.isSet(ShowAllREs) || PrintOptions.isSet(ShowSimplifiedREs)) {
    113117        //Print to the terminal the AST that was generated by the simplifier.
    114118        errs() << "Simplifier:\n" << Printer_RE::PrintRE(r) << '\n';
    115119    }
     120
    116121    return r;
    117122}
     123
    118124}
  • icGREP/icgrep-devel/icgrep/re/re_toolchain.h

    r5817 r5835  
    1111namespace pablo { class PabloKernel; class PabloAST; }
    1212namespace re { class RE; class CC;}
    13 #include <vector>
    1413
    1514namespace re {
     
    2423};
    2524   
    26 bool AlgorithmOptionIsSet(RE_AlgorithmFlags flag);
     25bool LLVM_READONLY AlgorithmOptionIsSet(RE_AlgorithmFlags flag);
    2726   
    2827extern int IfInsertionGap;
    2928
    30 const llvm::cl::OptionCategory * re_toolchain_flags();
     29const llvm::cl::OptionCategory * LLVM_READONLY re_toolchain_flags();
    3130
    3231RE * resolveModesAndExternalSymbols(RE * r);
Note: See TracChangeset for help on using the changeset viewer.