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

Last change on this file was 5646, checked in by nmedfort, 2 months ago

Minor clean up. Bug fix for object cache when the same cached kernel is used twice in a single run. Improvement to RE Minimizer.

File size: 4.5 KB
Line 
1#include "re_star_normal.h"
2#include <re/re_name.h>
3#include <re/re_any.h>
4#include <re/re_start.h>
5#include <re/re_end.h>
6#include <re/re_alt.h>
7#include <re/re_cc.h>
8#include <re/re_seq.h>
9#include <re/re_rep.h>
10#include <re/re_diff.h>
11#include <re/re_intersect.h>
12#include <re/re_assertion.h>
13#include <re/re_analysis.h>
14
15using namespace llvm;
16
17namespace re {
18
19RE * RE_Star_Normal::star_normal(RE * re) {
20
21    if (Alt * alt = dyn_cast<Alt>(re)) {
22        std::vector<RE *> list;
23        list.reserve(alt->size());
24        for (RE * re : *alt) {
25            list.push_back(star_normal(re));
26        }
27        re = makeAlt(list.begin(), list.end());
28    } else if (Seq * seq = dyn_cast<Seq>(re)) {
29        std::vector<RE *> list;
30        list.reserve(seq->size());
31        for (RE * re : *seq) {
32            list.push_back(star_normal(re));
33        }
34        re = makeSeq(list.begin(), list.end());
35    } else if (Assertion * a = dyn_cast<Assertion>(re)) {
36        re = makeAssertion(star_normal(a->getAsserted()), a->getKind(), a->getSense());
37    } else if (Rep * rep = dyn_cast<Rep>(re)) {
38         if (rep->getLB() == 0 && rep->getUB() == Rep::UNBOUNDED_REP) {
39            RE * expr = helper(rep->getRE());
40            re = makeRep(expr, 0, rep->getUB());
41        } else {
42            RE * expr = star_normal(rep->getRE());
43            re = makeRep(expr, rep->getLB(), rep->getUB());
44        }
45    } else if (Diff * diff = dyn_cast<Diff>(re)) {
46        re = makeDiff(star_normal(diff->getLH()), star_normal(diff->getRH()));
47    } else if (Intersect * e = dyn_cast<Intersect>(re)) {
48        re = makeIntersect(star_normal(e->getLH()), star_normal(e->getRH()));
49    } else if (Name * name = dyn_cast<Name>(re)) {
50        if (name->getDefinition()) {
51            name->setDefinition(star_normal(name->getDefinition()));
52        }
53    }
54    return re;
55}
56
57RE * RE_Star_Normal::helper(RE * re) {
58    if (Alt * alt = dyn_cast<Alt>(re)) {
59        std::vector<RE *> list;
60        list.reserve(alt->size());
61        for (RE * re : *alt) {
62            list.push_back(helper(re));
63        }
64        re = makeAlt(list.begin(), list.end());
65    } else if (Seq * seq = dyn_cast<Seq>(re)) {
66        RE * const re_first = *(seq->begin());
67        RE * const re_follow = makeSeq(seq->begin() + 1, seq->end());
68        const auto isFirstNullable = isNullable(re_first);
69        const auto isFollowNullable = isNullable(re_follow);
70        if (LLVM_LIKELY(!isFirstNullable && !isFollowNullable)) {
71            re = makeSeq({star_normal(re_first), star_normal(re_follow)});
72        } else if (!isFirstNullable && isFollowNullable) {
73            re = makeSeq({helper(re_first), star_normal(re_follow)});
74        } else if (isFirstNullable && !isFollowNullable) {
75            re = makeSeq({star_normal(re_first), helper(re_follow)});
76        } else {
77            re = makeAlt({helper(re_first), helper(re_follow)});
78        }
79    } else if (Assertion * a = dyn_cast<Assertion>(re)) {
80        re = makeAssertion(helper(a->getAsserted()), a->getKind(), a->getSense());
81    } else if (Rep * rep = dyn_cast<Rep>(re)) {
82        RE * const expr = helper(rep->getRE());
83        if (rep->getLB() == 0 && rep->getUB() == Rep::UNBOUNDED_REP) {
84            re = expr;
85        } else {
86            re = makeRep(expr, rep->getLB(), rep->getUB());
87        }
88    } else if (Diff * diff = dyn_cast<Diff>(re)) {
89        re = makeDiff(helper(diff->getLH()), helper(diff->getRH()));
90    } else if (Intersect * e = dyn_cast<Intersect>(re)) {
91        re = makeIntersect(helper(e->getLH()), helper(e->getRH()));
92    } else if (Name * name = dyn_cast<Name>(re)) {
93        if (name->getDefinition()) {
94            name->setDefinition(helper(name->getDefinition()));
95        }
96    }
97    return re;
98}
99
100bool RE_Star_Normal::isNullable(const RE * re) {
101    if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
102        for (const RE * re : *re_seq) {
103            if (!isNullable(re)) {
104                return false;
105            }
106        }
107        return true;
108    } else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
109        for (const RE * re : *re_alt) {
110            if (isNullable(re)) {
111                return true;
112            }
113        }
114    } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
115        return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
116    } else if (const Diff * diff = dyn_cast<const Diff>(re)) {
117        return isNullable(diff->getLH()) && !isNullable(diff->getRH());
118    } else if (const Intersect * e = dyn_cast<const Intersect>(re)) {
119        return isNullable(e->getLH()) && isNullable(e->getRH());
120    } 
121    return false;
122}
123
124
125}
Note: See TracBrowser for help on using the repository browser.