Ignore:
Timestamp:
Sep 21, 2017, 3:10:34 PM (21 months ago)
Author:
nmedfort
Message:

Minor clean up. Bug fix for object cache when the same cached kernel is used twice in a single run. Improvement to RE Minimizer.

File:
1 edited

Legend:

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

    r5630 r5646  
    1212#include <boost/container/flat_map.hpp>
    1313
     14#include <llvm/Support/raw_ostream.h>
     15#include <re/printer_re.h>
     16
    1417using namespace llvm;
    1518
    1619namespace re {
    1720
    18 using AlternationSet = boost::container::flat_set<RE *, MemoizerComparator>;
    19 
     21using Set = boost::container::flat_set<RE *>;
    2022using Map = boost::container::flat_map<RE *, RE *>;
    2123
    22 struct PassContainer {
    23 
    24     RE * minimize(RE * const original) {
    25         const auto f = mMapping.find(original);
    26         if (LLVM_UNLIKELY(f != mMapping.end())) {
     24struct PassContainer : private Memoizer {
     25
     26    RE * minimize(RE * original) {
     27        const auto f = mMap.find(original);
     28        if (LLVM_UNLIKELY(f != mMap.end())) {
    2729            return f->second;
    2830        }
    2931        RE * re = original;
    30         if (Alt * alt = dyn_cast<Alt>(re)) {
    31             AlternationSet list;
     32repeat: if (Alt * alt = dyn_cast<Alt>(re)) {
     33            Set list;
    3234            list.reserve(alt->size());
     35            RE * namedCC = nullptr;
     36            bool repeat = false;
    3337            for (RE * item : *alt) {
    3438                item = minimize(item);
    3539                if (LLVM_UNLIKELY(isa<Vector>(item) && cast<Vector>(item)->empty())) {
    3640                    continue;
     41                } else if (LLVM_UNLIKELY(isa<Alt>(item))) {
     42                    repeat = true;
     43                } else { // if we have an alternation containing multiple CCs, combine them
     44                    CC * const cc = extractCC(item);
     45                    if (cc) {
     46                        namedCC = namedCC ? makeCC(extractCC(namedCC), cc) : item;
     47                        continue;
     48                    }
    3749                }
    3850                list.insert(item);
    3951            }
    40             // When compiling Pablo code, CSE can identify common prefixes but cannot
    41             // identify common suffixes. Prioritize this optimization accordingly.
     52            // Combine and/or insert any named CC object into the alternation
     53            if (namedCC) {
     54                if (LLVM_UNLIKELY(isa<CC>(namedCC))) {
     55                    namedCC = memoize(cast<CC>(namedCC));
     56                }
     57                list.insert(cast<Name>(namedCC));
     58            }
     59            // Pablo CSE may identify common prefixes but cannot identify common suffixes.
    4260            extractCommonSuffixes(list);
    4361            extractCommonPrefixes(list);
    4462            re = makeAlt(list.begin(), list.end());
     63            if (LLVM_UNLIKELY(repeat)) {
     64                goto repeat;
     65            }
    4566        } else if (Seq * seq = dyn_cast<Seq>(re)) {
    4667            std::vector<RE *> list;
    4768            list.reserve(seq->size());
     69            bool repeat = false;
    4870            for (RE * item : *seq) {
    4971                item = minimize(item);
    5072                if (LLVM_UNLIKELY(isa<Vector>(item) && cast<Vector>(item)->empty())) {
    5173                    continue;
     74                } else if (LLVM_UNLIKELY(isa<Seq>(item))) {
     75                    repeat = true;
    5276                }
    5377                list.push_back(item);
    5478            }
     79            for (unsigned i = 1, run = 0; i < list.size(); ) {
     80                if (LLVM_UNLIKELY(list[i - 1] == list[i])) {
     81                    ++run;
     82                } else if (LLVM_UNLIKELY(run != 0)) {
     83                    // If we have a run of the same RE, make a bounded repetition for it
     84                    const auto j = i - run; assert (j > 0);
     85                    list[j - 1] = memoize(makeRep(list[j - 1], run + 1, run + 1));
     86                    list.erase(list.begin() + j, list.begin() + i);
     87                    i = j;
     88                    run = 0;
     89                    continue;
     90                } else if (LLVM_UNLIKELY(isa<Rep>(list[i - 1]) && isa<Rep>(list[i]))){
     91                    // If we have adjacent repetitions of the same RE, we can merge them
     92                    Rep * const r1 = cast<Rep>(list[i - 1]);
     93                    Rep * const r2 = cast<Rep>(list[i]);
     94                    if (LLVM_UNLIKELY(r1->getRE() == r2->getRE())) {
     95                        list[i - 1] = memoize(combineRep(r1, r2));
     96                        list.erase(list.begin() + i);
     97                        continue;
     98                    }
     99                }
     100                ++i;
     101            }
    55102            re = makeSeq(list.begin(), list.end());
     103            if (LLVM_UNLIKELY(repeat)) {
     104                goto repeat;
     105            }
    56106        } else if (Assertion * a = dyn_cast<Assertion>(re)) {
    57             minimize(a->getAsserted());
     107            re = makeAssertion(minimize(a->getAsserted()), a->getKind(), a->getSense());
    58108        } else if (Rep * rep = dyn_cast<Rep>(re)) {
    59             minimize(rep->getRE());
     109            re = makeRep(minimize(rep->getRE()), rep->getLB(), rep->getUB());
    60110        } else if (Diff * diff = dyn_cast<Diff>(re)) {
    61             minimize(diff->getLH());
    62             minimize(diff->getRH());
    63         } else if (Intersect * e = dyn_cast<Intersect>(re)) {
    64             minimize(e->getLH());
    65             minimize(e->getRH());
     111            re = makeDiff(minimize(diff->getLH()), minimize(diff->getRH()));
     112        } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
     113            re = makeIntersect(minimize(ix->getLH()), minimize(ix->getRH()));
    66114        } else if (Name * n = dyn_cast<Name>(re)) {
    67             assert (n->getDefinition());
    68             if (!isa<CC>(n->getDefinition())) {
    69                 n->setDefinition(minimize(n->getDefinition()));
    70             }
    71         }
    72         mMapping.emplace(original, re);
     115            RE * const def = n->getDefinition(); assert (def);
     116            if (LLVM_UNLIKELY(!isa<CC>(def))) {
     117                n->setDefinition(minimize(def));
     118            }
     119        }
     120        re = memoize(re);
     121        mMap.emplace(original, re);
     122        if (LLVM_LIKELY(original != re)) {
     123            mMap.emplace(re, re);
     124        }
    73125        return re;
    74126    }
    75127
    76     void extractCommonPrefixes(AlternationSet & source) {
    77         if (LLVM_UNLIKELY(source.size() < 2)) {
     128protected:
     129
     130    void extractCommonPrefixes(Set & source) {
     131        std::vector<RE *> combine;
     132restart:if (LLVM_UNLIKELY(source.size() < 2)) {
    78133            return;
    79134        }
    80135        for (auto i = source.begin(); i != source.end(); ++i) {
    81             assert (mCombine.empty());
    82             assert (*i);
    83             if (Seq * seq_i = dyn_cast<Seq>(*i)) {
    84                 assert (seq_i);
    85                 RE * const head = seq_i->front();
    86                 assert (head);
    87                 for (auto j = i + 1; j != source.end(); ) {
    88                     if (Seq * seq_j = dyn_cast<Seq>(*j)) {
    89                         if (LLVM_UNLIKELY(head == seq_j->front())) {
    90                             mCombine.push_back(seq_j);
    91                             j = source.erase(j);
     136            assert (combine.empty());           
     137            RE * const head = getHead(*i);
     138            for (auto j = i + 1; j != source.end(); ) {
     139                if (LLVM_UNLIKELY(head == getHead(*j))) {
     140                    combine.push_back(*j);
     141                    j = source.erase(j);
     142                    continue;
     143                }
     144                ++j;
     145            }
     146
     147            if (LLVM_UNLIKELY(!combine.empty())) {
     148                combine.push_back(*i);
     149                source.erase(i);
     150                Set tailSet;
     151                tailSet.reserve(combine.size());
     152                bool isOptional = false;
     153                for (RE * const re : combine) {
     154                    if (LLVM_LIKELY(isa<Seq>(re))) {
     155                        Seq * const seq = cast<Seq>(re);
     156                        if (LLVM_LIKELY(seq->size() > 1)) {
     157                            tailSet.insert(minimize(makeSeq(seq->begin() + 1, seq->end())));
     158                            continue;
     159                        }
     160                    } else if (LLVM_UNLIKELY(isa<Rep>(re))) {
     161                        Rep * const rep = cast<Rep>(re);
     162                        if (head != rep) {
     163                            assert (head == rep->getRE());
     164                            assert (rep->getLB() > 0);
     165                            const auto lb = rep->getLB() - 1;
     166                            const auto ub = rep->getUB() == Rep::UNBOUNDED_REP ? Rep::UNBOUNDED_REP : rep->getUB() - 1;
     167                            tailSet.insert(minimize(makeRep(rep->getRE(), lb, ub)));
    92168                            continue;
    93169                        }
    94170                    }
    95                     ++j;
    96                 }
    97                 if (LLVM_UNLIKELY(!mCombine.empty())) {
    98                     AlternationSet tailSet;
    99                     tailSet.reserve(mCombine.size() + 1);
    100                     for (Seq * seq_j : mCombine) {
    101                         if (LLVM_LIKELY(seq_j->size() > 1)) {
    102                             tailSet.insert(makeSeq(seq_j->begin() + 1, seq_j->end()));
     171                    isOptional = true;
     172                }
     173                combine.clear();
     174                extractCommonPrefixes(tailSet);
     175                RE * tail = makeAlt(tailSet.begin(), tailSet.end());
     176                if (LLVM_UNLIKELY(isOptional)) {
     177                    tail = makeRep(tail, 0, 1);
     178                }
     179                source.insert(minimize(makeSeq({ head, tail })));
     180                goto restart;
     181            }
     182        }
     183    }
     184
     185    void extractCommonSuffixes(Set & source) {
     186        std::vector<RE *> combine;
     187restart:if (LLVM_UNLIKELY(source.size() < 2)) {
     188            return;
     189        }
     190        for (auto i = source.begin(); i != source.end(); ++i) {
     191            assert (combine.empty());
     192            assert (*i);
     193            RE * const tail = getTail(*i);
     194            for (auto j = i + 1; j != source.end(); ) {
     195                if (LLVM_UNLIKELY(tail == getTail(*j))) {
     196                    combine.push_back(*j);
     197                    j = source.erase(j);
     198                    continue;
     199                }
     200                ++j;
     201            }
     202            if (LLVM_UNLIKELY(!combine.empty())) {
     203                combine.push_back(*i);
     204                source.erase(i);
     205                Set headSet;
     206                headSet.reserve(combine.size());
     207                bool isOptional = false;
     208                for (RE * const re : combine) {
     209                    if (LLVM_LIKELY(isa<Seq>(re))) {
     210                        Seq * const seq = cast<Seq>(re);
     211                        if (LLVM_LIKELY(seq->size() > 1)) {
     212                            headSet.insert(minimize(makeSeq(seq->begin(), seq->end() - 1)));
     213                            continue;
    103214                        }
    104                     }
    105                     mCombine.clear();
    106                     if (LLVM_LIKELY(seq_i->size() > 1)) {
    107                         tailSet.insert(makeSeq(seq_i->begin() + 1, seq_i->end()));
    108                     }
    109                     extractCommonPrefixes(tailSet);
    110                     source.erase(i);
    111                     RE * const tail = makeAlt(tailSet.begin(), tailSet.end());
    112                     source.insert(makeSeq({ head, tail }));
    113                     extractCommonPrefixes(source);
    114                     break;
    115                 }
    116             }
    117         }
    118     }
    119 
    120     void extractCommonSuffixes(AlternationSet & source) {
    121         if (LLVM_UNLIKELY(source.size() < 2)) {
    122             return;
    123         }
    124         for (auto i = source.begin(); i != source.end(); ++i) {
    125             assert (mCombine.empty());
    126             assert (*i);
    127             if (Seq * seq_i = dyn_cast<Seq>(*i)) {
    128                 assert (seq_i);
    129                 assert (!seq_i->empty());
    130                 RE * const tail = seq_i->back();
    131                 for (auto j = i + 1; j != source.end(); ) {
    132                     if (Seq * seq_j = dyn_cast<Seq>(*j)) {
    133                         if (LLVM_UNLIKELY(tail == seq_j->back())) {
    134                             mCombine.push_back(seq_j);
    135                             j = source.erase(j);
     215                    } else if (LLVM_UNLIKELY(isa<Rep>(re))) {
     216                        Rep * const rep = cast<Rep>(re);
     217                        if (tail != rep) {
     218                            assert (tail == rep->getRE());
     219                            assert (rep->getUB() != 0);
     220                            assert (rep->getLB() > 0);
     221                            const auto lb = rep->getLB() - 1;
     222                            const auto ub = (rep->getUB() == Rep::UNBOUNDED_REP) ? Rep::UNBOUNDED_REP : rep->getUB() - 1;
     223                            headSet.insert(minimize(makeRep(rep->getRE(), lb, ub)));
    136224                            continue;
    137225                        }
    138226                    }
    139                     ++j;
    140                 }
    141                 if (LLVM_UNLIKELY(!mCombine.empty())) {
    142                     AlternationSet headSet;
    143                     headSet.reserve(mCombine.size() + 1);
    144                     for (Seq * seq_j : mCombine) {
    145                         if (LLVM_LIKELY(seq_j->size() > 1)) {
    146                             headSet.insert(makeSeq(seq_j->begin(), seq_j->end() - 1));
    147                         }
    148                     }
    149                     mCombine.clear();
    150                     if (LLVM_LIKELY(seq_i->size() > 1)) {
    151                         headSet.insert(makeSeq(seq_i->begin(), seq_i->end() - 1));
    152                     }
    153                     extractCommonSuffixes(headSet);
    154                     extractCommonPrefixes(headSet);
    155                     source.erase(i);
    156                     RE * head = makeAlt(headSet.begin(), headSet.end());
    157                     source.insert(makeSeq({ head, tail }));
    158                     extractCommonSuffixes(source);
    159                     break;
    160                 }
    161             }
    162         }
     227                    isOptional = true;
     228                }
     229                combine.clear();
     230                extractCommonSuffixes(headSet);
     231                extractCommonPrefixes(headSet);
     232                RE * head = makeAlt(headSet.begin(), headSet.end());
     233                if (LLVM_UNLIKELY(isOptional)) {
     234                    head = makeRep(head, 0, 1);
     235                }
     236                source.insert(minimize(makeSeq({ head, tail })));
     237                goto restart;
     238            }
     239        }
     240    }
     241
     242    static CC * extractCC(RE * const re) {
     243        if (LLVM_UNLIKELY(isa<CC>(re))) {
     244            return cast<CC>(re);
     245        } else if (isa<Name>(re)) {
     246            RE * const def = cast<Name>(re)->getDefinition();
     247            if (LLVM_LIKELY(isa<CC>(def))) {
     248                return cast<CC>(def);
     249            }
     250        }
     251        return nullptr;
     252    }
     253
     254    static RE * combineRep(Rep * const r1, Rep * const r2) {
     255        assert (r1->getRE() == r2->getRE());
     256        assert (r1->getLB() != Rep::UNBOUNDED_REP);
     257        assert (r2->getLB() != Rep::UNBOUNDED_REP);
     258        const int lb = r1->getLB() + r2->getLB();
     259        int ub = Rep::UNBOUNDED_REP;
     260        if ((r1->getUB() != Rep::UNBOUNDED_REP) && (r2->getUB() != Rep::UNBOUNDED_REP)) {
     261            ub = r1->getUB() + r2->getUB();
     262        }
     263        return makeRep(r1->getRE(), lb, ub);
     264    }
     265
     266    static RE * getHead(RE * re) {
     267        assert (re);
     268        if (isa<Seq>(re)) {
     269            re = cast<Seq>(re)->front(); assert (re);
     270        } else if (isa<Rep>(re)) {
     271            Rep * const rep = cast<Rep>(re);
     272            assert (rep->getLB() != Rep::UNBOUNDED_REP);
     273            if (rep->getLB() > 0) {
     274                re = rep->getRE(); assert (re);
     275            }
     276        }
     277        return re;
     278    }
     279
     280    static RE * getTail(RE * re) {
     281        assert (re);
     282        if (isa<Seq>(re)) {
     283            re = cast<Seq>(re)->back();
     284            assert (re);
     285        } else if (isa<Rep>(re)) {
     286            Rep * const rep = cast<Rep>(re);
     287            assert (rep->getLB() != Rep::UNBOUNDED_REP);
     288            assert (rep->getUB() == Rep::UNBOUNDED_REP || rep->getUB() >= rep->getLB());
     289            if (rep->getLB() > 0) {
     290                re = rep->getRE(); assert (re);
     291            }
     292        }
     293        return re;
    163294    }
    164295
    165296private:
    166297
    167     std::vector<Seq *>  mCombine;
    168     Map                 mMapping;
     298    Map mMap;
    169299};
    170300
Note: See TracChangeset for help on using the changeset viewer.