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

Last change on this file was 5646, checked in by nmedfort, 4 days 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.