]>
Commit | Line | Data |
---|---|---|
6eda9fa5 | 1 | /* Support routines for value queries. |
a945c346 | 2 | Copyright (C) 2020-2024 Free Software Foundation, Inc. |
6eda9fa5 AH |
3 | Contributed by Aldy Hernandez <aldyh@redhat.com> and |
4 | Andrew MacLeod <amacleod@redhat.com>. | |
5 | ||
6 | This file is part of GCC. | |
7 | ||
8 | GCC is free software; you can redistribute it and/or modify | |
9 | it under the terms of the GNU General Public License as published by | |
10 | the Free Software Foundation; either version 3, or (at your option) | |
11 | any later version. | |
12 | ||
13 | GCC is distributed in the hope that it will be useful, | |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | GNU General Public License for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
19 | along with GCC; see the file COPYING3. If not see | |
20 | <http://www.gnu.org/licenses/>. */ | |
21 | ||
22 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
25 | #include "backend.h" | |
26 | #include "tree.h" | |
27 | #include "gimple.h" | |
28 | #include "ssa.h" | |
29 | #include "tree-pretty-print.h" | |
30 | #include "fold-const.h" | |
6eda9fa5 AH |
31 | #include "value-query.h" |
32 | #include "alloc-pool.h" | |
13dbaefe | 33 | #include "gimple-range.h" |
0a7e721a | 34 | #include "value-range-storage.h" |
6eda9fa5 | 35 | |
6eda9fa5 AH |
36 | // range_query default methods. |
37 | ||
38 | bool | |
45c8523d | 39 | range_query::range_on_edge (vrange &r, edge, tree expr) |
6eda9fa5 | 40 | { |
7c097d18 | 41 | return range_of_expr (r, expr); |
6eda9fa5 AH |
42 | } |
43 | ||
39fe6209 AM |
44 | bool |
45 | range_query::range_on_entry (vrange &r, basic_block, tree expr) | |
46 | { | |
47 | return range_of_expr (r, expr); | |
48 | } | |
49 | ||
50 | bool | |
51 | range_query::range_on_exit (vrange &r, basic_block, tree expr) | |
52 | { | |
53 | return range_of_expr (r, expr); | |
54 | } | |
55 | ||
6eda9fa5 | 56 | bool |
45c8523d | 57 | range_query::range_of_stmt (vrange &r, gimple *stmt, tree name) |
6eda9fa5 AH |
58 | { |
59 | if (!name) | |
60 | name = gimple_get_lhs (stmt); | |
61 | ||
62 | gcc_checking_assert (!name || name == gimple_get_lhs (stmt)); | |
63 | ||
64 | if (name) | |
65 | return range_of_expr (r, name); | |
66 | return false; | |
67 | } | |
68 | ||
39fe6209 AM |
69 | // If the range of expr EXPR at STMT is a single value, return it. |
70 | // Otherwise return NULL_TREE. | |
71 | ||
6eda9fa5 | 72 | tree |
7c097d18 | 73 | range_query::value_of_expr (tree expr, gimple *stmt) |
6eda9fa5 AH |
74 | { |
75 | tree t; | |
6eda9fa5 | 76 | |
a9058b08 | 77 | if (!Value_Range::supports_type_p (TREE_TYPE (expr))) |
6eda9fa5 | 78 | return NULL_TREE; |
ca5f4666 | 79 | |
45c8523d AH |
80 | Value_Range r (TREE_TYPE (expr)); |
81 | ||
7c097d18 | 82 | if (range_of_expr (r, expr, stmt)) |
ca5f4666 | 83 | { |
c46b5b0a | 84 | // A constant used in an unreachable block often returns as UNDEFINED. |
ca5f4666 AM |
85 | // If the result is undefined, check the global value for a constant. |
86 | if (r.undefined_p ()) | |
7c097d18 | 87 | range_of_expr (r, expr); |
ca5f4666 AM |
88 | if (r.singleton_p (&t)) |
89 | return t; | |
90 | } | |
6eda9fa5 AH |
91 | return NULL_TREE; |
92 | } | |
93 | ||
39fe6209 AM |
94 | // If the range on edge E for EXPR is a single value, return it. |
95 | // Otherwise return NULL_TREE. | |
96 | ||
6eda9fa5 | 97 | tree |
7c097d18 | 98 | range_query::value_on_edge (edge e, tree expr) |
6eda9fa5 AH |
99 | { |
100 | tree t; | |
6eda9fa5 | 101 | |
a9058b08 | 102 | if (!Value_Range::supports_type_p (TREE_TYPE (expr))) |
6eda9fa5 | 103 | return NULL_TREE; |
45c8523d | 104 | Value_Range r (TREE_TYPE (expr)); |
7c097d18 | 105 | if (range_on_edge (r, e, expr)) |
ca5f4666 | 106 | { |
c46b5b0a | 107 | // A constant used in an unreachable block often returns as UNDEFINED. |
ca5f4666 AM |
108 | // If the result is undefined, check the global value for a constant. |
109 | if (r.undefined_p ()) | |
7c097d18 | 110 | range_of_expr (r, expr); |
ca5f4666 AM |
111 | if (r.singleton_p (&t)) |
112 | return t; | |
113 | } | |
6eda9fa5 | 114 | return NULL_TREE; |
6eda9fa5 AH |
115 | } |
116 | ||
39fe6209 AM |
117 | // If the range of STMT for NAME is a single value, return it. |
118 | // Otherwise return NULL_TREE. | |
119 | ||
6eda9fa5 AH |
120 | tree |
121 | range_query::value_of_stmt (gimple *stmt, tree name) | |
122 | { | |
123 | tree t; | |
6eda9fa5 AH |
124 | |
125 | if (!name) | |
126 | name = gimple_get_lhs (stmt); | |
127 | ||
128 | gcc_checking_assert (!name || name == gimple_get_lhs (stmt)); | |
129 | ||
a9058b08 | 130 | if (!name || !Value_Range::supports_type_p (TREE_TYPE (name))) |
6eda9fa5 | 131 | return NULL_TREE; |
45c8523d | 132 | Value_Range r (TREE_TYPE (name)); |
6eda9fa5 AH |
133 | if (range_of_stmt (r, stmt, name) && r.singleton_p (&t)) |
134 | return t; | |
135 | return NULL_TREE; | |
39fe6209 AM |
136 | } |
137 | ||
138 | // If the range on entry to BB for EXPR is a single value, return it. | |
139 | // Otherwise return NULL_TREE. | |
140 | ||
141 | tree | |
142 | range_query::value_on_entry (basic_block bb, tree expr) | |
143 | { | |
144 | tree t; | |
6eda9fa5 | 145 | |
39fe6209 AM |
146 | gcc_checking_assert (bb); |
147 | if (!Value_Range::supports_type_p (TREE_TYPE (expr))) | |
148 | return NULL_TREE; | |
149 | ||
150 | Value_Range r (TREE_TYPE (expr)); | |
151 | ||
152 | if (range_on_entry (r, bb, expr) && r.singleton_p (&t)) | |
153 | return t; | |
154 | return NULL_TREE; | |
155 | } | |
156 | ||
157 | // If the range on exit to BB for EXPR is a single value, return it. | |
158 | // Otherwise return NULL_TREE. | |
159 | ||
160 | tree | |
161 | range_query::value_on_exit (basic_block bb, tree expr) | |
162 | { | |
163 | tree t; | |
164 | ||
165 | gcc_checking_assert (bb); | |
166 | if (!Value_Range::supports_type_p (TREE_TYPE (expr))) | |
167 | return NULL_TREE; | |
168 | ||
169 | Value_Range r (TREE_TYPE (expr)); | |
170 | ||
171 | if (range_on_exit (r, bb, expr) && r.singleton_p (&t)) | |
172 | return t; | |
173 | return NULL_TREE; | |
6eda9fa5 AH |
174 | } |
175 | ||
586d6f7a AH |
176 | void |
177 | range_query::dump (FILE *) | |
178 | { | |
179 | } | |
180 | ||
6eda9fa5 AH |
181 | range_query::range_query () |
182 | { | |
3aaa69e5 | 183 | m_oracle = NULL; |
6eda9fa5 AH |
184 | } |
185 | ||
186 | range_query::~range_query () | |
187 | { | |
6eda9fa5 | 188 | } |
13dbaefe | 189 | |
39fe6209 AM |
190 | // This routine will invoke the equivalent of range_of_expr on |
191 | // either a gimple statement STMT, on entry to block BBENTRY, or on | |
192 | // exit from block BBEXIT. Only one of these 3 fields may be set. | |
193 | // It is valid for none of them to be set, in wqhich case there is no context. | |
194 | ||
195 | bool | |
196 | range_query::invoke_range_of_expr (vrange &r, tree expr, gimple *stmt, | |
197 | basic_block bbentry, basic_block bbexit) | |
198 | { | |
199 | if (bbentry) | |
200 | { | |
201 | gcc_checking_assert (!stmt && !bbexit); | |
202 | return range_on_entry (r, bbentry, expr); | |
203 | } | |
204 | if (bbexit) | |
205 | { | |
206 | gcc_checking_assert (!stmt); | |
207 | return range_on_exit (r, bbexit, expr); | |
208 | } | |
209 | ||
210 | return range_of_expr (r, expr, stmt); | |
211 | } | |
212 | ||
213 | // Return a range in R for the tree EXPR. The context can be either a STMT, | |
214 | // or on entry to block BBENTRY or exit from block BBEXIT. | |
215 | // Return true if a range is representable, and UNDEFINED/false if not. | |
caa60c12 AH |
216 | |
217 | bool | |
39fe6209 AM |
218 | range_query::get_tree_range (vrange &r, tree expr, gimple *stmt, |
219 | basic_block bbentry, basic_block bbexit) | |
caa60c12 AH |
220 | { |
221 | tree type; | |
222 | if (TYPE_P (expr)) | |
223 | type = expr; | |
224 | else | |
225 | type = TREE_TYPE (expr); | |
226 | ||
a9058b08 | 227 | if (!Value_Range::supports_type_p (type)) |
caa60c12 AH |
228 | { |
229 | r.set_undefined (); | |
230 | return false; | |
231 | } | |
232 | if (expr == type) | |
233 | { | |
234 | r.set_varying (type); | |
235 | return true; | |
236 | } | |
237 | switch (TREE_CODE (expr)) | |
238 | { | |
239 | case INTEGER_CST: | |
cb779afe | 240 | { |
cb779afe AH |
241 | if (TREE_OVERFLOW_P (expr)) |
242 | expr = drop_tree_overflow (expr); | |
c284f8d2 | 243 | r.set (expr, expr); |
cb779afe AH |
244 | return true; |
245 | } | |
8bb1df03 | 246 | |
a6efab5f | 247 | case REAL_CST: |
e9b0dd2a | 248 | { |
e9b0dd2a | 249 | frange &f = as_a <frange> (r); |
cb779afe | 250 | REAL_VALUE_TYPE *rv = TREE_REAL_CST_PTR (expr); |
fae324f1 AH |
251 | if (real_isnan (rv)) |
252 | { | |
253 | bool sign = real_isneg (rv); | |
254 | f.set_nan (TREE_TYPE (expr), sign); | |
255 | } | |
256 | else | |
257 | { | |
258 | nan_state nan (false); | |
259 | f.set (TREE_TYPE (expr), *rv, *rv, nan); | |
260 | } | |
e9b0dd2a AH |
261 | return true; |
262 | } | |
caa60c12 AH |
263 | |
264 | case SSA_NAME: | |
39fe6209 AM |
265 | // If this is not an abnormal or virtual ssa, invoke range_of_expr. |
266 | if (gimple_range_ssa_p (expr)) | |
267 | return invoke_range_of_expr (r, expr, stmt, bbentry, bbexit); | |
45c8523d | 268 | gimple_range_global (r, expr); |
caa60c12 AH |
269 | return true; |
270 | ||
271 | case ADDR_EXPR: | |
272 | { | |
273 | // Handle &var which can show up in phi arguments. | |
274 | bool ov; | |
275 | if (tree_single_nonzero_warnv_p (expr, &ov)) | |
276 | { | |
45c8523d | 277 | r.set_nonzero (type); |
caa60c12 AH |
278 | return true; |
279 | } | |
280 | break; | |
281 | } | |
282 | ||
283 | default: | |
284 | break; | |
285 | } | |
e02c9d91 | 286 | if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr)) |
caa60c12 | 287 | { |
e02c9d91 JJ |
288 | tree op0 = TREE_OPERAND (expr, 0); |
289 | tree op1 = TREE_OPERAND (expr, 1); | |
290 | if (COMPARISON_CLASS_P (expr) | |
291 | && !Value_Range::supports_type_p (TREE_TYPE (op0))) | |
292 | return false; | |
2eb50117 | 293 | range_op_handler op (TREE_CODE (expr)); |
caa60c12 AH |
294 | if (op) |
295 | { | |
e02c9d91 JJ |
296 | Value_Range r0 (TREE_TYPE (op0)); |
297 | Value_Range r1 (TREE_TYPE (op1)); | |
39fe6209 AM |
298 | invoke_range_of_expr (r0, op0, stmt, bbentry, bbexit); |
299 | invoke_range_of_expr (r1, op1, stmt, bbentry, bbexit); | |
2f92f685 AM |
300 | if (!op.fold_range (r, type, r0, r1)) |
301 | r.set_varying (type); | |
caa60c12 AH |
302 | } |
303 | else | |
304 | r.set_varying (type); | |
305 | return true; | |
306 | } | |
307 | if (UNARY_CLASS_P (expr)) | |
308 | { | |
2eb50117 | 309 | range_op_handler op (TREE_CODE (expr)); |
59c8e96d | 310 | tree op0_type = TREE_TYPE (TREE_OPERAND (expr, 0)); |
a9058b08 | 311 | if (op && Value_Range::supports_type_p (op0_type)) |
caa60c12 | 312 | { |
45c8523d AH |
313 | Value_Range r0 (TREE_TYPE (TREE_OPERAND (expr, 0))); |
314 | Value_Range r1 (type); | |
315 | r1.set_varying (type); | |
39fe6209 AM |
316 | invoke_range_of_expr (r0, TREE_OPERAND (expr, 0), stmt, bbentry, |
317 | bbexit); | |
2f92f685 AM |
318 | if (!op.fold_range (r, type, r0, r1)) |
319 | r.set_varying (type); | |
caa60c12 AH |
320 | } |
321 | else | |
322 | r.set_varying (type); | |
323 | return true; | |
324 | } | |
325 | r.set_varying (type); | |
326 | return true; | |
327 | } | |
328 | ||
13dbaefe AH |
329 | // Return the range for NAME from SSA_NAME_RANGE_INFO. |
330 | ||
331 | static inline void | |
0a7e721a | 332 | get_ssa_name_range_info (vrange &r, const_tree name) |
13dbaefe AH |
333 | { |
334 | tree type = TREE_TYPE (name); | |
335 | gcc_checking_assert (!POINTER_TYPE_P (type)); | |
336 | gcc_checking_assert (TREE_CODE (name) == SSA_NAME); | |
337 | ||
e1366a7e | 338 | vrange_storage *ri = SSA_NAME_RANGE_INFO (name); |
13dbaefe | 339 | |
164758b0 | 340 | if (ri) |
e1366a7e | 341 | ri->get_vrange (r, TREE_TYPE (name)); |
164758b0 AH |
342 | else |
343 | r.set_varying (type); | |
13dbaefe AH |
344 | } |
345 | ||
346 | // Return nonnull attribute of pointer NAME from SSA_NAME_PTR_INFO. | |
347 | ||
348 | static inline bool | |
349 | get_ssa_name_ptr_info_nonnull (const_tree name) | |
350 | { | |
351 | gcc_assert (POINTER_TYPE_P (TREE_TYPE (name))); | |
352 | struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name); | |
353 | if (pi == NULL) | |
354 | return false; | |
355 | /* TODO Now pt->null is conservatively set to true in PTA | |
356 | analysis. vrp is the only pass (including ipa-vrp) | |
7407f704 | 357 | that clears pt.null via set_ptr_nonnull when it knows |
13dbaefe AH |
358 | for sure. PTA will preserves the pt.null value set by VRP. |
359 | ||
360 | When PTA analysis is improved, pt.anything, pt.nonlocal | |
361 | and pt.escaped may also has to be considered before | |
362 | deciding that pointer cannot point to NULL. */ | |
363 | return !pi->pt.null; | |
364 | } | |
365 | ||
160fe603 | 366 | // Update the global range for NAME into the SSA_RANGE_NAME_INFO and |
13dbaefe AH |
367 | // Return the legacy global range for NAME if it has one, otherwise |
368 | // return VARYING. | |
56aa8ad7 AM |
369 | // See discussion here regarding why there use to be a wrapper function: |
370 | // https://gcc.gnu.org/pipermail/gcc-patches/2021-June/571709.html | |
371 | // Legacy EVRP has been removed, leaving just this function. | |
13dbaefe | 372 | |
56aa8ad7 AM |
373 | void |
374 | gimple_range_global (vrange &r, tree name, struct function *fun) | |
13dbaefe AH |
375 | { |
376 | tree type = TREE_TYPE (name); | |
56aa8ad7 | 377 | gcc_checking_assert (TREE_CODE (name) == SSA_NAME); |
13dbaefe AH |
378 | |
379 | if (SSA_NAME_IS_DEFAULT_DEF (name)) | |
380 | { | |
381 | tree sym = SSA_NAME_VAR (name); | |
382 | // Adapted from vr_values::get_lattice_entry(). | |
383 | // Use a range from an SSA_NAME's available range. | |
384 | if (TREE_CODE (sym) == PARM_DECL) | |
385 | { | |
386 | // Try to use the "nonnull" attribute to create ~[0, 0] | |
387 | // anti-ranges for pointers. Note that this is only valid with | |
388 | // default definitions of PARM_DECLs. | |
389 | if (POINTER_TYPE_P (type) | |
99f3ad2e | 390 | && ((cfun && fun == cfun && nonnull_arg_p (sym)) |
13dbaefe AH |
391 | || get_ssa_name_ptr_info_nonnull (name))) |
392 | r.set_nonzero (type); | |
d155442d | 393 | else if (!POINTER_TYPE_P (type)) |
13dbaefe | 394 | { |
0a7e721a | 395 | get_ssa_name_range_info (r, name); |
13dbaefe AH |
396 | if (r.undefined_p ()) |
397 | r.set_varying (type); | |
398 | } | |
399 | else | |
400 | r.set_varying (type); | |
401 | } | |
402 | // If this is a local automatic with no definition, use undefined. | |
403 | else if (TREE_CODE (sym) != RESULT_DECL) | |
404 | r.set_undefined (); | |
405 | else | |
406 | r.set_varying (type); | |
407 | } | |
408 | else if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name)) | |
409 | { | |
0a7e721a | 410 | get_ssa_name_range_info (r, name); |
13dbaefe AH |
411 | if (r.undefined_p ()) |
412 | r.set_varying (type); | |
413 | } | |
414 | else if (POINTER_TYPE_P (type) && SSA_NAME_PTR_INFO (name)) | |
415 | { | |
416 | if (get_ssa_name_ptr_info_nonnull (name)) | |
417 | r.set_nonzero (type); | |
418 | else | |
419 | r.set_varying (type); | |
420 | } | |
421 | else | |
422 | r.set_varying (type); | |
423 | } | |
424 | ||
13dbaefe AH |
425 | // ---------------------------------------------- |
426 | // global_range_query implementation. | |
427 | ||
428 | global_range_query global_ranges; | |
429 | ||
13dbaefe | 430 | bool |
45c8523d | 431 | global_range_query::range_of_expr (vrange &r, tree expr, gimple *stmt) |
13dbaefe | 432 | { |
a9058b08 | 433 | if (!gimple_range_ssa_p (expr)) |
caa60c12 | 434 | return get_tree_range (r, expr, stmt); |
13dbaefe | 435 | |
56aa8ad7 | 436 | gimple_range_global (r, expr); |
13dbaefe AH |
437 | |
438 | return true; | |
439 | } | |
3aaa69e5 AM |
440 | |
441 | // Return any known relation between SSA1 and SSA2 before stmt S is executed. | |
442 | // If GET_RANGE is true, query the range of both operands first to ensure | |
c46b5b0a | 443 | // the definitions have been processed and any relations have be created. |
3aaa69e5 AM |
444 | |
445 | relation_kind | |
446 | range_query::query_relation (gimple *s, tree ssa1, tree ssa2, bool get_range) | |
447 | { | |
3aaa69e5 | 448 | if (!m_oracle || TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME) |
ade5531c | 449 | return VREL_VARYING; |
3aaa69e5 AM |
450 | |
451 | // Ensure ssa1 and ssa2 have both been evaluated. | |
452 | if (get_range) | |
453 | { | |
45c8523d AH |
454 | Value_Range tmp1 (TREE_TYPE (ssa1)); |
455 | Value_Range tmp2 (TREE_TYPE (ssa2)); | |
456 | range_of_expr (tmp1, ssa1, s); | |
457 | range_of_expr (tmp2, ssa2, s); | |
3aaa69e5 AM |
458 | } |
459 | return m_oracle->query_relation (gimple_bb (s), ssa1, ssa2); | |
460 | } | |
461 | ||
462 | // Return any known relation between SSA1 and SSA2 on edge E. | |
463 | // If GET_RANGE is true, query the range of both operands first to ensure | |
c46b5b0a | 464 | // the definitions have been processed and any relations have be created. |
3aaa69e5 AM |
465 | |
466 | relation_kind | |
467 | range_query::query_relation (edge e, tree ssa1, tree ssa2, bool get_range) | |
468 | { | |
469 | basic_block bb; | |
3aaa69e5 | 470 | if (!m_oracle || TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME) |
ade5531c | 471 | return VREL_VARYING; |
3aaa69e5 AM |
472 | |
473 | // Use destination block if it has a single predecessor, and this picks | |
474 | // up any relation on the edge. | |
475 | // Otherwise choose the src edge and the result is the same as on-exit. | |
476 | if (!single_pred_p (e->dest)) | |
477 | bb = e->src; | |
478 | else | |
479 | bb = e->dest; | |
480 | ||
481 | // Ensure ssa1 and ssa2 have both been evaluated. | |
482 | if (get_range) | |
483 | { | |
45c8523d | 484 | Value_Range tmp (TREE_TYPE (ssa1)); |
3aaa69e5 AM |
485 | range_on_edge (tmp, e, ssa1); |
486 | range_on_edge (tmp, e, ssa2); | |
487 | } | |
488 | return m_oracle->query_relation (bb, ssa1, ssa2); | |
489 | } |