Line data Source code
1 : /* Typesafe symbolic ranges of values (e.g. "bytes m-n").
2 : Copyright (C) 2019-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-ranges.h"
26 : #include "analyzer/region-model-manager.h"
27 : #include "analyzer/region-model.h"
28 : #include "analyzer/analyzer-selftests.h"
29 :
30 : #if ENABLE_ANALYZER
31 :
32 : namespace ana {
33 :
34 : template<typename ConcreteValueType>
35 : std::unique_ptr<text_art::tree_widget>
36 587 : symbolic::range<ConcreteValueType>::
37 : make_dump_widget (symbolic::node_dump_state &nds,
38 : const char *prefix) const
39 : {
40 : using text_art::tree_widget;
41 587 : std::unique_ptr<tree_widget> widget;
42 587 : if (prefix)
43 576 : widget = tree_widget::from_fmt (nds, nullptr, "%s: symbolic range", prefix);
44 : else
45 11 : widget = tree_widget::from_fmt (nds, nullptr, "symbolic range");
46 1174 : widget->add_child (m_start_offset->make_dump_widget (nds, "start offset"));
47 1174 : widget->add_child (m_size->make_dump_widget (nds, "size"));
48 587 : return widget;
49 : }
50 :
51 : template
52 : std::unique_ptr<text_art::tree_widget>
53 : symbolic::range<integer_with_unit<units::bit>>::
54 : make_dump_widget (symbolic::node_dump_state &nds,
55 : const char *prefix) const;
56 :
57 : template<typename ConcreteValueType>
58 : void
59 14425744 : symbolic::range<ConcreteValueType>::accept_node_visitor (node_visitor &v) const
60 : {
61 14425744 : m_start_offset->accept_node_visitor (v);
62 14425744 : m_size->accept_node_visitor (v);
63 14425744 : }
64 :
65 : template
66 : void
67 : symbolic::range<integer_with_unit<units::bit>>::
68 : accept_node_visitor (node_visitor &v) const;
69 :
70 : template<>
71 : DEBUG_FUNCTION void
72 0 : symbolic_bit_range::dump () const
73 : {
74 0 : symbolic::dump_node_tree_to_stderr<symbolic_bit_range> (*this);
75 0 : }
76 :
77 : template<>
78 : DEBUG_FUNCTION void
79 0 : symbolic_byte_range::dump () const
80 : {
81 0 : symbolic::dump_node_tree_to_stderr<symbolic_byte_range> (*this);
82 0 : }
83 :
84 : template<typename ConcreteValueType>
85 : void
86 0 : symbolic::range<ConcreteValueType>::log (const char *label, logger &log) const
87 : {
88 0 : pretty_printer *pp = log.get_printer ();
89 0 : log.start_log_line ();
90 0 : pp_printf (pp, "%s: ", label);
91 0 : dump_inline_to_pp (pp);
92 0 : log.end_log_line ();
93 0 : }
94 :
95 : template
96 : void
97 : symbolic_bit_range::log (const char *label, logger &log) const;
98 :
99 : template<typename ConcreteValueType>
100 : std::unique_ptr<json::object>
101 12 : symbolic::range<ConcreteValueType>::to_json () const
102 : {
103 12 : auto obj = std::make_unique<json::object> ();
104 12 : obj->set ("start_offset", m_start_offset->to_json ());
105 12 : obj->set ("size", m_size->to_json ());
106 12 : return obj;
107 : }
108 :
109 : template
110 : std::unique_ptr<json::object>
111 : symbolic_bit_range::to_json () const;
112 :
113 : template
114 : std::unique_ptr<json::object>
115 : symbolic_byte_range::to_json () const;
116 :
117 : template<typename ConcreteValueType>
118 : void
119 4 : symbolic::range<ConcreteValueType>::dump_inline_to_pp (pretty_printer *pp) const
120 : {
121 4 : pp_character (pp, '[');
122 4 : if (m_size->is_zero_p ())
123 : {
124 0 : pp_character (pp, ']');
125 0 : return;
126 : }
127 4 : if (m_size->is_one_p ())
128 : {
129 0 : m_start_offset->dump_inline_to_pp (pp, units::role::offset);
130 0 : pp_character (pp, ']');
131 0 : return;
132 : }
133 4 : m_start_offset->dump_inline_to_pp (pp, units::role::offset);
134 4 : pp_string (pp, "..");
135 4 : get_next_offset ().dump_inline_to_pp (pp, units::role::offset);
136 4 : pp_character (pp, ')');
137 : }
138 :
139 : template
140 : void
141 : symbolic_bit_range::dump_inline_to_pp (pretty_printer *pp) const;
142 :
143 : symbolic_bit_range
144 481233 : bits_from_bytes (const symbolic_byte_range &byte_range)
145 : {
146 481233 : return symbolic_bit_range (bits_from_bytes (byte_range.get_start_offset ()),
147 481233 : bits_from_bytes (byte_range.get_size ()));
148 : }
149 :
150 : /* Attempt to determine if THIS range intersects OTHER,
151 : using constraints from MODEL. */
152 :
153 : template<typename ConcreteValueType>
154 : tristate
155 148 : symbolic::range<ConcreteValueType>::
156 : intersects (const symbolic::range<ConcreteValueType> &other,
157 : const region_model &model) const
158 : {
159 : /* If either is empty, then there is no intersection. */
160 148 : if (this->empty_p ())
161 16 : return tristate::TS_FALSE;
162 132 : if (other.empty_p ())
163 12 : return tristate::TS_FALSE;
164 :
165 : /* For brevity, consider THIS to be "range A", and OTHER to be "range B". */
166 :
167 120 : region_model_manager *mgr = model.get_manager ();
168 :
169 120 : auto &first_offset_a = get_start_offset ();
170 120 : auto &first_offset_b = other.get_start_offset ();
171 :
172 120 : if (&first_offset_a == &first_offset_b)
173 44 : return tristate::TS_TRUE;
174 76 : auto &last_offset_a = get_last_offset ();
175 76 : auto &last_offset_b = other.get_last_offset ();
176 :
177 : auto *first_offset_sval_a
178 76 : = mgr->get_svalue_from_scalar<ConcreteValueType> (size_type_node,
179 : first_offset_a);
180 : auto *first_offset_sval_b
181 76 : = mgr->get_svalue_from_scalar<ConcreteValueType> (size_type_node,
182 : first_offset_b);
183 : auto *last_offset_sval_a
184 76 : = mgr->get_svalue_from_scalar<ConcreteValueType> (size_type_node,
185 : last_offset_a);
186 : auto *last_offset_sval_b
187 76 : = mgr->get_svalue_from_scalar<ConcreteValueType> (size_type_node,
188 : last_offset_b);
189 : /* Is B fully before A? */
190 76 : tristate b_fully_before_a = model.eval_condition (last_offset_sval_b,
191 : LT_EXPR,
192 : first_offset_sval_a);
193 : /* Is B fully after A? */
194 76 : tristate b_fully_after_a = model.eval_condition (first_offset_sval_b,
195 : GT_EXPR,
196 : last_offset_sval_a);
197 :
198 76 : if (b_fully_before_a.is_true ()
199 76 : || b_fully_after_a.is_true ())
200 40 : return tristate::TS_FALSE;
201 :
202 36 : if (b_fully_before_a.is_unknown ()
203 36 : || b_fully_after_a.is_unknown ())
204 16 : return tristate::TS_UNKNOWN;
205 :
206 20 : return tristate::TS_TRUE;
207 : }
208 :
209 : template
210 : tristate
211 : symbolic_byte_range::intersects (const symbolic_byte_range &other,
212 : const region_model &model) const;
213 :
214 : bool
215 96 : maybe_bytes_from_bits (const symbolic_bit_range &bit_range,
216 : symbolic_byte_range *out)
217 : {
218 96 : const symbolic_byte_offset *start_byte_offset
219 96 : = maybe_bytes_from_bits (bit_range.get_start_offset ());
220 96 : if (!start_byte_offset)
221 : return false;
222 :
223 96 : const symbolic_byte_size *byte_size
224 96 : = maybe_bytes_from_bits (bit_range.get_size ());
225 96 : if (!byte_size)
226 : return false;
227 :
228 89 : *out = symbolic_byte_range (*start_byte_offset, *byte_size);
229 89 : return true;
230 : }
231 :
232 : #if CHECKING_P
233 :
234 : namespace selftest {
235 :
236 : static void
237 4 : test_concrete ()
238 : {
239 4 : symbolic::node_manager node_mgr;
240 4 : auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
241 4 : auto &byte_mgr = node_mgr.get_scalars ().get_bytes ();
242 :
243 4 : symbolic_bit_range bits_16_to_23
244 8 : (bit_mgr.get_concrete (16_bits),
245 8 : bit_mgr.get_concrete (8_bits));
246 4 : ASSERT_SAME_SYMBOLIC_NODE (bits_16_to_23.get_start_offset (),
247 : bit_mgr.get_concrete (16_bits));
248 4 : ASSERT_SAME_SYMBOLIC_NODE (bits_16_to_23.get_size (),
249 : bit_mgr.get_concrete (8_bits));
250 4 : ASSERT_SAME_SYMBOLIC_NODE (bits_16_to_23.get_last_offset (),
251 : bit_mgr.get_concrete (23_bits));
252 4 : ASSERT_SAME_SYMBOLIC_NODE (bits_16_to_23.get_next_offset (),
253 : bit_mgr.get_concrete (24_bits));
254 4 : bits_16_to_23.to_json ();
255 :
256 8 : ASSERT_EQ
257 : (symbolic_bit_range::from_endpoints (bit_mgr.get_concrete (16_bits),
258 : bit_mgr.get_concrete (24_bits)),
259 : bits_16_to_23);
260 :
261 4 : symbolic_byte_range bytes_16_to_23
262 8 : (byte_mgr.get_concrete (16_bytes),
263 8 : byte_mgr.get_concrete (8_bytes));
264 4 : ASSERT_SAME_SYMBOLIC_NODE (bytes_16_to_23.get_start_offset (),
265 : byte_mgr.get_concrete (16_bytes));
266 4 : ASSERT_SAME_SYMBOLIC_NODE (bytes_16_to_23.get_size (),
267 : byte_mgr.get_concrete (8_bytes));
268 4 : ASSERT_SAME_SYMBOLIC_NODE (bytes_16_to_23.get_last_offset (),
269 : byte_mgr.get_concrete (23_bytes));
270 4 : ASSERT_SAME_SYMBOLIC_NODE (bytes_16_to_23.get_next_offset (),
271 : byte_mgr.get_concrete (24_bytes));
272 4 : bytes_16_to_23.to_json ();
273 :
274 8 : ASSERT_EQ
275 : (symbolic_byte_range::from_endpoints (byte_mgr.get_concrete (16_bytes),
276 : byte_mgr.get_concrete (24_bytes)),
277 : bytes_16_to_23);
278 :
279 4 : }
280 :
281 : static void
282 4 : test_intersects (void)
283 : {
284 4 : symbolic::node_manager node_mgr;
285 4 : auto &byte_mgr = node_mgr.get_scalars ().get_bytes ();
286 4 : region_model m (node_mgr);
287 :
288 : /* Test various concrete ranges. */
289 4 : auto &zero = byte_mgr.get_concrete (0_bytes);
290 4 : auto &one = byte_mgr.get_concrete (1_byte);
291 4 : auto &five = byte_mgr.get_concrete (5_bytes);
292 4 : auto &nine = byte_mgr.get_concrete (9_bytes);
293 4 : auto &ten = byte_mgr.get_concrete (10_bytes);
294 :
295 4 : symbolic_byte_range r0_9 (zero, ten);
296 4 : symbolic_byte_range r0 (zero, one);
297 4 : symbolic_byte_range r5_9 (five, five);
298 4 : symbolic_byte_range r9 (nine, one);
299 4 : symbolic_byte_range r10 (ten, one);
300 4 : symbolic_byte_range r10_19 (ten, ten);
301 :
302 4 : ASSERT_EQ (r0_9.get_start_offset (), zero);
303 4 : ASSERT_EQ (r0_9.get_size (), ten);
304 4 : ASSERT_EQ (r0_9.get_next_offset (), ten);
305 4 : ASSERT_EQ (r0_9.get_last_offset (), nine);
306 :
307 4 : symbolic_byte_range concrete_empty (zero, zero);
308 4 : ASSERT_TRUE (concrete_empty.empty_p ());
309 :
310 4 : ASSERT_EQ (r0_9.intersects (r0, m), tristate::TS_TRUE);
311 4 : ASSERT_EQ (r0.intersects (r0_9, m), tristate::TS_TRUE);
312 4 : ASSERT_EQ (r0_9.intersects (r9, m), tristate::TS_TRUE);
313 4 : ASSERT_EQ (r9.intersects (r0_9, m), tristate::TS_TRUE);
314 4 : ASSERT_EQ (r0_9.intersects (r10, m), tristate::TS_FALSE);
315 4 : ASSERT_EQ (r10.intersects (r0_9, m), tristate::TS_FALSE);
316 4 : ASSERT_EQ (concrete_empty.intersects (r0_9, m), tristate::TS_FALSE);
317 4 : ASSERT_EQ (r0_9.intersects (concrete_empty, m), tristate::TS_FALSE);
318 :
319 4 : ASSERT_EQ (r5_9.intersects (r0, m), tristate::TS_FALSE);
320 4 : ASSERT_EQ (r0.intersects (r5_9, m), tristate::TS_FALSE);
321 4 : ASSERT_EQ (r9.intersects (r5_9, m), tristate::TS_TRUE);
322 4 : ASSERT_EQ (r10.intersects (r5_9, m), tristate::TS_FALSE);
323 :
324 : /* Test various symbolic ranges. */
325 4 : tree x = build_global_decl ("x", size_type_node);
326 4 : const svalue *x_init_sval = m.get_rvalue (x, nullptr);
327 4 : auto &x_init = byte_mgr.get_scalar_from_svalue (*x_init_sval);
328 4 : tree y = build_global_decl ("y", size_type_node);
329 4 : const svalue *y_init_sval = m.get_rvalue (y, nullptr);
330 4 : auto &y_init = byte_mgr.get_scalar_from_svalue (*y_init_sval);
331 :
332 4 : symbolic_byte_range r0_x_minus_1 (zero, x_init);
333 4 : symbolic_byte_range rx (x_init, one);
334 4 : symbolic_byte_range r0_y_minus_1 (zero, y_init);
335 4 : symbolic_byte_range ry (y_init, one);
336 4 : symbolic_byte_range rx_x_plus_y_minus_1 (x_init, y_init);
337 4 : symbolic_byte_range symbolic_empty (x_init, zero);
338 4 : ASSERT_TRUE (symbolic_empty.empty_p ());
339 :
340 4 : ASSERT_SAME_SYMBOLIC_NODE (rx_x_plus_y_minus_1.get_start_offset (), x_init);
341 4 : ASSERT_SAME_SYMBOLIC_NODE (rx_x_plus_y_minus_1.get_size (), y_init);
342 4 : ASSERT_EQ
343 : (rx_x_plus_y_minus_1.get_next_offset ().get_kind (),
344 : symbolic_byte_offset::kind::sum);
345 4 : ASSERT_EQ
346 : (rx_x_plus_y_minus_1.get_last_offset ().get_kind (),
347 : symbolic_byte_offset::kind::sum);
348 :
349 4 : ASSERT_EQ (rx.intersects (ry, m), tristate::TS_UNKNOWN);
350 4 : ASSERT_EQ (rx.intersects (concrete_empty, m), tristate::TS_FALSE);
351 4 : ASSERT_EQ (concrete_empty.intersects (rx, m), tristate::TS_FALSE);
352 4 : ASSERT_EQ (rx.intersects (symbolic_empty, m), tristate::TS_FALSE);
353 4 : ASSERT_EQ (symbolic_empty.intersects (rx, m), tristate::TS_FALSE);
354 4 : ASSERT_EQ (r0_x_minus_1.intersects (r0, m), tristate::TS_TRUE);
355 4 : ASSERT_EQ (r0_x_minus_1.intersects (r0_y_minus_1, m), tristate::TS_TRUE);
356 4 : }
357 :
358 : /* Run all of the selftests within this file. */
359 :
360 : void
361 4 : analyzer_symbolic_ranges_cc_tests ()
362 : {
363 4 : test_concrete ();
364 4 : test_intersects ();
365 4 : }
366 :
367 : } // namespace selftest
368 :
369 : #endif /* CHECKING_P */
370 :
371 : } // namespace ana
372 :
373 : #endif /* #if ENABLE_ANALYZER */
|