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