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 10426265 : range_query::range_on_edge (vrange &r, edge, tree expr)
40 : {
41 10426265 : 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 1635628 : range_query::range_of_stmt (vrange &r, gimple *stmt, tree name)
58 : {
59 1635628 : if (!name)
60 1635628 : name = gimple_get_lhs (stmt);
61 :
62 1635628 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
63 :
64 1635628 : if (name)
65 1635628 : return range_of_expr (r, name);
66 : return false;
67 : }
68 :
69 : // Default for updating range info is to do nothing.
70 : void
71 116932432 : range_query::update_range_info (tree)
72 : {
73 116932432 : }
74 :
75 : // Default for updating range info is to do nothing.
76 : void
77 4101915 : range_query::update_range_info (tree, const vrange &)
78 : {
79 4101915 : }
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 150006339 : range_query::value_of_expr (tree expr, gimple *stmt)
86 : {
87 150006339 : tree t;
88 :
89 150006339 : if (!value_range::supports_type_p (TREE_TYPE (expr)))
90 : return NULL_TREE;
91 :
92 147166762 : value_range r (TREE_TYPE (expr));
93 :
94 147166762 : 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 147166762 : if (r.undefined_p ())
99 230166 : range_of_expr (r, expr);
100 147166762 : if (r.singleton_p (&t))
101 1550597 : return t;
102 : }
103 : return NULL_TREE;
104 147166762 : }
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 23929364 : range_query::value_on_edge (edge e, tree expr)
111 : {
112 23929364 : tree t;
113 :
114 23929364 : if (!value_range::supports_type_p (TREE_TYPE (expr)))
115 : return NULL_TREE;
116 23663818 : value_range r (TREE_TYPE (expr));
117 23663818 : 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 23663818 : if (r.undefined_p ())
122 273947 : range_of_expr (r, expr);
123 23663818 : if (r.singleton_p (&t))
124 323126 : return t;
125 : }
126 : return NULL_TREE;
127 23663818 : }
128 :
129 : // If the range of STMT for NAME is a single value, return it.
130 : // Otherwise return NULL_TREE.
131 :
132 : tree
133 46850628 : range_query::value_of_stmt (gimple *stmt, tree name)
134 : {
135 46850628 : tree t;
136 :
137 46850628 : if (!name)
138 0 : name = gimple_get_lhs (stmt);
139 :
140 46850628 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
141 :
142 46850628 : if (!name || !value_range::supports_type_p (TREE_TYPE (name)))
143 1685463 : return NULL_TREE;
144 45165165 : value_range r (TREE_TYPE (name));
145 90330330 : if (range_of_stmt (r, stmt, name) && r.singleton_p (&t))
146 281898 : return t;
147 : return NULL_TREE;
148 45165165 : }
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 27858982 : range_query::create_gori (int not_executable_flag, int sw_max_edges)
201 : {
202 27858982 : gcc_checking_assert (m_gori == &default_gori);
203 27858982 : gcc_checking_assert (m_map == NULL);
204 27858982 : m_map = new gori_map ();
205 27858982 : gcc_checking_assert (m_map);
206 27858982 : m_gori = new gori_compute (*m_map, not_executable_flag, sw_max_edges);
207 27858982 : gcc_checking_assert (m_gori);
208 27858982 : }
209 :
210 : void
211 95542859 : range_query::destroy_gori ()
212 : {
213 95542859 : if (m_gori && m_gori != &default_gori)
214 27858981 : delete m_gori;
215 95542859 : if (m_map)
216 27858981 : delete m_map;
217 95542859 : m_map = NULL;
218 95542859 : m_gori= &default_gori;
219 95542859 : }
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 27858982 : range_query::create_infer_oracle (range_query *q, bool do_search)
229 : {
230 27858982 : gcc_checking_assert (m_infer == &default_infer_oracle);
231 27858982 : m_infer = new infer_range_manager (do_search, q);
232 27858982 : gcc_checking_assert (m_infer);
233 27858982 : }
234 :
235 : void
236 123401840 : range_query::destroy_infer_oracle ()
237 : {
238 123401840 : if (m_infer && m_infer != &default_infer_oracle)
239 27858981 : delete m_infer;
240 123401840 : m_infer = &default_infer_oracle;
241 123401840 : }
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 27858988 : range_query::create_relation_oracle (bool do_trans_p)
249 : {
250 27858988 : gcc_checking_assert (this != &global_ranges);
251 27858988 : gcc_checking_assert (m_relation == &default_relation_oracle);
252 :
253 27858988 : if (!dom_info_available_p (CDI_DOMINATORS))
254 : return;
255 25418327 : m_relation = new dom_oracle (do_trans_p);
256 25418327 : gcc_checking_assert (m_relation);
257 : }
258 :
259 : // Destroy any relation oracle that was created.
260 :
261 : void
262 123401846 : 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 123401846 : if (m_relation && m_relation != &default_relation_oracle)
267 : {
268 25418327 : delete m_relation;
269 25418327 : m_relation = &default_relation_oracle;
270 : }
271 123401846 : }
272 :
273 : void
274 55318481 : range_query::share_query (range_query &q)
275 : {
276 55318481 : m_relation = q.m_relation;
277 55318481 : m_infer = q.m_infer;
278 55318481 : m_gori = q.m_gori;
279 55318481 : m_map = q.m_map;
280 55318481 : m_shared_copy_p = true;
281 55318481 : }
282 :
283 150861351 : range_query::range_query ()
284 : {
285 150861351 : m_relation = &default_relation_oracle;
286 150861351 : m_infer = &default_infer_oracle;
287 150861351 : m_gori = &default_gori;
288 150861351 : m_map = NULL;
289 150861351 : m_shared_copy_p = false;
290 150861351 : }
291 :
292 150861339 : range_query::~range_query ()
293 : {
294 : // Do not destroy anything if this is a shared copy.
295 150861339 : if (m_shared_copy_p)
296 55318480 : return;
297 95542859 : destroy_gori ();
298 95542859 : destroy_infer_oracle ();
299 95542859 : destroy_relation_oracle ();
300 150861339 : }
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 28162610 : range_query::invoke_range_of_expr (vrange &r, tree expr, gimple *stmt,
309 : basic_block bbentry, basic_block bbexit,
310 : edge e)
311 : {
312 28162610 : if (bbentry)
313 : {
314 0 : gcc_checking_assert (!stmt && !bbexit && !e);
315 0 : return range_on_entry (r, bbentry, expr);
316 : }
317 28162610 : if (bbexit)
318 : {
319 0 : gcc_checking_assert (!stmt && !e);
320 0 : return range_on_exit (r, bbexit, expr);
321 : }
322 28162610 : if (e)
323 : {
324 2079865 : gcc_checking_assert (!stmt);
325 2079865 : return range_on_edge (r, e, expr);
326 : }
327 :
328 26082745 : 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 293742616 : range_query::get_tree_range (vrange &r, tree expr, gimple *stmt,
337 : basic_block bbentry, basic_block bbexit, edge e)
338 : {
339 293742616 : tree type;
340 293742616 : if (TYPE_P (expr))
341 : type = expr;
342 : else
343 293742616 : type = TREE_TYPE (expr);
344 :
345 293742616 : if (!r.supports_type_p (type))
346 : {
347 19547700 : r.set_undefined ();
348 19547700 : return false;
349 : }
350 274194916 : if (expr == type)
351 : {
352 0 : r.set_varying (type);
353 0 : return true;
354 : }
355 274194916 : switch (TREE_CODE (expr))
356 : {
357 223960910 : case INTEGER_CST:
358 223960910 : {
359 223960910 : if (TREE_OVERFLOW_P (expr))
360 172 : expr = drop_tree_overflow (expr);
361 223960910 : r.set (expr, expr);
362 223960910 : return true;
363 : }
364 :
365 4832344 : case REAL_CST:
366 4832344 : {
367 4832344 : frange &f = as_a <frange> (r);
368 4832344 : REAL_VALUE_TYPE *rv = TREE_REAL_CST_PTR (expr);
369 4832344 : 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 4816261 : nan_state nan (false);
377 4816261 : f.set (TREE_TYPE (expr), *rv, *rv, nan);
378 : }
379 : return true;
380 : }
381 :
382 34253 : case SSA_NAME:
383 : // If this is not an abnormal or virtual ssa, invoke range_of_expr.
384 34253 : if (gimple_range_ssa_p (expr))
385 0 : return invoke_range_of_expr (r, expr, stmt, bbentry, bbexit, e);
386 34253 : gimple_range_global (r, expr);
387 34253 : return true;
388 :
389 9793115 : case ADDR_EXPR:
390 9793115 : {
391 : // Handle &var which can show up in phi arguments.
392 9793115 : bool ov;
393 9793115 : if (tree_single_nonzero_warnv_p (expr, &ov))
394 : {
395 9735075 : r.set_nonzero (type);
396 9735075 : return true;
397 : }
398 58040 : break;
399 : }
400 :
401 : default:
402 : if (POLY_INT_CST_P (expr))
403 : {
404 : unsigned int precision = TYPE_PRECISION (type);
405 : r.set_varying (type);
406 : r.update_bitmask ({ wi::zero (precision), get_nonzero_bits (expr) });
407 : return true;
408 : }
409 : break;
410 : }
411 35632334 : if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr))
412 : {
413 11122794 : tree op0 = TREE_OPERAND (expr, 0);
414 11122794 : tree op1 = TREE_OPERAND (expr, 1);
415 11122794 : if (COMPARISON_CLASS_P (expr)
416 11122794 : && !value_range::supports_type_p (TREE_TYPE (op0)))
417 : return false;
418 11122794 : range_op_handler op (TREE_CODE (expr));
419 11122794 : if (op)
420 : {
421 11122794 : value_range r0 (TREE_TYPE (op0));
422 11122794 : value_range r1 (TREE_TYPE (op1));
423 11122794 : invoke_range_of_expr (r0, op0, stmt, bbentry, bbexit, e);
424 11122794 : invoke_range_of_expr (r1, op1, stmt, bbentry, bbexit, e);
425 11122794 : if (!op.fold_range (r, type, r0, r1))
426 0 : r.set_varying (type);
427 11122794 : }
428 : else
429 0 : r.set_varying (type);
430 11122794 : return true;
431 : }
432 24509540 : if (UNARY_CLASS_P (expr))
433 : {
434 5926786 : range_op_handler op (TREE_CODE (expr));
435 5926786 : tree op0_type = TREE_TYPE (TREE_OPERAND (expr, 0));
436 5926786 : if (op && value_range::supports_type_p (op0_type))
437 : {
438 5917022 : value_range r0 (TREE_TYPE (TREE_OPERAND (expr, 0)));
439 5917022 : value_range r1 (type);
440 5917022 : r1.set_varying (type);
441 5917022 : invoke_range_of_expr (r0, TREE_OPERAND (expr, 0), stmt, bbentry,
442 : bbexit, e);
443 5917022 : if (!op.fold_range (r, type, r0, r1))
444 0 : r.set_varying (type);
445 5917022 : }
446 : else
447 9764 : r.set_varying (type);
448 5926786 : return true;
449 : }
450 18582754 : r.set_varying (type);
451 18582754 : return true;
452 : }
453 :
454 : // Return the range for NAME from SSA_NAME_RANGE_INFO.
455 :
456 : static inline void
457 174410430 : get_ssa_name_range_info (vrange &r, const_tree name)
458 : {
459 174410430 : tree type = TREE_TYPE (name);
460 174410430 : gcc_checking_assert (!POINTER_TYPE_P (type));
461 174410430 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
462 :
463 174410430 : vrange_storage *ri = SSA_NAME_RANGE_INFO (name);
464 :
465 174410430 : if (ri)
466 159198872 : ri->get_vrange (r, TREE_TYPE (name));
467 : else
468 15211558 : r.set_varying (type);
469 174410430 : }
470 :
471 : // Return nonnull attribute of pointer NAME from SSA_NAME_PTR_INFO.
472 :
473 : static inline bool
474 91907971 : get_ssa_name_ptr_info_nonnull (const_tree name)
475 : {
476 91907971 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
477 91907971 : struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
478 91907971 : if (pi == NULL)
479 : return false;
480 : /* TODO Now pt->null is conservatively set to true in PTA
481 : analysis. vrp is the only pass (including ipa-vrp)
482 : that clears pt.null via set_ptr_nonnull when it knows
483 : for sure. PTA will preserves the pt.null value set by VRP.
484 :
485 : When PTA analysis is improved, pt.anything, pt.nonlocal
486 : and pt.escaped may also has to be considered before
487 : deciding that pointer cannot point to NULL. */
488 90711848 : return !pi->pt.null;
489 : }
490 :
491 : // Update the global range for NAME into the SSA_RANGE_NAME_INFO and
492 : // Return the legacy global range for NAME if it has one, otherwise
493 : // return VARYING.
494 : // See discussion here regarding why there use to be a wrapper function:
495 : // https://gcc.gnu.org/pipermail/gcc-patches/2021-June/571709.html
496 : // Legacy EVRP has been removed, leaving just this function.
497 :
498 : void
499 601784197 : gimple_range_global (vrange &r, tree name, struct function *fun)
500 : {
501 601784197 : tree type = TREE_TYPE (name);
502 601784197 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
503 :
504 601784197 : if (SSA_NAME_IS_DEFAULT_DEF (name))
505 : {
506 39621910 : tree sym = SSA_NAME_VAR (name);
507 : // Adapted from vr_values::get_lattice_entry().
508 : // Use a range from an SSA_NAME's available range.
509 39621910 : if (TREE_CODE (sym) == PARM_DECL)
510 : {
511 : // Try to use the "nonnull" attribute to create ~[0, 0]
512 : // anti-ranges for pointers. Note that this is only valid with
513 : // default definitions of PARM_DECLs.
514 36792265 : if (POINTER_TYPE_P (type)
515 36792265 : && ((cfun && fun == cfun && nonnull_arg_p (sym))
516 11090802 : || get_ssa_name_ptr_info_nonnull (name)))
517 10352107 : r.set_nonzero (type);
518 26440158 : else if (!POINTER_TYPE_P (type))
519 : {
520 15541358 : get_ssa_name_range_info (r, name);
521 15541358 : if (r.undefined_p ())
522 0 : r.set_varying (type);
523 : }
524 : else
525 10898800 : r.set_varying (type);
526 : }
527 : // If this is a local automatic with no definition, use undefined.
528 2829645 : else if (TREE_CODE (sym) != RESULT_DECL)
529 2519031 : r.set_undefined ();
530 : else
531 310614 : r.set_varying (type);
532 : }
533 562162287 : else if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name))
534 : {
535 158869072 : get_ssa_name_range_info (r, name);
536 158869072 : if (r.undefined_p ())
537 0 : r.set_varying (type);
538 : }
539 403293215 : else if (POINTER_TYPE_P (type) && SSA_NAME_PTR_INFO (name))
540 : {
541 80817169 : if (get_ssa_name_ptr_info_nonnull (name))
542 10753440 : r.set_nonzero (type);
543 : else
544 70063729 : r.set_varying (type);
545 : }
546 : else
547 322476046 : r.set_varying (type);
548 601784197 : }
549 :
550 : // ----------------------------------------------
551 : // global_range_query implementation.
552 :
553 : global_range_query global_ranges;
554 :
555 : bool
556 407138540 : global_range_query::range_of_expr (vrange &r, tree expr, gimple *stmt)
557 : {
558 407138540 : if (!gimple_range_ssa_p (expr))
559 114070324 : return get_tree_range (r, expr, stmt);
560 :
561 293068216 : gimple_range_global (r, expr);
562 :
563 293068216 : return true;
564 : }
|
