1/* Support routines for value queries.
2 Copyright (C) 2020-2023 Free Software Foundation, Inc.
3 Contributed by Aldy Hernandez <aldyh@redhat.com> and
4 Andrew MacLeod <amacleod@redhat.com>.
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify
9it under the terms of the GNU General Public License as published by
10the Free Software Foundation; either version 3, or (at your option)
11any later version.
12
13GCC is distributed in the hope that it will be useful,
14but WITHOUT ANY WARRANTY; without even the implied warranty of
15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16GNU General Public License for more details.
17
18You should have received a copy of the GNU General Public License
19along 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
38bool
39range_query::range_on_edge (vrange &r, edge, tree expr)
40{
41 return range_of_expr (r, expr);
42}
43
44bool
45range_query::range_of_stmt (vrange &r, gimple *stmt, tree name)
46{
47 if (!name)
48 name = gimple_get_lhs (stmt);
49
50 gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
51
52 if (name)
53 return range_of_expr (r, expr: name);
54 return false;
55}
56
57tree
58range_query::value_of_expr (tree expr, gimple *stmt)
59{
60 tree t;
61
62 if (!Value_Range::supports_type_p (TREE_TYPE (expr)))
63 return NULL_TREE;
64
65 Value_Range r (TREE_TYPE (expr));
66
67 if (range_of_expr (r, expr, stmt))
68 {
69 // A constant used in an unreachable block often returns as UNDEFINED.
70 // If the result is undefined, check the global value for a constant.
71 if (r.undefined_p ())
72 range_of_expr (r, expr);
73 if (r.singleton_p (result: &t))
74 return t;
75 }
76 return NULL_TREE;
77}
78
79tree
80range_query::value_on_edge (edge e, tree expr)
81{
82 tree t;
83
84 if (!Value_Range::supports_type_p (TREE_TYPE (expr)))
85 return NULL_TREE;
86 Value_Range r (TREE_TYPE (expr));
87 if (range_on_edge (r, e, expr))
88 {
89 // A constant used in an unreachable block often 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 (result: &t))
94 return t;
95 }
96 return NULL_TREE;
97
98}
99
100tree
101range_query::value_of_stmt (gimple *stmt, tree name)
102{
103 tree t;
104
105 if (!name)
106 name = gimple_get_lhs (stmt);
107
108 gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
109
110 if (!name || !Value_Range::supports_type_p (TREE_TYPE (name)))
111 return NULL_TREE;
112 Value_Range r (TREE_TYPE (name));
113 if (range_of_stmt (r, stmt, name) && r.singleton_p (result: &t))
114 return t;
115 return NULL_TREE;
116
117}
118
119void
120range_query::dump (FILE *)
121{
122}
123
124range_query::range_query ()
125{
126 m_oracle = NULL;
127}
128
129range_query::~range_query ()
130{
131}
132
133// Return a range in R for the tree EXPR. Return true if a range is
134// representable, and UNDEFINED/false if not.
135
136bool
137range_query::get_tree_range (vrange &r, tree expr, gimple *stmt)
138{
139 tree type;
140 if (TYPE_P (expr))
141 type = expr;
142 else
143 type = TREE_TYPE (expr);
144
145 if (!Value_Range::supports_type_p (type))
146 {
147 r.set_undefined ();
148 return false;
149 }
150 if (expr == type)
151 {
152 r.set_varying (type);
153 return true;
154 }
155 switch (TREE_CODE (expr))
156 {
157 case INTEGER_CST:
158 {
159 irange &i = as_a <irange> (v&: r);
160 if (TREE_OVERFLOW_P (expr))
161 expr = drop_tree_overflow (expr);
162 wide_int w = wi::to_wide (t: expr);
163 i.set (TREE_TYPE (expr), w, w);
164 return true;
165 }
166
167 case REAL_CST:
168 {
169 frange &f = as_a <frange> (v&: r);
170 REAL_VALUE_TYPE *rv = TREE_REAL_CST_PTR (expr);
171 if (real_isnan (rv))
172 {
173 bool sign = real_isneg (rv);
174 f.set_nan (TREE_TYPE (expr), sign);
175 }
176 else
177 {
178 nan_state nan (false);
179 f.set (TREE_TYPE (expr), *rv, *rv, nan);
180 }
181 return true;
182 }
183
184 case SSA_NAME:
185 gimple_range_global (v&: r, name: expr);
186 return true;
187
188 case ADDR_EXPR:
189 {
190 // Handle &var which can show up in phi arguments.
191 bool ov;
192 if (tree_single_nonzero_warnv_p (expr, &ov))
193 {
194 r.set_nonzero (type);
195 return true;
196 }
197 break;
198 }
199
200 default:
201 break;
202 }
203 if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr))
204 {
205 tree op0 = TREE_OPERAND (expr, 0);
206 tree op1 = TREE_OPERAND (expr, 1);
207 if (COMPARISON_CLASS_P (expr)
208 && !Value_Range::supports_type_p (TREE_TYPE (op0)))
209 return false;
210 range_op_handler op (TREE_CODE (expr));
211 if (op)
212 {
213 Value_Range r0 (TREE_TYPE (op0));
214 Value_Range r1 (TREE_TYPE (op1));
215 range_of_expr (r&: r0, expr: op0, stmt);
216 range_of_expr (r&: r1, expr: op1, stmt);
217 if (!op.fold_range (r, type, lh: r0, rh: r1))
218 r.set_varying (type);
219 }
220 else
221 r.set_varying (type);
222 return true;
223 }
224 if (UNARY_CLASS_P (expr))
225 {
226 range_op_handler op (TREE_CODE (expr));
227 tree op0_type = TREE_TYPE (TREE_OPERAND (expr, 0));
228 if (op && Value_Range::supports_type_p (type: op0_type))
229 {
230 Value_Range r0 (TREE_TYPE (TREE_OPERAND (expr, 0)));
231 Value_Range r1 (type);
232 r1.set_varying (type);
233 range_of_expr (r&: r0, TREE_OPERAND (expr, 0), stmt);
234 if (!op.fold_range (r, type, lh: r0, rh: r1))
235 r.set_varying (type);
236 }
237 else
238 r.set_varying (type);
239 return true;
240 }
241 r.set_varying (type);
242 return true;
243}
244
245// Return the range for NAME from SSA_NAME_RANGE_INFO.
246
247static inline void
248get_ssa_name_range_info (vrange &r, const_tree name)
249{
250 tree type = TREE_TYPE (name);
251 gcc_checking_assert (!POINTER_TYPE_P (type));
252 gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
253
254 vrange_storage *ri = SSA_NAME_RANGE_INFO (name);
255
256 if (ri)
257 ri->get_vrange (r, TREE_TYPE (name));
258 else
259 r.set_varying (type);
260}
261
262// Return nonnull attribute of pointer NAME from SSA_NAME_PTR_INFO.
263
264static inline bool
265get_ssa_name_ptr_info_nonnull (const_tree name)
266{
267 gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
268 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
269 if (pi == NULL)
270 return false;
271 /* TODO Now pt->null is conservatively set to true in PTA
272 analysis. vrp is the only pass (including ipa-vrp)
273 that clears pt.null via set_ptr_nonnull when it knows
274 for sure. PTA will preserves the pt.null value set by VRP.
275
276 When PTA analysis is improved, pt.anything, pt.nonlocal
277 and pt.escaped may also has to be considered before
278 deciding that pointer cannot point to NULL. */
279 return !pi->pt.null;
280}
281
282// Update the global range for NAME into the SSA_RANGE_NAME_INFO and
283// Return the legacy global range for NAME if it has one, otherwise
284// return VARYING.
285
286static void
287get_range_global (vrange &r, tree name, struct function *fun = cfun)
288{
289 tree type = TREE_TYPE (name);
290
291 if (SSA_NAME_IS_DEFAULT_DEF (name))
292 {
293 tree sym = SSA_NAME_VAR (name);
294 // Adapted from vr_values::get_lattice_entry().
295 // Use a range from an SSA_NAME's available range.
296 if (TREE_CODE (sym) == PARM_DECL)
297 {
298 // Try to use the "nonnull" attribute to create ~[0, 0]
299 // anti-ranges for pointers. Note that this is only valid with
300 // default definitions of PARM_DECLs.
301 if (POINTER_TYPE_P (type)
302 && ((cfun && fun == cfun && nonnull_arg_p (sym))
303 || get_ssa_name_ptr_info_nonnull (name)))
304 r.set_nonzero (type);
305 else if (!POINTER_TYPE_P (type))
306 {
307 get_ssa_name_range_info (r, name);
308 if (r.undefined_p ())
309 r.set_varying (type);
310 }
311 else
312 r.set_varying (type);
313 }
314 // If this is a local automatic with no definition, use undefined.
315 else if (TREE_CODE (sym) != RESULT_DECL)
316 r.set_undefined ();
317 else
318 r.set_varying (type);
319 }
320 else if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name))
321 {
322 get_ssa_name_range_info (r, name);
323 if (r.undefined_p ())
324 r.set_varying (type);
325 }
326 else if (POINTER_TYPE_P (type) && SSA_NAME_PTR_INFO (name))
327 {
328 if (get_ssa_name_ptr_info_nonnull (name))
329 r.set_nonzero (type);
330 else
331 r.set_varying (type);
332 }
333 else
334 r.set_varying (type);
335}
336
337// This is where the ranger picks up global info to seed initial
338// requests. It is a slightly restricted version of
339// get_range_global() above.
340//
341// The reason for the difference is that we can always pick the
342// default definition of an SSA with no adverse effects, but for other
343// SSAs, if we pick things up to early, we may prematurely eliminate
344// builtin_unreachables.
345//
346// Without this restriction, the test in g++.dg/tree-ssa/pr61034.C has
347// all of its unreachable calls removed too early.
348//
349// See discussion here:
350// https://gcc.gnu.org/pipermail/gcc-patches/2021-June/571709.html
351
352void
353gimple_range_global (vrange &r, tree name, struct function *fun)
354{
355 tree type = TREE_TYPE (name);
356 gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
357
358 if (SSA_NAME_IS_DEFAULT_DEF (name) || (fun && fun->after_inlining)
359 || is_a<gphi *> (SSA_NAME_DEF_STMT (name)))
360 {
361 get_range_global (r, name, fun);
362 return;
363 }
364 r.set_varying (type);
365}
366
367// ----------------------------------------------
368// global_range_query implementation.
369
370global_range_query global_ranges;
371
372bool
373global_range_query::range_of_expr (vrange &r, tree expr, gimple *stmt)
374{
375 if (!gimple_range_ssa_p (exp: expr))
376 return get_tree_range (r, expr, stmt);
377
378 get_range_global (r, name: expr);
379
380 return true;
381}
382
383// Return any known relation between SSA1 and SSA2 before stmt S is executed.
384// If GET_RANGE is true, query the range of both operands first to ensure
385// the definitions have been processed and any relations have be created.
386
387relation_kind
388range_query::query_relation (gimple *s, tree ssa1, tree ssa2, bool get_range)
389{
390 if (!m_oracle || TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
391 return VREL_VARYING;
392
393 // Ensure ssa1 and ssa2 have both been evaluated.
394 if (get_range)
395 {
396 Value_Range tmp1 (TREE_TYPE (ssa1));
397 Value_Range tmp2 (TREE_TYPE (ssa2));
398 range_of_expr (r&: tmp1, expr: ssa1, s);
399 range_of_expr (r&: tmp2, expr: ssa2, s);
400 }
401 return m_oracle->query_relation (gimple_bb (g: s), ssa1, ssa2);
402}
403
404// Return any known relation between SSA1 and SSA2 on edge E.
405// If GET_RANGE is true, query the range of both operands first to ensure
406// the definitions have been processed and any relations have be created.
407
408relation_kind
409range_query::query_relation (edge e, tree ssa1, tree ssa2, bool get_range)
410{
411 basic_block bb;
412 if (!m_oracle || TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
413 return VREL_VARYING;
414
415 // Use destination block if it has a single predecessor, and this picks
416 // up any relation on the edge.
417 // Otherwise choose the src edge and the result is the same as on-exit.
418 if (!single_pred_p (bb: e->dest))
419 bb = e->src;
420 else
421 bb = e->dest;
422
423 // Ensure ssa1 and ssa2 have both been evaluated.
424 if (get_range)
425 {
426 Value_Range tmp (TREE_TYPE (ssa1));
427 range_on_edge (r&: tmp, e, expr: ssa1);
428 range_on_edge (r&: tmp, e, expr: ssa2);
429 }
430 return m_oracle->query_relation (bb, ssa1, ssa2);
431}
432

source code of gcc/value-query.cc