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

Last change on this file was 5604, checked in by xuedongx, 7 weeks ago

update re_analysis for unit bounded repetition and local language

File size: 9.8 KB
Line 
1#include "re_analysis.h"
2#include <re/re_cc.h>
3#include <re/re_name.h>
4#include <re/re_start.h>
5#include <re/re_end.h>
6#include <re/re_any.h>
7#include <re/re_seq.h>
8#include <re/re_alt.h>
9#include <re/re_rep.h>
10#include <re/re_diff.h>
11#include <re/re_intersect.h>
12#include <re/re_assertion.h>
13#include <iostream>
14#include <re/printer_re.h>
15#include <limits.h>
16
17using namespace llvm;
18
19namespace re {
20
21bool isByteLength(const RE * re) {
22    if (const Alt * alt = dyn_cast<Alt>(re)) {
23        for (const RE * re : *alt) {
24            if (!isByteLength(re)) {
25                return false;
26            }
27        }
28        return true;
29    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
30        return (seq->size() == 1) && isByteLength(&seq[0]);
31    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
32        return (rep->getLB() == 1) && (rep->getUB() == 1) && isByteLength(rep->getRE());
33    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
34        return isByteLength(diff->getLH()) && isByteLength(diff->getRH());
35    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
36        return isByteLength(e->getLH()) && isByteLength(e->getRH());
37    } else if (isa<CC>(re)) {
38        return cast<CC>(re)->max_codepoint() <= 0x7F;
39    } else if (const Name * n = dyn_cast<Name>(re)) {
40        if (n->getType() == Name::Type::Byte) {
41            return true;
42        } else if (n->getType() == Name::Type::Capture || n->getType() == Name::Type::Reference) {
43            return isByteLength(n->getDefinition());
44        }
45        return false;
46    }
47    return false; // otherwise
48}
49
50bool isUnicodeUnitLength(const RE * re) {
51    if (const Alt * alt = dyn_cast<Alt>(re)) {
52        for (const RE * re : *alt) {
53            if (!isUnicodeUnitLength(re)) {
54                return false;
55            }
56        }
57        return true;
58    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
59        return (seq->size() == 1) && isUnicodeUnitLength(&seq[0]);
60    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
61        return (rep->getLB() == 1) && (rep->getUB() == 1) && isUnicodeUnitLength(rep->getRE());
62    } else if (isa<Assertion>(re)) {
63        return false;
64    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
65        return isUnicodeUnitLength(diff->getLH()) && isUnicodeUnitLength(diff->getRH());
66    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
67        return isUnicodeUnitLength(e->getLH()) && isUnicodeUnitLength(e->getRH());
68    } else if (isa<Any>(re)) {
69        return true;
70    } else if (isa<CC>(re)) {
71        return true;
72    } else if (const Name * n = dyn_cast<Name>(re)) {
73        // Eventually names might be set up for not unit length items.
74        if (n->getType() == Name::Type::Unicode || n->getType() == Name::Type::UnicodeProperty || n->getType() == Name::Type::Byte) {
75            return true;
76        } else if (n->getType() == Name::Type::Capture || n->getType() == Name::Type::Reference) {
77            return isUnicodeUnitLength(n->getDefinition());
78        }
79        return false;
80    }
81    return false; // otherwise
82}
83
84std::pair<int, int> getUnicodeUnitLengthRange(const RE * re) {
85    if (const Alt * alt = dyn_cast<Alt>(re)) {
86        std::pair<int, int> range = std::make_pair(INT_MAX, 0);
87        for (const RE * re : *alt) {
88            auto r = getUnicodeUnitLengthRange(re);
89            range.first = std::min<int>(range.first, r.first);
90            range.second = std::max<int>(range.second, r.second);
91        }
92        return range;
93    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
94        std::pair<int, int> range = std::make_pair(0, 0);
95        for (const RE * re : *seq) {
96            auto tmp = getUnicodeUnitLengthRange(re);
97            if (LLVM_LIKELY(tmp.first < (INT_MAX - range.first))) {
98                range.first += tmp.first;
99            } else {
100                range.first = INT_MAX;
101            }
102            if (LLVM_LIKELY(tmp.second < (INT_MAX - range.second))) {
103                range.second += tmp.second;
104            } else {
105                range.second = INT_MAX;
106            }
107        }
108        return range;
109    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
110        auto range = getUnicodeUnitLengthRange(rep->getRE());
111        if (LLVM_LIKELY(rep->getLB() != Rep::UNBOUNDED_REP && range.first < INT_MAX)) {
112            range.first *= rep->getLB();
113        } else {
114            range.first = INT_MAX;
115        }
116        if (LLVM_LIKELY(rep->getUB() != Rep::UNBOUNDED_REP && range.second < INT_MAX)) {
117            range.second *= rep->getUB();
118        } else {
119            range.second = INT_MAX;
120        }
121        return range;
122    } else if (isa<Assertion>(re) || isa<Start>(re) || isa<End>(re)) {
123        return std::make_pair(0, 0);
124    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
125        const auto r1 = getUnicodeUnitLengthRange(diff->getLH());
126        const auto r2 = getUnicodeUnitLengthRange(diff->getRH());
127        return std::make_pair(std::min(r1.first, r2.first), std::max(r1.second, r2.second));
128    } else if (const Intersect * i = dyn_cast<Intersect>(re)) {
129        const auto r1 = getUnicodeUnitLengthRange(i->getLH());
130        const auto r2 = getUnicodeUnitLengthRange(i->getRH());
131        return std::make_pair(std::min(r1.first, r2.first), std::max(r1.second, r2.second));
132    } else if (isa<CC>(re)) {
133        return std::make_pair(1, 1);
134    } else if (const Name * n = dyn_cast<Name>(re)) {
135        // Eventually names might be set up for not unit length items.
136        switch (n->getType()) {
137            case Name::Type::Byte:
138            case Name::Type::Unicode:
139            case Name::Type::UnicodeProperty:
140                return std::make_pair(1, 1);
141            case Name::Type::Capture:
142            case Name::Type::Reference:
143                return getUnicodeUnitLengthRange(n->getDefinition());
144            case Name::Type::ZeroWidth:
145                return std::make_pair(0, 0);
146            case Name::Type::Unknown:
147                return std::make_pair(0, INT_MAX);
148        }
149    } 
150    return std::make_pair(1, 1);
151}
152   
153int minMatchLength(RE * re) {
154    if (Alt * alt = dyn_cast<Alt>(re)) {
155        int minAltLength = INT_MAX;
156        for (RE * re : *alt) {
157            minAltLength = std::min(minAltLength, minMatchLength(re));
158        }
159        return minAltLength;
160    } else if (Seq * seq = dyn_cast<Seq>(re)) {
161        int minSeqLength = 0;
162        for (RE * re : *seq) {
163            minSeqLength += minMatchLength(re);
164        }
165        return minSeqLength;
166    } else if (Rep * rep = dyn_cast<Rep>(re)) {
167        if (rep->getLB() == 0) return 0;
168        else return (rep->getLB()) * minMatchLength(rep->getRE());
169    } else if (isa<Assertion>(re)) {
170        return 0;
171    } else if (Diff * diff = dyn_cast<Diff>(re)) {
172        return minMatchLength(diff->getLH());
173    } else if (Intersect * e = dyn_cast<Intersect>(re)) {
174        return std::min(minMatchLength(e->getLH()), minMatchLength(e->getRH()));
175    } else if (isa<Any>(re)) {
176        return 1;
177    } else if (isa<CC>(re)) {
178        return 1;
179    } else if (const Name * n = dyn_cast<Name>(re)) {
180        // Eventually names might be set up for not unit length items.
181        switch (n->getType()) {
182            case Name::Type::Byte:
183            case Name::Type::Unicode:
184            case Name::Type::UnicodeProperty:
185                return 1;
186            case Name::Type::Capture:
187            case Name::Type::Reference:
188                return minMatchLength(n->getDefinition());
189            default:
190                return 0;
191        }
192    }
193    return 0; // otherwise
194}
195
196//If a regular expression contains unit and not byteLength bounded repetition type, we select a different pipeline to utilize the log2 technique.
197bool unitBoundedRep(const RE * re) {
198    if (const Alt * alt = dyn_cast<Alt>(re)) {
199        for (const RE * re : *alt) {
200            if (unitBoundedRep(re)) {
201                return true;
202            }
203        }
204        return false;
205    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
206        for (const RE * re : *seq) {
207            if (unitBoundedRep(re)) {
208                return true;
209            }
210        }
211        return false;
212    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
213        if (rep->getLB() == 0 && rep->getUB() == Rep::UNBOUNDED_REP) {
214            return false;
215        } else {
216            return (!isByteLength(rep->getRE()) && isUnicodeUnitLength(rep->getRE()));
217        }
218    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
219        return unitBoundedRep(diff->getLH()) || unitBoundedRep(diff->getRH());
220    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
221        return unitBoundedRep(e->getLH()) || unitBoundedRep(e->getRH());
222    } else if (const Name * n = dyn_cast<Name>(re)) {
223        if (n->getType() == Name::Type::Capture || n->getType() == Name::Type::Reference) {
224            return unitBoundedRep(n->getDefinition());
225        }
226        return false;
227    }
228    return false; // otherwise
229 
230}
231
232//Cases that not include bounded repetition, assertion, start and end type can suit for local language compile pipeline.
233bool isTypeForLocal(const RE * re) {
234    if (const Alt * alt = dyn_cast<Alt>(re)) {
235        for (const RE * re : *alt) {
236            if (!isTypeForLocal(re)) {
237                return false;
238            }
239        }
240        return true;
241    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
242    for (const RE * re : *seq) {
243        if (!isTypeForLocal(re)) {
244            return false;
245        }
246    }
247        return true;
248    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
249        if (rep->getLB() != 0 || rep->getUB() != Rep::UNBOUNDED_REP) {
250            return false;
251        } 
252        return true;
253    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
254        return isTypeForLocal(diff->getLH()) && isTypeForLocal(diff->getRH());
255    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
256        return isTypeForLocal(e->getLH()) && isTypeForLocal(e->getRH());
257    } else if (isa<Start>(re) || isa<End>(re) || isa<Assertion>(re)) {
258        return false;
259    }
260    return true; // otherwise
261}
262
263}
Note: See TracBrowser for help on using the repository browser.