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