1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005-2019 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 #include "gimple-ssa-evrp-analyze.h"
44
evrp_range_analyzer(bool update_global_ranges)45 evrp_range_analyzer::evrp_range_analyzer (bool update_global_ranges)
46 : stack (10), m_update_global_ranges (update_global_ranges)
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 }
57 vr_values = new class vr_values;
58 }
59
60 /* Push an unwinding marker onto the unwinding stack. */
61
62 void
push_marker()63 evrp_range_analyzer::push_marker ()
64 {
65 stack.safe_push (std::make_pair (NULL_TREE, (value_range *)NULL));
66 }
67
68 /* Analyze ranges as we enter basic block BB. */
69
70 void
enter(basic_block bb)71 evrp_range_analyzer::enter (basic_block bb)
72 {
73 if (!optimize)
74 return;
75 push_marker ();
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 *
try_find_new_range(tree name,tree op,tree_code code,tree limit)83 evrp_range_analyzer::try_find_new_range (tree name,
84 tree op, tree_code code, tree limit)
85 {
86 value_range vr;
87 value_range *old_vr = get_value_range (name);
88
89 /* Discover VR when condition is true. */
90 vr_values->extract_range_for_var_from_comparison_expr (name, code, op,
91 limit, &vr);
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 ())
95 {
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 ()))
99 return NULL;
100 value_range *new_vr = vr_values->allocate_value_range ();
101 new_vr->move (&vr);
102 return new_vr;
103 }
104 return NULL;
105 }
106
107 /* For LHS record VR in the SSA info. */
108 void
set_ssa_range_info(tree lhs,value_range * vr)109 evrp_range_analyzer::set_ssa_range_info (tree lhs, value_range *vr)
110 {
111 gcc_assert (m_update_global_ranges);
112
113 /* Set the SSA with the value range. */
114 if (INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
115 {
116 if (vr->constant_p ())
117 set_range_info (lhs, vr->kind (),
118 wi::to_wide (vr->min ()),
119 wi::to_wide (vr->max ()));
120 }
121 else if (POINTER_TYPE_P (TREE_TYPE (lhs))
122 && range_includes_zero_p (vr) == 0)
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
all_uses_feed_or_dominated_by_stmt(tree name,gimple * stmt)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
157 void
record_ranges_from_incoming_edge(basic_block bb)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 }
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
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)
208 {
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 value_range *old_vr = get_value_range (vrs[i].first);
213 value_range tem (old_vr->kind (), old_vr->min (), old_vr->max ());
214 tem.intersect (vrs[i].second);
215 if (tem.equal_p (*old_vr, /*ignore_equivs=*/true))
216 continue;
217 push_value_range (vrs[i].first, vrs[i].second);
218 if (is_fallthru
219 && m_update_global_ranges
220 && all_uses_feed_or_dominated_by_stmt (vrs[i].first, stmt))
221 {
222 set_ssa_range_info (vrs[i].first, vrs[i].second);
223 maybe_set_nonzero_bits (pred_e, vrs[i].first);
224 }
225 }
226 }
227 }
228 }
229
230 void
record_ranges_from_phis(basic_block bb)231 evrp_range_analyzer::record_ranges_from_phis (basic_block bb)
232 {
233 /* Visit PHI stmts and discover any new VRs possible. */
234 bool has_unvisited_preds = false;
235 edge_iterator ei;
236 edge e;
237 FOR_EACH_EDGE (e, ei, bb->preds)
238 if (e->flags & EDGE_EXECUTABLE
239 && !(e->src->flags & BB_VISITED))
240 {
241 has_unvisited_preds = true;
242 break;
243 }
244
245 for (gphi_iterator gpi = gsi_start_phis (bb);
246 !gsi_end_p (gpi); gsi_next (&gpi))
247 {
248 gphi *phi = gpi.phi ();
249 tree lhs = PHI_RESULT (phi);
250 if (virtual_operand_p (lhs))
251 continue;
252
253 value_range vr_result;
254 bool interesting = stmt_interesting_for_vrp (phi);
255 if (!has_unvisited_preds && interesting)
256 vr_values->extract_range_from_phi_node (phi, &vr_result);
257 else
258 {
259 vr_result.set_varying ();
260 /* When we have an unvisited executable predecessor we can't
261 use PHI arg ranges which may be still UNDEFINED but have
262 to use VARYING for them. But we can still resort to
263 SCEV for loop header PHIs. */
264 struct loop *l;
265 if (scev_initialized_p ()
266 && interesting
267 && (l = loop_containing_stmt (phi))
268 && l->header == gimple_bb (phi))
269 vr_values->adjust_range_with_scev (&vr_result, l, phi, lhs);
270 }
271 vr_values->update_value_range (lhs, &vr_result);
272
273 /* Set the SSA with the value range. */
274 if (m_update_global_ranges)
275 set_ssa_range_info (lhs, &vr_result);
276 }
277 }
278
279 /* Record ranges from STMT into our VR_VALUES class. If TEMPORARY is
280 true, then this is a temporary equivalence and should be recorded
281 into the unwind table. Othewise record the equivalence into the
282 global table. */
283
284 void
record_ranges_from_stmt(gimple * stmt,bool temporary)285 evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt, bool temporary)
286 {
287 tree output = NULL_TREE;
288
289 if (!optimize)
290 return;
291
292 if (dyn_cast <gcond *> (stmt))
293 ;
294 else if (stmt_interesting_for_vrp (stmt))
295 {
296 edge taken_edge;
297 value_range vr;
298 vr_values->extract_range_from_stmt (stmt, &taken_edge, &output, &vr);
299 if (output)
300 {
301 /* Set the SSA with the value range. There are two cases to
302 consider. First (the the most common) is we are processing
303 STMT in a context where its resulting range globally holds
304 and thus it can be reflected into the global ranges and need
305 not be unwound as we leave scope.
306
307 The second case occurs if we are processing a statement in
308 a context where the resulting range must not be reflected
309 into the global tables and must be unwound as we leave
310 the current context. This happens in jump threading for
311 example. */
312 if (!temporary)
313 {
314 /* Case one. We can just update the underlying range
315 information as well as the global information. */
316 vr_values->update_value_range (output, &vr);
317 if (m_update_global_ranges)
318 set_ssa_range_info (output, &vr);
319 }
320 else
321 {
322 /* We're going to need to unwind this range. We cannot
323 use VR as that's a stack object. We have to allocate
324 a new range and push the old range onto the stack. We
325 also have to be very careful about sharing the underlying
326 bitmaps. Ugh. */
327 value_range *new_vr = vr_values->allocate_value_range ();
328 new_vr->set (vr.kind (), vr.min (), vr.max ());
329 vr.equiv_clear ();
330 push_value_range (output, new_vr);
331 }
332 }
333 else
334 vr_values->set_defs_to_varying (stmt);
335 }
336 else
337 vr_values->set_defs_to_varying (stmt);
338
339 /* See if we can derive a range for any of STMT's operands. */
340 tree op;
341 ssa_op_iter i;
342 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
343 {
344 tree value;
345 enum tree_code comp_code;
346
347 /* If OP is used in such a way that we can infer a value
348 range for it, and we don't find a previous assertion for
349 it, create a new assertion location node for OP. */
350 if (infer_value_range (stmt, op, &comp_code, &value))
351 {
352 /* If we are able to infer a nonzero value range for OP,
353 then walk backwards through the use-def chain to see if OP
354 was set via a typecast.
355 If so, then we can also infer a nonzero value range
356 for the operand of the NOP_EXPR. */
357 if (comp_code == NE_EXPR && integer_zerop (value))
358 {
359 tree t = op;
360 gimple *def_stmt = SSA_NAME_DEF_STMT (t);
361 while (is_gimple_assign (def_stmt)
362 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
363 && TREE_CODE
364 (gimple_assign_rhs1 (def_stmt)) == SSA_NAME
365 && POINTER_TYPE_P
366 (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
367 {
368 t = gimple_assign_rhs1 (def_stmt);
369 def_stmt = SSA_NAME_DEF_STMT (t);
370
371 /* Add VR when (T COMP_CODE value) condition is
372 true. */
373 value_range *op_range
374 = try_find_new_range (t, t, comp_code, value);
375 if (op_range)
376 push_value_range (t, op_range);
377 }
378 }
379 /* Add VR when (OP COMP_CODE value) condition is true. */
380 value_range *op_range = try_find_new_range (op, op,
381 comp_code, value);
382 if (op_range)
383 push_value_range (op, op_range);
384 }
385 }
386 }
387
388 /* Unwind recorded ranges to their most recent state. */
389
390 void
pop_to_marker(void)391 evrp_range_analyzer::pop_to_marker (void)
392 {
393 gcc_checking_assert (!stack.is_empty ());
394 while (stack.last ().first != NULL_TREE)
395 pop_value_range (stack.last ().first);
396 stack.pop ();
397 }
398
399 /* Restore/pop VRs valid only for BB when we leave BB. */
400
401 void
leave(basic_block bb ATTRIBUTE_UNUSED)402 evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED)
403 {
404 if (!optimize)
405 return;
406 pop_to_marker ();
407 }
408
409
410 /* Push the Value Range of VAR to the stack and update it with new VR. */
411
412 void
push_value_range(tree var,value_range * vr)413 evrp_range_analyzer::push_value_range (tree var, value_range *vr)
414 {
415 if (dump_file && (dump_flags & TDF_DETAILS))
416 {
417 fprintf (dump_file, "pushing new range for ");
418 print_generic_expr (dump_file, var);
419 fprintf (dump_file, ": ");
420 dump_value_range (dump_file, vr);
421 fprintf (dump_file, "\n");
422 }
423 stack.safe_push (std::make_pair (var, get_value_range (var)));
424 vr_values->set_vr_value (var, vr);
425 }
426
427 /* Pop the Value Range from the vrp_stack and update VAR with it. */
428
429 value_range *
pop_value_range(tree var)430 evrp_range_analyzer::pop_value_range (tree var)
431 {
432 value_range *vr = stack.last ().second;
433 gcc_checking_assert (var == stack.last ().first);
434 if (dump_file && (dump_flags & TDF_DETAILS))
435 {
436 fprintf (dump_file, "popping range for ");
437 print_generic_expr (dump_file, var);
438 fprintf (dump_file, ", restoring ");
439 dump_value_range (dump_file, vr);
440 fprintf (dump_file, "\n");
441 }
442 vr_values->set_vr_value (var, vr);
443 stack.pop ();
444 return vr;
445 }
446