Daily bump.
[official-gcc.git] / gcc / value-query.cc
blob17ebd86ce5f414e5f742e59eebd1d29e8527c8be
1 /* Support routines for value queries.
2 Copyright (C) 2020-2021 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)
11 any later version.
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/>. */
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-range-equiv.h"
32 #include "value-query.h"
33 #include "alloc-pool.h"
34 #include "gimple-range.h"
36 // value_query default methods.
38 tree
39 value_query::value_on_edge (edge, tree expr)
41 return value_of_expr (expr);
44 tree
45 value_query::value_of_stmt (gimple *stmt, tree name)
47 if (!name)
48 name = gimple_get_lhs (stmt);
50 gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
52 if (name)
53 return value_of_expr (name);
54 return NULL_TREE;
57 // range_query default methods.
59 bool
60 range_query::range_on_edge (irange &r, edge, tree expr)
62 return range_of_expr (r, expr);
65 bool
66 range_query::range_of_stmt (irange &r, gimple *stmt, tree name)
68 if (!name)
69 name = gimple_get_lhs (stmt);
71 gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
73 if (name)
74 return range_of_expr (r, name);
75 return false;
78 tree
79 range_query::value_of_expr (tree expr, gimple *stmt)
81 tree t;
82 int_range_max r;
84 if (!irange::supports_type_p (TREE_TYPE (expr)))
85 return NULL_TREE;
87 if (range_of_expr (r, expr, stmt))
89 // A constant used in an unreachable block oftens returns as UNDEFINED.
90 // If the result is undefined, check the global value for a constant.
91 if (r.undefined_p ())
92 range_of_expr (r, expr);
93 if (r.singleton_p (&t))
94 return t;
96 return NULL_TREE;
99 tree
100 range_query::value_on_edge (edge e, tree expr)
102 tree t;
103 int_range_max r;
105 if (!irange::supports_type_p (TREE_TYPE (expr)))
106 return NULL_TREE;
107 if (range_on_edge (r, e, expr))
109 // A constant used in an unreachable block oftens returns as UNDEFINED.
110 // If the result is undefined, check the global value for a constant.
111 if (r.undefined_p ())
112 range_of_expr (r, expr);
113 if (r.singleton_p (&t))
114 return t;
116 return NULL_TREE;
120 tree
121 range_query::value_of_stmt (gimple *stmt, tree name)
123 tree t;
124 int_range_max r;
126 if (!name)
127 name = gimple_get_lhs (stmt);
129 gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
131 if (!name || !irange::supports_type_p (TREE_TYPE (name)))
132 return NULL_TREE;
133 if (range_of_stmt (r, stmt, name) && r.singleton_p (&t))
134 return t;
135 return NULL_TREE;
139 void
140 range_query::dump (FILE *)
144 // valuation_query support routines for value_range_equiv's.
146 class equiv_allocator : public object_allocator<value_range_equiv>
148 public:
149 equiv_allocator ()
150 : object_allocator<value_range_equiv> ("equiv_allocator pool") { }
153 value_range_equiv *
154 range_query::allocate_value_range_equiv ()
156 return new (equiv_alloc->allocate ()) value_range_equiv;
159 void
160 range_query::free_value_range_equiv (value_range_equiv *v)
162 equiv_alloc->remove (v);
165 const class value_range_equiv *
166 range_query::get_value_range (const_tree expr, gimple *stmt)
168 int_range_max r;
169 if (range_of_expr (r, const_cast<tree> (expr), stmt))
170 return new (equiv_alloc->allocate ()) value_range_equiv (r);
171 return new (equiv_alloc->allocate ()) value_range_equiv (TREE_TYPE (expr));
174 range_query::range_query ()
176 equiv_alloc = new equiv_allocator;
177 m_oracle = NULL;
180 range_query::~range_query ()
182 equiv_alloc->release ();
183 delete equiv_alloc;
186 // Return a range in R for the tree EXPR. Return true if a range is
187 // representable, and UNDEFINED/false if not.
189 bool
190 range_query::get_tree_range (irange &r, tree expr, gimple *stmt)
192 tree type;
193 if (TYPE_P (expr))
194 type = expr;
195 else
196 type = TREE_TYPE (expr);
198 if (!irange::supports_type_p (type))
200 r.set_undefined ();
201 return false;
203 if (expr == type)
205 r.set_varying (type);
206 return true;
208 switch (TREE_CODE (expr))
210 case INTEGER_CST:
211 if (TREE_OVERFLOW_P (expr))
212 expr = drop_tree_overflow (expr);
213 r.set (expr, expr);
214 return true;
216 case SSA_NAME:
217 r = gimple_range_global (expr);
218 return true;
220 case ADDR_EXPR:
222 // Handle &var which can show up in phi arguments.
223 bool ov;
224 if (tree_single_nonzero_warnv_p (expr, &ov))
226 r = range_nonzero (type);
227 return true;
229 break;
232 default:
233 break;
235 if (BINARY_CLASS_P (expr))
237 range_operator *op = range_op_handler (TREE_CODE (expr), type);
238 if (op)
240 int_range_max r0, r1;
241 range_of_expr (r0, TREE_OPERAND (expr, 0), stmt);
242 range_of_expr (r1, TREE_OPERAND (expr, 1), stmt);
243 op->fold_range (r, type, r0, r1);
245 else
246 r.set_varying (type);
247 return true;
249 if (UNARY_CLASS_P (expr))
251 range_operator *op = range_op_handler (TREE_CODE (expr), type);
252 if (op)
254 int_range_max r0;
255 range_of_expr (r0, TREE_OPERAND (expr, 0), stmt);
256 op->fold_range (r, type, r0, int_range<1> (type));
258 else
259 r.set_varying (type);
260 return true;
262 r.set_varying (type);
263 return true;
266 // Return the range for NAME from SSA_NAME_RANGE_INFO.
268 static inline void
269 get_ssa_name_range_info (irange &r, const_tree name)
271 tree type = TREE_TYPE (name);
272 gcc_checking_assert (!POINTER_TYPE_P (type));
273 gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
275 range_info_def *ri = SSA_NAME_RANGE_INFO (name);
277 // Return VR_VARYING for SSA_NAMEs with NULL RANGE_INFO or SSA_NAMEs
278 // with integral types width > 2 * HOST_BITS_PER_WIDE_INT precision.
279 if (!ri || (GET_MODE_PRECISION (SCALAR_INT_TYPE_MODE (TREE_TYPE (name)))
280 > 2 * HOST_BITS_PER_WIDE_INT))
281 r.set_varying (type);
282 else
283 r.set (wide_int_to_tree (type, ri->get_min ()),
284 wide_int_to_tree (type, ri->get_max ()),
285 SSA_NAME_RANGE_TYPE (name));
288 // Return nonnull attribute of pointer NAME from SSA_NAME_PTR_INFO.
290 static inline bool
291 get_ssa_name_ptr_info_nonnull (const_tree name)
293 gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
294 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
295 if (pi == NULL)
296 return false;
297 /* TODO Now pt->null is conservatively set to true in PTA
298 analysis. vrp is the only pass (including ipa-vrp)
299 that clears pt.null via set_ptr_nonnull when it knows
300 for sure. PTA will preserves the pt.null value set by VRP.
302 When PTA analysis is improved, pt.anything, pt.nonlocal
303 and pt.escaped may also has to be considered before
304 deciding that pointer cannot point to NULL. */
305 return !pi->pt.null;
308 // Update the global range for NAME into the SSA_RANGE_NAME_INFO and
309 // SSA_NAME_PTR_INFO fields. Return TRUE if the range for NAME was
310 // updated.
312 bool
313 update_global_range (irange &r, tree name)
315 tree type = TREE_TYPE (name);
317 if (r.undefined_p () || r.varying_p ())
318 return false;
320 if (INTEGRAL_TYPE_P (type))
322 // If a global range already exists, incorporate it.
323 if (SSA_NAME_RANGE_INFO (name))
325 value_range glob;
326 get_ssa_name_range_info (glob, name);
327 r.intersect (glob);
329 if (r.undefined_p ())
330 return false;
332 value_range vr = r;
333 set_range_info (name, vr);
334 return true;
336 else if (POINTER_TYPE_P (type))
338 if (r.nonzero_p ())
340 set_ptr_nonnull (name);
341 return true;
344 return false;
347 // Return the legacy global range for NAME if it has one, otherwise
348 // return VARYING.
350 static void
351 get_range_global (irange &r, tree name)
353 tree type = TREE_TYPE (name);
355 if (SSA_NAME_IS_DEFAULT_DEF (name))
357 tree sym = SSA_NAME_VAR (name);
358 // Adapted from vr_values::get_lattice_entry().
359 // Use a range from an SSA_NAME's available range.
360 if (TREE_CODE (sym) == PARM_DECL)
362 // Try to use the "nonnull" attribute to create ~[0, 0]
363 // anti-ranges for pointers. Note that this is only valid with
364 // default definitions of PARM_DECLs.
365 if (POINTER_TYPE_P (type)
366 && ((cfun && nonnull_arg_p (sym))
367 || get_ssa_name_ptr_info_nonnull (name)))
368 r.set_nonzero (type);
369 else if (INTEGRAL_TYPE_P (type))
371 get_ssa_name_range_info (r, name);
372 if (r.undefined_p ())
373 r.set_varying (type);
375 else
376 r.set_varying (type);
378 // If this is a local automatic with no definition, use undefined.
379 else if (TREE_CODE (sym) != RESULT_DECL)
380 r.set_undefined ();
381 else
382 r.set_varying (type);
384 else if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name))
386 get_ssa_name_range_info (r, name);
387 if (r.undefined_p ())
388 r.set_varying (type);
390 else if (POINTER_TYPE_P (type) && SSA_NAME_PTR_INFO (name))
392 if (get_ssa_name_ptr_info_nonnull (name))
393 r.set_nonzero (type);
394 else
395 r.set_varying (type);
397 else
398 r.set_varying (type);
401 // This is where the ranger picks up global info to seed initial
402 // requests. It is a slightly restricted version of
403 // get_range_global() above.
405 // The reason for the difference is that we can always pick the
406 // default definition of an SSA with no adverse effects, but for other
407 // SSAs, if we pick things up to early, we may prematurely eliminate
408 // builtin_unreachables.
410 // Without this restriction, the test in g++.dg/tree-ssa/pr61034.C has
411 // all of its unreachable calls removed too early.
413 // See discussion here:
414 // https://gcc.gnu.org/pipermail/gcc-patches/2021-June/571709.html
416 value_range
417 gimple_range_global (tree name)
419 tree type = TREE_TYPE (name);
420 gcc_checking_assert (TREE_CODE (name) == SSA_NAME
421 && irange::supports_type_p (type));
423 if (SSA_NAME_IS_DEFAULT_DEF (name) || (cfun && cfun->after_inlining)
424 || is_a<gphi *> (SSA_NAME_DEF_STMT (name)))
426 value_range vr;
427 get_range_global (vr, name);
428 return vr;
430 return value_range (type);
433 // ----------------------------------------------
434 // global_range_query implementation.
436 global_range_query global_ranges;
438 // Like get_range_query, but for accessing global ranges.
440 range_query *
441 get_global_range_query ()
443 return &global_ranges;
446 bool
447 global_range_query::range_of_expr (irange &r, tree expr, gimple *stmt)
449 tree type = TREE_TYPE (expr);
451 if (!irange::supports_type_p (type) || !gimple_range_ssa_p (expr))
452 return get_tree_range (r, expr, stmt);
454 get_range_global (r, expr);
456 return true;
459 // Return any known relation between SSA1 and SSA2 before stmt S is executed.
460 // If GET_RANGE is true, query the range of both operands first to ensure
461 // the defintions have been processed and any relations have be created.
463 relation_kind
464 range_query::query_relation (gimple *s, tree ssa1, tree ssa2, bool get_range)
466 int_range_max tmp;
467 if (!m_oracle || TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
468 return VREL_NONE;
470 // Ensure ssa1 and ssa2 have both been evaluated.
471 if (get_range)
473 range_of_expr (tmp, ssa1, s);
474 range_of_expr (tmp, ssa2, s);
476 return m_oracle->query_relation (gimple_bb (s), ssa1, ssa2);
479 // Return any known relation between SSA1 and SSA2 on edge E.
480 // If GET_RANGE is true, query the range of both operands first to ensure
481 // the defintions have been processed and any relations have be created.
483 relation_kind
484 range_query::query_relation (edge e, tree ssa1, tree ssa2, bool get_range)
486 basic_block bb;
487 int_range_max tmp;
488 if (!m_oracle || TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
489 return VREL_NONE;
491 // Use destination block if it has a single predecessor, and this picks
492 // up any relation on the edge.
493 // Otherwise choose the src edge and the result is the same as on-exit.
494 if (!single_pred_p (e->dest))
495 bb = e->src;
496 else
497 bb = e->dest;
499 // Ensure ssa1 and ssa2 have both been evaluated.
500 if (get_range)
502 range_on_edge (tmp, e, ssa1);
503 range_on_edge (tmp, e, ssa2);
505 return m_oracle->query_relation (bb, ssa1, ssa2);