LCOV - code coverage report
Current view: top level - gcc - tree-ssa-ccp.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 94.5 % 1576 1489
Test Date: 2026-11-14 16:39:50 Functions: 98.0 % 51 50
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Conditional constant propagation pass for the GNU compiler.
       2              :    Copyright (C) 2000-2026 Free Software Foundation, Inc.
       3              :    Adapted from original RTL SSA-CCP by Daniel Berlin <dberlin@dberlin.org>
       4              :    Adapted to GIMPLE trees by Diego Novillo <dnovillo@redhat.com>
       5              : 
       6              : This file is part of GCC.
       7              : 
       8              : GCC is free software; you can redistribute it and/or modify it
       9              : under the terms of the GNU General Public License as published by the
      10              : Free Software Foundation; either version 3, or (at your option) any
      11              : later version.
      12              : 
      13              : GCC is distributed in the hope that it will be useful, but WITHOUT
      14              : ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
      15              : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      16              : for more details.
      17              : 
      18              : You should have received a copy of the GNU General Public License
      19              : along with GCC; see the file COPYING3.  If not see
      20              : <http://www.gnu.org/licenses/>.  */
      21              : 
      22              : /* Conditional constant propagation (CCP) is based on the SSA
      23              :    propagation engine (tree-ssa-propagate.cc).  Constant assignments of
      24              :    the form VAR = CST are propagated from the assignments into uses of
      25              :    VAR, which in turn may generate new constants.  The simulation uses
      26              :    a four level lattice to keep track of constant values associated
      27              :    with SSA names.  Given an SSA name V_i, it may take one of the
      28              :    following values:
      29              : 
      30              :         UNINITIALIZED   ->  the initial state of the value.  This value
      31              :                             is replaced with a correct initial value
      32              :                             the first time the value is used, so the
      33              :                             rest of the pass does not need to care about
      34              :                             it.  Using this value simplifies initialization
      35              :                             of the pass, and prevents us from needlessly
      36              :                             scanning statements that are never reached.
      37              : 
      38              :         UNDEFINED       ->  V_i is a local variable whose definition
      39              :                             has not been processed yet.  Therefore we
      40              :                             don't yet know if its value is a constant
      41              :                             or not.
      42              : 
      43              :         CONSTANT        ->  V_i has been found to hold a constant
      44              :                             value C.
      45              : 
      46              :         VARYING         ->  V_i cannot take a constant value, or if it
      47              :                             does, it is not possible to determine it
      48              :                             at compile time.
      49              : 
      50              :    The core of SSA-CCP is in ccp_visit_stmt and ccp_visit_phi_node:
      51              : 
      52              :    1- In ccp_visit_stmt, we are interested in assignments whose RHS
      53              :       evaluates into a constant and conditional jumps whose predicate
      54              :       evaluates into a boolean true or false.  When an assignment of
      55              :       the form V_i = CONST is found, V_i's lattice value is set to
      56              :       CONSTANT and CONST is associated with it.  This causes the
      57              :       propagation engine to add all the SSA edges coming out the
      58              :       assignment into the worklists, so that statements that use V_i
      59              :       can be visited.
      60              : 
      61              :       If the statement is a conditional with a constant predicate, we
      62              :       mark the outgoing edges as executable or not executable
      63              :       depending on the predicate's value.  This is then used when
      64              :       visiting PHI nodes to know when a PHI argument can be ignored.
      65              : 
      66              : 
      67              :    2- In ccp_visit_phi_node, if all the PHI arguments evaluate to the
      68              :       same constant C, then the LHS of the PHI is set to C.  This
      69              :       evaluation is known as the "meet operation".  Since one of the
      70              :       goals of this evaluation is to optimistically return constant
      71              :       values as often as possible, it uses two main short cuts:
      72              : 
      73              :       - If an argument is flowing in through a non-executable edge, it
      74              :         is ignored.  This is useful in cases like this:
      75              : 
      76              :                         if (PRED)
      77              :                           a_9 = 3;
      78              :                         else
      79              :                           a_10 = 100;
      80              :                         a_11 = PHI (a_9, a_10)
      81              : 
      82              :         If PRED is known to always evaluate to false, then we can
      83              :         assume that a_11 will always take its value from a_10, meaning
      84              :         that instead of consider it VARYING (a_9 and a_10 have
      85              :         different values), we can consider it CONSTANT 100.
      86              : 
      87              :       - If an argument has an UNDEFINED value, then it does not affect
      88              :         the outcome of the meet operation.  If a variable V_i has an
      89              :         UNDEFINED value, it means that either its defining statement
      90              :         hasn't been visited yet or V_i has no defining statement, in
      91              :         which case the original symbol 'V' is being used
      92              :         uninitialized.  Since 'V' is a local variable, the compiler
      93              :         may assume any initial value for it.
      94              : 
      95              : 
      96              :    After propagation, every variable V_i that ends up with a lattice
      97              :    value of CONSTANT will have the associated constant value in the
      98              :    array CONST_VAL[i].VALUE.  That is fed into substitute_and_fold for
      99              :    final substitution and folding.
     100              : 
     101              :    This algorithm uses wide-ints at the max precision of the target.
     102              :    This means that, with one uninteresting exception, variables with
     103              :    UNSIGNED types never go to VARYING because the bits above the
     104              :    precision of the type of the variable are always zero.  The
     105              :    uninteresting case is a variable of UNSIGNED type that has the
     106              :    maximum precision of the target.  Such variables can go to VARYING,
     107              :    but this causes no loss of information since these variables will
     108              :    never be extended.
     109              : 
     110              :    References:
     111              : 
     112              :      Constant propagation with conditional branches,
     113              :      Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
     114              : 
     115              :      Building an Optimizing Compiler,
     116              :      Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
     117              : 
     118              :      Advanced Compiler Design and Implementation,
     119              :      Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6  */
     120              : 
     121              : #include "config.h"
     122              : #include "system.h"
     123              : #include "coretypes.h"
     124              : #include "backend.h"
     125              : #include "target.h"
     126              : #include "tree.h"
     127              : #include "gimple.h"
     128              : #include "tree-pass.h"
     129              : #include "ssa.h"
     130              : #include "gimple-pretty-print.h"
     131              : #include "fold-const.h"
     132              : #include "gimple-iterator.h"
     133              : #include "gimple-fold.h"
     134              : #include "tree-eh.h"
     135              : #include "gimplify.h"
     136              : #include "tree-cfg.h"
     137              : #include "tree-ssa-propagate.h"
     138              : #include "dbgcnt.h"
     139              : #include "builtins.h"
     140              : #include "cfgloop.h"
     141              : #include "stor-layout.h"
     142              : #include "optabs-query.h"
     143              : #include "tree-ssa-ccp.h"
     144              : #include "tree-dfa.h"
     145              : #include "diagnostic-core.h"
     146              : #include "stringpool.h"
     147              : #include "attribs.h"
     148              : #include "tree-vector-builder.h"
     149              : #include "cgraph.h"
     150              : #include "alloc-pool.h"
     151              : #include "symbol-summary.h"
     152              : #include "ipa-utils.h"
     153              : #include "sreal.h"
     154              : #include "ipa-cp.h"
     155              : #include "ipa-prop.h"
     156              : #include "internal-fn.h"
     157              : #include "gimple-range.h"
     158              : #include "tree-ssa-strlen.h"
     159              : 
     160              : /* Possible lattice values.  */
     161              : typedef enum
     162              : {
     163              :   UNINITIALIZED,
     164              :   UNDEFINED,
     165              :   CONSTANT,
     166              :   VARYING
     167              : } ccp_lattice_t;
     168              : 
     169    527032850 : class ccp_prop_value_t {
     170              : public:
     171              :     /* Lattice value.  */
     172              :     ccp_lattice_t lattice_val;
     173              : 
     174              :     /* Propagated value.  */
     175              :     tree value;
     176              : 
     177              :     /* Mask that applies to the propagated value during CCP.  For X
     178              :        with a CONSTANT lattice value X & ~mask == value & ~mask.  The
     179              :        zero bits in the mask cover constant values.  The ones mean no
     180              :        information.  */
     181              :     widest_int mask;
     182              : };
     183              : 
     184      5714131 : class ccp_propagate : public ssa_propagation_engine
     185              : {
     186              :  public:
     187              :   enum ssa_prop_result visit_stmt (gimple *, edge *, tree *) final override;
     188              :   enum ssa_prop_result visit_phi (gphi *) final override;
     189              : };
     190              : 
     191              : /* Array of propagated constant values.  After propagation,
     192              :    CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I).  If
     193              :    the constant is held in an SSA name representing a memory store
     194              :    (i.e., a VDEF), CONST_VAL[I].MEM_REF will contain the actual
     195              :    memory reference used to store (i.e., the LHS of the assignment
     196              :    doing the store).  */
     197              : static ccp_prop_value_t *const_val;
     198              : static unsigned n_const_val;
     199              : 
     200              : static void canonicalize_value (ccp_prop_value_t *);
     201              : static void ccp_lattice_meet (ccp_prop_value_t *, ccp_prop_value_t *);
     202              : 
     203              : /* Dump constant propagation value VAL to file OUTF prefixed by PREFIX.  */
     204              : 
     205              : static void
     206           55 : dump_lattice_value (FILE *outf, const char *prefix, ccp_prop_value_t val)
     207              : {
     208           55 :   switch (val.lattice_val)
     209              :     {
     210            0 :     case UNINITIALIZED:
     211            0 :       fprintf (outf, "%sUNINITIALIZED", prefix);
     212            0 :       break;
     213            0 :     case UNDEFINED:
     214            0 :       fprintf (outf, "%sUNDEFINED", prefix);
     215            0 :       break;
     216           16 :     case VARYING:
     217           16 :       fprintf (outf, "%sVARYING", prefix);
     218           16 :       break;
     219           39 :     case CONSTANT:
     220           39 :       if (TREE_CODE (val.value) != INTEGER_CST
     221           39 :           || val.mask == 0)
     222              :         {
     223           36 :           fprintf (outf, "%sCONSTANT ", prefix);
     224           36 :           print_generic_expr (outf, val.value, dump_flags);
     225              :         }
     226              :       else
     227              :         {
     228            3 :           widest_int cval = wi::bit_and_not (wi::to_widest (val.value),
     229            3 :                                              val.mask);
     230            3 :           fprintf (outf, "%sCONSTANT ", prefix);
     231            3 :           print_hex (cval, outf);
     232            3 :           fprintf (outf, " (");
     233            3 :           print_hex (val.mask, outf);
     234            3 :           fprintf (outf, ")");
     235            3 :         }
     236              :       break;
     237            0 :     default:
     238            0 :       gcc_unreachable ();
     239              :     }
     240           55 : }
     241              : 
     242              : 
     243              : /* Print lattice value VAL to stderr.  */
     244              : 
     245              : void debug_lattice_value (ccp_prop_value_t val);
     246              : 
     247              : DEBUG_FUNCTION void
     248            0 : debug_lattice_value (ccp_prop_value_t val)
     249              : {
     250            0 :   dump_lattice_value (stderr, "", val);
     251            0 :   fprintf (stderr, "\n");
     252            0 : }
     253              : 
     254              : /* Extend NONZERO_BITS to a full mask, based on sgn.  */
     255              : 
     256              : static widest_int
     257     53689399 : extend_mask (const wide_int &nonzero_bits, signop sgn)
     258              : {
     259     53689399 :   return widest_int::from (nonzero_bits, sgn);
     260              : }
     261              : 
     262              : /* Compute a default value for variable VAR and store it in the
     263              :    CONST_VAL array.  The following rules are used to get default
     264              :    values:
     265              : 
     266              :    1- Global and static variables that are declared constant are
     267              :       considered CONSTANT.
     268              : 
     269              :    2- Any other value is considered UNDEFINED.  This is useful when
     270              :       considering PHI nodes.  PHI arguments that are undefined do not
     271              :       change the constant value of the PHI node, which allows for more
     272              :       constants to be propagated.
     273              : 
     274              :    3- Variables defined by statements other than assignments and PHI
     275              :       nodes are considered VARYING.
     276              : 
     277              :    4- Initial values of variables that are not GIMPLE registers are
     278              :       considered VARYING.  */
     279              : 
     280              : static ccp_prop_value_t
     281     10706786 : get_default_value (tree var)
     282              : {
     283     10706786 :   ccp_prop_value_t val = { UNINITIALIZED, NULL_TREE, 0 };
     284     10706786 :   gimple *stmt;
     285              : 
     286     10706786 :   stmt = SSA_NAME_DEF_STMT (var);
     287              : 
     288     10706786 :   if (gimple_nop_p (stmt))
     289              :     {
     290              :       /* Variables defined by an empty statement are those used
     291              :          before being initialized.  If VAR is a local variable, we
     292              :          can assume initially that it is UNDEFINED, otherwise we must
     293              :          consider it VARYING.  */
     294      9951234 :       if (!virtual_operand_p (var)
     295      9951234 :           && SSA_NAME_VAR (var)
     296     19902317 :           && VAR_P (SSA_NAME_VAR (var)))
     297      1631847 :         val.lattice_val = UNDEFINED;
     298              :       else
     299              :         {
     300      8319387 :           val.lattice_val = VARYING;
     301      8319387 :           val.mask = -1;
     302      8319387 :           if (flag_tree_bit_ccp && !VECTOR_TYPE_P (TREE_TYPE (var)))
     303              :             {
     304      7870096 :               wide_int nonzero_bits = get_nonzero_bits (var);
     305      7870096 :               tree value;
     306      7870096 :               widest_int mask;
     307              : 
     308      7870096 :               if (SSA_NAME_VAR (var)
     309      7869945 :                   && TREE_CODE (SSA_NAME_VAR (var)) == PARM_DECL
     310      7804749 :                   && ipcp_get_parm_bits (SSA_NAME_VAR (var), &value, &mask))
     311              :                 {
     312        84751 :                   val.lattice_val = CONSTANT;
     313        84751 :                   val.value = value;
     314        84751 :                   widest_int ipa_value = wi::to_widest (value);
     315              :                   /* Unknown bits from IPA CP must be equal to zero.  */
     316        84751 :                   gcc_assert (wi::bit_and (ipa_value, mask) == 0);
     317        84751 :                   val.mask = mask;
     318        84751 :                   if (nonzero_bits != -1)
     319        68339 :                     val.mask &= extend_mask (nonzero_bits,
     320        68339 :                                              TYPE_SIGN (TREE_TYPE (var)));
     321        84751 :                 }
     322      7785345 :               else if (nonzero_bits != -1)
     323              :                 {
     324         2127 :                   val.lattice_val = CONSTANT;
     325         2127 :                   val.value = build_zero_cst (TREE_TYPE (var));
     326         2127 :                   val.mask = extend_mask (nonzero_bits,
     327         2127 :                                           TYPE_SIGN (TREE_TYPE (var)));
     328              :                 }
     329      7870415 :             }
     330              :         }
     331              :     }
     332       755552 :   else if (is_gimple_assign (stmt))
     333              :     {
     334       653527 :       tree cst;
     335       653527 :       if (gimple_assign_single_p (stmt)
     336       297290 :           && DECL_P (gimple_assign_rhs1 (stmt))
     337       666245 :           && (cst = get_symbol_constant_value (gimple_assign_rhs1 (stmt))))
     338              :         {
     339           97 :           val.lattice_val = CONSTANT;
     340           97 :           val.value = cst;
     341              :         }
     342              :       else
     343              :         {
     344              :           /* Any other variable defined by an assignment is considered
     345              :              UNDEFINED.  */
     346       653430 :           val.lattice_val = UNDEFINED;
     347              :         }
     348              :     }
     349       102025 :   else if ((is_gimple_call (stmt)
     350        22458 :             && gimple_call_lhs (stmt) != NULL_TREE)
     351       102025 :            || gimple_code (stmt) == GIMPLE_PHI)
     352              :     {
     353              :       /* A variable defined by a call or a PHI node is considered
     354              :          UNDEFINED.  */
     355       101968 :       val.lattice_val = UNDEFINED;
     356              :     }
     357              :   else
     358              :     {
     359              :       /* Otherwise, VAR will never take on a constant value.  */
     360           57 :       val.lattice_val = VARYING;
     361           57 :       val.mask = -1;
     362              :     }
     363              : 
     364     10706786 :   return val;
     365              : }
     366              : 
     367              : 
     368              : /* Get the constant value associated with variable VAR.  */
     369              : 
     370              : static inline ccp_prop_value_t *
     371   3257791605 : get_value (tree var)
     372              : {
     373   3257791605 :   ccp_prop_value_t *val;
     374              : 
     375   3257791605 :   if (const_val == NULL
     376   6515583210 :       || SSA_NAME_VERSION (var) >= n_const_val)
     377              :     return NULL;
     378              : 
     379   3257784284 :   val = &const_val[SSA_NAME_VERSION (var)];
     380   3257784284 :   if (val->lattice_val == UNINITIALIZED)
     381     10706786 :     *val = get_default_value (var);
     382              : 
     383   3257784284 :   canonicalize_value (val);
     384              : 
     385   3257784284 :   return val;
     386              : }
     387              : 
     388              : /* Return the constant tree value associated with VAR.  */
     389              : 
     390              : static inline tree
     391   2573834633 : get_constant_value (tree var)
     392              : {
     393   2573834633 :   ccp_prop_value_t *val;
     394   2573834633 :   if (TREE_CODE (var) != SSA_NAME)
     395              :     {
     396         1211 :       if (is_gimple_min_invariant (var))
     397              :         return var;
     398            0 :       return NULL_TREE;
     399              :     }
     400   2573833422 :   val = get_value (var);
     401   2573833422 :   if (val
     402   2573826335 :       && val->lattice_val == CONSTANT
     403   3055603592 :       && (TREE_CODE (val->value) != INTEGER_CST
     404   2573833422 :           || val->mask == 0))
     405              :     return val->value;
     406              :   return NULL_TREE;
     407              : }
     408              : 
     409              : /* Sets the value associated with VAR to VARYING.  */
     410              : 
     411              : static inline void
     412     61648400 : set_value_varying (tree var)
     413              : {
     414     61648400 :   ccp_prop_value_t *val = &const_val[SSA_NAME_VERSION (var)];
     415              : 
     416     61648400 :   val->lattice_val = VARYING;
     417     61648400 :   val->value = NULL_TREE;
     418     61648400 :   val->mask = -1;
     419     61648400 : }
     420              : 
     421              : /* For integer constants, make sure to drop TREE_OVERFLOW.  */
     422              : 
     423              : static void
     424   3682919331 : canonicalize_value (ccp_prop_value_t *val)
     425              : {
     426   3682919331 :   if (val->lattice_val != CONSTANT)
     427              :     return;
     428              : 
     429   1270542333 :   if (TREE_OVERFLOW_P (val->value))
     430           58 :     val->value = drop_tree_overflow (val->value);
     431              : }
     432              : 
     433              : /* Return whether the lattice transition is valid.  */
     434              : 
     435              : static bool
     436    272349431 : valid_lattice_transition (const ccp_prop_value_t &old_val,
     437              :                           const ccp_prop_value_t &new_val)
     438              : {
     439              :   /* Lattice transitions must always be monotonically increasing in
     440              :      value.  */
     441    272349431 :   if (old_val.lattice_val < new_val.lattice_val)
     442              :     return true;
     443              : 
     444    170097165 :   if (old_val.lattice_val != new_val.lattice_val)
     445              :     return false;
     446              : 
     447    170097165 :   if (!old_val.value && !new_val.value)
     448              :     return true;
     449              : 
     450              :   /* Now both lattice values are CONSTANT.  */
     451              : 
     452              :   /* Allow arbitrary copy changes as we might look through PHI <a_1, ...>
     453              :      when only a single copy edge is executable.  */
     454    170062038 :   if (TREE_CODE (old_val.value) == SSA_NAME
     455        30756 :       && TREE_CODE (new_val.value) == SSA_NAME)
     456              :     return true;
     457              : 
     458              :   /* Allow transitioning from a constant to a copy.  */
     459    170031282 :   if (is_gimple_min_invariant (old_val.value)
     460    170031282 :       && TREE_CODE (new_val.value) == SSA_NAME)
     461              :     return true;
     462              : 
     463              :   /* Allow transitioning from PHI <&x, not executable> == &x
     464              :      to PHI <&x, &y> == common alignment.  */
     465    169797239 :   if (TREE_CODE (old_val.value) != INTEGER_CST
     466       443837 :       && TREE_CODE (new_val.value) == INTEGER_CST)
     467              :     return true;
     468              : 
     469              :   /* Bit-lattices have to agree in the still valid bits.  */
     470    169379549 :   if (TREE_CODE (old_val.value) == INTEGER_CST
     471    169353402 :       && TREE_CODE (new_val.value) == INTEGER_CST)
     472    338706804 :     return (wi::bit_and_not (wi::to_widest (old_val.value), new_val.mask)
     473    508060206 :             == wi::bit_and_not (wi::to_widest (new_val.value), new_val.mask));
     474              : 
     475              :   /* Otherwise constant values have to agree.  */
     476        26147 :   if (operand_equal_p (old_val.value, new_val.value, 0))
     477              :     return true;
     478              : 
     479              :   /* At least the kinds and types should agree now.  */
     480            0 :   if (TREE_CODE (old_val.value) != TREE_CODE (new_val.value)
     481            0 :       || !types_compatible_p (TREE_TYPE (old_val.value),
     482            0 :                               TREE_TYPE (new_val.value)))
     483              :     return false;
     484              : 
     485              :   /* For floats and !HONOR_NANS allow transitions from (partial) NaN
     486              :      to non-NaN.  */
     487            0 :   tree type = TREE_TYPE (new_val.value);
     488            0 :   if (SCALAR_FLOAT_TYPE_P (type)
     489            0 :       && !HONOR_NANS (type))
     490              :     {
     491            0 :       if (REAL_VALUE_ISNAN (TREE_REAL_CST (old_val.value)))
     492              :         return true;
     493              :     }
     494            0 :   else if (VECTOR_FLOAT_TYPE_P (type)
     495            0 :            && !HONOR_NANS (type))
     496              :     {
     497            0 :       unsigned int count
     498            0 :         = tree_vector_builder::binary_encoded_nelts (old_val.value,
     499            0 :                                                      new_val.value);
     500            0 :       for (unsigned int i = 0; i < count; ++i)
     501            0 :         if (!REAL_VALUE_ISNAN
     502              :                (TREE_REAL_CST (VECTOR_CST_ENCODED_ELT (old_val.value, i)))
     503            0 :             && !operand_equal_p (VECTOR_CST_ENCODED_ELT (old_val.value, i),
     504            0 :                                  VECTOR_CST_ENCODED_ELT (new_val.value, i), 0))
     505              :           return false;
     506              :       return true;
     507              :     }
     508            0 :   else if (COMPLEX_FLOAT_TYPE_P (type)
     509            0 :            && !HONOR_NANS (type))
     510              :     {
     511            0 :       if (!REAL_VALUE_ISNAN (TREE_REAL_CST (TREE_REALPART (old_val.value)))
     512            0 :           && !operand_equal_p (TREE_REALPART (old_val.value),
     513            0 :                                TREE_REALPART (new_val.value), 0))
     514              :         return false;
     515            0 :       if (!REAL_VALUE_ISNAN (TREE_REAL_CST (TREE_IMAGPART (old_val.value)))
     516            0 :           && !operand_equal_p (TREE_IMAGPART (old_val.value),
     517            0 :                                TREE_IMAGPART (new_val.value), 0))
     518            0 :         return false;
     519              :       return true;
     520              :     }
     521              :   return false;
     522              : }
     523              : 
     524              : /* Set the value for variable VAR to NEW_VAL.  Return true if the new
     525              :    value is different from VAR's previous value.  */
     526              : 
     527              : static bool
     528    272349431 : set_lattice_value (tree var, ccp_prop_value_t *new_val)
     529              : {
     530              :   /* We can deal with old UNINITIALIZED values just fine here.  */
     531    272349431 :   ccp_prop_value_t *old_val = &const_val[SSA_NAME_VERSION (var)];
     532              : 
     533    272349431 :   canonicalize_value (new_val);
     534              : 
     535              :   /* We have to be careful to not go up the bitwise lattice
     536              :      represented by the mask.  Instead of dropping to VARYING
     537              :      use the meet operator to retain a conservative value.
     538              :      Missed optimizations like PR65851 makes this necessary.
     539              :      It also ensures we converge to a stable lattice solution.  */
     540    272349431 :   if (old_val->lattice_val != UNINITIALIZED
     541              :       /* But avoid using meet for constant -> copy transitions.  */
     542    176594819 :       && !(old_val->lattice_val == CONSTANT
     543    176513566 :            && CONSTANT_CLASS_P (old_val->value)
     544    173506643 :            && new_val->lattice_val == CONSTANT
     545    169595267 :            && TREE_CODE (new_val->value) == SSA_NAME))
     546    176360776 :     ccp_lattice_meet (new_val, old_val);
     547              : 
     548    272349431 :   gcc_checking_assert (valid_lattice_transition (*old_val, *new_val));
     549              : 
     550              :   /* If *OLD_VAL and NEW_VAL are the same, return false to inform the
     551              :      caller that this was a non-transition.  */
     552    544698862 :   if (old_val->lattice_val != new_val->lattice_val
     553    272349431 :       || (new_val->lattice_val == CONSTANT
     554    170062038 :           && (TREE_CODE (new_val->value) != TREE_CODE (old_val->value)
     555    169410305 :               || (TREE_CODE (new_val->value) == INTEGER_CST
     556    169353402 :                   && (new_val->mask != old_val->mask
     557     32393937 :                       || (wi::bit_and_not (wi::to_widest (old_val->value),
     558              :                                            new_val->mask)
     559    320854982 :                           != wi::bit_and_not (wi::to_widest (new_val->value),
     560              :                                               new_val->mask))))
     561     16225420 :               || (TREE_CODE (new_val->value) != INTEGER_CST
     562        56903 :                   && !operand_equal_p (new_val->value, old_val->value, 0)))))
     563              :     {
     564              :       /* ???  We would like to delay creation of INTEGER_CSTs from
     565              :          partially constants here.  */
     566              : 
     567    256088884 :       if (dump_file && (dump_flags & TDF_DETAILS))
     568              :         {
     569           51 :           dump_lattice_value (dump_file, "Lattice value changed to ", *new_val);
     570           51 :           fprintf (dump_file, ".  Adding SSA edges to worklist.\n");
     571              :         }
     572              : 
     573    256088884 :       *old_val = *new_val;
     574              : 
     575    256088884 :       gcc_assert (new_val->lattice_val != UNINITIALIZED);
     576              :       return true;
     577              :     }
     578              : 
     579              :   return false;
     580              : }
     581              : 
     582              : static ccp_prop_value_t get_value_for_expr (tree, bool);
     583              : static ccp_prop_value_t bit_value_binop (enum tree_code, tree, tree, tree);
     584              : void bit_value_binop (enum tree_code, signop, int, widest_int *, widest_int *,
     585              :                       signop, int, const widest_int &, const widest_int &,
     586              :                       signop, int, const widest_int &, const widest_int &);
     587              : 
     588              : /* Return a widest_int that can be used for bitwise simplifications
     589              :    from VAL.  */
     590              : 
     591              : static widest_int
     592    324016499 : value_to_wide_int (ccp_prop_value_t val)
     593              : {
     594    324016499 :   if (val.value
     595    256790768 :       && TREE_CODE (val.value) == INTEGER_CST)
     596    256790768 :     return wi::to_widest (val.value);
     597              : 
     598     67225731 :   return 0;
     599              : }
     600              : 
     601              : /* Return the value for the address expression EXPR based on alignment
     602              :    information.  */
     603              : 
     604              : static ccp_prop_value_t
     605      8843728 : get_value_from_alignment (tree expr)
     606              : {
     607      8843728 :   tree type = TREE_TYPE (expr);
     608      8843728 :   ccp_prop_value_t val;
     609      8843728 :   unsigned HOST_WIDE_INT bitpos;
     610      8843728 :   unsigned int align;
     611              : 
     612      8843728 :   gcc_assert (TREE_CODE (expr) == ADDR_EXPR);
     613              : 
     614      8843728 :   get_pointer_alignment_1 (expr, &align, &bitpos);
     615      8843728 :   val.mask = wi::bit_and_not
     616     17687456 :     (POINTER_TYPE_P (type) || TYPE_UNSIGNED (type)
     617      8843728 :      ? wi::mask <widest_int> (TYPE_PRECISION (type), false)
     618            0 :      : -1,
     619     17687456 :      align / BITS_PER_UNIT - 1);
     620      8843728 :   val.lattice_val
     621     15005365 :     = wi::sext (val.mask, TYPE_PRECISION (type)) == -1 ? VARYING : CONSTANT;
     622      8843728 :   if (val.lattice_val == CONSTANT)
     623      6161637 :     val.value = build_int_cstu (type, bitpos / BITS_PER_UNIT);
     624              :   else
     625      2682091 :     val.value = NULL_TREE;
     626              : 
     627      8843728 :   return val;
     628              : }
     629              : 
     630              : /* Return the value for the tree operand EXPR.  If FOR_BITS_P is true
     631              :    return constant bits extracted from alignment information for
     632              :    invariant addresses.  */
     633              : 
     634              : static ccp_prop_value_t
     635    502078247 : get_value_for_expr (tree expr, bool for_bits_p)
     636              : {
     637    502078247 :   ccp_prop_value_t val;
     638              : 
     639    502078247 :   if (TREE_CODE (expr) == SSA_NAME)
     640              :     {
     641    313920251 :       ccp_prop_value_t *val_ = get_value (expr);
     642    313920251 :       if (val_)
     643    313920134 :         val = *val_;
     644              :       else
     645              :         {
     646          117 :           val.lattice_val = VARYING;
     647          117 :           val.value = NULL_TREE;
     648          117 :           val.mask = -1;
     649              :         }
     650    313920251 :       if (for_bits_p
     651    213073666 :           && val.lattice_val == CONSTANT)
     652              :         {
     653    146320400 :           if (TREE_CODE (val.value) == ADDR_EXPR)
     654       216955 :             val = get_value_from_alignment (val.value);
     655    146103445 :           else if (TREE_CODE (val.value) != INTEGER_CST)
     656              :             {
     657      7794060 :               val.lattice_val = VARYING;
     658      7794060 :               val.value = NULL_TREE;
     659      7794060 :               val.mask = -1;
     660              :             }
     661              :         }
     662              :       /* Fall back to a copy value.  */
     663              :       if (!for_bits_p
     664    100846585 :           && val.lattice_val == VARYING
     665      9746729 :           && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr))
     666              :         {
     667      9741540 :           val.lattice_val = CONSTANT;
     668      9741540 :           val.value = expr;
     669      9741540 :           val.mask = -1;
     670              :         }
     671              :     }
     672    188157996 :   else if (is_gimple_min_invariant (expr)
     673    188157996 :            && (!for_bits_p || TREE_CODE (expr) == INTEGER_CST))
     674              :     {
     675    152785616 :       val.lattice_val = CONSTANT;
     676    152785616 :       val.value = expr;
     677    152785616 :       val.mask = 0;
     678    152785616 :       canonicalize_value (&val);
     679              :     }
     680     35372380 :   else if (TREE_CODE (expr) == ADDR_EXPR)
     681      8626773 :     val = get_value_from_alignment (expr);
     682              :   else
     683              :     {
     684     26745607 :       val.lattice_val = VARYING;
     685     26745607 :       val.mask = -1;
     686     26745607 :       val.value = NULL_TREE;
     687              :     }
     688              : 
     689    502078247 :   if (val.lattice_val == VARYING
     690    103840706 :       && INTEGRAL_TYPE_P (TREE_TYPE (expr))
     691    573188070 :       && TYPE_UNSIGNED (TREE_TYPE (expr)))
     692     34525513 :     val.mask = wi::zext (val.mask, TYPE_PRECISION (TREE_TYPE (expr)));
     693              : 
     694    502078247 :   return val;
     695              : }
     696              : 
     697              : /* Return the likely CCP lattice value for STMT.
     698              : 
     699              :    If STMT has no operands, then return CONSTANT.
     700              : 
     701              :    Else if undefinedness of operands of STMT cause its value to be
     702              :    undefined, then return UNDEFINED.
     703              : 
     704              :    Else if any operands of STMT are constants, then return CONSTANT.
     705              : 
     706              :    Else return VARYING.  */
     707              : 
     708              : static ccp_lattice_t
     709    245451421 : likely_value (gimple *stmt)
     710              : {
     711    245451421 :   bool has_constant_operand, has_undefined_operand, all_undefined_operands;
     712    245451421 :   bool has_nsa_operand;
     713    245451421 :   tree use;
     714    245451421 :   ssa_op_iter iter;
     715    245451421 :   unsigned i;
     716              : 
     717    245451421 :   enum gimple_code code = gimple_code (stmt);
     718              : 
     719              :   /* This function appears to be called only for assignments, calls,
     720              :      conditionals, and switches, due to the logic in visit_stmt.  */
     721    245451421 :   gcc_assert (code == GIMPLE_ASSIGN
     722              :               || code == GIMPLE_CALL
     723              :               || code == GIMPLE_COND
     724              :               || code == GIMPLE_SWITCH);
     725              : 
     726              :   /* If the statement has volatile operands, it won't fold to a
     727              :      constant value.  */
     728    447477662 :   if (gimple_has_volatile_ops (stmt))
     729              :     return VARYING;
     730              : 
     731              :   /* .DEFERRED_INIT produces undefined except for AUTO_INIT_CXX26
     732              :      which produces varying because it is undefined that needs to have
     733              :      the same value in all uses.  */
     734    245451365 :   if (gimple_call_internal_p (stmt, IFN_DEFERRED_INIT))
     735              :     {
     736        42005 :       if (tree_to_uhwi (gimple_call_arg (stmt, 1)) & AUTO_INIT_CXX26)
     737              :         return VARYING;
     738              :       else
     739          550 :         return UNDEFINED;
     740              :     }
     741              : 
     742              :   /* Arrive here for more complex cases.  */
     743    245409360 :   has_constant_operand = false;
     744    245409360 :   has_undefined_operand = false;
     745    245409360 :   all_undefined_operands = true;
     746    245409360 :   has_nsa_operand = false;
     747    503532820 :   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
     748              :     {
     749    258123460 :       ccp_prop_value_t *val = get_value (use);
     750              : 
     751    258123460 :       if (val && val->lattice_val == UNDEFINED)
     752              :         has_undefined_operand = true;
     753              :       else
     754              :         all_undefined_operands = false;
     755              : 
     756    258123343 :       if (val && val->lattice_val == CONSTANT)
     757    164332860 :         has_constant_operand = true;
     758              : 
     759    258123460 :       if (SSA_NAME_IS_DEFAULT_DEF (use)
     760    258123460 :           || !prop_simulate_again_p (SSA_NAME_DEF_STMT (use)))
     761              :         has_nsa_operand = true;
     762              :     }
     763              : 
     764              :   /* There may be constants in regular rhs operands.  For calls we
     765              :      have to ignore lhs, fndecl and static chain, otherwise only
     766              :      the lhs.  */
     767    490818720 :   for (i = (is_gimple_call (stmt) ? 2 : 0) + gimple_has_lhs (stmt);
     768    741252782 :        i < gimple_num_ops (stmt); ++i)
     769              :     {
     770    495843422 :       tree op = gimple_op (stmt, i);
     771    495843422 :       if (!op || TREE_CODE (op) == SSA_NAME)
     772    323002858 :         continue;
     773    172840564 :       if (is_gimple_min_invariant (op))
     774              :         has_constant_operand = true;
     775     33552625 :       else if (TREE_CODE (op) == CONSTRUCTOR)
     776              :         {
     777              :           unsigned j;
     778              :           tree val;
     779    496437328 :           FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (op), j, val)
     780       593906 :             if (CONSTANT_CLASS_P (val))
     781              :               {
     782              :                 has_constant_operand = true;
     783              :                 break;
     784              :               }
     785              :         }
     786              :     }
     787              : 
     788    245409360 :   if (has_constant_operand)
     789    193704455 :     all_undefined_operands = false;
     790              : 
     791    245409360 :   if (has_undefined_operand
     792    245409360 :       && code == GIMPLE_CALL
     793    245409360 :       && gimple_call_internal_p (stmt))
     794        20188 :     switch (gimple_call_internal_fn (stmt))
     795              :       {
     796              :         /* These 3 builtins use the first argument just as a magic
     797              :            way how to find out a decl uid.  */
     798              :       case IFN_GOMP_SIMD_LANE:
     799              :       case IFN_GOMP_SIMD_VF:
     800              :       case IFN_GOMP_SIMD_LAST_LANE:
     801              :         has_undefined_operand = false;
     802              :         break;
     803              :       default:
     804              :         break;
     805              :       }
     806              : 
     807              :   /* If the operation combines operands like COMPLEX_EXPR make sure to
     808              :      not mark the result UNDEFINED if only one part of the result is
     809              :      undefined.  */
     810    245389295 :   if (has_undefined_operand && all_undefined_operands)
     811              :     return UNDEFINED;
     812    245326169 :   else if (code == GIMPLE_ASSIGN && has_undefined_operand)
     813              :     {
     814        63464 :       switch (gimple_assign_rhs_code (stmt))
     815              :         {
     816              :         /* Unary operators are handled with all_undefined_operands.  */
     817              :         case PLUS_EXPR:
     818              :         case MINUS_EXPR:
     819              :         case POINTER_PLUS_EXPR:
     820              :         case BIT_XOR_EXPR:
     821              :           /* Not MIN_EXPR, MAX_EXPR.  One VARYING operand may be selected.
     822              :              Not bitwise operators, one VARYING operand may specify the
     823              :              result completely.
     824              :              Not logical operators for the same reason, apart from XOR.
     825              :              Not COMPLEX_EXPR as one VARYING operand makes the result partly
     826              :              not UNDEFINED.  Not *DIV_EXPR, comparisons and shifts because
     827              :              the undefined operand may be promoted.  */
     828              :           return UNDEFINED;
     829              : 
     830              :         case ADDR_EXPR:
     831              :           /* If any part of an address is UNDEFINED, like the index
     832              :              of an ARRAY_EXPR, then treat the result as UNDEFINED.  */
     833              :           return UNDEFINED;
     834              : 
     835              :         default:
     836              :           ;
     837              :         }
     838              :     }
     839              :   /* If there was an UNDEFINED operand but the result may be not UNDEFINED
     840              :      fall back to CONSTANT.  During iteration UNDEFINED may still drop
     841              :      to CONSTANT.  */
     842    245284130 :   if (has_undefined_operand)
     843              :     return CONSTANT;
     844              : 
     845              :   /* We do not consider virtual operands here -- load from read-only
     846              :      memory may have only VARYING virtual operands, but still be
     847              :      constant.  Also we can combine the stmt with definitions from
     848              :      operands whose definitions are not simulated again.  */
     849    245110749 :   if (has_constant_operand
     850    245110749 :       || has_nsa_operand
     851    245110749 :       || gimple_references_memory_p (stmt))
     852    245102869 :     return CONSTANT;
     853              : 
     854              :   return VARYING;
     855              : }
     856              : 
     857              : /* Returns true if STMT cannot be constant.  */
     858              : 
     859              : static bool
     860    343827268 : surely_varying_stmt_p (gimple *stmt)
     861              : {
     862              :   /* If the statement has operands that we cannot handle, it cannot be
     863              :      constant.  */
     864    483241767 :   if (gimple_has_volatile_ops (stmt))
     865              :     return true;
     866              : 
     867              :   /* If it is a call and does not return a value or is not a
     868              :      builtin and not an indirect call or a call to function with
     869              :      assume_aligned/alloc_align attribute, it is varying.  */
     870    333899329 :   if (is_gimple_call (stmt))
     871              :     {
     872     17180042 :       tree fndecl, fntype = gimple_call_fntype (stmt);
     873     17180042 :       if (!gimple_call_lhs (stmt)
     874     17180042 :           || ((fndecl = gimple_call_fndecl (stmt)) != NULL_TREE
     875      6909985 :               && !fndecl_built_in_p (fndecl)
     876      4081873 :               && !lookup_attribute ("assume_aligned",
     877      4081873 :                                     TYPE_ATTRIBUTES (fntype))
     878      4081831 :               && !lookup_attribute ("alloc_align",
     879      4081831 :                                     TYPE_ATTRIBUTES (fntype))))
     880              :         return true;
     881              :     }
     882              : 
     883              :   /* Any other store operation is not interesting.  */
     884    429025805 :   else if (gimple_vdef (stmt))
     885              :     return true;
     886              : 
     887              :   /* Anything other than assignments and conditional jumps are not
     888              :      interesting for CCP.  */
     889    289908647 :   if (gimple_code (stmt) != GIMPLE_ASSIGN
     890              :       && gimple_code (stmt) != GIMPLE_COND
     891              :       && gimple_code (stmt) != GIMPLE_SWITCH
     892              :       && gimple_code (stmt) != GIMPLE_CALL)
     893    204562077 :     return true;
     894              : 
     895              :   return false;
     896              : }
     897              : 
     898              : /* Initialize local data structures for CCP.  */
     899              : 
     900              : static void
     901      5714131 : ccp_initialize (void)
     902              : {
     903      5714131 :   basic_block bb;
     904              : 
     905      5714131 :   n_const_val = num_ssa_names;
     906      5714131 :   const_val = XCNEWVEC (ccp_prop_value_t, n_const_val);
     907              : 
     908              :   /* Initialize simulation flags for PHI nodes and statements.  */
     909     55171176 :   FOR_EACH_BB_FN (bb, cfun)
     910              :     {
     911     49457045 :       gimple_stmt_iterator i;
     912              : 
     913    476887724 :       for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
     914              :         {
     915    377973634 :           gimple *stmt = gsi_stmt (i);
     916    377973634 :           bool is_varying;
     917              : 
     918              :           /* If the statement is a control insn, then we do not
     919              :              want to avoid simulating the statement once.  Failure
     920              :              to do so means that those edges will never get added.  */
     921    377973634 :           if (stmt_ends_bb_p (stmt))
     922              :             is_varying = false;
     923              :           else
     924    343827268 :             is_varying = surely_varying_stmt_p (stmt);
     925              : 
     926    343827268 :           if (is_varying)
     927              :             {
     928    258480698 :               tree def;
     929    258480698 :               ssa_op_iter iter;
     930              : 
     931              :               /* If the statement will not produce a constant, mark
     932              :                  all its outputs VARYING.  */
     933    315285982 :               FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
     934     56805284 :                 set_value_varying (def);
     935              :             }
     936    377973634 :           prop_set_simulate_again (stmt, !is_varying);
     937              :         }
     938              :     }
     939              : 
     940              :   /* Now process PHI nodes.  We never clear the simulate_again flag on
     941              :      phi nodes, since we do not know which edges are executable yet,
     942              :      except for phi nodes for virtual operands when we do not do store ccp.  */
     943     55171176 :   FOR_EACH_BB_FN (bb, cfun)
     944              :     {
     945     49457045 :       gphi_iterator i;
     946              : 
     947     67386040 :       for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
     948              :         {
     949     17928995 :           gphi *phi = i.phi ();
     950              : 
     951     35857990 :           if (virtual_operand_p (gimple_phi_result (phi)))
     952      8118891 :             prop_set_simulate_again (phi, false);
     953              :           else
     954      9810104 :             prop_set_simulate_again (phi, true);
     955              :         }
     956              :     }
     957      5714131 : }
     958              : 
     959              : /* Debug count support. Reset the values of ssa names
     960              :    VARYING when the total number ssa names analyzed is
     961              :    beyond the debug count specified.  */
     962              : 
     963              : static void
     964      5714131 : do_dbg_cnt (void)
     965              : {
     966      5714131 :   unsigned i;
     967    232888840 :   for (i = 0; i < num_ssa_names; i++)
     968              :     {
     969    227174709 :       if (!dbg_cnt (ccp))
     970              :         {
     971            0 :           const_val[i].lattice_val = VARYING;
     972            0 :           const_val[i].mask = -1;
     973            0 :           const_val[i].value = NULL_TREE;
     974              :         }
     975              :     }
     976      5714131 : }
     977              : 
     978              : 
     979              : /* We want to provide our own GET_VALUE and FOLD_STMT virtual methods.  */
     980     22856524 : class ccp_folder : public substitute_and_fold_engine
     981              : {
     982              :  public:
     983              :   tree value_of_expr (tree, gimple *) final override;
     984              :   bool fold_stmt (gimple_stmt_iterator *) final override;
     985              : };
     986              : 
     987              : /* This method just wraps GET_CONSTANT_VALUE for now.  Over time
     988              :    naked calls to GET_CONSTANT_VALUE should be eliminated in favor
     989              :    of calling member functions.  */
     990              : 
     991              : tree
     992    308411917 : ccp_folder::value_of_expr (tree op, gimple *)
     993              : {
     994    308411917 :   return get_constant_value (op);
     995              : }
     996              : 
     997              : /* Do final substitution of propagated values, cleanup the flowgraph and
     998              :    free allocated storage.  If NONZERO_P, record nonzero bits.
     999              : 
    1000              :    Return TRUE when something was optimized.  */
    1001              : 
    1002              : static bool
    1003      5714131 : ccp_finalize (bool nonzero_p)
    1004              : {
    1005      5714131 :   bool something_changed;
    1006      5714131 :   unsigned i;
    1007      5714131 :   tree name;
    1008              : 
    1009      5714131 :   do_dbg_cnt ();
    1010              : 
    1011              :   /* Derive nonzero and alignment bits from partially constant integers.  */
    1012    232888840 :   FOR_EACH_SSA_NAME (i, name, cfun)
    1013              :     {
    1014    185489568 :       ccp_prop_value_t *val;
    1015              : 
    1016    338705860 :       if (!POINTER_TYPE_P (TREE_TYPE (name))
    1017    335361065 :           && (!INTEGRAL_TYPE_P (TREE_TYPE (name))
    1018              :               /* Don't record nonzero bits before IPA to avoid
    1019              :                  using too much memory.  */
    1020     65561313 :               || !nonzero_p))
    1021    170140401 :         continue;
    1022              : 
    1023     99272527 :       val = get_value (name);
    1024    183195887 :       if (val->lattice_val != CONSTANT
    1025     27907185 :           || TREE_CODE (val->value) != INTEGER_CST
    1026    127179712 :           || val->mask == 0)
    1027     83923360 :         continue;
    1028              : 
    1029     15349167 :       unsigned int precision = TYPE_PRECISION (TREE_TYPE (val->value));
    1030     15349167 :       wide_int value = wi::to_wide (val->value);
    1031     15349167 :       wide_int mask = wide_int::from (val->mask, precision, UNSIGNED);
    1032     15349474 :       value = value & ~mask;
    1033     15349167 :       set_bitmask (name, value, mask);
    1034     15349474 :     }
    1035              : 
    1036              :   /* Perform substitutions based on the known constant values.  */
    1037      5714131 :   class ccp_folder ccp_folder;
    1038      5714131 :   something_changed = ccp_folder.substitute_and_fold ();
    1039              : 
    1040      5714131 :   free (const_val);
    1041      5714131 :   const_val = NULL;
    1042      5714131 :   return something_changed;
    1043      5714131 : }
    1044              : 
    1045              : 
    1046              : /* Compute the meet operator between *VAL1 and *VAL2.  Store the result
    1047              :    in VAL1.
    1048              : 
    1049              :                 any  M UNDEFINED   = any
    1050              :                 any  M VARYING     = VARYING
    1051              :                 Ci   M Cj          = Ci         if (i == j)
    1052              :                 Ci   M Cj          = VARYING    if (i != j)
    1053              :    */
    1054              : 
    1055              : static void
    1056    243364295 : ccp_lattice_meet (ccp_prop_value_t *val1, ccp_prop_value_t *val2)
    1057              : {
    1058    243364295 :   if (val1->lattice_val == UNDEFINED
    1059              :       /* For UNDEFINED M SSA we can't always SSA because its definition
    1060              :          may not dominate the PHI node.  Doing optimistic copy propagation
    1061              :          also causes a lot of gcc.dg/uninit-pred*.c FAILs.  */
    1062       168859 :       && (val2->lattice_val != CONSTANT
    1063        95542 :           || TREE_CODE (val2->value) != SSA_NAME))
    1064              :     {
    1065              :       /* UNDEFINED M any = any   */
    1066        93921 :       *val1 = *val2;
    1067              :     }
    1068    243270374 :   else if (val2->lattice_val == UNDEFINED
    1069              :            /* See above.  */
    1070        95857 :            && (val1->lattice_val != CONSTANT
    1071        61519 :                || TREE_CODE (val1->value) != SSA_NAME))
    1072              :     {
    1073              :       /* any M UNDEFINED = any
    1074              :          Nothing to do.  VAL1 already contains the value we want.  */
    1075              :       ;
    1076              :     }
    1077    243199713 :   else if (val1->lattice_val == VARYING
    1078    236970882 :            || val2->lattice_val == VARYING)
    1079              :     {
    1080              :       /* any M VARYING = VARYING.  */
    1081      6246259 :       val1->lattice_val = VARYING;
    1082      6246259 :       val1->mask = -1;
    1083      6246259 :       val1->value = NULL_TREE;
    1084              :     }
    1085    236953454 :   else if (val1->lattice_val == CONSTANT
    1086    236878516 :            && val2->lattice_val == CONSTANT
    1087    236853320 :            && TREE_CODE (val1->value) == INTEGER_CST
    1088    231710569 :            && TREE_CODE (val2->value) == INTEGER_CST)
    1089              :     {
    1090              :       /* Ci M Cj = Ci           if (i == j)
    1091              :          Ci M Cj = VARYING      if (i != j)
    1092              : 
    1093              :          For INTEGER_CSTs mask unequal bits.  If no equal bits remain,
    1094              :          drop to varying.  */
    1095    459361556 :       val1->mask = (val1->mask | val2->mask
    1096    459361556 :                     | (wi::to_widest (val1->value)
    1097    689042334 :                        ^ wi::to_widest (val2->value)));
    1098    229875658 :       if (wi::sext (val1->mask, TYPE_PRECISION (TREE_TYPE (val1->value))) == -1)
    1099              :         {
    1100       524537 :           val1->lattice_val = VARYING;
    1101       524537 :           val1->value = NULL_TREE;
    1102              :         }
    1103              :     }
    1104      7272676 :   else if (val1->lattice_val == CONSTANT
    1105      7197738 :            && val2->lattice_val == CONSTANT
    1106     14445218 :            && operand_equal_p (val1->value, val2->value, 0))
    1107              :     {
    1108              :       /* Ci M Cj = Ci           if (i == j)
    1109              :          Ci M Cj = VARYING      if (i != j)
    1110              : 
    1111              :          VAL1 already contains the value we want for equivalent values.  */
    1112              :     }
    1113      6850809 :   else if (val1->lattice_val == CONSTANT
    1114      6775871 :            && val2->lattice_val == CONSTANT
    1115      6750675 :            && (TREE_CODE (val1->value) == ADDR_EXPR
    1116      6548010 :                || TREE_CODE (val2->value) == ADDR_EXPR))
    1117              :     {
    1118              :       /* When not equal addresses are involved try meeting for
    1119              :          alignment.  */
    1120       765351 :       ccp_prop_value_t tem = *val2;
    1121       765351 :       if (TREE_CODE (val1->value) == ADDR_EXPR)
    1122       202665 :         *val1 = get_value_for_expr (val1->value, true);
    1123       765351 :       if (TREE_CODE (val2->value) == ADDR_EXPR)
    1124       662386 :         tem = get_value_for_expr (val2->value, true);
    1125       765351 :       ccp_lattice_meet (val1, &tem);
    1126       765351 :     }
    1127              :   else
    1128              :     {
    1129              :       /* Any other combination is VARYING.  */
    1130      6085458 :       val1->lattice_val = VARYING;
    1131      6085458 :       val1->mask = -1;
    1132      6085458 :       val1->value = NULL_TREE;
    1133              :     }
    1134    243364295 : }
    1135              : 
    1136              : 
    1137              : /* Loop through the PHI_NODE's parameters for BLOCK and compare their
    1138              :    lattice values to determine PHI_NODE's lattice value.  The value of a
    1139              :    PHI node is determined calling ccp_lattice_meet with all the arguments
    1140              :    of the PHI node that are incoming via executable edges.  */
    1141              : 
    1142              : enum ssa_prop_result
    1143     70323190 : ccp_propagate::visit_phi (gphi *phi)
    1144              : {
    1145     70323190 :   unsigned i;
    1146     70323190 :   ccp_prop_value_t new_val;
    1147              : 
    1148     70323190 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1149              :     {
    1150            1 :       fprintf (dump_file, "\nVisiting PHI node: ");
    1151            1 :       print_gimple_stmt (dump_file, phi, 0, dump_flags);
    1152              :     }
    1153              : 
    1154     70323190 :   new_val.lattice_val = UNDEFINED;
    1155     70323190 :   new_val.value = NULL_TREE;
    1156     70323190 :   new_val.mask = 0;
    1157              : 
    1158     70323190 :   bool first = true;
    1159     70323190 :   bool non_exec_edge = false;
    1160    206905076 :   for (i = 0; i < gimple_phi_num_args (phi); i++)
    1161              :     {
    1162              :       /* Compute the meet operator over all the PHI arguments flowing
    1163              :          through executable edges.  */
    1164    142987406 :       edge e = gimple_phi_arg_edge (phi, i);
    1165              : 
    1166    142987406 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1167              :         {
    1168            6 :           fprintf (dump_file,
    1169              :               "\tArgument #%d (%d -> %d %sexecutable)\n",
    1170            3 :               i, e->src->index, e->dest->index,
    1171            3 :               (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
    1172              :         }
    1173              : 
    1174              :       /* If the incoming edge is executable, Compute the meet operator for
    1175              :          the existing value of the PHI node and the current PHI argument.  */
    1176    142987406 :       if (e->flags & EDGE_EXECUTABLE)
    1177              :         {
    1178    136561358 :           tree arg = gimple_phi_arg (phi, i)->def;
    1179    136561358 :           ccp_prop_value_t arg_val = get_value_for_expr (arg, false);
    1180              : 
    1181    136561358 :           if (first)
    1182              :             {
    1183     70323190 :               new_val = arg_val;
    1184     70323190 :               first = false;
    1185              :             }
    1186              :           else
    1187     66238168 :             ccp_lattice_meet (&new_val, &arg_val);
    1188              : 
    1189    136561358 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1190              :             {
    1191            3 :               fprintf (dump_file, "\t");
    1192            3 :               print_generic_expr (dump_file, arg, dump_flags);
    1193            3 :               dump_lattice_value (dump_file, "\tValue: ", arg_val);
    1194            3 :               fprintf (dump_file, "\n");
    1195              :             }
    1196              : 
    1197    136561358 :           if (new_val.lattice_val == VARYING)
    1198              :             break;
    1199    136561358 :         }
    1200              :       else
    1201              :         non_exec_edge = true;
    1202              :     }
    1203              : 
    1204              :   /* In case there were non-executable edges and the value is a copy
    1205              :      make sure its definition dominates the PHI node.  */
    1206     70323190 :   if (non_exec_edge
    1207      6084126 :       && new_val.lattice_val == CONSTANT
    1208      5979139 :       && TREE_CODE (new_val.value) == SSA_NAME
    1209      1542500 :       && ! SSA_NAME_IS_DEFAULT_DEF (new_val.value)
    1210     71724088 :       && ! dominated_by_p (CDI_DOMINATORS, gimple_bb (phi),
    1211      1400898 :                            gimple_bb (SSA_NAME_DEF_STMT (new_val.value))))
    1212              :     {
    1213        84074 :       new_val.lattice_val = VARYING;
    1214        84074 :       new_val.value = NULL_TREE;
    1215        84074 :       new_val.mask = -1;
    1216              :     }
    1217              : 
    1218     70323190 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1219              :     {
    1220            1 :       dump_lattice_value (dump_file, "\n    PHI node value: ", new_val);
    1221            1 :       fprintf (dump_file, "\n\n");
    1222              :     }
    1223              : 
    1224              :   /* Make the transition to the new value.  */
    1225     70323190 :   if (set_lattice_value (gimple_phi_result (phi), &new_val))
    1226              :     {
    1227     68552901 :       if (new_val.lattice_val == VARYING)
    1228              :         return SSA_PROP_VARYING;
    1229              :       else
    1230     61938650 :         return SSA_PROP_INTERESTING;
    1231              :     }
    1232              :   else
    1233              :     return SSA_PROP_NOT_INTERESTING;
    1234     70323190 : }
    1235              : 
    1236              : /* Return the constant value for OP or OP otherwise.  */
    1237              : 
    1238              : static tree
    1239    295927928 : valueize_op (tree op)
    1240              : {
    1241    295927928 :   if (TREE_CODE (op) == SSA_NAME)
    1242              :     {
    1243    283680547 :       tree tem = get_constant_value (op);
    1244    283680547 :       if (tem)
    1245     28216016 :         return tem;
    1246              :     }
    1247              :   return op;
    1248              : }
    1249              : 
    1250              : /* Return the constant value for OP, but signal to not follow SSA
    1251              :    edges if the definition may be simulated again.  */
    1252              : 
    1253              : static tree
    1254   3844290186 : valueize_op_1 (tree op)
    1255              : {
    1256   3844290186 :   if (TREE_CODE (op) == SSA_NAME)
    1257              :     {
    1258              :       /* If the definition may be simulated again we cannot follow
    1259              :          this SSA edge as the SSA propagator does not necessarily
    1260              :          re-visit the use.  */
    1261   3844290186 :       gimple *def_stmt = SSA_NAME_DEF_STMT (op);
    1262   3844290186 :       if (!gimple_nop_p (def_stmt)
    1263   3844290186 :           && prop_simulate_again_p (def_stmt))
    1264              :         return NULL_TREE;
    1265   1924046738 :       tree tem = get_constant_value (op);
    1266   1924046738 :       if (tem)
    1267      4450892 :         return tem;
    1268              :     }
    1269              :   return op;
    1270              : }
    1271              : 
    1272              : /* CCP specific front-end to the non-destructive constant folding
    1273              :    routines.
    1274              : 
    1275              :    Attempt to simplify the RHS of STMT knowing that one or more
    1276              :    operands are constants.
    1277              : 
    1278              :    If simplification is possible, return the simplified RHS,
    1279              :    otherwise return the original RHS or NULL_TREE.  */
    1280              : 
    1281              : static tree
    1282    245276250 : ccp_fold (gimple *stmt)
    1283              : {
    1284    245276250 :   switch (gimple_code (stmt))
    1285              :     {
    1286       104307 :     case GIMPLE_SWITCH:
    1287       104307 :       {
    1288              :         /* Return the constant switch index.  */
    1289       104307 :         return valueize_op (gimple_switch_index (as_a <gswitch *> (stmt)));
    1290              :       }
    1291              : 
    1292    245171943 :     case GIMPLE_COND:
    1293    245171943 :     case GIMPLE_ASSIGN:
    1294    245171943 :     case GIMPLE_CALL:
    1295    245171943 :       return gimple_fold_stmt_to_constant_1 (stmt,
    1296    245171943 :                                              valueize_op, valueize_op_1);
    1297              : 
    1298            0 :     default:
    1299            0 :       gcc_unreachable ();
    1300              :     }
    1301              : }
    1302              : 
    1303              : /* Determine the minimum and maximum values, *MIN and *MAX respectively,
    1304              :    represented by the mask pair VAL and MASK with signedness SGN and
    1305              :    precision PRECISION.  */
    1306              : 
    1307              : static void
    1308     29379294 : value_mask_to_min_max (widest_int *min, widest_int *max,
    1309              :                        const widest_int &val, const widest_int &mask,
    1310              :                        signop sgn, int precision)
    1311              : {
    1312     29379294 :   *min = wi::bit_and_not (val, mask);
    1313     29379294 :   *max = val | mask;
    1314     29379294 :   if (sgn == SIGNED && wi::neg_p (mask))
    1315              :     {
    1316      7043644 :       widest_int sign_bit = wi::lshift (1, precision - 1);
    1317      7043644 :       *min ^= sign_bit;
    1318      7043644 :       *max ^= sign_bit;
    1319              :       /* MAX is zero extended, and MIN is sign extended.  */
    1320      7043644 :       *min = wi::ext (*min, precision, sgn);
    1321      7043692 :       *max = wi::ext (*max, precision, sgn);
    1322      7043644 :     }
    1323     29379294 : }
    1324              : 
    1325              : /* Apply the operation CODE in type TYPE to the value, mask pair
    1326              :    RVAL and RMASK representing a value of type RTYPE and set
    1327              :    the value, mask pair *VAL and *MASK to the result.  */
    1328              : 
    1329              : void
    1330     98560314 : bit_value_unop (enum tree_code code, signop type_sgn, int type_precision,
    1331              :                 widest_int *val, widest_int *mask,
    1332              :                 signop rtype_sgn, int rtype_precision,
    1333              :                 const widest_int &rval, const widest_int &rmask)
    1334              : {
    1335     98565311 :   switch (code)
    1336              :     {
    1337       733012 :     case BIT_NOT_EXPR:
    1338       733012 :       *mask = rmask;
    1339       733012 :       *val = ~rval;
    1340       733012 :       break;
    1341              : 
    1342       315748 :     case NEGATE_EXPR:
    1343       315748 :       {
    1344       315748 :         widest_int temv, temm;
    1345              :         /* Return ~rval + 1.  */
    1346       315748 :         bit_value_unop (BIT_NOT_EXPR, type_sgn, type_precision, &temv, &temm,
    1347              :                         type_sgn, type_precision, rval, rmask);
    1348       315748 :         bit_value_binop (PLUS_EXPR, type_sgn, type_precision, val, mask,
    1349              :                          type_sgn, type_precision, temv, temm,
    1350       631496 :                          type_sgn, type_precision, 1, 0);
    1351       315748 :         break;
    1352       315748 :       }
    1353              : 
    1354     97383652 :     CASE_CONVERT:
    1355     97383652 :       {
    1356              :         /* First extend mask and value according to the original type.  */
    1357     97383652 :         *mask = wi::ext (rmask, rtype_precision, rtype_sgn);
    1358     97383652 :         *val = wi::ext (rval, rtype_precision, rtype_sgn);
    1359              : 
    1360              :         /* Then extend mask and value according to the target type.  */
    1361     97383652 :         *mask = wi::ext (*mask, type_precision, type_sgn);
    1362     97383652 :         *val = wi::ext (*val, type_precision, type_sgn);
    1363     97383652 :         break;
    1364              :       }
    1365              : 
    1366       132896 :     case ABS_EXPR:
    1367       132896 :     case ABSU_EXPR:
    1368       132896 :       if (wi::sext (rmask, rtype_precision) == -1)
    1369              :         {
    1370       121202 :           *mask = -1;
    1371       121202 :           *val = 0;
    1372              :         }
    1373        11694 :       else if (wi::neg_p (rmask))
    1374              :         {
    1375              :           /* Result is either rval or -rval.  */
    1376          300 :           widest_int temv, temm;
    1377          300 :           bit_value_unop (NEGATE_EXPR, rtype_sgn, rtype_precision, &temv,
    1378              :                           &temm, type_sgn, type_precision, rval, rmask);
    1379          300 :           temm |= (rmask | (rval ^ temv));
    1380              :           /* Extend the result.  */
    1381          300 :           *mask = wi::ext (temm, type_precision, type_sgn);
    1382          300 :           *val = wi::ext (temv, type_precision, type_sgn);
    1383          300 :         }
    1384        11394 :       else if (wi::neg_p (rval))
    1385              :         {
    1386              :           bit_value_unop (NEGATE_EXPR, type_sgn, type_precision, val, mask,
    1387              :                           type_sgn, type_precision, rval, rmask);
    1388              :         }
    1389              :       else
    1390              :         {
    1391         6397 :           *mask = rmask;
    1392         6397 :           *val = rval;
    1393              :         }
    1394              :       break;
    1395              : 
    1396            3 :     default:
    1397            3 :       *mask = -1;
    1398            3 :       *val = 0;
    1399            3 :       break;
    1400              :     }
    1401     98560314 : }
    1402              : 
    1403              : /* Determine the mask pair *VAL and *MASK from multiplying the
    1404              :    argument mask pair RVAL, RMASK by the unsigned constant C.  */
    1405              : static void
    1406     31986919 : bit_value_mult_const (signop sgn, int width,
    1407              :                       widest_int *val, widest_int *mask,
    1408              :                       const widest_int &rval, const widest_int &rmask,
    1409              :                       widest_int c)
    1410              : {
    1411     31986919 :   widest_int sum_mask = 0;
    1412              : 
    1413              :   /* Ensure rval_lo only contains known bits.  */
    1414     31986919 :   widest_int rval_lo = wi::bit_and_not (rval, rmask);
    1415              : 
    1416     31986919 :   if (rval_lo != 0)
    1417              :     {
    1418              :       /* General case (some bits of multiplicand are known set).  */
    1419       867770 :       widest_int sum_val = 0;
    1420      2090659 :       while (c != 0)
    1421              :         {
    1422              :           /* Determine the lowest bit set in the multiplier.  */
    1423      1222889 :           int bitpos = wi::ctz (c);
    1424      1222889 :           widest_int term_mask = rmask << bitpos;
    1425      1222889 :           widest_int term_val = rval_lo << bitpos;
    1426              : 
    1427              :           /* sum += term.  */
    1428      1222889 :           widest_int lo = sum_val + term_val;
    1429      1287849 :           widest_int hi = (sum_val | sum_mask) + (term_val | term_mask);
    1430      1352811 :           sum_mask |= term_mask | (lo ^ hi);
    1431      1222889 :           sum_val = lo;
    1432              : 
    1433              :           /* Clear this bit in the multiplier.  */
    1434      1222889 :           c ^= wi::lshift (1, bitpos);
    1435      1352809 :         }
    1436              :       /* Correctly extend the result value.  */
    1437       867770 :       *val = wi::ext (sum_val, width, sgn);
    1438       867770 :     }
    1439              :   else
    1440              :     {
    1441              :       /* Special case (no bits of multiplicand are known set).  */
    1442     80642277 :       while (c != 0)
    1443              :         {
    1444              :           /* Determine the lowest bit set in the multiplier.  */
    1445     49523128 :           int bitpos = wi::ctz (c);
    1446     49523128 :           widest_int term_mask = rmask << bitpos;
    1447              : 
    1448              :           /* sum += term.  */
    1449     49523128 :           widest_int hi = sum_mask + term_mask;
    1450     49523128 :           sum_mask |= term_mask | hi;
    1451              : 
    1452              :           /* Clear this bit in the multiplier.  */
    1453     49523137 :           c ^= wi::lshift (1, bitpos);
    1454     49523208 :         }
    1455     31119149 :       *val = 0;
    1456              :     }
    1457              : 
    1458              :   /* Correctly extend the result mask.  */
    1459     32051900 :   *mask = wi::ext (sum_mask, width, sgn);
    1460     31986919 : }
    1461              : 
    1462              : /* Fill up to MAX values in the BITS array with values representing
    1463              :    each of the non-zero bits in the value X.  Returns the number of
    1464              :    bits in X (capped at the maximum value MAX).  For example, an X
    1465              :    value 11, places 1, 2 and 8 in BITS and returns the value 3.  */
    1466              : 
    1467              : static unsigned int
    1468       344570 : get_individual_bits (widest_int *bits, widest_int x, unsigned int max)
    1469              : {
    1470       344570 :   unsigned int count = 0;
    1471      1369437 :   while (count < max && x != 0)
    1472              :     {
    1473      1024867 :       int bitpos = wi::ctz (x);
    1474      1024867 :       bits[count] = wi::lshift (1, bitpos);
    1475      1024867 :       x ^= bits[count];
    1476      1024867 :       count++;
    1477              :     }
    1478       344570 :   return count;
    1479              : }
    1480              : 
    1481              : /* Array of 2^N - 1 values representing the bits flipped between
    1482              :    consecutive Gray codes.  This is used to efficiently enumerate
    1483              :    all permutations on N bits using XOR.  */
    1484              : static const unsigned char gray_code_bit_flips[63] = {
    1485              :   0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
    1486              :   0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
    1487              :   0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
    1488              :   0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
    1489              : };
    1490              : 
    1491              : /* Apply the operation CODE in type TYPE to the value, mask pairs
    1492              :    R1VAL, R1MASK and R2VAL, R2MASK representing a values of type R1TYPE
    1493              :    and R2TYPE and set the value, mask pair *VAL and *MASK to the result.  */
    1494              : 
    1495              : void
    1496    286270440 : bit_value_binop (enum tree_code code, signop sgn, int width,
    1497              :                  widest_int *val, widest_int *mask,
    1498              :                  signop r1type_sgn, int r1type_precision,
    1499              :                  const widest_int &r1val, const widest_int &r1mask,
    1500              :                  signop r2type_sgn, int r2type_precision ATTRIBUTE_UNUSED,
    1501              :                  const widest_int &r2val, const widest_int &r2mask)
    1502              : {
    1503    286270440 :   bool swap_p = false;
    1504              : 
    1505              :   /* Assume we'll get a constant result.  Use an initial non varying
    1506              :      value, we fall back to varying in the end if necessary.  */
    1507    286270440 :   *mask = -1;
    1508              :   /* Ensure that VAL is initialized (to any value).  */
    1509    286270440 :   *val = 0;
    1510              : 
    1511    286270440 :   switch (code)
    1512              :     {
    1513      9716501 :     case BIT_AND_EXPR:
    1514              :       /* The mask is constant where there is a known not
    1515              :          set bit, (m1 | m2) & ((v1 | m1) & (v2 | m2)) */
    1516      9716501 :       *mask = (r1mask | r2mask) & (r1val | r1mask) & (r2val | r2mask);
    1517      9716501 :       *val = r1val & r2val;
    1518      9716501 :       break;
    1519              : 
    1520      3195070 :     case BIT_IOR_EXPR:
    1521              :       /* The mask is constant where there is a known
    1522              :          set bit, (m1 | m2) & ~((v1 & ~m1) | (v2 & ~m2)).  */
    1523      6390140 :       *mask = wi::bit_and_not (r1mask | r2mask,
    1524      6390140 :                                wi::bit_and_not (r1val, r1mask)
    1525     12780280 :                                | wi::bit_and_not (r2val, r2mask));
    1526      3195070 :       *val = r1val | r2val;
    1527      3195070 :       break;
    1528              : 
    1529       265384 :     case BIT_XOR_EXPR:
    1530              :       /* m1 | m2  */
    1531       265384 :       *mask = r1mask | r2mask;
    1532       265384 :       *val = r1val ^ r2val;
    1533       265384 :       break;
    1534              : 
    1535        27397 :     case LROTATE_EXPR:
    1536        27397 :     case RROTATE_EXPR:
    1537        27397 :       if (r2mask == 0)
    1538              :         {
    1539        16687 :           widest_int shift = r2val;
    1540        16687 :           if (shift == 0)
    1541              :             {
    1542          266 :               *mask = r1mask;
    1543          266 :               *val = r1val;
    1544              :             }
    1545              :           else
    1546              :             {
    1547        16421 :               if (wi::neg_p (shift, r2type_sgn))
    1548              :                 {
    1549            4 :                   shift = -shift;
    1550            4 :                   if (code == RROTATE_EXPR)
    1551              :                     code = LROTATE_EXPR;
    1552              :                   else
    1553              :                     code = RROTATE_EXPR;
    1554              :                 }
    1555        16417 :               if (code == RROTATE_EXPR)
    1556              :                 {
    1557        15978 :                   *mask = wi::rrotate (r1mask, shift, width);
    1558        15978 :                   *val = wi::rrotate (r1val, shift, width);
    1559              :                 }
    1560              :               else
    1561              :                 {
    1562          443 :                   *mask = wi::lrotate (r1mask, shift, width);
    1563          443 :                   *val = wi::lrotate (r1val, shift, width);
    1564              :                 }
    1565        16421 :               *mask = wi::ext (*mask, width, sgn);
    1566        16421 :               *val = wi::ext (*val, width, sgn);
    1567              :             }
    1568        16687 :         }
    1569        21420 :       else if (wi::ltu_p (r2val | r2mask, width)
    1570        35049 :                && wi::popcount (r2mask) <= 4)
    1571              :         {
    1572        29619 :           widest_int bits[4];
    1573         3291 :           widest_int res_val, res_mask;
    1574         3291 :           widest_int tmp_val, tmp_mask;
    1575         3291 :           widest_int shift = wi::bit_and_not (r2val, r2mask);
    1576         3291 :           unsigned int bit_count = get_individual_bits (bits, r2mask, 4);
    1577         3291 :           unsigned int count = (1 << bit_count) - 1;
    1578              : 
    1579              :           /* Initialize result to rotate by smallest value of shift.  */
    1580         3291 :           if (code == RROTATE_EXPR)
    1581              :             {
    1582         1584 :               res_mask = wi::rrotate (r1mask, shift, width);
    1583         1584 :               res_val = wi::rrotate (r1val, shift, width);
    1584              :             }
    1585              :           else
    1586              :             {
    1587         1707 :               res_mask = wi::lrotate (r1mask, shift, width);
    1588         1707 :               res_val = wi::lrotate (r1val, shift, width);
    1589              :             }
    1590              : 
    1591              :           /* Iterate through the remaining values of shift.  */
    1592        38664 :           for (unsigned int i=0; i<count; i++)
    1593              :             {
    1594        35373 :               shift ^= bits[gray_code_bit_flips[i]];
    1595        35373 :               if (code == RROTATE_EXPR)
    1596              :                 {
    1597        17320 :                   tmp_mask = wi::rrotate (r1mask, shift, width);
    1598        17320 :                   tmp_val = wi::rrotate (r1val, shift, width);
    1599              :                 }
    1600              :               else
    1601              :                 {
    1602        18053 :                   tmp_mask = wi::lrotate (r1mask, shift, width);
    1603        18053 :                   tmp_val = wi::lrotate (r1val, shift, width);
    1604              :                 }
    1605              :               /* Accumulate the result.  */
    1606        35373 :               res_mask |= tmp_mask | (res_val ^ tmp_val);
    1607              :             }
    1608         3291 :           *val = wi::ext (wi::bit_and_not (res_val, res_mask), width, sgn);
    1609         3291 :           *mask = wi::ext (res_mask, width, sgn);
    1610        16455 :         }
    1611              :       break;
    1612              : 
    1613      8076237 :     case LSHIFT_EXPR:
    1614      8076237 :     case RSHIFT_EXPR:
    1615              :       /* ???  We can handle partially known shift counts if we know
    1616              :          its sign.  That way we can tell that (x << (y | 8)) & 255
    1617              :          is zero.  */
    1618      8076237 :       if (r2mask == 0)
    1619              :         {
    1620      7028814 :           if (r2val == 0)
    1621              :             {
    1622        14980 :               *mask = r1mask;
    1623        14980 :               *val = r1val;
    1624              :             }
    1625              :           else
    1626              :             {
    1627      7013834 :               if (wi::neg_p (r2val, r2type_sgn))
    1628              :                 break;
    1629      7013665 :               if (code == RSHIFT_EXPR)
    1630              :                 {
    1631      6736926 :                   *mask = wi::rshift (wi::ext (r1mask, width, sgn), r2val, sgn);
    1632      6736893 :                   *val = wi::rshift (wi::ext (r1val, width, sgn), r2val, sgn);
    1633              :                 }
    1634              :               else
    1635              :                 {
    1636       276778 :                   *mask = wi::ext (r1mask << r2val, width, sgn);
    1637       276772 :                   *val = wi::ext (r1val << r2val, width, sgn);
    1638              :                 }
    1639              :             }
    1640              :         }
    1641      1047423 :       else if (wi::ltu_p (r2val | r2mask, width))
    1642              :         {
    1643       956908 :           if (wi::popcount (r2mask) <= 4)
    1644              :             {
    1645      3071511 :               widest_int bits[4];
    1646       341279 :               widest_int arg_val, arg_mask;
    1647       341279 :               widest_int res_val, res_mask;
    1648       341279 :               widest_int tmp_val, tmp_mask;
    1649       341279 :               widest_int shift = wi::bit_and_not (r2val, r2mask);
    1650       341279 :               unsigned int bit_count = get_individual_bits (bits, r2mask, 4);
    1651       341279 :               unsigned int count = (1 << bit_count) - 1;
    1652              : 
    1653              :               /* Initialize result to shift by smallest value of shift.  */
    1654       341279 :               if (code == RSHIFT_EXPR)
    1655              :                 {
    1656       132752 :                   arg_mask = wi::ext (r1mask, width, sgn);
    1657       132752 :                   arg_val = wi::ext (r1val, width, sgn);
    1658       132752 :                   res_mask = wi::rshift (arg_mask, shift, sgn);
    1659       132752 :                   res_val = wi::rshift (arg_val, shift, sgn);
    1660              :                 }
    1661              :               else
    1662              :                 {
    1663       208527 :                   arg_mask = r1mask;
    1664       208527 :                   arg_val = r1val;
    1665       208527 :                   res_mask = arg_mask << shift;
    1666       208527 :                   res_val = arg_val << shift;
    1667              :                 }
    1668              : 
    1669              :               /* Iterate through the remaining values of shift.  */
    1670      3245304 :               for (unsigned int i=0; i<count; i++)
    1671              :                 {
    1672      2904025 :                   shift ^= bits[gray_code_bit_flips[i]];
    1673      2904025 :                   if (code == RSHIFT_EXPR)
    1674              :                     {
    1675      1161996 :                       tmp_mask = wi::rshift (arg_mask, shift, sgn);
    1676      1161996 :                       tmp_val = wi::rshift (arg_val, shift, sgn);
    1677              :                     }
    1678              :                   else
    1679              :                     {
    1680      1742029 :                       tmp_mask = arg_mask << shift;
    1681      1742029 :                       tmp_val = arg_val << shift;
    1682              :                     }
    1683              :                   /* Accumulate the result.  */
    1684      2904025 :                   res_mask |= tmp_mask | (res_val ^ tmp_val);
    1685              :                 }
    1686       341279 :               res_mask = wi::ext (res_mask, width, sgn);
    1687       341279 :               res_val = wi::ext (res_val, width, sgn);
    1688       341279 :               *val = wi::bit_and_not (res_val, res_mask);
    1689       341279 :               *mask = res_mask;
    1690      1706395 :             }
    1691       615629 :           else if ((r1val | r1mask) == 0)
    1692              :             {
    1693              :               /* Handle shifts of zero to avoid undefined wi::ctz below.  */
    1694            0 :               *mask = 0;
    1695            0 :               *val = 0;
    1696              :             }
    1697       615629 :           else if (code == LSHIFT_EXPR)
    1698              :             {
    1699       421214 :               widest_int tmp = wi::mask <widest_int> (width, false);
    1700       421214 :               tmp <<= wi::ctz (r1val | r1mask);
    1701       421214 :               tmp <<= wi::bit_and_not (r2val, r2mask);
    1702       421214 :               *mask = wi::ext (tmp, width, sgn);
    1703       421214 :               *val = 0;
    1704       421214 :             }
    1705       194415 :           else if (!wi::neg_p (r1val | r1mask, sgn))
    1706              :             {
    1707              :               /* Logical right shift, or zero sign bit.  */
    1708       170812 :               widest_int arg = r1val | r1mask;
    1709       170812 :               int lzcount = wi::clz (arg);
    1710       170812 :               if (lzcount)
    1711       170804 :                 lzcount -= wi::get_precision (arg) - width;
    1712       170812 :               widest_int tmp = wi::mask <widest_int> (width, false);
    1713       170812 :               tmp = wi::lrshift (tmp, lzcount);
    1714       170812 :               tmp = wi::lrshift (tmp, wi::bit_and_not (r2val, r2mask));
    1715       170812 :               *mask = wi::ext (tmp, width, sgn);
    1716       170812 :               *val = 0;
    1717       170812 :             }
    1718        23603 :           else if (!wi::neg_p (r1mask))
    1719              :             {
    1720              :               /* Arithmetic right shift with set sign bit.  */
    1721         1078 :               widest_int arg = wi::bit_and_not (r1val, r1mask);
    1722         1078 :               int sbcount = wi::clrsb (arg);
    1723         1078 :               sbcount -= wi::get_precision (arg) - width;
    1724         1078 :               widest_int tmp = wi::mask <widest_int> (width, false);
    1725         1078 :               tmp = wi::lrshift (tmp, sbcount);
    1726         1078 :               tmp = wi::lrshift (tmp, wi::bit_and_not (r2val, r2mask));
    1727         1078 :               *mask = wi::sext (tmp, width);
    1728         1078 :               tmp = wi::bit_not (tmp);
    1729         1078 :               *val = wi::sext (tmp, width);
    1730         1078 :             }
    1731              :         }
    1732              :       break;
    1733              : 
    1734    136066994 :     case PLUS_EXPR:
    1735    136066994 :     case POINTER_PLUS_EXPR:
    1736    136066994 :       {
    1737              :         /* Do the addition with unknown bits set to zero, to give carry-ins of
    1738              :            zero wherever possible.  */
    1739    272133988 :         widest_int lo = (wi::bit_and_not (r1val, r1mask)
    1740    272133988 :                          + wi::bit_and_not (r2val, r2mask));
    1741    136066994 :         lo = wi::ext (lo, width, sgn);
    1742              :         /* Do the addition with unknown bits set to one, to give carry-ins of
    1743              :            one wherever possible.  */
    1744    136067304 :         widest_int hi = (r1val | r1mask) + (r2val | r2mask);
    1745    136066994 :         hi = wi::ext (hi, width, sgn);
    1746              :         /* Each bit in the result is known if (a) the corresponding bits in
    1747              :            both inputs are known, and (b) the carry-in to that bit position
    1748              :            is known.  We can check condition (b) by seeing if we got the same
    1749              :            result with minimised carries as with maximised carries.  */
    1750    136067618 :         *mask = r1mask | r2mask | (lo ^ hi);
    1751    136066994 :         *mask = wi::ext (*mask, width, sgn);
    1752              :         /* It shouldn't matter whether we choose lo or hi here.  */
    1753    136066994 :         *val = lo;
    1754    136066994 :         break;
    1755    136067073 :       }
    1756              : 
    1757     40408048 :     case MINUS_EXPR:
    1758     40408048 :     case POINTER_DIFF_EXPR:
    1759     40408048 :       {
    1760              :         /* Subtraction is derived from the addition algorithm above.  */
    1761     40408048 :         widest_int lo = wi::bit_and_not (r1val, r1mask) - (r2val | r2mask);
    1762     40408048 :         lo = wi::ext (lo, width, sgn);
    1763     40408232 :         widest_int hi = (r1val | r1mask) - wi::bit_and_not (r2val, r2mask);
    1764     40408048 :         hi = wi::ext (hi, width, sgn);
    1765     40408416 :         *mask = r1mask | r2mask | (lo ^ hi);
    1766     40408048 :         *mask = wi::ext (*mask, width, sgn);
    1767     40408048 :         *val = lo;
    1768     40408048 :         break;
    1769     40408148 :       }
    1770              : 
    1771     35997569 :     case MULT_EXPR:
    1772     35997569 :       if (r2mask == 0
    1773     32015879 :           && !wi::neg_p (r2val, sgn)
    1774     70719308 :           && (flag_expensive_optimizations || wi::popcount (r2val) < 8))
    1775     31888943 :         bit_value_mult_const (sgn, width, val, mask, r1val, r1mask, r2val);
    1776      4108626 :       else if (r1mask == 0
    1777       100552 :                && !wi::neg_p (r1val, sgn)
    1778      4221977 :                && (flag_expensive_optimizations || wi::popcount (r1val) < 8))
    1779        97976 :         bit_value_mult_const (sgn, width, val, mask, r2val, r2mask, r1val);
    1780              :       else
    1781              :         {
    1782              :           /* Just track trailing zeros in both operands and transfer
    1783              :              them to the other.  */
    1784      4010650 :           int r1tz = wi::ctz (r1val | r1mask);
    1785      4010650 :           int r2tz = wi::ctz (r2val | r2mask);
    1786      4010650 :           if (r1tz + r2tz >= width)
    1787              :             {
    1788            7 :               *mask = 0;
    1789            7 :               *val = 0;
    1790              :             }
    1791      4010643 :           else if (r1tz + r2tz > 0)
    1792              :             {
    1793       952690 :               *mask = wi::ext (wi::mask <widest_int> (r1tz + r2tz, true),
    1794       476345 :                                width, sgn);
    1795       476345 :               *val = 0;
    1796              :             }
    1797              :         }
    1798              :       break;
    1799              : 
    1800     31126452 :     case EQ_EXPR:
    1801     31126452 :     case NE_EXPR:
    1802     31126452 :       {
    1803     31126452 :         widest_int m = r1mask | r2mask;
    1804     31126452 :         if (wi::bit_and_not (r1val, m) != wi::bit_and_not (r2val, m))
    1805              :           {
    1806      2355658 :             *mask = 0;
    1807      2355658 :             *val = ((code == EQ_EXPR) ? 0 : 1);
    1808              :           }
    1809              :         else
    1810              :           {
    1811              :             /* We know the result of a comparison is always one or zero.  */
    1812     28770794 :             *mask = 1;
    1813     28770794 :             *val = 0;
    1814              :           }
    1815     31126452 :         break;
    1816     31126452 :       }
    1817              : 
    1818      7602792 :     case GE_EXPR:
    1819      7602792 :     case GT_EXPR:
    1820      7602792 :       swap_p = true;
    1821      7602792 :       code = swap_tree_comparison (code);
    1822              :       /* Fall through.  */
    1823     12413685 :     case LT_EXPR:
    1824     12413685 :     case LE_EXPR:
    1825     12413685 :       {
    1826     12413685 :         widest_int min1, max1, min2, max2;
    1827     12413685 :         int minmax, maxmin;
    1828              : 
    1829     12413685 :         const widest_int &o1val = swap_p ? r2val : r1val;
    1830      7602792 :         const widest_int &o1mask = swap_p ? r2mask : r1mask;
    1831      7602792 :         const widest_int &o2val = swap_p ? r1val : r2val;
    1832      7602792 :         const widest_int &o2mask = swap_p ? r1mask : r2mask;
    1833              : 
    1834     12413685 :         value_mask_to_min_max (&min1, &max1, o1val, o1mask,
    1835              :                                r1type_sgn, r1type_precision);
    1836     12413685 :         value_mask_to_min_max (&min2, &max2, o2val, o2mask,
    1837              :                                r1type_sgn, r1type_precision);
    1838              : 
    1839              :         /* For comparisons the signedness is in the comparison operands.  */
    1840              :         /* Do a cross comparison of the max/min pairs.  */
    1841     12413685 :         maxmin = wi::cmp (max1, min2, r1type_sgn);
    1842     12413685 :         minmax = wi::cmp (min1, max2, r1type_sgn);
    1843     19310424 :         if (maxmin < (code == LE_EXPR ? 1 : 0))  /* o1 < or <= o2.  */
    1844              :           {
    1845      3007235 :             *mask = 0;
    1846      3007235 :             *val = 1;
    1847              :           }
    1848     11998823 :         else if (minmax > (code == LT_EXPR ? -1 : 0))  /* o1 >= or > o2.  */
    1849              :           {
    1850       416149 :             *mask = 0;
    1851       416149 :             *val = 0;
    1852              :           }
    1853      8990301 :         else if (maxmin == minmax)  /* o1 and o2 are equal.  */
    1854              :           {
    1855              :             /* This probably should never happen as we'd have
    1856              :                folded the thing during fully constant value folding.  */
    1857            0 :             *mask = 0;
    1858            0 :             *val = (code == LE_EXPR ? 1 : 0);
    1859              :           }
    1860              :         else
    1861              :           {
    1862              :             /* We know the result of a comparison is always one or zero.  */
    1863      8990301 :             *mask = 1;
    1864      8990301 :             *val = 0;
    1865              :           }
    1866     12413685 :         break;
    1867     12413771 :       }
    1868              : 
    1869      2275962 :     case MIN_EXPR:
    1870      2275962 :     case MAX_EXPR:
    1871      2275962 :       {
    1872      2275962 :         widest_int min1, max1, min2, max2;
    1873              : 
    1874      2275962 :         value_mask_to_min_max (&min1, &max1, r1val, r1mask, sgn, width);
    1875      2275962 :         value_mask_to_min_max (&min2, &max2, r2val, r2mask, sgn, width);
    1876              : 
    1877      2275962 :         if (wi::cmp (max1, min2, sgn) <= 0)  /* r1 is less than r2.  */
    1878              :           {
    1879        27397 :             if (code == MIN_EXPR)
    1880              :               {
    1881        26510 :                 *mask = r1mask;
    1882        26510 :                 *val = r1val;
    1883              :               }
    1884              :             else
    1885              :               {
    1886          887 :                 *mask = r2mask;
    1887          887 :                 *val = r2val;
    1888              :               }
    1889              :           }
    1890      2248565 :         else if (wi::cmp (min1, max2, sgn) >= 0)  /* r2 is less than r1.  */
    1891              :           {
    1892       114797 :             if (code == MIN_EXPR)
    1893              :               {
    1894         1541 :                 *mask = r2mask;
    1895         1541 :                 *val = r2val;
    1896              :               }
    1897              :             else
    1898              :               {
    1899       113256 :                 *mask = r1mask;
    1900       113256 :                 *val = r1val;
    1901              :               }
    1902              :           }
    1903              :         else
    1904              :           {
    1905              :             /* The result is either r1 or r2.  */
    1906      2133772 :             *mask = r1mask | r2mask | (r1val ^ r2val);
    1907      2133768 :             *val = r1val;
    1908              :           }
    1909      2275962 :         break;
    1910      2275966 :       }
    1911              : 
    1912      2528678 :     case TRUNC_MOD_EXPR:
    1913      2528678 :       {
    1914      2528678 :         widest_int r1max = r1val | r1mask;
    1915      2528678 :         widest_int r2max = r2val | r2mask;
    1916      2528678 :         if (r2mask == 0)
    1917              :           {
    1918       507108 :             widest_int shift = wi::exact_log2 (r2val);
    1919       507108 :             if (shift != -1)
    1920              :               {
    1921              :                 // Handle modulo by a power of 2 as a bitwise and.
    1922        89409 :                 widest_int tem_val, tem_mask;
    1923        89409 :                 bit_value_binop (BIT_AND_EXPR, sgn, width, &tem_val, &tem_mask,
    1924              :                                  r1type_sgn, r1type_precision, r1val, r1mask,
    1925              :                                  r2type_sgn, r2type_precision,
    1926        89409 :                                  r2val - 1, r2mask);
    1927        89409 :                 if (sgn == UNSIGNED
    1928        89239 :                     || !wi::neg_p (r1max)
    1929       178648 :                     || (tem_mask == 0 && tem_val == 0))
    1930              :                   {
    1931        41194 :                     *val = tem_val;
    1932        41194 :                     *mask = tem_mask;
    1933        41194 :                     return;
    1934              :                   }
    1935        89409 :               }
    1936       507108 :           }
    1937      2487484 :         if (sgn == UNSIGNED
    1938      2487484 :             || (!wi::neg_p (r1max) && !wi::neg_p (r2max)))
    1939              :           {
    1940              :             /* Confirm R2 has some bits set, to avoid division by zero.  */
    1941       936161 :             widest_int r2min = wi::bit_and_not (r2val, r2mask);
    1942       936161 :             if (r2min != 0)
    1943              :               {
    1944              :                 /* R1 % R2 is R1 if R1 is always less than R2.  */
    1945       327073 :                 if (wi::ltu_p (r1max, r2min))
    1946              :                   {
    1947        16085 :                     *mask = r1mask;
    1948        16085 :                     *val = r1val;
    1949              :                   }
    1950              :                 else
    1951              :                   {
    1952              :                     /* R1 % R2 is always less than the maximum of R2.  */
    1953       310988 :                     unsigned int lzcount = wi::clz (r2max);
    1954       310988 :                     unsigned int bits = wi::get_precision (r2max) - lzcount;
    1955       310988 :                     if (r2max == wi::lshift (1, bits))
    1956            0 :                       bits--;
    1957       310988 :                     *mask = wi::mask <widest_int> (bits, false);
    1958       310988 :                     *val = 0;
    1959              :                   }
    1960              :                }
    1961       936161 :             }
    1962      2528678 :         }
    1963      2487484 :       break;
    1964              : 
    1965      4152092 :     case EXACT_DIV_EXPR:
    1966      4152092 :     case TRUNC_DIV_EXPR:
    1967      4152092 :       {
    1968      4152092 :         widest_int r1max = r1val | r1mask;
    1969      4152092 :         widest_int r2max = r2val | r2mask;
    1970      8304184 :         if (r2mask == 0
    1971      4152092 :             && (code == EXACT_DIV_EXPR
    1972      3213227 :                 || sgn == UNSIGNED
    1973      1254219 :                 || !wi::neg_p (r1max)))
    1974              :           {
    1975      2214152 :             widest_int shift = wi::exact_log2 (r2val);
    1976      2214152 :             if (shift != -1)
    1977              :               {
    1978              :                 // Handle division by a power of 2 as an rshift.
    1979      1715096 :                 bit_value_binop (RSHIFT_EXPR, sgn, width, val, mask,
    1980              :                                  r1type_sgn, r1type_precision, r1val, r1mask,
    1981              :                                  r2type_sgn, r2type_precision, shift, r2mask);
    1982      1715096 :                 return;
    1983              :               }
    1984      2214152 :           }
    1985      2436996 :         if (sgn == UNSIGNED
    1986      2436996 :             || (!wi::neg_p (r1max) && !wi::neg_p (r2max)))
    1987              :           {
    1988              :             /* Confirm R2 has some bits set, to avoid division by zero.  */
    1989       745075 :             widest_int r2min = wi::bit_and_not (r2val, r2mask);
    1990       745075 :             if (r2min != 0)
    1991              :               {
    1992              :                 /* R1 / R2 is zero if R1 is always less than R2.  */
    1993       371054 :                 if (wi::ltu_p (r1max, r2min))
    1994              :                   {
    1995         2560 :                     *mask = 0;
    1996         2560 :                     *val = 0;
    1997              :                   }
    1998              :                 else
    1999              :                   {
    2000       368494 :                     widest_int upper
    2001       368494 :                       = wi::udiv_trunc (wi::zext (r1max, width), r2min);
    2002       368494 :                     unsigned int lzcount = wi::clz (upper);
    2003       368494 :                     unsigned int bits = wi::get_precision (upper) - lzcount;
    2004       368494 :                     *mask = wi::mask <widest_int> (bits, false);
    2005       368494 :                     *val = 0;
    2006       368494 :                   }
    2007              :                }
    2008       745075 :             }
    2009      4152096 :         }
    2010      2436996 :       break;
    2011              : 
    2012          169 :     default:;
    2013              :     }
    2014              : }
    2015              : 
    2016              : /* Return the propagation value when applying the operation CODE to
    2017              :    the value RHS yielding type TYPE.  */
    2018              : 
    2019              : static ccp_prop_value_t
    2020     31260293 : bit_value_unop (enum tree_code code, tree type, tree rhs)
    2021              : {
    2022     31260293 :   ccp_prop_value_t rval = get_value_for_expr (rhs, true);
    2023     31260293 :   widest_int value, mask;
    2024     31260293 :   ccp_prop_value_t val;
    2025              : 
    2026     31260293 :   if (rval.lattice_val == UNDEFINED)
    2027            0 :     return rval;
    2028              : 
    2029     31260293 :   gcc_assert ((rval.lattice_val == CONSTANT
    2030              :                && TREE_CODE (rval.value) == INTEGER_CST)
    2031              :               || wi::sext (rval.mask, TYPE_PRECISION (TREE_TYPE (rhs))) == -1);
    2032     62520586 :   bit_value_unop (code, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask,
    2033     31260293 :                   TYPE_SIGN (TREE_TYPE (rhs)), TYPE_PRECISION (TREE_TYPE (rhs)),
    2034     62520586 :                   value_to_wide_int (rval), rval.mask);
    2035     31260489 :   if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
    2036              :     {
    2037     24735121 :       val.lattice_val = CONSTANT;
    2038     24735121 :       val.mask = mask;
    2039              :       /* ???  Delay building trees here.  */
    2040     24735121 :       val.value = wide_int_to_tree (type, value);
    2041              :     }
    2042              :   else
    2043              :     {
    2044      6525172 :       val.lattice_val = VARYING;
    2045      6525172 :       val.value = NULL_TREE;
    2046      6525172 :       val.mask = -1;
    2047              :     }
    2048     31260293 :   return val;
    2049     31260722 : }
    2050              : 
    2051              : /* Return the propagation value when applying the operation CODE to
    2052              :    the values RHS1 and RHS2 yielding type TYPE.  */
    2053              : 
    2054              : static ccp_prop_value_t
    2055    146509451 : bit_value_binop (enum tree_code code, tree type, tree rhs1, tree rhs2)
    2056              : {
    2057    146509451 :   ccp_prop_value_t r1val = get_value_for_expr (rhs1, true);
    2058    146509451 :   ccp_prop_value_t r2val = get_value_for_expr (rhs2, true);
    2059    146509451 :   widest_int value, mask;
    2060    146509451 :   ccp_prop_value_t val;
    2061              : 
    2062    146509451 :   if (r1val.lattice_val == UNDEFINED
    2063    146376121 :       || r2val.lattice_val == UNDEFINED)
    2064              :     {
    2065       139482 :       val.lattice_val = VARYING;
    2066       139482 :       val.value = NULL_TREE;
    2067       139482 :       val.mask = -1;
    2068       139482 :       return val;
    2069              :     }
    2070              : 
    2071    146369969 :   gcc_assert ((r1val.lattice_val == CONSTANT
    2072              :                && TREE_CODE (r1val.value) == INTEGER_CST)
    2073              :               || wi::sext (r1val.mask,
    2074              :                            TYPE_PRECISION (TREE_TYPE (rhs1))) == -1);
    2075    146369969 :   gcc_assert ((r2val.lattice_val == CONSTANT
    2076              :                && TREE_CODE (r2val.value) == INTEGER_CST)
    2077              :               || wi::sext (r2val.mask,
    2078              :                            TYPE_PRECISION (TREE_TYPE (rhs2))) == -1);
    2079    292739938 :   bit_value_binop (code, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask,
    2080    146369969 :                    TYPE_SIGN (TREE_TYPE (rhs1)), TYPE_PRECISION (TREE_TYPE (rhs1)),
    2081    292805549 :                    value_to_wide_int (r1val), r1val.mask,
    2082    146369969 :                    TYPE_SIGN (TREE_TYPE (rhs2)), TYPE_PRECISION (TREE_TYPE (rhs2)),
    2083    292739938 :                    value_to_wide_int (r2val), r2val.mask);
    2084              : 
    2085              :   /* (x * x) & 2 == 0.  */
    2086    146369969 :   if (code == MULT_EXPR && rhs1 == rhs2 && TYPE_PRECISION (type) > 1)
    2087              :     {
    2088       175414 :       widest_int m = 2;
    2089       175414 :       if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
    2090          299 :         value = wi::bit_and_not (value, m);
    2091              :       else
    2092       175115 :         value = 0;
    2093       175414 :       mask = wi::bit_and_not (mask, m);
    2094       175414 :     }
    2095              : 
    2096    146434951 :   if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
    2097              :     {
    2098    122704759 :       val.lattice_val = CONSTANT;
    2099    122704759 :       val.mask = mask;
    2100              :       /* ???  Delay building trees here.  */
    2101    122704759 :       val.value = wide_int_to_tree (type, value);
    2102              :     }
    2103              :   else
    2104              :     {
    2105     23665210 :       val.lattice_val = VARYING;
    2106     23665210 :       val.value = NULL_TREE;
    2107     23665210 :       val.mask = -1;
    2108              :     }
    2109              :   return val;
    2110    146509758 : }
    2111              : 
    2112              : /* Return the propagation value for __builtin_assume_aligned
    2113              :    and functions with assume_aligned or alloc_aligned attribute.
    2114              :    For __builtin_assume_aligned, ATTR is NULL_TREE,
    2115              :    for assume_aligned attribute ATTR is non-NULL and ALLOC_ALIGNED
    2116              :    is false, for alloc_aligned attribute ATTR is non-NULL and
    2117              :    ALLOC_ALIGNED is true.  */
    2118              : 
    2119              : static ccp_prop_value_t
    2120         8563 : bit_value_assume_aligned (gimple *stmt, tree attr, ccp_prop_value_t ptrval,
    2121              :                           bool alloc_aligned)
    2122              : {
    2123         8563 :   tree align, misalign = NULL_TREE, type;
    2124         8563 :   unsigned HOST_WIDE_INT aligni, misaligni = 0;
    2125         8563 :   ccp_prop_value_t alignval;
    2126         8563 :   widest_int value, mask;
    2127         8563 :   ccp_prop_value_t val;
    2128              : 
    2129         8563 :   if (attr == NULL_TREE)
    2130              :     {
    2131         3581 :       tree ptr = gimple_call_arg (stmt, 0);
    2132         3581 :       type = TREE_TYPE (ptr);
    2133         3581 :       ptrval = get_value_for_expr (ptr, true);
    2134              :     }
    2135              :   else
    2136              :     {
    2137         4982 :       tree lhs = gimple_call_lhs (stmt);
    2138         4982 :       type = TREE_TYPE (lhs);
    2139              :     }
    2140              : 
    2141         8563 :   if (ptrval.lattice_val == UNDEFINED)
    2142            0 :     return ptrval;
    2143         8563 :   gcc_assert ((ptrval.lattice_val == CONSTANT
    2144              :                && TREE_CODE (ptrval.value) == INTEGER_CST)
    2145              :               || wi::sext (ptrval.mask, TYPE_PRECISION (type)) == -1);
    2146         8563 :   if (attr == NULL_TREE)
    2147              :     {
    2148              :       /* Get aligni and misaligni from __builtin_assume_aligned.  */
    2149         3581 :       align = gimple_call_arg (stmt, 1);
    2150         3581 :       if (!tree_fits_uhwi_p (align))
    2151           47 :         return ptrval;
    2152         3534 :       aligni = tree_to_uhwi (align);
    2153         3534 :       if (gimple_call_num_args (stmt) > 2)
    2154              :         {
    2155           36 :           misalign = gimple_call_arg (stmt, 2);
    2156           36 :           if (!tree_fits_uhwi_p (misalign))
    2157            2 :             return ptrval;
    2158           34 :           misaligni = tree_to_uhwi (misalign);
    2159              :         }
    2160              :     }
    2161              :   else
    2162              :     {
    2163              :       /* Get aligni and misaligni from assume_aligned or
    2164              :          alloc_align attributes.  */
    2165         4982 :       if (TREE_VALUE (attr) == NULL_TREE)
    2166            0 :         return ptrval;
    2167         4982 :       attr = TREE_VALUE (attr);
    2168         4982 :       align = TREE_VALUE (attr);
    2169         4982 :       if (!tree_fits_uhwi_p (align))
    2170            0 :         return ptrval;
    2171         4982 :       aligni = tree_to_uhwi (align);
    2172         4982 :       if (alloc_aligned)
    2173              :         {
    2174         4940 :           if (aligni == 0 || aligni > gimple_call_num_args (stmt))
    2175            0 :             return ptrval;
    2176         4940 :           align = gimple_call_arg (stmt, aligni - 1);
    2177         4940 :           if (!tree_fits_uhwi_p (align))
    2178          226 :             return ptrval;
    2179         4714 :           aligni = tree_to_uhwi (align);
    2180              :         }
    2181           42 :       else if (TREE_CHAIN (attr) && TREE_VALUE (TREE_CHAIN (attr)))
    2182              :         {
    2183           21 :           misalign = TREE_VALUE (TREE_CHAIN (attr));
    2184           21 :           if (!tree_fits_uhwi_p (misalign))
    2185            0 :             return ptrval;
    2186           21 :           misaligni = tree_to_uhwi (misalign);
    2187              :         }
    2188              :     }
    2189         8288 :   if (aligni <= 1 || (aligni & (aligni - 1)) != 0 || misaligni >= aligni)
    2190          154 :     return ptrval;
    2191              : 
    2192         8134 :   align = build_int_cst_type (type, -aligni);
    2193         8134 :   alignval = get_value_for_expr (align, true);
    2194        16268 :   bit_value_binop (BIT_AND_EXPR, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask,
    2195        16268 :                    TYPE_SIGN (type), TYPE_PRECISION (type), value_to_wide_int (ptrval), ptrval.mask,
    2196        16268 :                    TYPE_SIGN (type), TYPE_PRECISION (type), value_to_wide_int (alignval), alignval.mask);
    2197              : 
    2198         8134 :   if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
    2199              :     {
    2200         8134 :       val.lattice_val = CONSTANT;
    2201         8134 :       val.mask = mask;
    2202         8134 :       gcc_assert ((mask.to_uhwi () & (aligni - 1)) == 0);
    2203         8134 :       gcc_assert ((value.to_uhwi () & (aligni - 1)) == 0);
    2204         8134 :       value |= misaligni;
    2205              :       /* ???  Delay building trees here.  */
    2206         8134 :       val.value = wide_int_to_tree (type, value);
    2207              :     }
    2208              :   else
    2209              :     {
    2210            0 :       val.lattice_val = VARYING;
    2211            0 :       val.value = NULL_TREE;
    2212            0 :       val.mask = -1;
    2213              :     }
    2214         8134 :   return val;
    2215         8563 : }
    2216              : 
    2217              : /* Evaluate statement STMT.
    2218              :    Valid only for assignments, calls, conditionals, and switches. */
    2219              : 
    2220              : static ccp_prop_value_t
    2221    245451421 : evaluate_stmt (gimple *stmt)
    2222              : {
    2223    245451421 :   ccp_prop_value_t val;
    2224    245451421 :   tree simplified = NULL_TREE;
    2225    245451421 :   ccp_lattice_t likelyvalue = likely_value (stmt);
    2226    245451421 :   bool is_constant = false;
    2227    245451421 :   unsigned int align;
    2228    245451421 :   bool ignore_return_flags = false;
    2229              : 
    2230    245451421 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2231              :     {
    2232           66 :       fprintf (dump_file, "which is likely ");
    2233           66 :       switch (likelyvalue)
    2234              :         {
    2235           65 :         case CONSTANT:
    2236           65 :           fprintf (dump_file, "CONSTANT");
    2237           65 :           break;
    2238            0 :         case UNDEFINED:
    2239            0 :           fprintf (dump_file, "UNDEFINED");
    2240            0 :           break;
    2241            1 :         case VARYING:
    2242            1 :           fprintf (dump_file, "VARYING");
    2243            1 :           break;
    2244           66 :         default:;
    2245              :         }
    2246           66 :       fprintf (dump_file, "\n");
    2247              :     }
    2248              : 
    2249              :   /* If the statement is likely to have a CONSTANT result, then try
    2250              :      to fold the statement to determine the constant value.  */
    2251              :   /* FIXME.  This is the only place that we call ccp_fold.
    2252              :      Since likely_value never returns CONSTANT for calls, we will
    2253              :      not attempt to fold them, including builtins that may profit.  */
    2254    245451421 :   if (likelyvalue == CONSTANT)
    2255              :     {
    2256    245276250 :       simplified = ccp_fold (stmt);
    2257    245276250 :       if (simplified
    2258     34034302 :           && TREE_CODE (simplified) == SSA_NAME)
    2259              :         {
    2260              :           /* We may not use values of something that may be simulated again,
    2261              :              see valueize_op_1.  */
    2262     17288045 :           if (SSA_NAME_IS_DEFAULT_DEF (simplified)
    2263     17288045 :               || ! prop_simulate_again_p (SSA_NAME_DEF_STMT (simplified)))
    2264              :             {
    2265     12641945 :               ccp_prop_value_t *val = get_value (simplified);
    2266     12641945 :               if (val && val->lattice_val != VARYING)
    2267       612122 :                 return *val;
    2268              :             }
    2269              :           else
    2270              :             /* We may also not place a non-valueized copy in the lattice
    2271              :                as that might become stale if we never re-visit this stmt.  */
    2272              :             simplified = NULL_TREE;
    2273              :         }
    2274     28776080 :       is_constant = simplified && is_gimple_min_invariant (simplified);
    2275     13818831 :       if (is_constant)
    2276              :         {
    2277              :           /* The statement produced a constant value.  */
    2278     13818831 :           val.lattice_val = CONSTANT;
    2279     13818831 :           val.value = simplified;
    2280     13818831 :           val.mask = 0;
    2281     13818831 :           return val;
    2282              :         }
    2283              :     }
    2284              :   /* If the statement is likely to have a VARYING result, then do not
    2285              :      bother folding the statement.  */
    2286       175171 :   else if (likelyvalue == VARYING)
    2287              :     {
    2288        49391 :       enum gimple_code code = gimple_code (stmt);
    2289        49391 :       if (code == GIMPLE_ASSIGN)
    2290              :         {
    2291          814 :           enum tree_code subcode = gimple_assign_rhs_code (stmt);
    2292              : 
    2293              :           /* Other cases cannot satisfy is_gimple_min_invariant
    2294              :              without folding.  */
    2295          814 :           if (get_gimple_rhs_class (subcode) == GIMPLE_SINGLE_RHS)
    2296          814 :             simplified = gimple_assign_rhs1 (stmt);
    2297              :         }
    2298        48577 :       else if (code == GIMPLE_SWITCH)
    2299            0 :         simplified = gimple_switch_index (as_a <gswitch *> (stmt));
    2300              :       else
    2301              :         /* These cannot satisfy is_gimple_min_invariant without folding.  */
    2302        48577 :         gcc_assert (code == GIMPLE_CALL || code == GIMPLE_COND);
    2303          814 :       is_constant = simplified && is_gimple_min_invariant (simplified);
    2304            0 :       if (is_constant)
    2305              :         {
    2306              :           /* The statement produced a constant value.  */
    2307            0 :           val.lattice_val = CONSTANT;
    2308            0 :           val.value = simplified;
    2309            0 :           val.mask = 0;
    2310              :         }
    2311              :     }
    2312              :   /* If the statement result is likely UNDEFINED, make it so.  */
    2313       125780 :   else if (likelyvalue == UNDEFINED)
    2314              :     {
    2315       125780 :       val.lattice_val = UNDEFINED;
    2316       125780 :       val.value = NULL_TREE;
    2317       125780 :       val.mask = 0;
    2318       125780 :       return val;
    2319              :     }
    2320              : 
    2321              :   /* Resort to simplification for bitwise tracking.  */
    2322    230894688 :   if (flag_tree_bit_ccp
    2323    230814677 :       && (likelyvalue == CONSTANT || is_gimple_call (stmt)
    2324          814 :           || (gimple_assign_single_p (stmt)
    2325          814 :               && gimple_assign_rhs_code (stmt) == ADDR_EXPR))
    2326    461708622 :       && !is_constant)
    2327              :     {
    2328    230813934 :       enum gimple_code code = gimple_code (stmt);
    2329    230813934 :       val.lattice_val = VARYING;
    2330    230813934 :       val.value = NULL_TREE;
    2331    230813934 :       val.mask = -1;
    2332    230813934 :       if (code == GIMPLE_ASSIGN)
    2333              :         {
    2334    185306260 :           enum tree_code subcode = gimple_assign_rhs_code (stmt);
    2335    185306260 :           tree rhs1 = gimple_assign_rhs1 (stmt);
    2336    185306260 :           tree lhs = gimple_assign_lhs (stmt);
    2337    370145519 :           if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
    2338     35117448 :                || POINTER_TYPE_P (TREE_TYPE (lhs)))
    2339    363696721 :               && (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
    2340     30198660 :                   || POINTER_TYPE_P (TREE_TYPE (rhs1))))
    2341    178501587 :             switch (get_gimple_rhs_class (subcode))
    2342              :               {
    2343     40194816 :               case GIMPLE_SINGLE_RHS:
    2344     40194816 :                 val = get_value_for_expr (rhs1, true);
    2345     40194816 :                 break;
    2346              : 
    2347     31260293 :               case GIMPLE_UNARY_RHS:
    2348     31260293 :                 val = bit_value_unop (subcode, TREE_TYPE (lhs), rhs1);
    2349     31260293 :                 break;
    2350              : 
    2351    107025443 :               case GIMPLE_BINARY_RHS:
    2352    107025443 :                 val = bit_value_binop (subcode, TREE_TYPE (lhs), rhs1,
    2353    107025443 :                                        gimple_assign_rhs2 (stmt));
    2354    107025443 :                 break;
    2355              : 
    2356              :               default:;
    2357              :               }
    2358              :         }
    2359     45507674 :       else if (code == GIMPLE_COND)
    2360              :         {
    2361     40959580 :           enum tree_code code = gimple_cond_code (stmt);
    2362     40959580 :           tree rhs1 = gimple_cond_lhs (stmt);
    2363     40959580 :           tree rhs2 = gimple_cond_rhs (stmt);
    2364     81346631 :           if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
    2365     48904115 :               || POINTER_TYPE_P (TREE_TYPE (rhs1)))
    2366     39484008 :             val = bit_value_binop (code, TREE_TYPE (rhs1), rhs1, rhs2);
    2367              :         }
    2368      4548094 :       else if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
    2369              :         {
    2370      2421312 :           tree fndecl = gimple_call_fndecl (stmt);
    2371      2421312 :           switch (DECL_FUNCTION_CODE (fndecl))
    2372              :             {
    2373       243515 :             case BUILT_IN_MALLOC:
    2374       243515 :             case BUILT_IN_REALLOC:
    2375       243515 :             case BUILT_IN_GOMP_REALLOC:
    2376       243515 :             case BUILT_IN_CALLOC:
    2377       243515 :             case BUILT_IN_STRDUP:
    2378       243515 :             case BUILT_IN_STRNDUP:
    2379       243515 :               val.lattice_val = CONSTANT;
    2380       243515 :               val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
    2381       245748 :               val.mask = ~((HOST_WIDE_INT) MALLOC_ABI_ALIGNMENT
    2382       243515 :                            / BITS_PER_UNIT - 1);
    2383       243515 :               break;
    2384              : 
    2385        52843 :             CASE_BUILT_IN_ALLOCA:
    2386        90691 :               align = (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_ALLOCA
    2387        37852 :                        ? BIGGEST_ALIGNMENT
    2388        14991 :                        : TREE_INT_CST_LOW (gimple_call_arg (stmt, 1)));
    2389        52843 :               val.lattice_val = CONSTANT;
    2390        52843 :               val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
    2391        52843 :               val.mask = ~((HOST_WIDE_INT) align / BITS_PER_UNIT - 1);
    2392        52843 :               break;
    2393              : 
    2394         3195 :             case BUILT_IN_ASSUME_ALIGNED:
    2395         3195 :               val = bit_value_assume_aligned (stmt, NULL_TREE, val, false);
    2396         3195 :               ignore_return_flags = true;
    2397         3195 :               break;
    2398              : 
    2399          130 :             case BUILT_IN_ALIGNED_ALLOC:
    2400          130 :             case BUILT_IN_GOMP_ALLOC:
    2401          130 :               {
    2402          130 :                 tree align = get_constant_value (gimple_call_arg (stmt, 0));
    2403          130 :                 if (align
    2404          122 :                     && tree_fits_uhwi_p (align))
    2405              :                   {
    2406          122 :                     unsigned HOST_WIDE_INT aligni = tree_to_uhwi (align);
    2407          122 :                     if (aligni > 1
    2408              :                         /* align must be power-of-two */
    2409          106 :                         && (aligni & (aligni - 1)) == 0)
    2410              :                       {
    2411          106 :                         val.lattice_val = CONSTANT;
    2412          106 :                         val.value = build_int_cst (ptr_type_node, 0);
    2413          106 :                         val.mask = -aligni;
    2414              :                       }
    2415              :                   }
    2416              :                 break;
    2417              :               }
    2418              : 
    2419         5702 :             case BUILT_IN_BSWAP16:
    2420         5702 :             case BUILT_IN_BSWAP32:
    2421         5702 :             case BUILT_IN_BSWAP64:
    2422         5702 :             case BUILT_IN_BSWAP128:
    2423         5702 :               val = get_value_for_expr (gimple_call_arg (stmt, 0), true);
    2424         5702 :               if (val.lattice_val == UNDEFINED)
    2425              :                 break;
    2426         5702 :               else if (val.lattice_val == CONSTANT
    2427         2485 :                        && val.value
    2428         2485 :                        && TREE_CODE (val.value) == INTEGER_CST)
    2429              :                 {
    2430         2485 :                   tree type = TREE_TYPE (gimple_call_lhs (stmt));
    2431         2485 :                   int prec = TYPE_PRECISION (type);
    2432         2485 :                   wide_int wval = wi::to_wide (val.value);
    2433         2485 :                   val.value
    2434         2485 :                     = wide_int_to_tree (type,
    2435         4970 :                                         wi::bswap (wide_int::from (wval, prec,
    2436              :                                                                    UNSIGNED)));
    2437         2485 :                   val.mask
    2438         4970 :                     = widest_int::from (wi::bswap (wide_int::from (val.mask,
    2439              :                                                                    prec,
    2440              :                                                                    UNSIGNED)),
    2441         2485 :                                         UNSIGNED);
    2442         2485 :                   if (wi::sext (val.mask, prec) != -1)
    2443              :                     break;
    2444         2485 :                 }
    2445         3217 :               val.lattice_val = VARYING;
    2446         3217 :               val.value = NULL_TREE;
    2447         3217 :               val.mask = -1;
    2448         3217 :               break;
    2449              : 
    2450          408 :             case BUILT_IN_BITREVERSE8:
    2451          408 :             case BUILT_IN_BITREVERSE16:
    2452          408 :             case BUILT_IN_BITREVERSE32:
    2453          408 :             case BUILT_IN_BITREVERSE64:
    2454          408 :             case BUILT_IN_BITREVERSE128:
    2455          408 :               val = get_value_for_expr (gimple_call_arg (stmt, 0), true);
    2456          408 :               if (val.lattice_val == UNDEFINED)
    2457              :                 break;
    2458          408 :               else if (val.lattice_val == CONSTANT
    2459           20 :                        && val.value
    2460           20 :                        && TREE_CODE (val.value) == INTEGER_CST)
    2461              :                 {
    2462           20 :                   tree type = TREE_TYPE (gimple_call_lhs (stmt));
    2463           20 :                   int prec = TYPE_PRECISION (type);
    2464           20 :                   wide_int wval = wi::to_wide (val.value);
    2465           20 :                   wval = wide_int::from (wval, prec, UNSIGNED);
    2466           20 :                   wide_int wmask = wide_int::from (val.mask, prec, UNSIGNED);
    2467           20 :                   val.value = wide_int_to_tree (type, wi::bitreverse (wval));
    2468           40 :                   val.mask = widest_int::from (wi::bitreverse (wmask),
    2469           20 :                                                UNSIGNED);
    2470           20 :                   if (wi::sext (val.mask, prec) != -1)
    2471              :                     break;
    2472           20 :                 }
    2473          388 :               val.lattice_val = VARYING;
    2474          388 :               val.value = NULL_TREE;
    2475          388 :               val.mask = -1;
    2476          388 :               break;
    2477              : 
    2478            0 :             default:;
    2479              :             }
    2480              :         }
    2481    230813934 :       if (is_gimple_call (stmt) && gimple_call_lhs (stmt))
    2482              :         {
    2483      4454316 :           tree fntype = gimple_call_fntype (stmt);
    2484      4454316 :           if (fntype)
    2485              :             {
    2486      3922742 :               tree attrs = lookup_attribute ("assume_aligned",
    2487      3922742 :                                              TYPE_ATTRIBUTES (fntype));
    2488      3922742 :               if (attrs)
    2489           42 :                 val = bit_value_assume_aligned (stmt, attrs, val, false);
    2490      3922742 :               attrs = lookup_attribute ("alloc_align",
    2491      3922742 :                                         TYPE_ATTRIBUTES (fntype));
    2492      3922742 :               if (attrs)
    2493         4940 :                 val = bit_value_assume_aligned (stmt, attrs, val, true);
    2494              :             }
    2495      4454316 :           int flags = ignore_return_flags
    2496      4454316 :                       ? 0 : gimple_call_return_flags (as_a <gcall *> (stmt));
    2497      4451121 :           if (flags & ERF_RETURNS_ARG
    2498      4451121 :               && (flags & ERF_RETURN_ARG_MASK) < gimple_call_num_args (stmt))
    2499              :             {
    2500       156807 :               val = get_value_for_expr
    2501       313614 :                          (gimple_call_arg (stmt,
    2502       156807 :                                            flags & ERF_RETURN_ARG_MASK), true);
    2503              :             }
    2504              :         }
    2505    230813934 :       is_constant = (val.lattice_val == CONSTANT);
    2506              :     }
    2507              : 
    2508    230894688 :   tree lhs = gimple_get_lhs (stmt);
    2509    230894688 :   if (flag_tree_bit_ccp
    2510    230814677 :       && lhs && TREE_CODE (lhs) == SSA_NAME && !VECTOR_TYPE_P (TREE_TYPE (lhs))
    2511    418536506 :       && ((is_constant && TREE_CODE (val.value) == INTEGER_CST)
    2512              :           || !is_constant))
    2513              :     {
    2514    187641818 :       tree lhs = gimple_get_lhs (stmt);
    2515    187641818 :       wide_int nonzero_bits = get_nonzero_bits (lhs);
    2516    187641818 :       if (nonzero_bits != -1)
    2517              :         {
    2518     53619057 :           if (!is_constant)
    2519              :             {
    2520      4301482 :               val.lattice_val = CONSTANT;
    2521      4301482 :               val.value = build_zero_cst (TREE_TYPE (lhs));
    2522      4301482 :               val.mask = extend_mask (nonzero_bits, TYPE_SIGN (TREE_TYPE (lhs)));
    2523      4301482 :               is_constant = true;
    2524              :             }
    2525              :           else
    2526              :             {
    2527     49317698 :               if (wi::bit_and_not (wi::to_wide (val.value), nonzero_bits) != 0)
    2528        63970 :                 val.value = wide_int_to_tree (TREE_TYPE (lhs),
    2529              :                                               nonzero_bits
    2530       127940 :                                               & wi::to_wide (val.value));
    2531     49317575 :               if (nonzero_bits == 0)
    2532          124 :                 val.mask = 0;
    2533              :               else
    2534     98635001 :                 val.mask = val.mask & extend_mask (nonzero_bits,
    2535     98634902 :                                                    TYPE_SIGN (TREE_TYPE (lhs)));
    2536              :             }
    2537              :         }
    2538    187641818 :     }
    2539              : 
    2540              :   /* The statement produced a nonconstant value.  */
    2541    230894688 :   if (!is_constant)
    2542              :     {
    2543              :       /* The statement produced a copy.  */
    2544     14454272 :       if (simplified && TREE_CODE (simplified) == SSA_NAME
    2545     87023400 :           && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (simplified))
    2546              :         {
    2547     12010556 :           val.lattice_val = CONSTANT;
    2548     12010556 :           val.value = simplified;
    2549     12010556 :           val.mask = -1;
    2550              :         }
    2551              :       /* The statement is VARYING.  */
    2552              :       else
    2553              :         {
    2554     63000447 :           val.lattice_val = VARYING;
    2555     63000447 :           val.value = NULL_TREE;
    2556     63000447 :           val.mask = -1;
    2557              :         }
    2558              :     }
    2559              : 
    2560    230894688 :   return val;
    2561    245451421 : }
    2562              : 
    2563              : typedef hash_table<nofree_ptr_hash<gimple> > gimple_htab;
    2564              : 
    2565              : /* Given a BUILT_IN_STACK_SAVE value SAVED_VAL, insert a clobber of VAR before
    2566              :    each matching BUILT_IN_STACK_RESTORE.  Mark visited phis in VISITED.  */
    2567              : 
    2568              : static void
    2569          527 : insert_clobber_before_stack_restore (tree saved_val, tree var,
    2570              :                                      gimple_htab **visited)
    2571              : {
    2572          527 :   gimple *stmt;
    2573          527 :   gassign *clobber_stmt;
    2574          527 :   tree clobber;
    2575          527 :   imm_use_iterator iter;
    2576          527 :   gimple_stmt_iterator i;
    2577          527 :   gimple **slot;
    2578              : 
    2579         1058 :   FOR_EACH_IMM_USE_STMT (stmt, iter, saved_val)
    2580          531 :     if (gimple_call_builtin_p (stmt, BUILT_IN_STACK_RESTORE))
    2581              :       {
    2582          518 :         clobber = build_clobber (TREE_TYPE (var), CLOBBER_STORAGE_END);
    2583          518 :         clobber_stmt = gimple_build_assign (var, clobber);
    2584              :         /* Manually update the vdef/vuse here. */
    2585         1036 :         gimple_set_vuse (clobber_stmt, gimple_vuse (stmt));
    2586          518 :         gimple_set_vdef (clobber_stmt, make_ssa_name (gimple_vop (cfun)));
    2587         1036 :         gimple_set_vuse (stmt, gimple_vdef (clobber_stmt));
    2588         1036 :         SSA_NAME_DEF_STMT (gimple_vdef (clobber_stmt)) = clobber_stmt;
    2589          518 :         update_stmt (stmt);
    2590          518 :         i = gsi_for_stmt (stmt);
    2591          518 :         gsi_insert_before (&i, clobber_stmt, GSI_SAME_STMT);
    2592              :       }
    2593           13 :     else if (gimple_code (stmt) == GIMPLE_PHI)
    2594              :       {
    2595           12 :         if (!*visited)
    2596           12 :           *visited = new gimple_htab (10);
    2597              : 
    2598           12 :         slot = (*visited)->find_slot (stmt, INSERT);
    2599           12 :         if (*slot != NULL)
    2600            0 :           continue;
    2601              : 
    2602           12 :         *slot = stmt;
    2603           12 :         insert_clobber_before_stack_restore (gimple_phi_result (stmt), var,
    2604              :                                              visited);
    2605              :       }
    2606            1 :     else if (gimple_assign_ssa_name_copy_p (stmt))
    2607            0 :       insert_clobber_before_stack_restore (gimple_assign_lhs (stmt), var,
    2608          527 :                                            visited);
    2609          527 : }
    2610              : 
    2611              : /* Advance the iterator to the previous non-debug gimple statement in the same
    2612              :    or dominating basic block.  */
    2613              : 
    2614              : static inline void
    2615        12040 : gsi_prev_dom_bb_nondebug (gimple_stmt_iterator *i)
    2616              : {
    2617        12040 :   basic_block dom;
    2618              : 
    2619        12040 :   gsi_prev_nondebug (i);
    2620        24702 :   while (gsi_end_p (*i))
    2621              :     {
    2622          630 :       dom = get_immediate_dominator (CDI_DOMINATORS, gsi_bb (*i));
    2623          630 :       if (dom == NULL || dom == ENTRY_BLOCK_PTR_FOR_FN (cfun))
    2624              :         return;
    2625              : 
    2626         1244 :       *i = gsi_last_bb (dom);
    2627              :     }
    2628              : }
    2629              : 
    2630              : /* Find a BUILT_IN_STACK_SAVE dominating gsi_stmt (I), and insert
    2631              :    a clobber of VAR before each matching BUILT_IN_STACK_RESTORE.
    2632              : 
    2633              :    It is possible that BUILT_IN_STACK_SAVE cannot be found in a dominator when
    2634              :    a previous pass (such as DOM) duplicated it along multiple paths to a BB.
    2635              :    In that case the function gives up without inserting the clobbers.  */
    2636              : 
    2637              : static void
    2638          523 : insert_clobbers_for_var (gimple_stmt_iterator i, tree var)
    2639              : {
    2640          523 :   gimple *stmt;
    2641          523 :   tree saved_val;
    2642          523 :   gimple_htab *visited = NULL;
    2643              : 
    2644        12563 :   for (; !gsi_end_p (i); gsi_prev_dom_bb_nondebug (&i))
    2645              :     {
    2646        12555 :       stmt = gsi_stmt (i);
    2647              : 
    2648        12555 :       if (!gimple_call_builtin_p (stmt, BUILT_IN_STACK_SAVE))
    2649        12040 :         continue;
    2650              : 
    2651          515 :       saved_val = gimple_call_lhs (stmt);
    2652          515 :       if (saved_val == NULL_TREE)
    2653            0 :         continue;
    2654              : 
    2655          515 :       insert_clobber_before_stack_restore (saved_val, var, &visited);
    2656          515 :       break;
    2657              :     }
    2658              : 
    2659          523 :   delete visited;
    2660          523 : }
    2661              : 
    2662              : /* Detects a __builtin_alloca_with_align with constant size argument.  Declares
    2663              :    fixed-size array and returns the address, if found, otherwise returns
    2664              :    NULL_TREE.  */
    2665              : 
    2666              : static tree
    2667        12293 : fold_builtin_alloca_with_align (gimple *stmt)
    2668              : {
    2669        12293 :   unsigned HOST_WIDE_INT size, threshold, n_elem;
    2670        12293 :   tree lhs, arg, block, var, elem_type, array_type;
    2671              : 
    2672              :   /* Get lhs.  */
    2673        12293 :   lhs = gimple_call_lhs (stmt);
    2674        12293 :   if (lhs == NULL_TREE)
    2675              :     return NULL_TREE;
    2676              : 
    2677              :   /* Detect constant argument.  */
    2678        12293 :   arg = get_constant_value (gimple_call_arg (stmt, 0));
    2679        12293 :   if (arg == NULL_TREE
    2680         1089 :       || TREE_CODE (arg) != INTEGER_CST
    2681         1089 :       || !tree_fits_uhwi_p (arg))
    2682              :     return NULL_TREE;
    2683              : 
    2684         1089 :   size = tree_to_uhwi (arg);
    2685              : 
    2686              :   /* Heuristic: don't fold large allocas.  */
    2687         1089 :   threshold = (unsigned HOST_WIDE_INT)param_large_stack_frame;
    2688              :   /* In case the alloca is located at function entry, it has the same lifetime
    2689              :      as a declared array, so we allow a larger size.  */
    2690         1089 :   block = gimple_block (stmt);
    2691         1089 :   if (!(cfun->after_inlining
    2692          708 :         && block
    2693          680 :         && TREE_CODE (BLOCK_SUPERCONTEXT (block)) == FUNCTION_DECL))
    2694          704 :     threshold /= 10;
    2695         1089 :   if (size > threshold)
    2696              :     return NULL_TREE;
    2697              : 
    2698              :   /* We have to be able to move points-to info.  We used to assert
    2699              :      that we can but IPA PTA might end up with two UIDs here
    2700              :      as it might need to handle more than one instance being
    2701              :      live at the same time.  Instead of trying to detect this case
    2702              :      (using the first UID would be OK) just give up for now.  */
    2703          547 :   const pt_solution *pt = ssa_name_pt_solution (lhs);
    2704          547 :   unsigned uid = 0;
    2705          100 :   if (pt != NULL
    2706          185 :       && !pt->anything
    2707          611 :       && !pt_solution_singleton_or_null_p (pt, &uid))
    2708              :     return NULL_TREE;
    2709              : 
    2710              :   /* Declare array.  */
    2711          523 :   elem_type = build_nonstandard_integer_type (BITS_PER_UNIT, 1);
    2712          523 :   n_elem = size * 8 / BITS_PER_UNIT;
    2713          523 :   array_type = build_array_type_nelts (elem_type, n_elem);
    2714              : 
    2715          523 :   if (tree ssa_name = SSA_NAME_IDENTIFIER (lhs))
    2716              :     {
    2717              :       /* Give the temporary a name derived from the name of the VLA
    2718              :          declaration so it can be referenced in diagnostics.  */
    2719          481 :       const char *name = IDENTIFIER_POINTER (ssa_name);
    2720          481 :       var = create_tmp_var (array_type, name);
    2721              :     }
    2722              :   else
    2723           42 :     var = create_tmp_var (array_type);
    2724              : 
    2725          523 :   if (gimple *lhsdef = SSA_NAME_DEF_STMT (lhs))
    2726              :     {
    2727              :       /* Set the temporary's location to that of the VLA declaration
    2728              :          so it can be pointed to in diagnostics.  */
    2729          523 :       location_t loc = gimple_location (lhsdef);
    2730          523 :       DECL_SOURCE_LOCATION (var) = loc;
    2731              :     }
    2732              : 
    2733          523 :   SET_DECL_ALIGN (var, TREE_INT_CST_LOW (gimple_call_arg (stmt, 1)));
    2734          523 :   if (uid != 0)
    2735          140 :     SET_DECL_PT_UID (var, uid);
    2736              : 
    2737              :   /* Fold alloca to the address of the array.  */
    2738          523 :   return fold_convert (TREE_TYPE (lhs), build_fold_addr_expr (var));
    2739              : }
    2740              : 
    2741              : /* Fold the stmt at *GSI with CCP specific information that propagating
    2742              :    and regular folding does not catch.  */
    2743              : 
    2744              : bool
    2745    364907875 : ccp_folder::fold_stmt (gimple_stmt_iterator *gsi)
    2746              : {
    2747    364907875 :   gimple *stmt = gsi_stmt (*gsi);
    2748              : 
    2749    364907875 :   switch (gimple_code (stmt))
    2750              :     {
    2751     19174091 :     case GIMPLE_COND:
    2752     19174091 :       {
    2753     19174091 :         gcond *cond_stmt = as_a <gcond *> (stmt);
    2754     19174091 :         ccp_prop_value_t val;
    2755              :         /* Statement evaluation will handle type mismatches in constants
    2756              :            more gracefully than the final propagation.  This allows us to
    2757              :            fold more conditionals here.  */
    2758     19174091 :         val = evaluate_stmt (stmt);
    2759     19174091 :         if (val.lattice_val != CONSTANT
    2760     19174091 :             || val.mask != 0)
    2761              :           return false;
    2762              : 
    2763       479263 :         if (dump_file)
    2764              :           {
    2765           24 :             fprintf (dump_file, "Folding predicate ");
    2766           24 :             print_gimple_expr (dump_file, stmt, 0);
    2767           24 :             fprintf (dump_file, " to ");
    2768           24 :             print_generic_expr (dump_file, val.value);
    2769           24 :             fprintf (dump_file, "\n");
    2770              :           }
    2771              : 
    2772       479263 :         if (integer_zerop (val.value))
    2773       355489 :           gimple_cond_make_false (cond_stmt);
    2774              :         else
    2775       123774 :           gimple_cond_make_true (cond_stmt);
    2776              : 
    2777              :         return true;
    2778     19174091 :       }
    2779              : 
    2780     24227520 :     case GIMPLE_CALL:
    2781     24227520 :       {
    2782     24227520 :         tree lhs = gimple_call_lhs (stmt);
    2783     24227520 :         int flags = gimple_call_flags (stmt);
    2784     24227520 :         tree val;
    2785     24227520 :         tree argt;
    2786     24227520 :         bool changed = false;
    2787     24227520 :         unsigned i;
    2788              : 
    2789              :         /* If the call was folded into a constant make sure it goes
    2790              :            away even if we cannot propagate into all uses because of
    2791              :            type issues.  */
    2792     24227520 :         if (lhs
    2793      9251698 :             && TREE_CODE (lhs) == SSA_NAME
    2794      7725557 :             && (val = get_constant_value (lhs))
    2795              :             /* Don't optimize away calls that have side-effects.  */
    2796           15 :             && (flags & (ECF_CONST|ECF_PURE)) != 0
    2797     24227520 :             && (flags & ECF_LOOPING_CONST_OR_PURE) == 0)
    2798              :           {
    2799            0 :             tree new_rhs = unshare_expr (val);
    2800            0 :             if (!useless_type_conversion_p (TREE_TYPE (lhs),
    2801            0 :                                             TREE_TYPE (new_rhs)))
    2802            0 :               new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs);
    2803            0 :             gimplify_and_update_call_from_tree (gsi, new_rhs);
    2804            0 :             return true;
    2805              :           }
    2806              : 
    2807              :         /* Internal calls provide no argument types, so the extra laxity
    2808              :            for normal calls does not apply.  */
    2809     24227520 :         if (gimple_call_internal_p (stmt))
    2810              :           return false;
    2811              : 
    2812              :         /* The heuristic of fold_builtin_alloca_with_align differs before and
    2813              :            after inlining, so we don't require the arg to be changed into a
    2814              :            constant for folding, but just to be constant.  */
    2815     23429049 :         if (gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN)
    2816     23429049 :             || gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX))
    2817              :           {
    2818        12293 :             tree new_rhs = fold_builtin_alloca_with_align (stmt);
    2819        12293 :             if (new_rhs)
    2820              :               {
    2821          523 :                 gimplify_and_update_call_from_tree (gsi, new_rhs);
    2822          523 :                 tree var = TREE_OPERAND (TREE_OPERAND (new_rhs, 0),0);
    2823          523 :                 insert_clobbers_for_var (*gsi, var);
    2824          523 :                 return true;
    2825              :               }
    2826              :           }
    2827              : 
    2828              :         /* If there's no extra info from an assume_aligned call,
    2829              :            drop it so it doesn't act as otherwise useless dataflow
    2830              :            barrier.  */
    2831     23428526 :         if (gimple_call_builtin_p (stmt, BUILT_IN_ASSUME_ALIGNED))
    2832              :           {
    2833         3195 :             tree ptr = gimple_call_arg (stmt, 0);
    2834         3195 :             ccp_prop_value_t ptrval = get_value_for_expr (ptr, true);
    2835         3195 :             if (ptrval.lattice_val == CONSTANT
    2836          386 :                 && TREE_CODE (ptrval.value) == INTEGER_CST
    2837         3581 :                 && ptrval.mask != 0)
    2838              :               {
    2839          386 :                 ccp_prop_value_t val
    2840          386 :                   = bit_value_assume_aligned (stmt, NULL_TREE, ptrval, false);
    2841          386 :                 unsigned int ptralign = least_bit_hwi (ptrval.mask.to_uhwi ());
    2842          386 :                 unsigned int align = least_bit_hwi (val.mask.to_uhwi ());
    2843          386 :                 if (ptralign == align
    2844          386 :                     && ((TREE_INT_CST_LOW (ptrval.value) & (align - 1))
    2845          368 :                         == (TREE_INT_CST_LOW (val.value) & (align - 1))))
    2846              :                   {
    2847          368 :                     replace_call_with_value (gsi, ptr);
    2848          368 :                     return true;
    2849              :                   }
    2850          386 :               }
    2851         3195 :           }
    2852              : 
    2853              :         /* Propagate into the call arguments.  Compared to replace_uses_in
    2854              :            this can use the argument slot types for type verification
    2855              :            instead of the current argument type.  We also can safely
    2856              :            drop qualifiers here as we are dealing with constants anyway.  */
    2857     23428158 :         argt = TYPE_ARG_TYPES (gimple_call_fntype (stmt));
    2858     64993976 :         for (i = 0; i < gimple_call_num_args (stmt) && argt;
    2859     41565818 :              ++i, argt = TREE_CHAIN (argt))
    2860              :           {
    2861     41565818 :             tree arg = gimple_call_arg (stmt, i);
    2862     41565818 :             if (TREE_CODE (arg) == SSA_NAME
    2863     16143037 :                 && (val = get_constant_value (arg))
    2864     41565848 :                 && useless_type_conversion_p
    2865           30 :                      (TYPE_MAIN_VARIANT (TREE_VALUE (argt)),
    2866           30 :                       TYPE_MAIN_VARIANT (TREE_TYPE (val))))
    2867              :               {
    2868           30 :                 gimple_call_set_arg (stmt, i, unshare_expr (val));
    2869           30 :                 changed = true;
    2870              :               }
    2871              :           }
    2872              : 
    2873              :         return changed;
    2874              :       }
    2875              : 
    2876    109806843 :     case GIMPLE_ASSIGN:
    2877    109806843 :       {
    2878    109806843 :         tree lhs = gimple_assign_lhs (stmt);
    2879    109806843 :         tree val;
    2880              : 
    2881              :         /* If we have a load that turned out to be constant replace it
    2882              :            as we cannot propagate into all uses in all cases.  */
    2883    109806843 :         if (gimple_assign_single_p (stmt)
    2884     73375277 :             && TREE_CODE (lhs) == SSA_NAME
    2885    143621257 :             && (val = get_constant_value (lhs)))
    2886              :           {
    2887         5264 :             tree rhs = unshare_expr (val);
    2888         5264 :             if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
    2889            0 :               rhs = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
    2890         5264 :             gimple_assign_set_rhs_from_tree (gsi, rhs);
    2891         5264 :             return true;
    2892              :           }
    2893              : 
    2894              :         return false;
    2895              :       }
    2896              : 
    2897              :     default:
    2898              :       return false;
    2899              :     }
    2900              : }
    2901              : 
    2902              : /* Visit the assignment statement STMT.  Set the value of its LHS to the
    2903              :    value computed by the RHS and store LHS in *OUTPUT_P.  If STMT
    2904              :    creates virtual definitions, set the value of each new name to that
    2905              :    of the RHS (if we can derive a constant out of the RHS).
    2906              :    Value-returning call statements also perform an assignment, and
    2907              :    are handled here.  */
    2908              : 
    2909              : static enum ssa_prop_result
    2910    203471392 : visit_assignment (gimple *stmt, tree *output_p)
    2911              : {
    2912    203471392 :   ccp_prop_value_t val;
    2913    203471392 :   enum ssa_prop_result retval = SSA_PROP_NOT_INTERESTING;
    2914              : 
    2915    203471392 :   tree lhs = gimple_get_lhs (stmt);
    2916    203471392 :   if (TREE_CODE (lhs) == SSA_NAME)
    2917              :     {
    2918              :       /* Evaluate the statement, which could be
    2919              :          either a GIMPLE_ASSIGN or a GIMPLE_CALL.  */
    2920    202026241 :       val = evaluate_stmt (stmt);
    2921              : 
    2922              :       /* If STMT is an assignment to an SSA_NAME, we only have one
    2923              :          value to set.  */
    2924    202026241 :       if (set_lattice_value (lhs, &val))
    2925              :         {
    2926    187535983 :           *output_p = lhs;
    2927    187535983 :           if (val.lattice_val == VARYING)
    2928              :             retval = SSA_PROP_VARYING;
    2929              :           else
    2930    127696339 :             retval = SSA_PROP_INTERESTING;
    2931              :         }
    2932              :     }
    2933              : 
    2934    203471392 :   return retval;
    2935    203471392 : }
    2936              : 
    2937              : 
    2938              : /* Visit the conditional statement STMT.  Return SSA_PROP_INTERESTING
    2939              :    if it can determine which edge will be taken.  Otherwise, return
    2940              :    SSA_PROP_VARYING.  */
    2941              : 
    2942              : static enum ssa_prop_result
    2943     24251089 : visit_cond_stmt (gimple *stmt, edge *taken_edge_p)
    2944              : {
    2945     24251089 :   ccp_prop_value_t val;
    2946     24251089 :   basic_block block;
    2947              : 
    2948     24251089 :   block = gimple_bb (stmt);
    2949     24251089 :   val = evaluate_stmt (stmt);
    2950     24251089 :   if (val.lattice_val != CONSTANT
    2951     24251089 :       || val.mask != 0)
    2952              :     return SSA_PROP_VARYING;
    2953              : 
    2954              :   /* Find which edge out of the conditional block will be taken and add it
    2955              :      to the worklist.  If no single edge can be determined statically,
    2956              :      return SSA_PROP_VARYING to feed all the outgoing edges to the
    2957              :      propagation engine.  */
    2958      5554682 :   *taken_edge_p = find_taken_edge (block, val.value);
    2959      5554682 :   if (*taken_edge_p)
    2960              :     return SSA_PROP_INTERESTING;
    2961              :   else
    2962            0 :     return SSA_PROP_VARYING;
    2963     24251089 : }
    2964              : 
    2965              : 
    2966              : /* Evaluate statement STMT.  If the statement produces an output value and
    2967              :    its evaluation changes the lattice value of its output, return
    2968              :    SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the
    2969              :    output value.
    2970              : 
    2971              :    If STMT is a conditional branch and we can determine its truth
    2972              :    value, set *TAKEN_EDGE_P accordingly.  If STMT produces a varying
    2973              :    value, return SSA_PROP_VARYING.  */
    2974              : 
    2975              : enum ssa_prop_result
    2976    240080733 : ccp_propagate::visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p)
    2977              : {
    2978    240080733 :   tree def;
    2979    240080733 :   ssa_op_iter iter;
    2980              : 
    2981    240080733 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2982              :     {
    2983          100 :       fprintf (dump_file, "\nVisiting statement:\n");
    2984          100 :       print_gimple_stmt (dump_file, stmt, 0, dump_flags);
    2985              :     }
    2986              : 
    2987    240080733 :   switch (gimple_code (stmt))
    2988              :     {
    2989    198035988 :       case GIMPLE_ASSIGN:
    2990              :         /* If the statement is an assignment that produces a single
    2991              :            output value, evaluate its RHS to see if the lattice value of
    2992              :            its output has changed.  */
    2993    198035988 :         return visit_assignment (stmt, output_p);
    2994              : 
    2995     10960287 :       case GIMPLE_CALL:
    2996              :         /* A value-returning call also performs an assignment.  */
    2997     10960287 :         if (gimple_call_lhs (stmt) != NULL_TREE)
    2998      5435404 :           return visit_assignment (stmt, output_p);
    2999              :         break;
    3000              : 
    3001     24251089 :       case GIMPLE_COND:
    3002     24251089 :       case GIMPLE_SWITCH:
    3003              :         /* If STMT is a conditional branch, see if we can determine
    3004              :            which branch will be taken.   */
    3005              :         /* FIXME.  It appears that we should be able to optimize
    3006              :            computed GOTOs here as well.  */
    3007     24251089 :         return visit_cond_stmt (stmt, taken_edge_p);
    3008              : 
    3009              :       default:
    3010              :         break;
    3011              :     }
    3012              : 
    3013              :   /* Any other kind of statement is not interesting for constant
    3014              :      propagation and, therefore, not worth simulating.  */
    3015     12358252 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3016           42 :     fprintf (dump_file, "No interesting values produced.  Marked VARYING.\n");
    3017              : 
    3018              :   /* Definitions made by statements other than assignments to
    3019              :      SSA_NAMEs represent unknown modifications to their outputs.
    3020              :      Mark them VARYING.  */
    3021     17201368 :   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
    3022      4843116 :     set_value_varying (def);
    3023              : 
    3024              :   return SSA_PROP_VARYING;
    3025              : }
    3026              : 
    3027              : 
    3028              : /* Main entry point for SSA Conditional Constant Propagation.  If NONZERO_P,
    3029              :    record nonzero bits.  */
    3030              : 
    3031              : static unsigned int
    3032      5714131 : do_ssa_ccp (bool nonzero_p)
    3033              : {
    3034      5714131 :   unsigned int todo = 0;
    3035              : 
    3036              :   /* We want to minimize the number of latches to reduce iteration.  */
    3037      5714131 :   loop_optimizer_init (LOOPS_HAVE_SIMPLE_LATCHES);
    3038              : 
    3039      5714131 :   calculate_dominance_info (CDI_DOMINATORS);
    3040              : 
    3041      5714131 :   ccp_initialize ();
    3042      5714131 :   class ccp_propagate ccp_propagate;
    3043      5714131 :   ccp_propagate.ssa_propagate ();
    3044     11319074 :   if (ccp_finalize (nonzero_p || flag_ipa_bit_cp))
    3045              :     {
    3046      1721275 :       todo = TODO_cleanup_cfg;
    3047              : 
    3048              :       /* ccp_finalize does not preserve loop-closed ssa.  */
    3049      1721275 :       loops_state_clear (LOOP_CLOSED_SSA);
    3050              :     }
    3051              : 
    3052      5714131 :   free_dominance_info (CDI_DOMINATORS);
    3053              : 
    3054      5714131 :   loop_optimizer_finalize ();
    3055              : 
    3056      5714131 :   return todo;
    3057      5714131 : }
    3058              : 
    3059              : 
    3060              : namespace {
    3061              : 
    3062              : const pass_data pass_data_ccp =
    3063              : {
    3064              :   GIMPLE_PASS, /* type */
    3065              :   "ccp", /* name */
    3066              :   OPTGROUP_NONE, /* optinfo_flags */
    3067              :   TV_TREE_CCP, /* tv_id */
    3068              :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    3069              :   0, /* properties_provided */
    3070              :   0, /* properties_destroyed */
    3071              :   0, /* todo_flags_start */
    3072              :   TODO_update_address_taken, /* todo_flags_finish */
    3073              : };
    3074              : 
    3075              : class pass_ccp : public gimple_opt_pass
    3076              : {
    3077              : public:
    3078      1485900 :   pass_ccp (gcc::context *ctxt)
    3079      2971800 :     : gimple_opt_pass (pass_data_ccp, ctxt), nonzero_p (false)
    3080              :   {}
    3081              : 
    3082              :   /* opt_pass methods: */
    3083      1188720 :   opt_pass * clone () final override { return new pass_ccp (m_ctxt); }
    3084      1485900 :   void set_pass_param (unsigned int n, bool param) final override
    3085              :     {
    3086      1485900 :       gcc_assert (n == 0);
    3087      1485900 :       nonzero_p = param;
    3088      1485900 :     }
    3089      5716205 :   bool gate (function *) final override { return flag_tree_ccp != 0; }
    3090      5714131 :   unsigned int execute (function *) final override
    3091              :   {
    3092      5714131 :     return do_ssa_ccp (nonzero_p);
    3093              :   }
    3094              : 
    3095              :  private:
    3096              :   /* Determines whether the pass instance records nonzero bits.  */
    3097              :   bool nonzero_p;
    3098              : }; // class pass_ccp
    3099              : 
    3100              : } // anon namespace
    3101              : 
    3102              : gimple_opt_pass *
    3103       297180 : make_pass_ccp (gcc::context *ctxt)
    3104              : {
    3105       297180 :   return new pass_ccp (ctxt);
    3106              : }
    3107              : 
    3108              : /* A simple pass that emits some warnings post IPA.  */
    3109              : 
    3110              : namespace {
    3111              : 
    3112              : const pass_data pass_data_post_ipa_warn =
    3113              : {
    3114              :   GIMPLE_PASS, /* type */
    3115              :   "post_ipa_warn", /* name */
    3116              :   OPTGROUP_NONE, /* optinfo_flags */
    3117              :   TV_NONE, /* tv_id */
    3118              :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    3119              :   0, /* properties_provided */
    3120              :   0, /* properties_destroyed */
    3121              :   0, /* todo_flags_start */
    3122              :   0, /* todo_flags_finish */
    3123              : };
    3124              : 
    3125              : class pass_post_ipa_warn : public gimple_opt_pass
    3126              : {
    3127              : public:
    3128       594360 :   pass_post_ipa_warn (gcc::context *ctxt)
    3129      1188720 :     : gimple_opt_pass (pass_data_post_ipa_warn, ctxt)
    3130              :   {}
    3131              : 
    3132              :   /* opt_pass methods: */
    3133       297180 :   opt_pass * clone () final override { return new pass_post_ipa_warn (m_ctxt); }
    3134      1065452 :   bool gate (function *) final override { return warn_nonnull != 0; }
    3135              :   unsigned int execute (function *) final override;
    3136              : 
    3137              : }; // class pass_fold_builtins
    3138              : 
    3139              : unsigned int
    3140       113149 : pass_post_ipa_warn::execute (function *fun)
    3141              : {
    3142       113149 :   basic_block bb;
    3143       113149 :   gimple_ranger *ranger = NULL;
    3144              : 
    3145      1132946 :   FOR_EACH_BB_FN (bb, fun)
    3146              :     {
    3147      1019797 :       gimple_stmt_iterator gsi;
    3148     11004514 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    3149              :         {
    3150      8964920 :           gimple *stmt = gsi_stmt (gsi);
    3151      8964920 :           if (!is_gimple_call (stmt) || warning_suppressed_p (stmt, OPT_Wnonnull))
    3152      8407126 :             continue;
    3153              : 
    3154       557794 :           tree fntype = gimple_call_fntype (stmt);
    3155       557794 :           if (!fntype)
    3156         5578 :             continue;
    3157       552216 :           bitmap nonnullargs = get_nonnull_args (fntype);
    3158              : 
    3159       552216 :           tree fndecl = gimple_call_fndecl (stmt);
    3160      1070899 :           const bool closure = fndecl && DECL_LAMBDA_FUNCTION_P (fndecl);
    3161              : 
    3162       813505 :           for (unsigned i = nonnullargs ? 0 : ~0U;
    3163       813505 :                i < gimple_call_num_args (stmt); i++)
    3164              :             {
    3165       261289 :               tree arg = gimple_call_arg (stmt, i);
    3166       261289 :               if (TREE_CODE (TREE_TYPE (arg)) != POINTER_TYPE)
    3167       261184 :                 continue;
    3168       164493 :               if (!integer_zerop (arg))
    3169       156264 :                 continue;
    3170         8229 :               if (i == 0 && closure)
    3171              :                 /* Avoid warning for the first argument to lambda functions.  */
    3172           14 :                 continue;
    3173         8215 :               if (!bitmap_empty_p (nonnullargs)
    3174         8215 :                   && !bitmap_bit_p (nonnullargs, i))
    3175         8095 :                 continue;
    3176              : 
    3177              :               /* In C++ non-static member functions argument 0 refers
    3178              :                  to the implicit this pointer.  Use the same one-based
    3179              :                  numbering for ordinary arguments.  */
    3180          120 :               unsigned argno = TREE_CODE (fntype) == METHOD_TYPE ? i : i + 1;
    3181          120 :               location_t loc = (EXPR_HAS_LOCATION (arg)
    3182            0 :                                 ? EXPR_LOCATION (arg)
    3183          120 :                                 : gimple_location (stmt));
    3184          120 :               auto_diagnostic_group d;
    3185          120 :               if (argno == 0)
    3186              :                 {
    3187           21 :                   if (warning_at (loc, OPT_Wnonnull,
    3188              :                                   "%qs pointer is null", "this")
    3189           15 :                       && fndecl)
    3190            9 :                     inform (DECL_SOURCE_LOCATION (fndecl),
    3191              :                             "in a call to non-static member function %qD",
    3192              :                             fndecl);
    3193           15 :                   continue;
    3194              :                 }
    3195              : 
    3196          105 :               if (!warning_at (loc, OPT_Wnonnull,
    3197              :                                "argument %u null where non-null "
    3198              :                                "expected", argno))
    3199            0 :                 continue;
    3200              : 
    3201          105 :               tree fndecl = gimple_call_fndecl (stmt);
    3202          105 :               if (fndecl && DECL_IS_UNDECLARED_BUILTIN (fndecl))
    3203           53 :                 inform (loc, "in a call to built-in function %qD",
    3204              :                         fndecl);
    3205           52 :               else if (fndecl)
    3206           52 :                 inform (DECL_SOURCE_LOCATION (fndecl),
    3207              :                         "in a call to function %qD declared %qs",
    3208              :                         fndecl, "nonnull");
    3209          120 :             }
    3210       552216 :           BITMAP_FREE (nonnullargs);
    3211              : 
    3212       552216 :           for (tree attrs = TYPE_ATTRIBUTES (fntype);
    3213       590498 :                (attrs = lookup_attribute ("nonnull_if_nonzero", attrs));
    3214        38282 :                attrs = TREE_CHAIN (attrs))
    3215              :             {
    3216        38282 :               tree args = TREE_VALUE (attrs);
    3217        38282 :               unsigned int idx = TREE_INT_CST_LOW (TREE_VALUE (args)) - 1;
    3218        38282 :               unsigned int idx2
    3219        38282 :                 = TREE_INT_CST_LOW (TREE_VALUE (TREE_CHAIN (args))) - 1;
    3220        38282 :               unsigned int idx3 = idx2;
    3221        38282 :               if (tree chain2 = TREE_CHAIN (TREE_CHAIN (args)))
    3222          923 :                 idx3 = TREE_INT_CST_LOW (TREE_VALUE (chain2)) - 1;
    3223        38282 :               if (idx < gimple_call_num_args (stmt)
    3224        38281 :                   && idx2 < gimple_call_num_args (stmt)
    3225        76562 :                   && idx3 < gimple_call_num_args (stmt))
    3226              :                 {
    3227        38280 :                   tree arg = gimple_call_arg (stmt, idx);
    3228        38280 :                   tree arg2 = gimple_call_arg (stmt, idx2);
    3229        38280 :                   tree arg3 = gimple_call_arg (stmt, idx3);
    3230        38280 :                   if (TREE_CODE (TREE_TYPE (arg)) != POINTER_TYPE
    3231        38191 :                       || !integer_zerop (arg)
    3232          290 :                       || !INTEGRAL_TYPE_P (TREE_TYPE (arg2))
    3233          290 :                       || !INTEGRAL_TYPE_P (TREE_TYPE (arg3))
    3234          290 :                       || integer_zerop (arg2)
    3235          214 :                       || integer_zerop (arg3)
    3236        38466 :                       || ((TREE_CODE (fntype) == METHOD_TYPE || closure)
    3237            0 :                           && (idx == 0 || idx2 == 0 || idx3 == 0)))
    3238        38150 :                     continue;
    3239          186 :                   if (!integer_nonzerop (arg2)
    3240          186 :                       && !tree_expr_nonzero_p (arg2))
    3241              :                     {
    3242           98 :                       if (TREE_CODE (arg2) != SSA_NAME || optimize < 2)
    3243           56 :                         continue;
    3244           98 :                       if (!ranger)
    3245           14 :                         ranger = enable_ranger (cfun);
    3246              : 
    3247           98 :                       int_range_max vr;
    3248          196 :                       get_range_query (cfun)->range_of_expr (vr, arg2, stmt);
    3249           98 :                       if (range_includes_zero_p (vr))
    3250           56 :                         continue;
    3251           98 :                     }
    3252          130 :                   if (idx2 != idx3
    3253           45 :                       && !integer_nonzerop (arg3)
    3254          153 :                       && !tree_expr_nonzero_p (arg3))
    3255              :                     {
    3256           20 :                       if (TREE_CODE (arg3) != SSA_NAME || optimize < 2)
    3257            0 :                         continue;
    3258           20 :                       if (!ranger)
    3259            0 :                         ranger = enable_ranger (cfun);
    3260              : 
    3261           20 :                       int_range_max vr;
    3262           40 :                       get_range_query (cfun)->range_of_expr (vr, arg3, stmt);
    3263           20 :                       if (range_includes_zero_p (vr))
    3264            0 :                         continue;
    3265           20 :                     }
    3266          130 :                   unsigned argno = idx + 1;
    3267          130 :                   unsigned argno2 = idx2 + 1;
    3268          130 :                   unsigned argno3 = idx3 + 1;
    3269          130 :                   location_t loc = (EXPR_HAS_LOCATION (arg)
    3270            0 :                                     ? EXPR_LOCATION (arg)
    3271          130 :                                     : gimple_location (stmt));
    3272          130 :                   auto_diagnostic_group d;
    3273              : 
    3274          130 :                   if (idx2 != idx3)
    3275              :                     {
    3276           45 :                       if (!warning_at (loc, OPT_Wnonnull,
    3277              :                                        "argument %u null where non-null "
    3278              :                                        "expected because arguments %u and %u "
    3279              :                                        "are nonzero", argno, argno2, argno3))
    3280            0 :                         continue;
    3281              :                     }
    3282           85 :                   else if (!warning_at (loc, OPT_Wnonnull,
    3283              :                                         "argument %u null where non-null "
    3284              :                                         "expected because argument %u is "
    3285              :                                         "nonzero", argno, argno2))
    3286            0 :                     continue;
    3287              : 
    3288          130 :                   tree fndecl = gimple_call_fndecl (stmt);
    3289          130 :                   if (fndecl && DECL_IS_UNDECLARED_BUILTIN (fndecl))
    3290           37 :                     inform (loc, "in a call to built-in function %qD",
    3291              :                             fndecl);
    3292           93 :                   else if (fndecl)
    3293           93 :                     inform (DECL_SOURCE_LOCATION (fndecl),
    3294              :                             "in a call to function %qD declared %qs",
    3295              :                             fndecl, "nonnull_if_nonzero");
    3296          130 :                 }
    3297              :             }
    3298              :         }
    3299              :     }
    3300       113149 :   if (ranger)
    3301           14 :     disable_ranger (cfun);
    3302       113149 :   return 0;
    3303              : }
    3304              : 
    3305              : } // anon namespace
    3306              : 
    3307              : gimple_opt_pass *
    3308       297180 : make_pass_post_ipa_warn (gcc::context *ctxt)
    3309              : {
    3310       297180 :   return new pass_post_ipa_warn (ctxt);
    3311              : }
        

Generated by: LCOV version 2.5.0-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.