Line data Source code
1 : /* Symbolic offsets and ranges.
2 : Copyright (C) 2023-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 "sbitmap.h"
24 : #include "ordered-hash-map.h"
25 :
26 : #include "analyzer/analyzer-logging.h"
27 : #include "analyzer/supergraph.h"
28 : #include "analyzer/call-string.h"
29 : #include "analyzer/program-point.h"
30 : #include "analyzer/store.h"
31 : #include "analyzer/region-model.h"
32 : #include "analyzer/constraint-manager.h"
33 : #include "analyzer/analyzer-selftests.h"
34 : #include "analyzer/ranges.h"
35 :
36 : #if ENABLE_ANALYZER
37 :
38 : namespace ana {
39 :
40 : /* class symbolic_byte_offset. */
41 :
42 268 : symbolic_byte_offset::symbolic_byte_offset (int i, region_model_manager &mgr)
43 268 : : m_num_bytes_sval (mgr.get_or_create_int_cst (size_type_node, i))
44 : {
45 268 : }
46 :
47 684 : symbolic_byte_offset::symbolic_byte_offset (const svalue *num_bytes_sval)
48 684 : : m_num_bytes_sval (num_bytes_sval)
49 : {
50 684 : }
51 :
52 144 : symbolic_byte_offset::symbolic_byte_offset (region_offset offset,
53 144 : region_model_manager &mgr)
54 : {
55 144 : if (offset.concrete_p ())
56 : {
57 136 : bit_offset_t num_bits = offset.get_bit_offset ();
58 136 : gcc_assert (num_bits % BITS_PER_UNIT == 0);
59 136 : byte_offset_t num_bytes = num_bits / BITS_PER_UNIT;
60 136 : m_num_bytes_sval = mgr.get_or_create_int_cst (size_type_node, num_bytes);
61 : }
62 : else
63 8 : m_num_bytes_sval = offset.get_symbolic_byte_offset ();
64 144 : }
65 :
66 : void
67 0 : symbolic_byte_offset::dump_to_pp (pretty_printer *pp, bool simple) const
68 : {
69 0 : pp_string (pp, "byte ");
70 0 : m_num_bytes_sval->dump_to_pp (pp, simple);
71 0 : }
72 :
73 : void
74 0 : symbolic_byte_offset::dump (bool simple) const
75 : {
76 0 : tree_dump_pretty_printer pp (stderr);
77 0 : dump_to_pp (&pp, simple);
78 0 : pp_newline (&pp);
79 0 : }
80 :
81 : std::unique_ptr<json::value>
82 0 : symbolic_byte_offset::to_json () const
83 : {
84 0 : return m_num_bytes_sval->to_json ();
85 : }
86 :
87 : tree
88 536 : symbolic_byte_offset::maybe_get_constant () const
89 : {
90 536 : return m_num_bytes_sval->maybe_get_constant ();
91 : }
92 :
93 : /* class symbolic_byte_range. */
94 :
95 144 : symbolic_byte_range::symbolic_byte_range (region_offset start,
96 : const svalue *num_bytes,
97 144 : region_model_manager &mgr)
98 144 : : m_start (start, mgr),
99 144 : m_size (num_bytes)
100 : {
101 144 : }
102 :
103 : void
104 0 : symbolic_byte_range::dump_to_pp (pretty_printer *pp,
105 : bool simple,
106 : region_model_manager &mgr) const
107 : {
108 0 : if (empty_p ())
109 : {
110 0 : pp_string (pp, "empty");
111 0 : return;
112 : }
113 :
114 0 : if (tree size_cst = m_size.maybe_get_constant ())
115 0 : if (integer_onep (size_cst))
116 : {
117 0 : pp_string (pp, "byte ");
118 0 : m_start.get_svalue ()->dump_to_pp (pp, simple);
119 0 : return;
120 : }
121 :
122 0 : pp_string (pp, "bytes ");
123 0 : m_start.get_svalue ()->dump_to_pp (pp, simple);
124 0 : pp_string (pp, " to ");
125 0 : get_last_byte_offset (mgr).get_svalue ()->dump_to_pp (pp, simple);
126 : }
127 :
128 : void
129 0 : symbolic_byte_range::dump (bool simple, region_model_manager &mgr) const
130 : {
131 0 : tree_dump_pretty_printer pp (stderr);
132 0 : dump_to_pp (&pp, simple, mgr);
133 0 : pp_newline (&pp);
134 0 : }
135 :
136 : std::unique_ptr<json::value>
137 0 : symbolic_byte_range::to_json () const
138 : {
139 0 : auto obj = std::make_unique<json::object> ();
140 0 : obj->set ("start", m_start.to_json ());
141 0 : obj->set ("size", m_size.to_json ());
142 0 : return obj;
143 0 : }
144 :
145 : bool
146 536 : symbolic_byte_range::empty_p () const
147 : {
148 536 : tree cst = m_size.maybe_get_constant ();
149 536 : if (!cst)
150 : return false;
151 364 : return zerop (cst);
152 : }
153 :
154 : symbolic_byte_offset
155 248 : symbolic_byte_range::get_last_byte_offset (region_model_manager &mgr) const
156 : {
157 248 : gcc_assert (!empty_p ());
158 248 : const symbolic_byte_offset one (1, mgr);
159 248 : return symbolic_byte_offset
160 : (mgr.get_or_create_binop (size_type_node,
161 : MINUS_EXPR,
162 248 : get_next_byte_offset (mgr).get_svalue (),
163 248 : one.get_svalue ()));
164 : }
165 :
166 : symbolic_byte_offset
167 256 : symbolic_byte_range::get_next_byte_offset (region_model_manager &mgr) const
168 : {
169 512 : return symbolic_byte_offset (mgr.get_or_create_binop (size_type_node,
170 : PLUS_EXPR,
171 : m_start.get_svalue (),
172 256 : m_size.get_svalue ()));
173 : }
174 :
175 : /* Attempt to determine if THIS range intersects OTHER,
176 : using constraints from MODEL. */
177 :
178 : tristate
179 148 : symbolic_byte_range::intersection (const symbolic_byte_range &other,
180 : const region_model &model) const
181 : {
182 : /* If either is empty, then there is no intersection. */
183 148 : if (empty_p ())
184 16 : return tristate::TS_FALSE;
185 132 : if (other.empty_p ())
186 12 : return tristate::TS_FALSE;
187 :
188 : /* For brevity, consider THIS to be "range A", and OTHER to be "range B". */
189 :
190 120 : region_model_manager *mgr = model.get_manager ();
191 :
192 120 : const svalue *first_sval_a = m_start.get_svalue ();
193 120 : const svalue *first_sval_b = other.m_start.get_svalue ();
194 120 : const svalue *last_sval_a = get_last_byte_offset (*mgr).get_svalue ();
195 120 : const svalue *last_sval_b = other.get_last_byte_offset (*mgr).get_svalue ();
196 :
197 120 : if (m_size.get_svalue ()->get_kind () == SK_UNKNOWN
198 120 : || other.m_size.get_svalue ()->get_kind () == SK_UNKNOWN)
199 : {
200 16 : if (first_sval_a == first_sval_b)
201 16 : return tristate::TS_TRUE;
202 : else
203 0 : return tristate::TS_UNKNOWN;
204 : }
205 :
206 104 : if (first_sval_a == first_sval_b)
207 28 : return tristate::TS_TRUE;
208 :
209 : /* Is B fully before A? */
210 76 : tristate b_fully_before_a = model.eval_condition (last_sval_b,
211 : LT_EXPR,
212 : first_sval_a);
213 : /* Is B fully after A? */
214 76 : tristate b_fully_after_a = model.eval_condition (first_sval_b,
215 : GT_EXPR,
216 : last_sval_a);
217 :
218 76 : if (b_fully_before_a.is_true ()
219 76 : || b_fully_after_a.is_true ())
220 40 : return tristate::TS_FALSE;
221 :
222 36 : if (b_fully_before_a.is_unknown ()
223 36 : || b_fully_after_a.is_unknown ())
224 16 : return tristate::TS_UNKNOWN;
225 :
226 20 : return tristate::TS_TRUE;
227 : }
228 :
229 : #if CHECKING_P
230 :
231 : namespace selftest {
232 :
233 4 : static void test_intersects (void)
234 : {
235 4 : region_model_manager mgr;
236 4 : region_model m (&mgr);
237 :
238 : /* Test various concrete ranges. */
239 4 : symbolic_byte_offset zero (0, mgr);
240 4 : symbolic_byte_offset one (1, mgr);
241 4 : symbolic_byte_offset five (5, mgr);
242 4 : symbolic_byte_offset nine (9, mgr);
243 4 : symbolic_byte_offset ten (10, mgr);
244 :
245 4 : symbolic_byte_range r0_9 (zero, ten);
246 4 : symbolic_byte_range r0 (zero, one);
247 4 : symbolic_byte_range r5_9 (five, five);
248 4 : symbolic_byte_range r9 (nine, one);
249 4 : symbolic_byte_range r10 (ten, one);
250 4 : symbolic_byte_range r10_19 (ten, ten);
251 :
252 4 : ASSERT_EQ (r0_9.get_start_byte_offset (), zero);
253 4 : ASSERT_EQ (r0_9.get_size_in_bytes (), ten);
254 4 : ASSERT_EQ (r0_9.get_next_byte_offset (mgr), ten);
255 4 : ASSERT_EQ (r0_9.get_last_byte_offset (mgr), nine);
256 :
257 4 : symbolic_byte_range concrete_empty (zero, zero);
258 4 : ASSERT_TRUE (concrete_empty.empty_p ());
259 :
260 4 : ASSERT_EQ (r0_9.intersection (r0, m), tristate::TS_TRUE);
261 4 : ASSERT_EQ (r0.intersection (r0_9, m), tristate::TS_TRUE);
262 4 : ASSERT_EQ (r0_9.intersection (r9, m), tristate::TS_TRUE);
263 4 : ASSERT_EQ (r9.intersection (r0_9, m), tristate::TS_TRUE);
264 4 : ASSERT_EQ (r0_9.intersection (r10, m), tristate::TS_FALSE);
265 4 : ASSERT_EQ (r10.intersection (r0_9, m), tristate::TS_FALSE);
266 4 : ASSERT_EQ (concrete_empty.intersection (r0_9, m), tristate::TS_FALSE);
267 4 : ASSERT_EQ (r0_9.intersection (concrete_empty, m), tristate::TS_FALSE);
268 :
269 4 : ASSERT_EQ (r5_9.intersection (r0, m), tristate::TS_FALSE);
270 4 : ASSERT_EQ (r0.intersection (r5_9, m), tristate::TS_FALSE);
271 4 : ASSERT_EQ (r9.intersection (r5_9, m), tristate::TS_TRUE);
272 4 : ASSERT_EQ (r10.intersection (r5_9, m), tristate::TS_FALSE);
273 :
274 : /* Test various symbolic ranges. */
275 4 : tree x = build_global_decl ("x", size_type_node);
276 4 : const svalue *x_init_sval = m.get_rvalue (x, nullptr);
277 4 : tree y = build_global_decl ("y", size_type_node);
278 4 : const svalue *y_init_sval = m.get_rvalue (y, nullptr);
279 :
280 4 : symbolic_byte_range r0_x_minus_1 (zero, x_init_sval);
281 4 : symbolic_byte_range rx (x_init_sval, one);
282 4 : symbolic_byte_range r0_y_minus_1 (zero, y_init_sval);
283 4 : symbolic_byte_range ry (y_init_sval, one);
284 4 : symbolic_byte_range rx_x_plus_y_minus_1 (x_init_sval, y_init_sval);
285 :
286 4 : symbolic_byte_range symbolic_empty (x_init_sval, zero);
287 4 : ASSERT_TRUE (symbolic_empty.empty_p ());
288 :
289 4 : ASSERT_EQ (rx_x_plus_y_minus_1.get_start_byte_offset (), x_init_sval);
290 4 : ASSERT_EQ (rx_x_plus_y_minus_1.get_size_in_bytes (), y_init_sval);
291 4 : ASSERT_EQ
292 : (rx_x_plus_y_minus_1.get_next_byte_offset (mgr).get_svalue ()->get_kind (),
293 : SK_BINOP);
294 4 : ASSERT_EQ
295 : (rx_x_plus_y_minus_1.get_last_byte_offset (mgr).get_svalue ()->get_kind (),
296 : SK_BINOP);
297 :
298 4 : ASSERT_EQ (rx.intersection (ry, m), tristate::TS_UNKNOWN);
299 4 : ASSERT_EQ (rx.intersection (concrete_empty, m), tristate::TS_FALSE);
300 4 : ASSERT_EQ (concrete_empty.intersection (rx, m), tristate::TS_FALSE);
301 4 : ASSERT_EQ (rx.intersection (symbolic_empty, m), tristate::TS_FALSE);
302 4 : ASSERT_EQ (symbolic_empty.intersection (rx, m), tristate::TS_FALSE);
303 4 : ASSERT_EQ (r0_x_minus_1.intersection (r0, m), tristate::TS_TRUE);
304 : #if 0
305 : ASSERT_EQ (r0_x_minus_1.intersection (rx, m), tristate::TS_FALSE);
306 : /* Fails (with UNKNOWN): b_fully_after_a is UNKNOWN, when it could
307 : be TRUE: last of A is (x - 1), but it's not necessarily true that
308 : X > (x - 1), for the case where x is (unsigned)0. */
309 : #endif
310 4 : ASSERT_EQ (r0_x_minus_1.intersection (r0_y_minus_1, m), tristate::TS_TRUE);
311 : // TODO: etc
312 4 : }
313 :
314 : /* Run all of the selftests within this file. */
315 :
316 : void
317 4 : analyzer_ranges_cc_tests ()
318 : {
319 4 : test_intersects ();
320 4 : }
321 :
322 : } // namespace selftest
323 :
324 : #endif /* CHECKING_P */
325 :
326 : } // namespace ana
327 :
328 : #endif /* #if ENABLE_ANALYZER */
|
