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 : 10887942 : range_query::range_on_edge (vrange &r, edge, tree expr)
40 : : {
41 : 10887942 : 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 : 1671727 : range_query::range_of_stmt (vrange &r, gimple *stmt, tree name)
58 : : {
59 : 1671727 : if (!name)
60 : 1671727 : name = gimple_get_lhs (stmt);
61 : :
62 : 1671727 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
63 : :
64 : 1671727 : if (name)
65 : 1671727 : return range_of_expr (r, name);
66 : : return false;
67 : : }
68 : :
69 : : // Default for updating range info is to do nothing.
70 : : void
71 : 4182103 : range_query::update_range_info (tree, const vrange &)
72 : : {
73 : 4182103 : }
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 : 152539951 : range_query::value_of_expr (tree expr, gimple *stmt)
80 : : {
81 : 152539951 : tree t;
82 : :
83 : 152539951 : if (!value_range::supports_type_p (TREE_TYPE (expr)))
84 : : return NULL_TREE;
85 : :
86 : 149896326 : value_range r (TREE_TYPE (expr));
87 : :
88 : 149896326 : 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 : 149896326 : if (r.undefined_p ())
93 : 222791 : range_of_expr (r, expr);
94 : 149896326 : if (r.singleton_p (&t))
95 : 1635532 : return t;
96 : : }
97 : : return NULL_TREE;
98 : 149896326 : }
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 : 25392916 : range_query::value_on_edge (edge e, tree expr)
105 : : {
106 : 25392916 : tree t;
107 : :
108 : 25392916 : if (!value_range::supports_type_p (TREE_TYPE (expr)))
109 : : return NULL_TREE;
110 : 25150032 : value_range r (TREE_TYPE (expr));
111 : 25150032 : 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 : 25150032 : if (r.undefined_p ())
116 : 274718 : range_of_expr (r, expr);
117 : 25150032 : if (r.singleton_p (&t))
118 : 372332 : return t;
119 : : }
120 : : return NULL_TREE;
121 : 25150032 : }
122 : :
123 : : // If the range of STMT for NAME is a single value, return it.
124 : : // Otherwise return NULL_TREE.
125 : :
126 : : tree
127 : 48043598 : range_query::value_of_stmt (gimple *stmt, tree name)
128 : : {
129 : 48043598 : tree t;
130 : :
131 : 48043598 : if (!name)
132 : 0 : name = gimple_get_lhs (stmt);
133 : :
134 : 48043598 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
135 : :
136 : 48043598 : if (!name || !value_range::supports_type_p (TREE_TYPE (name)))
137 : 1625574 : return NULL_TREE;
138 : 46418024 : value_range r (TREE_TYPE (name));
139 : 92836048 : if (range_of_stmt (r, stmt, name) && r.singleton_p (&t))
140 : 271627 : return t;
141 : : return NULL_TREE;
142 : 46418024 : }
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 : 28308752 : range_query::create_gori (int not_executable_flag, int sw_max_edges)
195 : : {
196 : 28308752 : gcc_checking_assert (m_gori == &default_gori);
197 : 28308752 : gcc_checking_assert (m_map == NULL);
198 : 28308752 : m_map = new gori_map ();
199 : 28308752 : gcc_checking_assert (m_map);
200 : 28308752 : m_gori = new gori_compute (*m_map, not_executable_flag, sw_max_edges);
201 : 28308752 : gcc_checking_assert (m_gori);
202 : 28308752 : }
203 : :
204 : : void
205 : 98380532 : range_query::destroy_gori ()
206 : : {
207 : 98380532 : if (m_gori && m_gori != &default_gori)
208 : 28308752 : delete m_gori;
209 : 98380532 : if (m_map)
210 : 28308752 : delete m_map;
211 : 98380532 : m_map = NULL;
212 : 98380532 : m_gori= &default_gori;
213 : 98380532 : }
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 : 28308752 : range_query::create_infer_oracle (range_query *q, bool do_search)
223 : : {
224 : 28308752 : gcc_checking_assert (m_infer == &default_infer_oracle);
225 : 28308752 : m_infer = new infer_range_manager (do_search, q);
226 : 28308752 : gcc_checking_assert (m_infer);
227 : 28308752 : }
228 : :
229 : : void
230 : 126689284 : range_query::destroy_infer_oracle ()
231 : : {
232 : 126689284 : if (m_infer && m_infer != &default_infer_oracle)
233 : 28308752 : delete m_infer;
234 : 126689284 : m_infer = &default_infer_oracle;
235 : 126689284 : }
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 : 28308758 : range_query::create_relation_oracle (bool do_trans_p)
243 : : {
244 : 28308758 : gcc_checking_assert (this != &global_ranges);
245 : 28308758 : gcc_checking_assert (m_relation == &default_relation_oracle);
246 : :
247 : 28308758 : if (!dom_info_available_p (CDI_DOMINATORS))
248 : : return;
249 : 25866618 : m_relation = new dom_oracle (do_trans_p);
250 : 25866618 : gcc_checking_assert (m_relation);
251 : : }
252 : :
253 : : // Destroy any relation oracle that was created.
254 : :
255 : : void
256 : 126689290 : 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 : 126689290 : if (m_relation && m_relation != &default_relation_oracle)
261 : : {
262 : 25866618 : delete m_relation;
263 : 25866618 : m_relation = &default_relation_oracle;
264 : : }
265 : 126689290 : }
266 : :
267 : : void
268 : 57493334 : range_query::share_query (range_query &q)
269 : : {
270 : 57493334 : m_relation = q.m_relation;
271 : 57493334 : m_infer = q.m_infer;
272 : 57493334 : m_gori = q.m_gori;
273 : 57493334 : m_map = q.m_map;
274 : 57493334 : m_shared_copy_p = true;
275 : 57493334 : }
276 : :
277 : 155873875 : range_query::range_query ()
278 : : {
279 : 155873875 : m_relation = &default_relation_oracle;
280 : 155873875 : m_infer = &default_infer_oracle;
281 : 155873875 : m_gori = &default_gori;
282 : 155873875 : m_map = NULL;
283 : 155873875 : m_shared_copy_p = false;
284 : 155873875 : }
285 : :
286 : 155873866 : range_query::~range_query ()
287 : : {
288 : : // Do not destroy anything if this is a shared copy.
289 : 155873866 : if (m_shared_copy_p)
290 : 57493334 : return;
291 : 98380532 : destroy_gori ();
292 : 98380532 : destroy_infer_oracle ();
293 : 98380532 : destroy_relation_oracle ();
294 : 155873866 : }
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 : 28650216 : range_query::invoke_range_of_expr (vrange &r, tree expr, gimple *stmt,
303 : : basic_block bbentry, basic_block bbexit,
304 : : edge e)
305 : : {
306 : 28650216 : if (bbentry)
307 : : {
308 : 0 : gcc_checking_assert (!stmt && !bbexit && !e);
309 : 0 : return range_on_entry (r, bbentry, expr);
310 : : }
311 : 28650216 : if (bbexit)
312 : : {
313 : 0 : gcc_checking_assert (!stmt && !e);
314 : 0 : return range_on_exit (r, bbexit, expr);
315 : : }
316 : 28650216 : if (e)
317 : : {
318 : 2199063 : gcc_checking_assert (!stmt);
319 : 2199063 : return range_on_edge (r, e, expr);
320 : : }
321 : :
322 : 26451153 : 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 : 305352779 : range_query::get_tree_range (vrange &r, tree expr, gimple *stmt,
331 : : basic_block bbentry, basic_block bbexit, edge e)
332 : : {
333 : 305352779 : tree type;
334 : 305352779 : if (TYPE_P (expr))
335 : : type = expr;
336 : : else
337 : 305352779 : type = TREE_TYPE (expr);
338 : :
339 : 305352779 : if (!value_range::supports_type_p (type))
340 : : {
341 : 20115150 : r.set_undefined ();
342 : 20115150 : return false;
343 : : }
344 : 285237629 : if (expr == type)
345 : : {
346 : 0 : r.set_varying (type);
347 : 0 : return true;
348 : : }
349 : 285237629 : switch (TREE_CODE (expr))
350 : : {
351 : 233554362 : case INTEGER_CST:
352 : 233554362 : {
353 : 233554362 : if (TREE_OVERFLOW_P (expr))
354 : 148 : expr = drop_tree_overflow (expr);
355 : 233554362 : r.set (expr, expr);
356 : 233554362 : return true;
357 : : }
358 : :
359 : 4952521 : case REAL_CST:
360 : 4952521 : {
361 : 4952521 : frange &f = as_a <frange> (r);
362 : 4952521 : REAL_VALUE_TYPE *rv = TREE_REAL_CST_PTR (expr);
363 : 4952521 : if (real_isnan (rv))
364 : : {
365 : 16010 : bool sign = real_isneg (rv);
366 : 16010 : f.set_nan (TREE_TYPE (expr), sign);
367 : : }
368 : : else
369 : : {
370 : 4936511 : nan_state nan (false);
371 : 4936511 : 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 : 10357621 : case ADDR_EXPR:
384 : 10357621 : {
385 : : // Handle &var which can show up in phi arguments.
386 : 10357621 : bool ov;
387 : 10357621 : if (tree_single_nonzero_warnv_p (expr, &ov))
388 : : {
389 : 10300204 : r.set_nonzero (type);
390 : 10300204 : return true;
391 : : }
392 : 57417 : 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 : 36397221 : if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr))
406 : : {
407 : 11310238 : tree op0 = TREE_OPERAND (expr, 0);
408 : 11310238 : tree op1 = TREE_OPERAND (expr, 1);
409 : 11310238 : if (COMPARISON_CLASS_P (expr)
410 : 11310238 : && !value_range::supports_type_p (TREE_TYPE (op0)))
411 : : return false;
412 : 11310238 : range_op_handler op (TREE_CODE (expr));
413 : 11310238 : if (op)
414 : : {
415 : 11310238 : value_range r0 (TREE_TYPE (op0));
416 : 11310238 : value_range r1 (TREE_TYPE (op1));
417 : 11310238 : invoke_range_of_expr (r0, op0, stmt, bbentry, bbexit, e);
418 : 11310238 : invoke_range_of_expr (r1, op1, stmt, bbentry, bbexit, e);
419 : 11310238 : if (!op.fold_range (r, type, r0, r1))
420 : 0 : r.set_varying (type);
421 : 11310238 : }
422 : : else
423 : 0 : r.set_varying (type);
424 : 11310238 : return true;
425 : : }
426 : 25086983 : if (UNARY_CLASS_P (expr))
427 : : {
428 : 6039467 : range_op_handler op (TREE_CODE (expr));
429 : 6039467 : tree op0_type = TREE_TYPE (TREE_OPERAND (expr, 0));
430 : 6039467 : if (op && value_range::supports_type_p (op0_type))
431 : : {
432 : 6029740 : value_range r0 (TREE_TYPE (TREE_OPERAND (expr, 0)));
433 : 6029740 : value_range r1 (type);
434 : 6029740 : r1.set_varying (type);
435 : 6029740 : invoke_range_of_expr (r0, TREE_OPERAND (expr, 0), stmt, bbentry,
436 : : bbexit, e);
437 : 6029740 : if (!op.fold_range (r, type, r0, r1))
438 : 0 : r.set_varying (type);
439 : 6029740 : }
440 : : else
441 : 9727 : r.set_varying (type);
442 : 6039467 : return true;
443 : : }
444 : 19047516 : r.set_varying (type);
445 : 19047516 : return true;
446 : : }
447 : :
448 : : // Return the range for NAME from SSA_NAME_RANGE_INFO.
449 : :
450 : : static inline void
451 : 174122556 : get_ssa_name_range_info (vrange &r, const_tree name)
452 : : {
453 : 174122556 : tree type = TREE_TYPE (name);
454 : 174122556 : gcc_checking_assert (!POINTER_TYPE_P (type));
455 : 174122556 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
456 : :
457 : 174122556 : vrange_storage *ri = SSA_NAME_RANGE_INFO (name);
458 : :
459 : 174122556 : if (ri)
460 : 158443482 : ri->get_vrange (r, TREE_TYPE (name));
461 : : else
462 : 15679074 : r.set_varying (type);
463 : 174122556 : }
464 : :
465 : : // Return nonnull attribute of pointer NAME from SSA_NAME_PTR_INFO.
466 : :
467 : : static inline bool
468 : 95222920 : get_ssa_name_ptr_info_nonnull (const_tree name)
469 : : {
470 : 95222920 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
471 : 95222920 : struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
472 : 95222920 : 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 : 94026781 : 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 : 614312729 : gimple_range_global (vrange &r, tree name, struct function *fun)
494 : : {
495 : 614312729 : tree type = TREE_TYPE (name);
496 : 614312729 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
497 : :
498 : 614312729 : if (SSA_NAME_IS_DEFAULT_DEF (name))
499 : : {
500 : 40863357 : 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 : 40863357 : 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 : 37959009 : if (POINTER_TYPE_P (type)
509 : 37959009 : && ((cfun && fun == cfun && nonnull_arg_p (sym))
510 : 11173516 : || get_ssa_name_ptr_info_nonnull (name)))
511 : 10963310 : r.set_nonzero (type);
512 : 26995699 : else if (!POINTER_TYPE_P (type))
513 : : {
514 : 16011107 : get_ssa_name_range_info (r, name);
515 : 16011107 : if (r.undefined_p ())
516 : 0 : r.set_varying (type);
517 : : }
518 : : else
519 : 10984592 : r.set_varying (type);
520 : : }
521 : : // If this is a local automatic with no definition, use undefined.
522 : 2904348 : else if (TREE_CODE (sym) != RESULT_DECL)
523 : 2575591 : r.set_undefined ();
524 : : else
525 : 328757 : r.set_varying (type);
526 : : }
527 : 573449372 : else if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name))
528 : : {
529 : 158111449 : get_ssa_name_range_info (r, name);
530 : 158111449 : if (r.undefined_p ())
531 : 0 : r.set_varying (type);
532 : : }
533 : 415337923 : else if (POINTER_TYPE_P (type) && SSA_NAME_PTR_INFO (name))
534 : : {
535 : 84049404 : if (get_ssa_name_ptr_info_nonnull (name))
536 : 10977576 : r.set_nonzero (type);
537 : : else
538 : 73071828 : r.set_varying (type);
539 : : }
540 : : else
541 : 331288519 : r.set_varying (type);
542 : 614312729 : }
543 : :
544 : : // ----------------------------------------------
545 : : // global_range_query implementation.
546 : :
547 : : global_range_query global_ranges;
548 : :
549 : : bool
550 : 412843598 : global_range_query::range_of_expr (vrange &r, tree expr, gimple *stmt)
551 : : {
552 : 412843598 : if (!gimple_range_ssa_p (expr))
553 : 120488701 : return get_tree_range (r, expr, stmt);
554 : :
555 : 292354897 : gimple_range_global (r, expr);
556 : :
557 : 292354897 : return true;
558 : : }
|
