LCOV - code coverage report
Current view: top level - gcc - vr-values.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 96.9 % 969 939
Test Date: 2025-07-05 13:26:22 Functions: 100.0 % 32 32
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-2025 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-iterator.h"
      36                 :             : #include "gimple-fold.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                 :             : #include "gimple-range.h"
      54                 :             : 
      55                 :             : /* Return true if op is in a boolean [0, 1] value-range.  */
      56                 :             : 
      57                 :             : bool
      58                 :      481822 : simplify_using_ranges::op_with_boolean_value_range_p (tree op, gimple *s)
      59                 :             : {
      60                 :      481822 :   if (TYPE_PRECISION (TREE_TYPE (op)) == 1)
      61                 :             :     return true;
      62                 :             : 
      63                 :      469340 :   if (integer_zerop (op)
      64                 :      469340 :       || integer_onep (op))
      65                 :       10162 :     return true;
      66                 :             : 
      67                 :      459178 :   if (TREE_CODE (op) != SSA_NAME)
      68                 :             :     return false;
      69                 :             : 
      70                 :             :   /* ?? Errr, this should probably check for [0,0] and [1,1] as well
      71                 :             :      as [0,1].  */
      72                 :      459178 :   int_range_max vr;
      73                 :      459178 :   return (query->range_of_expr (vr, op, s)
      74                 :      459178 :           && vr == range_true_and_false (TREE_TYPE (op)));
      75                 :      459178 : }
      76                 :             : 
      77                 :             : /* Helper function for simplify_internal_call_using_ranges and
      78                 :             :    extract_range_basic.  Return true if OP0 SUBCODE OP1 for
      79                 :             :    SUBCODE {PLUS,MINUS,MULT}_EXPR is known to never overflow or
      80                 :             :    always overflow.  Set *OVF to true if it is known to always
      81                 :             :    overflow.  */
      82                 :             : 
      83                 :             : static bool
      84                 :      144633 : check_for_binary_op_overflow (range_query *query,
      85                 :             :                               enum tree_code subcode, tree type,
      86                 :             :                               tree op0, tree op1, bool *ovf, gimple *s = NULL)
      87                 :             : {
      88                 :      144633 :   relation_kind rel = VREL_VARYING;
      89                 :             :   /* For subtraction see if relations could simplify it.  */
      90                 :      144633 :   if (s
      91                 :      144633 :       && subcode == MINUS_EXPR
      92                 :      144633 :       && types_compatible_p (TREE_TYPE (op0), TREE_TYPE (op1)))
      93                 :             :     {
      94                 :       28859 :       rel = query->relation().query (s, op0, op1);
      95                 :             :       /* The result of the infinite precision subtraction of
      96                 :             :          the same values will be always 0.  That will fit into any result
      97                 :             :          type.  */
      98                 :       28859 :       if (rel == VREL_EQ)
      99                 :             :         return true;
     100                 :             :     }
     101                 :             : 
     102                 :      144632 :   int_range_max vr0, vr1;
     103                 :      144632 :   if (!query->range_of_expr (vr0, op0, s) || vr0.undefined_p ())
     104                 :          12 :     vr0.set_varying (TREE_TYPE (op0));
     105                 :      144632 :   if (!query->range_of_expr (vr1, op1, s) || vr1.undefined_p ())
     106                 :           4 :     vr1.set_varying (TREE_TYPE (op1));
     107                 :             : 
     108                 :      144632 :   tree vr0min = wide_int_to_tree (TREE_TYPE (op0), vr0.lower_bound ());
     109                 :      144632 :   tree vr0max = wide_int_to_tree (TREE_TYPE (op0), vr0.upper_bound ());
     110                 :      144632 :   tree vr1min = wide_int_to_tree (TREE_TYPE (op1), vr1.lower_bound ());
     111                 :      144632 :   tree vr1max = wide_int_to_tree (TREE_TYPE (op1), vr1.upper_bound ());
     112                 :             : 
     113                 :             :   /* If op1 is not negative, op0 - op1 in infinite precision for op0 >= op1
     114                 :             :      will be always in [0, op0] and so if vr0max - vr1min fits into type,
     115                 :             :      there won't be any overflow.  */
     116                 :      144632 :   if ((rel == VREL_GT || rel == VREL_GE)
     117                 :          20 :       && tree_int_cst_sgn (vr1min) >= 0
     118                 :      144649 :       && !arith_overflowed_p (MINUS_EXPR, type, vr0max, vr1min))
     119                 :             :     return true;
     120                 :             : 
     121                 :             :   /* If op1 is not negative, op0 - op1 in infinite precision for op0 < op1
     122                 :             :      will be always in [-inf, -1] and so will always overflow if type is
     123                 :             :      unsigned.  */
     124                 :      144615 :   if (rel == VREL_LT
     125                 :           1 :       && tree_int_cst_sgn (vr1min) >= 0
     126                 :      144616 :       && TYPE_UNSIGNED (type))
     127                 :             :     {
     128                 :           1 :       *ovf = true;
     129                 :           1 :       return true;
     130                 :             :     }
     131                 :             : 
     132                 :      237587 :   *ovf = arith_overflowed_p (subcode, type, vr0min,
     133                 :             :                              subcode == MINUS_EXPR ? vr1max : vr1min);
     134                 :      237587 :   if (arith_overflowed_p (subcode, type, vr0max,
     135                 :      144614 :                           subcode == MINUS_EXPR ? vr1min : vr1max) != *ovf)
     136                 :             :     return false;
     137                 :       39273 :   if (subcode == MULT_EXPR)
     138                 :             :     {
     139                 :       23871 :       if (arith_overflowed_p (subcode, type, vr0min, vr1max) != *ovf
     140                 :       23871 :           || arith_overflowed_p (subcode, type, vr0max, vr1min) != *ovf)
     141                 :         376 :         return false;
     142                 :             :     }
     143                 :       38897 :   if (*ovf)
     144                 :             :     {
     145                 :             :       /* So far we found that there is an overflow on the boundaries.
     146                 :             :          That doesn't prove that there is an overflow even for all values
     147                 :             :          in between the boundaries.  For that compute widest2_int range
     148                 :             :          of the result and see if it doesn't overlap the range of
     149                 :             :          type.  */
     150                 :       36939 :       widest2_int wmin, wmax;
     151                 :      332489 :       widest2_int w[4];
     152                 :       36939 :       int i;
     153                 :       36939 :       signop sign0 = TYPE_SIGN (TREE_TYPE (op0));
     154                 :       36939 :       signop sign1 = TYPE_SIGN (TREE_TYPE (op1));
     155                 :       36953 :       w[0] = widest2_int::from (vr0.lower_bound (), sign0);
     156                 :       36953 :       w[1] = widest2_int::from (vr0.upper_bound (), sign0);
     157                 :       36944 :       w[2] = widest2_int::from (vr1.lower_bound (), sign1);
     158                 :       36944 :       w[3] = widest2_int::from (vr1.upper_bound (), sign1);
     159                 :      184695 :       for (i = 0; i < 4; i++)
     160                 :             :         {
     161                 :      147756 :           widest2_int wt;
     162                 :      147756 :           switch (subcode)
     163                 :             :             {
     164                 :       26760 :             case PLUS_EXPR:
     165                 :       26760 :               wt = wi::add (w[i & 1], w[2 + (i & 2) / 2]);
     166                 :       26760 :               break;
     167                 :       27624 :             case MINUS_EXPR:
     168                 :       27624 :               wt = wi::sub (w[i & 1], w[2 + (i & 2) / 2]);
     169                 :       27624 :               break;
     170                 :       93372 :             case MULT_EXPR:
     171                 :       93372 :               wt = wi::mul (w[i & 1], w[2 + (i & 2) / 2]);
     172                 :       93372 :               break;
     173                 :           0 :             default:
     174                 :           0 :               gcc_unreachable ();
     175                 :             :             }
     176                 :      147756 :           if (i == 0)
     177                 :             :             {
     178                 :       36939 :               wmin = wt;
     179                 :       36939 :               wmax = wt;
     180                 :             :             }
     181                 :             :           else
     182                 :             :             {
     183                 :      110817 :               wmin = wi::smin (wmin, wt);
     184                 :      111473 :               wmax = wi::smax (wmax, wt);
     185                 :             :             }
     186                 :      147756 :         }
     187                 :             :       /* The result of op0 CODE op1 is known to be in range
     188                 :             :          [wmin, wmax].  */
     189                 :       36939 :       widest2_int wtmin
     190                 :       73878 :         = widest2_int::from (irange_val_min (type), TYPE_SIGN (type));
     191                 :       36939 :       widest2_int wtmax
     192                 :       73878 :         = widest2_int::from (irange_val_max (type), TYPE_SIGN (type));
     193                 :             :       /* If all values in [wmin, wmax] are smaller than
     194                 :             :          [wtmin, wtmax] or all are larger than [wtmin, wtmax],
     195                 :             :          the arithmetic operation will always overflow.  */
     196                 :       72868 :       if (wmax < wtmin || wmin > wtmax)
     197                 :        1652 :         return true;
     198                 :             :       return false;
     199                 :      221844 :     }
     200                 :             :   return true;
     201                 :      144632 : }
     202                 :             : 
     203                 :             : /* Set INIT, STEP, and DIRECTION to the corresponding values of NAME
     204                 :             :    within LOOP, and return TRUE.  Otherwise return FALSE, and set R to
     205                 :             :    the conservative range of NAME within the loop.  */
     206                 :             : 
     207                 :             : static bool
     208                 :     6343649 : get_scev_info (vrange &r, tree name, gimple *stmt, class loop *l,
     209                 :             :                tree &init, tree &step, enum ev_direction &dir)
     210                 :             : {
     211                 :     6343649 :   tree ev = analyze_scalar_evolution (l, name);
     212                 :     6343649 :   tree chrec = instantiate_parameters (l, ev);
     213                 :     6343649 :   tree type = TREE_TYPE (name);
     214                 :     6343649 :   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
     215                 :             :     {
     216                 :     3136982 :       r.set_varying (type);
     217                 :     3136982 :       return false;
     218                 :             :     }
     219                 :     3206667 :   if (is_gimple_min_invariant (chrec))
     220                 :             :     {
     221                 :           0 :       if (is_gimple_constant (chrec))
     222                 :           0 :         r.set (chrec, chrec);
     223                 :             :       else
     224                 :           0 :         r.set_varying (type);
     225                 :           0 :       return false;
     226                 :             :     }
     227                 :             : 
     228                 :     3206667 :   init = initial_condition_in_loop_num (chrec, l->num);
     229                 :     3206667 :   step = evolution_part_in_loop_num (chrec, l->num);
     230                 :     3206667 :   if (!init || !step)
     231                 :             :     {
     232                 :           0 :       r.set_varying (type);
     233                 :           0 :       return false;
     234                 :             :     }
     235                 :     3206667 :   dir = scev_direction (chrec);
     236                 :     3206667 :   if (dir == EV_DIR_UNKNOWN
     237                 :     3206667 :       || scev_probably_wraps_p (NULL, init, step, stmt,
     238                 :             :                                 get_chrec_loop (chrec), true))
     239                 :             :     {
     240                 :      780412 :       r.set_varying (type);
     241                 :      780412 :       return false;
     242                 :             :     }
     243                 :             :   return true;
     244                 :             : }
     245                 :             : 
     246                 :             : /* Return TRUE if STEP * NIT may overflow when calculated in TYPE.  */
     247                 :             : 
     248                 :             : static bool
     249                 :     2070711 : induction_variable_may_overflow_p (tree type,
     250                 :             :                                    const wide_int &step, const widest_int &nit)
     251                 :             : {
     252                 :     2070711 :   wi::overflow_type ovf;
     253                 :     2070711 :   signop sign = TYPE_SIGN (type);
     254                 :     2070711 :   widest_int max_step = wi::mul (widest_int::from (step, sign),
     255                 :     2070711 :                                  nit, sign, &ovf);
     256                 :             : 
     257                 :     2070711 :   if (ovf || !wi::fits_to_tree_p (max_step, type))
     258                 :       23271 :     return true;
     259                 :             : 
     260                 :             :   /* For a signed type we have to check whether the result has the
     261                 :             :      expected signedness which is that of the step as number of
     262                 :             :      iterations is unsigned.  */
     263                 :     2047440 :   return (sign == SIGNED
     264                 :     4094539 :           && wi::gts_p (max_step, 0) != wi::gts_p (step, 0));
     265                 :     2070711 : }
     266                 :             : 
     267                 :             : /* Set R to the range from BEGIN to END, assuming the direction of the
     268                 :             :    loop is DIR.  */
     269                 :             : 
     270                 :             : static void
     271                 :     2425849 : range_from_loop_direction (irange &r, tree type,
     272                 :             :                            const irange &begin, const irange &end,
     273                 :             :                            ev_direction dir)
     274                 :             : {
     275                 :     2425849 :   signop sign = TYPE_SIGN (type);
     276                 :             : 
     277                 :     2425849 :   if (begin.undefined_p () || end.undefined_p ())
     278                 :        8291 :     r.set_varying (type);
     279                 :     2417558 :   else if (dir == EV_DIR_GROWS)
     280                 :             :     {
     281                 :     2255214 :       if (wi::gt_p (begin.lower_bound (), end.upper_bound (), sign))
     282                 :         555 :         r.set_varying (type);
     283                 :             :       else
     284                 :     2254659 :         r = int_range<1> (type, begin.lower_bound (), end.upper_bound ());
     285                 :             :     }
     286                 :             :   else
     287                 :             :     {
     288                 :      162352 :       if (wi::gt_p (end.lower_bound (), begin.upper_bound (), sign))
     289                 :          86 :         r.set_varying (type);
     290                 :             :       else
     291                 :      162266 :         r = int_range<1> (type, end.lower_bound (), begin.upper_bound ());
     292                 :             :     }
     293                 :     2425849 : }
     294                 :             : 
     295                 :             : /* Set V to the range of NAME in STMT within LOOP.  Return TRUE if a
     296                 :             :    range was found.  */
     297                 :             : 
     298                 :             : bool
     299                 :     6343649 : range_of_var_in_loop (vrange &v, tree name, class loop *l, gimple *stmt,
     300                 :             :                       range_query *query)
     301                 :             : {
     302                 :     6343649 :   tree init, step;
     303                 :     6343649 :   enum ev_direction dir;
     304                 :     6343649 :   if (!get_scev_info (v, name, stmt, l, init, step, dir))
     305                 :             :     return true;
     306                 :             : 
     307                 :             :   // Calculate ranges for the values from SCEV.
     308                 :     2426255 :   irange &r = as_a <irange> (v);
     309                 :     2426255 :   tree type = TREE_TYPE (init);
     310                 :     2426255 :   int_range<2> rinit (type), rstep (type), max_init (type);
     311                 :     2426255 :   if (!query->range_of_expr (rinit, init, stmt)
     312                 :     2426255 :       || !query->range_of_expr (rstep, step, stmt))
     313                 :           0 :     return false;
     314                 :             : 
     315                 :             :   // Calculate the final range of NAME if possible.
     316                 :     2426255 :   if (rinit.singleton_p () && rstep.singleton_p ())
     317                 :             :     {
     318                 :     2071117 :       widest_int nit;
     319                 :     2071117 :       if (!max_loop_iterations (l, &nit))
     320                 :             :         return false;
     321                 :             : 
     322                 :     2070711 :       if (!induction_variable_may_overflow_p (type, rstep.lower_bound (), nit))
     323                 :             :         {
     324                 :             :           // Calculate the max bounds for init (init + niter * step).
     325                 :     2047099 :           wide_int w = wide_int::from (nit, TYPE_PRECISION (type), TYPE_SIGN (type));
     326                 :     2047099 :           int_range<1> niter (type, w, w);
     327                 :     2047099 :           int_range_max max_step;
     328                 :     2047099 :           range_op_handler mult_handler (MULT_EXPR);
     329                 :     2047099 :           range_op_handler plus_handler (PLUS_EXPR);
     330                 :     2047099 :           if (!mult_handler.fold_range (max_step, type, niter, rstep)
     331                 :     2047099 :               || !plus_handler.fold_range (max_init, type, rinit, max_step))
     332                 :           0 :             return false;
     333                 :     2047099 :         }
     334                 :     2071117 :     }
     335                 :     2425849 :   range_from_loop_direction (r, type, rinit, max_init, dir);
     336                 :     2425849 :   return true;
     337                 :     2426255 : }
     338                 :             : 
     339                 :             : /* Helper function for vrp_evaluate_conditional_warnv & other
     340                 :             :    optimizers.  */
     341                 :             : 
     342                 :             : tree
     343                 :    20136430 : simplify_using_ranges::fold_cond_with_ops (enum tree_code code,
     344                 :             :                                            tree op0, tree op1, gimple *s)
     345                 :             : {
     346                 :    20136430 :   value_range r0 (TREE_TYPE (op0));
     347                 :    20136430 :   value_range r1 (TREE_TYPE (op1));
     348                 :    20136430 :   if (!query->range_of_expr (r0, op0, s)
     349                 :    20136430 :       || !query->range_of_expr (r1, op1, s))
     350                 :        5938 :     return NULL_TREE;
     351                 :             : 
     352                 :    20130492 :   int_range<1> res;
     353                 :    20130492 :   range_op_handler handler (code);
     354                 :             : 
     355                 :             :   // Find any relation between op0 and op1 and pass it to fold_range.
     356                 :    20130492 :   relation_kind rel = VREL_VARYING;
     357                 :    20130492 :   if (gimple_range_ssa_p (op0) && gimple_range_ssa_p (op1))
     358                 :     4432766 :     rel = query->relation ().query (s, op0, op1);
     359                 :             : 
     360                 :    20130492 :   if (handler && handler.fold_range (res, boolean_type_node, r0, r1,
     361                 :             :                                      relation_trio::op1_op2 (rel)))
     362                 :             :     {
     363                 :    20130492 :       if (res == range_true ())
     364                 :       10172 :         return boolean_true_node;
     365                 :    20120320 :       if (res == range_false ())
     366                 :        4337 :         return boolean_false_node;
     367                 :             :     }
     368                 :             :   return NULL;
     369                 :    20136430 : }
     370                 :             : 
     371                 :             : /* Helper function for legacy_fold_cond.  */
     372                 :             : 
     373                 :             : tree
     374                 :    20561058 : simplify_using_ranges::legacy_fold_cond_overflow (gimple *stmt)
     375                 :             : {
     376                 :    20561058 :   tree ret;
     377                 :    20561058 :   tree_code code = gimple_cond_code (stmt);
     378                 :    20561058 :   tree op0 = gimple_cond_lhs (stmt);
     379                 :    20561058 :   tree op1 = gimple_cond_rhs (stmt);
     380                 :             : 
     381                 :             :   /* We only deal with integral and pointer types.  */
     382                 :    40731662 :   if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
     383                 :    25014794 :       && !POINTER_TYPE_P (TREE_TYPE (op0)))
     384                 :             :     return NULL_TREE;
     385                 :             : 
     386                 :             :   /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed
     387                 :             :      as a simple equality test, then prefer that over its current form
     388                 :             :      for evaluation.
     389                 :             : 
     390                 :             :      An overflow test which collapses to an equality test can always be
     391                 :             :      expressed as a comparison of one argument against zero.  Overflow
     392                 :             :      occurs when the chosen argument is zero and does not occur if the
     393                 :             :      chosen argument is not zero.  */
     394                 :    19731650 :   tree x;
     395                 :    19731650 :   if (overflow_comparison_p (code, op0, op1, &x))
     396                 :             :     {
     397                 :        1345 :       wide_int max = wi::max_value (TYPE_PRECISION (TREE_TYPE (op0)), UNSIGNED);
     398                 :             :       /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0)
     399                 :             :          B = A - 1; if (A > B) -> B = A - 1; if (A != 0)
     400                 :             :          B = A + 1; if (B < A) -> B = A + 1; if (B == 0)
     401                 :             :          B = A + 1; if (B > A) -> B = A + 1; if (B != 0) */
     402                 :        1345 :       if (integer_zerop (x))
     403                 :             :         {
     404                 :         162 :           op1 = x;
     405                 :         162 :           code = (code == LT_EXPR || code == LE_EXPR) ? EQ_EXPR : NE_EXPR;
     406                 :             :         }
     407                 :             :       /* B = A + 1; if (A > B) -> B = A + 1; if (B == 0)
     408                 :             :          B = A + 1; if (A < B) -> B = A + 1; if (B != 0)
     409                 :             :          B = A - 1; if (B > A) -> B = A - 1; if (A == 0)
     410                 :             :          B = A - 1; if (B < A) -> B = A - 1; if (A != 0) */
     411                 :        1183 :       else if (wi::to_wide (x) == max - 1)
     412                 :             :         {
     413                 :         847 :           op0 = op1;
     414                 :         847 :           op1 = wide_int_to_tree (TREE_TYPE (op0), 0);
     415                 :         847 :           code = (code == GT_EXPR || code == GE_EXPR) ? EQ_EXPR : NE_EXPR;
     416                 :             :         }
     417                 :             :       else
     418                 :             :         {
     419                 :         336 :           int_range_max vro, vri;
     420                 :         336 :           tree type = TREE_TYPE (op0);
     421                 :         336 :           if (code == GT_EXPR || code == GE_EXPR)
     422                 :             :             {
     423                 :         118 :               vro.set (type,
     424                 :         236 :                        wi::to_wide (TYPE_MIN_VALUE (type)),
     425                 :         118 :                        wi::to_wide (x), VR_ANTI_RANGE);
     426                 :         118 :               vri.set (type,
     427                 :         236 :                        wi::to_wide (TYPE_MIN_VALUE (type)),
     428                 :         236 :                        wi::to_wide (x));
     429                 :             :             }
     430                 :         218 :           else if (code == LT_EXPR || code == LE_EXPR)
     431                 :             :             {
     432                 :         218 :               vro.set (type,
     433                 :         436 :                        wi::to_wide (TYPE_MIN_VALUE (type)),
     434                 :         218 :                        wi::to_wide (x));
     435                 :         218 :               vri.set (type,
     436                 :         436 :                        wi::to_wide (TYPE_MIN_VALUE (type)),
     437                 :         436 :                        wi::to_wide (x),
     438                 :             :                        VR_ANTI_RANGE);
     439                 :             :             }
     440                 :             :           else
     441                 :           0 :             gcc_unreachable ();
     442                 :         336 :           int_range_max vr0;
     443                 :         336 :           if (!query->range_of_expr (vr0, op0, stmt))
     444                 :           0 :             vr0.set_varying (TREE_TYPE (op0));
     445                 :             :           /* If vro, the range for OP0 to pass the overflow test, has
     446                 :             :              no intersection with *vr0, OP0's known range, then the
     447                 :             :              overflow test can't pass, so return the node for false.
     448                 :             :              If it is the inverted range, vri, that has no
     449                 :             :              intersection, then the overflow test must pass, so return
     450                 :             :              the node for true.  In other cases, we could proceed with
     451                 :             :              a simplified condition comparing OP0 and X, with LE_EXPR
     452                 :             :              for previously LE_ or LT_EXPR and GT_EXPR otherwise, but
     453                 :             :              the comments next to the enclosing if suggest it's not
     454                 :             :              generally profitable to do so.  */
     455                 :         336 :           vro.intersect (vr0);
     456                 :         336 :           if (vro.undefined_p ())
     457                 :           8 :             return boolean_false_node;
     458                 :         328 :           vri.intersect (vr0);
     459                 :         328 :           if (vri.undefined_p ())
     460                 :           0 :             return boolean_true_node;
     461                 :         336 :         }
     462                 :        1345 :     }
     463                 :             : 
     464                 :    19731642 :   if ((ret = fold_cond_with_ops (code, op0, op1, stmt)))
     465                 :             :     return ret;
     466                 :             :   return NULL_TREE;
     467                 :             : }
     468                 :             : 
     469                 :             : /* Visit conditional statement STMT.  If we can determine which edge
     470                 :             :    will be taken out of STMT's basic block, record it in
     471                 :             :    *TAKEN_EDGE_P.  Otherwise, set *TAKEN_EDGE_P to NULL.  */
     472                 :             : 
     473                 :             : void
     474                 :    20561058 : simplify_using_ranges::legacy_fold_cond (gcond *stmt, edge *taken_edge_p)
     475                 :             : {
     476                 :    20561058 :   tree val;
     477                 :             : 
     478                 :    20561058 :   *taken_edge_p = NULL;
     479                 :             : 
     480                 :    20561058 :   if (dump_file && (dump_flags & TDF_DETAILS))
     481                 :             :     {
     482                 :         377 :       tree use;
     483                 :         377 :       ssa_op_iter i;
     484                 :             : 
     485                 :         377 :       fprintf (dump_file, "\nVisiting conditional with predicate: ");
     486                 :         377 :       print_gimple_stmt (dump_file, stmt, 0);
     487                 :         377 :       fprintf (dump_file, "\nWith known ranges\n");
     488                 :             : 
     489                 :         844 :       FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
     490                 :             :         {
     491                 :         467 :           fprintf (dump_file, "\t");
     492                 :         467 :           print_generic_expr (dump_file, use);
     493                 :         467 :           fprintf (dump_file, ": ");
     494                 :         467 :           value_range r (TREE_TYPE (use));
     495                 :         467 :           query->range_of_expr (r, use, stmt);
     496                 :         467 :           r.dump (dump_file);
     497                 :         467 :         }
     498                 :             : 
     499                 :         377 :       fprintf (dump_file, "\n");
     500                 :             :     }
     501                 :             : 
     502                 :    20561058 :   val = legacy_fold_cond_overflow (stmt);
     503                 :    20561058 :   if (val)
     504                 :           8 :     *taken_edge_p = find_taken_edge (gimple_bb (stmt), val);
     505                 :             : 
     506                 :    20561058 :   if (dump_file && (dump_flags & TDF_DETAILS))
     507                 :             :     {
     508                 :         377 :       fprintf (dump_file, "\nPredicate evaluates to: ");
     509                 :         377 :       if (val == NULL_TREE)
     510                 :         377 :         fprintf (dump_file, "DON'T KNOW\n");
     511                 :             :       else
     512                 :           0 :         print_generic_stmt (dump_file, val);
     513                 :             :     }
     514                 :    20561058 : }
     515                 :             : 
     516                 :             : /* Simplify boolean operations if the source is known
     517                 :             :    to be already a boolean.  */
     518                 :             : bool
     519                 :      464955 : simplify_using_ranges::simplify_truth_ops_using_ranges
     520                 :             :                                         (gimple_stmt_iterator *gsi,
     521                 :             :                                          gimple *stmt)
     522                 :             : {
     523                 :      464955 :   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
     524                 :      464955 :   tree lhs, op0, op1;
     525                 :      464955 :   bool need_conversion;
     526                 :             : 
     527                 :             :   /* We handle only !=/== case here.  */
     528                 :      464955 :   gcc_assert (rhs_code == EQ_EXPR || rhs_code == NE_EXPR);
     529                 :             : 
     530                 :      464955 :   op0 = gimple_assign_rhs1 (stmt);
     531                 :      464955 :   if (!op_with_boolean_value_range_p (op0, stmt))
     532                 :             :     return false;
     533                 :             : 
     534                 :       16867 :   op1 = gimple_assign_rhs2 (stmt);
     535                 :       16867 :   if (!op_with_boolean_value_range_p (op1, stmt))
     536                 :             :     return false;
     537                 :             : 
     538                 :             :   /* Reduce number of cases to handle to NE_EXPR.  As there is no
     539                 :             :      BIT_XNOR_EXPR we cannot replace A == B with a single statement.  */
     540                 :       16468 :   if (rhs_code == EQ_EXPR)
     541                 :             :     {
     542                 :        7557 :       if (TREE_CODE (op1) == INTEGER_CST)
     543                 :        3205 :         op1 = int_const_binop (BIT_XOR_EXPR, op1,
     544                 :        6410 :                                build_int_cst (TREE_TYPE (op1), 1));
     545                 :             :       else
     546                 :             :         return false;
     547                 :             :     }
     548                 :             : 
     549                 :       12116 :   lhs = gimple_assign_lhs (stmt);
     550                 :       12116 :   need_conversion
     551                 :       12116 :     = !useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (op0));
     552                 :             : 
     553                 :             :   /* Make sure to not sign-extend a 1-bit 1 when converting the result.  */
     554                 :       12116 :   if (need_conversion
     555                 :       10633 :       && !TYPE_UNSIGNED (TREE_TYPE (op0))
     556                 :        4561 :       && TYPE_PRECISION (TREE_TYPE (op0)) == 1
     557                 :       12139 :       && TYPE_PRECISION (TREE_TYPE (lhs)) > 1)
     558                 :             :     return false;
     559                 :             : 
     560                 :             :   /* For A != 0 we can substitute A itself.  */
     561                 :       12116 :   if (integer_zerop (op1))
     562                 :        7702 :     gimple_assign_set_rhs_with_ops (gsi,
     563                 :             :                                     need_conversion
     564                 :           0 :                                     ? NOP_EXPR : TREE_CODE (op0), op0);
     565                 :             :   /* For A != B we substitute A ^ B.  Either with conversion.  */
     566                 :        4414 :   else if (need_conversion)
     567                 :             :     {
     568                 :        2931 :       tree tem = make_ssa_name (TREE_TYPE (op0));
     569                 :        2931 :       gassign *newop
     570                 :        2931 :         = gimple_build_assign (tem, BIT_XOR_EXPR, op0, op1);
     571                 :        2931 :       gsi_insert_before (gsi, newop, GSI_SAME_STMT);
     572                 :        5839 :       if (INTEGRAL_TYPE_P (TREE_TYPE (tem))
     573                 :        5839 :           && TYPE_PRECISION (TREE_TYPE (tem)) > 1)
     574                 :             :         {
     575                 :        5680 :           int_range<1> vr (TREE_TYPE (tem),
     576                 :        5680 :                            wi::zero (TYPE_PRECISION (TREE_TYPE (tem))),
     577                 :        5680 :                            wi::one (TYPE_PRECISION (TREE_TYPE (tem))));
     578                 :        2840 :           set_range_info (tem, vr);
     579                 :        2840 :         }
     580                 :        2931 :       gimple_assign_set_rhs_with_ops (gsi, NOP_EXPR, tem);
     581                 :             :     }
     582                 :             :   /* Or without.  */
     583                 :             :   else
     584                 :        1483 :     gimple_assign_set_rhs_with_ops (gsi, BIT_XOR_EXPR, op0, op1);
     585                 :       12116 :   update_stmt (gsi_stmt (*gsi));
     586                 :       12116 :   fold_stmt (gsi, follow_single_use_edges);
     587                 :             : 
     588                 :       12116 :   return true;
     589                 :             : }
     590                 :             : 
     591                 :             : /* Simplify a division or modulo operator to a right shift or bitwise and
     592                 :             :    if the first operand is unsigned or is greater than zero and the second
     593                 :             :    operand is an exact power of two.  For TRUNC_MOD_EXPR op0 % op1 with
     594                 :             :    constant op1 (op1min = op1) or with op1 in [op1min, op1max] range,
     595                 :             :    optimize it into just op0 if op0's range is known to be a subset of
     596                 :             :    [-op1min + 1, op1min - 1] for signed and [0, op1min - 1] for unsigned
     597                 :             :    modulo.  */
     598                 :             : 
     599                 :             : bool
     600                 :      322862 : simplify_using_ranges::simplify_div_or_mod_using_ranges
     601                 :             :                                         (gimple_stmt_iterator *gsi,
     602                 :             :                                          gimple *stmt)
     603                 :             : {
     604                 :      322862 :   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
     605                 :      322862 :   tree val = NULL;
     606                 :      322862 :   tree op0 = gimple_assign_rhs1 (stmt);
     607                 :      322862 :   tree op1 = gimple_assign_rhs2 (stmt);
     608                 :      322862 :   tree op0min = NULL_TREE, op0max = NULL_TREE;
     609                 :      322862 :   tree op1min = op1;
     610                 :      322862 :   int_range_max vr;
     611                 :             : 
     612                 :      322862 :   if (TREE_CODE (op0) == INTEGER_CST)
     613                 :             :     {
     614                 :             :       op0min = op0;
     615                 :             :       op0max = op0;
     616                 :             :     }
     617                 :             :   else
     618                 :             :     {
     619                 :      298578 :       if (!query->range_of_expr (vr, op0, stmt))
     620                 :           0 :         vr.set_varying (TREE_TYPE (op0));
     621                 :      298578 :       if (!vr.varying_p () && !vr.undefined_p ())
     622                 :             :         {
     623                 :      147567 :           tree type = vr.type ();
     624                 :      147567 :           op0min = wide_int_to_tree (type, vr.lower_bound ());
     625                 :      147576 :           op0max = wide_int_to_tree (type, vr.upper_bound ());
     626                 :             :         }
     627                 :             :     }
     628                 :             : 
     629                 :      322862 :   if (rhs_code == TRUNC_MOD_EXPR
     630                 :      148384 :       && TREE_CODE (op1) == SSA_NAME)
     631                 :             :     {
     632                 :       86529 :       int_range_max vr1;
     633                 :       86529 :       if (!query->range_of_expr (vr1, op1, stmt))
     634                 :           0 :         vr1.set_varying (TREE_TYPE (op1));
     635                 :       86529 :       if (!vr1.varying_p () && !vr1.undefined_p ())
     636                 :       25187 :         op1min = wide_int_to_tree (vr1.type (), vr1.lower_bound ());
     637                 :       86529 :     }
     638                 :      148384 :   if (rhs_code == TRUNC_MOD_EXPR
     639                 :      148384 :       && TREE_CODE (op1min) == INTEGER_CST
     640                 :       87038 :       && tree_int_cst_sgn (op1min) == 1
     641                 :       66546 :       && op0max
     642                 :       39734 :       && tree_int_cst_lt (op0max, op1min))
     643                 :             :     {
     644                 :        1159 :       if (TYPE_UNSIGNED (TREE_TYPE (op0))
     645                 :         473 :           || tree_int_cst_sgn (op0min) >= 0
     646                 :        1324 :           || tree_int_cst_lt (fold_unary (NEGATE_EXPR, TREE_TYPE (op1min), op1min),
     647                 :             :                               op0min))
     648                 :             :         {
     649                 :             :           /* If op0 already has the range op0 % op1 has,
     650                 :             :              then TRUNC_MOD_EXPR won't change anything.  */
     651                 :        1125 :           gimple_assign_set_rhs_from_tree (gsi, op0);
     652                 :        1125 :           return true;
     653                 :             :         }
     654                 :             :     }
     655                 :             : 
     656                 :      321737 :   if (TREE_CODE (op0) != SSA_NAME)
     657                 :             :     return false;
     658                 :             : 
     659                 :      297460 :   if (!integer_pow2p (op1))
     660                 :             :     {
     661                 :             :       /* X % -Y can be only optimized into X % Y either if
     662                 :             :          X is not INT_MIN, or Y is not -1.  Fold it now, as after
     663                 :             :          remove_range_assertions the range info might be not available
     664                 :             :          anymore.  */
     665                 :      258644 :       if (rhs_code == TRUNC_MOD_EXPR
     666                 :      258644 :           && fold_stmt (gsi, follow_single_use_edges))
     667                 :             :         return true;
     668                 :      258644 :       return false;
     669                 :             :     }
     670                 :             : 
     671                 :       38816 :   if (TYPE_UNSIGNED (TREE_TYPE (op0)))
     672                 :           0 :     val = integer_one_node;
     673                 :             :   else
     674                 :             :     {
     675                 :       38816 :       tree zero = build_zero_cst (TREE_TYPE (op0));
     676                 :       38816 :       val = fold_cond_with_ops (GE_EXPR, op0, zero, stmt);
     677                 :             :     }
     678                 :             : 
     679                 :       38816 :   if (val && integer_onep (val))
     680                 :             :     {
     681                 :        5971 :       tree t;
     682                 :             : 
     683                 :        5971 :       if (rhs_code == TRUNC_DIV_EXPR)
     684                 :             :         {
     685                 :        3617 :           t = build_int_cst (integer_type_node, tree_log2 (op1));
     686                 :        3617 :           gimple_assign_set_rhs_code (stmt, RSHIFT_EXPR);
     687                 :        3617 :           gimple_assign_set_rhs1 (stmt, op0);
     688                 :        3617 :           gimple_assign_set_rhs2 (stmt, t);
     689                 :             :         }
     690                 :             :       else
     691                 :             :         {
     692                 :        2354 :           t = build_int_cst (TREE_TYPE (op1), 1);
     693                 :        2354 :           t = int_const_binop (MINUS_EXPR, op1, t);
     694                 :        2354 :           t = fold_convert (TREE_TYPE (op0), t);
     695                 :             : 
     696                 :        2354 :           gimple_assign_set_rhs_code (stmt, BIT_AND_EXPR);
     697                 :        2354 :           gimple_assign_set_rhs1 (stmt, op0);
     698                 :        2354 :           gimple_assign_set_rhs2 (stmt, t);
     699                 :             :         }
     700                 :             : 
     701                 :        5971 :       update_stmt (stmt);
     702                 :        5971 :       fold_stmt (gsi, follow_single_use_edges);
     703                 :        5971 :       return true;
     704                 :             :     }
     705                 :             : 
     706                 :             :   return false;
     707                 :      322862 : }
     708                 :             : 
     709                 :             : /* Simplify a min or max if the ranges of the two operands are
     710                 :             :    disjoint.   Return true if we do simplify.  */
     711                 :             : 
     712                 :             : bool
     713                 :      179980 : simplify_using_ranges::simplify_min_or_max_using_ranges
     714                 :             :                                 (gimple_stmt_iterator *gsi,
     715                 :             :                                  gimple *stmt)
     716                 :             : {
     717                 :      179980 :   tree op0 = gimple_assign_rhs1 (stmt);
     718                 :      179980 :   tree op1 = gimple_assign_rhs2 (stmt);
     719                 :      179980 :   tree val;
     720                 :             : 
     721                 :      179980 :   val = fold_cond_with_ops (LE_EXPR, op0, op1, stmt);
     722                 :      179980 :   if (!val)
     723                 :      172581 :     val = fold_cond_with_ops (LT_EXPR, op0, op1, stmt);
     724                 :             : 
     725                 :      172581 :   if (val)
     726                 :             :     {
     727                 :             :       /* VAL == TRUE -> OP0 < or <= op1
     728                 :             :          VAL == FALSE -> OP0 > or >= op1.  */
     729                 :        8079 :       tree res = ((gimple_assign_rhs_code (stmt) == MAX_EXPR)
     730                 :        8079 :                   == integer_zerop (val)) ? op0 : op1;
     731                 :        8079 :       gimple_assign_set_rhs_from_tree (gsi, res);
     732                 :        8079 :       return true;
     733                 :             :     }
     734                 :             : 
     735                 :             :   return false;
     736                 :             : }
     737                 :             : 
     738                 :             : /* If the operand to an ABS_EXPR is >= 0, then eliminate the
     739                 :             :    ABS_EXPR.  If the operand is <= 0, then simplify the
     740                 :             :    ABS_EXPR into a NEGATE_EXPR.  */
     741                 :             : 
     742                 :             : bool
     743                 :        6828 : simplify_using_ranges::simplify_abs_using_ranges (gimple_stmt_iterator *gsi,
     744                 :             :                                                   gimple *stmt)
     745                 :             : {
     746                 :        6828 :   tree op = gimple_assign_rhs1 (stmt);
     747                 :        6828 :   tree zero = build_zero_cst (TREE_TYPE (op));
     748                 :        6828 :   tree val = fold_cond_with_ops (LE_EXPR, op, zero, stmt);
     749                 :             : 
     750                 :        6828 :   if (!val)
     751                 :             :     {
     752                 :             :       /* The range is neither <= 0 nor > 0.  Now see if it is
     753                 :             :          either < 0 or >= 0.  */
     754                 :        6583 :       val = fold_cond_with_ops (LT_EXPR, op, zero, stmt);
     755                 :             :     }
     756                 :        6583 :   if (val)
     757                 :             :     {
     758                 :         458 :       gimple_assign_set_rhs1 (stmt, op);
     759                 :         458 :       if (integer_zerop (val))
     760                 :         294 :         gimple_assign_set_rhs_code (stmt, SSA_NAME);
     761                 :             :       else
     762                 :         164 :         gimple_assign_set_rhs_code (stmt, NEGATE_EXPR);
     763                 :         458 :       update_stmt (stmt);
     764                 :         458 :       fold_stmt (gsi, follow_single_use_edges);
     765                 :         458 :       return true;
     766                 :             :     }
     767                 :             :   return false;
     768                 :             : }
     769                 :             : 
     770                 :             : /* irange wrapper for wi_set_zero_nonzero_bits.
     771                 :             : 
     772                 :             :    Return TRUE if VR was a constant range and we were able to compute
     773                 :             :    the bit masks.  */
     774                 :             : 
     775                 :             : static bool
     776                 :     1683078 : vr_set_zero_nonzero_bits (const tree expr_type,
     777                 :             :                           const irange *vr,
     778                 :             :                           wide_int *may_be_nonzero,
     779                 :             :                           wide_int *must_be_nonzero)
     780                 :             : {
     781                 :     1683078 :   if (vr->varying_p () || vr->undefined_p ())
     782                 :             :     {
     783                 :      989191 :       *may_be_nonzero = wi::minus_one (TYPE_PRECISION (expr_type));
     784                 :      989191 :       *must_be_nonzero = wi::zero (TYPE_PRECISION (expr_type));
     785                 :      989191 :       return false;
     786                 :             :     }
     787                 :      693889 :   wi_set_zero_nonzero_bits (expr_type, vr->lower_bound (), vr->upper_bound (),
     788                 :             :                             *may_be_nonzero, *must_be_nonzero);
     789                 :      693887 :   return true;
     790                 :             : }
     791                 :             : 
     792                 :             : /* Optimize away redundant BIT_AND_EXPR and BIT_IOR_EXPR.
     793                 :             :    If all the bits that are being cleared by & are already
     794                 :             :    known to be zero from VR, or all the bits that are being
     795                 :             :    set by | are already known to be one from VR, the bit
     796                 :             :    operation is redundant.  */
     797                 :             : 
     798                 :             : bool
     799                 :     1317856 : simplify_using_ranges::simplify_bit_ops_using_ranges
     800                 :             :                                 (gimple_stmt_iterator *gsi,
     801                 :             :                                  gimple *stmt)
     802                 :             : {
     803                 :     1317856 :   tree op0 = gimple_assign_rhs1 (stmt);
     804                 :     1317856 :   tree op1 = gimple_assign_rhs2 (stmt);
     805                 :     1317856 :   tree op = NULL_TREE;
     806                 :     1317856 :   int_range_max vr0, vr1;
     807                 :     1317856 :   wide_int may_be_nonzero0, may_be_nonzero1;
     808                 :     1317856 :   wide_int must_be_nonzero0, must_be_nonzero1;
     809                 :     1317856 :   wide_int mask;
     810                 :             : 
     811                 :     1317856 :   if (!query->range_of_expr (vr0, op0, stmt)
     812                 :     1317856 :       || vr0.undefined_p ())
     813                 :             :     return false;
     814                 :     1317135 :   if (!query->range_of_expr (vr1, op1, stmt)
     815                 :     1317135 :       || vr1.undefined_p ())
     816                 :             :     return false;
     817                 :             : 
     818                 :     1316802 :   if (!vr_set_zero_nonzero_bits (TREE_TYPE (op0), &vr0, &may_be_nonzero0,
     819                 :             :                                  &must_be_nonzero0))
     820                 :             :     return false;
     821                 :      366276 :   if (!vr_set_zero_nonzero_bits (TREE_TYPE (op1), &vr1, &may_be_nonzero1,
     822                 :             :                                  &must_be_nonzero1))
     823                 :             :     return false;
     824                 :             : 
     825                 :      327611 :   switch (gimple_assign_rhs_code (stmt))
     826                 :             :     {
     827                 :      230557 :     case BIT_AND_EXPR:
     828                 :      230557 :       mask = wi::bit_and_not (may_be_nonzero0, must_be_nonzero1);
     829                 :      230557 :       if (mask == 0)
     830                 :             :         {
     831                 :             :           op = op0;
     832                 :             :           break;
     833                 :             :         }
     834                 :      225533 :       mask = wi::bit_and_not (may_be_nonzero1, must_be_nonzero0);
     835                 :      225533 :       if (mask == 0)
     836                 :             :         {
     837                 :             :           op = op1;
     838                 :             :           break;
     839                 :             :         }
     840                 :             :       break;
     841                 :       97054 :     case BIT_IOR_EXPR:
     842                 :       97054 :       mask = wi::bit_and_not (may_be_nonzero0, must_be_nonzero1);
     843                 :       97054 :       if (mask == 0)
     844                 :             :         {
     845                 :             :           op = op1;
     846                 :             :           break;
     847                 :             :         }
     848                 :       97053 :       mask = wi::bit_and_not (may_be_nonzero1, must_be_nonzero0);
     849                 :       97053 :       if (mask == 0)
     850                 :             :         {
     851                 :             :           op = op0;
     852                 :             :           break;
     853                 :             :         }
     854                 :             :       break;
     855                 :           0 :     default:
     856                 :           0 :       gcc_unreachable ();
     857                 :             :     }
     858                 :             : 
     859                 :        5242 :   if (op == NULL_TREE)
     860                 :      322369 :     return false;
     861                 :             : 
     862                 :        5242 :   gimple_assign_set_rhs_with_ops (gsi, TREE_CODE (op), op);
     863                 :        5242 :   update_stmt (gsi_stmt (*gsi));
     864                 :        5242 :   return true;
     865                 :     1317868 : }
     866                 :             : 
     867                 :             : /* We are comparing trees OP0 and OP1 using COND_CODE.  OP0 has
     868                 :             :    a known value range VR.
     869                 :             : 
     870                 :             :    If there is one and only one value which will satisfy the
     871                 :             :    conditional, then return that value.  Else return NULL.
     872                 :             : 
     873                 :             :    If signed overflow must be undefined for the value to satisfy
     874                 :             :    the conditional, then set *STRICT_OVERFLOW_P to true.  */
     875                 :             : 
     876                 :             : static tree
     877                 :     1485794 : test_for_singularity (enum tree_code cond_code, tree op0,
     878                 :             :                       tree op1, const irange *vr)
     879                 :             : {
     880                 :     1485794 :   tree min = NULL;
     881                 :     1485794 :   tree max = NULL;
     882                 :             : 
     883                 :             :   /* Extract minimum/maximum values which satisfy the conditional as it was
     884                 :             :      written.  */
     885                 :     1485794 :   if (cond_code == LE_EXPR || cond_code == LT_EXPR)
     886                 :             :     {
     887                 :      648090 :       min = TYPE_MIN_VALUE (TREE_TYPE (op0));
     888                 :             : 
     889                 :      648090 :       max = op1;
     890                 :      648090 :       if (cond_code == LT_EXPR)
     891                 :             :         {
     892                 :       90102 :           tree one = build_int_cst (TREE_TYPE (op0), 1);
     893                 :       90102 :           max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one);
     894                 :             :           /* Signal to compare_values_warnv this expr doesn't overflow.  */
     895                 :       90102 :           if (EXPR_P (max))
     896                 :           0 :             suppress_warning (max, OPT_Woverflow);
     897                 :             :         }
     898                 :             :     }
     899                 :      837704 :   else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
     900                 :             :     {
     901                 :      723310 :       max = TYPE_MAX_VALUE (TREE_TYPE (op0));
     902                 :             : 
     903                 :      723310 :       min = op1;
     904                 :      723310 :       if (cond_code == GT_EXPR)
     905                 :             :         {
     906                 :      634757 :           tree one = build_int_cst (TREE_TYPE (op0), 1);
     907                 :      634757 :           min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one);
     908                 :             :           /* Signal to compare_values_warnv this expr doesn't overflow.  */
     909                 :      634757 :           if (EXPR_P (min))
     910                 :           0 :             suppress_warning (min, OPT_Woverflow);
     911                 :             :         }
     912                 :             :     }
     913                 :             : 
     914                 :             :   /* Now refine the minimum and maximum values using any
     915                 :             :      value range information we have for op0.  */
     916                 :     1485794 :   if (min && max)
     917                 :             :     {
     918                 :     1371400 :       tree type = TREE_TYPE (op0);
     919                 :     1371400 :       tree tmin = wide_int_to_tree (type, vr->lower_bound ());
     920                 :     1371400 :       tree tmax = wide_int_to_tree (type, vr->upper_bound ());
     921                 :     1371400 :       if (compare_values (tmin, min) == 1)
     922                 :      410760 :         min = tmin;
     923                 :     1371400 :       if (compare_values (tmax, max) == -1)
     924                 :      519764 :         max = tmax;
     925                 :             : 
     926                 :             :       /* If the new min/max values have converged to a single value,
     927                 :             :          then there is only one value which can satisfy the condition,
     928                 :             :          return that value.  */
     929                 :     1371400 :       if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min))
     930                 :             :         return min;
     931                 :             :     }
     932                 :             :   return NULL;
     933                 :             : }
     934                 :             : 
     935                 :             : /* Return whether the value range *VR fits in an integer type specified
     936                 :             :    by PRECISION and UNSIGNED_P.  */
     937                 :             : 
     938                 :             : bool
     939                 :      237114 : range_fits_type_p (const irange *vr,
     940                 :             :                    unsigned dest_precision, signop dest_sgn)
     941                 :             : {
     942                 :      237114 :   tree src_type;
     943                 :      237114 :   unsigned src_precision;
     944                 :      237114 :   widest_int tem;
     945                 :      237114 :   signop src_sgn;
     946                 :             : 
     947                 :             :   /* Now we can only handle ranges with constant bounds.  */
     948                 :      237114 :   if (vr->undefined_p () || vr->varying_p ())
     949                 :             :     return false;
     950                 :             : 
     951                 :             :   /* We can only handle integral and pointer types.  */
     952                 :      187229 :   src_type = vr->type ();
     953                 :      187229 :   if (!INTEGRAL_TYPE_P (src_type)
     954                 :           0 :       && !POINTER_TYPE_P (src_type))
     955                 :             :     return false;
     956                 :             : 
     957                 :             :   /* An extension is fine unless VR is SIGNED and dest_sgn is UNSIGNED,
     958                 :             :      and so is an identity transform.  */
     959                 :      187229 :   src_precision = TYPE_PRECISION (src_type);
     960                 :      187229 :   src_sgn = TYPE_SIGN (src_type);
     961                 :      187229 :   if ((src_precision < dest_precision
     962                 :        7460 :        && !(dest_sgn == UNSIGNED && src_sgn == SIGNED))
     963                 :      180869 :       || (src_precision == dest_precision && src_sgn == dest_sgn))
     964                 :             :     return true;
     965                 :             : 
     966                 :      180768 :   wide_int vrmin = vr->lower_bound ();
     967                 :      180768 :   wide_int vrmax = vr->upper_bound ();
     968                 :             : 
     969                 :             :   /* For sign changes, the MSB of the wide_int has to be clear.
     970                 :             :      An unsigned value with its MSB set cannot be represented by
     971                 :             :      a signed wide_int, while a negative value cannot be represented
     972                 :             :      by an unsigned wide_int.  */
     973                 :      180768 :   if (src_sgn != dest_sgn
     974                 :      180768 :       && (wi::lts_p (vrmin, 0) || wi::lts_p (vrmax, 0)))
     975                 :       54826 :     return false;
     976                 :             : 
     977                 :             :   /* Then we can perform the conversion on both ends and compare
     978                 :             :      the result for equality.  */
     979                 :      125942 :   signop sign = TYPE_SIGN (vr->type ());
     980                 :      125942 :   tem = wi::ext (widest_int::from (vrmin, sign), dest_precision, dest_sgn);
     981                 :      125942 :   if (tem != widest_int::from (vrmin, sign))
     982                 :             :     return false;
     983                 :      119262 :   tem = wi::ext (widest_int::from (vrmax, sign), dest_precision, dest_sgn);
     984                 :      119262 :   if (tem != widest_int::from (vrmax, sign))
     985                 :             :     return false;
     986                 :             : 
     987                 :             :   return true;
     988                 :      180768 : }
     989                 :             : 
     990                 :             : // Clear edge E of EDGE_EXECUTABLE (it is unexecutable). If it wasn't
     991                 :             : // previously clear, propagate to successor blocks if appropriate.
     992                 :             : 
     993                 :             : void
     994                 :      302681 : simplify_using_ranges::set_and_propagate_unexecutable (edge e)
     995                 :             : {
     996                 :             :   // If not_executable is already set, we're done.
     997                 :             :   // This works in the absence of a flag as well.
     998                 :      302681 :   if ((e->flags & m_not_executable_flag) == m_not_executable_flag)
     999                 :      213741 :     return;
    1000                 :             : 
    1001                 :      195387 :   e->flags |= m_not_executable_flag;
    1002                 :      195387 :   m_flag_set_edges.safe_push (e);
    1003                 :             : 
    1004                 :             :   // Check if the destination block needs to propagate the property.
    1005                 :      195387 :   basic_block bb = e->dest;
    1006                 :             : 
    1007                 :             :   // If any incoming edge is executable, we are done.
    1008                 :      195387 :   edge_iterator ei;
    1009                 :      326488 :   FOR_EACH_EDGE (e, ei, bb->preds)
    1010                 :      237548 :     if ((e->flags & m_not_executable_flag) == 0)
    1011                 :             :       return;
    1012                 :             : 
    1013                 :             :   // This block is also unexecutable, propagate to all exit edges as well.
    1014                 :      156509 :   FOR_EACH_EDGE (e, ei, bb->succs)
    1015                 :       67569 :     set_and_propagate_unexecutable (e);
    1016                 :             : }
    1017                 :             : 
    1018                 :             : /* If COND can be folded entirely as TRUE or FALSE, rewrite the
    1019                 :             :    conditional as such, and return TRUE.  */
    1020                 :             : 
    1021                 :             : bool
    1022                 :    20866797 : simplify_using_ranges::fold_cond (gcond *cond)
    1023                 :             : {
    1024                 :    20866797 :   int_range_max r;
    1025                 :    20866797 :   if (query->range_of_stmt (r, cond) && r.singleton_p ())
    1026                 :             :     {
    1027                 :             :       // COND has already been folded if arguments are constant.
    1028                 :      305739 :       if (TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
    1029                 :      305739 :           && TREE_CODE (gimple_cond_rhs (cond)) != SSA_NAME)
    1030                 :             :         return false;
    1031                 :      228146 :       if (dump_file)
    1032                 :             :         {
    1033                 :         184 :           fprintf (dump_file, "Folding predicate ");
    1034                 :         184 :           print_gimple_expr (dump_file, cond, 0);
    1035                 :         184 :           fprintf (dump_file, " to ");
    1036                 :             :         }
    1037                 :      228146 :       edge e0 = EDGE_SUCC (gimple_bb (cond), 0);
    1038                 :      228146 :       edge e1 = EDGE_SUCC (gimple_bb (cond), 1);
    1039                 :      228146 :       if (r.zero_p ())
    1040                 :             :         {
    1041                 :      142957 :           if (dump_file)
    1042                 :         128 :             fprintf (dump_file, "0\n");
    1043                 :      142957 :           gimple_cond_make_false (cond);
    1044                 :      142957 :           if (e0->flags & EDGE_TRUE_VALUE)
    1045                 :      141462 :             set_and_propagate_unexecutable (e0);
    1046                 :             :           else
    1047                 :        1495 :             set_and_propagate_unexecutable (e1);
    1048                 :             :         }
    1049                 :             :       else
    1050                 :             :         {
    1051                 :       85189 :           if (dump_file)
    1052                 :          56 :             fprintf (dump_file, "1\n");
    1053                 :       85189 :           gimple_cond_make_true (cond);
    1054                 :       85189 :           if (e0->flags & EDGE_FALSE_VALUE)
    1055                 :         817 :             set_and_propagate_unexecutable (e0);
    1056                 :             :           else
    1057                 :       84372 :             set_and_propagate_unexecutable (e1);
    1058                 :             :         }
    1059                 :      228146 :       update_stmt (cond);
    1060                 :      228146 :       return true;
    1061                 :             :     }
    1062                 :             : 
    1063                 :             :   // FIXME: Audit the code below and make sure it never finds anything.
    1064                 :    20561058 :   edge taken_edge;
    1065                 :    20561058 :   legacy_fold_cond (cond, &taken_edge);
    1066                 :             : 
    1067                 :    20561058 :   if (taken_edge)
    1068                 :             :     {
    1069                 :           8 :       if (taken_edge->flags & EDGE_TRUE_VALUE)
    1070                 :             :         {
    1071                 :           0 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1072                 :           0 :             fprintf (dump_file, "\nVRP Predicate evaluates to: 1\n");
    1073                 :           0 :           gimple_cond_make_true (cond);
    1074                 :             :         }
    1075                 :           8 :       else if (taken_edge->flags & EDGE_FALSE_VALUE)
    1076                 :             :         {
    1077                 :           8 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1078                 :           0 :             fprintf (dump_file, "\nVRP Predicate evaluates to: 0\n");
    1079                 :           8 :           gimple_cond_make_false (cond);
    1080                 :             :         }
    1081                 :             :       else
    1082                 :           0 :        gcc_unreachable ();
    1083                 :           8 :       update_stmt (cond);
    1084                 :           8 :       return true;
    1085                 :             :     }
    1086                 :             :   return false;
    1087                 :    20866797 : }
    1088                 :             : 
    1089                 :             : /* Simplify a conditional using a relational operator to an equality
    1090                 :             :    test if the range information indicates only one value can satisfy
    1091                 :             :    the original conditional.  */
    1092                 :             : 
    1093                 :             : bool
    1094                 :    11994600 : simplify_using_ranges::simplify_cond_using_ranges_1 (gcond *stmt)
    1095                 :             : {
    1096                 :    11994600 :   tree op0 = gimple_cond_lhs (stmt);
    1097                 :    11994600 :   tree op1 = gimple_cond_rhs (stmt);
    1098                 :    11994600 :   enum tree_code cond_code = gimple_cond_code (stmt);
    1099                 :             : 
    1100                 :    11994600 :   if (fold_cond (stmt))
    1101                 :             :     return true;
    1102                 :             : 
    1103                 :    11873335 :   if (simplify_compare_using_ranges_1 (cond_code, op0, op1, stmt))
    1104                 :             :     {
    1105                 :      338579 :       if (dump_file)
    1106                 :             :         {
    1107                 :          26 :           fprintf (dump_file, "Simplified relational ");
    1108                 :          26 :           print_gimple_stmt (dump_file, stmt, 0);
    1109                 :          26 :           fprintf (dump_file, " into ");
    1110                 :             :         }
    1111                 :             : 
    1112                 :      338579 :       gimple_cond_set_code (stmt, cond_code);
    1113                 :      338579 :       gimple_cond_set_lhs (stmt, op0);
    1114                 :      338579 :       gimple_cond_set_rhs (stmt, op1);
    1115                 :             : 
    1116                 :      338579 :       update_stmt (stmt);
    1117                 :             : 
    1118                 :      338579 :        if (dump_file)
    1119                 :             :         {
    1120                 :          26 :           print_gimple_stmt (dump_file, stmt, 0);
    1121                 :          26 :           fprintf (dump_file, "\n");
    1122                 :             :         }
    1123                 :      338579 :       return true;
    1124                 :             :     }
    1125                 :             :   return false;
    1126                 :             : }
    1127                 :             : 
    1128                 :             : /* Like simplify_cond_using_ranges_1 but for assignments rather
    1129                 :             :    than GIMPLE_COND. */
    1130                 :             : 
    1131                 :             : bool
    1132                 :     1219804 : simplify_using_ranges::simplify_compare_assign_using_ranges_1
    1133                 :             :                                         (gimple_stmt_iterator *gsi,
    1134                 :             :                                          gimple *stmt)
    1135                 :             : {
    1136                 :     1219804 :   enum tree_code code = gimple_assign_rhs_code (stmt);
    1137                 :     1219804 :   tree op0 = gimple_assign_rhs1 (stmt);
    1138                 :     1219804 :   tree op1 = gimple_assign_rhs2 (stmt);
    1139                 :     1219804 :   gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
    1140                 :     1219804 :   bool happened = false;
    1141                 :             : 
    1142                 :     1219804 :   if (simplify_compare_using_ranges_1 (code, op0, op1, stmt))
    1143                 :             :     {
    1144                 :        6754 :       if (dump_file)
    1145                 :             :         {
    1146                 :           3 :           fprintf (dump_file, "Simplified relational ");
    1147                 :           3 :           print_gimple_stmt (dump_file, stmt, 0);
    1148                 :           3 :           fprintf (dump_file, " into ");
    1149                 :             :         }
    1150                 :             : 
    1151                 :        6754 :       gimple_assign_set_rhs_code (stmt, code);
    1152                 :        6754 :       gimple_assign_set_rhs1 (stmt, op0);
    1153                 :        6754 :       gimple_assign_set_rhs2 (stmt, op1);
    1154                 :             : 
    1155                 :        6754 :       update_stmt (stmt);
    1156                 :             : 
    1157                 :        6754 :        if (dump_file)
    1158                 :             :         {
    1159                 :           3 :           print_gimple_stmt (dump_file, stmt, 0);
    1160                 :           3 :           fprintf (dump_file, "\n");
    1161                 :             :         }
    1162                 :             :       happened = true;
    1163                 :             :     }
    1164                 :             : 
    1165                 :             :   /* Transform EQ_EXPR, NE_EXPR into BIT_XOR_EXPR or identity
    1166                 :             :      if the RHS is zero or one, and the LHS are known to be boolean
    1167                 :             :      values.  */
    1168                 :     1219804 :   if ((code == EQ_EXPR || code == NE_EXPR)
    1169                 :      664951 :       && INTEGRAL_TYPE_P (TREE_TYPE (op0))
    1170                 :     1684759 :       && simplify_truth_ops_using_ranges (gsi, stmt))
    1171                 :             :     happened = true;
    1172                 :             : 
    1173                 :     1219804 :   return happened;
    1174                 :             : }
    1175                 :             : 
    1176                 :             : /* Try to simplify OP0 COND_CODE OP1 using a relational operator to an
    1177                 :             :    equality test if the range information indicates only one value can
    1178                 :             :    satisfy the original conditional.   */
    1179                 :             : 
    1180                 :             : bool
    1181                 :    13093139 : simplify_using_ranges::simplify_compare_using_ranges_1 (tree_code &cond_code, tree &op0, tree &op1, gimple *stmt)
    1182                 :             : {
    1183                 :    13093139 :   bool happened = false;
    1184                 :    13093139 :   if (cond_code != NE_EXPR
    1185                 :    13093139 :       && cond_code != EQ_EXPR
    1186                 :     3373635 :       && TREE_CODE (op0) == SSA_NAME
    1187                 :     3373198 :       && INTEGRAL_TYPE_P (TREE_TYPE (op0))
    1188                 :    16123188 :       && is_gimple_min_invariant (op1))
    1189                 :             :     {
    1190                 :     1806260 :       int_range_max vr;
    1191                 :             : 
    1192                 :     1806260 :       if (!query->range_of_expr (vr, op0, stmt))
    1193                 :           0 :         vr.set_undefined ();
    1194                 :             : 
    1195                 :             :       /* If we have range information for OP0, then we might be
    1196                 :             :          able to simplify this conditional. */
    1197                 :     1806260 :       if (!vr.undefined_p () && !vr.varying_p ())
    1198                 :             :         {
    1199                 :      742897 :           tree new_tree = test_for_singularity (cond_code, op0, op1, &vr);
    1200                 :      742897 :           if (new_tree)
    1201                 :             :             {
    1202                 :      114394 :               cond_code = EQ_EXPR;
    1203                 :      114394 :               op1 = new_tree;
    1204                 :      114394 :               happened = true;
    1205                 :             :             }
    1206                 :             : 
    1207                 :             :           /* Try again after inverting the condition.  We only deal
    1208                 :             :              with integral types here, so no need to worry about
    1209                 :             :              issues with inverting FP comparisons.  */
    1210                 :      742897 :           new_tree = test_for_singularity
    1211                 :      742897 :                        (invert_tree_comparison (cond_code, false),
    1212                 :             :                         op0, op1, &vr);
    1213                 :      742897 :           if (new_tree)
    1214                 :             :             {
    1215                 :      163034 :               cond_code = NE_EXPR;
    1216                 :      163034 :               op1 = new_tree;
    1217                 :      163034 :               happened = true;
    1218                 :             :             }
    1219                 :             :         }
    1220                 :     1806260 :     }
    1221                 :             :   // Try to simplify casted conditions.
    1222                 :    13093139 :   if (simplify_casted_compare (cond_code, op0, op1))
    1223                 :       75312 :     happened = true;
    1224                 :    13093139 :   return happened;
    1225                 :             : }
    1226                 :             : 
    1227                 :             : /* Simplify OP0 code OP1 when OP1 is a constant and OP0 was a SSA_NAME
    1228                 :             :    defined by a type conversion. Replacing OP0 with RHS of the type conversion.
    1229                 :             :    Doing so makes the conversion dead which helps subsequent passes.  */
    1230                 :             : 
    1231                 :             : bool
    1232                 :    13093139 : simplify_using_ranges::simplify_casted_compare (tree_code &, tree &op0, tree &op1)
    1233                 :             : {
    1234                 :             : 
    1235                 :             :   /* If we have a comparison of an SSA_NAME (OP0) against a constant,
    1236                 :             :      see if OP0 was set by a type conversion where the source of
    1237                 :             :      the conversion is another SSA_NAME with a range that fits
    1238                 :             :      into the range of OP0's type.
    1239                 :             : 
    1240                 :             :      If so, the conversion is redundant as the earlier SSA_NAME can be
    1241                 :             :      used for the comparison directly if we just massage the constant in the
    1242                 :             :      comparison.  */
    1243                 :    13093139 :   if (TREE_CODE (op0) == SSA_NAME
    1244                 :    13011488 :       && TREE_CODE (op1) == INTEGER_CST)
    1245                 :             :     {
    1246                 :     9173047 :       gimple *def_stmt = SSA_NAME_DEF_STMT (op0);
    1247                 :     9173047 :       tree innerop;
    1248                 :             : 
    1249                 :     9173047 :       if (!is_gimple_assign (def_stmt))
    1250                 :             :         return false;
    1251                 :             : 
    1252                 :     5646048 :       switch (gimple_assign_rhs_code (def_stmt))
    1253                 :             :         {
    1254                 :      463846 :         CASE_CONVERT:
    1255                 :      463846 :           innerop = gimple_assign_rhs1 (def_stmt);
    1256                 :      463846 :           break;
    1257                 :       48066 :         case VIEW_CONVERT_EXPR:
    1258                 :       48066 :           innerop = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), 0);
    1259                 :       48066 :           if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop)))
    1260                 :             :             return false;
    1261                 :             :           break;
    1262                 :             :         default:
    1263                 :             :           return false;
    1264                 :             :         }
    1265                 :             : 
    1266                 :      510940 :       if (TREE_CODE (innerop) == SSA_NAME
    1267                 :      510912 :           && !POINTER_TYPE_P (TREE_TYPE (innerop))
    1268                 :      505221 :           && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop)
    1269                 :     1016148 :           && desired_pro_or_demotion_p (TREE_TYPE (innerop), TREE_TYPE (op0)))
    1270                 :             :         {
    1271                 :      474549 :           int_range_max vr;
    1272                 :             : 
    1273                 :      474549 :           if (query->range_of_expr (vr, innerop)
    1274                 :      474546 :               && !vr.varying_p ()
    1275                 :      149800 :               && !vr.undefined_p ()
    1276                 :      149675 :               && range_fits_type_p (&vr,
    1277                 :      149675 :                                     TYPE_PRECISION (TREE_TYPE (op0)),
    1278                 :      149675 :                                     TYPE_SIGN (TREE_TYPE (op0)))
    1279                 :      549861 :               && int_fits_type_p (op1, TREE_TYPE (innerop)))
    1280                 :             :             {
    1281                 :       75312 :               tree newconst = fold_convert (TREE_TYPE (innerop), op1);
    1282                 :       75312 :               op0 = innerop;
    1283                 :       75312 :               op1 = newconst;
    1284                 :       75312 :               return true;
    1285                 :             :             }
    1286                 :      474549 :         }
    1287                 :             :     }
    1288                 :             :   return false;
    1289                 :             : }
    1290                 :             : 
    1291                 :             : /* Simplify a switch statement using the value range of the switch
    1292                 :             :    argument.  */
    1293                 :             : 
    1294                 :             : bool
    1295                 :       65999 : simplify_using_ranges::simplify_switch_using_ranges (gswitch *stmt)
    1296                 :             : {
    1297                 :       65999 :   tree op = gimple_switch_index (stmt);
    1298                 :       65999 :   tree type = TREE_TYPE (op);
    1299                 :       65999 :   int_range_max op_range (type);
    1300                 :       65999 :   int_range_max default_range (type);
    1301                 :       65999 :   auto_vec<unsigned> cases;
    1302                 :       65999 :   cases.truncate (0);
    1303                 :       65999 :   edge e;
    1304                 :       65999 :   switch_update su;
    1305                 :             : 
    1306                 :             :   // Abort if we don't have a useful range for the switch index.
    1307                 :       65999 :   if (!query->range_of_expr (op_range, op, stmt)
    1308                 :       65999 :       || op_range.varying_p () || op_range.undefined_p ())
    1309                 :             :     return false;
    1310                 :             : 
    1311                 :             :   // Default range starts with full known range of op.
    1312                 :       15737 :   default_range = op_range;
    1313                 :       15737 :   edge default_edge = gimple_switch_default_edge (cfun, stmt);
    1314                 :             : 
    1315                 :       15737 :   unsigned x, lim = gimple_switch_num_labels (stmt);
    1316                 :       94098 :   for (x = 1; x < lim; x++)
    1317                 :             :     {
    1318                 :       79086 :       e = gimple_switch_edge (cfun, stmt, x);
    1319                 :       79086 :       tree label = gimple_switch_label (stmt, x);
    1320                 :             : 
    1321                 :             :       // If this edge is the same as the default edge, do nothing else.
    1322                 :       79086 :       if (e == default_edge)
    1323                 :        6178 :         continue;
    1324                 :             :       // Ada sometimes has mismatched labels and index.  Just bail.
    1325                 :       79080 :       if (TREE_TYPE (CASE_LOW (label)) != type)
    1326                 :         725 :         return false;
    1327                 :             : 
    1328                 :       78355 :       wide_int low = wi::to_wide (CASE_LOW (label));
    1329                 :       78355 :       wide_int high;
    1330                 :             :       // Singleton cases have no CASE_HIGH.
    1331                 :       78355 :       tree tree_high = CASE_HIGH (label);
    1332                 :       78355 :       if (tree_high)
    1333                 :        3620 :         high = wi::to_wide (tree_high);
    1334                 :             :       else
    1335                 :       74735 :         high = low;
    1336                 :             : 
    1337                 :             :       // If the case range is fully contained in op_range, leave the
    1338                 :             :       // case as it is, otherwise adjust the labels.
    1339                 :       78355 :       int_range_max case_range (type, low, high);
    1340                 :       78355 :       if (case_range.intersect (op_range))
    1341                 :             :         {
    1342                 :             :           // If none of the label is in op_range, skip this label.
    1343                 :        6208 :           if (case_range.undefined_p ())
    1344                 :        6172 :             continue;
    1345                 :             : 
    1346                 :             :           // Part of the label is in op_range, but not all of it.  CASE_RANGE
    1347                 :             :           // contains the part that is.   Adjust the case range to
    1348                 :             :           // the new min/max.
    1349                 :          36 :           if (case_range.lower_bound () != low)
    1350                 :          10 :             CASE_LOW (label) = wide_int_to_tree (type,
    1351                 :          20 :                                                  case_range.lower_bound ());
    1352                 :          36 :           if (case_range.singleton_p ())
    1353                 :           4 :             CASE_HIGH (label) = NULL_TREE;
    1354                 :             :           else
    1355                 :          32 :             if (case_range.upper_bound () != high)
    1356                 :           7 :               CASE_HIGH (label) = wide_int_to_tree (type,
    1357                 :          14 :                                                     case_range.upper_bound ());
    1358                 :             :         }
    1359                 :             :       // Add case label to the keep list.
    1360                 :       72183 :       cases.safe_push (x);
    1361                 :             :       // Remove case_range from needing to be handled by the default.
    1362                 :       72183 :       case_range.invert ();
    1363                 :       72183 :       default_range.intersect (case_range);
    1364                 :       78355 :     }
    1365                 :             : 
    1366                 :             :   // An undefined DEFAULT range means the current default case is not needed.
    1367                 :       15012 :   unsigned idx = default_range.undefined_p () ? 0 : 1;
    1368                 :       15012 :   unsigned vec_size = cases.length () + idx;
    1369                 :       15012 :   if (vec_size == lim)
    1370                 :             :     return false;
    1371                 :             : 
    1372                 :        4037 :   tree vec2 = make_tree_vec (vec_size);
    1373                 :             :   // Add default label if there is one.
    1374                 :        4037 :   if (idx)
    1375                 :             :     {
    1376                 :        3102 :       TREE_VEC_ELT (vec2, 0) = gimple_switch_default_label (stmt);
    1377                 :        3102 :       e = gimple_switch_edge (cfun, stmt, 0);
    1378                 :        3102 :       e->aux =  (void *)-1;
    1379                 :             :     }
    1380                 :             : 
    1381                 :       15880 :   for (x = 0; x < cases.length (); x++)
    1382                 :             :     {
    1383                 :       11843 :       unsigned swi = cases[x];
    1384                 :       11843 :       TREE_VEC_ELT (vec2, idx++) = gimple_switch_label (stmt, swi);
    1385                 :       11843 :       e = gimple_switch_edge (cfun, stmt, swi);
    1386                 :       11843 :       e->aux =  (void *)-1;
    1387                 :             :     }
    1388                 :             : 
    1389                 :             :   /* Queue not needed edges for later removal.  */
    1390                 :        4037 :   edge_iterator ei;
    1391                 :       25300 :   FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
    1392                 :             :     {
    1393                 :       21263 :       if (e->aux == (void *)-1)
    1394                 :             :         {
    1395                 :       14297 :           e->aux = NULL;
    1396                 :       14297 :           continue;
    1397                 :             :         }
    1398                 :             : 
    1399                 :        6966 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1400                 :             :         {
    1401                 :           0 :           fprintf (dump_file, "removing unreachable case label\n");
    1402                 :             :         }
    1403                 :        6966 :       to_remove_edges.safe_push (e);
    1404                 :        6966 :       set_and_propagate_unexecutable (e);
    1405                 :        6966 :       e->flags &= ~EDGE_EXECUTABLE;
    1406                 :        6966 :       e->flags |= EDGE_IGNORE;
    1407                 :             :     }
    1408                 :             : 
    1409                 :             :   /* And queue an update for the stmt.  */
    1410                 :        4037 :   su.stmt = stmt;
    1411                 :        4037 :   su.vec = vec2;
    1412                 :        4037 :   to_update_switch_stmts.safe_push (su);
    1413                 :        4037 :   return true;
    1414                 :       65999 : }
    1415                 :             : 
    1416                 :             : void
    1417                 :    13096104 : simplify_using_ranges::cleanup_edges_and_switches (void)
    1418                 :             : {
    1419                 :    13096104 :   int i;
    1420                 :    13096104 :   edge e;
    1421                 :    13096104 :   switch_update *su;
    1422                 :             : 
    1423                 :             :   /* Clear any edges marked as not executable.  */
    1424                 :    13096104 :   if (m_not_executable_flag)
    1425                 :             :     {
    1426                 :     4419288 :       FOR_EACH_VEC_ELT (m_flag_set_edges, i, e)
    1427                 :      195387 :         e->flags &= ~m_not_executable_flag;
    1428                 :             :     }
    1429                 :             :   /* Remove dead edges from SWITCH_EXPR optimization.  This leaves the
    1430                 :             :      CFG in a broken state and requires a cfg_cleanup run.  */
    1431                 :    13106821 :   FOR_EACH_VEC_ELT (to_remove_edges, i, e)
    1432                 :        6966 :     remove_edge (e);
    1433                 :             : 
    1434                 :             :   /* Update SWITCH_EXPR case label vector.  */
    1435                 :    13100141 :   FOR_EACH_VEC_ELT (to_update_switch_stmts, i, su)
    1436                 :             :     {
    1437                 :        4037 :       size_t j;
    1438                 :        4037 :       size_t n = TREE_VEC_LENGTH (su->vec);
    1439                 :        4037 :       tree label;
    1440                 :        4037 :       gimple_switch_set_num_labels (su->stmt, n);
    1441                 :       23019 :       for (j = 0; j < n; j++)
    1442                 :       14945 :         gimple_switch_set_label (su->stmt, j, TREE_VEC_ELT (su->vec, j));
    1443                 :             :       /* As we may have replaced the default label with a regular one
    1444                 :             :          make sure to make it a real default label again.  This ensures
    1445                 :             :          optimal expansion.  */
    1446                 :        4037 :       label = gimple_switch_label (su->stmt, 0);
    1447                 :        4037 :       CASE_LOW (label) = NULL_TREE;
    1448                 :        4037 :       CASE_HIGH (label) = NULL_TREE;
    1449                 :             :     }
    1450                 :             : 
    1451                 :    13096104 :   if (!to_remove_edges.is_empty ())
    1452                 :             :     {
    1453                 :        3751 :       free_dominance_info (CDI_DOMINATORS);
    1454                 :        3751 :       loops_state_set (LOOPS_NEED_FIXUP);
    1455                 :             :     }
    1456                 :             : 
    1457                 :    13096104 :   to_remove_edges.release ();
    1458                 :    13096104 :   to_update_switch_stmts.release ();
    1459                 :    13096104 : }
    1460                 :             : 
    1461                 :             : /* Simplify an integral conversion from an SSA name in STMT.  */
    1462                 :             : 
    1463                 :             : static bool
    1464                 :     4726794 : simplify_conversion_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt)
    1465                 :             : {
    1466                 :     4726794 :   tree innerop, middleop, finaltype;
    1467                 :     4726794 :   gimple *def_stmt;
    1468                 :     4726794 :   signop inner_sgn, middle_sgn, final_sgn;
    1469                 :     4726794 :   unsigned inner_prec, middle_prec, final_prec;
    1470                 :     4726794 :   widest_int innermin, innermed, innermax, middlemin, middlemed, middlemax;
    1471                 :             : 
    1472                 :     4726794 :   finaltype = TREE_TYPE (gimple_assign_lhs (stmt));
    1473                 :     4726794 :   if (!INTEGRAL_TYPE_P (finaltype))
    1474                 :             :     return false;
    1475                 :     4355999 :   middleop = gimple_assign_rhs1 (stmt);
    1476                 :     4355999 :   def_stmt = SSA_NAME_DEF_STMT (middleop);
    1477                 :     4355999 :   if (!is_gimple_assign (def_stmt)
    1478                 :     4355999 :       || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
    1479                 :             :     return false;
    1480                 :      154756 :   innerop = gimple_assign_rhs1 (def_stmt);
    1481                 :      154756 :   if (TREE_CODE (innerop) != SSA_NAME
    1482                 :      154756 :       || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop))
    1483                 :             :     return false;
    1484                 :             : 
    1485                 :             :   /* Get the value-range of the inner operand.  Use global ranges in
    1486                 :             :      case innerop was created during substitute-and-fold.  */
    1487                 :      151515 :   wide_int imin, imax;
    1488                 :      151515 :   int_range_max vr;
    1489                 :      151515 :   if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop)))
    1490                 :             :     return false;
    1491                 :      255812 :   get_range_query (cfun)->range_of_expr (vr, innerop, stmt);
    1492                 :      127906 :   if (vr.undefined_p () || vr.varying_p ())
    1493                 :             :     return false;
    1494                 :       73127 :   innermin = widest_int::from (vr.lower_bound (), TYPE_SIGN (TREE_TYPE (innerop)));
    1495                 :       73127 :   innermax = widest_int::from (vr.upper_bound (), TYPE_SIGN (TREE_TYPE (innerop)));
    1496                 :             : 
    1497                 :             :   /* Simulate the conversion chain to check if the result is equal if
    1498                 :             :      the middle conversion is removed.  */
    1499                 :       73127 :   inner_prec = TYPE_PRECISION (TREE_TYPE (innerop));
    1500                 :       73127 :   middle_prec = TYPE_PRECISION (TREE_TYPE (middleop));
    1501                 :       73127 :   final_prec = TYPE_PRECISION (finaltype);
    1502                 :             : 
    1503                 :             :   /* If the first conversion is not injective, the second must not
    1504                 :             :      be widening.  */
    1505                 :       73127 :   if (wi::gtu_p (innermax - innermin,
    1506                 :      146254 :                  wi::mask <widest_int> (middle_prec, false))
    1507                 :       73127 :       && middle_prec < final_prec)
    1508                 :             :     return false;
    1509                 :             :   /* We also want a medium value so that we can track the effect that
    1510                 :             :      narrowing conversions with sign change have.  */
    1511                 :       59493 :   inner_sgn = TYPE_SIGN (TREE_TYPE (innerop));
    1512                 :       59493 :   if (inner_sgn == UNSIGNED)
    1513                 :       45486 :     innermed = wi::shifted_mask <widest_int> (1, inner_prec - 1, false);
    1514                 :             :   else
    1515                 :       14007 :     innermed = 0;
    1516                 :       59493 :   if (wi::cmp (innermin, innermed, inner_sgn) >= 0
    1517                 :       59493 :       || wi::cmp (innermed, innermax, inner_sgn) >= 0)
    1518                 :       46745 :     innermed = innermin;
    1519                 :             : 
    1520                 :       59493 :   middle_sgn = TYPE_SIGN (TREE_TYPE (middleop));
    1521                 :       59493 :   middlemin = wi::ext (innermin, middle_prec, middle_sgn);
    1522                 :       59493 :   middlemed = wi::ext (innermed, middle_prec, middle_sgn);
    1523                 :       59493 :   middlemax = wi::ext (innermax, middle_prec, middle_sgn);
    1524                 :             : 
    1525                 :             :   /* Require that the final conversion applied to both the original
    1526                 :             :      and the intermediate range produces the same result.  */
    1527                 :       59493 :   final_sgn = TYPE_SIGN (finaltype);
    1528                 :      118986 :   if (wi::ext (middlemin, final_prec, final_sgn)
    1529                 :      118986 :          != wi::ext (innermin, final_prec, final_sgn)
    1530                 :      113488 :       || wi::ext (middlemed, final_prec, final_sgn)
    1531                 :      229725 :          != wi::ext (innermed, final_prec, final_sgn)
    1532                 :      155557 :       || wi::ext (middlemax, final_prec, final_sgn)
    1533                 :      203589 :          != wi::ext (innermax, final_prec, final_sgn))
    1534                 :             :     return false;
    1535                 :             : 
    1536                 :       46870 :   gimple_assign_set_rhs1 (stmt, innerop);
    1537                 :       46870 :   fold_stmt (gsi, follow_single_use_edges);
    1538                 :       46870 :   return true;
    1539                 :     4878309 : }
    1540                 :             : 
    1541                 :             : /* Simplify a conversion from integral SSA name to float in STMT.  */
    1542                 :             : 
    1543                 :             : bool
    1544                 :      254565 : simplify_using_ranges::simplify_float_conversion_using_ranges
    1545                 :             :                                         (gimple_stmt_iterator *gsi,
    1546                 :             :                                          gimple *stmt)
    1547                 :             : {
    1548                 :      254565 :   tree rhs1 = gimple_assign_rhs1 (stmt);
    1549                 :      254565 :   int_range_max vr;
    1550                 :      254565 :   scalar_float_mode fltmode
    1551                 :      254565 :     = SCALAR_FLOAT_TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt)));
    1552                 :      254565 :   scalar_int_mode mode;
    1553                 :      254565 :   tree tem;
    1554                 :      254565 :   gassign *conv;
    1555                 :             : 
    1556                 :             :   /* We can only handle constant ranges.  */
    1557                 :      254565 :   if (!query->range_of_expr (vr, rhs1, stmt)
    1558                 :      254565 :       || vr.varying_p ()
    1559                 :      354678 :       || vr.undefined_p ())
    1560                 :             :     return false;
    1561                 :             : 
    1562                 :             :   /* The code below doesn't work for large/huge _BitInt, nor is really
    1563                 :             :      needed for those, bitint lowering does use ranges already.  */
    1564                 :       99430 :   if (TREE_CODE (TREE_TYPE (rhs1)) == BITINT_TYPE
    1565                 :       99430 :       && TYPE_MODE (TREE_TYPE (rhs1)) == BLKmode)
    1566                 :             :     return false;
    1567                 :             :   /* First check if we can use a signed type in place of an unsigned.  */
    1568                 :       99428 :   scalar_int_mode rhs_mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (rhs1));
    1569                 :       99428 :   if (TYPE_UNSIGNED (TREE_TYPE (rhs1))
    1570                 :        5572 :       && can_float_p (fltmode, rhs_mode, 0) != CODE_FOR_nothing
    1571                 :      103248 :       && range_fits_type_p (&vr, TYPE_PRECISION (TREE_TYPE (rhs1)), SIGNED))
    1572                 :             :     mode = rhs_mode;
    1573                 :             :   /* If we can do the conversion in the current input mode do nothing.  */
    1574                 :       97966 :   else if (can_float_p (fltmode, rhs_mode,
    1575                 :       97966 :                         TYPE_UNSIGNED (TREE_TYPE (rhs1))) != CODE_FOR_nothing)
    1576                 :             :     return false;
    1577                 :             :   /* Otherwise search for a mode we can use, starting from the narrowest
    1578                 :             :      integer mode available.  */
    1579                 :             :   else
    1580                 :             :     {
    1581                 :        4395 :       mode = NARROWEST_INT_MODE;
    1582                 :       15852 :       for (;;)
    1583                 :             :         {
    1584                 :             :           /* If we cannot do a signed conversion to float from mode
    1585                 :             :              or if the value-range does not fit in the signed type
    1586                 :             :              try with a wider mode.  */
    1587                 :       15852 :           if (can_float_p (fltmode, mode, 0) != CODE_FOR_nothing
    1588                 :       15852 :               && range_fits_type_p (&vr, GET_MODE_PRECISION (mode), SIGNED))
    1589                 :             :             break;
    1590                 :             : 
    1591                 :             :           /* But do not widen the input.  Instead leave that to the
    1592                 :             :              optabs expansion code.  */
    1593                 :       31444 :           if (!GET_MODE_WIDER_MODE (mode).exists (&mode)
    1594                 :       15722 :               || GET_MODE_PRECISION (mode) > TYPE_PRECISION (TREE_TYPE (rhs1)))
    1595                 :             :             return false;
    1596                 :             :         }
    1597                 :             :     }
    1598                 :             : 
    1599                 :             :   /* It works, insert a truncation or sign-change before the
    1600                 :             :      float conversion.  */
    1601                 :        1592 :   tem = make_ssa_name (build_nonstandard_integer_type
    1602                 :        1592 :                           (GET_MODE_PRECISION (mode), 0));
    1603                 :        1592 :   conv = gimple_build_assign (tem, NOP_EXPR, rhs1);
    1604                 :        1592 :   gsi_insert_before (gsi, conv, GSI_SAME_STMT);
    1605                 :        1592 :   gimple_assign_set_rhs1 (stmt, tem);
    1606                 :        1592 :   fold_stmt (gsi, follow_single_use_edges);
    1607                 :             : 
    1608                 :        1592 :   return true;
    1609                 :      254565 : }
    1610                 :             : 
    1611                 :             : /* Simplify an internal fn call using ranges if possible.  */
    1612                 :             : 
    1613                 :             : bool
    1614                 :      361846 : simplify_using_ranges::simplify_internal_call_using_ranges
    1615                 :             :                                         (gimple_stmt_iterator *gsi,
    1616                 :             :                                          gimple *stmt)
    1617                 :             : {
    1618                 :      361846 :   enum tree_code subcode;
    1619                 :      361846 :   bool is_ubsan = false;
    1620                 :      361846 :   bool ovf = false;
    1621                 :      361846 :   switch (gimple_call_internal_fn (stmt))
    1622                 :             :     {
    1623                 :             :     case IFN_UBSAN_CHECK_ADD:
    1624                 :             :       subcode = PLUS_EXPR;
    1625                 :             :       is_ubsan = true;
    1626                 :             :       break;
    1627                 :        2455 :     case IFN_UBSAN_CHECK_SUB:
    1628                 :        2455 :       subcode = MINUS_EXPR;
    1629                 :        2455 :       is_ubsan = true;
    1630                 :        2455 :       break;
    1631                 :        2122 :     case IFN_UBSAN_CHECK_MUL:
    1632                 :        2122 :       subcode = MULT_EXPR;
    1633                 :        2122 :       is_ubsan = true;
    1634                 :        2122 :       break;
    1635                 :       41267 :     case IFN_ADD_OVERFLOW:
    1636                 :       41267 :       subcode = PLUS_EXPR;
    1637                 :       41267 :       break;
    1638                 :       49613 :     case IFN_SUB_OVERFLOW:
    1639                 :       49613 :       subcode = MINUS_EXPR;
    1640                 :       49613 :       break;
    1641                 :       47481 :     case IFN_MUL_OVERFLOW:
    1642                 :       47481 :       subcode = MULT_EXPR;
    1643                 :       47481 :       break;
    1644                 :             :     default:
    1645                 :             :       return false;
    1646                 :             :     }
    1647                 :             : 
    1648                 :      145503 :   tree op0 = gimple_call_arg (stmt, 0);
    1649                 :      145503 :   tree op1 = gimple_call_arg (stmt, 1);
    1650                 :      145503 :   tree type;
    1651                 :      145503 :   if (is_ubsan)
    1652                 :             :     {
    1653                 :        7142 :       type = TREE_TYPE (op0);
    1654                 :        7142 :       if (VECTOR_TYPE_P (type))
    1655                 :             :         return false;
    1656                 :             :     }
    1657                 :      138361 :   else if (gimple_call_lhs (stmt) == NULL_TREE)
    1658                 :             :     return false;
    1659                 :             :   else
    1660                 :      138361 :     type = TREE_TYPE (TREE_TYPE (gimple_call_lhs (stmt)));
    1661                 :      144633 :   if (!check_for_binary_op_overflow (query, subcode, type, op0, op1, &ovf, stmt)
    1662                 :      144633 :       || (is_ubsan && ovf))
    1663                 :             :     return false;
    1664                 :             : 
    1665                 :        3460 :   gimple *g;
    1666                 :        3460 :   location_t loc = gimple_location (stmt);
    1667                 :        3460 :   if (is_ubsan)
    1668                 :         568 :     g = gimple_build_assign (gimple_call_lhs (stmt), subcode, op0, op1);
    1669                 :             :   else
    1670                 :             :     {
    1671                 :        2892 :       tree utype = type;
    1672                 :        2892 :       if (ovf
    1673                 :        1408 :           || !useless_type_conversion_p (type, TREE_TYPE (op0))
    1674                 :        3581 :           || !useless_type_conversion_p (type, TREE_TYPE (op1)))
    1675                 :        2487 :         utype = unsigned_type_for (type);
    1676                 :        2892 :       if (TREE_CODE (op0) == INTEGER_CST)
    1677                 :        1174 :         op0 = fold_convert (utype, op0);
    1678                 :        1718 :       else if (!useless_type_conversion_p (utype, TREE_TYPE (op0)))
    1679                 :             :         {
    1680                 :         719 :           g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, op0);
    1681                 :         719 :           gimple_set_location (g, loc);
    1682                 :         719 :           gsi_insert_before (gsi, g, GSI_SAME_STMT);
    1683                 :         719 :           op0 = gimple_assign_lhs (g);
    1684                 :             :         }
    1685                 :        2892 :       if (TREE_CODE (op1) == INTEGER_CST)
    1686                 :        1663 :         op1 = fold_convert (utype, op1);
    1687                 :        1229 :       else if (!useless_type_conversion_p (utype, TREE_TYPE (op1)))
    1688                 :             :         {
    1689                 :          21 :           g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, op1);
    1690                 :          21 :           gimple_set_location (g, loc);
    1691                 :          21 :           gsi_insert_before (gsi, g, GSI_SAME_STMT);
    1692                 :          21 :           op1 = gimple_assign_lhs (g);
    1693                 :             :         }
    1694                 :        2892 :       g = gimple_build_assign (make_ssa_name (utype), subcode, op0, op1);
    1695                 :        2892 :       gimple_set_location (g, loc);
    1696                 :        2892 :       gsi_insert_before (gsi, g, GSI_SAME_STMT);
    1697                 :        2892 :       if (utype != type)
    1698                 :             :         {
    1699                 :        1334 :           g = gimple_build_assign (make_ssa_name (type), NOP_EXPR,
    1700                 :             :                                    gimple_assign_lhs (g));
    1701                 :        1334 :           gimple_set_location (g, loc);
    1702                 :        1334 :           gsi_insert_before (gsi, g, GSI_SAME_STMT);
    1703                 :             :         }
    1704                 :        2892 :       g = gimple_build_assign (gimple_call_lhs (stmt), COMPLEX_EXPR,
    1705                 :             :                                gimple_assign_lhs (g),
    1706                 :        2892 :                                build_int_cst (type, ovf));
    1707                 :             :     }
    1708                 :        3460 :   gimple_set_location (g, loc);
    1709                 :        3460 :   gsi_replace (gsi, g, false);
    1710                 :        3460 :   return true;
    1711                 :             : }
    1712                 :             : 
    1713                 :             : /* Return true if VAR is a two-valued variable.  Set a and b with the
    1714                 :             :    two-values when it is true.  Return false otherwise.  */
    1715                 :             : 
    1716                 :             : bool
    1717                 :      516121 : simplify_using_ranges::two_valued_val_range_p (tree var, tree *a, tree *b,
    1718                 :             :                                                gimple *s)
    1719                 :             : {
    1720                 :      516121 :   int_range_max vr;
    1721                 :      516121 :   if (!query->range_of_expr (vr, var, s))
    1722                 :             :     return false;
    1723                 :      516121 :   if (vr.varying_p () || vr.undefined_p ())
    1724                 :             :     return false;
    1725                 :             : 
    1726                 :      811693 :   if ((vr.num_pairs () == 1 && vr.upper_bound () - vr.lower_bound () == 1)
    1727                 :      419912 :       || (vr.num_pairs () == 2
    1728                 :      289743 :           && vr.lower_bound (0) == vr.upper_bound (0)
    1729                 :      246443 :           && vr.lower_bound (1) == vr.upper_bound (1)))
    1730                 :             :     {
    1731                 :        6646 :       *a = wide_int_to_tree (TREE_TYPE (var), vr.lower_bound ());
    1732                 :        6646 :       *b = wide_int_to_tree (TREE_TYPE (var), vr.upper_bound ());
    1733                 :        6646 :       return true;
    1734                 :             :     }
    1735                 :             :   return false;
    1736                 :      516121 : }
    1737                 :             : 
    1738                 :    13096104 : simplify_using_ranges::simplify_using_ranges (range_query *query,
    1739                 :    13096104 :                                               int not_executable_flag)
    1740                 :    13096104 :   : query (query)
    1741                 :             : {
    1742                 :    13096104 :   to_remove_edges = vNULL;
    1743                 :    13096104 :   to_update_switch_stmts = vNULL;
    1744                 :    13096104 :   m_not_executable_flag = not_executable_flag;
    1745                 :    13096104 :   m_flag_set_edges = vNULL;
    1746                 :    13096104 : }
    1747                 :             : 
    1748                 :    13096104 : simplify_using_ranges::~simplify_using_ranges ()
    1749                 :             : {
    1750                 :    13096104 :   cleanup_edges_and_switches ();
    1751                 :    13096104 :   m_flag_set_edges.release ();
    1752                 :    13096104 : }
    1753                 :             : 
    1754                 :             : /* Simplify STMT using ranges if possible.  */
    1755                 :             : 
    1756                 :             : bool
    1757                 :   234974072 : simplify_using_ranges::simplify (gimple_stmt_iterator *gsi)
    1758                 :             : {
    1759                 :   234974072 :   gcc_checking_assert (query);
    1760                 :             : 
    1761                 :   234974072 :   gimple *stmt = gsi_stmt (*gsi);
    1762                 :   234974072 :   if (is_gimple_assign (stmt))
    1763                 :             :     {
    1764                 :    67641412 :       enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
    1765                 :    67641412 :       tree rhs1 = gimple_assign_rhs1 (stmt);
    1766                 :    67641412 :       tree rhs2 = gimple_assign_rhs2 (stmt);
    1767                 :    67641412 :       tree lhs = gimple_assign_lhs (stmt);
    1768                 :    67641412 :       tree val1 = NULL_TREE, val2 = NULL_TREE;
    1769                 :    67641412 :       use_operand_p use_p;
    1770                 :    67641412 :       gimple *use_stmt;
    1771                 :             : 
    1772                 :             :       /* Convert:
    1773                 :             :          LHS = CST BINOP VAR
    1774                 :             :          Where VAR is two-valued and LHS is used in GIMPLE_COND only
    1775                 :             :          To:
    1776                 :             :          LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2)
    1777                 :             : 
    1778                 :             :          Also handles:
    1779                 :             :          LHS = VAR BINOP CST
    1780                 :             :          Where VAR is two-valued and LHS is used in GIMPLE_COND only
    1781                 :             :          To:
    1782                 :             :          LHS = VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST) */
    1783                 :             : 
    1784                 :    67641412 :       if (TREE_CODE_CLASS (rhs_code) == tcc_binary
    1785                 :    14136997 :           && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
    1786                 :    10043088 :           && ((TREE_CODE (rhs1) == INTEGER_CST
    1787                 :      178425 :                && TREE_CODE (rhs2) == SSA_NAME)
    1788                 :     9865263 :               || (TREE_CODE (rhs2) == INTEGER_CST
    1789                 :     6613736 :                   && TREE_CODE (rhs1) == SSA_NAME))
    1790                 :     6790961 :           && single_imm_use (lhs, &use_p, &use_stmt)
    1791                 :    72867345 :           && gimple_code (use_stmt) == GIMPLE_COND)
    1792                 :             : 
    1793                 :             :         {
    1794                 :      516121 :           tree new_rhs1 = NULL_TREE;
    1795                 :      516121 :           tree new_rhs2 = NULL_TREE;
    1796                 :      516121 :           tree cmp_var = NULL_TREE;
    1797                 :             : 
    1798                 :      516121 :           if (TREE_CODE (rhs2) == SSA_NAME
    1799                 :      516121 :               && two_valued_val_range_p (rhs2, &val1, &val2, stmt))
    1800                 :             :             {
    1801                 :             :               /* Optimize RHS1 OP [VAL1, VAL2].  */
    1802                 :         188 :               new_rhs1 = int_const_binop (rhs_code, rhs1, val1);
    1803                 :         188 :               new_rhs2 = int_const_binop (rhs_code, rhs1, val2);
    1804                 :         188 :               cmp_var = rhs2;
    1805                 :             :             }
    1806                 :      515933 :           else if (TREE_CODE (rhs1) == SSA_NAME
    1807                 :      515933 :                    && two_valued_val_range_p (rhs1, &val1, &val2, stmt))
    1808                 :             :             {
    1809                 :             :               /* Optimize [VAL1, VAL2] OP RHS2.  */
    1810                 :        6458 :               new_rhs1 = int_const_binop (rhs_code, val1, rhs2);
    1811                 :        6458 :               new_rhs2 = int_const_binop (rhs_code, val2, rhs2);
    1812                 :        6458 :               cmp_var = rhs1;
    1813                 :             :             }
    1814                 :             : 
    1815                 :             :           /* If we could not find two-vals or the optimzation is invalid as
    1816                 :             :              in divide by zero, new_rhs1 / new_rhs will be NULL_TREE.  */
    1817                 :      516121 :           if (new_rhs1 && new_rhs2)
    1818                 :             :             {
    1819                 :        6646 :               tree cond = gimple_build (gsi, true, GSI_SAME_STMT,
    1820                 :             :                                         UNKNOWN_LOCATION,
    1821                 :             :                                         EQ_EXPR, boolean_type_node,
    1822                 :             :                                         cmp_var, val1);
    1823                 :        6646 :               gimple_assign_set_rhs_with_ops (gsi,
    1824                 :             :                                               COND_EXPR, cond,
    1825                 :             :                                               new_rhs1,
    1826                 :             :                                               new_rhs2);
    1827                 :        6646 :               update_stmt (gsi_stmt (*gsi));
    1828                 :        6646 :               fold_stmt (gsi, follow_single_use_edges);
    1829                 :     8118702 :               return true;
    1830                 :             :             }
    1831                 :             :         }
    1832                 :             : 
    1833                 :    67634766 :       if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
    1834                 :     1219804 :         return simplify_compare_assign_using_ranges_1 (gsi, stmt);
    1835                 :             : 
    1836                 :    66414962 :       switch (rhs_code)
    1837                 :             :         {
    1838                 :             : 
    1839                 :             :       /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
    1840                 :             :          and BIT_AND_EXPR respectively if the first operand is greater
    1841                 :             :          than zero and the second operand is an exact power of two.
    1842                 :             :          Also optimize TRUNC_MOD_EXPR away if the second operand is
    1843                 :             :          constant and the first operand already has the right value
    1844                 :             :          range.  */
    1845                 :      324076 :         case TRUNC_DIV_EXPR:
    1846                 :      324076 :         case TRUNC_MOD_EXPR:
    1847                 :      324076 :           if ((TREE_CODE (rhs1) == SSA_NAME
    1848                 :      324076 :                || TREE_CODE (rhs1) == INTEGER_CST)
    1849                 :      324076 :               && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
    1850                 :      322862 :             return simplify_div_or_mod_using_ranges (gsi, stmt);
    1851                 :             :           break;
    1852                 :             : 
    1853                 :             :       /* Transform ABS (X) into X or -X as appropriate.  */
    1854                 :       55186 :         case ABS_EXPR:
    1855                 :       55186 :           if (TREE_CODE (rhs1) == SSA_NAME
    1856                 :       55186 :               && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
    1857                 :        6828 :             return simplify_abs_using_ranges (gsi, stmt);
    1858                 :             :           break;
    1859                 :             : 
    1860                 :     1347350 :         case BIT_AND_EXPR:
    1861                 :     1347350 :         case BIT_IOR_EXPR:
    1862                 :             :           /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR if all the bits
    1863                 :             :              being cleared are already cleared or all the bits being set
    1864                 :             :              are already set.  Beware that boolean types must be handled
    1865                 :             :              logically (see range-op.cc) unless they have precision 1.  */
    1866                 :     2590202 :           if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
    1867                 :     2560708 :               && (TREE_CODE (TREE_TYPE (rhs1)) != BOOLEAN_TYPE
    1868                 :      301396 :                   || TYPE_PRECISION (TREE_TYPE (rhs1)) == 1))
    1869                 :     1317856 :             return simplify_bit_ops_using_ranges (gsi, stmt);
    1870                 :             :           break;
    1871                 :             : 
    1872                 :     5800477 :         CASE_CONVERT:
    1873                 :     5800477 :           if (TREE_CODE (rhs1) == SSA_NAME
    1874                 :     5800477 :               && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
    1875                 :     4726794 :             return simplify_conversion_using_ranges (gsi, stmt);
    1876                 :             :           break;
    1877                 :             : 
    1878                 :      256916 :         case FLOAT_EXPR:
    1879                 :      256916 :           if (TREE_CODE (rhs1) == SSA_NAME
    1880                 :      256916 :               && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
    1881                 :      254565 :             return simplify_float_conversion_using_ranges (gsi, stmt);
    1882                 :             :           break;
    1883                 :             : 
    1884                 :      179980 :         case MIN_EXPR:
    1885                 :      179980 :         case MAX_EXPR:
    1886                 :      179980 :           return simplify_min_or_max_using_ranges (gsi, stmt);
    1887                 :             : 
    1888                 :      395125 :         case RSHIFT_EXPR:
    1889                 :      395125 :           {
    1890                 :      395125 :             tree op0 = gimple_assign_rhs1 (stmt);
    1891                 :      395125 :             tree type = TREE_TYPE (op0);
    1892                 :      395125 :             int_range_max range;
    1893                 :      395125 :             if (TYPE_SIGN (type) == SIGNED
    1894                 :      395125 :                 && query->range_of_expr (range, op0, stmt))
    1895                 :             :               {
    1896                 :       83367 :                 unsigned prec = TYPE_PRECISION (TREE_TYPE (op0));
    1897                 :      166734 :                 int_range<2> nzm1 (type, wi::minus_one (prec), wi::zero (prec),
    1898                 :       83367 :                                    VR_ANTI_RANGE);
    1899                 :       83367 :                 range.intersect (nzm1);
    1900                 :             :                 // If there are no ranges other than [-1, 0] remove the shift.
    1901                 :       83367 :                 if (range.undefined_p ())
    1902                 :             :                   {
    1903                 :          57 :                     gimple_assign_set_rhs_from_tree (gsi, op0);
    1904                 :          57 :                     return true;
    1905                 :             :                   }
    1906                 :             :                 return false;
    1907                 :       83367 :               }
    1908                 :      311758 :             break;
    1909                 :      395125 :           }
    1910                 :             :         default:
    1911                 :             :           break;
    1912                 :             :         }
    1913                 :             :     }
    1914                 :   167332660 :   else if (gimple_code (stmt) == GIMPLE_COND)
    1915                 :    11994600 :     return simplify_cond_using_ranges_1 (as_a <gcond *> (stmt));
    1916                 :   155338060 :   else if (gimple_code (stmt) == GIMPLE_SWITCH)
    1917                 :       65999 :     return simplify_switch_using_ranges (as_a <gswitch *> (stmt));
    1918                 :   155272061 :   else if (is_gimple_call (stmt)
    1919                 :   155272061 :            && gimple_call_internal_p (stmt))
    1920                 :      361846 :     return simplify_internal_call_using_ranges (gsi, stmt);
    1921                 :             : 
    1922                 :             :   return false;
    1923                 :             : }
        

Generated by: LCOV version 2.1-beta

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,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.