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 | 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, cst: i)) |
65 | { |
66 | } |
67 | |
68 | symbolic_byte_offset::symbolic_byte_offset (const svalue *num_bytes_sval) |
69 | : m_num_bytes_sval (num_bytes_sval) |
70 | { |
71 | } |
72 | |
73 | symbolic_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 | |
87 | void |
88 | symbolic_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 | |
94 | void |
95 | symbolic_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 | |
106 | json::value * |
107 | symbolic_byte_offset::to_json () const |
108 | { |
109 | return m_num_bytes_sval->to_json (); |
110 | } |
111 | |
112 | tree |
113 | symbolic_byte_offset::maybe_get_constant () const |
114 | { |
115 | return m_num_bytes_sval->maybe_get_constant (); |
116 | } |
117 | |
118 | /* class symbolic_byte_range. */ |
119 | |
120 | symbolic_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 | |
128 | void |
129 | symbolic_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 | |
153 | void |
154 | symbolic_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 | |
165 | json::value * |
166 | symbolic_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 | |
174 | bool |
175 | symbolic_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 | |
183 | symbolic_byte_offset |
184 | symbolic_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 | |
195 | symbolic_byte_offset |
196 | symbolic_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 | |
207 | tristate |
208 | 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 | 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 | |
260 | namespace selftest { |
261 | |
262 | static 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 | |
345 | void |
346 | analyzer_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 | |