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

Last change on this file since 6173 was 6173, checked in by nmedfort, 7 months ago

Added RE_Inspector.

Migrated RE passes to RE_Transformer.

Incorporated Memoizer functionality into RE_Transformer/Inspector.

Removed Memoizer.

Bug fix for unicode_set.

File size: 11.0 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_range.h>
8#include <boost/container/flat_set.hpp>
9#include <boost/container/flat_map.hpp>
10#include <llvm/ADT/SmallVector.h>
11#include <re/re_toolchain.h>
12
13using namespace llvm;
14using namespace boost::container;
15
16namespace re {
17
18using Set = flat_set<RE *>;
19using Map = flat_map<RE *, RE *>;
20using List = std::vector<RE *>;
21
22struct PassContainer final : public RE_Transformer {
23
24    RE * transformAlt(Alt * alt) override {
25        Set set;
26        set.reserve(alt->size());
27        assert ("combine list must be empty!" && mCombine.empty());
28        for (RE * item : *alt) {
29            // since transform will memorize every item/innerItem, set insert is sufficient here
30            item = transform(item);
31            if (LLVM_UNLIKELY(isa<Alt>(item))) {               
32                for (RE * const innerItem : *cast<Alt>(item)) {
33                    set.insert(innerItem);
34                }
35            } else if (CC * const cc = extractCC(item)) {
36                combineCC(cc);
37            } else {
38                set.insert(item);
39            }
40        }
41        // insert any CC objects into the alternation
42        for (auto cc : mCombine) {
43            set.insert(transform(cc));
44        }
45        mCombine.clear();
46        // Pablo CSE may identify common prefixes but cannot identify common suffixes.
47        extractCommonSuffixes(set);
48        extractCommonPrefixes(set);
49        if (unchanged(alt, set)) {
50            return alt;
51        } else {
52            return makeAlt(set.begin(), set.end());
53        }
54    }
55
56    RE * transformSeq(Seq * seq) override {
57        List list;
58        list.reserve(seq->size());
59        for (RE * item : *seq) {
60            item = transform(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] = transform(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] = transform(combineTwoReps(r1, r2));
86                    list.erase(list.begin() + i);
87                    continue;
88                }
89            }
90            ++i;
91        }
92        if (unchanged(seq, list)) {
93            return seq;
94        } else {
95            return makeSeq(list.begin(), list.end());
96        }
97    }
98
99    RE * transformName(Name * nm) override {
100        nm->setDefinition(transform(nm->getDefinition()));
101        return nm;
102    }
103
104    PassContainer() : RE_Transformer("minimizer", NameTransformationMode::TransformDefinition) { }
105
106protected:
107
108    void extractCommonPrefixes(Set & alts) {
109        if (LLVM_LIKELY(alts.size() > 1)) {
110            SmallVector<RE *, 8> optimized;
111            for (auto i = alts.begin(); i != alts.end(); ) {
112                assert ("combine list must be empty!" && mCombine.empty());
113                RE * const head = headOf(*i);
114                for (auto j = i + 1; j != alts.end(); ) {
115                    if (LLVM_UNLIKELY(head == headOf(*j))) {
116                        mCombine.push_back(*j);
117                        j = alts.erase(j);
118                    } else {
119                        ++j;
120                    }
121                }
122                if (LLVM_LIKELY(mCombine.empty())) {
123                    ++i;
124                } else {
125                    mCombine.push_back(*i);
126                    i = alts.erase(i);
127                    Set tailSet;
128                    tailSet.reserve(mCombine.size());
129                    bool nullable = false;
130                    for (RE * const re : mCombine) {
131                        if (LLVM_LIKELY(isa<Seq>(re))) {
132                            Seq * const seq = cast<Seq>(re);
133                            if (LLVM_LIKELY(seq->size() > 1)) {
134                                assert (head == seq->front());
135                                tailSet.insert(transform(tailOf(seq)));
136                                continue;
137                            }
138                        } else if (LLVM_UNLIKELY(isa<Rep>(re))) {
139                            Rep * const rep = cast<Rep>(re);
140                            if (head != rep) {
141                                assert (head == rep->getRE());
142                                tailSet.insert(transform(makeRepWithOneFewerRepitition(rep)));
143                                continue;
144                            }
145                        }
146                        nullable = true;
147                    }
148                    mCombine.clear();
149                    if (LLVM_UNLIKELY(nullable)) {
150                        tailSet.insert(transform(makeSeq()));
151                    }
152                    RE * const tail = makeAlt(tailSet.begin(), tailSet.end());
153                    optimized.push_back(transform(makeSeq({ head, tail })));
154                }
155            }
156            alts.insert(optimized.begin(), optimized.end());
157        }       
158    }
159
160    void extractCommonSuffixes(Set & alts) {
161        if (LLVM_LIKELY(alts.size() > 1)) {
162            SmallVector<RE *, 8> optimized;
163            for (auto i = alts.begin(); i != alts.end(); ) {
164                assert ("combine list must be empty!" && mCombine.empty());
165                RE * const last = lastOf(*i);
166                for (auto j = i + 1; j != alts.end(); ) {
167                    if (LLVM_UNLIKELY(last == lastOf(*j))) {
168                        mCombine.push_back(*j);
169                        j = alts.erase(j);
170                    } else {
171                        ++j;
172                    }
173                }
174                if (LLVM_LIKELY(mCombine.empty())) {
175                    ++i;
176                } else {
177                    mCombine.push_back(*i);
178                    i = alts.erase(i);
179                    Set initSet;
180                    initSet.reserve(mCombine.size());
181                    bool nullable = false;
182                    for (RE * const re : mCombine) {
183                        if (LLVM_LIKELY(isa<Seq>(re))) {
184                            Seq * const seq = cast<Seq>(re);
185                            if (LLVM_LIKELY(seq->size() > 1)) {
186                                assert (last == seq->back());
187                                initSet.insert(transform(initOf(seq)));
188                                continue;
189                            }
190                        } else if (LLVM_UNLIKELY(isa<Rep>(re))) {
191                            Rep * const rep = cast<Rep>(re);
192                            if (last != rep) {
193                                assert (last == rep->getRE());
194                                initSet.insert(transform(makeRepWithOneFewerRepitition(rep)));
195                                continue;
196                            }
197                        }
198                        nullable = true;
199                    }
200                    mCombine.clear();
201                    if (LLVM_UNLIKELY(nullable)) {
202                        initSet.insert(transform(makeSeq()));
203                    }
204                    RE * const init = makeAlt(initSet.begin(), initSet.end());
205                    optimized.push_back(transform(makeSeq({ init, last })));
206                }
207            }
208            alts.insert(optimized.begin(), optimized.end());
209        }       
210    }
211
212    static CC * extractCC(RE * const re) {
213        if (isa<CC>(re)) {
214            return cast<CC>(re);
215        } else if (isa<Name>(re)) {
216            RE * const def = cast<Name>(re)->getDefinition();
217            if (LLVM_LIKELY(isa<CC>(def))) {
218                return cast<CC>(def);
219            }
220        }
221        return nullptr;
222    }
223
224    void combineCC(CC * const cc) {
225        for (RE *& existing : mCombine) {
226            if (LLVM_LIKELY(cast<CC>(existing)->getAlphabet() == cc->getAlphabet())) {
227                existing = makeCC(cast<CC>(existing), cc);
228                return;
229            }
230        }
231        mCombine.push_back(cc);
232    }
233
234    static RE * combineTwoReps(Rep * const r1, Rep * const r2) {
235        assert (r1->getRE() == r2->getRE());
236        assert (r1->getLB() != Rep::UNBOUNDED_REP);
237        assert (r2->getLB() != Rep::UNBOUNDED_REP);
238        const int lb = r1->getLB() + r2->getLB();
239        int ub = Rep::UNBOUNDED_REP;
240        if ((r1->getUB() != Rep::UNBOUNDED_REP) && (r2->getUB() != Rep::UNBOUNDED_REP)) {
241            assert (r1->getUB() < (std::numeric_limits<int>::max() - r2->getUB()));
242            ub = r1->getUB() + r2->getUB();
243        }
244        return makeRep(r1->getRE(), lb, ub);
245    }
246
247    static RE * makeRepWithOneFewerRepitition(Rep * const re) {
248        assert (re->getLB() > 0);
249        const auto lb = re->getLB() - 1;
250        assert (re->getUB() != 0);
251        const auto ub = (re->getUB() == Rep::UNBOUNDED_REP) ? Rep::UNBOUNDED_REP : re->getUB() - 1;
252        return makeRep(re->getRE(), lb, ub);
253    }
254
255    static RE * headOf(RE * const re) {
256        if (Seq * seq = dyn_cast<Seq>(re)) {
257            if (LLVM_LIKELY(!seq->empty())) {
258                return seq->front();
259            }
260        } else if (Rep * const rep = dyn_cast<Rep>(re)) {
261            if (rep->getLB() > 0) {
262                return rep->getRE();
263            }
264        }
265        return re;
266    }
267
268    static RE * tailOf(Seq * const seq) {
269        return makeSeq(seq->begin() + 1, seq->end());
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    static RE * initOf(Seq * const seq) {
286        return makeSeq(seq->begin(), seq->end() - 1);
287    }
288
289
290    template <typename T>
291    static bool unchanged(const Vector * A, const T & B) {
292        if (A->size() != B.size()) {
293            return false;
294        }
295        auto i = A->cbegin();
296        for (const auto j : B) {
297            if (*i != j) {
298                return false;
299            }
300            ++i;
301        }
302        return true;
303    }
304
305    SmallVector<RE *, 16> mCombine;
306};
307
308
309RE * RE_Minimizer::minimize(RE * re) {
310    PassContainer pc;
311    return pc.transformRE(re);
312}
313
314}
Note: See TracBrowser for help on using the repository browser.