]>
Commit | Line | Data |
---|---|---|
9c015ccf | 1 | /* Support routines for Value Range Propagation (VRP). |
2 | Copyright (C) 2005-2017 Free Software Foundation, Inc. | |
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 | ||
44 | class evrp_folder : public substitute_and_fold_engine | |
45 | { | |
46 | public: | |
47 | tree get_value (tree) FINAL OVERRIDE; | |
48 | ||
49 | class vr_values *vr_values; | |
50 | }; | |
51 | ||
52 | tree | |
53 | evrp_folder::get_value (tree op) | |
54 | { | |
55 | return vr_values->op_with_constant_singleton_value_range (op); | |
56 | } | |
57 | ||
71ddacbb | 58 | class evrp_range_analyzer |
59 | { | |
60 | public: | |
61 | evrp_range_analyzer (void); | |
62 | ~evrp_range_analyzer (void) { stack.release (); } | |
63 | ||
64 | void enter (basic_block); | |
65 | void leave (basic_block); | |
66 | void record_ranges_from_stmt (gimple *); | |
67 | ||
68 | class vr_values vr_values; | |
69 | ||
70 | private: | |
71 | DISABLE_COPY_AND_ASSIGN (evrp_range_analyzer); | |
72 | void push_value_range (tree var, value_range *vr); | |
73 | value_range *pop_value_range (tree var); | |
74 | value_range *try_find_new_range (tree, tree op, tree_code code, tree limit); | |
75 | void record_ranges_from_incoming_edge (basic_block); | |
76 | void record_ranges_from_phis (basic_block); | |
77 | ||
78 | /* STACK holds the old VR. */ | |
79 | auto_vec<std::pair <tree, value_range*> > stack; | |
80 | ||
81 | /* Temporary delegators. */ | |
82 | value_range *get_value_range (const_tree op) | |
83 | { return vr_values.get_value_range (op); } | |
84 | bool update_value_range (const_tree op, value_range *vr) | |
85 | { return vr_values.update_value_range (op, vr); } | |
86 | void extract_range_from_phi_node (gphi *phi, value_range *vr) | |
87 | { vr_values.extract_range_from_phi_node (phi, vr); } | |
88 | void adjust_range_with_scev (value_range *vr, struct loop *loop, | |
89 | gimple *stmt, tree var) | |
90 | { vr_values.adjust_range_with_scev (vr, loop, stmt, var); } | |
91 | void extract_range_from_stmt (gimple *stmt, edge *taken_edge_p, | |
92 | tree *output_p, value_range *vr) | |
93 | { vr_values.extract_range_from_stmt (stmt, taken_edge_p, output_p, vr); } | |
94 | void set_defs_to_varying (gimple *stmt) | |
95 | { return vr_values.set_defs_to_varying (stmt); } | |
96 | void set_vr_value (tree name, value_range *vr) | |
97 | { vr_values.set_vr_value (name, vr); } | |
98 | void extract_range_for_var_from_comparison_expr (tree var, | |
99 | enum tree_code cond_code, | |
100 | tree op, tree limit, | |
101 | value_range *vr_p) | |
102 | { vr_values.extract_range_for_var_from_comparison_expr (var, cond_code, | |
103 | op, limit, vr_p); } | |
104 | }; | |
105 | ||
106 | evrp_range_analyzer::evrp_range_analyzer () : stack (10) | |
107 | { | |
108 | edge e; | |
109 | edge_iterator ei; | |
110 | basic_block bb; | |
111 | ||
112 | FOR_EACH_BB_FN (bb, cfun) | |
113 | { | |
114 | bb->flags &= ~BB_VISITED; | |
115 | FOR_EACH_EDGE (e, ei, bb->preds) | |
116 | e->flags |= EDGE_EXECUTABLE; | |
117 | } | |
118 | } | |
119 | ||
120 | ||
9c015ccf | 121 | /* evrp_dom_walker visits the basic blocks in the dominance order and set |
122 | the Value Ranges (VR) for SSA_NAMEs in the scope. Use this VR to | |
123 | discover more VRs. */ | |
124 | ||
125 | class evrp_dom_walker : public dom_walker | |
126 | { | |
127 | public: | |
71ddacbb | 128 | evrp_dom_walker () : dom_walker (CDI_DOMINATORS) |
9c015ccf | 129 | { |
130 | need_eh_cleanup = BITMAP_ALLOC (NULL); | |
131 | } | |
132 | ~evrp_dom_walker () | |
133 | { | |
134 | BITMAP_FREE (need_eh_cleanup); | |
135 | } | |
136 | virtual edge before_dom_children (basic_block); | |
137 | virtual void after_dom_children (basic_block); | |
a62a30a4 | 138 | void cleanup (void); |
139 | ||
140 | private: | |
141 | DISABLE_COPY_AND_ASSIGN (evrp_dom_walker); | |
9c015ccf | 142 | bitmap need_eh_cleanup; |
143 | auto_vec<gimple *> stmts_to_fixup; | |
144 | auto_vec<gimple *> stmts_to_remove; | |
145 | ||
71ddacbb | 146 | class evrp_range_analyzer evrp_range_analyzer; |
9c015ccf | 147 | |
148 | /* Temporary delegators. */ | |
149 | value_range *get_value_range (const_tree op) | |
71ddacbb | 150 | { return evrp_range_analyzer.vr_values.get_value_range (op); } |
9c015ccf | 151 | tree op_with_constant_singleton_value_range (tree op) |
71ddacbb | 152 | { return evrp_range_analyzer.vr_values.op_with_constant_singleton_value_range (op); } |
9c015ccf | 153 | void vrp_visit_cond_stmt (gcond *cond, edge *e) |
71ddacbb | 154 | { evrp_range_analyzer.vr_values.vrp_visit_cond_stmt (cond, e); } |
9c015ccf | 155 | }; |
156 | ||
71ddacbb | 157 | void |
158 | evrp_range_analyzer::enter (basic_block bb) | |
159 | { | |
160 | stack.safe_push (std::make_pair (NULL_TREE, (value_range *)NULL)); | |
161 | record_ranges_from_incoming_edge (bb); | |
162 | record_ranges_from_phis (bb); | |
163 | } | |
9c015ccf | 164 | |
71ddacbb | 165 | /* Find new range for NAME such that (OP CODE LIMIT) is true. */ |
9c015ccf | 166 | value_range * |
71ddacbb | 167 | evrp_range_analyzer::try_find_new_range (tree name, |
168 | tree op, tree_code code, tree limit) | |
9c015ccf | 169 | { |
170 | value_range vr = VR_INITIALIZER; | |
171 | value_range *old_vr = get_value_range (name); | |
172 | ||
173 | /* Discover VR when condition is true. */ | |
174 | extract_range_for_var_from_comparison_expr (name, code, op, | |
175 | limit, &vr); | |
176 | /* If we found any usable VR, set the VR to ssa_name and create a | |
177 | PUSH old value in the stack with the old VR. */ | |
178 | if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE) | |
179 | { | |
180 | if (old_vr->type == vr.type | |
181 | && vrp_operand_equal_p (old_vr->min, vr.min) | |
182 | && vrp_operand_equal_p (old_vr->max, vr.max)) | |
183 | return NULL; | |
184 | value_range *new_vr = vr_values.vrp_value_range_pool.allocate (); | |
185 | *new_vr = vr; | |
186 | return new_vr; | |
187 | } | |
188 | return NULL; | |
189 | } | |
190 | ||
5c56ab3e | 191 | /* If BB is reached by a single incoming edge (ignoring loop edges), |
192 | then derive ranges implied by traversing that edge. */ | |
9c015ccf | 193 | |
5c56ab3e | 194 | void |
71ddacbb | 195 | evrp_range_analyzer::record_ranges_from_incoming_edge (basic_block bb) |
9c015ccf | 196 | { |
9c015ccf | 197 | edge pred_e = single_pred_edge_ignoring_loop_edges (bb, false); |
198 | if (pred_e) | |
199 | { | |
200 | gimple *stmt = last_stmt (pred_e->src); | |
201 | tree op0 = NULL_TREE; | |
202 | ||
203 | if (stmt | |
204 | && gimple_code (stmt) == GIMPLE_COND | |
205 | && (op0 = gimple_cond_lhs (stmt)) | |
206 | && TREE_CODE (op0) == SSA_NAME | |
207 | && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))) | |
208 | || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))))) | |
209 | { | |
210 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
211 | { | |
212 | fprintf (dump_file, "Visiting controlling predicate "); | |
213 | print_gimple_stmt (dump_file, stmt, 0); | |
214 | } | |
215 | /* Entering a new scope. Try to see if we can find a VR | |
216 | here. */ | |
217 | tree op1 = gimple_cond_rhs (stmt); | |
218 | if (TREE_OVERFLOW_P (op1)) | |
219 | op1 = drop_tree_overflow (op1); | |
220 | tree_code code = gimple_cond_code (stmt); | |
221 | ||
222 | auto_vec<assert_info, 8> asserts; | |
223 | register_edge_assert_for (op0, pred_e, code, op0, op1, asserts); | |
224 | if (TREE_CODE (op1) == SSA_NAME) | |
225 | register_edge_assert_for (op1, pred_e, code, op0, op1, asserts); | |
226 | ||
227 | auto_vec<std::pair<tree, value_range *>, 8> vrs; | |
228 | for (unsigned i = 0; i < asserts.length (); ++i) | |
229 | { | |
230 | value_range *vr = try_find_new_range (asserts[i].name, | |
231 | asserts[i].expr, | |
232 | asserts[i].comp_code, | |
233 | asserts[i].val); | |
234 | if (vr) | |
235 | vrs.safe_push (std::make_pair (asserts[i].name, vr)); | |
236 | } | |
237 | /* Push updated ranges only after finding all of them to avoid | |
238 | ordering issues that can lead to worse ranges. */ | |
239 | for (unsigned i = 0; i < vrs.length (); ++i) | |
240 | push_value_range (vrs[i].first, vrs[i].second); | |
241 | } | |
242 | } | |
5c56ab3e | 243 | } |
244 | ||
5c56ab3e | 245 | void |
71ddacbb | 246 | evrp_range_analyzer::record_ranges_from_phis (basic_block bb) |
5c56ab3e | 247 | { |
9c015ccf | 248 | /* Visit PHI stmts and discover any new VRs possible. */ |
249 | bool has_unvisited_preds = false; | |
250 | edge_iterator ei; | |
251 | edge e; | |
252 | FOR_EACH_EDGE (e, ei, bb->preds) | |
253 | if (e->flags & EDGE_EXECUTABLE | |
254 | && !(e->src->flags & BB_VISITED)) | |
255 | { | |
256 | has_unvisited_preds = true; | |
257 | break; | |
258 | } | |
259 | ||
260 | for (gphi_iterator gpi = gsi_start_phis (bb); | |
261 | !gsi_end_p (gpi); gsi_next (&gpi)) | |
262 | { | |
263 | gphi *phi = gpi.phi (); | |
264 | tree lhs = PHI_RESULT (phi); | |
265 | if (virtual_operand_p (lhs)) | |
266 | continue; | |
71ddacbb | 267 | |
9c015ccf | 268 | value_range vr_result = VR_INITIALIZER; |
269 | bool interesting = stmt_interesting_for_vrp (phi); | |
71ddacbb | 270 | if (!has_unvisited_preds && interesting) |
9c015ccf | 271 | extract_range_from_phi_node (phi, &vr_result); |
272 | else | |
273 | { | |
274 | set_value_range_to_varying (&vr_result); | |
275 | /* When we have an unvisited executable predecessor we can't | |
276 | use PHI arg ranges which may be still UNDEFINED but have | |
277 | to use VARYING for them. But we can still resort to | |
278 | SCEV for loop header PHIs. */ | |
279 | struct loop *l; | |
280 | if (interesting | |
281 | && (l = loop_containing_stmt (phi)) | |
282 | && l->header == gimple_bb (phi)) | |
71ddacbb | 283 | adjust_range_with_scev (&vr_result, l, phi, lhs); |
9c015ccf | 284 | } |
285 | update_value_range (lhs, &vr_result); | |
286 | ||
9c015ccf | 287 | /* Set the SSA with the value range. */ |
288 | if (INTEGRAL_TYPE_P (TREE_TYPE (lhs))) | |
289 | { | |
290 | if ((vr_result.type == VR_RANGE | |
291 | || vr_result.type == VR_ANTI_RANGE) | |
292 | && (TREE_CODE (vr_result.min) == INTEGER_CST) | |
293 | && (TREE_CODE (vr_result.max) == INTEGER_CST)) | |
294 | set_range_info (lhs, vr_result.type, | |
295 | wi::to_wide (vr_result.min), | |
296 | wi::to_wide (vr_result.max)); | |
297 | } | |
298 | else if (POINTER_TYPE_P (TREE_TYPE (lhs)) | |
299 | && ((vr_result.type == VR_RANGE | |
300 | && range_includes_zero_p (vr_result.min, | |
301 | vr_result.max) == 0) | |
302 | || (vr_result.type == VR_ANTI_RANGE | |
303 | && range_includes_zero_p (vr_result.min, | |
304 | vr_result.max) == 1))) | |
305 | set_ptr_nonnull (lhs); | |
306 | } | |
5c56ab3e | 307 | } |
308 | ||
309 | /* Record any ranges created by statement STMT. */ | |
310 | ||
311 | void | |
71ddacbb | 312 | evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt) |
5c56ab3e | 313 | { |
314 | tree output = NULL_TREE; | |
315 | ||
316 | if (dyn_cast <gcond *> (stmt)) | |
317 | ; | |
318 | else if (stmt_interesting_for_vrp (stmt)) | |
319 | { | |
320 | edge taken_edge; | |
321 | value_range vr = VR_INITIALIZER; | |
322 | extract_range_from_stmt (stmt, &taken_edge, &output, &vr); | |
323 | if (output && (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)) | |
324 | { | |
325 | update_value_range (output, &vr); | |
326 | ||
327 | /* Set the SSA with the value range. */ | |
328 | if (INTEGRAL_TYPE_P (TREE_TYPE (output))) | |
329 | { | |
330 | if ((vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE) | |
71ddacbb | 331 | && (TREE_CODE (vr.min) == INTEGER_CST) |
332 | && (TREE_CODE (vr.max) == INTEGER_CST)) | |
5c56ab3e | 333 | set_range_info (output, vr.type, |
334 | wi::to_wide (vr.min), | |
335 | wi::to_wide (vr.max)); | |
336 | } | |
337 | else if (POINTER_TYPE_P (TREE_TYPE (output)) | |
338 | && ((vr.type == VR_RANGE | |
339 | && range_includes_zero_p (vr.min, vr.max) == 0) | |
340 | || (vr.type == VR_ANTI_RANGE | |
341 | && range_includes_zero_p (vr.min, vr.max) == 1))) | |
342 | set_ptr_nonnull (output); | |
343 | } | |
344 | else | |
345 | set_defs_to_varying (stmt); | |
346 | } | |
347 | else | |
348 | set_defs_to_varying (stmt); | |
349 | ||
350 | /* See if we can derive a range for any of STMT's operands. */ | |
351 | tree op; | |
352 | ssa_op_iter i; | |
353 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE) | |
354 | { | |
355 | tree value; | |
356 | enum tree_code comp_code; | |
357 | ||
358 | /* If OP is used in such a way that we can infer a value | |
359 | range for it, and we don't find a previous assertion for | |
360 | it, create a new assertion location node for OP. */ | |
361 | if (infer_value_range (stmt, op, &comp_code, &value)) | |
362 | { | |
363 | /* If we are able to infer a nonzero value range for OP, | |
364 | then walk backwards through the use-def chain to see if OP | |
365 | was set via a typecast. | |
366 | If so, then we can also infer a nonzero value range | |
367 | for the operand of the NOP_EXPR. */ | |
368 | if (comp_code == NE_EXPR && integer_zerop (value)) | |
369 | { | |
370 | tree t = op; | |
371 | gimple *def_stmt = SSA_NAME_DEF_STMT (t); | |
372 | while (is_gimple_assign (def_stmt) | |
373 | && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)) | |
374 | && TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME | |
375 | && POINTER_TYPE_P | |
376 | (TREE_TYPE (gimple_assign_rhs1 (def_stmt)))) | |
377 | { | |
378 | t = gimple_assign_rhs1 (def_stmt); | |
379 | def_stmt = SSA_NAME_DEF_STMT (t); | |
380 | ||
381 | /* Add VR when (T COMP_CODE value) condition is 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 | ||
397 | edge | |
398 | evrp_dom_walker::before_dom_children (basic_block bb) | |
399 | { | |
400 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
401 | fprintf (dump_file, "Visiting BB%d\n", bb->index); | |
402 | ||
71ddacbb | 403 | evrp_range_analyzer.enter (bb); |
5c56ab3e | 404 | |
405 | for (gphi_iterator gpi = gsi_start_phis (bb); | |
406 | !gsi_end_p (gpi); gsi_next (&gpi)) | |
407 | { | |
408 | gphi *phi = gpi.phi (); | |
409 | tree lhs = PHI_RESULT (phi); | |
410 | if (virtual_operand_p (lhs)) | |
411 | continue; | |
412 | ||
413 | /* Mark PHIs whose lhs we fully propagate for removal. */ | |
414 | tree val = op_with_constant_singleton_value_range (lhs); | |
415 | if (val && may_propagate_copy (lhs, val)) | |
416 | { | |
417 | stmts_to_remove.safe_push (phi); | |
418 | continue; | |
419 | } | |
420 | } | |
9c015ccf | 421 | |
422 | edge taken_edge = NULL; | |
423 | ||
424 | /* Visit all other stmts and discover any new VRs possible. */ | |
425 | for (gimple_stmt_iterator gsi = gsi_start_bb (bb); | |
426 | !gsi_end_p (gsi); gsi_next (&gsi)) | |
427 | { | |
428 | gimple *stmt = gsi_stmt (gsi); | |
429 | tree output = NULL_TREE; | |
430 | gimple *old_stmt = stmt; | |
431 | bool was_noreturn = (is_gimple_call (stmt) | |
432 | && gimple_call_noreturn_p (stmt)); | |
433 | ||
434 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
435 | { | |
436 | fprintf (dump_file, "Visiting stmt "); | |
437 | print_gimple_stmt (dump_file, stmt, 0); | |
438 | } | |
439 | ||
71ddacbb | 440 | evrp_range_analyzer.record_ranges_from_stmt (stmt); |
441 | ||
9c015ccf | 442 | if (gcond *cond = dyn_cast <gcond *> (stmt)) |
443 | { | |
444 | vrp_visit_cond_stmt (cond, &taken_edge); | |
445 | if (taken_edge) | |
446 | { | |
447 | if (taken_edge->flags & EDGE_TRUE_VALUE) | |
448 | gimple_cond_make_true (cond); | |
449 | else if (taken_edge->flags & EDGE_FALSE_VALUE) | |
450 | gimple_cond_make_false (cond); | |
451 | else | |
452 | gcc_unreachable (); | |
453 | update_stmt (stmt); | |
454 | } | |
455 | } | |
456 | else if (stmt_interesting_for_vrp (stmt)) | |
457 | { | |
9c015ccf | 458 | value_range vr = VR_INITIALIZER; |
5c56ab3e | 459 | output = get_output_for_vrp (stmt); |
460 | if (output) | |
9c015ccf | 461 | { |
71ddacbb | 462 | tree val; |
9c015ccf | 463 | vr = *get_value_range (output); |
464 | ||
465 | /* Mark stmts whose output we fully propagate for removal. */ | |
5c56ab3e | 466 | if ((vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE) |
467 | && (val = op_with_constant_singleton_value_range (output)) | |
9c015ccf | 468 | && may_propagate_copy (output, val) |
469 | && !stmt_could_throw_p (stmt) | |
470 | && !gimple_has_side_effects (stmt)) | |
471 | { | |
472 | stmts_to_remove.safe_push (stmt); | |
473 | continue; | |
474 | } | |
9c015ccf | 475 | } |
476 | } | |
477 | ||
478 | /* Try folding stmts with the VR discovered. */ | |
479 | class evrp_folder evrp_folder; | |
71ddacbb | 480 | evrp_folder.vr_values = &evrp_range_analyzer.vr_values; |
9c015ccf | 481 | bool did_replace = evrp_folder.replace_uses_in (stmt); |
482 | if (fold_stmt (&gsi, follow_single_use_edges) | |
483 | || did_replace) | |
484 | { | |
485 | stmt = gsi_stmt (gsi); | |
486 | update_stmt (stmt); | |
487 | did_replace = true; | |
488 | } | |
489 | ||
490 | if (did_replace) | |
491 | { | |
492 | /* If we cleaned up EH information from the statement, | |
493 | remove EH edges. */ | |
494 | if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)) | |
495 | bitmap_set_bit (need_eh_cleanup, bb->index); | |
496 | ||
497 | /* If we turned a not noreturn call into a noreturn one | |
498 | schedule it for fixup. */ | |
499 | if (!was_noreturn | |
500 | && is_gimple_call (stmt) | |
501 | && gimple_call_noreturn_p (stmt)) | |
502 | stmts_to_fixup.safe_push (stmt); | |
503 | ||
504 | if (gimple_assign_single_p (stmt)) | |
505 | { | |
506 | tree rhs = gimple_assign_rhs1 (stmt); | |
507 | if (TREE_CODE (rhs) == ADDR_EXPR) | |
508 | recompute_tree_invariant_for_addr_expr (rhs); | |
509 | } | |
510 | } | |
511 | } | |
512 | ||
513 | /* Visit BB successor PHI nodes and replace PHI args. */ | |
5c56ab3e | 514 | edge e; |
515 | edge_iterator ei; | |
9c015ccf | 516 | FOR_EACH_EDGE (e, ei, bb->succs) |
517 | { | |
518 | for (gphi_iterator gpi = gsi_start_phis (e->dest); | |
519 | !gsi_end_p (gpi); gsi_next (&gpi)) | |
520 | { | |
521 | gphi *phi = gpi.phi (); | |
522 | use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e); | |
523 | tree arg = USE_FROM_PTR (use_p); | |
524 | if (TREE_CODE (arg) != SSA_NAME | |
525 | || virtual_operand_p (arg)) | |
526 | continue; | |
527 | tree val = op_with_constant_singleton_value_range (arg); | |
528 | if (val && may_propagate_copy (arg, val)) | |
529 | propagate_value (use_p, val); | |
530 | } | |
531 | } | |
532 | ||
533 | bb->flags |= BB_VISITED; | |
534 | ||
535 | return taken_edge; | |
536 | } | |
537 | ||
71ddacbb | 538 | void |
539 | evrp_dom_walker::after_dom_children (basic_block bb) | |
540 | { | |
541 | evrp_range_analyzer.leave (bb); | |
542 | } | |
543 | ||
9c015ccf | 544 | /* Restore/pop VRs valid only for BB when we leave BB. */ |
545 | ||
546 | void | |
71ddacbb | 547 | evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED) |
9c015ccf | 548 | { |
549 | gcc_checking_assert (!stack.is_empty ()); | |
550 | while (stack.last ().first != NULL_TREE) | |
551 | pop_value_range (stack.last ().first); | |
552 | stack.pop (); | |
553 | } | |
554 | ||
555 | /* Push the Value Range of VAR to the stack and update it with new VR. */ | |
556 | ||
557 | void | |
71ddacbb | 558 | evrp_range_analyzer::push_value_range (tree var, value_range *vr) |
9c015ccf | 559 | { |
560 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
561 | { | |
562 | fprintf (dump_file, "pushing new range for "); | |
563 | print_generic_expr (dump_file, var); | |
564 | fprintf (dump_file, ": "); | |
565 | dump_value_range (dump_file, vr); | |
566 | fprintf (dump_file, "\n"); | |
567 | } | |
568 | stack.safe_push (std::make_pair (var, get_value_range (var))); | |
569 | set_vr_value (var, vr); | |
570 | } | |
571 | ||
572 | /* Pop the Value Range from the vrp_stack and update VAR with it. */ | |
573 | ||
574 | value_range * | |
71ddacbb | 575 | evrp_range_analyzer::pop_value_range (tree var) |
9c015ccf | 576 | { |
577 | value_range *vr = stack.last ().second; | |
578 | gcc_checking_assert (var == stack.last ().first); | |
579 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
580 | { | |
581 | fprintf (dump_file, "popping range for "); | |
582 | print_generic_expr (dump_file, var); | |
583 | fprintf (dump_file, ", restoring "); | |
584 | dump_value_range (dump_file, vr); | |
585 | fprintf (dump_file, "\n"); | |
586 | } | |
587 | set_vr_value (var, vr); | |
588 | stack.pop (); | |
589 | return vr; | |
590 | } | |
591 | ||
a62a30a4 | 592 | /* Perform any cleanups after the main phase of EVRP has completed. */ |
9c015ccf | 593 | |
a62a30a4 | 594 | void |
595 | evrp_dom_walker::cleanup (void) | |
9c015ccf | 596 | { |
9c015ccf | 597 | if (dump_file) |
598 | { | |
599 | fprintf (dump_file, "\nValue ranges after Early VRP:\n\n"); | |
71ddacbb | 600 | evrp_range_analyzer.vr_values.dump_all_value_ranges (dump_file); |
9c015ccf | 601 | fprintf (dump_file, "\n"); |
602 | } | |
603 | ||
604 | /* Remove stmts in reverse order to make debug stmt creation possible. */ | |
a62a30a4 | 605 | while (! stmts_to_remove.is_empty ()) |
9c015ccf | 606 | { |
a62a30a4 | 607 | gimple *stmt = stmts_to_remove.pop (); |
9c015ccf | 608 | if (dump_file && dump_flags & TDF_DETAILS) |
609 | { | |
610 | fprintf (dump_file, "Removing dead stmt "); | |
611 | print_gimple_stmt (dump_file, stmt, 0); | |
612 | fprintf (dump_file, "\n"); | |
613 | } | |
614 | gimple_stmt_iterator gsi = gsi_for_stmt (stmt); | |
615 | if (gimple_code (stmt) == GIMPLE_PHI) | |
616 | remove_phi_node (&gsi, true); | |
617 | else | |
618 | { | |
619 | unlink_stmt_vdef (stmt); | |
620 | gsi_remove (&gsi, true); | |
621 | release_defs (stmt); | |
622 | } | |
623 | } | |
624 | ||
a62a30a4 | 625 | if (!bitmap_empty_p (need_eh_cleanup)) |
626 | gimple_purge_all_dead_eh_edges (need_eh_cleanup); | |
9c015ccf | 627 | |
628 | /* Fixup stmts that became noreturn calls. This may require splitting | |
629 | blocks and thus isn't possible during the dominator walk. Do this | |
630 | in reverse order so we don't inadvertedly remove a stmt we want to | |
631 | fixup by visiting a dominating now noreturn call first. */ | |
a62a30a4 | 632 | while (!stmts_to_fixup.is_empty ()) |
9c015ccf | 633 | { |
a62a30a4 | 634 | gimple *stmt = stmts_to_fixup.pop (); |
9c015ccf | 635 | fixup_noreturn_call (stmt); |
636 | } | |
a62a30a4 | 637 | } |
638 | ||
639 | /* Main entry point for the early vrp pass which is a simplified non-iterative | |
640 | version of vrp where basic blocks are visited in dominance order. Value | |
641 | ranges discovered in early vrp will also be used by ipa-vrp. */ | |
642 | ||
643 | static unsigned int | |
644 | execute_early_vrp () | |
645 | { | |
a62a30a4 | 646 | /* Ideally this setup code would move into the ctor for the dominator |
647 | walk. However, this setup can change the number of blocks which | |
648 | invalidates the internal arrays that are set up by the dominator | |
649 | walker. */ | |
650 | loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS); | |
651 | rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); | |
652 | scev_initialize (); | |
653 | calculate_dominance_info (CDI_DOMINATORS); | |
a62a30a4 | 654 | |
655 | /* Walk stmts in dominance order and propagate VRP. */ | |
656 | evrp_dom_walker walker; | |
657 | walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); | |
658 | walker.cleanup (); | |
9c015ccf | 659 | |
660 | scev_finalize (); | |
661 | loop_optimizer_finalize (); | |
662 | return 0; | |
663 | } | |
664 | ||
665 | namespace { | |
666 | ||
667 | const pass_data pass_data_early_vrp = | |
668 | { | |
669 | GIMPLE_PASS, /* type */ | |
670 | "evrp", /* name */ | |
671 | OPTGROUP_NONE, /* optinfo_flags */ | |
672 | TV_TREE_EARLY_VRP, /* tv_id */ | |
673 | PROP_ssa, /* properties_required */ | |
674 | 0, /* properties_provided */ | |
675 | 0, /* properties_destroyed */ | |
676 | 0, /* todo_flags_start */ | |
677 | ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ), | |
678 | }; | |
679 | ||
680 | class pass_early_vrp : public gimple_opt_pass | |
681 | { | |
682 | public: | |
683 | pass_early_vrp (gcc::context *ctxt) | |
684 | : gimple_opt_pass (pass_data_early_vrp, ctxt) | |
685 | {} | |
686 | ||
687 | /* opt_pass methods: */ | |
688 | opt_pass * clone () { return new pass_early_vrp (m_ctxt); } | |
689 | virtual bool gate (function *) | |
690 | { | |
691 | return flag_tree_vrp != 0; | |
692 | } | |
693 | virtual unsigned int execute (function *) | |
694 | { return execute_early_vrp (); } | |
695 | ||
696 | }; // class pass_vrp | |
697 | } // anon namespace | |
698 | ||
699 | gimple_opt_pass * | |
700 | make_pass_early_vrp (gcc::context *ctxt) | |
701 | { | |
702 | return new pass_early_vrp (ctxt); | |
703 | } | |
704 |