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 10802043 : range_query::range_on_edge (vrange &r, edge, tree expr)
40 : {
41 10802043 : 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 1655078 : range_query::range_of_stmt (vrange &r, gimple *stmt, tree name)
58 : {
59 1655078 : if (!name)
60 1655078 : name = gimple_get_lhs (stmt);
61 :
62 1655078 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
63 :
64 1655078 : if (name)
65 1655078 : return range_of_expr (r, name);
66 : return false;
67 : }
68 :
69 : // Default for updating range info is to do nothing.
70 : void
71 4191231 : range_query::update_range_info (tree, const vrange &)
72 : {
73 4191231 : }
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 153463299 : range_query::value_of_expr (tree expr, gimple *stmt)
80 : {
81 153463299 : tree t;
82 :
83 153463299 : if (!value_range::supports_type_p (TREE_TYPE (expr)))
84 : return NULL_TREE;
85 :
86 150615450 : value_range r (TREE_TYPE (expr));
87 :
88 150615450 : 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 150615450 : if (r.undefined_p ())
93 230095 : range_of_expr (r, expr);
94 150615450 : if (r.singleton_p (&t))
95 1646315 : return t;
96 : }
97 : return NULL_TREE;
98 150615450 : }
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 25018625 : range_query::value_on_edge (edge e, tree expr)
105 : {
106 25018625 : tree t;
107 :
108 25018625 : if (!value_range::supports_type_p (TREE_TYPE (expr)))
109 : return NULL_TREE;
110 24754045 : value_range r (TREE_TYPE (expr));
111 24754045 : 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 24754045 : if (r.undefined_p ())
116 281005 : range_of_expr (r, expr);
117 24754045 : if (r.singleton_p (&t))
118 357757 : return t;
119 : }
120 : return NULL_TREE;
121 24754045 : }
122 :
123 : // If the range of STMT for NAME is a single value, return it.
124 : // Otherwise return NULL_TREE.
125 :
126 : tree
127 47657646 : range_query::value_of_stmt (gimple *stmt, tree name)
128 : {
129 47657646 : tree t;
130 :
131 47657646 : if (!name)
132 0 : name = gimple_get_lhs (stmt);
133 :
134 47657646 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
135 :
136 47657646 : if (!name || !value_range::supports_type_p (TREE_TYPE (name)))
137 1688584 : return NULL_TREE;
138 45969062 : value_range r (TREE_TYPE (name));
139 91938124 : if (range_of_stmt (r, stmt, name) && r.singleton_p (&t))
140 285014 : return t;
141 : return NULL_TREE;
142 45969062 : }
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 28136694 : range_query::create_gori (int not_executable_flag, int sw_max_edges)
195 : {
196 28136694 : gcc_checking_assert (m_gori == &default_gori);
197 28136694 : gcc_checking_assert (m_map == NULL);
198 28136694 : m_map = new gori_map ();
199 28136694 : gcc_checking_assert (m_map);
200 28136694 : m_gori = new gori_compute (*m_map, not_executable_flag, sw_max_edges);
201 28136694 : gcc_checking_assert (m_gori);
202 28136694 : }
203 :
204 : void
205 98296132 : range_query::destroy_gori ()
206 : {
207 98296132 : if (m_gori && m_gori != &default_gori)
208 28136693 : delete m_gori;
209 98296132 : if (m_map)
210 28136693 : delete m_map;
211 98296132 : m_map = NULL;
212 98296132 : m_gori= &default_gori;
213 98296132 : }
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 28136694 : range_query::create_infer_oracle (range_query *q, bool do_search)
223 : {
224 28136694 : gcc_checking_assert (m_infer == &default_infer_oracle);
225 28136694 : m_infer = new infer_range_manager (do_search, q);
226 28136694 : gcc_checking_assert (m_infer);
227 28136694 : }
228 :
229 : void
230 126432825 : range_query::destroy_infer_oracle ()
231 : {
232 126432825 : if (m_infer && m_infer != &default_infer_oracle)
233 28136693 : delete m_infer;
234 126432825 : m_infer = &default_infer_oracle;
235 126432825 : }
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 28136700 : range_query::create_relation_oracle (bool do_trans_p)
243 : {
244 28136700 : gcc_checking_assert (this != &global_ranges);
245 28136700 : gcc_checking_assert (m_relation == &default_relation_oracle);
246 :
247 28136700 : if (!dom_info_available_p (CDI_DOMINATORS))
248 : return;
249 25685811 : m_relation = new dom_oracle (do_trans_p);
250 25685811 : gcc_checking_assert (m_relation);
251 : }
252 :
253 : // Destroy any relation oracle that was created.
254 :
255 : void
256 126432831 : 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 126432831 : if (m_relation && m_relation != &default_relation_oracle)
261 : {
262 25685811 : delete m_relation;
263 25685811 : m_relation = &default_relation_oracle;
264 : }
265 126432831 : }
266 :
267 : void
268 57664993 : range_query::share_query (range_query &q)
269 : {
270 57664993 : m_relation = q.m_relation;
271 57664993 : m_infer = q.m_infer;
272 57664993 : m_gori = q.m_gori;
273 57664993 : m_map = q.m_map;
274 57664993 : m_shared_copy_p = true;
275 57664993 : }
276 :
277 155961136 : range_query::range_query ()
278 : {
279 155961136 : m_relation = &default_relation_oracle;
280 155961136 : m_infer = &default_infer_oracle;
281 155961136 : m_gori = &default_gori;
282 155961136 : m_map = NULL;
283 155961136 : m_shared_copy_p = false;
284 155961136 : }
285 :
286 155961124 : range_query::~range_query ()
287 : {
288 : // Do not destroy anything if this is a shared copy.
289 155961124 : if (m_shared_copy_p)
290 57664992 : return;
291 98296132 : destroy_gori ();
292 98296132 : destroy_infer_oracle ();
293 98296132 : destroy_relation_oracle ();
294 155961124 : }
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 28562597 : range_query::invoke_range_of_expr (vrange &r, tree expr, gimple *stmt,
303 : basic_block bbentry, basic_block bbexit,
304 : edge e)
305 : {
306 28562597 : if (bbentry)
307 : {
308 0 : gcc_checking_assert (!stmt && !bbexit && !e);
309 0 : return range_on_entry (r, bbentry, expr);
310 : }
311 28562597 : if (bbexit)
312 : {
313 0 : gcc_checking_assert (!stmt && !e);
314 0 : return range_on_exit (r, bbexit, expr);
315 : }
316 28562597 : if (e)
317 : {
318 2157075 : gcc_checking_assert (!stmt);
319 2157075 : return range_on_edge (r, e, expr);
320 : }
321 :
322 26405522 : 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 306456064 : range_query::get_tree_range (vrange &r, tree expr, gimple *stmt,
331 : basic_block bbentry, basic_block bbexit, edge e)
332 : {
333 306456064 : tree type;
334 306456064 : if (TYPE_P (expr))
335 : type = expr;
336 : else
337 306456064 : type = TREE_TYPE (expr);
338 :
339 306456064 : if (!value_range::supports_type_p (type))
340 : {
341 19904580 : r.set_undefined ();
342 19904580 : return false;
343 : }
344 286551484 : if (expr == type)
345 : {
346 0 : r.set_varying (type);
347 0 : return true;
348 : }
349 286551484 : switch (TREE_CODE (expr))
350 : {
351 235215340 : case INTEGER_CST:
352 235215340 : {
353 235215340 : if (TREE_OVERFLOW_P (expr))
354 172 : expr = drop_tree_overflow (expr);
355 235215340 : r.set (expr, expr);
356 235215340 : return true;
357 : }
358 :
359 4926997 : case REAL_CST:
360 4926997 : {
361 4926997 : frange &f = as_a <frange> (r);
362 4926997 : REAL_VALUE_TYPE *rv = TREE_REAL_CST_PTR (expr);
363 4926997 : 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 4911038 : nan_state nan (false);
371 4911038 : 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 10287262 : case ADDR_EXPR:
384 10287262 : {
385 : // Handle &var which can show up in phi arguments.
386 10287262 : bool ov;
387 10287262 : if (tree_single_nonzero_warnv_p (expr, &ov))
388 : {
389 10229472 : r.set_nonzero (type);
390 10229472 : return true;
391 : }
392 57790 : 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 36145409 : if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr))
406 : {
407 11277063 : tree op0 = TREE_OPERAND (expr, 0);
408 11277063 : tree op1 = TREE_OPERAND (expr, 1);
409 11277063 : if (COMPARISON_CLASS_P (expr)
410 11277063 : && !value_range::supports_type_p (TREE_TYPE (op0)))
411 : return false;
412 11277063 : range_op_handler op (TREE_CODE (expr));
413 11277063 : if (op)
414 : {
415 11277063 : value_range r0 (TREE_TYPE (op0));
416 11277063 : value_range r1 (TREE_TYPE (op1));
417 11277063 : invoke_range_of_expr (r0, op0, stmt, bbentry, bbexit, e);
418 11277063 : invoke_range_of_expr (r1, op1, stmt, bbentry, bbexit, e);
419 11277063 : if (!op.fold_range (r, type, r0, r1))
420 0 : r.set_varying (type);
421 11277063 : }
422 : else
423 0 : r.set_varying (type);
424 11277063 : return true;
425 : }
426 24868346 : if (UNARY_CLASS_P (expr))
427 : {
428 6018228 : range_op_handler op (TREE_CODE (expr));
429 6018228 : tree op0_type = TREE_TYPE (TREE_OPERAND (expr, 0));
430 6018228 : if (op && value_range::supports_type_p (op0_type))
431 : {
432 6008471 : value_range r0 (TREE_TYPE (TREE_OPERAND (expr, 0)));
433 6008471 : value_range r1 (type);
434 6008471 : r1.set_varying (type);
435 6008471 : invoke_range_of_expr (r0, TREE_OPERAND (expr, 0), stmt, bbentry,
436 : bbexit, e);
437 6008471 : if (!op.fold_range (r, type, r0, r1))
438 0 : r.set_varying (type);
439 6008471 : }
440 : else
441 9757 : r.set_varying (type);
442 6018228 : return true;
443 : }
444 18850118 : r.set_varying (type);
445 18850118 : return true;
446 : }
447 :
448 : // Return the range for NAME from SSA_NAME_RANGE_INFO.
449 :
450 : static inline void
451 178698818 : get_ssa_name_range_info (vrange &r, const_tree name)
452 : {
453 178698818 : tree type = TREE_TYPE (name);
454 178698818 : gcc_checking_assert (!POINTER_TYPE_P (type));
455 178698818 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
456 :
457 178698818 : vrange_storage *ri = SSA_NAME_RANGE_INFO (name);
458 :
459 178698818 : if (ri)
460 162991602 : ri->get_vrange (r, TREE_TYPE (name));
461 : else
462 15707216 : r.set_varying (type);
463 178698818 : }
464 :
465 : // Return nonnull attribute of pointer NAME from SSA_NAME_PTR_INFO.
466 :
467 : static inline bool
468 94914520 : get_ssa_name_ptr_info_nonnull (const_tree name)
469 : {
470 94914520 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
471 94914520 : struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
472 94914520 : 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 93698771 : 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 616546645 : gimple_range_global (vrange &r, tree name, struct function *fun)
494 : {
495 616546645 : tree type = TREE_TYPE (name);
496 616546645 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
497 :
498 616546645 : if (SSA_NAME_IS_DEFAULT_DEF (name))
499 : {
500 40605982 : 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 40605982 : 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 37736157 : if (POINTER_TYPE_P (type)
509 37736157 : && ((cfun && fun == cfun && nonnull_arg_p (sym))
510 11250195 : || get_ssa_name_ptr_info_nonnull (name)))
511 10636249 : r.set_nonzero (type);
512 27099908 : else if (!POINTER_TYPE_P (type))
513 : {
514 16043819 : get_ssa_name_range_info (r, name);
515 16043819 : if (r.undefined_p ())
516 0 : r.set_varying (type);
517 : }
518 : else
519 11056089 : r.set_varying (type);
520 : }
521 : // If this is a local automatic with no definition, use undefined.
522 2869825 : else if (TREE_CODE (sym) != RESULT_DECL)
523 2550415 : r.set_undefined ();
524 : else
525 319410 : r.set_varying (type);
526 : }
527 575940663 : else if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name))
528 : {
529 162654999 : get_ssa_name_range_info (r, name);
530 162654999 : if (r.undefined_p ())
531 0 : r.set_varying (type);
532 : }
533 413285664 : else if (POINTER_TYPE_P (type) && SSA_NAME_PTR_INFO (name))
534 : {
535 83664325 : if (get_ssa_name_ptr_info_nonnull (name))
536 11440836 : r.set_nonzero (type);
537 : else
538 72223489 : r.set_varying (type);
539 : }
540 : else
541 329621339 : r.set_varying (type);
542 616546645 : }
543 :
544 : // ----------------------------------------------
545 : // global_range_query implementation.
546 :
547 : global_range_query global_ranges;
548 :
549 : bool
550 418068286 : global_range_query::range_of_expr (vrange &r, tree expr, gimple *stmt)
551 : {
552 418068286 : if (!gimple_range_ssa_p (expr))
553 121322889 : return get_tree_range (r, expr, stmt);
554 :
555 296745397 : gimple_range_global (r, expr);
556 :
557 296745397 : return true;
558 : }
|
