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>.
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-range-equiv.h"
32 #include "value-query.h"
33 #include "alloc-pool.h"
34 #include "gimple-range.h"
35
36 // value_query default methods.
37
38 tree
value_on_edge(edge,tree expr)39 value_query::value_on_edge (edge, tree expr)
40 {
41 return value_of_expr (expr);
42 }
43
44 tree
value_of_stmt(gimple * stmt,tree name)45 value_query::value_of_stmt (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 value_of_expr (name);
54 return NULL_TREE;
55 }
56
57 // range_query default methods.
58
59 bool
range_on_edge(irange & r,edge,tree expr)60 range_query::range_on_edge (irange &r, edge, tree expr)
61 {
62 return range_of_expr (r, expr);
63 }
64
65 bool
range_of_stmt(irange & r,gimple * stmt,tree name)66 range_query::range_of_stmt (irange &r, gimple *stmt, tree name)
67 {
68 if (!name)
69 name = gimple_get_lhs (stmt);
70
71 gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
72
73 if (name)
74 return range_of_expr (r, name);
75 return false;
76 }
77
78 tree
value_of_expr(tree expr,gimple * stmt)79 range_query::value_of_expr (tree expr, gimple *stmt)
80 {
81 tree t;
82 int_range_max r;
83
84 if (!irange::supports_type_p (TREE_TYPE (expr)))
85 return NULL_TREE;
86
87 if (range_of_expr (r, expr, stmt))
88 {
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;
95 }
96 return NULL_TREE;
97 }
98
99 tree
value_on_edge(edge e,tree expr)100 range_query::value_on_edge (edge e, tree expr)
101 {
102 tree t;
103 int_range_max r;
104
105 if (!irange::supports_type_p (TREE_TYPE (expr)))
106 return NULL_TREE;
107 if (range_on_edge (r, e, expr))
108 {
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;
115 }
116 return NULL_TREE;
117
118 }
119
120 tree
value_of_stmt(gimple * stmt,tree name)121 range_query::value_of_stmt (gimple *stmt, tree name)
122 {
123 tree t;
124 int_range_max r;
125
126 if (!name)
127 name = gimple_get_lhs (stmt);
128
129 gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
130
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;
136
137 }
138
139 void
dump(FILE *)140 range_query::dump (FILE *)
141 {
142 }
143
144 // valuation_query support routines for value_range_equiv's.
145
146 class equiv_allocator : public object_allocator<value_range_equiv>
147 {
148 public:
equiv_allocator()149 equiv_allocator ()
150 : object_allocator<value_range_equiv> ("equiv_allocator pool") { }
151 };
152
153 value_range_equiv *
allocate_value_range_equiv()154 range_query::allocate_value_range_equiv ()
155 {
156 return new (equiv_alloc->allocate ()) value_range_equiv;
157 }
158
159 void
free_value_range_equiv(value_range_equiv * v)160 range_query::free_value_range_equiv (value_range_equiv *v)
161 {
162 equiv_alloc->remove (v);
163 }
164
165 const class value_range_equiv *
get_value_range(const_tree expr,gimple * stmt)166 range_query::get_value_range (const_tree expr, gimple *stmt)
167 {
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));
172 }
173
range_query()174 range_query::range_query ()
175 {
176 equiv_alloc = new equiv_allocator;
177 m_oracle = NULL;
178 }
179
~range_query()180 range_query::~range_query ()
181 {
182 equiv_alloc->release ();
183 delete equiv_alloc;
184 }
185
186 // Return a range in R for the tree EXPR. Return true if a range is
187 // representable, and UNDEFINED/false if not.
188
189 bool
get_tree_range(irange & r,tree expr,gimple * stmt)190 range_query::get_tree_range (irange &r, tree expr, gimple *stmt)
191 {
192 tree type;
193 if (TYPE_P (expr))
194 type = expr;
195 else
196 type = TREE_TYPE (expr);
197
198 if (!irange::supports_type_p (type))
199 {
200 r.set_undefined ();
201 return false;
202 }
203 if (expr == type)
204 {
205 r.set_varying (type);
206 return true;
207 }
208 switch (TREE_CODE (expr))
209 {
210 case INTEGER_CST:
211 if (TREE_OVERFLOW_P (expr))
212 expr = drop_tree_overflow (expr);
213 r.set (expr, expr);
214 return true;
215
216 case SSA_NAME:
217 r = gimple_range_global (expr);
218 return true;
219
220 case ADDR_EXPR:
221 {
222 // Handle &var which can show up in phi arguments.
223 bool ov;
224 if (tree_single_nonzero_warnv_p (expr, &ov))
225 {
226 r = range_nonzero (type);
227 return true;
228 }
229 break;
230 }
231
232 default:
233 break;
234 }
235 if (BINARY_CLASS_P (expr))
236 {
237 range_operator *op = range_op_handler (TREE_CODE (expr), type);
238 if (op)
239 {
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);
244 }
245 else
246 r.set_varying (type);
247 return true;
248 }
249 if (UNARY_CLASS_P (expr))
250 {
251 range_operator *op = range_op_handler (TREE_CODE (expr), type);
252 if (op)
253 {
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));
257 }
258 else
259 r.set_varying (type);
260 return true;
261 }
262 r.set_varying (type);
263 return true;
264 }
265
266 // Return the range for NAME from SSA_NAME_RANGE_INFO.
267
268 static inline void
get_ssa_name_range_info(irange & r,const_tree name)269 get_ssa_name_range_info (irange &r, const_tree name)
270 {
271 tree type = TREE_TYPE (name);
272 gcc_checking_assert (!POINTER_TYPE_P (type));
273 gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
274
275 range_info_def *ri = SSA_NAME_RANGE_INFO (name);
276
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));
286 }
287
288 // Return nonnull attribute of pointer NAME from SSA_NAME_PTR_INFO.
289
290 static inline bool
get_ssa_name_ptr_info_nonnull(const_tree name)291 get_ssa_name_ptr_info_nonnull (const_tree name)
292 {
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.
301
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;
306 }
307
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.
311
312 bool
update_global_range(irange & r,tree name)313 update_global_range (irange &r, tree name)
314 {
315 tree type = TREE_TYPE (name);
316
317 if (r.undefined_p () || r.varying_p ())
318 return false;
319
320 if (INTEGRAL_TYPE_P (type))
321 {
322 // If a global range already exists, incorporate it.
323 if (SSA_NAME_RANGE_INFO (name))
324 {
325 value_range glob;
326 get_ssa_name_range_info (glob, name);
327 r.intersect (glob);
328 }
329 if (r.undefined_p ())
330 return false;
331
332 value_range vr = r;
333 set_range_info (name, vr);
334 return true;
335 }
336 else if (POINTER_TYPE_P (type))
337 {
338 if (r.nonzero_p ())
339 {
340 set_ptr_nonnull (name);
341 return true;
342 }
343 }
344 return false;
345 }
346
347 // Return the legacy global range for NAME if it has one, otherwise
348 // return VARYING.
349
350 static void
get_range_global(irange & r,tree name)351 get_range_global (irange &r, tree name)
352 {
353 tree type = TREE_TYPE (name);
354
355 if (SSA_NAME_IS_DEFAULT_DEF (name))
356 {
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)
361 {
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))
370 {
371 get_ssa_name_range_info (r, name);
372 if (r.undefined_p ())
373 r.set_varying (type);
374 }
375 else
376 r.set_varying (type);
377 }
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);
383 }
384 else if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name))
385 {
386 get_ssa_name_range_info (r, name);
387 if (r.undefined_p ())
388 r.set_varying (type);
389 }
390 else if (POINTER_TYPE_P (type) && SSA_NAME_PTR_INFO (name))
391 {
392 if (get_ssa_name_ptr_info_nonnull (name))
393 r.set_nonzero (type);
394 else
395 r.set_varying (type);
396 }
397 else
398 r.set_varying (type);
399 }
400
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.
404 //
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.
409 //
410 // Without this restriction, the test in g++.dg/tree-ssa/pr61034.C has
411 // all of its unreachable calls removed too early.
412 //
413 // See discussion here:
414 // https://gcc.gnu.org/pipermail/gcc-patches/2021-June/571709.html
415
416 value_range
gimple_range_global(tree name)417 gimple_range_global (tree name)
418 {
419 tree type = TREE_TYPE (name);
420 gcc_checking_assert (TREE_CODE (name) == SSA_NAME
421 && irange::supports_type_p (type));
422
423 if (SSA_NAME_IS_DEFAULT_DEF (name) || (cfun && cfun->after_inlining)
424 || is_a<gphi *> (SSA_NAME_DEF_STMT (name)))
425 {
426 value_range vr;
427 get_range_global (vr, name);
428 return vr;
429 }
430 return value_range (type);
431 }
432
433 // ----------------------------------------------
434 // global_range_query implementation.
435
436 global_range_query global_ranges;
437
438 bool
range_of_expr(irange & r,tree expr,gimple * stmt)439 global_range_query::range_of_expr (irange &r, tree expr, gimple *stmt)
440 {
441 tree type = TREE_TYPE (expr);
442
443 if (!irange::supports_type_p (type) || !gimple_range_ssa_p (expr))
444 return get_tree_range (r, expr, stmt);
445
446 get_range_global (r, expr);
447
448 return true;
449 }
450
451 // Return any known relation between SSA1 and SSA2 before stmt S is executed.
452 // If GET_RANGE is true, query the range of both operands first to ensure
453 // the defintions have been processed and any relations have be created.
454
455 relation_kind
query_relation(gimple * s,tree ssa1,tree ssa2,bool get_range)456 range_query::query_relation (gimple *s, tree ssa1, tree ssa2, bool get_range)
457 {
458 int_range_max tmp;
459 if (!m_oracle || TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
460 return VREL_NONE;
461
462 // Ensure ssa1 and ssa2 have both been evaluated.
463 if (get_range)
464 {
465 range_of_expr (tmp, ssa1, s);
466 range_of_expr (tmp, ssa2, s);
467 }
468 return m_oracle->query_relation (gimple_bb (s), ssa1, ssa2);
469 }
470
471 // Return any known relation between SSA1 and SSA2 on edge E.
472 // If GET_RANGE is true, query the range of both operands first to ensure
473 // the defintions have been processed and any relations have be created.
474
475 relation_kind
query_relation(edge e,tree ssa1,tree ssa2,bool get_range)476 range_query::query_relation (edge e, tree ssa1, tree ssa2, bool get_range)
477 {
478 basic_block bb;
479 int_range_max tmp;
480 if (!m_oracle || TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
481 return VREL_NONE;
482
483 // Use destination block if it has a single predecessor, and this picks
484 // up any relation on the edge.
485 // Otherwise choose the src edge and the result is the same as on-exit.
486 if (!single_pred_p (e->dest))
487 bb = e->src;
488 else
489 bb = e->dest;
490
491 // Ensure ssa1 and ssa2 have both been evaluated.
492 if (get_range)
493 {
494 range_on_edge (tmp, e, ssa1);
495 range_on_edge (tmp, e, ssa2);
496 }
497 return m_oracle->query_relation (bb, ssa1, ssa2);
498 }
499