source: icGREP/icgrep-devel/icgrep/re/re_minimizer.cpp @ 5835

Last change on this file since 5835 was 5835, checked in by nmedfort, 17 months ago

Revised RE_Minimizer to use alphabets + minor optimizations to RE functions

File size: 11.1 KB
RevLine 
[5630]1#include "re_minimizer.h"
2#include <re/re_name.h>
3#include <re/re_alt.h>
4#include <re/re_cc.h>
5#include <re/re_seq.h>
6#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>
11#include <boost/container/flat_set.hpp>
12#include <boost/container/flat_map.hpp>
[5835]13#include <llvm/ADT/SmallVector.h>
[5630]14
[5646]15
[5630]16using namespace llvm;
[5835]17using namespace boost::container;
[5630]18
19namespace re {
20
[5835]21using Set = flat_set<RE *>;
22using Map = flat_map<RE *, RE *>;
[5755]23using List = std::vector<RE *>;
[5630]24
[5646]25struct PassContainer : private Memoizer {
[5630]26
[5835]27    RE * minimize(RE * re) {
28        const auto f = find(re);
29        if (LLVM_UNLIKELY(f != end())) {
30            return *f;
[5630]31        }
[5835]32        if (Alt * const alt = dyn_cast<Alt>(re)) {
[5755]33            Set set;
34            set.reserve(alt->size());
[5630]35            for (RE * item : *alt) {
36                item = minimize(item);
[5755]37                if (LLVM_UNLIKELY(isa<Alt>(item))) {
[5835]38                    for (RE * const innerItem : *cast<Alt>(item)) {
39                        set.insert(innerItem);
[5755]40                    }
[5835]41                } else if (CC * const cc = extractCC(item)) {
42                    combineCC(cc);
43                } else {
44                    set.insert(item);
[5630]45                }
46            }
[5835]47            // insert any CC objects into the alternation
48            for (auto cc : mCombine) {
49                set.insert(memoize(cc));
[5646]50            }
[5835]51            mCombine.clear();
[5646]52            // Pablo CSE may identify common prefixes but cannot identify common suffixes.
[5755]53            extractCommonSuffixes(set);
54            extractCommonPrefixes(set);
55            re = makeAlt(set.begin(), set.end());
[5835]56        } else if (Seq * const seq = dyn_cast<Seq>(re)) {
[5755]57            List list;
[5630]58            list.reserve(seq->size());
59            for (RE * item : *seq) {
60                item = minimize(item);
[5755]61                if (LLVM_UNLIKELY(isa<Seq>(item))) {
[5835]62                    for (RE * const innerItem : *cast<Seq>(item)) {
63                        list.push_back(innerItem);
[5755]64                    }
[5835]65                } else {
66                    list.push_back(item);
[5630]67                }
68            }
[5646]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;
79                    continue;
80                } else if (LLVM_UNLIKELY(isa<Rep>(list[i - 1]) && isa<Rep>(list[i]))){
[5835]81                    // If we have adjacent repetitions of the same RE, merge them
[5646]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())) {
[5835]85                        list[i - 1] = memoize(combineTwoReps(r1, r2));
[5646]86                        list.erase(list.begin() + i);
87                        continue;
88                    }
89                }
90                ++i;
91            }
[5630]92            re = makeSeq(list.begin(), list.end());
[5835]93        } else if (Assertion * const a = dyn_cast<Assertion>(re)) {
[5646]94            re = makeAssertion(minimize(a->getAsserted()), a->getKind(), a->getSense());
[5835]95        } else if (Rep * const rep = dyn_cast<Rep>(re)) {
[5646]96            re = makeRep(minimize(rep->getRE()), rep->getLB(), rep->getUB());
[5835]97        } else if (Diff * const diff = dyn_cast<Diff>(re)) {
[5646]98            re = makeDiff(minimize(diff->getLH()), minimize(diff->getRH()));
[5835]99        } else if (Intersect * const ix = dyn_cast<Intersect>(re)) {
[5646]100            re = makeIntersect(minimize(ix->getLH()), minimize(ix->getRH()));
[5835]101        } else if (Name * const n = dyn_cast<Name>(re)) {
102            RE * const def = n->getDefinition();
103            if (LLVM_LIKELY(def != nullptr)) {
[5646]104                n->setDefinition(minimize(def));
[5630]105            }
106        }
[5835]107        return memoize(re);
[5630]108    }
109
[5646]110protected:
111
[5835]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                    }
[5646]125                }
[5835]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                            }
[5630]149                        }
[5835]150                        nullable = true;
[5630]151                    }
[5835]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 })));
[5630]158                }
159            }
[5835]160            alts.insert(optimized.begin(), optimized.end());
161        }       
[5630]162    }
163
[5835]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                    }
[5646]177                }
[5835]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                            }
[5630]201                        }
[5835]202                        nullable = true;
[5630]203                    }
[5835]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 })));
[5630]210                }
211            }
[5835]212            alts.insert(optimized.begin(), optimized.end());
213        }       
[5630]214    }
215
[5646]216    static CC * extractCC(RE * const re) {
[5835]217        if (isa<CC>(re)) {
[5646]218            return cast<CC>(re);
219        } else if (isa<Name>(re)) {
220            RE * const def = cast<Name>(re)->getDefinition();
221            if (LLVM_LIKELY(isa<CC>(def))) {
222                return cast<CC>(def);
223            }
224        }
225        return nullptr;
226    }
227
[5835]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) {
[5646]239        assert (r1->getRE() == r2->getRE());
240        assert (r1->getLB() != Rep::UNBOUNDED_REP);
241        assert (r2->getLB() != Rep::UNBOUNDED_REP);
242        const int lb = r1->getLB() + r2->getLB();
243        int ub = Rep::UNBOUNDED_REP;
244        if ((r1->getUB() != Rep::UNBOUNDED_REP) && (r2->getUB() != Rep::UNBOUNDED_REP)) {
[5835]245            assert (r1->getUB() < (std::numeric_limits<int>::max() - r2->getUB()));
[5646]246            ub = r1->getUB() + r2->getUB();
247        }
248        return makeRep(r1->getRE(), lb, ub);
249    }
250
[5835]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)) {
[5646]265            if (rep->getLB() > 0) {
[5835]266                return rep->getRE();
[5646]267            }
268        }
269        return re;
270    }
271
[5835]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)) {
[5646]278            if (rep->getLB() > 0) {
[5835]279                return rep->getRE();
[5646]280            }
281        }
282        return re;
283    }
284
[5835]285    SmallVector<RE *, 16> mCombine;
[5630]286};
287
288
289RE * RE_Minimizer::minimize(RE * re) {
290    PassContainer pc;
291    return pc.minimize(re);
292}
293
294}
Note: See TracBrowser for help on using the repository browser.