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