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

Last change on this file since 5782 was 5646, checked in by nmedfort, 20 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.