Branch data Line data Source code
1 : : /* Support routines for value queries.
2 : : Copyright (C) 2020-2024 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 : 10108322 : range_query::range_on_edge (vrange &r, edge, tree expr)
40 : : {
41 : 10108322 : return range_of_expr (r, expr);
42 : : }
43 : :
44 : : bool
45 : 1346393 : range_query::range_of_stmt (vrange &r, gimple *stmt, tree name)
46 : : {
47 : 1346393 : if (!name)
48 : 1346393 : name = gimple_get_lhs (stmt);
49 : :
50 : 1346393 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
51 : :
52 : 1346393 : if (name)
53 : 1346393 : return range_of_expr (r, name);
54 : : return false;
55 : : }
56 : :
57 : : tree
58 : 135756668 : range_query::value_of_expr (tree expr, gimple *stmt)
59 : : {
60 : 135756668 : tree t;
61 : :
62 : 135756668 : if (!Value_Range::supports_type_p (TREE_TYPE (expr)))
63 : : return NULL_TREE;
64 : :
65 : 133374309 : Value_Range r (TREE_TYPE (expr));
66 : :
67 : 133374309 : 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 : 133374309 : if (r.undefined_p ())
72 : 208646 : range_of_expr (r, expr);
73 : 133374309 : if (r.singleton_p (&t))
74 : 1390304 : return t;
75 : : }
76 : : return NULL_TREE;
77 : 133374309 : }
78 : :
79 : : tree
80 : 21363132 : range_query::value_on_edge (edge e, tree expr)
81 : : {
82 : 21363132 : tree t;
83 : :
84 : 21363132 : if (!Value_Range::supports_type_p (TREE_TYPE (expr)))
85 : : return NULL_TREE;
86 : 21125458 : Value_Range r (TREE_TYPE (expr));
87 : 21125458 : 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 : 21125458 : if (r.undefined_p ())
92 : 257932 : range_of_expr (r, expr);
93 : 21125458 : if (r.singleton_p (&t))
94 : 306803 : return t;
95 : : }
96 : : return NULL_TREE;
97 : :
98 : 21125458 : }
99 : :
100 : : tree
101 : 43538793 : range_query::value_of_stmt (gimple *stmt, tree name)
102 : : {
103 : 43538793 : tree t;
104 : :
105 : 43538793 : if (!name)
106 : 0 : name = gimple_get_lhs (stmt);
107 : :
108 : 43538793 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
109 : :
110 : 43538793 : if (!name || !Value_Range::supports_type_p (TREE_TYPE (name)))
111 : 1485090 : return NULL_TREE;
112 : 42053703 : Value_Range r (TREE_TYPE (name));
113 : 84107406 : if (range_of_stmt (r, stmt, name) && r.singleton_p (&t))
114 : 239004 : return t;
115 : : return NULL_TREE;
116 : :
117 : 42053703 : }
118 : :
119 : : void
120 : 0 : range_query::dump (FILE *)
121 : : {
122 : 0 : }
123 : :
124 : 130990071 : range_query::range_query ()
125 : : {
126 : 130990071 : m_oracle = NULL;
127 : 130990071 : }
128 : :
129 : 130990071 : range_query::~range_query ()
130 : : {
131 : 130990071 : }
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 : :
136 : : bool
137 : 238360682 : range_query::get_tree_range (vrange &r, tree expr, gimple *stmt)
138 : : {
139 : 238360682 : tree type;
140 : 238360682 : if (TYPE_P (expr))
141 : : type = expr;
142 : : else
143 : 238360682 : type = TREE_TYPE (expr);
144 : :
145 : 238360682 : if (!Value_Range::supports_type_p (type))
146 : : {
147 : 18586339 : r.set_undefined ();
148 : 18586339 : return false;
149 : : }
150 : 219774343 : if (expr == type)
151 : : {
152 : 0 : r.set_varying (type);
153 : 0 : return true;
154 : : }
155 : 219774343 : switch (TREE_CODE (expr))
156 : : {
157 : 181083861 : case INTEGER_CST:
158 : 181083861 : {
159 : 181083861 : irange &i = as_a <irange> (r);
160 : 181083861 : if (TREE_OVERFLOW_P (expr))
161 : 113 : expr = drop_tree_overflow (expr);
162 : 181083861 : wide_int w = wi::to_wide (expr);
163 : 181083861 : i.set (TREE_TYPE (expr), w, w);
164 : 181083861 : return true;
165 : 181083861 : }
166 : :
167 : 5142570 : case REAL_CST:
168 : 5142570 : {
169 : 5142570 : frange &f = as_a <frange> (r);
170 : 5142570 : REAL_VALUE_TYPE *rv = TREE_REAL_CST_PTR (expr);
171 : 5142570 : if (real_isnan (rv))
172 : : {
173 : 10760 : bool sign = real_isneg (rv);
174 : 10760 : f.set_nan (TREE_TYPE (expr), sign);
175 : : }
176 : : else
177 : : {
178 : 5131810 : nan_state nan (false);
179 : 5131810 : f.set (TREE_TYPE (expr), *rv, *rv, nan);
180 : : }
181 : : return true;
182 : : }
183 : :
184 : 31996 : case SSA_NAME:
185 : 31996 : gimple_range_global (r, expr);
186 : 31996 : return true;
187 : :
188 : 6528618 : case ADDR_EXPR:
189 : 6528618 : {
190 : : // Handle &var which can show up in phi arguments.
191 : 6528618 : bool ov;
192 : 6528618 : if (tree_single_nonzero_warnv_p (expr, &ov))
193 : : {
194 : 6517853 : r.set_nonzero (type);
195 : 6517853 : return true;
196 : : }
197 : 10765 : break;
198 : : }
199 : :
200 : : default:
201 : : break;
202 : : }
203 : 26998063 : if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr))
204 : : {
205 : 6152978 : tree op0 = TREE_OPERAND (expr, 0);
206 : 6152978 : tree op1 = TREE_OPERAND (expr, 1);
207 : 6152978 : if (COMPARISON_CLASS_P (expr)
208 : 6152978 : && !Value_Range::supports_type_p (TREE_TYPE (op0)))
209 : : return false;
210 : 6152978 : range_op_handler op (TREE_CODE (expr));
211 : 6152978 : if (op)
212 : : {
213 : 6152978 : Value_Range r0 (TREE_TYPE (op0));
214 : 6152978 : Value_Range r1 (TREE_TYPE (op1));
215 : 6152978 : range_of_expr (r0, op0, stmt);
216 : 6152978 : range_of_expr (r1, op1, stmt);
217 : 6152978 : if (!op.fold_range (r, type, r0, r1))
218 : 0 : r.set_varying (type);
219 : 6152978 : }
220 : : else
221 : 0 : r.set_varying (type);
222 : 6152978 : return true;
223 : : }
224 : 20845085 : if (UNARY_CLASS_P (expr))
225 : : {
226 : 4465168 : range_op_handler op (TREE_CODE (expr));
227 : 4465168 : tree op0_type = TREE_TYPE (TREE_OPERAND (expr, 0));
228 : 4465168 : if (op && Value_Range::supports_type_p (op0_type))
229 : : {
230 : 4465040 : Value_Range r0 (TREE_TYPE (TREE_OPERAND (expr, 0)));
231 : 4465040 : Value_Range r1 (type);
232 : 4465040 : r1.set_varying (type);
233 : 4465040 : range_of_expr (r0, TREE_OPERAND (expr, 0), stmt);
234 : 4465040 : if (!op.fold_range (r, type, r0, r1))
235 : 0 : r.set_varying (type);
236 : 4465040 : }
237 : : else
238 : 128 : r.set_varying (type);
239 : 4465168 : return true;
240 : : }
241 : 16379917 : r.set_varying (type);
242 : 16379917 : return true;
243 : : }
244 : :
245 : : // Return the range for NAME from SSA_NAME_RANGE_INFO.
246 : :
247 : : static inline void
248 : 130181479 : get_ssa_name_range_info (vrange &r, const_tree name)
249 : : {
250 : 130181479 : tree type = TREE_TYPE (name);
251 : 130181479 : gcc_checking_assert (!POINTER_TYPE_P (type));
252 : 130181479 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
253 : :
254 : 130181479 : vrange_storage *ri = SSA_NAME_RANGE_INFO (name);
255 : :
256 : 130181479 : if (ri)
257 : 116315761 : ri->get_vrange (r, TREE_TYPE (name));
258 : : else
259 : 13865718 : r.set_varying (type);
260 : 130181479 : }
261 : :
262 : : // Return nonnull attribute of pointer NAME from SSA_NAME_PTR_INFO.
263 : :
264 : : static inline bool
265 : 69903311 : get_ssa_name_ptr_info_nonnull (const_tree name)
266 : : {
267 : 69903311 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
268 : 69903311 : struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
269 : 69903311 : 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 : 68704847 : 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 : :
286 : : static void
287 : 481274480 : get_range_global (vrange &r, tree name, struct function *fun = cfun)
288 : : {
289 : 481274480 : tree type = TREE_TYPE (name);
290 : :
291 : 481274480 : if (SSA_NAME_IS_DEFAULT_DEF (name))
292 : : {
293 : 36541009 : 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 : 36541009 : 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 : 33899051 : if (POINTER_TYPE_P (type)
302 : 33899051 : && ((cfun && fun == cfun && nonnull_arg_p (sym))
303 : 10810962 : || get_ssa_name_ptr_info_nonnull (name)))
304 : 9021449 : r.set_nonzero (type);
305 : 24877602 : else if (!POINTER_TYPE_P (type))
306 : : {
307 : 14115205 : get_ssa_name_range_info (r, name);
308 : 14115205 : if (r.undefined_p ())
309 : 0 : r.set_varying (type);
310 : : }
311 : : else
312 : 10762397 : r.set_varying (type);
313 : : }
314 : : // If this is a local automatic with no definition, use undefined.
315 : 2641958 : else if (TREE_CODE (sym) != RESULT_DECL)
316 : 2377955 : r.set_undefined ();
317 : : else
318 : 264003 : r.set_varying (type);
319 : : }
320 : 444733471 : else if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name))
321 : : {
322 : 116066274 : get_ssa_name_range_info (r, name);
323 : 116066274 : if (r.undefined_p ())
324 : 0 : r.set_varying (type);
325 : : }
326 : 328667197 : else if (POINTER_TYPE_P (type) && SSA_NAME_PTR_INFO (name))
327 : : {
328 : 59092349 : if (get_ssa_name_ptr_info_nonnull (name))
329 : 8263801 : r.set_nonzero (type);
330 : : else
331 : 50828548 : r.set_varying (type);
332 : : }
333 : : else
334 : 269574848 : r.set_varying (type);
335 : 481274480 : }
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 : :
352 : : void
353 : 266461375 : gimple_range_global (vrange &r, tree name, struct function *fun)
354 : : {
355 : 266461375 : tree type = TREE_TYPE (name);
356 : 266461375 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
357 : :
358 : 241390509 : if (SSA_NAME_IS_DEFAULT_DEF (name) || (fun && fun->after_inlining)
359 : 308565043 : || is_a<gphi *> (SSA_NAME_DEF_STMT (name)))
360 : : {
361 : 228362063 : get_range_global (r, name, fun);
362 : 228362063 : return;
363 : : }
364 : 38099312 : r.set_varying (type);
365 : : }
366 : :
367 : : // ----------------------------------------------
368 : : // global_range_query implementation.
369 : :
370 : : global_range_query global_ranges;
371 : :
372 : : bool
373 : 350842402 : global_range_query::range_of_expr (vrange &r, tree expr, gimple *stmt)
374 : : {
375 : 350842402 : if (!gimple_range_ssa_p (expr))
376 : 97929985 : return get_tree_range (r, expr, stmt);
377 : :
378 : 252912417 : get_range_global (r, expr);
379 : :
380 : 252912417 : 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 : :
387 : : relation_kind
388 : 81397130 : range_query::query_relation (gimple *s, tree ssa1, tree ssa2, bool get_range)
389 : : {
390 : 81397130 : 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 : 23008510 : if (get_range)
395 : : {
396 : 23008510 : Value_Range tmp1 (TREE_TYPE (ssa1));
397 : 23008510 : Value_Range tmp2 (TREE_TYPE (ssa2));
398 : 23008510 : range_of_expr (tmp1, ssa1, s);
399 : 23008510 : range_of_expr (tmp2, ssa2, s);
400 : 23008510 : }
401 : 23008510 : return m_oracle->query_relation (gimple_bb (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 : :
408 : : relation_kind
409 : 44596775 : range_query::query_relation (edge e, tree ssa1, tree ssa2, bool get_range)
410 : : {
411 : 44596775 : basic_block bb;
412 : 44596775 : 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 : 52626738 : if (!single_pred_p (e->dest))
419 : 24760523 : bb = e->src;
420 : : else
421 : : bb = e->dest;
422 : :
423 : : // Ensure ssa1 and ssa2 have both been evaluated.
424 : 26313369 : if (get_range)
425 : : {
426 : 0 : Value_Range tmp (TREE_TYPE (ssa1));
427 : 0 : range_on_edge (tmp, e, ssa1);
428 : 0 : range_on_edge (tmp, e, ssa2);
429 : 0 : }
430 : 26313369 : return m_oracle->query_relation (bb, ssa1, ssa2);
431 : : }
|
