Line data Source code
1 : /* Support routines for value queries.
2 : Copyright (C) 2020-2026 Free Software Foundation, Inc.
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"
31 : #include "value-query.h"
32 : #include "alloc-pool.h"
33 : #include "gimple-range.h"
34 : #include "value-range-storage.h"
35 :
36 : // range_query default methods.
37 :
38 : bool
39 10525948 : range_query::range_on_edge (vrange &r, edge, tree expr)
40 : {
41 10525948 : return range_of_expr (r, expr);
42 : }
43 :
44 : bool
45 0 : range_query::range_on_entry (vrange &r, basic_block, tree expr)
46 : {
47 0 : return range_of_expr (r, expr);
48 : }
49 :
50 : bool
51 0 : range_query::range_on_exit (vrange &r, basic_block, tree expr)
52 : {
53 0 : return range_of_expr (r, expr);
54 : }
55 :
56 : bool
57 1455694 : range_query::range_of_stmt (vrange &r, gimple *stmt, tree name)
58 : {
59 1455694 : if (!name)
60 1455694 : name = gimple_get_lhs (stmt);
61 :
62 1455694 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
63 :
64 1455694 : if (name)
65 1455694 : return range_of_expr (r, name);
66 : return false;
67 : }
68 :
69 : // Default for updating range info is to do nothing.
70 : void
71 116229740 : range_query::update_range_info (tree)
72 : {
73 116229740 : }
74 :
75 : // Default for updating range info is to do nothing.
76 : void
77 4139010 : range_query::update_range_info (tree, const vrange &)
78 : {
79 4139010 : }
80 :
81 : // If the range of expr EXPR at STMT is a single value, return it.
82 : // Otherwise return NULL_TREE.
83 :
84 : tree
85 151565558 : range_query::value_of_expr (tree expr, gimple *stmt)
86 : {
87 151565558 : tree t;
88 :
89 151565558 : if (!value_range::supports_type_p (TREE_TYPE (expr)))
90 : return NULL_TREE;
91 :
92 148719214 : value_range r (TREE_TYPE (expr));
93 :
94 148719214 : if (range_of_expr (r, expr, stmt))
95 : {
96 : // A constant used in an unreachable block often returns as UNDEFINED.
97 : // If the result is undefined, check the global value for a constant.
98 148719214 : if (r.undefined_p ())
99 227657 : range_of_expr (r, expr);
100 148719214 : if (r.singleton_p (&t))
101 1490611 : return t;
102 : }
103 : return NULL_TREE;
104 148719214 : }
105 :
106 : // If the range on edge E for EXPR is a single value, return it.
107 : // Otherwise return NULL_TREE.
108 :
109 : tree
110 24021730 : range_query::value_on_edge (edge e, tree expr)
111 : {
112 24021730 : tree t;
113 :
114 24021730 : if (!value_range::supports_type_p (TREE_TYPE (expr)))
115 : return NULL_TREE;
116 23754914 : value_range r (TREE_TYPE (expr));
117 23754914 : if (range_on_edge (r, e, expr))
118 : {
119 : // A constant used in an unreachable block often returns as UNDEFINED.
120 : // If the result is undefined, check the global value for a constant.
121 23754914 : if (r.undefined_p ())
122 269031 : range_of_expr (r, expr);
123 23754914 : if (r.singleton_p (&t))
124 299740 : return t;
125 : }
126 : return NULL_TREE;
127 23754914 : }
128 :
129 : // If the range of STMT for NAME is a single value, return it.
130 : // Otherwise return NULL_TREE.
131 :
132 : tree
133 47247525 : range_query::value_of_stmt (gimple *stmt, tree name)
134 : {
135 47247525 : tree t;
136 :
137 47247525 : if (!name)
138 0 : name = gimple_get_lhs (stmt);
139 :
140 47247525 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
141 :
142 47247525 : if (!name || !value_range::supports_type_p (TREE_TYPE (name)))
143 1688933 : return NULL_TREE;
144 45558592 : value_range r (TREE_TYPE (name));
145 91117184 : if (range_of_stmt (r, stmt, name) && r.singleton_p (&t))
146 263477 : return t;
147 : return NULL_TREE;
148 45558592 : }
149 :
150 : // If the range on entry to BB for EXPR is a single value, return it.
151 : // Otherwise return NULL_TREE.
152 :
153 : tree
154 0 : range_query::value_on_entry (basic_block bb, tree expr)
155 : {
156 0 : tree t;
157 :
158 0 : gcc_checking_assert (bb);
159 0 : if (!value_range::supports_type_p (TREE_TYPE (expr)))
160 : return NULL_TREE;
161 :
162 0 : value_range r (TREE_TYPE (expr));
163 :
164 0 : if (range_on_entry (r, bb, expr) && r.singleton_p (&t))
165 0 : return t;
166 : return NULL_TREE;
167 0 : }
168 :
169 : // If the range on exit to BB for EXPR is a single value, return it.
170 : // Otherwise return NULL_TREE.
171 :
172 : tree
173 0 : range_query::value_on_exit (basic_block bb, tree expr)
174 : {
175 0 : tree t;
176 :
177 0 : gcc_checking_assert (bb);
178 0 : if (!value_range::supports_type_p (TREE_TYPE (expr)))
179 : return NULL_TREE;
180 :
181 0 : value_range r (TREE_TYPE (expr));
182 :
183 0 : if (range_on_exit (r, bb, expr) && r.singleton_p (&t))
184 0 : return t;
185 : return NULL_TREE;
186 0 : }
187 :
188 : void
189 0 : range_query::dump (FILE *)
190 : {
191 0 : }
192 :
193 : // Default oracle for all range queries. This contains no storage and thus
194 : // can be used anywhere.
195 : relation_oracle default_relation_oracle;
196 : infer_range_oracle default_infer_oracle;
197 : gimple_outgoing_range default_gori;
198 :
199 : void
200 28047689 : range_query::create_gori (int not_executable_flag, int sw_max_edges)
201 : {
202 28047689 : gcc_checking_assert (m_gori == &default_gori);
203 28047689 : gcc_checking_assert (m_map == NULL);
204 28047689 : m_map = new gori_map ();
205 28047689 : gcc_checking_assert (m_map);
206 28047689 : m_gori = new gori_compute (*m_map, not_executable_flag, sw_max_edges);
207 28047689 : gcc_checking_assert (m_gori);
208 28047689 : }
209 :
210 : void
211 95938958 : range_query::destroy_gori ()
212 : {
213 95938958 : if (m_gori && m_gori != &default_gori)
214 28047688 : delete m_gori;
215 95938958 : if (m_map)
216 28047688 : delete m_map;
217 95938958 : m_map = NULL;
218 95938958 : m_gori= &default_gori;
219 95938958 : }
220 :
221 : // Create an infer oracle using Q as the default range query if needed.
222 : // if DO_SEARCH is true, use immediate uses to scan alluses of a NAME the first
223 : // time it is queried. This is primarily for passes which operate in the
224 : // on-demand model where earlier uses may not have been seen.
225 : // VRP and DOM walk passes set this to FALSE as they will walk all statements
226 : // in order.
227 : void
228 28047689 : range_query::create_infer_oracle (range_query *q, bool do_search)
229 : {
230 28047689 : gcc_checking_assert (m_infer == &default_infer_oracle);
231 28047689 : m_infer = new infer_range_manager (do_search, q);
232 28047689 : gcc_checking_assert (m_infer);
233 28047689 : }
234 :
235 : void
236 123986646 : range_query::destroy_infer_oracle ()
237 : {
238 123986646 : if (m_infer && m_infer != &default_infer_oracle)
239 28047688 : delete m_infer;
240 123986646 : m_infer = &default_infer_oracle;
241 123986646 : }
242 :
243 : // Create dominance based range oracle for the current query if dom info is
244 : // available. DO_TRANS_P indicates whether transitive relations should
245 : // be created. This can cost more in compile time.
246 :
247 : void
248 28047695 : range_query::create_relation_oracle (bool do_trans_p)
249 : {
250 28047695 : gcc_checking_assert (this != &global_ranges);
251 28047695 : gcc_checking_assert (m_relation == &default_relation_oracle);
252 :
253 28047695 : if (!dom_info_available_p (CDI_DOMINATORS))
254 : return;
255 25594912 : m_relation = new dom_oracle (do_trans_p);
256 25594912 : gcc_checking_assert (m_relation);
257 : }
258 :
259 : // Destroy any relation oracle that was created.
260 :
261 : void
262 123986652 : range_query::destroy_relation_oracle ()
263 : {
264 : // m_relation can be NULL if a derived range_query class took care of
265 : // disposing its own oracle.
266 123986652 : if (m_relation && m_relation != &default_relation_oracle)
267 : {
268 25594912 : delete m_relation;
269 25594912 : m_relation = &default_relation_oracle;
270 : }
271 123986652 : }
272 :
273 : void
274 55443684 : range_query::share_query (range_query &q)
275 : {
276 55443684 : m_relation = q.m_relation;
277 55443684 : m_infer = q.m_infer;
278 55443684 : m_gori = q.m_gori;
279 55443684 : m_map = q.m_map;
280 55443684 : m_shared_copy_p = true;
281 55443684 : }
282 :
283 151382653 : range_query::range_query ()
284 : {
285 151382653 : m_relation = &default_relation_oracle;
286 151382653 : m_infer = &default_infer_oracle;
287 151382653 : m_gori = &default_gori;
288 151382653 : m_map = NULL;
289 151382653 : m_shared_copy_p = false;
290 151382653 : }
291 :
292 151382641 : range_query::~range_query ()
293 : {
294 : // Do not destroy anything if this is a shared copy.
295 151382641 : if (m_shared_copy_p)
296 55443683 : return;
297 95938958 : destroy_gori ();
298 95938958 : destroy_infer_oracle ();
299 95938958 : destroy_relation_oracle ();
300 151382641 : }
301 :
302 : // This routine will invoke the equivalent of range_of_expr on
303 : // either a gimple statement STMT, on entry to block BBENTRY, or on
304 : // exit from block BBEXIT. Only one of these 3 fields may be set.
305 : // It is valid for none of them to be set, in wqhich case there is no context.
306 :
307 : bool
308 28271083 : range_query::invoke_range_of_expr (vrange &r, tree expr, gimple *stmt,
309 : basic_block bbentry, basic_block bbexit,
310 : edge e)
311 : {
312 28271083 : if (bbentry)
313 : {
314 0 : gcc_checking_assert (!stmt && !bbexit && !e);
315 0 : return range_on_entry (r, bbentry, expr);
316 : }
317 28271083 : if (bbexit)
318 : {
319 0 : gcc_checking_assert (!stmt && !e);
320 0 : return range_on_exit (r, bbexit, expr);
321 : }
322 28271083 : if (e)
323 : {
324 2094525 : gcc_checking_assert (!stmt);
325 2094525 : return range_on_edge (r, e, expr);
326 : }
327 :
328 26176558 : return range_of_expr (r, expr, stmt);
329 : }
330 :
331 : // Return a range in R for the tree EXPR. The context can be either a STMT,
332 : // or on entry to block BBENTRY or exit from block BBEXIT.
333 : // Return true if a range is representable, and UNDEFINED/false if not.
334 :
335 : bool
336 295157366 : range_query::get_tree_range (vrange &r, tree expr, gimple *stmt,
337 : basic_block bbentry, basic_block bbexit, edge e)
338 : {
339 295157366 : tree type;
340 295157366 : if (TYPE_P (expr))
341 : type = expr;
342 : else
343 295157366 : type = TREE_TYPE (expr);
344 :
345 295157366 : if (!r.supports_type_p (type))
346 : {
347 19873610 : r.set_undefined ();
348 19873610 : return false;
349 : }
350 275283756 : if (expr == type)
351 : {
352 0 : r.set_varying (type);
353 0 : return true;
354 : }
355 275283756 : switch (TREE_CODE (expr))
356 : {
357 224738732 : case INTEGER_CST:
358 224738732 : {
359 224738732 : if (TREE_OVERFLOW_P (expr))
360 175 : expr = drop_tree_overflow (expr);
361 224738732 : r.set (expr, expr);
362 224738732 : return true;
363 : }
364 :
365 4848947 : case REAL_CST:
366 4848947 : {
367 4848947 : frange &f = as_a <frange> (r);
368 4848947 : REAL_VALUE_TYPE *rv = TREE_REAL_CST_PTR (expr);
369 4848947 : if (real_isnan (rv))
370 : {
371 16083 : bool sign = real_isneg (rv);
372 16083 : f.set_nan (TREE_TYPE (expr), sign);
373 : }
374 : else
375 : {
376 4832864 : nan_state nan (false);
377 4832864 : f.set (TREE_TYPE (expr), *rv, *rv, nan);
378 : }
379 : return true;
380 : }
381 :
382 35003 : case SSA_NAME:
383 : // If this is not an abnormal or virtual ssa, invoke range_of_expr.
384 35003 : if (gimple_range_ssa_p (expr))
385 0 : return invoke_range_of_expr (r, expr, stmt, bbentry, bbexit, e);
386 35003 : gimple_range_global (r, expr);
387 35003 : return true;
388 :
389 9842751 : case ADDR_EXPR:
390 9842751 : {
391 : // Handle &var which can show up in phi arguments.
392 9842751 : if (tree_single_nonzero_p (expr))
393 : {
394 9784674 : r.set_nonzero (type);
395 9784674 : return true;
396 : }
397 : break;
398 : }
399 :
400 : default:
401 : if (POLY_INT_CST_P (expr))
402 : {
403 : unsigned int precision = TYPE_PRECISION (type);
404 : r.set_varying (type);
405 : r.update_bitmask ({ wi::zero (precision), get_nonzero_bits (expr) });
406 : return true;
407 : }
408 : break;
409 : }
410 35876400 : if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr))
411 : {
412 11169472 : tree op0 = TREE_OPERAND (expr, 0);
413 11169472 : tree op1 = TREE_OPERAND (expr, 1);
414 11169472 : if (COMPARISON_CLASS_P (expr)
415 11169472 : && !value_range::supports_type_p (TREE_TYPE (op0)))
416 : return false;
417 11169472 : range_op_handler op (TREE_CODE (expr));
418 11169472 : if (op)
419 : {
420 11169472 : value_range r0 (TREE_TYPE (op0));
421 11169472 : value_range r1 (TREE_TYPE (op1));
422 11169472 : invoke_range_of_expr (r0, op0, stmt, bbentry, bbexit, e);
423 11169472 : invoke_range_of_expr (r1, op1, stmt, bbentry, bbexit, e);
424 11169472 : if (!op.fold_range (r, type, r0, r1))
425 0 : r.set_varying (type);
426 11169472 : }
427 : else
428 0 : r.set_varying (type);
429 11169472 : return true;
430 : }
431 24706928 : if (UNARY_CLASS_P (expr))
432 : {
433 5941903 : range_op_handler op (TREE_CODE (expr));
434 5941903 : tree op0_type = TREE_TYPE (TREE_OPERAND (expr, 0));
435 5941903 : if (op && value_range::supports_type_p (op0_type))
436 : {
437 5932139 : value_range r0 (TREE_TYPE (TREE_OPERAND (expr, 0)));
438 5932139 : value_range r1 (type);
439 5932139 : r1.set_varying (type);
440 5932139 : invoke_range_of_expr (r0, TREE_OPERAND (expr, 0), stmt, bbentry,
441 : bbexit, e);
442 5932139 : if (!op.fold_range (r, type, r0, r1))
443 0 : r.set_varying (type);
444 5932139 : }
445 : else
446 9764 : r.set_varying (type);
447 5941903 : return true;
448 : }
449 18765025 : r.set_varying (type);
450 18765025 : return true;
451 : }
452 :
453 : // Return the range for NAME from SSA_NAME_RANGE_INFO.
454 :
455 : static inline void
456 175853244 : get_ssa_name_range_info (vrange &r, const_tree name)
457 : {
458 175853244 : tree type = TREE_TYPE (name);
459 175853244 : gcc_checking_assert (!POINTER_TYPE_P (type));
460 175853244 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
461 :
462 175853244 : vrange_storage *ri = SSA_NAME_RANGE_INFO (name);
463 :
464 175853244 : if (ri)
465 160399354 : ri->get_vrange (r, TREE_TYPE (name));
466 : else
467 15453890 : r.set_varying (type);
468 175853244 : }
469 :
470 : // Return nonnull attribute of pointer NAME from SSA_NAME_PTR_INFO.
471 :
472 : static inline bool
473 92896755 : get_ssa_name_ptr_info_nonnull (const_tree name)
474 : {
475 92896755 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
476 92896755 : struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
477 92896755 : if (pi == NULL)
478 : return false;
479 : /* TODO Now pt->null is conservatively set to true in PTA
480 : analysis. vrp is the only pass (including ipa-vrp)
481 : that clears pt.null via set_ptr_nonnull when it knows
482 : for sure. PTA will preserves the pt.null value set by VRP.
483 :
484 : When PTA analysis is improved, pt.anything, pt.nonlocal
485 : and pt.escaped may also has to be considered before
486 : deciding that pointer cannot point to NULL. */
487 91685888 : return !pi->pt.null;
488 : }
489 :
490 : // Update the global range for NAME into the SSA_RANGE_NAME_INFO and
491 : // Return the legacy global range for NAME if it has one, otherwise
492 : // return VARYING.
493 : // See discussion here regarding why there use to be a wrapper function:
494 : // https://gcc.gnu.org/pipermail/gcc-patches/2021-June/571709.html
495 : // Legacy EVRP has been removed, leaving just this function.
496 :
497 : void
498 605835241 : gimple_range_global (vrange &r, tree name, struct function *fun)
499 : {
500 605835241 : tree type = TREE_TYPE (name);
501 605835241 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
502 :
503 605835241 : if (SSA_NAME_IS_DEFAULT_DEF (name))
504 : {
505 40096376 : tree sym = SSA_NAME_VAR (name);
506 : // Adapted from vr_values::get_lattice_entry().
507 : // Use a range from an SSA_NAME's available range.
508 40096376 : if (TREE_CODE (sym) == PARM_DECL)
509 : {
510 : // Try to use the "nonnull" attribute to create ~[0, 0]
511 : // anti-ranges for pointers. Note that this is only valid with
512 : // default definitions of PARM_DECLs.
513 37244368 : if (POINTER_TYPE_P (type)
514 37244368 : && ((cfun && fun == cfun && nonnull_arg_p (sym))
515 11151051 : || get_ssa_name_ptr_info_nonnull (name)))
516 10500543 : r.set_nonzero (type);
517 26743825 : else if (!POINTER_TYPE_P (type))
518 : {
519 15784379 : get_ssa_name_range_info (r, name);
520 15784379 : if (r.undefined_p ())
521 0 : r.set_varying (type);
522 : }
523 : else
524 10959446 : r.set_varying (type);
525 : }
526 : // If this is a local automatic with no definition, use undefined.
527 2852008 : else if (TREE_CODE (sym) != RESULT_DECL)
528 2533579 : r.set_undefined ();
529 : else
530 318429 : r.set_varying (type);
531 : }
532 565738865 : else if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name))
533 : {
534 160068865 : get_ssa_name_range_info (r, name);
535 160068865 : if (r.undefined_p ())
536 0 : r.set_varying (type);
537 : }
538 405670000 : else if (POINTER_TYPE_P (type) && SSA_NAME_PTR_INFO (name))
539 : {
540 81745704 : if (get_ssa_name_ptr_info_nonnull (name))
541 10634468 : r.set_nonzero (type);
542 : else
543 71111236 : r.set_varying (type);
544 : }
545 : else
546 323924296 : r.set_varying (type);
547 605835241 : }
548 :
549 : // ----------------------------------------------
550 : // global_range_query implementation.
551 :
552 : global_range_query global_ranges;
553 :
554 : bool
555 408606830 : global_range_query::range_of_expr (vrange &r, tree expr, gimple *stmt)
556 : {
557 408606830 : if (!gimple_range_ssa_p (expr))
558 114138916 : return get_tree_range (r, expr, stmt);
559 :
560 294467914 : gimple_range_global (r, expr);
561 :
562 294467914 : return true;
563 : }
|
