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 | |
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 | range_query::range_on_edge (vrange &r, edge, tree expr) |
40 | { |
41 | return range_of_expr (r, expr); |
42 | } |
43 | |
44 | bool |
45 | range_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 | |
57 | tree |
58 | range_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 | |
79 | tree |
80 | range_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 | |
100 | tree |
101 | range_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 | |
119 | void |
120 | range_query::dump (FILE *) |
121 | { |
122 | } |
123 | |
124 | range_query::range_query () |
125 | { |
126 | m_oracle = NULL; |
127 | } |
128 | |
129 | range_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 | |
136 | bool |
137 | range_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 | |
247 | static inline void |
248 | get_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 | |
264 | static inline bool |
265 | get_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 | |
286 | static void |
287 | get_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 | |
352 | void |
353 | gimple_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 | |
370 | global_range_query global_ranges; |
371 | |
372 | bool |
373 | global_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 | |
387 | relation_kind |
388 | range_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 | |
408 | relation_kind |
409 | range_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 | |