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