Line data Source code
1 : /* Gimple range inference implementation.
2 : Copyright (C) 2022-2026 Free Software Foundation, Inc.
3 : Contributed by Andrew MacLeod <amacleod@redhat.com>.
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify
8 : it under the terms of the GNU General Public License as published by
9 : the Free Software Foundation; either version 3, or (at your option)
10 : any later version.
11 :
12 : GCC is distributed in the hope that it will be useful,
13 : but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : GNU General Public License for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : #include "config.h"
22 : #include "system.h"
23 : #include "coretypes.h"
24 : #include "backend.h"
25 : #include "insn-codes.h"
26 : #include "tree.h"
27 : #include "gimple.h"
28 : #include "ssa.h"
29 : #include "gimple-pretty-print.h"
30 : #include "gimple-range.h"
31 : #include "value-range-storage.h"
32 : #include "tree-cfg.h"
33 : #include "target.h"
34 : #include "attribs.h"
35 : #include "gimple-iterator.h"
36 : #include "gimple-walk.h"
37 : #include "cfganal.h"
38 : #include "tree-dfa.h"
39 :
40 : // Create the global oracle.
41 :
42 : infer_range_oracle infer_oracle;
43 :
44 : // This class is merely an accessor which is granted internals to
45 : // gimple_infer_range such that non_null_loadstore as a static callback can
46 : // call the protected add_nonzero ().
47 : // Static functions ccannot be friends, so we do it through a class wrapper.
48 :
49 : class non_null_wrapper
50 : {
51 : public:
52 29383462 : inline non_null_wrapper (gimple_infer_range *infer) : m_infer (infer) { }
53 29383462 : inline void add_nonzero (tree name) { m_infer->add_nonzero (name); }
54 : inline void add_range (tree t, vrange &r) { m_infer->add_range (t, r); }
55 : private:
56 : gimple_infer_range *m_infer;
57 : };
58 :
59 : // Adapted from infer_nonnull_range_by_dereference and check_loadstore
60 : // to process nonnull ssa_name OP in S. DATA contains a pointer to a
61 : // stmt range inference instance.
62 :
63 : static bool
64 52922406 : non_null_loadstore (gimple *, tree op, tree, void *data)
65 : {
66 52922406 : if (TREE_CODE (op) == MEM_REF || TREE_CODE (op) == TARGET_MEM_REF)
67 : {
68 : /* Some address spaces may legitimately dereference zero. */
69 29383973 : addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (op));
70 29383973 : if (!targetm.addr_space.zero_address_valid (as))
71 : {
72 29383462 : non_null_wrapper wrapper ((gimple_infer_range *)data);
73 29383462 : wrapper.add_nonzero (TREE_OPERAND (op, 0));
74 : }
75 : }
76 52922406 : return false;
77 : }
78 :
79 : // Process an ASSUME call to see if there are any inferred ranges available.
80 :
81 : void
82 423 : gimple_infer_range::check_assume_func (gcall *call)
83 : {
84 423 : tree arg;
85 423 : unsigned i;
86 423 : tree assume_id = TREE_OPERAND (gimple_call_arg (call, 0), 0);
87 423 : if (!assume_id)
88 : return;
89 423 : struct function *fun = DECL_STRUCT_FUNCTION (assume_id);
90 423 : if (!fun)
91 : return;
92 : // Loop over arguments, matching them to the assume parameters.
93 423 : for (arg = DECL_ARGUMENTS (assume_id), i = 1;
94 960 : arg && i < gimple_call_num_args (call);
95 537 : i++, arg = DECL_CHAIN (arg))
96 : {
97 537 : tree op = gimple_call_arg (call, i);
98 537 : tree type = TREE_TYPE (op);
99 537 : if (gimple_range_ssa_p (op) && value_range::supports_type_p (type))
100 : {
101 402 : tree default_def = ssa_default_def (fun, arg);
102 402 : if (!default_def || type != TREE_TYPE (default_def))
103 3 : continue;
104 : // Query the global range of the default def in the assume function.
105 399 : value_range assume_range (type);
106 399 : gimple_range_global (assume_range, default_def, fun);
107 : // If there is a non-varying result, add it as an inferred range.
108 399 : if (!assume_range.varying_p ())
109 : {
110 218 : add_range (op, assume_range);
111 218 : if (dump_file)
112 : {
113 48 : print_generic_expr (dump_file, assume_id, TDF_SLIM);
114 48 : fprintf (dump_file, " assume inferred range of ");
115 48 : print_generic_expr (dump_file, op, TDF_SLIM);
116 48 : fprintf (dump_file, " (param ");
117 48 : print_generic_expr (dump_file, arg, TDF_SLIM);
118 48 : fprintf (dump_file, ") = ");
119 48 : assume_range.dump (dump_file);
120 48 : fputc ('\n', dump_file);
121 : }
122 : }
123 399 : }
124 : }
125 : }
126 :
127 : // Add NAME and RANGE to the range inference summary.
128 :
129 : void
130 24371900 : gimple_infer_range::add_range (tree name, vrange &range)
131 : {
132 : // Do not add an inferred range if it is VARYING.
133 24371900 : if (range.varying_p ())
134 : return;
135 24370825 : m_names[num_args] = name;
136 24370825 : m_ranges[num_args] = range;
137 24370825 : if (num_args < size_limit - 1)
138 24370825 : num_args++;
139 : }
140 :
141 : // Add a nonzero range for NAME to the range inference summary.
142 :
143 : void
144 35352935 : gimple_infer_range::add_nonzero (tree name)
145 : {
146 35352935 : if (!gimple_range_ssa_p (name))
147 11007546 : return;
148 24345389 : prange nz;
149 24345389 : nz.set_nonzero (TREE_TYPE (name));
150 24345389 : add_range (name, nz);
151 24345389 : }
152 :
153 : // Process S for range inference and fill in the summary list.
154 : // This is the routine where any new inferred ranges should be added.
155 : // If USE_RANGEOPS is true, invoke range-ops on stmts with a single
156 : // ssa-name a constant to reflect an inferred range. ie
157 : // x_2 = y_3 + 1 will provide an inferred range for y_3 of [-INF, +INF - 1].
158 : // This defaults to FALSE as it can be expensive.,
159 :
160 366463980 : gimple_infer_range::gimple_infer_range (gimple *s, range_query *q,
161 4031103780 : bool use_rangeops)
162 : {
163 366463980 : num_args = 0;
164 :
165 366463980 : if (is_a<gphi *> (s))
166 366463980 : return;
167 :
168 : // Default to the global query if none provided.
169 330968358 : if (!q)
170 0 : q = get_global_range_query ();
171 :
172 330968358 : if (is_a<gcall *> (s) && flag_delete_null_pointer_checks)
173 : {
174 20752013 : tree fntype = gimple_call_fntype (s);
175 20752013 : bitmap nonnullargs = get_nonnull_args (fntype);
176 : // Process any non-null arguments
177 20752013 : if (nonnullargs)
178 : {
179 13936483 : for (unsigned i = 0; i < gimple_call_num_args (s); i++)
180 : {
181 9874685 : if (bitmap_empty_p (nonnullargs)
182 9874685 : || bitmap_bit_p (nonnullargs, i))
183 : {
184 5216384 : tree op = gimple_call_arg (s, i);
185 5216384 : if (POINTER_TYPE_P (TREE_TYPE (op)))
186 5182792 : add_nonzero (op);
187 : }
188 : }
189 4061798 : BITMAP_FREE (nonnullargs);
190 : }
191 20752013 : if (fntype)
192 20094382 : for (tree attrs = TYPE_ATTRIBUTES (fntype);
193 21864265 : (attrs = lookup_attribute ("nonnull_if_nonzero", attrs));
194 1769883 : attrs = TREE_CHAIN (attrs))
195 : {
196 1769883 : tree args = TREE_VALUE (attrs);
197 1769883 : unsigned int idx = TREE_INT_CST_LOW (TREE_VALUE (args)) - 1;
198 1769883 : unsigned int idx2
199 1769883 : = TREE_INT_CST_LOW (TREE_VALUE (TREE_CHAIN (args))) - 1;
200 1769883 : unsigned int idx3 = idx2;
201 1769883 : if (tree chain2 = TREE_CHAIN (TREE_CHAIN (args)))
202 13596 : idx3 = TREE_INT_CST_LOW (TREE_VALUE (chain2)) - 1;
203 1769883 : if (idx < gimple_call_num_args (s)
204 1769847 : && idx2 < gimple_call_num_args (s)
205 3539697 : && idx3 < gimple_call_num_args (s))
206 : {
207 1769814 : tree arg = gimple_call_arg (s, idx);
208 1769814 : tree arg2 = gimple_call_arg (s, idx2);
209 1769814 : tree arg3 = gimple_call_arg (s, idx3);
210 1771822 : if (!POINTER_TYPE_P (TREE_TYPE (arg))
211 1769553 : || !INTEGRAL_TYPE_P (TREE_TYPE (arg2))
212 1769538 : || !INTEGRAL_TYPE_P (TREE_TYPE (arg3))
213 1769538 : || integer_zerop (arg2)
214 3538363 : || integer_zerop (arg3))
215 1449 : continue;
216 1768365 : if (integer_nonzerop (arg2) && integer_nonzerop (arg3))
217 317311 : add_nonzero (arg);
218 : else
219 : {
220 1451054 : value_range r (TREE_TYPE (arg2));
221 1451054 : if (q->range_of_expr (r, arg2, s)
222 1451054 : && !r.contains_p (build_zero_cst (TREE_TYPE (arg2))))
223 : {
224 469931 : if (idx2 == idx3)
225 469143 : add_nonzero (arg);
226 : else
227 : {
228 788 : value_range r2 (TREE_TYPE (arg3));
229 788 : tree zero3 = build_zero_cst (TREE_TYPE (arg3));
230 788 : if (q->range_of_expr (r2, arg3, s)
231 1576 : && !r2.contains_p (zero3))
232 227 : add_nonzero (arg);
233 788 : }
234 : }
235 1451054 : }
236 : }
237 : }
238 : // Fallthru and walk load/store ops now.
239 : }
240 :
241 : // Check for inferred ranges from ASSUME calls.
242 330968358 : if (is_a<gcall *> (s) && gimple_call_internal_p (s)
243 331639126 : && gimple_call_internal_fn (s) == IFN_ASSUME)
244 423 : check_assume_func (as_a<gcall *> (s));
245 :
246 : // Look for possible non-null values.
247 330835826 : if (flag_delete_null_pointer_checks && gimple_code (s) != GIMPLE_ASM
248 661599950 : && !gimple_clobber_p (s))
249 325145476 : walk_stmt_load_store_ops (s, (void *)this, non_null_loadstore,
250 : non_null_loadstore);
251 :
252 : // Gated by flag.
253 330968358 : if (!use_rangeops)
254 : return;
255 :
256 : // Check if there are any inferred ranges from range-ops.
257 0 : gimple_range_op_handler handler (s);
258 0 : if (!handler)
259 : return;
260 :
261 : // Only proceed if ONE operand is an SSA_NAME, This may provide an
262 : // inferred range for 'y + 3' , but will bypass expressions like
263 : // 'y + z' as it depends on symbolic values.
264 0 : tree ssa1 = gimple_range_ssa_p (handler.operand1 ());
265 0 : tree ssa2 = gimple_range_ssa_p (handler.operand2 ());
266 0 : if ((ssa1 != NULL) == (ssa2 != NULL))
267 : return;
268 :
269 : // The other operand should be a constant, so just use the global range
270 : // query to pick up any other values.
271 0 : if (ssa1)
272 : {
273 0 : value_range op1 (TREE_TYPE (ssa1));
274 0 : if (op1_range (op1, s, q) && !op1.varying_p ())
275 0 : add_range (ssa1, op1);
276 0 : }
277 : else
278 : {
279 0 : gcc_checking_assert (ssa2);
280 0 : value_range op2 (TREE_TYPE (ssa2));
281 0 : if (op2_range (op2, s, q) && !op2.varying_p ())
282 0 : add_range (ssa2, op2);
283 0 : }
284 : }
285 :
286 : // Create an single inferred range for NAMe using range R.
287 :
288 289223 : gimple_infer_range::gimple_infer_range (tree name, vrange &r)
289 : {
290 26293 : num_args = 0;
291 26293 : add_range (name, r);
292 26293 : }
293 :
294 : // -------------------------------------------------------------------------
295 :
296 : // This class is an element in the list of inferred ranges.
297 :
298 : class exit_range
299 : {
300 : public:
301 : tree name;
302 : gimple *stmt;
303 : vrange_storage *range;
304 : exit_range *next;
305 : };
306 :
307 :
308 : // If there is an element which matches SSA, return a pointer to the element.
309 : // Otherwise return NULL.
310 :
311 : exit_range *
312 16915873 : infer_range_manager::exit_range_head::find_ptr (tree ssa)
313 : {
314 : // Return NULL if SSA is not in this list.
315 33831746 : if (!m_names || !bitmap_bit_p (m_names, SSA_NAME_VERSION (ssa)))
316 9457283 : return NULL;
317 8034341 : for (exit_range *ptr = head; ptr != NULL; ptr = ptr->next)
318 8034341 : if (ptr->name == ssa)
319 : return ptr;
320 : // Should be unreachable.
321 0 : gcc_unreachable ();
322 : return NULL;
323 : }
324 :
325 : // Construct a range infer manager. DO_SEARCH indicates whether an immediate
326 : // use scan should be made the first time a name is processed. This is for
327 : // on-demand clients who may not visit every statement and may miss uses.
328 : // Q is the range_query to use for any lookups. Default is NULL which maps
329 : // to the global_range_query.
330 :
331 29017078 : infer_range_manager::infer_range_manager (bool do_search, range_query *q)
332 : {
333 : // Set the range query to use.
334 29017078 : m_query = q ? q : get_global_range_query ();
335 :
336 29017078 : bitmap_obstack_initialize (&m_bitmaps);
337 29017078 : m_on_exit.create (0);
338 29017078 : m_on_exit.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
339 : // m_seen == NULL indicates no scanning. Otherwise the bit indicates a
340 : // scan has been performed on NAME.
341 29017078 : if (do_search)
342 23198755 : m_seen = BITMAP_ALLOC (&m_bitmaps);
343 : else
344 5818323 : m_seen = NULL;
345 29017078 : obstack_init (&m_list_obstack);
346 : // Non-zero elements are very common, so cache them for each ssa-name.
347 29017078 : m_nonzero.create (0);
348 58034156 : m_nonzero.safe_grow_cleared (num_ssa_names + 1);
349 29017078 : m_range_allocator = new vrange_allocator;
350 29017078 : }
351 :
352 : // Destruct a range infer manager.
353 :
354 58034156 : infer_range_manager::~infer_range_manager ()
355 : {
356 29017078 : m_nonzero.release ();
357 29017078 : obstack_free (&m_list_obstack, NULL);
358 29017078 : m_on_exit.release ();
359 29017078 : bitmap_obstack_release (&m_bitmaps);
360 29017078 : delete m_range_allocator;
361 58034156 : }
362 :
363 : // Return a non-zero range value of the appropriate type for NAME from
364 : // the cache, creating it if necessary.
365 :
366 : const vrange&
367 0 : infer_range_manager::get_nonzero (tree name)
368 : {
369 0 : unsigned v = SSA_NAME_VERSION (name);
370 0 : if (v >= m_nonzero.length ())
371 0 : m_nonzero.safe_grow_cleared (num_ssa_names + 20);
372 0 : if (!m_nonzero[v])
373 : {
374 0 : m_nonzero[v]
375 0 : = (irange *) m_range_allocator->alloc (sizeof (int_range <2>));
376 0 : m_nonzero[v]->set_nonzero (TREE_TYPE (name));
377 : }
378 0 : return *(m_nonzero[v]);
379 : }
380 :
381 : // Return TRUE if NAME has a range inference in block BB. If NAME is NULL,
382 : // return TRUE if there are any name sin BB.
383 :
384 : bool
385 694503352 : infer_range_manager::has_range_p (basic_block bb, tree name)
386 : {
387 : // Check if this is an immediate use search model.
388 1103758004 : if (name && m_seen && !bitmap_bit_p (m_seen, SSA_NAME_VERSION (name)))
389 27936878 : register_all_uses (name);
390 :
391 1389006704 : if (bb->index >= (int)m_on_exit.length ())
392 : return false;
393 :
394 694170656 : bitmap b = m_on_exit[bb->index].m_names;
395 694170656 : if (!b)
396 : return false;
397 :
398 55280308 : if (name)
399 52725820 : return bitmap_bit_p (m_on_exit[bb->index].m_names, SSA_NAME_VERSION (name));
400 2554488 : return !bitmap_empty_p (b);
401 : }
402 :
403 : // Return TRUE if NAME has a range inference in block BB, and adjust range R
404 : // to include it.
405 :
406 : bool
407 639312217 : infer_range_manager::maybe_adjust_range (vrange &r, tree name, basic_block bb)
408 : {
409 639312217 : if (!has_range_p (bb, name))
410 : return false;
411 5507572 : exit_range *ptr = m_on_exit[bb->index].find_ptr (name);
412 5507572 : gcc_checking_assert (ptr);
413 : // Return true if this exit range changes R, otherwise false.
414 5507572 : tree type = TREE_TYPE (name);
415 5507572 : value_range tmp (type);
416 5507572 : ptr->range->get_vrange (tmp, type);
417 5507572 : return r.intersect (tmp);
418 5507572 : }
419 :
420 : // Add all inferred ranges in INFER at stmt S.
421 :
422 : void
423 16421490 : infer_range_manager::add_ranges (gimple *s, gimple_infer_range &infer)
424 : {
425 33135008 : for (unsigned x = 0; x < infer.num (); x++)
426 : {
427 16713518 : tree arg = infer.name (x);
428 16713518 : value_range r (TREE_TYPE (arg));
429 16713518 : m_query->range_of_expr (r, arg, s);
430 : // Only add the inferred range if it changes the current range.
431 16713518 : if (r.intersect (infer.range (x)))
432 5619667 : add_range (arg, s, infer.range (x));
433 16713518 : }
434 16421490 : }
435 :
436 : // Add range R as an inferred range for NAME on stmt S.
437 :
438 : void
439 11408301 : infer_range_manager::add_range (tree name, gimple *s, const vrange &r)
440 : {
441 11408301 : basic_block bb = gimple_bb (s);
442 11408301 : if (!bb)
443 : return;
444 22816602 : if (bb->index >= (int)m_on_exit.length ())
445 36 : m_on_exit.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
446 :
447 : // Create the summary list bitmap if it doesn't exist.
448 11408301 : if (!m_on_exit[bb->index].m_names)
449 7913184 : m_on_exit[bb->index].m_names = BITMAP_ALLOC (&m_bitmaps);
450 :
451 11408301 : if (dump_file && (dump_flags & TDF_DETAILS))
452 : {
453 97 : fprintf (dump_file, " on-exit update ");
454 97 : print_generic_expr (dump_file, name, TDF_SLIM);
455 97 : fprintf (dump_file, " in BB%d : ",bb->index);
456 97 : r.dump (dump_file);
457 97 : fprintf (dump_file, "\n");
458 : }
459 :
460 22816602 : get_range_query (cfun)->update_range_info (name);
461 :
462 : // If NAME already has a range, intersect them and done.
463 11408301 : exit_range *ptr = m_on_exit[bb->index].find_ptr (name);
464 11408301 : if (ptr)
465 : {
466 1951018 : tree type = TREE_TYPE (name);
467 1951018 : value_range cur (r), name_range (type);
468 1951018 : ptr->range->get_vrange (name_range, type);
469 : // If no new info is added, just return.
470 1951018 : if (!cur.intersect (name_range))
471 : return;
472 21 : if (ptr->range->fits_p (cur))
473 21 : ptr->range->set_vrange (cur);
474 : else
475 0 : ptr->range = m_range_allocator->clone (cur);
476 21 : ptr->stmt = s;
477 21 : return;
478 1951018 : }
479 :
480 : // Otherwise create a record.
481 9457283 : bitmap_set_bit (m_on_exit[bb->index].m_names, SSA_NAME_VERSION (name));
482 9457283 : ptr = (exit_range *)obstack_alloc (&m_list_obstack, sizeof (exit_range));
483 9457283 : ptr->range = m_range_allocator->clone (r);
484 9457283 : ptr->name = name;
485 9457283 : ptr->stmt = s;
486 9457283 : ptr->next = m_on_exit[bb->index].head;
487 9457283 : m_on_exit[bb->index].head = ptr;
488 : }
489 :
490 : // Add a non-zero inferred range for NAME at stmt S.
491 :
492 : void
493 0 : infer_range_manager::add_nonzero (tree name, gimple *s)
494 : {
495 0 : add_range (name, s, get_nonzero (name));
496 0 : }
497 :
498 : // Follow immediate use chains and find all inferred ranges for NAME.
499 :
500 : void
501 27936878 : infer_range_manager::register_all_uses (tree name)
502 : {
503 27936878 : gcc_checking_assert (m_seen);
504 :
505 : // Check if we've already processed this name.
506 27936878 : unsigned v = SSA_NAME_VERSION (name);
507 27936878 : if (bitmap_bit_p (m_seen, v))
508 0 : return;
509 27936878 : bitmap_set_bit (m_seen, v);
510 :
511 27936878 : use_operand_p use_p;
512 27936878 : imm_use_iterator iter;
513 :
514 : // Loop over each immediate use and see if it has an inferred range.
515 157293461 : FOR_EACH_IMM_USE_FAST (use_p, iter, name)
516 : {
517 101419705 : gimple *s = USE_STMT (use_p);
518 101419705 : gimple_infer_range infer (s, m_query);
519 109077012 : for (unsigned x = 0; x < infer.num (); x++)
520 : {
521 7657307 : if (name == infer.name (x))
522 5788634 : add_range (name, s, infer.range (x));
523 : }
524 27936878 : }
525 : }
|
