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