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
47namespace ue2 {
48
49struct Grey;
50struct GoughSSAVar;
51struct GoughSSAVarJoin;
52
53struct 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
65struct 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
73struct 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
80typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS,
81 GoughVertexProps, GoughEdgeProps, GoughGraphProps> GoughGraph;
82
83typedef GoughGraph::vertex_descriptor GoughVertex;
84typedef GoughGraph::edge_descriptor GoughEdge;
85
86struct 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
102struct GoughSSAVarWithInputs;
103struct GoughSSAVarMin;
104struct GoughSSAVarJoin;
105
106struct 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 }
129protected:
130 flat_set<GoughSSAVar *> inputs;
131 flat_set<GoughSSAVarWithInputs *> outputs;
132 friend struct GoughSSAVarWithInputs;
133 friend struct GoughSSAVarMin;
134 friend struct GoughSSAVarJoin;
135};
136
137struct 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
149struct 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;
154protected:
155 virtual void remove_input_raw(GoughSSAVar *v) = 0;
156 friend struct GoughSSAVar;
157};
158
159struct 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
171protected:
172 void remove_input_raw(GoughSSAVar *v) override;
173};
174
175struct 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
190protected:
191 void remove_input_raw(GoughSSAVar *v) override;
192
193private:
194 std::map<GoughSSAVar *, flat_set<GoughEdge>> input_map;
195};
196
197struct 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
206u32 assign_slots(GoughGraph &g, const Grey &grey);
207void 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);
210bool 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
215static inline
216bool 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
220static inline
221bool 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