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 : #include "fold-const.h"
40 :
41 : // Create the global oracle.
42 :
43 : infer_range_oracle infer_oracle;
44 :
45 : // This class is merely an accessor which is granted internals to
46 : // gimple_infer_range such that non_null_loadstore as a static callback can
47 : // call the protected add_nonzero ().
48 : // Static functions ccannot be friends, so we do it through a class wrapper.
49 :
50 : class non_null_wrapper
51 : {
52 : public:
53 29039521 : inline non_null_wrapper (gimple_infer_range *infer) : m_infer (infer) { }
54 29039521 : inline void add_nonzero (tree name) { m_infer->add_nonzero (name); }
55 : inline void add_range (tree t, vrange &r) { m_infer->add_range (t, r); }
56 : private:
57 : gimple_infer_range *m_infer;
58 : };
59 :
60 : // Adapted from infer_nonnull_range_by_dereference and check_loadstore
61 : // to process nonnull ssa_name OP in S. DATA contains a pointer to a
62 : // stmt range inference instance.
63 :
64 : static bool
65 53211277 : non_null_loadstore (gimple *stmt, tree op, tree, void *data)
66 : {
67 106422554 : if (TREE_CODE (op) == MEM_REF
68 53211277 : || (TREE_CODE (op) == TARGET_MEM_REF
69 1705443 : && !TMR_INDEX2 (op)
70 1672013 : && (!TMR_INDEX (op)
71 858580 : || (TMR_STEP (op)
72 804290 : && expr_not_equal_to (TMR_STEP (op),
73 54015567 : wi::one (TYPE_PRECISION (TREE_TYPE
74 : (TMR_STEP (op)))),
75 : stmt)))))
76 : {
77 : /* Some address spaces may legitimately dereference zero. */
78 29040021 : addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (op));
79 29040021 : if (!targetm.addr_space.zero_address_valid (as))
80 : {
81 29039521 : non_null_wrapper wrapper ((gimple_infer_range *)data);
82 29039521 : wrapper.add_nonzero (TREE_OPERAND (op, 0));
83 : }
84 : }
85 53211277 : return false;
86 : }
87 :
88 : // Process an ASSUME call to see if there are any inferred ranges available.
89 :
90 : void
91 423 : gimple_infer_range::check_assume_func (gcall *call)
92 : {
93 423 : tree arg;
94 423 : unsigned i;
95 423 : tree assume_id = TREE_OPERAND (gimple_call_arg (call, 0), 0);
96 423 : if (!assume_id)
97 : return;
98 423 : struct function *fun = DECL_STRUCT_FUNCTION (assume_id);
99 423 : if (!fun)
100 : return;
101 : // Loop over arguments, matching them to the assume parameters.
102 423 : for (arg = DECL_ARGUMENTS (assume_id), i = 1;
103 960 : arg && i < gimple_call_num_args (call);
104 537 : i++, arg = DECL_CHAIN (arg))
105 : {
106 537 : tree op = gimple_call_arg (call, i);
107 537 : tree type = TREE_TYPE (op);
108 537 : if (gimple_range_ssa_p (op) && value_range::supports_type_p (type))
109 : {
110 402 : tree default_def = ssa_default_def (fun, arg);
111 402 : if (!default_def || type != TREE_TYPE (default_def))
112 3 : continue;
113 : // Query the global range of the default def in the assume function.
114 399 : value_range assume_range (type);
115 399 : gimple_range_global (assume_range, default_def, fun);
116 : // If there is a non-varying result, add it as an inferred range.
117 399 : if (!assume_range.varying_p ())
118 : {
119 218 : add_range (op, assume_range);
120 218 : if (dump_file)
121 : {
122 48 : print_generic_expr (dump_file, assume_id, TDF_SLIM);
123 48 : fprintf (dump_file, " assume inferred range of ");
124 48 : print_generic_expr (dump_file, op, TDF_SLIM);
125 48 : fprintf (dump_file, " (param ");
126 48 : print_generic_expr (dump_file, arg, TDF_SLIM);
127 48 : fprintf (dump_file, ") = ");
128 48 : assume_range.dump (dump_file);
129 48 : fputc ('\n', dump_file);
130 : }
131 : }
132 399 : }
133 : }
134 : }
135 :
136 : // Add NAME and RANGE to the range inference summary.
137 :
138 : void
139 24007302 : gimple_infer_range::add_range (tree name, vrange &range)
140 : {
141 : // Do not add an inferred range if it is VARYING.
142 24007302 : if (range.varying_p ())
143 : return;
144 24006230 : m_names[num_args] = name;
145 24006230 : m_ranges[num_args] = range;
146 24006230 : if (num_args < size_limit - 1)
147 24006230 : num_args++;
148 : }
149 :
150 : // Add a nonzero range for NAME to the range inference summary.
151 :
152 : void
153 34782363 : gimple_infer_range::add_nonzero (tree name)
154 : {
155 34782363 : if (!gimple_range_ssa_p (name))
156 : return;
157 23981377 : prange nz;
158 23981377 : nz.set_nonzero (TREE_TYPE (name));
159 23981377 : add_range (name, nz);
160 23981377 : }
161 :
162 : // Process S for range inference and fill in the summary list.
163 : // This is the routine where any new inferred ranges should be added.
164 : // If USE_RANGEOPS is true, invoke range-ops on stmts with a single
165 : // ssa-name a constant to reflect an inferred range. ie
166 : // x_2 = y_3 + 1 will provide an inferred range for y_3 of [-INF, +INF - 1].
167 : // This defaults to FALSE as it can be expensive.,
168 :
169 379026322 : gimple_infer_range::gimple_infer_range (gimple *s, range_query *q,
170 4169289542 : bool use_rangeops)
171 : {
172 379026322 : num_args = 0;
173 :
174 379026322 : if (is_a<gphi *> (s))
175 379026322 : return;
176 :
177 : // Default to the global query if none provided.
178 341700022 : if (!q)
179 0 : q = get_global_range_query ();
180 :
181 341700022 : if (is_a<gcall *> (s) && flag_delete_null_pointer_checks)
182 : {
183 20904631 : tree fntype = gimple_call_fntype (s);
184 20904631 : bitmap nonnullargs = get_nonnull_args (fntype);
185 : // Process any non-null arguments
186 20904631 : if (nonnullargs)
187 : {
188 13703014 : for (unsigned i = 0; i < gimple_call_num_args (s); i++)
189 : {
190 9711408 : if (bitmap_empty_p (nonnullargs)
191 9711408 : || bitmap_bit_p (nonnullargs, i))
192 : {
193 4932703 : tree op = gimple_call_arg (s, i);
194 4932703 : if (POINTER_TYPE_P (TREE_TYPE (op)))
195 4899236 : add_nonzero (op);
196 : }
197 : }
198 3991606 : BITMAP_FREE (nonnullargs);
199 : }
200 20904631 : if (fntype)
201 20241973 : for (tree attrs = TYPE_ATTRIBUTES (fntype);
202 22126368 : (attrs = lookup_attribute ("nonnull_if_nonzero", attrs));
203 1884395 : attrs = TREE_CHAIN (attrs))
204 : {
205 1884395 : tree args = TREE_VALUE (attrs);
206 1884395 : unsigned int idx = TREE_INT_CST_LOW (TREE_VALUE (args)) - 1;
207 1884395 : unsigned int idx2
208 1884395 : = TREE_INT_CST_LOW (TREE_VALUE (TREE_CHAIN (args))) - 1;
209 1884395 : unsigned int idx3 = idx2;
210 1884395 : if (tree chain2 = TREE_CHAIN (TREE_CHAIN (args)))
211 13776 : idx3 = TREE_INT_CST_LOW (TREE_VALUE (chain2)) - 1;
212 1884395 : if (idx < gimple_call_num_args (s)
213 1884359 : && idx2 < gimple_call_num_args (s)
214 3768721 : && idx3 < gimple_call_num_args (s))
215 : {
216 1884326 : tree arg = gimple_call_arg (s, idx);
217 1884326 : tree arg2 = gimple_call_arg (s, idx2);
218 1884326 : tree arg3 = gimple_call_arg (s, idx3);
219 1886219 : if (!POINTER_TYPE_P (TREE_TYPE (arg))
220 1884065 : || !INTEGRAL_TYPE_P (TREE_TYPE (arg2))
221 1884050 : || !INTEGRAL_TYPE_P (TREE_TYPE (arg3))
222 1884050 : || integer_zerop (arg2)
223 3767429 : || integer_zerop (arg3))
224 1407 : continue;
225 1882919 : if (integer_nonzerop (arg2) && integer_nonzerop (arg3))
226 346351 : add_nonzero (arg);
227 : else
228 : {
229 1536568 : value_range r (TREE_TYPE (arg2));
230 1536568 : if (q->range_of_expr (r, arg2, s)
231 1536568 : && !r.contains_p (build_zero_cst (TREE_TYPE (arg2))))
232 : {
233 497812 : if (idx2 == idx3)
234 497028 : add_nonzero (arg);
235 : else
236 : {
237 784 : value_range r2 (TREE_TYPE (arg3));
238 784 : tree zero3 = build_zero_cst (TREE_TYPE (arg3));
239 784 : if (q->range_of_expr (r2, arg3, s)
240 1568 : && !r2.contains_p (zero3))
241 227 : add_nonzero (arg);
242 784 : }
243 : }
244 1536568 : }
245 : }
246 : }
247 : // Fallthru and walk load/store ops now.
248 : }
249 :
250 : // Check for inferred ranges from ASSUME calls.
251 341700022 : if (is_a<gcall *> (s) && gimple_call_internal_p (s)
252 342375720 : && gimple_call_internal_fn (s) == IFN_ASSUME)
253 423 : check_assume_func (as_a<gcall *> (s));
254 :
255 : // Look for possible non-null values.
256 341568031 : if (flag_delete_null_pointer_checks && gimple_code (s) != GIMPLE_ASM
257 683086441 : && !gimple_clobber_p (s))
258 335785009 : walk_stmt_load_store_ops (s, (void *)this, non_null_loadstore,
259 : non_null_loadstore);
260 :
261 : // Gated by flag.
262 341700022 : if (!use_rangeops)
263 : return;
264 :
265 : // Check if there are any inferred ranges from range-ops.
266 0 : gimple_range_op_handler handler (s);
267 0 : if (!handler)
268 : return;
269 :
270 : // Only proceed if ONE operand is an SSA_NAME, This may provide an
271 : // inferred range for 'y + 3' , but will bypass expressions like
272 : // 'y + z' as it depends on symbolic values.
273 0 : tree ssa1 = gimple_range_ssa_p (handler.operand1 ());
274 0 : tree ssa2 = gimple_range_ssa_p (handler.operand2 ());
275 0 : if ((ssa1 != NULL) == (ssa2 != NULL))
276 : return;
277 :
278 : // The other operand should be a constant, so just use the global range
279 : // query to pick up any other values.
280 0 : if (ssa1)
281 : {
282 0 : value_range op1 (TREE_TYPE (ssa1));
283 0 : if (op1_range (op1, s, q) && !op1.varying_p ())
284 0 : add_range (ssa1, op1);
285 0 : }
286 : else
287 : {
288 0 : gcc_checking_assert (ssa2);
289 0 : value_range op2 (TREE_TYPE (ssa2));
290 0 : if (op2_range (op2, s, q) && !op2.varying_p ())
291 0 : add_range (ssa2, op2);
292 0 : }
293 : }
294 :
295 : // Create an single inferred range for NAMe using range R.
296 :
297 282777 : gimple_infer_range::gimple_infer_range (tree name, vrange &r)
298 : {
299 25707 : num_args = 0;
300 25707 : add_range (name, r);
301 25707 : }
302 :
303 : // -------------------------------------------------------------------------
304 :
305 : // This class is an element in the list of inferred ranges.
306 :
307 : class exit_range
308 : {
309 : public:
310 : tree name;
311 : gimple *stmt;
312 : vrange_storage *range;
313 : exit_range *next;
314 : exit_range *name_link;
315 : };
316 :
317 :
318 : // If there is an element which matches SSA, return a pointer to the element.
319 : // Otherwise return NULL.
320 :
321 : exit_range *
322 16881807 : infer_range_manager::exit_range_head::find_ptr (tree ssa)
323 : {
324 : // Return NULL if SSA is not in this list.
325 33763614 : if (!m_names || !bitmap_bit_p (m_names, SSA_NAME_VERSION (ssa)))
326 : return NULL;
327 8376411 : for (exit_range *ptr = head; ptr != NULL; ptr = ptr->next)
328 8376411 : if (ptr->name == ssa)
329 : return ptr;
330 : // Should be unreachable.
331 0 : gcc_unreachable ();
332 : return NULL;
333 : }
334 :
335 : // Construct a range infer manager. DO_SEARCH indicates whether an immediate
336 : // use scan should be made the first time a name is processed. This is for
337 : // on-demand clients who may not visit every statement and may miss uses.
338 : // Q is the range_query to use for any lookups. Default is NULL which maps
339 : // to the global_range_query.
340 :
341 29420773 : infer_range_manager::infer_range_manager (bool do_search, range_query *q)
342 : {
343 : // Set the range query to use.
344 29420773 : m_query = q ? q : get_global_range_query ();
345 :
346 29420773 : bitmap_obstack_initialize (&m_bitmaps);
347 29420773 : m_on_exit.create (0);
348 29420773 : m_on_exit.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
349 : // m_seen == NULL indicates no scanning. Otherwise the bit indicates a
350 : // scan has been performed on NAME.
351 29420773 : if (do_search)
352 23516629 : m_seen = BITMAP_ALLOC (&m_bitmaps);
353 : else
354 5904144 : m_seen = NULL;
355 29420773 : obstack_init (&m_list_obstack);
356 : // Non-zero elements are very common, so cache them for each ssa-name.
357 29420773 : m_name_info.create (0);
358 58841546 : m_name_info.safe_grow_cleared (num_ssa_names + 1);
359 29420773 : m_range_allocator = new vrange_allocator;
360 29420773 : }
361 :
362 : // Destruct a range infer manager.
363 :
364 58841546 : infer_range_manager::~infer_range_manager ()
365 : {
366 29420773 : m_name_info.release ();
367 29420773 : obstack_free (&m_list_obstack, NULL);
368 29420773 : m_on_exit.release ();
369 29420773 : bitmap_obstack_release (&m_bitmaps);
370 29420773 : delete m_range_allocator;
371 58841546 : }
372 :
373 : // Return a non-zero range value of the appropriate type for NAME from
374 : // the cache, creating it if necessary.
375 :
376 : const vrange&
377 0 : infer_range_manager::get_nonzero (tree name)
378 : {
379 0 : unsigned v = SSA_NAME_VERSION (name);
380 0 : if (v >= m_name_info.length ())
381 0 : m_name_info.safe_grow_cleared (num_ssa_names + 20);
382 0 : if (!m_name_info[v].nonzero)
383 : {
384 0 : m_name_info[v].nonzero
385 0 : = (irange *) m_range_allocator->alloc (sizeof (int_range <2>));
386 0 : m_name_info[v].nonzero->set_nonzero (TREE_TYPE (name));
387 : }
388 0 : return *(m_name_info[v].nonzero);
389 : }
390 :
391 : // Return TRUE if NAME has a range inference in block BB. If NAME is NULL,
392 : // return TRUE if there are any name sin BB.
393 :
394 : bool
395 741356645 : infer_range_manager::has_range_p (basic_block bb, tree name)
396 : {
397 : // Check if this is an immediate use search model.
398 1194537221 : if (name && m_seen && !bitmap_bit_p (m_seen, SSA_NAME_VERSION (name)))
399 28682915 : register_all_uses (name);
400 :
401 1482713290 : if (bb->index >= (int)m_on_exit.length ())
402 : return false;
403 :
404 741018046 : bitmap b = m_on_exit[bb->index].m_names;
405 741018046 : if (!b)
406 : return false;
407 :
408 56994728 : if (name)
409 54433423 : return bitmap_bit_p (m_on_exit[bb->index].m_names, SSA_NAME_VERSION (name));
410 2561305 : return !bitmap_empty_p (b);
411 : }
412 :
413 : // Return TRUE if NAME has a range inference in block BB, and adjust range R
414 : // to include it.
415 :
416 : bool
417 685478729 : infer_range_manager::maybe_adjust_range (vrange &r, tree name, basic_block bb)
418 : {
419 685478729 : if (!has_range_p (bb, name))
420 : return false;
421 5938607 : exit_range *ptr = m_on_exit[bb->index].find_ptr (name);
422 5938607 : gcc_checking_assert (ptr);
423 : // Return true if this exit range changes R, otherwise false.
424 5938607 : tree type = TREE_TYPE (name);
425 5938607 : value_range tmp (type);
426 5938607 : ptr->range->get_vrange (tmp, type);
427 5938607 : return r.intersect (tmp);
428 5938607 : }
429 :
430 : // Add all inferred ranges in INFER at stmt S.
431 :
432 : void
433 16583566 : infer_range_manager::add_ranges (gimple *s, gimple_infer_range &infer)
434 : {
435 33467384 : for (unsigned x = 0; x < infer.num (); x++)
436 : {
437 16883818 : tree arg = infer.name (x);
438 16883818 : value_range r (TREE_TYPE (arg));
439 16883818 : m_query->range_of_expr (r, arg, s);
440 : // Only add the inferred range if it changes the current range.
441 16883818 : if (r.intersect (infer.range (x)))
442 5622937 : add_range (arg, s, infer.range (x));
443 16883818 : }
444 16583566 : }
445 :
446 : // Add range R as an inferred range for NAME on stmt S.
447 :
448 : void
449 10943200 : infer_range_manager::add_range (tree name, gimple *s, const vrange &r)
450 : {
451 10943200 : basic_block bb = gimple_bb (s);
452 10943200 : if (!bb)
453 : return;
454 21886400 : if (bb->index >= (int)m_on_exit.length ())
455 36 : m_on_exit.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
456 :
457 10943200 : if (SSA_NAME_VERSION (name) >= m_name_info.length ())
458 4 : m_name_info.safe_grow_cleared (num_ssa_names + 20);
459 :
460 : // Create the summary list bitmap if it doesn't exist.
461 10943200 : if (!m_on_exit[bb->index].m_names)
462 7569283 : m_on_exit[bb->index].m_names = BITMAP_ALLOC (&m_bitmaps);
463 :
464 10943200 : if (dump_file && (dump_flags & TDF_DETAILS))
465 : {
466 91 : fprintf (dump_file, " on-exit update ");
467 91 : print_generic_expr (dump_file, name, TDF_SLIM);
468 91 : fprintf (dump_file, " in BB%d : ",bb->index);
469 91 : r.dump (dump_file);
470 91 : fprintf (dump_file, "\n");
471 : }
472 :
473 21886400 : get_range_query (cfun)->update_range_info (name);
474 :
475 : // If NAME already has a range, intersect them and done.
476 10943200 : exit_range *ptr = m_on_exit[bb->index].find_ptr (name);
477 10943200 : if (ptr)
478 : {
479 1858806 : tree type = TREE_TYPE (name);
480 1858806 : value_range cur (r), name_range (type);
481 1858806 : ptr->range->get_vrange (name_range, type);
482 : // If no new info is added, just return.
483 1858806 : if (!cur.intersect (name_range))
484 : return;
485 21 : if (ptr->range->fits_p (cur))
486 21 : ptr->range->set_vrange (cur);
487 : else
488 0 : ptr->range = m_range_allocator->clone (cur);
489 21 : ptr->stmt = s;
490 21 : return;
491 1858806 : }
492 :
493 : // Otherwise create a record.
494 9084394 : bitmap_set_bit (m_on_exit[bb->index].m_names, SSA_NAME_VERSION (name));
495 9084394 : ptr = (exit_range *)obstack_alloc (&m_list_obstack, sizeof (exit_range));
496 9084394 : ptr->range = m_range_allocator->clone (r);
497 9084394 : ptr->name = name;
498 9084394 : ptr->stmt = s;
499 9084394 : ptr->next = m_on_exit[bb->index].head;
500 9084394 : ptr->name_link = m_name_info[SSA_NAME_VERSION (name)].name_link;
501 9084394 : m_name_info[SSA_NAME_VERSION (name)].name_link = ptr;
502 9084394 : m_on_exit[bb->index].head = ptr;
503 : }
504 :
505 : // Add a non-zero inferred range for NAME at stmt S.
506 :
507 : void
508 0 : infer_range_manager::add_nonzero (tree name, gimple *s)
509 : {
510 0 : add_range (name, s, get_nonzero (name));
511 0 : }
512 :
513 : // Follow immediate use chains and find all inferred ranges for NAME.
514 :
515 : void
516 28682915 : infer_range_manager::register_all_uses (tree name)
517 : {
518 28682915 : gcc_checking_assert (m_seen);
519 :
520 : // Check if we've already processed this name.
521 28682915 : unsigned v = SSA_NAME_VERSION (name);
522 28682915 : if (bitmap_bit_p (m_seen, v))
523 0 : return;
524 28682915 : bitmap_set_bit (m_seen, v);
525 :
526 28682915 : use_operand_p use_p;
527 28682915 : imm_use_iterator iter;
528 :
529 : // Loop over each immediate use and see if it has an inferred range.
530 133464653 : FOR_EACH_IMM_USE_FAST (use_p, iter, name)
531 : {
532 104781738 : gimple *s = USE_STMT (use_p);
533 104781738 : gimple_infer_range infer (s, m_query);
534 216685888 : for (unsigned x = 0; x < infer.num (); x++)
535 : {
536 7122412 : if (name == infer.name (x))
537 5320263 : add_range (name, s, infer.range (x));
538 : }
539 28682915 : }
540 : }
541 :
542 : // Clear all inferred ranges for NAME.
543 :
544 : void
545 1157 : infer_range_manager::clear(tree name)
546 : {
547 : // Check if this name has any inferred ranges.
548 1157 : unsigned v = SSA_NAME_VERSION (name);
549 1157 : if (v >= m_name_info.length ())
550 : return;
551 :
552 1157 : exit_range *ptr = m_name_info[v].name_link;
553 1157 : for ( ; ptr ; ptr = ptr->name_link)
554 : {
555 0 : basic_block bb = gimple_bb (ptr->stmt);
556 0 : unsigned bbi = bb->index;
557 0 : bitmap_clear_bit (m_on_exit[bbi].m_names, v);
558 0 : ptr->name = NULL;
559 : }
560 :
561 1157 : m_name_info[v].name_link = NULL;
562 1157 : if (m_seen)
563 0 : bitmap_clear_bit (m_seen, v);
564 : }
|
