source: icGREP/icgrep-devel/icgrep/re/re_local.cpp @ 5748

Last change on this file since 5748 was 5748, checked in by nmedfort, 14 months ago

Bug fix for segment pipeline parallel mode + memory management improvements.

File size: 6.8 KB
Line 
1#include "re_local.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_any.h>
11#include <re/re_analysis.h>
12#include <UCD/resolve_properties.h>
13#include <boost/container/flat_set.hpp>
14#include <boost/range/adaptor/reversed.hpp>
15#include <util/slab_allocator.h>
16#include <map>
17
18using namespace boost::container;
19using namespace llvm;
20
21namespace re {
22 
23inline void combine(CC *& a, CC * b) {
24    if (a && b) {
25        a = makeCC(a, b);
26    } else if (b) {
27        a = b;
28    }
29}
30
31CC * RE_Local::first(RE * re) {
32    if (Name * name = dyn_cast<Name>(re)) {
33        if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
34            return first(name->getDefinition());
35        } else {
36            UndefinedNameError(name);
37        }
38    } else if (CC * cc = dyn_cast<CC>(re)) {
39        return cc;
40    } else if (Seq * seq = dyn_cast<Seq>(re)) {
41        CC * cc = nullptr;
42        for (auto & si : *seq) {
43            combine(cc, first(si));
44            if (!isNullable(si)) {
45                break;
46            }
47        }
48        return cc;
49    } else if (Alt * alt = dyn_cast<Alt>(re)) {
50        CC * cc = nullptr;
51        for (auto & ai : *alt) {
52            combine(cc, first(ai));
53        }
54        return cc;
55    } else if (Rep * rep = dyn_cast<Rep>(re)) {
56        return first(rep->getRE());
57    } else if (Diff * diff = dyn_cast<Diff>(re)) {
58        if (CC * lh = first(diff->getLH())) {
59            if (CC * rh = first(diff->getRH())) {
60                return subtractCC(lh, rh);
61            }
62        }
63    } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
64        if (CC * lh = first(ix->getLH())) {
65            if (CC * rh = first(ix->getRH())) {
66                return intersectCC(lh, rh);
67            }
68        }
69    }
70    return nullptr;
71}
72
73CC * RE_Local::final(RE * re) {
74    if (Name * name = dyn_cast<Name>(re)) {
75        if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
76            return final(name->getDefinition());
77        } else {
78            UndefinedNameError(name);
79        }
80    } else if (CC * cc = dyn_cast<CC>(re)) {
81        return cc;
82    } else if (Seq * seq = dyn_cast<Seq>(re)) {
83        CC * cc = nullptr;
84        for (auto & si : boost::adaptors::reverse(*seq)) {
85            combine(cc, first(si));
86            if (!isNullable(si)) {
87                break;
88            }
89        }
90        return cc;
91    } else if (Alt * alt = dyn_cast<Alt>(re)) {
92        CC * cc = nullptr;
93        for (auto & ai : *alt) {
94            combine(cc, final(ai));
95        }
96        return cc;
97    } else if (Rep * rep = dyn_cast<Rep>(re)) {
98        return final(rep->getRE());
99    } else if (Diff * diff = dyn_cast<Diff>(re)) {
100        if (CC * lh = final(diff->getLH())) {
101            if (CC * rh = final(diff->getRH())) {
102                return subtractCC(lh, rh);
103            }
104        }
105    } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
106        if (CC * lh = final(ix->getLH())) {
107            if (CC * rh = final(ix->getRH())) {
108                return intersectCC(lh, rh);
109            }
110        }
111    }
112    return nullptr;
113
114}
115
116void RE_Local::follow(RE * re, std::map<CC *, CC*> &follow_map) {
117    if (Name * name = dyn_cast<Name>(re)) {
118        if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
119            return follow(name->getDefinition(), follow_map);
120        } else {
121            UndefinedNameError(name);
122        }
123    } else if (Seq * seq = dyn_cast<Seq>(re)) {
124        if (seq->size() > 0) {
125            RE * re_first = *(seq->begin());
126            RE * re_follow = makeSeq(seq->begin() + 1, seq->end());
127            auto e1 = final(re_first);
128            auto e2 = first(re_follow);
129            if (e1 && e2) {
130                auto e = follow_map.find(e1);
131                if (e != follow_map.end()) {
132                    e->second = makeCC(e->second, e2);
133                } else {
134                    follow_map.emplace(e1, e2);
135                }
136            }
137            follow(re_first, follow_map);
138            follow(re_follow, follow_map);
139        }
140    } else if (Alt * alt = dyn_cast<Alt>(re)) {
141        for (auto ai = alt->begin(); ai != alt->end(); ++ai) {
142            follow(*ai, follow_map);
143        }
144    } else if (Rep * rep = dyn_cast<Rep>(re)) {
145        auto e1 = final(rep->getRE());
146        auto e2 = first(rep->getRE());
147        if (e1 && e2) {
148            auto e = follow_map.find(e1);
149            if (e != follow_map.end()) {
150                e->second = makeCC(e->second, e2);
151            } else {
152                follow_map.emplace(e1, e2);
153            }
154        }
155        follow(rep->getRE(), follow_map);
156    }
157}
158
159bool RE_Local::isLocalLanguage(RE * re) {   
160    UCD::UnicodeSet seen;
161    return isLocalLanguage_helper(re, seen);
162}
163
164bool RE_Local::isLocalLanguage_helper(const RE * re, UCD::UnicodeSet & seen) {
165    assert ("RE object cannot be null!" && re);
166    if (isa<Any>(re)) {
167        const bool no_intersect = seen.empty();
168        seen.insert_range(0x00, 0x10FFFF);
169        return no_intersect;
170    } else if (const CC * cc = dyn_cast<CC>(re)) {
171        const bool has_intersect = cc->intersects(seen);
172        seen = seen + *cc;
173        return !has_intersect;
174    } else if (const Name * n = dyn_cast<Name>(re)) {
175        return isLocalLanguage_helper(n->getDefinition(), seen);
176    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
177        for (const RE * item : *seq) {
178            if (!isLocalLanguage_helper(item, seen)) return false;
179        }
180        return true;
181    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
182        for (RE * item : *alt) {
183            if (!isLocalLanguage_helper(item, seen)) return false;
184        }
185        return true;
186    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
187        if (rep->getUB() > 1) return false;
188        return isLocalLanguage_helper(rep->getRE(), seen);
189    } else {
190        // A local language cannot contain Intersects, Differences, Assertions, Start, End.
191        return false;
192    }
193}
194
195bool RE_Local::isNullable(const RE * re) {
196    if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
197        for (const RE * re : *re_seq) {
198            if (!isNullable(re)) {
199                return false;
200            }
201        }
202        return true;
203    } else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
204        for (const RE * re : *re_alt) {
205            if (isNullable(re)) {
206                return true;
207            }
208        }
209    } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
210        return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
211    } else if (const Diff * diff = dyn_cast<const Diff>(re)) {
212        return isNullable(diff->getLH()) && !isNullable(diff->getRH());
213    } else if (const Intersect * e = dyn_cast<const Intersect>(re)) {
214        return isNullable(e->getLH()) && isNullable(e->getRH());
215    } 
216    return false;
217}
218
219}
Note: See TracBrowser for help on using the repository browser.