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

Last change on this file was 5812, checked in by nmedfort, 6 months ago

Bug fix for RE local + some clean up of RE local and the RE Compiler

File size: 5.2 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_analysis.h>
11#include <re/re_nullable.h>
12#include <boost/container/flat_map.hpp>
13#include <boost/range/adaptor/reversed.hpp>
14
15using namespace boost::container;
16using namespace llvm;
17
18namespace re {
19
20using FollowMap = flat_map<const CC *, const CC*>;
21
22inline const CC * combine(const CC * a, const CC * b) {
23    if (a && b) {
24        return makeCC(a, b);
25    } else if (b) {
26        return b;
27    }
28    return a;
29}
30
31const CC * first(const RE * re) {
32    if (const 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 (const CC * cc = dyn_cast<CC>(re)) {
39        return cc;
40    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
41        const CC * cc = nullptr;
42        for (auto & si : *seq) {
43            cc = combine(cc, first(si));
44            if (!RE_Nullable::isNullable(si)) {
45                break;
46            }
47        }
48        return cc;
49    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
50        const CC * cc = nullptr;
51        for (auto & ai : *alt) {
52            cc = combine(cc, first(ai));
53        }
54        return cc;
55    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
56        return first(rep->getRE());
57    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
58        if (const CC * lh = first(diff->getLH())) {
59            if (const CC * rh = first(diff->getRH())) {
60                return subtractCC(lh, rh);
61            }
62        }
63    } else if (const Intersect * ix = dyn_cast<Intersect>(re)) {
64        if (const CC * lh = first(ix->getLH())) {
65            if (const CC * rh = first(ix->getRH())) {
66                return intersectCC(lh, rh);
67            }
68        }
69    }
70    return nullptr;
71}
72
73const CC * final(const RE * re) {
74    if (const 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 (const CC * cc = dyn_cast<CC>(re)) {
81        return cc;
82    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
83        const CC * cc = nullptr;
84        for (auto & si : boost::adaptors::reverse(*seq)) {
85            cc = combine(cc, final(si));
86            if (!RE_Nullable::isNullable(si)) {
87                break;
88            }
89        }
90        return cc;
91    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
92        const CC * cc = nullptr;
93        for (auto & ai : *alt) {
94            cc = combine(cc, final(ai));
95        }
96        return cc;
97    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
98        return final(rep->getRE());
99    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
100        if (const CC * lh = final(diff->getLH())) {
101            if (const CC * rh = final(diff->getRH())) {
102                return subtractCC(lh, rh);
103            }
104        }
105    } else if (const Intersect * ix = dyn_cast<Intersect>(re)) {
106        if (const CC * lh = final(ix->getLH())) {
107            if (const CC * rh = final(ix->getRH())) {
108                return intersectCC(lh, rh);
109            }
110        }
111    }
112    return nullptr;
113
114}
115
116void follow(const RE * re, FollowMap & follows) {
117    if (const Name * name = dyn_cast<Name>(re)) {
118        if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
119            return follow(name->getDefinition(), follows);
120        } else {
121            UndefinedNameError(name);
122        }
123    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
124        if (!seq->empty()) {
125            const RE * const re_first = *(seq->begin());
126            const RE * const 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 = follows.find(e1);
131                if (e != follows.end()) {
132                    e->second = makeCC(e->second, e2);
133                } else {
134                    follows.emplace(e1, e2);
135                }
136            }
137            follow(re_first, follows);
138            follow(re_follow, follows);
139        }
140    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
141        for (auto ai = alt->begin(); ai != alt->end(); ++ai) {
142            follow(*ai, follows);
143        }
144    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
145        const auto e1 = final(rep->getRE());
146        auto e2 = first(rep->getRE());
147        if (e1 && e2) {
148            auto e = follows.find(e1);
149            if (e != follows.end()) {
150                e->second = makeCC(e->second, e2);
151            } else {
152                follows.emplace(e1, e2);
153            }
154        }
155        follow(rep->getRE(), follows);
156    }
157}
158
159CC * RE_Local::getFirstUniqueSymbol(RE * const re) {
160    const CC * const re_first = first(re);
161    if (re_first) {
162        FollowMap follows;
163        follow(re, follows);
164        for (const auto & entry : follows) {
165            if (entry.second->intersects(*re_first)) {
166                return nullptr;
167            }
168        }
169    }
170    return const_cast<CC *>(re_first);
171}
172
173}
Note: See TracBrowser for help on using the repository browser.