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

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

Revised RE_Minimizer to use alphabets + minor optimizations to RE functions

File size: 11.1 KB
Line 
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>
13#include <llvm/ADT/SmallVector.h>
14
15
16using namespace llvm;
17using namespace boost::container;
18
19namespace re {
20
21using Set = flat_set<RE *>;
22using Map = flat_map<RE *, RE *>;
23using List = std::vector<RE *>;
24
25struct 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;
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] = 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    }
109
110protected:
111
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                            }
149                        }
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                            }
201                        }
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        }       
214    }
215
216    static CC * extractCC(RE * const re) {
217        if (isa<CC>(re)) {
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
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) {
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)) {
245            assert (r1->getUB() < (std::numeric_limits<int>::max() - r2->getUB()));
246            ub = r1->getUB() + r2->getUB();
247        }
248        return makeRep(r1->getRE(), lb, ub);
249    }
250
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)) {
265            if (rep->getLB() > 0) {
266                return rep->getRE();
267            }
268        }
269        return re;
270    }
271
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)) {
278            if (rep->getLB() > 0) {
279                return rep->getRE();
280            }
281        }
282        return re;
283    }
284
285    SmallVector<RE *, 16> mCombine;
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.