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

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

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

File size: 6.8 KB
RevLine 
[5568]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>
[5619]14#include <boost/range/adaptor/reversed.hpp>
[5748]15#include <util/slab_allocator.h>
[5568]16#include <map>
17
18using namespace boost::container;
19using namespace llvm;
20
21namespace re {
22 
[5619]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) {
[5568]32    if (Name * name = dyn_cast<Name>(re)) {
33        if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
[5619]34            return first(name->getDefinition());
[5568]35        } else {
[5649]36            UndefinedNameError(name);
[5568]37        }
38    } else if (CC * cc = dyn_cast<CC>(re)) {
[5619]39        return cc;
[5568]40    } else if (Seq * seq = dyn_cast<Seq>(re)) {
[5619]41        CC * cc = nullptr;
42        for (auto & si : *seq) {
43            combine(cc, first(si));
44            if (!isNullable(si)) {
[5568]45                break;
46            }
47        }
[5619]48        return cc;
[5568]49    } else if (Alt * alt = dyn_cast<Alt>(re)) {
[5619]50        CC * cc = nullptr;
51        for (auto & ai : *alt) {
52            combine(cc, first(ai));
[5568]53        }
[5619]54        return cc;
[5568]55    } else if (Rep * rep = dyn_cast<Rep>(re)) {
56        return first(rep->getRE());
57    } else if (Diff * diff = dyn_cast<Diff>(re)) {
[5619]58        if (CC * lh = first(diff->getLH())) {
59            if (CC * rh = first(diff->getRH())) {
60                return subtractCC(lh, rh);
61            }
[5568]62        }
63    } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
[5619]64        if (CC * lh = first(ix->getLH())) {
65            if (CC * rh = first(ix->getRH())) {
66                return intersectCC(lh, rh);
67            }
[5568]68        }
69    }
70    return nullptr;
71}
72
[5619]73CC * RE_Local::final(RE * re) {
[5568]74    if (Name * name = dyn_cast<Name>(re)) {
75        if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
[5619]76            return final(name->getDefinition());
[5568]77        } else {
[5649]78            UndefinedNameError(name);
[5568]79        }
80    } else if (CC * cc = dyn_cast<CC>(re)) {
[5619]81        return cc;
[5568]82    } else if (Seq * seq = dyn_cast<Seq>(re)) {
[5619]83        CC * cc = nullptr;
84        for (auto & si : boost::adaptors::reverse(*seq)) {
85            combine(cc, first(si));
86            if (!isNullable(si)) {
[5568]87                break;
88            }
89        }
[5619]90        return cc;
[5568]91    } else if (Alt * alt = dyn_cast<Alt>(re)) {
[5619]92        CC * cc = nullptr;
93        for (auto & ai : *alt) {
94            combine(cc, final(ai));
[5568]95        }
[5619]96        return cc;
[5568]97    } else if (Rep * rep = dyn_cast<Rep>(re)) {
98        return final(rep->getRE());
99    } else if (Diff * diff = dyn_cast<Diff>(re)) {
[5619]100        if (CC * lh = final(diff->getLH())) {
101            if (CC * rh = final(diff->getRH())) {
102                return subtractCC(lh, rh);
103            }
[5568]104        }
105    } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
[5619]106        if (CC * lh = final(ix->getLH())) {
107            if (CC * rh = final(ix->getRH())) {
108                return intersectCC(lh, rh);
109            }
[5568]110        }
111    }
112    return nullptr;
113
114}
115
[5620]116void RE_Local::follow(RE * re, std::map<CC *, CC*> &follow_map) {
[5568]117    if (Name * name = dyn_cast<Name>(re)) {
118        if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
119            return follow(name->getDefinition(), follow_map);
120        } else {
[5649]121            UndefinedNameError(name);
[5568]122        }
123    } else if (Seq * seq = dyn_cast<Seq>(re)) {
[5736]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                }
[5568]136            }
[5736]137            follow(re_first, follow_map);
138            follow(re_follow, follow_map);
[5568]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()) {
[5620]150                e->second = makeCC(e->second, e2);
[5568]151            } else {
[5620]152                follow_map.emplace(e1, e2);
[5568]153            }
154        }
[5575]155        follow(rep->getRE(), follow_map);
[5568]156    }
157}
158
[5748]159bool RE_Local::isLocalLanguage(RE * re) {   
160    UCD::UnicodeSet seen;
[5632]161    return isLocalLanguage_helper(re, seen);
[5568]162}
163
[5706]164bool RE_Local::isLocalLanguage_helper(const RE * re, UCD::UnicodeSet & seen) {
[5568]165    assert ("RE object cannot be null!" && re);
[5632]166    if (isa<Any>(re)) {
[5706]167        const bool no_intersect = seen.empty();
[5748]168        seen.insert_range(0x00, 0x10FFFF);
[5632]169        return no_intersect;
170    } else if (const CC * cc = dyn_cast<CC>(re)) {
[5748]171        const bool has_intersect = cc->intersects(seen);
172        seen = seen + *cc;
[5632]173        return !has_intersect;
174    } else if (const Name * n = dyn_cast<Name>(re)) {
[5706]175        return isLocalLanguage_helper(n->getDefinition(), seen);
[5748]176    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
177        for (const RE * item : *seq) {
[5706]178            if (!isLocalLanguage_helper(item, seen)) return false;
[5568]179        }
[5632]180        return true;
[5748]181    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
182        for (RE * item : *alt) {
[5706]183            if (!isLocalLanguage_helper(item, seen)) return false;
[5568]184        }
[5632]185        return true;
[5748]186    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
187        if (rep->getUB() > 1) return false;
188        return isLocalLanguage_helper(rep->getRE(), seen);
[5632]189    } else {
190        // A local language cannot contain Intersects, Differences, Assertions, Start, End.
191        return false;
[5568]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
[5569]219}
Note: See TracBrowser for help on using the repository browser.