|
131
|
1 /* Support routines for Value Range Propagation (VRP).
|
|
145
|
2 Copyright (C) 2005-2020 Free Software Foundation, Inc.
|
|
131
|
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
|
|
145
|
45 evrp_range_analyzer::evrp_range_analyzer (bool update_global_ranges)
|
|
|
46 : stack (10), m_update_global_ranges (update_global_ranges)
|
|
131
|
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
|
|
|
63 evrp_range_analyzer::push_marker ()
|
|
|
64 {
|
|
145
|
65 stack.safe_push (std::make_pair (NULL_TREE, (value_range_equiv *)NULL));
|
|
131
|
66 }
|
|
|
67
|
|
|
68 /* Analyze ranges as we enter basic block BB. */
|
|
|
69
|
|
|
70 void
|
|
|
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. */
|
|
145
|
82 value_range_equiv *
|
|
131
|
83 evrp_range_analyzer::try_find_new_range (tree name,
|
|
145
|
84 tree op, tree_code code, tree limit)
|
|
131
|
85 {
|
|
145
|
86 value_range_equiv vr;
|
|
|
87 const value_range_equiv *old_vr = get_value_range (name);
|
|
131
|
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 {
|
|
145
|
96 if (old_vr->equal_p (vr, /*ignore_equivs=*/true))
|
|
131
|
97 return NULL;
|
|
145
|
98 value_range_equiv *new_vr = vr_values->allocate_value_range_equiv ();
|
|
|
99 new_vr->move (&vr);
|
|
131
|
100 return new_vr;
|
|
|
101 }
|
|
|
102 return NULL;
|
|
|
103 }
|
|
|
104
|
|
|
105 /* For LHS record VR in the SSA info. */
|
|
|
106 void
|
|
145
|
107 evrp_range_analyzer::set_ssa_range_info (tree lhs, value_range_equiv *vr)
|
|
131
|
108 {
|
|
145
|
109 gcc_assert (m_update_global_ranges);
|
|
|
110
|
|
131
|
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
|
|
|
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
|
|
|
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
|
|
145
|
188 auto_vec<std::pair<tree, value_range_equiv *>, 8> vrs;
|
|
131
|
189 for (unsigned i = 0; i < asserts.length (); ++i)
|
|
|
190 {
|
|
145
|
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);
|
|
131
|
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). */
|
|
145
|
211 const value_range_equiv *old_vr
|
|
|
212 = get_value_range (vrs[i].first);
|
|
|
213 value_range tem (*old_vr);
|
|
131
|
214 tem.intersect (vrs[i].second);
|
|
145
|
215 if (tem.equal_p (*old_vr))
|
|
|
216 {
|
|
|
217 vr_values->free_value_range (vrs[i].second);
|
|
|
218 continue;
|
|
|
219 }
|
|
131
|
220 push_value_range (vrs[i].first, vrs[i].second);
|
|
|
221 if (is_fallthru
|
|
145
|
222 && m_update_global_ranges
|
|
131
|
223 && all_uses_feed_or_dominated_by_stmt (vrs[i].first, stmt))
|
|
|
224 {
|
|
|
225 set_ssa_range_info (vrs[i].first, vrs[i].second);
|
|
|
226 maybe_set_nonzero_bits (pred_e, vrs[i].first);
|
|
|
227 }
|
|
|
228 }
|
|
|
229 }
|
|
|
230 }
|
|
|
231 }
|
|
|
232
|
|
|
233 void
|
|
|
234 evrp_range_analyzer::record_ranges_from_phis (basic_block bb)
|
|
|
235 {
|
|
|
236 /* Visit PHI stmts and discover any new VRs possible. */
|
|
|
237 bool has_unvisited_preds = false;
|
|
|
238 edge_iterator ei;
|
|
|
239 edge e;
|
|
|
240 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
241 if (e->flags & EDGE_EXECUTABLE
|
|
|
242 && !(e->src->flags & BB_VISITED))
|
|
|
243 {
|
|
|
244 has_unvisited_preds = true;
|
|
|
245 break;
|
|
|
246 }
|
|
|
247
|
|
|
248 for (gphi_iterator gpi = gsi_start_phis (bb);
|
|
|
249 !gsi_end_p (gpi); gsi_next (&gpi))
|
|
|
250 {
|
|
|
251 gphi *phi = gpi.phi ();
|
|
|
252 tree lhs = PHI_RESULT (phi);
|
|
|
253 if (virtual_operand_p (lhs))
|
|
|
254 continue;
|
|
|
255
|
|
145
|
256 /* Skips floats and other things we can't represent in a
|
|
|
257 range. */
|
|
|
258 if (!value_range::supports_type_p (TREE_TYPE (lhs)))
|
|
|
259 continue;
|
|
|
260
|
|
|
261 value_range_equiv vr_result;
|
|
131
|
262 bool interesting = stmt_interesting_for_vrp (phi);
|
|
|
263 if (!has_unvisited_preds && interesting)
|
|
|
264 vr_values->extract_range_from_phi_node (phi, &vr_result);
|
|
|
265 else
|
|
|
266 {
|
|
145
|
267 vr_result.set_varying (TREE_TYPE (lhs));
|
|
131
|
268 /* When we have an unvisited executable predecessor we can't
|
|
|
269 use PHI arg ranges which may be still UNDEFINED but have
|
|
|
270 to use VARYING for them. But we can still resort to
|
|
|
271 SCEV for loop header PHIs. */
|
|
145
|
272 class loop *l;
|
|
131
|
273 if (scev_initialized_p ()
|
|
|
274 && interesting
|
|
|
275 && (l = loop_containing_stmt (phi))
|
|
|
276 && l->header == gimple_bb (phi))
|
|
|
277 vr_values->adjust_range_with_scev (&vr_result, l, phi, lhs);
|
|
|
278 }
|
|
|
279 vr_values->update_value_range (lhs, &vr_result);
|
|
|
280
|
|
|
281 /* Set the SSA with the value range. */
|
|
145
|
282 if (m_update_global_ranges)
|
|
|
283 set_ssa_range_info (lhs, &vr_result);
|
|
131
|
284 }
|
|
|
285 }
|
|
|
286
|
|
|
287 /* Record ranges from STMT into our VR_VALUES class. If TEMPORARY is
|
|
|
288 true, then this is a temporary equivalence and should be recorded
|
|
|
289 into the unwind table. Othewise record the equivalence into the
|
|
|
290 global table. */
|
|
|
291
|
|
|
292 void
|
|
|
293 evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt, bool temporary)
|
|
|
294 {
|
|
|
295 tree output = NULL_TREE;
|
|
|
296
|
|
|
297 if (!optimize)
|
|
|
298 return;
|
|
|
299
|
|
|
300 if (dyn_cast <gcond *> (stmt))
|
|
|
301 ;
|
|
|
302 else if (stmt_interesting_for_vrp (stmt))
|
|
|
303 {
|
|
|
304 edge taken_edge;
|
|
145
|
305 value_range_equiv vr;
|
|
131
|
306 vr_values->extract_range_from_stmt (stmt, &taken_edge, &output, &vr);
|
|
|
307 if (output)
|
|
|
308 {
|
|
|
309 /* Set the SSA with the value range. There are two cases to
|
|
|
310 consider. First (the the most common) is we are processing
|
|
|
311 STMT in a context where its resulting range globally holds
|
|
|
312 and thus it can be reflected into the global ranges and need
|
|
|
313 not be unwound as we leave scope.
|
|
|
314
|
|
|
315 The second case occurs if we are processing a statement in
|
|
|
316 a context where the resulting range must not be reflected
|
|
|
317 into the global tables and must be unwound as we leave
|
|
|
318 the current context. This happens in jump threading for
|
|
|
319 example. */
|
|
|
320 if (!temporary)
|
|
|
321 {
|
|
|
322 /* Case one. We can just update the underlying range
|
|
|
323 information as well as the global information. */
|
|
|
324 vr_values->update_value_range (output, &vr);
|
|
145
|
325 if (m_update_global_ranges)
|
|
|
326 set_ssa_range_info (output, &vr);
|
|
131
|
327 }
|
|
|
328 else
|
|
|
329 {
|
|
145
|
330 /* We're going to need to unwind this range. We cannot
|
|
|
331 use VR as that's a stack object. We have to allocate
|
|
131
|
332 a new range and push the old range onto the stack. We
|
|
|
333 also have to be very careful about sharing the underlying
|
|
|
334 bitmaps. Ugh. */
|
|
145
|
335 value_range_equiv *new_vr
|
|
|
336 = vr_values->allocate_value_range_equiv ();
|
|
|
337 new_vr->set (vr.min (), vr.max (), NULL, vr.kind ());
|
|
|
338 vr.equiv_clear ();
|
|
131
|
339 push_value_range (output, new_vr);
|
|
|
340 }
|
|
|
341 }
|
|
|
342 else
|
|
|
343 vr_values->set_defs_to_varying (stmt);
|
|
|
344 }
|
|
|
345 else
|
|
|
346 vr_values->set_defs_to_varying (stmt);
|
|
|
347
|
|
|
348 /* See if we can derive a range for any of STMT's operands. */
|
|
|
349 tree op;
|
|
|
350 ssa_op_iter i;
|
|
|
351 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
|
|
|
352 {
|
|
|
353 tree value;
|
|
|
354 enum tree_code comp_code;
|
|
|
355
|
|
|
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))
|
|
|
360 {
|
|
|
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))
|
|
|
367 {
|
|
|
368 tree t = op;
|
|
|
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))
|
|
|
372 && TREE_CODE
|
|
|
373 (gimple_assign_rhs1 (def_stmt)) == SSA_NAME
|
|
|
374 && POINTER_TYPE_P
|
|
|
375 (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
|
|
|
376 {
|
|
|
377 t = gimple_assign_rhs1 (def_stmt);
|
|
|
378 def_stmt = SSA_NAME_DEF_STMT (t);
|
|
|
379
|
|
|
380 /* Add VR when (T COMP_CODE value) condition is
|
|
|
381 true. */
|
|
145
|
382 value_range_equiv *op_range
|
|
131
|
383 = try_find_new_range (t, t, comp_code, value);
|
|
|
384 if (op_range)
|
|
|
385 push_value_range (t, op_range);
|
|
|
386 }
|
|
|
387 }
|
|
|
388 /* Add VR when (OP COMP_CODE value) condition is true. */
|
|
145
|
389 value_range_equiv *op_range = try_find_new_range (op, op,
|
|
|
390 comp_code, value);
|
|
131
|
391 if (op_range)
|
|
|
392 push_value_range (op, op_range);
|
|
|
393 }
|
|
|
394 }
|
|
|
395 }
|
|
|
396
|
|
|
397 /* Unwind recorded ranges to their most recent state. */
|
|
|
398
|
|
|
399 void
|
|
|
400 evrp_range_analyzer::pop_to_marker (void)
|
|
|
401 {
|
|
|
402 gcc_checking_assert (!stack.is_empty ());
|
|
|
403 while (stack.last ().first != NULL_TREE)
|
|
145
|
404 pop_value_range ();
|
|
131
|
405 stack.pop ();
|
|
|
406 }
|
|
|
407
|
|
|
408 /* Restore/pop VRs valid only for BB when we leave BB. */
|
|
|
409
|
|
|
410 void
|
|
|
411 evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED)
|
|
|
412 {
|
|
|
413 if (!optimize)
|
|
|
414 return;
|
|
|
415 pop_to_marker ();
|
|
|
416 }
|
|
|
417
|
|
|
418
|
|
|
419 /* Push the Value Range of VAR to the stack and update it with new VR. */
|
|
|
420
|
|
|
421 void
|
|
145
|
422 evrp_range_analyzer::push_value_range (tree var, value_range_equiv *vr)
|
|
131
|
423 {
|
|
|
424 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
425 {
|
|
|
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");
|
|
|
431 }
|
|
145
|
432 value_range_equiv *old_vr = vr_values->swap_vr_value (var, vr);
|
|
|
433 stack.safe_push (std::make_pair (var, old_vr));
|
|
131
|
434 }
|
|
|
435
|
|
145
|
436 /* Pop a Value Range from the vrp_stack. */
|
|
131
|
437
|
|
145
|
438 void
|
|
|
439 evrp_range_analyzer::pop_value_range ()
|
|
131
|
440 {
|
|
145
|
441 std::pair<tree, value_range_equiv *> e = stack.pop ();
|
|
|
442 tree var = e.first;
|
|
|
443 value_range_equiv *vr = e.second;
|
|
131
|
444 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
445 {
|
|
|
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");
|
|
|
451 }
|
|
145
|
452 /* We saved off a lattice entry, now give it back and release
|
|
|
453 the one we popped. */
|
|
|
454 value_range_equiv *popped_vr = vr_values->swap_vr_value (var, vr);
|
|
|
455 if (popped_vr)
|
|
|
456 vr_values->free_value_range (popped_vr);
|
|
131
|
457 }
|
