]>
Commit | Line | Data |
---|---|---|
74ba745b | 1 | /* Support routines for Value Range Propagation (VRP). |
85ec4feb | 2 | Copyright (C) 2005-2018 Free Software Foundation, Inc. |
74ba745b JL |
3 | |
4 | This file is part of GCC. | |
5 | ||
6 | GCC is free software; you can redistribute it and/or modify | |
7 | it under the terms of the GNU General Public License as published by | |
8 | the Free Software Foundation; either version 3, or (at your option) | |
9 | any later version. | |
10 | ||
11 | GCC is distributed in the hope that it will be useful, | |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | GNU General Public License for more details. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
17 | along with GCC; see the file COPYING3. If not see | |
18 | <http://www.gnu.org/licenses/>. */ | |
19 | ||
20 | #include "config.h" | |
21 | #include "system.h" | |
22 | #include "coretypes.h" | |
23 | #include "backend.h" | |
24 | #include "tree.h" | |
25 | #include "gimple.h" | |
26 | #include "tree-pass.h" | |
27 | #include "ssa.h" | |
28 | #include "gimple-pretty-print.h" | |
29 | #include "cfganal.h" | |
30 | #include "gimple-fold.h" | |
31 | #include "tree-eh.h" | |
32 | #include "gimple-iterator.h" | |
33 | #include "tree-cfg.h" | |
34 | #include "tree-ssa-loop-manip.h" | |
35 | #include "tree-ssa-loop.h" | |
36 | #include "cfgloop.h" | |
37 | #include "tree-scalar-evolution.h" | |
38 | #include "tree-ssa-propagate.h" | |
39 | #include "alloc-pool.h" | |
40 | #include "domwalk.h" | |
41 | #include "tree-cfgcleanup.h" | |
42 | #include "vr-values.h" | |
43 | #include "gimple-ssa-evrp-analyze.h" | |
44 | ||
45 | evrp_range_analyzer::evrp_range_analyzer () : stack (10) | |
46 | { | |
47 | edge e; | |
48 | edge_iterator ei; | |
49 | basic_block bb; | |
50 | FOR_EACH_BB_FN (bb, cfun) | |
51 | { | |
52 | bb->flags &= ~BB_VISITED; | |
53 | FOR_EACH_EDGE (e, ei, bb->preds) | |
54 | e->flags |= EDGE_EXECUTABLE; | |
55 | } | |
a5de02e9 | 56 | vr_values = new class vr_values; |
74ba745b JL |
57 | } |
58 | ||
df80fc53 JL |
59 | /* Push an unwinding marker onto the unwinding stack. */ |
60 | ||
74ba745b | 61 | void |
df80fc53 | 62 | evrp_range_analyzer::push_marker () |
74ba745b JL |
63 | { |
64 | stack.safe_push (std::make_pair (NULL_TREE, (value_range *)NULL)); | |
df80fc53 JL |
65 | } |
66 | ||
67 | /* Analyze ranges as we enter basic block BB. */ | |
68 | ||
69 | void | |
70 | evrp_range_analyzer::enter (basic_block bb) | |
71 | { | |
72 | push_marker (); | |
74ba745b JL |
73 | record_ranges_from_incoming_edge (bb); |
74 | record_ranges_from_phis (bb); | |
75 | bb->flags |= BB_VISITED; | |
76 | } | |
77 | ||
78 | /* Find new range for NAME such that (OP CODE LIMIT) is true. */ | |
79 | value_range * | |
80 | evrp_range_analyzer::try_find_new_range (tree name, | |
81 | tree op, tree_code code, tree limit) | |
82 | { | |
83 | value_range vr = VR_INITIALIZER; | |
84 | value_range *old_vr = get_value_range (name); | |
85 | ||
86 | /* Discover VR when condition is true. */ | |
a5de02e9 JL |
87 | vr_values->extract_range_for_var_from_comparison_expr (name, code, op, |
88 | limit, &vr); | |
74ba745b JL |
89 | /* If we found any usable VR, set the VR to ssa_name and create a |
90 | PUSH old value in the stack with the old VR. */ | |
91 | if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE) | |
92 | { | |
93 | if (old_vr->type == vr.type | |
94 | && vrp_operand_equal_p (old_vr->min, vr.min) | |
95 | && vrp_operand_equal_p (old_vr->max, vr.max)) | |
96 | return NULL; | |
3e406d33 | 97 | value_range *new_vr = vr_values->allocate_value_range (); |
74ba745b JL |
98 | *new_vr = vr; |
99 | return new_vr; | |
100 | } | |
101 | return NULL; | |
102 | } | |
103 | ||
4aa458f2 RB |
104 | /* For LHS record VR in the SSA info. */ |
105 | void | |
106 | evrp_range_analyzer::set_ssa_range_info (tree lhs, value_range *vr) | |
107 | { | |
108 | /* Set the SSA with the value range. */ | |
109 | if (INTEGRAL_TYPE_P (TREE_TYPE (lhs))) | |
110 | { | |
111 | if ((vr->type == VR_RANGE | |
112 | || vr->type == VR_ANTI_RANGE) | |
113 | && (TREE_CODE (vr->min) == INTEGER_CST) | |
114 | && (TREE_CODE (vr->max) == INTEGER_CST)) | |
115 | set_range_info (lhs, vr->type, | |
116 | wi::to_wide (vr->min), | |
117 | wi::to_wide (vr->max)); | |
118 | } | |
119 | else if (POINTER_TYPE_P (TREE_TYPE (lhs)) | |
120 | && ((vr->type == VR_RANGE | |
121 | && range_includes_zero_p (vr->min, | |
122 | vr->max) == 0) | |
123 | || (vr->type == VR_ANTI_RANGE | |
124 | && range_includes_zero_p (vr->min, | |
125 | vr->max) == 1))) | |
126 | set_ptr_nonnull (lhs); | |
127 | } | |
128 | ||
129 | /* Return true if all uses of NAME are dominated by STMT or feed STMT | |
130 | via a chain of single immediate uses. */ | |
131 | ||
132 | static bool | |
133 | all_uses_feed_or_dominated_by_stmt (tree name, gimple *stmt) | |
134 | { | |
135 | use_operand_p use_p, use2_p; | |
136 | imm_use_iterator iter; | |
137 | basic_block stmt_bb = gimple_bb (stmt); | |
138 | ||
139 | FOR_EACH_IMM_USE_FAST (use_p, iter, name) | |
140 | { | |
141 | gimple *use_stmt = USE_STMT (use_p), *use_stmt2; | |
142 | if (use_stmt == stmt | |
143 | || is_gimple_debug (use_stmt) | |
144 | || (gimple_bb (use_stmt) != stmt_bb | |
145 | && dominated_by_p (CDI_DOMINATORS, | |
146 | gimple_bb (use_stmt), stmt_bb))) | |
147 | continue; | |
148 | while (use_stmt != stmt | |
149 | && is_gimple_assign (use_stmt) | |
150 | && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME | |
151 | && single_imm_use (gimple_assign_lhs (use_stmt), | |
152 | &use2_p, &use_stmt2)) | |
153 | use_stmt = use_stmt2; | |
154 | if (use_stmt != stmt) | |
155 | return false; | |
156 | } | |
157 | return true; | |
158 | } | |
159 | ||
74ba745b JL |
160 | void |
161 | evrp_range_analyzer::record_ranges_from_incoming_edge (basic_block bb) | |
162 | { | |
163 | edge pred_e = single_pred_edge_ignoring_loop_edges (bb, false); | |
164 | if (pred_e) | |
165 | { | |
166 | gimple *stmt = last_stmt (pred_e->src); | |
167 | tree op0 = NULL_TREE; | |
168 | ||
169 | if (stmt | |
170 | && gimple_code (stmt) == GIMPLE_COND | |
171 | && (op0 = gimple_cond_lhs (stmt)) | |
172 | && TREE_CODE (op0) == SSA_NAME | |
173 | && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))) | |
174 | || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))))) | |
175 | { | |
176 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
177 | { | |
178 | fprintf (dump_file, "Visiting controlling predicate "); | |
179 | print_gimple_stmt (dump_file, stmt, 0); | |
180 | } | |
181 | /* Entering a new scope. Try to see if we can find a VR | |
182 | here. */ | |
183 | tree op1 = gimple_cond_rhs (stmt); | |
184 | if (TREE_OVERFLOW_P (op1)) | |
185 | op1 = drop_tree_overflow (op1); | |
186 | tree_code code = gimple_cond_code (stmt); | |
187 | ||
188 | auto_vec<assert_info, 8> asserts; | |
189 | register_edge_assert_for (op0, pred_e, code, op0, op1, asserts); | |
190 | if (TREE_CODE (op1) == SSA_NAME) | |
191 | register_edge_assert_for (op1, pred_e, code, op0, op1, asserts); | |
192 | ||
193 | auto_vec<std::pair<tree, value_range *>, 8> vrs; | |
194 | for (unsigned i = 0; i < asserts.length (); ++i) | |
195 | { | |
196 | value_range *vr = try_find_new_range (asserts[i].name, | |
197 | asserts[i].expr, | |
198 | asserts[i].comp_code, | |
199 | asserts[i].val); | |
200 | if (vr) | |
201 | vrs.safe_push (std::make_pair (asserts[i].name, vr)); | |
202 | } | |
4aa458f2 RB |
203 | |
204 | /* If pred_e is really a fallthru we can record value ranges | |
205 | in SSA names as well. */ | |
206 | bool is_fallthru = assert_unreachable_fallthru_edge_p (pred_e); | |
207 | ||
74ba745b JL |
208 | /* Push updated ranges only after finding all of them to avoid |
209 | ordering issues that can lead to worse ranges. */ | |
210 | for (unsigned i = 0; i < vrs.length (); ++i) | |
4aa458f2 RB |
211 | { |
212 | push_value_range (vrs[i].first, vrs[i].second); | |
213 | if (is_fallthru | |
214 | && all_uses_feed_or_dominated_by_stmt (vrs[i].first, stmt)) | |
215 | { | |
216 | set_ssa_range_info (vrs[i].first, vrs[i].second); | |
217 | maybe_set_nonzero_bits (pred_e, vrs[i].first); | |
218 | } | |
219 | } | |
74ba745b JL |
220 | } |
221 | } | |
222 | } | |
223 | ||
224 | void | |
225 | evrp_range_analyzer::record_ranges_from_phis (basic_block bb) | |
226 | { | |
227 | /* Visit PHI stmts and discover any new VRs possible. */ | |
228 | bool has_unvisited_preds = false; | |
229 | edge_iterator ei; | |
230 | edge e; | |
231 | FOR_EACH_EDGE (e, ei, bb->preds) | |
232 | if (e->flags & EDGE_EXECUTABLE | |
233 | && !(e->src->flags & BB_VISITED)) | |
234 | { | |
235 | has_unvisited_preds = true; | |
236 | break; | |
237 | } | |
238 | ||
239 | for (gphi_iterator gpi = gsi_start_phis (bb); | |
240 | !gsi_end_p (gpi); gsi_next (&gpi)) | |
241 | { | |
242 | gphi *phi = gpi.phi (); | |
243 | tree lhs = PHI_RESULT (phi); | |
244 | if (virtual_operand_p (lhs)) | |
245 | continue; | |
246 | ||
247 | value_range vr_result = VR_INITIALIZER; | |
248 | bool interesting = stmt_interesting_for_vrp (phi); | |
249 | if (!has_unvisited_preds && interesting) | |
a5de02e9 | 250 | vr_values->extract_range_from_phi_node (phi, &vr_result); |
74ba745b JL |
251 | else |
252 | { | |
253 | set_value_range_to_varying (&vr_result); | |
254 | /* When we have an unvisited executable predecessor we can't | |
255 | use PHI arg ranges which may be still UNDEFINED but have | |
256 | to use VARYING for them. But we can still resort to | |
257 | SCEV for loop header PHIs. */ | |
258 | struct loop *l; | |
5e4a80e8 JL |
259 | if (scev_initialized_p () |
260 | && interesting | |
74ba745b JL |
261 | && (l = loop_containing_stmt (phi)) |
262 | && l->header == gimple_bb (phi)) | |
a5de02e9 | 263 | vr_values->adjust_range_with_scev (&vr_result, l, phi, lhs); |
74ba745b | 264 | } |
a5de02e9 | 265 | vr_values->update_value_range (lhs, &vr_result); |
74ba745b JL |
266 | |
267 | /* Set the SSA with the value range. */ | |
4aa458f2 | 268 | set_ssa_range_info (lhs, &vr_result); |
74ba745b JL |
269 | } |
270 | } | |
271 | ||
df80fc53 JL |
272 | /* Record ranges from STMT into our VR_VALUES class. If TEMPORARY is |
273 | true, then this is a temporary equivalence and should be recorded | |
274 | into the unwind table. Othewise record the equivalence into the | |
275 | global table. */ | |
276 | ||
74ba745b | 277 | void |
df80fc53 | 278 | evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt, bool temporary) |
74ba745b JL |
279 | { |
280 | tree output = NULL_TREE; | |
281 | ||
282 | if (dyn_cast <gcond *> (stmt)) | |
283 | ; | |
284 | else if (stmt_interesting_for_vrp (stmt)) | |
285 | { | |
286 | edge taken_edge; | |
287 | value_range vr = VR_INITIALIZER; | |
a5de02e9 | 288 | vr_values->extract_range_from_stmt (stmt, &taken_edge, &output, &vr); |
d48f6f3f | 289 | if (output) |
74ba745b | 290 | { |
df80fc53 JL |
291 | /* Set the SSA with the value range. There are two cases to |
292 | consider. First (the the most common) is we are processing | |
293 | STMT in a context where its resulting range globally holds | |
294 | and thus it can be reflected into the global ranges and need | |
295 | not be unwound as we leave scope. | |
296 | ||
297 | The second case occurs if we are processing a statement in | |
298 | a context where the resulting range must not be reflected | |
299 | into the global tables and must be unwound as we leave | |
300 | the current context. This happens in jump threading for | |
301 | example. */ | |
302 | if (!temporary) | |
303 | { | |
304 | /* Case one. We can just update the underlying range | |
305 | information as well as the global information. */ | |
306 | vr_values->update_value_range (output, &vr); | |
307 | set_ssa_range_info (output, &vr); | |
308 | } | |
309 | else | |
310 | { | |
311 | /* We're going to need to unwind this range. We can | |
312 | not use VR as that's a stack object. We have to allocate | |
313 | a new range and push the old range onto the stack. We | |
314 | also have to be very careful about sharing the underlying | |
315 | bitmaps. Ugh. */ | |
316 | value_range *new_vr = vr_values->allocate_value_range (); | |
317 | *new_vr = vr; | |
318 | new_vr->equiv = NULL; | |
319 | push_value_range (output, new_vr); | |
320 | } | |
74ba745b JL |
321 | } |
322 | else | |
a5de02e9 | 323 | vr_values->set_defs_to_varying (stmt); |
74ba745b JL |
324 | } |
325 | else | |
a5de02e9 | 326 | vr_values->set_defs_to_varying (stmt); |
74ba745b JL |
327 | |
328 | /* See if we can derive a range for any of STMT's operands. */ | |
329 | tree op; | |
330 | ssa_op_iter i; | |
331 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE) | |
332 | { | |
333 | tree value; | |
334 | enum tree_code comp_code; | |
335 | ||
336 | /* If OP is used in such a way that we can infer a value | |
337 | range for it, and we don't find a previous assertion for | |
338 | it, create a new assertion location node for OP. */ | |
339 | if (infer_value_range (stmt, op, &comp_code, &value)) | |
340 | { | |
341 | /* If we are able to infer a nonzero value range for OP, | |
342 | then walk backwards through the use-def chain to see if OP | |
343 | was set via a typecast. | |
344 | If so, then we can also infer a nonzero value range | |
345 | for the operand of the NOP_EXPR. */ | |
346 | if (comp_code == NE_EXPR && integer_zerop (value)) | |
347 | { | |
348 | tree t = op; | |
349 | gimple *def_stmt = SSA_NAME_DEF_STMT (t); | |
350 | while (is_gimple_assign (def_stmt) | |
351 | && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)) | |
352 | && TREE_CODE | |
353 | (gimple_assign_rhs1 (def_stmt)) == SSA_NAME | |
354 | && POINTER_TYPE_P | |
355 | (TREE_TYPE (gimple_assign_rhs1 (def_stmt)))) | |
356 | { | |
357 | t = gimple_assign_rhs1 (def_stmt); | |
358 | def_stmt = SSA_NAME_DEF_STMT (t); | |
359 | ||
360 | /* Add VR when (T COMP_CODE value) condition is | |
361 | true. */ | |
362 | value_range *op_range | |
363 | = try_find_new_range (t, t, comp_code, value); | |
364 | if (op_range) | |
365 | push_value_range (t, op_range); | |
366 | } | |
367 | } | |
368 | /* Add VR when (OP COMP_CODE value) condition is true. */ | |
369 | value_range *op_range = try_find_new_range (op, op, | |
370 | comp_code, value); | |
371 | if (op_range) | |
372 | push_value_range (op, op_range); | |
373 | } | |
374 | } | |
375 | } | |
376 | ||
df80fc53 | 377 | /* Unwind recorded ranges to their most recent state. */ |
74ba745b JL |
378 | |
379 | void | |
df80fc53 | 380 | evrp_range_analyzer::pop_to_marker (void) |
74ba745b JL |
381 | { |
382 | gcc_checking_assert (!stack.is_empty ()); | |
383 | while (stack.last ().first != NULL_TREE) | |
384 | pop_value_range (stack.last ().first); | |
385 | stack.pop (); | |
386 | } | |
387 | ||
df80fc53 JL |
388 | /* Restore/pop VRs valid only for BB when we leave BB. */ |
389 | ||
390 | void | |
391 | evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED) | |
392 | { | |
393 | pop_to_marker (); | |
394 | } | |
395 | ||
396 | ||
74ba745b JL |
397 | /* Push the Value Range of VAR to the stack and update it with new VR. */ |
398 | ||
399 | void | |
400 | evrp_range_analyzer::push_value_range (tree var, value_range *vr) | |
401 | { | |
402 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
403 | { | |
404 | fprintf (dump_file, "pushing new range for "); | |
405 | print_generic_expr (dump_file, var); | |
406 | fprintf (dump_file, ": "); | |
407 | dump_value_range (dump_file, vr); | |
408 | fprintf (dump_file, "\n"); | |
409 | } | |
410 | stack.safe_push (std::make_pair (var, get_value_range (var))); | |
a5de02e9 | 411 | vr_values->set_vr_value (var, vr); |
74ba745b JL |
412 | } |
413 | ||
414 | /* Pop the Value Range from the vrp_stack and update VAR with it. */ | |
415 | ||
416 | value_range * | |
417 | evrp_range_analyzer::pop_value_range (tree var) | |
418 | { | |
419 | value_range *vr = stack.last ().second; | |
420 | gcc_checking_assert (var == stack.last ().first); | |
421 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
422 | { | |
423 | fprintf (dump_file, "popping range for "); | |
424 | print_generic_expr (dump_file, var); | |
425 | fprintf (dump_file, ", restoring "); | |
426 | dump_value_range (dump_file, vr); | |
427 | fprintf (dump_file, "\n"); | |
428 | } | |
a5de02e9 | 429 | vr_values->set_vr_value (var, vr); |
74ba745b JL |
430 | stack.pop (); |
431 | return vr; | |
432 | } |