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 16458203 : range_query::range_on_edge (vrange &r, edge, tree expr)
40 : {
41 16458203 : 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 1508051 : range_query::range_of_stmt (vrange &r, gimple *stmt, tree name)
58 : {
59 1508051 : if (!name)
60 1508051 : name = gimple_get_lhs (stmt);
61 :
62 1508051 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
63 :
64 1508051 : if (name)
65 1508051 : return range_of_expr (r, name);
66 : return false;
67 : }
68 :
69 : // Default for updating range info is to do nothing.
70 : void
71 120681340 : range_query::update_range_info (tree)
72 : {
73 120681340 : }
74 :
75 : // Default for updating range info is to do nothing.
76 : void
77 4233788 : range_query::update_range_info (tree, const vrange &)
78 : {
79 4233788 : }
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 53983283 : range_query::value_of_expr (tree expr, gimple *stmt)
86 : {
87 53983283 : tree t;
88 :
89 53983283 : if (!value_range::supports_type_p (TREE_TYPE (expr)))
90 : return NULL_TREE;
91 :
92 53981760 : value_range r (TREE_TYPE (expr));
93 :
94 53981760 : 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 53981760 : if (r.undefined_p ())
99 19518 : range_of_expr (r, expr);
100 53981760 : if (r.singleton_p (&t))
101 1743826 : return t;
102 : }
103 : return NULL_TREE;
104 53981760 : }
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 15 : range_query::value_on_edge (edge e, tree expr)
111 : {
112 15 : tree t;
113 :
114 15 : if (!value_range::supports_type_p (TREE_TYPE (expr)))
115 : return NULL_TREE;
116 15 : value_range r (TREE_TYPE (expr));
117 15 : 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 15 : if (r.undefined_p ())
122 0 : range_of_expr (r, expr);
123 15 : if (r.singleton_p (&t))
124 3 : return t;
125 : }
126 : return NULL_TREE;
127 15 : }
128 :
129 : // If the range of STMT for NAME is a single value, return it.
130 : // Otherwise return NULL_TREE.
131 :
132 : tree
133 48621988 : range_query::value_of_stmt (gimple *stmt, tree name)
134 : {
135 48621988 : tree t;
136 :
137 48621988 : if (!name)
138 0 : name = gimple_get_lhs (stmt);
139 :
140 48621988 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
141 :
142 48621988 : if (!name || !value_range::supports_type_p (TREE_TYPE (name)))
143 1807257 : return NULL_TREE;
144 46814731 : value_range r (TREE_TYPE (name));
145 93629462 : if (range_of_stmt (r, stmt, name) && r.singleton_p (&t))
146 280308 : return t;
147 : return NULL_TREE;
148 46814731 : }
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 28204919 : range_query::create_gori (int not_executable_flag, int sw_max_edges)
201 : {
202 28204919 : gcc_checking_assert (m_gori == &default_gori);
203 28204919 : gcc_checking_assert (m_map == NULL);
204 28204919 : m_map = new gori_map ();
205 28204919 : gcc_checking_assert (m_map);
206 28204919 : m_gori = new gori_compute (*m_map, not_executable_flag, sw_max_edges);
207 28204919 : gcc_checking_assert (m_gori);
208 28204919 : }
209 :
210 : void
211 97287696 : range_query::destroy_gori ()
212 : {
213 97287696 : if (m_gori && m_gori != &default_gori)
214 28204919 : delete m_gori;
215 97287696 : if (m_map)
216 28204919 : delete m_map;
217 97287696 : m_map = NULL;
218 97287696 : m_gori= &default_gori;
219 97287696 : }
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 28204919 : range_query::create_infer_oracle (range_query *q, bool do_search)
229 : {
230 28204919 : gcc_checking_assert (m_infer == &default_infer_oracle);
231 28204919 : m_infer = new infer_range_manager (do_search, q);
232 28204919 : gcc_checking_assert (m_infer);
233 28204919 : }
234 :
235 : void
236 125492615 : range_query::destroy_infer_oracle ()
237 : {
238 125492615 : if (m_infer && m_infer != &default_infer_oracle)
239 28204919 : delete m_infer;
240 125492615 : m_infer = &default_infer_oracle;
241 125492615 : }
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 28204925 : range_query::create_relation_oracle (bool do_trans_p)
249 : {
250 28204925 : gcc_checking_assert (this != &global_ranges);
251 28204925 : gcc_checking_assert (m_relation == &default_relation_oracle);
252 :
253 28204925 : if (!dom_info_available_p (CDI_DOMINATORS))
254 : return;
255 26166897 : m_relation = new dom_oracle (do_trans_p);
256 26166897 : gcc_checking_assert (m_relation);
257 : }
258 :
259 : // Destroy any relation oracle that was created.
260 :
261 : void
262 125492621 : 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 125492621 : if (m_relation && m_relation != &default_relation_oracle)
267 : {
268 26166897 : delete m_relation;
269 26166897 : m_relation = &default_relation_oracle;
270 : }
271 125492621 : }
272 :
273 : void
274 56369349 : range_query::share_query (range_query &q)
275 : {
276 56369349 : m_relation = q.m_relation;
277 56369349 : m_infer = q.m_infer;
278 56369349 : m_gori = q.m_gori;
279 56369349 : m_map = q.m_map;
280 56369349 : m_shared_copy_p = true;
281 56369349 : }
282 :
283 153657054 : range_query::range_query ()
284 : {
285 153657054 : m_relation = &default_relation_oracle;
286 153657054 : m_infer = &default_infer_oracle;
287 153657054 : m_gori = &default_gori;
288 153657054 : m_map = NULL;
289 153657054 : m_shared_copy_p = false;
290 153657054 : }
291 :
292 153657045 : range_query::~range_query ()
293 : {
294 : // Do not destroy anything if this is a shared copy.
295 153657045 : if (m_shared_copy_p)
296 56369349 : return;
297 97287696 : destroy_gori ();
298 97287696 : destroy_infer_oracle ();
299 97287696 : destroy_relation_oracle ();
300 153657045 : }
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 30701473 : range_query::invoke_range_of_expr (vrange &r, tree expr, gimple *stmt,
309 : basic_block bbentry, basic_block bbexit,
310 : edge e)
311 : {
312 30701473 : if (bbentry)
313 : {
314 0 : gcc_checking_assert (!stmt && !bbexit && !e);
315 0 : return range_on_entry (r, bbentry, expr);
316 : }
317 30701473 : if (bbexit)
318 : {
319 0 : gcc_checking_assert (!stmt && !e);
320 0 : return range_on_exit (r, bbexit, expr);
321 : }
322 30701473 : if (e)
323 : {
324 2636762 : gcc_checking_assert (!stmt);
325 2636762 : return range_on_edge (r, e, expr);
326 : }
327 :
328 28064711 : 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 302617661 : range_query::get_tree_range (vrange &r, tree expr, gimple *stmt,
337 : basic_block bbentry, basic_block bbexit, edge e)
338 : {
339 302617661 : tree type;
340 302617661 : if (TYPE_P (expr))
341 : type = expr;
342 : else
343 302617661 : type = TREE_TYPE (expr);
344 :
345 302617661 : if (!r.supports_type_p (type))
346 : {
347 20738825 : r.set_undefined ();
348 20738825 : return false;
349 : }
350 281878836 : if (expr == type)
351 : {
352 0 : r.set_varying (type);
353 0 : return true;
354 : }
355 281878836 : switch (TREE_CODE (expr))
356 : {
357 227827263 : case INTEGER_CST:
358 227827263 : {
359 227827263 : if (TREE_OVERFLOW_P (expr))
360 63 : expr = drop_tree_overflow (expr);
361 227827263 : r.set (expr, expr);
362 227827263 : return true;
363 : }
364 :
365 4785686 : case REAL_CST:
366 4785686 : {
367 4785686 : frange &f = as_a <frange> (r);
368 4785686 : REAL_VALUE_TYPE *rv = TREE_REAL_CST_PTR (expr);
369 4785686 : if (real_isnan (rv))
370 : {
371 16110 : bool sign = real_isneg (rv);
372 16110 : f.set_nan (TREE_TYPE (expr), sign);
373 : }
374 : else
375 : {
376 4769576 : nan_state nan (false);
377 4769576 : f.set (TREE_TYPE (expr), *rv, *rv, nan);
378 : }
379 : return true;
380 : }
381 :
382 35389 : case SSA_NAME:
383 : // If this is not an abnormal or virtual ssa, invoke range_of_expr.
384 35389 : if (gimple_range_ssa_p (expr))
385 0 : return invoke_range_of_expr (r, expr, stmt, bbentry, bbexit, e);
386 35389 : gimple_range_global (r, expr);
387 35389 : return true;
388 :
389 10415199 : case ADDR_EXPR:
390 10415199 : {
391 : // Handle &expr, and set points to.
392 10415199 : if (tree_single_nonzero_p (expr))
393 10356929 : r.set_nonzero (type);
394 : else
395 58270 : r.set_varying (type);
396 : // Set points to field.
397 10415199 : gcc_checking_assert (is_a <prange> (r));
398 10415199 : prange &ptr = as_a <prange> (r);
399 10415199 : ptr.set_pt (expr, true);
400 10415199 : return true;
401 : }
402 :
403 38815299 : default:
404 38815299 : if (POLY_INT_CST_P (expr))
405 : {
406 : unsigned int precision = TYPE_PRECISION (type);
407 : r.set_varying (type);
408 : r.update_bitmask ({ wi::zero (precision), get_nonzero_bits (expr) });
409 : return true;
410 : }
411 38815299 : break;
412 : }
413 38815299 : if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr))
414 : {
415 11623417 : tree op0 = TREE_OPERAND (expr, 0);
416 11623417 : tree op1 = TREE_OPERAND (expr, 1);
417 11623417 : if (COMPARISON_CLASS_P (expr)
418 11623417 : && !value_range::supports_type_p (TREE_TYPE (op0)))
419 : return false;
420 11623417 : range_op_handler op (TREE_CODE (expr));
421 11623417 : if (op)
422 : {
423 11623417 : value_range r0 (TREE_TYPE (op0));
424 11623417 : value_range r1 (TREE_TYPE (op1));
425 11623417 : invoke_range_of_expr (r0, op0, stmt, bbentry, bbexit, e);
426 11623417 : invoke_range_of_expr (r1, op1, stmt, bbentry, bbexit, e);
427 11623417 : if (!op.fold_range (r, type, r0, r1))
428 0 : r.set_varying (type);
429 11623417 : }
430 : else
431 0 : r.set_varying (type);
432 11623417 : return true;
433 : }
434 27191882 : if (UNARY_CLASS_P (expr))
435 : {
436 7464664 : range_op_handler op (TREE_CODE (expr));
437 7464664 : tree op0_type = TREE_TYPE (TREE_OPERAND (expr, 0));
438 7464664 : if (op && value_range::supports_type_p (op0_type))
439 : {
440 7454639 : value_range r0 (TREE_TYPE (TREE_OPERAND (expr, 0)));
441 7454639 : value_range r1 (type);
442 7454639 : r1.set_varying (type);
443 7454639 : invoke_range_of_expr (r0, TREE_OPERAND (expr, 0), stmt, bbentry,
444 : bbexit, e);
445 7454639 : if (!op.fold_range (r, type, r0, r1))
446 0 : r.set_varying (type);
447 7454639 : }
448 : else
449 10025 : r.set_varying (type);
450 7464664 : return true;
451 : }
452 19727218 : r.set_varying (type);
453 19727218 : return true;
454 : }
455 :
456 : // Return the range for NAME from SSA_NAME_RANGE_INFO.
457 :
458 : static inline void
459 179274887 : get_ssa_name_range_info (vrange &r, const_tree name)
460 : {
461 179274887 : tree type = TREE_TYPE (name);
462 179274887 : gcc_checking_assert (!POINTER_TYPE_P (type));
463 179274887 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
464 :
465 179274887 : vrange_storage *ri = SSA_NAME_RANGE_INFO (name);
466 :
467 179274887 : if (ri)
468 163557561 : ri->get_vrange (r, TREE_TYPE (name));
469 : else
470 15717326 : r.set_varying (type);
471 179274887 : }
472 :
473 : // Return nonnull attribute of pointer NAME from SSA_NAME_PTR_INFO.
474 :
475 : static inline bool
476 95660335 : get_ssa_name_ptr_info_nonnull (const_tree name)
477 : {
478 95660335 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
479 95660335 : struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
480 95660335 : if (pi == NULL)
481 : return false;
482 : /* TODO Now pt->null is conservatively set to true in PTA
483 : analysis. vrp is the only pass (including ipa-vrp)
484 : that clears pt.null via set_ptr_nonnull when it knows
485 : for sure. PTA will preserves the pt.null value set by VRP.
486 :
487 : When PTA analysis is improved, pt.anything, pt.nonlocal
488 : and pt.escaped may also has to be considered before
489 : deciding that pointer cannot point to NULL. */
490 94430787 : return !pi->pt.null;
491 : }
492 :
493 : // Update the global range for NAME into the SSA_RANGE_NAME_INFO and
494 : // Return the legacy global range for NAME if it has one, otherwise
495 : // return VARYING.
496 : // See discussion here regarding why there use to be a wrapper function:
497 : // https://gcc.gnu.org/pipermail/gcc-patches/2021-June/571709.html
498 : // Legacy EVRP has been removed, leaving just this function.
499 :
500 : void
501 621280086 : gimple_range_global (vrange &r, tree name, struct function *fun)
502 : {
503 621280086 : tree type = TREE_TYPE (name);
504 621280086 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
505 :
506 621280086 : if (SSA_NAME_IS_DEFAULT_DEF (name))
507 : {
508 41242659 : tree sym = SSA_NAME_VAR (name);
509 : // Adapted from vr_values::get_lattice_entry().
510 : // Use a range from an SSA_NAME's available range.
511 41242659 : if (TREE_CODE (sym) == PARM_DECL)
512 : {
513 : // Try to use the "nonnull" attribute to create ~[0, 0]
514 : // anti-ranges for pointers. Note that this is only valid with
515 : // default definitions of PARM_DECLs.
516 38287654 : if (POINTER_TYPE_P (type)
517 38287654 : && ((cfun && fun == cfun && nonnull_arg_p (sym))
518 11349393 : || get_ssa_name_ptr_info_nonnull (name)))
519 11083343 : r.set_nonzero (type);
520 27204311 : else if (!POINTER_TYPE_P (type))
521 : {
522 16048979 : get_ssa_name_range_info (r, name);
523 16048979 : if (r.undefined_p ())
524 0 : r.set_varying (type);
525 : }
526 : else
527 11155332 : r.set_varying (type);
528 : }
529 : // If this is a local automatic with no definition, use undefined.
530 2955005 : else if (TREE_CODE (sym) != RESULT_DECL)
531 2627066 : r.set_undefined ();
532 : else
533 327939 : r.set_varying (type);
534 : }
535 580037427 : else if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name))
536 : {
537 163225908 : get_ssa_name_range_info (r, name);
538 163225908 : if (r.undefined_p ())
539 0 : r.set_varying (type);
540 : }
541 416811519 : else if (POINTER_TYPE_P (type) && SSA_NAME_PTR_INFO (name))
542 : {
543 84310942 : if (get_ssa_name_ptr_info_nonnull (name))
544 10973956 : r.set_nonzero (type);
545 : else
546 73336986 : r.set_varying (type);
547 : }
548 : else
549 332500577 : r.set_varying (type);
550 621280086 : }
551 :
552 : // ----------------------------------------------
553 : // global_range_query implementation.
554 :
555 : global_range_query global_ranges;
556 :
557 : bool
558 422108272 : global_range_query::range_of_expr (vrange &r, tree expr, gimple *stmt)
559 : {
560 422108272 : if (!gimple_range_ssa_p (expr))
561 118683602 : return get_tree_range (r, expr, stmt);
562 :
563 303424670 : gimple_range_global (r, expr);
564 :
565 303424670 : return true;
566 : }
|
