]>
git.ipfire.org Git - thirdparty/gcc.git/blob - gcc/analyzer/constraint-manager.h
1 /* Tracking equivalence classes and constraints at a point on an execution path.
2 Copyright (C) 2019-2020 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_CONSTRAINT_MANAGER_H
22 #define GCC_ANALYZER_CONSTRAINT_MANAGER_H
26 class constraint_manager
;
28 /* Abstract base class for specifying how state should be purged. */
33 virtual ~purge_criteria () {}
34 virtual bool should_purge_p (svalue_id sid
) const = 0;
37 /* An equivalence class within a constraint manager: a set of
38 svalue_ids that are known to all be equal to each other,
39 together with an optional tree constant that they are equal to. */
45 equiv_class (const equiv_class
&other
);
47 hashval_t
hash () const;
48 bool operator== (const equiv_class
&other
);
50 void add (svalue_id sid
, const constraint_manager
&cm
);
51 bool del (svalue_id sid
);
53 tree
get_any_constant () const { return m_constant
; }
55 svalue_id
get_representative () const;
57 void remap_svalue_ids (const svalue_id_map
&map
);
61 void print (pretty_printer
*pp
) const;
63 /* An equivalence class can contain multiple constants (e.g. multiple
64 different zeroes, for different types); these are just for the last
69 // TODO: should this be a set rather than a vec?
70 auto_vec
<svalue_id
> m_vars
;
73 /* The various kinds of constraint. */
82 const char *constraint_op_code (enum constraint_op c_op
);
84 /* An ID for an equiv_class within a constraint_manager. Internally, this
85 is an index into a vector of equiv_class * within the constraint_manager. */
90 static equiv_class_id
null () { return equiv_class_id (-1); }
92 equiv_class_id (unsigned idx
) : m_idx (idx
) {}
93 const equiv_class
&get_obj (const constraint_manager
&cm
) const;
94 equiv_class
&get_obj (constraint_manager
&cm
) const;
96 bool operator== (const equiv_class_id
&other
) const
98 return m_idx
== other
.m_idx
;
100 bool operator!= (const equiv_class_id
&other
) const
102 return m_idx
!= other
.m_idx
;
105 bool null_p () const { return m_idx
== -1; }
107 static equiv_class_id
from_int (int idx
) { return equiv_class_id (idx
); }
108 int as_int () const { return m_idx
; }
110 void print (pretty_printer
*pp
) const;
112 void update_for_removal (equiv_class_id other
)
114 if (m_idx
> other
.m_idx
)
121 /* A relationship between two equivalence classes in a constraint_manager. */
126 constraint (equiv_class_id lhs
, enum constraint_op c_op
, equiv_class_id rhs
)
127 : m_lhs (lhs
), m_op (c_op
), m_rhs (rhs
)
129 gcc_assert (!lhs
.null_p ());
130 gcc_assert (!rhs
.null_p ());
133 void print (pretty_printer
*pp
, const constraint_manager
&cm
) const;
135 hashval_t
hash () const;
136 bool operator== (const constraint
&other
) const;
138 /* Is this an ordering, rather than a "!=". */
139 bool is_ordering_p () const
141 return m_op
!= CONSTRAINT_NE
;
144 equiv_class_id m_lhs
;
145 enum constraint_op m_op
;
146 equiv_class_id m_rhs
;
149 /* An abstract base class for use with constraint_manager::for_each_fact. */
154 virtual ~fact_visitor () {}
155 virtual void on_fact (svalue_id lhs
, enum tree_code
, svalue_id rhs
) = 0;
158 /* A collection of equivalence classes and constraints on them.
160 Given N svalues, this can be thought of as representing a subset of
161 N-dimensional space. When we call add_constraint,
162 we are effectively taking an intersection with that constraint. */
164 class constraint_manager
167 constraint_manager () {}
168 constraint_manager (const constraint_manager
&other
);
169 virtual ~constraint_manager () {}
171 virtual constraint_manager
*clone (region_model
*) const = 0;
172 virtual tree
maybe_get_constant (svalue_id sid
) const = 0;
173 virtual svalue_id
get_sid_for_constant (tree cst
) const = 0;
174 virtual int get_num_svalues () const = 0;
176 constraint_manager
& operator= (const constraint_manager
&other
);
178 hashval_t
hash () const;
179 bool operator== (const constraint_manager
&other
) const;
180 bool operator!= (const constraint_manager
&other
) const
182 return !(*this == other
);
185 void print (pretty_printer
*pp
) const;
186 void dump_to_pp (pretty_printer
*pp
) const;
187 void dump (FILE *fp
) const;
190 const equiv_class
&get_equiv_class_by_index (unsigned idx
) const
192 return *m_equiv_classes
[idx
];
194 equiv_class
&get_equiv_class_by_index (unsigned idx
)
196 return *m_equiv_classes
[idx
];
199 equiv_class
&get_equiv_class (svalue_id sid
)
201 equiv_class_id ec_id
= get_or_add_equiv_class (sid
);
202 return ec_id
.get_obj (*this);
205 bool add_constraint (svalue_id lhs
, enum tree_code op
, svalue_id rhs
);
207 bool add_constraint (equiv_class_id lhs_ec_id
,
209 equiv_class_id rhs_ec_id
);
211 bool get_equiv_class_by_sid (svalue_id sid
, equiv_class_id
*out
) const;
212 equiv_class_id
get_or_add_equiv_class (svalue_id sid
);
213 tristate
eval_condition (equiv_class_id lhs
,
216 tristate
eval_condition (svalue_id lhs
,
220 void purge (const purge_criteria
&p
, purge_stats
*stats
);
222 void remap_svalue_ids (const svalue_id_map
&map
);
224 void canonicalize (unsigned num_svalue_ids
);
226 static void merge (const constraint_manager
&cm_a
,
227 const constraint_manager
&cm_b
,
228 constraint_manager
*out
,
229 const model_merger
&merger
);
231 void for_each_fact (fact_visitor
*) const;
233 void validate () const;
235 auto_delete_vec
<equiv_class
> m_equiv_classes
;
236 auto_vec
<constraint
> m_constraints
;
239 static void clean_merger_input (const constraint_manager
&cm_in
,
240 const one_way_svalue_id_map
&map_sid_to_m
,
241 constraint_manager
*out
);
243 void add_constraint_internal (equiv_class_id lhs_id
,
244 enum constraint_op c_op
,
245 equiv_class_id rhs_id
);
250 #endif /* GCC_ANALYZER_CONSTRAINT_MANAGER_H */