Branch data Line data Source code
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 : 10 : dump_args_t (const inner_args_t &inner_args)
51 : 10 : : 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 : 1399128 : const exploded_node *get_inner_node () const { return m_inner_node; }
69 : 180948 : unsigned get_index () const { return m_index; }
70 : :
71 : : protected:
72 : 194645 : base_feasible_node (const exploded_node *inner_node, unsigned index)
73 : 194645 : : 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 : 192279 : feasible_node (const exploded_node *inner_node, unsigned index,
87 : : const feasibility_state &state,
88 : : unsigned path_length)
89 : 192279 : : base_feasible_node (inner_node, index),
90 : 192279 : m_state (state),
91 : 192279 : 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 : 187642 : const feasibility_state &get_state () const { return m_state; }
99 : 1359 : 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 : 661171 : 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 : 2366 : infeasible_node (const exploded_node *inner_node, unsigned index,
123 : : std::unique_ptr<rejected_constraint> rc)
124 : 2366 : : base_feasible_node (inner_node, index),
125 : 2366 : 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 : 122726 : const exploded_edge *get_inner_edge () const { return m_inner_edge; }
145 : :
146 : : protected:
147 : 186877 : base_feasible_edge (base_feasible_node *src, base_feasible_node *dest,
148 : : const exploded_edge *inner_edge)
149 : 186877 : : 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 : 184511 : feasible_edge (feasible_node *src, feasible_node *dest,
162 : : const exploded_edge *inner_edge)
163 : 184511 : : 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 : 2366 : infeasible_edge (feasible_node *src, infeasible_node *dest,
176 : : const exploded_edge *inner_edge)
177 : 2366 : : 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 : 7768 : 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 : 2366 : 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 */
|
