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