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