Line data Source code
1 : /* A (base_region, symbolic byte offset) pair.
2 : Copyright (C) 2026 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 : #include "analyzer/common.h"
22 :
23 : #include "selftest.h"
24 :
25 : #include "analyzer/symbolic-pointers.h"
26 : #include "analyzer/region-model.h"
27 : #include "analyzer/analyzer-selftests.h"
28 :
29 : #if ENABLE_ANALYZER
30 :
31 : namespace ana {
32 : namespace symbolic {
33 :
34 : // class pointer
35 :
36 : DEBUG_FUNCTION void
37 0 : pointer::dump () const
38 : {
39 0 : symbolic::dump_node_tree_to_stderr<pointer> (*this);
40 0 : }
41 :
42 : std::unique_ptr<text_art::tree_widget>
43 1217 : pointer::make_dump_widget (symbolic::node_dump_state &nds) const
44 : {
45 1217 : using text_art::tree_widget;
46 1217 : std::unique_ptr<tree_widget> widget
47 1217 : (tree_widget::from_fmt (nds, nullptr, "Pointer"));
48 2434 : widget->add_child (m_base_reg.make_dump_widget (nds, "base region"));
49 2434 : widget->add_child (m_byte_offset.make_dump_widget (nds, "byte offset"));
50 1217 : return widget;
51 : }
52 :
53 : void
54 4122910 : pointer::accept_node_visitor (symbolic::node_visitor &v) const
55 : {
56 4122910 : m_base_reg.accept_node_visitor (v);
57 4122910 : m_byte_offset.accept_node_visitor (v);
58 4122910 : }
59 :
60 : std::unique_ptr<json::object>
61 105 : pointer::to_json () const
62 : {
63 105 : auto obj = std::make_unique<json::object> ();
64 105 : obj->set ("base_reg", m_base_reg.to_json ());
65 105 : obj->set ("byte_offset", m_byte_offset.to_json ());
66 105 : return obj;
67 : }
68 :
69 : int
70 11080650 : pointer::cmp (const pointer &other) const
71 : {
72 11080650 : if (int c = symbolic::node::cmp (m_base_reg, other.m_base_reg))
73 : return c;
74 6203631 : return symbolic::node::cmp (m_byte_offset, other.m_byte_offset);
75 : }
76 :
77 : /* A symbolic::pointer is a non-NULL pointer, except in certain
78 : special cases (see the comment for region::non_null_p). */
79 :
80 : bool
81 12177 : pointer::non_null_p () const
82 : {
83 12177 : if (!zero_offset_p ())
84 : return true;
85 9141 : return m_base_reg.non_null_p ();
86 : }
87 :
88 : /* Compare byte offsets OFFSET_A and OFFSET_B. */
89 :
90 : static tristate
91 1175 : eval_byte_offset_comparison (const pointer::symbolic_byte_offset &offset_a,
92 : enum tree_code op,
93 : const pointer::symbolic_byte_offset &offset_b,
94 : const region_model &model)
95 : {
96 219 : return symbolic_byte_offset::get_partial_ordering (offset_a, op, offset_b, &model);
97 : }
98 :
99 : /* Evaluate the condition LHS OP RHS for comparing symbolic pointers.
100 :
101 : See if they point to the same base region, and if we know about
102 : the offsets within their regions.
103 :
104 : Use MODEL for aliasing information and any knowledge from
105 : constraint_manager about ordering of pointers. */
106 :
107 : tristate
108 956 : pointer::eval_condition (const pointer &lhs,
109 : enum tree_code op,
110 : const pointer &rhs,
111 : const region_model &model)
112 : {
113 : /* Try to determine if they're the same base region. */
114 956 : const tristate same_base_region
115 956 : = model.get_store ()->eval_alias (&lhs.get_base_region (),
116 956 : &rhs.get_base_region (),
117 : model);
118 :
119 : /* Try to determine if they're the same offset relative to their
120 : base region. */
121 956 : const tristate same_byte_offset
122 956 : = eval_byte_offset_comparison (lhs.get_byte_offset (),
123 : EQ_EXPR,
124 : rhs.get_byte_offset (),
125 : model);
126 :
127 : /* With that, we might know if they're equal/non-equal. */
128 956 : const tristate equality = same_base_region.and_(same_byte_offset);
129 :
130 956 : switch (op)
131 : {
132 0 : default:
133 0 : gcc_unreachable ();
134 :
135 292 : case EQ_EXPR:
136 292 : return equality;
137 :
138 277 : case NE_EXPR:
139 277 : return equality.not_ ();
140 :
141 187 : case GE_EXPR:
142 187 : case LE_EXPR:
143 187 : if (equality.is_true ())
144 24 : return tristate (true);
145 163 : else if (same_base_region.is_true ())
146 103 : return eval_byte_offset_comparison (lhs.get_byte_offset (),
147 : op,
148 : rhs.get_byte_offset (),
149 103 : model);
150 : else
151 60 : return tristate::unknown ();
152 :
153 200 : case GT_EXPR:
154 200 : case LT_EXPR:
155 200 : if (equality.is_true ())
156 24 : return tristate (false);
157 176 : else if (same_base_region.is_true ())
158 116 : return eval_byte_offset_comparison (lhs.get_byte_offset (),
159 : op,
160 : rhs.get_byte_offset (),
161 116 : model);
162 : else
163 60 : return tristate::unknown ();
164 : }
165 : }
166 :
167 : } // namespace ana::symbolic
168 :
169 : #if CHECKING_P
170 :
171 : namespace selftest {
172 :
173 : static void
174 4 : test_eval_condition ()
175 : {
176 4 : symbolic::node_manager node_mgr;
177 4 : auto &rmm = node_mgr.get_svalue_manager ();
178 4 : region_model model (node_mgr);
179 :
180 4 : coord_test ct;
181 :
182 4 : tree c1 = build_global_decl ("c1", ct.m_coord_type);
183 4 : tree c2 = build_global_decl ("c2", ct.m_coord_type);
184 :
185 4 : tree c1_x = build3 (COMPONENT_REF, TREE_TYPE (ct.m_x_field),
186 : c1, ct.m_x_field, NULL_TREE);
187 4 : tree c1_y = build3 (COMPONENT_REF, TREE_TYPE (ct.m_y_field),
188 : c1, ct.m_y_field, NULL_TREE);
189 :
190 4 : const region *c1_reg = model.get_lvalue (c1, nullptr);
191 4 : const region *c1_x_reg = model.get_lvalue (c1_x, nullptr);
192 4 : const region *c1_y_reg = model.get_lvalue (c1_y, nullptr);
193 :
194 4 : const region *c2_reg = model.get_lvalue (c2, nullptr);
195 :
196 4 : auto ptr_to_c1 = c1_reg->get_pointer (rmm);
197 4 : auto ptr_to_c1_x = c1_x_reg->get_pointer (rmm);
198 4 : auto ptr_to_c1_y = c1_y_reg->get_pointer (rmm);
199 :
200 4 : auto ptr_to_c2 = c2_reg->get_pointer (rmm);
201 :
202 : // Self-comparison of pointer with concrete offset:
203 4 : {
204 4 : ASSERT_EQ (symbolic::pointer::eval_condition (ptr_to_c1,
205 : EQ_EXPR,
206 : ptr_to_c1,
207 : model),
208 : tristate (true));
209 4 : ASSERT_EQ (symbolic::pointer::eval_condition (ptr_to_c1,
210 : NE_EXPR,
211 : ptr_to_c1,
212 : model),
213 : tristate (false));
214 4 : ASSERT_EQ (symbolic::pointer::eval_condition (ptr_to_c1,
215 : GE_EXPR,
216 : ptr_to_c1,
217 : model),
218 : tristate (true));
219 4 : ASSERT_EQ (symbolic::pointer::eval_condition (ptr_to_c1,
220 : LE_EXPR,
221 : ptr_to_c1,
222 : model),
223 : tristate (true));
224 4 : ASSERT_EQ (symbolic::pointer::eval_condition (ptr_to_c1,
225 : GT_EXPR,
226 : ptr_to_c1,
227 : model),
228 : tristate (false));
229 4 : ASSERT_EQ (symbolic::pointer::eval_condition (ptr_to_c1,
230 : LT_EXPR,
231 : ptr_to_c1,
232 : model),
233 : tristate (false));
234 : }
235 :
236 : // Pointer to struct should equal pointer to initial field of that struct:
237 8 : ASSERT_EQ (ptr_to_c1, ptr_to_c1_x);
238 :
239 : /* Comparison of pointers to different fields in the same struct
240 : (same base region, different concrete offset). */
241 4 : {
242 4 : ASSERT_EQ (symbolic::pointer::eval_condition (ptr_to_c1_x,
243 : EQ_EXPR,
244 : ptr_to_c1_y,
245 : model),
246 : tristate (false));
247 4 : ASSERT_EQ (symbolic::pointer::eval_condition (ptr_to_c1_x,
248 : NE_EXPR,
249 : ptr_to_c1_y,
250 : model),
251 : tristate (true));
252 4 : ASSERT_EQ (symbolic::pointer::eval_condition (ptr_to_c1_x,
253 : GE_EXPR,
254 : ptr_to_c1_y,
255 : model),
256 : tristate (false));
257 4 : ASSERT_EQ (symbolic::pointer::eval_condition (ptr_to_c1_x,
258 : LE_EXPR,
259 : ptr_to_c1_y,
260 : model),
261 : tristate (true));
262 4 : ASSERT_EQ (symbolic::pointer::eval_condition (ptr_to_c1_x,
263 : GT_EXPR,
264 : ptr_to_c1_y,
265 : model),
266 : tristate (false));
267 4 : ASSERT_EQ (symbolic::pointer::eval_condition (ptr_to_c1_x,
268 : LT_EXPR,
269 : ptr_to_c1_y,
270 : model),
271 : tristate (true));
272 : }
273 :
274 : /* Different base regions where we know nothing, but know
275 : they are concrete base regions. */
276 4 : {
277 4 : ASSERT_EQ (symbolic::pointer::eval_condition (ptr_to_c1,
278 : EQ_EXPR,
279 : ptr_to_c2,
280 : model),
281 : tristate (false));
282 4 : ASSERT_EQ (symbolic::pointer::eval_condition (ptr_to_c1,
283 : NE_EXPR,
284 : ptr_to_c2,
285 : model),
286 : tristate (true));
287 4 : ASSERT_EQ (symbolic::pointer::eval_condition (ptr_to_c1,
288 : GE_EXPR,
289 : ptr_to_c2,
290 : model),
291 : tristate::unknown ());
292 4 : ASSERT_EQ (symbolic::pointer::eval_condition (ptr_to_c1,
293 : LE_EXPR,
294 : ptr_to_c2,
295 : model),
296 : tristate::unknown ());
297 4 : ASSERT_EQ (symbolic::pointer::eval_condition (ptr_to_c1,
298 : GT_EXPR,
299 : ptr_to_c2,
300 : model),
301 : tristate::unknown ());
302 4 : ASSERT_EQ (symbolic::pointer::eval_condition (ptr_to_c1,
303 : LT_EXPR,
304 : ptr_to_c2,
305 : model),
306 : tristate::unknown ());
307 : }
308 4 : }
309 :
310 : /* Run all of the selftests within this file. */
311 :
312 : void
313 4 : analyzer_symbolic_pointers_cc_tests ()
314 : {
315 4 : test_eval_condition ();
316 4 : }
317 :
318 : } // namespace selftest
319 :
320 : #endif /* CHECKING_P */
321 :
322 : } // namespace ana
323 :
324 : #endif /* #if ENABLE_ANALYZER */
|