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 : 10795383 : range_query::range_on_edge (vrange &r, edge, tree expr)
40 : : {
41 : 10795383 : 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 : 1669677 : range_query::range_of_stmt (vrange &r, gimple *stmt, tree name)
58 : : {
59 : 1669677 : if (!name)
60 : 1669677 : name = gimple_get_lhs (stmt);
61 : :
62 : 1669677 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
63 : :
64 : 1669677 : if (name)
65 : 1669677 : return range_of_expr (r, name);
66 : : return false;
67 : : }
68 : :
69 : : // Default for updating range info is to do nothing.
70 : : void
71 : 4142283 : range_query::update_range_info (tree, const vrange &)
72 : : {
73 : 4142283 : }
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 : 151600599 : range_query::value_of_expr (tree expr, gimple *stmt)
80 : : {
81 : 151600599 : tree t;
82 : :
83 : 151600599 : if (!value_range::supports_type_p (TREE_TYPE (expr)))
84 : : return NULL_TREE;
85 : :
86 : 148949847 : value_range r (TREE_TYPE (expr));
87 : :
88 : 148949847 : 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 : 148949847 : if (r.undefined_p ())
93 : 221559 : range_of_expr (r, expr);
94 : 148949847 : if (r.singleton_p (&t))
95 : 1609309 : return t;
96 : : }
97 : : return NULL_TREE;
98 : 148949847 : }
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 : 25362569 : range_query::value_on_edge (edge e, tree expr)
105 : : {
106 : 25362569 : tree t;
107 : :
108 : 25362569 : if (!value_range::supports_type_p (TREE_TYPE (expr)))
109 : : return NULL_TREE;
110 : 25112403 : value_range r (TREE_TYPE (expr));
111 : 25112403 : 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 : 25112403 : if (r.undefined_p ())
116 : 270914 : range_of_expr (r, expr);
117 : 25112403 : if (r.singleton_p (&t))
118 : 367912 : return t;
119 : : }
120 : : return NULL_TREE;
121 : 25112403 : }
122 : :
123 : : // If the range of STMT for NAME is a single value, return it.
124 : : // Otherwise return NULL_TREE.
125 : :
126 : : tree
127 : 47867484 : range_query::value_of_stmt (gimple *stmt, tree name)
128 : : {
129 : 47867484 : tree t;
130 : :
131 : 47867484 : if (!name)
132 : 0 : name = gimple_get_lhs (stmt);
133 : :
134 : 47867484 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
135 : :
136 : 47867484 : if (!name || !value_range::supports_type_p (TREE_TYPE (name)))
137 : 1629431 : return NULL_TREE;
138 : 46238053 : value_range r (TREE_TYPE (name));
139 : 92476106 : if (range_of_stmt (r, stmt, name) && r.singleton_p (&t))
140 : 266670 : return t;
141 : : return NULL_TREE;
142 : 46238053 : }
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 : 28199083 : range_query::create_gori (int not_executable_flag, int sw_max_edges)
195 : : {
196 : 28199083 : gcc_checking_assert (m_gori == &default_gori);
197 : 28199083 : gcc_checking_assert (m_map == NULL);
198 : 28199083 : m_map = new gori_map ();
199 : 28199083 : gcc_checking_assert (m_map);
200 : 28199083 : m_gori = new gori_compute (*m_map, not_executable_flag, sw_max_edges);
201 : 28199083 : gcc_checking_assert (m_gori);
202 : 28199083 : }
203 : :
204 : : void
205 : 97722745 : range_query::destroy_gori ()
206 : : {
207 : 97722745 : if (m_gori && m_gori != &default_gori)
208 : 28199083 : delete m_gori;
209 : 97722745 : if (m_map)
210 : 28199083 : delete m_map;
211 : 97722745 : m_map = NULL;
212 : 97722745 : m_gori= &default_gori;
213 : 97722745 : }
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 : 28199083 : range_query::create_infer_oracle (range_query *q, bool do_search)
223 : : {
224 : 28199083 : gcc_checking_assert (m_infer == &default_infer_oracle);
225 : 28199083 : m_infer = new infer_range_manager (do_search, q);
226 : 28199083 : gcc_checking_assert (m_infer);
227 : 28199083 : }
228 : :
229 : : void
230 : 125921828 : range_query::destroy_infer_oracle ()
231 : : {
232 : 125921828 : if (m_infer && m_infer != &default_infer_oracle)
233 : 28199083 : delete m_infer;
234 : 125921828 : m_infer = &default_infer_oracle;
235 : 125921828 : }
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 : 28199089 : range_query::create_relation_oracle (bool do_trans_p)
243 : : {
244 : 28199089 : gcc_checking_assert (this != &global_ranges);
245 : 28199089 : gcc_checking_assert (m_relation == &default_relation_oracle);
246 : :
247 : 28199089 : if (!dom_info_available_p (CDI_DOMINATORS))
248 : : return;
249 : 25765349 : m_relation = new dom_oracle (do_trans_p);
250 : 25765349 : gcc_checking_assert (m_relation);
251 : : }
252 : :
253 : : // Destroy any relation oracle that was created.
254 : :
255 : : void
256 : 125921834 : 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 : 125921834 : if (m_relation && m_relation != &default_relation_oracle)
261 : : {
262 : 25765349 : delete m_relation;
263 : 25765349 : m_relation = &default_relation_oracle;
264 : : }
265 : 125921834 : }
266 : :
267 : : void
268 : 56990113 : range_query::share_query (range_query &q)
269 : : {
270 : 56990113 : m_relation = q.m_relation;
271 : 56990113 : m_infer = q.m_infer;
272 : 56990113 : m_gori = q.m_gori;
273 : 56990113 : m_map = q.m_map;
274 : 56990113 : m_shared_copy_p = true;
275 : 56990113 : }
276 : :
277 : 154712867 : range_query::range_query ()
278 : : {
279 : 154712867 : m_relation = &default_relation_oracle;
280 : 154712867 : m_infer = &default_infer_oracle;
281 : 154712867 : m_gori = &default_gori;
282 : 154712867 : m_map = NULL;
283 : 154712867 : m_shared_copy_p = false;
284 : 154712867 : }
285 : :
286 : 154712858 : range_query::~range_query ()
287 : : {
288 : : // Do not destroy anything if this is a shared copy.
289 : 154712858 : if (m_shared_copy_p)
290 : 56990113 : return;
291 : 97722745 : destroy_gori ();
292 : 97722745 : destroy_infer_oracle ();
293 : 97722745 : destroy_relation_oracle ();
294 : 154712858 : }
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 : 28576397 : range_query::invoke_range_of_expr (vrange &r, tree expr, gimple *stmt,
303 : : basic_block bbentry, basic_block bbexit,
304 : : edge e)
305 : : {
306 : 28576397 : if (bbentry)
307 : : {
308 : 0 : gcc_checking_assert (!stmt && !bbexit && !e);
309 : 0 : return range_on_entry (r, bbentry, expr);
310 : : }
311 : 28576397 : if (bbexit)
312 : : {
313 : 0 : gcc_checking_assert (!stmt && !e);
314 : 0 : return range_on_exit (r, bbexit, expr);
315 : : }
316 : 28576397 : if (e)
317 : : {
318 : 2189525 : gcc_checking_assert (!stmt);
319 : 2189525 : return range_on_edge (r, e, expr);
320 : : }
321 : :
322 : 26386872 : 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 : 303604953 : range_query::get_tree_range (vrange &r, tree expr, gimple *stmt,
331 : : basic_block bbentry, basic_block bbexit, edge e)
332 : : {
333 : 303604953 : tree type;
334 : 303604953 : if (TYPE_P (expr))
335 : : type = expr;
336 : : else
337 : 303604953 : type = TREE_TYPE (expr);
338 : :
339 : 303604953 : if (!value_range::supports_type_p (type))
340 : : {
341 : 20083713 : r.set_undefined ();
342 : 20083713 : return false;
343 : : }
344 : 283521240 : if (expr == type)
345 : : {
346 : 0 : r.set_varying (type);
347 : 0 : return true;
348 : : }
349 : 283521240 : switch (TREE_CODE (expr))
350 : : {
351 : 231967960 : case INTEGER_CST:
352 : 231967960 : {
353 : 231967960 : if (TREE_OVERFLOW_P (expr))
354 : 148 : expr = drop_tree_overflow (expr);
355 : 231967960 : r.set (expr, expr);
356 : 231967960 : return true;
357 : : }
358 : :
359 : 4953119 : case REAL_CST:
360 : 4953119 : {
361 : 4953119 : frange &f = as_a <frange> (r);
362 : 4953119 : REAL_VALUE_TYPE *rv = TREE_REAL_CST_PTR (expr);
363 : 4953119 : if (real_isnan (rv))
364 : : {
365 : 16037 : bool sign = real_isneg (rv);
366 : 16037 : f.set_nan (TREE_TYPE (expr), sign);
367 : : }
368 : : else
369 : : {
370 : 4937082 : nan_state nan (false);
371 : 4937082 : f.set (TREE_TYPE (expr), *rv, *rv, nan);
372 : : }
373 : : return true;
374 : : }
375 : :
376 : 33321 : case SSA_NAME:
377 : : // If this is not an abnormal or virtual ssa, invoke range_of_expr.
378 : 33321 : if (gimple_range_ssa_p (expr))
379 : 0 : return invoke_range_of_expr (r, expr, stmt, bbentry, bbexit, e);
380 : 33321 : gimple_range_global (r, expr);
381 : 33321 : return true;
382 : :
383 : 10273707 : case ADDR_EXPR:
384 : 10273707 : {
385 : : // Handle &var which can show up in phi arguments.
386 : 10273707 : bool ov;
387 : 10273707 : if (tree_single_nonzero_warnv_p (expr, &ov))
388 : : {
389 : 10216437 : r.set_nonzero (type);
390 : 10216437 : return true;
391 : : }
392 : 57270 : 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 : 36350403 : if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr))
406 : : {
407 : 11279230 : tree op0 = TREE_OPERAND (expr, 0);
408 : 11279230 : tree op1 = TREE_OPERAND (expr, 1);
409 : 11279230 : if (COMPARISON_CLASS_P (expr)
410 : 11279230 : && !value_range::supports_type_p (TREE_TYPE (op0)))
411 : : return false;
412 : 11279230 : range_op_handler op (TREE_CODE (expr));
413 : 11279230 : if (op)
414 : : {
415 : 11279230 : value_range r0 (TREE_TYPE (op0));
416 : 11279230 : value_range r1 (TREE_TYPE (op1));
417 : 11279230 : invoke_range_of_expr (r0, op0, stmt, bbentry, bbexit, e);
418 : 11279230 : invoke_range_of_expr (r1, op1, stmt, bbentry, bbexit, e);
419 : 11279230 : if (!op.fold_range (r, type, r0, r1))
420 : 0 : r.set_varying (type);
421 : 11279230 : }
422 : : else
423 : 0 : r.set_varying (type);
424 : 11279230 : return true;
425 : : }
426 : 25071173 : if (UNARY_CLASS_P (expr))
427 : : {
428 : 6027618 : range_op_handler op (TREE_CODE (expr));
429 : 6027618 : tree op0_type = TREE_TYPE (TREE_OPERAND (expr, 0));
430 : 6027618 : if (op && value_range::supports_type_p (op0_type))
431 : : {
432 : 6017937 : value_range r0 (TREE_TYPE (TREE_OPERAND (expr, 0)));
433 : 6017937 : value_range r1 (type);
434 : 6017937 : r1.set_varying (type);
435 : 6017937 : invoke_range_of_expr (r0, TREE_OPERAND (expr, 0), stmt, bbentry,
436 : : bbexit, e);
437 : 6017937 : if (!op.fold_range (r, type, r0, r1))
438 : 0 : r.set_varying (type);
439 : 6017937 : }
440 : : else
441 : 9681 : r.set_varying (type);
442 : 6027618 : return true;
443 : : }
444 : 19043555 : r.set_varying (type);
445 : 19043555 : return true;
446 : : }
447 : :
448 : : // Return the range for NAME from SSA_NAME_RANGE_INFO.
449 : :
450 : : static inline void
451 : 172929297 : get_ssa_name_range_info (vrange &r, const_tree name)
452 : : {
453 : 172929297 : tree type = TREE_TYPE (name);
454 : 172929297 : gcc_checking_assert (!POINTER_TYPE_P (type));
455 : 172929297 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
456 : :
457 : 172929297 : vrange_storage *ri = SSA_NAME_RANGE_INFO (name);
458 : :
459 : 172929297 : if (ri)
460 : 157448724 : ri->get_vrange (r, TREE_TYPE (name));
461 : : else
462 : 15480573 : r.set_varying (type);
463 : 172929297 : }
464 : :
465 : : // Return nonnull attribute of pointer NAME from SSA_NAME_PTR_INFO.
466 : :
467 : : static inline bool
468 : 94658744 : get_ssa_name_ptr_info_nonnull (const_tree name)
469 : : {
470 : 94658744 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
471 : 94658744 : struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
472 : 94658744 : 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 : 93471281 : 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 : 611405741 : gimple_range_global (vrange &r, tree name, struct function *fun)
494 : : {
495 : 611405741 : tree type = TREE_TYPE (name);
496 : 611405741 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
497 : :
498 : 611405741 : if (SSA_NAME_IS_DEFAULT_DEF (name))
499 : : {
500 : 40490066 : 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 : 40490066 : 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 : 37602806 : if (POINTER_TYPE_P (type)
509 : 37602806 : && ((cfun && fun == cfun && nonnull_arg_p (sym))
510 : 11112886 : || get_ssa_name_ptr_info_nonnull (name)))
511 : 10865599 : r.set_nonzero (type);
512 : 26737207 : else if (!POINTER_TYPE_P (type))
513 : : {
514 : 15812416 : get_ssa_name_range_info (r, name);
515 : 15812416 : if (r.undefined_p ())
516 : 0 : r.set_varying (type);
517 : : }
518 : : else
519 : 10924791 : r.set_varying (type);
520 : : }
521 : : // If this is a local automatic with no definition, use undefined.
522 : 2887260 : else if (TREE_CODE (sym) != RESULT_DECL)
523 : 2561199 : r.set_undefined ();
524 : : else
525 : 326061 : r.set_varying (type);
526 : : }
527 : 570915675 : else if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name))
528 : : {
529 : 157116881 : get_ssa_name_range_info (r, name);
530 : 157116881 : if (r.undefined_p ())
531 : 0 : r.set_varying (type);
532 : : }
533 : 413798794 : else if (POINTER_TYPE_P (type) && SSA_NAME_PTR_INFO (name))
534 : : {
535 : 83545858 : if (get_ssa_name_ptr_info_nonnull (name))
536 : 10818478 : r.set_nonzero (type);
537 : : else
538 : 72727380 : r.set_varying (type);
539 : : }
540 : : else
541 : 330252936 : r.set_varying (type);
542 : 611405741 : }
543 : :
544 : : // ----------------------------------------------
545 : : // global_range_query implementation.
546 : :
547 : : global_range_query global_ranges;
548 : :
549 : : bool
550 : 410703963 : global_range_query::range_of_expr (vrange &r, tree expr, gimple *stmt)
551 : : {
552 : 410703963 : if (!gimple_range_ssa_p (expr))
553 : 119518231 : return get_tree_range (r, expr, stmt);
554 : :
555 : 291185732 : gimple_range_global (r, expr);
556 : :
557 : 291185732 : return true;
558 : : }
|
