1 /* Gimple range inference implementation.
2 Copyright (C) 2022-2024 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>.
5 This file is part of GCC.
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)
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.
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/>. */
23 #include "coretypes.h"
25 #include "insn-codes.h"
29 #include "gimple-pretty-print.h"
30 #include "gimple-range.h"
31 #include "value-range-storage.h"
35 #include "gimple-iterator.h"
36 #include "gimple-walk.h"
40 // Create the global oracle.
42 infer_range_oracle infer_oracle
;
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.
49 class non_null_wrapper
52 inline non_null_wrapper (gimple_infer_range
*infer
) : m_infer (infer
) { }
53 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
); }
56 gimple_infer_range
*m_infer
;
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.
64 non_null_loadstore (gimple
*, tree op
, tree
, void *data
)
66 if (TREE_CODE (op
) == MEM_REF
|| TREE_CODE (op
) == TARGET_MEM_REF
)
68 /* Some address spaces may legitimately dereference zero. */
69 addr_space_t as
= TYPE_ADDR_SPACE (TREE_TYPE (op
));
70 if (!targetm
.addr_space
.zero_address_valid (as
))
72 non_null_wrapper
wrapper ((gimple_infer_range
*)data
);
73 wrapper
.add_nonzero (TREE_OPERAND (op
, 0));
79 // Process an ASSUME call to see if there are any inferred ranges available.
82 gimple_infer_range::check_assume_func (gcall
*call
)
86 tree assume_id
= TREE_OPERAND (gimple_call_arg (call
, 0), 0);
89 struct function
*fun
= DECL_STRUCT_FUNCTION (assume_id
);
92 // Loop over arguments, matching them to the assume parameters.
93 for (arg
= DECL_ARGUMENTS (assume_id
), i
= 1;
94 arg
&& i
< gimple_call_num_args (call
);
95 i
++, arg
= DECL_CHAIN (arg
))
97 tree op
= gimple_call_arg (call
, i
);
98 tree type
= TREE_TYPE (op
);
99 if (gimple_range_ssa_p (op
) && value_range::supports_type_p (type
))
101 tree default_def
= ssa_default_def (fun
, arg
);
102 if (!default_def
|| type
!= TREE_TYPE (default_def
))
104 // Query the global range of the default def in the assume function.
105 value_range
assume_range (type
);
106 gimple_range_global (assume_range
, default_def
, fun
);
107 // If there is a non-varying result, add it as an inferred range.
108 if (!assume_range
.varying_p ())
110 add_range (op
, assume_range
);
113 print_generic_expr (dump_file
, assume_id
, TDF_SLIM
);
114 fprintf (dump_file
, " assume inferred range of ");
115 print_generic_expr (dump_file
, op
, TDF_SLIM
);
116 fprintf (dump_file
, " (param ");
117 print_generic_expr (dump_file
, arg
, TDF_SLIM
);
118 fprintf (dump_file
, ") = ");
119 assume_range
.dump (dump_file
);
120 fputc ('\n', dump_file
);
127 // Add NAME and RANGE to the range inference summary.
130 gimple_infer_range::add_range (tree name
, vrange
&range
)
132 // Do not add an inferred range if it is VARYING.
133 if (range
.varying_p ())
135 m_names
[num_args
] = name
;
136 m_ranges
[num_args
] = range
;
137 if (num_args
< size_limit
- 1)
141 // Add a nonzero range for NAME to the range inference summary.
144 gimple_infer_range::add_nonzero (tree name
)
146 if (!gimple_range_ssa_p (name
))
149 nz
.set_nonzero (TREE_TYPE (name
));
150 add_range (name
, nz
);
153 // Process S for range inference and fill in the summary list.
154 // This is the routine where new inferred ranges should be added.
155 // If USE_RANGEOPS is true, invoke range-ops on stmts with a single
156 // ssa-name aa 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.,
160 gimple_infer_range::gimple_infer_range (gimple
*s
, bool use_rangeops
)
164 if (is_a
<gphi
*> (s
))
167 if (is_a
<gcall
*> (s
) && flag_delete_null_pointer_checks
)
169 tree fntype
= gimple_call_fntype (s
);
170 bitmap nonnullargs
= get_nonnull_args (fntype
);
171 // Process any non-null arguments
174 for (unsigned i
= 0; i
< gimple_call_num_args (s
); i
++)
176 if (bitmap_empty_p (nonnullargs
)
177 || bitmap_bit_p (nonnullargs
, i
))
179 tree op
= gimple_call_arg (s
, i
);
180 if (POINTER_TYPE_P (TREE_TYPE (op
)))
184 BITMAP_FREE (nonnullargs
);
186 // Fallthru and walk load/store ops now.
189 // Check for inferred ranges from ASSUME calls.
190 if (is_a
<gcall
*> (s
) && gimple_call_internal_p (s
)
191 && gimple_call_internal_fn (s
) == IFN_ASSUME
)
192 check_assume_func (as_a
<gcall
*> (s
));
194 // Look for possible non-null values.
195 if (flag_delete_null_pointer_checks
&& gimple_code (s
) != GIMPLE_ASM
196 && !gimple_clobber_p (s
))
197 walk_stmt_load_store_ops (s
, (void *)this, non_null_loadstore
,
204 // Check if there are any inferred ranges from range-ops.
205 gimple_range_op_handler
handler (s
);
209 // Only proceed if ONE operand is an SSA_NAME, This may provide an
210 // inferred range for 'y + 3' , but will bypass expressions like
211 // 'y + z' as it depends on symbolic values.
212 tree ssa1
= gimple_range_ssa_p (handler
.operand1 ());
213 tree ssa2
= gimple_range_ssa_p (handler
.operand2 ());
214 if ((ssa1
!= NULL
) == (ssa2
!= NULL
))
217 // The other operand should be a constant, so just use the global range
218 // query to pick up any other values.
221 value_range
op1 (TREE_TYPE (ssa1
));
222 if (op1_range (op1
, s
, get_global_range_query ()) && !op1
.varying_p ())
223 add_range (ssa1
, op1
);
227 gcc_checking_assert (ssa2
);
228 value_range
op2 (TREE_TYPE (ssa2
));
229 if (op2_range (op2
, s
, get_global_range_query ()) && !op2
.varying_p ())
230 add_range (ssa2
, op2
);
234 // Create an single inferred range for NAMe using range R.
236 gimple_infer_range::gimple_infer_range (tree name
, vrange
&r
)
242 // -------------------------------------------------------------------------
244 // This class is an element in the list of inferred ranges.
251 vrange_storage
*range
;
256 // If there is an element which matches SSA, return a pointer to the element.
257 // Otherwise return NULL.
260 infer_range_manager::exit_range_head::find_ptr (tree ssa
)
262 // Return NULL if SSA is not in this list.
263 if (!m_names
|| !bitmap_bit_p (m_names
, SSA_NAME_VERSION (ssa
)))
265 for (exit_range
*ptr
= head
; ptr
!= NULL
; ptr
= ptr
->next
)
266 if (ptr
->name
== ssa
)
268 // Should be unreachable.
273 // Construct a range infer manager. DO_SEARCH indicates whether an immediate
274 // use scan should be made the first time a name is processed. This is for
275 // on-demand clients who may not visit every statement and may miss uses.
277 infer_range_manager::infer_range_manager (bool do_search
)
279 bitmap_obstack_initialize (&m_bitmaps
);
280 m_on_exit
.create (0);
281 m_on_exit
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
282 // m_seen == NULL indicates no scanning. Otherwise the bit indicates a
283 // scan has been performed on NAME.
285 m_seen
= BITMAP_ALLOC (&m_bitmaps
);
288 obstack_init (&m_list_obstack
);
289 // Non-zero elements are very common, so cache them for each ssa-name.
290 m_nonzero
.create (0);
291 m_nonzero
.safe_grow_cleared (num_ssa_names
+ 1);
292 m_range_allocator
= new vrange_allocator
;
295 // Destruct a range infer manager.
297 infer_range_manager::~infer_range_manager ()
299 m_nonzero
.release ();
300 obstack_free (&m_list_obstack
, NULL
);
301 m_on_exit
.release ();
302 bitmap_obstack_release (&m_bitmaps
);
303 delete m_range_allocator
;
306 // Return a non-zero range value of the appropriate type for NAME from
307 // the cache, creating it if necessary.
310 infer_range_manager::get_nonzero (tree name
)
312 unsigned v
= SSA_NAME_VERSION (name
);
313 if (v
>= m_nonzero
.length ())
314 m_nonzero
.safe_grow_cleared (num_ssa_names
+ 20);
318 = (irange
*) m_range_allocator
->alloc (sizeof (int_range
<2>));
319 m_nonzero
[v
]->set_nonzero (TREE_TYPE (name
));
321 return *(m_nonzero
[v
]);
324 // Return TRUE if NAME has a range inference in block BB. If NAME is NULL,
325 // return TRUE if there are any name sin BB.
328 infer_range_manager::has_range_p (basic_block bb
, tree name
)
330 // Check if this is an immediate use search model.
331 if (name
&& m_seen
&& !bitmap_bit_p (m_seen
, SSA_NAME_VERSION (name
)))
332 register_all_uses (name
);
334 if (bb
->index
>= (int)m_on_exit
.length ())
337 bitmap b
= m_on_exit
[bb
->index
].m_names
;
342 return bitmap_bit_p (m_on_exit
[bb
->index
].m_names
, SSA_NAME_VERSION (name
));
343 return !bitmap_empty_p (b
);
346 // Return TRUE if NAME has a range inference in block BB, and adjust range R
350 infer_range_manager::maybe_adjust_range (vrange
&r
, tree name
, basic_block bb
)
352 if (!has_range_p (bb
, name
))
354 exit_range
*ptr
= m_on_exit
[bb
->index
].find_ptr (name
);
355 gcc_checking_assert (ptr
);
356 // Return true if this exit range changes R, otherwise false.
357 tree type
= TREE_TYPE (name
);
358 value_range
tmp (type
);
359 ptr
->range
->get_vrange (tmp
, type
);
360 return r
.intersect (tmp
);
363 // Add all inferred ranges in INFER at stmt S.
366 infer_range_manager::add_ranges (gimple
*s
, gimple_infer_range
&infer
)
368 for (unsigned x
= 0; x
< infer
.num (); x
++)
369 add_range (infer
.name (x
), s
, infer
.range (x
));
372 // Add range R as an inferred range for NAME on stmt S.
375 infer_range_manager::add_range (tree name
, gimple
*s
, const vrange
&r
)
377 basic_block bb
= gimple_bb (s
);
380 if (bb
->index
>= (int)m_on_exit
.length ())
381 m_on_exit
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
383 // Create the summary list bitmap if it doesn't exist.
384 if (!m_on_exit
[bb
->index
].m_names
)
385 m_on_exit
[bb
->index
].m_names
= BITMAP_ALLOC (&m_bitmaps
);
387 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
389 fprintf (dump_file
, " on-exit update ");
390 print_generic_expr (dump_file
, name
, TDF_SLIM
);
391 fprintf (dump_file
, " in BB%d : ",bb
->index
);
393 fprintf (dump_file
, "\n");
396 // If NAME already has a range, intersect them and done.
397 exit_range
*ptr
= m_on_exit
[bb
->index
].find_ptr (name
);
400 tree type
= TREE_TYPE (name
);
401 value_range
cur (r
), name_range (type
);
402 ptr
->range
->get_vrange (name_range
, type
);
403 // If no new info is added, just return.
404 if (!cur
.intersect (name_range
))
406 if (ptr
->range
->fits_p (cur
))
407 ptr
->range
->set_vrange (cur
);
409 ptr
->range
= m_range_allocator
->clone (cur
);
414 // Otherwise create a record.
415 bitmap_set_bit (m_on_exit
[bb
->index
].m_names
, SSA_NAME_VERSION (name
));
416 ptr
= (exit_range
*)obstack_alloc (&m_list_obstack
, sizeof (exit_range
));
417 ptr
->range
= m_range_allocator
->clone (r
);
420 ptr
->next
= m_on_exit
[bb
->index
].head
;
421 m_on_exit
[bb
->index
].head
= ptr
;
424 // Add a non-zero inferred range for NAME at stmt S.
427 infer_range_manager::add_nonzero (tree name
, gimple
*s
)
429 add_range (name
, s
, get_nonzero (name
));
432 // Follow immediate use chains and find all inferred ranges for NAME.
435 infer_range_manager::register_all_uses (tree name
)
437 gcc_checking_assert (m_seen
);
439 // Check if we've already processed this name.
440 unsigned v
= SSA_NAME_VERSION (name
);
441 if (bitmap_bit_p (m_seen
, v
))
443 bitmap_set_bit (m_seen
, v
);
446 imm_use_iterator iter
;
448 // Loop over each immediate use and see if it has an inferred range.
449 FOR_EACH_IMM_USE_FAST (use_p
, iter
, name
)
451 gimple
*s
= USE_STMT (use_p
);
452 gimple_infer_range
infer (s
);
453 for (unsigned x
= 0; x
< infer
.num (); x
++)
455 if (name
== infer
.name (x
))
456 add_range (name
, s
, infer
.range (x
));