hppa: Fix REG+D address support before reload
[official-gcc.git] / gcc / analyzer / ranges.cc
blobffdd0d4c57226b12605e05a0c669eaeca6655dc2
1 /* Symbolic offsets and ranges.
2 Copyright (C) 2023-2024 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
5 This file is part of GCC.
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.
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.
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/>. */
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"
57 #if ENABLE_ANALYZER
59 namespace ana {
61 /* class symbolic_byte_offset. */
63 symbolic_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, i))
68 symbolic_byte_offset::symbolic_byte_offset (const svalue *num_bytes_sval)
69 : m_num_bytes_sval (num_bytes_sval)
73 symbolic_byte_offset::symbolic_byte_offset (region_offset offset,
74 region_model_manager &mgr)
76 if (offset.concrete_p ())
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, num_bytes);
83 else
84 m_num_bytes_sval = offset.get_symbolic_byte_offset ();
87 void
88 symbolic_byte_offset::dump_to_pp (pretty_printer *pp, bool simple) const
90 pp_string (pp, "byte ");
91 m_num_bytes_sval->dump_to_pp (pp, simple);
94 void
95 symbolic_byte_offset::dump (bool simple) const
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, simple);
102 pp_newline (&pp);
103 pp_flush (&pp);
106 tree
107 symbolic_byte_offset::maybe_get_constant () const
109 return m_num_bytes_sval->maybe_get_constant ();
112 /* class symbolic_byte_range. */
114 symbolic_byte_range::symbolic_byte_range (region_offset start,
115 const svalue *num_bytes,
116 region_model_manager &mgr)
117 : m_start (start, mgr),
118 m_size (num_bytes)
122 void
123 symbolic_byte_range::dump_to_pp (pretty_printer *pp,
124 bool simple,
125 region_model_manager &mgr) const
127 if (empty_p ())
129 pp_string (pp, "empty");
130 return;
133 if (tree size_cst = m_size.maybe_get_constant ())
134 if (integer_onep (size_cst))
136 pp_string (pp, "byte ");
137 m_start.get_svalue ()->dump_to_pp (pp, simple);
138 return;
141 pp_string (pp, "bytes ");
142 m_start.get_svalue ()->dump_to_pp (pp, simple);
143 pp_string (pp, " to ");
144 get_last_byte_offset (mgr).get_svalue ()->dump_to_pp (pp, simple);
147 void
148 symbolic_byte_range::dump (bool simple, region_model_manager &mgr) const
150 pretty_printer pp;
151 pp_format_decoder (&pp) = default_tree_printer;
152 pp_show_color (&pp) = pp_show_color (global_dc->printer);
153 pp.buffer->stream = stderr;
154 dump_to_pp (&pp, simple, mgr);
155 pp_newline (&pp);
156 pp_flush (&pp);
159 bool
160 symbolic_byte_range::empty_p () const
162 tree cst = m_size.maybe_get_constant ();
163 if (!cst)
164 return false;
165 return zerop (cst);
168 symbolic_byte_offset
169 symbolic_byte_range::get_last_byte_offset (region_model_manager &mgr) const
171 gcc_assert (!empty_p ());
172 const symbolic_byte_offset one (1, mgr);
173 return symbolic_byte_offset
174 (mgr.get_or_create_binop (size_type_node,
175 MINUS_EXPR,
176 get_next_byte_offset (mgr).get_svalue (),
177 one.get_svalue ()));
180 symbolic_byte_offset
181 symbolic_byte_range::get_next_byte_offset (region_model_manager &mgr) const
183 return symbolic_byte_offset (mgr.get_or_create_binop (size_type_node,
184 PLUS_EXPR,
185 m_start.get_svalue (),
186 m_size.get_svalue ()));
189 /* Attempt to determine if THIS range intersects OTHER,
190 using constraints from MODEL. */
192 tristate
193 symbolic_byte_range::intersection (const symbolic_byte_range &other,
194 const region_model &model) const
196 /* If either is empty, then there is no intersection. */
197 if (empty_p ())
198 return tristate::TS_FALSE;
199 if (other.empty_p ())
200 return tristate::TS_FALSE;
202 /* For brevity, consider THIS to be "range A", and OTHER to be "range B". */
204 region_model_manager *mgr = model.get_manager ();
206 const svalue *first_sval_a = m_start.get_svalue ();
207 const svalue *first_sval_b = other.m_start.get_svalue ();
208 const svalue *last_sval_a = get_last_byte_offset (*mgr).get_svalue ();
209 const svalue *last_sval_b = other.get_last_byte_offset (*mgr).get_svalue ();
211 if (m_size.get_svalue ()->get_kind () == SK_UNKNOWN
212 || other.m_size.get_svalue ()->get_kind () == SK_UNKNOWN)
214 if (first_sval_a == first_sval_b)
215 return tristate::TS_TRUE;
216 else
217 return tristate::TS_UNKNOWN;
220 if (first_sval_a == first_sval_b)
221 return tristate::TS_TRUE;
223 /* Is B fully before A? */
224 tristate b_fully_before_a = model.eval_condition (last_sval_b,
225 LT_EXPR,
226 first_sval_a);
227 /* Is B fully after A? */
228 tristate b_fully_after_a = model.eval_condition (first_sval_b,
229 GT_EXPR,
230 last_sval_a);
232 if (b_fully_before_a.is_true ()
233 || b_fully_after_a.is_true ())
234 return tristate::TS_FALSE;
236 if (b_fully_before_a.is_unknown ()
237 || b_fully_after_a.is_unknown ())
238 return tristate::TS_UNKNOWN;
240 return tristate::TS_TRUE;
243 #if CHECKING_P
245 namespace selftest {
247 static void test_intersects (void)
249 region_model_manager mgr;
250 region_model m (&mgr);
252 /* Test various concrete ranges. */
253 symbolic_byte_offset zero (0, mgr);
254 symbolic_byte_offset one (1, mgr);
255 symbolic_byte_offset five (5, mgr);
256 symbolic_byte_offset nine (9, mgr);
257 symbolic_byte_offset ten (10, mgr);
259 symbolic_byte_range r0_9 (zero, ten);
260 symbolic_byte_range r0 (zero, one);
261 symbolic_byte_range r5_9 (five, five);
262 symbolic_byte_range r9 (nine, one);
263 symbolic_byte_range r10 (ten, one);
264 symbolic_byte_range r10_19 (ten, ten);
266 ASSERT_EQ (r0_9.get_start_byte_offset (), zero);
267 ASSERT_EQ (r0_9.get_size_in_bytes (), ten);
268 ASSERT_EQ (r0_9.get_next_byte_offset (mgr), ten);
269 ASSERT_EQ (r0_9.get_last_byte_offset (mgr), nine);
271 symbolic_byte_range concrete_empty (zero, zero);
272 ASSERT_TRUE (concrete_empty.empty_p ());
274 ASSERT_EQ (r0_9.intersection (r0, m), tristate::TS_TRUE);
275 ASSERT_EQ (r0.intersection (r0_9, m), tristate::TS_TRUE);
276 ASSERT_EQ (r0_9.intersection (r9, m), tristate::TS_TRUE);
277 ASSERT_EQ (r9.intersection (r0_9, m), tristate::TS_TRUE);
278 ASSERT_EQ (r0_9.intersection (r10, m), tristate::TS_FALSE);
279 ASSERT_EQ (r10.intersection (r0_9, m), tristate::TS_FALSE);
280 ASSERT_EQ (concrete_empty.intersection (r0_9, m), tristate::TS_FALSE);
281 ASSERT_EQ (r0_9.intersection (concrete_empty, m), tristate::TS_FALSE);
283 ASSERT_EQ (r5_9.intersection (r0, m), tristate::TS_FALSE);
284 ASSERT_EQ (r0.intersection (r5_9, m), tristate::TS_FALSE);
285 ASSERT_EQ (r9.intersection (r5_9, m), tristate::TS_TRUE);
286 ASSERT_EQ (r10.intersection (r5_9, m), tristate::TS_FALSE);
288 /* Test various symbolic ranges. */
289 tree x = build_global_decl ("x", size_type_node);
290 const svalue *x_init_sval = m.get_rvalue (x, nullptr);
291 tree y = build_global_decl ("y", size_type_node);
292 const svalue *y_init_sval = m.get_rvalue (y, nullptr);
294 symbolic_byte_range r0_x_minus_1 (zero, x_init_sval);
295 symbolic_byte_range rx (x_init_sval, one);
296 symbolic_byte_range r0_y_minus_1 (zero, y_init_sval);
297 symbolic_byte_range ry (y_init_sval, one);
298 symbolic_byte_range rx_x_plus_y_minus_1 (x_init_sval, y_init_sval);
300 symbolic_byte_range symbolic_empty (x_init_sval, zero);
301 ASSERT_TRUE (symbolic_empty.empty_p ());
303 ASSERT_EQ (rx_x_plus_y_minus_1.get_start_byte_offset (), x_init_sval);
304 ASSERT_EQ (rx_x_plus_y_minus_1.get_size_in_bytes (), y_init_sval);
305 ASSERT_EQ
306 (rx_x_plus_y_minus_1.get_next_byte_offset (mgr).get_svalue ()->get_kind (),
307 SK_BINOP);
308 ASSERT_EQ
309 (rx_x_plus_y_minus_1.get_last_byte_offset (mgr).get_svalue ()->get_kind (),
310 SK_BINOP);
312 ASSERT_EQ (rx.intersection (ry, m), tristate::TS_UNKNOWN);
313 ASSERT_EQ (rx.intersection (concrete_empty, m), tristate::TS_FALSE);
314 ASSERT_EQ (concrete_empty.intersection (rx, m), tristate::TS_FALSE);
315 ASSERT_EQ (rx.intersection (symbolic_empty, m), tristate::TS_FALSE);
316 ASSERT_EQ (symbolic_empty.intersection (rx, m), tristate::TS_FALSE);
317 ASSERT_EQ (r0_x_minus_1.intersection (r0, m), tristate::TS_TRUE);
318 #if 0
319 ASSERT_EQ (r0_x_minus_1.intersection (rx, m), tristate::TS_FALSE);
320 /* Fails (with UNKNOWN): b_fully_after_a is UNKNOWN, when it could
321 be TRUE: last of A is (x - 1), but it's not necessarily true that
322 X > (x - 1), for the case where x is (unsigned)0. */
323 #endif
324 ASSERT_EQ (r0_x_minus_1.intersection (r0_y_minus_1, m), tristate::TS_TRUE);
325 // TODO: etc
328 /* Run all of the selftests within this file. */
330 void
331 analyzer_ranges_cc_tests ()
333 test_intersects ();
336 } // namespace selftest
338 #endif /* CHECKING_P */
340 } // namespace ana
342 #endif /* #if ENABLE_ANALYZER */