Line data Source code
1 : /* Support routines for Value Range Propagation (VRP).
2 : Copyright (C) 2005-2026 Free Software Foundation, Inc.
3 : Contributed by Diego Novillo <dnovillo@redhat.com>.
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify
8 : it under the terms of the GNU General Public License as published by
9 : the Free Software Foundation; either version 3, or (at your option)
10 : any later version.
11 :
12 : GCC is distributed in the hope that it will be useful,
13 : but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : GNU General Public License for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : #include "config.h"
22 : #include "system.h"
23 : #include "coretypes.h"
24 : #include "basic-block.h"
25 : #include "bitmap.h"
26 : #include "sbitmap.h"
27 : #include "options.h"
28 : #include "dominance.h"
29 : #include "function.h"
30 : #include "cfg.h"
31 : #include "tree.h"
32 : #include "gimple.h"
33 : #include "tree-pass.h"
34 : #include "ssa.h"
35 : #include "gimple-pretty-print.h"
36 : #include "fold-const.h"
37 : #include "cfganal.h"
38 : #include "gimple-iterator.h"
39 : #include "tree-cfg.h"
40 : #include "tree-ssa-loop-manip.h"
41 : #include "tree-ssa-loop-niter.h"
42 : #include "tree-into-ssa.h"
43 : #include "cfgloop.h"
44 : #include "tree-scalar-evolution.h"
45 : #include "tree-ssa-propagate.h"
46 : #include "domwalk.h"
47 : #include "vr-values.h"
48 : #include "gimple-array-bounds.h"
49 : #include "gimple-range.h"
50 : #include "gimple-range-path.h"
51 : #include "value-pointer-equiv.h"
52 : #include "gimple-fold.h"
53 : #include "tree-dfa.h"
54 : #include "tree-ssa-dce.h"
55 : #include "alloc-pool.h"
56 : #include "cgraph.h"
57 : #include "symbol-summary.h"
58 : #include "ipa-utils.h"
59 : #include "sreal.h"
60 : #include "ipa-cp.h"
61 : #include "ipa-prop.h"
62 : #include "attribs.h"
63 : #include "diagnostic-core.h"
64 :
65 : // This class is utilized by VRP and ranger to remove __builtin_unreachable
66 : // calls, and reflect any resulting global ranges.
67 : //
68 : // maybe_register() is called on condition statements , and if that
69 : // matches the pattern of one branch being a builtin_unreachable, either check
70 : // for early removal or register the resulting executable edge in a list.
71 : //
72 : // During early/non-final processing, we check to see if ALL exports from the
73 : // block can be safely updated with a new global value. If they can, then
74 : // we rewrite the condition and update those values immediately. Otherwise
75 : // the unreachable condition is left in the IL until the final pass.
76 : //
77 : // During final processing, after all blocks have been registered,
78 : // remove_and_update_globals() will
79 : // - check all exports from registered blocks
80 : // - ensure the cache entry of each export is set with the appropriate range
81 : // - rewrite the conditions to take the executable edge
82 : // - perform DCE on any feeding instructions to those rewritten conditions
83 : //
84 : // Then each of the immediate use chain of each export is walked, and a new
85 : // global range created by unioning the ranges at all remaining use locations.
86 :
87 : class remove_unreachable {
88 : public:
89 4233722 : remove_unreachable (range_query &r, bool all) : m_ranger (r), final_p (all)
90 4233722 : { m_list.create (30); m_tmp = BITMAP_ALLOC (NULL); }
91 4233720 : ~remove_unreachable () { BITMAP_FREE (m_tmp); m_list.release (); }
92 : void handle_early (gimple *s, edge e);
93 : void maybe_register (gimple *s);
94 : bool remove ();
95 : bool remove_and_update_globals ();
96 : bool fully_replaceable (tree name, basic_block bb);
97 : vec<std::pair<int, int> > m_list;
98 : range_query &m_ranger;
99 : bool final_p;
100 : bitmap m_tmp;
101 : };
102 :
103 : // Check if block BB has a __builtin_unreachable () call on one arm, and
104 : // register the executable edge if so.
105 :
106 : void
107 8516052 : remove_unreachable::maybe_register (gimple *s)
108 : {
109 8516052 : gcc_checking_assert (gimple_code (s) == GIMPLE_COND);
110 8516052 : basic_block bb = gimple_bb (s);
111 :
112 8516052 : edge e0 = EDGE_SUCC (bb, 0);
113 8516052 : basic_block bb0 = e0->dest;
114 9833148 : bool un0 = EDGE_COUNT (bb0->succs) == 0
115 9833148 : && gimple_seq_unreachable_p (bb_seq (bb0));
116 8516052 : edge e1 = EDGE_SUCC (bb, 1);
117 8516052 : basic_block bb1 = e1->dest;
118 8786537 : bool un1 = EDGE_COUNT (bb1->succs) == 0
119 8786537 : && gimple_seq_unreachable_p (bb_seq (bb1));
120 :
121 : // If the 2 blocks are not different, ignore.
122 8516052 : if (un0 == un1)
123 : return;
124 :
125 : // Constant expressions are ignored.
126 346266 : if (TREE_CODE (gimple_cond_lhs (s)) != SSA_NAME
127 346266 : && TREE_CODE (gimple_cond_rhs (s)) != SSA_NAME)
128 : return;
129 :
130 346178 : edge e = un0 ? e1 : e0;
131 :
132 346178 : if (!final_p)
133 232704 : handle_early (s, e);
134 : else
135 113474 : m_list.safe_push (std::make_pair (e->src->index, e->dest->index));
136 : }
137 :
138 : // Return true if all uses of NAME are dominated by block BB. 1 use
139 : // is allowed in block BB, This is one we hope to remove.
140 : // ie
141 : // _2 = _1 & 7;
142 : // if (_2 != 0)
143 : // goto <bb 3>; [0.00%]
144 : // Any additional use of _1 or _2 in this block invalidates early replacement.
145 :
146 : bool
147 233796 : remove_unreachable::fully_replaceable (tree name, basic_block bb)
148 : {
149 233796 : use_operand_p use_p;
150 233796 : imm_use_iterator iter;
151 233796 : bool saw_in_bb = false;
152 :
153 : // If a name loads from memory, we may lose information used in
154 : // commoning opportunities later. See tree-ssa/ssa-pre-34.c.
155 233796 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
156 464344 : if (gimple_vuse (def_stmt))
157 : return false;
158 :
159 41346 : FOR_EACH_IMM_USE_FAST (use_p, iter, name)
160 : {
161 28206 : gimple *use_stmt = USE_STMT (use_p);
162 : // Ignore debug stmts and the branch.
163 28206 : if (is_gimple_debug (use_stmt))
164 10193 : continue;
165 18013 : basic_block use_bb = gimple_bb (use_stmt);
166 : // Only one use in the block allowed to avoid complicated cases.
167 18013 : if (use_bb == bb)
168 : {
169 7993 : if (saw_in_bb)
170 : return false;
171 : else
172 : saw_in_bb = true;
173 : }
174 10020 : else if (!dominated_by_p (CDI_DOMINATORS, use_bb, bb))
175 : return false;
176 4644 : }
177 4248 : return true;
178 : }
179 :
180 : // This routine is called to check builtin_unreachable calls during any
181 : // time before final removal. The only way we can be sure it does not
182 : // provide any additional information is to expect that we can update the
183 : // global values of all exports from a block. This means the branch
184 : // to the unreachable call must dominate all uses of those ssa-names, with
185 : // the exception that there can be a single use in the block containing
186 : // the branch. IF the name used in the branch is defined in the block, it may
187 : // contain the name of something else that will be an export. And likewise
188 : // that may also use another name that is an export etc.
189 : //
190 : // As long as there is only a single use, we can be sure that there are no other
191 : // side effects (like being passed to a call, or stored to a global, etc.
192 : // This means we will miss cases where there are 2 or more uses that have
193 : // no interveneing statements that may had side effects, but it catches most
194 : // of the cases we care about, and prevents expensive in depth analysis.
195 : //
196 : // Ranger will still reflect the proper ranges at other places in these missed
197 : // cases, we simply will not remove/set globals early.
198 :
199 : void
200 232704 : remove_unreachable::handle_early (gimple *s, edge e)
201 : {
202 : // If there is no gori_ssa, there is no early processsing.
203 232704 : if (!m_ranger.gori_ssa ())
204 : return ;
205 232704 : bool lhs_p = TREE_CODE (gimple_cond_lhs (s)) == SSA_NAME;
206 232704 : bool rhs_p = TREE_CODE (gimple_cond_rhs (s)) == SSA_NAME;
207 : // Do not remove __builtin_unreachable if it confers a relation, or
208 : // that relation may be lost in subsequent passes.
209 232704 : if (lhs_p && rhs_p)
210 : return;
211 : // Do not remove addresses early. ie if (x == &y)
212 231127 : if (lhs_p && TREE_CODE (gimple_cond_rhs (s)) == ADDR_EXPR)
213 : return;
214 :
215 230710 : gcc_checking_assert (gimple_outgoing_range_stmt_p (e->src) == s);
216 230710 : gcc_checking_assert (!final_p);
217 :
218 : // Check if every export and its dependencies are dominated by this branch.
219 : // Dependencies are required as it needs to dominate potential
220 : // recalculations. See PR 123300.
221 230710 : tree name;
222 234958 : FOR_EACH_GORI_EXPORT_AND_DEP_NAME (m_ranger.gori_ssa (), e->src, name, m_tmp)
223 : {
224 233796 : if (!fully_replaceable (name, e->src))
225 229548 : return;
226 : }
227 :
228 : // Set the global value for each.
229 2714 : FOR_EACH_GORI_EXPORT_NAME (m_ranger.gori_ssa (), e->src, name)
230 : {
231 1552 : value_range r (TREE_TYPE (name));
232 1552 : m_ranger.range_on_entry (r, e->dest, name);
233 : // Nothing at this late stage we can do if the write fails.
234 1552 : if (!set_range_info (name, r))
235 258 : continue;
236 1552 : }
237 :
238 1162 : tree ssa = lhs_p ? gimple_cond_lhs (s) : gimple_cond_rhs (s);
239 :
240 : // Rewrite the condition.
241 1162 : if (e->flags & EDGE_TRUE_VALUE)
242 326 : gimple_cond_make_true (as_a<gcond *> (s));
243 : else
244 836 : gimple_cond_make_false (as_a<gcond *> (s));
245 1162 : update_stmt (s);
246 :
247 : // If the name on S is defined in this block, see if there is DCE work to do.
248 1162 : if (gimple_bb (SSA_NAME_DEF_STMT (ssa)) == e->src)
249 : {
250 393 : auto_bitmap dce;
251 393 : bitmap_set_bit (dce, SSA_NAME_VERSION (ssa));
252 393 : simple_dce_from_worklist (dce);
253 393 : }
254 : }
255 :
256 : // Process the edges in the list, change the conditions and removing any
257 : // dead code feeding those conditions. This removes the unreachables, but
258 : // makes no attempt to set globals values.
259 :
260 : bool
261 2 : remove_unreachable::remove ()
262 : {
263 2 : if (!final_p || m_list.length () == 0)
264 : return false;
265 :
266 : bool change = false;
267 : unsigned i;
268 0 : for (i = 0; i < m_list.length (); i++)
269 : {
270 0 : auto eb = m_list[i];
271 0 : basic_block src = BASIC_BLOCK_FOR_FN (cfun, eb.first);
272 0 : basic_block dest = BASIC_BLOCK_FOR_FN (cfun, eb.second);
273 0 : if (!src || !dest)
274 0 : continue;
275 0 : edge e = find_edge (src, dest);
276 0 : gimple *s = gimple_outgoing_range_stmt_p (e->src);
277 0 : gcc_checking_assert (gimple_code (s) == GIMPLE_COND);
278 :
279 0 : tree name = gimple_range_ssa_p (gimple_cond_lhs (s));
280 0 : if (!name)
281 0 : name = gimple_range_ssa_p (gimple_cond_rhs (s));
282 : // Check if global value can be set for NAME.
283 0 : if (name && fully_replaceable (name, src))
284 : {
285 0 : value_range r (TREE_TYPE (name));
286 0 : if (gori_name_on_edge (r, name, e, &m_ranger))
287 0 : set_range_info (name, r);
288 0 : }
289 :
290 0 : change = true;
291 : // Rewrite the condition.
292 0 : if (e->flags & EDGE_TRUE_VALUE)
293 0 : gimple_cond_make_true (as_a<gcond *> (s));
294 : else
295 0 : gimple_cond_make_false (as_a<gcond *> (s));
296 0 : update_stmt (s);
297 : }
298 :
299 : return change;
300 : }
301 :
302 :
303 : // Process the edges in the list, change the conditions and removing any
304 : // dead code feeding those conditions. Calculate the range of any
305 : // names that may have been exported from those blocks, and determine if
306 : // there is any updates to their global ranges..
307 : // Return true if any builtin_unreachables/globals eliminated/updated.
308 :
309 : bool
310 4233720 : remove_unreachable::remove_and_update_globals ()
311 : {
312 4233720 : if (m_list.length () == 0)
313 : return false;
314 :
315 : // If there is no import/export info, Do basic removal.
316 28456 : if (!m_ranger.gori_ssa ())
317 0 : return remove ();
318 :
319 28456 : bool change = false;
320 28456 : tree name;
321 28456 : unsigned i;
322 28456 : bitmap_iterator bi;
323 28456 : auto_bitmap all_exports;
324 141930 : for (i = 0; i < m_list.length (); i++)
325 : {
326 113474 : auto eb = m_list[i];
327 113474 : basic_block src = BASIC_BLOCK_FOR_FN (cfun, eb.first);
328 113474 : basic_block dest = BASIC_BLOCK_FOR_FN (cfun, eb.second);
329 113474 : if (!src || !dest)
330 113474 : continue;
331 113474 : edge e = find_edge (src, dest);
332 113474 : gimple *s = gimple_outgoing_range_stmt_p (e->src);
333 113474 : gcc_checking_assert (gimple_code (s) == GIMPLE_COND);
334 :
335 113474 : bool dominate_exit_p = true;
336 269773 : FOR_EACH_GORI_EXPORT_NAME (m_ranger.gori_ssa (), e->src, name)
337 : {
338 : // Ensure the cache is set for NAME in the succ block.
339 156299 : value_range r(TREE_TYPE (name));
340 156299 : value_range ex(TREE_TYPE (name));
341 156299 : m_ranger.range_on_entry (r, e->dest, name);
342 156299 : m_ranger.range_on_entry (ex, EXIT_BLOCK_PTR_FOR_FN (cfun), name);
343 : // If the range produced by this __builtin_unreachacble expression
344 : // is not fully reflected in the range at exit, then it does not
345 : // dominate the exit of the function.
346 156299 : if (ex.intersect (r))
347 34208 : dominate_exit_p = false;
348 156299 : }
349 :
350 : // If the exit is dominated, add to the export list. Otherwise if this
351 : // isn't the final VRP pass, leave the call in the IL.
352 113474 : if (dominate_exit_p)
353 83567 : bitmap_ior_into (all_exports,
354 83567 : m_ranger.gori_ssa ()->exports (e->src));
355 29907 : else if (!final_p)
356 0 : continue;
357 :
358 113474 : change = true;
359 : // Rewrite the condition.
360 113474 : if (e->flags & EDGE_TRUE_VALUE)
361 2980 : gimple_cond_make_true (as_a<gcond *> (s));
362 : else
363 110494 : gimple_cond_make_false (as_a<gcond *> (s));
364 113474 : update_stmt (s);
365 : }
366 :
367 28456 : if (bitmap_empty_p (all_exports))
368 : return false;
369 : // Invoke DCE on all exported names to eliminate dead feeding defs.
370 24202 : auto_bitmap dce;
371 24202 : bitmap_copy (dce, all_exports);
372 : // Don't attempt to DCE parameters.
373 125506 : EXECUTE_IF_SET_IN_BITMAP (all_exports, 0, i, bi)
374 101304 : if (!ssa_name (i) || SSA_NAME_IS_DEFAULT_DEF (ssa_name (i)))
375 883 : bitmap_clear_bit (dce, i);
376 24202 : simple_dce_from_worklist (dce);
377 :
378 : // Loop over all uses of each name and find maximal range. This is the
379 : // new global range.
380 24202 : use_operand_p use_p;
381 24202 : imm_use_iterator iter;
382 125506 : EXECUTE_IF_SET_IN_BITMAP (all_exports, 0, i, bi)
383 : {
384 101304 : name = ssa_name (i);
385 137238 : if (!name || SSA_NAME_IN_FREE_LIST (name))
386 100645 : continue;
387 35934 : value_range r (TREE_TYPE (name));
388 35934 : value_range exp_range (TREE_TYPE (name));
389 35934 : r.set_undefined ();
390 212549 : FOR_EACH_IMM_USE_FAST (use_p, iter, name)
391 : {
392 161706 : gimple *use_stmt = USE_STMT (use_p);
393 161706 : if (is_gimple_debug (use_stmt))
394 74785 : continue;
395 86921 : if (!m_ranger.range_of_expr (exp_range, name, use_stmt))
396 0 : exp_range.set_varying (TREE_TYPE (name));
397 86921 : r.union_ (exp_range);
398 86921 : if (r.varying_p ())
399 : break;
400 35934 : }
401 : // Include the on-exit range to ensure non-dominated unreachables
402 : // don't incorrectly impact the global range.
403 35934 : m_ranger.range_on_entry (exp_range, EXIT_BLOCK_PTR_FOR_FN (cfun), name);
404 35934 : r.union_ (exp_range);
405 35934 : if (r.varying_p () || r.undefined_p ())
406 21052 : continue;
407 14882 : if (!set_range_info (name, r))
408 14223 : continue;
409 659 : change = true;
410 35934 : }
411 24202 : return change;
412 52658 : }
413 :
414 : /* VR_TYPE describes a range with minimum value *MIN and maximum
415 : value *MAX. Restrict the range to the set of values that have
416 : no bits set outside NONZERO_BITS. Update *MIN and *MAX and
417 : return the new range type.
418 :
419 : SGN gives the sign of the values described by the range. */
420 :
421 : enum value_range_kind
422 17051609 : intersect_range_with_nonzero_bits (enum value_range_kind vr_type,
423 : wide_int *min, wide_int *max,
424 : const wide_int &nonzero_bits,
425 : signop sgn)
426 : {
427 17051609 : if (vr_type == VR_ANTI_RANGE)
428 : {
429 : /* The VR_ANTI_RANGE is equivalent to the union of the ranges
430 : A: [-INF, *MIN) and B: (*MAX, +INF]. First use NONZERO_BITS
431 : to create an inclusive upper bound for A and an inclusive lower
432 : bound for B. */
433 462643 : wide_int a_max = wi::round_down_for_mask (*min - 1, nonzero_bits);
434 462643 : wide_int b_min = wi::round_up_for_mask (*max + 1, nonzero_bits);
435 :
436 : /* If the calculation of A_MAX wrapped, A is effectively empty
437 : and A_MAX is the highest value that satisfies NONZERO_BITS.
438 : Likewise if the calculation of B_MIN wrapped, B is effectively
439 : empty and B_MIN is the lowest value that satisfies NONZERO_BITS. */
440 462643 : bool a_empty = wi::ge_p (a_max, *min, sgn);
441 462643 : bool b_empty = wi::le_p (b_min, *max, sgn);
442 :
443 : /* If both A and B are empty, there are no valid values. */
444 462643 : if (a_empty && b_empty)
445 : return VR_UNDEFINED;
446 :
447 : /* If exactly one of A or B is empty, return a VR_RANGE for the
448 : other one. */
449 462643 : if (a_empty || b_empty)
450 : {
451 0 : *min = b_min;
452 0 : *max = a_max;
453 0 : gcc_checking_assert (wi::le_p (*min, *max, sgn));
454 : return VR_RANGE;
455 : }
456 :
457 : /* Update the VR_ANTI_RANGE bounds. */
458 462643 : *min = a_max + 1;
459 462643 : *max = b_min - 1;
460 462643 : gcc_checking_assert (wi::le_p (*min, *max, sgn));
461 :
462 : /* Now check whether the excluded range includes any values that
463 : satisfy NONZERO_BITS. If not, switch to a full VR_RANGE. */
464 462643 : if (wi::round_up_for_mask (*min, nonzero_bits) == b_min)
465 : {
466 0 : unsigned int precision = min->get_precision ();
467 0 : *min = wi::min_value (precision, sgn);
468 0 : *max = wi::max_value (precision, sgn);
469 0 : vr_type = VR_RANGE;
470 : }
471 462643 : }
472 17051609 : if (vr_type == VR_RANGE || vr_type == VR_VARYING)
473 : {
474 16588966 : *max = wi::round_down_for_mask (*max, nonzero_bits);
475 :
476 : /* Check that the range contains at least one valid value. */
477 16588966 : if (wi::gt_p (*min, *max, sgn))
478 : return VR_UNDEFINED;
479 :
480 16588966 : *min = wi::round_up_for_mask (*min, nonzero_bits);
481 16588966 : gcc_checking_assert (wi::le_p (*min, *max, sgn));
482 : }
483 : return vr_type;
484 : }
485 :
486 : /* Return the single symbol (an SSA_NAME) contained in T if any, or NULL_TREE
487 : otherwise. We only handle additive operations and set NEG to true if the
488 : symbol is negated and INV to the invariant part, if any. */
489 :
490 : static tree
491 5184540 : get_single_symbol (tree t, bool *neg, tree *inv)
492 : {
493 5184540 : bool neg_;
494 5184540 : tree inv_;
495 :
496 5184540 : *inv = NULL_TREE;
497 5184540 : *neg = false;
498 :
499 5184540 : if (TREE_CODE (t) == PLUS_EXPR
500 5184540 : || TREE_CODE (t) == POINTER_PLUS_EXPR
501 5184540 : || TREE_CODE (t) == MINUS_EXPR)
502 : {
503 0 : if (is_gimple_min_invariant (TREE_OPERAND (t, 0)))
504 : {
505 0 : neg_ = (TREE_CODE (t) == MINUS_EXPR);
506 0 : inv_ = TREE_OPERAND (t, 0);
507 0 : t = TREE_OPERAND (t, 1);
508 : }
509 0 : else if (is_gimple_min_invariant (TREE_OPERAND (t, 1)))
510 : {
511 0 : neg_ = false;
512 0 : inv_ = TREE_OPERAND (t, 1);
513 0 : t = TREE_OPERAND (t, 0);
514 : }
515 : else
516 : return NULL_TREE;
517 : }
518 : else
519 : {
520 : neg_ = false;
521 : inv_ = NULL_TREE;
522 : }
523 :
524 5184540 : if (TREE_CODE (t) == NEGATE_EXPR)
525 : {
526 0 : t = TREE_OPERAND (t, 0);
527 0 : neg_ = !neg_;
528 : }
529 :
530 5184540 : if (TREE_CODE (t) != SSA_NAME)
531 : return NULL_TREE;
532 :
533 0 : if (inv_ && TREE_OVERFLOW_P (inv_))
534 0 : inv_ = drop_tree_overflow (inv_);
535 :
536 0 : *neg = neg_;
537 0 : *inv = inv_;
538 0 : return t;
539 : }
540 :
541 : /* Compare two values VAL1 and VAL2. Return
542 :
543 : -2 if VAL1 and VAL2 cannot be compared at compile-time,
544 : -1 if VAL1 < VAL2,
545 : 0 if VAL1 == VAL2,
546 : +1 if VAL1 > VAL2, and
547 : +2 if VAL1 != VAL2
548 :
549 : This is similar to tree_int_cst_compare but supports pointer values
550 : and values that cannot be compared at compile time.
551 :
552 : If STRICT_OVERFLOW_P is not NULL, then set *STRICT_OVERFLOW_P to
553 : true if the return value is only valid if we assume that signed
554 : overflow is undefined. */
555 :
556 : int
557 2919258 : compare_values_warnv (tree val1, tree val2, bool *strict_overflow_p)
558 : {
559 2919258 : if (val1 == val2)
560 : return 0;
561 :
562 : /* Below we rely on the fact that VAL1 and VAL2 are both pointers or
563 : both integers. */
564 2592270 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1))
565 : == POINTER_TYPE_P (TREE_TYPE (val2)));
566 :
567 : /* Convert the two values into the same type. This is needed because
568 : sizetype causes sign extension even for unsigned types. */
569 2592270 : if (!useless_type_conversion_p (TREE_TYPE (val1), TREE_TYPE (val2)))
570 0 : val2 = fold_convert (TREE_TYPE (val1), val2);
571 :
572 2592270 : const bool overflow_undefined
573 5179187 : = INTEGRAL_TYPE_P (TREE_TYPE (val1))
574 5179187 : && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1));
575 2592270 : tree inv1, inv2;
576 2592270 : bool neg1, neg2;
577 2592270 : tree sym1 = get_single_symbol (val1, &neg1, &inv1);
578 2592270 : tree sym2 = get_single_symbol (val2, &neg2, &inv2);
579 :
580 : /* If VAL1 and VAL2 are of the form '[-]NAME [+ CST]', return -1 or +1
581 : accordingly. If VAL1 and VAL2 don't use the same name, return -2. */
582 2592270 : if (sym1 && sym2)
583 : {
584 : /* Both values must use the same name with the same sign. */
585 0 : if (sym1 != sym2 || neg1 != neg2)
586 : return -2;
587 :
588 : /* [-]NAME + CST == [-]NAME + CST. */
589 0 : if (inv1 == inv2)
590 : return 0;
591 :
592 : /* If overflow is defined we cannot simplify more. */
593 0 : if (!overflow_undefined)
594 : return -2;
595 :
596 0 : if (strict_overflow_p != NULL
597 : /* Symbolic range building sets the no-warning bit to declare
598 : that overflow doesn't happen. */
599 0 : && (!inv1 || !warning_suppressed_p (val1, OPT_Woverflow))
600 0 : && (!inv2 || !warning_suppressed_p (val2, OPT_Woverflow)))
601 0 : *strict_overflow_p = true;
602 :
603 0 : if (!inv1)
604 0 : inv1 = build_int_cst (TREE_TYPE (val1), 0);
605 0 : if (!inv2)
606 0 : inv2 = build_int_cst (TREE_TYPE (val2), 0);
607 :
608 0 : return wi::cmp (wi::to_wide (inv1), wi::to_wide (inv2),
609 0 : TYPE_SIGN (TREE_TYPE (val1)));
610 : }
611 :
612 2592270 : const bool cst1 = is_gimple_min_invariant (val1);
613 2592270 : const bool cst2 = is_gimple_min_invariant (val2);
614 :
615 : /* If one is of the form '[-]NAME + CST' and the other is constant, then
616 : it might be possible to say something depending on the constants. */
617 2592270 : if ((sym1 && inv1 && cst2) || (sym2 && inv2 && cst1))
618 : {
619 0 : if (!overflow_undefined)
620 : return -2;
621 :
622 0 : if (strict_overflow_p != NULL
623 : /* Symbolic range building sets the no-warning bit to declare
624 : that overflow doesn't happen. */
625 0 : && (!sym1 || !warning_suppressed_p (val1, OPT_Woverflow))
626 0 : && (!sym2 || !warning_suppressed_p (val2, OPT_Woverflow)))
627 0 : *strict_overflow_p = true;
628 :
629 0 : const signop sgn = TYPE_SIGN (TREE_TYPE (val1));
630 0 : tree cst = cst1 ? val1 : val2;
631 0 : tree inv = cst1 ? inv2 : inv1;
632 :
633 : /* Compute the difference between the constants. If it overflows or
634 : underflows, this means that we can trivially compare the NAME with
635 : it and, consequently, the two values with each other. */
636 0 : wide_int diff = wi::to_wide (cst) - wi::to_wide (inv);
637 0 : if (wi::cmp (0, wi::to_wide (inv), sgn)
638 0 : != wi::cmp (diff, wi::to_wide (cst), sgn))
639 : {
640 0 : const int res = wi::cmp (wi::to_wide (cst), wi::to_wide (inv), sgn);
641 0 : return cst1 ? res : -res;
642 : }
643 :
644 : return -2;
645 0 : }
646 :
647 : /* We cannot say anything more for non-constants. */
648 2592270 : if (!cst1 || !cst2)
649 : return -2;
650 :
651 2592270 : if (!POINTER_TYPE_P (TREE_TYPE (val1)))
652 : {
653 : /* We cannot compare overflowed values. */
654 2592270 : if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
655 : return -2;
656 :
657 2592270 : if (TREE_CODE (val1) == INTEGER_CST
658 2592270 : && TREE_CODE (val2) == INTEGER_CST)
659 2592270 : return tree_int_cst_compare (val1, val2);
660 :
661 0 : if (poly_int_tree_p (val1) && poly_int_tree_p (val2))
662 : {
663 0 : if (known_eq (wi::to_poly_widest (val1),
664 : wi::to_poly_widest (val2)))
665 : return 0;
666 0 : if (known_lt (wi::to_poly_widest (val1),
667 : wi::to_poly_widest (val2)))
668 : return -1;
669 0 : if (known_gt (wi::to_poly_widest (val1),
670 : wi::to_poly_widest (val2)))
671 : return 1;
672 : }
673 :
674 0 : return -2;
675 : }
676 : else
677 : {
678 0 : if (TREE_CODE (val1) == INTEGER_CST && TREE_CODE (val2) == INTEGER_CST)
679 : {
680 : /* We cannot compare overflowed values. */
681 0 : if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
682 : return -2;
683 :
684 0 : return tree_int_cst_compare (val1, val2);
685 : }
686 :
687 : /* First see if VAL1 and VAL2 are not the same. */
688 0 : if (operand_equal_p (val1, val2, 0))
689 : return 0;
690 :
691 0 : fold_defer_overflow_warnings ();
692 :
693 : /* If VAL1 is a lower address than VAL2, return -1. */
694 0 : tree t = fold_binary_to_constant (LT_EXPR, boolean_type_node, val1, val2);
695 0 : if (t && integer_onep (t))
696 : {
697 0 : fold_undefer_and_ignore_overflow_warnings ();
698 0 : return -1;
699 : }
700 :
701 : /* If VAL1 is a higher address than VAL2, return +1. */
702 0 : t = fold_binary_to_constant (LT_EXPR, boolean_type_node, val2, val1);
703 0 : if (t && integer_onep (t))
704 : {
705 0 : fold_undefer_and_ignore_overflow_warnings ();
706 0 : return 1;
707 : }
708 :
709 : /* If VAL1 is different than VAL2, return +2. */
710 0 : t = fold_binary_to_constant (NE_EXPR, boolean_type_node, val1, val2);
711 0 : fold_undefer_and_ignore_overflow_warnings ();
712 0 : if (t && integer_onep (t))
713 : return 2;
714 :
715 0 : return -2;
716 : }
717 : }
718 :
719 : /* Compare values like compare_values_warnv. */
720 :
721 : int
722 2919258 : compare_values (tree val1, tree val2)
723 : {
724 2919258 : bool sop;
725 2919258 : return compare_values_warnv (val1, val2, &sop);
726 : }
727 :
728 : /* Helper for overflow_comparison_p
729 :
730 : OP0 CODE OP1 is a comparison. Examine the comparison and potentially
731 : OP1's defining statement to see if it ultimately has the form
732 : OP0 CODE (OP0 PLUS INTEGER_CST)
733 :
734 : If so, return TRUE indicating this is an overflow test and store into
735 : *NEW_CST an updated constant that can be used in a narrowed range test.
736 :
737 : REVERSED indicates if the comparison was originally:
738 :
739 : OP1 CODE' OP0.
740 :
741 : This affects how we build the updated constant. */
742 :
743 : static bool
744 40171063 : overflow_comparison_p_1 (enum tree_code code, tree op0, tree op1,
745 : bool reversed, tree *new_cst)
746 : {
747 : /* See if this is a relational operation between two SSA_NAMES with
748 : unsigned, overflow wrapping values. If so, check it more deeply. */
749 40171063 : if ((code == LT_EXPR || code == LE_EXPR
750 34125624 : || code == GE_EXPR || code == GT_EXPR)
751 9497679 : && TREE_CODE (op0) == SSA_NAME
752 6684882 : && TREE_CODE (op1) == SSA_NAME
753 3872243 : && INTEGRAL_TYPE_P (TREE_TYPE (op0))
754 3522095 : && TYPE_UNSIGNED (TREE_TYPE (op0))
755 41623804 : && TYPE_OVERFLOW_WRAPS (TREE_TYPE (op0)))
756 : {
757 1452741 : gimple *op1_def = SSA_NAME_DEF_STMT (op1);
758 :
759 : /* Now look at the defining statement of OP1 to see if it adds
760 : or subtracts a nonzero constant from another operand. */
761 1452741 : if (op1_def
762 1452741 : && is_gimple_assign (op1_def)
763 1118264 : && gimple_assign_rhs_code (op1_def) == PLUS_EXPR
764 316121 : && TREE_CODE (gimple_assign_rhs2 (op1_def)) == INTEGER_CST
765 1628567 : && !integer_zerop (gimple_assign_rhs2 (op1_def)))
766 : {
767 175826 : tree target = gimple_assign_rhs1 (op1_def);
768 :
769 : /* If we did not find our target SSA_NAME, then this is not
770 : an overflow test. */
771 175826 : if (op0 != target)
772 : return false;
773 :
774 1364 : tree type = TREE_TYPE (op0);
775 1364 : wide_int max = wi::max_value (TYPE_PRECISION (type), UNSIGNED);
776 1364 : tree inc = gimple_assign_rhs2 (op1_def);
777 1364 : if (reversed)
778 217 : *new_cst = wide_int_to_tree (type, max + wi::to_wide (inc));
779 : else
780 1147 : *new_cst = wide_int_to_tree (type, max - wi::to_wide (inc));
781 1364 : return true;
782 1364 : }
783 : }
784 : return false;
785 : }
786 :
787 : /* OP0 CODE OP1 is a comparison. Examine the comparison and potentially
788 : OP1's defining statement to see if it ultimately has the form
789 : OP0 CODE (OP0 PLUS INTEGER_CST)
790 :
791 : If so, return TRUE indicating this is an overflow test and store into
792 : *NEW_CST an updated constant that can be used in a narrowed range test.
793 :
794 : These statements are left as-is in the IL to facilitate discovery of
795 : {ADD,SUB}_OVERFLOW sequences later in the optimizer pipeline. But
796 : the alternate range representation is often useful within VRP. */
797 :
798 : bool
799 20086105 : overflow_comparison_p (tree_code code, tree name, tree val, tree *new_cst)
800 : {
801 20086105 : if (overflow_comparison_p_1 (code, name, val, false, new_cst))
802 : return true;
803 20084958 : return overflow_comparison_p_1 (swap_tree_comparison (code), val, name,
804 20084958 : true, new_cst);
805 : }
806 :
807 : /* Searches the case label vector VEC for the index *IDX of the CASE_LABEL
808 : that includes the value VAL. The search is restricted to the range
809 : [START_IDX, n - 1] where n is the size of VEC.
810 :
811 : If there is a CASE_LABEL for VAL, its index is placed in IDX and true is
812 : returned.
813 :
814 : If there is no CASE_LABEL for VAL and there is one that is larger than VAL,
815 : it is placed in IDX and false is returned.
816 :
817 : If VAL is larger than any CASE_LABEL, n is placed on IDX and false is
818 : returned. */
819 :
820 : bool
821 155388 : find_case_label_index (gswitch *stmt, size_t start_idx, tree val, size_t *idx)
822 : {
823 155388 : size_t n = gimple_switch_num_labels (stmt);
824 155388 : size_t low, high;
825 :
826 : /* Find case label for minimum of the value range or the next one.
827 : At each iteration we are searching in [low, high - 1]. */
828 :
829 636657 : for (low = start_idx, high = n; high != low; )
830 : {
831 385798 : tree t;
832 385798 : int cmp;
833 : /* Note that i != high, so we never ask for n. */
834 385798 : size_t i = (high + low) / 2;
835 385798 : t = gimple_switch_label (stmt, i);
836 :
837 : /* Cache the result of comparing CASE_LOW and val. */
838 385798 : cmp = tree_int_cst_compare (CASE_LOW (t), val);
839 :
840 385798 : if (cmp == 0)
841 : {
842 : /* Ranges cannot be empty. */
843 58328 : *idx = i;
844 58328 : return true;
845 : }
846 327470 : else if (cmp > 0)
847 : high = i;
848 : else
849 : {
850 144976 : low = i + 1;
851 144976 : if (CASE_HIGH (t) != NULL
852 144976 : && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
853 : {
854 1589 : *idx = i;
855 1589 : return true;
856 : }
857 : }
858 : }
859 :
860 95471 : *idx = high;
861 95471 : return false;
862 : }
863 :
864 : /* Searches the case label vector VEC for the range of CASE_LABELs that is used
865 : for values between MIN and MAX. The first index is placed in MIN_IDX. The
866 : last index is placed in MAX_IDX. If the range of CASE_LABELs is empty
867 : then MAX_IDX < MIN_IDX.
868 : Returns true if the default label is not needed. */
869 :
870 : bool
871 77694 : find_case_label_range (gswitch *stmt, tree min, tree max, size_t *min_idx,
872 : size_t *max_idx)
873 : {
874 77694 : size_t i, j;
875 77694 : bool min_take_default = !find_case_label_index (stmt, 1, min, &i);
876 77694 : bool max_take_default = !find_case_label_index (stmt, i, max, &j);
877 :
878 77694 : if (i == j
879 : && min_take_default
880 7218 : && max_take_default)
881 : {
882 : /* Only the default case label reached.
883 : Return an empty range. */
884 2545 : *min_idx = 1;
885 2545 : *max_idx = 0;
886 2545 : return false;
887 : }
888 : else
889 : {
890 75149 : bool take_default = min_take_default || max_take_default;
891 75149 : tree low, high;
892 75149 : size_t k;
893 :
894 75149 : if (max_take_default)
895 53533 : j--;
896 :
897 : /* If the case label range is continuous, we do not need
898 : the default case label. Verify that. */
899 75149 : high = CASE_LOW (gimple_switch_label (stmt, i));
900 75149 : if (CASE_HIGH (gimple_switch_label (stmt, i)))
901 3155 : high = CASE_HIGH (gimple_switch_label (stmt, i));
902 220132 : for (k = i + 1; k <= j; ++k)
903 : {
904 188015 : low = CASE_LOW (gimple_switch_label (stmt, k));
905 188015 : if (!integer_onep (int_const_binop (MINUS_EXPR, low, high)))
906 : {
907 : take_default = true;
908 : break;
909 : }
910 144983 : high = low;
911 144983 : if (CASE_HIGH (gimple_switch_label (stmt, k)))
912 5710 : high = CASE_HIGH (gimple_switch_label (stmt, k));
913 : }
914 :
915 75149 : *min_idx = i;
916 75149 : *max_idx = j;
917 75149 : return !take_default;
918 : }
919 : }
920 :
921 : /* Given a SWITCH_STMT, return the case label that encompasses the
922 : known possible values for the switch operand. RANGE_OF_OP is a
923 : range for the known values of the switch operand. */
924 :
925 : tree
926 97832 : find_case_label_range (gswitch *switch_stmt, const irange *range_of_op)
927 : {
928 97832 : if (range_of_op->undefined_p ()
929 97832 : || range_of_op->varying_p ())
930 : return NULL_TREE;
931 :
932 77694 : size_t i, j;
933 77694 : tree op = gimple_switch_index (switch_stmt);
934 77694 : tree type = TREE_TYPE (op);
935 77694 : tree tmin = wide_int_to_tree (type, range_of_op->lower_bound ());
936 77694 : tree tmax = wide_int_to_tree (type, range_of_op->upper_bound ());
937 77694 : find_case_label_range (switch_stmt, tmin, tmax, &i, &j);
938 77694 : if (i == j)
939 : {
940 : /* Look for exactly one label that encompasses the range of
941 : the operand. */
942 6171 : tree label = gimple_switch_label (switch_stmt, i);
943 6171 : tree case_high
944 6171 : = CASE_HIGH (label) ? CASE_HIGH (label) : CASE_LOW (label);
945 6171 : wide_int wlow = wi::to_wide (CASE_LOW (label));
946 6171 : wide_int whigh = wi::to_wide (case_high);
947 6171 : int_range_max label_range (TREE_TYPE (case_high), wlow, whigh);
948 6171 : if (!types_compatible_p (label_range.type (), range_of_op->type ()))
949 2 : range_cast (label_range, range_of_op->type ());
950 6171 : label_range.intersect (*range_of_op);
951 6171 : if (label_range == *range_of_op)
952 4307 : return label;
953 6171 : }
954 71523 : else if (i > j)
955 : {
956 : /* If there are no labels at all, take the default. */
957 2545 : return gimple_switch_label (switch_stmt, 0);
958 : }
959 : else
960 : {
961 : /* Otherwise, there are various labels that can encompass
962 : the range of operand. In which case, see if the range of
963 : the operand is entirely *outside* the bounds of all the
964 : (non-default) case labels. If so, take the default. */
965 68978 : unsigned n = gimple_switch_num_labels (switch_stmt);
966 68978 : tree min_label = gimple_switch_label (switch_stmt, 1);
967 68978 : tree max_label = gimple_switch_label (switch_stmt, n - 1);
968 68978 : tree case_high = CASE_HIGH (max_label);
969 68978 : if (!case_high)
970 65756 : case_high = CASE_LOW (max_label);
971 68978 : int_range_max label_range (TREE_TYPE (CASE_LOW (min_label)),
972 137956 : wi::to_wide (CASE_LOW (min_label)),
973 137956 : wi::to_wide (case_high));
974 68978 : if (!types_compatible_p (label_range.type (), range_of_op->type ()))
975 32 : range_cast (label_range, range_of_op->type ());
976 68978 : label_range.intersect (*range_of_op);
977 68978 : if (label_range.undefined_p ())
978 313 : return gimple_switch_label (switch_stmt, 0);
979 68978 : }
980 : return NULL_TREE;
981 : }
982 :
983 : struct case_info
984 : {
985 : tree expr;
986 : basic_block bb;
987 : };
988 :
989 : // This is a ranger based folder which continues to use the dominator
990 : // walk to access the substitute and fold machinery. Ranges are calculated
991 : // on demand.
992 :
993 : class rvrp_folder : public substitute_and_fold_engine
994 : {
995 : public:
996 :
997 4233720 : rvrp_folder (gimple_ranger *r, bool all)
998 4233720 : : substitute_and_fold_engine (),
999 4233720 : m_unreachable (*r, all),
1000 4233720 : m_simplifier (r, r->non_executable_edge_flag)
1001 : {
1002 4233720 : m_ranger = r;
1003 4233720 : m_pta = new pointer_equiv_analyzer (m_ranger);
1004 4233720 : m_last_bb_stmt = NULL;
1005 4233720 : }
1006 :
1007 4233720 : ~rvrp_folder ()
1008 4233720 : {
1009 4233720 : delete m_pta;
1010 4233720 : }
1011 :
1012 119222232 : tree value_of_expr (tree name, gimple *s = NULL) override
1013 : {
1014 : // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
1015 119222232 : if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1016 : return NULL;
1017 119209302 : tree ret = m_ranger->value_of_expr (name, s);
1018 119209302 : if (!ret && supported_pointer_equiv_p (name))
1019 51810853 : ret = m_pta->get_equiv (name);
1020 : return ret;
1021 : }
1022 :
1023 24725970 : tree value_on_edge (edge e, tree name) override
1024 : {
1025 : // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
1026 24725970 : if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1027 : return NULL;
1028 24700508 : tree ret = m_ranger->value_on_edge (e, name);
1029 24700508 : if (!ret && supported_pointer_equiv_p (name))
1030 7634581 : ret = m_pta->get_equiv (name);
1031 : return ret;
1032 : }
1033 :
1034 47160606 : tree value_of_stmt (gimple *s, tree name = NULL) override
1035 : {
1036 : // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
1037 47160606 : if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1038 : return NULL;
1039 47158692 : return m_ranger->value_of_stmt (s, name);
1040 : }
1041 :
1042 36940311 : void pre_fold_bb (basic_block bb) override
1043 : {
1044 36940311 : m_pta->enter (bb);
1045 51603407 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1046 14663096 : gsi_next (&gsi))
1047 14663096 : m_ranger->register_inferred_ranges (gsi.phi ());
1048 36940311 : m_last_bb_stmt = last_nondebug_stmt (bb);
1049 36940311 : }
1050 :
1051 36940311 : void post_fold_bb (basic_block bb) override
1052 : {
1053 36940311 : m_pta->leave (bb);
1054 36940311 : }
1055 :
1056 238511523 : void pre_fold_stmt (gimple *stmt) override
1057 : {
1058 238511523 : m_pta->visit_stmt (stmt);
1059 : // If this is the last stmt and there are inferred ranges, reparse the
1060 : // block for transitive inferred ranges that occur earlier in the block.
1061 238511523 : if (stmt == m_last_bb_stmt)
1062 : {
1063 30735921 : m_ranger->register_transitive_inferred_ranges (gimple_bb (stmt));
1064 : // Also check for builtin_unreachable calls.
1065 30735921 : if (cfun->after_inlining && gimple_code (stmt) == GIMPLE_COND)
1066 8516044 : m_unreachable.maybe_register (stmt);
1067 : }
1068 238511523 : }
1069 :
1070 238248598 : bool fold_stmt (gimple_stmt_iterator *gsi) override
1071 : {
1072 238248598 : bool ret = m_simplifier.simplify (gsi);
1073 238248598 : if (!ret)
1074 237658815 : ret = m_ranger->fold_stmt (gsi, follow_single_use_edges);
1075 238248598 : m_ranger->register_inferred_ranges (gsi_stmt (*gsi));
1076 238248598 : return ret;
1077 : }
1078 :
1079 : remove_unreachable m_unreachable;
1080 : private:
1081 : DISABLE_COPY_AND_ASSIGN (rvrp_folder);
1082 : gimple_ranger *m_ranger;
1083 : simplify_using_ranges m_simplifier;
1084 : pointer_equiv_analyzer *m_pta;
1085 : gimple *m_last_bb_stmt;
1086 : };
1087 :
1088 : /* Main entry point for a VRP pass using just ranger. This can be called
1089 : from anywhere to perform a VRP pass, including from EVRP. */
1090 :
1091 : unsigned int
1092 4233720 : execute_ranger_vrp (struct function *fun, bool final_p)
1093 : {
1094 4233720 : loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
1095 4233720 : rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1096 4233720 : scev_initialize ();
1097 4233720 : calculate_dominance_info (CDI_DOMINATORS);
1098 :
1099 4233720 : set_all_edges_as_executable (fun);
1100 4233720 : gimple_ranger *ranger = enable_ranger (fun, false);
1101 4233720 : phi_analysis (*ranger);
1102 4233720 : rvrp_folder folder (ranger, final_p);
1103 4233720 : folder.substitute_and_fold ();
1104 : // Ensure the cache in SCEV has been cleared before processing
1105 : // globals to be removed.
1106 4233720 : scev_reset ();
1107 : // Remove tagged builtin-unreachable and maybe update globals.
1108 4233720 : folder.m_unreachable.remove_and_update_globals ();
1109 4233720 : if (dump_file && (dump_flags & TDF_DETAILS))
1110 45 : ranger->dump (dump_file);
1111 :
1112 4233720 : if (value_range::supports_type_p (TREE_TYPE
1113 : (TREE_TYPE (current_function_decl)))
1114 1834513 : && flag_ipa_vrp
1115 6067425 : && !lookup_attribute ("noipa", DECL_ATTRIBUTES (current_function_decl)))
1116 : {
1117 1803381 : edge e;
1118 1803381 : edge_iterator ei;
1119 1803381 : bool found = false;
1120 1803381 : value_range return_range (TREE_TYPE (TREE_TYPE (current_function_decl)));
1121 3580438 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
1122 5330321 : if (greturn *ret = dyn_cast <greturn *> (*gsi_last_bb (e->src)))
1123 : {
1124 1776207 : tree retval = gimple_return_retval (ret);
1125 1776207 : if (!retval)
1126 : {
1127 10773 : return_range.set_varying (TREE_TYPE (TREE_TYPE (current_function_decl)));
1128 10773 : found = true;
1129 10773 : continue;
1130 : }
1131 1765434 : value_range r (TREE_TYPE (retval));
1132 1765434 : if (ranger->range_of_expr (r, retval, ret)
1133 1765434 : && !r.undefined_p ()
1134 3530180 : && !r.varying_p ())
1135 : {
1136 737083 : if (!found)
1137 734964 : return_range = r;
1138 : else
1139 2119 : return_range.union_ (r);
1140 : }
1141 : else
1142 1028351 : return_range.set_varying (TREE_TYPE (retval));
1143 1765434 : found = true;
1144 1765434 : }
1145 1803381 : if (found && !return_range.varying_p ())
1146 : {
1147 734902 : ipa_record_return_value_range (return_range);
1148 1342090 : if (POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (current_function_decl)))
1149 260851 : && return_range.nonzero_p ()
1150 987512 : && cgraph_node::get (current_function_decl)
1151 252610 : ->add_detected_attribute ("returns_nonnull"))
1152 223429 : warn_function_returns_nonnull (current_function_decl);
1153 : }
1154 1803381 : }
1155 :
1156 4233720 : disable_ranger (fun);
1157 4233720 : scev_finalize ();
1158 4233720 : loop_optimizer_finalize ();
1159 8467440 : return 0;
1160 4233720 : }
1161 :
1162 : // Implement a Fast VRP folder. Not quite as effective but faster.
1163 :
1164 : class fvrp_folder : public substitute_and_fold_engine
1165 : {
1166 : public:
1167 6 : fvrp_folder (dom_ranger *dr, bool final_p) : substitute_and_fold_engine (),
1168 6 : m_simplifier (dr)
1169 : {
1170 6 : m_dom_ranger = dr;
1171 6 : if (final_p)
1172 2 : m_unreachable = new remove_unreachable (*dr, final_p);
1173 : else
1174 4 : m_unreachable = NULL;
1175 6 : }
1176 :
1177 6 : ~fvrp_folder () { }
1178 :
1179 164 : tree value_of_expr (tree name, gimple *s = NULL) override
1180 : {
1181 : // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
1182 164 : if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1183 : return NULL;
1184 164 : return m_dom_ranger->value_of_expr (name, s);
1185 : }
1186 :
1187 15 : tree value_on_edge (edge e, tree name) override
1188 : {
1189 : // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
1190 15 : if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1191 : return NULL;
1192 15 : return m_dom_ranger->value_on_edge (e, name);
1193 : }
1194 :
1195 123 : tree value_of_stmt (gimple *s, tree name = NULL) override
1196 : {
1197 : // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
1198 123 : if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1199 : return NULL;
1200 123 : return m_dom_ranger->value_of_stmt (s, name);
1201 : }
1202 :
1203 25 : void pre_fold_bb (basic_block bb) override
1204 : {
1205 25 : m_dom_ranger->pre_bb (bb);
1206 : // Now process the PHIs in advance.
1207 25 : gphi_iterator psi = gsi_start_phis (bb);
1208 39 : for ( ; !gsi_end_p (psi); gsi_next (&psi))
1209 : {
1210 14 : tree name = gimple_range_ssa_p (PHI_RESULT (psi.phi ()));
1211 14 : if (name)
1212 : {
1213 6 : value_range vr(TREE_TYPE (name));
1214 6 : m_dom_ranger->range_of_stmt (vr, psi.phi (), name);
1215 6 : }
1216 : }
1217 25 : }
1218 :
1219 25 : void post_fold_bb (basic_block bb) override
1220 : {
1221 25 : m_dom_ranger->post_bb (bb);
1222 25 : }
1223 :
1224 149 : void pre_fold_stmt (gimple *s) override
1225 : {
1226 : // Ensure range_of_stmt has been called.
1227 149 : tree type = gimple_range_type (s);
1228 149 : if (type)
1229 : {
1230 133 : value_range vr(type);
1231 133 : m_dom_ranger->range_of_stmt (vr, s);
1232 133 : }
1233 149 : if (m_unreachable && gimple_code (s) == GIMPLE_COND)
1234 8 : m_unreachable->maybe_register (s);
1235 :
1236 149 : }
1237 :
1238 140 : bool fold_stmt (gimple_stmt_iterator *gsi) override
1239 : {
1240 140 : bool ret = m_simplifier.simplify (gsi);
1241 140 : if (!ret)
1242 137 : ret = ::fold_stmt (gsi, follow_single_use_edges);
1243 140 : return ret;
1244 : }
1245 :
1246 : remove_unreachable *m_unreachable;
1247 : private:
1248 : DISABLE_COPY_AND_ASSIGN (fvrp_folder);
1249 : simplify_using_ranges m_simplifier;
1250 : dom_ranger *m_dom_ranger;
1251 : };
1252 :
1253 :
1254 : // Main entry point for a FAST VRP pass using a dom ranger.
1255 :
1256 : unsigned int
1257 6 : execute_fast_vrp (struct function *fun, bool final_p)
1258 : {
1259 6 : calculate_dominance_info (CDI_DOMINATORS);
1260 6 : dom_ranger dr;
1261 6 : fvrp_folder folder (&dr, final_p);
1262 :
1263 6 : gcc_checking_assert (!fun->x_range_query);
1264 6 : set_all_edges_as_executable (fun);
1265 6 : fun->x_range_query = &dr;
1266 : // Create a relation oracle without transitives.
1267 6 : get_range_query (fun)->create_relation_oracle (false);
1268 :
1269 6 : folder.substitute_and_fold ();
1270 6 : if (folder.m_unreachable)
1271 2 : folder.m_unreachable->remove ();
1272 :
1273 6 : get_range_query (fun)->destroy_relation_oracle ();
1274 6 : fun->x_range_query = NULL;
1275 12 : return 0;
1276 6 : }
1277 :
1278 : namespace {
1279 :
1280 : const pass_data pass_data_vrp =
1281 : {
1282 : GIMPLE_PASS, /* type */
1283 : "vrp", /* name */
1284 : OPTGROUP_NONE, /* optinfo_flags */
1285 : TV_TREE_VRP, /* tv_id */
1286 : PROP_ssa, /* properties_required */
1287 : 0, /* properties_provided */
1288 : 0, /* properties_destroyed */
1289 : 0, /* todo_flags_start */
1290 : ( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */
1291 : };
1292 :
1293 : const pass_data pass_data_early_vrp =
1294 : {
1295 : GIMPLE_PASS, /* type */
1296 : "evrp", /* name */
1297 : OPTGROUP_NONE, /* optinfo_flags */
1298 : TV_TREE_EARLY_VRP, /* tv_id */
1299 : PROP_ssa, /* properties_required */
1300 : 0, /* properties_provided */
1301 : 0, /* properties_destroyed */
1302 : 0, /* todo_flags_start */
1303 : ( TODO_cleanup_cfg | TODO_update_ssa ),
1304 : };
1305 :
1306 : const pass_data pass_data_fast_vrp =
1307 : {
1308 : GIMPLE_PASS, /* type */
1309 : "fvrp", /* name */
1310 : OPTGROUP_NONE, /* optinfo_flags */
1311 : TV_TREE_FAST_VRP, /* tv_id */
1312 : PROP_ssa, /* properties_required */
1313 : 0, /* properties_provided */
1314 : 0, /* properties_destroyed */
1315 : 0, /* todo_flags_start */
1316 : ( TODO_cleanup_cfg | TODO_update_ssa ),
1317 : };
1318 :
1319 :
1320 : class pass_vrp : public gimple_opt_pass
1321 : {
1322 : public:
1323 857166 : pass_vrp (gcc::context *ctxt, const pass_data &data_)
1324 1714332 : : gimple_opt_pass (data_, ctxt), data (data_), final_p (false)
1325 : { }
1326 :
1327 : /* opt_pass methods: */
1328 285722 : opt_pass * clone () final override
1329 285722 : { return new pass_vrp (m_ctxt, data); }
1330 571444 : void set_pass_param (unsigned int n, bool param) final override
1331 : {
1332 571444 : gcc_assert (n == 0);
1333 571444 : final_p = param;
1334 571444 : }
1335 4495396 : bool gate (function *) final override { return flag_tree_vrp != 0; }
1336 4233726 : unsigned int execute (function *fun) final override
1337 : {
1338 : // Check for fast vrp.
1339 4233726 : bool use_fvrp = (&data == &pass_data_fast_vrp);
1340 4233726 : if (!use_fvrp && last_basic_block_for_fn (fun) > param_vrp_block_limit)
1341 : {
1342 6 : use_fvrp = true;
1343 6 : warning (OPT_Wdisabled_optimization,
1344 : "using fast VRP algorithm; %d basic blocks"
1345 : " exceeds %<--param=vrp-block-limit=%d%> limit",
1346 : n_basic_blocks_for_fn (fun),
1347 : param_vrp_block_limit);
1348 : }
1349 4233726 : if (use_fvrp)
1350 6 : return execute_fast_vrp (fun, final_p);
1351 4233720 : return execute_ranger_vrp (fun, final_p);
1352 : }
1353 :
1354 : private:
1355 : const pass_data &data;
1356 : bool final_p;
1357 : }; // class pass_vrp
1358 : } // anon namespace
1359 :
1360 : gimple_opt_pass *
1361 285722 : make_pass_vrp (gcc::context *ctxt)
1362 : {
1363 285722 : return new pass_vrp (ctxt, pass_data_vrp);
1364 : }
1365 :
1366 : gimple_opt_pass *
1367 285722 : make_pass_early_vrp (gcc::context *ctxt)
1368 : {
1369 285722 : return new pass_vrp (ctxt, pass_data_early_vrp);
1370 : }
1371 :
1372 : gimple_opt_pass *
1373 0 : make_pass_fast_vrp (gcc::context *ctxt)
1374 : {
1375 0 : return new pass_vrp (ctxt, pass_data_fast_vrp);
1376 : }
|
