GCC Middle and Back End API Reference
feasible-graph.h
Go to the documentation of this file.
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
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it
8under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful, but
13WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
25
26namespace ana {
27
28/* Forward decls. */
29
31 class feasible_node;
32 class infeasible_node;
34 class feasible_edge;
35 class infeasible_edge;
36class feasible_graph;
38
39/* A traits class for feasible_graph. */
40
42{
47 {
49
50 dump_args_t (const inner_args_t &inner_args)
51 : m_inner_args (inner_args)
52 {
53 }
54
56 };
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
63class 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
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
84{
85public:
86 feasible_node (const exploded_node *inner_node, unsigned index,
88 unsigned path_length)
89 : base_feasible_node (inner_node, index),
90 m_state (state),
91 m_path_length (path_length)
92 {
93 }
94
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 (); }
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
110private:
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
120{
121public:
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
130 const dump_args_t &args) const final override;
131
132private:
133 std::unique_ptr<rejected_constraint> m_rc;
134};
135
136/* Base class of edge within a feasible_graph. */
137
138class base_feasible_edge : public dedge<fg_traits>
139{
140 public:
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:
148 const exploded_edge *inner_edge)
149 : dedge<fg_traits> (src, dest), m_inner_edge (inner_edge)
150 {
151 }
152
154};
155
156/* Subclass of base_feasible_edge for connecting two feasible_nodes. */
157
159{
160 public:
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
173{
174 public:
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
189class feasible_graph : public digraph <fg_traits>
190{
191 public:
193
196 unsigned path_length);
197
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
211private:
212 void dump_feasible_path (const feasible_node &dst_fnode,
213 pretty_printer *pp) const;
214
216};
217
218class feasible_cluster : public cluster <fg_traits>
219{
220};
221
222} // namespace ana
223
224#endif /* GCC_ANALYZER_FEASIBLE_GRAPH_H */
Definition feasible-graph.h:139
void dump_dot(graphviz_out *gv, const dump_args_t &args) const final override
base_feasible_edge(base_feasible_node *src, base_feasible_node *dest, const exploded_edge *inner_edge)
Definition feasible-graph.h:147
const exploded_edge * m_inner_edge
Definition feasible-graph.h:153
const exploded_edge * get_inner_edge() const
Definition feasible-graph.h:144
Definition feasible-graph.h:64
const exploded_node * m_inner_node
Definition feasible-graph.h:76
base_feasible_node(const exploded_node *inner_node, unsigned index)
Definition feasible-graph.h:72
void dump_dot_id(pretty_printer *pp) const
unsigned get_index() const
Definition feasible-graph.h:69
const exploded_node * get_inner_node() const
Definition feasible-graph.h:68
unsigned m_index
Definition feasible-graph.h:77
Definition exploded-graph.h:381
Definition exploded-graph.h:203
Definition exploded-graph.h:997
const region_model & get_model() const
Definition exploded-graph.h:1013
const auto_sbitmap & get_snodes_visited() const
Definition exploded-graph.h:1014
Definition feasible-graph.h:219
Definition feasible-graph.h:159
feasible_edge(feasible_node *src, feasible_node *dest, const exploded_edge *inner_edge)
Definition feasible-graph.h:161
Definition feasible-graph.h:190
unsigned get_num_infeasible() const
Definition feasible-graph.h:207
unsigned m_num_infeasible
Definition feasible-graph.h:215
std::unique_ptr< exploded_path > make_epath(feasible_node *fnode) const
void log_stats(logger *logger) const
void dump_feasible_path(const feasible_node &dst_fnode, pretty_printer *pp) const
feasible_node * add_node(const exploded_node *enode, const feasibility_state &state, unsigned path_length)
void dump_feasible_path(const feasible_node &dst_fnode, const char *filename) const
void add_feasibility_problem(feasible_node *src_fnode, const exploded_edge *eedge, std::unique_ptr< rejected_constraint > rc)
Definition feasible-graph.h:84
feasible_node(const exploded_node *inner_node, unsigned index, const feasibility_state &state, unsigned path_length)
Definition feasible-graph.h:86
unsigned get_path_length() const
Definition feasible-graph.h:105
feasibility_state m_state
Definition feasible-graph.h:111
bool get_state_at_stmt(const gimple *target_stmt, region_model *out) const
const feasibility_state & get_state() const
Definition feasible-graph.h:98
const region_model & get_model() const
Definition feasible-graph.h:99
const auto_sbitmap & get_snodes_visited() const
Definition feasible-graph.h:100
void dump_dot(graphviz_out *gv, const dump_args_t &args) const final override
unsigned m_path_length
Definition feasible-graph.h:112
Definition feasible-graph.h:173
infeasible_edge(feasible_node *src, infeasible_node *dest, const exploded_edge *inner_edge)
Definition feasible-graph.h:175
Definition feasible-graph.h:120
std::unique_ptr< rejected_constraint > m_rc
Definition feasible-graph.h:133
infeasible_node(const exploded_node *inner_node, unsigned index, std::unique_ptr< rejected_constraint > rc)
Definition feasible-graph.h:122
void dump_dot(graphviz_out *gv, const dump_args_t &args) const final override
Definition analyzer-logging.h:34
Definition region-model.h:263
Definition sbitmap.h:300
Definition digraph.h:127
Definition digraph.h:59
Definition digraph.h:81
Definition digraph.h:43
Definition graphviz.h:29
Definition pretty-print.h:241
Definition access-diagram.h:30
Definition exploded-graph.h:184
Definition feasible-graph.h:47
dump_args_t(const inner_args_t &inner_args)
Definition feasible-graph.h:50
const inner_args_t & m_inner_args
Definition feasible-graph.h:55
eg_traits::dump_args_t inner_args_t
Definition feasible-graph.h:48
Definition feasible-graph.h:42
feasible_graph graph_t
Definition feasible-graph.h:45
base_feasible_node node_t
Definition feasible-graph.h:43
feasible_cluster cluster_t
Definition feasible-graph.h:57
base_feasible_edge edge_t
Definition feasible-graph.h:44
Definition gimple.h:221
Definition ira-emit.cc:158
Definition genautomata.cc:669