1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005-2019 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"
43 #include "gimple-ssa-evrp-analyze.h"
45 evrp_range_analyzer::evrp_range_analyzer (bool update_global_ranges
)
46 : stack (10), m_update_global_ranges (update_global_ranges
)
51 FOR_EACH_BB_FN (bb
, cfun
)
53 bb
->flags
&= ~BB_VISITED
;
54 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
55 e
->flags
|= EDGE_EXECUTABLE
;
57 vr_values
= new class vr_values
;
60 /* Push an unwinding marker onto the unwinding stack. */
63 evrp_range_analyzer::push_marker ()
65 stack
.safe_push (std::make_pair (NULL_TREE
, (value_range
*)NULL
));
68 /* Analyze ranges as we enter basic block BB. */
71 evrp_range_analyzer::enter (basic_block bb
)
76 record_ranges_from_incoming_edge (bb
);
77 record_ranges_from_phis (bb
);
78 bb
->flags
|= BB_VISITED
;
81 /* Find new range for NAME such that (OP CODE LIMIT) is true. */
83 evrp_range_analyzer::try_find_new_range (tree name
,
84 tree op
, tree_code code
, tree limit
)
87 const value_range
*old_vr
= get_value_range (name
);
89 /* Discover VR when condition is true. */
90 vr_values
->extract_range_for_var_from_comparison_expr (name
, code
, op
,
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. */
94 if (!vr
.undefined_p () && !vr
.varying_p ())
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 ()))
100 value_range
*new_vr
= vr_values
->allocate_value_range ();
107 /* For LHS record VR in the SSA info. */
109 evrp_range_analyzer::set_ssa_range_info (tree lhs
, value_range
*vr
)
111 gcc_assert (m_update_global_ranges
);
113 /* Set the SSA with the value range. */
114 if (INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
116 if (vr
->constant_p ())
117 set_range_info (lhs
, vr
->kind (),
118 wi::to_wide (vr
->min ()),
119 wi::to_wide (vr
->max ()));
121 else if (POINTER_TYPE_P (TREE_TYPE (lhs
))
122 && range_includes_zero_p (vr
) == 0)
123 set_ptr_nonnull (lhs
);
126 /* Return true if all uses of NAME are dominated by STMT or feed STMT
127 via a chain of single immediate uses. */
130 all_uses_feed_or_dominated_by_stmt (tree name
, gimple
*stmt
)
132 use_operand_p use_p
, use2_p
;
133 imm_use_iterator iter
;
134 basic_block stmt_bb
= gimple_bb (stmt
);
136 FOR_EACH_IMM_USE_FAST (use_p
, iter
, name
)
138 gimple
*use_stmt
= USE_STMT (use_p
), *use_stmt2
;
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
)))
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
)
158 evrp_range_analyzer::record_ranges_from_incoming_edge (basic_block bb
)
160 edge pred_e
= single_pred_edge_ignoring_loop_edges (bb
, false);
163 gimple
*stmt
= last_stmt (pred_e
->src
);
164 tree op0
= NULL_TREE
;
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
)))))
173 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
175 fprintf (dump_file
, "Visiting controlling predicate ");
176 print_gimple_stmt (dump_file
, stmt
, 0);
178 /* Entering a new scope. Try to see if we can find a VR
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
);
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
);
190 auto_vec
<std::pair
<tree
, value_range
*>, 8> vrs
;
191 for (unsigned i
= 0; i
< asserts
.length (); ++i
)
193 value_range
*vr
= try_find_new_range (asserts
[i
].name
,
195 asserts
[i
].comp_code
,
198 vrs
.safe_push (std::make_pair (asserts
[i
].name
, vr
));
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
);
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
)
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). */
212 const value_range
*old_vr
= get_value_range (vrs
[i
].first
);
213 value_range_base
tem (old_vr
->kind (), old_vr
->min (),
215 tem
.intersect (vrs
[i
].second
);
216 if (tem
.equal_p (*old_vr
))
218 vr_values
->free_value_range (vrs
[i
].second
);
221 push_value_range (vrs
[i
].first
, vrs
[i
].second
);
223 && m_update_global_ranges
224 && all_uses_feed_or_dominated_by_stmt (vrs
[i
].first
, stmt
))
226 set_ssa_range_info (vrs
[i
].first
, vrs
[i
].second
);
227 maybe_set_nonzero_bits (pred_e
, vrs
[i
].first
);
235 evrp_range_analyzer::record_ranges_from_phis (basic_block bb
)
237 /* Visit PHI stmts and discover any new VRs possible. */
238 bool has_unvisited_preds
= false;
241 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
242 if (e
->flags
& EDGE_EXECUTABLE
243 && !(e
->src
->flags
& BB_VISITED
))
245 has_unvisited_preds
= true;
249 for (gphi_iterator gpi
= gsi_start_phis (bb
);
250 !gsi_end_p (gpi
); gsi_next (&gpi
))
252 gphi
*phi
= gpi
.phi ();
253 tree lhs
= PHI_RESULT (phi
);
254 if (virtual_operand_p (lhs
))
257 /* Skips floats and other things we can't represent in a
259 if (!value_range_base::supports_type_p (TREE_TYPE (lhs
)))
262 value_range vr_result
;
263 bool interesting
= stmt_interesting_for_vrp (phi
);
264 if (!has_unvisited_preds
&& interesting
)
265 vr_values
->extract_range_from_phi_node (phi
, &vr_result
);
268 vr_result
.set_varying (TREE_TYPE (lhs
));
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. */
274 if (scev_initialized_p ()
276 && (l
= loop_containing_stmt (phi
))
277 && l
->header
== gimple_bb (phi
))
278 vr_values
->adjust_range_with_scev (&vr_result
, l
, phi
, lhs
);
280 vr_values
->update_value_range (lhs
, &vr_result
);
282 /* Set the SSA with the value range. */
283 if (m_update_global_ranges
)
284 set_ssa_range_info (lhs
, &vr_result
);
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
294 evrp_range_analyzer::record_ranges_from_stmt (gimple
*stmt
, bool temporary
)
296 tree output
= NULL_TREE
;
301 if (dyn_cast
<gcond
*> (stmt
))
303 else if (stmt_interesting_for_vrp (stmt
))
307 vr_values
->extract_range_from_stmt (stmt
, &taken_edge
, &output
, &vr
);
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.
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
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
);
326 if (m_update_global_ranges
)
327 set_ssa_range_info (output
, &vr
);
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
333 a new range and push the old range onto the stack. We
334 also have to be very careful about sharing the underlying
336 value_range
*new_vr
= vr_values
->allocate_value_range ();
337 new_vr
->set (vr
.kind (), vr
.min (), vr
.max ());
339 push_value_range (output
, new_vr
);
343 vr_values
->set_defs_to_varying (stmt
);
346 vr_values
->set_defs_to_varying (stmt
);
348 /* See if we can derive a range for any of STMT's operands. */
351 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_USE
)
354 enum tree_code comp_code
;
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
))
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
))
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
))
373 (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
375 (TREE_TYPE (gimple_assign_rhs1 (def_stmt
))))
377 t
= gimple_assign_rhs1 (def_stmt
);
378 def_stmt
= SSA_NAME_DEF_STMT (t
);
380 /* Add VR when (T COMP_CODE value) condition is
382 value_range
*op_range
383 = try_find_new_range (t
, t
, comp_code
, value
);
385 push_value_range (t
, op_range
);
388 /* Add VR when (OP COMP_CODE value) condition is true. */
389 value_range
*op_range
= try_find_new_range (op
, op
,
392 push_value_range (op
, op_range
);
397 /* Unwind recorded ranges to their most recent state. */
400 evrp_range_analyzer::pop_to_marker (void)
402 gcc_checking_assert (!stack
.is_empty ());
403 while (stack
.last ().first
!= NULL_TREE
)
408 /* Restore/pop VRs valid only for BB when we leave BB. */
411 evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED
)
419 /* Push the Value Range of VAR to the stack and update it with new VR. */
422 evrp_range_analyzer::push_value_range (tree var
, value_range
*vr
)
424 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
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");
432 value_range
*old_vr
= vr_values
->swap_vr_value (var
, vr
);
433 stack
.safe_push (std::make_pair (var
, old_vr
));
436 /* Pop a Value Range from the vrp_stack. */
439 evrp_range_analyzer::pop_value_range ()
441 std::pair
<tree
, value_range
*> e
= stack
.pop ();
443 value_range
*vr
= e
.second
;
444 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
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");
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
);
456 vr_values
->free_value_range (popped_vr
);