1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
|
/*
* Copyright (c) 2015-2017, Intel Corporation
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* * Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* * Neither the name of Intel Corporation nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef GOUGHCOMPILE_INTERNAL_H
#define GOUGHCOMPILE_INTERNAL_H
#include "gough_internal.h"
#include "mcclellancompile.h"
#include "ue2common.h"
#include "util/charreach.h"
#include "util/flat_containers.h"
#include "util/noncopyable.h"
#include "util/order_check.h"
#include <map>
#include <memory>
#include <set>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
namespace ue2 {
struct Grey;
struct GoughSSAVar;
struct GoughSSAVarJoin;
struct GoughVertexProps {
GoughVertexProps() {}
explicit GoughVertexProps(u32 state_in) : state_id(state_in) {}
u32 state_id = ~0U;
std::vector<std::shared_ptr<GoughSSAVarJoin> > vars; /* owns variables */
std::vector<std::pair<ReportID, GoughSSAVar *> > reports; /**< report som,
som variable */
std::vector<std::pair<ReportID, GoughSSAVar *> > reports_eod;
};
struct GoughEdgeProps {
GoughEdgeProps(void) : top(false) {}
bool top;
CharReach reach;
std::vector<std::shared_ptr<GoughSSAVar> > vars; /* owns variables */
};
struct GoughGraphProps {
boost::adjacency_list_traits<boost::vecS, boost::vecS>::vertex_descriptor
initial_vertex; /* for triggered nfas, dead state;
* for others start anchored or start floating
*/
};
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS,
GoughVertexProps, GoughEdgeProps, GoughGraphProps> GoughGraph;
typedef GoughGraph::vertex_descriptor GoughVertex;
typedef GoughGraph::edge_descriptor GoughEdge;
struct gough_edge_id {
gough_edge_id(const GoughGraph &g, const GoughEdge &e)
: src(g[source(e, g)].state_id), dest(g[target(e, g)].state_id),
first_char(g[e].reach.find_first()) {}
bool operator<(const gough_edge_id &b) const {
const gough_edge_id &a = *this;
ORDER_CHECK(src);
ORDER_CHECK(dest);
ORDER_CHECK(first_char);
return false;
}
const u32 src;
const u32 dest;
const u32 first_char; /* ~0U if only top */
};
struct GoughSSAVarWithInputs;
struct GoughSSAVarMin;
struct GoughSSAVarJoin;
struct GoughSSAVar : noncopyable {
GoughSSAVar(void) : seen(false), slot(INVALID_SLOT) {}
virtual ~GoughSSAVar();
const flat_set<GoughSSAVar *> &get_inputs() const {
return inputs;
}
const flat_set<GoughSSAVarWithInputs *> &get_outputs() const {
return outputs;
}
virtual void replace_input(GoughSSAVar *old_v, GoughSSAVar *new_v) = 0;
virtual void generate(std::vector<gough_ins> *out) const = 0;
bool seen; /* for temp use by remove_dead alg */
u32 slot;
void clear_outputs();
/** remove all inputs and outputs of the vertex, call before
* removing vertex */
virtual void clear_all() {
clear_outputs();
}
protected:
flat_set<GoughSSAVar *> inputs;
flat_set<GoughSSAVarWithInputs *> outputs;
friend struct GoughSSAVarWithInputs;
friend struct GoughSSAVarMin;
friend struct GoughSSAVarJoin;
};
struct GoughSSAVarNew : public GoughSSAVar {
explicit GoughSSAVarNew(u32 adjust_in) : adjust(adjust_in) {}
void replace_input(GoughSSAVar *, GoughSSAVar *) override {
assert(0);
}
void generate(std::vector<gough_ins> *out) const override;
const u32 adjust;
};
struct GoughSSAVarWithInputs : public GoughSSAVar {
GoughSSAVarWithInputs(void) {}
void replace_input(GoughSSAVar *old_v, GoughSSAVar *new_v) override = 0;
virtual void clear_inputs() = 0;
void clear_all() override;
protected:
virtual void remove_input_raw(GoughSSAVar *v) = 0;
friend struct GoughSSAVar;
};
struct GoughSSAVarMin : public GoughSSAVarWithInputs {
GoughSSAVarMin(void) {}
void generate(std::vector<gough_ins> *out) const override;
void clear_inputs() override;
void replace_input(GoughSSAVar *old_v, GoughSSAVar *new_v) override;
virtual void add_input(GoughSSAVar *v) {
inputs.insert(v);
v->outputs.insert(this);
}
protected:
void remove_input_raw(GoughSSAVar *v) override;
};
struct GoughSSAVarJoin : public GoughSSAVarWithInputs {
GoughSSAVarJoin(void) {}
/* dummy; all joins at a point must be generated simultaneously */
void generate(std::vector<gough_ins> *out) const override;
GoughSSAVar *get_input(const GoughEdge &prev) const;
void clear_inputs() override;
void replace_input(GoughSSAVar *old_v, GoughSSAVar *new_v) override;
void add_input(GoughSSAVar *v, GoughEdge prev);
const flat_set<GoughEdge> &get_edges_for_input(GoughSSAVar *input) const;
const std::map<GoughSSAVar *, flat_set<GoughEdge>> &get_input_map() const;
protected:
void remove_input_raw(GoughSSAVar *v) override;
private:
std::map<GoughSSAVar *, flat_set<GoughEdge>> input_map;
};
struct gough_accel_state_info {
u32 margin;
bool two_byte;
gough_accel_state_info(u32 margin_in, bool two_byte_in)
: margin(margin_in), two_byte(two_byte_in) {
}
};
u32 assign_slots(GoughGraph &g, const Grey &grey);
void find_allowed_accel_states(const GoughGraph &g,
const std::map<gough_edge_id, std::vector<gough_ins> > &blocks,
std::map<dstate_id_t, gough_accel_state_info> *out);
bool find_normal_self_loop(GoughVertex v, const GoughGraph &g, GoughEdge *out);
} // namespace ue2
// Note: C structure, can't be in namespace ue2
static inline
bool operator==(const gough_ins &a, const gough_ins &b) {
return a.op == b.op && a.dest == b.dest && a.src == b.src;
}
static inline
bool operator<(const gough_ins &a, const gough_ins &b) {
return std::tie(a.op, a.src, a.dest) < std::tie(b.op, b.src, b.dest);
}
#endif
|
