Branch data Line data Source code
1 : : /* Gimple range inference implementation.
2 : : Copyright (C) 2022-2025 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 : 28606910 : inline non_null_wrapper (gimple_infer_range *infer) : m_infer (infer) { }
53 : 28606910 : 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 : 52482518 : non_null_loadstore (gimple *, tree op, tree, void *data)
65 : : {
66 : 52482518 : if (TREE_CODE (op) == MEM_REF || TREE_CODE (op) == TARGET_MEM_REF)
67 : : {
68 : : /* Some address spaces may legitimately dereference zero. */
69 : 28607413 : addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (op));
70 : 28607413 : if (!targetm.addr_space.zero_address_valid (as))
71 : : {
72 : 28606910 : non_null_wrapper wrapper ((gimple_infer_range *)data);
73 : 28606910 : wrapper.add_nonzero (TREE_OPERAND (op, 0));
74 : : }
75 : : }
76 : 52482518 : return false;
77 : : }
78 : :
79 : : // Process an ASSUME call to see if there are any inferred ranges available.
80 : :
81 : : void
82 : 403 : gimple_infer_range::check_assume_func (gcall *call)
83 : : {
84 : 403 : tree arg;
85 : 403 : unsigned i;
86 : 403 : tree assume_id = TREE_OPERAND (gimple_call_arg (call, 0), 0);
87 : 403 : if (!assume_id)
88 : : return;
89 : 403 : struct function *fun = DECL_STRUCT_FUNCTION (assume_id);
90 : 403 : if (!fun)
91 : : return;
92 : : // Loop over arguments, matching them to the assume parameters.
93 : 403 : for (arg = DECL_ARGUMENTS (assume_id), i = 1;
94 : 920 : arg && i < gimple_call_num_args (call);
95 : 517 : i++, arg = DECL_CHAIN (arg))
96 : : {
97 : 517 : tree op = gimple_call_arg (call, i);
98 : 517 : tree type = TREE_TYPE (op);
99 : 517 : if (gimple_range_ssa_p (op) && value_range::supports_type_p (type))
100 : : {
101 : 382 : tree default_def = ssa_default_def (fun, arg);
102 : 382 : 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 : 379 : value_range assume_range (type);
106 : 379 : gimple_range_global (assume_range, default_def, fun);
107 : : // If there is a non-varying result, add it as an inferred range.
108 : 379 : if (!assume_range.varying_p ())
109 : : {
110 : 214 : add_range (op, assume_range);
111 : 214 : 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 : 379 : }
124 : : }
125 : : }
126 : :
127 : : // Add NAME and RANGE to the range inference summary.
128 : :
129 : : void
130 : 23770637 : gimple_infer_range::add_range (tree name, vrange &range)
131 : : {
132 : : // Do not add an inferred range if it is VARYING.
133 : 23770637 : if (range.varying_p ())
134 : : return;
135 : 23768934 : m_names[num_args] = name;
136 : 23768934 : m_ranges[num_args] = range;
137 : 23768934 : if (num_args < size_limit - 1)
138 : 23768934 : num_args++;
139 : : }
140 : :
141 : : // Add a nonzero range for NAME to the range inference summary.
142 : :
143 : : void
144 : 34580395 : gimple_infer_range::add_nonzero (tree name)
145 : : {
146 : 34580395 : if (!gimple_range_ssa_p (name))
147 : 10829905 : return;
148 : 23750490 : prange nz;
149 : 23750490 : nz.set_nonzero (TREE_TYPE (name));
150 : 23750490 : add_range (name, nz);
151 : 23750490 : }
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 : 347122553 : gimple_infer_range::gimple_infer_range (gimple *s, range_query *q,
161 : 3818348083 : bool use_rangeops)
162 : : {
163 : 347122553 : num_args = 0;
164 : :
165 : 347122553 : if (is_a<gphi *> (s))
166 : 347122553 : return;
167 : :
168 : : // Default to the global query if none provided.
169 : 311805832 : if (!q)
170 : 0 : q = get_global_range_query ();
171 : :
172 : 311805832 : if (is_a<gcall *> (s) && flag_delete_null_pointer_checks)
173 : : {
174 : 19927546 : tree fntype = gimple_call_fntype (s);
175 : 19927546 : bitmap nonnullargs = get_nonnull_args (fntype);
176 : : // Process any non-null arguments
177 : 19927546 : if (nonnullargs)
178 : : {
179 : 14533910 : for (unsigned i = 0; i < gimple_call_num_args (s); i++)
180 : : {
181 : 10338634 : if (bitmap_empty_p (nonnullargs)
182 : 10338634 : || bitmap_bit_p (nonnullargs, i))
183 : : {
184 : 5373747 : tree op = gimple_call_arg (s, i);
185 : 5373747 : if (POINTER_TYPE_P (TREE_TYPE (op)))
186 : 5316372 : add_nonzero (op);
187 : : }
188 : : }
189 : 4195276 : BITMAP_FREE (nonnullargs);
190 : : }
191 : 19927546 : if (fntype)
192 : 19518884 : for (tree attrs = TYPE_ATTRIBUTES (fntype);
193 : 20884911 : (attrs = lookup_attribute ("nonnull_if_nonzero", attrs));
194 : 1366027 : attrs = TREE_CHAIN (attrs))
195 : : {
196 : 1366027 : tree args = TREE_VALUE (attrs);
197 : 1366027 : unsigned int idx = TREE_INT_CST_LOW (TREE_VALUE (args)) - 1;
198 : 1366027 : unsigned int idx2
199 : 1366027 : = TREE_INT_CST_LOW (TREE_VALUE (TREE_CHAIN (args))) - 1;
200 : 1366027 : if (idx < gimple_call_num_args (s)
201 : 1366027 : && idx2 < gimple_call_num_args (s))
202 : : {
203 : 1365958 : tree arg = gimple_call_arg (s, idx);
204 : 1365958 : tree arg2 = gimple_call_arg (s, idx2);
205 : 1370416 : if (!POINTER_TYPE_P (TREE_TYPE (arg))
206 : 1365697 : || !INTEGRAL_TYPE_P (TREE_TYPE (arg2))
207 : 2731640 : || integer_zerop (arg2))
208 : 917 : continue;
209 : 1365041 : if (integer_nonzerop (arg2))
210 : 270402 : add_nonzero (arg);
211 : : else
212 : : {
213 : 1094639 : value_range r (TREE_TYPE (arg2));
214 : 1094639 : if (q->range_of_expr (r, arg2, s)
215 : 1094639 : && !r.contains_p (build_zero_cst (TREE_TYPE (arg2))))
216 : 386711 : add_nonzero (arg);
217 : 1094639 : }
218 : : }
219 : : }
220 : : // Fallthru and walk load/store ops now.
221 : : }
222 : :
223 : : // Check for inferred ranges from ASSUME calls.
224 : 311805832 : if (is_a<gcall *> (s) && gimple_call_internal_p (s)
225 : 312227498 : && gimple_call_internal_fn (s) == IFN_ASSUME)
226 : 403 : check_assume_func (as_a<gcall *> (s));
227 : :
228 : : // Look for possible non-null values.
229 : 311677749 : if (flag_delete_null_pointer_checks && gimple_code (s) != GIMPLE_ASM
230 : 623297479 : && !gimple_clobber_p (s))
231 : 305200867 : walk_stmt_load_store_ops (s, (void *)this, non_null_loadstore,
232 : : non_null_loadstore);
233 : :
234 : : // Gated by flag.
235 : 311805832 : if (!use_rangeops)
236 : : return;
237 : :
238 : : // Check if there are any inferred ranges from range-ops.
239 : 0 : gimple_range_op_handler handler (s);
240 : 0 : if (!handler)
241 : : return;
242 : :
243 : : // Only proceed if ONE operand is an SSA_NAME, This may provide an
244 : : // inferred range for 'y + 3' , but will bypass expressions like
245 : : // 'y + z' as it depends on symbolic values.
246 : 0 : tree ssa1 = gimple_range_ssa_p (handler.operand1 ());
247 : 0 : tree ssa2 = gimple_range_ssa_p (handler.operand2 ());
248 : 0 : if ((ssa1 != NULL) == (ssa2 != NULL))
249 : : return;
250 : :
251 : : // The other operand should be a constant, so just use the global range
252 : : // query to pick up any other values.
253 : 0 : if (ssa1)
254 : : {
255 : 0 : value_range op1 (TREE_TYPE (ssa1));
256 : 0 : if (op1_range (op1, s, q) && !op1.varying_p ())
257 : 0 : add_range (ssa1, op1);
258 : 0 : }
259 : : else
260 : : {
261 : 0 : gcc_checking_assert (ssa2);
262 : 0 : value_range op2 (TREE_TYPE (ssa2));
263 : 0 : if (op2_range (op2, s, q) && !op2.varying_p ())
264 : 0 : add_range (ssa2, op2);
265 : 0 : }
266 : : }
267 : :
268 : : // Create an single inferred range for NAMe using range R.
269 : :
270 : 219263 : gimple_infer_range::gimple_infer_range (tree name, vrange &r)
271 : : {
272 : 19933 : num_args = 0;
273 : 19933 : add_range (name, r);
274 : 19933 : }
275 : :
276 : : // -------------------------------------------------------------------------
277 : :
278 : : // This class is an element in the list of inferred ranges.
279 : :
280 : : class exit_range
281 : : {
282 : : public:
283 : : tree name;
284 : : gimple *stmt;
285 : : vrange_storage *range;
286 : : exit_range *next;
287 : : };
288 : :
289 : :
290 : : // If there is an element which matches SSA, return a pointer to the element.
291 : : // Otherwise return NULL.
292 : :
293 : : exit_range *
294 : 16100444 : infer_range_manager::exit_range_head::find_ptr (tree ssa)
295 : : {
296 : : // Return NULL if SSA is not in this list.
297 : 32200888 : if (!m_names || !bitmap_bit_p (m_names, SSA_NAME_VERSION (ssa)))
298 : 9011228 : return NULL;
299 : 7647709 : for (exit_range *ptr = head; ptr != NULL; ptr = ptr->next)
300 : 7647709 : if (ptr->name == ssa)
301 : : return ptr;
302 : : // Should be unreachable.
303 : 0 : gcc_unreachable ();
304 : : return NULL;
305 : : }
306 : :
307 : : // Construct a range infer manager. DO_SEARCH indicates whether an immediate
308 : : // use scan should be made the first time a name is processed. This is for
309 : : // on-demand clients who may not visit every statement and may miss uses.
310 : : // Q is the range_query to use for any lookups. Default is NULL which maps
311 : : // to the global_range_query.
312 : :
313 : 27271053 : infer_range_manager::infer_range_manager (bool do_search, range_query *q)
314 : : {
315 : : // Set the range query to use.
316 : 27271053 : m_query = q ? q : get_global_range_query ();
317 : :
318 : 27271053 : bitmap_obstack_initialize (&m_bitmaps);
319 : 27271053 : m_on_exit.create (0);
320 : 27271053 : m_on_exit.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
321 : : // m_seen == NULL indicates no scanning. Otherwise the bit indicates a
322 : : // scan has been performed on NAME.
323 : 27271053 : if (do_search)
324 : 21581502 : m_seen = BITMAP_ALLOC (&m_bitmaps);
325 : : else
326 : 5689551 : m_seen = NULL;
327 : 27271053 : obstack_init (&m_list_obstack);
328 : : // Non-zero elements are very common, so cache them for each ssa-name.
329 : 27271053 : m_nonzero.create (0);
330 : 54542106 : m_nonzero.safe_grow_cleared (num_ssa_names + 1);
331 : 27271053 : m_range_allocator = new vrange_allocator;
332 : 27271053 : }
333 : :
334 : : // Destruct a range infer manager.
335 : :
336 : 54542106 : infer_range_manager::~infer_range_manager ()
337 : : {
338 : 27271053 : m_nonzero.release ();
339 : 27271053 : obstack_free (&m_list_obstack, NULL);
340 : 27271053 : m_on_exit.release ();
341 : 27271053 : bitmap_obstack_release (&m_bitmaps);
342 : 27271053 : delete m_range_allocator;
343 : 54542106 : }
344 : :
345 : : // Return a non-zero range value of the appropriate type for NAME from
346 : : // the cache, creating it if necessary.
347 : :
348 : : const vrange&
349 : 0 : infer_range_manager::get_nonzero (tree name)
350 : : {
351 : 0 : unsigned v = SSA_NAME_VERSION (name);
352 : 0 : if (v >= m_nonzero.length ())
353 : 0 : m_nonzero.safe_grow_cleared (num_ssa_names + 20);
354 : 0 : if (!m_nonzero[v])
355 : : {
356 : 0 : m_nonzero[v]
357 : 0 : = (irange *) m_range_allocator->alloc (sizeof (int_range <2>));
358 : 0 : m_nonzero[v]->set_nonzero (TREE_TYPE (name));
359 : : }
360 : 0 : return *(m_nonzero[v]);
361 : : }
362 : :
363 : : // Return TRUE if NAME has a range inference in block BB. If NAME is NULL,
364 : : // return TRUE if there are any name sin BB.
365 : :
366 : : bool
367 : 635371578 : infer_range_manager::has_range_p (basic_block bb, tree name)
368 : : {
369 : : // Check if this is an immediate use search model.
370 : 1002159575 : if (name && m_seen && !bitmap_bit_p (m_seen, SSA_NAME_VERSION (name)))
371 : 26644484 : register_all_uses (name);
372 : :
373 : 1270743156 : if (bb->index >= (int)m_on_exit.length ())
374 : : return false;
375 : :
376 : 635060230 : bitmap b = m_on_exit[bb->index].m_names;
377 : 635060230 : if (!b)
378 : : return false;
379 : :
380 : 52471334 : if (name)
381 : 49995219 : return bitmap_bit_p (m_on_exit[bb->index].m_names, SSA_NAME_VERSION (name));
382 : 2476115 : return !bitmap_empty_p (b);
383 : : }
384 : :
385 : : // Return TRUE if NAME has a range inference in block BB, and adjust range R
386 : : // to include it.
387 : :
388 : : bool
389 : 583930982 : infer_range_manager::maybe_adjust_range (vrange &r, tree name, basic_block bb)
390 : : {
391 : 583930982 : if (!has_range_p (bb, name))
392 : : return false;
393 : 5216952 : exit_range *ptr = m_on_exit[bb->index].find_ptr (name);
394 : 5216952 : gcc_checking_assert (ptr);
395 : : // Return true if this exit range changes R, otherwise false.
396 : 5216952 : tree type = TREE_TYPE (name);
397 : 5216952 : value_range tmp (type);
398 : 5216952 : ptr->range->get_vrange (tmp, type);
399 : 5216952 : return r.intersect (tmp);
400 : 5216952 : }
401 : :
402 : : // Add all inferred ranges in INFER at stmt S.
403 : :
404 : : void
405 : 16302367 : infer_range_manager::add_ranges (gimple *s, gimple_infer_range &infer)
406 : : {
407 : 32872793 : for (unsigned x = 0; x < infer.num (); x++)
408 : : {
409 : 16570426 : tree arg = infer.name (x);
410 : 16570426 : value_range r (TREE_TYPE (arg));
411 : 16570426 : m_query->range_of_expr (r, arg, s);
412 : : // Only add the inferred range if it changes the current range.
413 : 16570426 : if (r.intersect (infer.range (x)))
414 : 5470242 : add_range (arg, s, infer.range (x));
415 : 16570426 : }
416 : 16302367 : }
417 : :
418 : : // Add range R as an inferred range for NAME on stmt S.
419 : :
420 : : void
421 : 10883492 : infer_range_manager::add_range (tree name, gimple *s, const vrange &r)
422 : : {
423 : 10883492 : basic_block bb = gimple_bb (s);
424 : 10883492 : if (!bb)
425 : : return;
426 : 21766984 : if (bb->index >= (int)m_on_exit.length ())
427 : 4 : m_on_exit.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
428 : :
429 : : // Create the summary list bitmap if it doesn't exist.
430 : 10883492 : if (!m_on_exit[bb->index].m_names)
431 : 7532064 : m_on_exit[bb->index].m_names = BITMAP_ALLOC (&m_bitmaps);
432 : :
433 : 10883492 : if (dump_file && (dump_flags & TDF_DETAILS))
434 : : {
435 : 79 : fprintf (dump_file, " on-exit update ");
436 : 79 : print_generic_expr (dump_file, name, TDF_SLIM);
437 : 79 : fprintf (dump_file, " in BB%d : ",bb->index);
438 : 79 : r.dump (dump_file);
439 : 79 : fprintf (dump_file, "\n");
440 : : }
441 : :
442 : : // If NAME already has a range, intersect them and done.
443 : 10883492 : exit_range *ptr = m_on_exit[bb->index].find_ptr (name);
444 : 10883492 : if (ptr)
445 : : {
446 : 1872264 : tree type = TREE_TYPE (name);
447 : 1872264 : value_range cur (r), name_range (type);
448 : 1872264 : ptr->range->get_vrange (name_range, type);
449 : : // If no new info is added, just return.
450 : 1872264 : if (!cur.intersect (name_range))
451 : : return;
452 : 21 : if (ptr->range->fits_p (cur))
453 : 21 : ptr->range->set_vrange (cur);
454 : : else
455 : 0 : ptr->range = m_range_allocator->clone (cur);
456 : 21 : ptr->stmt = s;
457 : 21 : return;
458 : 1872264 : }
459 : :
460 : : // Otherwise create a record.
461 : 9011228 : bitmap_set_bit (m_on_exit[bb->index].m_names, SSA_NAME_VERSION (name));
462 : 9011228 : ptr = (exit_range *)obstack_alloc (&m_list_obstack, sizeof (exit_range));
463 : 9011228 : ptr->range = m_range_allocator->clone (r);
464 : 9011228 : ptr->name = name;
465 : 9011228 : ptr->stmt = s;
466 : 9011228 : ptr->next = m_on_exit[bb->index].head;
467 : 9011228 : m_on_exit[bb->index].head = ptr;
468 : : }
469 : :
470 : : // Add a non-zero inferred range for NAME at stmt S.
471 : :
472 : : void
473 : 0 : infer_range_manager::add_nonzero (tree name, gimple *s)
474 : : {
475 : 0 : add_range (name, s, get_nonzero (name));
476 : 0 : }
477 : :
478 : : // Follow immediate use chains and find all inferred ranges for NAME.
479 : :
480 : : void
481 : 26644484 : infer_range_manager::register_all_uses (tree name)
482 : : {
483 : 26644484 : gcc_checking_assert (m_seen);
484 : :
485 : : // Check if we've already processed this name.
486 : 26644484 : unsigned v = SSA_NAME_VERSION (name);
487 : 26644484 : if (bitmap_bit_p (m_seen, v))
488 : 0 : return;
489 : 26644484 : bitmap_set_bit (m_seen, v);
490 : :
491 : 26644484 : use_operand_p use_p;
492 : 26644484 : imm_use_iterator iter;
493 : :
494 : : // Loop over each immediate use and see if it has an inferred range.
495 : 119432844 : FOR_EACH_IMM_USE_FAST (use_p, iter, name)
496 : : {
497 : 92788360 : gimple *s = USE_STMT (use_p);
498 : 92788360 : gimple_infer_range infer (s, m_query);
499 : 99986868 : for (unsigned x = 0; x < infer.num (); x++)
500 : : {
501 : 7198508 : if (name == infer.name (x))
502 : 5413250 : add_range (name, s, infer.range (x));
503 : : }
504 : : }
505 : : }
|
