Mercurial > hg > CbC > CbC_gcc
comparison gcc/gimple-ssa-evrp-analyze.c @ 131:84e7813d76e9
gcc-8.2
author | mir3636 |
---|---|
date | Thu, 25 Oct 2018 07:37:49 +0900 |
parents | |
children | 1830386684a0 |
comparison
equal
deleted
inserted
replaced
111:04ced10e8804 | 131:84e7813d76e9 |
---|---|
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 } |