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 4401438 : remove_unreachable (range_query &r, bool all) : m_ranger (r), final_p (all)
89 4401438 : { m_list.create (30); m_tmp = BITMAP_ALLOC (NULL); }
90 4401435 : ~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<edge> 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 8680719 : remove_unreachable::maybe_register (gimple *s)
107 : {
108 8680719 : gcc_checking_assert (gimple_code (s) == GIMPLE_COND);
109 8680719 : basic_block bb = gimple_bb (s);
110 :
111 8680719 : edge e0 = EDGE_SUCC (bb, 0);
112 8680719 : basic_block bb0 = e0->dest;
113 10001513 : bool un0 = EDGE_COUNT (bb0->succs) == 0
114 10001513 : && gimple_seq_unreachable_p (bb_seq (bb0));
115 8680719 : edge e1 = EDGE_SUCC (bb, 1);
116 8680719 : basic_block bb1 = e1->dest;
117 8951810 : bool un1 = EDGE_COUNT (bb1->succs) == 0
118 8951810 : && gimple_seq_unreachable_p (bb_seq (bb1));
119 :
120 : // If the 2 blocks are not different, ignore.
121 8680719 : if (un0 == un1)
122 8313519 : return;
123 :
124 : // Constant expressions are ignored.
125 367288 : if (TREE_CODE (gimple_cond_lhs (s)) != SSA_NAME
126 367288 : && TREE_CODE (gimple_cond_rhs (s)) != SSA_NAME)
127 : return;
128 :
129 367200 : edge e = un0 ? e1 : e0;
130 :
131 367200 : if (!final_p)
132 247031 : handle_early (s, e);
133 : else
134 120169 : m_list.safe_push (e);
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 248386 : remove_unreachable::fully_replaceable (tree name, basic_block bb)
147 : {
148 248386 : use_operand_p use_p;
149 248386 : imm_use_iterator iter;
150 248386 : 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 248386 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
155 492776 : if (gimple_vuse (def_stmt))
156 : return false;
157 :
158 38048 : FOR_EACH_IMM_USE_FAST (use_p, iter, name)
159 : {
160 33296 : gimple *use_stmt = USE_STMT (use_p);
161 : // Ignore debug stmts and the branch.
162 33296 : if (is_gimple_debug (use_stmt))
163 12007 : continue;
164 21289 : basic_block use_bb = gimple_bb (use_stmt);
165 : // Only one use in the block allowed to avoid complicated cases.
166 21289 : if (use_bb == bb)
167 : {
168 10067 : if (saw_in_bb)
169 : return false;
170 : else
171 : saw_in_bb = true;
172 : }
173 11222 : else if (!dominated_by_p (CDI_DOMINATORS, use_bb, bb))
174 : return false;
175 5180 : }
176 4752 : 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 247031 : remove_unreachable::handle_early (gimple *s, edge e)
200 : {
201 : // If there is no gori_ssa, there is no early processing.
202 247031 : if (!m_ranger.gori_ssa ())
203 : return ;
204 247031 : bool lhs_p = TREE_CODE (gimple_cond_lhs (s)) == SSA_NAME;
205 247031 : 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 247031 : if (lhs_p && rhs_p)
209 : return;
210 : // Do not remove addresses early. ie if (x == &y)
211 245618 : if (lhs_p && TREE_CODE (gimple_cond_rhs (s)) == ADDR_EXPR)
212 : return;
213 :
214 245230 : gcc_checking_assert (gimple_outgoing_range_stmt_p (e->src) == s);
215 245230 : 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 245230 : tree name;
221 249982 : FOR_EACH_GORI_EXPORT_AND_DEP_NAME (m_ranger.gori_ssa (), e->src, name, m_tmp)
222 : {
223 248386 : if (!fully_replaceable (name, e->src))
224 243634 : return;
225 : }
226 :
227 : // Set the global value for each.
228 3657 : FOR_EACH_GORI_EXPORT_NAME (m_ranger.gori_ssa (), e->src, name)
229 : {
230 2061 : value_range r (TREE_TYPE (name));
231 2061 : m_ranger.range_on_entry (r, e->dest, name);
232 : // Nothing at this late stage we can do if the write fails.
233 2061 : if (!set_range_info (name, r))
234 245 : continue;
235 2061 : }
236 :
237 1596 : tree ssa = lhs_p ? gimple_cond_lhs (s) : gimple_cond_rhs (s);
238 :
239 : // Rewrite the condition.
240 1596 : if (e->flags & EDGE_TRUE_VALUE)
241 366 : gimple_cond_make_true (as_a<gcond *> (s));
242 : else
243 1230 : gimple_cond_make_false (as_a<gcond *> (s));
244 1596 : update_stmt (s);
245 :
246 : // If the name on S is defined in this block, see if there is DCE work to do.
247 1596 : if (gimple_bb (SSA_NAME_DEF_STMT (ssa)) == e->src)
248 : {
249 521 : auto_bitmap dce;
250 521 : bitmap_set_bit (dce, SSA_NAME_VERSION (ssa));
251 521 : simple_dce_from_worklist (dce, nullptr, true);
252 521 : }
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 3 : remove_unreachable::remove ()
261 : {
262 3 : 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 : edge e = m_list[i];
270 0 : gimple *s = gimple_outgoing_range_stmt_p (e->src);
271 0 : gcc_checking_assert (gimple_code (s) == GIMPLE_COND);
272 :
273 0 : tree name = gimple_range_ssa_p (gimple_cond_lhs (s));
274 0 : if (!name)
275 0 : name = gimple_range_ssa_p (gimple_cond_rhs (s));
276 : // Check if global value can be set for NAME.
277 0 : if (name && fully_replaceable (name, e->src))
278 : {
279 0 : value_range r (TREE_TYPE (name));
280 0 : if (gori_name_on_edge (r, name, e, &m_ranger))
281 0 : set_range_info (name, r);
282 0 : }
283 :
284 0 : change = true;
285 : // Rewrite the condition.
286 0 : if (e->flags & EDGE_TRUE_VALUE)
287 0 : gimple_cond_make_true (as_a<gcond *> (s));
288 : else
289 0 : gimple_cond_make_false (as_a<gcond *> (s));
290 0 : update_stmt (s);
291 : }
292 :
293 : return change;
294 : }
295 :
296 :
297 : // Process the edges in the list, change the conditions and removing any
298 : // dead code feeding those conditions. Calculate the range of any
299 : // names that may have been exported from those blocks, and determine if
300 : // there is any updates to their global ranges..
301 : // Return true if any builtin_unreachables/globals eliminated/updated.
302 :
303 : bool
304 4401435 : remove_unreachable::remove_and_update_globals ()
305 : {
306 4401435 : if (m_list.length () == 0)
307 : return false;
308 :
309 : // If there is no import/export info, Do basic removal.
310 29377 : if (!m_ranger.gori_ssa ())
311 0 : return remove ();
312 :
313 29377 : bool change = false;
314 29377 : tree name;
315 29377 : unsigned i;
316 29377 : bitmap_iterator bi;
317 29377 : auto_bitmap all_exports;
318 149546 : for (i = 0; i < m_list.length (); i++)
319 : {
320 120169 : edge e = m_list[i];
321 120169 : gimple *s = gimple_outgoing_range_stmt_p (e->src);
322 120169 : gcc_checking_assert (gimple_code (s) == GIMPLE_COND);
323 :
324 120169 : bool dominate_exit_p = true;
325 288262 : FOR_EACH_GORI_EXPORT_NAME (m_ranger.gori_ssa (), e->src, name)
326 : {
327 : // Ensure the cache is set for NAME in the succ block.
328 168093 : value_range r(TREE_TYPE (name));
329 168093 : value_range ex(TREE_TYPE (name));
330 168093 : m_ranger.range_on_entry (r, e->dest, name);
331 168093 : m_ranger.range_on_entry (ex, EXIT_BLOCK_PTR_FOR_FN (cfun), name);
332 : // If the range produced by this __builtin_unreachacble expression
333 : // is not fully reflected in the range at exit, then it does not
334 : // dominate the exit of the function.
335 168093 : if (ex.intersect (r))
336 35998 : dominate_exit_p = false;
337 168093 : }
338 :
339 : // If the exit is dominated, add to the export list. Otherwise if this
340 : // isn't the final VRP pass, leave the call in the IL.
341 120169 : if (dominate_exit_p)
342 88544 : bitmap_ior_into (all_exports,
343 88544 : m_ranger.gori_ssa ()->exports (e->src));
344 31625 : else if (!final_p)
345 0 : continue;
346 :
347 120169 : change = true;
348 : // Rewrite the condition.
349 120169 : if (e->flags & EDGE_TRUE_VALUE)
350 3048 : gimple_cond_make_true (as_a<gcond *> (s));
351 : else
352 117121 : gimple_cond_make_false (as_a<gcond *> (s));
353 120169 : update_stmt (s);
354 : }
355 :
356 29377 : if (bitmap_empty_p (all_exports))
357 : return false;
358 : // Invoke DCE on all exported names to eliminate dead feeding defs.
359 24021 : auto_bitmap dce;
360 24021 : bitmap_copy (dce, all_exports);
361 : // Don't attempt to DCE parameters.
362 134097 : EXECUTE_IF_SET_IN_BITMAP (all_exports, 0, i, bi)
363 110076 : if (!ssa_name (i) || SSA_NAME_IS_DEFAULT_DEF (ssa_name (i)))
364 1107 : bitmap_clear_bit (dce, i);
365 24021 : simple_dce_from_worklist (dce);
366 :
367 : // Loop over all uses of each name and find maximal range. This is the
368 : // new global range.
369 24021 : use_operand_p use_p;
370 24021 : imm_use_iterator iter;
371 134097 : EXECUTE_IF_SET_IN_BITMAP (all_exports, 0, i, bi)
372 : {
373 110076 : name = ssa_name (i);
374 152159 : if (!name || SSA_NAME_IN_FREE_LIST (name))
375 109227 : continue;
376 42083 : value_range r (TREE_TYPE (name));
377 42083 : value_range exp_range (TREE_TYPE (name));
378 42083 : r.set_undefined ();
379 227508 : FOR_EACH_IMM_USE_FAST (use_p, iter, name)
380 : {
381 212356 : gimple *use_stmt = USE_STMT (use_p);
382 212356 : if (is_gimple_debug (use_stmt))
383 106848 : continue;
384 105508 : if (!m_ranger.range_of_expr (exp_range, name, use_stmt))
385 0 : exp_range.set_varying (TREE_TYPE (name));
386 105508 : r.union_ (exp_range);
387 105508 : if (r.varying_p ())
388 : break;
389 42083 : }
390 : // Include the on-exit range to ensure non-dominated unreachables
391 : // don't incorrectly impact the global range.
392 42083 : m_ranger.range_on_entry (exp_range, EXIT_BLOCK_PTR_FOR_FN (cfun), name);
393 42083 : r.union_ (exp_range);
394 42083 : if (r.varying_p () || r.undefined_p ())
395 26974 : continue;
396 15109 : if (!set_range_info (name, r))
397 14260 : continue;
398 849 : change = true;
399 42083 : }
400 24021 : return change;
401 53398 : }
402 :
403 : /* VR_TYPE describes a range with minimum value *MIN and maximum
404 : value *MAX. Restrict the range to the set of values that have
405 : no bits set outside NONZERO_BITS. Update *MIN and *MAX and
406 : return the new range type.
407 :
408 : SGN gives the sign of the values described by the range. */
409 :
410 : enum value_range_kind
411 17957962 : intersect_range_with_nonzero_bits (enum value_range_kind vr_type,
412 : wide_int *min, wide_int *max,
413 : const wide_int &nonzero_bits,
414 : signop sgn)
415 : {
416 17957962 : if (vr_type == VR_ANTI_RANGE)
417 : {
418 : /* The VR_ANTI_RANGE is equivalent to the union of the ranges
419 : A: [-INF, *MIN) and B: (*MAX, +INF]. First use NONZERO_BITS
420 : to create an inclusive upper bound for A and an inclusive lower
421 : bound for B. */
422 490954 : wide_int a_max = wi::round_down_for_mask (*min - 1, nonzero_bits);
423 490954 : wide_int b_min = wi::round_up_for_mask (*max + 1, nonzero_bits);
424 :
425 : /* If the calculation of A_MAX wrapped, A is effectively empty
426 : and A_MAX is the highest value that satisfies NONZERO_BITS.
427 : Likewise if the calculation of B_MIN wrapped, B is effectively
428 : empty and B_MIN is the lowest value that satisfies NONZERO_BITS. */
429 490954 : bool a_empty = wi::ge_p (a_max, *min, sgn);
430 490954 : bool b_empty = wi::le_p (b_min, *max, sgn);
431 :
432 : /* If both A and B are empty, there are no valid values. */
433 490954 : if (a_empty && b_empty)
434 : return VR_UNDEFINED;
435 :
436 : /* If exactly one of A or B is empty, return a VR_RANGE for the
437 : other one. */
438 490954 : if (a_empty || b_empty)
439 : {
440 0 : *min = b_min;
441 0 : *max = a_max;
442 0 : gcc_checking_assert (wi::le_p (*min, *max, sgn));
443 : return VR_RANGE;
444 : }
445 :
446 : /* Update the VR_ANTI_RANGE bounds. */
447 490954 : *min = a_max + 1;
448 490954 : *max = b_min - 1;
449 490954 : gcc_checking_assert (wi::le_p (*min, *max, sgn));
450 :
451 : /* Now check whether the excluded range includes any values that
452 : satisfy NONZERO_BITS. If not, switch to a full VR_RANGE. */
453 490954 : if (wi::round_up_for_mask (*min, nonzero_bits) == b_min)
454 : {
455 0 : unsigned int precision = min->get_precision ();
456 0 : *min = wi::min_value (precision, sgn);
457 0 : *max = wi::max_value (precision, sgn);
458 0 : vr_type = VR_RANGE;
459 : }
460 490954 : }
461 17957962 : if (vr_type == VR_RANGE || vr_type == VR_VARYING)
462 : {
463 17467008 : *max = wi::round_down_for_mask (*max, nonzero_bits);
464 :
465 : /* Check that the range contains at least one valid value. */
466 17467008 : if (wi::gt_p (*min, *max, sgn))
467 : return VR_UNDEFINED;
468 :
469 17467008 : *min = wi::round_up_for_mask (*min, nonzero_bits);
470 17467008 : gcc_checking_assert (wi::le_p (*min, *max, sgn));
471 : }
472 : return vr_type;
473 : }
474 :
475 : /* Return the single symbol (an SSA_NAME) contained in T if any, or NULL_TREE
476 : otherwise. We only handle additive operations and set NEG to true if the
477 : symbol is negated and INV to the invariant part, if any. */
478 :
479 : static tree
480 5342322 : get_single_symbol (tree t, bool *neg, tree *inv)
481 : {
482 5342322 : bool neg_;
483 5342322 : tree inv_;
484 :
485 5342322 : *inv = NULL_TREE;
486 5342322 : *neg = false;
487 :
488 5342322 : if (TREE_CODE (t) == PLUS_EXPR
489 5342322 : || TREE_CODE (t) == POINTER_PLUS_EXPR
490 5342322 : || TREE_CODE (t) == MINUS_EXPR)
491 : {
492 0 : if (is_gimple_min_invariant (TREE_OPERAND (t, 0)))
493 : {
494 0 : neg_ = (TREE_CODE (t) == MINUS_EXPR);
495 0 : inv_ = TREE_OPERAND (t, 0);
496 0 : t = TREE_OPERAND (t, 1);
497 : }
498 0 : else if (is_gimple_min_invariant (TREE_OPERAND (t, 1)))
499 : {
500 0 : neg_ = false;
501 0 : inv_ = TREE_OPERAND (t, 1);
502 0 : t = TREE_OPERAND (t, 0);
503 : }
504 : else
505 : return NULL_TREE;
506 : }
507 : else
508 : {
509 : neg_ = false;
510 : inv_ = NULL_TREE;
511 : }
512 :
513 5342322 : if (TREE_CODE (t) == NEGATE_EXPR)
514 : {
515 0 : t = TREE_OPERAND (t, 0);
516 0 : neg_ = !neg_;
517 : }
518 :
519 5342322 : if (TREE_CODE (t) != SSA_NAME)
520 : return NULL_TREE;
521 :
522 0 : if (inv_ && TREE_OVERFLOW_P (inv_))
523 0 : inv_ = drop_tree_overflow (inv_);
524 :
525 0 : *neg = neg_;
526 0 : *inv = inv_;
527 0 : return t;
528 : }
529 :
530 : /* Compare two values VAL1 and VAL2. Return
531 :
532 : -2 if VAL1 and VAL2 cannot be compared at compile-time,
533 : -1 if VAL1 < VAL2,
534 : 0 if VAL1 == VAL2,
535 : +1 if VAL1 > VAL2, and
536 : +2 if VAL1 != VAL2
537 :
538 : This is similar to tree_int_cst_compare but supports pointer values
539 : and values that cannot be compared at compile time. */
540 :
541 : int
542 3007208 : compare_values (tree val1, tree val2)
543 : {
544 3007208 : if (val1 == val2)
545 : return 0;
546 :
547 : /* Below we rely on the fact that VAL1 and VAL2 are both pointers or
548 : both integers. */
549 2671161 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1))
550 : == POINTER_TYPE_P (TREE_TYPE (val2)));
551 :
552 : /* Convert the two values into the same type. This is needed because
553 : sizetype causes sign extension even for unsigned types. */
554 2671161 : if (!useless_type_conversion_p (TREE_TYPE (val1), TREE_TYPE (val2)))
555 0 : val2 = fold_convert (TREE_TYPE (val1), val2);
556 :
557 2671161 : const bool overflow_undefined
558 5336841 : = INTEGRAL_TYPE_P (TREE_TYPE (val1))
559 5336841 : && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1));
560 2671161 : tree inv1, inv2;
561 2671161 : bool neg1, neg2;
562 2671161 : tree sym1 = get_single_symbol (val1, &neg1, &inv1);
563 2671161 : tree sym2 = get_single_symbol (val2, &neg2, &inv2);
564 :
565 : /* If VAL1 and VAL2 are of the form '[-]NAME [+ CST]', return -1 or +1
566 : accordingly. If VAL1 and VAL2 don't use the same name, return -2. */
567 2671161 : if (sym1 && sym2)
568 : {
569 : /* Both values must use the same name with the same sign. */
570 0 : if (sym1 != sym2 || neg1 != neg2)
571 : return -2;
572 :
573 : /* [-]NAME + CST == [-]NAME + CST. */
574 0 : if (inv1 == inv2)
575 : return 0;
576 :
577 : /* If overflow is defined we cannot simplify more. */
578 0 : if (!overflow_undefined)
579 : return -2;
580 :
581 0 : if (!inv1)
582 0 : inv1 = build_int_cst (TREE_TYPE (val1), 0);
583 0 : if (!inv2)
584 0 : inv2 = build_int_cst (TREE_TYPE (val2), 0);
585 :
586 0 : return wi::cmp (wi::to_wide (inv1), wi::to_wide (inv2),
587 0 : TYPE_SIGN (TREE_TYPE (val1)));
588 : }
589 :
590 2671161 : const bool cst1 = is_gimple_min_invariant (val1);
591 2671161 : const bool cst2 = is_gimple_min_invariant (val2);
592 :
593 : /* If one is of the form '[-]NAME + CST' and the other is constant, then
594 : it might be possible to say something depending on the constants. */
595 2671161 : if ((sym1 && inv1 && cst2) || (sym2 && inv2 && cst1))
596 : {
597 0 : if (!overflow_undefined)
598 : return -2;
599 :
600 0 : const signop sgn = TYPE_SIGN (TREE_TYPE (val1));
601 0 : tree cst = cst1 ? val1 : val2;
602 0 : tree inv = cst1 ? inv2 : inv1;
603 :
604 : /* Compute the difference between the constants. If it overflows or
605 : underflows, this means that we can trivially compare the NAME with
606 : it and, consequently, the two values with each other. */
607 0 : wide_int diff = wi::to_wide (cst) - wi::to_wide (inv);
608 0 : if (wi::cmp (0, wi::to_wide (inv), sgn)
609 0 : != wi::cmp (diff, wi::to_wide (cst), sgn))
610 : {
611 0 : const int res = wi::cmp (wi::to_wide (cst), wi::to_wide (inv), sgn);
612 0 : return cst1 ? res : -res;
613 : }
614 :
615 : return -2;
616 0 : }
617 :
618 : /* We cannot say anything more for non-constants. */
619 2671161 : if (!cst1 || !cst2)
620 : return -2;
621 :
622 2671161 : if (!POINTER_TYPE_P (TREE_TYPE (val1)))
623 : {
624 : /* We cannot compare overflowed values. */
625 2671161 : if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
626 : return -2;
627 :
628 2671161 : if (TREE_CODE (val1) == INTEGER_CST
629 2671161 : && TREE_CODE (val2) == INTEGER_CST)
630 2671161 : return tree_int_cst_compare (val1, val2);
631 :
632 0 : if (poly_int_tree_p (val1) && poly_int_tree_p (val2))
633 : {
634 0 : if (known_eq (wi::to_poly_widest (val1),
635 : wi::to_poly_widest (val2)))
636 : return 0;
637 0 : if (known_lt (wi::to_poly_widest (val1),
638 : wi::to_poly_widest (val2)))
639 : return -1;
640 0 : if (known_gt (wi::to_poly_widest (val1),
641 : wi::to_poly_widest (val2)))
642 : return 1;
643 : }
644 :
645 0 : return -2;
646 : }
647 : else
648 : {
649 0 : if (TREE_CODE (val1) == INTEGER_CST && TREE_CODE (val2) == INTEGER_CST)
650 : {
651 : /* We cannot compare overflowed values. */
652 0 : if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
653 : return -2;
654 :
655 0 : return tree_int_cst_compare (val1, val2);
656 : }
657 :
658 : /* First see if VAL1 and VAL2 are not the same. */
659 0 : if (operand_equal_p (val1, val2, 0))
660 : return 0;
661 :
662 : /* If VAL1 is a lower address than VAL2, return -1. */
663 0 : tree t = fold_binary_to_constant (LT_EXPR, boolean_type_node, val1, val2);
664 0 : if (t && integer_onep (t))
665 : return -1;
666 :
667 : /* If VAL1 is a higher address than VAL2, return +1. */
668 0 : t = fold_binary_to_constant (LT_EXPR, boolean_type_node, val2, val1);
669 0 : if (t && integer_onep (t))
670 : return 1;
671 :
672 : /* If VAL1 is different than VAL2, return +2. */
673 0 : t = fold_binary_to_constant (NE_EXPR, boolean_type_node, val1, val2);
674 0 : if (t && integer_onep (t))
675 0 : return 2;
676 :
677 : return -2;
678 : }
679 : }
680 :
681 : /* Helper for overflow_comparison_p
682 :
683 : OP0 CODE OP1 is a comparison. Examine the comparison and potentially
684 : OP1's defining statement to see if it ultimately has the form
685 : OP0 CODE (OP0 PLUS INTEGER_CST)
686 :
687 : If so, return TRUE indicating this is an overflow test and store into
688 : *NEW_CST an updated constant that can be used in a narrowed range test.
689 :
690 : REVERSED indicates if the comparison was originally:
691 :
692 : OP1 CODE' OP0.
693 :
694 : This affects how we build the updated constant. */
695 :
696 : static bool
697 41017749 : overflow_comparison_p_1 (enum tree_code code, tree op0, tree op1,
698 : bool reversed, tree *new_cst)
699 : {
700 : /* See if this is a relational operation between two SSA_NAMES with
701 : unsigned, overflow wrapping values. If so, check it more deeply. */
702 41017749 : if ((code == LT_EXPR || code == LE_EXPR
703 34859435 : || code == GE_EXPR || code == GT_EXPR)
704 9701739 : && TREE_CODE (op0) == SSA_NAME
705 6809735 : && TREE_CODE (op1) == SSA_NAME
706 3917899 : && INTEGRAL_TYPE_P (TREE_TYPE (op0))
707 3554085 : && TYPE_UNSIGNED (TREE_TYPE (op0))
708 42479442 : && TYPE_OVERFLOW_WRAPS (TREE_TYPE (op0)))
709 : {
710 1461693 : gimple *op1_def = SSA_NAME_DEF_STMT (op1);
711 :
712 : /* Now look at the defining statement of OP1 to see if it adds
713 : or subtracts a nonzero constant from another operand. */
714 1461693 : if (op1_def
715 1461693 : && is_gimple_assign (op1_def)
716 1112401 : && gimple_assign_rhs_code (op1_def) == PLUS_EXPR
717 320314 : && TREE_CODE (gimple_assign_rhs2 (op1_def)) == INTEGER_CST
718 1639413 : && !integer_zerop (gimple_assign_rhs2 (op1_def)))
719 : {
720 177720 : tree target = gimple_assign_rhs1 (op1_def);
721 :
722 : /* If we did not find our target SSA_NAME, then this is not
723 : an overflow test. */
724 177720 : if (op0 != target)
725 : return false;
726 :
727 1163 : tree type = TREE_TYPE (op0);
728 1163 : wide_int max = wi::max_value (TYPE_PRECISION (type), UNSIGNED);
729 1163 : tree inc = gimple_assign_rhs2 (op1_def);
730 1163 : if (reversed)
731 208 : *new_cst = wide_int_to_tree (type, max + wi::to_wide (inc));
732 : else
733 955 : *new_cst = wide_int_to_tree (type, max - wi::to_wide (inc));
734 1163 : return true;
735 1163 : }
736 : }
737 : return false;
738 : }
739 :
740 : /* OP0 CODE OP1 is a comparison. Examine the comparison and potentially
741 : OP1's defining statement to see if it ultimately has the form
742 : OP0 CODE (OP0 PLUS INTEGER_CST)
743 :
744 : If so, return TRUE indicating this is an overflow test and store into
745 : *NEW_CST an updated constant that can be used in a narrowed range test.
746 :
747 : These statements are left as-is in the IL to facilitate discovery of
748 : {ADD,SUB}_OVERFLOW sequences later in the optimizer pipeline. But
749 : the alternate range representation is often useful within VRP. */
750 :
751 : bool
752 20509352 : overflow_comparison_p (tree_code code, tree name, tree val, tree *new_cst)
753 : {
754 20509352 : if (overflow_comparison_p_1 (code, name, val, false, new_cst))
755 : return true;
756 20508397 : return overflow_comparison_p_1 (swap_tree_comparison (code), val, name,
757 20508397 : true, new_cst);
758 : }
759 :
760 : /* Searches the case label vector VEC for the index *IDX of the CASE_LABEL
761 : that includes the value VAL. The search is restricted to the range
762 : [START_IDX, n - 1] where n is the size of VEC.
763 :
764 : If there is a CASE_LABEL for VAL, its index is placed in IDX and true is
765 : returned.
766 :
767 : If there is no CASE_LABEL for VAL and there is one that is larger than VAL,
768 : it is placed in IDX and false is returned.
769 :
770 : If VAL is larger than any CASE_LABEL, n is placed on IDX and false is
771 : returned. */
772 :
773 : bool
774 141328 : find_case_label_index (gswitch *stmt, size_t start_idx, tree val, size_t *idx)
775 : {
776 141328 : size_t n = gimple_switch_num_labels (stmt);
777 141328 : size_t low, high;
778 :
779 : /* Find case label for minimum of the value range or the next one.
780 : At each iteration we are searching in [low, high - 1]. */
781 :
782 587958 : for (low = start_idx, high = n; high != low; )
783 : {
784 359924 : tree t;
785 359924 : int cmp;
786 : /* Note that i != high, so we never ask for n. */
787 359924 : size_t i = (high + low) / 2;
788 359924 : t = gimple_switch_label (stmt, i);
789 :
790 : /* Cache the result of comparing CASE_LOW and val. */
791 359924 : cmp = tree_int_cst_compare (CASE_LOW (t), val);
792 :
793 359924 : if (cmp == 0)
794 : {
795 : /* Ranges cannot be empty. */
796 53006 : *idx = i;
797 53006 : return true;
798 : }
799 306918 : else if (cmp > 0)
800 : high = i;
801 : else
802 : {
803 131759 : low = i + 1;
804 131759 : if (CASE_HIGH (t) != NULL
805 131759 : && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
806 : {
807 1616 : *idx = i;
808 1616 : return true;
809 : }
810 : }
811 : }
812 :
813 86706 : *idx = high;
814 86706 : return false;
815 : }
816 :
817 : /* Searches the case label vector VEC for the range of CASE_LABELs that is used
818 : for values between MIN and MAX. The first index is placed in MIN_IDX. The
819 : last index is placed in MAX_IDX. If the range of CASE_LABELs is empty
820 : then MAX_IDX < MIN_IDX.
821 : Returns true if the default label is not needed. */
822 :
823 : bool
824 70664 : find_case_label_range (gswitch *stmt, tree min, tree max, size_t *min_idx,
825 : size_t *max_idx)
826 : {
827 70664 : size_t i, j;
828 70664 : bool min_take_default = !find_case_label_index (stmt, 1, min, &i);
829 70664 : bool max_take_default = !find_case_label_index (stmt, i, max, &j);
830 :
831 70664 : if (i == j
832 : && min_take_default
833 7952 : && max_take_default)
834 : {
835 : /* Only the default case label reached.
836 : Return an empty range. */
837 3199 : *min_idx = 1;
838 3199 : *max_idx = 0;
839 3199 : return false;
840 : }
841 : else
842 : {
843 67465 : bool take_default = min_take_default || max_take_default;
844 67465 : tree low, high;
845 67465 : size_t k;
846 :
847 67465 : if (max_take_default)
848 45783 : j--;
849 :
850 : /* If the case label range is continuous, we do not need
851 : the default case label. Verify that. */
852 67465 : high = CASE_LOW (gimple_switch_label (stmt, i));
853 67465 : if (CASE_HIGH (gimple_switch_label (stmt, i)))
854 3104 : high = CASE_HIGH (gimple_switch_label (stmt, i));
855 198377 : for (k = i + 1; k <= j; ++k)
856 : {
857 170082 : low = CASE_LOW (gimple_switch_label (stmt, k));
858 170082 : if (!integer_onep (int_const_binop (MINUS_EXPR, low, high)))
859 : {
860 : take_default = true;
861 : break;
862 : }
863 130912 : high = low;
864 130912 : if (CASE_HIGH (gimple_switch_label (stmt, k)))
865 5623 : high = CASE_HIGH (gimple_switch_label (stmt, k));
866 : }
867 :
868 67465 : *min_idx = i;
869 67465 : *max_idx = j;
870 67465 : return !take_default;
871 : }
872 : }
873 :
874 : /* Given a SWITCH_STMT, return the case label that encompasses the
875 : known possible values for the switch operand. RANGE_OF_OP is a
876 : range for the known values of the switch operand. */
877 :
878 : tree
879 92101 : find_case_label_range (gswitch *switch_stmt, const irange *range_of_op)
880 : {
881 92101 : if (range_of_op->undefined_p ()
882 92101 : || range_of_op->varying_p ())
883 : return NULL_TREE;
884 :
885 70664 : size_t i, j;
886 70664 : tree op = gimple_switch_index (switch_stmt);
887 70664 : tree type = TREE_TYPE (op);
888 70664 : tree tmin = wide_int_to_tree (type, range_of_op->lower_bound ());
889 70664 : tree tmax = wide_int_to_tree (type, range_of_op->upper_bound ());
890 70664 : find_case_label_range (switch_stmt, tmin, tmax, &i, &j);
891 70664 : if (i == j)
892 : {
893 : /* Look for exactly one label that encompasses the range of
894 : the operand. */
895 6309 : tree label = gimple_switch_label (switch_stmt, i);
896 6309 : tree case_high
897 6309 : = CASE_HIGH (label) ? CASE_HIGH (label) : CASE_LOW (label);
898 6309 : wide_int wlow = wi::to_wide (CASE_LOW (label));
899 6309 : wide_int whigh = wi::to_wide (case_high);
900 6309 : int_range_max label_range (TREE_TYPE (case_high), wlow, whigh);
901 6309 : if (!types_compatible_p (label_range.type (), range_of_op->type ()))
902 10 : range_cast (label_range, range_of_op->type ());
903 6309 : label_range.intersect (*range_of_op);
904 6309 : if (label_range == *range_of_op)
905 4230 : return label;
906 6309 : }
907 64355 : else if (i > j)
908 : {
909 : /* If there are no labels at all, take the default. */
910 3199 : return gimple_switch_label (switch_stmt, 0);
911 : }
912 : else
913 : {
914 : /* Otherwise, there are various labels that can encompass
915 : the range of operand. In which case, see if the range of
916 : the operand is entirely *outside* the bounds of all the
917 : (non-default) case labels. If so, take the default. */
918 61156 : unsigned n = gimple_switch_num_labels (switch_stmt);
919 61156 : tree min_label = gimple_switch_label (switch_stmt, 1);
920 61156 : tree max_label = gimple_switch_label (switch_stmt, n - 1);
921 61156 : tree case_high = CASE_HIGH (max_label);
922 61156 : if (!case_high)
923 57871 : case_high = CASE_LOW (max_label);
924 61156 : int_range_max label_range (TREE_TYPE (CASE_LOW (min_label)),
925 122312 : wi::to_wide (CASE_LOW (min_label)),
926 122312 : wi::to_wide (case_high));
927 61156 : if (!types_compatible_p (label_range.type (), range_of_op->type ()))
928 29 : range_cast (label_range, range_of_op->type ());
929 61156 : label_range.intersect (*range_of_op);
930 61156 : if (label_range.undefined_p ())
931 151 : return gimple_switch_label (switch_stmt, 0);
932 61156 : }
933 : return NULL_TREE;
934 : }
935 :
936 : struct case_info
937 : {
938 : tree expr;
939 : basic_block bb;
940 : };
941 :
942 : // This is a ranger based folder which continues to use the dominator
943 : // walk to access the substitute and fold machinery. Ranges are calculated
944 : // on demand.
945 :
946 : class rvrp_folder : public substitute_and_fold_engine
947 : {
948 : public:
949 :
950 4401435 : rvrp_folder (gimple_ranger *r, bool all)
951 : : substitute_and_fold_engine (),
952 4401435 : m_unreachable (*r, all),
953 4401435 : m_simplifier (r, r->non_executable_edge_flag)
954 : {
955 4401435 : m_ranger = r;
956 4401435 : m_last_bb_stmt = NULL;
957 4401435 : }
958 :
959 124164353 : tree value_of_expr (tree name, gimple *s = NULL) override
960 : {
961 : // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
962 124164353 : if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
963 : return NULL_TREE;
964 124151173 : if (!value_range::supports_type_p (TREE_TYPE (name)))
965 : return NULL_TREE;
966 :
967 120923961 : value_range r (TREE_TYPE (name));
968 120923961 : if (!m_ranger->range_of_expr (r, name, s))
969 : return NULL_TREE;
970 :
971 : // A constant used in an unreachable block often returns as UNDEFINED.
972 : // If the result is undefined, check the global value for a constant.
973 120923961 : if (r.undefined_p ())
974 225051 : range_of_expr (r, name);
975 :
976 120923961 : tree ret;
977 120923961 : if (r.singleton_p (&ret))
978 885596 : return ret;
979 : else
980 120038365 : ret = NULL_TREE;
981 120038365 : if (is_a <prange> (r))
982 : {
983 54009609 : prange &p = as_a <prange> (r);
984 54009609 : ret = p.pt_invariant ();
985 : // A const points has to be gimple_min_invariant.
986 54009609 : gcc_checking_assert (!ret || is_gimple_min_invariant (ret));
987 : }
988 :
989 120038365 : return ret;
990 120923961 : }
991 :
992 25174225 : tree value_on_edge (edge e, tree name) override
993 : {
994 : // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
995 25174225 : if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
996 : return NULL;
997 25148050 : if (!value_range::supports_type_p (TREE_TYPE (name)))
998 : return NULL_TREE;
999 :
1000 24868600 : value_range r (TREE_TYPE (name));
1001 24868600 : if (!m_ranger->range_on_edge (r, e, name))
1002 : return NULL_TREE;
1003 :
1004 : // A constant used in an unreachable block often returns as UNDEFINED.
1005 : // If the result is undefined, check the global value for a constant.
1006 24868600 : if (r.undefined_p ())
1007 280805 : range_of_expr (r, name);
1008 :
1009 24868600 : tree ret;
1010 24868600 : if (r.singleton_p (&ret))
1011 333833 : return ret;
1012 : else
1013 24534767 : ret = NULL_TREE;
1014 24534767 : if (is_a <prange> (r))
1015 : {
1016 7809966 : prange &p = as_a <prange> (r);
1017 7809966 : ret = p.pt_invariant ();
1018 : // A const points has to be gimple_min_invariant.
1019 7809966 : gcc_checking_assert (!ret || is_gimple_min_invariant (ret));
1020 : }
1021 :
1022 24534767 : return ret;
1023 24868600 : }
1024 :
1025 49017632 : tree value_of_stmt (gimple *s, tree name = NULL) override
1026 : {
1027 : // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
1028 49017632 : if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1029 : return NULL;
1030 49015632 : return m_ranger->value_of_stmt (s, name);
1031 : }
1032 :
1033 38109169 : void pre_fold_bb (basic_block bb) override
1034 : {
1035 53015754 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1036 14906585 : gsi_next (&gsi))
1037 14906585 : m_ranger->register_inferred_ranges (gsi.phi ());
1038 38109169 : m_last_bb_stmt = last_nondebug_stmt (bb);
1039 38109169 : }
1040 :
1041 259617072 : void pre_fold_stmt (gimple *stmt) override
1042 : {
1043 : // If this is the last stmt and there are inferred ranges, reparse the
1044 : // block for transitive inferred ranges that occur earlier in the block.
1045 259617072 : if (stmt == m_last_bb_stmt)
1046 : {
1047 31718820 : m_ranger->register_transitive_inferred_ranges (gimple_bb (stmt));
1048 : // Also check for builtin_unreachable calls.
1049 31718820 : if (cfun->after_inlining && gimple_code (stmt) == GIMPLE_COND)
1050 8680710 : m_unreachable.maybe_register (stmt);
1051 : }
1052 259617072 : }
1053 :
1054 259327328 : bool fold_stmt (gimple_stmt_iterator *gsi) override
1055 : {
1056 259327328 : bool ret = m_simplifier.simplify (gsi);
1057 259327328 : if (!ret)
1058 258712994 : ret = m_ranger->fold_stmt (gsi, follow_single_use_edges);
1059 259327328 : m_ranger->register_inferred_ranges (gsi_stmt (*gsi));
1060 259327328 : return ret;
1061 : }
1062 :
1063 : remove_unreachable m_unreachable;
1064 : private:
1065 : DISABLE_COPY_AND_ASSIGN (rvrp_folder);
1066 : gimple_ranger *m_ranger;
1067 : simplify_using_ranges m_simplifier;
1068 : gimple *m_last_bb_stmt;
1069 : };
1070 :
1071 : /* Main entry point for a VRP pass using just ranger. This can be called
1072 : from anywhere to perform a VRP pass, including from EVRP. */
1073 :
1074 : unsigned int
1075 4401435 : execute_ranger_vrp (struct function *fun, bool final_p)
1076 : {
1077 4401435 : loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
1078 4401435 : rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1079 4401435 : scev_initialize ();
1080 4401435 : calculate_dominance_info (CDI_DOMINATORS);
1081 :
1082 4401435 : set_all_edges_as_executable (fun);
1083 4401435 : gimple_ranger *ranger = enable_ranger (fun, false);
1084 4401435 : phi_analysis (*ranger);
1085 4401435 : rvrp_folder folder (ranger, final_p);
1086 4401435 : folder.substitute_and_fold ();
1087 : // Ensure the cache in SCEV has been cleared before processing
1088 : // globals to be removed.
1089 4401435 : scev_reset ();
1090 : // Remove tagged builtin-unreachable and maybe update globals.
1091 4401435 : folder.m_unreachable.remove_and_update_globals ();
1092 4401435 : if (dump_file && (dump_flags & TDF_DETAILS))
1093 48 : ranger->dump (dump_file);
1094 :
1095 4401435 : if (value_range::supports_type_p (TREE_TYPE
1096 : (TREE_TYPE (current_function_decl)))
1097 1883906 : && flag_ipa_vrp
1098 6284535 : && !lookup_attribute ("noipa", DECL_ATTRIBUTES (current_function_decl)))
1099 : {
1100 1849850 : edge e;
1101 1849850 : edge_iterator ei;
1102 1849850 : bool found = false;
1103 1849850 : value_range return_range (TREE_TYPE (TREE_TYPE (current_function_decl)));
1104 3673277 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
1105 5469431 : if (greturn *ret = dyn_cast <greturn *> (*gsi_last_bb (e->src)))
1106 : {
1107 1822577 : tree retval = gimple_return_retval (ret);
1108 1822577 : if (!retval)
1109 : {
1110 10850 : return_range.set_varying (TREE_TYPE (TREE_TYPE (current_function_decl)));
1111 10850 : found = true;
1112 10850 : continue;
1113 : }
1114 1811727 : value_range r (TREE_TYPE (retval));
1115 1811727 : if (ranger->range_of_expr (r, retval, ret)
1116 1811727 : && !r.undefined_p ()
1117 3622763 : && !r.varying_p ())
1118 : {
1119 754828 : if (!found)
1120 752603 : return_range = r;
1121 : else
1122 2225 : return_range.union_ (r);
1123 : }
1124 : else
1125 1056899 : return_range.set_varying (TREE_TYPE (retval));
1126 1811727 : found = true;
1127 1811727 : }
1128 1849850 : if (found && !return_range.varying_p ())
1129 : {
1130 752540 : ipa_record_return_value_range (return_range);
1131 1379034 : if (POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (current_function_decl)))
1132 267496 : && !return_range.contains_zero_p ()
1133 1011837 : && cgraph_node::get (current_function_decl)
1134 259297 : ->add_detected_attribute ("returns_nonnull"))
1135 229295 : warn_function_returns_nonnull (current_function_decl);
1136 : }
1137 1849850 : }
1138 :
1139 4401435 : disable_ranger (fun);
1140 4401435 : scev_finalize ();
1141 4401435 : loop_optimizer_finalize ();
1142 8802870 : return 0;
1143 4401435 : }
1144 :
1145 : // Implement a Fast VRP folder. Not quite as effective but faster.
1146 :
1147 : class fvrp_folder : public substitute_and_fold_engine
1148 : {
1149 : public:
1150 9 : fvrp_folder (dom_ranger *dr, bool final_p) : substitute_and_fold_engine (),
1151 9 : m_simplifier (dr)
1152 : {
1153 9 : m_dom_ranger = dr;
1154 9 : if (final_p)
1155 3 : m_unreachable = new remove_unreachable (*dr, final_p);
1156 : else
1157 6 : m_unreachable = NULL;
1158 9 : }
1159 :
1160 9 : ~fvrp_folder () { }
1161 :
1162 579 : tree value_of_expr (tree name, gimple *s = NULL) override
1163 : {
1164 : // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
1165 579 : if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1166 : return NULL;
1167 579 : return m_dom_ranger->value_of_expr (name, s);
1168 : }
1169 :
1170 27 : tree value_on_edge (edge e, tree name) override
1171 : {
1172 : // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
1173 27 : if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1174 : return NULL;
1175 27 : return m_dom_ranger->value_on_edge (e, name);
1176 : }
1177 :
1178 399 : tree value_of_stmt (gimple *s, tree name = NULL) override
1179 : {
1180 : // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
1181 399 : if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1182 : return NULL;
1183 399 : return m_dom_ranger->value_of_stmt (s, name);
1184 : }
1185 :
1186 37 : void pre_fold_bb (basic_block bb) override
1187 : {
1188 37 : m_dom_ranger->pre_bb (bb);
1189 : // Now process the PHIs in advance.
1190 37 : gphi_iterator psi = gsi_start_phis (bb);
1191 57 : for ( ; !gsi_end_p (psi); gsi_next (&psi))
1192 : {
1193 20 : tree name = gimple_range_ssa_p (PHI_RESULT (psi.phi ()));
1194 20 : if (name)
1195 : {
1196 9 : value_range vr(TREE_TYPE (name));
1197 9 : m_dom_ranger->range_of_stmt (vr, psi.phi (), name);
1198 9 : }
1199 : }
1200 37 : }
1201 :
1202 37 : void post_fold_bb (basic_block bb) override
1203 : {
1204 37 : m_dom_ranger->post_bb (bb);
1205 37 : }
1206 :
1207 431 : void pre_fold_stmt (gimple *s) override
1208 : {
1209 : // Ensure range_of_stmt has been called.
1210 431 : tree type = gimple_range_type (s);
1211 431 : if (type)
1212 : {
1213 412 : value_range vr(type);
1214 412 : m_dom_ranger->range_of_stmt (vr, s);
1215 412 : }
1216 431 : if (m_unreachable && gimple_code (s) == GIMPLE_COND)
1217 9 : m_unreachable->maybe_register (s);
1218 :
1219 431 : }
1220 :
1221 422 : bool fold_stmt (gimple_stmt_iterator *gsi) override
1222 : {
1223 422 : bool ret = m_simplifier.simplify (gsi);
1224 422 : if (!ret)
1225 419 : ret = ::fold_stmt (gsi, follow_single_use_edges);
1226 422 : return ret;
1227 : }
1228 :
1229 : remove_unreachable *m_unreachable;
1230 : private:
1231 : DISABLE_COPY_AND_ASSIGN (fvrp_folder);
1232 : simplify_using_ranges m_simplifier;
1233 : dom_ranger *m_dom_ranger;
1234 : };
1235 :
1236 :
1237 : // Main entry point for a FAST VRP pass using a dom ranger.
1238 :
1239 : unsigned int
1240 9 : execute_fast_vrp (struct function *fun, bool final_p)
1241 : {
1242 9 : calculate_dominance_info (CDI_DOMINATORS);
1243 9 : dom_ranger dr;
1244 : // Create a relation oracle without transitives. It will automatically
1245 : // be destroyed when the destructor for 'dr' runs.
1246 9 : dr.create_relation_oracle (false);
1247 9 : fvrp_folder folder (&dr, final_p);
1248 :
1249 9 : set_all_edges_as_executable (fun);
1250 : // Make DR the current range_query.
1251 9 : range_query *saved = set_range_query (fun, &dr);
1252 :
1253 9 : folder.substitute_and_fold ();
1254 9 : if (folder.m_unreachable)
1255 3 : folder.m_unreachable->remove ();
1256 :
1257 9 : range_query *q = set_range_query (fun, saved);
1258 9 : gcc_checking_assert (q == &dr);
1259 18 : return 0;
1260 9 : }
1261 :
1262 : namespace {
1263 :
1264 : const pass_data pass_data_vrp =
1265 : {
1266 : GIMPLE_PASS, /* type */
1267 : "vrp", /* name */
1268 : OPTGROUP_NONE, /* optinfo_flags */
1269 : TV_TREE_VRP, /* tv_id */
1270 : PROP_ssa, /* properties_required */
1271 : 0, /* properties_provided */
1272 : 0, /* properties_destroyed */
1273 : 0, /* todo_flags_start */
1274 : ( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */
1275 : };
1276 :
1277 : const pass_data pass_data_early_vrp =
1278 : {
1279 : GIMPLE_PASS, /* type */
1280 : "evrp", /* name */
1281 : OPTGROUP_NONE, /* optinfo_flags */
1282 : TV_TREE_EARLY_VRP, /* tv_id */
1283 : PROP_ssa, /* properties_required */
1284 : 0, /* properties_provided */
1285 : 0, /* properties_destroyed */
1286 : 0, /* todo_flags_start */
1287 : ( TODO_cleanup_cfg | TODO_update_ssa ),
1288 : };
1289 :
1290 : const pass_data pass_data_fast_vrp =
1291 : {
1292 : GIMPLE_PASS, /* type */
1293 : "fvrp", /* name */
1294 : OPTGROUP_NONE, /* optinfo_flags */
1295 : TV_TREE_FAST_VRP, /* tv_id */
1296 : PROP_ssa, /* properties_required */
1297 : 0, /* properties_provided */
1298 : 0, /* properties_destroyed */
1299 : 0, /* todo_flags_start */
1300 : ( TODO_cleanup_cfg | TODO_update_ssa ),
1301 : };
1302 :
1303 :
1304 : class pass_vrp : public gimple_opt_pass
1305 : {
1306 : public:
1307 883761 : pass_vrp (gcc::context *ctxt, const pass_data &data_)
1308 1767522 : : gimple_opt_pass (data_, ctxt), data (data_), final_p (false)
1309 : { }
1310 :
1311 : /* opt_pass methods: */
1312 294587 : opt_pass * clone () final override
1313 294587 : { return new pass_vrp (m_ctxt, data); }
1314 589174 : void set_pass_param (unsigned int n, bool param) final override
1315 : {
1316 589174 : gcc_assert (n == 0);
1317 589174 : final_p = param;
1318 589174 : }
1319 4669708 : bool gate (function *) final override { return flag_tree_vrp != 0; }
1320 4401444 : unsigned int execute (function *fun) final override
1321 : {
1322 : // Check for fast vrp.
1323 4401444 : bool use_fvrp = (&data == &pass_data_fast_vrp);
1324 4401444 : if (!use_fvrp && last_basic_block_for_fn (fun) > param_vrp_block_limit)
1325 : {
1326 9 : use_fvrp = true;
1327 9 : warning (OPT_Wdisabled_optimization,
1328 : "using fast VRP algorithm; %d basic blocks"
1329 : " exceeds %<--param=vrp-block-limit=%d%> limit",
1330 : n_basic_blocks_for_fn (fun),
1331 : param_vrp_block_limit);
1332 : }
1333 4401444 : if (use_fvrp)
1334 9 : return execute_fast_vrp (fun, final_p);
1335 4401435 : return execute_ranger_vrp (fun, final_p);
1336 : }
1337 :
1338 : private:
1339 : const pass_data &data;
1340 : bool final_p;
1341 : }; // class pass_vrp
1342 : } // anon namespace
1343 :
1344 : gimple_opt_pass *
1345 294587 : make_pass_vrp (gcc::context *ctxt)
1346 : {
1347 294587 : return new pass_vrp (ctxt, pass_data_vrp);
1348 : }
1349 :
1350 : gimple_opt_pass *
1351 294587 : make_pass_early_vrp (gcc::context *ctxt)
1352 : {
1353 294587 : return new pass_vrp (ctxt, pass_data_early_vrp);
1354 : }
1355 :
1356 : gimple_opt_pass *
1357 0 : make_pass_fast_vrp (gcc::context *ctxt)
1358 : {
1359 0 : return new pass_vrp (ctxt, pass_data_fast_vrp);
1360 : }
|
