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

Revised RE_Minimizer to use alphabets + minor optimizations to RE functions

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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
Note: See TracChangeset for help on using the changeset viewer.