]>
Commit | Line | Data |
---|---|---|
8bd73801 | 1 | /* Support routines for Value Range Propagation (VRP). |
fbd26352 | 2 | Copyright (C) 2005-2019 Free Software Foundation, Inc. |
8bd73801 | 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 | ||
447602ef | 45 | evrp_range_analyzer::evrp_range_analyzer (bool update_global_ranges) |
46 | : stack (10), m_update_global_ranges (update_global_ranges) | |
8bd73801 | 47 | { |
48 | edge e; | |
49 | edge_iterator ei; | |
50 | basic_block bb; | |
51 | FOR_EACH_BB_FN (bb, cfun) | |
52 | { | |
53 | bb->flags &= ~BB_VISITED; | |
54 | FOR_EACH_EDGE (e, ei, bb->preds) | |
55 | e->flags |= EDGE_EXECUTABLE; | |
56 | } | |
c561e1e7 | 57 | vr_values = new class vr_values; |
8bd73801 | 58 | } |
59 | ||
4b69806c | 60 | /* Push an unwinding marker onto the unwinding stack. */ |
61 | ||
8bd73801 | 62 | void |
4b69806c | 63 | evrp_range_analyzer::push_marker () |
8bd73801 | 64 | { |
65 | stack.safe_push (std::make_pair (NULL_TREE, (value_range *)NULL)); | |
4b69806c | 66 | } |
67 | ||
68 | /* Analyze ranges as we enter basic block BB. */ | |
69 | ||
70 | void | |
71 | evrp_range_analyzer::enter (basic_block bb) | |
72 | { | |
e9332a4e | 73 | if (!optimize) |
74 | return; | |
4b69806c | 75 | push_marker (); |
8bd73801 | 76 | record_ranges_from_incoming_edge (bb); |
77 | record_ranges_from_phis (bb); | |
78 | bb->flags |= BB_VISITED; | |
79 | } | |
80 | ||
81 | /* Find new range for NAME such that (OP CODE LIMIT) is true. */ | |
82 | value_range * | |
83 | evrp_range_analyzer::try_find_new_range (tree name, | |
84 | tree op, tree_code code, tree limit) | |
85 | { | |
be44111e | 86 | value_range vr; |
448df21a | 87 | const value_range *old_vr = get_value_range (name); |
8bd73801 | 88 | |
89 | /* Discover VR when condition is true. */ | |
c561e1e7 | 90 | vr_values->extract_range_for_var_from_comparison_expr (name, code, op, |
91 | limit, &vr); | |
8bd73801 | 92 | /* If we found any usable VR, set the VR to ssa_name and create a |
93 | PUSH old value in the stack with the old VR. */ | |
be44111e | 94 | if (!vr.undefined_p () && !vr.varying_p ()) |
8bd73801 | 95 | { |
be44111e | 96 | if (old_vr->kind () == vr.kind () |
97 | && vrp_operand_equal_p (old_vr->min (), vr.min ()) | |
98 | && vrp_operand_equal_p (old_vr->max (), vr.max ())) | |
8bd73801 | 99 | return NULL; |
2e1f26dd | 100 | value_range *new_vr = vr_values->allocate_value_range (); |
48625f58 | 101 | new_vr->move (&vr); |
8bd73801 | 102 | return new_vr; |
103 | } | |
104 | return NULL; | |
105 | } | |
106 | ||
dd435793 | 107 | /* For LHS record VR in the SSA info. */ |
108 | void | |
109 | evrp_range_analyzer::set_ssa_range_info (tree lhs, value_range *vr) | |
110 | { | |
447602ef | 111 | gcc_assert (m_update_global_ranges); |
112 | ||
dd435793 | 113 | /* Set the SSA with the value range. */ |
114 | if (INTEGRAL_TYPE_P (TREE_TYPE (lhs))) | |
115 | { | |
be44111e | 116 | if (vr->constant_p ()) |
117 | set_range_info (lhs, vr->kind (), | |
118 | wi::to_wide (vr->min ()), | |
119 | wi::to_wide (vr->max ())); | |
dd435793 | 120 | } |
121 | else if (POINTER_TYPE_P (TREE_TYPE (lhs)) | |
6180f4cd | 122 | && range_includes_zero_p (vr) == 0) |
dd435793 | 123 | set_ptr_nonnull (lhs); |
124 | } | |
125 | ||
126 | /* Return true if all uses of NAME are dominated by STMT or feed STMT | |
127 | via a chain of single immediate uses. */ | |
128 | ||
129 | static bool | |
130 | all_uses_feed_or_dominated_by_stmt (tree name, gimple *stmt) | |
131 | { | |
132 | use_operand_p use_p, use2_p; | |
133 | imm_use_iterator iter; | |
134 | basic_block stmt_bb = gimple_bb (stmt); | |
135 | ||
136 | FOR_EACH_IMM_USE_FAST (use_p, iter, name) | |
137 | { | |
138 | gimple *use_stmt = USE_STMT (use_p), *use_stmt2; | |
139 | if (use_stmt == stmt | |
140 | || is_gimple_debug (use_stmt) | |
141 | || (gimple_bb (use_stmt) != stmt_bb | |
142 | && dominated_by_p (CDI_DOMINATORS, | |
143 | gimple_bb (use_stmt), stmt_bb))) | |
144 | continue; | |
145 | while (use_stmt != stmt | |
146 | && is_gimple_assign (use_stmt) | |
147 | && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME | |
148 | && single_imm_use (gimple_assign_lhs (use_stmt), | |
149 | &use2_p, &use_stmt2)) | |
150 | use_stmt = use_stmt2; | |
151 | if (use_stmt != stmt) | |
152 | return false; | |
153 | } | |
154 | return true; | |
155 | } | |
156 | ||
8bd73801 | 157 | void |
158 | evrp_range_analyzer::record_ranges_from_incoming_edge (basic_block bb) | |
159 | { | |
160 | edge pred_e = single_pred_edge_ignoring_loop_edges (bb, false); | |
161 | if (pred_e) | |
162 | { | |
163 | gimple *stmt = last_stmt (pred_e->src); | |
164 | tree op0 = NULL_TREE; | |
165 | ||
166 | if (stmt | |
167 | && gimple_code (stmt) == GIMPLE_COND | |
168 | && (op0 = gimple_cond_lhs (stmt)) | |
169 | && TREE_CODE (op0) == SSA_NAME | |
170 | && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))) | |
171 | || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))))) | |
172 | { | |
173 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
174 | { | |
175 | fprintf (dump_file, "Visiting controlling predicate "); | |
176 | print_gimple_stmt (dump_file, stmt, 0); | |
177 | } | |
178 | /* Entering a new scope. Try to see if we can find a VR | |
179 | here. */ | |
180 | tree op1 = gimple_cond_rhs (stmt); | |
181 | if (TREE_OVERFLOW_P (op1)) | |
182 | op1 = drop_tree_overflow (op1); | |
183 | tree_code code = gimple_cond_code (stmt); | |
184 | ||
185 | auto_vec<assert_info, 8> asserts; | |
186 | register_edge_assert_for (op0, pred_e, code, op0, op1, asserts); | |
187 | if (TREE_CODE (op1) == SSA_NAME) | |
188 | register_edge_assert_for (op1, pred_e, code, op0, op1, asserts); | |
189 | ||
190 | auto_vec<std::pair<tree, value_range *>, 8> vrs; | |
191 | for (unsigned i = 0; i < asserts.length (); ++i) | |
192 | { | |
193 | value_range *vr = try_find_new_range (asserts[i].name, | |
194 | asserts[i].expr, | |
195 | asserts[i].comp_code, | |
196 | asserts[i].val); | |
197 | if (vr) | |
198 | vrs.safe_push (std::make_pair (asserts[i].name, vr)); | |
199 | } | |
dd435793 | 200 | |
201 | /* If pred_e is really a fallthru we can record value ranges | |
202 | in SSA names as well. */ | |
203 | bool is_fallthru = assert_unreachable_fallthru_edge_p (pred_e); | |
204 | ||
8bd73801 | 205 | /* Push updated ranges only after finding all of them to avoid |
206 | ordering issues that can lead to worse ranges. */ | |
207 | for (unsigned i = 0; i < vrs.length (); ++i) | |
dd435793 | 208 | { |
3127e17b | 209 | /* But make sure we do not weaken ranges like when |
210 | getting first [64, +INF] and then ~[0, 0] from | |
211 | conditions like (s & 0x3cc0) == 0). */ | |
448df21a | 212 | const value_range *old_vr = get_value_range (vrs[i].first); |
0f01167a | 213 | value_range_base tem (old_vr->kind (), old_vr->min (), |
214 | old_vr->max ()); | |
3127e17b | 215 | tem.intersect (vrs[i].second); |
0f01167a | 216 | if (tem.equal_p (*old_vr)) |
d6f839ac | 217 | { |
218 | vr_values->free_value_range (vrs[i].second); | |
219 | continue; | |
220 | } | |
dd435793 | 221 | push_value_range (vrs[i].first, vrs[i].second); |
222 | if (is_fallthru | |
447602ef | 223 | && m_update_global_ranges |
dd435793 | 224 | && all_uses_feed_or_dominated_by_stmt (vrs[i].first, stmt)) |
225 | { | |
226 | set_ssa_range_info (vrs[i].first, vrs[i].second); | |
227 | maybe_set_nonzero_bits (pred_e, vrs[i].first); | |
228 | } | |
229 | } | |
8bd73801 | 230 | } |
231 | } | |
232 | } | |
233 | ||
234 | void | |
235 | evrp_range_analyzer::record_ranges_from_phis (basic_block bb) | |
236 | { | |
237 | /* Visit PHI stmts and discover any new VRs possible. */ | |
238 | bool has_unvisited_preds = false; | |
239 | edge_iterator ei; | |
240 | edge e; | |
241 | FOR_EACH_EDGE (e, ei, bb->preds) | |
242 | if (e->flags & EDGE_EXECUTABLE | |
243 | && !(e->src->flags & BB_VISITED)) | |
244 | { | |
245 | has_unvisited_preds = true; | |
246 | break; | |
247 | } | |
248 | ||
249 | for (gphi_iterator gpi = gsi_start_phis (bb); | |
250 | !gsi_end_p (gpi); gsi_next (&gpi)) | |
251 | { | |
252 | gphi *phi = gpi.phi (); | |
253 | tree lhs = PHI_RESULT (phi); | |
254 | if (virtual_operand_p (lhs)) | |
255 | continue; | |
256 | ||
d8f890de | 257 | /* Skips floats and other things we can't represent in a |
258 | range. */ | |
259 | if (!value_range_base::supports_type_p (TREE_TYPE (lhs))) | |
260 | continue; | |
261 | ||
be44111e | 262 | value_range vr_result; |
8bd73801 | 263 | bool interesting = stmt_interesting_for_vrp (phi); |
264 | if (!has_unvisited_preds && interesting) | |
c561e1e7 | 265 | vr_values->extract_range_from_phi_node (phi, &vr_result); |
8bd73801 | 266 | else |
267 | { | |
d8f890de | 268 | vr_result.set_varying (TREE_TYPE (lhs)); |
8bd73801 | 269 | /* When we have an unvisited executable predecessor we can't |
270 | use PHI arg ranges which may be still UNDEFINED but have | |
271 | to use VARYING for them. But we can still resort to | |
272 | SCEV for loop header PHIs. */ | |
2e966e2a | 273 | class loop *l; |
891c5e19 | 274 | if (scev_initialized_p () |
275 | && interesting | |
8bd73801 | 276 | && (l = loop_containing_stmt (phi)) |
277 | && l->header == gimple_bb (phi)) | |
c561e1e7 | 278 | vr_values->adjust_range_with_scev (&vr_result, l, phi, lhs); |
8bd73801 | 279 | } |
c561e1e7 | 280 | vr_values->update_value_range (lhs, &vr_result); |
8bd73801 | 281 | |
282 | /* Set the SSA with the value range. */ | |
447602ef | 283 | if (m_update_global_ranges) |
284 | set_ssa_range_info (lhs, &vr_result); | |
8bd73801 | 285 | } |
286 | } | |
287 | ||
4b69806c | 288 | /* Record ranges from STMT into our VR_VALUES class. If TEMPORARY is |
289 | true, then this is a temporary equivalence and should be recorded | |
290 | into the unwind table. Othewise record the equivalence into the | |
291 | global table. */ | |
292 | ||
8bd73801 | 293 | void |
4b69806c | 294 | evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt, bool temporary) |
8bd73801 | 295 | { |
296 | tree output = NULL_TREE; | |
297 | ||
e9332a4e | 298 | if (!optimize) |
299 | return; | |
300 | ||
8bd73801 | 301 | if (dyn_cast <gcond *> (stmt)) |
302 | ; | |
303 | else if (stmt_interesting_for_vrp (stmt)) | |
304 | { | |
305 | edge taken_edge; | |
be44111e | 306 | value_range vr; |
c561e1e7 | 307 | vr_values->extract_range_from_stmt (stmt, &taken_edge, &output, &vr); |
256aaca0 | 308 | if (output) |
8bd73801 | 309 | { |
4b69806c | 310 | /* Set the SSA with the value range. There are two cases to |
311 | consider. First (the the most common) is we are processing | |
312 | STMT in a context where its resulting range globally holds | |
313 | and thus it can be reflected into the global ranges and need | |
314 | not be unwound as we leave scope. | |
315 | ||
316 | The second case occurs if we are processing a statement in | |
317 | a context where the resulting range must not be reflected | |
318 | into the global tables and must be unwound as we leave | |
319 | the current context. This happens in jump threading for | |
320 | example. */ | |
321 | if (!temporary) | |
322 | { | |
323 | /* Case one. We can just update the underlying range | |
324 | information as well as the global information. */ | |
325 | vr_values->update_value_range (output, &vr); | |
447602ef | 326 | if (m_update_global_ranges) |
327 | set_ssa_range_info (output, &vr); | |
4b69806c | 328 | } |
329 | else | |
330 | { | |
07c11f2b | 331 | /* We're going to need to unwind this range. We cannot |
332 | use VR as that's a stack object. We have to allocate | |
4b69806c | 333 | a new range and push the old range onto the stack. We |
334 | also have to be very careful about sharing the underlying | |
335 | bitmaps. Ugh. */ | |
336 | value_range *new_vr = vr_values->allocate_value_range (); | |
48625f58 | 337 | new_vr->set (vr.kind (), vr.min (), vr.max ()); |
338 | vr.equiv_clear (); | |
4b69806c | 339 | push_value_range (output, new_vr); |
340 | } | |
8bd73801 | 341 | } |
342 | else | |
c561e1e7 | 343 | vr_values->set_defs_to_varying (stmt); |
8bd73801 | 344 | } |
345 | else | |
c561e1e7 | 346 | vr_values->set_defs_to_varying (stmt); |
8bd73801 | 347 | |
348 | /* See if we can derive a range for any of STMT's operands. */ | |
349 | tree op; | |
350 | ssa_op_iter i; | |
351 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE) | |
352 | { | |
353 | tree value; | |
354 | enum tree_code comp_code; | |
355 | ||
356 | /* If OP is used in such a way that we can infer a value | |
357 | range for it, and we don't find a previous assertion for | |
358 | it, create a new assertion location node for OP. */ | |
359 | if (infer_value_range (stmt, op, &comp_code, &value)) | |
360 | { | |
361 | /* If we are able to infer a nonzero value range for OP, | |
362 | then walk backwards through the use-def chain to see if OP | |
363 | was set via a typecast. | |
364 | If so, then we can also infer a nonzero value range | |
365 | for the operand of the NOP_EXPR. */ | |
366 | if (comp_code == NE_EXPR && integer_zerop (value)) | |
367 | { | |
368 | tree t = op; | |
369 | gimple *def_stmt = SSA_NAME_DEF_STMT (t); | |
370 | while (is_gimple_assign (def_stmt) | |
371 | && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)) | |
372 | && TREE_CODE | |
373 | (gimple_assign_rhs1 (def_stmt)) == SSA_NAME | |
374 | && POINTER_TYPE_P | |
375 | (TREE_TYPE (gimple_assign_rhs1 (def_stmt)))) | |
376 | { | |
377 | t = gimple_assign_rhs1 (def_stmt); | |
378 | def_stmt = SSA_NAME_DEF_STMT (t); | |
379 | ||
380 | /* Add VR when (T COMP_CODE value) condition is | |
381 | true. */ | |
382 | value_range *op_range | |
383 | = try_find_new_range (t, t, comp_code, value); | |
384 | if (op_range) | |
385 | push_value_range (t, op_range); | |
386 | } | |
387 | } | |
388 | /* Add VR when (OP COMP_CODE value) condition is true. */ | |
389 | value_range *op_range = try_find_new_range (op, op, | |
390 | comp_code, value); | |
391 | if (op_range) | |
392 | push_value_range (op, op_range); | |
393 | } | |
394 | } | |
395 | } | |
396 | ||
4b69806c | 397 | /* Unwind recorded ranges to their most recent state. */ |
8bd73801 | 398 | |
399 | void | |
4b69806c | 400 | evrp_range_analyzer::pop_to_marker (void) |
8bd73801 | 401 | { |
402 | gcc_checking_assert (!stack.is_empty ()); | |
403 | while (stack.last ().first != NULL_TREE) | |
d6f839ac | 404 | pop_value_range (); |
8bd73801 | 405 | stack.pop (); |
406 | } | |
407 | ||
4b69806c | 408 | /* Restore/pop VRs valid only for BB when we leave BB. */ |
409 | ||
410 | void | |
411 | evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED) | |
412 | { | |
e9332a4e | 413 | if (!optimize) |
414 | return; | |
4b69806c | 415 | pop_to_marker (); |
416 | } | |
417 | ||
418 | ||
8bd73801 | 419 | /* Push the Value Range of VAR to the stack and update it with new VR. */ |
420 | ||
421 | void | |
422 | evrp_range_analyzer::push_value_range (tree var, value_range *vr) | |
423 | { | |
424 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
425 | { | |
426 | fprintf (dump_file, "pushing new range for "); | |
427 | print_generic_expr (dump_file, var); | |
428 | fprintf (dump_file, ": "); | |
429 | dump_value_range (dump_file, vr); | |
430 | fprintf (dump_file, "\n"); | |
431 | } | |
d6f839ac | 432 | value_range *old_vr = vr_values->swap_vr_value (var, vr); |
433 | stack.safe_push (std::make_pair (var, old_vr)); | |
8bd73801 | 434 | } |
435 | ||
d6f839ac | 436 | /* Pop a Value Range from the vrp_stack. */ |
8bd73801 | 437 | |
d6f839ac | 438 | void |
439 | evrp_range_analyzer::pop_value_range () | |
8bd73801 | 440 | { |
d6f839ac | 441 | std::pair<tree, value_range *> e = stack.pop (); |
442 | tree var = e.first; | |
443 | value_range *vr = e.second; | |
8bd73801 | 444 | if (dump_file && (dump_flags & TDF_DETAILS)) |
445 | { | |
446 | fprintf (dump_file, "popping range for "); | |
447 | print_generic_expr (dump_file, var); | |
448 | fprintf (dump_file, ", restoring "); | |
449 | dump_value_range (dump_file, vr); | |
450 | fprintf (dump_file, "\n"); | |
451 | } | |
d6f839ac | 452 | /* We saved off a lattice entry, now give it back and release |
453 | the one we popped. */ | |
454 | value_range *popped_vr = vr_values->swap_vr_value (var, vr); | |
455 | if (popped_vr) | |
456 | vr_values->free_value_range (popped_vr); | |
8bd73801 | 457 | } |