Branch data Line data Source code
1 : : /* Symbolic offsets and ranges.
2 : : Copyright (C) 2023-2025 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 */
|
