]>
Commit | Line | Data |
---|---|---|
156d7d8d | 1 | /* Gimple range inference implementation. |
a945c346 | 2 | Copyright (C) 2022-2024 Free Software Foundation, Inc. |
b7501739 AM |
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" | |
3ae9def0 | 31 | #include "value-range-storage.h" |
b7501739 AM |
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" | |
53e6d7a3 | 38 | #include "tree-dfa.h" |
b7501739 | 39 | |
07441e41 AM |
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 | 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); } | |
55 | private: | |
56 | gimple_infer_range *m_infer; | |
57 | }; | |
58 | ||
b7501739 AM |
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 | |
156d7d8d | 61 | // stmt range inference instance. |
b7501739 AM |
62 | |
63 | static bool | |
64 | non_null_loadstore (gimple *, tree op, tree, void *data) | |
65 | { | |
66 | if (TREE_CODE (op) == MEM_REF || TREE_CODE (op) == TARGET_MEM_REF) | |
67 | { | |
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)) | |
71 | { | |
07441e41 AM |
72 | non_null_wrapper wrapper ((gimple_infer_range *)data); |
73 | wrapper.add_nonzero (TREE_OPERAND (op, 0)); | |
b7501739 AM |
74 | } |
75 | } | |
76 | return false; | |
77 | } | |
78 | ||
53e6d7a3 AM |
79 | // Process an ASSUME call to see if there are any inferred ranges available. |
80 | ||
81 | void | |
82 | gimple_infer_range::check_assume_func (gcall *call) | |
83 | { | |
84 | tree arg; | |
85 | unsigned i; | |
86 | tree assume_id = TREE_OPERAND (gimple_call_arg (call, 0), 0); | |
87 | if (!assume_id) | |
88 | return; | |
89 | struct function *fun = DECL_STRUCT_FUNCTION (assume_id); | |
90 | if (!fun) | |
91 | return; | |
c46b5b0a | 92 | // Loop over arguments, matching them to the assume parameters. |
53e6d7a3 AM |
93 | for (arg = DECL_ARGUMENTS (assume_id), i = 1; |
94 | arg && i < gimple_call_num_args (call); | |
95 | i++, arg = DECL_CHAIN (arg)) | |
96 | { | |
97 | tree op = gimple_call_arg (call, i); | |
98 | tree type = TREE_TYPE (op); | |
3dedfad5 | 99 | if (gimple_range_ssa_p (op) && value_range::supports_type_p (type)) |
53e6d7a3 AM |
100 | { |
101 | tree default_def = ssa_default_def (fun, arg); | |
102 | if (!default_def || type != TREE_TYPE (default_def)) | |
103 | continue; | |
104 | // Query the global range of the default def in the assume function. | |
3dedfad5 | 105 | value_range assume_range (type); |
99f3ad2e | 106 | gimple_range_global (assume_range, default_def, fun); |
53e6d7a3 AM |
107 | // If there is a non-varying result, add it as an inferred range. |
108 | if (!assume_range.varying_p ()) | |
109 | { | |
110 | add_range (op, assume_range); | |
111 | if (dump_file) | |
112 | { | |
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); | |
121 | } | |
122 | } | |
123 | } | |
124 | } | |
125 | } | |
126 | ||
a8bb495a | 127 | // Add NAME and RANGE to the range inference summary. |
b7501739 AM |
128 | |
129 | void | |
45c8523d | 130 | gimple_infer_range::add_range (tree name, vrange &range) |
b7501739 | 131 | { |
efc4255d AM |
132 | // Do not add an inferred range if it is VARYING. |
133 | if (range.varying_p ()) | |
134 | return; | |
b7501739 AM |
135 | m_names[num_args] = name; |
136 | m_ranges[num_args] = range; | |
137 | if (num_args < size_limit - 1) | |
138 | num_args++; | |
139 | } | |
140 | ||
156d7d8d | 141 | // Add a nonzero range for NAME to the range inference summary. |
b7501739 AM |
142 | |
143 | void | |
156d7d8d | 144 | gimple_infer_range::add_nonzero (tree name) |
b7501739 AM |
145 | { |
146 | if (!gimple_range_ssa_p (name)) | |
147 | return; | |
da73261c | 148 | prange nz; |
b7501739 AM |
149 | nz.set_nonzero (TREE_TYPE (name)); |
150 | add_range (name, nz); | |
151 | } | |
152 | ||
156d7d8d AM |
153 | // Process S for range inference and fill in the summary list. |
154 | // This is the routine where new inferred ranges should be added. | |
efc4255d AM |
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., | |
b7501739 | 159 | |
efc4255d | 160 | gimple_infer_range::gimple_infer_range (gimple *s, bool use_rangeops) |
b7501739 AM |
161 | { |
162 | num_args = 0; | |
163 | ||
164 | if (is_a<gphi *> (s)) | |
165 | return; | |
166 | ||
167 | if (is_a<gcall *> (s) && flag_delete_null_pointer_checks) | |
168 | { | |
169 | tree fntype = gimple_call_fntype (s); | |
170 | bitmap nonnullargs = get_nonnull_args (fntype); | |
171 | // Process any non-null arguments | |
172 | if (nonnullargs) | |
173 | { | |
174 | for (unsigned i = 0; i < gimple_call_num_args (s); i++) | |
175 | { | |
176 | if (bitmap_empty_p (nonnullargs) | |
177 | || bitmap_bit_p (nonnullargs, i)) | |
178 | { | |
179 | tree op = gimple_call_arg (s, i); | |
180 | if (POINTER_TYPE_P (TREE_TYPE (op))) | |
181 | add_nonzero (op); | |
182 | } | |
183 | } | |
184 | BITMAP_FREE (nonnullargs); | |
185 | } | |
186 | // Fallthru and walk load/store ops now. | |
187 | } | |
188 | ||
53e6d7a3 AM |
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)); | |
193 | ||
b7501739 AM |
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, | |
198 | non_null_loadstore); | |
199 | ||
efc4255d AM |
200 | // Gated by flag. |
201 | if (!use_rangeops) | |
202 | return; | |
203 | ||
204 | // Check if there are any inferred ranges from range-ops. | |
205 | gimple_range_op_handler handler (s); | |
206 | if (!handler) | |
207 | return; | |
208 | ||
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)) | |
215 | return; | |
216 | ||
217 | // The other operand should be a constant, so just use the global range | |
218 | // query to pick up any other values. | |
219 | if (ssa1) | |
220 | { | |
3dedfad5 | 221 | value_range op1 (TREE_TYPE (ssa1)); |
efc4255d AM |
222 | if (op1_range (op1, s, get_global_range_query ()) && !op1.varying_p ()) |
223 | add_range (ssa1, op1); | |
224 | } | |
225 | else | |
226 | { | |
227 | gcc_checking_assert (ssa2); | |
3dedfad5 | 228 | value_range op2 (TREE_TYPE (ssa2)); |
efc4255d AM |
229 | if (op2_range (op2, s, get_global_range_query ()) && !op2.varying_p ()) |
230 | add_range (ssa2, op2); | |
231 | } | |
b7501739 AM |
232 | } |
233 | ||
07441e41 AM |
234 | // Create an single inferred range for NAMe using range R. |
235 | ||
236 | gimple_infer_range::gimple_infer_range (tree name, vrange &r) | |
237 | { | |
238 | num_args = 0; | |
239 | add_range (name, r); | |
240 | } | |
241 | ||
b7501739 AM |
242 | // ------------------------------------------------------------------------- |
243 | ||
c46b5b0a | 244 | // This class is an element in the list of inferred ranges. |
b7501739 AM |
245 | |
246 | class exit_range | |
247 | { | |
248 | public: | |
249 | tree name; | |
07441e41 | 250 | gimple *stmt; |
e1366a7e | 251 | vrange_storage *range; |
b7501739 AM |
252 | exit_range *next; |
253 | }; | |
254 | ||
07441e41 | 255 | |
b7501739 AM |
256 | // If there is an element which matches SSA, return a pointer to the element. |
257 | // Otherwise return NULL. | |
258 | ||
259 | exit_range * | |
156d7d8d | 260 | infer_range_manager::exit_range_head::find_ptr (tree ssa) |
b7501739 AM |
261 | { |
262 | // Return NULL if SSA is not in this list. | |
263 | if (!m_names || !bitmap_bit_p (m_names, SSA_NAME_VERSION (ssa))) | |
264 | return NULL; | |
265 | for (exit_range *ptr = head; ptr != NULL; ptr = ptr->next) | |
266 | if (ptr->name == ssa) | |
267 | return ptr; | |
268 | // Should be unreachable. | |
269 | gcc_unreachable (); | |
270 | return NULL; | |
271 | } | |
272 | ||
156d7d8d | 273 | // Construct a range infer manager. DO_SEARCH indicates whether an immediate |
b7501739 AM |
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. | |
276 | ||
156d7d8d | 277 | infer_range_manager::infer_range_manager (bool do_search) |
b7501739 AM |
278 | { |
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. | |
284 | if (do_search) | |
285 | m_seen = BITMAP_ALLOC (&m_bitmaps); | |
286 | else | |
287 | m_seen = NULL; | |
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); | |
e1366a7e | 292 | m_range_allocator = new vrange_allocator; |
b7501739 AM |
293 | } |
294 | ||
156d7d8d | 295 | // Destruct a range infer manager. |
b7501739 | 296 | |
156d7d8d | 297 | infer_range_manager::~infer_range_manager () |
b7501739 AM |
298 | { |
299 | m_nonzero.release (); | |
300 | obstack_free (&m_list_obstack, NULL); | |
301 | m_on_exit.release (); | |
302 | bitmap_obstack_release (&m_bitmaps); | |
3ae9def0 | 303 | delete m_range_allocator; |
b7501739 AM |
304 | } |
305 | ||
306 | // Return a non-zero range value of the appropriate type for NAME from | |
307 | // the cache, creating it if necessary. | |
308 | ||
45c8523d | 309 | const vrange& |
156d7d8d | 310 | infer_range_manager::get_nonzero (tree name) |
b7501739 AM |
311 | { |
312 | unsigned v = SSA_NAME_VERSION (name); | |
313 | if (v >= m_nonzero.length ()) | |
314 | m_nonzero.safe_grow_cleared (num_ssa_names + 20); | |
315 | if (!m_nonzero[v]) | |
316 | { | |
e1366a7e AH |
317 | m_nonzero[v] |
318 | = (irange *) m_range_allocator->alloc (sizeof (int_range <2>)); | |
45c8523d | 319 | m_nonzero[v]->set_nonzero (TREE_TYPE (name)); |
b7501739 AM |
320 | } |
321 | return *(m_nonzero[v]); | |
322 | } | |
323 | ||
07441e41 AM |
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. | |
b7501739 AM |
326 | |
327 | bool | |
07441e41 | 328 | infer_range_manager::has_range_p (basic_block bb, tree name) |
b7501739 AM |
329 | { |
330 | // Check if this is an immediate use search model. | |
07441e41 | 331 | if (name && m_seen && !bitmap_bit_p (m_seen, SSA_NAME_VERSION (name))) |
b7501739 AM |
332 | register_all_uses (name); |
333 | ||
334 | if (bb->index >= (int)m_on_exit.length ()) | |
335 | return false; | |
07441e41 AM |
336 | |
337 | bitmap b = m_on_exit[bb->index].m_names; | |
338 | if (!b) | |
b7501739 | 339 | return false; |
07441e41 AM |
340 | |
341 | if (name) | |
342 | return bitmap_bit_p (m_on_exit[bb->index].m_names, SSA_NAME_VERSION (name)); | |
343 | return !bitmap_empty_p (b); | |
b7501739 AM |
344 | } |
345 | ||
156d7d8d | 346 | // Return TRUE if NAME has a range inference in block BB, and adjust range R |
b7501739 AM |
347 | // to include it. |
348 | ||
349 | bool | |
45c8523d | 350 | infer_range_manager::maybe_adjust_range (vrange &r, tree name, basic_block bb) |
b7501739 | 351 | { |
07441e41 | 352 | if (!has_range_p (bb, name)) |
b7501739 AM |
353 | return false; |
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. | |
e1366a7e | 357 | tree type = TREE_TYPE (name); |
3dedfad5 | 358 | value_range tmp (type); |
e1366a7e AH |
359 | ptr->range->get_vrange (tmp, type); |
360 | return r.intersect (tmp); | |
b7501739 AM |
361 | } |
362 | ||
07441e41 AM |
363 | // Add all inferred ranges in INFER at stmt S. |
364 | ||
365 | void | |
366 | infer_range_manager::add_ranges (gimple *s, gimple_infer_range &infer) | |
367 | { | |
368 | for (unsigned x = 0; x < infer.num (); x++) | |
369 | add_range (infer.name (x), s, infer.range (x)); | |
370 | } | |
371 | ||
372 | // Add range R as an inferred range for NAME on stmt S. | |
b7501739 AM |
373 | |
374 | void | |
07441e41 | 375 | infer_range_manager::add_range (tree name, gimple *s, const vrange &r) |
b7501739 | 376 | { |
07441e41 AM |
377 | basic_block bb = gimple_bb (s); |
378 | if (!bb) | |
379 | return; | |
b7501739 AM |
380 | if (bb->index >= (int)m_on_exit.length ()) |
381 | m_on_exit.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); | |
382 | ||
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); | |
386 | ||
387 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
388 | { | |
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); | |
392 | r.dump (dump_file); | |
393 | fprintf (dump_file, "\n"); | |
394 | } | |
395 | ||
396 | // If NAME already has a range, intersect them and done. | |
397 | exit_range *ptr = m_on_exit[bb->index].find_ptr (name); | |
398 | if (ptr) | |
399 | { | |
e1366a7e | 400 | tree type = TREE_TYPE (name); |
3dedfad5 | 401 | value_range cur (r), name_range (type); |
e1366a7e | 402 | ptr->range->get_vrange (name_range, type); |
b7501739 | 403 | // If no new info is added, just return. |
e1366a7e | 404 | if (!cur.intersect (name_range)) |
b7501739 AM |
405 | return; |
406 | if (ptr->range->fits_p (cur)) | |
e1366a7e | 407 | ptr->range->set_vrange (cur); |
b7501739 | 408 | else |
e1366a7e | 409 | ptr->range = m_range_allocator->clone (cur); |
07441e41 | 410 | ptr->stmt = s; |
b7501739 AM |
411 | return; |
412 | } | |
413 | ||
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)); | |
3ae9def0 | 417 | ptr->range = m_range_allocator->clone (r); |
b7501739 | 418 | ptr->name = name; |
07441e41 | 419 | ptr->stmt = s; |
b7501739 AM |
420 | ptr->next = m_on_exit[bb->index].head; |
421 | m_on_exit[bb->index].head = ptr; | |
422 | } | |
423 | ||
07441e41 | 424 | // Add a non-zero inferred range for NAME at stmt S. |
b7501739 AM |
425 | |
426 | void | |
07441e41 | 427 | infer_range_manager::add_nonzero (tree name, gimple *s) |
b7501739 | 428 | { |
07441e41 | 429 | add_range (name, s, get_nonzero (name)); |
b7501739 AM |
430 | } |
431 | ||
156d7d8d | 432 | // Follow immediate use chains and find all inferred ranges for NAME. |
b7501739 AM |
433 | |
434 | void | |
156d7d8d | 435 | infer_range_manager::register_all_uses (tree name) |
b7501739 AM |
436 | { |
437 | gcc_checking_assert (m_seen); | |
438 | ||
439 | // Check if we've already processed this name. | |
440 | unsigned v = SSA_NAME_VERSION (name); | |
441 | if (bitmap_bit_p (m_seen, v)) | |
442 | return; | |
443 | bitmap_set_bit (m_seen, v); | |
444 | ||
445 | use_operand_p use_p; | |
446 | imm_use_iterator iter; | |
447 | ||
156d7d8d | 448 | // Loop over each immediate use and see if it has an inferred range. |
b7501739 AM |
449 | FOR_EACH_IMM_USE_FAST (use_p, iter, name) |
450 | { | |
451 | gimple *s = USE_STMT (use_p); | |
156d7d8d AM |
452 | gimple_infer_range infer (s); |
453 | for (unsigned x = 0; x < infer.num (); x++) | |
b7501739 | 454 | { |
156d7d8d | 455 | if (name == infer.name (x)) |
07441e41 | 456 | add_range (name, s, infer.range (x)); |
b7501739 AM |
457 | } |
458 | } | |
459 | } |