Branch data Line data Source code
1 : : /* Gimple range inference implementation.
2 : : Copyright (C) 2022-2024 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 : : // Adapted from infer_nonnull_range_by_dereference and check_loadstore
41 : : // to process nonnull ssa_name OP in S. DATA contains a pointer to a
42 : : // stmt range inference instance.
43 : :
44 : : static bool
45 : 46151746 : non_null_loadstore (gimple *, tree op, tree, void *data)
46 : : {
47 : 46151746 : if (TREE_CODE (op) == MEM_REF || TREE_CODE (op) == TARGET_MEM_REF)
48 : : {
49 : : /* Some address spaces may legitimately dereference zero. */
50 : 23647000 : addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (op));
51 : 23647000 : if (!targetm.addr_space.zero_address_valid (as))
52 : : {
53 : 23646528 : tree ssa = TREE_OPERAND (op, 0);
54 : 23646528 : ((gimple_infer_range *)data)->add_nonzero (ssa);
55 : : }
56 : : }
57 : 46151746 : return false;
58 : : }
59 : :
60 : : // Process an ASSUME call to see if there are any inferred ranges available.
61 : :
62 : : void
63 : 378 : gimple_infer_range::check_assume_func (gcall *call)
64 : : {
65 : 378 : tree arg;
66 : 378 : unsigned i;
67 : 378 : tree assume_id = TREE_OPERAND (gimple_call_arg (call, 0), 0);
68 : 378 : if (!assume_id)
69 : : return;
70 : 378 : struct function *fun = DECL_STRUCT_FUNCTION (assume_id);
71 : 378 : if (!fun)
72 : : return;
73 : : // Loop over arguments, matching them to the assume parameters.
74 : 378 : for (arg = DECL_ARGUMENTS (assume_id), i = 1;
75 : 852 : arg && i < gimple_call_num_args (call);
76 : 474 : i++, arg = DECL_CHAIN (arg))
77 : : {
78 : 474 : tree op = gimple_call_arg (call, i);
79 : 474 : tree type = TREE_TYPE (op);
80 : 474 : if (gimple_range_ssa_p (op) && Value_Range::supports_type_p (type))
81 : : {
82 : 339 : tree default_def = ssa_default_def (fun, arg);
83 : 339 : if (!default_def || type != TREE_TYPE (default_def))
84 : 3 : continue;
85 : : // Query the global range of the default def in the assume function.
86 : 336 : Value_Range assume_range (type);
87 : 336 : gimple_range_global (assume_range, default_def, fun);
88 : : // If there is a non-varying result, add it as an inferred range.
89 : 336 : if (!assume_range.varying_p ())
90 : : {
91 : 184 : add_range (op, assume_range);
92 : 184 : if (dump_file)
93 : : {
94 : 37 : print_generic_expr (dump_file, assume_id, TDF_SLIM);
95 : 37 : fprintf (dump_file, " assume inferred range of ");
96 : 37 : print_generic_expr (dump_file, op, TDF_SLIM);
97 : 37 : fprintf (dump_file, " (param ");
98 : 37 : print_generic_expr (dump_file, arg, TDF_SLIM);
99 : 37 : fprintf (dump_file, ") = ");
100 : 37 : assume_range.dump (dump_file);
101 : 37 : fputc ('\n', dump_file);
102 : : }
103 : : }
104 : 336 : }
105 : : }
106 : : }
107 : :
108 : : // Add NAME and RANGE to the range inference summary.
109 : :
110 : : void
111 : 21023241 : gimple_infer_range::add_range (tree name, vrange &range)
112 : : {
113 : 21023241 : m_names[num_args] = name;
114 : 21023241 : m_ranges[num_args] = range;
115 : 21023241 : if (num_args < size_limit - 1)
116 : 21023241 : num_args++;
117 : 21023241 : }
118 : :
119 : : // Add a nonzero range for NAME to the range inference summary.
120 : :
121 : : void
122 : 28789403 : gimple_infer_range::add_nonzero (tree name)
123 : : {
124 : 28789403 : if (!gimple_range_ssa_p (name))
125 : 7766346 : return;
126 : 21023057 : int_range<2> nz;
127 : 21023057 : nz.set_nonzero (TREE_TYPE (name));
128 : 21023057 : add_range (name, nz);
129 : 21023057 : }
130 : :
131 : : // Process S for range inference and fill in the summary list.
132 : : // This is the routine where new inferred ranges should be added.
133 : :
134 : 3090223301 : gimple_infer_range::gimple_infer_range (gimple *s)
135 : : {
136 : 280929391 : num_args = 0;
137 : :
138 : 280929391 : if (is_a<gphi *> (s))
139 : : return;
140 : :
141 : 253944148 : if (is_a<gcall *> (s) && flag_delete_null_pointer_checks)
142 : : {
143 : 17863363 : tree fntype = gimple_call_fntype (s);
144 : 17863363 : bitmap nonnullargs = get_nonnull_args (fntype);
145 : : // Process any non-null arguments
146 : 17863363 : if (nonnullargs)
147 : : {
148 : 13612462 : for (unsigned i = 0; i < gimple_call_num_args (s); i++)
149 : : {
150 : 9657910 : if (bitmap_empty_p (nonnullargs)
151 : 9657910 : || bitmap_bit_p (nonnullargs, i))
152 : : {
153 : 5937501 : tree op = gimple_call_arg (s, i);
154 : 5937501 : if (POINTER_TYPE_P (TREE_TYPE (op)))
155 : 5142875 : add_nonzero (op);
156 : : }
157 : : }
158 : 3954552 : BITMAP_FREE (nonnullargs);
159 : : }
160 : : // Fallthru and walk load/store ops now.
161 : : }
162 : :
163 : : // Check for inferred ranges from ASSUME calls.
164 : 253944148 : if (is_a<gcall *> (s) && gimple_call_internal_p (s)
165 : 254330102 : && gimple_call_internal_fn (s) == IFN_ASSUME)
166 : 378 : check_assume_func (as_a<gcall *> (s));
167 : :
168 : : // Look for possible non-null values.
169 : 253870330 : if (flag_delete_null_pointer_checks && gimple_code (s) != GIMPLE_ASM
170 : 507599468 : && !gimple_clobber_p (s))
171 : 248644000 : walk_stmt_load_store_ops (s, (void *)this, non_null_loadstore,
172 : : non_null_loadstore);
173 : :
174 : : }
175 : :
176 : : // -------------------------------------------------------------------------
177 : :
178 : : // This class is an element in the list of inferred ranges.
179 : :
180 : : class exit_range
181 : : {
182 : : public:
183 : : tree name;
184 : : vrange_storage *range;
185 : : exit_range *next;
186 : : };
187 : :
188 : : // If there is an element which matches SSA, return a pointer to the element.
189 : : // Otherwise return NULL.
190 : :
191 : : exit_range *
192 : 29874548 : infer_range_manager::exit_range_head::find_ptr (tree ssa)
193 : : {
194 : : // Return NULL if SSA is not in this list.
195 : 59749096 : if (!m_names || !bitmap_bit_p (m_names, SSA_NAME_VERSION (ssa)))
196 : 14485239 : return NULL;
197 : 22283675 : for (exit_range *ptr = head; ptr != NULL; ptr = ptr->next)
198 : 22283675 : if (ptr->name == ssa)
199 : 15389309 : return ptr;
200 : : // Should be unreachable.
201 : 0 : gcc_unreachable ();
202 : : return NULL;
203 : : }
204 : :
205 : : // Construct a range infer manager. DO_SEARCH indicates whether an immediate
206 : : // use scan should be made the first time a name is processed. This is for
207 : : // on-demand clients who may not visit every statement and may miss uses.
208 : :
209 : 24313375 : infer_range_manager::infer_range_manager (bool do_search)
210 : : {
211 : 24313375 : bitmap_obstack_initialize (&m_bitmaps);
212 : 24313375 : m_on_exit.create (0);
213 : 24313375 : m_on_exit.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
214 : : // m_seen == NULL indicates no scanning. Otherwise the bit indicates a
215 : : // scan has been performed on NAME.
216 : 24313375 : if (do_search)
217 : 19089081 : m_seen = BITMAP_ALLOC (&m_bitmaps);
218 : : else
219 : 5224294 : m_seen = NULL;
220 : 24313375 : obstack_init (&m_list_obstack);
221 : : // Non-zero elements are very common, so cache them for each ssa-name.
222 : 24313375 : m_nonzero.create (0);
223 : 48626750 : m_nonzero.safe_grow_cleared (num_ssa_names + 1);
224 : 24313375 : m_range_allocator = new vrange_allocator;
225 : 24313375 : }
226 : :
227 : : // Destruct a range infer manager.
228 : :
229 : 24313375 : infer_range_manager::~infer_range_manager ()
230 : : {
231 : 24313375 : m_nonzero.release ();
232 : 24313375 : obstack_free (&m_list_obstack, NULL);
233 : 24313375 : m_on_exit.release ();
234 : 24313375 : bitmap_obstack_release (&m_bitmaps);
235 : 24313375 : delete m_range_allocator;
236 : 24313375 : }
237 : :
238 : : // Return a non-zero range value of the appropriate type for NAME from
239 : : // the cache, creating it if necessary.
240 : :
241 : : const vrange&
242 : 0 : infer_range_manager::get_nonzero (tree name)
243 : : {
244 : 0 : unsigned v = SSA_NAME_VERSION (name);
245 : 0 : if (v >= m_nonzero.length ())
246 : 0 : m_nonzero.safe_grow_cleared (num_ssa_names + 20);
247 : 0 : if (!m_nonzero[v])
248 : : {
249 : 0 : m_nonzero[v]
250 : 0 : = (irange *) m_range_allocator->alloc (sizeof (int_range <2>));
251 : 0 : m_nonzero[v]->set_nonzero (TREE_TYPE (name));
252 : : }
253 : 0 : return *(m_nonzero[v]);
254 : : }
255 : :
256 : : // Return TRUE if there are any range inferences in block BB.
257 : :
258 : : bool
259 : 27753227 : infer_range_manager::has_range_p (basic_block bb)
260 : : {
261 : 55506454 : if (bb->index >= (int)m_on_exit.length ())
262 : : return false;
263 : 27753227 : bitmap b = m_on_exit[bb->index].m_names;
264 : 27753227 : return b && !bitmap_empty_p (b);
265 : : }
266 : :
267 : : // Return TRUE if NAME has a range inference in block BB.
268 : :
269 : : bool
270 : 469073914 : infer_range_manager::has_range_p (tree name, basic_block bb)
271 : : {
272 : : // Check if this is an immediate use search model.
273 : 714557699 : if (m_seen && !bitmap_bit_p (m_seen, SSA_NAME_VERSION (name)))
274 : 19141157 : register_all_uses (name);
275 : :
276 : 938147828 : if (bb->index >= (int)m_on_exit.length ())
277 : : return false;
278 : 469073876 : if (!m_on_exit[bb->index].m_names)
279 : : return false;
280 : 83292675 : if (!bitmap_bit_p (m_on_exit[bb->index].m_names, SSA_NAME_VERSION (name)))
281 : : return false;
282 : : return true;
283 : : }
284 : :
285 : : // Return TRUE if NAME has a range inference in block BB, and adjust range R
286 : : // to include it.
287 : :
288 : : bool
289 : 439225252 : infer_range_manager::maybe_adjust_range (vrange &r, tree name, basic_block bb)
290 : : {
291 : 439225252 : if (!has_range_p (name, bb))
292 : : return false;
293 : 10368896 : exit_range *ptr = m_on_exit[bb->index].find_ptr (name);
294 : 10368896 : gcc_checking_assert (ptr);
295 : : // Return true if this exit range changes R, otherwise false.
296 : 10368896 : tree type = TREE_TYPE (name);
297 : 10368896 : Value_Range tmp (type);
298 : 10368896 : ptr->range->get_vrange (tmp, type);
299 : 10368896 : return r.intersect (tmp);
300 : 10368896 : }
301 : :
302 : : // Add range R as an inferred range for NAME in block BB.
303 : :
304 : : void
305 : 19505652 : infer_range_manager::add_range (tree name, basic_block bb, const vrange &r)
306 : : {
307 : 39011304 : if (bb->index >= (int)m_on_exit.length ())
308 : 0 : m_on_exit.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
309 : :
310 : : // Create the summary list bitmap if it doesn't exist.
311 : 19505652 : if (!m_on_exit[bb->index].m_names)
312 : 11067186 : m_on_exit[bb->index].m_names = BITMAP_ALLOC (&m_bitmaps);
313 : :
314 : 19505652 : if (dump_file && (dump_flags & TDF_DETAILS))
315 : : {
316 : 130 : fprintf (dump_file, " on-exit update ");
317 : 130 : print_generic_expr (dump_file, name, TDF_SLIM);
318 : 130 : fprintf (dump_file, " in BB%d : ",bb->index);
319 : 130 : r.dump (dump_file);
320 : 130 : fprintf (dump_file, "\n");
321 : : }
322 : :
323 : : // If NAME already has a range, intersect them and done.
324 : 19505652 : exit_range *ptr = m_on_exit[bb->index].find_ptr (name);
325 : 19505652 : if (ptr)
326 : : {
327 : 5020413 : tree type = TREE_TYPE (name);
328 : 5020413 : Value_Range cur (r), name_range (type);
329 : 5020413 : ptr->range->get_vrange (name_range, type);
330 : : // If no new info is added, just return.
331 : 5020413 : if (!cur.intersect (name_range))
332 : : return;
333 : 27 : if (ptr->range->fits_p (cur))
334 : 27 : ptr->range->set_vrange (cur);
335 : : else
336 : 0 : ptr->range = m_range_allocator->clone (cur);
337 : 27 : return;
338 : 5020413 : }
339 : :
340 : : // Otherwise create a record.
341 : 14485239 : bitmap_set_bit (m_on_exit[bb->index].m_names, SSA_NAME_VERSION (name));
342 : 14485239 : ptr = (exit_range *)obstack_alloc (&m_list_obstack, sizeof (exit_range));
343 : 14485239 : ptr->range = m_range_allocator->clone (r);
344 : 14485239 : ptr->name = name;
345 : 14485239 : ptr->next = m_on_exit[bb->index].head;
346 : 14485239 : m_on_exit[bb->index].head = ptr;
347 : : }
348 : :
349 : : // Add a non-zero inferred range for NAME in block BB.
350 : :
351 : : void
352 : 0 : infer_range_manager::add_nonzero (tree name, basic_block bb)
353 : : {
354 : 0 : add_range (name, bb, get_nonzero (name));
355 : 0 : }
356 : :
357 : : // Follow immediate use chains and find all inferred ranges for NAME.
358 : :
359 : : void
360 : 19141157 : infer_range_manager::register_all_uses (tree name)
361 : : {
362 : 19141157 : gcc_checking_assert (m_seen);
363 : :
364 : : // Check if we've already processed this name.
365 : 19141157 : unsigned v = SSA_NAME_VERSION (name);
366 : 19141157 : if (bitmap_bit_p (m_seen, v))
367 : 0 : return;
368 : 19141157 : bitmap_set_bit (m_seen, v);
369 : :
370 : 19141157 : use_operand_p use_p;
371 : 19141157 : imm_use_iterator iter;
372 : :
373 : : // Loop over each immediate use and see if it has an inferred range.
374 : 85888374 : FOR_EACH_IMM_USE_FAST (use_p, iter, name)
375 : : {
376 : 66747217 : gimple *s = USE_STMT (use_p);
377 : 66747217 : gimple_infer_range infer (s);
378 : 72893095 : for (unsigned x = 0; x < infer.num (); x++)
379 : : {
380 : 6145878 : if (name == infer.name (x))
381 : 4606146 : add_range (name, gimple_bb (s), infer.range (x));
382 : : }
383 : : }
384 : : }
|
