]>
Commit | Line | Data |
---|---|---|
156d7d8d | 1 | /* Gimple range inference implementation. |
b7501739 AM |
2 | Copyright (C) 2022 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" | |
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" | |
38 | ||
39 | // Adapted from infer_nonnull_range_by_dereference and check_loadstore | |
40 | // to process nonnull ssa_name OP in S. DATA contains a pointer to a | |
156d7d8d | 41 | // stmt range inference instance. |
b7501739 AM |
42 | |
43 | static bool | |
44 | non_null_loadstore (gimple *, tree op, tree, void *data) | |
45 | { | |
46 | if (TREE_CODE (op) == MEM_REF || TREE_CODE (op) == TARGET_MEM_REF) | |
47 | { | |
48 | /* Some address spaces may legitimately dereference zero. */ | |
49 | addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (op)); | |
50 | if (!targetm.addr_space.zero_address_valid (as)) | |
51 | { | |
52 | tree ssa = TREE_OPERAND (op, 0); | |
156d7d8d | 53 | ((gimple_infer_range *)data)->add_nonzero (ssa); |
b7501739 AM |
54 | } |
55 | } | |
56 | return false; | |
57 | } | |
58 | ||
156d7d8d | 59 | // Add NAME and RANGE to the the range inference summary. |
b7501739 AM |
60 | |
61 | void | |
45c8523d | 62 | gimple_infer_range::add_range (tree name, vrange &range) |
b7501739 AM |
63 | { |
64 | m_names[num_args] = name; | |
65 | m_ranges[num_args] = range; | |
66 | if (num_args < size_limit - 1) | |
67 | num_args++; | |
68 | } | |
69 | ||
156d7d8d | 70 | // Add a nonzero range for NAME to the range inference summary. |
b7501739 AM |
71 | |
72 | void | |
156d7d8d | 73 | gimple_infer_range::add_nonzero (tree name) |
b7501739 AM |
74 | { |
75 | if (!gimple_range_ssa_p (name)) | |
76 | return; | |
77 | int_range<2> nz; | |
78 | nz.set_nonzero (TREE_TYPE (name)); | |
79 | add_range (name, nz); | |
80 | } | |
81 | ||
156d7d8d AM |
82 | // Process S for range inference and fill in the summary list. |
83 | // This is the routine where new inferred ranges should be added. | |
b7501739 | 84 | |
156d7d8d | 85 | gimple_infer_range::gimple_infer_range (gimple *s) |
b7501739 AM |
86 | { |
87 | num_args = 0; | |
88 | ||
89 | if (is_a<gphi *> (s)) | |
90 | return; | |
91 | ||
92 | if (is_a<gcall *> (s) && flag_delete_null_pointer_checks) | |
93 | { | |
94 | tree fntype = gimple_call_fntype (s); | |
95 | bitmap nonnullargs = get_nonnull_args (fntype); | |
96 | // Process any non-null arguments | |
97 | if (nonnullargs) | |
98 | { | |
99 | for (unsigned i = 0; i < gimple_call_num_args (s); i++) | |
100 | { | |
101 | if (bitmap_empty_p (nonnullargs) | |
102 | || bitmap_bit_p (nonnullargs, i)) | |
103 | { | |
104 | tree op = gimple_call_arg (s, i); | |
105 | if (POINTER_TYPE_P (TREE_TYPE (op))) | |
106 | add_nonzero (op); | |
107 | } | |
108 | } | |
109 | BITMAP_FREE (nonnullargs); | |
110 | } | |
111 | // Fallthru and walk load/store ops now. | |
112 | } | |
113 | ||
114 | // Look for possible non-null values. | |
115 | if (flag_delete_null_pointer_checks && gimple_code (s) != GIMPLE_ASM | |
116 | && !gimple_clobber_p (s)) | |
117 | walk_stmt_load_store_ops (s, (void *)this, non_null_loadstore, | |
118 | non_null_loadstore); | |
119 | ||
120 | } | |
121 | ||
122 | // ------------------------------------------------------------------------- | |
123 | ||
761cc32e | 124 | // This class is an element in the list of infered ranges. |
b7501739 AM |
125 | |
126 | class exit_range | |
127 | { | |
128 | public: | |
129 | tree name; | |
45c8523d | 130 | vrange *range; |
b7501739 AM |
131 | exit_range *next; |
132 | }; | |
133 | ||
134 | // If there is an element which matches SSA, return a pointer to the element. | |
135 | // Otherwise return NULL. | |
136 | ||
137 | exit_range * | |
156d7d8d | 138 | infer_range_manager::exit_range_head::find_ptr (tree ssa) |
b7501739 AM |
139 | { |
140 | // Return NULL if SSA is not in this list. | |
141 | if (!m_names || !bitmap_bit_p (m_names, SSA_NAME_VERSION (ssa))) | |
142 | return NULL; | |
143 | for (exit_range *ptr = head; ptr != NULL; ptr = ptr->next) | |
144 | if (ptr->name == ssa) | |
145 | return ptr; | |
146 | // Should be unreachable. | |
147 | gcc_unreachable (); | |
148 | return NULL; | |
149 | } | |
150 | ||
156d7d8d | 151 | // Construct a range infer manager. DO_SEARCH indicates whether an immediate |
b7501739 AM |
152 | // use scan should be made the first time a name is processed. This is for |
153 | // on-demand clients who may not visit every statement and may miss uses. | |
154 | ||
156d7d8d | 155 | infer_range_manager::infer_range_manager (bool do_search) |
b7501739 AM |
156 | { |
157 | bitmap_obstack_initialize (&m_bitmaps); | |
158 | m_on_exit.create (0); | |
159 | m_on_exit.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); | |
160 | // m_seen == NULL indicates no scanning. Otherwise the bit indicates a | |
161 | // scan has been performed on NAME. | |
162 | if (do_search) | |
163 | m_seen = BITMAP_ALLOC (&m_bitmaps); | |
164 | else | |
165 | m_seen = NULL; | |
166 | obstack_init (&m_list_obstack); | |
167 | // Non-zero elements are very common, so cache them for each ssa-name. | |
168 | m_nonzero.create (0); | |
169 | m_nonzero.safe_grow_cleared (num_ssa_names + 1); | |
3ae9def0 | 170 | m_range_allocator = new obstack_vrange_allocator; |
b7501739 AM |
171 | } |
172 | ||
156d7d8d | 173 | // Destruct a range infer manager. |
b7501739 | 174 | |
156d7d8d | 175 | infer_range_manager::~infer_range_manager () |
b7501739 AM |
176 | { |
177 | m_nonzero.release (); | |
178 | obstack_free (&m_list_obstack, NULL); | |
179 | m_on_exit.release (); | |
180 | bitmap_obstack_release (&m_bitmaps); | |
3ae9def0 | 181 | delete m_range_allocator; |
b7501739 AM |
182 | } |
183 | ||
184 | // Return a non-zero range value of the appropriate type for NAME from | |
185 | // the cache, creating it if necessary. | |
186 | ||
45c8523d | 187 | const vrange& |
156d7d8d | 188 | infer_range_manager::get_nonzero (tree name) |
b7501739 AM |
189 | { |
190 | unsigned v = SSA_NAME_VERSION (name); | |
191 | if (v >= m_nonzero.length ()) | |
192 | m_nonzero.safe_grow_cleared (num_ssa_names + 20); | |
193 | if (!m_nonzero[v]) | |
194 | { | |
3ae9def0 | 195 | m_nonzero[v] = m_range_allocator->alloc_vrange (TREE_TYPE (name)); |
45c8523d | 196 | m_nonzero[v]->set_nonzero (TREE_TYPE (name)); |
b7501739 AM |
197 | } |
198 | return *(m_nonzero[v]); | |
199 | } | |
200 | ||
156d7d8d | 201 | // Return TRUE if NAME has a range inference in block BB. |
b7501739 AM |
202 | |
203 | bool | |
156d7d8d | 204 | infer_range_manager::has_range_p (tree name, basic_block bb) |
b7501739 AM |
205 | { |
206 | // Check if this is an immediate use search model. | |
207 | if (m_seen && !bitmap_bit_p (m_seen, SSA_NAME_VERSION (name))) | |
208 | register_all_uses (name); | |
209 | ||
210 | if (bb->index >= (int)m_on_exit.length ()) | |
211 | return false; | |
212 | if (!m_on_exit[bb->index].m_names) | |
213 | return false; | |
214 | if (!bitmap_bit_p (m_on_exit[bb->index].m_names, SSA_NAME_VERSION (name))) | |
215 | return false; | |
216 | return true; | |
217 | } | |
218 | ||
156d7d8d | 219 | // Return TRUE if NAME has a range inference in block BB, and adjust range R |
b7501739 AM |
220 | // to include it. |
221 | ||
222 | bool | |
45c8523d | 223 | infer_range_manager::maybe_adjust_range (vrange &r, tree name, basic_block bb) |
b7501739 AM |
224 | { |
225 | if (!has_range_p (name, bb)) | |
226 | return false; | |
227 | exit_range *ptr = m_on_exit[bb->index].find_ptr (name); | |
228 | gcc_checking_assert (ptr); | |
229 | // Return true if this exit range changes R, otherwise false. | |
230 | return r.intersect (*(ptr->range)); | |
231 | } | |
232 | ||
156d7d8d | 233 | // Add range R as an inferred range for NAME in block BB. |
b7501739 AM |
234 | |
235 | void | |
45c8523d | 236 | infer_range_manager::add_range (tree name, basic_block bb, const vrange &r) |
b7501739 AM |
237 | { |
238 | if (bb->index >= (int)m_on_exit.length ()) | |
239 | m_on_exit.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); | |
240 | ||
241 | // Create the summary list bitmap if it doesn't exist. | |
242 | if (!m_on_exit[bb->index].m_names) | |
243 | m_on_exit[bb->index].m_names = BITMAP_ALLOC (&m_bitmaps); | |
244 | ||
245 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
246 | { | |
247 | fprintf (dump_file, " on-exit update "); | |
248 | print_generic_expr (dump_file, name, TDF_SLIM); | |
249 | fprintf (dump_file, " in BB%d : ",bb->index); | |
250 | r.dump (dump_file); | |
251 | fprintf (dump_file, "\n"); | |
252 | } | |
253 | ||
254 | // If NAME already has a range, intersect them and done. | |
255 | exit_range *ptr = m_on_exit[bb->index].find_ptr (name); | |
256 | if (ptr) | |
257 | { | |
45c8523d | 258 | Value_Range cur (r); |
b7501739 AM |
259 | // If no new info is added, just return. |
260 | if (!cur.intersect (*(ptr->range))) | |
261 | return; | |
262 | if (ptr->range->fits_p (cur)) | |
263 | *(ptr->range) = cur; | |
264 | else | |
d8474337 AH |
265 | { |
266 | vrange &v = cur; | |
3ae9def0 | 267 | ptr->range = m_range_allocator->clone (v); |
d8474337 | 268 | } |
b7501739 AM |
269 | return; |
270 | } | |
271 | ||
272 | // Otherwise create a record. | |
273 | bitmap_set_bit (m_on_exit[bb->index].m_names, SSA_NAME_VERSION (name)); | |
274 | ptr = (exit_range *)obstack_alloc (&m_list_obstack, sizeof (exit_range)); | |
3ae9def0 | 275 | ptr->range = m_range_allocator->clone (r); |
b7501739 AM |
276 | ptr->name = name; |
277 | ptr->next = m_on_exit[bb->index].head; | |
278 | m_on_exit[bb->index].head = ptr; | |
279 | } | |
280 | ||
156d7d8d | 281 | // Add a non-zero inferred range for NAME in block BB. |
b7501739 AM |
282 | |
283 | void | |
156d7d8d | 284 | infer_range_manager::add_nonzero (tree name, basic_block bb) |
b7501739 AM |
285 | { |
286 | add_range (name, bb, get_nonzero (name)); | |
287 | } | |
288 | ||
156d7d8d | 289 | // Follow immediate use chains and find all inferred ranges for NAME. |
b7501739 AM |
290 | |
291 | void | |
156d7d8d | 292 | infer_range_manager::register_all_uses (tree name) |
b7501739 AM |
293 | { |
294 | gcc_checking_assert (m_seen); | |
295 | ||
296 | // Check if we've already processed this name. | |
297 | unsigned v = SSA_NAME_VERSION (name); | |
298 | if (bitmap_bit_p (m_seen, v)) | |
299 | return; | |
300 | bitmap_set_bit (m_seen, v); | |
301 | ||
302 | use_operand_p use_p; | |
303 | imm_use_iterator iter; | |
304 | ||
156d7d8d | 305 | // Loop over each immediate use and see if it has an inferred range. |
b7501739 AM |
306 | FOR_EACH_IMM_USE_FAST (use_p, iter, name) |
307 | { | |
308 | gimple *s = USE_STMT (use_p); | |
156d7d8d AM |
309 | gimple_infer_range infer (s); |
310 | for (unsigned x = 0; x < infer.num (); x++) | |
b7501739 | 311 | { |
156d7d8d AM |
312 | if (name == infer.name (x)) |
313 | add_range (name, gimple_bb (s), infer.range (x)); | |
b7501739 AM |
314 | } |
315 | } | |
316 | } |