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

Last change on this file since 6170 was 6170, checked in by cameron, 13 months ago

RE Transformation names and printing

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