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