1/* Symbolic offsets and ranges.
2 Copyright (C) 2023-2024 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it
8under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful, but
13WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
59namespace ana {
60
61/* class symbolic_byte_offset. */
62
63symbolic_byte_offset::symbolic_byte_offset (int i, region_model_manager &mgr)
64: m_num_bytes_sval (mgr.get_or_create_int_cst (size_type_node, cst: i))
65{
66}
67
68symbolic_byte_offset::symbolic_byte_offset (const svalue *num_bytes_sval)
69: m_num_bytes_sval (num_bytes_sval)
70{
71}
72
73symbolic_byte_offset::symbolic_byte_offset (region_offset offset,
74 region_model_manager &mgr)
75{
76 if (offset.concrete_p ())
77 {
78 bit_offset_t num_bits = offset.get_bit_offset ();
79 gcc_assert (num_bits % BITS_PER_UNIT == 0);
80 byte_offset_t num_bytes = num_bits / BITS_PER_UNIT;
81 m_num_bytes_sval = mgr.get_or_create_int_cst (size_type_node, cst: num_bytes);
82 }
83 else
84 m_num_bytes_sval = offset.get_symbolic_byte_offset ();
85}
86
87void
88symbolic_byte_offset::dump_to_pp (pretty_printer *pp, bool simple) const
89{
90 pp_string (pp, "byte ");
91 m_num_bytes_sval->dump_to_pp (pp, simple);
92}
93
94void
95symbolic_byte_offset::dump (bool simple) const
96{
97 pretty_printer pp;
98 pp_format_decoder (&pp) = default_tree_printer;
99 pp_show_color (&pp) = pp_show_color (global_dc->printer);
100 pp.buffer->stream = stderr;
101 dump_to_pp (pp: &pp, simple);
102 pp_newline (&pp);
103 pp_flush (&pp);
104}
105
106json::value *
107symbolic_byte_offset::to_json () const
108{
109 return m_num_bytes_sval->to_json ();
110}
111
112tree
113symbolic_byte_offset::maybe_get_constant () const
114{
115 return m_num_bytes_sval->maybe_get_constant ();
116}
117
118/* class symbolic_byte_range. */
119
120symbolic_byte_range::symbolic_byte_range (region_offset start,
121 const svalue *num_bytes,
122 region_model_manager &mgr)
123: m_start (start, mgr),
124 m_size (num_bytes)
125{
126}
127
128void
129symbolic_byte_range::dump_to_pp (pretty_printer *pp,
130 bool simple,
131 region_model_manager &mgr) const
132{
133 if (empty_p ())
134 {
135 pp_string (pp, "empty");
136 return;
137 }
138
139 if (tree size_cst = m_size.maybe_get_constant ())
140 if (integer_onep (size_cst))
141 {
142 pp_string (pp, "byte ");
143 m_start.get_svalue ()->dump_to_pp (pp, simple);
144 return;
145 }
146
147 pp_string (pp, "bytes ");
148 m_start.get_svalue ()->dump_to_pp (pp, simple);
149 pp_string (pp, " to ");
150 get_last_byte_offset (mgr).get_svalue ()->dump_to_pp (pp, simple);
151}
152
153void
154symbolic_byte_range::dump (bool simple, region_model_manager &mgr) const
155{
156 pretty_printer pp;
157 pp_format_decoder (&pp) = default_tree_printer;
158 pp_show_color (&pp) = pp_show_color (global_dc->printer);
159 pp.buffer->stream = stderr;
160 dump_to_pp (pp: &pp, simple, mgr);
161 pp_newline (&pp);
162 pp_flush (&pp);
163}
164
165json::value *
166symbolic_byte_range::to_json () const
167{
168 json::object *obj = new json::object ();
169 obj->set (key: "start", v: m_start.to_json ());
170 obj->set (key: "size", v: m_size.to_json ());
171 return obj;
172}
173
174bool
175symbolic_byte_range::empty_p () const
176{
177 tree cst = m_size.maybe_get_constant ();
178 if (!cst)
179 return false;
180 return zerop (cst);
181}
182
183symbolic_byte_offset
184symbolic_byte_range::get_last_byte_offset (region_model_manager &mgr) const
185{
186 gcc_assert (!empty_p ());
187 const symbolic_byte_offset one (1, mgr);
188 return symbolic_byte_offset
189 (mgr.get_or_create_binop (size_type_node,
190 op: MINUS_EXPR,
191 arg0: get_next_byte_offset (mgr).get_svalue (),
192 arg1: one.get_svalue ()));
193}
194
195symbolic_byte_offset
196symbolic_byte_range::get_next_byte_offset (region_model_manager &mgr) const
197{
198 return symbolic_byte_offset (mgr.get_or_create_binop (size_type_node,
199 op: PLUS_EXPR,
200 arg0: m_start.get_svalue (),
201 arg1: m_size.get_svalue ()));
202}
203
204/* Attempt to determine if THIS range intersects OTHER,
205 using constraints from MODEL. */
206
207tristate
208symbolic_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 if (empty_p ())
213 return tristate::TS_FALSE;
214 if (other.empty_p ())
215 return tristate::TS_FALSE;
216
217 /* For brevity, consider THIS to be "range A", and OTHER to be "range B". */
218
219 region_model_manager *mgr = model.get_manager ();
220
221 const svalue *first_sval_a = m_start.get_svalue ();
222 const svalue *first_sval_b = other.m_start.get_svalue ();
223 const svalue *last_sval_a = get_last_byte_offset (mgr&: *mgr).get_svalue ();
224 const svalue *last_sval_b = other.get_last_byte_offset (mgr&: *mgr).get_svalue ();
225
226 if (m_size.get_svalue ()->get_kind () == SK_UNKNOWN
227 || other.m_size.get_svalue ()->get_kind () == SK_UNKNOWN)
228 {
229 if (first_sval_a == first_sval_b)
230 return tristate::TS_TRUE;
231 else
232 return tristate::TS_UNKNOWN;
233 }
234
235 if (first_sval_a == first_sval_b)
236 return tristate::TS_TRUE;
237
238 /* Is B fully before A? */
239 tristate b_fully_before_a = model.eval_condition (lhs: last_sval_b,
240 op: LT_EXPR,
241 rhs: first_sval_a);
242 /* Is B fully after A? */
243 tristate b_fully_after_a = model.eval_condition (lhs: first_sval_b,
244 op: GT_EXPR,
245 rhs: last_sval_a);
246
247 if (b_fully_before_a.is_true ()
248 || b_fully_after_a.is_true ())
249 return tristate::TS_FALSE;
250
251 if (b_fully_before_a.is_unknown ()
252 || b_fully_after_a.is_unknown ())
253 return tristate::TS_UNKNOWN;
254
255 return tristate::TS_TRUE;
256}
257
258#if CHECKING_P
259
260namespace selftest {
261
262static void test_intersects (void)
263{
264 region_model_manager mgr;
265 region_model m (&mgr);
266
267 /* Test various concrete ranges. */
268 symbolic_byte_offset zero (0, mgr);
269 symbolic_byte_offset one (1, mgr);
270 symbolic_byte_offset five (5, mgr);
271 symbolic_byte_offset nine (9, mgr);
272 symbolic_byte_offset ten (10, mgr);
273
274 symbolic_byte_range r0_9 (zero, ten);
275 symbolic_byte_range r0 (zero, one);
276 symbolic_byte_range r5_9 (five, five);
277 symbolic_byte_range r9 (nine, one);
278 symbolic_byte_range r10 (ten, one);
279 symbolic_byte_range r10_19 (ten, ten);
280
281 ASSERT_EQ (r0_9.get_start_byte_offset (), zero);
282 ASSERT_EQ (r0_9.get_size_in_bytes (), ten);
283 ASSERT_EQ (r0_9.get_next_byte_offset (mgr), ten);
284 ASSERT_EQ (r0_9.get_last_byte_offset (mgr), nine);
285
286 symbolic_byte_range concrete_empty (zero, zero);
287 ASSERT_TRUE (concrete_empty.empty_p ());
288
289 ASSERT_EQ (r0_9.intersection (r0, m), tristate::TS_TRUE);
290 ASSERT_EQ (r0.intersection (r0_9, m), tristate::TS_TRUE);
291 ASSERT_EQ (r0_9.intersection (r9, m), tristate::TS_TRUE);
292 ASSERT_EQ (r9.intersection (r0_9, m), tristate::TS_TRUE);
293 ASSERT_EQ (r0_9.intersection (r10, m), tristate::TS_FALSE);
294 ASSERT_EQ (r10.intersection (r0_9, m), tristate::TS_FALSE);
295 ASSERT_EQ (concrete_empty.intersection (r0_9, m), tristate::TS_FALSE);
296 ASSERT_EQ (r0_9.intersection (concrete_empty, m), tristate::TS_FALSE);
297
298 ASSERT_EQ (r5_9.intersection (r0, m), tristate::TS_FALSE);
299 ASSERT_EQ (r0.intersection (r5_9, m), tristate::TS_FALSE);
300 ASSERT_EQ (r9.intersection (r5_9, m), tristate::TS_TRUE);
301 ASSERT_EQ (r10.intersection (r5_9, m), tristate::TS_FALSE);
302
303 /* Test various symbolic ranges. */
304 tree x = build_global_decl (name: "x", size_type_node);
305 const svalue *x_init_sval = m.get_rvalue (expr: x, ctxt: nullptr);
306 tree y = build_global_decl (name: "y", size_type_node);
307 const svalue *y_init_sval = m.get_rvalue (expr: y, ctxt: nullptr);
308
309 symbolic_byte_range r0_x_minus_1 (zero, x_init_sval);
310 symbolic_byte_range rx (x_init_sval, one);
311 symbolic_byte_range r0_y_minus_1 (zero, y_init_sval);
312 symbolic_byte_range ry (y_init_sval, one);
313 symbolic_byte_range rx_x_plus_y_minus_1 (x_init_sval, y_init_sval);
314
315 symbolic_byte_range symbolic_empty (x_init_sval, zero);
316 ASSERT_TRUE (symbolic_empty.empty_p ());
317
318 ASSERT_EQ (rx_x_plus_y_minus_1.get_start_byte_offset (), x_init_sval);
319 ASSERT_EQ (rx_x_plus_y_minus_1.get_size_in_bytes (), y_init_sval);
320 ASSERT_EQ
321 (rx_x_plus_y_minus_1.get_next_byte_offset (mgr).get_svalue ()->get_kind (),
322 SK_BINOP);
323 ASSERT_EQ
324 (rx_x_plus_y_minus_1.get_last_byte_offset (mgr).get_svalue ()->get_kind (),
325 SK_BINOP);
326
327 ASSERT_EQ (rx.intersection (ry, m), tristate::TS_UNKNOWN);
328 ASSERT_EQ (rx.intersection (concrete_empty, m), tristate::TS_FALSE);
329 ASSERT_EQ (concrete_empty.intersection (rx, m), tristate::TS_FALSE);
330 ASSERT_EQ (rx.intersection (symbolic_empty, m), tristate::TS_FALSE);
331 ASSERT_EQ (symbolic_empty.intersection (rx, m), tristate::TS_FALSE);
332 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 ASSERT_EQ (r0_x_minus_1.intersection (r0_y_minus_1, m), tristate::TS_TRUE);
340 // TODO: etc
341}
342
343/* Run all of the selftests within this file. */
344
345void
346analyzer_ranges_cc_tests ()
347{
348 test_intersects ();
349}
350
351} // namespace selftest
352
353#endif /* CHECKING_P */
354
355} // namespace ana
356
357#endif /* #if ENABLE_ANALYZER */
358

source code of gcc/analyzer/ranges.cc