1 /* A graph for exploring trees of feasible paths through the egraph.
2 Copyright (C) 2021-2023 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 rejected_constraint *rc)
124 : base_feasible_node (inner_node, index),
125 m_rc (rc)
126 {
127 }
128 ~infeasible_node () { delete m_rc; }
129
130 void dump_dot (graphviz_out *gv,
131 const dump_args_t &args) const final override;
132
133 private:
134 rejected_constraint *m_rc;
135 };
136
137 /* Base class of edge within a feasible_graph. */
138
139 class base_feasible_edge : public dedge<fg_traits>
140 {
141 public:
142 void dump_dot (graphviz_out *gv,
143 const dump_args_t &args) const final override;
144
145 const exploded_edge *get_inner_edge () const { return m_inner_edge; }
146
147 protected:
148 base_feasible_edge (base_feasible_node *src, base_feasible_node *dest,
149 const exploded_edge *inner_edge)
150 : dedge<fg_traits> (src, dest), m_inner_edge (inner_edge)
151 {
152 }
153
154 const exploded_edge *m_inner_edge;
155 };
156
157 /* Subclass of base_feasible_edge for connecting two feasible_nodes. */
158
159 class feasible_edge : public base_feasible_edge
160 {
161 public:
162 feasible_edge (feasible_node *src, feasible_node *dest,
163 const exploded_edge *inner_edge)
164 : base_feasible_edge (src, dest, inner_edge)
165 {
166 }
167 };
168
169 /* Subclass of base_feasible_edge for connecting a feasible_node
170 to an infeasible_node (and thus terminating this part of the
171 exploration). */
172
173 class infeasible_edge : public base_feasible_edge
174 {
175 public:
176 infeasible_edge (feasible_node *src, infeasible_node *dest,
177 const exploded_edge *inner_edge)
178 : base_feasible_edge (src, dest, inner_edge)
179 {
180 }
181 };
182
183 /* A digraph subclass for exploring trees of feasible paths through
184 the egraph. This is actually a tree.
185
186 The paths within the graph of feasible_nodes express feasible paths
187 through the graph, and it also captures known infeasible edges,
188 which is invaluable for debugging. */
189
190 class feasible_graph : public digraph <fg_traits>
191 {
192 public:
193 feasible_graph ();
194
195 feasible_node *add_node (const exploded_node *enode,
196 const feasibility_state &state,
197 unsigned path_length);
198
199 void add_feasibility_problem (feasible_node *src_fnode,
200 const exploded_edge *eedge,
201 rejected_constraint *rc);
202
203 std::unique_ptr<exploded_path> make_epath (feasible_node *fnode) const;
204
205 void dump_feasible_path (const feasible_node &dst_fnode,
206 const char *filename) const;
207
208 unsigned get_num_infeasible () const { return m_num_infeasible; }
209
210 void log_stats (logger *logger) const;
211
212 private:
213 void dump_feasible_path (const feasible_node &dst_fnode,
214 pretty_printer *pp) const;
215
216 unsigned m_num_infeasible;
217 };
218
219 class feasible_cluster : public cluster <fg_traits>
220 {
221 };
222
223 } // namespace ana
224
225 #endif /* GCC_ANALYZER_FEASIBLE_GRAPH_H */