LCOV - code coverage report
Current view: top level - gcc - vr-values.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 1920 2037 94.3 %
Date: 2020-03-28 11:57:23 Functions: 63 64 98.4 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Support routines for Value Range Propagation (VRP).
       2                 :            :    Copyright (C) 2005-2020 Free Software Foundation, Inc.
       3                 :            : 
       4                 :            : This file is part of GCC.
       5                 :            : 
       6                 :            : GCC is free software; you can redistribute it and/or modify
       7                 :            : it under the terms of the GNU General Public License as published by
       8                 :            : the Free Software Foundation; either version 3, or (at your option)
       9                 :            : any later version.
      10                 :            : 
      11                 :            : GCC is distributed in the hope that it will be useful,
      12                 :            : but WITHOUT ANY WARRANTY; without even the implied warranty of
      13                 :            : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      14                 :            : GNU General Public License for more details.
      15                 :            : 
      16                 :            : You should have received a copy of the GNU General Public License
      17                 :            : along with GCC; see the file COPYING3.  If not see
      18                 :            : <http://www.gnu.org/licenses/>.  */
      19                 :            : 
      20                 :            : #include "config.h"
      21                 :            : #include "system.h"
      22                 :            : #include "coretypes.h"
      23                 :            : #include "backend.h"
      24                 :            : #include "insn-codes.h"
      25                 :            : #include "tree.h"
      26                 :            : #include "gimple.h"
      27                 :            : #include "ssa.h"
      28                 :            : #include "optabs-tree.h"
      29                 :            : #include "gimple-pretty-print.h"
      30                 :            : #include "diagnostic-core.h"
      31                 :            : #include "flags.h"
      32                 :            : #include "fold-const.h"
      33                 :            : #include "calls.h"
      34                 :            : #include "cfganal.h"
      35                 :            : #include "gimple-fold.h"
      36                 :            : #include "gimple-iterator.h"
      37                 :            : #include "tree-cfg.h"
      38                 :            : #include "tree-ssa-loop-niter.h"
      39                 :            : #include "tree-ssa-loop.h"
      40                 :            : #include "intl.h"
      41                 :            : #include "cfgloop.h"
      42                 :            : #include "tree-scalar-evolution.h"
      43                 :            : #include "tree-ssa-propagate.h"
      44                 :            : #include "tree-chrec.h"
      45                 :            : #include "omp-general.h"
      46                 :            : #include "case-cfn-macros.h"
      47                 :            : #include "alloc-pool.h"
      48                 :            : #include "attribs.h"
      49                 :            : #include "range.h"
      50                 :            : #include "vr-values.h"
      51                 :            : #include "cfghooks.h"
      52                 :            : #include "range-op.h"
      53                 :            : 
      54                 :            : /* Set value range VR to a non-negative range of type TYPE.  */
      55                 :            : 
      56                 :            : static inline void
      57                 :   17385700 : set_value_range_to_nonnegative (value_range_equiv *vr, tree type)
      58                 :            : {
      59                 :   17385700 :   tree zero = build_int_cst (type, 0);
      60                 :   17385700 :   vr->update (zero, vrp_val_max (type));
      61                 :   17385700 : }
      62                 :            : 
      63                 :            : /* Set value range VR to a range of a truthvalue of type TYPE.  */
      64                 :            : 
      65                 :            : static inline void
      66                 :    3568720 : set_value_range_to_truthvalue (value_range_equiv *vr, tree type)
      67                 :            : {
      68                 :    3568720 :   if (TYPE_PRECISION (type) == 1)
      69                 :    3568720 :     vr->set_varying (type);
      70                 :            :   else
      71                 :          0 :     vr->update (build_int_cst (type, 0), build_int_cst (type, 1));
      72                 :    3568720 : }
      73                 :            : 
      74                 :            : /* Return the lattice entry for VAR or NULL if it doesn't exist or cannot
      75                 :            :    be initialized.  */
      76                 :            : 
      77                 :            : value_range_equiv *
      78                 : 1281530000 : vr_values::get_lattice_entry (const_tree var)
      79                 :            : {
      80                 : 1281530000 :   value_range_equiv *vr;
      81                 : 1281530000 :   tree sym;
      82                 : 1281530000 :   unsigned ver = SSA_NAME_VERSION (var);
      83                 :            : 
      84                 :            :   /* If we query the entry for a new SSA name avoid reallocating the lattice
      85                 :            :      since we should get here at most from the substitute-and-fold stage which
      86                 :            :      will never try to change values.  */
      87                 : 1281530000 :   if (ver >= num_vr_values)
      88                 :            :     return NULL;
      89                 :            : 
      90                 : 1281530000 :   vr = vr_value[ver];
      91                 : 1281530000 :   if (vr)
      92                 :            :     return vr;
      93                 :            : 
      94                 :            :   /* Create a default value range.  */
      95                 :  107796000 :   vr_value[ver] = vr = vrp_value_range_pool.allocate ();
      96                 :            : 
      97                 :            :   /* After propagation finished return varying.  */
      98                 :  107796000 :   if (values_propagated)
      99                 :            :     {
     100                 :   20146400 :       vr->set_varying (TREE_TYPE (var));
     101                 :   20146400 :       return vr;
     102                 :            :     }
     103                 :            : 
     104                 :   87649800 :   vr->set_undefined ();
     105                 :            : 
     106                 :            :   /* If VAR is a default definition of a parameter, the variable can
     107                 :            :      take any value in VAR's type.  */
     108                 :   87649800 :   if (SSA_NAME_IS_DEFAULT_DEF (var))
     109                 :            :     {
     110                 :    5668010 :       sym = SSA_NAME_VAR (var);
     111                 :    5668010 :       if (TREE_CODE (sym) == PARM_DECL)
     112                 :            :         {
     113                 :            :           /* Try to use the "nonnull" attribute to create ~[0, 0]
     114                 :            :              anti-ranges for pointers.  Note that this is only valid with
     115                 :            :              default definitions of PARM_DECLs.  */
     116                 :    8084250 :           if (POINTER_TYPE_P (TREE_TYPE (sym))
     117                 :    6119180 :               && (nonnull_arg_p (sym)
     118                 :    1673400 :                   || get_ptr_nonnull (var)))
     119                 :            :             {
     120                 :    1729620 :               vr->set_nonzero (TREE_TYPE (sym));
     121                 :    1729620 :               vr->equiv_clear ();
     122                 :            :             }
     123                 :    3605220 :           else if (INTEGRAL_TYPE_P (TREE_TYPE (sym)))
     124                 :            :             {
     125                 :    1651210 :               get_range_info (var, *vr);
     126                 :    1651210 :               if (vr->undefined_p ())
     127                 :          0 :                 vr->set_varying (TREE_TYPE (sym));
     128                 :            :             }
     129                 :            :           else
     130                 :    1954010 :             vr->set_varying (TREE_TYPE (sym));
     131                 :            :         }
     132                 :     333171 :       else if (TREE_CODE (sym) == RESULT_DECL
     133                 :     333171 :                && DECL_BY_REFERENCE (sym))
     134                 :            :         {
     135                 :      46916 :           vr->set_nonzero (TREE_TYPE (sym));
     136                 :      46916 :           vr->equiv_clear ();
     137                 :            :         }
     138                 :            :     }
     139                 :            : 
     140                 :            :   return vr;
     141                 :            : }
     142                 :            : 
     143                 :            : /* Return value range information for VAR.
     144                 :            : 
     145                 :            :    If we have no values ranges recorded (ie, VRP is not running), then
     146                 :            :    return NULL.  Otherwise create an empty range if none existed for VAR.  */
     147                 :            : 
     148                 :            : const value_range_equiv *
     149                 : 1188550000 : vr_values::get_value_range (const_tree var)
     150                 :            : {
     151                 :            :   /* If we have no recorded ranges, then return NULL.  */
     152                 : 1188550000 :   if (!vr_value)
     153                 :            :     return NULL;
     154                 :            : 
     155                 : 1188550000 :   value_range_equiv *vr = get_lattice_entry (var);
     156                 :            : 
     157                 :            :   /* Reallocate the lattice if needed.  */
     158                 : 1188550000 :   if (!vr)
     159                 :            :     {
     160                 :          0 :       unsigned int old_sz = num_vr_values;
     161                 :          0 :       num_vr_values = num_ssa_names + num_ssa_names / 10;
     162                 :          0 :       vr_value = XRESIZEVEC (value_range_equiv *, vr_value, num_vr_values);
     163                 :          0 :       for ( ; old_sz < num_vr_values; old_sz++)
     164                 :          0 :         vr_value [old_sz] = NULL;
     165                 :            : 
     166                 :            :       /* Now that the lattice has been resized, we should never fail.  */
     167                 :          0 :       vr = get_lattice_entry (var);
     168                 :          0 :       gcc_assert (vr);
     169                 :            :     }
     170                 :            : 
     171                 :            :   return vr;
     172                 :            : }
     173                 :            : 
     174                 :            : /* Set the lattice entry for DEF to VARYING.  */
     175                 :            : 
     176                 :            : void
     177                 :   36294900 : vr_values::set_def_to_varying (const_tree def)
     178                 :            : {
     179                 :   36294900 :   value_range_equiv *vr = get_lattice_entry (def);
     180                 :   36294900 :   if (vr)
     181                 :   36294900 :     vr->set_varying (TREE_TYPE (def));
     182                 :   36294900 : }
     183                 :            : 
     184                 :            : /* Set value-ranges of all SSA names defined by STMT to varying.  */
     185                 :            : 
     186                 :            : void
     187                 :  285616000 : vr_values::set_defs_to_varying (gimple *stmt)
     188                 :            : {
     189                 :  285616000 :   ssa_op_iter i;
     190                 :  285616000 :   tree def;
     191                 :  319131000 :   FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
     192                 :   33514800 :     set_def_to_varying (def);
     193                 :  285616000 : }
     194                 :            : 
     195                 :            : /* Update the value range and equivalence set for variable VAR to
     196                 :            :    NEW_VR.  Return true if NEW_VR is different from VAR's previous
     197                 :            :    value.
     198                 :            : 
     199                 :            :    NOTE: This function assumes that NEW_VR is a temporary value range
     200                 :            :    object created for the sole purpose of updating VAR's range.  The
     201                 :            :    storage used by the equivalence set from NEW_VR will be freed by
     202                 :            :    this function.  Do not call update_value_range when NEW_VR
     203                 :            :    is the range object associated with another SSA name.  */
     204                 :            : 
     205                 :            : bool
     206                 :   56685100 : vr_values::update_value_range (const_tree var, value_range_equiv *new_vr)
     207                 :            : {
     208                 :   56685100 :   value_range_equiv *old_vr;
     209                 :   56685100 :   bool is_new;
     210                 :            : 
     211                 :            :   /* If there is a value-range on the SSA name from earlier analysis
     212                 :            :      factor that in.  */
     213                 :   56685100 :   if (INTEGRAL_TYPE_P (TREE_TYPE (var)))
     214                 :            :     {
     215                 :   42901100 :       value_range_equiv nr;
     216                 :   42901100 :       get_range_info (var, nr);
     217                 :   42901100 :       if (!nr.undefined_p ())
     218                 :   42901100 :         new_vr->intersect (&nr);
     219                 :            :     }
     220                 :            : 
     221                 :            :   /* Update the value range, if necessary.  If we cannot allocate a lattice
     222                 :            :      entry for VAR keep it at VARYING.  This happens when DOM feeds us stmts
     223                 :            :      with SSA names allocated after setting up the lattice.  */
     224                 :   56685100 :   old_vr = get_lattice_entry (var);
     225                 :   56685100 :   if (!old_vr)
     226                 :            :     return false;
     227                 :   56685100 :   is_new = !old_vr->equal_p (*new_vr, /*ignore_equivs=*/false);
     228                 :            : 
     229                 :   56685100 :   if (is_new)
     230                 :            :     {
     231                 :            :       /* Do not allow transitions up the lattice.  The following
     232                 :            :          is slightly more awkward than just new_vr->type < old_vr->type
     233                 :            :          because VR_RANGE and VR_ANTI_RANGE need to be considered
     234                 :            :          the same.  We may not have is_new when transitioning to
     235                 :            :          UNDEFINED.  If old_vr->type is VARYING, we shouldn't be
     236                 :            :          called, if we are anyway, keep it VARYING.  */
     237                 :   55390500 :       if (old_vr->varying_p ())
     238                 :            :         {
     239                 :       2220 :           new_vr->set_varying (TREE_TYPE (var));
     240                 :       2220 :           is_new = false;
     241                 :            :         }
     242                 :   55388200 :       else if (new_vr->undefined_p ())
     243                 :            :         {
     244                 :         37 :           old_vr->set_varying (TREE_TYPE (var));
     245                 :         37 :           new_vr->set_varying (TREE_TYPE (var));
     246                 :         37 :           return true;
     247                 :            :         }
     248                 :            :       else
     249                 :   55388200 :         old_vr->set (new_vr->min (), new_vr->max (), new_vr->equiv (),
     250                 :            :                      new_vr->kind ());
     251                 :            :     }
     252                 :            : 
     253                 :   56685000 :   new_vr->equiv_clear ();
     254                 :            : 
     255                 :   56685000 :   return is_new;
     256                 :            : }
     257                 :            : 
     258                 :            : /* Return true if value range VR involves exactly one symbol SYM.  */
     259                 :            : 
     260                 :            : static bool
     261                 :    5064810 : symbolic_range_based_on_p (value_range *vr, const_tree sym)
     262                 :            : {
     263                 :    5064810 :   bool neg, min_has_symbol, max_has_symbol;
     264                 :    5064810 :   tree inv;
     265                 :            : 
     266                 :    5064810 :   if (is_gimple_min_invariant (vr->min ()))
     267                 :            :     min_has_symbol = false;
     268                 :     267826 :   else if (get_single_symbol (vr->min (), &neg, &inv) == sym)
     269                 :            :     min_has_symbol = true;
     270                 :            :   else
     271                 :            :     return false;
     272                 :            : 
     273                 :    4855390 :   if (is_gimple_min_invariant (vr->max ()))
     274                 :            :     max_has_symbol = false;
     275                 :     171705 :   else if (get_single_symbol (vr->max (), &neg, &inv) == sym)
     276                 :            :     max_has_symbol = true;
     277                 :            :   else
     278                 :            :     return false;
     279                 :            : 
     280                 :    4712580 :   return (min_has_symbol || max_has_symbol);
     281                 :            : }
     282                 :            : 
     283                 :            : /* Return true if the result of assignment STMT is know to be non-zero.  */
     284                 :            : 
     285                 :            : static bool
     286                 :   11809500 : gimple_assign_nonzero_p (gimple *stmt)
     287                 :            : {
     288                 :   11809500 :   enum tree_code code = gimple_assign_rhs_code (stmt);
     289                 :   11809500 :   bool strict_overflow_p;
     290                 :   11809500 :   switch (get_gimple_rhs_class (code))
     291                 :            :     {
     292                 :    2593070 :     case GIMPLE_UNARY_RHS:
     293                 :    2593070 :       return tree_unary_nonzero_warnv_p (gimple_assign_rhs_code (stmt),
     294                 :            :                                          gimple_expr_type (stmt),
     295                 :            :                                          gimple_assign_rhs1 (stmt),
     296                 :    2593070 :                                          &strict_overflow_p);
     297                 :    6583310 :     case GIMPLE_BINARY_RHS:
     298                 :    6583310 :       return tree_binary_nonzero_warnv_p (gimple_assign_rhs_code (stmt),
     299                 :            :                                           gimple_expr_type (stmt),
     300                 :            :                                           gimple_assign_rhs1 (stmt),
     301                 :            :                                           gimple_assign_rhs2 (stmt),
     302                 :    6583310 :                                           &strict_overflow_p);
     303                 :            :     case GIMPLE_TERNARY_RHS:
     304                 :            :       return false;
     305                 :    2587580 :     case GIMPLE_SINGLE_RHS:
     306                 :    2587580 :       return tree_single_nonzero_warnv_p (gimple_assign_rhs1 (stmt),
     307                 :    2587580 :                                           &strict_overflow_p);
     308                 :          0 :     case GIMPLE_INVALID_RHS:
     309                 :          0 :       gcc_unreachable ();
     310                 :          0 :     default:
     311                 :          0 :       gcc_unreachable ();
     312                 :            :     }
     313                 :            : }
     314                 :            : 
     315                 :            : /* Return true if STMT is known to compute a non-zero value.  */
     316                 :            : 
     317                 :            : static bool
     318                 :   18814500 : gimple_stmt_nonzero_p (gimple *stmt)
     319                 :            : {
     320                 :   18814500 :   switch (gimple_code (stmt))
     321                 :            :     {
     322                 :   11809500 :     case GIMPLE_ASSIGN:
     323                 :   11809500 :       return gimple_assign_nonzero_p (stmt);
     324                 :    7005060 :     case GIMPLE_CALL:
     325                 :    7005060 :       {
     326                 :    7005060 :         gcall *call_stmt = as_a<gcall *> (stmt);
     327                 :    7005060 :         return (gimple_call_nonnull_result_p (call_stmt)
     328                 :    7005060 :                 || gimple_call_nonnull_arg (call_stmt));
     329                 :            :       }
     330                 :          0 :     default:
     331                 :          0 :       gcc_unreachable ();
     332                 :            :     }
     333                 :            : }
     334                 :            : /* Like tree_expr_nonzero_p, but this function uses value ranges
     335                 :            :    obtained so far.  */
     336                 :            : 
     337                 :            : bool
     338                 :   18814500 : vr_values::vrp_stmt_computes_nonzero (gimple *stmt)
     339                 :            : {
     340                 :   18814500 :   if (gimple_stmt_nonzero_p (stmt))
     341                 :            :     return true;
     342                 :            : 
     343                 :            :   /* If we have an expression of the form &X->a, then the expression
     344                 :            :      is nonnull if X is nonnull.  */
     345                 :   18486700 :   if (is_gimple_assign (stmt)
     346                 :   18486700 :       && gimple_assign_rhs_code (stmt) == ADDR_EXPR)
     347                 :            :     {
     348                 :    2261520 :       tree expr = gimple_assign_rhs1 (stmt);
     349                 :    2261520 :       poly_int64 bitsize, bitpos;
     350                 :    2261520 :       tree offset;
     351                 :    2261520 :       machine_mode mode;
     352                 :    2261520 :       int unsignedp, reversep, volatilep;
     353                 :    2261520 :       tree base = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize,
     354                 :            :                                        &bitpos, &offset, &mode, &unsignedp,
     355                 :            :                                        &reversep, &volatilep);
     356                 :            : 
     357                 :    2261520 :       if (base != NULL_TREE
     358                 :    2261520 :           && TREE_CODE (base) == MEM_REF
     359                 :    4521620 :           && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
     360                 :            :         {
     361                 :    2257500 :           poly_offset_int off = 0;
     362                 :    2257500 :           bool off_cst = false;
     363                 :    2257500 :           if (offset == NULL_TREE || TREE_CODE (offset) == INTEGER_CST)
     364                 :            :             {
     365                 :    2208020 :               off = mem_ref_offset (base);
     366                 :    2208020 :               if (offset)
     367                 :         60 :                 off += poly_offset_int::from (wi::to_poly_wide (offset),
     368                 :         30 :                                               SIGNED);
     369                 :    2208020 :               off <<= LOG2_BITS_PER_UNIT;
     370                 :    2208020 :               off += bitpos;
     371                 :    2208020 :               off_cst = true;
     372                 :            :             }
     373                 :            :           /* If &X->a is equal to X and X is ~[0, 0], the result is too.
     374                 :            :              For -fdelete-null-pointer-checks -fno-wrapv-pointer we don't
     375                 :            :              allow going from non-NULL pointer to NULL.  */
     376                 :    2208020 :           if ((off_cst && known_eq (off, 0))
     377                 :    1449440 :               || (flag_delete_null_pointer_checks
     378                 :    1448490 :                   && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr))))
     379                 :            :             {
     380                 :    2256550 :               const value_range_equiv *vr
     381                 :    2256550 :                 = get_value_range (TREE_OPERAND (base, 0));
     382                 :    2256550 :               if (!range_includes_zero_p (vr))
     383                 :    2054690 :                 return true;
     384                 :            :             }
     385                 :            :           /* If MEM_REF has a "positive" offset, consider it non-NULL
     386                 :            :              always, for -fdelete-null-pointer-checks also "negative"
     387                 :            :              ones.  Punt for unknown offsets (e.g. variable ones).  */
     388                 :     457857 :           if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr))
     389                 :     457852 :               && off_cst
     390                 :     434411 :               && known_ne (off, 0)
     391                 :     915709 :               && (flag_delete_null_pointer_checks || known_gt (off, 0)))
     392                 :     255041 :             return true;
     393                 :            :         }
     394                 :            :     }
     395                 :            : 
     396                 :            :   return false;
     397                 :            : }
     398                 :            : 
     399                 :            : /* Returns true if EXPR is a valid value (as expected by compare_values) --
     400                 :            :    a gimple invariant, or SSA_NAME +- CST.  */
     401                 :            : 
     402                 :            : static bool
     403                 :    1315450 : valid_value_p (tree expr)
     404                 :            : {
     405                 :    1315450 :   if (TREE_CODE (expr) == SSA_NAME)
     406                 :            :     return true;
     407                 :            : 
     408                 :     876739 :   if (TREE_CODE (expr) == PLUS_EXPR
     409                 :     876739 :       || TREE_CODE (expr) == MINUS_EXPR)
     410                 :          0 :     return (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
     411                 :          0 :             && TREE_CODE (TREE_OPERAND (expr, 1)) == INTEGER_CST);
     412                 :            : 
     413                 :     876739 :   return is_gimple_min_invariant (expr);
     414                 :            : }
     415                 :            : 
     416                 :            : /* If OP has a value range with a single constant value return that,
     417                 :            :    otherwise return NULL_TREE.  This returns OP itself if OP is a
     418                 :            :    constant.  */
     419                 :            : 
     420                 :            : tree
     421                 :  164208000 : vr_values::op_with_constant_singleton_value_range (tree op)
     422                 :            : {
     423                 :  164208000 :   if (is_gimple_min_invariant (op))
     424                 :            :     return op;
     425                 :            : 
     426                 :  162011000 :   if (TREE_CODE (op) != SSA_NAME)
     427                 :            :     return NULL_TREE;
     428                 :            : 
     429                 :  161996000 :   tree t;
     430                 :  161996000 :   if (get_value_range (op)->singleton_p (&t))
     431                 :     783865 :     return t;
     432                 :            :   return NULL;
     433                 :            : }
     434                 :            : 
     435                 :            : /* Return true if op is in a boolean [0, 1] value-range.  */
     436                 :            : 
     437                 :            : bool
     438                 :     329702 : vr_values::op_with_boolean_value_range_p (tree op)
     439                 :            : {
     440                 :     329702 :   const value_range_equiv *vr;
     441                 :            : 
     442                 :     329702 :   if (TYPE_PRECISION (TREE_TYPE (op)) == 1)
     443                 :            :     return true;
     444                 :            : 
     445                 :     320724 :   if (integer_zerop (op)
     446                 :     320724 :       || integer_onep (op))
     447                 :       4726 :     return true;
     448                 :            : 
     449                 :     315998 :   if (TREE_CODE (op) != SSA_NAME)
     450                 :            :     return false;
     451                 :            : 
     452                 :     315998 :   vr = get_value_range (op);
     453                 :     315998 :   return (vr->kind () == VR_RANGE
     454                 :      74291 :           && integer_zerop (vr->min ())
     455                 :     366138 :           && integer_onep (vr->max ()));
     456                 :            : }
     457                 :            : 
     458                 :            : /* Extract value range information for VAR when (OP COND_CODE LIMIT) is
     459                 :            :    true and store it in *VR_P.  */
     460                 :            : 
     461                 :            : void
     462                 :   45308400 : vr_values::extract_range_for_var_from_comparison_expr (tree var,
     463                 :            :                                                        enum tree_code cond_code,
     464                 :            :                                                        tree op, tree limit,
     465                 :            :                                                        value_range_equiv *vr_p)
     466                 :            : {
     467                 :   45308400 :   tree  min, max, type;
     468                 :   45308400 :   const value_range_equiv *limit_vr;
     469                 :   45308400 :   type = TREE_TYPE (var);
     470                 :            : 
     471                 :            :   /* For pointer arithmetic, we only keep track of pointer equality
     472                 :            :      and inequality.  If we arrive here with unfolded conditions like
     473                 :            :      _1 > _1 do not derive anything.  */
     474                 :   45308400 :   if ((POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR)
     475                 :   45004800 :       || limit == var)
     476                 :            :     {
     477                 :     303687 :       vr_p->set_varying (type);
     478                 :     303687 :       return;
     479                 :            :     }
     480                 :            : 
     481                 :            :   /* If LIMIT is another SSA name and LIMIT has a range of its own,
     482                 :            :      try to use LIMIT's range to avoid creating symbolic ranges
     483                 :            :      unnecessarily. */
     484                 :   45004800 :   limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL;
     485                 :            : 
     486                 :            :   /* LIMIT's range is only interesting if it has any useful information.  */
     487                 :    8642800 :   if (! limit_vr
     488                 :    8642800 :       || limit_vr->undefined_p ()
     489                 :    8638230 :       || limit_vr->varying_p ()
     490                 :   12992700 :       || (limit_vr->symbolic_p ()
     491                 :    1345950 :           && ! (limit_vr->kind () == VR_RANGE
     492                 :    1089480 :                 && (limit_vr->min () == limit_vr->max ()
     493                 :     992371 :                     || operand_equal_p (limit_vr->min (),
     494                 :     992371 :                                         limit_vr->max (), 0)))))
     495                 :            :     limit_vr = NULL;
     496                 :            : 
     497                 :            :   /* Initially, the new range has the same set of equivalences of
     498                 :            :      VAR's range.  This will be revised before returning the final
     499                 :            :      value.  Since assertions may be chained via mutually exclusive
     500                 :            :      predicates, we will need to trim the set of equivalences before
     501                 :            :      we are done.  */
     502                 :   45004800 :   gcc_assert (vr_p->equiv () == NULL);
     503                 :   45004800 :   vr_p->equiv_add (var, get_value_range (var), &vrp_equiv_obstack);
     504                 :            : 
     505                 :            :   /* Extract a new range based on the asserted comparison for VAR and
     506                 :            :      LIMIT's value range.  Notice that if LIMIT has an anti-range, we
     507                 :            :      will only use it for equality comparisons (EQ_EXPR).  For any
     508                 :            :      other kind of assertion, we cannot derive a range from LIMIT's
     509                 :            :      anti-range that can be used to describe the new range.  For
     510                 :            :      instance, ASSERT_EXPR <x_2, x_2 <= b_4>.  If b_4 is ~[2, 10],
     511                 :            :      then b_4 takes on the ranges [-INF, 1] and [11, +INF].  There is
     512                 :            :      no single range for x_2 that could describe LE_EXPR, so we might
     513                 :            :      as well build the range [b_4, +INF] for it.
     514                 :            :      One special case we handle is extracting a range from a
     515                 :            :      range test encoded as (unsigned)var + CST <= limit.  */
     516                 :   45004800 :   if (TREE_CODE (op) == NOP_EXPR
     517                 :   45004800 :       || TREE_CODE (op) == PLUS_EXPR)
     518                 :            :     {
     519                 :     697167 :       if (TREE_CODE (op) == PLUS_EXPR)
     520                 :            :         {
     521                 :     539259 :           min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (op, 1)),
     522                 :            :                              TREE_OPERAND (op, 1));
     523                 :     539259 :           max = int_const_binop (PLUS_EXPR, limit, min);
     524                 :     539259 :           op = TREE_OPERAND (op, 0);
     525                 :            :         }
     526                 :            :       else
     527                 :            :         {
     528                 :     157908 :           min = build_int_cst (TREE_TYPE (var), 0);
     529                 :     157908 :           max = limit;
     530                 :            :         }
     531                 :            : 
     532                 :            :       /* Make sure to not set TREE_OVERFLOW on the final type
     533                 :            :          conversion.  We are willingly interpreting large positive
     534                 :            :          unsigned values as negative signed values here.  */
     535                 :     697167 :       min = force_fit_type (TREE_TYPE (var), wi::to_widest (min), 0, false);
     536                 :     697167 :       max = force_fit_type (TREE_TYPE (var), wi::to_widest (max), 0, false);
     537                 :            : 
     538                 :            :       /* We can transform a max, min range to an anti-range or
     539                 :            :          vice-versa.  Use set_and_canonicalize which does this for
     540                 :            :          us.  */
     541                 :     697167 :       if (cond_code == LE_EXPR)
     542                 :     506094 :         vr_p->set (min, max, vr_p->equiv ());
     543                 :     191073 :       else if (cond_code == GT_EXPR)
     544                 :     191073 :         vr_p->set (min, max, vr_p->equiv (), VR_ANTI_RANGE);
     545                 :            :       else
     546                 :          0 :         gcc_unreachable ();
     547                 :            :     }
     548                 :   44307600 :   else if (cond_code == EQ_EXPR)
     549                 :            :     {
     550                 :    7115110 :       enum value_range_kind range_kind;
     551                 :            : 
     552                 :    7115110 :       if (limit_vr)
     553                 :            :         {
     554                 :     549285 :           range_kind = limit_vr->kind ();
     555                 :     549285 :           min = limit_vr->min ();
     556                 :     549285 :           max = limit_vr->max ();
     557                 :            :         }
     558                 :            :       else
     559                 :            :         {
     560                 :            :           range_kind = VR_RANGE;
     561                 :            :           min = limit;
     562                 :            :           max = limit;
     563                 :            :         }
     564                 :            : 
     565                 :    7115110 :       vr_p->update (min, max, range_kind);
     566                 :            : 
     567                 :            :       /* When asserting the equality VAR == LIMIT and LIMIT is another
     568                 :            :          SSA name, the new range will also inherit the equivalence set
     569                 :            :          from LIMIT.  */
     570                 :    7115110 :       if (TREE_CODE (limit) == SSA_NAME)
     571                 :    1860160 :         vr_p->equiv_add (limit, get_value_range (limit), &vrp_equiv_obstack);
     572                 :            :     }
     573                 :   37192500 :   else if (cond_code == NE_EXPR)
     574                 :            :     {
     575                 :            :       /* As described above, when LIMIT's range is an anti-range and
     576                 :            :          this assertion is an inequality (NE_EXPR), then we cannot
     577                 :            :          derive anything from the anti-range.  For instance, if
     578                 :            :          LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
     579                 :            :          not imply that VAR's range is [0, 0].  So, in the case of
     580                 :            :          anti-ranges, we just assert the inequality using LIMIT and
     581                 :            :          not its anti-range.
     582                 :            : 
     583                 :            :          If LIMIT_VR is a range, we can only use it to build a new
     584                 :            :          anti-range if LIMIT_VR is a single-valued range.  For
     585                 :            :          instance, if LIMIT_VR is [0, 1], the predicate
     586                 :            :          VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
     587                 :            :          Rather, it means that for value 0 VAR should be ~[0, 0]
     588                 :            :          and for value 1, VAR should be ~[1, 1].  We cannot
     589                 :            :          represent these ranges.
     590                 :            : 
     591                 :            :          The only situation in which we can build a valid
     592                 :            :          anti-range is when LIMIT_VR is a single-valued range
     593                 :            :          (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX).  In that case,
     594                 :            :          build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX].  */
     595                 :   30637700 :       if (limit_vr
     596                 :     882608 :           && limit_vr->kind () == VR_RANGE
     597                 :   31420300 :           && compare_values (limit_vr->min (), limit_vr->max ()) == 0)
     598                 :            :         {
     599                 :      39810 :           min = limit_vr->min ();
     600                 :      39810 :           max = limit_vr->max ();
     601                 :            :         }
     602                 :            :       else
     603                 :            :         {
     604                 :            :           /* In any other case, we cannot use LIMIT's range to build a
     605                 :            :              valid anti-range.  */
     606                 :            :           min = max = limit;
     607                 :            :         }
     608                 :            : 
     609                 :            :       /* If MIN and MAX cover the whole range for their type, then
     610                 :            :          just use the original LIMIT.  */
     611                 :   30637700 :       if (INTEGRAL_TYPE_P (type)
     612                 :    7285380 :           && vrp_val_is_min (min)
     613                 :   33418100 :           && vrp_val_is_max (max))
     614                 :            :         min = max = limit;
     615                 :            : 
     616                 :   30637700 :       vr_p->set (min, max, vr_p->equiv (), VR_ANTI_RANGE);
     617                 :            :     }
     618                 :    6554840 :   else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
     619                 :            :     {
     620                 :    3320200 :       min = TYPE_MIN_VALUE (type);
     621                 :            : 
     622                 :    3320200 :       if (limit_vr == NULL || limit_vr->kind () == VR_ANTI_RANGE)
     623                 :            :         max = limit;
     624                 :            :       else
     625                 :            :         {
     626                 :            :           /* If LIMIT_VR is of the form [N1, N2], we need to build the
     627                 :            :              range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
     628                 :            :              LT_EXPR.  */
     629                 :     918206 :           max = limit_vr->max ();
     630                 :            :         }
     631                 :            : 
     632                 :            :       /* If the maximum value forces us to be out of bounds, simply punt.
     633                 :            :          It would be pointless to try and do anything more since this
     634                 :            :          all should be optimized away above us.  */
     635                 :    3320200 :       if (cond_code == LT_EXPR
     636                 :    3320200 :           && compare_values (max, min) == 0)
     637                 :        258 :         vr_p->set_varying (TREE_TYPE (min));
     638                 :            :       else
     639                 :            :         {
     640                 :            :           /* For LT_EXPR, we create the range [MIN, MAX - 1].  */
     641                 :    3319940 :           if (cond_code == LT_EXPR)
     642                 :            :             {
     643                 :    1358090 :               if (TYPE_PRECISION (TREE_TYPE (max)) == 1
     644                 :    1358090 :                   && !TYPE_UNSIGNED (TREE_TYPE (max)))
     645                 :         55 :                 max = fold_build2 (PLUS_EXPR, TREE_TYPE (max), max,
     646                 :            :                                    build_int_cst (TREE_TYPE (max), -1));
     647                 :            :               else
     648                 :    1358040 :                 max = fold_build2 (MINUS_EXPR, TREE_TYPE (max), max,
     649                 :            :                                    build_int_cst (TREE_TYPE (max), 1));
     650                 :            :               /* Signal to compare_values_warnv this expr doesn't overflow.  */
     651                 :    1358090 :               if (EXPR_P (max))
     652                 :     766168 :                 TREE_NO_WARNING (max) = 1;
     653                 :            :             }
     654                 :            : 
     655                 :    3319940 :           vr_p->update (min, max);
     656                 :            :         }
     657                 :            :     }
     658                 :    3234640 :   else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
     659                 :            :     {
     660                 :    3234640 :       max = TYPE_MAX_VALUE (type);
     661                 :            : 
     662                 :    3234640 :       if (limit_vr == NULL || limit_vr->kind () == VR_ANTI_RANGE)
     663                 :            :         min = limit;
     664                 :            :       else
     665                 :            :         {
     666                 :            :           /* If LIMIT_VR is of the form [N1, N2], we need to build the
     667                 :            :              range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
     668                 :            :              GT_EXPR.  */
     669                 :     653971 :           min = limit_vr->min ();
     670                 :            :         }
     671                 :            : 
     672                 :            :       /* If the minimum value forces us to be out of bounds, simply punt.
     673                 :            :          It would be pointless to try and do anything more since this
     674                 :            :          all should be optimized away above us.  */
     675                 :    3234640 :       if (cond_code == GT_EXPR
     676                 :    3234640 :           && compare_values (min, max) == 0)
     677                 :        184 :         vr_p->set_varying (TREE_TYPE (min));
     678                 :            :       else
     679                 :            :         {
     680                 :            :           /* For GT_EXPR, we create the range [MIN + 1, MAX].  */
     681                 :    3234450 :           if (cond_code == GT_EXPR)
     682                 :            :             {
     683                 :    1927140 :               if (TYPE_PRECISION (TREE_TYPE (min)) == 1
     684                 :    1927140 :                   && !TYPE_UNSIGNED (TREE_TYPE (min)))
     685                 :         56 :                 min = fold_build2 (MINUS_EXPR, TREE_TYPE (min), min,
     686                 :            :                                    build_int_cst (TREE_TYPE (min), -1));
     687                 :            :               else
     688                 :    1927080 :                 min = fold_build2 (PLUS_EXPR, TREE_TYPE (min), min,
     689                 :            :                                    build_int_cst (TREE_TYPE (min), 1));
     690                 :            :               /* Signal to compare_values_warnv this expr doesn't overflow.  */
     691                 :    1927140 :               if (EXPR_P (min))
     692                 :     601006 :                 TREE_NO_WARNING (min) = 1;
     693                 :            :             }
     694                 :            : 
     695                 :    3234450 :           vr_p->update (min, max);
     696                 :            :         }
     697                 :            :     }
     698                 :            :   else
     699                 :          0 :     gcc_unreachable ();
     700                 :            : 
     701                 :            :   /* Finally intersect the new range with what we already know about var.  */
     702                 :   45004800 :   vr_p->intersect (get_value_range (var));
     703                 :            : }
     704                 :            : 
     705                 :            : /* Extract value range information from an ASSERT_EXPR EXPR and store
     706                 :            :    it in *VR_P.  */
     707                 :            : 
     708                 :            : void
     709                 :    7232270 : vr_values::extract_range_from_assert (value_range_equiv *vr_p, tree expr)
     710                 :            : {
     711                 :    7232270 :   tree var = ASSERT_EXPR_VAR (expr);
     712                 :    7232270 :   tree cond = ASSERT_EXPR_COND (expr);
     713                 :    7232270 :   tree limit, op;
     714                 :    7232270 :   enum tree_code cond_code;
     715                 :    7232270 :   gcc_assert (COMPARISON_CLASS_P (cond));
     716                 :            : 
     717                 :            :   /* Find VAR in the ASSERT_EXPR conditional.  */
     718                 :    7232270 :   if (var == TREE_OPERAND (cond, 0)
     719                 :     128594 :       || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR
     720                 :    7266490 :       || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR)
     721                 :            :     {
     722                 :            :       /* If the predicate is of the form VAR COMP LIMIT, then we just
     723                 :            :          take LIMIT from the RHS and use the same comparison code.  */
     724                 :    7232270 :       cond_code = TREE_CODE (cond);
     725                 :    7232270 :       limit = TREE_OPERAND (cond, 1);
     726                 :    7232270 :       op = TREE_OPERAND (cond, 0);
     727                 :            :     }
     728                 :            :   else
     729                 :            :     {
     730                 :            :       /* If the predicate is of the form LIMIT COMP VAR, then we need
     731                 :            :          to flip around the comparison code to create the proper range
     732                 :            :          for VAR.  */
     733                 :          0 :       cond_code = swap_tree_comparison (TREE_CODE (cond));
     734                 :          0 :       limit = TREE_OPERAND (cond, 0);
     735                 :          0 :       op = TREE_OPERAND (cond, 1);
     736                 :            :     }
     737                 :    7232270 :   extract_range_for_var_from_comparison_expr (var, cond_code, op,
     738                 :            :                                               limit, vr_p);
     739                 :    7232270 : }
     740                 :            : 
     741                 :            : /* Extract range information from SSA name VAR and store it in VR.  If
     742                 :            :    VAR has an interesting range, use it.  Otherwise, create the
     743                 :            :    range [VAR, VAR] and return it.  This is useful in situations where
     744                 :            :    we may have conditionals testing values of VARYING names.  For
     745                 :            :    instance,
     746                 :            : 
     747                 :            :         x_3 = y_5;
     748                 :            :         if (x_3 > y_5)
     749                 :            :           ...
     750                 :            : 
     751                 :            :     Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
     752                 :            :     always false.  */
     753                 :            : 
     754                 :            : void
     755                 :    1515610 : vr_values::extract_range_from_ssa_name (value_range_equiv *vr, tree var)
     756                 :            : {
     757                 :    1515610 :   const value_range_equiv *var_vr = get_value_range (var);
     758                 :            : 
     759                 :    1515610 :   if (!var_vr->varying_p ())
     760                 :     365591 :     vr->deep_copy (var_vr);
     761                 :            :   else
     762                 :    1150020 :     vr->set (var);
     763                 :            : 
     764                 :    1515610 :   if (!vr->undefined_p ())
     765                 :    1511450 :     vr->equiv_add (var, get_value_range (var), &vrp_equiv_obstack);
     766                 :    1515610 : }
     767                 :            : 
     768                 :            : /* Extract range information from a binary expression OP0 CODE OP1 based on
     769                 :            :    the ranges of each of its operands with resulting type EXPR_TYPE.
     770                 :            :    The resulting range is stored in *VR.  */
     771                 :            : 
     772                 :            : void
     773                 :   29924900 : vr_values::extract_range_from_binary_expr (value_range_equiv *vr,
     774                 :            :                                            enum tree_code code,
     775                 :            :                                            tree expr_type, tree op0, tree op1)
     776                 :            : {
     777                 :            :   /* Get value ranges for each operand.  For constant operands, create
     778                 :            :      a new value range with the operand to simplify processing.  */
     779                 :   29924900 :   value_range vr0, vr1;
     780                 :   29924900 :   if (TREE_CODE (op0) == SSA_NAME)
     781                 :   28466200 :     vr0 = *(get_value_range (op0));
     782                 :    1458670 :   else if (is_gimple_min_invariant (op0))
     783                 :    1458670 :     vr0.set (op0);
     784                 :            :   else
     785                 :          0 :     vr0.set_varying (TREE_TYPE (op0));
     786                 :            : 
     787                 :   29924900 :   if (TREE_CODE (op1) == SSA_NAME)
     788                 :   12538400 :     vr1 = *(get_value_range (op1));
     789                 :   17386500 :   else if (is_gimple_min_invariant (op1))
     790                 :   17386500 :     vr1.set (op1);
     791                 :            :   else
     792                 :          0 :     vr1.set_varying (TREE_TYPE (op1));
     793                 :            : 
     794                 :            :   /* If one argument is varying, we can sometimes still deduce a
     795                 :            :      range for the output: any + [3, +INF] is in [MIN+3, +INF].  */
     796                 :   59679400 :   if (INTEGRAL_TYPE_P (TREE_TYPE (op0))
     797                 :   54261100 :       && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0)))
     798                 :            :     {
     799                 :    8916110 :       if (vr0.varying_p () && !vr1.varying_p ())
     800                 :    2623810 :         vr0 = value_range (vrp_val_min (expr_type), vrp_val_max (expr_type));
     801                 :    6292300 :       else if (vr1.varying_p () && !vr0.varying_p ())
     802                 :     691187 :         vr1 = value_range (vrp_val_min (expr_type), vrp_val_max (expr_type));
     803                 :            :     }
     804                 :            : 
     805                 :   29924900 :   range_fold_binary_expr (vr, code, expr_type, &vr0, &vr1);
     806                 :            : 
     807                 :            :   /* Set value_range for n in following sequence:
     808                 :            :      def = __builtin_memchr (arg, 0, sz)
     809                 :            :      n = def - arg
     810                 :            :      Here the range for n can be set to [0, PTRDIFF_MAX - 1]. */
     811                 :            : 
     812                 :   29924900 :   if (vr->varying_p ()
     813                 :   14757300 :       && code == POINTER_DIFF_EXPR
     814                 :     771653 :       && TREE_CODE (op0) == SSA_NAME
     815                 :   30693000 :       && TREE_CODE (op1) == SSA_NAME)
     816                 :            :     {
     817                 :     737444 :       tree op0_ptype = TREE_TYPE (TREE_TYPE (op0));
     818                 :     737444 :       tree op1_ptype = TREE_TYPE (TREE_TYPE (op1));
     819                 :     737444 :       gcall *call_stmt = NULL;
     820                 :            : 
     821                 :     737444 :       if (TYPE_MODE (op0_ptype) == TYPE_MODE (char_type_node)
     822                 :     165559 :           && TYPE_PRECISION (op0_ptype) == TYPE_PRECISION (char_type_node)
     823                 :     150706 :           && TYPE_MODE (op1_ptype) == TYPE_MODE (char_type_node)
     824                 :     150336 :           && TYPE_PRECISION (op1_ptype) == TYPE_PRECISION (char_type_node)
     825                 :     150336 :           && (call_stmt = dyn_cast<gcall *>(SSA_NAME_DEF_STMT (op0)))
     826                 :       1964 :           && gimple_call_builtin_p (call_stmt, BUILT_IN_MEMCHR)
     827                 :       1034 :           && operand_equal_p (op0, gimple_call_lhs (call_stmt), 0)
     828                 :       1034 :           && operand_equal_p (op1, gimple_call_arg (call_stmt, 0), 0)
     829                 :     737928 :           && integer_zerop (gimple_call_arg (call_stmt, 1)))
     830                 :            :             {
     831                 :          3 :               tree max = vrp_val_max (ptrdiff_type_node);
     832                 :          3 :               wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max)));
     833                 :          3 :               tree range_min = build_zero_cst (expr_type);
     834                 :          3 :               tree range_max = wide_int_to_tree (expr_type, wmax - 1);
     835                 :          3 :               vr->set (range_min, range_max);
     836                 :          3 :               return;
     837                 :            :             }
     838                 :            :      }
     839                 :            : 
     840                 :            :   /* Try harder for PLUS and MINUS if the range of one operand is symbolic
     841                 :            :      and based on the other operand, for example if it was deduced from a
     842                 :            :      symbolic comparison.  When a bound of the range of the first operand
     843                 :            :      is invariant, we set the corresponding bound of the new range to INF
     844                 :            :      in order to avoid recursing on the range of the second operand.  */
     845                 :   29924900 :   if (vr->varying_p ()
     846                 :   14757200 :       && (code == PLUS_EXPR || code == MINUS_EXPR)
     847                 :    6821000 :       && TREE_CODE (op1) == SSA_NAME
     848                 :    3585580 :       && vr0.kind () == VR_RANGE
     849                 :   30932100 :       && symbolic_range_based_on_p (&vr0, op1))
     850                 :            :     {
     851                 :      57659 :       const bool minus_p = (code == MINUS_EXPR);
     852                 :      57659 :       value_range n_vr1;
     853                 :            : 
     854                 :            :       /* Try with VR0 and [-INF, OP1].  */
     855                 :      57659 :       if (is_gimple_min_invariant (minus_p ? vr0.max () : vr0.min ()))
     856                 :      54172 :         n_vr1.set (vrp_val_min (expr_type), op1);
     857                 :            : 
     858                 :            :       /* Try with VR0 and [OP1, +INF].  */
     859                 :       3487 :       else if (is_gimple_min_invariant (minus_p ? vr0.min () : vr0.max ()))
     860                 :       1923 :         n_vr1.set (op1, vrp_val_max (expr_type));
     861                 :            : 
     862                 :            :       /* Try with VR0 and [OP1, OP1].  */
     863                 :            :       else
     864                 :       1564 :         n_vr1.set (op1, op1);
     865                 :            : 
     866                 :      57659 :       range_fold_binary_expr (vr, code, expr_type, &vr0, &n_vr1);
     867                 :            :     }
     868                 :            : 
     869                 :   29924900 :   if (vr->varying_p ()
     870                 :   14733900 :       && (code == PLUS_EXPR || code == MINUS_EXPR)
     871                 :    6797640 :       && TREE_CODE (op0) == SSA_NAME
     872                 :    6724790 :       && vr1.kind () == VR_RANGE
     873                 :   33982600 :       && symbolic_range_based_on_p (&vr1, op0))
     874                 :            :     {
     875                 :      27436 :       const bool minus_p = (code == MINUS_EXPR);
     876                 :      27436 :       value_range n_vr0;
     877                 :            : 
     878                 :            :       /* Try with [-INF, OP0] and VR1.  */
     879                 :      27436 :       if (is_gimple_min_invariant (minus_p ? vr1.max () : vr1.min ()))
     880                 :       1396 :         n_vr0.set (vrp_val_min (expr_type), op0);
     881                 :            : 
     882                 :            :       /* Try with [OP0, +INF] and VR1.  */
     883                 :      26040 :       else if (is_gimple_min_invariant (minus_p ? vr1.min (): vr1.max ()))
     884                 :      25406 :         n_vr0.set (op0, vrp_val_max (expr_type));
     885                 :            : 
     886                 :            :       /* Try with [OP0, OP0] and VR1.  */
     887                 :            :       else
     888                 :        634 :         n_vr0.set (op0);
     889                 :            : 
     890                 :      27436 :       range_fold_binary_expr (vr, code, expr_type, &n_vr0, &vr1);
     891                 :            :     }
     892                 :            : 
     893                 :            :   /* If we didn't derive a range for MINUS_EXPR, and
     894                 :            :      op1's range is ~[op0,op0] or vice-versa, then we
     895                 :            :      can derive a non-null range.  This happens often for
     896                 :            :      pointer subtraction.  */
     897                 :   29924900 :   if (vr->varying_p ()
     898                 :   14729500 :       && (code == MINUS_EXPR || code == POINTER_DIFF_EXPR)
     899                 :    1957720 :       && TREE_CODE (op0) == SSA_NAME
     900                 :   31827300 :       && ((vr0.kind () == VR_ANTI_RANGE
     901                 :      47976 :            && vr0.min () == op1
     902                 :      13503 :            && vr0.min () == vr0.max ())
     903                 :    1888910 :           || (vr1.kind () == VR_ANTI_RANGE
     904                 :      42791 :               && vr1.min () == op0
     905                 :       4943 :               && vr1.min () == vr1.max ())))
     906                 :            :     {
     907                 :      18446 :       vr->set_nonzero (expr_type);
     908                 :      18446 :       vr->equiv_clear ();
     909                 :            :     }
     910                 :            : }
     911                 :            : 
     912                 :            : /* Extract range information from a unary expression CODE OP0 based on
     913                 :            :    the range of its operand with resulting type TYPE.
     914                 :            :    The resulting range is stored in *VR.  */
     915                 :            : 
     916                 :            : void
     917                 :   14543800 : vr_values::extract_range_from_unary_expr (value_range_equiv *vr,
     918                 :            :                                           enum tree_code code,
     919                 :            :                                           tree type, tree op0)
     920                 :            : {
     921                 :   14543800 :   value_range vr0;
     922                 :            : 
     923                 :            :   /* Get value ranges for the operand.  For constant operands, create
     924                 :            :      a new value range with the operand to simplify processing.  */
     925                 :   14543800 :   if (TREE_CODE (op0) == SSA_NAME)
     926                 :   14069700 :     vr0 = *(get_value_range (op0));
     927                 :     474065 :   else if (is_gimple_min_invariant (op0))
     928                 :     474065 :     vr0.set (op0);
     929                 :            :   else
     930                 :          0 :     vr0.set_varying (type);
     931                 :            : 
     932                 :   14543800 :   range_fold_unary_expr (vr, code, type, &vr0, TREE_TYPE (op0));
     933                 :   14543800 : }
     934                 :            : 
     935                 :            : 
     936                 :            : /* Extract range information from a conditional expression STMT based on
     937                 :            :    the ranges of each of its operands and the expression code.  */
     938                 :            : 
     939                 :            : void
     940                 :      99066 : vr_values::extract_range_from_cond_expr (value_range_equiv *vr, gassign *stmt)
     941                 :            : {
     942                 :            :   /* Get value ranges for each operand.  For constant operands, create
     943                 :            :      a new value range with the operand to simplify processing.  */
     944                 :      99066 :   tree op0 = gimple_assign_rhs2 (stmt);
     945                 :      99066 :   value_range_equiv tem0;
     946                 :      99066 :   const value_range_equiv *vr0 = &tem0;
     947                 :      99066 :   if (TREE_CODE (op0) == SSA_NAME)
     948                 :      62876 :     vr0 = get_value_range (op0);
     949                 :      36190 :   else if (is_gimple_min_invariant (op0))
     950                 :      36190 :     tem0.set (op0);
     951                 :            :   else
     952                 :          0 :     tem0.set_varying (TREE_TYPE (op0));
     953                 :            : 
     954                 :      99066 :   tree op1 = gimple_assign_rhs3 (stmt);
     955                 :      99066 :   value_range_equiv tem1;
     956                 :      99066 :   const value_range_equiv *vr1 = &tem1;
     957                 :      99066 :   if (TREE_CODE (op1) == SSA_NAME)
     958                 :      23103 :     vr1 = get_value_range (op1);
     959                 :      75963 :   else if (is_gimple_min_invariant (op1))
     960                 :      75963 :     tem1.set (op1);
     961                 :            :   else
     962                 :          0 :     tem1.set_varying (TREE_TYPE (op1));
     963                 :            : 
     964                 :            :   /* The resulting value range is the union of the operand ranges */
     965                 :      99066 :   vr->deep_copy (vr0);
     966                 :      99066 :   vr->union_ (vr1);
     967                 :      99066 : }
     968                 :            : 
     969                 :            : 
     970                 :            : /* Extract range information from a comparison expression EXPR based
     971                 :            :    on the range of its operand and the expression code.  */
     972                 :            : 
     973                 :            : void
     974                 :    3647670 : vr_values::extract_range_from_comparison (value_range_equiv *vr,
     975                 :            :                                           enum tree_code code,
     976                 :            :                                           tree type, tree op0, tree op1)
     977                 :            : {
     978                 :    3647670 :   bool sop;
     979                 :    3647670 :   tree val;
     980                 :            : 
     981                 :    3647670 :   val = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, false, &sop,
     982                 :            :                                                  NULL);
     983                 :    3647670 :   if (val)
     984                 :            :     {
     985                 :            :       /* Since this expression was found on the RHS of an assignment,
     986                 :            :          its type may be different from _Bool.  Convert VAL to EXPR's
     987                 :            :          type.  */
     988                 :      78942 :       val = fold_convert (type, val);
     989                 :      78942 :       if (is_gimple_min_invariant (val))
     990                 :      78942 :         vr->set (val);
     991                 :            :       else
     992                 :          0 :         vr->update (val, val);
     993                 :            :     }
     994                 :            :   else
     995                 :            :     /* The result of a comparison is always true or false.  */
     996                 :    3568720 :     set_value_range_to_truthvalue (vr, type);
     997                 :    3647670 : }
     998                 :            : 
     999                 :            : /* Helper function for simplify_internal_call_using_ranges and
    1000                 :            :    extract_range_basic.  Return true if OP0 SUBCODE OP1 for
    1001                 :            :    SUBCODE {PLUS,MINUS,MULT}_EXPR is known to never overflow or
    1002                 :            :    always overflow.  Set *OVF to true if it is known to always
    1003                 :            :    overflow.  */
    1004                 :            : 
    1005                 :            : bool
    1006                 :     482330 : vr_values::check_for_binary_op_overflow (enum tree_code subcode, tree type,
    1007                 :            :                                          tree op0, tree op1, bool *ovf)
    1008                 :            : {
    1009                 :     482330 :   value_range vr0, vr1;
    1010                 :     482330 :   if (TREE_CODE (op0) == SSA_NAME)
    1011                 :     306529 :     vr0 = *get_value_range (op0);
    1012                 :     175801 :   else if (TREE_CODE (op0) == INTEGER_CST)
    1013                 :     175801 :     vr0.set (op0);
    1014                 :            :   else
    1015                 :          0 :     vr0.set_varying (TREE_TYPE (op0));
    1016                 :            : 
    1017                 :     482330 :   if (TREE_CODE (op1) == SSA_NAME)
    1018                 :     308445 :     vr1 = *get_value_range (op1);
    1019                 :     173885 :   else if (TREE_CODE (op1) == INTEGER_CST)
    1020                 :     173885 :     vr1.set (op1);
    1021                 :            :   else
    1022                 :          0 :     vr1.set_varying (TREE_TYPE (op1));
    1023                 :            : 
    1024                 :     482330 :   tree vr0min = vr0.min (), vr0max = vr0.max ();
    1025                 :     482330 :   tree vr1min = vr1.min (), vr1max = vr1.max ();
    1026                 :     482330 :   if (!range_int_cst_p (&vr0)
    1027                 :     233643 :       || TREE_OVERFLOW (vr0min)
    1028                 :     715973 :       || TREE_OVERFLOW (vr0max))
    1029                 :            :     {
    1030                 :     248687 :       vr0min = vrp_val_min (TREE_TYPE (op0));
    1031                 :     248687 :       vr0max = vrp_val_max (TREE_TYPE (op0));
    1032                 :            :     }
    1033                 :     482330 :   if (!range_int_cst_p (&vr1)
    1034                 :     236554 :       || TREE_OVERFLOW (vr1min)
    1035                 :     718884 :       || TREE_OVERFLOW (vr1max))
    1036                 :            :     {
    1037                 :     245776 :       vr1min = vrp_val_min (TREE_TYPE (op1));
    1038                 :     245776 :       vr1max = vrp_val_max (TREE_TYPE (op1));
    1039                 :            :     }
    1040                 :     792925 :   *ovf = arith_overflowed_p (subcode, type, vr0min,
    1041                 :            :                              subcode == MINUS_EXPR ? vr1max : vr1min);
    1042                 :     792925 :   if (arith_overflowed_p (subcode, type, vr0max,
    1043                 :     482330 :                           subcode == MINUS_EXPR ? vr1min : vr1max) != *ovf)
    1044                 :            :     return false;
    1045                 :     127694 :   if (subcode == MULT_EXPR)
    1046                 :            :     {
    1047                 :      87760 :       if (arith_overflowed_p (subcode, type, vr0min, vr1max) != *ovf
    1048                 :      87760 :           || arith_overflowed_p (subcode, type, vr0max, vr1min) != *ovf)
    1049                 :       1345 :         return false;
    1050                 :            :     }
    1051                 :     126349 :   if (*ovf)
    1052                 :            :     {
    1053                 :            :       /* So far we found that there is an overflow on the boundaries.
    1054                 :            :          That doesn't prove that there is an overflow even for all values
    1055                 :            :          in between the boundaries.  For that compute widest_int range
    1056                 :            :          of the result and see if it doesn't overlap the range of
    1057                 :            :          type.  */
    1058                 :     123751 :       widest_int wmin, wmax;
    1059                 :     123751 :       widest_int w[4];
    1060                 :     123751 :       int i;
    1061                 :     123751 :       w[0] = wi::to_widest (vr0min);
    1062                 :     123751 :       w[1] = wi::to_widest (vr0max);
    1063                 :     123751 :       w[2] = wi::to_widest (vr1min);
    1064                 :     123751 :       w[3] = wi::to_widest (vr1max);
    1065                 :     618755 :       for (i = 0; i < 4; i++)
    1066                 :            :         {
    1067                 :     495004 :           widest_int wt;
    1068                 :     495004 :           switch (subcode)
    1069                 :            :             {
    1070                 :      68452 :             case PLUS_EXPR:
    1071                 :      68452 :               wt = wi::add (w[i & 1], w[2 + (i & 2) / 2]);
    1072                 :      68452 :               break;
    1073                 :      82568 :             case MINUS_EXPR:
    1074                 :      82568 :               wt = wi::sub (w[i & 1], w[2 + (i & 2) / 2]);
    1075                 :      82568 :               break;
    1076                 :     343984 :             case MULT_EXPR:
    1077                 :     343984 :               wt = wi::mul (w[i & 1], w[2 + (i & 2) / 2]);
    1078                 :     343984 :               break;
    1079                 :          0 :             default:
    1080                 :          0 :               gcc_unreachable ();
    1081                 :            :             }
    1082                 :     495004 :           if (i == 0)
    1083                 :            :             {
    1084                 :     123751 :               wmin = wt;
    1085                 :     123751 :               wmax = wt;
    1086                 :            :             }
    1087                 :            :           else
    1088                 :            :             {
    1089                 :     371253 :               wmin = wi::smin (wmin, wt);
    1090                 :     371253 :               wmax = wi::smax (wmax, wt);
    1091                 :            :             }
    1092                 :            :         }
    1093                 :            :       /* The result of op0 CODE op1 is known to be in range
    1094                 :            :          [wmin, wmax].  */
    1095                 :     123751 :       widest_int wtmin = wi::to_widest (vrp_val_min (type));
    1096                 :     123751 :       widest_int wtmax = wi::to_widest (vrp_val_max (type));
    1097                 :            :       /* If all values in [wmin, wmax] are smaller than
    1098                 :            :          [wtmin, wtmax] or all are larger than [wtmin, wtmax],
    1099                 :            :          the arithmetic operation will always overflow.  */
    1100                 :     246416 :       if (wmax < wtmin || wmin > wtmax)
    1101                 :       1806 :         return true;
    1102                 :            :       return false;
    1103                 :            :     }
    1104                 :            :   return true;
    1105                 :            : }
    1106                 :            : 
    1107                 :            : /* Try to derive a nonnegative or nonzero range out of STMT relying
    1108                 :            :    primarily on generic routines in fold in conjunction with range data.
    1109                 :            :    Store the result in *VR */
    1110                 :            : 
    1111                 :            : void
    1112                 :   36893000 : vr_values::extract_range_basic (value_range_equiv *vr, gimple *stmt)
    1113                 :            : {
    1114                 :   36893000 :   bool sop;
    1115                 :   36893000 :   tree type = gimple_expr_type (stmt);
    1116                 :            : 
    1117                 :   36893000 :   if (is_gimple_call (stmt))
    1118                 :            :     {
    1119                 :    7136080 :       tree arg;
    1120                 :    7136080 :       int mini, maxi, zerov = 0, prec;
    1121                 :    7136080 :       enum tree_code subcode = ERROR_MARK;
    1122                 :    7136080 :       combined_fn cfn = gimple_call_combined_fn (stmt);
    1123                 :    7136080 :       scalar_int_mode mode;
    1124                 :            : 
    1125                 :    7136080 :       switch (cfn)
    1126                 :            :         {
    1127                 :       3076 :         case CFN_BUILT_IN_CONSTANT_P:
    1128                 :            :           /* Resolve calls to __builtin_constant_p after inlining.  */
    1129                 :       3076 :           if (cfun->after_inlining)
    1130                 :            :             {
    1131                 :       1767 :               vr->set_zero (type);
    1132                 :       1767 :               vr->equiv_clear ();
    1133                 :     694542 :               return;
    1134                 :            :             }
    1135                 :            :           break;
    1136                 :            :           /* Both __builtin_ffs* and __builtin_popcount return
    1137                 :            :              [0, prec].  */
    1138                 :       1624 :         CASE_CFN_FFS:
    1139                 :       1624 :         CASE_CFN_POPCOUNT:
    1140                 :       1624 :           arg = gimple_call_arg (stmt, 0);
    1141                 :       1624 :           prec = TYPE_PRECISION (TREE_TYPE (arg));
    1142                 :       1624 :           mini = 0;
    1143                 :       1624 :           maxi = prec;
    1144                 :       1624 :           if (TREE_CODE (arg) == SSA_NAME)
    1145                 :            :             {
    1146                 :       1624 :               const value_range_equiv *vr0 = get_value_range (arg);
    1147                 :            :               /* If arg is non-zero, then ffs or popcount are non-zero.  */
    1148                 :       1624 :               if (range_includes_zero_p (vr0) == 0)
    1149                 :        116 :                 mini = 1;
    1150                 :            :               /* If some high bits are known to be zero,
    1151                 :            :                  we can decrease the maximum.  */
    1152                 :       1624 :               if (vr0->kind () == VR_RANGE
    1153                 :        310 :                   && TREE_CODE (vr0->max ()) == INTEGER_CST
    1154                 :       1934 :                   && !operand_less_p (vr0->min (),
    1155                 :        310 :                                       build_zero_cst (TREE_TYPE (vr0->min ()))))
    1156                 :        245 :                 maxi = tree_floor_log2 (vr0->max ()) + 1;
    1157                 :            :             }
    1158                 :       1624 :           goto bitop_builtin;
    1159                 :            :           /* __builtin_parity* returns [0, 1].  */
    1160                 :        701 :         CASE_CFN_PARITY:
    1161                 :        701 :           mini = 0;
    1162                 :        701 :           maxi = 1;
    1163                 :        701 :           goto bitop_builtin;
    1164                 :            :           /* __builtin_c[lt]z* return [0, prec-1], except for
    1165                 :            :              when the argument is 0, but that is undefined behavior.
    1166                 :            :              On many targets where the CLZ RTL or optab value is defined
    1167                 :            :              for 0 the value is prec, so include that in the range
    1168                 :            :              by default.  */
    1169                 :      11725 :         CASE_CFN_CLZ:
    1170                 :      11725 :           arg = gimple_call_arg (stmt, 0);
    1171                 :      11725 :           prec = TYPE_PRECISION (TREE_TYPE (arg));
    1172                 :      11725 :           mini = 0;
    1173                 :      11725 :           maxi = prec;
    1174                 :      11725 :           mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg));
    1175                 :      11725 :           if (optab_handler (clz_optab, mode) != CODE_FOR_nothing
    1176                 :      11311 :               && CLZ_DEFINED_VALUE_AT_ZERO (mode, zerov)
    1177                 :            :               /* Handle only the single common value.  */
    1178                 :      11745 :               && zerov != prec)
    1179                 :            :             /* Magic value to give up, unless vr0 proves
    1180                 :            :                arg is non-zero.  */
    1181                 :            :             mini = -2;
    1182                 :      11725 :           if (TREE_CODE (arg) == SSA_NAME)
    1183                 :            :             {
    1184                 :      11725 :               const value_range_equiv *vr0 = get_value_range (arg);
    1185                 :            :               /* From clz of VR_RANGE minimum we can compute
    1186                 :            :                  result maximum.  */
    1187                 :      11725 :               if (vr0->kind () == VR_RANGE
    1188                 :      11725 :                   && TREE_CODE (vr0->min ()) == INTEGER_CST)
    1189                 :            :                 {
    1190                 :       6710 :                   maxi = prec - 1 - tree_floor_log2 (vr0->min ());
    1191                 :       6710 :                   if (maxi != prec)
    1192                 :            :                     mini = 0;
    1193                 :            :                 }
    1194                 :       5015 :               else if (vr0->kind () == VR_ANTI_RANGE
    1195                 :       5015 :                        && integer_zerop (vr0->min ()))
    1196                 :            :                 {
    1197                 :          0 :                   maxi = prec - 1;
    1198                 :          0 :                   mini = 0;
    1199                 :            :                 }
    1200                 :       5188 :               if (mini == -2)
    1201                 :            :                 break;
    1202                 :            :               /* From clz of VR_RANGE maximum we can compute
    1203                 :            :                  result minimum.  */
    1204                 :      11725 :               if (vr0->kind () == VR_RANGE
    1205                 :      11725 :                   && TREE_CODE (vr0->max ()) == INTEGER_CST)
    1206                 :            :                 {
    1207                 :       6730 :                   mini = prec - 1 - tree_floor_log2 (vr0->max ());
    1208                 :       6730 :                   if (mini == prec)
    1209                 :            :                     break;
    1210                 :            :                 }
    1211                 :            :             }
    1212                 :      11725 :           if (mini == -2)
    1213                 :            :             break;
    1214                 :      11725 :           goto bitop_builtin;
    1215                 :            :           /* __builtin_ctz* return [0, prec-1], except for
    1216                 :            :              when the argument is 0, but that is undefined behavior.
    1217                 :            :              If there is a ctz optab for this mode and
    1218                 :            :              CTZ_DEFINED_VALUE_AT_ZERO, include that in the range,
    1219                 :            :              otherwise just assume 0 won't be seen.  */
    1220                 :       3350 :         CASE_CFN_CTZ:
    1221                 :       3350 :           arg = gimple_call_arg (stmt, 0);
    1222                 :       3350 :           prec = TYPE_PRECISION (TREE_TYPE (arg));
    1223                 :       3350 :           mini = 0;
    1224                 :       3350 :           maxi = prec - 1;
    1225                 :       3350 :           mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg));
    1226                 :       3350 :           if (optab_handler (ctz_optab, mode) != CODE_FOR_nothing
    1227                 :       6553 :               && CTZ_DEFINED_VALUE_AT_ZERO (mode, zerov))
    1228                 :            :             {
    1229                 :            :               /* Handle only the two common values.  */
    1230                 :         76 :               if (zerov == -1)
    1231                 :            :                 mini = -1;
    1232                 :         76 :               else if (zerov == prec)
    1233                 :         76 :                 maxi = prec;
    1234                 :            :               else
    1235                 :            :                 /* Magic value to give up, unless vr0 proves
    1236                 :            :                    arg is non-zero.  */
    1237                 :            :                 mini = -2;
    1238                 :            :             }
    1239                 :       3350 :           if (TREE_CODE (arg) == SSA_NAME)
    1240                 :            :             {
    1241                 :       3350 :               const value_range_equiv *vr0 = get_value_range (arg);
    1242                 :            :               /* If arg is non-zero, then use [0, prec - 1].  */
    1243                 :       3350 :               if ((vr0->kind () == VR_RANGE
    1244                 :       2126 :                    && integer_nonzerop (vr0->min ()))
    1245                 :       3412 :                   || (vr0->kind () == VR_ANTI_RANGE
    1246                 :         18 :                       && integer_zerop (vr0->min ())))
    1247                 :            :                 {
    1248                 :            :                   mini = 0;
    1249                 :            :                   maxi = prec - 1;
    1250                 :            :                 }
    1251                 :            :               /* If some high bits are known to be zero,
    1252                 :            :                  we can decrease the result maximum.  */
    1253                 :       3350 :               if (vr0->kind () == VR_RANGE
    1254                 :       3350 :                   && TREE_CODE (vr0->max ()) == INTEGER_CST)
    1255                 :            :                 {
    1256                 :       2104 :                   maxi = tree_floor_log2 (vr0->max ());
    1257                 :            :                   /* For vr0 [0, 0] give up.  */
    1258                 :       2104 :                   if (maxi == -1)
    1259                 :            :                     break;
    1260                 :            :                 }
    1261                 :            :             }
    1262                 :       3350 :           if (mini == -2)
    1263                 :            :             break;
    1264                 :       3350 :           goto bitop_builtin;
    1265                 :            :           /* __builtin_clrsb* returns [0, prec-1].  */
    1266                 :        177 :         CASE_CFN_CLRSB:
    1267                 :        177 :           arg = gimple_call_arg (stmt, 0);
    1268                 :        177 :           prec = TYPE_PRECISION (TREE_TYPE (arg));
    1269                 :        177 :           mini = 0;
    1270                 :        177 :           maxi = prec - 1;
    1271                 :        177 :           goto bitop_builtin;
    1272                 :      17577 :         bitop_builtin:
    1273                 :      17577 :           vr->set (build_int_cst (type, mini), build_int_cst (type, maxi));
    1274                 :      17577 :           return;
    1275                 :            :         case CFN_UBSAN_CHECK_ADD:
    1276                 :            :           subcode = PLUS_EXPR;
    1277                 :            :           break;
    1278                 :            :         case CFN_UBSAN_CHECK_SUB:
    1279                 :            :           subcode = MINUS_EXPR;
    1280                 :            :           break;
    1281                 :            :         case CFN_UBSAN_CHECK_MUL:
    1282                 :            :           subcode = MULT_EXPR;
    1283                 :            :           break;
    1284                 :          0 :         case CFN_GOACC_DIM_SIZE:
    1285                 :          0 :         case CFN_GOACC_DIM_POS:
    1286                 :            :           /* Optimizing these two internal functions helps the loop
    1287                 :            :              optimizer eliminate outer comparisons.  Size is [1,N]
    1288                 :            :              and pos is [0,N-1].  */
    1289                 :          0 :           {
    1290                 :          0 :             bool is_pos = cfn == CFN_GOACC_DIM_POS;
    1291                 :          0 :             int axis = oacc_get_ifn_dim_arg (stmt);
    1292                 :          0 :             int size = oacc_get_fn_dim_size (current_function_decl, axis);
    1293                 :            : 
    1294                 :          0 :             if (!size)
    1295                 :            :               /* If it's dynamic, the backend might know a hardware
    1296                 :            :                  limitation.  */
    1297                 :          0 :               size = targetm.goacc.dim_limit (axis);
    1298                 :            : 
    1299                 :          0 :             tree type = TREE_TYPE (gimple_call_lhs (stmt));
    1300                 :          0 :             vr->set(build_int_cst (type, is_pos ? 0 : 1),
    1301                 :            :                     size
    1302                 :          0 :                     ? build_int_cst (type, size - is_pos) : vrp_val_max (type));
    1303                 :            :           }
    1304                 :          0 :           return;
    1305                 :      85813 :         case CFN_BUILT_IN_STRLEN:
    1306                 :      85813 :           if (tree lhs = gimple_call_lhs (stmt))
    1307                 :      85813 :             if (ptrdiff_type_node
    1308                 :      85813 :                 && (TYPE_PRECISION (ptrdiff_type_node)
    1309                 :      85813 :                     == TYPE_PRECISION (TREE_TYPE (lhs))))
    1310                 :            :               {
    1311                 :      85813 :                 tree type = TREE_TYPE (lhs);
    1312                 :      85813 :                 tree max = vrp_val_max (ptrdiff_type_node);
    1313                 :      85813 :                 wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max)));
    1314                 :      85813 :                 tree range_min = build_zero_cst (type);
    1315                 :            :                 /* To account for the terminating NUL, the maximum length
    1316                 :            :                    is one less than the maximum array size, which in turn
    1317                 :            :                    is one  less than PTRDIFF_MAX (or SIZE_MAX where it's
    1318                 :            :                    smaller than the former type).
    1319                 :            :                    FIXME: Use max_object_size() - 1 here.  */
    1320                 :      85813 :                 tree range_max = wide_int_to_tree (type, wmax - 2);
    1321                 :      85813 :                 vr->set (range_min, range_max);
    1322                 :      85813 :                 return;
    1323                 :            :               }
    1324                 :            :           break;
    1325                 :            :         default:
    1326                 :            :           break;
    1327                 :            :         }
    1328                 :            :       if (subcode != ERROR_MARK)
    1329                 :            :         {
    1330                 :      22289 :           bool saved_flag_wrapv = flag_wrapv;
    1331                 :            :           /* Pretend the arithmetics is wrapping.  If there is
    1332                 :            :              any overflow, we'll complain, but will actually do
    1333                 :            :              wrapping operation.  */
    1334                 :      22289 :           flag_wrapv = 1;
    1335                 :      22289 :           extract_range_from_binary_expr (vr, subcode, type,
    1336                 :            :                                           gimple_call_arg (stmt, 0),
    1337                 :            :                                           gimple_call_arg (stmt, 1));
    1338                 :      22289 :           flag_wrapv = saved_flag_wrapv;
    1339                 :            : 
    1340                 :            :           /* If for both arguments vrp_valueize returned non-NULL,
    1341                 :            :              this should have been already folded and if not, it
    1342                 :            :              wasn't folded because of overflow.  Avoid removing the
    1343                 :            :              UBSAN_CHECK_* calls in that case.  */
    1344                 :      22289 :           if (vr->kind () == VR_RANGE
    1345                 :      22289 :               && (vr->min () == vr->max ()
    1346                 :       1477 :                   || operand_equal_p (vr->min (), vr->max (), 0)))
    1347                 :        444 :             vr->set_varying (vr->type ());
    1348                 :      22289 :           return;
    1349                 :            :         }
    1350                 :            :     }
    1351                 :            :   /* Handle extraction of the two results (result of arithmetics and
    1352                 :            :      a flag whether arithmetics overflowed) from {ADD,SUB,MUL}_OVERFLOW
    1353                 :            :      internal function.  Similarly from ATOMIC_COMPARE_EXCHANGE.  */
    1354                 :   29757000 :   else if (is_gimple_assign (stmt)
    1355                 :   29757000 :            && (gimple_assign_rhs_code (stmt) == REALPART_EXPR
    1356                 :   29546900 :                || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR)
    1357                 :   30396800 :            && INTEGRAL_TYPE_P (type))
    1358                 :            :     {
    1359                 :     639866 :       enum tree_code code = gimple_assign_rhs_code (stmt);
    1360                 :     639866 :       tree op = gimple_assign_rhs1 (stmt);
    1361                 :     639866 :       if (TREE_CODE (op) == code && TREE_CODE (TREE_OPERAND (op, 0)) == SSA_NAME)
    1362                 :            :         {
    1363                 :     639714 :           gimple *g = SSA_NAME_DEF_STMT (TREE_OPERAND (op, 0));
    1364                 :     639714 :           if (is_gimple_call (g) && gimple_call_internal_p (g))
    1365                 :            :             {
    1366                 :     637049 :               enum tree_code subcode = ERROR_MARK;
    1367                 :     637049 :               switch (gimple_call_internal_fn (g))
    1368                 :            :                 {
    1369                 :     124379 :                 case IFN_ADD_OVERFLOW:
    1370                 :     124379 :                   subcode = PLUS_EXPR;
    1371                 :     124379 :                   break;
    1372                 :     169068 :                 case IFN_SUB_OVERFLOW:
    1373                 :     169068 :                   subcode = MINUS_EXPR;
    1374                 :     169068 :                   break;
    1375                 :            :                 case IFN_MUL_OVERFLOW:
    1376                 :            :                   subcode = MULT_EXPR;
    1377                 :            :                   break;
    1378                 :     157598 :                 case IFN_ATOMIC_COMPARE_EXCHANGE:
    1379                 :     157598 :                   if (code == IMAGPART_EXPR)
    1380                 :            :                     {
    1381                 :            :                       /* This is the boolean return value whether compare and
    1382                 :            :                          exchange changed anything or not.  */
    1383                 :      85878 :                       vr->set (build_int_cst (type, 0),
    1384                 :      85878 :                                build_int_cst (type, 1));
    1385                 :      85878 :                       return;
    1386                 :            :                     }
    1387                 :            :                   break;
    1388                 :            :                 default:
    1389                 :            :                   break;
    1390                 :            :                 }
    1391                 :     293447 :               if (subcode != ERROR_MARK)
    1392                 :            :                 {
    1393                 :     479451 :                   tree op0 = gimple_call_arg (g, 0);
    1394                 :     479451 :                   tree op1 = gimple_call_arg (g, 1);
    1395                 :     479451 :                   if (code == IMAGPART_EXPR)
    1396                 :            :                     {
    1397                 :     342966 :                       bool ovf = false;
    1398                 :     342966 :                       if (check_for_binary_op_overflow (subcode, type,
    1399                 :            :                                                         op0, op1, &ovf))
    1400                 :        477 :                         vr->set (build_int_cst (type, ovf));
    1401                 :     342489 :                       else if (TYPE_PRECISION (type) == 1
    1402                 :     342489 :                                && !TYPE_UNSIGNED (type))
    1403                 :        516 :                         vr->set_varying (type);
    1404                 :            :                       else
    1405                 :     341973 :                         vr->set (build_int_cst (type, 0),
    1406                 :     341973 :                                  build_int_cst (type, 1));
    1407                 :            :                     }
    1408                 :     136485 :                   else if (types_compatible_p (type, TREE_TYPE (op0))
    1409                 :     204282 :                            && types_compatible_p (type, TREE_TYPE (op1)))
    1410                 :            :                     {
    1411                 :      49766 :                       bool saved_flag_wrapv = flag_wrapv;
    1412                 :            :                       /* Pretend the arithmetics is wrapping.  If there is
    1413                 :            :                          any overflow, IMAGPART_EXPR will be set.  */
    1414                 :      49766 :                       flag_wrapv = 1;
    1415                 :      49766 :                       extract_range_from_binary_expr (vr, subcode, type,
    1416                 :            :                                                       op0, op1);
    1417                 :      49766 :                       flag_wrapv = saved_flag_wrapv;
    1418                 :            :                     }
    1419                 :            :                   else
    1420                 :            :                     {
    1421                 :      86719 :                       value_range_equiv vr0, vr1;
    1422                 :      86719 :                       bool saved_flag_wrapv = flag_wrapv;
    1423                 :            :                       /* Pretend the arithmetics is wrapping.  If there is
    1424                 :            :                          any overflow, IMAGPART_EXPR will be set.  */
    1425                 :      86719 :                       flag_wrapv = 1;
    1426                 :      86719 :                       extract_range_from_unary_expr (&vr0, NOP_EXPR,
    1427                 :            :                                                      type, op0);
    1428                 :      86719 :                       extract_range_from_unary_expr (&vr1, NOP_EXPR,
    1429                 :            :                                                      type, op1);
    1430                 :      86719 :                       range_fold_binary_expr (vr, subcode, type, &vr0, &vr1);
    1431                 :      86719 :                       flag_wrapv = saved_flag_wrapv;
    1432                 :            :                     }
    1433                 :     479451 :                   return;
    1434                 :            :                 }
    1435                 :            :             }
    1436                 :            :         }
    1437                 :            :     }
    1438                 :   36200300 :   if (INTEGRAL_TYPE_P (type)
    1439                 :   36200300 :       && gimple_stmt_nonnegative_warnv_p (stmt, &sop))
    1440                 :   17385700 :     set_value_range_to_nonnegative (vr, type);
    1441                 :   18814500 :   else if (vrp_stmt_computes_nonzero (stmt))
    1442                 :            :     {
    1443                 :    2382530 :       vr->set_nonzero (type);
    1444                 :    2382530 :       vr->equiv_clear ();
    1445                 :            :     }
    1446                 :            :   else
    1447                 :   16432000 :     vr->set_varying (type);
    1448                 :            : }
    1449                 :            : 
    1450                 :            : 
    1451                 :            : /* Try to compute a useful range out of assignment STMT and store it
    1452                 :            :    in *VR.  */
    1453                 :            : 
    1454                 :            : void
    1455                 :   58952400 : vr_values::extract_range_from_assignment (value_range_equiv *vr, gassign *stmt)
    1456                 :            : {
    1457                 :   58952400 :   enum tree_code code = gimple_assign_rhs_code (stmt);
    1458                 :            : 
    1459                 :   58952400 :   if (code == ASSERT_EXPR)
    1460                 :    7232270 :     extract_range_from_assert (vr, gimple_assign_rhs1 (stmt));
    1461                 :   51720100 :   else if (code == SSA_NAME)
    1462                 :    1053960 :     extract_range_from_ssa_name (vr, gimple_assign_rhs1 (stmt));
    1463                 :   50666100 :   else if (TREE_CODE_CLASS (code) == tcc_binary)
    1464                 :   58021800 :     extract_range_from_binary_expr (vr, gimple_assign_rhs_code (stmt),
    1465                 :            :                                     gimple_expr_type (stmt),
    1466                 :            :                                     gimple_assign_rhs1 (stmt),
    1467                 :            :                                     gimple_assign_rhs2 (stmt));
    1468                 :   21655300 :   else if (TREE_CODE_CLASS (code) == tcc_unary)
    1469                 :   14370400 :     extract_range_from_unary_expr (vr, gimple_assign_rhs_code (stmt),
    1470                 :            :                                    gimple_expr_type (stmt),
    1471                 :            :                                    gimple_assign_rhs1 (stmt));
    1472                 :    7284900 :   else if (code == COND_EXPR)
    1473                 :      99066 :     extract_range_from_cond_expr (vr, stmt);
    1474                 :    7185840 :   else if (TREE_CODE_CLASS (code) == tcc_comparison)
    1475                 :    7295330 :     extract_range_from_comparison (vr, gimple_assign_rhs_code (stmt),
    1476                 :            :                                    gimple_expr_type (stmt),
    1477                 :            :                                    gimple_assign_rhs1 (stmt),
    1478                 :            :                                    gimple_assign_rhs2 (stmt));
    1479                 :    3538170 :   else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
    1480                 :    3538170 :            && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
    1481                 :          0 :     vr->set (gimple_assign_rhs1 (stmt));
    1482                 :            :   else
    1483                 :    3538170 :     vr->set_varying (TREE_TYPE (gimple_assign_lhs (stmt)));
    1484                 :            : 
    1485                 :   58952400 :   if (vr->varying_p ())
    1486                 :   29646100 :     extract_range_basic (vr, stmt);
    1487                 :   58952400 : }
    1488                 :            : 
    1489                 :            : /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
    1490                 :            : 
    1491                 :            :    - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
    1492                 :            :      all the values in the ranges.
    1493                 :            : 
    1494                 :            :    - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
    1495                 :            : 
    1496                 :            :    - Return NULL_TREE if it is not always possible to determine the
    1497                 :            :      value of the comparison.
    1498                 :            : 
    1499                 :            :    Also set *STRICT_OVERFLOW_P to indicate whether comparision evaluation
    1500                 :            :    assumed signed overflow is undefined.  */
    1501                 :            : 
    1502                 :            : 
    1503                 :            : static tree
    1504                 :  284743000 : compare_ranges (enum tree_code comp, const value_range_equiv *vr0,
    1505                 :            :                 const value_range_equiv *vr1, bool *strict_overflow_p)
    1506                 :            : {
    1507                 :            :   /* VARYING or UNDEFINED ranges cannot be compared.  */
    1508                 :  284743000 :   if (vr0->varying_p ()
    1509                 :  280493000 :       || vr0->undefined_p ()
    1510                 :  280489000 :       || vr1->varying_p ()
    1511                 :  564195000 :       || vr1->undefined_p ())
    1512                 :            :     return NULL_TREE;
    1513                 :            : 
    1514                 :            :   /* Anti-ranges need to be handled separately.  */
    1515                 :  279450000 :   if (vr0->kind () == VR_ANTI_RANGE || vr1->kind () == VR_ANTI_RANGE)
    1516                 :            :     {
    1517                 :            :       /* If both are anti-ranges, then we cannot compute any
    1518                 :            :          comparison.  */
    1519                 :     977176 :       if (vr0->kind () == VR_ANTI_RANGE && vr1->kind () == VR_ANTI_RANGE)
    1520                 :            :         return NULL_TREE;
    1521                 :            : 
    1522                 :            :       /* These comparisons are never statically computable.  */
    1523                 :     815691 :       if (comp == GT_EXPR
    1524                 :     815691 :           || comp == GE_EXPR
    1525                 :     815691 :           || comp == LT_EXPR
    1526                 :     583230 :           || comp == LE_EXPR)
    1527                 :            :         return NULL_TREE;
    1528                 :            : 
    1529                 :            :       /* Equality can be computed only between a range and an
    1530                 :            :          anti-range.  ~[VAL1, VAL2] == [VAL1, VAL2] is always false.  */
    1531                 :     532481 :       if (vr0->kind () == VR_RANGE)
    1532                 :            :         /* To simplify processing, make VR0 the anti-range.  */
    1533                 :     179874 :         std::swap (vr0, vr1);
    1534                 :            : 
    1535                 :     532481 :       gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
    1536                 :            : 
    1537                 :     532481 :       if (compare_values_warnv (vr0->min (), vr1->min (), strict_overflow_p) == 0
    1538                 :     532481 :           && compare_values_warnv (vr0->max (), vr1->max (), strict_overflow_p) == 0)
    1539                 :        405 :         return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
    1540                 :            : 
    1541                 :     532076 :       return NULL_TREE;
    1542                 :            :     }
    1543                 :            : 
    1544                 :            :   /* Simplify processing.  If COMP is GT_EXPR or GE_EXPR, switch the
    1545                 :            :      operands around and change the comparison code.  */
    1546                 :  278473000 :   if (comp == GT_EXPR || comp == GE_EXPR)
    1547                 :            :     {
    1548                 :  136143000 :       comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
    1549                 :  278473000 :       std::swap (vr0, vr1);
    1550                 :            :     }
    1551                 :            : 
    1552                 :  278473000 :   if (comp == EQ_EXPR)
    1553                 :            :     {
    1554                 :            :       /* Equality may only be computed if both ranges represent
    1555                 :            :          exactly one value.  */
    1556                 :     986448 :       if (compare_values_warnv (vr0->min (), vr0->max (), strict_overflow_p) == 0
    1557                 :     986448 :           && compare_values_warnv (vr1->min (), vr1->max (), strict_overflow_p) == 0)
    1558                 :            :         {
    1559                 :     495798 :           int cmp_min = compare_values_warnv (vr0->min (), vr1->min (),
    1560                 :            :                                               strict_overflow_p);
    1561                 :     495798 :           int cmp_max = compare_values_warnv (vr0->max (), vr1->max (),
    1562                 :            :                                               strict_overflow_p);
    1563                 :     495798 :           if (cmp_min == 0 && cmp_max == 0)
    1564                 :       2308 :             return boolean_true_node;
    1565                 :     493490 :           else if (cmp_min != -2 && cmp_max != -2)
    1566                 :       1262 :             return boolean_false_node;
    1567                 :            :         }
    1568                 :            :       /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1.  */
    1569                 :     490650 :       else if (compare_values_warnv (vr0->min (), vr1->max (),
    1570                 :            :                                      strict_overflow_p) == 1
    1571                 :     490650 :                || compare_values_warnv (vr1->min (), vr0->max (),
    1572                 :            :                                         strict_overflow_p) == 1)
    1573                 :       2657 :         return boolean_false_node;
    1574                 :            : 
    1575                 :     980221 :       return NULL_TREE;
    1576                 :            :     }
    1577                 :  277486000 :   else if (comp == NE_EXPR)
    1578                 :            :     {
    1579                 :    1725860 :       int cmp1, cmp2;
    1580                 :            : 
    1581                 :            :       /* If VR0 is completely to the left or completely to the right
    1582                 :            :          of VR1, they are always different.  Notice that we need to
    1583                 :            :          make sure that both comparisons yield similar results to
    1584                 :            :          avoid comparing values that cannot be compared at
    1585                 :            :          compile-time.  */
    1586                 :    1725860 :       cmp1 = compare_values_warnv (vr0->max (), vr1->min (), strict_overflow_p);
    1587                 :    1725860 :       cmp2 = compare_values_warnv (vr0->min (), vr1->max (), strict_overflow_p);
    1588                 :    1725860 :       if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
    1589                 :       5203 :         return boolean_true_node;
    1590                 :            : 
    1591                 :            :       /* If VR0 and VR1 represent a single value and are identical,
    1592                 :            :          return false.  */
    1593                 :    1720660 :       else if (compare_values_warnv (vr0->min (), vr0->max (),
    1594                 :            :                                      strict_overflow_p) == 0
    1595                 :     923842 :                && compare_values_warnv (vr1->min (), vr1->max (),
    1596                 :            :                                         strict_overflow_p) == 0
    1597                 :     659963 :                && compare_values_warnv (vr0->min (), vr1->min (),
    1598                 :            :                                         strict_overflow_p) == 0
    1599                 :    1724270 :                && compare_values_warnv (vr0->max (), vr1->max (),
    1600                 :            :                                         strict_overflow_p) == 0)
    1601                 :       3614 :         return boolean_false_node;
    1602                 :            : 
    1603                 :            :       /* Otherwise, they may or may not be different.  */
    1604                 :            :       else
    1605                 :    1717040 :         return NULL_TREE;
    1606                 :            :     }
    1607                 :  275760000 :   else if (comp == LT_EXPR || comp == LE_EXPR)
    1608                 :            :     {
    1609                 :  275760000 :       int tst;
    1610                 :            : 
    1611                 :            :       /* If VR0 is to the left of VR1, return true.  */
    1612                 :  275760000 :       tst = compare_values_warnv (vr0->max (), vr1->min (), strict_overflow_p);
    1613                 :  275760000 :       if ((comp == LT_EXPR && tst == -1)
    1614                 :  275741000 :           || (comp == LE_EXPR && (tst == -1 || tst == 0)))
    1615                 :      33842 :         return boolean_true_node;
    1616                 :            : 
    1617                 :            :       /* If VR0 is to the right of VR1, return false.  */
    1618                 :  275727000 :       tst = compare_values_warnv (vr0->min (), vr1->max (), strict_overflow_p);
    1619                 :  275727000 :       if ((comp == LT_EXPR && (tst == 0 || tst == 1))
    1620                 :  275713000 :           || (comp == LE_EXPR && tst == 1))
    1621                 :      16770 :         return boolean_false_node;
    1622                 :            : 
    1623                 :            :       /* Otherwise, we don't know.  */
    1624                 :            :       return NULL_TREE;
    1625                 :            :     }
    1626                 :            : 
    1627                 :          0 :   gcc_unreachable ();
    1628                 :            : }
    1629                 :            : 
    1630                 :            : /* Given a value range VR, a value VAL and a comparison code COMP, return
    1631                 :            :    BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
    1632                 :            :    values in VR.  Return BOOLEAN_FALSE_NODE if the comparison
    1633                 :            :    always returns false.  Return NULL_TREE if it is not always
    1634                 :            :    possible to determine the value of the comparison.  Also set
    1635                 :            :    *STRICT_OVERFLOW_P to indicate whether comparision evaluation
    1636                 :            :    assumed signed overflow is undefined.  */
    1637                 :            : 
    1638                 :            : static tree
    1639                 :   73737900 : compare_range_with_value (enum tree_code comp, const value_range_equiv *vr,
    1640                 :            :                           tree val, bool *strict_overflow_p)
    1641                 :            : {
    1642                 :   73737900 :   if (vr->varying_p () || vr->undefined_p ())
    1643                 :            :     return NULL_TREE;
    1644                 :            : 
    1645                 :            :   /* Anti-ranges need to be handled separately.  */
    1646                 :   45991600 :   if (vr->kind () == VR_ANTI_RANGE)
    1647                 :            :     {
    1648                 :            :       /* For anti-ranges, the only predicates that we can compute at
    1649                 :            :          compile time are equality and inequality.  */
    1650                 :    2727840 :       if (comp == GT_EXPR
    1651                 :    2727840 :           || comp == GE_EXPR
    1652                 :    2727840 :           || comp == LT_EXPR
    1653                 :    1918080 :           || comp == LE_EXPR)
    1654                 :            :         return NULL_TREE;
    1655                 :            : 
    1656                 :            :       /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2.  */
    1657                 :    1700900 :       if (!vr->may_contain_p (val))
    1658                 :      11578 :         return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
    1659                 :            : 
    1660                 :            :       return NULL_TREE;
    1661                 :            :     }
    1662                 :            : 
    1663                 :   43263800 :   if (comp == EQ_EXPR)
    1664                 :            :     {
    1665                 :            :       /* EQ_EXPR may only be computed if VR represents exactly
    1666                 :            :          one value.  */
    1667                 :   10806300 :       if (compare_values_warnv (vr->min (), vr->max (), strict_overflow_p) == 0)
    1668                 :            :         {
    1669                 :    7528130 :           int cmp = compare_values_warnv (vr->min (), val, strict_overflow_p);
    1670                 :    7528130 :           if (cmp == 0)
    1671                 :      15030 :             return boolean_true_node;
    1672                 :    7513100 :           else if (cmp == -1 || cmp == 1 || cmp == 2)
    1673                 :      88162 :             return boolean_false_node;
    1674                 :            :         }
    1675                 :    3278120 :       else if (compare_values_warnv (val, vr->min (), strict_overflow_p) == -1
    1676                 :    3278120 :                || compare_values_warnv (vr->max (), val, strict_overflow_p) == -1)
    1677                 :     127692 :         return boolean_false_node;
    1678                 :            : 
    1679                 :   10575400 :       return NULL_TREE;
    1680                 :            :     }
    1681                 :   32457600 :   else if (comp == NE_EXPR)
    1682                 :            :     {
    1683                 :            :       /* If VAL is not inside VR, then they are always different.  */
    1684                 :   16464400 :       if (compare_values_warnv (vr->max (), val, strict_overflow_p) == -1
    1685                 :   16464400 :           || compare_values_warnv (vr->min (), val, strict_overflow_p) == 1)
    1686                 :     313307 :         return boolean_true_node;
    1687                 :            : 
    1688                 :            :       /* If VR represents exactly one value equal to VAL, then return
    1689                 :            :          false.  */
    1690                 :   16151100 :       if (compare_values_warnv (vr->min (), vr->max (), strict_overflow_p) == 0
    1691                 :   16151100 :           && compare_values_warnv (vr->min (), val, strict_overflow_p) == 0)
    1692                 :      33592 :         return boolean_false_node;
    1693                 :            : 
    1694                 :            :       /* Otherwise, they may or may not be different.  */
    1695                 :   16117500 :       return NULL_TREE;
    1696                 :            :     }
    1697                 :   15993100 :   else if (comp == LT_EXPR || comp == LE_EXPR)
    1698                 :            :     {
    1699                 :    7348760 :       int tst;
    1700                 :            : 
    1701                 :            :       /* If VR is to the left of VAL, return true.  */
    1702                 :    7348760 :       tst = compare_values_warnv (vr->max (), val, strict_overflow_p);
    1703                 :    7348760 :       if ((comp == LT_EXPR && tst == -1)
    1704                 :    7347750 :           || (comp == LE_EXPR && (tst == -1 || tst == 0)))
    1705                 :      52369 :         return boolean_true_node;
    1706                 :            : 
    1707                 :            :       /* If VR is to the right of VAL, return false.  */
    1708                 :    7296390 :       tst = compare_values_warnv (vr->min (), val, strict_overflow_p);
    1709                 :    7296390 :       if ((comp == LT_EXPR && (tst == 0 || tst == 1))
    1710                 :    7289260 :           || (comp == LE_EXPR && tst == 1))
    1711                 :      20864 :         return boolean_false_node;
    1712                 :            : 
    1713                 :            :       /* Otherwise, we don't know.  */
    1714                 :            :       return NULL_TREE;
    1715                 :            :     }
    1716                 :    8644370 :   else if (comp == GT_EXPR || comp == GE_EXPR)
    1717                 :            :     {
    1718                 :    8644370 :       int tst;
    1719                 :            : 
    1720                 :            :       /* If VR is to the right of VAL, return true.  */
    1721                 :    8644370 :       tst = compare_values_warnv (vr->min (), val, strict_overflow_p);
    1722                 :    8644370 :       if ((comp == GT_EXPR && tst == 1)
    1723                 :    8619070 :           || (comp == GE_EXPR && (tst == 0 || tst == 1)))
    1724                 :      96122 :         return boolean_true_node;
    1725                 :            : 
    1726                 :            :       /* If VR is to the left of VAL, return false.  */
    1727                 :    8548250 :       tst = compare_values_warnv (vr->max (), val, strict_overflow_p);
    1728                 :    8548250 :       if ((comp == GT_EXPR && (tst == -1 || tst == 0))
    1729                 :    8516300 :           || (comp == GE_EXPR && tst == -1))
    1730                 :      33577 :         return boolean_false_node;
    1731                 :            : 
    1732                 :            :       /* Otherwise, we don't know.  */
    1733                 :            :       return NULL_TREE;
    1734                 :            :     }
    1735                 :            : 
    1736                 :          0 :   gcc_unreachable ();
    1737                 :            : }
    1738                 :            : /* Given a range VR, a LOOP and a variable VAR, determine whether it
    1739                 :            :    would be profitable to adjust VR using scalar evolution information
    1740                 :            :    for VAR.  If so, update VR with the new limits.  */
    1741                 :            : 
    1742                 :            : void
    1743                 :    2094250 : vr_values::adjust_range_with_scev (value_range_equiv *vr, class loop *loop,
    1744                 :            :                                    gimple *stmt, tree var)
    1745                 :            : {
    1746                 :    2094250 :   tree init, step, chrec, tmin, tmax, min, max, type, tem;
    1747                 :    2094250 :   enum ev_direction dir;
    1748                 :            : 
    1749                 :            :   /* TODO.  Don't adjust anti-ranges.  An anti-range may provide
    1750                 :            :      better opportunities than a regular range, but I'm not sure.  */
    1751                 :    2094250 :   if (vr->kind () == VR_ANTI_RANGE)
    1752                 :            :     return;
    1753                 :            : 
    1754                 :    2094250 :   chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
    1755                 :            : 
    1756                 :            :   /* Like in PR19590, scev can return a constant function.  */
    1757                 :    2094250 :   if (is_gimple_min_invariant (chrec))
    1758                 :            :     {
    1759                 :         43 :       vr->set (chrec);
    1760                 :         43 :       return;
    1761                 :            :     }
    1762                 :            : 
    1763                 :    2094210 :   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
    1764                 :            :     return;
    1765                 :            : 
    1766                 :    1427570 :   init = initial_condition_in_loop_num (chrec, loop->num);
    1767                 :    1427570 :   tem = op_with_constant_singleton_value_range (init);
    1768                 :    1427570 :   if (tem)
    1769                 :     892237 :     init = tem;
    1770                 :    1427570 :   step = evolution_part_in_loop_num (chrec, loop->num);
    1771                 :    1427570 :   tem = op_with_constant_singleton_value_range (step);
    1772                 :    1427570 :   if (tem)
    1773                 :    1315450 :     step = tem;
    1774                 :            : 
    1775                 :            :   /* If STEP is symbolic, we can't know whether INIT will be the
    1776                 :            :      minimum or maximum value in the range.  Also, unless INIT is
    1777                 :            :      a simple expression, compare_values and possibly other functions
    1778                 :            :      in tree-vrp won't be able to handle it.  */
    1779                 :    1427570 :   if (step == NULL_TREE
    1780                 :    1427570 :       || !is_gimple_min_invariant (step)
    1781                 :    2743020 :       || !valid_value_p (init))
    1782                 :     112124 :     return;
    1783                 :            : 
    1784                 :    1315450 :   dir = scev_direction (chrec);
    1785                 :    1315450 :   if (/* Do not adjust ranges if we do not know whether the iv increases
    1786                 :            :          or decreases,  ... */
    1787                 :            :       dir == EV_DIR_UNKNOWN
    1788                 :            :       /* ... or if it may wrap.  */
    1789                 :    1315450 :       || scev_probably_wraps_p (NULL_TREE, init, step, stmt,
    1790                 :            :                                 get_chrec_loop (chrec), true))
    1791                 :     279270 :     return;
    1792                 :            : 
    1793                 :    1036180 :   type = TREE_TYPE (var);
    1794                 :    1036180 :   if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
    1795                 :     139630 :     tmin = lower_bound_in_type (type, type);
    1796                 :            :   else
    1797                 :     896549 :     tmin = TYPE_MIN_VALUE (type);
    1798                 :    1036180 :   if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
    1799                 :     139630 :     tmax = upper_bound_in_type (type, type);
    1800                 :            :   else
    1801                 :     896549 :     tmax = TYPE_MAX_VALUE (type);
    1802                 :            : 
    1803                 :            :   /* Try to use estimated number of iterations for the loop to constrain the
    1804                 :            :      final value in the evolution.  */
    1805                 :    1036180 :   if (TREE_CODE (step) == INTEGER_CST
    1806                 :    1036180 :       && is_gimple_val (init)
    1807                 :    2072360 :       && (TREE_CODE (init) != SSA_NAME
    1808                 :     229146 :           || get_value_range (init)->kind () == VR_RANGE))
    1809                 :            :     {
    1810                 :     894918 :       widest_int nit;
    1811                 :            : 
    1812                 :            :       /* We are only entering here for loop header PHI nodes, so using
    1813                 :            :          the number of latch executions is the correct thing to use.  */
    1814                 :     894918 :       if (max_loop_iterations (loop, &nit))
    1815                 :            :         {
    1816                 :     883562 :           signop sgn = TYPE_SIGN (TREE_TYPE (step));
    1817                 :     883562 :           wi::overflow_type overflow;
    1818                 :            : 
    1819                 :     883562 :           widest_int wtmp = wi::mul (wi::to_widest (step), nit, sgn,
    1820                 :     883562 :                                      &overflow);
    1821                 :            :           /* If the multiplication overflowed we can't do a meaningful
    1822                 :            :              adjustment.  Likewise if the result doesn't fit in the type
    1823                 :            :              of the induction variable.  For a signed type we have to
    1824                 :            :              check whether the result has the expected signedness which
    1825                 :            :              is that of the step as number of iterations is unsigned.  */
    1826                 :     883562 :           if (!overflow
    1827                 :     883562 :               && wi::fits_to_tree_p (wtmp, TREE_TYPE (init))
    1828                 :    1725720 :               && (sgn == UNSIGNED
    1829                 :     586315 :                   || wi::gts_p (wtmp, 0) == wi::gts_p (wi::to_wide (step), 0)))
    1830                 :            :             {
    1831                 :     841966 :               value_range_equiv maxvr;
    1832                 :     841966 :               tem = wide_int_to_tree (TREE_TYPE (init), wtmp);
    1833                 :     841966 :               extract_range_from_binary_expr (&maxvr, PLUS_EXPR,
    1834                 :     841966 :                                               TREE_TYPE (init), init, tem);
    1835                 :            :               /* Likewise if the addition did.  */
    1836                 :     841966 :               if (maxvr.kind () == VR_RANGE)
    1837                 :            :                 {
    1838                 :     810320 :                   value_range initvr;
    1839                 :            : 
    1840                 :     810320 :                   if (TREE_CODE (init) == SSA_NAME)
    1841                 :      42053 :                     initvr = *(get_value_range (init));
    1842                 :     768267 :                   else if (is_gimple_min_invariant (init))
    1843                 :     768267 :                     initvr.set (init);
    1844                 :            :                   else
    1845                 :       4441 :                     return;
    1846                 :            : 
    1847                 :            :                   /* Check if init + nit * step overflows.  Though we checked
    1848                 :            :                      scev {init, step}_loop doesn't wrap, it is not enough
    1849                 :            :                      because the loop may exit immediately.  Overflow could
    1850                 :            :                      happen in the plus expression in this case.  */
    1851                 :     810320 :                   if ((dir == EV_DIR_DECREASES
    1852                 :      23071 :                        && compare_values (maxvr.min (), initvr.min ()) != -1)
    1853                 :     832556 :                       || (dir == EV_DIR_GROWS
    1854                 :     787249 :                           && compare_values (maxvr.max (), initvr.max ()) != 1))
    1855                 :       4441 :                     return;
    1856                 :            : 
    1857                 :     805879 :                   tmin = maxvr.min ();
    1858                 :     805879 :                   tmax = maxvr.max ();
    1859                 :            :                 }
    1860                 :            :             }
    1861                 :            :         }
    1862                 :            :     }
    1863                 :            : 
    1864                 :    1031740 :   if (vr->varying_p () || vr->undefined_p ())
    1865                 :            :     {
    1866                 :     662958 :       min = tmin;
    1867                 :     662958 :       max = tmax;
    1868                 :            : 
    1869                 :            :       /* For VARYING or UNDEFINED ranges, just about anything we get
    1870                 :            :          from scalar evolutions should be better.  */
    1871                 :            : 
    1872                 :     662958 :       if (dir == EV_DIR_DECREASES)
    1873                 :            :         max = init;
    1874                 :            :       else
    1875                 :     605023 :         min = init;
    1876                 :            :     }
    1877                 :     368780 :   else if (vr->kind () == VR_RANGE)
    1878                 :            :     {
    1879                 :     368780 :       min = vr->min ();
    1880                 :     368780 :       max = vr->max ();
    1881                 :            : 
    1882                 :     368780 :       if (dir == EV_DIR_DECREASES)
    1883                 :            :         {
    1884                 :            :           /* INIT is the maximum value.  If INIT is lower than VR->MAX ()
    1885                 :            :              but no smaller than VR->MIN (), set VR->MAX () to INIT.  */
    1886                 :      15863 :           if (compare_values (init, max) == -1)
    1887                 :         12 :             max = init;
    1888                 :            : 
    1889                 :            :           /* According to the loop information, the variable does not
    1890                 :            :              overflow.  */
    1891                 :      15863 :           if (compare_values (min, tmin) == -1)
    1892                 :       6780 :             min = tmin;
    1893                 :            : 
    1894                 :            :         }
    1895                 :            :       else
    1896                 :            :         {
    1897                 :            :           /* If INIT is bigger than VR->MIN (), set VR->MIN () to INIT.  */
    1898                 :     352917 :           if (compare_values (init, min) == 1)
    1899                 :         86 :             min = init;
    1900                 :            : 
    1901                 :     352917 :           if (compare_values (tmax, max) == -1)
    1902                 :     303230 :             max = tmax;
    1903                 :            :         }
    1904                 :            :     }
    1905                 :            :   else
    1906                 :            :     return;
    1907                 :            : 
    1908                 :            :   /* If we just created an invalid range with the minimum
    1909                 :            :      greater than the maximum, we fail conservatively.
    1910                 :            :      This should happen only in unreachable
    1911                 :            :      parts of code, or for invalid programs.  */
    1912                 :    1031740 :   if (compare_values (min, max) == 1)
    1913                 :            :     return;
    1914                 :            : 
    1915                 :            :   /* Even for valid range info, sometimes overflow flag will leak in.
    1916                 :            :      As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
    1917                 :            :      drop them.  */
    1918                 :    1031740 :   if (TREE_OVERFLOW_P (min))
    1919                 :          0 :     min = drop_tree_overflow (min);
    1920                 :    1031740 :   if (TREE_OVERFLOW_P (max))
    1921                 :          0 :     max = drop_tree_overflow (max);
    1922                 :            : 
    1923                 :    1031740 :   vr->update (min, max);
    1924                 :            : }
    1925                 :            : 
    1926                 :            : /* Dump value ranges of all SSA_NAMEs to FILE.  */
    1927                 :            : 
    1928                 :            : void
    1929                 :        961 : vr_values::dump_all_value_ranges (FILE *file)
    1930                 :            : {
    1931                 :        961 :   size_t i;
    1932                 :            : 
    1933                 :      22049 :   for (i = 0; i < num_vr_values; i++)
    1934                 :            :     {
    1935                 :      21088 :       if (vr_value[i])
    1936                 :            :         {
    1937                 :       6281 :           print_generic_expr (file, ssa_name (i));
    1938                 :       6281 :           fprintf (file, ": ");
    1939                 :       6281 :           dump_value_range (file, vr_value[i]);
    1940                 :       6281 :           fprintf (file, "\n");
    1941                 :            :         }
    1942                 :            :     }
    1943                 :            : 
    1944                 :        961 :   fprintf (file, "\n");
    1945                 :        961 : }
    1946                 :            : 
    1947                 :            : /* Initialize VRP lattice.  */
    1948                 :            : 
    1949                 :    4887480 : vr_values::vr_values () : vrp_value_range_pool ("Tree VRP value ranges")
    1950                 :            : {
    1951                 :    4887480 :   values_propagated = false;
    1952                 :    4887480 :   num_vr_values = num_ssa_names * 2;
    1953                 :    4887480 :   vr_value = XCNEWVEC (value_range_equiv *, num_vr_values);
    1954                 :    9774950 :   vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names);
    1955                 :    4887480 :   bitmap_obstack_initialize (&vrp_equiv_obstack);
    1956                 :    4887480 :   to_remove_edges = vNULL;
    1957                 :    4887480 :   to_update_switch_stmts = vNULL;
    1958                 :    4887480 : }
    1959                 :            : 
    1960                 :            : /* Free VRP lattice.  */
    1961                 :            : 
    1962                 :    4887480 : vr_values::~vr_values ()
    1963                 :            : {
    1964                 :            :   /* Free allocated memory.  */
    1965                 :    4887480 :   free (vr_value);
    1966                 :    4887480 :   free (vr_phi_edge_counts);
    1967                 :    4887480 :   bitmap_obstack_release (&vrp_equiv_obstack);
    1968                 :    4887480 :   vrp_value_range_pool.release ();
    1969                 :            : 
    1970                 :            :   /* So that we can distinguish between VRP data being available
    1971                 :            :      and not available.  */
    1972                 :    4887480 :   vr_value = NULL;
    1973                 :    4887480 :   vr_phi_edge_counts = NULL;
    1974                 :            : 
    1975                 :            :   /* If there are entries left in TO_REMOVE_EDGES or TO_UPDATE_SWITCH_STMTS
    1976                 :            :      then an EVRP client did not clean up properly.  Catch it now rather
    1977                 :            :      than seeing something more obscure later.  */
    1978                 :    4887480 :   gcc_assert (to_remove_edges.is_empty ()
    1979                 :            :               && to_update_switch_stmts.is_empty ());
    1980                 :    4887480 : }
    1981                 :            : 
    1982                 :            : 
    1983                 :            : /* A hack.  */
    1984                 :            : static class vr_values *x_vr_values;
    1985                 :            : 
    1986                 :            : /* Return the singleton value-range for NAME or NAME.  */
    1987                 :            : 
    1988                 :            : static inline tree
    1989                 :   90708700 : vrp_valueize (tree name)
    1990                 :            : {
    1991                 :   90708700 :   if (TREE_CODE (name) == SSA_NAME)
    1992                 :            :     {
    1993                 :   79708000 :       const value_range_equiv *vr = x_vr_values->get_value_range (name);
    1994                 :   79708000 :       if (vr->kind () == VR_RANGE
    1995                 :   29062800 :           && (TREE_CODE (vr->min ()) == SSA_NAME
    1996                 :   27731500 :               || is_gimple_min_invariant (vr->min ()))
    1997                 :  108522000 :           && vrp_operand_equal_p (vr->min (), vr->max ()))
    1998                 :    4019190 :         return vr->min ();
    1999                 :            :     }
    2000                 :            :   return name;
    2001                 :            : }
    2002                 :            : 
    2003                 :            : /* Return the singleton value-range for NAME if that is a constant
    2004                 :            :    but signal to not follow SSA edges.  */
    2005                 :            : 
    2006                 :            : static inline tree
    2007                 :  414037000 : vrp_valueize_1 (tree name)
    2008                 :            : {
    2009                 :  414037000 :   if (TREE_CODE (name) == SSA_NAME)
    2010                 :            :     {
    2011                 :            :       /* If the definition may be simulated again we cannot follow
    2012                 :            :          this SSA edge as the SSA propagator does not necessarily
    2013                 :            :          re-visit the use.  */
    2014                 :  414037000 :       gimple *def_stmt = SSA_NAME_DEF_STMT (name);
    2015                 :  414037000 :       if (!gimple_nop_p (def_stmt)
    2016                 :  414037000 :           && prop_simulate_again_p (def_stmt))
    2017                 :  172571000 :         return NULL_TREE;
    2018                 :  241493000 :       const value_range_equiv *vr = x_vr_values->get_value_range (name);
    2019                 :  241493000 :       tree singleton;
    2020                 :  241493000 :       if (vr->singleton_p (&singleton))
    2021                 :      26256 :         return singleton;
    2022                 :            :     }
    2023                 :            :   return name;
    2024                 :            : }
    2025                 :            : 
    2026                 :            : /* Given STMT, an assignment or call, return its LHS if the type
    2027                 :            :    of the LHS is suitable for VRP analysis, else return NULL_TREE.  */
    2028                 :            : 
    2029                 :            : tree
    2030                 :   75570900 : get_output_for_vrp (gimple *stmt)
    2031                 :            : {
    2032                 :   75570900 :   if (!is_gimple_assign (stmt) && !is_gimple_call (stmt))
    2033                 :            :     return NULL_TREE;
    2034                 :            : 
    2035                 :            :   /* We only keep track of ranges in integral and pointer types.  */
    2036                 :   75553900 :   tree lhs = gimple_get_lhs (stmt);
    2037                 :   75553900 :   if (TREE_CODE (lhs) == SSA_NAME
    2038                 :  151108000 :       && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
    2039                 :            :            /* It is valid to have NULL MIN/MAX values on a type.  See
    2040                 :            :               build_range_type.  */
    2041                 :   58242200 :            && TYPE_MIN_VALUE (TREE_TYPE (lhs))
    2042                 :   58242200 :            && TYPE_MAX_VALUE (TREE_TYPE (lhs)))
    2043                 :   17311800 :           || POINTER_TYPE_P (TREE_TYPE (lhs))))
    2044                 :   75187900 :     return lhs;
    2045                 :            : 
    2046                 :            :   return NULL_TREE;
    2047                 :            : }
    2048                 :            : 
    2049                 :            : /* Visit assignment STMT.  If it produces an interesting range, record
    2050                 :            :    the range in VR and set LHS to OUTPUT_P.  */
    2051                 :            : 
    2052                 :            : void
    2053                 :   69381000 : vr_values::vrp_visit_assignment_or_call (gimple *stmt, tree *output_p,
    2054                 :            :                                          value_range_equiv *vr)
    2055                 :            : {
    2056                 :   69381000 :   tree lhs = get_output_for_vrp (stmt);
    2057                 :   69381000 :   *output_p = lhs;
    2058                 :            : 
    2059                 :            :   /* We only keep track of ranges in integral and pointer types.  */
    2060                 :   69381000 :   if (lhs)
    2061                 :            :     {
    2062                 :   69064500 :       enum gimple_code code = gimple_code (stmt);
    2063                 :            : 
    2064                 :            :       /* Try folding the statement to a constant first.  */
    2065                 :   69064500 :       x_vr_values = this;
    2066                 :   69064500 :       tree tem = gimple_fold_stmt_to_constant_1 (stmt, vrp_valueize,
    2067                 :            :                                                  vrp_valueize_1);
    2068                 :   69064500 :       x_vr_values = NULL;
    2069                 :   69064500 :       if (tem)
    2070                 :            :         {
    2071                 :   13858300 :           if (TREE_CODE (tem) == SSA_NAME
    2072                 :   13858300 :               && (SSA_NAME_IS_DEFAULT_DEF (tem)
    2073                 :    1691030 :                   || ! prop_simulate_again_p (SSA_NAME_DEF_STMT (tem))))
    2074                 :            :             {
    2075                 :     461646 :               extract_range_from_ssa_name (vr, tem);
    2076                 :     461646 :               return;
    2077                 :            :             }
    2078                 :   13396600 :           else if (is_gimple_min_invariant (tem))
    2079                 :            :             {
    2080                 :    2514370 :               vr->set (tem);
    2081                 :    2514370 :               return;
    2082                 :            :             }
    2083                 :            :         }
    2084                 :            :       /* Then dispatch to value-range extracting functions.  */
    2085                 :   66088500 :       if (code == GIMPLE_CALL)
    2086                 :    7136080 :         extract_range_basic (vr, stmt);
    2087                 :            :       else
    2088                 :   58952400 :         extract_range_from_assignment (vr, as_a <gassign *> (stmt));
    2089                 :            :     }
    2090                 :            : }
    2091                 :            : 
    2092                 :            : /* Helper that gets the value range of the SSA_NAME with version I
    2093                 :            :    or a symbolic range containing the SSA_NAME only if the value range
    2094                 :            :    is varying or undefined.  Uses TEM as storage for the alternate range.  */
    2095                 :            : 
    2096                 :            : const value_range_equiv *
    2097                 :  319940000 : vr_values::get_vr_for_comparison (int i, value_range_equiv *tem)
    2098                 :            : {
    2099                 :            :   /* Shallow-copy equiv bitmap.  */
    2100                 :  319940000 :   const value_range_equiv *vr = get_value_range (ssa_name (i));
    2101                 :            : 
    2102                 :            :   /* If name N_i does not have a valid range, use N_i as its own
    2103                 :            :      range.  This allows us to compare against names that may
    2104                 :            :      have N_i in their ranges.  */
    2105                 :  319940000 :   if (vr->varying_p () || vr->undefined_p ())
    2106                 :            :     {
    2107                 :   31435800 :       tem->set (ssa_name (i));
    2108                 :   31435800 :       return tem;
    2109                 :            :     }
    2110                 :            : 
    2111                 :            :   return vr;
    2112                 :            : }
    2113                 :            : 
    2114                 :            : /* Compare all the value ranges for names equivalent to VAR with VAL
    2115                 :            :    using comparison code COMP.  Return the same value returned by
    2116                 :            :    compare_range_with_value, including the setting of
    2117                 :            :    *STRICT_OVERFLOW_P.  */
    2118                 :            : 
    2119                 :            : tree
    2120                 :   27387000 : vr_values::compare_name_with_value (enum tree_code comp, tree var, tree val,
    2121                 :            :                                     bool *strict_overflow_p, bool use_equiv_p)
    2122                 :            : {
    2123                 :            :   /* Get the set of equivalences for VAR.  */
    2124                 :   27387000 :   bitmap e = get_value_range (var)->equiv ();
    2125                 :            : 
    2126                 :            :   /* Start at -1.  Set it to 0 if we do a comparison without relying
    2127                 :            :      on overflow, or 1 if all comparisons rely on overflow.  */
    2128                 :   27387000 :   int used_strict_overflow = -1;
    2129                 :            : 
    2130                 :            :   /* Compare vars' value range with val.  */
    2131                 :   27387000 :   value_range_equiv tem_vr;
    2132                 :   27387000 :   const value_range_equiv *equiv_vr
    2133                 :   27387000 :     = get_vr_for_comparison (SSA_NAME_VERSION (var), &tem_vr);
    2134                 :   27387000 :   bool sop = false;
    2135                 :   27387000 :   tree retval = compare_range_with_value (comp, equiv_vr, val, &sop);
    2136                 :   27387000 :   if (retval)
    2137                 :          0 :     used_strict_overflow = sop ? 1 : 0;
    2138                 :            : 
    2139                 :            :   /* If the equiv set is empty we have done all work we need to do.  */
    2140                 :   27387000 :   if (e == NULL)
    2141                 :            :     {
    2142                 :   25357400 :       if (retval && used_strict_overflow > 0)
    2143                 :          0 :         *strict_overflow_p = true;
    2144                 :   25357400 :       return retval;
    2145                 :            :     }
    2146                 :            : 
    2147                 :    2029540 :   unsigned i;
    2148                 :    2029540 :   bitmap_iterator bi;
    2149                 :    9571310 :   EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
    2150                 :            :     {
    2151                 :    7541760 :       tree name = ssa_name (i);
    2152                 :    7541760 :       if (!name)
    2153                 :          0 :         continue;
    2154                 :            : 
    2155                 :    8171070 :       if (!use_equiv_p
    2156                 :    6641130 :           && !SSA_NAME_IS_DEFAULT_DEF (name)
    2157                 :   14056100 :           && prop_simulate_again_p (SSA_NAME_DEF_STMT (name)))
    2158                 :     629305 :         continue;
    2159                 :            : 
    2160                 :    6912460 :       equiv_vr = get_vr_for_comparison (i, &tem_vr);
    2161                 :    6912460 :       sop = false;
    2162                 :    6912460 :       tree t = compare_range_with_value (comp, equiv_vr, val, &sop);
    2163                 :    6912460 :       if (t)
    2164                 :            :         {
    2165                 :            :           /* If we get different answers from different members
    2166                 :            :              of the equivalence set this check must be in a dead
    2167                 :            :              code region.  Folding it to a trap representation
    2168                 :            :              would be correct here.  For now just return don't-know.  */
    2169                 :       1802 :           if (retval != NULL
    2170                 :       1802 :               && t != retval)
    2171                 :            :             {
    2172                 :            :               retval = NULL_TREE;
    2173                 :            :               break;
    2174                 :            :             }
    2175                 :       1802 :           retval = t;
    2176                 :            : 
    2177                 :       1802 :           if (!sop)
    2178                 :            :             used_strict_overflow = 0;
    2179                 :          0 :           else if (used_strict_overflow < 0)
    2180                 :          0 :             used_strict_overflow = 1;
    2181                 :            :         }
    2182                 :            :     }
    2183                 :            : 
    2184                 :    2029540 :   if (retval && used_strict_overflow > 0)
    2185                 :          0 :     *strict_overflow_p = true;
    2186                 :            : 
    2187                 :            :   return retval;
    2188                 :            : }
    2189                 :            : 
    2190                 :            : 
    2191                 :            : /* Given a comparison code COMP and names N1 and N2, compare all the
    2192                 :            :    ranges equivalent to N1 against all the ranges equivalent to N2
    2193                 :            :    to determine the value of N1 COMP N2.  Return the same value
    2194                 :            :    returned by compare_ranges.  Set *STRICT_OVERFLOW_P to indicate
    2195                 :            :    whether we relied on undefined signed overflow in the comparison.  */
    2196                 :            : 
    2197                 :            : 
    2198                 :            : tree
    2199                 :    3639440 : vr_values::compare_names (enum tree_code comp, tree n1, tree n2,
    2200                 :            :                           bool *strict_overflow_p)
    2201                 :            : {
    2202                 :            :   /* Compare the ranges of every name equivalent to N1 against the
    2203                 :            :      ranges of every name equivalent to N2.  */
    2204                 :    3639440 :   bitmap e1 = get_value_range (n1)->equiv ();
    2205                 :    3639440 :   bitmap e2 = get_value_range (n2)->equiv ();
    2206                 :            : 
    2207                 :            :   /* Use the fake bitmaps if e1 or e2 are not available.  */
    2208                 :    3639440 :   static bitmap s_e1 = NULL, s_e2 = NULL;
    2209                 :    3639440 :   static bitmap_obstack *s_obstack = NULL;
    2210                 :    3639440 :   if (s_obstack == NULL)
    2211                 :            :     {
    2212                 :      31615 :       s_obstack = XNEW (bitmap_obstack);
    2213                 :      31615 :       bitmap_obstack_initialize (s_obstack);
    2214                 :      31615 :       s_e1 = BITMAP_ALLOC (s_obstack);
    2215                 :      31615 :       s_e2 = BITMAP_ALLOC (s_obstack);
    2216                 :            :     }
    2217                 :    3639440 :   if (e1 == NULL)
    2218                 :    2903890 :     e1 = s_e1;
    2219                 :    3639440 :   if (e2 == NULL)
    2220                 :    3111400 :     e2 = s_e2;
    2221                 :            : 
    2222                 :            :   /* Add N1 and N2 to their own set of equivalences to avoid
    2223                 :            :      duplicating the body of the loop just to check N1 and N2
    2224                 :            :      ranges.  */
    2225                 :    3639440 :   bitmap_set_bit (e1, SSA_NAME_VERSION (n1));
    2226                 :    3639440 :   bitmap_set_bit (e2, SSA_NAME_VERSION (n2));
    2227                 :            : 
    2228                 :            :   /* If the equivalence sets have a common intersection, then the two
    2229                 :            :      names can be compared without checking their ranges.  */
    2230                 :    3639440 :   if (bitmap_intersect_p (e1, e2))
    2231                 :            :     {
    2232                 :        680 :       bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
    2233                 :        680 :       bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
    2234                 :            : 
    2235                 :        550 :       return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR)
    2236                 :       1230 :              ? boolean_true_node
    2237                 :        680 :              : boolean_false_node;
    2238                 :            :     }
    2239                 :            : 
    2240                 :            :   /* Start at -1.  Set it to 0 if we do a comparison without relying
    2241                 :            :      on overflow, or 1 if all comparisons rely on overflow.  */
    2242                 :    3638760 :   int used_strict_overflow = -1;
    2243                 :            : 
    2244                 :            :   /* Otherwise, compare all the equivalent ranges.  First, add N1 and
    2245                 :            :      N2 to their own set of equivalences to avoid duplicating the body
    2246                 :            :      of the loop just to check N1 and N2 ranges.  */
    2247                 :    3638760 :   bitmap_iterator bi1;
    2248                 :    3638760 :   unsigned i1;
    2249                 :   11972100 :   EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
    2250                 :            :     {
    2251                 :    8333710 :       if (!ssa_name (i1))
    2252                 :          0 :         continue;
    2253                 :            : 
    2254                 :    8333710 :       value_range_equiv tem_vr1;
    2255                 :    8333710 :       const value_range_equiv *vr1 = get_vr_for_comparison (i1, &tem_vr1);
    2256                 :            : 
    2257                 :    8333710 :       tree t = NULL_TREE, retval = NULL_TREE;
    2258                 :    8333710 :       bitmap_iterator bi2;
    2259                 :    8333710 :       unsigned i2;
    2260                 :  285641000 :       EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
    2261                 :            :         {
    2262                 :  277307000 :           if (!ssa_name (i2))
    2263                 :          0 :             continue;
    2264                 :            : 
    2265                 :  277307000 :           bool sop = false;
    2266                 :            : 
    2267                 :  277307000 :           value_range_equiv tem_vr2;
    2268                 :  277307000 :           const value_range_equiv *vr2 = get_vr_for_comparison (i2, &tem_vr2);
    2269                 :            : 
    2270                 :  277307000 :           t = compare_ranges (comp, vr1, vr2, &sop);
    2271                 :  277307000 :           if (t)
    2272                 :            :             {
    2273                 :            :               /* If we get different answers from different members
    2274                 :            :                  of the equivalence set this check must be in a dead
    2275                 :            :                  code region.  Folding it to a trap representation
    2276                 :            :                  would be correct here.  For now just return don't-know.  */
    2277                 :        383 :               if (retval != NULL && t != retval)
    2278                 :            :                 {
    2279                 :          0 :                   bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
    2280                 :          0 :                   bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
    2281                 :          0 :                   return NULL_TREE;
    2282                 :            :                 }
    2283                 :        383 :               retval = t;
    2284                 :            : 
    2285                 :        383 :               if (!sop)
    2286                 :            :                 used_strict_overflow = 0;
    2287                 :          0 :               else if (used_strict_overflow < 0)
    2288                 :          0 :                 used_strict_overflow = 1;
    2289                 :            :             }
    2290                 :            :         }
    2291                 :            : 
    2292                 :    8333710 :       if (retval)
    2293                 :            :         {
    2294                 :        375 :           bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
    2295                 :        375 :           bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
    2296                 :        375 :           if (used_strict_overflow > 0)
    2297                 :          0 :             *strict_overflow_p = true;
    2298                 :        375 :           return retval;
    2299                 :            :         }
    2300                 :            :     }
    2301                 :            : 
    2302                 :            :   /* None of the equivalent ranges are useful in computing this
    2303                 :            :      comparison.  */
    2304                 :    3638390 :   bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
    2305                 :    3638390 :   bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
    2306                 :    3638390 :   return NULL_TREE;
    2307                 :            : }
    2308                 :            : 
    2309                 :            : /* Helper function for vrp_evaluate_conditional_warnv & other
    2310                 :            :    optimizers.  */
    2311                 :            : 
    2312                 :            : tree
    2313                 :   32214800 : vr_values::vrp_evaluate_conditional_warnv_with_ops_using_ranges
    2314                 :            :     (enum tree_code code, tree op0, tree op1, bool * strict_overflow_p)
    2315                 :            : {
    2316                 :   32214800 :   const value_range_equiv *vr0, *vr1;
    2317                 :   32214800 :   vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
    2318                 :   32214800 :   vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
    2319                 :            : 
    2320                 :   32214800 :   tree res = NULL_TREE;
    2321                 :   32214800 :   if (vr0 && vr1)
    2322                 :    7435970 :     res = compare_ranges (code, vr0, vr1, strict_overflow_p);
    2323                 :   32214800 :   if (!res && vr0)
    2324                 :   31644300 :     res = compare_range_with_value (code, vr0, op1, strict_overflow_p);
    2325                 :   32214800 :   if (!res && vr1)
    2326                 :    7760330 :     res = (compare_range_with_value
    2327                 :    7760330 :             (swap_tree_comparison (code), vr1, op0, strict_overflow_p));
    2328                 :   32214800 :   return res;
    2329                 :            : }
    2330                 :            : 
    2331                 :            : /* Helper function for vrp_evaluate_conditional_warnv. */
    2332                 :            : 
    2333                 :            : tree
    2334                 :   34553500 : vr_values::vrp_evaluate_conditional_warnv_with_ops (enum tree_code code,
    2335                 :            :                                                     tree op0, tree op1,
    2336                 :            :                                                     bool use_equiv_p,
    2337                 :            :                                                     bool *strict_overflow_p,
    2338                 :            :                                                     bool *only_ranges)
    2339                 :            : {
    2340                 :   34553500 :   tree ret;
    2341                 :   34553500 :   if (only_ranges)
    2342                 :   17434100 :     *only_ranges = true;
    2343                 :            : 
    2344                 :            :   /* We only deal with integral and pointer types.  */
    2345                 :   68544500 :   if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
    2346                 :   43210400 :       && !POINTER_TYPE_P (TREE_TYPE (op0)))
    2347                 :            :     return NULL_TREE;
    2348                 :            : 
    2349                 :            :   /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed
    2350                 :            :      as a simple equality test, then prefer that over its current form
    2351                 :            :      for evaluation.
    2352                 :            : 
    2353                 :            :      An overflow test which collapses to an equality test can always be
    2354                 :            :      expressed as a comparison of one argument against zero.  Overflow
    2355                 :            :      occurs when the chosen argument is zero and does not occur if the
    2356                 :            :      chosen argument is not zero.  */
    2357                 :   31991500 :   tree x;
    2358                 :   31991500 :   if (overflow_comparison_p (code, op0, op1, use_equiv_p, &x))
    2359                 :            :     {
    2360                 :       1795 :       wide_int max = wi::max_value (TYPE_PRECISION (TREE_TYPE (op0)), UNSIGNED);
    2361                 :            :       /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0)
    2362                 :            :          B = A - 1; if (A > B) -> B = A - 1; if (A != 0)
    2363                 :            :          B = A + 1; if (B < A) -> B = A + 1; if (B == 0)
    2364                 :            :          B = A + 1; if (B > A) -> B = A + 1; if (B != 0) */
    2365                 :       1795 :       if (integer_zerop (x))
    2366                 :            :         {
    2367                 :        506 :           op1 = x;
    2368                 :        506 :           code = (code == LT_EXPR || code == LE_EXPR) ? EQ_EXPR : NE_EXPR;
    2369                 :            :         }
    2370                 :            :       /* B = A + 1; if (A > B) -> B = A + 1; if (B == 0)
    2371                 :            :          B = A + 1; if (A < B) -> B = A + 1; if (B != 0)
    2372                 :            :          B = A - 1; if (B > A) -> B = A - 1; if (A == 0)
    2373                 :            :          B = A - 1; if (B < A) -> B = A - 1; if (A != 0) */
    2374                 :       1289 :       else if (wi::to_wide (x) == max - 1)
    2375                 :            :         {
    2376                 :        942 :           op0 = op1;
    2377                 :        942 :           op1 = wide_int_to_tree (TREE_TYPE (op0), 0);
    2378                 :        942 :           code = (code == GT_EXPR || code == GE_EXPR) ? EQ_EXPR : NE_EXPR;
    2379                 :            :         }
    2380                 :            :       else
    2381                 :            :         {
    2382                 :        347 :           value_range vro, vri;
    2383                 :        347 :           if (code == GT_EXPR || code == GE_EXPR)
    2384                 :            :             {
    2385                 :        185 :               vro.set (TYPE_MIN_VALUE (TREE_TYPE (op0)), x, VR_ANTI_RANGE);
    2386                 :        185 :               vri.set (TYPE_MIN_VALUE (TREE_TYPE (op0)), x);
    2387                 :            :             }
    2388                 :        162 :           else if (code == LT_EXPR || code == LE_EXPR)
    2389                 :            :             {
    2390                 :        162 :               vro.set (TYPE_MIN_VALUE (TREE_TYPE (op0)), x);
    2391                 :        162 :               vri.set (TYPE_MIN_VALUE (TREE_TYPE (op0)), x, VR_ANTI_RANGE);
    2392                 :            :             }
    2393                 :            :           else
    2394                 :          0 :             gcc_unreachable ();
    2395                 :        347 :           const value_range_equiv *vr0 = get_value_range (op0);
    2396                 :            :           /* If vro, the range for OP0 to pass the overflow test, has
    2397                 :            :              no intersection with *vr0, OP0's known range, then the
    2398                 :            :              overflow test can't pass, so return the node for false.
    2399                 :            :              If it is the inverted range, vri, that has no
    2400                 :            :              intersection, then the overflow test must pass, so return
    2401                 :            :              the node for true.  In other cases, we could proceed with
    2402                 :            :              a simplified condition comparing OP0 and X, with LE_EXPR
    2403                 :            :              for previously LE_ or LT_EXPR and GT_EXPR otherwise, but
    2404                 :            :              the comments next to the enclosing if suggest it's not
    2405                 :            :              generally profitable to do so.  */
    2406                 :        347 :           vro.intersect (vr0);
    2407                 :        347 :           if (vro.undefined_p ())
    2408                 :         25 :             return boolean_false_node;
    2409                 :        332 :           vri.intersect (vr0);
    2410                 :        332 :           if (vri.undefined_p ())
    2411                 :         10 :             return boolean_true_node;
    2412                 :            :         }
    2413                 :            :     }
    2414                 :            : 
    2415                 :   63982900 :   if ((ret = vrp_evaluate_conditional_warnv_with_ops_using_ranges
    2416                 :   31991400 :                (code, op0, op1, strict_overflow_p)))
    2417                 :            :     return ret;
    2418                 :   31139700 :   if (only_ranges)
    2419                 :   16387000 :     *only_ranges = false;
    2420                 :            :   /* Do not use compare_names during propagation, it's quadratic.  */
    2421                 :   31139700 :   if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME
    2422                 :    7295100 :       && use_equiv_p)
    2423                 :    3639440 :     return compare_names (code, op0, op1, strict_overflow_p);
    2424                 :   27500300 :   else if (TREE_CODE (op0) == SSA_NAME)
    2425                 :   27000800 :     return compare_name_with_value (code, op0, op1,
    2426                 :   27000800 :                                     strict_overflow_p, use_equiv_p);
    2427                 :     499443 :   else if (TREE_CODE (op1) == SSA_NAME)
    2428                 :     386171 :     return compare_name_with_value (swap_tree_comparison (code), op1, op0,
    2429                 :     386171 :                                     strict_overflow_p, use_equiv_p);
    2430                 :            :   return NULL_TREE;
    2431                 :            : }
    2432                 :            : 
    2433                 :            : /* Given (CODE OP0 OP1) within STMT, try to simplify it based on value range
    2434                 :            :    information.  Return NULL if the conditional cannot be evaluated.
    2435                 :            :    The ranges of all the names equivalent with the operands in COND
    2436                 :            :    will be used when trying to compute the value.  If the result is
    2437                 :            :    based on undefined signed overflow, issue a warning if
    2438                 :            :    appropriate.  */
    2439                 :            : 
    2440                 :            : tree
    2441                 :   17443700 : vr_values::vrp_evaluate_conditional (tree_code code, tree op0,
    2442                 :            :                                      tree op1, gimple *stmt)
    2443                 :            : {
    2444                 :   17443700 :   bool sop;
    2445                 :   17443700 :   tree ret;
    2446                 :   17443700 :   bool only_ranges;
    2447                 :            : 
    2448                 :            :   /* Some passes and foldings leak constants with overflow flag set
    2449                 :            :      into the IL.  Avoid doing wrong things with these and bail out.  */
    2450                 :   17443700 :   if ((TREE_CODE (op0) == INTEGER_CST
    2451                 :      15061 :        && TREE_OVERFLOW (op0))
    2452                 :   17458700 :       || (TREE_CODE (op1) == INTEGER_CST
    2453                 :   12304600 :           && TREE_OVERFLOW (op1)))
    2454                 :            :     return NULL_TREE;
    2455                 :            : 
    2456                 :   17434100 :   sop = false;
    2457                 :   17434100 :   ret = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, true, &sop,
    2458                 :            :                                                  &only_ranges);
    2459                 :            : 
    2460                 :   17434100 :   if (ret && sop)
    2461                 :            :     {
    2462                 :          4 :       enum warn_strict_overflow_code wc;
    2463                 :          4 :       const char* warnmsg;
    2464                 :            : 
    2465                 :          4 :       if (is_gimple_min_invariant (ret))
    2466                 :            :         {
    2467                 :            :           wc = WARN_STRICT_OVERFLOW_CONDITIONAL;
    2468                 :            :           warnmsg = G_("assuming signed overflow does not occur when "
    2469                 :            :                        "simplifying conditional to constant");
    2470                 :            :         }
    2471                 :            :       else
    2472                 :            :         {
    2473                 :          0 :           wc = WARN_STRICT_OVERFLOW_COMPARISON;
    2474                 :          0 :           warnmsg = G_("assuming signed overflow does not occur when "
    2475                 :            :                        "simplifying conditional");
    2476                 :            :         }
    2477                 :            : 
    2478                 :          4 :       if (issue_strict_overflow_warning (wc))
    2479                 :            :         {
    2480                 :          0 :           location_t location;
    2481                 :            : 
    2482                 :          0 :           if (!gimple_has_location (stmt))
    2483                 :          0 :             location = input_location;
    2484                 :            :           else
    2485                 :          0 :             location = gimple_location (stmt);
    2486                 :          0 :           warning_at (location, OPT_Wstrict_overflow, "%s", warnmsg);
    2487                 :            :         }
    2488                 :            :     }
    2489                 :            : 
    2490                 :   17434100 :   if (warn_type_limits
    2491                 :    2782880 :       && ret && only_ranges
    2492                 :      19007 :       && TREE_CODE_CLASS (code) == tcc_comparison
    2493                 :      19007 :       && TREE_CODE (op0) == SSA_NAME)
    2494                 :            :     {
    2495                 :            :       /* If the comparison is being folded and the operand on the LHS
    2496                 :            :          is being compared against a constant value that is outside of
    2497                 :            :          the natural range of OP0's type, then the predicate will
    2498                 :            :          always fold regardless of the value of OP0.  If -Wtype-limits
    2499                 :            :          was specified, emit a warning.  */
    2500                 :      18991 :       tree type = TREE_TYPE (op0);
    2501                 :      18991 :       const value_range_equiv *vr0 = get_value_range (op0);
    2502                 :            : 
    2503                 :      18991 :       if (vr0->kind () == VR_RANGE
    2504                 :      15777 :           && INTEGRAL_TYPE_P (type)
    2505                 :      11362 :           && vrp_val_is_min (vr0->min ())
    2506                 :       2344 :           && vrp_val_is_max (vr0->max ())
    2507                 :      18991 :           && is_gimple_min_invariant (op1))
    2508                 :            :         {
    2509                 :          0 :           location_t location;
    2510                 :            : 
    2511                 :          0 :           if (!gimple_has_location (stmt))
    2512                 :          0 :             location = input_location;
    2513                 :            :           else
    2514                 :          0 :             location = gimple_location (stmt);
    2515                 :            : 
    2516                 :          0 :           warning_at (location, OPT_Wtype_limits,
    2517                 :          0 :                       integer_zerop (ret)
    2518                 :            :                       ? G_("comparison always false "
    2519                 :            :                            "due to limited range of data type")
    2520                 :            :                       : G_("comparison always true "
    2521                 :            :                            "due to limited range of data type"));
    2522                 :            :         }
    2523                 :            :     }
    2524                 :            : 
    2525                 :            :   return ret;
    2526                 :            : }
    2527                 :            : 
    2528                 :            : 
    2529                 :            : /* Visit conditional statement STMT.  If we can determine which edge
    2530                 :            :    will be taken out of STMT's basic block, record it in
    2531                 :            :    *TAKEN_EDGE_P.  Otherwise, set *TAKEN_EDGE_P to NULL.  */
    2532                 :            : 
    2533                 :            : void
    2534                 :   13471700 : vr_values::vrp_visit_cond_stmt (gcond *stmt, edge *taken_edge_p)
    2535                 :            : {
    2536                 :   13471700 :   tree val;
    2537                 :            : 
    2538                 :   13471700 :   *taken_edge_p = NULL;
    2539                 :            : 
    2540                 :   13471700 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2541                 :            :     {
    2542                 :        455 :       tree use;
    2543                 :        455 :       ssa_op_iter i;
    2544                 :            : 
    2545                 :        455 :       fprintf (dump_file, "\nVisiting conditional with predicate: ");
    2546                 :        455 :       print_gimple_stmt (dump_file, stmt, 0);
    2547                 :        455 :       fprintf (dump_file, "\nWith known ranges\n");
    2548                 :            : 
    2549                 :       1029 :       FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
    2550                 :            :         {
    2551                 :        574 :           fprintf (dump_file, "\t");
    2552                 :        574 :           print_generic_expr (dump_file, use);
    2553                 :        574 :           fprintf (dump_file, ": ");
    2554                 :        574 :           dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]);
    2555                 :            :         }
    2556                 :            : 
    2557                 :        455 :       fprintf (dump_file, "\n");
    2558                 :            :     }
    2559                 :            : 
    2560                 :            :   /* Compute the value of the predicate COND by checking the known
    2561                 :            :      ranges of each of its operands.
    2562                 :            : 
    2563                 :            :      Note that we cannot evaluate all the equivalent ranges here
    2564                 :            :      because those ranges may not yet be final and with the current
    2565                 :            :      propagation strategy, we cannot determine when the value ranges
    2566                 :            :      of the names in the equivalence set have changed.
    2567                 :            : 
    2568                 :            :      For instance, given the following code fragment
    2569                 :            : 
    2570                 :            :         i_5 = PHI <8, i_13>
    2571                 :            :         ...
    2572                 :            :         i_14 = ASSERT_EXPR <i_5, i_5 != 0>
    2573                 :            :         if (i_14 == 1)
    2574                 :            :           ...
    2575                 :            : 
    2576                 :            :      Assume that on the first visit to i_14, i_5 has the temporary
    2577                 :            :      range [8, 8] because the second argument to the PHI function is
    2578                 :            :      not yet executable.  We derive the range ~[0, 0] for i_14 and the
    2579                 :            :      equivalence set { i_5 }.  So, when we visit 'if (i_14 == 1)' for
    2580                 :            :      the first time, since i_14 is equivalent to the range [8, 8], we
    2581                 :            :      determine that the predicate is always false.
    2582                 :            : 
    2583                 :            :      On the next round of propagation, i_13 is determined to be
    2584                 :            :      VARYING, which causes i_5 to drop down to VARYING.  So, another
    2585                 :            :      visit to i_14 is scheduled.  In this second visit, we compute the
    2586                 :            :      exact same range and equivalence set for i_14, namely ~[0, 0] and
    2587                 :            :      { i_5 }.  But we did not have the previous range for i_5
    2588                 :            :      registered, so vrp_visit_assignment thinks that the range for
    2589                 :            :      i_14 has not changed.  Therefore, the predicate 'if (i_14 == 1)'
    2590                 :            :      is not visited again, which stops propagation from visiting
    2591                 :            :      statements in the THEN clause of that if().
    2592                 :            : 
    2593                 :            :      To properly fix this we would need to keep the previous range
    2594                 :            :      value for the names in the equivalence set.  This way we would've
    2595                 :            :      discovered that from one visit to the other i_5 changed from
    2596                 :            :      range [8, 8] to VR_VARYING.
    2597                 :            : 
    2598                 :            :      However, fixing this apparent limitation may not be worth the
    2599                 :            :      additional checking.  Testing on several code bases (GCC, DLV,
    2600                 :            :      MICO, TRAMP3D and SPEC2000) showed that doing this results in
    2601                 :            :      4 more predicates folded in SPEC.  */
    2602                 :            : 
    2603                 :   13471700 :   bool sop;
    2604                 :   13471700 :   val = vrp_evaluate_conditional_warnv_with_ops (gimple_cond_code (stmt),
    2605                 :            :                                                  gimple_cond_lhs (stmt),
    2606                 :            :                                                  gimple_cond_rhs (stmt),
    2607                 :            :                                                  false, &sop, NULL);
    2608                 :   13471700 :   if (val)
    2609                 :     673505 :     *taken_edge_p = find_taken_edge (gimple_bb (stmt), val);
    2610                 :            : 
    2611                 :   13471700 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2612                 :            :     {
    2613                 :        455 :       fprintf (dump_file, "\nPredicate evaluates to: ");
    2614                 :        455 :       if (val == NULL_TREE)
    2615                 :        425 :         fprintf (dump_file, "DON'T KNOW\n");
    2616                 :            :       else
    2617                 :         30 :         print_generic_stmt (dump_file, val);
    2618                 :            :     }
    2619                 :   13471700 : }
    2620                 :            : 
    2621                 :            : /* Searches the case label vector VEC for the ranges of CASE_LABELs that are
    2622                 :            :    used in range VR.  The indices are placed in MIN_IDX1, MAX_IDX, MIN_IDX2 and
    2623                 :            :    MAX_IDX2.  If the ranges of CASE_LABELs are empty then MAX_IDX1 < MIN_IDX1.
    2624                 :            :    Returns true if the default label is not needed.  */
    2625                 :            : 
    2626                 :            : static bool
    2627                 :      29865 : find_case_label_ranges (gswitch *stmt, const value_range_equiv *vr,
    2628                 :            :                         size_t *min_idx1, size_t *max_idx1,
    2629                 :            :                         size_t *min_idx2, size_t *max_idx2)
    2630                 :            : {
    2631                 :      29865 :   size_t i, j, k, l;
    2632                 :      29865 :   unsigned int n = gimple_switch_num_labels (stmt);
    2633                 :      29865 :   bool take_default;
    2634                 :      29865 :   tree case_low, case_high;
    2635                 :      29865 :   tree min = vr->min (), max = vr->max ();
    2636                 :            : 
    2637                 :      29865 :   gcc_checking_assert (!vr->varying_p () && !vr->undefined_p ());
    2638                 :            : 
    2639                 :      29865 :   take_default = !find_case_label_range (stmt, min, max, &i, &j);
    2640                 :            : 
    2641                 :            :   /* Set second range to empty.  */
    2642                 :      29865 :   *min_idx2 = 1;
    2643                 :      29865 :   *max_idx2 = 0;
    2644                 :            : 
    2645                 :      29865 :   if (vr->kind () == VR_RANGE)
    2646                 :            :     {
    2647                 :      27546 :       *min_idx1 = i;
    2648                 :      27546 :       *max_idx1 = j;
    2649                 :      27546 :       return !take_default;
    2650                 :            :     }
    2651                 :            : 
    2652                 :            :   /* Set first range to all case labels.  */
    2653                 :       2319 :   *min_idx1 = 1;
    2654                 :       2319 :   *max_idx1 = n - 1;
    2655                 :            : 
    2656                 :       2319 :   if (i > j)
    2657                 :            :     return false;
    2658                 :            : 
    2659                 :            :   /* Make sure all the values of case labels [i , j] are contained in
    2660                 :            :      range [MIN, MAX].  */
    2661                 :        270 :   case_low = CASE_LOW (gimple_switch_label (stmt, i));
    2662                 :        270 :   case_high = CASE_HIGH (gimple_switch_label (stmt, j));
    2663                 :        270 :   if (tree_int_cst_compare (case_low, min) < 0)
    2664                 :          9 :     i += 1;
    2665                 :        270 :   if (case_high != NULL_TREE
    2666                 :        270 :       && tree_int_cst_compare (max, case_high) < 0)
    2667                 :         20 :     j -= 1;
    2668                 :            : 
    2669                 :        270 :   if (i > j)
    2670                 :            :     return false;
    2671                 :            : 
    2672                 :            :   /* If the range spans case labels [i, j], the corresponding anti-range spans
    2673                 :            :      the labels [1, i - 1] and [j + 1, n -  1].  */
    2674                 :        248 :   k = j + 1;
    2675                 :        248 :   l = n - 1;
    2676                 :        248 :   if (k > l)
    2677                 :            :     {
    2678                 :         29 :       k = 1;
    2679                 :         29 :       l = 0;
    2680                 :            :     }
    2681                 :            : 
    2682                 :        248 :   j = i - 1;
    2683                 :        248 :   i = 1;
    2684                 :        248 :   if (i > j)
    2685                 :            :     {
    2686                 :        120 :       i = k;
    2687                 :        120 :       j = l;
    2688                 :        120 :       k = 1;
    2689                 :        120 :       l = 0;
    2690                 :            :     }
    2691                 :            : 
    2692                 :        248 :   *min_idx1 = i;
    2693                 :        248 :   *max_idx1 = j;
    2694                 :        248 :   *min_idx2 = k;
    2695                 :        248 :   *max_idx2 = l;
    2696                 :        248 :   return false;
    2697                 :            : }
    2698                 :            : 
    2699                 :            : /* Visit switch statement STMT.  If we can determine which edge
    2700                 :            :    will be taken out of STMT's basic block, record it in
    2701                 :            :    *TAKEN_EDGE_P.  Otherwise, *TAKEN_EDGE_P set to NULL.  */
    2702                 :            : 
    2703                 :            : void
    2704                 :      76613 : vr_values::vrp_visit_switch_stmt (gswitch *stmt, edge *taken_edge_p)
    2705                 :            : {
    2706                 :      76613 :   tree op, val;
    2707                 :      76613 :   const value_range_equiv *vr;
    2708                 :      76613 :   size_t i = 0, j = 0, k, l;
    2709                 :      76613 :   bool take_default;
    2710                 :            : 
    2711                 :      76613 :   *taken_edge_p = NULL;
    2712                 :      76613 :   op = gimple_switch_index (stmt);
    2713                 :      76613 :   if (TREE_CODE (op) != SSA_NAME)
    2714                 :      75517 :     return;
    2715                 :            : 
    2716                 :      76607 :   vr = get_value_range (op);
    2717                 :      76607 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2718                 :            :     {
    2719                 :          1 :       fprintf (dump_file, "\nVisiting switch expression with operand ");
    2720                 :          1 :       print_generic_expr (dump_file, op);
    2721                 :          1 :       fprintf (dump_file, " with known range ");
    2722                 :          1 :       dump_value_range (dump_file, vr);
    2723                 :          1 :       fprintf (dump_file, "\n");
    2724                 :            :     }
    2725                 :            : 
    2726                 :      76607 :   if (vr->undefined_p ()
    2727                 :      76533 :       || vr->varying_p ()
    2728                 :      98586 :       || vr->symbolic_p ())
    2729                 :      56754 :     return;
    2730                 :            : 
    2731                 :            :   /* Find the single edge that is taken from the switch expression.  */
    2732                 :      19853 :   take_default = !find_case_label_ranges (stmt, vr, &i, &j, &k, &l);
    2733                 :            : 
    2734                 :            :   /* Check if the range spans no CASE_LABEL. If so, we only reach the default
    2735                 :            :      label */
    2736                 :      19853 :   if (j < i)
    2737                 :            :     {
    2738                 :        685 :       gcc_assert (take_default);
    2739                 :        685 :       val = gimple_switch_default_label (stmt);
    2740                 :            :     }
    2741                 :            :   else
    2742                 :            :     {
    2743                 :            :       /* Check if labels with index i to j and maybe the default label
    2744                 :            :          are all reaching the same label.  */
    2745                 :            : 
    2746                 :      19168 :       val = gimple_switch_label (stmt, i);
    2747                 :      19168 :       if (take_default
    2748                 :      19168 :           && CASE_LABEL (gimple_switch_default_label (stmt))
    2749                 :      18195 :           != CASE_LABEL (val))
    2750                 :            :         {
    2751                 :      18195 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2752                 :          0 :             fprintf (dump_file, "  not a single destination for this "
    2753                 :            :                      "range\n");
    2754                 :      18195 :           return;
    2755                 :            :         }
    2756                 :        973 :       for (++i; i <= j; ++i)
    2757                 :            :         {
    2758                 :        562 :           if (CASE_LABEL (gimple_switch_label (stmt, i)) != CASE_LABEL (val))
    2759                 :            :             {
    2760                 :        562 :               if (dump_file && (dump_flags & TDF_DETAILS))
    2761                 :          0 :                 fprintf (dump_file, "  not a single destination for this "
    2762                 :            :                          "range\n");
    2763                 :        562 :               return;
    2764                 :            :             }
    2765                 :            :         }
    2766                 :        411 :       for (; k <= l; ++k)
    2767                 :            :         {
    2768                 :          0 :           if (CASE_LABEL (gimple_switch_label (stmt, k)) != CASE_LABEL (val))
    2769                 :            :             {
    2770                 :          0 :               if (dump_file && (dump_flags & TDF_DETAILS))
    2771                 :          0 :                 fprintf (dump_file, "  not a single destination for this "
    2772                 :            :                          "range\n");
    2773                 :          0 :               return;
    2774                 :            :             }
    2775                 :            :         }
    2776                 :            :     }
    2777                 :            : 
    2778                 :       2192 :   *taken_edge_p = find_edge (gimple_bb (stmt),
    2779                 :       1096 :                              label_to_block (cfun, CASE_LABEL (val)));
    2780                 :            : 
    2781                 :       1096 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2782                 :            :     {
    2783                 :          0 :       fprintf (dump_file, "  will take edge to ");
    2784                 :          0 :       print_generic_stmt (dump_file, CASE_LABEL (val));
    2785                 :            :     }
    2786                 :            : }
    2787                 :            : 
    2788                 :            : 
    2789                 :            : /* Evaluate statement STMT.  If the statement produces a useful range,
    2790                 :            :    set VR and corepsponding OUTPUT_P.
    2791                 :            : 
    2792                 :            :    If STMT is a conditional branch and we can determine its truth
    2793                 :            :    value, the taken edge is recorded in *TAKEN_EDGE_P.  */
    2794                 :            : 
    2795                 :            : void
    2796                 :   77818400 : vr_values::extract_range_from_stmt (gimple *stmt, edge *taken_edge_p,
    2797                 :            :                                     tree *output_p, value_range_equiv *vr)
    2798                 :            : {
    2799                 :            : 
    2800                 :   77818400 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2801                 :            :     {
    2802                 :       3161 :       fprintf (dump_file, "\nVisiting statement:\n");
    2803                 :       3161 :       print_gimple_stmt (dump_file, stmt, 0, dump_flags);
    2804                 :            :     }
    2805                 :            : 
    2806                 :   77818400 :   if (!stmt_interesting_for_vrp (stmt))
    2807                 :    2673490 :     gcc_assert (stmt_ends_bb_p (stmt));
    2808                 :   75144900 :   else if (is_gimple_assign (stmt) || is_gimple_call (stmt))
    2809                 :   69381000 :     vrp_visit_assignment_or_call (stmt, output_p, vr);
    2810                 :    5763840 :   else if (gimple_code (stmt) == GIMPLE_COND)
    2811                 :    5687230 :     vrp_visit_cond_stmt (as_a <gcond *> (stmt), taken_edge_p);
    2812                 :      76613 :   else if (gimple_code (stmt) == GIMPLE_SWITCH)
    2813                 :      76613 :     vrp_visit_switch_stmt (as_a <gswitch *> (stmt), taken_edge_p);
    2814                 :   77818400 : }
    2815                 :            : 
    2816                 :            : /* Visit all arguments for PHI node PHI that flow through executable
    2817                 :            :    edges.  If a valid value range can be derived from all the incoming
    2818                 :            :    value ranges, set a new range in VR_RESULT.  */
    2819                 :            : 
    2820                 :            : void
    2821                 :    8287820 : vr_values::extract_range_from_phi_node (gphi *phi,
    2822                 :            :                                         value_range_equiv *vr_result)
    2823                 :            : {
    2824                 :    8287820 :   tree lhs = PHI_RESULT (phi);
    2825                 :    8287820 :   const value_range_equiv *lhs_vr = get_value_range (lhs);
    2826                 :    8287820 :   bool first = true;
    2827                 :    8287820 :   int old_edges;
    2828                 :    8287820 :   class loop *l;
    2829                 :            : 
    2830                 :    8287820 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2831                 :            :     {
    2832                 :        351 :       fprintf (dump_file, "\nVisiting PHI node: ");
    2833                 :        351 :       print_gimple_stmt (dump_file, phi, 0, dump_flags);
    2834                 :            :     }
    2835                 :            : 
    2836                 :            :   bool may_simulate_backedge_again = false;
    2837                 :            :   int edges = 0;
    2838                 :   21661800 :   for (size_t i = 0; i < gimple_phi_num_args (phi); i++)
    2839                 :            :     {
    2840                 :   16809700 :       edge e = gimple_phi_arg_edge (phi, i);
    2841                 :            : 
    2842                 :   16809700 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2843                 :            :         {
    2844                 :       1386 :           fprintf (dump_file,
    2845                 :            :               "    Argument #%d (%d -> %d %sexecutable)\n",
    2846                 :        693 :               (int) i, e->src->index, e->dest->index,
    2847                 :        693 :               (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
    2848                 :            :         }
    2849                 :            : 
    2850                 :   16809700 :       if (e->flags & EDGE_EXECUTABLE)
    2851                 :            :         {
    2852                 :   15492000 :           value_range_equiv vr_arg_tem;
    2853                 :   15492000 :           const value_range_equiv *vr_arg = &vr_arg_tem;
    2854                 :            : 
    2855                 :   15492000 :           ++edges;
    2856                 :            : 
    2857                 :   15492000 :           tree arg = PHI_ARG_DEF (phi, i);
    2858                 :   15492000 :           if (TREE_CODE (arg) == SSA_NAME)
    2859                 :            :             {
    2860                 :            :               /* See if we are eventually going to change one of the args.  */
    2861                 :   10965300 :               gimple *def_stmt = SSA_NAME_DEF_STMT (arg);
    2862                 :   10965300 :               if (! gimple_nop_p (def_stmt)
    2863                 :   10760100 :                   && prop_simulate_again_p (def_stmt)
    2864                 :   16912400 :                   && e->flags & EDGE_DFS_BACK)
    2865                 :            :                 may_simulate_backedge_again = true;
    2866                 :            : 
    2867                 :   10965300 :               const value_range_equiv *vr_arg_ = get_value_range (arg);
    2868                 :            :               /* Do not allow equivalences or symbolic ranges to leak in from
    2869                 :            :                  backedges.  That creates invalid equivalencies.
    2870                 :            :                  See PR53465 and PR54767.  */
    2871                 :   10965300 :               if (e->flags & EDGE_DFS_BACK)
    2872                 :            :                 {
    2873                 :    1844430 :                   if (!vr_arg_->varying_p () && !vr_arg_->undefined_p ())
    2874                 :            :                     {
    2875                 :    1612730 :                       vr_arg_tem.set (vr_arg_->min (), vr_arg_->max (), NULL,
    2876                 :            :                                       vr_arg_->kind ());
    2877                 :    1612730 :                       if (vr_arg_tem.symbolic_p ())
    2878                 :     202825 :                         vr_arg_tem.set_varying (TREE_TYPE (arg));
    2879                 :            :                     }
    2880                 :            :                   else
    2881                 :            :                     vr_arg = vr_arg_;
    2882                 :            :                 }
    2883                 :            :               /* If the non-backedge arguments range is VR_VARYING then
    2884                 :            :                  we can still try recording a simple equivalence.  */
    2885                 :    9120900 :               else if (vr_arg_->varying_p ())
    2886                 :    4928810 :                 vr_arg_tem.set (arg);
    2887                 :            :               else
    2888                 :            :                 vr_arg = vr_arg_;
    2889                 :            :             }
    2890                 :            :           else
    2891                 :            :             {
    2892                 :    4526630 :               if (TREE_OVERFLOW_P (arg))
    2893                 :         25 :                 arg = drop_tree_overflow (arg);
    2894                 :            : 
    2895                 :    4526630 :               vr_arg_tem.set (arg);
    2896                 :            :             }
    2897                 :            : 
    2898                 :   15492000 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2899                 :            :             {
    2900                 :        637 :               fprintf (dump_file, "\t");
    2901                 :        637 :               print_generic_expr (dump_file, arg, dump_flags);
    2902                 :        637 :               fprintf (dump_file, ": ");
    2903                 :        637 :               dump_value_range (dump_file, vr_arg);
    2904                 :        637 :               fprintf (dump_file, "\n");
    2905                 :            :             }
    2906                 :            : 
    2907                 :   15492000 :           if (first)
    2908                 :    8258200 :             vr_result->deep_copy (vr_arg);
    2909                 :            :           else
    2910                 :    7233770 :             vr_result->union_ (vr_arg);
    2911                 :   15492000 :           first = false;
    2912                 :            : 
    2913                 :   15492000 :           if (vr_result->varying_p ())
    2914                 :            :             break;
    2915                 :            :         }
    2916                 :            :     }
    2917                 :            : 
    2918                 :    8287820 :   if (vr_result->varying_p ())
    2919                 :    3435790 :     goto varying;
    2920                 :    4852040 :   else if (vr_result->undefined_p ())
    2921                 :      47836 :     goto update_range;
    2922                 :            : 
    2923                 :    4804200 :   old_edges = vr_phi_edge_counts[SSA_NAME_VERSION (lhs)];
    2924                 :    4804200 :   vr_phi_edge_counts[SSA_NAME_VERSION (lhs)] = edges;
    2925                 :            : 
    2926                 :            :   /* To prevent infinite iterations in the algorithm, derive ranges
    2927                 :            :      when the new value is slightly bigger or smaller than the
    2928                 :            :      previous one.  We don't do this if we have seen a new executable
    2929                 :            :      edge; this helps us avoid an infinity for conditionals
    2930                 :            :      which are not in a loop.  If the old value-range was VR_UNDEFINED
    2931                 :            :      use the updated range and iterate one more time.  If we will not
    2932                 :            :      simulate this PHI again via the backedge allow us to iterate.  */
    2933                 :    4804200 :   if (edges > 0
    2934                 :    4804200 :       && gimple_phi_num_args (phi) > 1
    2935                 :    3676120 :       && edges == old_edges
    2936                 :     893027 :       && !lhs_vr->undefined_p ()
    2937                 :    5697230 :       && may_simulate_backedge_again)
    2938                 :            :     {
    2939                 :            :       /* Compare old and new ranges, fall back to varying if the
    2940                 :            :          values are not comparable.  */
    2941                 :     699122 :       int cmp_min = compare_values (lhs_vr->min (), vr_result->min ());
    2942                 :     699122 :       if (cmp_min == -2)
    2943                 :       9762 :         goto varying;
    2944                 :     689360 :       int cmp_max = compare_values (lhs_vr->max (), vr_result->max ());
    2945                 :     689360 :       if (cmp_max == -2)
    2946                 :        210 :         goto varying;
    2947                 :            : 
    2948                 :            :       /* For non VR_RANGE or for pointers fall back to varying if
    2949                 :            :          the range changed.  */
    2950                 :     689150 :       if ((lhs_vr->kind () != VR_RANGE || vr_result->kind () != VR_RANGE
    2951                 :     662139 :            || POINTER_TYPE_P (TREE_TYPE (lhs)))
    2952                 :     712915 :           && (cmp_min != 0 || cmp_max != 0))
    2953                 :      26810 :         goto varying;
    2954                 :            : 
    2955                 :            :       /* If the new minimum is larger than the previous one
    2956                 :            :          retain the old value.  If the new minimum value is smaller
    2957                 :            :          than the previous one and not -INF go all the way to -INF + 1.
    2958                 :            :          In the first case, to avoid infinite bouncing between different
    2959                 :            :          minimums, and in the other case to avoid iterating millions of
    2960                 :            :          times to reach -INF.  Going to -INF + 1 also lets the following
    2961                 :            :          iteration compute whether there will be any overflow, at the
    2962                 :            :          expense of one additional iteration.  */
    2963                 :     662340 :       tree new_min = vr_result->min ();
    2964                 :     662340 :       tree new_max = vr_result->max ();
    2965                 :     662340 :       if (cmp_min < 0)
    2966                 :       1700 :         new_min = lhs_vr->min ();
    2967                 :     660640 :       else if (cmp_min > 0
    2968                 :     660640 :                && (TREE_CODE (vr_result->min ()) != INTEGER_CST
    2969                 :      23391 :                    || tree_int_cst_lt (vrp_val_min (vr_result->type ()),
    2970                 :      23391 :                                        vr_result->min ())))
    2971                 :      21058 :         new_min = int_const_binop (PLUS_EXPR,
    2972                 :      21058 :                                    vrp_val_min (vr_result->type ()),
    2973                 :      42116 :                                    build_int_cst (vr_result->type (), 1));
    2974                 :            : 
    2975                 :            :       /* Similarly for the maximum value.  */
    2976                 :     662340 :       if (cmp_max > 0)
    2977                 :       5940 :         new_max = lhs_vr->max ();
    2978                 :     656400 :       else if (cmp_max < 0
    2979                 :     656400 :                && (TREE_CODE (vr_result->max ()) != INTEGER_CST
    2980                 :     438983 :                    || tree_int_cst_lt (vr_result->max (),
    2981                 :     438983 :                                        vrp_val_max (vr_result->type ()))))
    2982                 :     380903 :         new_max = int_const_binop (MINUS_EXPR,
    2983                 :     380903 :                                    vrp_val_max (vr_result->type ()),
    2984                 :     761806 :                                    build_int_cst (vr_result->type (), 1));
    2985                 :            : 
    2986                 :     662340 :       vr_result->update (new_min, new_max, vr_result->kind ());
    2987                 :            : 
    2988                 :            :       /* If we dropped either bound to +-INF then if this is a loop
    2989                 :            :          PHI node SCEV may known more about its value-range.  */
    2990                 :     662340 :       if (cmp_min > 0 || cmp_min < 0
    2991                 :     662340 :            || cmp_max < 0 || cmp_max > 0)
    2992                 :     466054 :         goto scev_check;
    2993                 :            : 
    2994                 :     196286 :       goto infinite_check;
    2995                 :            :     }
    2996                 :            : 
    2997                 :    4105080 :   goto update_range;
    2998                 :            : 
    2999                 :    3472570 : varying:
    3000                 :    3472570 :   vr_result->set_varying (TREE_TYPE (lhs));
    3001                 :            : 
    3002                 :    3938620 : scev_check:
    3003                 :            :   /* If this is a loop PHI node SCEV may known more about its value-range.
    3004                 :            :      scev_check can be reached from two paths, one is a fall through from above
    3005                 :            :      "varying" label, the other is direct goto from code block which tries to
    3006                 :            :      avoid infinite simulation.  */
    3007                 :    3938620 :   if (scev_initialized_p ()
    3008                 :    2954820 :       && (l = loop_containing_stmt (phi))
    3009                 :    6893450 :       && l->header == gimple_bb (phi))
    3010                 :    1022790 :     adjust_range_with_scev (vr_result, l, phi, lhs);
    3011                 :            : 
    3012                 :    4134910 : infinite_check:
    3013                 :            :   /* If we will end up with a (-INF, +INF) range, set it to
    3014                 :            :      VARYING.  Same if the previous max value was invalid for
    3015                 :            :      the type and we end up with vr_result.min > vr_result.max.  */
    3016                 :    4134910 :   if ((!vr_result->varying_p () && !vr_result->undefined_p ())
    3017                 :    5757020 :       && !((vrp_val_is_max (vr_result->max ()) && vrp_val_is_min (vr_result->min ()))
    3018                 :     811052 :            || compare_values (vr_result->min (), vr_result->max ()) > 0))
    3019                 :            :     ;
    3020                 :            :   else
    3021                 :    3323860 :     vr_result->set_varying (TREE_TYPE (lhs));
    3022                 :            : 
    3023                 :            :   /* If the new range is different than the previous value, keep
    3024                 :            :      iterating.  */
    3025                 :    8287820 : update_range:
    3026                 :    8287820 :   return;
    3027                 :            : }
    3028                 :            : 
    3029                 :            : /* Simplify boolean operations if the source is known
    3030                 :            :    to be already a boolean.  */
    3031                 :            : bool
    3032                 :     320388 : vr_values::simplify_truth_ops_using_ranges (gimple_stmt_iterator *gsi,
    3033                 :            :                                             gimple *stmt)
    3034                 :            : {
    3035                 :     320388 :   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
    3036                 :     320388 :   tree lhs, op0, op1;
    3037                 :     320388 :   bool need_conversion;
    3038                 :            : 
    3039                 :            :   /* We handle only !=/== case here.  */
    3040                 :     320388 :   gcc_assert (rhs_code == EQ_EXPR || rhs_code == NE_EXPR);
    3041                 :            : 
    3042                 :     320388 :   op0 = gimple_assign_rhs1 (stmt);
    3043                 :     320388 :   if (!op_with_boolean_value_range_p (op0))
    3044                 :            :     return false;
    3045                 :            : 
    3046                 :       9314 :   op1 = gimple_assign_rhs2 (stmt);
    3047                 :       9314 :   if (!op_with_boolean_value_range_p (op1))
    3048                 :            :     return false;
    3049                 :            : 
    3050                 :            :   /* Reduce number of cases to handle to NE_EXPR.  As there is no
    3051                 :            :      BIT_XNOR_EXPR we cannot replace A == B with a single statement.  */
    3052                 :       9234 :   if (rhs_code == EQ_EXPR)
    3053                 :            :     {
    3054                 :       4457 :       if (TREE_CODE (op1) == INTEGER_CST)
    3055                 :       1466 :         op1 = int_const_binop (BIT_XOR_EXPR, op1,
    3056                 :       2932 :                                build_int_cst (TREE_TYPE (op1), 1));
    3057                 :            :       else
    3058                 :            :         return false;
    3059                 :            :     }
    3060                 :            : 
    3061                 :       6243 :   lhs = gimple_assign_lhs (stmt);
    3062                 :       6243 :   need_conversion
    3063                 :       6243 :     = !useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (op0));
    3064                 :            : 
    3065                 :            :   /* Make sure to not sign-extend a 1-bit 1 when converting the result.  */
    3066                 :       6243 :   if (need_conversion
    3067                 :       5247 :       && !TYPE_UNSIGNED (TREE_TYPE (op0))
    3068                 :       2866 :       && TYPE_PRECISION (TREE_TYPE (op0)) == 1
    3069                 :       6256 :       && TYPE_PRECISION (TREE_TYPE (lhs)) > 1)
    3070                 :            :     return false;
    3071                 :            : 
    3072                 :            :   /* For A != 0 we can substitute A itself.  */
    3073                 :       6243 :   if (integer_zerop (op1))
    3074                 :       3742 :     gimple_assign_set_rhs_with_ops (gsi,
    3075                 :            :                                     need_conversion
    3076                 :          0 :                                     ? NOP_EXPR : TREE_CODE (op0), op0);
    3077                 :            :   /* For A != B we substitute A ^ B.  Either with conversion.  */
    3078                 :       2501 :   else if (need_conversion)
    3079                 :            :     {
    3080                 :       1505 :       tree tem = make_ssa_name (TREE_TYPE (op0));
    3081                 :       1505 :       gassign *newop
    3082                 :       1505 :         = gimple_build_assign (tem, BIT_XOR_EXPR, op0, op1);
    3083                 :       1505 :       gsi_insert_before (gsi, newop, GSI_SAME_STMT);
    3084                 :       2892 :       if (INTEGRAL_TYPE_P (TREE_TYPE (tem))
    3085                 :       2892 :           && TYPE_PRECISION (TREE_TYPE (tem)) > 1)
    3086                 :       4269 :         set_range_info (tem, VR_RANGE,
    3087                 :       1423 :                         wi::zero (TYPE_PRECISION (TREE_TYPE (tem))),
    3088                 :       3533 :                         wi::one (TYPE_PRECISION (TREE_TYPE (tem))));
    3089                 :       1505 :       gimple_assign_set_rhs_with_ops (gsi, NOP_EXPR, tem);
    3090                 :            :     }
    3091                 :            :   /* Or without.  */
    3092                 :            :   else
    3093                 :        996 :     gimple_assign_set_rhs_with_ops (gsi, BIT_XOR_EXPR, op0, op1);
    3094                 :       6243 :   update_stmt (gsi_stmt (*gsi));
    3095                 :       6243 :   fold_stmt (gsi, follow_single_use_edges);
    3096                 :            : 
    3097                 :       6243 :   return true;
    3098                 :            : }
    3099                 :            : 
    3100                 :            : /* Simplify a division or modulo operator to a right shift or bitwise and
    3101                 :            :    if the first operand is unsigned or is greater than zero and the second
    3102                 :            :    operand is an exact power of two.  For TRUNC_MOD_EXPR op0 % op1 with
    3103                 :            :    constant op1 (op1min = op1) or with op1 in [op1min, op1max] range,
    3104                 :            :    optimize it into just op0 if op0's range is known to be a subset of
    3105                 :            :    [-op1min + 1, op1min - 1] for signed and [0, op1min - 1] for unsigned
    3106                 :            :    modulo.  */
    3107                 :            : 
    3108                 :            : bool
    3109                 :     215818 : vr_values::simplify_div_or_mod_using_ranges (gimple_stmt_iterator *gsi,
    3110                 :            :                                              gimple *stmt)
    3111                 :            : {
    3112                 :     215818 :   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
    3113                 :     215818 :   tree val = NULL;
    3114                 :     215818 :   tree op0 = gimple_assign_rhs1 (stmt);
    3115                 :     215818 :   tree op1 = gimple_assign_rhs2 (stmt);
    3116                 :     215818 :   tree op0min = NULL_TREE, op0max = NULL_TREE;
    3117                 :     215818 :   tree op1min = op1;
    3118                 :     215818 :   const value_range_equiv *vr = NULL;
    3119                 :            : 
    3120                 :     215818 :   if (TREE_CODE (op0) == INTEGER_CST)
    3121                 :            :     {
    3122                 :            :       op0min = op0;
    3123                 :            :       op0max = op0;
    3124                 :            :     }
    3125                 :            :   else
    3126                 :            :     {
    3127                 :     196190 :       vr = get_value_range (op0);
    3128                 :     196190 :       if (range_int_cst_p (vr))
    3129                 :            :         {
    3130                 :      65961 :           op0min = vr->min ();
    3131                 :      65961 :           op0max = vr->max ();
    3132                 :            :         }
    3133                 :            :     }
    3134                 :            : 
    3135                 :     215818 :   if (rhs_code == TRUNC_MOD_EXPR
    3136                 :      97277 :       && TREE_CODE (op1) == SSA_NAME)
    3137                 :            :     {
    3138                 :      61513 :       const value_range_equiv *vr1 = get_value_range (op1);
    3139                 :      61513 :       if (range_int_cst_p (vr1))
    3140                 :       9783 :         op1min = vr1->min ();
    3141                 :            :     }
    3142                 :     215818 :   if (rhs_code == TRUNC_MOD_EXPR
    3143                 :      97277 :       && TREE_CODE (op1min) == INTEGER_CST
    3144                 :      45547 :       && tree_int_cst_sgn (op1min) == 1
    3145                 :      39751 :       && op0max
    3146                 :     236469 :       && tree_int_cst_lt (op0max, op1min))
    3147                 :            :     {
    3148                 :       1001 :       if (TYPE_UNSIGNED (TREE_TYPE (op0))
    3149                 :        321 :           || tree_int_cst_sgn (op0min) >= 0
    3150                 :       1076 :           || tree_int_cst_lt (fold_unary (NEGATE_EXPR, TREE_TYPE (op1min), op1min),
    3151                 :            :                               op0min))
    3152                 :            :         {
    3153                 :            :           /* If op0 already has the range op0 % op1 has,
    3154                 :            :              then TRUNC_MOD_EXPR won't change anything.  */
    3155                 :        992 :           gimple_assign_set_rhs_from_tree (gsi, op0);
    3156                 :        992 :           return true;
    3157                 :            :         }
    3158                 :            :     }
    3159                 :            : 
    3160                 :     214826 :   if (TREE_CODE (op0) != SSA_NAME)
    3161                 :            :     return false;
    3162                 :            : 
    3163                 :     195203 :   if (!integer_pow2p (op1))
    3164                 :            :     {
    3165                 :            :       /* X % -Y can be only optimized into X % Y either if
    3166                 :            :          X is not INT_MIN, or Y is not -1.  Fold it now, as after
    3167                 :            :          remove_range_assertions the range info might be not available
    3168                 :            :          anymore.  */
    3169                 :     162110 :       if (rhs_code == TRUNC_MOD_EXPR
    3170                 :     162110 :           && fold_stmt (gsi, follow_single_use_edges))
    3171                 :            :         return true;
    3172                 :     162110 :       return false;
    3173                 :            :     }
    3174                 :            : 
    3175                 :      33093 :   if (TYPE_UNSIGNED (TREE_TYPE (op0)))
    3176                 :       5855 :     val = integer_one_node;
    3177                 :            :   else
    3178                 :            :     {
    3179                 :      27238 :       bool sop = false;
    3180                 :            : 
    3181                 :      27238 :       val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
    3182                 :            : 
    3183                 :      27238 :       if (val
    3184                 :       2460 :           && sop
    3185                 :          0 :           && integer_onep (val)
    3186                 :      27238 :           && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
    3187                 :            :         {
    3188                 :          0 :           location_t location;
    3189                 :            : 
    3190                 :          0 :           if (!gimple_has_location (stmt))
    3191                 :          0 :             location = input_location;
    3192                 :            :           else
    3193                 :          0 :             location = gimple_location (stmt);
    3194                 :          0 :           warning_at (location, OPT_Wstrict_overflow,
    3195                 :            :                       "assuming signed overflow does not occur when "
    3196                 :            :                       "simplifying %</%> or %<%%%> to %<>>%> or %<&%>");
    3197                 :            :         }
    3198                 :            :     }
    3199                 :            : 
    3200                 :      33093 :   if (val && integer_onep (val))
    3201                 :            :     {
    3202                 :       8315 :       tree t;
    3203                 :            : 
    3204                 :       8315 :       if (rhs_code == TRUNC_DIV_EXPR)
    3205                 :            :         {
    3206                 :       7764 :           t = build_int_cst (integer_type_node, tree_log2 (op1));
    3207                 :       7764 :           gimple_assign_set_rhs_code (stmt, RSHIFT_EXPR);
    3208                 :       7764 :           gimple_assign_set_rhs1 (stmt, op0);
    3209                 :       7764 :           gimple_assign_set_rhs2 (stmt, t);
    3210                 :            :         }
    3211                 :            :       else
    3212                 :            :         {
    3213                 :        551 :           t = build_int_cst (TREE_TYPE (op1), 1);
    3214                 :        551 :           t = int_const_binop (MINUS_EXPR, op1, t);
    3215                 :        551 :           t = fold_convert (TREE_TYPE (op0), t);
    3216                 :            : 
    3217                 :        551 :           gimple_assign_set_rhs_code (stmt, BIT_AND_EXPR);
    3218                 :        551 :           gimple_assign_set_rhs1 (stmt, op0);
    3219                 :        551 :           gimple_assign_set_rhs2 (stmt, t);
    3220                 :            :         }
    3221                 :            : 
    3222                 :       8315 :       update_stmt (stmt);
    3223                 :       8315 :       fold_stmt (gsi, follow_single_use_edges);
    3224                 :       8315 :       return true;
    3225                 :            :     }
    3226                 :            : 
    3227                 :            :   return false;
    3228                 :            : }
    3229                 :            : 
    3230                 :            : /* Simplify a min or max if the ranges of the two operands are
    3231                 :            :    disjoint.   Return true if we do simplify.  */
    3232                 :            : 
    3233                 :            : bool
    3234                 :     112276 : vr_values::simplify_min_or_max_using_ranges (gimple_stmt_iterator *gsi,
    3235                 :            :                                              gimple *stmt)
    3236                 :            : {
    3237                 :     112276 :   tree op0 = gimple_assign_rhs1 (stmt);
    3238                 :     112276 :   tree op1 = gimple_assign_rhs2 (stmt);
    3239                 :     112276 :   bool sop = false;
    3240                 :     112276 :   tree val;
    3241                 :            : 
    3242                 :     112276 :   val = (vrp_evaluate_conditional_warnv_with_ops_using_ranges
    3243                 :     112276 :          (LE_EXPR, op0, op1, &sop));
    3244                 :     112276 :   if (!val)
    3245                 :            :     {
    3246                 :     111064 :       sop = false;
    3247                 :     111064 :       val = (vrp_evaluate_conditional_warnv_with_ops_using_ranges
    3248                 :     111064 :              (LT_EXPR, op0, op1, &sop));
    3249                 :            :     }
    3250                 :            : 
    3251                 :     112276 :   if (val)
    3252                 :            :     {
    3253                 :       1857 :       if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
    3254                 :            :         {
    3255                 :          0 :           location_t location;
    3256                 :            : 
    3257                 :          0 :           if (!gimple_has_location (stmt))
    3258                 :          0 :             location = input_location;
    3259                 :            :           else
    3260                 :          0 :             location = gimple_location (stmt);
    3261                 :          0 :           warning_at (location, OPT_Wstrict_overflow,
    3262                 :            :                       "assuming signed overflow does not occur when "
    3263                 :            :                       "simplifying %<min/max (X,Y)%> to %<X%> or %<Y%>");
    3264                 :            :         }
    3265                 :            : 
    3266                 :            :       /* VAL == TRUE -> OP0 < or <= op1
    3267                 :            :          VAL == FALSE -> OP0 > or >= op1.  */
    3268                 :       1857 :       tree res = ((gimple_assign_rhs_code (stmt) == MAX_EXPR)
    3269                 :       1857 :                   == integer_zerop (val)) ? op0 : op1;
    3270                 :       1857 :       gimple_assign_set_rhs_from_tree (gsi, res);
    3271                 :       1857 :       return true;
    3272                 :            :     }
    3273                 :            : 
    3274                 :            :   return false;
    3275                 :            : }
    3276                 :            : 
    3277                 :            : /* If the operand to an ABS_EXPR is >= 0, then eliminate the
    3278                 :            :    ABS_EXPR.  If the operand is <= 0, then simplify the
    3279                 :            :    ABS_EXPR into a NEGATE_EXPR.  */
    3280                 :            : 
    3281                 :            : bool
    3282                 :       3330 : vr_values::simplify_abs_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt)
    3283                 :            : {
    3284                 :       3330 :   tree op = gimple_assign_rhs1 (stmt);
    3285                 :       3330 :   const value_range_equiv *vr = get_value_range (op);
    3286                 :            : 
    3287                 :       3330 :   if (vr)
    3288                 :            :     {
    3289                 :       3330 :       tree val = NULL;
    3290                 :       3330 :       bool sop = false;
    3291                 :            : 
    3292                 :       3330 :       val = compare_range_with_value (LE_EXPR, vr, integer_zero_node, &sop);
    3293                 :       3330 :       if (!val)
    3294                 :            :         {
    3295                 :            :           /* The range is neither <= 0 nor > 0.  Now see if it is
    3296                 :            :              either < 0 or >= 0.  */
    3297                 :       3295 :           sop = false;
    3298                 :       3295 :           val = compare_range_with_value (LT_EXPR, vr, integer_zero_node,
    3299                 :            :                                           &sop);
    3300                 :            :         }
    3301                 :            : 
    3302                 :       3330 :       if (val)
    3303                 :            :         {
    3304                 :        110 :           if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
    3305                 :            :             {
    3306                 :          0 :               location_t location;
    3307                 :            : 
    3308                 :          0 :               if (!gimple_has_location (stmt))
    3309                 :          0 :                 location = input_location;
    3310                 :            :               else
    3311                 :          0 :                 location = gimple_location (stmt);
    3312                 :          0 :               warning_at (location, OPT_Wstrict_overflow,
    3313                 :            :                           "assuming signed overflow does not occur when "
    3314                 :            :                           "simplifying %<abs (X)%> to %<X%> or %<-X%>");
    3315                 :            :             }
    3316                 :            : 
    3317                 :        110 :           gimple_assign_set_rhs1 (stmt, op);
    3318                 :        110 :           if (integer_zerop (val))
    3319                 :         82 :             gimple_assign_set_rhs_code (stmt, SSA_NAME);
    3320                 :            :           else
    3321                 :         28 :             gimple_assign_set_rhs_code (stmt, NEGATE_EXPR);
    3322                 :        110 :           update_stmt (stmt);
    3323                 :        110 :           fold_stmt (gsi, follow_single_use_edges);
    3324                 :        110 :           return true;
    3325                 :            :         }
    3326                 :            :     }
    3327                 :            : 
    3328                 :            :   return false;
    3329                 :            : }
    3330                 :            : 
    3331                 :            : /* value_range wrapper for wi_set_zero_nonzero_bits.
    3332                 :            : 
    3333                 :            :    Return TRUE if VR was a constant range and we were able to compute
    3334                 :            :    the bit masks.  */
    3335                 :            : 
    3336                 :            : static bool
    3337                 :     971904 : vr_set_zero_nonzero_bits (const tree expr_type,
    3338                 :            :                           const value_range *vr,
    3339                 :            :                           wide_int *may_be_nonzero,
    3340                 :            :                           wide_int *must_be_nonzero)
    3341                 :            : {
    3342                 :     971904 :   if (range_int_cst_p (vr))
    3343                 :            :     {
    3344                 :     321318 :       wi_set_zero_nonzero_bits (expr_type,
    3345                 :     321318 :                                 wi::to_wide (vr->min ()),
    3346                 :     321318 :                                 wi::to_wide (vr->max ()),
    3347                 :            :                                 *may_be_nonzero, *must_be_nonzero);
    3348                 :     321318 :       return true;
    3349                 :            :     }
    3350                 :    1210440 :   *may_be_nonzero = wi::minus_one (TYPE_PRECISION (expr_type));
    3351                 :     650586 :   *must_be_nonzero = wi::zero (TYPE_PRECISION (expr_type));
    3352                 :     650586 :   return false;
    3353                 :            : }
    3354                 :            : 
    3355                 :            : /* Optimize away redundant BIT_AND_EXPR and BIT_IOR_EXPR.
    3356                 :            :    If all the bits that are being cleared by & are already
    3357                 :            :    known to be zero from VR, or all the bits that are being
    3358                 :            :    set by | are already known to be one from VR, the bit
    3359                 :            :    operation is redundant.  */
    3360                 :            : 
    3361                 :            : bool
    3362                 :     802280 : vr_values::simplify_bit_ops_using_ranges (gimple_stmt_iterator *gsi,
    3363                 :            :                                           gimple *stmt)
    3364                 :            : {
    3365                 :     802280 :   tree op0 = gimple_assign_rhs1 (stmt);
    3366                 :     802280 :   tree op1 = gimple_assign_rhs2 (stmt);
    3367                 :     802280 :   tree op = NULL_TREE;
    3368                 :     802280 :   value_range vr0, vr1;
    3369                 :     802280 :   wide_int may_be_nonzero0, may_be_nonzero1;
    3370                 :     802280 :   wide_int must_be_nonzero0, must_be_nonzero1;
    3371                 :     802280 :   wide_int mask;
    3372                 :            : 
    3373                 :     802280 :   if (TREE_CODE (op0) == SSA_NAME)
    3374                 :     802280 :     vr0 = *(get_value_range (op0));
    3375                 :          0 :   else if (is_gimple_min_invariant (op0))
    3376                 :          0 :     vr0.set (op0);
    3377                 :            :   else
    3378                 :            :     return false;
    3379                 :            : 
    3380                 :     802280 :   if (TREE_CODE (op1) == SSA_NAME)
    3381                 :     382614 :     vr1 = *(get_value_range (op1));
    3382                 :     419666 :   else if (is_gimple_min_invariant (op1))
    3383                 :     419666 :     vr1.set (op1);
    3384                 :            :   else
    3385                 :            :     return false;
    3386                 :            : 
    3387                 :     802280 :   if (!vr_set_zero_nonzero_bits (TREE_TYPE (op0), &vr0, &may_be_nonzero0,
    3388                 :            :                                  &must_be_nonzero0))
    3389                 :            :     return false;
    3390                 :     169624 :   if (!vr_set_zero_nonzero_bits (TREE_TYPE (op1), &vr1, &may_be_nonzero1,
    3391                 :            :                                  &must_be_nonzero1))
    3392                 :            :     return false;
    3393                 :            : 
    3394                 :     151694 :   switch (gimple_assign_rhs_code (stmt))
    3395                 :            :     {
    3396                 :     109173 :     case BIT_AND_EXPR:
    3397                 :     109173 :       mask = wi::bit_and_not (may_be_nonzero0, must_be_nonzero1);
    3398                 :     109173 :       if (mask == 0)
    3399                 :            :         {
    3400                 :            :           op = op0;
    3401                 :            :           break;
    3402                 :            :         }
    3403                 :     108954 :       mask = wi::bit_and_not (may_be_nonzero1, must_be_nonzero0);
    3404                 :     108954 :       if (mask == 0)
    3405                 :            :         {
    3406                 :            :           op = op1;
    3407                 :            :           break;
    3408                 :            :         }
    3409                 :            :       break;
    3410                 :      42521 :     case BIT_IOR_EXPR:
    3411                 :      42521 :       mask = wi::bit_and_not (may_be_nonzero0, must_be_nonzero1);
    3412                 :      42521 :       if (mask == 0)
    3413                 :            :         {
    3414                 :            :           op = op1;
    3415                 :            :           break;
    3416                 :            :         }
    3417                 :      42521 :       mask = wi::bit_and_not (may_be_nonzero1, must_be_nonzero0);
    3418                 :      42521 :       if (mask == 0)
    3419                 :            :         {
    3420                 :            :           op = op0;
    3421                 :            :           break;
    3422                 :            :         }
    3423                 :            :       break;
    3424                 :          0 :     default:
    3425                 :          0 :       gcc_unreachable ();
    3426                 :            :     }
    3427                 :            : 
    3428                 :        222 :   if (op == NULL_TREE)
    3429                 :     151472 :     return false;
    3430                 :            : 
    3431                 :        222 :   gimple_assign_set_rhs_with_ops (gsi, TREE_CODE (op), op);
    3432                 :        222 :   update_stmt (gsi_stmt (*gsi));
    3433                 :            :   return true;
    3434                 :            : }
    3435                 :            : 
    3436                 :            : /* We are comparing trees OP0 and OP1 using COND_CODE.  OP0 has
    3437                 :            :    a known value range VR.
    3438                 :            : 
    3439                 :            :    If there is one and only one value which will satisfy the
    3440                 :            :    conditional, then return that value.  Else return NULL.
    3441                 :            : 
    3442                 :            :    If signed overflow must be undefined for the value to satisfy
    3443                 :            :    the conditional, then set *STRICT_OVERFLOW_P to true.  */
    3444                 :            : 
    3445                 :            : static tree
    3446                 :     527638 : test_for_singularity (enum tree_code cond_code, tree op0,
    3447                 :            :                       tree op1, const value_range_equiv *vr)
    3448                 :            : {
    3449                 :     527638 :   tree min = NULL;
    3450                 :     527638 :   tree max = NULL;
    3451                 :            : 
    3452                 :            :   /* Extract minimum/maximum values which satisfy the conditional as it was
    3453                 :            :      written.  */
    3454                 :     527638 :   if (cond_code == LE_EXPR || cond_code == LT_EXPR)
    3455                 :            :     {
    3456                 :     235620 :       min = TYPE_MIN_VALUE (TREE_TYPE (op0));
    3457                 :            : 
    3458                 :     235620 :       max = op1;
    3459                 :     235620 :       if (cond_code == LT_EXPR)
    3460                 :            :         {
    3461                 :      27016 :           tree one = build_int_cst (TREE_TYPE (op0), 1);
    3462                 :      27016 :           max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one);
    3463                 :            :           /* Signal to compare_values_warnv this expr doesn't overflow.  */
    3464                 :      27016 :           if (EXPR_P (max))
    3465                 :          0 :             TREE_NO_WARNING (max) = 1;
    3466                 :            :         }
    3467                 :            :     }
    3468                 :     292018 :   else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
    3469                 :            :     {
    3470                 :     292018 :       max = TYPE_MAX_VALUE (TREE_TYPE (op0));
    3471                 :            : 
    3472                 :     292018 :       min = op1;
    3473                 :     292018 :       if (cond_code == GT_EXPR)
    3474                 :            :         {
    3475                 :     266015 :           tree one = build_int_cst (TREE_TYPE (op0), 1);
    3476                 :     266015 :           min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one);
    3477                 :            :           /* Signal to compare_values_warnv this expr doesn't overflow.  */
    3478                 :     266015 :           if (EXPR_P (min))
    3479                 :          0 :             TREE_NO_WARNING (min) = 1;
    3480                 :            :         }
    3481                 :            :     }
    3482                 :            : 
    3483                 :            :   /* Now refine the minimum and maximum values using any
    3484                 :            :      value range information we have for op0.  */
    3485                 :     527638 :   if (min && max)
    3486                 :            :     {
    3487                 :     527638 :       if (compare_values (vr->min (), min) == 1)
    3488                 :     175950 :         min = vr->min ();
    3489                 :     527638 :       if (compare_values (vr->max (), max) == -1)
    3490                 :     228411 :         max = vr->max ();
    3491                 :            : 
    3492                 :            :       /* If the new min/max values have converged to a single value,
    3493                 :            :          then there is only one value which can satisfy the condition,
    3494                 :            :          return that value.  */
    3495                 :     527638 :       if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min))
    3496                 :     167102 :         return min;
    3497                 :            :     }
    3498                 :            :   return NULL;
    3499                 :            : }
    3500                 :            : 
    3501                 :            : /* Return whether the value range *VR fits in an integer type specified
    3502                 :            :    by PRECISION and UNSIGNED_P.  */
    3503                 :            : 
    3504                 :            : static bool
    3505                 :      74678 : range_fits_type_p (const value_range_equiv *vr,
    3506                 :            :                    unsigned dest_precision, signop dest_sgn)
    3507                 :            : {
    3508                 :      74678 :   tree src_type;
    3509                 :      74678 :   unsigned src_precision;
    3510                 :      74678 :   widest_int tem;
    3511                 :      74678 :   signop src_sgn;
    3512                 :            : 
    3513                 :            :   /* We can only handle integral and pointer types.  */
    3514                 :      74678 :   src_type = vr->type ();
    3515                 :      74678 :   if (!INTEGRAL_TYPE_P (src_type)
    3516                 :          0 :       && !POINTER_TYPE_P (src_type))
    3517                 :            :     return false;
    3518                 :            : 
    3519                 :            :   /* An extension is fine unless VR is SIGNED and dest_sgn is UNSIGNED,
    3520                 :            :      and so is an identity transform.  */
    3521                 :      74678 :   src_precision = TYPE_PRECISION (vr->type ());
    3522                 :      74678 :   src_sgn = TYPE_SIGN (src_type);
    3523                 :      74678 :   if ((src_precision < dest_precision
    3524                 :       1297 :        && !(dest_sgn == UNSIGNED && src_sgn == SIGNED))
    3525                 :      73721 :       || (src_precision == dest_precision && src_sgn == dest_sgn))
    3526                 :            :     return true;
    3527                 :            : 
    3528                 :            :   /* Now we can only handle ranges with constant bounds.  */
    3529                 :      73708 :   if (!range_int_cst_p (vr))
    3530                 :            :     return false;
    3531                 :            : 
    3532                 :            :   /* For sign changes, the MSB of the wide_int has to be clear.
    3533                 :            :      An unsigned value with its MSB set cannot be represented by
    3534                 :            :      a signed wide_int, while a negative value cannot be represented
    3535                 :            :      by an unsigned wide_int.  */
    3536                 :      73708 :   if (src_sgn != dest_sgn
    3537                 :      73708 :       && (wi::lts_p (wi::to_wide (vr->min ()), 0)
    3538                 :      29926 :           || wi::lts_p (wi::to_wide (vr->max ()), 0)))
    3539                 :      15165 :     return false;
    3540                 :            : 
    3541                 :            :   /* Then we can perform the conversion on both ends and compare
    3542                 :            :      the result for equality.  */
    3543                 :      58543 :   tem = wi::ext (wi::to_widest (vr->min ()), dest_precision, dest_sgn);
    3544                 :      58543 :   if (tem != wi::to_widest (vr->min ()))
    3545                 :            :     return false;
    3546                 :      57786 :   tem = wi::ext (wi::to_widest (vr->max ()), dest_precision, dest_sgn);
    3547                 :      57786 :   if (tem != wi::to_widest (vr->max ()))
    3548                 :       7699 :     return false;
    3549                 :            : 
    3550                 :            :   return true;
    3551                 :            : }
    3552                 :            : 
    3553                 :            : /* Simplify a conditional using a relational operator to an equality
    3554                 :            :    test if the range information indicates only one value can satisfy
    3555                 :            :    the original conditional.  */
    3556                 :            : 
    3557                 :            : bool
    3558                 :    7519440 : vr_values::simplify_cond_using_ranges_1 (gcond *stmt)
    3559                 :            : {
    3560                 :    7519440 :   tree op0 = gimple_cond_lhs (stmt);
    3561                 :    7519440 :   tree op1 = gimple_cond_rhs (stmt);
    3562                 :    7519440 :   enum tree_code cond_code = gimple_cond_code (stmt);
    3563                 :            : 
    3564                 :    7519440 :   if (cond_code != NE_EXPR
    3565                 :    7519440 :       && cond_code != EQ_EXPR
    3566                 :    1635750 :       && TREE_CODE (op0) == SSA_NAME
    3567                 :    1635380 :       && INTEGRAL_TYPE_P (TREE_TYPE (op0))
    3568                 :    8997550 :       && is_gimple_min_invariant (op1))
    3569                 :            :     {
    3570                 :     740647 :       const value_range_equiv *vr = get_value_range (op0);
    3571                 :            : 
    3572                 :            :       /* If we have range information for OP0, then we might be
    3573                 :            :          able to simplify this conditional. */
    3574                 :     740647 :       if (vr->kind () == VR_RANGE)
    3575                 :            :         {
    3576                 :     307648 :           tree new_tree = test_for_singularity (cond_code, op0, op1, vr);
    3577                 :     307648 :           if (new_tree)
    3578                 :            :             {
    3579                 :      87658 :               if (dump_file)
    3580                 :            :                 {
    3581                 :          4 :                   fprintf (dump_file, "Simplified relational ");
    3582                 :          4 :                   print_gimple_stmt (dump_file, stmt, 0);
    3583                 :          4 :                   fprintf (dump_file, " into ");
    3584                 :            :                 }
    3585                 :            : 
    3586                 :      87658 :               gimple_cond_set_code (stmt, EQ_EXPR);
    3587                 :      87658 :               gimple_cond_set_lhs (stmt, op0);
    3588                 :      87658 :               gimple_cond_set_rhs (stmt, new_tree);
    3589                 :            : 
    3590                 :      87658 :               update_stmt (stmt);
    3591                 :            : 
    3592                 :      87658 :               if (dump_file)
    3593                 :            :                 {
    3594                 :          4 :                   print_gimple_stmt (dump_file, stmt, 0);
    3595                 :          4 :                   fprintf (dump_file, "\n");
    3596                 :            :                 }
    3597                 :            : 
    3598                 :      87658 :               return true;
    3599                 :            :             }
    3600                 :            : 
    3601                 :            :           /* Try again after inverting the condition.  We only deal
    3602                 :            :              with integral types here, so no need to worry about
    3603                 :            :              issues with inverting FP comparisons.  */
    3604                 :     219990 :           new_tree = test_for_singularity
    3605                 :     219990 :                        (invert_tree_comparison (cond_code, false),
    3606                 :            :                         op0, op1, vr);
    3607                 :     219990 :           if (new_tree)
    3608                 :            :             {
    3609                 :      79444 :               if (dump_file)
    3610                 :            :                 {
    3611                 :          6 :                   fprintf (dump_file, "Simplified relational ");
    3612                 :          6 :                   print_gimple_stmt (dump_file, stmt, 0);
    3613                 :          6 :                   fprintf (dump_file, " into ");
    3614                 :            :                 }
    3615                 :            : 
    3616                 :      79444 :               gimple_cond_set_code (stmt, NE_EXPR);
    3617                 :      79444 :               gimple_cond_set_lhs (stmt, op0);
    3618                 :      79444 :               gimple_cond_set_rhs (stmt, new_tree);
    3619                 :            : 
    3620                 :      79444 :               update_stmt (stmt);
    3621                 :            : 
    3622                 :      79444 :               if (dump_file)
    3623                 :            :                 {
    3624                 :          6 :                   print_gimple_stmt (dump_file, stmt, 0);
    3625                 :          6 :                   fprintf (dump_file, "\n");
    3626                 :            :                 }
    3627                 :            : 
    3628                 :      79444 :               return true;
    3629                 :            :             }
    3630                 :            :         }
    3631                 :            :     }
    3632                 :            :   return false;
    3633                 :            : }
    3634                 :            : 
    3635                 :            : /* STMT is a conditional at the end of a basic block.
    3636                 :            : 
    3637                 :            :    If the conditional is of the form SSA_NAME op constant and the SSA_NAME
    3638                 :            :    was set via a type conversion, try to replace the SSA_NAME with the RHS
    3639                 :            :    of the type conversion.  Doing so makes the conversion dead which helps
    3640                 :            :    subsequent passes.  */
    3641                 :            : 
    3642                 :            : void
    3643                 :    5133550 : vr_values::simplify_cond_using_ranges_2 (gcond *stmt)
    3644                 :            : {
    3645                 :    5133550 :   tree op0 = gimple_cond_lhs (stmt);
    3646                 :    5133550 :   tree op1 = gimple_cond_rhs (stmt);
    3647                 :            : 
    3648                 :            :   /* If we have a comparison of an SSA_NAME (OP0) against a constant,
    3649                 :            :      see if OP0 was set by a type conversion where the source of
    3650                 :            :      the conversion is another SSA_NAME with a range that fits
    3651                 :            :      into the range of OP0's type.
    3652                 :            : 
    3653                 :            :      If so, the conversion is redundant as the earlier SSA_NAME can be
    3654                 :            :      used for the comparison directly if we just massage the constant in the
    3655                 :            :      comparison.  */
    3656                 :    5133550 :   if (TREE_CODE (op0) == SSA_NAME
    3657                 :    5008750 :       && TREE_CODE (op1) == INTEGER_CST)
    3658                 :            :     {
    3659                 :    3488330 :       gimple *def_stmt = SSA_NAME_DEF_STMT (op0);
    3660                 :    3488330 :       tree innerop;
    3661                 :            : 
    3662                 :    3488330 :       if (!is_gimple_assign (def_stmt)
    3663                 :    3488330 :           || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
    3664                 :            :         return;
    3665                 :            : 
    3666                 :     167262 :       innerop = gimple_assign_rhs1 (def_stmt);
    3667                 :            : 
    3668                 :     167262 :       if (TREE_CODE (innerop) == SSA_NAME
    3669                 :     167234 :           && !POINTER_TYPE_P (TREE_TYPE (innerop))
    3670                 :     164820 :           && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop)
    3671                 :     332074 :           && desired_pro_or_demotion_p (TREE_TYPE (innerop), TREE_TYPE (op0)))
    3672                 :            :         {
    3673                 :     150848 :           const value_range_equiv *vr = get_value_range (innerop);
    3674                 :            : 
    3675                 :     150848 :           if (range_int_cst_p (vr)
    3676                 :      70243 :               && range_fits_type_p (vr,
    3677                 :      70243 :                                     TYPE_PRECISION (TREE_TYPE (op0)),
    3678                 :      70243 :                                     TYPE_SIGN (TREE_TYPE (op0)))
    3679                 :     200706 :               && int_fits_type_p (op1, TREE_TYPE (innerop)))
    3680                 :            :             {
    3681                 :      49858 :               tree newconst = fold_convert (TREE_TYPE (innerop), op1);
    3682                 :      49858 :               gimple_cond_set_lhs (stmt, innerop);
    3683                 :      49858 :               gimple_cond_set_rhs (stmt, newconst);
    3684                 :      49858 :               update_stmt (stmt);
    3685                 :      49858 :               if (dump_file && (dump_flags & TDF_DETAILS))
    3686                 :            :                 {
    3687                 :          3 :                   fprintf (dump_file, "Folded into: ");
    3688                 :          3 :                   print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    3689                 :          3 :                   fprintf (dump_file, "\n");
    3690                 :            :                 }
    3691                 :            :             }
    3692                 :            :         }
    3693                 :            :     }
    3694                 :            : }
    3695                 :            : 
    3696                 :            : /* Simplify a switch statement using the value range of the switch
    3697                 :            :    argument.  */
    3698                 :            : 
    3699                 :            : bool
    3700                 :      38201 : vr_values::simplify_switch_using_ranges (gswitch *stmt)
    3701                 :            : {
    3702                 :      38201 :   tree op = gimple_switch_index (stmt);
    3703                 :      38201 :   const value_range_equiv *vr = NULL;
    3704                 :      38201 :   bool take_default;
    3705                 :      38201 :   edge e;
    3706                 :      38201 :   edge_iterator ei;
    3707                 :      38201 :   size_t i = 0, j = 0, n, n2;
    3708                 :      38201 :   tree vec2;
    3709                 :      38201 :   switch_update su;
    3710                 :      38201 :   size_t k = 1, l = 0;
    3711                 :            : 
    3712                 :      38201 :   if (TREE_CODE (op) == SSA_NAME)
    3713                 :            :     {
    3714                 :      38184 :       vr = get_value_range (op);
    3715                 :            : 
    3716                 :            :       /* We can only handle integer ranges.  */
    3717                 :      38184 :       if (vr->varying_p ()
    3718                 :      10353 :           || vr->undefined_p ()
    3719                 :      48503 :           || vr->symbolic_p ())
    3720                 :      28172 :         return false;
    3721                 :            : 
    3722                 :            :       /* Find case label for min/max of the value range.  */
    3723                 :      10012 :       take_default = !find_case_label_ranges (stmt, vr, &i, &j, &k, &l);
    3724                 :            :     }
    3725                 :         17 :   else if (TREE_CODE (op) == INTEGER_CST)
    3726                 :            :     {
    3727                 :         17 :       take_default = !find_case_label_index (stmt, 1, op, &i);
    3728                 :         17 :       if (take_default)
    3729                 :            :         {
    3730                 :          0 :           i = 1;
    3731                 :          0 :           j = 0;
    3732                 :            :         }
    3733                 :            :       else
    3734                 :            :         {
    3735                 :         17 :           j = i;
    3736                 :            :         }
    3737                 :            :     }
    3738                 :            :   else
    3739                 :            :     return false;
    3740                 :            : 
    3741                 :      10029 :   n = gimple_switch_num_labels (stmt);
    3742                 :            : 
    3743                 :            :   /* We can truncate the case label ranges that partially overlap with OP's
    3744                 :            :      value range.  */
    3745                 :      10029 :   size_t min_idx = 1, max_idx = 0;
    3746                 :      10029 :   if (vr != NULL)
    3747                 :      10012 :     find_case_label_range (stmt, vr->min (), vr->max (), &min_idx, &max_idx);
    3748                 :      10029 :   if (min_idx <= max_idx)
    3749                 :            :     {
    3750                 :       9385 :       tree min_label = gimple_switch_label (stmt, min_idx);
    3751                 :       9385 :       tree max_label = gimple_switch_label (stmt, max_idx);
    3752                 :            : 
    3753                 :            :       /* Avoid changing the type of the case labels when truncating.  */
    3754                 :       9385 :       tree case_label_type = TREE_TYPE (CASE_LOW (min_label));
    3755                 :       9385 :       tree vr_min = fold_convert (case_label_type, vr->min ());
    3756                 :       9385 :       tree vr_max = fold_convert (case_label_type, vr->max ());
    3757                 :            : 
    3758                 :       9385 :       if (vr->kind () == VR_RANGE)
    3759                 :            :         {
    3760                 :            :           /* If OP's value range is [2,8] and the low label range is
    3761                 :            :              0 ... 3, truncate the label's range to 2 .. 3.  */
    3762                 :       9327 :           if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0
    3763                 :          6 :               && CASE_HIGH (min_label) != NULL_TREE
    3764                 :       9333 :               && tree_int_cst_compare (CASE_HIGH (min_label), vr_min) >= 0)
    3765                 :          6 :             CASE_LOW (min_label) = vr_min;
    3766                 :            : 
    3767                 :            :           /* If OP's value range is [2,8] and the high label range is
    3768                 :            :              7 ... 10, truncate the label's range to 7 .. 8.  */
    3769                 :       9327 :           if (tree_int_cst_compare (CASE_LOW (max_label), vr_max) <= 0
    3770                 :       9327 :               && CASE_HIGH (max_label) != NULL_TREE
    3771                 :       9514 :               && tree_int_cst_compare (CASE_HIGH (max_label), vr_max) > 0)
    3772                 :         10 :             CASE_HIGH (max_label) = vr_max;
    3773                 :            :         }
    3774                 :         58 :       else if (vr->kind () == VR_ANTI_RANGE)
    3775                 :            :         {
    3776                 :         58 :           tree one_cst = build_one_cst (case_label_type);
    3777                 :            : 
    3778                 :         58 :           if (min_label == max_label)
    3779                 :            :             {
    3780                 :            :               /* If OP's value range is ~[7,8] and the label's range is
    3781                 :            :                  7 ... 10, truncate the label's range to 9 ... 10.  */
    3782                 :         51 :               if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) == 0
    3783                 :         48 :                   && CASE_HIGH (min_label) != NULL_TREE
    3784                 :         53 :                   && tree_int_cst_compare (CASE_HIGH (min_label), vr_max) > 0)
    3785                 :          2 :                 CASE_LOW (min_label)
    3786                 :          2 :                   = int_const_binop (PLUS_EXPR, vr_max, one_cst);
    3787                 :            : 
    3788                 :            :               /* If OP's value range is ~[7,8] and the label's range is
    3789                 :            :                  5 ... 8, truncate the label's range to 5 ... 6.  */
    3790                 :         51 :               if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0
    3791                 :          3 :                   && CASE_HIGH (min_label) != NULL_TREE
    3792                 :         54 :                   && tree_int_cst_compare (CASE_HIGH (min_label), vr_max) == 0)
    3793                 :          1 :                 CASE_HIGH (min_label)
    3794                 :          1 :                   = int_const_binop (MINUS_EXPR, vr_min, one_cst);
    3795                 :            :             }
    3796                 :            :           else
    3797                 :            :             {
    3798                 :            :               /* If OP's value range is ~[2,8] and the low label range is
    3799                 :            :                  0 ... 3, truncate the label's range to 0 ... 1.  */
    3800                 :          7 :               if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0
    3801                 :          1 :                   && CASE_HIGH (min_label) != NULL_TREE
    3802                 :          8 :                   && tree_int_cst_compare (CASE_HIGH (min_label), vr_min) >= 0)
    3803                 :          1 :                 CASE_HIGH (min_label)
    3804                 :          1 :                   = int_const_binop (MINUS_EXPR, vr_min, one_cst);
    3805                 :            : 
    3806                 :            :               /* If OP's value range is ~[2,8] and the high label range is
    3807                 :            :                  7 ... 10, truncate the label's range to 9 ... 10.  */
    3808                 :          7 :               if (tree_int_cst_compare (CASE_LOW (max_label), vr_max) <= 0
    3809                 :          7 :                   && CASE_HIGH (max_label) != NULL_TREE
    3810                 :          8 :                   && tree_int_cst_compare (CASE_HIGH (max_label), vr_max) > 0)
    3811                 :          1 :                 CASE_LOW (max_label)
    3812                 :          1 :                   = int_const_binop (PLUS_EXPR, vr_max, one_cst);
    3813                 :            :             }
    3814                 :            :         }
    3815                 :            : 
    3816                 :            :       /* Canonicalize singleton case ranges.  */
    3817                 :       9385 :       if (tree_int_cst_equal (CASE_LOW (min_label), CASE_HIGH (min_label)))
    3818                 :          3 :         CASE_HIGH (min_label) = NULL_TREE;
    3819                 :       9385 :       if (tree_int_cst_equal (CASE_LOW (max_label), CASE_HIGH (max_label)))
    3820                 :          3 :         CASE_HIGH (max_label) = NULL_TREE;
    3821                 :            :     }
    3822                 :            : 
    3823                 :            :   /* We can also eliminate case labels that lie completely outside OP's value
    3824                 :            :      range.  */
    3825                 :            : 
    3826                 :            :   /* Bail out if this is just all edges taken.  */
    3827                 :      10029 :   if (i == 1
    3828                 :       7532 :       && j == n - 1
    3829                 :       7390 :       && take_default)
    3830                 :            :     return false;
    3831                 :            : 
    3832                 :            :   /* Build a new vector of taken case labels.  */
    3833                 :       3023 :   vec2 = make_tree_vec (j - i + 1 + l - k + 1 + (int)take_default);
    3834                 :       3023 :   n2 = 0;
    3835                 :            : 
    3836                 :            :   /* Add the default edge, if necessary.  */
    3837                 :       3023 :   if (take_default)
    3838                 :       2579 :     TREE_VEC_ELT (vec2, n2++) = gimple_switch_default_label (stmt);
    3839                 :            : 
    3840                 :      10860 :   for (; i <= j; ++i, ++n2)
    3841                 :       7837 :     TREE_VEC_ELT (vec2, n2) = gimple_switch_label (stmt, i);
    3842                 :            : 
    3843                 :       3201 :   for (; k <= l; ++k, ++n2)
    3844                 :        178 :     TREE_VEC_ELT (vec2, n2) = gimple_switch_label (stmt, k);
    3845                 :            : 
    3846                 :            :   /* Mark needed edges.  */
    3847                 :      13617 :   for (i = 0; i < n2; ++i)
    3848                 :            :     {
    3849                 :      10594 :       e = find_edge (gimple_bb (stmt),
    3850                 :            :                      label_to_block (cfun,
    3851                 :      10594 :                                      CASE_LABEL (TREE_VEC_ELT (vec2, i))));
    3852                 :      10594 :       e->aux = (void *)-1;
    3853                 :            :     }
    3854                 :            : 
    3855                 :            :   /* Queue not needed edges for later removal.  */
    3856                 :      18798 :   FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
    3857                 :            :     {
    3858                 :      15775 :       if (e->aux == (void *)-1)
    3859                 :            :         {
    3860                 :      10261 :           e->aux = NULL;
    3861                 :      10261 :           continue;
    3862                 :            :         }
    3863                 :            : 
    3864                 :       5514 :       if (dump_file && (dump_flags & TDF_DETAILS))
    3865                 :            :         {
    3866                 :          0 :           fprintf (dump_file, "removing unreachable case label\n");
    3867                 :            :         }
    3868                 :       5514 :       to_remove_edges.safe_push (e);
    3869                 :       5514 :       e->flags &= ~EDGE_EXECUTABLE;
    3870                 :       5514 :       e->flags |= EDGE_IGNORE;
    3871                 :            :     }
    3872                 :            : 
    3873                 :            :   /* And queue an update for the stmt.  */
    3874                 :       3023 :   su.stmt = stmt;
    3875                 :       3023 :   su.vec = vec2;
    3876                 :       3023 :   to_update_switch_stmts.safe_push (su);
    3877                 :       3023 :   return false;
    3878                 :            : }
    3879                 :            : 
    3880                 :            : void
    3881                 :    2813820 : vr_values::cleanup_edges_and_switches (void)
    3882                 :            : {
    3883                 :    2813820 :   int i;
    3884                 :    2813820 :   edge e;
    3885                 :    2813820 :   switch_update *su;
    3886                 :            : 
    3887                 :            :   /* Remove dead edges from SWITCH_EXPR optimization.  This leaves the
    3888                 :            :      CFG in a broken state and requires a cfg_cleanup run.  */
    3889                 :    2819330 :   FOR_EACH_VEC_ELT (to_remove_edges, i, e)
    3890                 :       5514 :     remove_edge (e);
    3891                 :            : 
    3892                 :            :   /* Update SWITCH_EXPR case label vector.  */
    3893                 :    2816840 :   FOR_EACH_VEC_ELT (to_update_switch_stmts, i, su)
    3894                 :            :     {
    3895                 :       3023 :       size_t j;
    3896                 :       3023 :       size_t n = TREE_VEC_LENGTH (su->vec);
    3897                 :       3023 :       tree label;
    3898                 :       3023 :       gimple_switch_set_num_labels (su->stmt, n);
    3899                 :      13617 :       for (j = 0; j < n; j++)
    3900                 :      10594 :         gimple_switch_set_label (su->stmt, j, TREE_VEC_ELT (su->vec, j));
    3901                 :            :       /* As we may have replaced the default label with a regular one
    3902                 :            :          make sure to make it a real default label again.  This ensures
    3903                 :            :          optimal expansion.  */
    3904                 :       3023 :       label = gimple_switch_label (su->stmt, 0);
    3905                 :       3023 :       CASE_LOW (label) = NULL_TREE;
    3906                 :       3023 :       CASE_HIGH (label) = NULL_TREE;
    3907                 :            :     }
    3908                 :            : 
    3909                 :    2813820 :   if (!to_remove_edges.is_empty ())
    3910                 :            :     {
    3911                 :       2861 :       free_dominance_info (CDI_DOMINATORS);
    3912                 :       2861 :       loops_state_set (LOOPS_NEED_FIXUP);
    3913                 :            :     }
    3914                 :            : 
    3915                 :    2813820 :   to_remove_edges.release ();
    3916                 :    2813820 :   to_update_switch_stmts.release ();
    3917                 :    2813820 : }
    3918                 :            : 
    3919                 :            : /* Simplify an integral conversion from an SSA name in STMT.  */
    3920                 :            : 
    3921                 :            : static bool
    3922                 :    3312860 : simplify_conversion_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt)
    3923                 :            : {
    3924                 :    3312860 :   tree innerop, middleop, finaltype;
    3925                 :    3312860 :   gimple *def_stmt;
    3926                 :    3312860 :   signop inner_sgn, middle_sgn, final_sgn;
    3927                 :    3312860 :   unsigned inner_prec, middle_prec, final_prec;
    3928                 :    3312860 :   widest_int innermin, innermed, innermax, middlemin, middlemed, middlemax;
    3929                 :            : 
    3930                 :    3312860 :   finaltype = TREE_TYPE (gimple_assign_lhs (stmt));
    3931                 :    3312860 :   if (!INTEGRAL_TYPE_P (finaltype))
    3932                 :            :     return false;
    3933                 :    3124980 :   middleop = gimple_assign_rhs1 (stmt);
    3934                 :    3124980 :   def_stmt = SSA_NAME_DEF_STMT (middleop);
    3935                 :    3124980 :   if (!is_gimple_assign (def_stmt)
    3936                 :    3124980 :       || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
    3937                 :            :     return false;
    3938                 :     104557 :   innerop = gimple_assign_rhs1 (def_stmt);
    3939                 :     104557 :   if (TREE_CODE (innerop) != SSA_NAME
    3940                 :     104557 :       || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop))
    3941                 :            :     return false;
    3942                 :            : 
    3943                 :            :   /* Get the value-range of the inner operand.  Use get_range_info in
    3944                 :            :      case innerop was created during substitute-and-fold.  */
    3945                 :     101258 :   wide_int imin, imax;
    3946                 :     202301 :   if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop))
    3947                 :     179383 :       || get_range_info (innerop, &imin, &imax) != VR_RANGE)
    3948                 :      80107 :     return false;
    3949                 :      21151 :   innermin = widest_int::from (imin, TYPE_SIGN (TREE_TYPE (innerop)));
    3950                 :      21151 :   innermax = widest_int::from (imax, TYPE_SIGN (TREE_TYPE (innerop)));
    3951                 :            : 
    3952                 :            :   /* Simulate the conversion chain to check if the result is equal if
    3953                 :            :      the middle conversion is removed.  */
    3954                 :      21151 :   inner_prec = TYPE_PRECISION (TREE_TYPE (innerop));
    3955                 :      21151 :   middle_prec = TYPE_PRECISION (TREE_TYPE (middleop));
    3956                 :      21151 :   final_prec = TYPE_PRECISION (finaltype);
    3957                 :            : 
    3958                 :            :   /* If the first conversion is not injective, the second must not
    3959                 :            :      be widening.  */
    3960                 :      42302 :   if (wi::gtu_p (innermax - innermin,
    3961                 :      21151 :                  wi::mask <widest_int> (middle_prec, false))
    3962                 :      21151 :       && middle_prec < final_prec)
    3963                 :       6925 :     return false;
    3964                 :            :   /* We also want a medium value so that we can track the effect that
    3965                 :            :      narrowing conversions with sign change have.  */
    3966                 :      14226 :   inner_sgn = TYPE_SIGN (TREE_TYPE (innerop));
    3967                 :      14226 :   if (inner_sgn == UNSIGNED)
    3968                 :       4165 :     innermed = wi::shifted_mask <widest_int> (1, inner_prec - 1, false);
    3969                 :            :   else
    3970                 :      10061 :     innermed = 0;
    3971                 :      14226 :   if (wi::cmp (innermin, innermed, inner_sgn) >= 0
    3972                 :      14226 :       || wi::cmp (innermed, innermax, inner_sgn) >= 0)
    3973                 :      13325 :     innermed = innermin;
    3974                 :            : 
    3975                 :      14226 :   middle_sgn = TYPE_SIGN (TREE_TYPE (middleop));
    3976                 :      14226 :   middlemin = wi::ext (innermin, middle_prec, middle_sgn);
    3977                 :      14226 :   middlemed = wi::ext (innermed, middle_prec, middle_sgn);
    3978                 :      14226 :   middlemax = wi::ext (innermax, middle_prec, middle_sgn);
    3979                 :            : 
    3980                 :            :   /* Require that the final conversion applied to both the original
    3981                 :            :      and the intermediate range produces the same result.  */
    3982                 :      14226 :   final_sgn = TYPE_SIGN (finaltype);
    3983                 :      14226 :   if (wi::ext (middlemin, final_prec, final_sgn)
    3984                 :      14226 :          != wi::ext (innermin, final_prec, final_sgn)
    3985                 :      13592 :       || wi::ext (middlemed, final_prec, final_sgn)
    3986                 :      27164 :          != wi::ext (innermed, final_prec, final_sgn)
    3987                 :      27293 :       || wi::ext (middlemax, final_prec, final_sgn)
    3988                 :      27051 :          != wi::ext (innermax, final_prec, final_sgn))
    3989                 :       1107 :     return false;
    3990                 :            : 
    3991                 :      13119 :   gimple_assign_set_rhs1 (stmt, innerop);
    3992                 :      13119 :   fold_stmt (gsi, follow_single_use_edges);
    3993                 :      13119 :   return true;
    3994                 :            : }
    3995                 :            : 
    3996                 :            : /* Simplify a conversion from integral SSA name to float in STMT.  */
    3997                 :            : 
    3998                 :            : bool
    3999                 :     136726 : vr_values::simplify_float_conversion_using_ranges (gimple_stmt_iterator *gsi,
    4000                 :            :                                                    gimple *stmt)
    4001                 :            : {
    4002                 :     136726 :   tree rhs1 = gimple_assign_rhs1 (stmt);
    4003                 :     136726 :   const value_range_equiv *vr = get_value_range (rhs1);
    4004                 :     136726 :   scalar_float_mode fltmode
    4005                 :     136726 :     = SCALAR_FLOAT_TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt)));
    4006                 :     136726 :   scalar_int_mode mode;
    4007                 :     136726 :   tree tem;
    4008                 :     136726 :   gassign *conv;
    4009                 :            : 
    4010                 :            :   /* We can only handle constant ranges.  */
    4011                 :     136726 :   if (!range_int_cst_p (vr))
    4012                 :            :     return false;
    4013                 :            : 
    4014                 :            :   /* First check if we can use a signed type in place of an unsigned.  */
    4015                 :      64384 :   scalar_int_mode rhs_mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (rhs1));
    4016                 :      64384 :   if (TYPE_UNSIGNED (TREE_TYPE (rhs1))
    4017                 :       3116 :       && can_float_p (fltmode, rhs_mode, 0) != CODE_FOR_nothing
    4018                 :      66176 :       && range_fits_type_p (vr, TYPE_PRECISION (TREE_TYPE (rhs1)), SIGNED))
    4019                 :            :     mode = rhs_mode;
    4020                 :            :   /* If we can do the conversion in the current input mode do nothing.  */
    4021                 :     126486 :   else if (can_float_p (fltmode, rhs_mode,
    4022                 :      63243 :                         TYPE_UNSIGNED (TREE_TYPE (rhs1))) != CODE_FOR_nothing)
    4023                 :            :     return false;
    4024                 :            :   /* Otherwise search for a mode we can use, starting from the narrowest
    4025                 :            :      integer mode available.  */
    4026                 :            :   else
    4027                 :            :     {
    4028                 :       2778 :       mode = NARROWEST_INT_MODE;
    4029                 :      11040 :       for (;;)
    4030                 :            :         {
    4031                 :            :           /* If we cannot do a signed conversion to float from mode
    4032                 :            :              or if the value-range does not fit in the signed type
    4033                 :            :              try with a wider mode.  */
    4034                 :      11040 :           if (can_float_p (fltmode, mode, 0) != CODE_FOR_nothing
    4035                 :      11040 :               && range_fits_type_p (vr, GET_MODE_PRECISION (mode), SIGNED))
    4036                 :            :             break;
    4037                 :            : 
    4038                 :            :           /* But do not widen the input.  Instead leave that to the
    4039                 :            :              optabs expansion code.  */
    4040                 :      10982 :           if (!GET_MODE_WIDER_MODE (mode).exists (&mode)
    4041                 :      10982 :               || GET_MODE_PRECISION (mode) > TYPE_PRECISION (TREE_TYPE (rhs1)))
    4042                 :            :             return false;
    4043                 :            :         }
    4044                 :            :     }
    4045                 :            : 
    4046                 :            :   /* It works, insert a truncation or sign-change before the
    4047                 :            :      float conversion.  */
    4048                 :       1199 :   tem = make_ssa_name (build_nonstandard_integer_type
    4049                 :       1199 :                           (GET_MODE_PRECISION (mode), 0));
    4050                 :       1199 :   conv = gimple_build_assign (tem, NOP_EXPR, rhs1);
    4051                 :       1199 :   gsi_insert_before (gsi, conv, GSI_SAME_STMT);
    4052                 :       1199 :   gimple_assign_set_rhs1 (stmt, tem);
    4053                 :       1199 :   fold_stmt (gsi, follow_single_use_edges);
    4054                 :            : 
    4055                 :       1199 :   return true;
    4056                 :            : }
    4057                 :            : 
    4058                 :            : /* Simplify an internal fn call using ranges if possible.  */
    4059                 :            : 
    4060                 :            : bool
    4061                 :     299639 : vr_values::simplify_internal_call_using_ranges (gimple_stmt_iterator *gsi,
    4062                 :            :                                                 gimple *stmt)
    4063                 :            : {
    4064                 :     299639 :   enum tree_code subcode;
    4065                 :     299639 :   bool is_ubsan = false;
    4066                 :     299639 :   bool ovf = false;
    4067                 :     299639 :   switch (gimple_call_internal_fn (stmt))
    4068                 :            :     {
    4069                 :            :     case IFN_UBSAN_CHECK_ADD:
    4070                 :            :       subcode = PLUS_EXPR;
    4071                 :            :       is_ubsan = true;
    4072                 :            :       break;
    4073                 :       4138 :     case IFN_UBSAN_CHECK_SUB:
    4074                 :       4138 :       subcode = MINUS_EXPR;
    4075                 :       4138 :       is_ubsan = true;
    4076                 :       4138 :       break;
    4077                 :       3669 :     case IFN_UBSAN_CHECK_MUL:
    4078                 :       3669 :       subcode = MULT_EXPR;
    4079                 :       3669 :       is_ubsan = true;
    4080                 :       3669 :       break;
    4081                 :      34402 :     case IFN_ADD_OVERFLOW:
    4082                 :      34402 :       subcode = PLUS_EXPR;
    4083                 :      34402 :       break;
    4084                 :      46807 :     case IFN_SUB_OVERFLOW:
    4085                 :      46807 :       subcode = MINUS_EXPR;
    4086                 :      46807 :       break;
    4087                 :      47878 :     case IFN_MUL_OVERFLOW:
    4088                 :      47878 :       subcode = MULT_EXPR;
    4089                 :      47878 :       break;
    4090                 :            :     default:
    4091                 :            :       return false;
    4092                 :            :     }
    4093                 :            : 
    4094                 :     141060 :   tree op0 = gimple_call_arg (stmt, 0);
    4095                 :     141060 :   tree op1 = gimple_call_arg (stmt, 1);
    4096                 :     141060 :   tree type;
    4097                 :     141060 :   if (is_ubsan)
    4098                 :            :     {
    4099                 :      11973 :       type = TREE_TYPE (op0);
    4100                 :      11973 :       if (VECTOR_TYPE_P (type))
    4101                 :            :         return false;
    4102                 :            :     }
    4103                 :     129087 :   else if (gimple_call_lhs (stmt) == NULL_TREE)
    4104                 :            :     return false;
    4105                 :            :   else
    4106                 :     129087 :     type = TREE_TYPE (TREE_TYPE (gimple_call_lhs (stmt)));
    4107                 :     139364 :   if (!check_for_binary_op_overflow (subcode, type, op0, op1, &ovf)
    4108                 :     139364 :       || (is_ubsan && ovf))
    4109                 :            :     return false;
    4110                 :            : 
    4111                 :       3741 :   gimple *g;
    4112                 :       3741 :   location_t loc = gimple_location (stmt);
    4113                 :       3741 :   if (is_ubsan)
    4114                 :        904 :     g = gimple_build_assign (gimple_call_lhs (stmt), subcode, op0, op1);
    4115                 :            :   else
    4116                 :            :     {
    4117                 :       2837 :       int prec = TYPE_PRECISION (type);
    4118                 :       2837 :       tree utype = type;
    4119                 :       2837 :       if (ovf
    4120                 :       1419 :           || !useless_type_conversion_p (type, TREE_TYPE (op0))
    4121                 :       3554 :           || !useless_type_conversion_p (type, TREE_TYPE (op1)))
    4122                 :       2480 :         utype = build_nonstandard_integer_type (prec, 1);
    4123                 :       2837 :       if (TREE_CODE (op0) == INTEGER_CST)
    4124                 :       1649 :         op0 = fold_convert (utype, op0);
    4125                 :       1188 :       else if (!useless_type_conversion_p (utype, TREE_TYPE (op0)))
    4126                 :            :         {
    4127                 :        663 :           g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, op0);
    4128                 :        663 :           gimple_set_location (g, loc);
    4129                 :        663 :           gsi_insert_before (gsi, g, GSI_SAME_STMT);
    4130                 :        663 :           op0 = gimple_assign_lhs (g);
    4131                 :            :         }
    4132                 :       2837 :       if (TREE_CODE (op1) == INTEGER_CST)
    4133                 :       1162 :         op1 = fold_convert (utype, op1);
    4134                 :       1675 :       else if (!useless_type_conversion_p (utype, TREE_TYPE (op1)))
    4135                 :            :         {
    4136                 :        473 :           g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, op1);
    4137                 :        473 :           gimple_set_location (g, loc);
    4138                 :        473 :           gsi_insert_before (gsi, g, GSI_SAME_STMT);
    4139                 :        473 :           op1 = gimple_assign_lhs (g);
    4140                 :            :         }
    4141                 :       2837 :       g = gimple_build_assign (make_ssa_name (utype), subcode, op0, op1);
    4142                 :       2837 :       gimple_set_location (g, loc);
    4143                 :       2837 :       gsi_insert_before (gsi, g, GSI_SAME_STMT);
    4144                 :       2837 :       if (utype != type)
    4145                 :            :         {
    4146                 :       2468 :           g = gimple_build_assign (make_ssa_name (type), NOP_EXPR,
    4147                 :            :                                    gimple_assign_lhs (g));
    4148                 :       2468 :           gimple_set_location (g, loc);
    4149                 :       2468 :           gsi_insert_before (gsi, g, GSI_SAME_STMT);
    4150                 :            :         }
    4151                 :       2837 :       g = gimple_build_assign (gimple_call_lhs (stmt), COMPLEX_EXPR,
    4152                 :            :                                gimple_assign_lhs (g),
    4153                 :            :                                build_int_cst (type, ovf));
    4154                 :            :     }
    4155                 :       3741 :   gimple_set_location (g, loc);
    4156                 :       3741 :   gsi_replace (gsi, g, false);
    4157                 :       3741 :   return true;
    4158                 :            : }
    4159                 :            : 
    4160                 :            : /* Return true if VAR is a two-valued variable.  Set a and b with the
    4161                 :            :    two-values when it is true.  Return false otherwise.  */
    4162                 :            : 
    4163                 :            : bool
    4164                 :     226310 : vr_values::two_valued_val_range_p (tree var, tree *a, tree *b)
    4165                 :            : {
    4166                 :     226310 :   const value_range_equiv *vr = get_value_range (var);
    4167                 :     226310 :   if (vr->varying_p ()
    4168                 :      83505 :       || vr->undefined_p ()
    4169                 :      83310 :       || TREE_CODE (vr->min ()) != INTEGER_CST
    4170                 :     304194 :       || TREE_CODE (vr->max ()) != INTEGER_CST)
    4171                 :            :     return false;
    4172                 :            : 
    4173                 :      77170 :   if (vr->kind () == VR_RANGE
    4174                 :      77170 :       && wi::to_wide (vr->max ()) - wi::to_wide (vr->min ()) == 1)
    4175                 :            :     {
    4176                 :        650 :       *a = vr->min ();
    4177                 :        650 :       *b = vr->max ();
    4178                 :        650 :       return true;
    4179                 :            :     }
    4180                 :            : 
    4181                 :            :   /* ~[TYPE_MIN + 1, TYPE_MAX - 1] */
    4182                 :      76520 :   if (vr->kind () == VR_ANTI_RANGE
    4183                 :      11393 :       && (wi::to_wide (vr->min ())
    4184                 :      22786 :           - wi::to_wide (vrp_val_min (TREE_TYPE (var)))) == 1
    4185                 :      76698 :       && (wi::to_wide (vrp_val_max (TREE_TYPE (var)))
    4186                 :      76874 :           - wi::to_wide (vr->max ())) == 1)
    4187                 :            :     {
    4188                 :          2 :       *a = vrp_val_min (TREE_TYPE (var));
    4189                 :          2 :       *b = vrp_val_max (TREE_TYPE (var));
    4190                 :          2 :       return true;
    4191                 :            :     }
    4192                 :            : 
    4193                 :            :   return false;
    4194                 :            : }
    4195                 :            : 
    4196                 :            : /* Simplify STMT using ranges if possible.  */
    4197                 :            : 
    4198                 :            : bool
    4199                 :  157603000 : vr_values::simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
    4200                 :            : {
    4201                 :  157603000 :   gimple *stmt = gsi_stmt (*gsi);
    4202                 :  157603000 :   if (is_gimple_assign (stmt))
    4203                 :            :     {
    4204                 :   49689000 :       enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
    4205                 :   49689000 :       tree rhs1 = gimple_assign_rhs1 (stmt);
    4206                 :   49689000 :       tree rhs2 = gimple_assign_rhs2 (stmt);
    4207                 :   49689000 :       tree lhs = gimple_assign_lhs (stmt);
    4208                 :   49689000 :       tree val1 = NULL_TREE, val2 = NULL_TREE;
    4209                 :   49689000 :       use_operand_p use_p;
    4210                 :   49689000 :       gimple *use_stmt;
    4211                 :            : 
    4212                 :            :       /* Convert:
    4213                 :            :          LHS = CST BINOP VAR
    4214                 :            :          Where VAR is two-valued and LHS is used in GIMPLE_COND only
    4215                 :            :          To:
    4216                 :            :          LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2)
    4217                 :            : 
    4218                 :            :          Also handles:
    4219                 :            :          LHS = VAR BINOP CST
    4220                 :            :          Where VAR is two-valued and LHS is used in GIMPLE_COND only
    4221                 :            :          To:
    4222                 :            :          LHS = VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST) */
    4223                 :            : 
    4224                 :   49689000 :       if (TREE_CODE_CLASS (rhs_code) == tcc_binary
    4225                 :    8229160 :           && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
    4226                 :    6032130 :           && ((TREE_CODE (rhs1) == INTEGER_CST
    4227                 :     109175 :                && TREE_CODE (rhs2) == SSA_NAME)
    4228                 :    5923500 :               || (TREE_CODE (rhs2) == INTEGER_CST
    4229                 :    3917080 :                   && TREE_CODE (rhs1) == SSA_NAME))
    4230                 :    4025160 :           && single_imm_use (lhs, &use_p, &use_stmt)
    4231                 :   52739300 :           && gimple_code (use_stmt) == GIMPLE_COND)
    4232                 :            : 
    4233                 :            :         {
    4234                 :     226310 :           tree new_rhs1 = NULL_TREE;
    4235                 :     226310 :           tree new_rhs2 = NULL_TREE;
    4236                 :     226310 :           tree cmp_var = NULL_TREE;
    4237                 :            : 
    4238                 :     226310 :           if (TREE_CODE (rhs2) == SSA_NAME
    4239                 :     226310 :               && two_valued_val_range_p (rhs2, &val1, &val2))
    4240                 :            :             {
    4241                 :            :               /* Optimize RHS1 OP [VAL1, VAL2].  */
    4242                 :        100 :               new_rhs1 = int_const_binop (rhs_code, rhs1, val1);
    4243                 :        100 :               new_rhs2 = int_const_binop (rhs_code, rhs1, val2);
    4244                 :        100 :               cmp_var = rhs2;
    4245                 :            :             }
    4246                 :     226210 :           else if (TREE_CODE (rhs1) == SSA_NAME
    4247                 :     226210 :                    && two_valued_val_range_p (rhs1, &val1, &val2))
    4248                 :            :             {
    4249                 :            :               /* Optimize [VAL1, VAL2] OP RHS2.  */
    4250                 :        552 :               new_rhs1 = int_const_binop (rhs_code, val1, rhs2);
    4251                 :        552 :               new_rhs2 = int_const_binop (rhs_code, val2, rhs2);
    4252                 :        552 :               cmp_var = rhs1;
    4253                 :            :             }
    4254                 :            : 
    4255                 :            :           /* If we could not find two-vals or the optimzation is invalid as
    4256                 :            :              in divide by zero, new_rhs1 / new_rhs will be NULL_TREE.  */
    4257                 :     226310 :           if (new_rhs1 && new_rhs2)
    4258                 :            :             {
    4259                 :        652 :               tree cond = build2 (EQ_EXPR, boolean_type_node, cmp_var, val1);
    4260                 :        652 :               gimple_assign_set_rhs_with_ops (gsi,
    4261                 :            :                                               COND_EXPR, cond,
    4262                 :            :                                               new_rhs1,
    4263                 :            :                                               new_rhs2);
    4264                 :        652 :               update_stmt (gsi_stmt (*gsi));
    4265                 :        652 :               fold_stmt (gsi, follow_single_use_edges);
    4266                 :    4904330 :               return true;
    4267                 :            :             }
    4268                 :            :         }
    4269                 :            : 
    4270                 :   49688400 :       switch (rhs_code)
    4271                 :            :         {
    4272                 :     476659 :         case EQ_EXPR:
    4273                 :     476659 :         case NE_EXPR:
    4274                 :            :           /* Transform EQ_EXPR, NE_EXPR into BIT_XOR_EXPR or identity
    4275                 :            :              if the RHS is zero or one, and the LHS are known to be boolean
    4276                 :            :              values.  */
    4277                 :     476659 :           if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
    4278                 :     320388 :             return simplify_truth_ops_using_ranges (gsi, stmt);
    4279                 :            :           break;
    4280                 :            : 
    4281                 :            :       /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
    4282                 :            :          and BIT_AND_EXPR respectively if the first operand is greater
    4283                 :            :          than zero and the second operand is an exact power of two.
    4284                 :            :          Also optimize TRUNC_MOD_EXPR away if the second operand is
    4285                 :            :          constant and the first operand already has the right value
    4286                 :            :          range.  */
    4287                 :     216886 :         case TRUNC_DIV_EXPR:
    4288                 :     216886 :         case TRUNC_MOD_EXPR:
    4289                 :     216886 :           if ((TREE_CODE (rhs1) == SSA_NAME
    4290                 :     216886 :                || TREE_CODE (rhs1) == INTEGER_CST)
    4291                 :     433734 :               && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
    4292                 :     215818 :             return simplify_div_or_mod_using_ranges (gsi, stmt);
    4293                 :            :           break;
    4294                 :            : 
    4295                 :            :       /* Transform ABS (X) into X or -X as appropriate.  */
    4296                 :      35506 :         case ABS_EXPR:
    4297                 :      35506 :           if (TREE_CODE (rhs1) == SSA_NAME
    4298                 :      71010 :               && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
    4299                 :       3330 :             return simplify_abs_using_ranges (gsi, stmt);
    4300                 :            :           break;
    4301                 :            : 
    4302                 :     807362 :         case BIT_AND_EXPR:
    4303                 :     807362 :         case BIT_IOR_EXPR:
    4304                 :            :           /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR
    4305                 :            :              if all the bits being cleared are already cleared or
    4306                 :            :              all the bits being set are already set.  */
    4307                 :     807362 :           if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
    4308                 :     802280 :             return simplify_bit_ops_using_ranges (gsi, stmt);
    4309                 :            :           break;
    4310                 :            : 
    4311                 :    3989910 :         CASE_CONVERT:
    4312                 :    3989910 :           if (TREE_CODE (rhs1) == SSA_NAME
    4313                 :    7824280 :               && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
    4314                 :    3312860 :             return simplify_conversion_using_ranges (gsi, stmt);
    4315                 :            :           break;
    4316                 :            : 
    4317                 :     137721 :         case FLOAT_EXPR:
    4318                 :     137721 :           if (TREE_CODE (rhs1) == SSA_NAME
    4319                 :     275442 :               && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
    4320                 :     136726 :             return simplify_float_conversion_using_ranges (gsi, stmt);
    4321                 :            :           break;
    4322                 :            : 
    4323                 :     112276 :         case MIN_EXPR:
    4324                 :     112276 :         case MAX_EXPR:
    4325                 :     112276 :           return simplify_min_or_max_using_ranges (gsi, stmt);
    4326                 :            : 
    4327                 :            :         default:
    4328                 :            :           break;
    4329                 :            :         }
    4330                 :            :     }
    4331                 :  107914000 :   else if (gimple_code (stmt) == GIMPLE_COND)
    4332                 :    7519440 :     return simplify_cond_using_ranges_1 (as_a <gcond *> (stmt));
    4333                 :  100395000 :   else if (gimple_code (stmt) == GIMPLE_SWITCH)
    4334                 :      38201 :     return simplify_switch_using_ranges (as_a <gswitch *> (stmt));
    4335                 :  100357000 :   else if (is_gimple_call (stmt)
    4336                 :  100357000 :            && gimple_call_internal_p (stmt))
    4337                 :     299639 :     return simplify_internal_call_using_ranges (gsi, stmt);
    4338                 :            : 
    4339                 :            :   return false;
    4340                 :            : }
    4341                 :            : 
    4342                 :            : /* Set the lattice entry for VAR to VR.  */
    4343                 :            : 
    4344                 :            : void
    4345                 :          0 : vr_values::set_vr_value (tree var, value_range_equiv *vr)
    4346                 :            : {
    4347                 :          0 :   if (SSA_NAME_VERSION (var) >= num_vr_values)
    4348                 :            :     return;
    4349                 :          0 :   vr_value[SSA_NAME_VERSION (var)] = vr;
    4350                 :            : }
    4351                 :            : 
    4352                 :            : /* Swap the lattice entry for VAR with VR and return the old entry.  */
    4353                 :            : 
    4354                 :            : value_range_equiv *
    4355                 :   84635900 : vr_values::swap_vr_value (tree var, value_range_equiv *vr)
    4356                 :            : {
    4357                 :   84635900 :   if (SSA_NAME_VERSION (var) >= num_vr_values)
    4358                 :            :     return NULL;
    4359                 :   84635900 :   std::swap (vr_value[SSA_NAME_VERSION (var)], vr);
    4360                 :   84635900 :   return vr;
    4361                 :            : }

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.