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 16025112 : range_query::range_on_edge (vrange &r, edge, tree expr)
40 : {
41 16025112 : 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 1458980 : range_query::range_of_stmt (vrange &r, gimple *stmt, tree name)
58 : {
59 1458980 : if (!name)
60 1458980 : name = gimple_get_lhs (stmt);
61 :
62 1458980 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
63 :
64 1458980 : if (name)
65 1458980 : return range_of_expr (r, name);
66 : return false;
67 : }
68 :
69 : // Default for updating range info is to do nothing.
70 : void
71 115441318 : range_query::update_range_info (tree)
72 : {
73 115441318 : }
74 :
75 : // Default for updating range info is to do nothing.
76 : void
77 4122775 : range_query::update_range_info (tree, const vrange &)
78 : {
79 4122775 : }
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 56819439 : range_query::value_of_expr (tree expr, gimple *stmt)
86 : {
87 56819439 : tree t;
88 :
89 56819439 : if (!value_range::supports_type_p (TREE_TYPE (expr)))
90 : return NULL_TREE;
91 :
92 56817574 : value_range r (TREE_TYPE (expr));
93 :
94 56817574 : 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 56817574 : if (r.undefined_p ())
99 21310 : range_of_expr (r, expr);
100 56817574 : if (r.singleton_p (&t))
101 1985360 : return t;
102 : }
103 : return NULL_TREE;
104 56817574 : }
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 11 : range_query::value_on_edge (edge e, tree expr)
111 : {
112 11 : tree t;
113 :
114 11 : if (!value_range::supports_type_p (TREE_TYPE (expr)))
115 : return NULL_TREE;
116 11 : value_range r (TREE_TYPE (expr));
117 11 : 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 11 : if (r.undefined_p ())
122 0 : range_of_expr (r, expr);
123 11 : if (r.singleton_p (&t))
124 3 : return t;
125 : }
126 : return NULL_TREE;
127 11 : }
128 :
129 : // If the range of STMT for NAME is a single value, return it.
130 : // Otherwise return NULL_TREE.
131 :
132 : tree
133 46939802 : range_query::value_of_stmt (gimple *stmt, tree name)
134 : {
135 46939802 : tree t;
136 :
137 46939802 : if (!name)
138 0 : name = gimple_get_lhs (stmt);
139 :
140 46939802 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
141 :
142 46939802 : if (!name || !value_range::supports_type_p (TREE_TYPE (name)))
143 1695649 : return NULL_TREE;
144 45244153 : value_range r (TREE_TYPE (name));
145 90488306 : if (range_of_stmt (r, stmt, name) && r.singleton_p (&t))
146 263371 : return t;
147 : return NULL_TREE;
148 45244153 : }
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 27888807 : range_query::create_gori (int not_executable_flag, int sw_max_edges)
201 : {
202 27888807 : gcc_checking_assert (m_gori == &default_gori);
203 27888807 : gcc_checking_assert (m_map == NULL);
204 27888807 : m_map = new gori_map ();
205 27888807 : gcc_checking_assert (m_map);
206 27888807 : m_gori = new gori_compute (*m_map, not_executable_flag, sw_max_edges);
207 27888807 : gcc_checking_assert (m_gori);
208 27888807 : }
209 :
210 : void
211 95331186 : range_query::destroy_gori ()
212 : {
213 95331186 : if (m_gori && m_gori != &default_gori)
214 27888805 : delete m_gori;
215 95331186 : if (m_map)
216 27888805 : delete m_map;
217 95331186 : m_map = NULL;
218 95331186 : m_gori= &default_gori;
219 95331186 : }
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 27888807 : range_query::create_infer_oracle (range_query *q, bool do_search)
229 : {
230 27888807 : gcc_checking_assert (m_infer == &default_infer_oracle);
231 27888807 : m_infer = new infer_range_manager (do_search, q);
232 27888807 : gcc_checking_assert (m_infer);
233 27888807 : }
234 :
235 : void
236 123219991 : range_query::destroy_infer_oracle ()
237 : {
238 123219991 : if (m_infer && m_infer != &default_infer_oracle)
239 27888805 : delete m_infer;
240 123219991 : m_infer = &default_infer_oracle;
241 123219991 : }
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 27888813 : range_query::create_relation_oracle (bool do_trans_p)
249 : {
250 27888813 : gcc_checking_assert (this != &global_ranges);
251 27888813 : gcc_checking_assert (m_relation == &default_relation_oracle);
252 :
253 27888813 : if (!dom_info_available_p (CDI_DOMINATORS))
254 : return;
255 25433051 : m_relation = new dom_oracle (do_trans_p);
256 25433051 : gcc_checking_assert (m_relation);
257 : }
258 :
259 : // Destroy any relation oracle that was created.
260 :
261 : void
262 123219997 : 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 123219997 : if (m_relation && m_relation != &default_relation_oracle)
267 : {
268 25433051 : delete m_relation;
269 25433051 : m_relation = &default_relation_oracle;
270 : }
271 123219997 : }
272 :
273 : void
274 55082179 : range_query::share_query (range_query &q)
275 : {
276 55082179 : m_relation = q.m_relation;
277 55082179 : m_infer = q.m_infer;
278 55082179 : m_gori = q.m_gori;
279 55082179 : m_map = q.m_map;
280 55082179 : m_shared_copy_p = true;
281 55082179 : }
282 :
283 150413378 : range_query::range_query ()
284 : {
285 150413378 : m_relation = &default_relation_oracle;
286 150413378 : m_infer = &default_infer_oracle;
287 150413378 : m_gori = &default_gori;
288 150413378 : m_map = NULL;
289 150413378 : m_shared_copy_p = false;
290 150413378 : }
291 :
292 150413363 : range_query::~range_query ()
293 : {
294 : // Do not destroy anything if this is a shared copy.
295 150413363 : if (m_shared_copy_p)
296 55082177 : return;
297 95331186 : destroy_gori ();
298 95331186 : destroy_infer_oracle ();
299 95331186 : destroy_relation_oracle ();
300 150413363 : }
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 31253413 : range_query::invoke_range_of_expr (vrange &r, tree expr, gimple *stmt,
309 : basic_block bbentry, basic_block bbexit,
310 : edge e)
311 : {
312 31253413 : if (bbentry)
313 : {
314 0 : gcc_checking_assert (!stmt && !bbexit && !e);
315 0 : return range_on_entry (r, bbentry, expr);
316 : }
317 31253413 : if (bbexit)
318 : {
319 0 : gcc_checking_assert (!stmt && !e);
320 0 : return range_on_exit (r, bbexit, expr);
321 : }
322 31253413 : if (e)
323 : {
324 2641342 : gcc_checking_assert (!stmt);
325 2641342 : return range_on_edge (r, e, expr);
326 : }
327 :
328 28612071 : 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 298930437 : range_query::get_tree_range (vrange &r, tree expr, gimple *stmt,
337 : basic_block bbentry, basic_block bbexit, edge e)
338 : {
339 298930437 : tree type;
340 298930437 : if (TYPE_P (expr))
341 : type = expr;
342 : else
343 298930437 : type = TREE_TYPE (expr);
344 :
345 298930437 : if (!r.supports_type_p (type))
346 : {
347 19745304 : r.set_undefined ();
348 19745304 : return false;
349 : }
350 279185133 : if (expr == type)
351 : {
352 0 : r.set_varying (type);
353 0 : return true;
354 : }
355 279185133 : switch (TREE_CODE (expr))
356 : {
357 226334035 : case INTEGER_CST:
358 226334035 : {
359 226334035 : if (TREE_OVERFLOW_P (expr))
360 116 : expr = drop_tree_overflow (expr);
361 226334035 : r.set (expr, expr);
362 226334035 : return true;
363 : }
364 :
365 4848133 : case REAL_CST:
366 4848133 : {
367 4848133 : frange &f = as_a <frange> (r);
368 4848133 : REAL_VALUE_TYPE *rv = TREE_REAL_CST_PTR (expr);
369 4848133 : 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 4832050 : nan_state nan (false);
377 4832050 : f.set (TREE_TYPE (expr), *rv, *rv, nan);
378 : }
379 : return true;
380 : }
381 :
382 35433 : case SSA_NAME:
383 : // If this is not an abnormal or virtual ssa, invoke range_of_expr.
384 35433 : if (gimple_range_ssa_p (expr))
385 0 : return invoke_range_of_expr (r, expr, stmt, bbentry, bbexit, e);
386 35433 : gimple_range_global (r, expr);
387 35433 : return true;
388 :
389 9945023 : case ADDR_EXPR:
390 9945023 : {
391 : // Handle &expr, and set points to.
392 9945023 : if (tree_single_nonzero_p (expr))
393 9886849 : r.set_nonzero (type);
394 : else
395 58174 : r.set_varying (type);
396 : // Set points to field.
397 9945023 : gcc_checking_assert (is_a <prange> (r));
398 9945023 : prange &ptr = as_a <prange> (r);
399 9945023 : ptr.set_pt (expr, true);
400 9945023 : return true;
401 : }
402 :
403 38022509 : default:
404 38022509 : 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 38022509 : break;
412 : }
413 38022509 : if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr))
414 : {
415 11856135 : tree op0 = TREE_OPERAND (expr, 0);
416 11856135 : tree op1 = TREE_OPERAND (expr, 1);
417 11856135 : if (COMPARISON_CLASS_P (expr)
418 11856135 : && !value_range::supports_type_p (TREE_TYPE (op0)))
419 : return false;
420 11856135 : range_op_handler op (TREE_CODE (expr));
421 11856135 : if (op)
422 : {
423 11856135 : value_range r0 (TREE_TYPE (op0));
424 11856135 : value_range r1 (TREE_TYPE (op1));
425 11856135 : invoke_range_of_expr (r0, op0, stmt, bbentry, bbexit, e);
426 11856135 : invoke_range_of_expr (r1, op1, stmt, bbentry, bbexit, e);
427 11856135 : if (!op.fold_range (r, type, r0, r1))
428 0 : r.set_varying (type);
429 11856135 : }
430 : else
431 0 : r.set_varying (type);
432 11856135 : return true;
433 : }
434 26166374 : if (UNARY_CLASS_P (expr))
435 : {
436 7551085 : range_op_handler op (TREE_CODE (expr));
437 7551085 : tree op0_type = TREE_TYPE (TREE_OPERAND (expr, 0));
438 7551085 : if (op && value_range::supports_type_p (op0_type))
439 : {
440 7541143 : value_range r0 (TREE_TYPE (TREE_OPERAND (expr, 0)));
441 7541143 : value_range r1 (type);
442 7541143 : r1.set_varying (type);
443 7541143 : invoke_range_of_expr (r0, TREE_OPERAND (expr, 0), stmt, bbentry,
444 : bbexit, e);
445 7541143 : if (!op.fold_range (r, type, r0, r1))
446 0 : r.set_varying (type);
447 7541143 : }
448 : else
449 9942 : r.set_varying (type);
450 7551085 : return true;
451 : }
452 18615289 : r.set_varying (type);
453 18615289 : return true;
454 : }
455 :
456 : // Return the range for NAME from SSA_NAME_RANGE_INFO.
457 :
458 : static inline void
459 175972203 : get_ssa_name_range_info (vrange &r, const_tree name)
460 : {
461 175972203 : tree type = TREE_TYPE (name);
462 175972203 : gcc_checking_assert (!POINTER_TYPE_P (type));
463 175972203 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
464 :
465 175972203 : vrange_storage *ri = SSA_NAME_RANGE_INFO (name);
466 :
467 175972203 : if (ri)
468 160584633 : ri->get_vrange (r, TREE_TYPE (name));
469 : else
470 15387570 : r.set_varying (type);
471 175972203 : }
472 :
473 : // Return nonnull attribute of pointer NAME from SSA_NAME_PTR_INFO.
474 :
475 : static inline bool
476 92045981 : get_ssa_name_ptr_info_nonnull (const_tree name)
477 : {
478 92045981 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
479 92045981 : struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
480 92045981 : 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 90850403 : 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 605431583 : gimple_range_global (vrange &r, tree name, struct function *fun)
502 : {
503 605431583 : tree type = TREE_TYPE (name);
504 605431583 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
505 :
506 605431583 : if (SSA_NAME_IS_DEFAULT_DEF (name))
507 : {
508 39777316 : 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 39777316 : 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 36942009 : if (POINTER_TYPE_P (type)
517 36942009 : && ((cfun && fun == cfun && nonnull_arg_p (sym))
518 11114395 : || get_ssa_name_ptr_info_nonnull (name)))
519 10300588 : r.set_nonzero (type);
520 26641421 : else if (!POINTER_TYPE_P (type))
521 : {
522 15720622 : get_ssa_name_range_info (r, name);
523 15720622 : if (r.undefined_p ())
524 0 : r.set_varying (type);
525 : }
526 : else
527 10920799 : r.set_varying (type);
528 : }
529 : // If this is a local automatic with no definition, use undefined.
530 2835307 : else if (TREE_CODE (sym) != RESULT_DECL)
531 2524735 : r.set_undefined ();
532 : else
533 310572 : r.set_varying (type);
534 : }
535 565654267 : else if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name))
536 : {
537 160251581 : get_ssa_name_range_info (r, name);
538 160251581 : if (r.undefined_p ())
539 0 : r.set_varying (type);
540 : }
541 405402686 : else if (POINTER_TYPE_P (type) && SSA_NAME_PTR_INFO (name))
542 : {
543 80931586 : if (get_ssa_name_ptr_info_nonnull (name))
544 10496981 : r.set_nonzero (type);
545 : else
546 70434605 : r.set_varying (type);
547 : }
548 : else
549 324471100 : r.set_varying (type);
550 605431583 : }
551 :
552 : // ----------------------------------------------
553 : // global_range_query implementation.
554 :
555 : global_range_query global_ranges;
556 :
557 : bool
558 412810009 : global_range_query::range_of_expr (vrange &r, tree expr, gimple *stmt)
559 : {
560 412810009 : if (!gimple_range_ssa_p (expr))
561 116394317 : return get_tree_range (r, expr, stmt);
562 :
563 296415692 : gimple_range_global (r, expr);
564 :
565 296415692 : return true;
566 : }
|
