1 /* Support routines for value queries.
2 Copyright (C) 2020-2022 Free Software Foundation, Inc.
3 Contributed by Aldy Hernandez <aldyh@redhat.com> and
4 Andrew MacLeod <amacleod@redhat.com>.
6 This file is part of GCC.
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)
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.
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/>. */
24 #include "coretypes.h"
29 #include "tree-pretty-print.h"
30 #include "fold-const.h"
31 #include "value-range-equiv.h"
32 #include "value-query.h"
33 #include "alloc-pool.h"
34 #include "gimple-range.h"
36 // value_query default methods.
39 value_query::value_on_edge (edge
, tree expr
)
41 return value_of_expr (expr
);
45 value_query::value_of_stmt (gimple
*stmt
, tree name
)
48 name
= gimple_get_lhs (stmt
);
50 gcc_checking_assert (!name
|| name
== gimple_get_lhs (stmt
));
53 return value_of_expr (name
);
57 // range_query default methods.
60 range_query::range_on_edge (vrange
&r
, edge
, tree expr
)
62 return range_of_expr (r
, expr
);
66 range_query::range_of_stmt (vrange
&r
, gimple
*stmt
, tree name
)
69 name
= gimple_get_lhs (stmt
);
71 gcc_checking_assert (!name
|| name
== gimple_get_lhs (stmt
));
74 return range_of_expr (r
, name
);
79 range_query::value_of_expr (tree expr
, gimple
*stmt
)
83 if (!vrange::supports_type_p (TREE_TYPE (expr
)))
86 Value_Range
r (TREE_TYPE (expr
));
88 if (range_of_expr (r
, expr
, stmt
))
90 // A constant used in an unreachable block oftens returns as UNDEFINED.
91 // If the result is undefined, check the global value for a constant.
93 range_of_expr (r
, expr
);
94 if (r
.singleton_p (&t
))
101 range_query::value_on_edge (edge e
, tree expr
)
105 if (!vrange::supports_type_p (TREE_TYPE (expr
)))
107 Value_Range
r (TREE_TYPE (expr
));
108 if (range_on_edge (r
, e
, expr
))
110 // A constant used in an unreachable block oftens returns as UNDEFINED.
111 // If the result is undefined, check the global value for a constant.
112 if (r
.undefined_p ())
113 range_of_expr (r
, expr
);
114 if (r
.singleton_p (&t
))
122 range_query::value_of_stmt (gimple
*stmt
, tree name
)
127 name
= gimple_get_lhs (stmt
);
129 gcc_checking_assert (!name
|| name
== gimple_get_lhs (stmt
));
131 if (!name
|| !vrange::supports_type_p (TREE_TYPE (name
)))
133 Value_Range
r (TREE_TYPE (name
));
134 if (range_of_stmt (r
, stmt
, name
) && r
.singleton_p (&t
))
141 range_query::dump (FILE *)
145 // valuation_query support routines for value_range_equiv's.
147 class equiv_allocator
: public object_allocator
<value_range_equiv
>
151 : object_allocator
<value_range_equiv
> ("equiv_allocator pool") { }
155 range_query::allocate_value_range_equiv ()
157 return new (equiv_alloc
->allocate ()) value_range_equiv
;
161 range_query::free_value_range_equiv (value_range_equiv
*v
)
163 equiv_alloc
->remove (v
);
166 const class value_range_equiv
*
167 range_query::get_value_range (const_tree expr
, gimple
*stmt
)
170 if (range_of_expr (r
, const_cast<tree
> (expr
), stmt
))
171 return new (equiv_alloc
->allocate ()) value_range_equiv (r
);
172 return new (equiv_alloc
->allocate ()) value_range_equiv (TREE_TYPE (expr
));
175 range_query::range_query ()
177 equiv_alloc
= new equiv_allocator
;
181 range_query::~range_query ()
183 equiv_alloc
->release ();
187 // Return a range in R for the tree EXPR. Return true if a range is
188 // representable, and UNDEFINED/false if not.
191 range_query::get_tree_range (vrange
&r
, tree expr
, gimple
*stmt
)
197 type
= TREE_TYPE (expr
);
199 if (!vrange::supports_type_p (type
))
206 r
.set_varying (type
);
209 switch (TREE_CODE (expr
))
212 if (TREE_OVERFLOW_P (expr
))
213 expr
= drop_tree_overflow (expr
);
218 gimple_range_global (r
, expr
);
223 // Handle &var which can show up in phi arguments.
225 if (tree_single_nonzero_warnv_p (expr
, &ov
))
227 r
.set_nonzero (type
);
236 if (BINARY_CLASS_P (expr
))
238 range_op_handler
op (TREE_CODE (expr
), type
);
241 Value_Range
r0 (TREE_TYPE (TREE_OPERAND (expr
, 0)));
242 Value_Range
r1 (TREE_TYPE (TREE_OPERAND (expr
, 1)));
243 range_of_expr (r0
, TREE_OPERAND (expr
, 0), stmt
);
244 range_of_expr (r1
, TREE_OPERAND (expr
, 1), stmt
);
245 op
.fold_range (r
, type
, r0
, r1
);
248 r
.set_varying (type
);
251 if (UNARY_CLASS_P (expr
))
253 range_op_handler
op (TREE_CODE (expr
), type
);
254 tree op0_type
= TREE_TYPE (TREE_OPERAND (expr
, 0));
255 if (op
&& vrange::supports_type_p (op0_type
))
257 Value_Range
r0 (TREE_TYPE (TREE_OPERAND (expr
, 0)));
258 Value_Range
r1 (type
);
259 r1
.set_varying (type
);
260 range_of_expr (r0
, TREE_OPERAND (expr
, 0), stmt
);
261 op
.fold_range (r
, type
, r0
, r1
);
264 r
.set_varying (type
);
267 r
.set_varying (type
);
271 // Return the range for NAME from SSA_NAME_RANGE_INFO.
274 get_ssa_name_range_info (irange
&r
, const_tree name
)
276 tree type
= TREE_TYPE (name
);
277 gcc_checking_assert (!POINTER_TYPE_P (type
));
278 gcc_checking_assert (TREE_CODE (name
) == SSA_NAME
);
280 range_info_def
*ri
= SSA_NAME_RANGE_INFO (name
);
282 // Return VR_VARYING for SSA_NAMEs with NULL RANGE_INFO or SSA_NAMEs
283 // with integral types width > 2 * HOST_BITS_PER_WIDE_INT precision.
284 if (!ri
|| (GET_MODE_PRECISION (SCALAR_INT_TYPE_MODE (TREE_TYPE (name
)))
285 > 2 * HOST_BITS_PER_WIDE_INT
))
286 r
.set_varying (type
);
288 r
.set (wide_int_to_tree (type
, ri
->get_min ()),
289 wide_int_to_tree (type
, ri
->get_max ()),
290 SSA_NAME_RANGE_TYPE (name
));
293 // Return nonnull attribute of pointer NAME from SSA_NAME_PTR_INFO.
296 get_ssa_name_ptr_info_nonnull (const_tree name
)
298 gcc_assert (POINTER_TYPE_P (TREE_TYPE (name
)));
299 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (name
);
302 /* TODO Now pt->null is conservatively set to true in PTA
303 analysis. vrp is the only pass (including ipa-vrp)
304 that clears pt.null via set_ptr_nonnull when it knows
305 for sure. PTA will preserves the pt.null value set by VRP.
307 When PTA analysis is improved, pt.anything, pt.nonlocal
308 and pt.escaped may also has to be considered before
309 deciding that pointer cannot point to NULL. */
313 // Update the global range for NAME into the SSA_RANGE_NAME_INFO and
314 // SSA_NAME_PTR_INFO fields. Return TRUE if the range for NAME was
318 update_global_range (vrange
&r
, tree name
)
320 tree type
= TREE_TYPE (name
);
322 if (r
.undefined_p () || r
.varying_p ())
325 if (INTEGRAL_TYPE_P (type
))
327 // If a global range already exists, incorporate it.
328 if (SSA_NAME_RANGE_INFO (name
))
331 get_ssa_name_range_info (glob
, name
);
334 if (r
.undefined_p ())
337 set_range_info (name
, as_a
<irange
> (r
));
340 else if (POINTER_TYPE_P (type
))
344 set_ptr_nonnull (name
);
351 // Return the legacy global range for NAME if it has one, otherwise
355 get_range_global (vrange
&r
, tree name
)
357 tree type
= TREE_TYPE (name
);
359 if (SSA_NAME_IS_DEFAULT_DEF (name
))
361 tree sym
= SSA_NAME_VAR (name
);
362 // Adapted from vr_values::get_lattice_entry().
363 // Use a range from an SSA_NAME's available range.
364 if (TREE_CODE (sym
) == PARM_DECL
)
366 // Try to use the "nonnull" attribute to create ~[0, 0]
367 // anti-ranges for pointers. Note that this is only valid with
368 // default definitions of PARM_DECLs.
369 if (POINTER_TYPE_P (type
)
370 && ((cfun
&& nonnull_arg_p (sym
))
371 || get_ssa_name_ptr_info_nonnull (name
)))
372 r
.set_nonzero (type
);
373 else if (INTEGRAL_TYPE_P (type
))
375 get_ssa_name_range_info (as_a
<irange
> (r
), name
);
376 if (r
.undefined_p ())
377 r
.set_varying (type
);
380 r
.set_varying (type
);
382 // If this is a local automatic with no definition, use undefined.
383 else if (TREE_CODE (sym
) != RESULT_DECL
)
386 r
.set_varying (type
);
388 else if (!POINTER_TYPE_P (type
) && SSA_NAME_RANGE_INFO (name
))
390 gcc_checking_assert (irange::supports_type_p (TREE_TYPE (name
)));
391 get_ssa_name_range_info (as_a
<irange
> (r
), name
);
392 if (r
.undefined_p ())
393 r
.set_varying (type
);
395 else if (POINTER_TYPE_P (type
) && SSA_NAME_PTR_INFO (name
))
397 if (get_ssa_name_ptr_info_nonnull (name
))
398 r
.set_nonzero (type
);
400 r
.set_varying (type
);
403 r
.set_varying (type
);
406 // This is where the ranger picks up global info to seed initial
407 // requests. It is a slightly restricted version of
408 // get_range_global() above.
410 // The reason for the difference is that we can always pick the
411 // default definition of an SSA with no adverse effects, but for other
412 // SSAs, if we pick things up to early, we may prematurely eliminate
413 // builtin_unreachables.
415 // Without this restriction, the test in g++.dg/tree-ssa/pr61034.C has
416 // all of its unreachable calls removed too early.
418 // See discussion here:
419 // https://gcc.gnu.org/pipermail/gcc-patches/2021-June/571709.html
422 gimple_range_global (vrange
&r
, tree name
)
424 tree type
= TREE_TYPE (name
);
425 gcc_checking_assert (TREE_CODE (name
) == SSA_NAME
);
427 if (SSA_NAME_IS_DEFAULT_DEF (name
) || (cfun
&& cfun
->after_inlining
)
428 || is_a
<gphi
*> (SSA_NAME_DEF_STMT (name
)))
430 get_range_global (r
, name
);
433 r
.set_varying (type
);
436 // ----------------------------------------------
437 // global_range_query implementation.
439 global_range_query global_ranges
;
442 global_range_query::range_of_expr (vrange
&r
, tree expr
, gimple
*stmt
)
444 tree type
= TREE_TYPE (expr
);
446 if (!irange::supports_type_p (type
) || !gimple_range_ssa_p (expr
))
447 return get_tree_range (r
, expr
, stmt
);
449 get_range_global (r
, expr
);
454 // Return any known relation between SSA1 and SSA2 before stmt S is executed.
455 // If GET_RANGE is true, query the range of both operands first to ensure
456 // the defintions have been processed and any relations have be created.
459 range_query::query_relation (gimple
*s
, tree ssa1
, tree ssa2
, bool get_range
)
461 if (!m_oracle
|| TREE_CODE (ssa1
) != SSA_NAME
|| TREE_CODE (ssa2
) != SSA_NAME
)
464 // Ensure ssa1 and ssa2 have both been evaluated.
467 Value_Range
tmp1 (TREE_TYPE (ssa1
));
468 Value_Range
tmp2 (TREE_TYPE (ssa2
));
469 range_of_expr (tmp1
, ssa1
, s
);
470 range_of_expr (tmp2
, ssa2
, s
);
472 return m_oracle
->query_relation (gimple_bb (s
), ssa1
, ssa2
);
475 // Return any known relation between SSA1 and SSA2 on edge E.
476 // If GET_RANGE is true, query the range of both operands first to ensure
477 // the defintions have been processed and any relations have be created.
480 range_query::query_relation (edge e
, tree ssa1
, tree ssa2
, bool get_range
)
483 if (!m_oracle
|| TREE_CODE (ssa1
) != SSA_NAME
|| TREE_CODE (ssa2
) != SSA_NAME
)
486 // Use destination block if it has a single predecessor, and this picks
487 // up any relation on the edge.
488 // Otherwise choose the src edge and the result is the same as on-exit.
489 if (!single_pred_p (e
->dest
))
494 // Ensure ssa1 and ssa2 have both been evaluated.
497 Value_Range
tmp (TREE_TYPE (ssa1
));
498 range_on_edge (tmp
, e
, ssa1
);
499 range_on_edge (tmp
, e
, ssa2
);
501 return m_oracle
->query_relation (bb
, ssa1
, ssa2
);