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