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>.
5 This file is part of GCC.
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)
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.
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/>. */
21 #ifndef GCC_ANALYZER_FEASIBLE_GRAPH_H
22 #define GCC_ANALYZER_FEASIBLE_GRAPH_H
24 #include "analyzer/exploded-graph.h"
30 class base_feasible_node
;
32 class infeasible_node
;
33 class base_feasible_edge
;
35 class infeasible_edge
;
37 class feasible_cluster
;
39 /* A traits class for feasible_graph. */
43 typedef base_feasible_node node_t
;
44 typedef base_feasible_edge edge_t
;
45 typedef feasible_graph graph_t
;
48 typedef typename
eg_traits::dump_args_t inner_args_t
;
50 dump_args_t (const inner_args_t
&inner_args
)
51 : m_inner_args (inner_args
)
55 const inner_args_t
&m_inner_args
;
57 typedef feasible_cluster cluster_t
;
60 /* Base class of node within a feasible_graph.
61 There can be 0 or more base_feasible_nodes per exploded_node. */
63 class base_feasible_node
: public dnode
<fg_traits
>
66 void dump_dot_id (pretty_printer
*pp
) const;
68 const exploded_node
*get_inner_node () const { return m_inner_node
; }
69 unsigned get_index () const { return m_index
; }
72 base_feasible_node (const exploded_node
*inner_node
, unsigned index
)
73 : m_inner_node (inner_node
), m_index (index
)
76 const exploded_node
*m_inner_node
;
80 /* Subclass of base_feasible_node for a node that is reachable via a
81 feasible path, with a particular state. */
83 class feasible_node
: public base_feasible_node
86 feasible_node (const exploded_node
*inner_node
, unsigned index
,
87 const feasibility_state
&state
,
89 : base_feasible_node (inner_node
, index
),
91 m_path_length (path_length
)
95 void dump_dot (graphviz_out
*gv
,
96 const dump_args_t
&args
) const final override
;
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
102 return m_state
.get_snodes_visited ();
105 unsigned get_path_length () const { return m_path_length
; }
107 bool get_state_at_stmt (const gimple
*target_stmt
,
108 region_model
*out
) const;
111 feasibility_state m_state
;
112 unsigned m_path_length
;
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
119 class infeasible_node
: public base_feasible_node
122 infeasible_node (const exploded_node
*inner_node
, unsigned index
,
123 rejected_constraint
*rc
)
124 : base_feasible_node (inner_node
, index
),
128 ~infeasible_node () { delete m_rc
; }
130 void dump_dot (graphviz_out
*gv
,
131 const dump_args_t
&args
) const final override
;
134 rejected_constraint
*m_rc
;
137 /* Base class of edge within a feasible_graph. */
139 class base_feasible_edge
: public dedge
<fg_traits
>
142 void dump_dot (graphviz_out
*gv
,
143 const dump_args_t
&args
) const final override
;
145 const exploded_edge
*get_inner_edge () const { return m_inner_edge
; }
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
)
154 const exploded_edge
*m_inner_edge
;
157 /* Subclass of base_feasible_edge for connecting two feasible_nodes. */
159 class feasible_edge
: public base_feasible_edge
162 feasible_edge (feasible_node
*src
, feasible_node
*dest
,
163 const exploded_edge
*inner_edge
)
164 : base_feasible_edge (src
, dest
, inner_edge
)
169 /* Subclass of base_feasible_edge for connecting a feasible_node
170 to an infeasible_node (and thus terminating this part of the
173 class infeasible_edge
: public base_feasible_edge
176 infeasible_edge (feasible_node
*src
, infeasible_node
*dest
,
177 const exploded_edge
*inner_edge
)
178 : base_feasible_edge (src
, dest
, inner_edge
)
183 /* A digraph subclass for exploring trees of feasible paths through
184 the egraph. This is actually a tree.
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. */
190 class feasible_graph
: public digraph
<fg_traits
>
195 feasible_node
*add_node (const exploded_node
*enode
,
196 const feasibility_state
&state
,
197 unsigned path_length
);
199 void add_feasibility_problem (feasible_node
*src_fnode
,
200 const exploded_edge
*eedge
,
201 rejected_constraint
*rc
);
203 std::unique_ptr
<exploded_path
> make_epath (feasible_node
*fnode
) const;
205 void dump_feasible_path (const feasible_node
&dst_fnode
,
206 const char *filename
) const;
208 unsigned get_num_infeasible () const { return m_num_infeasible
; }
210 void log_stats (logger
*logger
) const;
213 void dump_feasible_path (const feasible_node
&dst_fnode
,
214 pretty_printer
*pp
) const;
216 unsigned m_num_infeasible
;
219 class feasible_cluster
: public cluster
<fg_traits
>
225 #endif /* GCC_ANALYZER_FEASIBLE_GRAPH_H */