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

Last change on this file was 5817, checked in by cameron, 6 months ago

Toolchain restructuring; creating a total order for memoizer lessThan

File size: 5.1 KB
Line 
1#include "re_memoizer.hpp"
2#include <re/re_alt.h>
3#include <re/re_cc.h>
4#include <re/re_seq.h>
5#include <re/re_rep.h>
6#include <re/re_group.h>
7#include <re/re_range.h>
8#include <re/re_diff.h>
9#include <re/re_intersect.h>
10#include <re/re_assertion.h>
11#include <llvm/Support/ErrorHandling.h>
12
13using llvm::cast;
14
15namespace re {
16
17static bool compare(const RE * const lh, const RE * const rh);
18
19static bool lessThan(const Vector * const lh, const Vector * const rh) {
20    assert (lh->getClassTypeId() == rh->getClassTypeId());
21    assert (lh->getClassTypeId() == RE::ClassTypeId::Alt || lh->getClassTypeId() == RE::ClassTypeId::Seq);
22    if (LLVM_LIKELY(lh->size() != rh->size())) {
23        return lh->size() < rh->size();
24    }
25    for (auto i = lh->begin(), j = rh->begin(); i != lh->end(); ++i, ++j) {
26        assert (*i && *j);
27        if (compare(*i, *j)) {
28            return true;
29        } else if (compare(*j, *i)) {
30            return false;
31        }
32    }
33    return false;
34}
35
36inline bool lessThan(const Name * const lh, const Name * const rh) {
37    if (lh->getType() != rh->getType()) {
38        return lh->getType() < rh->getType();
39    } else if (lh->hasNamespace() != rh->hasNamespace()) {
40        return lh->hasNamespace();
41    } else if (lh->hasNamespace() && (lh->getNamespace() != rh->getNamespace())) {
42        return lh->getNamespace() < rh->getNamespace();
43    } else if (lh->getName() != rh->getName()) {
44        return lh->getName() < rh->getName();
45    } else if (lh->getDefinition() == nullptr) {
46        return rh->getDefinition() != nullptr;
47    } else if (rh->getDefinition() == nullptr) {
48        return false;
49    } else {
50        return compare(lh->getDefinition(), rh->getDefinition());
51    }
52}
53
54inline bool lessThan(const Assertion * const lh, const Assertion * const rh) {
55    if (lh->getKind() != rh->getKind()) {
56        return lh->getKind() < rh->getKind();
57    }
58    if (lh->getSense() != rh->getSense()) {
59        return lh->getSense() < rh->getSense();
60    }
61    return compare(lh->getAsserted(), rh->getAsserted());
62}
63   
64inline bool lessThan(const Rep * const lh, const Rep * const rh) {
65    if (lh->getLB() != rh->getLB()) {
66        return lh->getLB() < rh->getLB();
67    }
68    if (lh->getUB() != rh->getUB()) {
69        return lh->getUB() < rh->getUB();
70    }
71    return compare(lh->getRE(), rh->getRE());
72}
73
74inline bool lessThan(const Diff * const lh, const Diff * const rh) {
75    if (compare(lh->getLH(), rh->getLH())) {
76        return true;
77    } else if (compare(rh->getLH(), lh->getLH())) {
78        return false;
79    } else if (compare(lh->getRH(), rh->getRH())) {
80        return true;
81    } else {
82        return !compare(rh->getRH(), lh->getRH());
83    }
84}
85
86inline bool lessThan(const Range * const lh, const Range * const rh) {
87    if (compare(lh->getLo(), rh->getLo())) {
88        return true;
89    } else if (compare(rh->getLo(), lh->getLo())) {
90        return false;
91    } else if (compare(lh->getHi(), rh->getHi())) {
92        return true;
93    } else {
94        return !compare(rh->getHi(), lh->getHi());
95    }
96}
97
98static bool lessThan(const Intersect * const lh, const Intersect * const rh) {
99    if (compare(lh->getLH(), rh->getLH())) {
100        return true;
101    } else if (compare(rh->getLH(), lh->getLH())) {
102        return false;
103    } else if (compare(lh->getRH(), rh->getRH())) {
104        return true;
105    } else {
106        return !compare(rh->getRH(), lh->getRH());
107    }
108}
109
110inline bool lessThan(const Group * const lh, const Group * const rh) {
111    if (lh->getMode() != rh->getMode()) {
112        return lh->getMode() < rh->getMode();
113    }
114    if (lh->getSense() != rh->getSense()) {
115        return lh->getSense() < rh->getSense();
116    }
117    return compare(lh->getRE(), rh->getRE());
118}
119
120inline bool compare(const RE * const lh, const RE * const rh) {
121    using Type = RE::ClassTypeId;
122    assert (lh && rh);
123    const auto typeL = lh->getClassTypeId();
124    const auto typeR = rh->getClassTypeId();
125    if (LLVM_LIKELY(typeL != typeR)) {
126        return typeL < typeR;
127    }
128    switch (typeL) {
129        case Type::Alt:
130        case Type::Seq:
131            return lessThan(cast<Vector>(lh), cast<Vector>(rh));
132        case Type::Any: case Type::End: case Type::Start:
133            return false;
134        case Type::Assertion:
135            return lessThan(cast<Assertion>(lh), cast<Assertion>(rh));
136        case Type::CC:
137            return *cast<CC>(lh) < *cast<CC>(rh);
138        case Type::Name:
139            return lessThan(cast<Name>(lh), cast<Name>(rh));
140        case Type::Group:
141            return lessThan(cast<Group>(lh), cast<Group>(rh));
142        case Type::Range:
143            return lessThan(cast<Range>(lh), cast<Range>(rh));
144        case Type::Diff:
145            return lessThan(cast<Diff>(lh), cast<Diff>(rh));
146        case Type::Intersect:
147            return lessThan(cast<Intersect>(lh), cast<Intersect>(rh));
148        case Type::Rep:
149            return lessThan(cast<Rep>(lh), cast<Rep>(rh));
150        default:
151            llvm_unreachable("RE object of unknown type given to Memoizer");
152            return false;
153    }
154}
155
156bool MemoizerComparator::operator()(const RE * const lh, const RE * const rh) const {
157    return compare(lh, rh);
158}
159
160}
Note: See TracBrowser for help on using the repository browser.