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

Last change on this file since 5630 was 5630, checked in by nmedfort, 22 months ago

Partial check-in for avoidance of compiling Pablo/LLVM code to determine the Kernel struct type when using a cached object. Inactive RE alternation minimization check in.

File size: 6.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
14using namespace llvm;
15
16namespace re {
17
18using AlternationSet = boost::container::flat_set<RE *, MemoizerComparator>;
19
20using Map = boost::container::flat_map<RE *, RE *>;
21
22struct PassContainer {
23
24    RE * minimize(RE * const original) {
25        const auto f = mMapping.find(original);
26        if (LLVM_UNLIKELY(f != mMapping.end())) {
27            return f->second;
28        }
29        RE * re = original;
30        if (Alt * alt = dyn_cast<Alt>(re)) {
31            AlternationSet list;
32            list.reserve(alt->size());
33            for (RE * item : *alt) {
34                item = minimize(item);
35                if (LLVM_UNLIKELY(isa<Vector>(item) && cast<Vector>(item)->empty())) {
36                    continue;
37                }
38                list.insert(item);
39            }
40            // When compiling Pablo code, CSE can identify common prefixes but cannot
41            // identify common suffixes. Prioritize this optimization accordingly.
42            extractCommonSuffixes(list);
43            extractCommonPrefixes(list);
44            re = makeAlt(list.begin(), list.end());
45        } else if (Seq * seq = dyn_cast<Seq>(re)) {
46            std::vector<RE *> list;
47            list.reserve(seq->size());
48            for (RE * item : *seq) {
49                item = minimize(item);
50                if (LLVM_UNLIKELY(isa<Vector>(item) && cast<Vector>(item)->empty())) {
51                    continue;
52                }
53                list.push_back(item);
54            }
55            re = makeSeq(list.begin(), list.end());
56        } else if (Assertion * a = dyn_cast<Assertion>(re)) {
57            minimize(a->getAsserted());
58        } else if (Rep * rep = dyn_cast<Rep>(re)) {
59            minimize(rep->getRE());
60        } else if (Diff * diff = dyn_cast<Diff>(re)) {
61            minimize(diff->getLH());
62            minimize(diff->getRH());
63        } else if (Intersect * e = dyn_cast<Intersect>(re)) {
64            minimize(e->getLH());
65            minimize(e->getRH());
66        } else if (Name * n = dyn_cast<Name>(re)) {
67            assert (n->getDefinition());
68            if (!isa<CC>(n->getDefinition())) {
69                n->setDefinition(minimize(n->getDefinition()));
70            }
71        }
72        mMapping.emplace(original, re);
73        return re;
74    }
75
76    void extractCommonPrefixes(AlternationSet & source) {
77        if (LLVM_UNLIKELY(source.size() < 2)) {
78            return;
79        }
80        for (auto i = source.begin(); i != source.end(); ++i) {
81            assert (mCombine.empty());
82            assert (*i);
83            if (Seq * seq_i = dyn_cast<Seq>(*i)) {
84                assert (seq_i);
85                RE * const head = seq_i->front();
86                assert (head);
87                for (auto j = i + 1; j != source.end(); ) {
88                    if (Seq * seq_j = dyn_cast<Seq>(*j)) {
89                        if (LLVM_UNLIKELY(head == seq_j->front())) {
90                            mCombine.push_back(seq_j);
91                            j = source.erase(j);
92                            continue;
93                        }
94                    }
95                    ++j;
96                }
97                if (LLVM_UNLIKELY(!mCombine.empty())) {
98                    AlternationSet tailSet;
99                    tailSet.reserve(mCombine.size() + 1);
100                    for (Seq * seq_j : mCombine) {
101                        if (LLVM_LIKELY(seq_j->size() > 1)) {
102                            tailSet.insert(makeSeq(seq_j->begin() + 1, seq_j->end()));
103                        }
104                    }
105                    mCombine.clear();
106                    if (LLVM_LIKELY(seq_i->size() > 1)) {
107                        tailSet.insert(makeSeq(seq_i->begin() + 1, seq_i->end()));
108                    }
109                    extractCommonPrefixes(tailSet);
110                    source.erase(i);
111                    RE * const tail = makeAlt(tailSet.begin(), tailSet.end());
112                    source.insert(makeSeq({ head, tail }));
113                    extractCommonPrefixes(source);
114                    break;
115                }
116            }
117        }
118    }
119
120    void extractCommonSuffixes(AlternationSet & source) {
121        if (LLVM_UNLIKELY(source.size() < 2)) {
122            return;
123        }
124        for (auto i = source.begin(); i != source.end(); ++i) {
125            assert (mCombine.empty());
126            assert (*i);
127            if (Seq * seq_i = dyn_cast<Seq>(*i)) {
128                assert (seq_i);
129                assert (!seq_i->empty());
130                RE * const tail = seq_i->back();
131                for (auto j = i + 1; j != source.end(); ) {
132                    if (Seq * seq_j = dyn_cast<Seq>(*j)) {
133                        if (LLVM_UNLIKELY(tail == seq_j->back())) {
134                            mCombine.push_back(seq_j);
135                            j = source.erase(j);
136                            continue;
137                        }
138                    }
139                    ++j;
140                }
141                if (LLVM_UNLIKELY(!mCombine.empty())) {
142                    AlternationSet headSet;
143                    headSet.reserve(mCombine.size() + 1);
144                    for (Seq * seq_j : mCombine) {
145                        if (LLVM_LIKELY(seq_j->size() > 1)) {
146                            headSet.insert(makeSeq(seq_j->begin(), seq_j->end() - 1));
147                        }
148                    }
149                    mCombine.clear();
150                    if (LLVM_LIKELY(seq_i->size() > 1)) {
151                        headSet.insert(makeSeq(seq_i->begin(), seq_i->end() - 1));
152                    }
153                    extractCommonSuffixes(headSet);
154                    extractCommonPrefixes(headSet);
155                    source.erase(i);
156                    RE * head = makeAlt(headSet.begin(), headSet.end());
157                    source.insert(makeSeq({ head, tail }));
158                    extractCommonSuffixes(source);
159                    break;
160                }
161            }
162        }
163    }
164
165private:
166
167    std::vector<Seq *>  mCombine;
168    Map                 mMapping;
169};
170
171
172RE * RE_Minimizer::minimize(RE * re) {
173    PassContainer pc;
174    return pc.minimize(re);
175}
176
177}
Note: See TracBrowser for help on using the repository browser.