1 | /* A graph for exploring trees of feasible paths through the egraph. |
2 | Copyright (C) 2021-2024 Free Software Foundation, Inc. |
3 | Contributed by David Malcolm <dmalcolm@redhat.com>. |
4 | |
5 | This file is part of GCC. |
6 | |
7 | GCC is free software; you can redistribute it and/or modify it |
8 | under the terms of the GNU General Public License as published by |
9 | the Free Software Foundation; either version 3, or (at your option) |
10 | any later version. |
11 | |
12 | GCC is distributed in the hope that it will be useful, but |
13 | WITHOUT ANY WARRANTY; without even the implied warranty of |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
15 | General Public License for more details. |
16 | |
17 | You should have received a copy of the GNU General Public License |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ |
20 | |
21 | #ifndef GCC_ANALYZER_FEASIBLE_GRAPH_H |
22 | #define GCC_ANALYZER_FEASIBLE_GRAPH_H |
23 | |
24 | #include "analyzer/exploded-graph.h" |
25 | |
26 | namespace ana { |
27 | |
28 | /* Forward decls. */ |
29 | |
30 | class base_feasible_node; |
31 | class feasible_node; |
32 | class infeasible_node; |
33 | class base_feasible_edge; |
34 | class feasible_edge; |
35 | class infeasible_edge; |
36 | class feasible_graph; |
37 | class feasible_cluster; |
38 | |
39 | /* A traits class for feasible_graph. */ |
40 | |
41 | struct fg_traits |
42 | { |
43 | typedef base_feasible_node node_t; |
44 | typedef base_feasible_edge edge_t; |
45 | typedef feasible_graph graph_t; |
46 | struct dump_args_t |
47 | { |
48 | typedef typename eg_traits::dump_args_t inner_args_t; |
49 | |
50 | dump_args_t (const inner_args_t &inner_args) |
51 | : m_inner_args (inner_args) |
52 | { |
53 | } |
54 | |
55 | const inner_args_t &m_inner_args; |
56 | }; |
57 | typedef feasible_cluster cluster_t; |
58 | }; |
59 | |
60 | /* Base class of node within a feasible_graph. |
61 | There can be 0 or more base_feasible_nodes per exploded_node. */ |
62 | |
63 | class base_feasible_node : public dnode<fg_traits> |
64 | { |
65 | public: |
66 | void dump_dot_id (pretty_printer *pp) const; |
67 | |
68 | const exploded_node *get_inner_node () const { return m_inner_node; } |
69 | unsigned get_index () const { return m_index; } |
70 | |
71 | protected: |
72 | base_feasible_node (const exploded_node *inner_node, unsigned index) |
73 | : m_inner_node (inner_node), m_index (index) |
74 | {} |
75 | |
76 | const exploded_node *m_inner_node; |
77 | unsigned m_index; |
78 | }; |
79 | |
80 | /* Subclass of base_feasible_node for a node that is reachable via a |
81 | feasible path, with a particular state. */ |
82 | |
83 | class feasible_node : public base_feasible_node |
84 | { |
85 | public: |
86 | feasible_node (const exploded_node *inner_node, unsigned index, |
87 | const feasibility_state &state, |
88 | unsigned path_length) |
89 | : base_feasible_node (inner_node, index), |
90 | m_state (state), |
91 | m_path_length (path_length) |
92 | { |
93 | } |
94 | |
95 | void dump_dot (graphviz_out *gv, |
96 | const dump_args_t &args) const final override; |
97 | |
98 | const feasibility_state &get_state () const { return m_state; } |
99 | const region_model &get_model () const { return m_state.get_model (); } |
100 | const auto_sbitmap &get_snodes_visited () const |
101 | { |
102 | return m_state.get_snodes_visited (); |
103 | } |
104 | |
105 | unsigned get_path_length () const { return m_path_length; } |
106 | |
107 | bool get_state_at_stmt (const gimple *target_stmt, |
108 | region_model *out) const; |
109 | |
110 | private: |
111 | feasibility_state m_state; |
112 | unsigned m_path_length; |
113 | }; |
114 | |
115 | /* Subclass of base_feasible_node for a node that requires following |
116 | an infeasible edge to reach (and thus terminating this part of the |
117 | exploration). */ |
118 | |
119 | class infeasible_node : public base_feasible_node |
120 | { |
121 | public: |
122 | infeasible_node (const exploded_node *inner_node, unsigned index, |
123 | std::unique_ptr<rejected_constraint> rc) |
124 | : base_feasible_node (inner_node, index), |
125 | m_rc (std::move (rc)) |
126 | { |
127 | } |
128 | |
129 | void dump_dot (graphviz_out *gv, |
130 | const dump_args_t &args) const final override; |
131 | |
132 | private: |
133 | std::unique_ptr<rejected_constraint> m_rc; |
134 | }; |
135 | |
136 | /* Base class of edge within a feasible_graph. */ |
137 | |
138 | class base_feasible_edge : public dedge<fg_traits> |
139 | { |
140 | public: |
141 | void dump_dot (graphviz_out *gv, |
142 | const dump_args_t &args) const final override; |
143 | |
144 | const exploded_edge *get_inner_edge () const { return m_inner_edge; } |
145 | |
146 | protected: |
147 | base_feasible_edge (base_feasible_node *src, base_feasible_node *dest, |
148 | const exploded_edge *inner_edge) |
149 | : dedge<fg_traits> (src, dest), m_inner_edge (inner_edge) |
150 | { |
151 | } |
152 | |
153 | const exploded_edge *m_inner_edge; |
154 | }; |
155 | |
156 | /* Subclass of base_feasible_edge for connecting two feasible_nodes. */ |
157 | |
158 | class feasible_edge : public base_feasible_edge |
159 | { |
160 | public: |
161 | feasible_edge (feasible_node *src, feasible_node *dest, |
162 | const exploded_edge *inner_edge) |
163 | : base_feasible_edge (src, dest, inner_edge) |
164 | { |
165 | } |
166 | }; |
167 | |
168 | /* Subclass of base_feasible_edge for connecting a feasible_node |
169 | to an infeasible_node (and thus terminating this part of the |
170 | exploration). */ |
171 | |
172 | class infeasible_edge : public base_feasible_edge |
173 | { |
174 | public: |
175 | infeasible_edge (feasible_node *src, infeasible_node *dest, |
176 | const exploded_edge *inner_edge) |
177 | : base_feasible_edge (src, dest, inner_edge) |
178 | { |
179 | } |
180 | }; |
181 | |
182 | /* A digraph subclass for exploring trees of feasible paths through |
183 | the egraph. This is actually a tree. |
184 | |
185 | The paths within the graph of feasible_nodes express feasible paths |
186 | through the graph, and it also captures known infeasible edges, |
187 | which is invaluable for debugging. */ |
188 | |
189 | class feasible_graph : public digraph <fg_traits> |
190 | { |
191 | public: |
192 | feasible_graph (); |
193 | |
194 | feasible_node *add_node (const exploded_node *enode, |
195 | const feasibility_state &state, |
196 | unsigned path_length); |
197 | |
198 | void add_feasibility_problem (feasible_node *src_fnode, |
199 | const exploded_edge *eedge, |
200 | std::unique_ptr<rejected_constraint> rc); |
201 | |
202 | std::unique_ptr<exploded_path> make_epath (feasible_node *fnode) const; |
203 | |
204 | void dump_feasible_path (const feasible_node &dst_fnode, |
205 | const char *filename) const; |
206 | |
207 | unsigned get_num_infeasible () const { return m_num_infeasible; } |
208 | |
209 | void log_stats (logger *logger) const; |
210 | |
211 | private: |
212 | void dump_feasible_path (const feasible_node &dst_fnode, |
213 | pretty_printer *pp) const; |
214 | |
215 | unsigned m_num_infeasible; |
216 | }; |
217 | |
218 | class feasible_cluster : public cluster <fg_traits> |
219 | { |
220 | }; |
221 | |
222 | } // namespace ana |
223 | |
224 | #endif /* GCC_ANALYZER_FEASIBLE_GRAPH_H */ |
225 | |