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

Last change on this file since 6104 was 5812, checked in by nmedfort, 22 months ago

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

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