1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005-2017 Free Software Foundation, Inc.
4 This file is part of GCC.
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)
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.
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/>. */
22 #include "coretypes.h"
26 #include "tree-pass.h"
28 #include "gimple-pretty-print.h"
30 #include "gimple-fold.h"
32 #include "gimple-iterator.h"
34 #include "tree-ssa-loop-manip.h"
35 #include "tree-ssa-loop.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-ssa-propagate.h"
39 #include "alloc-pool.h"
41 #include "tree-cfgcleanup.h"
42 #include "vr-values.h"
44 class evrp_folder
: public substitute_and_fold_engine
47 tree
get_value (tree
) FINAL OVERRIDE
;
49 class vr_values
*vr_values
;
53 evrp_folder::get_value (tree op
)
55 return vr_values
->op_with_constant_singleton_value_range (op
);
58 /* evrp_dom_walker visits the basic blocks in the dominance order and set
59 the Value Ranges (VR) for SSA_NAMEs in the scope. Use this VR to
62 class evrp_dom_walker
: public dom_walker
66 : dom_walker (CDI_DOMINATORS
), stack (10)
68 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
72 BITMAP_FREE (need_eh_cleanup
);
74 virtual edge
before_dom_children (basic_block
);
75 virtual void after_dom_children (basic_block
);
76 void push_value_range (tree var
, value_range
*vr
);
77 value_range
*pop_value_range (tree var
);
78 value_range
*try_find_new_range (tree
, tree op
, tree_code code
, tree limit
);
80 /* Cond_stack holds the old VR. */
81 auto_vec
<std::pair
<tree
, value_range
*> > stack
;
82 bitmap need_eh_cleanup
;
83 auto_vec
<gimple
*> stmts_to_fixup
;
84 auto_vec
<gimple
*> stmts_to_remove
;
86 class vr_values vr_values
;
88 /* Temporary delegators. */
89 value_range
*get_value_range (const_tree op
)
90 { return vr_values
.get_value_range (op
); }
91 bool update_value_range (const_tree op
, value_range
*vr
)
92 { return vr_values
.update_value_range (op
, vr
); }
93 void extract_range_from_phi_node (gphi
*phi
, value_range
*vr
)
94 { vr_values
.extract_range_from_phi_node (phi
, vr
); }
95 void extract_range_for_var_from_comparison_expr (tree var
,
96 enum tree_code cond_code
,
99 { vr_values
.extract_range_for_var_from_comparison_expr (var
, cond_code
,
101 void adjust_range_with_scev (value_range
*vr
, struct loop
*loop
,
102 gimple
*stmt
, tree var
)
103 { vr_values
.adjust_range_with_scev (vr
, loop
, stmt
, var
); }
104 tree
op_with_constant_singleton_value_range (tree op
)
105 { return vr_values
.op_with_constant_singleton_value_range (op
); }
106 void extract_range_from_stmt (gimple
*stmt
, edge
*taken_edge_p
,
107 tree
*output_p
, value_range
*vr
)
108 { vr_values
.extract_range_from_stmt (stmt
, taken_edge_p
, output_p
, vr
); }
109 void set_defs_to_varying (gimple
*stmt
)
110 { return vr_values
.set_defs_to_varying (stmt
); }
111 void set_vr_value (tree name
, value_range
*vr
)
112 { vr_values
.set_vr_value (name
, vr
); }
113 void simplify_cond_using_ranges_2 (gcond
*stmt
)
114 { vr_values
.simplify_cond_using_ranges_2 (stmt
); }
115 void vrp_visit_cond_stmt (gcond
*cond
, edge
*e
)
116 { vr_values
.vrp_visit_cond_stmt (cond
, e
); }
119 /* Find new range for NAME such that (OP CODE LIMIT) is true. */
122 evrp_dom_walker::try_find_new_range (tree name
,
123 tree op
, tree_code code
, tree limit
)
125 value_range vr
= VR_INITIALIZER
;
126 value_range
*old_vr
= get_value_range (name
);
128 /* Discover VR when condition is true. */
129 extract_range_for_var_from_comparison_expr (name
, code
, op
,
131 /* If we found any usable VR, set the VR to ssa_name and create a
132 PUSH old value in the stack with the old VR. */
133 if (vr
.type
== VR_RANGE
|| vr
.type
== VR_ANTI_RANGE
)
135 if (old_vr
->type
== vr
.type
136 && vrp_operand_equal_p (old_vr
->min
, vr
.min
)
137 && vrp_operand_equal_p (old_vr
->max
, vr
.max
))
139 value_range
*new_vr
= vr_values
.vrp_value_range_pool
.allocate ();
146 /* See if there is any new scope is entered with new VR and set that VR to
147 ssa_name before visiting the statements in the scope. */
150 evrp_dom_walker::before_dom_children (basic_block bb
)
152 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
153 fprintf (dump_file
, "Visiting BB%d\n", bb
->index
);
155 stack
.safe_push (std::make_pair (NULL_TREE
, (value_range
*)NULL
));
157 edge pred_e
= single_pred_edge_ignoring_loop_edges (bb
, false);
160 gimple
*stmt
= last_stmt (pred_e
->src
);
161 tree op0
= NULL_TREE
;
164 && gimple_code (stmt
) == GIMPLE_COND
165 && (op0
= gimple_cond_lhs (stmt
))
166 && TREE_CODE (op0
) == SSA_NAME
167 && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt
)))
168 || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt
)))))
170 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
172 fprintf (dump_file
, "Visiting controlling predicate ");
173 print_gimple_stmt (dump_file
, stmt
, 0);
175 /* Entering a new scope. Try to see if we can find a VR
177 tree op1
= gimple_cond_rhs (stmt
);
178 if (TREE_OVERFLOW_P (op1
))
179 op1
= drop_tree_overflow (op1
);
180 tree_code code
= gimple_cond_code (stmt
);
182 auto_vec
<assert_info
, 8> asserts
;
183 register_edge_assert_for (op0
, pred_e
, code
, op0
, op1
, asserts
);
184 if (TREE_CODE (op1
) == SSA_NAME
)
185 register_edge_assert_for (op1
, pred_e
, code
, op0
, op1
, asserts
);
187 auto_vec
<std::pair
<tree
, value_range
*>, 8> vrs
;
188 for (unsigned i
= 0; i
< asserts
.length (); ++i
)
190 value_range
*vr
= try_find_new_range (asserts
[i
].name
,
192 asserts
[i
].comp_code
,
195 vrs
.safe_push (std::make_pair (asserts
[i
].name
, vr
));
197 /* Push updated ranges only after finding all of them to avoid
198 ordering issues that can lead to worse ranges. */
199 for (unsigned i
= 0; i
< vrs
.length (); ++i
)
200 push_value_range (vrs
[i
].first
, vrs
[i
].second
);
204 /* Visit PHI stmts and discover any new VRs possible. */
205 bool has_unvisited_preds
= false;
208 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
209 if (e
->flags
& EDGE_EXECUTABLE
210 && !(e
->src
->flags
& BB_VISITED
))
212 has_unvisited_preds
= true;
216 for (gphi_iterator gpi
= gsi_start_phis (bb
);
217 !gsi_end_p (gpi
); gsi_next (&gpi
))
219 gphi
*phi
= gpi
.phi ();
220 tree lhs
= PHI_RESULT (phi
);
221 if (virtual_operand_p (lhs
))
223 value_range vr_result
= VR_INITIALIZER
;
224 bool interesting
= stmt_interesting_for_vrp (phi
);
225 if (interesting
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
227 fprintf (dump_file
, "Visiting PHI node ");
228 print_gimple_stmt (dump_file
, phi
, 0);
230 if (!has_unvisited_preds
232 extract_range_from_phi_node (phi
, &vr_result
);
235 set_value_range_to_varying (&vr_result
);
236 /* When we have an unvisited executable predecessor we can't
237 use PHI arg ranges which may be still UNDEFINED but have
238 to use VARYING for them. But we can still resort to
239 SCEV for loop header PHIs. */
242 && (l
= loop_containing_stmt (phi
))
243 && l
->header
== gimple_bb (phi
))
244 adjust_range_with_scev (&vr_result
, l
, phi
, lhs
);
246 update_value_range (lhs
, &vr_result
);
248 /* Mark PHIs whose lhs we fully propagate for removal. */
249 tree val
= op_with_constant_singleton_value_range (lhs
);
250 if (val
&& may_propagate_copy (lhs
, val
))
252 stmts_to_remove
.safe_push (phi
);
256 /* Set the SSA with the value range. */
257 if (INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
259 if ((vr_result
.type
== VR_RANGE
260 || vr_result
.type
== VR_ANTI_RANGE
)
261 && (TREE_CODE (vr_result
.min
) == INTEGER_CST
)
262 && (TREE_CODE (vr_result
.max
) == INTEGER_CST
))
263 set_range_info (lhs
, vr_result
.type
,
264 wi::to_wide (vr_result
.min
),
265 wi::to_wide (vr_result
.max
));
267 else if (POINTER_TYPE_P (TREE_TYPE (lhs
))
268 && ((vr_result
.type
== VR_RANGE
269 && range_includes_zero_p (vr_result
.min
,
271 || (vr_result
.type
== VR_ANTI_RANGE
272 && range_includes_zero_p (vr_result
.min
,
273 vr_result
.max
) == 1)))
274 set_ptr_nonnull (lhs
);
277 edge taken_edge
= NULL
;
279 /* Visit all other stmts and discover any new VRs possible. */
280 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
281 !gsi_end_p (gsi
); gsi_next (&gsi
))
283 gimple
*stmt
= gsi_stmt (gsi
);
284 tree output
= NULL_TREE
;
285 gimple
*old_stmt
= stmt
;
286 bool was_noreturn
= (is_gimple_call (stmt
)
287 && gimple_call_noreturn_p (stmt
));
289 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
291 fprintf (dump_file
, "Visiting stmt ");
292 print_gimple_stmt (dump_file
, stmt
, 0);
295 if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
297 vrp_visit_cond_stmt (cond
, &taken_edge
);
300 if (taken_edge
->flags
& EDGE_TRUE_VALUE
)
301 gimple_cond_make_true (cond
);
302 else if (taken_edge
->flags
& EDGE_FALSE_VALUE
)
303 gimple_cond_make_false (cond
);
309 else if (stmt_interesting_for_vrp (stmt
))
312 value_range vr
= VR_INITIALIZER
;
313 extract_range_from_stmt (stmt
, &taken_edge
, &output
, &vr
);
315 && (vr
.type
== VR_RANGE
|| vr
.type
== VR_ANTI_RANGE
))
317 update_value_range (output
, &vr
);
318 vr
= *get_value_range (output
);
320 /* Mark stmts whose output we fully propagate for removal. */
322 if ((val
= op_with_constant_singleton_value_range (output
))
323 && may_propagate_copy (output
, val
)
324 && !stmt_could_throw_p (stmt
)
325 && !gimple_has_side_effects (stmt
))
327 stmts_to_remove
.safe_push (stmt
);
331 /* Set the SSA with the value range. */
332 if (INTEGRAL_TYPE_P (TREE_TYPE (output
)))
334 if ((vr
.type
== VR_RANGE
335 || vr
.type
== VR_ANTI_RANGE
)
336 && (TREE_CODE (vr
.min
) == INTEGER_CST
)
337 && (TREE_CODE (vr
.max
) == INTEGER_CST
))
338 set_range_info (output
, vr
.type
,
339 wi::to_wide (vr
.min
),
340 wi::to_wide (vr
.max
));
342 else if (POINTER_TYPE_P (TREE_TYPE (output
))
343 && ((vr
.type
== VR_RANGE
344 && range_includes_zero_p (vr
.min
,
346 || (vr
.type
== VR_ANTI_RANGE
347 && range_includes_zero_p (vr
.min
,
349 set_ptr_nonnull (output
);
352 set_defs_to_varying (stmt
);
355 set_defs_to_varying (stmt
);
357 /* See if we can derive a range for any of STMT's operands. */
360 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_USE
)
363 enum tree_code comp_code
;
365 /* If OP is used in such a way that we can infer a value
366 range for it, and we don't find a previous assertion for
367 it, create a new assertion location node for OP. */
368 if (infer_value_range (stmt
, op
, &comp_code
, &value
))
370 /* If we are able to infer a nonzero value range for OP,
371 then walk backwards through the use-def chain to see if OP
372 was set via a typecast.
373 If so, then we can also infer a nonzero value range
374 for the operand of the NOP_EXPR. */
375 if (comp_code
== NE_EXPR
&& integer_zerop (value
))
378 gimple
*def_stmt
= SSA_NAME_DEF_STMT (t
);
379 while (is_gimple_assign (def_stmt
)
380 && CONVERT_EXPR_CODE_P
381 (gimple_assign_rhs_code (def_stmt
))
383 (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
385 (TREE_TYPE (gimple_assign_rhs1 (def_stmt
))))
387 t
= gimple_assign_rhs1 (def_stmt
);
388 def_stmt
= SSA_NAME_DEF_STMT (t
);
390 /* Add VR when (T COMP_CODE value) condition is
392 value_range
*op_range
393 = try_find_new_range (t
, t
, comp_code
, value
);
395 push_value_range (t
, op_range
);
398 /* Add VR when (OP COMP_CODE value) condition is true. */
399 value_range
*op_range
= try_find_new_range (op
, op
,
402 push_value_range (op
, op_range
);
406 /* Try folding stmts with the VR discovered. */
407 class evrp_folder evrp_folder
;
408 evrp_folder
.vr_values
= &vr_values
;
409 bool did_replace
= evrp_folder
.replace_uses_in (stmt
);
410 if (fold_stmt (&gsi
, follow_single_use_edges
)
413 stmt
= gsi_stmt (gsi
);
420 /* If we cleaned up EH information from the statement,
422 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
423 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
425 /* If we turned a not noreturn call into a noreturn one
426 schedule it for fixup. */
428 && is_gimple_call (stmt
)
429 && gimple_call_noreturn_p (stmt
))
430 stmts_to_fixup
.safe_push (stmt
);
432 if (gimple_assign_single_p (stmt
))
434 tree rhs
= gimple_assign_rhs1 (stmt
);
435 if (TREE_CODE (rhs
) == ADDR_EXPR
)
436 recompute_tree_invariant_for_addr_expr (rhs
);
441 /* Visit BB successor PHI nodes and replace PHI args. */
442 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
444 for (gphi_iterator gpi
= gsi_start_phis (e
->dest
);
445 !gsi_end_p (gpi
); gsi_next (&gpi
))
447 gphi
*phi
= gpi
.phi ();
448 use_operand_p use_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
449 tree arg
= USE_FROM_PTR (use_p
);
450 if (TREE_CODE (arg
) != SSA_NAME
451 || virtual_operand_p (arg
))
453 tree val
= op_with_constant_singleton_value_range (arg
);
454 if (val
&& may_propagate_copy (arg
, val
))
455 propagate_value (use_p
, val
);
459 bb
->flags
|= BB_VISITED
;
464 /* Restore/pop VRs valid only for BB when we leave BB. */
467 evrp_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED
)
469 gcc_checking_assert (!stack
.is_empty ());
470 while (stack
.last ().first
!= NULL_TREE
)
471 pop_value_range (stack
.last ().first
);
475 /* Push the Value Range of VAR to the stack and update it with new VR. */
478 evrp_dom_walker::push_value_range (tree var
, value_range
*vr
)
480 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
482 fprintf (dump_file
, "pushing new range for ");
483 print_generic_expr (dump_file
, var
);
484 fprintf (dump_file
, ": ");
485 dump_value_range (dump_file
, vr
);
486 fprintf (dump_file
, "\n");
488 stack
.safe_push (std::make_pair (var
, get_value_range (var
)));
489 set_vr_value (var
, vr
);
492 /* Pop the Value Range from the vrp_stack and update VAR with it. */
495 evrp_dom_walker::pop_value_range (tree var
)
497 value_range
*vr
= stack
.last ().second
;
498 gcc_checking_assert (var
== stack
.last ().first
);
499 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
501 fprintf (dump_file
, "popping range for ");
502 print_generic_expr (dump_file
, var
);
503 fprintf (dump_file
, ", restoring ");
504 dump_value_range (dump_file
, vr
);
505 fprintf (dump_file
, "\n");
507 set_vr_value (var
, vr
);
513 /* Main entry point for the early vrp pass which is a simplified non-iterative
514 version of vrp where basic blocks are visited in dominance order. Value
515 ranges discovered in early vrp will also be used by ipa-vrp. */
524 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
525 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
527 calculate_dominance_info (CDI_DOMINATORS
);
528 FOR_EACH_BB_FN (bb
, cfun
)
530 bb
->flags
&= ~BB_VISITED
;
531 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
532 e
->flags
|= EDGE_EXECUTABLE
;
535 /* Walk stmts in dominance order and propagate VRP. */
536 evrp_dom_walker walker
;
537 walker
.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
541 fprintf (dump_file
, "\nValue ranges after Early VRP:\n\n");
542 walker
.vr_values
.dump_all_value_ranges (dump_file
);
543 fprintf (dump_file
, "\n");
546 /* Remove stmts in reverse order to make debug stmt creation possible. */
547 while (! walker
.stmts_to_remove
.is_empty ())
549 gimple
*stmt
= walker
.stmts_to_remove
.pop ();
550 if (dump_file
&& dump_flags
& TDF_DETAILS
)
552 fprintf (dump_file
, "Removing dead stmt ");
553 print_gimple_stmt (dump_file
, stmt
, 0);
554 fprintf (dump_file
, "\n");
556 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
557 if (gimple_code (stmt
) == GIMPLE_PHI
)
558 remove_phi_node (&gsi
, true);
561 unlink_stmt_vdef (stmt
);
562 gsi_remove (&gsi
, true);
567 if (!bitmap_empty_p (walker
.need_eh_cleanup
))
568 gimple_purge_all_dead_eh_edges (walker
.need_eh_cleanup
);
570 /* Fixup stmts that became noreturn calls. This may require splitting
571 blocks and thus isn't possible during the dominator walk. Do this
572 in reverse order so we don't inadvertedly remove a stmt we want to
573 fixup by visiting a dominating now noreturn call first. */
574 while (!walker
.stmts_to_fixup
.is_empty ())
576 gimple
*stmt
= walker
.stmts_to_fixup
.pop ();
577 fixup_noreturn_call (stmt
);
581 loop_optimizer_finalize ();
587 const pass_data pass_data_early_vrp
=
589 GIMPLE_PASS
, /* type */
591 OPTGROUP_NONE
, /* optinfo_flags */
592 TV_TREE_EARLY_VRP
, /* tv_id */
593 PROP_ssa
, /* properties_required */
594 0, /* properties_provided */
595 0, /* properties_destroyed */
596 0, /* todo_flags_start */
597 ( TODO_cleanup_cfg
| TODO_update_ssa
| TODO_verify_all
),
600 class pass_early_vrp
: public gimple_opt_pass
603 pass_early_vrp (gcc::context
*ctxt
)
604 : gimple_opt_pass (pass_data_early_vrp
, ctxt
)
607 /* opt_pass methods: */
608 opt_pass
* clone () { return new pass_early_vrp (m_ctxt
); }
609 virtual bool gate (function
*)
611 return flag_tree_vrp
!= 0;
613 virtual unsigned int execute (function
*)
614 { return execute_early_vrp (); }
620 make_pass_early_vrp (gcc::context
*ctxt
)
622 return new pass_early_vrp (ctxt
);