Ignore:
Timestamp:
Oct 16, 2018, 2:29:44 PM (7 months ago)
Author:
nmedfort
Message:

Added RE_Inspector.

Migrated RE passes to RE_Transformer.

Incorporated Memoizer functionality into RE_Transformer/Inspector.

Removed Memoizer.

Bug fix for unicode_set.

File:
1 edited

Legend:

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

    r5835 r6173  
    55#include <re/re_seq.h>
    66#include <re/re_rep.h>
    7 #include <re/re_diff.h>
    8 #include <re/re_intersect.h>
    9 #include <re/re_assertion.h>
    10 #include <re/re_memoizer.hpp>
     7#include <re/re_range.h>
    118#include <boost/container/flat_set.hpp>
    129#include <boost/container/flat_map.hpp>
    1310#include <llvm/ADT/SmallVector.h>
    14 
     11#include <re/re_toolchain.h>
    1512
    1613using namespace llvm;
     
    2320using List = std::vector<RE *>;
    2421
    25 struct PassContainer : private Memoizer {
    26 
    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)) {
    33             Set set;
    34             set.reserve(alt->size());
    35             for (RE * item : *alt) {
    36                 item = minimize(item);
    37                 if (LLVM_UNLIKELY(isa<Alt>(item))) {
    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();
    52             // Pablo CSE may identify common prefixes but cannot identify common suffixes.
    53             extractCommonSuffixes(set);
    54             extractCommonPrefixes(set);
    55             re = makeAlt(set.begin(), set.end());
    56         } else if (Seq * const seq = dyn_cast<Seq>(re)) {
    57             List list;
    58             list.reserve(seq->size());
    59             for (RE * item : *seq) {
    60                 item = minimize(item);
    61                 if (LLVM_UNLIKELY(isa<Seq>(item))) {
    62                     for (RE * const innerItem : *cast<Seq>(item)) {
    63                         list.push_back(innerItem);
    64                     }
    65                 } else {
    66                     list.push_back(item);
    67                 }
    68             }
    69             for (unsigned i = 1, run = 0; i < list.size(); ) {
    70                 if (LLVM_UNLIKELY(list[i - 1] == list[i])) {
    71                     ++run;
    72                 } else if (LLVM_UNLIKELY(run != 0)) {
    73                     // If we have a run of the same RE, make a bounded repetition for it
    74                     const auto j = i - run; assert (j > 0);
    75                     list[j - 1] = memoize(makeRep(list[j - 1], run + 1, run + 1));
    76                     list.erase(list.begin() + j, list.begin() + i);
    77                     i = j;
    78                     run = 0;
     22struct PassContainer final : public RE_Transformer {
     23
     24    RE * transformAlt(Alt * alt) override {
     25        Set set;
     26        set.reserve(alt->size());
     27        assert ("combine list must be empty!" && mCombine.empty());
     28        for (RE * item : *alt) {
     29            // since transform will memorize every item/innerItem, set insert is sufficient here
     30            item = transform(item);
     31            if (LLVM_UNLIKELY(isa<Alt>(item))) {               
     32                for (RE * const innerItem : *cast<Alt>(item)) {
     33                    set.insert(innerItem);
     34                }
     35            } else if (CC * const cc = extractCC(item)) {
     36                combineCC(cc);
     37            } else {
     38                set.insert(item);
     39            }
     40        }
     41        // insert any CC objects into the alternation
     42        for (auto cc : mCombine) {
     43            set.insert(transform(cc));
     44        }
     45        mCombine.clear();
     46        // Pablo CSE may identify common prefixes but cannot identify common suffixes.
     47        extractCommonSuffixes(set);
     48        extractCommonPrefixes(set);
     49        if (unchanged(alt, set)) {
     50            return alt;
     51        } else {
     52            return makeAlt(set.begin(), set.end());
     53        }
     54    }
     55
     56    RE * transformSeq(Seq * seq) override {
     57        List list;
     58        list.reserve(seq->size());
     59        for (RE * item : *seq) {
     60            item = transform(item);
     61            if (LLVM_UNLIKELY(isa<Seq>(item))) {
     62                for (RE * const innerItem : *cast<Seq>(item)) {
     63                    list.push_back(innerItem);
     64                }
     65            } else {
     66                list.push_back(item);
     67            }
     68        }
     69        for (unsigned i = 1, run = 0; i < list.size(); ) {
     70            if (LLVM_UNLIKELY(list[i - 1] == list[i])) {
     71                ++run;
     72            } else if (LLVM_UNLIKELY(run != 0)) {
     73                // If we have a run of the same RE, make a bounded repetition for it
     74                const auto j = i - run; assert (j > 0);
     75                list[j - 1] = transform(makeRep(list[j - 1], run + 1, run + 1));
     76                list.erase(list.begin() + j, list.begin() + i);
     77                i = j;
     78                run = 0;
     79                continue;
     80            } else if (LLVM_UNLIKELY(isa<Rep>(list[i - 1]) && isa<Rep>(list[i]))){
     81                // If we have adjacent repetitions of the same RE, merge them
     82                Rep * const r1 = cast<Rep>(list[i - 1]);
     83                Rep * const r2 = cast<Rep>(list[i]);
     84                if (LLVM_UNLIKELY(r1->getRE() == r2->getRE())) {
     85                    list[i - 1] = transform(combineTwoReps(r1, r2));
     86                    list.erase(list.begin() + i);
    7987                    continue;
    80                 } else if (LLVM_UNLIKELY(isa<Rep>(list[i - 1]) && isa<Rep>(list[i]))){
    81                     // If we have adjacent repetitions of the same RE, merge them
    82                     Rep * const r1 = cast<Rep>(list[i - 1]);
    83                     Rep * const r2 = cast<Rep>(list[i]);
    84                     if (LLVM_UNLIKELY(r1->getRE() == r2->getRE())) {
    85                         list[i - 1] = memoize(combineTwoReps(r1, r2));
    86                         list.erase(list.begin() + i);
    87                         continue;
    88                     }
    89                 }
    90                 ++i;
    91             }
    92             re = makeSeq(list.begin(), list.end());
    93         } else if (Assertion * const a = dyn_cast<Assertion>(re)) {
    94             re = makeAssertion(minimize(a->getAsserted()), a->getKind(), a->getSense());
    95         } else if (Rep * const rep = dyn_cast<Rep>(re)) {
    96             re = makeRep(minimize(rep->getRE()), rep->getLB(), rep->getUB());
    97         } else if (Diff * const diff = dyn_cast<Diff>(re)) {
    98             re = makeDiff(minimize(diff->getLH()), minimize(diff->getRH()));
    99         } else if (Intersect * const ix = dyn_cast<Intersect>(re)) {
    100             re = makeIntersect(minimize(ix->getLH()), minimize(ix->getRH()));
    101         } else if (Name * const n = dyn_cast<Name>(re)) {
    102             RE * const def = n->getDefinition();
    103             if (LLVM_LIKELY(def != nullptr)) {
    104                 n->setDefinition(minimize(def));
    105             }
    106         }
    107         return memoize(re);
    108     }
     88                }
     89            }
     90            ++i;
     91        }
     92        if (unchanged(seq, list)) {
     93            return seq;
     94        } else {
     95            return makeSeq(list.begin(), list.end());
     96        }
     97    }
     98
     99    RE * transformName(Name * nm) override {
     100        nm->setDefinition(transform(nm->getDefinition()));
     101        return nm;
     102    }
     103
     104    PassContainer() : RE_Transformer("minimizer", NameTransformationMode::TransformDefinition) { }
    109105
    110106protected:
    111107
    112     void extractCommonPrefixes(Set & alts) {       
     108    void extractCommonPrefixes(Set & alts) {
    113109        if (LLVM_LIKELY(alts.size() > 1)) {
    114110            SmallVector<RE *, 8> optimized;
     
    137133                            if (LLVM_LIKELY(seq->size() > 1)) {
    138134                                assert (head == seq->front());
    139                                 tailSet.insert(memoize(makeSeq(seq->begin() + 1, seq->end())));
     135                                tailSet.insert(transform(tailOf(seq)));
    140136                                continue;
    141137                            }
     
    144140                            if (head != rep) {
    145141                                assert (head == rep->getRE());
    146                                 tailSet.insert(memoize(makeRepWithOneFewerRepitition(rep)));
     142                                tailSet.insert(transform(makeRepWithOneFewerRepitition(rep)));
    147143                                continue;
    148144                            }
     
    152148                    mCombine.clear();
    153149                    if (LLVM_UNLIKELY(nullable)) {
    154                         tailSet.insert(memoize(makeSeq()));
     150                        tailSet.insert(transform(makeSeq()));
    155151                    }
    156152                    RE * const tail = makeAlt(tailSet.begin(), tailSet.end());
    157                     optimized.push_back(minimize(makeSeq({ head, tail })));
     153                    optimized.push_back(transform(makeSeq({ head, tail })));
    158154                }
    159155            }
     
    189185                            if (LLVM_LIKELY(seq->size() > 1)) {
    190186                                assert (last == seq->back());
    191                                 initSet.insert(memoize(makeSeq(seq->begin(), seq->end() - 1)));
     187                                initSet.insert(transform(initOf(seq)));
    192188                                continue;
    193189                            }
     
    196192                            if (last != rep) {
    197193                                assert (last == rep->getRE());
    198                                 initSet.insert(memoize(makeRepWithOneFewerRepitition(rep)));
     194                                initSet.insert(transform(makeRepWithOneFewerRepitition(rep)));
    199195                                continue;
    200196                            }
     
    204200                    mCombine.clear();
    205201                    if (LLVM_UNLIKELY(nullable)) {
    206                         initSet.insert(memoize(makeSeq()));
     202                        initSet.insert(transform(makeSeq()));
    207203                    }
    208204                    RE * const init = makeAlt(initSet.begin(), initSet.end());
    209                     optimized.push_back(minimize(makeSeq({ init, last })));
     205                    optimized.push_back(transform(makeSeq({ init, last })));
    210206                }
    211207            }
     
    270266    }
    271267
     268    static RE * tailOf(Seq * const seq) {
     269        return makeSeq(seq->begin() + 1, seq->end());
     270    }
     271
    272272    static RE * lastOf(RE * const re) {
    273273        if (Seq * seq = dyn_cast<Seq>(re)) {
     
    283283    }
    284284
     285    static RE * initOf(Seq * const seq) {
     286        return makeSeq(seq->begin(), seq->end() - 1);
     287    }
     288
     289
     290    template <typename T>
     291    static bool unchanged(const Vector * A, const T & B) {
     292        if (A->size() != B.size()) {
     293            return false;
     294        }
     295        auto i = A->cbegin();
     296        for (const auto j : B) {
     297            if (*i != j) {
     298                return false;
     299            }
     300            ++i;
     301        }
     302        return true;
     303    }
     304
    285305    SmallVector<RE *, 16> mCombine;
    286306};
     
    289309RE * RE_Minimizer::minimize(RE * re) {
    290310    PassContainer pc;
    291     return pc.minimize(re);
     311    return pc.transformRE(re);
    292312}
    293313
Note: See TracChangeset for help on using the changeset viewer.