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