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

Last change on this file since 5646 was 5646, checked in by nmedfort, 21 months ago

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 size: 11.4 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
14#include <llvm/Support/raw_ostream.h>
15#include <re/printer_re.h>
16
17using namespace llvm;
18
19namespace re {
20
21using Set = boost::container::flat_set<RE *>;
22using Map = boost::container::flat_map<RE *, RE *>;
23
24struct PassContainer : private Memoizer {
25
26    RE * minimize(RE * original) {
27        const auto f = mMap.find(original);
28        if (LLVM_UNLIKELY(f != mMap.end())) {
29            return f->second;
30        }
31        RE * re = original;
32repeat: if (Alt * alt = dyn_cast<Alt>(re)) {
33            Set list;
34            list.reserve(alt->size());
35            RE * namedCC = nullptr;
36            bool repeat = false;
37            for (RE * item : *alt) {
38                item = minimize(item);
39                if (LLVM_UNLIKELY(isa<Vector>(item) && cast<Vector>(item)->empty())) {
40                    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                    }
49                }
50                list.insert(item);
51            }
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.
60            extractCommonSuffixes(list);
61            extractCommonPrefixes(list);
62            re = makeAlt(list.begin(), list.end());
63            if (LLVM_UNLIKELY(repeat)) {
64                goto repeat;
65            }
66        } else if (Seq * seq = dyn_cast<Seq>(re)) {
67            std::vector<RE *> list;
68            list.reserve(seq->size());
69            bool repeat = false;
70            for (RE * item : *seq) {
71                item = minimize(item);
72                if (LLVM_UNLIKELY(isa<Vector>(item) && cast<Vector>(item)->empty())) {
73                    continue;
74                } else if (LLVM_UNLIKELY(isa<Seq>(item))) {
75                    repeat = true;
76                }
77                list.push_back(item);
78            }
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            }
102            re = makeSeq(list.begin(), list.end());
103            if (LLVM_UNLIKELY(repeat)) {
104                goto repeat;
105            }
106        } else if (Assertion * a = dyn_cast<Assertion>(re)) {
107            re = makeAssertion(minimize(a->getAsserted()), a->getKind(), a->getSense());
108        } else if (Rep * rep = dyn_cast<Rep>(re)) {
109            re = makeRep(minimize(rep->getRE()), rep->getLB(), rep->getUB());
110        } else if (Diff * diff = dyn_cast<Diff>(re)) {
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()));
114        } else if (Name * n = dyn_cast<Name>(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        }
125        return re;
126    }
127
128protected:
129
130    void extractCommonPrefixes(Set & source) {
131        std::vector<RE *> combine;
132restart:if (LLVM_UNLIKELY(source.size() < 2)) {
133            return;
134        }
135        for (auto i = source.begin(); i != source.end(); ++i) {
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)));
168                            continue;
169                        }
170                    }
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;
214                        }
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)));
224                            continue;
225                        }
226                    }
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;
294    }
295
296private:
297
298    Map mMap;
299};
300
301
302RE * RE_Minimizer::minimize(RE * re) {
303    PassContainer pc;
304    return pc.minimize(re);
305}
306
307}
Note: See TracBrowser for help on using the repository browser.