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

Last change on this file since 5812 was 5755, checked in by nmedfort, 18 months ago

Bug fixes and simplified MultiBlockKernel? logic

File size: 11.3 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 *>;
23using List = std::vector<RE *>;
24
25struct PassContainer : private Memoizer {
26
27    RE * minimize(RE * original) {
28        const auto f = mMap.find(original);
29        if (LLVM_UNLIKELY(f != mMap.end())) {
30            return f->second;
31        }
32        RE * re = original;
33repeat: if (Alt * alt = dyn_cast<Alt>(re)) {
34            Set set;
35            set.reserve(alt->size());
36            RE * namedCC = nullptr;
37            bool repeat = false;
38            for (RE * item : *alt) {
39                item = minimize(item);
40                if (LLVM_UNLIKELY(isa<Alt>(item))) {
41                    if (LLVM_UNLIKELY(cast<Alt>(item)->empty())) {
42                        continue;
43                    }
44                    repeat = true;
45                } else { // if we have an alternation containing multiple CCs, combine them
46                    CC * const cc = extractCC(item);
47                    if (cc) {
48                        namedCC = namedCC ? makeCC(extractCC(namedCC), cc) : item;
49                        continue;
50                    }
51                }
52                set.insert(item);
53            }
54            // Combine and/or insert any named CC object into the alternation
55            if (namedCC) {
56                if (LLVM_UNLIKELY(isa<CC>(namedCC))) {
57                    namedCC = memoize(cast<CC>(namedCC));
58                }
59                set.insert(cast<Name>(namedCC));
60            }
61            // Pablo CSE may identify common prefixes but cannot identify common suffixes.
62            extractCommonSuffixes(set);
63            extractCommonPrefixes(set);
64            re = makeAlt(set.begin(), set.end());
65            if (LLVM_UNLIKELY(repeat)) {
66                goto repeat;
67            }
68        } else if (Seq * seq = dyn_cast<Seq>(re)) {
69            List list;
70            list.reserve(seq->size());
71            bool repeat = false;
72            for (RE * item : *seq) {
73                item = minimize(item);
74                if (LLVM_UNLIKELY(isa<Seq>(item))) {
75                    if (LLVM_UNLIKELY(cast<Seq>(item)->empty())) {
76                        continue;
77                    }
78                    repeat = true;
79                }
80                list.push_back(item);
81            }
82            for (unsigned i = 1, run = 0; i < list.size(); ) {
83                if (LLVM_UNLIKELY(list[i - 1] == list[i])) {
84                    ++run;
85                } else if (LLVM_UNLIKELY(run != 0)) {
86                    // If we have a run of the same RE, make a bounded repetition for it
87                    const auto j = i - run; assert (j > 0);
88                    list[j - 1] = memoize(makeRep(list[j - 1], run + 1, run + 1));
89                    list.erase(list.begin() + j, list.begin() + i);
90                    i = j;
91                    run = 0;
92                    continue;
93                } else if (LLVM_UNLIKELY(isa<Rep>(list[i - 1]) && isa<Rep>(list[i]))){
94                    // If we have adjacent repetitions of the same RE, we can merge them
95                    Rep * const r1 = cast<Rep>(list[i - 1]);
96                    Rep * const r2 = cast<Rep>(list[i]);
97                    if (LLVM_UNLIKELY(r1->getRE() == r2->getRE())) {
98                        list[i - 1] = memoize(combineRep(r1, r2));
99                        list.erase(list.begin() + i);
100                        continue;
101                    }
102                }
103                ++i;
104            }
105            re = makeSeq(list.begin(), list.end());
106            if (LLVM_UNLIKELY(repeat)) {
107                goto repeat;
108            }
109        } else if (Assertion * a = dyn_cast<Assertion>(re)) {
110            re = makeAssertion(minimize(a->getAsserted()), a->getKind(), a->getSense());
111        } else if (Rep * rep = dyn_cast<Rep>(re)) {
112            re = makeRep(minimize(rep->getRE()), rep->getLB(), rep->getUB());
113        } else if (Diff * diff = dyn_cast<Diff>(re)) {
114            re = makeDiff(minimize(diff->getLH()), minimize(diff->getRH()));
115        } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
116            re = makeIntersect(minimize(ix->getLH()), minimize(ix->getRH()));
117        } else if (Name * n = dyn_cast<Name>(re)) {
118            RE * const def = n->getDefinition(); assert (def);
119            if (LLVM_UNLIKELY(!isa<CC>(def))) {
120                n->setDefinition(minimize(def));
121            }
122        }
123        re = memoize(re);
124        mMap.emplace(original, re);
125        if (LLVM_LIKELY(original != re)) {
126            mMap.emplace(re, re);
127        }
128        return re;
129    }
130
131protected:
132
133    void extractCommonPrefixes(Set & source) {
134        List combine;
135repeat: if (LLVM_UNLIKELY(source.size() < 2)) {
136            return;
137        }
138        for (auto i = source.begin(); i != source.end(); ++i) {
139            assert (combine.empty());
140            RE * const head = getHead(*i);
141            for (auto j = i + 1; j != source.end(); ) {
142                if (LLVM_UNLIKELY(head == getHead(*j))) {
143                    combine.push_back(*j);
144                    j = source.erase(j);
145                    continue;
146                }
147                ++j;
148            }
149
150            if (LLVM_UNLIKELY(!combine.empty())) {
151                combine.push_back(*i);
152                source.erase(i);
153                Set tailSet;
154                tailSet.reserve(combine.size());
155                bool isOptional = false;
156                for (RE * const re : combine) {
157                    if (LLVM_LIKELY(isa<Seq>(re))) {
158                        Seq * const seq = cast<Seq>(re);
159                        if (LLVM_LIKELY(seq->size() > 1)) {
160                            tailSet.insert(minimize(makeSeq(seq->begin() + 1, seq->end())));
161                            continue;
162                        }
163                    } else if (LLVM_UNLIKELY(isa<Rep>(re))) {
164                        Rep * const rep = cast<Rep>(re);
165                        if (head != rep) {
166                            assert (head == rep->getRE());
167                            assert (rep->getLB() > 0);
168                            const auto lb = rep->getLB() - 1;
169                            const auto ub = rep->getUB() == Rep::UNBOUNDED_REP ? Rep::UNBOUNDED_REP : rep->getUB() - 1;
170                            tailSet.insert(minimize(makeRep(rep->getRE(), lb, ub)));
171                            continue;
172                        }
173                    }
174                    isOptional = true;
175                }
176                combine.clear();
177                extractCommonPrefixes(tailSet);
178                RE * tail = makeAlt(tailSet.begin(), tailSet.end());
179                if (LLVM_UNLIKELY(isOptional)) {
180                    tail = makeRep(tail, 0, 1);
181                }
182                source.insert(minimize(makeSeq({ head, tail })));
183                goto repeat;
184            }
185        }
186    }
187
188    void extractCommonSuffixes(Set & source) {
189        List combine;
190repeat: if (LLVM_UNLIKELY(source.size() < 2)) {
191            return;
192        }
193        for (auto i = source.begin(); i != source.end(); ++i) {
194            assert (combine.empty());
195            assert (*i);
196            RE * const tail = getTail(*i);
197            for (auto j = i + 1; j != source.end(); ) {
198                if (LLVM_UNLIKELY(tail == getTail(*j))) {
199                    combine.push_back(*j);
200                    j = source.erase(j);
201                    continue;
202                }
203                ++j;
204            }
205            if (LLVM_UNLIKELY(!combine.empty())) {
206                combine.push_back(*i);
207                source.erase(i);
208                Set headSet;
209                headSet.reserve(combine.size());
210                bool isOptional = false;
211                for (RE * const re : combine) {
212                    if (LLVM_LIKELY(isa<Seq>(re))) {
213                        Seq * const seq = cast<Seq>(re);
214                        if (LLVM_LIKELY(seq->size() > 1)) {
215                            headSet.insert(minimize(makeSeq(seq->begin(), seq->end() - 1)));
216                            continue;
217                        }
218                    } else if (LLVM_UNLIKELY(isa<Rep>(re))) {
219                        Rep * const rep = cast<Rep>(re);
220                        if (tail != rep) {
221                            assert (tail == rep->getRE());
222                            assert (rep->getUB() != 0);
223                            assert (rep->getLB() > 0);
224                            const auto lb = rep->getLB() - 1;
225                            const auto ub = (rep->getUB() == Rep::UNBOUNDED_REP) ? Rep::UNBOUNDED_REP : rep->getUB() - 1;
226                            headSet.insert(minimize(makeRep(rep->getRE(), lb, ub)));
227                            continue;
228                        }
229                    }
230                    isOptional = true;
231                }
232                combine.clear();
233                extractCommonSuffixes(headSet);
234                extractCommonPrefixes(headSet);
235                RE * head = makeAlt(headSet.begin(), headSet.end());
236                if (LLVM_UNLIKELY(isOptional)) {
237                    head = makeRep(head, 0, 1);
238                }
239                source.insert(minimize(makeSeq({ head, tail })));
240                goto repeat;
241            }
242        }
243    }
244
245    static CC * extractCC(RE * const re) {
246        if (LLVM_UNLIKELY(isa<CC>(re))) {
247            return cast<CC>(re);
248        } else if (isa<Name>(re)) {
249            RE * const def = cast<Name>(re)->getDefinition();
250            if (LLVM_LIKELY(isa<CC>(def))) {
251                return cast<CC>(def);
252            }
253        }
254        return nullptr;
255    }
256
257    static RE * combineRep(Rep * const r1, Rep * const r2) {
258        assert (r1->getRE() == r2->getRE());
259        assert (r1->getLB() != Rep::UNBOUNDED_REP);
260        assert (r2->getLB() != Rep::UNBOUNDED_REP);
261        const int lb = r1->getLB() + r2->getLB();
262        int ub = Rep::UNBOUNDED_REP;
263        if ((r1->getUB() != Rep::UNBOUNDED_REP) && (r2->getUB() != Rep::UNBOUNDED_REP)) {
264            ub = r1->getUB() + r2->getUB();
265        }
266        return makeRep(r1->getRE(), lb, ub);
267    }
268
269    static RE * getHead(RE * re) {
270        assert (re);
271        if (isa<Seq>(re)) {
272            re = cast<Seq>(re)->front(); assert (re);
273        } else if (isa<Rep>(re)) {
274            Rep * const rep = cast<Rep>(re);
275            assert (rep->getLB() != Rep::UNBOUNDED_REP);
276            if (rep->getLB() > 0) {
277                re = rep->getRE(); assert (re);
278            }
279        }
280        return re;
281    }
282
283    static RE * getTail(RE * re) {
284        assert (re);
285        if (isa<Seq>(re)) {
286            re = cast<Seq>(re)->back();
287            assert (re);
288        } else if (isa<Rep>(re)) {
289            Rep * const rep = cast<Rep>(re);
290            assert (rep->getLB() != Rep::UNBOUNDED_REP);
291            assert (rep->getUB() == Rep::UNBOUNDED_REP || rep->getUB() >= rep->getLB());
292            if (rep->getLB() > 0) {
293                re = rep->getRE(); assert (re);
294            }
295        }
296        return re;
297    }
298
299private:
300
301    Map mMap;
302};
303
304
305RE * RE_Minimizer::minimize(RE * re) {
306    PassContainer pc;
307    return pc.minimize(re);
308}
309
310}
Note: See TracBrowser for help on using the repository browser.