Mercurial > hg > CbC > CbC_gcc

comparison gcc/gimple-ssa-evrp-analyze.c @ 132:d34655255c78

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update gcc-8.2
author mir3636
date Thu, 25 Oct 2018 10:21:07 +0900
parents 84e7813d76e9
children 1830386684a0
comparison
equal deleted inserted replaced
130:e108057fa461 132:d34655255c78
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 }