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