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 : 7672292 : range_query::range_on_edge (vrange &r, edge, tree expr)
40 : : {
41 : 7672292 : 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 : 1481611 : range_query::range_of_stmt (vrange &r, gimple *stmt, tree name)
58 : : {
59 : 1481611 : if (!name)
60 : 1481611 : name = gimple_get_lhs (stmt);
61 : :
62 : 1481611 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
63 : :
64 : 1481611 : if (name)
65 : 1481611 : 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 : 148310675 : range_query::value_of_expr (tree expr, gimple *stmt)
74 : : {
75 : 148310675 : tree t;
76 : :
77 : 148310675 : if (!value_range::supports_type_p (TREE_TYPE (expr)))
78 : : return NULL_TREE;
79 : :
80 : 145743485 : value_range r (TREE_TYPE (expr));
81 : :
82 : 145743485 : 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 : 145743485 : if (r.undefined_p ())
87 : 214128 : range_of_expr (r, expr);
88 : 145743485 : if (r.singleton_p (&t))
89 : 1580458 : return t;
90 : : }
91 : : return NULL_TREE;
92 : 145743485 : }
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 : 24074081 : range_query::value_on_edge (edge e, tree expr)
99 : : {
100 : 24074081 : tree t;
101 : :
102 : 24074081 : if (!value_range::supports_type_p (TREE_TYPE (expr)))
103 : : return NULL_TREE;
104 : 23840073 : value_range r (TREE_TYPE (expr));
105 : 23840073 : 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 : 23840073 : if (r.undefined_p ())
110 : 263510 : range_of_expr (r, expr);
111 : 23840073 : if (r.singleton_p (&t))
112 : 347805 : return t;
113 : : }
114 : : return NULL_TREE;
115 : 23840073 : }
116 : :
117 : : // If the range of STMT for NAME is a single value, return it.
118 : : // Otherwise return NULL_TREE.
119 : :
120 : : tree
121 : 46793345 : range_query::value_of_stmt (gimple *stmt, tree name)
122 : : {
123 : 46793345 : tree t;
124 : :
125 : 46793345 : if (!name)
126 : 0 : name = gimple_get_lhs (stmt);
127 : :
128 : 46793345 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
129 : :
130 : 46793345 : if (!name || !value_range::supports_type_p (TREE_TYPE (name)))
131 : 1577854 : return NULL_TREE;
132 : 45215491 : value_range r (TREE_TYPE (name));
133 : 90430982 : if (range_of_stmt (r, stmt, name) && r.singleton_p (&t))
134 : 247928 : return t;
135 : : return NULL_TREE;
136 : 45215491 : }
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 : 25675590 : range_query::create_gori (int not_executable_flag, int sw_max_edges)
189 : : {
190 : 25675590 : gcc_checking_assert (m_gori == &default_gori);
191 : 25675590 : gcc_checking_assert (m_map == NULL);
192 : 25675590 : m_map = new gori_map ();
193 : 25675590 : gcc_checking_assert (m_map);
194 : 25675590 : m_gori = new gori_compute (*m_map, not_executable_flag, sw_max_edges);
195 : 25675590 : gcc_checking_assert (m_gori);
196 : 25675590 : }
197 : :
198 : : void
199 : 89899040 : range_query::destroy_gori ()
200 : : {
201 : 89899040 : if (m_gori && m_gori != &default_gori)
202 : 25675590 : delete m_gori;
203 : 89899040 : if (m_map)
204 : 25675590 : delete m_map;
205 : 89899040 : m_map = NULL;
206 : 89899040 : m_gori= &default_gori;
207 : 89899040 : }
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 : 25675590 : range_query::create_infer_oracle (range_query *q, bool do_search)
217 : : {
218 : 25675590 : gcc_checking_assert (m_infer == &default_infer_oracle);
219 : 25675590 : m_infer = new infer_range_manager (do_search, q);
220 : 25675590 : gcc_checking_assert (m_infer);
221 : 25675590 : }
222 : :
223 : : void
224 : 115574630 : range_query::destroy_infer_oracle ()
225 : : {
226 : 115574630 : if (m_infer && m_infer != &default_infer_oracle)
227 : 25675590 : delete m_infer;
228 : 115574630 : m_infer = &default_infer_oracle;
229 : 115574630 : }
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 : 25675596 : range_query::create_relation_oracle (bool do_trans_p)
237 : : {
238 : 25675596 : gcc_checking_assert (this != &global_ranges);
239 : 25675596 : gcc_checking_assert (m_relation == &default_relation_oracle);
240 : :
241 : 25675596 : if (!dom_info_available_p (CDI_DOMINATORS))
242 : : return;
243 : 24734369 : m_relation = new dom_oracle (do_trans_p);
244 : 24734369 : gcc_checking_assert (m_relation);
245 : : }
246 : :
247 : : // Destroy any relation oracle that was created.
248 : :
249 : : void
250 : 115574636 : 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 : 115574636 : if (m_relation && m_relation != &default_relation_oracle)
255 : : {
256 : 24734369 : delete m_relation;
257 : 24734369 : m_relation = &default_relation_oracle;
258 : : }
259 : 115574636 : }
260 : :
261 : : void
262 : 51979472 : range_query::share_query (range_query &q)
263 : : {
264 : 51979472 : m_relation = q.m_relation;
265 : 51979472 : m_infer = q.m_infer;
266 : 51979472 : m_gori = q.m_gori;
267 : 51979472 : m_map = q.m_map;
268 : 51979472 : m_shared_copy_p = true;
269 : 51979472 : }
270 : :
271 : 141878521 : range_query::range_query ()
272 : : {
273 : 141878521 : m_relation = &default_relation_oracle;
274 : 141878521 : m_infer = &default_infer_oracle;
275 : 141878521 : m_gori = &default_gori;
276 : 141878521 : m_map = NULL;
277 : 141878521 : m_shared_copy_p = false;
278 : 141878521 : }
279 : :
280 : 141878512 : range_query::~range_query ()
281 : : {
282 : : // Do not destroy anything if this is a shared copy.
283 : 141878512 : if (m_shared_copy_p)
284 : 51979472 : return;
285 : 89899040 : destroy_gori ();
286 : 89899040 : destroy_infer_oracle ();
287 : 89899040 : destroy_relation_oracle ();
288 : 141878512 : }
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 : 17819190 : range_query::invoke_range_of_expr (vrange &r, tree expr, gimple *stmt,
297 : : basic_block bbentry, basic_block bbexit)
298 : : {
299 : 17819190 : if (bbentry)
300 : : {
301 : 0 : gcc_checking_assert (!stmt && !bbexit);
302 : 0 : return range_on_entry (r, bbentry, expr);
303 : : }
304 : 17819190 : if (bbexit)
305 : : {
306 : 0 : gcc_checking_assert (!stmt);
307 : 0 : return range_on_exit (r, bbexit, expr);
308 : : }
309 : :
310 : 17819190 : 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 : 264658523 : range_query::get_tree_range (vrange &r, tree expr, gimple *stmt,
319 : : basic_block bbentry, basic_block bbexit)
320 : : {
321 : 264658523 : tree type;
322 : 264658523 : if (TYPE_P (expr))
323 : : type = expr;
324 : : else
325 : 264658523 : type = TREE_TYPE (expr);
326 : :
327 : 264658523 : if (!value_range::supports_type_p (type))
328 : : {
329 : 20291997 : r.set_undefined ();
330 : 20291997 : return false;
331 : : }
332 : 244366526 : if (expr == type)
333 : : {
334 : 0 : r.set_varying (type);
335 : 0 : return true;
336 : : }
337 : 244366526 : switch (TREE_CODE (expr))
338 : : {
339 : 201624948 : case INTEGER_CST:
340 : 201624948 : {
341 : 201624948 : if (TREE_OVERFLOW_P (expr))
342 : 34 : expr = drop_tree_overflow (expr);
343 : 201624948 : r.set (expr, expr);
344 : 201624948 : return true;
345 : : }
346 : :
347 : 4389926 : case REAL_CST:
348 : 4389926 : {
349 : 4389926 : frange &f = as_a <frange> (r);
350 : 4389926 : REAL_VALUE_TYPE *rv = TREE_REAL_CST_PTR (expr);
351 : 4389926 : if (real_isnan (rv))
352 : : {
353 : 10504 : bool sign = real_isneg (rv);
354 : 10504 : f.set_nan (TREE_TYPE (expr), sign);
355 : : }
356 : : else
357 : : {
358 : 4379422 : nan_state nan (false);
359 : 4379422 : f.set (TREE_TYPE (expr), *rv, *rv, nan);
360 : : }
361 : : return true;
362 : : }
363 : :
364 : 32789 : case SSA_NAME:
365 : : // If this is not an abnormal or virtual ssa, invoke range_of_expr.
366 : 32789 : if (gimple_range_ssa_p (expr))
367 : 0 : return invoke_range_of_expr (r, expr, stmt, bbentry, bbexit);
368 : 32789 : gimple_range_global (r, expr);
369 : 32789 : return true;
370 : :
371 : 9117653 : case ADDR_EXPR:
372 : 9117653 : {
373 : : // Handle &var which can show up in phi arguments.
374 : 9117653 : bool ov;
375 : 9117653 : if (tree_single_nonzero_warnv_p (expr, &ov))
376 : : {
377 : 9061741 : r.set_nonzero (type);
378 : 9061741 : return true;
379 : : }
380 : 55912 : 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 : 29257122 : if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr))
394 : : {
395 : 6590751 : tree op0 = TREE_OPERAND (expr, 0);
396 : 6590751 : tree op1 = TREE_OPERAND (expr, 1);
397 : 6590751 : if (COMPARISON_CLASS_P (expr)
398 : 6590751 : && !value_range::supports_type_p (TREE_TYPE (op0)))
399 : : return false;
400 : 6590751 : range_op_handler op (TREE_CODE (expr));
401 : 6590751 : if (op)
402 : : {
403 : 6590751 : value_range r0 (TREE_TYPE (op0));
404 : 6590751 : value_range r1 (TREE_TYPE (op1));
405 : 6590751 : invoke_range_of_expr (r0, op0, stmt, bbentry, bbexit);
406 : 6590751 : invoke_range_of_expr (r1, op1, stmt, bbentry, bbexit);
407 : 6590751 : if (!op.fold_range (r, type, r0, r1))
408 : 0 : r.set_varying (type);
409 : 6590751 : }
410 : : else
411 : 0 : r.set_varying (type);
412 : 6590751 : return true;
413 : : }
414 : 22666371 : if (UNARY_CLASS_P (expr))
415 : : {
416 : 4637797 : range_op_handler op (TREE_CODE (expr));
417 : 4637797 : tree op0_type = TREE_TYPE (TREE_OPERAND (expr, 0));
418 : 4637797 : if (op && value_range::supports_type_p (op0_type))
419 : : {
420 : 4637688 : value_range r0 (TREE_TYPE (TREE_OPERAND (expr, 0)));
421 : 4637688 : value_range r1 (type);
422 : 4637688 : r1.set_varying (type);
423 : 4637688 : invoke_range_of_expr (r0, TREE_OPERAND (expr, 0), stmt, bbentry,
424 : : bbexit);
425 : 4637688 : if (!op.fold_range (r, type, r0, r1))
426 : 0 : r.set_varying (type);
427 : 4637688 : }
428 : : else
429 : 109 : r.set_varying (type);
430 : 4637797 : return true;
431 : : }
432 : 18028574 : r.set_varying (type);
433 : 18028574 : return true;
434 : : }
435 : :
436 : : // Return the range for NAME from SSA_NAME_RANGE_INFO.
437 : :
438 : : static inline void
439 : 149203798 : get_ssa_name_range_info (vrange &r, const_tree name)
440 : : {
441 : 149203798 : tree type = TREE_TYPE (name);
442 : 149203798 : gcc_checking_assert (!POINTER_TYPE_P (type));
443 : 149203798 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
444 : :
445 : 149203798 : vrange_storage *ri = SSA_NAME_RANGE_INFO (name);
446 : :
447 : 149203798 : if (ri)
448 : 134815896 : ri->get_vrange (r, TREE_TYPE (name));
449 : : else
450 : 14387902 : r.set_varying (type);
451 : 149203798 : }
452 : :
453 : : // Return nonnull attribute of pointer NAME from SSA_NAME_PTR_INFO.
454 : :
455 : : static inline bool
456 : 90116543 : get_ssa_name_ptr_info_nonnull (const_tree name)
457 : : {
458 : 90116543 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
459 : 90116543 : struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
460 : 90116543 : 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 : 88943823 : 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 : 562362115 : gimple_range_global (vrange &r, tree name, struct function *fun)
482 : : {
483 : 562362115 : tree type = TREE_TYPE (name);
484 : 562362115 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
485 : :
486 : 562362115 : if (SSA_NAME_IS_DEFAULT_DEF (name))
487 : : {
488 : 38757140 : 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 : 38757140 : 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 : 35774920 : if (POINTER_TYPE_P (type)
497 : 35774920 : && ((cfun && fun == cfun && nonnull_arg_p (sym))
498 : 10815322 : || get_ssa_name_ptr_info_nonnull (name)))
499 : 10494329 : r.set_nonzero (type);
500 : 25280591 : else if (!POINTER_TYPE_P (type))
501 : : {
502 : 14642174 : get_ssa_name_range_info (r, name);
503 : 14642174 : if (r.undefined_p ())
504 : 0 : r.set_varying (type);
505 : : }
506 : : else
507 : 10638417 : r.set_varying (type);
508 : : }
509 : : // If this is a local automatic with no definition, use undefined.
510 : 2982220 : else if (TREE_CODE (sym) != RESULT_DECL)
511 : 2657100 : r.set_undefined ();
512 : : else
513 : 325120 : r.set_varying (type);
514 : : }
515 : 523604975 : else if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name))
516 : : {
517 : 134561624 : get_ssa_name_range_info (r, name);
518 : 134561624 : if (r.undefined_p ())
519 : 0 : r.set_varying (type);
520 : : }
521 : 389043351 : else if (POINTER_TYPE_P (type) && SSA_NAME_PTR_INFO (name))
522 : : {
523 : 79301221 : if (get_ssa_name_ptr_info_nonnull (name))
524 : 10028984 : r.set_nonzero (type);
525 : : else
526 : 69272237 : r.set_varying (type);
527 : : }
528 : : else
529 : 309742130 : r.set_varying (type);
530 : 562362115 : }
531 : :
532 : : // ----------------------------------------------
533 : : // global_range_query implementation.
534 : :
535 : : global_range_query global_ranges;
536 : :
537 : : bool
538 : 374029286 : global_range_query::range_of_expr (vrange &r, tree expr, gimple *stmt)
539 : : {
540 : 374029286 : if (!gimple_range_ssa_p (expr))
541 : 102163840 : return get_tree_range (r, expr, stmt);
542 : :
543 : 271865446 : gimple_range_global (r, expr);
544 : :
545 : 271865446 : return true;
546 : : }
|
