gcc/tree-ssa-ccp.c

   1 /* Conditional constant propagation pass for the GNU compiler.
   2    Copyright (C) 2000-2021 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.c).  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 infomation 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-fold.h"
 133 #include "tree-eh.h"
 134 #include "gimplify.h"
 135 #include "gimple-iterator.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 "ipa-prop.h"
 154
 155 /* Possible lattice values.  */
 156 typedef enum
 157 {
 158   UNINITIALIZED,
 159   UNDEFINED,
 160   CONSTANT,
 161   VARYING
 162 } ccp_lattice_t;
 163
 164 class ccp_prop_value_t {
 165 public:
 166     /* Lattice value.  */
 167     ccp_lattice_t lattice_val;
 168
 169     /* Propagated value.  */
 170     tree value;
 171
 172     /* Mask that applies to the propagated value during CCP.  For X
 173        with a CONSTANT lattice value X & ~mask == value & ~mask.  The
 174        zero bits in the mask cover constant values.  The ones mean no
 175        information.  */
 176     widest_int mask;
 177 };
 178
 179 class ccp_propagate : public ssa_propagation_engine
 180 {
 181  public:
 182   enum ssa_prop_result visit_stmt (gimple *, edge *, tree *) FINAL OVERRIDE;
 183   enum ssa_prop_result visit_phi (gphi *) FINAL OVERRIDE;
 184 };
 185
 186 /* Array of propagated constant values.  After propagation,
 187    CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I).  If
 188    the constant is held in an SSA name representing a memory store
 189    (i.e., a VDEF), CONST_VAL[I].MEM_REF will contain the actual
 190    memory reference used to store (i.e., the LHS of the assignment
 191    doing the store).  */
 192 static ccp_prop_value_t *const_val;
 193 static unsigned n_const_val;
 194
 195 static void canonicalize_value (ccp_prop_value_t *);
 196 static void ccp_lattice_meet (ccp_prop_value_t *, ccp_prop_value_t *);
 197
 198 /* Dump constant propagation value VAL to file OUTF prefixed by PREFIX.  */
 199
 200 static void
 201 dump_lattice_value (FILE *outf, const char *prefix, ccp_prop_value_t val)
 202 {
 203   switch (val.lattice_val)
 204     {
 205     case UNINITIALIZED:
 206       fprintf (outf, "%sUNINITIALIZED", prefix);
 207       break;
 208     case UNDEFINED:
 209       fprintf (outf, "%sUNDEFINED", prefix);
 210       break;
 211     case VARYING:
 212       fprintf (outf, "%sVARYING", prefix);
 213       break;
 214     case CONSTANT:
 215       if (TREE_CODE (val.value) != INTEGER_CST
 216           || val.mask == 0)
 217         {
 218           fprintf (outf, "%sCONSTANT ", prefix);
 219           print_generic_expr (outf, val.value, dump_flags);
 220         }
 221       else
 222         {
 223           widest_int cval = wi::bit_and_not (wi::to_widest (val.value),
 224                                              val.mask);
 225           fprintf (outf, "%sCONSTANT ", prefix);
 226           print_hex (cval, outf);
 227           fprintf (outf, " (");
 228           print_hex (val.mask, outf);
 229           fprintf (outf, ")");
 230         }
 231       break;
 232     default:
 233       gcc_unreachable ();
 234     }
 235 }
 236
 237
 238 /* Print lattice value VAL to stderr.  */
 239
 240 void debug_lattice_value (ccp_prop_value_t val);
 241
 242 DEBUG_FUNCTION void
 243 debug_lattice_value (ccp_prop_value_t val)
 244 {
 245   dump_lattice_value (stderr, "", val);
 246   fprintf (stderr, "\n");
 247 }
 248
 249 /* Extend NONZERO_BITS to a full mask, based on sgn.  */
 250
 251 static widest_int
 252 extend_mask (const wide_int &nonzero_bits, signop sgn)
 253 {
 254   return widest_int::from (nonzero_bits, sgn);
 255 }
 256
 257 /* Compute a default value for variable VAR and store it in the
 258    CONST_VAL array.  The following rules are used to get default
 259    values:
 260
 261    1- Global and static variables that are declared constant are
 262       considered CONSTANT.
 263
 264    2- Any other value is considered UNDEFINED.  This is useful when
 265       considering PHI nodes.  PHI arguments that are undefined do not
 266       change the constant value of the PHI node, which allows for more
 267       constants to be propagated.
 268
 269    3- Variables defined by statements other than assignments and PHI
 270       nodes are considered VARYING.
 271
 272    4- Initial values of variables that are not GIMPLE registers are
 273       considered VARYING.  */
 274
 275 static ccp_prop_value_t
 276 get_default_value (tree var)
 277 {
 278   ccp_prop_value_t val = { UNINITIALIZED, NULL_TREE, 0 };
 279   gimple *stmt;
 280
 281   stmt = SSA_NAME_DEF_STMT (var);
 282
 283   if (gimple_nop_p (stmt))
 284     {
 285       /* Variables defined by an empty statement are those used
 286          before being initialized.  If VAR is a local variable, we
 287          can assume initially that it is UNDEFINED, otherwise we must
 288          consider it VARYING.  */
 289       if (!virtual_operand_p (var)
 290           && SSA_NAME_VAR (var)
 291           && TREE_CODE (SSA_NAME_VAR (var)) == VAR_DECL)
 292         val.lattice_val = UNDEFINED;
 293       else
 294         {
 295           val.lattice_val = VARYING;
 296           val.mask = -1;
 297           if (flag_tree_bit_ccp)
 298             {
 299               wide_int nonzero_bits = get_nonzero_bits (var);
 300               tree value;
 301               widest_int mask;
 302
 303               if (SSA_NAME_VAR (var)
 304                   && TREE_CODE (SSA_NAME_VAR (var)) == PARM_DECL
 305                   && ipcp_get_parm_bits (SSA_NAME_VAR (var), &value, &mask))
 306                 {
 307                   val.lattice_val = CONSTANT;
 308                   val.value = value;
 309                   widest_int ipa_value = wi::to_widest (value);
 310                   /* Unknown bits from IPA CP must be equal to zero.  */
 311                   gcc_assert (wi::bit_and (ipa_value, mask) == 0);
 312                   val.mask = mask;
 313                   if (nonzero_bits != -1)
 314                     val.mask &= extend_mask (nonzero_bits,
 315                                              TYPE_SIGN (TREE_TYPE (var)));
 316                 }
 317               else if (nonzero_bits != -1)
 318                 {
 319                   val.lattice_val = CONSTANT;
 320                   val.value = build_zero_cst (TREE_TYPE (var));
 321                   val.mask = extend_mask (nonzero_bits,
 322                                           TYPE_SIGN (TREE_TYPE (var)));
 323                 }
 324             }
 325         }
 326     }
 327   else if (is_gimple_assign (stmt))
 328     {
 329       tree cst;
 330       if (gimple_assign_single_p (stmt)
 331           && DECL_P (gimple_assign_rhs1 (stmt))
 332           && (cst = get_symbol_constant_value (gimple_assign_rhs1 (stmt))))
 333         {
 334           val.lattice_val = CONSTANT;
 335           val.value = cst;
 336         }
 337       else
 338         {
 339           /* Any other variable defined by an assignment is considered
 340              UNDEFINED.  */
 341           val.lattice_val = UNDEFINED;
 342         }
 343     }
 344   else if ((is_gimple_call (stmt)
 345             && gimple_call_lhs (stmt) != NULL_TREE)
 346            || gimple_code (stmt) == GIMPLE_PHI)
 347     {
 348       /* A variable defined by a call or a PHI node is considered
 349          UNDEFINED.  */
 350       val.lattice_val = UNDEFINED;
 351     }
 352   else
 353     {
 354       /* Otherwise, VAR will never take on a constant value.  */
 355       val.lattice_val = VARYING;
 356       val.mask = -1;
 357     }
 358
 359   return val;
 360 }
 361
 362
 363 /* Get the constant value associated with variable VAR.  */
 364
 365 static inline ccp_prop_value_t *
 366 get_value (tree var)
 367 {
 368   ccp_prop_value_t *val;
 369
 370   if (const_val == NULL
 371       || SSA_NAME_VERSION (var) >= n_const_val)
 372     return NULL;
 373
 374   val = &const_val[SSA_NAME_VERSION (var)];
 375   if (val->lattice_val == UNINITIALIZED)
 376     *val = get_default_value (var);
 377
 378   canonicalize_value (val);
 379
 380   return val;
 381 }
 382
 383 /* Return the constant tree value associated with VAR.  */
 384
 385 static inline tree
 386 get_constant_value (tree var)
 387 {
 388   ccp_prop_value_t *val;
 389   if (TREE_CODE (var) != SSA_NAME)
 390     {
 391       if (is_gimple_min_invariant (var))
 392         return var;
 393       return NULL_TREE;
 394     }
 395   val = get_value (var);
 396   if (val
 397       && val->lattice_val == CONSTANT
 398       && (TREE_CODE (val->value) != INTEGER_CST
 399           || val->mask == 0))
 400     return val->value;
 401   return NULL_TREE;
 402 }
 403
 404 /* Sets the value associated with VAR to VARYING.  */
 405
 406 static inline void
 407 set_value_varying (tree var)
 408 {
 409   ccp_prop_value_t *val = &const_val[SSA_NAME_VERSION (var)];
 410
 411   val->lattice_val = VARYING;
 412   val->value = NULL_TREE;
 413   val->mask = -1;
 414 }
 415
 416 /* For integer constants, make sure to drop TREE_OVERFLOW.  */
 417
 418 static void
 419 canonicalize_value (ccp_prop_value_t *val)
 420 {
 421   if (val->lattice_val != CONSTANT)
 422     return;
 423
 424   if (TREE_OVERFLOW_P (val->value))
 425     val->value = drop_tree_overflow (val->value);
 426 }
 427
 428 /* Return whether the lattice transition is valid.  */
 429
 430 static bool
 431 valid_lattice_transition (ccp_prop_value_t old_val, ccp_prop_value_t new_val)
 432 {
 433   /* Lattice transitions must always be monotonically increasing in
 434      value.  */
 435   if (old_val.lattice_val < new_val.lattice_val)
 436     return true;
 437
 438   if (old_val.lattice_val != new_val.lattice_val)
 439     return false;
 440
 441   if (!old_val.value && !new_val.value)
 442     return true;
 443
 444   /* Now both lattice values are CONSTANT.  */
 445
 446   /* Allow arbitrary copy changes as we might look through PHI <a_1, ...>
 447      when only a single copy edge is executable.  */
 448   if (TREE_CODE (old_val.value) == SSA_NAME
 449       && TREE_CODE (new_val.value) == SSA_NAME)
 450     return true;
 451
 452   /* Allow transitioning from a constant to a copy.  */
 453   if (is_gimple_min_invariant (old_val.value)
 454       && TREE_CODE (new_val.value) == SSA_NAME)
 455     return true;
 456
 457   /* Allow transitioning from PHI <&x, not executable> == &x
 458      to PHI <&x, &y> == common alignment.  */
 459   if (TREE_CODE (old_val.value) != INTEGER_CST
 460       && TREE_CODE (new_val.value) == INTEGER_CST)
 461     return true;
 462
 463   /* Bit-lattices have to agree in the still valid bits.  */
 464   if (TREE_CODE (old_val.value) == INTEGER_CST
 465       && TREE_CODE (new_val.value) == INTEGER_CST)
 466     return (wi::bit_and_not (wi::to_widest (old_val.value), new_val.mask)
 467             == wi::bit_and_not (wi::to_widest (new_val.value), new_val.mask));
 468
 469   /* Otherwise constant values have to agree.  */
 470   if (operand_equal_p (old_val.value, new_val.value, 0))
 471     return true;
 472
 473   /* At least the kinds and types should agree now.  */
 474   if (TREE_CODE (old_val.value) != TREE_CODE (new_val.value)
 475       || !types_compatible_p (TREE_TYPE (old_val.value),
 476                               TREE_TYPE (new_val.value)))
 477     return false;
 478
 479   /* For floats and !HONOR_NANS allow transitions from (partial) NaN
 480      to non-NaN.  */
 481   tree type = TREE_TYPE (new_val.value);
 482   if (SCALAR_FLOAT_TYPE_P (type)
 483       && !HONOR_NANS (type))
 484     {
 485       if (REAL_VALUE_ISNAN (TREE_REAL_CST (old_val.value)))
 486         return true;
 487     }
 488   else if (VECTOR_FLOAT_TYPE_P (type)
 489            && !HONOR_NANS (type))
 490     {
 491       unsigned int count
 492         = tree_vector_builder::binary_encoded_nelts (old_val.value,
 493                                                      new_val.value);
 494       for (unsigned int i = 0; i < count; ++i)
 495         if (!REAL_VALUE_ISNAN
 496                (TREE_REAL_CST (VECTOR_CST_ENCODED_ELT (old_val.value, i)))
 497             && !operand_equal_p (VECTOR_CST_ENCODED_ELT (old_val.value, i),
 498                                  VECTOR_CST_ENCODED_ELT (new_val.value, i), 0))
 499           return false;
 500       return true;
 501     }
 502   else if (COMPLEX_FLOAT_TYPE_P (type)
 503            && !HONOR_NANS (type))
 504     {
 505       if (!REAL_VALUE_ISNAN (TREE_REAL_CST (TREE_REALPART (old_val.value)))
 506           && !operand_equal_p (TREE_REALPART (old_val.value),
 507                                TREE_REALPART (new_val.value), 0))
 508         return false;
 509       if (!REAL_VALUE_ISNAN (TREE_REAL_CST (TREE_IMAGPART (old_val.value)))
 510           && !operand_equal_p (TREE_IMAGPART (old_val.value),
 511                                TREE_IMAGPART (new_val.value), 0))
 512         return false;
 513       return true;
 514     }
 515   return false;
 516 }
 517
 518 /* Set the value for variable VAR to NEW_VAL.  Return true if the new
 519    value is different from VAR's previous value.  */
 520
 521 static bool
 522 set_lattice_value (tree var, ccp_prop_value_t *new_val)
 523 {
 524   /* We can deal with old UNINITIALIZED values just fine here.  */
 525   ccp_prop_value_t *old_val = &const_val[SSA_NAME_VERSION (var)];
 526
 527   canonicalize_value (new_val);
 528
 529   /* We have to be careful to not go up the bitwise lattice
 530      represented by the mask.  Instead of dropping to VARYING
 531      use the meet operator to retain a conservative value.
 532      Missed optimizations like PR65851 makes this necessary.
 533      It also ensures we converge to a stable lattice solution.  */
 534   if (old_val->lattice_val != UNINITIALIZED)
 535     ccp_lattice_meet (new_val, old_val);
 536
 537   gcc_checking_assert (valid_lattice_transition (*old_val, *new_val));
 538
 539   /* If *OLD_VAL and NEW_VAL are the same, return false to inform the
 540      caller that this was a non-transition.  */
 541   if (old_val->lattice_val != new_val->lattice_val
 542       || (new_val->lattice_val == CONSTANT
 543           && (TREE_CODE (new_val->value) != TREE_CODE (old_val->value)
 544               || (TREE_CODE (new_val->value) == INTEGER_CST
 545                   && (new_val->mask != old_val->mask
 546                       || (wi::bit_and_not (wi::to_widest (old_val->value),
 547                                            new_val->mask)
 548                           != wi::bit_and_not (wi::to_widest (new_val->value),
 549                                               new_val->mask))))
 550               || (TREE_CODE (new_val->value) != INTEGER_CST
 551                   && !operand_equal_p (new_val->value, old_val->value, 0)))))
 552     {
 553       /* ???  We would like to delay creation of INTEGER_CSTs from
 554          partially constants here.  */
 555
 556       if (dump_file && (dump_flags & TDF_DETAILS))
 557         {
 558           dump_lattice_value (dump_file, "Lattice value changed to ", *new_val);
 559           fprintf (dump_file, ".  Adding SSA edges to worklist.\n");
 560         }
 561
 562       *old_val = *new_val;
 563
 564       gcc_assert (new_val->lattice_val != UNINITIALIZED);
 565       return true;
 566     }
 567
 568   return false;
 569 }
 570
 571 static ccp_prop_value_t get_value_for_expr (tree, bool);
 572 static ccp_prop_value_t bit_value_binop (enum tree_code, tree, tree, tree);
 573 void bit_value_binop (enum tree_code, signop, int, widest_int *, widest_int *,
 574                       signop, int, const widest_int &, const widest_int &,
 575                       signop, int, const widest_int &, const widest_int &);
 576
 577 /* Return a widest_int that can be used for bitwise simplifications
 578    from VAL.  */
 579
 580 static widest_int
 581 value_to_wide_int (ccp_prop_value_t val)
 582 {
 583   if (val.value
 584       && TREE_CODE (val.value) == INTEGER_CST)
 585     return wi::to_widest (val.value);
 586
 587   return 0;
 588 }
 589
 590 /* Return the value for the address expression EXPR based on alignment
 591    information.  */
 592
 593 static ccp_prop_value_t
 594 get_value_from_alignment (tree expr)
 595 {
 596   tree type = TREE_TYPE (expr);
 597   ccp_prop_value_t val;
 598   unsigned HOST_WIDE_INT bitpos;
 599   unsigned int align;
 600
 601   gcc_assert (TREE_CODE (expr) == ADDR_EXPR);
 602
 603   get_pointer_alignment_1 (expr, &align, &bitpos);
 604   val.mask = wi::bit_and_not
 605     (POINTER_TYPE_P (type) || TYPE_UNSIGNED (type)
 606      ? wi::mask <widest_int> (TYPE_PRECISION (type), false)
 607      : -1,
 608      align / BITS_PER_UNIT - 1);
 609   val.lattice_val
 610     = wi::sext (val.mask, TYPE_PRECISION (type)) == -1 ? VARYING : CONSTANT;
 611   if (val.lattice_val == CONSTANT)
 612     val.value = build_int_cstu (type, bitpos / BITS_PER_UNIT);
 613   else
 614     val.value = NULL_TREE;
 615
 616   return val;
 617 }
 618
 619 /* Return the value for the tree operand EXPR.  If FOR_BITS_P is true
 620    return constant bits extracted from alignment information for
 621    invariant addresses.  */
 622
 623 static ccp_prop_value_t
 624 get_value_for_expr (tree expr, bool for_bits_p)
 625 {
 626   ccp_prop_value_t val;
 627
 628   if (TREE_CODE (expr) == SSA_NAME)
 629     {
 630       ccp_prop_value_t *val_ = get_value (expr);
 631       if (val_)
 632         val = *val_;
 633       else
 634         {
 635           val.lattice_val = VARYING;
 636           val.value = NULL_TREE;
 637           val.mask = -1;
 638         }
 639       if (for_bits_p
 640           && val.lattice_val == CONSTANT)
 641         {
 642           if (TREE_CODE (val.value) == ADDR_EXPR)
 643             val = get_value_from_alignment (val.value);
 644           else if (TREE_CODE (val.value) != INTEGER_CST)
 645             {
 646               val.lattice_val = VARYING;
 647               val.value = NULL_TREE;
 648               val.mask = -1;
 649             }
 650         }
 651       /* Fall back to a copy value.  */
 652       if (!for_bits_p
 653           && val.lattice_val == VARYING
 654           && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr))
 655         {
 656           val.lattice_val = CONSTANT;
 657           val.value = expr;
 658           val.mask = -1;
 659         }
 660     }
 661   else if (is_gimple_min_invariant (expr)
 662            && (!for_bits_p || TREE_CODE (expr) == INTEGER_CST))
 663     {
 664       val.lattice_val = CONSTANT;
 665       val.value = expr;
 666       val.mask = 0;
 667       canonicalize_value (&val);
 668     }
 669   else if (TREE_CODE (expr) == ADDR_EXPR)
 670     val = get_value_from_alignment (expr);
 671   else
 672     {
 673       val.lattice_val = VARYING;
 674       val.mask = -1;
 675       val.value = NULL_TREE;
 676     }
 677
 678   if (val.lattice_val == VARYING
 679       && TYPE_UNSIGNED (TREE_TYPE (expr)))
 680     val.mask = wi::zext (val.mask, TYPE_PRECISION (TREE_TYPE (expr)));
 681
 682   return val;
 683 }
 684
 685 /* Return the likely CCP lattice value for STMT.
 686
 687    If STMT has no operands, then return CONSTANT.
 688
 689    Else if undefinedness of operands of STMT cause its value to be
 690    undefined, then return UNDEFINED.
 691
 692    Else if any operands of STMT are constants, then return CONSTANT.
 693
 694    Else return VARYING.  */
 695
 696 static ccp_lattice_t
 697 likely_value (gimple *stmt)
 698 {
 699   bool has_constant_operand, has_undefined_operand, all_undefined_operands;
 700   bool has_nsa_operand;
 701   tree use;
 702   ssa_op_iter iter;
 703   unsigned i;
 704
 705   enum gimple_code code = gimple_code (stmt);
 706
 707   /* This function appears to be called only for assignments, calls,
 708      conditionals, and switches, due to the logic in visit_stmt.  */
 709   gcc_assert (code == GIMPLE_ASSIGN
 710               || code == GIMPLE_CALL
 711               || code == GIMPLE_COND
 712               || code == GIMPLE_SWITCH);
 713
 714   /* If the statement has volatile operands, it won't fold to a
 715      constant value.  */
 716   if (gimple_has_volatile_ops (stmt))
 717     return VARYING;
 718
 719   /* Arrive here for more complex cases.  */
 720   has_constant_operand = false;
 721   has_undefined_operand = false;
 722   all_undefined_operands = true;
 723   has_nsa_operand = false;
 724   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
 725     {
 726       ccp_prop_value_t *val = get_value (use);
 727
 728       if (val && val->lattice_val == UNDEFINED)
 729         has_undefined_operand = true;
 730       else
 731         all_undefined_operands = false;
 732
 733       if (val && val->lattice_val == CONSTANT)
 734         has_constant_operand = true;
 735
 736       if (SSA_NAME_IS_DEFAULT_DEF (use)
 737           || !prop_simulate_again_p (SSA_NAME_DEF_STMT (use)))
 738         has_nsa_operand = true;
 739     }
 740
 741   /* There may be constants in regular rhs operands.  For calls we
 742      have to ignore lhs, fndecl and static chain, otherwise only
 743      the lhs.  */
 744   for (i = (is_gimple_call (stmt) ? 2 : 0) + gimple_has_lhs (stmt);
 745        i < gimple_num_ops (stmt); ++i)
 746     {
 747       tree op = gimple_op (stmt, i);
 748       if (!op || TREE_CODE (op) == SSA_NAME)
 749         continue;
 750       if (is_gimple_min_invariant (op))
 751         has_constant_operand = true;
 752     }
 753
 754   if (has_constant_operand)
 755     all_undefined_operands = false;
 756
 757   if (has_undefined_operand
 758       && code == GIMPLE_CALL
 759       && gimple_call_internal_p (stmt))
 760     switch (gimple_call_internal_fn (stmt))
 761       {
 762         /* These 3 builtins use the first argument just as a magic
 763            way how to find out a decl uid.  */
 764       case IFN_GOMP_SIMD_LANE:
 765       case IFN_GOMP_SIMD_VF:
 766       case IFN_GOMP_SIMD_LAST_LANE:
 767         has_undefined_operand = false;
 768         break;
 769       default:
 770         break;
 771       }
 772
 773   /* If the operation combines operands like COMPLEX_EXPR make sure to
 774      not mark the result UNDEFINED if only one part of the result is
 775      undefined.  */
 776   if (has_undefined_operand && all_undefined_operands)
 777     return UNDEFINED;
 778   else if (code == GIMPLE_ASSIGN && has_undefined_operand)
 779     {
 780       switch (gimple_assign_rhs_code (stmt))
 781         {
 782         /* Unary operators are handled with all_undefined_operands.  */
 783         case PLUS_EXPR:
 784         case MINUS_EXPR:
 785         case POINTER_PLUS_EXPR:
 786         case BIT_XOR_EXPR:
 787           /* Not MIN_EXPR, MAX_EXPR.  One VARYING operand may be selected.
 788              Not bitwise operators, one VARYING operand may specify the
 789              result completely.
 790              Not logical operators for the same reason, apart from XOR.
 791              Not COMPLEX_EXPR as one VARYING operand makes the result partly
 792              not UNDEFINED.  Not *DIV_EXPR, comparisons and shifts because
 793              the undefined operand may be promoted.  */
 794           return UNDEFINED;
 795
 796         case ADDR_EXPR:
 797           /* If any part of an address is UNDEFINED, like the index
 798              of an ARRAY_EXPR, then treat the result as UNDEFINED.  */
 799           return UNDEFINED;
 800
 801         default:
 802           ;
 803         }
 804     }
 805   /* If there was an UNDEFINED operand but the result may be not UNDEFINED
 806      fall back to CONSTANT.  During iteration UNDEFINED may still drop
 807      to CONSTANT.  */
 808   if (has_undefined_operand)
 809     return CONSTANT;
 810
 811   /* We do not consider virtual operands here -- load from read-only
 812      memory may have only VARYING virtual operands, but still be
 813      constant.  Also we can combine the stmt with definitions from
 814      operands whose definitions are not simulated again.  */
 815   if (has_constant_operand
 816       || has_nsa_operand
 817       || gimple_references_memory_p (stmt))
 818     return CONSTANT;
 819
 820   return VARYING;
 821 }
 822
 823 /* Returns true if STMT cannot be constant.  */
 824
 825 static bool
 826 surely_varying_stmt_p (gimple *stmt)
 827 {
 828   /* If the statement has operands that we cannot handle, it cannot be
 829      constant.  */
 830   if (gimple_has_volatile_ops (stmt))
 831     return true;
 832
 833   /* If it is a call and does not return a value or is not a
 834      builtin and not an indirect call or a call to function with
 835      assume_aligned/alloc_align attribute, it is varying.  */
 836   if (is_gimple_call (stmt))
 837     {
 838       tree fndecl, fntype = gimple_call_fntype (stmt);
 839       if (!gimple_call_lhs (stmt)
 840           || ((fndecl = gimple_call_fndecl (stmt)) != NULL_TREE
 841               && !fndecl_built_in_p (fndecl)
 842               && !lookup_attribute ("assume_aligned",
 843                                     TYPE_ATTRIBUTES (fntype))
 844               && !lookup_attribute ("alloc_align",
 845                                     TYPE_ATTRIBUTES (fntype))))
 846         return true;
 847     }
 848
 849   /* Any other store operation is not interesting.  */
 850   else if (gimple_vdef (stmt))
 851     return true;
 852
 853   /* Anything other than assignments and conditional jumps are not
 854      interesting for CCP.  */
 855   if (gimple_code (stmt) != GIMPLE_ASSIGN
 856       && gimple_code (stmt) != GIMPLE_COND
 857       && gimple_code (stmt) != GIMPLE_SWITCH
 858       && gimple_code (stmt) != GIMPLE_CALL)
 859     return true;
 860
 861   return false;
 862 }
 863
 864 /* Initialize local data structures for CCP.  */
 865
 866 static void
 867 ccp_initialize (void)
 868 {
 869   basic_block bb;
 870
 871   n_const_val = num_ssa_names;
 872   const_val = XCNEWVEC (ccp_prop_value_t, n_const_val);
 873
 874   /* Initialize simulation flags for PHI nodes and statements.  */
 875   FOR_EACH_BB_FN (bb, cfun)
 876     {
 877       gimple_stmt_iterator i;
 878
 879       for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
 880         {
 881           gimple *stmt = gsi_stmt (i);
 882           bool is_varying;
 883
 884           /* If the statement is a control insn, then we do not
 885              want to avoid simulating the statement once.  Failure
 886              to do so means that those edges will never get added.  */
 887           if (stmt_ends_bb_p (stmt))
 888             is_varying = false;
 889           else
 890             is_varying = surely_varying_stmt_p (stmt);
 891
 892           if (is_varying)
 893             {
 894               tree def;
 895               ssa_op_iter iter;
 896
 897               /* If the statement will not produce a constant, mark
 898                  all its outputs VARYING.  */
 899               FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 900                 set_value_varying (def);
 901             }
 902           prop_set_simulate_again (stmt, !is_varying);
 903         }
 904     }
 905
 906   /* Now process PHI nodes.  We never clear the simulate_again flag on
 907      phi nodes, since we do not know which edges are executable yet,
 908      except for phi nodes for virtual operands when we do not do store ccp.  */
 909   FOR_EACH_BB_FN (bb, cfun)
 910     {
 911       gphi_iterator i;
 912
 913       for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
 914         {
 915           gphi *phi = i.phi ();
 916
 917           if (virtual_operand_p (gimple_phi_result (phi)))
 918             prop_set_simulate_again (phi, false);
 919           else
 920             prop_set_simulate_again (phi, true);
 921         }
 922     }
 923 }
 924
 925 /* Debug count support. Reset the values of ssa names
 926    VARYING when the total number ssa names analyzed is
 927    beyond the debug count specified.  */
 928
 929 static void
 930 do_dbg_cnt (void)
 931 {
 932   unsigned i;
 933   for (i = 0; i < num_ssa_names; i++)
 934     {
 935       if (!dbg_cnt (ccp))
 936         {
 937           const_val[i].lattice_val = VARYING;
 938           const_val[i].mask = -1;
 939           const_val[i].value = NULL_TREE;
 940         }
 941     }
 942 }
 943
 944
 945 /* We want to provide our own GET_VALUE and FOLD_STMT virtual methods.  */
 946 class ccp_folder : public substitute_and_fold_engine
 947 {
 948  public:
 949   tree value_of_expr (tree, gimple *) FINAL OVERRIDE;
 950   bool fold_stmt (gimple_stmt_iterator *) FINAL OVERRIDE;
 951 };
 952
 953 /* This method just wraps GET_CONSTANT_VALUE for now.  Over time
 954    naked calls to GET_CONSTANT_VALUE should be eliminated in favor
 955    of calling member functions.  */
 956
 957 tree
 958 ccp_folder::value_of_expr (tree op, gimple *)
 959 {
 960   return get_constant_value (op);
 961 }
 962
 963 /* Do final substitution of propagated values, cleanup the flowgraph and
 964    free allocated storage.  If NONZERO_P, record nonzero bits.
 965
 966    Return TRUE when something was optimized.  */
 967
 968 static bool
 969 ccp_finalize (bool nonzero_p)
 970 {
 971   bool something_changed;
 972   unsigned i;
 973   tree name;
 974
 975   do_dbg_cnt ();
 976
 977   /* Derive alignment and misalignment information from partially
 978      constant pointers in the lattice or nonzero bits from partially
 979      constant integers.  */
 980   FOR_EACH_SSA_NAME (i, name, cfun)
 981     {
 982       ccp_prop_value_t *val;
 983       unsigned int tem, align;
 984
 985       if (!POINTER_TYPE_P (TREE_TYPE (name))
 986           && (!INTEGRAL_TYPE_P (TREE_TYPE (name))
 987               /* Don't record nonzero bits before IPA to avoid
 988                  using too much memory.  */
 989               || !nonzero_p))
 990         continue;
 991
 992       val = get_value (name);
 993       if (val->lattice_val != CONSTANT
 994           || TREE_CODE (val->value) != INTEGER_CST
 995           || val->mask == 0)
 996         continue;
 997
 998       if (POINTER_TYPE_P (TREE_TYPE (name)))
 999         {
1000           /* Trailing mask bits specify the alignment, trailing value
1001              bits the misalignment.  */
1002           tem = val->mask.to_uhwi ();
1003           align = least_bit_hwi (tem);
1004           if (align > 1)
1005             set_ptr_info_alignment (get_ptr_info (name), align,
1006                                     (TREE_INT_CST_LOW (val->value)
1007                                      & (align - 1)));
1008         }
1009       else
1010         {
1011           unsigned int precision = TYPE_PRECISION (TREE_TYPE (val->value));
1012           wide_int nonzero_bits
1013             = (wide_int::from (val->mask, precision, UNSIGNED)
1014                | wi::to_wide (val->value));
1015           nonzero_bits &= get_nonzero_bits (name);
1016           set_nonzero_bits (name, nonzero_bits);
1017         }
1018     }
1019
1020   /* Perform substitutions based on the known constant values.  */
1021   class ccp_folder ccp_folder;
1022   something_changed = ccp_folder.substitute_and_fold ();
1023
1024   free (const_val);
1025   const_val = NULL;
1026   return something_changed;
1027 }
1028
1029
1030 /* Compute the meet operator between *VAL1 and *VAL2.  Store the result
1031    in VAL1.
1032
1033                 any  M UNDEFINED   = any
1034                 any  M VARYING     = VARYING
1035                 Ci   M Cj          = Ci         if (i == j)
1036                 Ci   M Cj          = VARYING    if (i != j)
1037    */
1038
1039 static void
1040 ccp_lattice_meet (ccp_prop_value_t *val1, ccp_prop_value_t *val2)
1041 {
1042   if (val1->lattice_val == UNDEFINED
1043       /* For UNDEFINED M SSA we can't always SSA because its definition
1044          may not dominate the PHI node.  Doing optimistic copy propagation
1045          also causes a lot of gcc.dg/uninit-pred*.c FAILs.  */
1046       && (val2->lattice_val != CONSTANT
1047           || TREE_CODE (val2->value) != SSA_NAME))
1048     {
1049       /* UNDEFINED M any = any   */
1050       *val1 = *val2;
1051     }
1052   else if (val2->lattice_val == UNDEFINED
1053            /* See above.  */
1054            && (val1->lattice_val != CONSTANT
1055                || TREE_CODE (val1->value) != SSA_NAME))
1056     {
1057       /* any M UNDEFINED = any
1058          Nothing to do.  VAL1 already contains the value we want.  */
1059       ;
1060     }
1061   else if (val1->lattice_val == VARYING
1062            || val2->lattice_val == VARYING)
1063     {
1064       /* any M VARYING = VARYING.  */
1065       val1->lattice_val = VARYING;
1066       val1->mask = -1;
1067       val1->value = NULL_TREE;
1068     }
1069   else if (val1->lattice_val == CONSTANT
1070            && val2->lattice_val == CONSTANT
1071            && TREE_CODE (val1->value) == INTEGER_CST
1072            && TREE_CODE (val2->value) == INTEGER_CST)
1073     {
1074       /* Ci M Cj = Ci           if (i == j)
1075          Ci M Cj = VARYING      if (i != j)
1076
1077          For INTEGER_CSTs mask unequal bits.  If no equal bits remain,
1078          drop to varying.  */
1079       val1->mask = (val1->mask | val2->mask
1080                     | (wi::to_widest (val1->value)
1081                        ^ wi::to_widest (val2->value)));
1082       if (wi::sext (val1->mask, TYPE_PRECISION (TREE_TYPE (val1->value))) == -1)
1083         {
1084           val1->lattice_val = VARYING;
1085           val1->value = NULL_TREE;
1086         }
1087     }
1088   else if (val1->lattice_val == CONSTANT
1089            && val2->lattice_val == CONSTANT
1090            && operand_equal_p (val1->value, val2->value, 0))
1091     {
1092       /* Ci M Cj = Ci           if (i == j)
1093          Ci M Cj = VARYING      if (i != j)
1094
1095          VAL1 already contains the value we want for equivalent values.  */
1096     }
1097   else if (val1->lattice_val == CONSTANT
1098            && val2->lattice_val == CONSTANT
1099            && (TREE_CODE (val1->value) == ADDR_EXPR
1100                || TREE_CODE (val2->value) == ADDR_EXPR))
1101     {
1102       /* When not equal addresses are involved try meeting for
1103          alignment.  */
1104       ccp_prop_value_t tem = *val2;
1105       if (TREE_CODE (val1->value) == ADDR_EXPR)
1106         *val1 = get_value_for_expr (val1->value, true);
1107       if (TREE_CODE (val2->value) == ADDR_EXPR)
1108         tem = get_value_for_expr (val2->value, true);
1109       ccp_lattice_meet (val1, &tem);
1110     }
1111   else
1112     {
1113       /* Any other combination is VARYING.  */
1114       val1->lattice_val = VARYING;
1115       val1->mask = -1;
1116       val1->value = NULL_TREE;
1117     }
1118 }
1119
1120
1121 /* Loop through the PHI_NODE's parameters for BLOCK and compare their
1122    lattice values to determine PHI_NODE's lattice value.  The value of a
1123    PHI node is determined calling ccp_lattice_meet with all the arguments
1124    of the PHI node that are incoming via executable edges.  */
1125
1126 enum ssa_prop_result
1127 ccp_propagate::visit_phi (gphi *phi)
1128 {
1129   unsigned i;
1130   ccp_prop_value_t new_val;
1131
1132   if (dump_file && (dump_flags & TDF_DETAILS))
1133     {
1134       fprintf (dump_file, "\nVisiting PHI node: ");
1135       print_gimple_stmt (dump_file, phi, 0, dump_flags);
1136     }
1137
1138   new_val.lattice_val = UNDEFINED;
1139   new_val.value = NULL_TREE;
1140   new_val.mask = 0;
1141
1142   bool first = true;
1143   bool non_exec_edge = false;
1144   for (i = 0; i < gimple_phi_num_args (phi); i++)
1145     {
1146       /* Compute the meet operator over all the PHI arguments flowing
1147          through executable edges.  */
1148       edge e = gimple_phi_arg_edge (phi, i);
1149
1150       if (dump_file && (dump_flags & TDF_DETAILS))
1151         {
1152           fprintf (dump_file,
1153               "\tArgument #%d (%d -> %d %sexecutable)\n",
1154               i, e->src->index, e->dest->index,
1155               (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
1156         }
1157
1158       /* If the incoming edge is executable, Compute the meet operator for
1159          the existing value of the PHI node and the current PHI argument.  */
1160       if (e->flags & EDGE_EXECUTABLE)
1161         {
1162           tree arg = gimple_phi_arg (phi, i)->def;
1163           ccp_prop_value_t arg_val = get_value_for_expr (arg, false);
1164
1165           if (first)
1166             {
1167               new_val = arg_val;
1168               first = false;
1169             }
1170           else
1171             ccp_lattice_meet (&new_val, &arg_val);
1172
1173           if (dump_file && (dump_flags & TDF_DETAILS))
1174             {
1175               fprintf (dump_file, "\t");
1176               print_generic_expr (dump_file, arg, dump_flags);
1177               dump_lattice_value (dump_file, "\tValue: ", arg_val);
1178               fprintf (dump_file, "\n");
1179             }
1180
1181           if (new_val.lattice_val == VARYING)
1182             break;
1183         }
1184       else
1185         non_exec_edge = true;
1186     }
1187
1188   /* In case there were non-executable edges and the value is a copy
1189      make sure its definition dominates the PHI node.  */
1190   if (non_exec_edge
1191       && new_val.lattice_val == CONSTANT
1192       && TREE_CODE (new_val.value) == SSA_NAME
1193       && ! SSA_NAME_IS_DEFAULT_DEF (new_val.value)
1194       && ! dominated_by_p (CDI_DOMINATORS, gimple_bb (phi),
1195                            gimple_bb (SSA_NAME_DEF_STMT (new_val.value))))
1196     {
1197       new_val.lattice_val = VARYING;
1198       new_val.value = NULL_TREE;
1199       new_val.mask = -1;
1200     }
1201
1202   if (dump_file && (dump_flags & TDF_DETAILS))
1203     {
1204       dump_lattice_value (dump_file, "\n    PHI node value: ", new_val);
1205       fprintf (dump_file, "\n\n");
1206     }
1207
1208   /* Make the transition to the new value.  */
1209   if (set_lattice_value (gimple_phi_result (phi), &new_val))
1210     {
1211       if (new_val.lattice_val == VARYING)
1212         return SSA_PROP_VARYING;
1213       else
1214         return SSA_PROP_INTERESTING;
1215     }
1216   else
1217     return SSA_PROP_NOT_INTERESTING;
1218 }
1219
1220 /* Return the constant value for OP or OP otherwise.  */
1221
1222 static tree
1223 valueize_op (tree op)
1224 {
1225   if (TREE_CODE (op) == SSA_NAME)
1226     {
1227       tree tem = get_constant_value (op);
1228       if (tem)
1229         return tem;
1230     }
1231   return op;
1232 }
1233
1234 /* Return the constant value for OP, but signal to not follow SSA
1235    edges if the definition may be simulated again.  */
1236
1237 static tree
1238 valueize_op_1 (tree op)
1239 {
1240   if (TREE_CODE (op) == SSA_NAME)
1241     {
1242       /* If the definition may be simulated again we cannot follow
1243          this SSA edge as the SSA propagator does not necessarily
1244          re-visit the use.  */
1245       gimple *def_stmt = SSA_NAME_DEF_STMT (op);
1246       if (!gimple_nop_p (def_stmt)
1247           && prop_simulate_again_p (def_stmt))
1248         return NULL_TREE;
1249       tree tem = get_constant_value (op);
1250       if (tem)
1251         return tem;
1252     }
1253   return op;
1254 }
1255
1256 /* CCP specific front-end to the non-destructive constant folding
1257    routines.
1258
1259    Attempt to simplify the RHS of STMT knowing that one or more
1260    operands are constants.
1261
1262    If simplification is possible, return the simplified RHS,
1263    otherwise return the original RHS or NULL_TREE.  */
1264
1265 static tree
1266 ccp_fold (gimple *stmt)
1267 {
1268   location_t loc = gimple_location (stmt);
1269   switch (gimple_code (stmt))
1270     {
1271     case GIMPLE_COND:
1272       {
1273         /* Handle comparison operators that can appear in GIMPLE form.  */
1274         tree op0 = valueize_op (gimple_cond_lhs (stmt));
1275         tree op1 = valueize_op (gimple_cond_rhs (stmt));
1276         enum tree_code code = gimple_cond_code (stmt);
1277         return fold_binary_loc (loc, code, boolean_type_node, op0, op1);
1278       }
1279
1280     case GIMPLE_SWITCH:
1281       {
1282         /* Return the constant switch index.  */
1283         return valueize_op (gimple_switch_index (as_a <gswitch *> (stmt)));
1284       }
1285
1286     case GIMPLE_ASSIGN:
1287     case GIMPLE_CALL:
1288       return gimple_fold_stmt_to_constant_1 (stmt,
1289                                              valueize_op, valueize_op_1);
1290
1291     default:
1292       gcc_unreachable ();
1293     }
1294 }
1295
1296 /* Determine the minimum and maximum values, *MIN and *MAX respectively,
1297    represented by the mask pair VAL and MASK with signedness SGN and
1298    precision PRECISION.  */
1299
1300 void
1301 value_mask_to_min_max (widest_int *min, widest_int *max,
1302                        const widest_int &val, const widest_int &mask,
1303                        signop sgn, int precision)
1304 {
1305   *min = wi::bit_and_not (val, mask);
1306   *max = val | mask;
1307   if (sgn == SIGNED && wi::neg_p (mask))
1308     {
1309       widest_int sign_bit = wi::lshift (1, precision - 1);
1310       *min ^= sign_bit;
1311       *max ^= sign_bit;
1312       /* MAX is zero extended, and MIN is sign extended.  */
1313       *min = wi::ext (*min, precision, sgn);
1314       *max = wi::ext (*max, precision, sgn);
1315     }
1316 }
1317
1318 /* Apply the operation CODE in type TYPE to the value, mask pair
1319    RVAL and RMASK representing a value of type RTYPE and set
1320    the value, mask pair *VAL and *MASK to the result.  */
1321
1322 void
1323 bit_value_unop (enum tree_code code, signop type_sgn, int type_precision,
1324                 widest_int *val, widest_int *mask,
1325                 signop rtype_sgn, int rtype_precision,
1326                 const widest_int &rval, const widest_int &rmask)
1327 {
1328   switch (code)
1329     {
1330     case BIT_NOT_EXPR:
1331       *mask = rmask;
1332       *val = ~rval;
1333       break;
1334
1335     case NEGATE_EXPR:
1336       {
1337         widest_int temv, temm;
1338         /* Return ~rval + 1.  */
1339         bit_value_unop (BIT_NOT_EXPR, type_sgn, type_precision, &temv, &temm,
1340                         type_sgn, type_precision, rval, rmask);
1341         bit_value_binop (PLUS_EXPR, type_sgn, type_precision, val, mask,
1342                          type_sgn, type_precision, temv, temm,
1343                          type_sgn, type_precision, 1, 0);
1344         break;
1345       }
1346
1347     CASE_CONVERT:
1348       {
1349         /* First extend mask and value according to the original type.  */
1350         *mask = wi::ext (rmask, rtype_precision, rtype_sgn);
1351         *val = wi::ext (rval, rtype_precision, rtype_sgn);
1352
1353         /* Then extend mask and value according to the target type.  */
1354         *mask = wi::ext (*mask, type_precision, type_sgn);
1355         *val = wi::ext (*val, type_precision, type_sgn);
1356         break;
1357       }
1358
1359     case ABS_EXPR:
1360     case ABSU_EXPR:
1361       if (wi::sext (rmask, rtype_precision) == -1)
1362         *mask = -1;
1363       else if (wi::neg_p (rmask))
1364         {
1365           /* Result is either rval or -rval.  */
1366           widest_int temv, temm;
1367           bit_value_unop (NEGATE_EXPR, rtype_sgn, rtype_precision, &temv,
1368                           &temm, type_sgn, type_precision, rval, rmask);
1369           temm |= (rmask | (rval ^ temv));
1370           /* Extend the result.  */
1371           *mask = wi::ext (temm, type_precision, type_sgn);
1372           *val = wi::ext (temv, type_precision, type_sgn);
1373         }
1374       else if (wi::neg_p (rval))
1375         {
1376           bit_value_unop (NEGATE_EXPR, type_sgn, type_precision, val, mask,
1377                           type_sgn, type_precision, rval, rmask);
1378         }
1379       else
1380         {
1381           *mask = rmask;
1382           *val = rval;
1383         }
1384       break;
1385
1386     default:
1387       *mask = -1;
1388       break;
1389     }
1390 }
1391
1392 /* Determine the mask pair *VAL and *MASK from multiplying the
1393    argument mask pair RVAL, RMASK by the unsigned constant C.  */
1394 void
1395 bit_value_mult_const (signop sgn, int width,
1396                       widest_int *val, widest_int *mask,
1397                       const widest_int &rval, const widest_int &rmask,
1398                       widest_int c)
1399 {
1400   widest_int sum_mask = 0;
1401
1402   /* Ensure rval_lo only contains known bits.  */
1403   widest_int rval_lo = wi::bit_and_not (rval, rmask);
1404
1405   if (rval_lo != 0)
1406     {
1407       /* General case (some bits of multiplicand are known set).  */
1408       widest_int sum_val = 0;
1409       while (c != 0)
1410         {
1411           /* Determine the lowest bit set in the multiplier.  */
1412           int bitpos = wi::ctz (c);
1413           widest_int term_mask = rmask << bitpos;
1414           widest_int term_val = rval_lo << bitpos;
1415
1416           /* sum += term.  */
1417           widest_int lo = sum_val + term_val;
1418           widest_int hi = (sum_val | sum_mask) + (term_val | term_mask);
1419           sum_mask |= term_mask | (lo ^ hi);
1420           sum_val = lo;
1421
1422           /* Clear this bit in the multiplier.  */
1423           c ^= wi::lshift (1, bitpos);
1424         }
1425       /* Correctly extend the result value.  */
1426       *val = wi::ext (sum_val, width, sgn);
1427     }
1428   else
1429     {
1430       /* Special case (no bits of multiplicand are known set).  */
1431       while (c != 0)
1432         {
1433           /* Determine the lowest bit set in the multiplier.  */
1434           int bitpos = wi::ctz (c);
1435           widest_int term_mask = rmask << bitpos;
1436
1437           /* sum += term.  */
1438           widest_int hi = sum_mask + term_mask;
1439           sum_mask |= term_mask | hi;
1440
1441           /* Clear this bit in the multiplier.  */
1442           c ^= wi::lshift (1, bitpos);
1443         }
1444       *val = 0;
1445     }
1446
1447   /* Correctly extend the result mask.  */
1448   *mask = wi::ext (sum_mask, width, sgn);
1449 }
1450
1451 /* Fill up to MAX values in the BITS array with values representing
1452    each of the non-zero bits in the value X.  Returns the number of
1453    bits in X (capped at the maximum value MAX).  For example, an X
1454    value 11, places 1, 2 and 8 in BITS and returns the value 3.  */
1455
1456 unsigned int
1457 get_individual_bits (widest_int *bits, widest_int x, unsigned int max)
1458 {
1459   unsigned int count = 0;
1460   while (count < max && x != 0)
1461     {
1462       int bitpos = wi::ctz (x);
1463       bits[count] = wi::lshift (1, bitpos);
1464       x ^= bits[count];
1465       count++;
1466     }
1467   return count;
1468 }
1469
1470 /* Array of 2^N - 1 values representing the bits flipped between
1471    consecutive Gray codes.  This is used to efficiently enumerate
1472    all permutations on N bits using XOR.  */
1473 static const unsigned char gray_code_bit_flips[63] = {
1474   0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
1475   0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
1476   0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
1477   0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
1478 };
1479
1480 /* Apply the operation CODE in type TYPE to the value, mask pairs
1481    R1VAL, R1MASK and R2VAL, R2MASK representing a values of type R1TYPE
1482    and R2TYPE and set the value, mask pair *VAL and *MASK to the result.  */
1483
1484 void
1485 bit_value_binop (enum tree_code code, signop sgn, int width,
1486                  widest_int *val, widest_int *mask,
1487                  signop r1type_sgn, int r1type_precision,
1488                  const widest_int &r1val, const widest_int &r1mask,
1489                  signop r2type_sgn, int r2type_precision ATTRIBUTE_UNUSED,
1490                  const widest_int &r2val, const widest_int &r2mask)
1491 {
1492   bool swap_p = false;
1493
1494   /* Assume we'll get a constant result.  Use an initial non varying
1495      value, we fall back to varying in the end if necessary.  */
1496   *mask = -1;
1497   /* Ensure that VAL is initialized (to any value).  */
1498   *val = 0;
1499
1500   switch (code)
1501     {
1502     case BIT_AND_EXPR:
1503       /* The mask is constant where there is a known not
1504          set bit, (m1 | m2) & ((v1 | m1) & (v2 | m2)) */
1505       *mask = (r1mask | r2mask) & (r1val | r1mask) & (r2val | r2mask);
1506       *val = r1val & r2val;
1507       break;
1508
1509     case BIT_IOR_EXPR:
1510       /* The mask is constant where there is a known
1511          set bit, (m1 | m2) & ~((v1 & ~m1) | (v2 & ~m2)).  */
1512       *mask = wi::bit_and_not (r1mask | r2mask,
1513                                wi::bit_and_not (r1val, r1mask)
1514                                | wi::bit_and_not (r2val, r2mask));
1515       *val = r1val | r2val;
1516       break;
1517
1518     case BIT_XOR_EXPR:
1519       /* m1 | m2  */
1520       *mask = r1mask | r2mask;
1521       *val = r1val ^ r2val;
1522       break;
1523
1524     case LROTATE_EXPR:
1525     case RROTATE_EXPR:
1526       if (r2mask == 0)
1527         {
1528           widest_int shift = r2val;
1529           if (shift == 0)
1530             {
1531               *mask = r1mask;
1532               *val = r1val;
1533             }
1534           else
1535             {
1536               if (wi::neg_p (shift, r2type_sgn))
1537                 {
1538                   shift = -shift;
1539                   if (code == RROTATE_EXPR)
1540                     code = LROTATE_EXPR;
1541                   else
1542                     code = RROTATE_EXPR;
1543                 }
1544               if (code == RROTATE_EXPR)
1545                 {
1546                   *mask = wi::rrotate (r1mask, shift, width);
1547                   *val = wi::rrotate (r1val, shift, width);
1548                 }
1549               else
1550                 {
1551                   *mask = wi::lrotate (r1mask, shift, width);
1552                   *val = wi::lrotate (r1val, shift, width);
1553                 }
1554             }
1555         }
1556       else if (wi::ltu_p (r2val | r2mask, width)
1557                && wi::popcount (r2mask) <= 4)
1558         {
1559           widest_int bits[4];
1560           widest_int res_val, res_mask;
1561           widest_int tmp_val, tmp_mask;
1562           widest_int shift = wi::bit_and_not (r2val, r2mask);
1563           unsigned int bit_count = get_individual_bits (bits, r2mask, 4);
1564           unsigned int count = (1 << bit_count) - 1;
1565
1566           /* Initialize result to rotate by smallest value of shift.  */
1567           if (code == RROTATE_EXPR)
1568             {
1569               res_mask = wi::rrotate (r1mask, shift, width);
1570               res_val = wi::rrotate (r1val, shift, width);
1571             }
1572           else
1573             {
1574               res_mask = wi::lrotate (r1mask, shift, width);
1575               res_val = wi::lrotate (r1val, shift, width);
1576             }
1577
1578           /* Iterate through the remaining values of shift.  */
1579           for (unsigned int i=0; i<count; i++)
1580             {
1581               shift ^= bits[gray_code_bit_flips[i]];
1582               if (code == RROTATE_EXPR)
1583                 {
1584                   tmp_mask = wi::rrotate (r1mask, shift, width);
1585                   tmp_val = wi::rrotate (r1val, shift, width);
1586                 }
1587               else
1588                 {
1589                   tmp_mask = wi::lrotate (r1mask, shift, width);
1590                   tmp_val = wi::lrotate (r1val, shift, width);
1591                 }
1592               /* Accumulate the result.  */
1593               res_mask |= tmp_mask | (res_val ^ tmp_val);
1594             }
1595           *val = wi::bit_and_not (res_val, res_mask);
1596           *mask = res_mask;
1597         }
1598       break;
1599
1600     case LSHIFT_EXPR:
1601     case RSHIFT_EXPR:
1602       /* ???  We can handle partially known shift counts if we know
1603          its sign.  That way we can tell that (x << (y | 8)) & 255
1604          is zero.  */
1605       if (r2mask == 0)
1606         {
1607           widest_int shift = r2val;
1608           if (shift == 0)
1609             {
1610               *mask = r1mask;
1611               *val = r1val;
1612             }
1613           else
1614             {
1615               if (wi::neg_p (shift, r2type_sgn))
1616                 break;
1617               if (code == RSHIFT_EXPR)
1618                 {
1619                   *mask = wi::rshift (wi::ext (r1mask, width, sgn), shift, sgn);
1620                   *val = wi::rshift (wi::ext (r1val, width, sgn), shift, sgn);
1621                 }
1622               else
1623                 {
1624                   *mask = wi::ext (r1mask << shift, width, sgn);
1625                   *val = wi::ext (r1val << shift, width, sgn);
1626                 }
1627             }
1628         }
1629       else if (wi::ltu_p (r2val | r2mask, width))
1630         {
1631           if (wi::popcount (r2mask) <= 4)
1632             {
1633               widest_int bits[4];
1634               widest_int arg_val, arg_mask;
1635               widest_int res_val, res_mask;
1636               widest_int tmp_val, tmp_mask;
1637               widest_int shift = wi::bit_and_not (r2val, r2mask);
1638               unsigned int bit_count = get_individual_bits (bits, r2mask, 4);
1639               unsigned int count = (1 << bit_count) - 1;
1640
1641               /* Initialize result to shift by smallest value of shift.  */
1642               if (code == RSHIFT_EXPR)
1643                 {
1644                   arg_mask = wi::ext (r1mask, width, sgn);
1645                   arg_val = wi::ext (r1val, width, sgn);
1646                   res_mask = wi::rshift (arg_mask, shift, sgn);
1647                   res_val = wi::rshift (arg_val, shift, sgn);
1648                 }
1649               else
1650                 {
1651                   arg_mask = r1mask;
1652                   arg_val = r1val;
1653                   res_mask = arg_mask << shift;
1654                   res_val = arg_val << shift;
1655                 }
1656
1657               /* Iterate through the remaining values of shift.  */
1658               for (unsigned int i=0; i<count; i++)
1659                 {
1660                   shift ^= bits[gray_code_bit_flips[i]];
1661                   if (code == RSHIFT_EXPR)
1662                     {
1663                       tmp_mask = wi::rshift (arg_mask, shift, sgn);
1664                       tmp_val = wi::rshift (arg_val, shift, sgn);
1665                     }
1666                   else
1667                     {
1668                       tmp_mask = arg_mask << shift;
1669                       tmp_val = arg_val << shift;
1670                     }
1671                   /* Accumulate the result.  */
1672                   res_mask |= tmp_mask | (res_val ^ tmp_val);
1673                 }
1674               res_mask = wi::ext (res_mask, width, sgn);
1675               res_val = wi::ext (res_val, width, sgn);
1676               *val = wi::bit_and_not (res_val, res_mask);
1677               *mask = res_mask;
1678             }
1679           else if ((r1val | r1mask) == 0)
1680             {
1681               /* Handle shifts of zero to avoid undefined wi::ctz below.  */
1682               *mask = 0;
1683               *val = 0;
1684             }
1685           else if (code == LSHIFT_EXPR)
1686             {
1687               widest_int tmp = wi::mask <widest_int> (width, false);
1688               tmp <<= wi::ctz (r1val | r1mask);
1689               tmp <<= wi::bit_and_not (r2val, r2mask);
1690               *mask = wi::ext (tmp, width, sgn);
1691               *val = 0;
1692             }
1693           else if (!wi::neg_p (r1val | r1mask, sgn))
1694             {
1695               /* Logical right shift, or zero sign bit.  */
1696               widest_int arg = r1val | r1mask;
1697               int lzcount = wi::clz (arg);
1698               if (lzcount)
1699                 lzcount -= wi::get_precision (arg) - width;
1700               widest_int tmp = wi::mask <widest_int> (width, false);
1701               tmp = wi::lrshift (tmp, lzcount);
1702               tmp = wi::lrshift (tmp, wi::bit_and_not (r2val, r2mask));
1703               *mask = wi::ext (tmp, width, sgn);
1704               *val = 0;
1705             }
1706           else if (!wi::neg_p (r1mask))
1707             {
1708               /* Arithmetic right shift with set sign bit.  */
1709               widest_int arg = wi::bit_and_not (r1val, r1mask);
1710               int sbcount = wi::clrsb (arg);
1711               sbcount -= wi::get_precision (arg) - width;
1712               widest_int tmp = wi::mask <widest_int> (width, false);
1713               tmp = wi::lrshift (tmp, sbcount);
1714               tmp = wi::lrshift (tmp, wi::bit_and_not (r2val, r2mask));
1715               *mask = wi::sext (tmp, width);
1716               tmp = wi::bit_not (tmp);
1717               *val = wi::sext (tmp, width);
1718             }
1719         }
1720       break;
1721
1722     case PLUS_EXPR:
1723     case POINTER_PLUS_EXPR:
1724       {
1725         /* Do the addition with unknown bits set to zero, to give carry-ins of
1726            zero wherever possible.  */
1727         widest_int lo = (wi::bit_and_not (r1val, r1mask)
1728                          + wi::bit_and_not (r2val, r2mask));
1729         lo = wi::ext (lo, width, sgn);
1730         /* Do the addition with unknown bits set to one, to give carry-ins of
1731            one wherever possible.  */
1732         widest_int hi = (r1val | r1mask) + (r2val | r2mask);
1733         hi = wi::ext (hi, width, sgn);
1734         /* Each bit in the result is known if (a) the corresponding bits in
1735            both inputs are known, and (b) the carry-in to that bit position
1736            is known.  We can check condition (b) by seeing if we got the same
1737            result with minimised carries as with maximised carries.  */
1738         *mask = r1mask | r2mask | (lo ^ hi);
1739         *mask = wi::ext (*mask, width, sgn);
1740         /* It shouldn't matter whether we choose lo or hi here.  */
1741         *val = lo;
1742         break;
1743       }
1744
1745     case MINUS_EXPR:
1746     case POINTER_DIFF_EXPR:
1747       {
1748         /* Subtraction is derived from the addition algorithm above.  */
1749         widest_int lo = wi::bit_and_not (r1val, r1mask) - (r2val | r2mask);
1750         lo = wi::ext (lo, width, sgn);
1751         widest_int hi = (r1val | r1mask) - wi::bit_and_not (r2val, r2mask);
1752         hi = wi::ext (hi, width, sgn);
1753         *mask = r1mask | r2mask | (lo ^ hi);
1754         *mask = wi::ext (*mask, width, sgn);
1755         *val = lo;
1756         break;
1757       }
1758
1759     case MULT_EXPR:
1760       if (r2mask == 0
1761           && !wi::neg_p (r2val, sgn)
1762           && (flag_expensive_optimizations || wi::popcount (r2val) < 8))
1763         bit_value_mult_const (sgn, width, val, mask, r1val, r1mask, r2val);
1764       else if (r1mask == 0
1765                && !wi::neg_p (r1val, sgn)
1766                && (flag_expensive_optimizations || wi::popcount (r1val) < 8))
1767         bit_value_mult_const (sgn, width, val, mask, r2val, r2mask, r1val);
1768       else
1769         {
1770           /* Just track trailing zeros in both operands and transfer
1771              them to the other.  */
1772           int r1tz = wi::ctz (r1val | r1mask);
1773           int r2tz = wi::ctz (r2val | r2mask);
1774           if (r1tz + r2tz >= width)
1775             {
1776               *mask = 0;
1777               *val = 0;
1778             }
1779           else if (r1tz + r2tz > 0)
1780             {
1781               *mask = wi::ext (wi::mask <widest_int> (r1tz + r2tz, true),
1782                                width, sgn);
1783               *val = 0;
1784             }
1785         }
1786       break;
1787
1788     case EQ_EXPR:
1789     case NE_EXPR:
1790       {
1791         widest_int m = r1mask | r2mask;
1792         if (wi::bit_and_not (r1val, m) != wi::bit_and_not (r2val, m))
1793           {
1794             *mask = 0;
1795             *val = ((code == EQ_EXPR) ? 0 : 1);
1796           }
1797         else
1798           {
1799             /* We know the result of a comparison is always one or zero.  */
1800             *mask = 1;
1801             *val = 0;
1802           }
1803         break;
1804       }
1805
1806     case GE_EXPR:
1807     case GT_EXPR:
1808       swap_p = true;
1809       code = swap_tree_comparison (code);
1810       /* Fall through.  */
1811     case LT_EXPR:
1812     case LE_EXPR:
1813       {
1814         widest_int min1, max1, min2, max2;
1815         int minmax, maxmin;
1816
1817         const widest_int &o1val = swap_p ? r2val : r1val;
1818         const widest_int &o1mask = swap_p ? r2mask : r1mask;
1819         const widest_int &o2val = swap_p ? r1val : r2val;
1820         const widest_int &o2mask = swap_p ? r1mask : r2mask;
1821
1822         value_mask_to_min_max (&min1, &max1, o1val, o1mask,
1823                                r1type_sgn, r1type_precision);
1824         value_mask_to_min_max (&min2, &max2, o2val, o2mask,
1825                                r1type_sgn, r1type_precision);
1826
1827         /* For comparisons the signedness is in the comparison operands.  */
1828         /* Do a cross comparison of the max/min pairs.  */
1829         maxmin = wi::cmp (max1, min2, r1type_sgn);
1830         minmax = wi::cmp (min1, max2, r1type_sgn);
1831         if (maxmin < (code == LE_EXPR ? 1: 0))  /* o1 < or <= o2.  */
1832           {
1833             *mask = 0;
1834             *val = 1;
1835           }
1836         else if (minmax > (code == LT_EXPR ? -1 : 0))  /* o1 >= or > o2.  */
1837           {
1838             *mask = 0;
1839             *val = 0;
1840           }
1841         else if (maxmin == minmax)  /* o1 and o2 are equal.  */
1842           {
1843             /* This probably should never happen as we'd have
1844                folded the thing during fully constant value folding.  */
1845             *mask = 0;
1846             *val = (code == LE_EXPR ? 1 : 0);
1847           }
1848         else
1849           {
1850             /* We know the result of a comparison is always one or zero.  */
1851             *mask = 1;
1852             *val = 0;
1853           }
1854         break;
1855       }
1856
1857     case MIN_EXPR:
1858     case MAX_EXPR:
1859       {
1860         widest_int min1, max1, min2, max2;
1861
1862         value_mask_to_min_max (&min1, &max1, r1val, r1mask, sgn, width);
1863         value_mask_to_min_max (&min2, &max2, r2val, r2mask, sgn, width);
1864
1865         if (wi::cmp (max1, min2, sgn) <= 0)  /* r1 is less than r2.  */
1866           {
1867             if (code == MIN_EXPR)
1868               {
1869                 *mask = r1mask;
1870                 *val = r1val;
1871               }
1872             else
1873               {
1874                 *mask = r2mask;
1875                 *val = r2val;
1876               }
1877           }
1878         else if (wi::cmp (min1, max2, sgn) >= 0)  /* r2 is less than r1.  */
1879           {
1880             if (code == MIN_EXPR)
1881               {
1882                 *mask = r2mask;
1883                 *val = r2val;
1884               }
1885             else
1886               {
1887                 *mask = r1mask;
1888                 *val = r1val;
1889               }
1890           }
1891         else
1892           {
1893             /* The result is either r1 or r2.  */
1894             *mask = r1mask | r2mask | (r1val ^ r2val);
1895             *val = r1val;
1896           }
1897         break;
1898       }
1899
1900     case TRUNC_MOD_EXPR:
1901       {
1902         widest_int r1max = r1val | r1mask;
1903         widest_int r2max = r2val | r2mask;
1904         if (sgn == UNSIGNED
1905             || (!wi::neg_p (r1max) && !wi::neg_p (r2max)))
1906           {
1907             /* Confirm R2 has some bits set, to avoid division by zero.  */
1908             widest_int r2min = wi::bit_and_not (r2val, r2mask);
1909             if (r2min != 0)
1910               {
1911                 /* R1 % R2 is R1 if R1 is always less than R2.  */
1912                 if (wi::ltu_p (r1max, r2min))
1913                   {
1914                     *mask = r1mask;
1915                     *val = r1val;
1916                   }
1917                 else
1918                   {
1919                     /* R1 % R2 is always less than the maximum of R2.  */
1920                     unsigned int lzcount = wi::clz (r2max);
1921                     unsigned int bits = wi::get_precision (r2max) - lzcount;
1922                     if (r2max == wi::lshift (1, bits))
1923                       bits--;
1924                     *mask = wi::mask <widest_int> (bits, false);
1925                     *val = 0;
1926                   }
1927                }
1928             }
1929         }
1930       break;
1931
1932     case TRUNC_DIV_EXPR:
1933       {
1934         widest_int r1max = r1val | r1mask;
1935         widest_int r2max = r2val | r2mask;
1936         if (sgn == UNSIGNED
1937             || (!wi::neg_p (r1max) && !wi::neg_p (r2max)))
1938           {
1939             /* Confirm R2 has some bits set, to avoid division by zero.  */
1940             widest_int r2min = wi::bit_and_not (r2val, r2mask);
1941             if (r2min != 0)
1942               {
1943                 /* R1 / R2 is zero if R1 is always less than R2.  */
1944                 if (wi::ltu_p (r1max, r2min))
1945                   {
1946                     *mask = 0;
1947                     *val = 0;
1948                   }
1949                 else
1950                   {
1951                     widest_int upper = wi::udiv_trunc (r1max, r2min);
1952                     unsigned int lzcount = wi::clz (upper);
1953                     unsigned int bits = wi::get_precision (upper) - lzcount;
1954                     *mask = wi::mask <widest_int> (bits, false);
1955                     *val = 0;
1956                   }
1957                }
1958             }
1959         }
1960       break;
1961
1962     default:;
1963     }
1964 }
1965
1966 /* Return the propagation value when applying the operation CODE to
1967    the value RHS yielding type TYPE.  */
1968
1969 static ccp_prop_value_t
1970 bit_value_unop (enum tree_code code, tree type, tree rhs)
1971 {
1972   ccp_prop_value_t rval = get_value_for_expr (rhs, true);
1973   widest_int value, mask;
1974   ccp_prop_value_t val;
1975
1976   if (rval.lattice_val == UNDEFINED)
1977     return rval;
1978
1979   gcc_assert ((rval.lattice_val == CONSTANT
1980                && TREE_CODE (rval.value) == INTEGER_CST)
1981               || wi::sext (rval.mask, TYPE_PRECISION (TREE_TYPE (rhs))) == -1);
1982   bit_value_unop (code, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask,
1983                   TYPE_SIGN (TREE_TYPE (rhs)), TYPE_PRECISION (TREE_TYPE (rhs)),
1984                   value_to_wide_int (rval), rval.mask);
1985   if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
1986     {
1987       val.lattice_val = CONSTANT;
1988       val.mask = mask;
1989       /* ???  Delay building trees here.  */
1990       val.value = wide_int_to_tree (type, value);
1991     }
1992   else
1993     {
1994       val.lattice_val = VARYING;
1995       val.value = NULL_TREE;
1996       val.mask = -1;
1997     }
1998   return val;
1999 }
2000
2001 /* Return the propagation value when applying the operation CODE to
2002    the values RHS1 and RHS2 yielding type TYPE.  */
2003
2004 static ccp_prop_value_t
2005 bit_value_binop (enum tree_code code, tree type, tree rhs1, tree rhs2)
2006 {
2007   ccp_prop_value_t r1val = get_value_for_expr (rhs1, true);
2008   ccp_prop_value_t r2val = get_value_for_expr (rhs2, true);
2009   widest_int value, mask;
2010   ccp_prop_value_t val;
2011
2012   if (r1val.lattice_val == UNDEFINED
2013       || r2val.lattice_val == UNDEFINED)
2014     {
2015       val.lattice_val = VARYING;
2016       val.value = NULL_TREE;
2017       val.mask = -1;
2018       return val;
2019     }
2020
2021   gcc_assert ((r1val.lattice_val == CONSTANT
2022                && TREE_CODE (r1val.value) == INTEGER_CST)
2023               || wi::sext (r1val.mask,
2024                            TYPE_PRECISION (TREE_TYPE (rhs1))) == -1);
2025   gcc_assert ((r2val.lattice_val == CONSTANT
2026                && TREE_CODE (r2val.value) == INTEGER_CST)
2027               || wi::sext (r2val.mask,
2028                            TYPE_PRECISION (TREE_TYPE (rhs2))) == -1);
2029   bit_value_binop (code, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask,
2030                    TYPE_SIGN (TREE_TYPE (rhs1)), TYPE_PRECISION (TREE_TYPE (rhs1)),
2031                    value_to_wide_int (r1val), r1val.mask,
2032                    TYPE_SIGN (TREE_TYPE (rhs2)), TYPE_PRECISION (TREE_TYPE (rhs2)),
2033                    value_to_wide_int (r2val), r2val.mask);
2034
2035   /* (x * x) & 2 == 0.  */
2036   if (code == MULT_EXPR && rhs1 == rhs2 && TYPE_PRECISION (type) > 1)
2037     {
2038       widest_int m = 2;
2039       if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
2040         value = wi::bit_and_not (value, m);
2041       else
2042         value = 0;
2043       mask = wi::bit_and_not (mask, m);
2044     }
2045
2046   if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
2047     {
2048       val.lattice_val = CONSTANT;
2049       val.mask = mask;
2050       /* ???  Delay building trees here.  */
2051       val.value = wide_int_to_tree (type, value);
2052     }
2053   else
2054     {
2055       val.lattice_val = VARYING;
2056       val.value = NULL_TREE;
2057       val.mask = -1;
2058     }
2059   return val;
2060 }
2061
2062 /* Return the propagation value for __builtin_assume_aligned
2063    and functions with assume_aligned or alloc_aligned attribute.
2064    For __builtin_assume_aligned, ATTR is NULL_TREE,
2065    for assume_aligned attribute ATTR is non-NULL and ALLOC_ALIGNED
2066    is false, for alloc_aligned attribute ATTR is non-NULL and
2067    ALLOC_ALIGNED is true.  */
2068
2069 static ccp_prop_value_t
2070 bit_value_assume_aligned (gimple *stmt, tree attr, ccp_prop_value_t ptrval,
2071                           bool alloc_aligned)
2072 {
2073   tree align, misalign = NULL_TREE, type;
2074   unsigned HOST_WIDE_INT aligni, misaligni = 0;
2075   ccp_prop_value_t alignval;
2076   widest_int value, mask;
2077   ccp_prop_value_t val;
2078
2079   if (attr == NULL_TREE)
2080     {
2081       tree ptr = gimple_call_arg (stmt, 0);
2082       type = TREE_TYPE (ptr);
2083       ptrval = get_value_for_expr (ptr, true);
2084     }
2085   else
2086     {
2087       tree lhs = gimple_call_lhs (stmt);
2088       type = TREE_TYPE (lhs);
2089     }
2090
2091   if (ptrval.lattice_val == UNDEFINED)
2092     return ptrval;
2093   gcc_assert ((ptrval.lattice_val == CONSTANT
2094                && TREE_CODE (ptrval.value) == INTEGER_CST)
2095               || wi::sext (ptrval.mask, TYPE_PRECISION (type)) == -1);
2096   if (attr == NULL_TREE)
2097     {
2098       /* Get aligni and misaligni from __builtin_assume_aligned.  */
2099       align = gimple_call_arg (stmt, 1);
2100       if (!tree_fits_uhwi_p (align))
2101         return ptrval;
2102       aligni = tree_to_uhwi (align);
2103       if (gimple_call_num_args (stmt) > 2)
2104         {
2105           misalign = gimple_call_arg (stmt, 2);
2106           if (!tree_fits_uhwi_p (misalign))
2107             return ptrval;
2108           misaligni = tree_to_uhwi (misalign);
2109         }
2110     }
2111   else
2112     {
2113       /* Get aligni and misaligni from assume_aligned or
2114          alloc_align attributes.  */
2115       if (TREE_VALUE (attr) == NULL_TREE)
2116         return ptrval;
2117       attr = TREE_VALUE (attr);
2118       align = TREE_VALUE (attr);
2119       if (!tree_fits_uhwi_p (align))
2120         return ptrval;
2121       aligni = tree_to_uhwi (align);
2122       if (alloc_aligned)
2123         {
2124           if (aligni == 0 || aligni > gimple_call_num_args (stmt))
2125             return ptrval;
2126           align = gimple_call_arg (stmt, aligni - 1);
2127           if (!tree_fits_uhwi_p (align))
2128             return ptrval;
2129           aligni = tree_to_uhwi (align);
2130         }
2131       else if (TREE_CHAIN (attr) && TREE_VALUE (TREE_CHAIN (attr)))
2132         {
2133           misalign = TREE_VALUE (TREE_CHAIN (attr));
2134           if (!tree_fits_uhwi_p (misalign))
2135             return ptrval;
2136           misaligni = tree_to_uhwi (misalign);
2137         }
2138     }
2139   if (aligni <= 1 || (aligni & (aligni - 1)) != 0 || misaligni >= aligni)
2140     return ptrval;
2141
2142   align = build_int_cst_type (type, -aligni);
2143   alignval = get_value_for_expr (align, true);
2144   bit_value_binop (BIT_AND_EXPR, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask,
2145                    TYPE_SIGN (type), TYPE_PRECISION (type), value_to_wide_int (ptrval), ptrval.mask,
2146                    TYPE_SIGN (type), TYPE_PRECISION (type), value_to_wide_int (alignval), alignval.mask);
2147
2148   if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
2149     {
2150       val.lattice_val = CONSTANT;
2151       val.mask = mask;
2152       gcc_assert ((mask.to_uhwi () & (aligni - 1)) == 0);
2153       gcc_assert ((value.to_uhwi () & (aligni - 1)) == 0);
2154       value |= misaligni;
2155       /* ???  Delay building trees here.  */
2156       val.value = wide_int_to_tree (type, value);
2157     }
2158   else
2159     {
2160       val.lattice_val = VARYING;
2161       val.value = NULL_TREE;
2162       val.mask = -1;
2163     }
2164   return val;
2165 }
2166
2167 /* Evaluate statement STMT.
2168    Valid only for assignments, calls, conditionals, and switches. */
2169
2170 static ccp_prop_value_t
2171 evaluate_stmt (gimple *stmt)
2172 {
2173   ccp_prop_value_t val;
2174   tree simplified = NULL_TREE;
2175   ccp_lattice_t likelyvalue = likely_value (stmt);
2176   bool is_constant = false;
2177   unsigned int align;
2178   bool ignore_return_flags = false;
2179
2180   if (dump_file && (dump_flags & TDF_DETAILS))
2181     {
2182       fprintf (dump_file, "which is likely ");
2183       switch (likelyvalue)
2184         {
2185         case CONSTANT:
2186           fprintf (dump_file, "CONSTANT");
2187           break;
2188         case UNDEFINED:
2189           fprintf (dump_file, "UNDEFINED");
2190           break;
2191         case VARYING:
2192           fprintf (dump_file, "VARYING");
2193           break;
2194         default:;
2195         }
2196       fprintf (dump_file, "\n");
2197     }
2198
2199   /* If the statement is likely to have a CONSTANT result, then try
2200      to fold the statement to determine the constant value.  */
2201   /* FIXME.  This is the only place that we call ccp_fold.
2202      Since likely_value never returns CONSTANT for calls, we will
2203      not attempt to fold them, including builtins that may profit.  */
2204   if (likelyvalue == CONSTANT)
2205     {
2206       fold_defer_overflow_warnings ();
2207       simplified = ccp_fold (stmt);
2208       if (simplified
2209           && TREE_CODE (simplified) == SSA_NAME)
2210         {
2211           /* We may not use values of something that may be simulated again,
2212              see valueize_op_1.  */
2213           if (SSA_NAME_IS_DEFAULT_DEF (simplified)
2214               || ! prop_simulate_again_p (SSA_NAME_DEF_STMT (simplified)))
2215             {
2216               ccp_prop_value_t *val = get_value (simplified);
2217               if (val && val->lattice_val != VARYING)
2218                 {
2219                   fold_undefer_overflow_warnings (true, stmt, 0);
2220                   return *val;
2221                 }
2222             }
2223           else
2224             /* We may also not place a non-valueized copy in the lattice
2225                as that might become stale if we never re-visit this stmt.  */
2226             simplified = NULL_TREE;
2227         }
2228       is_constant = simplified && is_gimple_min_invariant (simplified);
2229       fold_undefer_overflow_warnings (is_constant, stmt, 0);
2230       if (is_constant)
2231         {
2232           /* The statement produced a constant value.  */
2233           val.lattice_val = CONSTANT;
2234           val.value = simplified;
2235           val.mask = 0;
2236           return val;
2237         }
2238     }
2239   /* If the statement is likely to have a VARYING result, then do not
2240      bother folding the statement.  */
2241   else if (likelyvalue == VARYING)
2242     {
2243       enum gimple_code code = gimple_code (stmt);
2244       if (code == GIMPLE_ASSIGN)
2245         {
2246           enum tree_code subcode = gimple_assign_rhs_code (stmt);
2247
2248           /* Other cases cannot satisfy is_gimple_min_invariant
2249              without folding.  */
2250           if (get_gimple_rhs_class (subcode) == GIMPLE_SINGLE_RHS)
2251             simplified = gimple_assign_rhs1 (stmt);
2252         }
2253       else if (code == GIMPLE_SWITCH)
2254         simplified = gimple_switch_index (as_a <gswitch *> (stmt));
2255       else
2256         /* These cannot satisfy is_gimple_min_invariant without folding.  */
2257         gcc_assert (code == GIMPLE_CALL || code == GIMPLE_COND);
2258       is_constant = simplified && is_gimple_min_invariant (simplified);
2259       if (is_constant)
2260         {
2261           /* The statement produced a constant value.  */
2262           val.lattice_val = CONSTANT;
2263           val.value = simplified;
2264           val.mask = 0;
2265         }
2266     }
2267   /* If the statement result is likely UNDEFINED, make it so.  */
2268   else if (likelyvalue == UNDEFINED)
2269     {
2270       val.lattice_val = UNDEFINED;
2271       val.value = NULL_TREE;
2272       val.mask = 0;
2273       return val;
2274     }
2275
2276   /* Resort to simplification for bitwise tracking.  */
2277   if (flag_tree_bit_ccp
2278       && (likelyvalue == CONSTANT || is_gimple_call (stmt)
2279           || (gimple_assign_single_p (stmt)
2280               && gimple_assign_rhs_code (stmt) == ADDR_EXPR))
2281       && !is_constant)
2282     {
2283       enum gimple_code code = gimple_code (stmt);
2284       val.lattice_val = VARYING;
2285       val.value = NULL_TREE;
2286       val.mask = -1;
2287       if (code == GIMPLE_ASSIGN)
2288         {
2289           enum tree_code subcode = gimple_assign_rhs_code (stmt);
2290           tree rhs1 = gimple_assign_rhs1 (stmt);
2291           tree lhs = gimple_assign_lhs (stmt);
2292           if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
2293                || POINTER_TYPE_P (TREE_TYPE (lhs)))
2294               && (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
2295                   || POINTER_TYPE_P (TREE_TYPE (rhs1))))
2296             switch (get_gimple_rhs_class (subcode))
2297               {
2298               case GIMPLE_SINGLE_RHS:
2299                 val = get_value_for_expr (rhs1, true);
2300                 break;
2301
2302               case GIMPLE_UNARY_RHS:
2303                 val = bit_value_unop (subcode, TREE_TYPE (lhs), rhs1);
2304                 break;
2305
2306               case GIMPLE_BINARY_RHS:
2307                 val = bit_value_binop (subcode, TREE_TYPE (lhs), rhs1,
2308                                        gimple_assign_rhs2 (stmt));
2309                 break;
2310
2311               default:;
2312               }
2313         }
2314       else if (code == GIMPLE_COND)
2315         {
2316           enum tree_code code = gimple_cond_code (stmt);
2317           tree rhs1 = gimple_cond_lhs (stmt);
2318           tree rhs2 = gimple_cond_rhs (stmt);
2319           if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
2320               || POINTER_TYPE_P (TREE_TYPE (rhs1)))
2321             val = bit_value_binop (code, TREE_TYPE (rhs1), rhs1, rhs2);
2322         }
2323       else if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
2324         {
2325           tree fndecl = gimple_call_fndecl (stmt);
2326           switch (DECL_FUNCTION_CODE (fndecl))
2327             {
2328             case BUILT_IN_MALLOC:
2329             case BUILT_IN_REALLOC:
2330             case BUILT_IN_CALLOC:
2331             case BUILT_IN_STRDUP:
2332             case BUILT_IN_STRNDUP:
2333               val.lattice_val = CONSTANT;
2334               val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
2335               val.mask = ~((HOST_WIDE_INT) MALLOC_ABI_ALIGNMENT
2336                            / BITS_PER_UNIT - 1);
2337               break;
2338
2339             CASE_BUILT_IN_ALLOCA:
2340               align = (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_ALLOCA
2341                        ? BIGGEST_ALIGNMENT
2342                        : TREE_INT_CST_LOW (gimple_call_arg (stmt, 1)));
2343               val.lattice_val = CONSTANT;
2344               val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
2345               val.mask = ~((HOST_WIDE_INT) align / BITS_PER_UNIT - 1);
2346               break;
2347
2348             case BUILT_IN_ASSUME_ALIGNED:
2349               val = bit_value_assume_aligned (stmt, NULL_TREE, val, false);
2350               ignore_return_flags = true;
2351               break;
2352
2353             case BUILT_IN_ALIGNED_ALLOC:
2354             case BUILT_IN_GOMP_ALLOC:
2355               {
2356                 tree align = get_constant_value (gimple_call_arg (stmt, 0));
2357                 if (align
2358                     && tree_fits_uhwi_p (align))
2359                   {
2360                     unsigned HOST_WIDE_INT aligni = tree_to_uhwi (align);
2361                     if (aligni > 1
2362                         /* align must be power-of-two */
2363                         && (aligni & (aligni - 1)) == 0)
2364                       {
2365                         val.lattice_val = CONSTANT;
2366                         val.value = build_int_cst (ptr_type_node, 0);
2367                         val.mask = -aligni;
2368                       }
2369                   }
2370                 break;
2371               }
2372
2373             case BUILT_IN_BSWAP16:
2374             case BUILT_IN_BSWAP32:
2375             case BUILT_IN_BSWAP64:
2376             case BUILT_IN_BSWAP128:
2377               val = get_value_for_expr (gimple_call_arg (stmt, 0), true);
2378               if (val.lattice_val == UNDEFINED)
2379                 break;
2380               else if (val.lattice_val == CONSTANT
2381                        && val.value
2382                        && TREE_CODE (val.value) == INTEGER_CST)
2383                 {
2384                   tree type = TREE_TYPE (gimple_call_lhs (stmt));
2385                   int prec = TYPE_PRECISION (type);
2386                   wide_int wval = wi::to_wide (val.value);
2387                   val.value
2388                     = wide_int_to_tree (type,
2389                                         wide_int::from (wval, prec,
2390                                                         UNSIGNED).bswap ());
2391                   val.mask
2392                     = widest_int::from (wide_int::from (val.mask, prec,
2393                                                         UNSIGNED).bswap (),
2394                                         UNSIGNED);
2395                   if (wi::sext (val.mask, prec) != -1)
2396                     break;
2397                 }
2398               val.lattice_val = VARYING;
2399               val.value = NULL_TREE;
2400               val.mask = -1;
2401               break;
2402
2403             default:;
2404             }
2405         }
2406       if (is_gimple_call (stmt) && gimple_call_lhs (stmt))
2407         {
2408           tree fntype = gimple_call_fntype (stmt);
2409           if (fntype)
2410             {
2411               tree attrs = lookup_attribute ("assume_aligned",
2412                                              TYPE_ATTRIBUTES (fntype));
2413               if (attrs)
2414                 val = bit_value_assume_aligned (stmt, attrs, val, false);
2415               attrs = lookup_attribute ("alloc_align",
2416                                         TYPE_ATTRIBUTES (fntype));
2417               if (attrs)
2418                 val = bit_value_assume_aligned (stmt, attrs, val, true);
2419             }
2420           int flags = ignore_return_flags
2421                       ? 0 : gimple_call_return_flags (as_a <gcall *> (stmt));
2422           if (flags & ERF_RETURNS_ARG
2423               && (flags & ERF_RETURN_ARG_MASK) < gimple_call_num_args (stmt))
2424             {
2425               val = get_value_for_expr
2426                          (gimple_call_arg (stmt,
2427                                            flags & ERF_RETURN_ARG_MASK), true);
2428             }
2429         }
2430       is_constant = (val.lattice_val == CONSTANT);
2431     }
2432
2433   if (flag_tree_bit_ccp
2434       && ((is_constant && TREE_CODE (val.value) == INTEGER_CST)
2435           || !is_constant)
2436       && gimple_get_lhs (stmt)
2437       && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME)
2438     {
2439       tree lhs = gimple_get_lhs (stmt);
2440       wide_int nonzero_bits = get_nonzero_bits (lhs);
2441       if (nonzero_bits != -1)
2442         {
2443           if (!is_constant)
2444             {
2445               val.lattice_val = CONSTANT;
2446               val.value = build_zero_cst (TREE_TYPE (lhs));
2447               val.mask = extend_mask (nonzero_bits, TYPE_SIGN (TREE_TYPE (lhs)));
2448               is_constant = true;
2449             }
2450           else
2451             {
2452               if (wi::bit_and_not (wi::to_wide (val.value), nonzero_bits) != 0)
2453                 val.value = wide_int_to_tree (TREE_TYPE (lhs),
2454                                               nonzero_bits
2455                                               & wi::to_wide (val.value));
2456               if (nonzero_bits == 0)
2457                 val.mask = 0;
2458               else
2459                 val.mask = val.mask & extend_mask (nonzero_bits,
2460                                                    TYPE_SIGN (TREE_TYPE (lhs)));
2461             }
2462         }
2463     }
2464
2465   /* The statement produced a nonconstant value.  */
2466   if (!is_constant)
2467     {
2468       /* The statement produced a copy.  */
2469       if (simplified && TREE_CODE (simplified) == SSA_NAME
2470           && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (simplified))
2471         {
2472           val.lattice_val = CONSTANT;
2473           val.value = simplified;
2474           val.mask = -1;
2475         }
2476       /* The statement is VARYING.  */
2477       else
2478         {
2479           val.lattice_val = VARYING;
2480           val.value = NULL_TREE;
2481           val.mask = -1;
2482         }
2483     }
2484
2485   return val;
2486 }
2487
2488 typedef hash_table<nofree_ptr_hash<gimple> > gimple_htab;
2489
2490 /* Given a BUILT_IN_STACK_SAVE value SAVED_VAL, insert a clobber of VAR before
2491    each matching BUILT_IN_STACK_RESTORE.  Mark visited phis in VISITED.  */
2492
2493 static void
2494 insert_clobber_before_stack_restore (tree saved_val, tree var,
2495                                      gimple_htab **visited)
2496 {
2497   gimple *stmt;
2498   gassign *clobber_stmt;
2499   tree clobber;
2500   imm_use_iterator iter;
2501   gimple_stmt_iterator i;
2502   gimple **slot;
2503
2504   FOR_EACH_IMM_USE_STMT (stmt, iter, saved_val)
2505     if (gimple_call_builtin_p (stmt, BUILT_IN_STACK_RESTORE))
2506       {
2507         clobber = build_clobber (TREE_TYPE (var));
2508         clobber_stmt = gimple_build_assign (var, clobber);
2509
2510         i = gsi_for_stmt (stmt);
2511         gsi_insert_before (&i, clobber_stmt, GSI_SAME_STMT);
2512       }
2513     else if (gimple_code (stmt) == GIMPLE_PHI)
2514       {
2515         if (!*visited)
2516           *visited = new gimple_htab (10);
2517
2518         slot = (*visited)->find_slot (stmt, INSERT);
2519         if (*slot != NULL)
2520           continue;
2521
2522         *slot = stmt;
2523         insert_clobber_before_stack_restore (gimple_phi_result (stmt), var,
2524                                              visited);
2525       }
2526     else if (gimple_assign_ssa_name_copy_p (stmt))
2527       insert_clobber_before_stack_restore (gimple_assign_lhs (stmt), var,
2528                                            visited);
2529 }
2530
2531 /* Advance the iterator to the previous non-debug gimple statement in the same
2532    or dominating basic block.  */
2533
2534 static inline void
2535 gsi_prev_dom_bb_nondebug (gimple_stmt_iterator *i)
2536 {
2537   basic_block dom;
2538
2539   gsi_prev_nondebug (i);
2540   while (gsi_end_p (*i))
2541     {
2542       dom = get_immediate_dominator (CDI_DOMINATORS, gsi_bb (*i));
2543       if (dom == NULL || dom == ENTRY_BLOCK_PTR_FOR_FN (cfun))
2544         return;
2545
2546       *i = gsi_last_bb (dom);
2547     }
2548 }
2549
2550 /* Find a BUILT_IN_STACK_SAVE dominating gsi_stmt (I), and insert
2551    a clobber of VAR before each matching BUILT_IN_STACK_RESTORE.
2552
2553    It is possible that BUILT_IN_STACK_SAVE cannot be found in a dominator when
2554    a previous pass (such as DOM) duplicated it along multiple paths to a BB.
2555    In that case the function gives up without inserting the clobbers.  */
2556
2557 static void
2558 insert_clobbers_for_var (gimple_stmt_iterator i, tree var)
2559 {
2560   gimple *stmt;
2561   tree saved_val;
2562   gimple_htab *visited = NULL;
2563
2564   for (; !gsi_end_p (i); gsi_prev_dom_bb_nondebug (&i))
2565     {
2566       stmt = gsi_stmt (i);
2567
2568       if (!gimple_call_builtin_p (stmt, BUILT_IN_STACK_SAVE))
2569         continue;
2570
2571       saved_val = gimple_call_lhs (stmt);
2572       if (saved_val == NULL_TREE)
2573         continue;
2574
2575       insert_clobber_before_stack_restore (saved_val, var, &visited);
2576       break;
2577     }
2578
2579   delete visited;
2580 }
2581
2582 /* Detects a __builtin_alloca_with_align with constant size argument.  Declares
2583    fixed-size array and returns the address, if found, otherwise returns
2584    NULL_TREE.  */
2585
2586 static tree
2587 fold_builtin_alloca_with_align (gimple *stmt)
2588 {
2589   unsigned HOST_WIDE_INT size, threshold, n_elem;
2590   tree lhs, arg, block, var, elem_type, array_type;
2591
2592   /* Get lhs.  */
2593   lhs = gimple_call_lhs (stmt);
2594   if (lhs == NULL_TREE)
2595     return NULL_TREE;
2596
2597   /* Detect constant argument.  */
2598   arg = get_constant_value (gimple_call_arg (stmt, 0));
2599   if (arg == NULL_TREE
2600       || TREE_CODE (arg) != INTEGER_CST
2601       || !tree_fits_uhwi_p (arg))
2602     return NULL_TREE;
2603
2604   size = tree_to_uhwi (arg);
2605
2606   /* Heuristic: don't fold large allocas.  */
2607   threshold = (unsigned HOST_WIDE_INT)param_large_stack_frame;
2608   /* In case the alloca is located at function entry, it has the same lifetime
2609      as a declared array, so we allow a larger size.  */
2610   block = gimple_block (stmt);
2611   if (!(cfun->after_inlining
2612         && block
2613         && TREE_CODE (BLOCK_SUPERCONTEXT (block)) == FUNCTION_DECL))
2614     threshold /= 10;
2615   if (size > threshold)
2616     return NULL_TREE;
2617
2618   /* We have to be able to move points-to info.  We used to assert
2619      that we can but IPA PTA might end up with two UIDs here
2620      as it might need to handle more than one instance being
2621      live at the same time.  Instead of trying to detect this case
2622      (using the first UID would be OK) just give up for now.  */
2623   struct ptr_info_def *pi = SSA_NAME_PTR_INFO (lhs);
2624   unsigned uid = 0;
2625   if (pi != NULL
2626       && !pi->pt.anything
2627       && !pt_solution_singleton_or_null_p (&pi->pt, &uid))
2628     return NULL_TREE;
2629
2630   /* Declare array.  */
2631   elem_type = build_nonstandard_integer_type (BITS_PER_UNIT, 1);
2632   n_elem = size * 8 / BITS_PER_UNIT;
2633   array_type = build_array_type_nelts (elem_type, n_elem);
2634
2635   if (tree ssa_name = SSA_NAME_IDENTIFIER (lhs))
2636     {
2637       /* Give the temporary a name derived from the name of the VLA
2638          declaration so it can be referenced in diagnostics.  */
2639       const char *name = IDENTIFIER_POINTER (ssa_name);
2640       var = create_tmp_var (array_type, name);
2641     }
2642   else
2643     var = create_tmp_var (array_type);
2644
2645   if (gimple *lhsdef = SSA_NAME_DEF_STMT (lhs))
2646     {
2647       /* Set the temporary's location to that of the VLA declaration
2648          so it can be pointed to in diagnostics.  */
2649       location_t loc = gimple_location (lhsdef);
2650       DECL_SOURCE_LOCATION (var) = loc;
2651     }
2652
2653   SET_DECL_ALIGN (var, TREE_INT_CST_LOW (gimple_call_arg (stmt, 1)));
2654   if (uid != 0)
2655     SET_DECL_PT_UID (var, uid);
2656
2657   /* Fold alloca to the address of the array.  */
2658   return fold_convert (TREE_TYPE (lhs), build_fold_addr_expr (var));
2659 }
2660
2661 /* Fold the stmt at *GSI with CCP specific information that propagating
2662    and regular folding does not catch.  */
2663
2664 bool
2665 ccp_folder::fold_stmt (gimple_stmt_iterator *gsi)
2666 {
2667   gimple *stmt = gsi_stmt (*gsi);
2668
2669   switch (gimple_code (stmt))
2670     {
2671     case GIMPLE_COND:
2672       {
2673         gcond *cond_stmt = as_a <gcond *> (stmt);
2674         ccp_prop_value_t val;
2675         /* Statement evaluation will handle type mismatches in constants
2676            more gracefully than the final propagation.  This allows us to
2677            fold more conditionals here.  */
2678         val = evaluate_stmt (stmt);
2679         if (val.lattice_val != CONSTANT
2680             || val.mask != 0)
2681           return false;
2682
2683         if (dump_file)
2684           {
2685             fprintf (dump_file, "Folding predicate ");
2686             print_gimple_expr (dump_file, stmt, 0);
2687             fprintf (dump_file, " to ");
2688             print_generic_expr (dump_file, val.value);
2689             fprintf (dump_file, "\n");
2690           }
2691
2692         if (integer_zerop (val.value))
2693           gimple_cond_make_false (cond_stmt);
2694         else
2695           gimple_cond_make_true (cond_stmt);
2696
2697         return true;
2698       }
2699
2700     case GIMPLE_CALL:
2701       {
2702         tree lhs = gimple_call_lhs (stmt);
2703         int flags = gimple_call_flags (stmt);
2704         tree val;
2705         tree argt;
2706         bool changed = false;
2707         unsigned i;
2708
2709         /* If the call was folded into a constant make sure it goes
2710            away even if we cannot propagate into all uses because of
2711            type issues.  */
2712         if (lhs
2713             && TREE_CODE (lhs) == SSA_NAME
2714             && (val = get_constant_value (lhs))
2715             /* Don't optimize away calls that have side-effects.  */
2716             && (flags & (ECF_CONST|ECF_PURE)) != 0
2717             && (flags & ECF_LOOPING_CONST_OR_PURE) == 0)
2718           {
2719             tree new_rhs = unshare_expr (val);
2720             if (!useless_type_conversion_p (TREE_TYPE (lhs),
2721                                             TREE_TYPE (new_rhs)))
2722               new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs);
2723             gimplify_and_update_call_from_tree (gsi, new_rhs);
2724             return true;
2725           }
2726
2727         /* Internal calls provide no argument types, so the extra laxity
2728            for normal calls does not apply.  */
2729         if (gimple_call_internal_p (stmt))
2730           return false;
2731
2732         /* The heuristic of fold_builtin_alloca_with_align differs before and
2733            after inlining, so we don't require the arg to be changed into a
2734            constant for folding, but just to be constant.  */
2735         if (gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN)
2736             || gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX))
2737           {
2738             tree new_rhs = fold_builtin_alloca_with_align (stmt);
2739             if (new_rhs)
2740               {
2741                 gimplify_and_update_call_from_tree (gsi, new_rhs);
2742                 tree var = TREE_OPERAND (TREE_OPERAND (new_rhs, 0),0);
2743                 insert_clobbers_for_var (*gsi, var);
2744                 return true;
2745               }
2746           }
2747
2748         /* If there's no extra info from an assume_aligned call,
2749            drop it so it doesn't act as otherwise useless dataflow
2750            barrier.  */
2751         if (gimple_call_builtin_p (stmt, BUILT_IN_ASSUME_ALIGNED))
2752           {
2753             tree ptr = gimple_call_arg (stmt, 0);
2754             ccp_prop_value_t ptrval = get_value_for_expr (ptr, true);
2755             if (ptrval.lattice_val == CONSTANT
2756                 && TREE_CODE (ptrval.value) == INTEGER_CST
2757                 && ptrval.mask != 0)
2758               {
2759                 ccp_prop_value_t val
2760                   = bit_value_assume_aligned (stmt, NULL_TREE, ptrval, false);
2761                 unsigned int ptralign = least_bit_hwi (ptrval.mask.to_uhwi ());
2762                 unsigned int align = least_bit_hwi (val.mask.to_uhwi ());
2763                 if (ptralign == align
2764                     && ((TREE_INT_CST_LOW (ptrval.value) & (align - 1))
2765                         == (TREE_INT_CST_LOW (val.value) & (align - 1))))
2766                   {
2767                     replace_call_with_value (gsi, ptr);
2768                     return true;
2769                   }
2770               }
2771           }
2772
2773         /* Propagate into the call arguments.  Compared to replace_uses_in
2774            this can use the argument slot types for type verification
2775            instead of the current argument type.  We also can safely
2776            drop qualifiers here as we are dealing with constants anyway.  */
2777         argt = TYPE_ARG_TYPES (gimple_call_fntype (stmt));
2778         for (i = 0; i < gimple_call_num_args (stmt) && argt;
2779              ++i, argt = TREE_CHAIN (argt))
2780           {
2781             tree arg = gimple_call_arg (stmt, i);
2782             if (TREE_CODE (arg) == SSA_NAME
2783                 && (val = get_constant_value (arg))
2784                 && useless_type_conversion_p
2785                      (TYPE_MAIN_VARIANT (TREE_VALUE (argt)),
2786                       TYPE_MAIN_VARIANT (TREE_TYPE (val))))
2787               {
2788                 gimple_call_set_arg (stmt, i, unshare_expr (val));
2789                 changed = true;
2790               }
2791           }
2792
2793         return changed;
2794       }
2795
2796     case GIMPLE_ASSIGN:
2797       {
2798         tree lhs = gimple_assign_lhs (stmt);
2799         tree val;
2800
2801         /* If we have a load that turned out to be constant replace it
2802            as we cannot propagate into all uses in all cases.  */
2803         if (gimple_assign_single_p (stmt)
2804             && TREE_CODE (lhs) == SSA_NAME
2805             && (val = get_constant_value (lhs)))
2806           {
2807             tree rhs = unshare_expr (val);
2808             if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2809               rhs = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
2810             gimple_assign_set_rhs_from_tree (gsi, rhs);
2811             return true;
2812           }
2813
2814         return false;
2815       }
2816
2817     default:
2818       return false;
2819     }
2820 }
2821
2822 /* Visit the assignment statement STMT.  Set the value of its LHS to the
2823    value computed by the RHS and store LHS in *OUTPUT_P.  If STMT
2824    creates virtual definitions, set the value of each new name to that
2825    of the RHS (if we can derive a constant out of the RHS).
2826    Value-returning call statements also perform an assignment, and
2827    are handled here.  */
2828
2829 static enum ssa_prop_result
2830 visit_assignment (gimple *stmt, tree *output_p)
2831 {
2832   ccp_prop_value_t val;
2833   enum ssa_prop_result retval = SSA_PROP_NOT_INTERESTING;
2834
2835   tree lhs = gimple_get_lhs (stmt);
2836   if (TREE_CODE (lhs) == SSA_NAME)
2837     {
2838       /* Evaluate the statement, which could be
2839          either a GIMPLE_ASSIGN or a GIMPLE_CALL.  */
2840       val = evaluate_stmt (stmt);
2841
2842       /* If STMT is an assignment to an SSA_NAME, we only have one
2843          value to set.  */
2844       if (set_lattice_value (lhs, &val))
2845         {
2846           *output_p = lhs;
2847           if (val.lattice_val == VARYING)
2848             retval = SSA_PROP_VARYING;
2849           else
2850             retval = SSA_PROP_INTERESTING;
2851         }
2852     }
2853
2854   return retval;
2855 }
2856
2857
2858 /* Visit the conditional statement STMT.  Return SSA_PROP_INTERESTING
2859    if it can determine which edge will be taken.  Otherwise, return
2860    SSA_PROP_VARYING.  */
2861
2862 static enum ssa_prop_result
2863 visit_cond_stmt (gimple *stmt, edge *taken_edge_p)
2864 {
2865   ccp_prop_value_t val;
2866   basic_block block;
2867
2868   block = gimple_bb (stmt);
2869   val = evaluate_stmt (stmt);
2870   if (val.lattice_val != CONSTANT
2871       || val.mask != 0)
2872     return SSA_PROP_VARYING;
2873
2874   /* Find which edge out of the conditional block will be taken and add it
2875      to the worklist.  If no single edge can be determined statically,
2876      return SSA_PROP_VARYING to feed all the outgoing edges to the
2877      propagation engine.  */
2878   *taken_edge_p = find_taken_edge (block, val.value);
2879   if (*taken_edge_p)
2880     return SSA_PROP_INTERESTING;
2881   else
2882     return SSA_PROP_VARYING;
2883 }
2884
2885
2886 /* Evaluate statement STMT.  If the statement produces an output value and
2887    its evaluation changes the lattice value of its output, return
2888    SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the
2889    output value.
2890
2891    If STMT is a conditional branch and we can determine its truth
2892    value, set *TAKEN_EDGE_P accordingly.  If STMT produces a varying
2893    value, return SSA_PROP_VARYING.  */
2894
2895 enum ssa_prop_result
2896 ccp_propagate::visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p)
2897 {
2898   tree def;
2899   ssa_op_iter iter;
2900
2901   if (dump_file && (dump_flags & TDF_DETAILS))
2902     {
2903       fprintf (dump_file, "\nVisiting statement:\n");
2904       print_gimple_stmt (dump_file, stmt, 0, dump_flags);
2905     }
2906
2907   switch (gimple_code (stmt))
2908     {
2909       case GIMPLE_ASSIGN:
2910         /* If the statement is an assignment that produces a single
2911            output value, evaluate its RHS to see if the lattice value of
2912            its output has changed.  */
2913         return visit_assignment (stmt, output_p);
2914
2915       case GIMPLE_CALL:
2916         /* A value-returning call also performs an assignment.  */
2917         if (gimple_call_lhs (stmt) != NULL_TREE)
2918           return visit_assignment (stmt, output_p);
2919         break;
2920
2921       case GIMPLE_COND:
2922       case GIMPLE_SWITCH:
2923         /* If STMT is a conditional branch, see if we can determine
2924            which branch will be taken.   */
2925         /* FIXME.  It appears that we should be able to optimize
2926            computed GOTOs here as well.  */
2927         return visit_cond_stmt (stmt, taken_edge_p);
2928
2929       default:
2930         break;
2931     }
2932
2933   /* Any other kind of statement is not interesting for constant
2934      propagation and, therefore, not worth simulating.  */
2935   if (dump_file && (dump_flags & TDF_DETAILS))
2936     fprintf (dump_file, "No interesting values produced.  Marked VARYING.\n");
2937
2938   /* Definitions made by statements other than assignments to
2939      SSA_NAMEs represent unknown modifications to their outputs.
2940      Mark them VARYING.  */
2941   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
2942     set_value_varying (def);
2943
2944   return SSA_PROP_VARYING;
2945 }
2946
2947
2948 /* Main entry point for SSA Conditional Constant Propagation.  If NONZERO_P,
2949    record nonzero bits.  */
2950
2951 static unsigned int
2952 do_ssa_ccp (bool nonzero_p)
2953 {
2954   unsigned int todo = 0;
2955   calculate_dominance_info (CDI_DOMINATORS);
2956
2957   ccp_initialize ();
2958   class ccp_propagate ccp_propagate;
2959   ccp_propagate.ssa_propagate ();
2960   if (ccp_finalize (nonzero_p || flag_ipa_bit_cp))
2961     {
2962       todo = (TODO_cleanup_cfg | TODO_update_ssa);
2963
2964       /* ccp_finalize does not preserve loop-closed ssa.  */
2965       loops_state_clear (LOOP_CLOSED_SSA);
2966     }
2967
2968   free_dominance_info (CDI_DOMINATORS);
2969   return todo;
2970 }
2971
2972
2973 namespace {
2974
2975 const pass_data pass_data_ccp =
2976 {
2977   GIMPLE_PASS, /* type */
2978   "ccp", /* name */
2979   OPTGROUP_NONE, /* optinfo_flags */
2980   TV_TREE_CCP, /* tv_id */
2981   ( PROP_cfg | PROP_ssa ), /* properties_required */
2982   0, /* properties_provided */
2983   0, /* properties_destroyed */
2984   0, /* todo_flags_start */
2985   TODO_update_address_taken, /* todo_flags_finish */
2986 };
2987
2988 class pass_ccp : public gimple_opt_pass
2989 {
2990 public:
2991   pass_ccp (gcc::context *ctxt)
2992     : gimple_opt_pass (pass_data_ccp, ctxt), nonzero_p (false)
2993   {}
2994
2995   /* opt_pass methods: */
2996   opt_pass * clone () { return new pass_ccp (m_ctxt); }
2997   void set_pass_param (unsigned int n, bool param)
2998     {
2999       gcc_assert (n == 0);
3000       nonzero_p = param;
3001     }
3002   virtual bool gate (function *) { return flag_tree_ccp != 0; }
3003   virtual unsigned int execute (function *) { return do_ssa_ccp (nonzero_p); }
3004
3005  private:
3006   /* Determines whether the pass instance records nonzero bits.  */
3007   bool nonzero_p;
3008 }; // class pass_ccp
3009
3010 } // anon namespace
3011
3012 gimple_opt_pass *
3013 make_pass_ccp (gcc::context *ctxt)
3014 {
3015   return new pass_ccp (ctxt);
3016 }
3017
3018
3019
3020 /* Try to optimize out __builtin_stack_restore.  Optimize it out
3021    if there is another __builtin_stack_restore in the same basic
3022    block and no calls or ASM_EXPRs are in between, or if this block's
3023    only outgoing edge is to EXIT_BLOCK and there are no calls or
3024    ASM_EXPRs after this __builtin_stack_restore.  */
3025
3026 static tree
3027 optimize_stack_restore (gimple_stmt_iterator i)
3028 {
3029   tree callee;
3030   gimple *stmt;
3031
3032   basic_block bb = gsi_bb (i);
3033   gimple *call = gsi_stmt (i);
3034
3035   if (gimple_code (call) != GIMPLE_CALL
3036       || gimple_call_num_args (call) != 1
3037       || TREE_CODE (gimple_call_arg (call, 0)) != SSA_NAME
3038       || !POINTER_TYPE_P (TREE_TYPE (gimple_call_arg (call, 0))))
3039     return NULL_TREE;
3040
3041   for (gsi_next (&i); !gsi_end_p (i); gsi_next (&i))
3042     {
3043       stmt = gsi_stmt (i);
3044       if (gimple_code (stmt) == GIMPLE_ASM)
3045         return NULL_TREE;
3046       if (gimple_code (stmt) != GIMPLE_CALL)
3047         continue;
3048
3049       callee = gimple_call_fndecl (stmt);
3050       if (!callee
3051           || !fndecl_built_in_p (callee, BUILT_IN_NORMAL)
3052           /* All regular builtins are ok, just obviously not alloca.  */
3053           || ALLOCA_FUNCTION_CODE_P (DECL_FUNCTION_CODE (callee)))
3054         return NULL_TREE;
3055
3056       if (fndecl_built_in_p (callee, BUILT_IN_STACK_RESTORE))
3057         goto second_stack_restore;
3058     }
3059
3060   if (!gsi_end_p (i))
3061     return NULL_TREE;
3062
3063   /* Allow one successor of the exit block, or zero successors.  */
3064   switch (EDGE_COUNT (bb->succs))
3065     {
3066     case 0:
3067       break;
3068     case 1:
3069       if (single_succ_edge (bb)->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
3070         return NULL_TREE;
3071       break;
3072     default:
3073       return NULL_TREE;
3074     }
3075  second_stack_restore:
3076
3077   /* If there's exactly one use, then zap the call to __builtin_stack_save.
3078      If there are multiple uses, then the last one should remove the call.
3079      In any case, whether the call to __builtin_stack_save can be removed
3080      or not is irrelevant to removing the call to __builtin_stack_restore.  */
3081   if (has_single_use (gimple_call_arg (call, 0)))
3082     {
3083       gimple *stack_save = SSA_NAME_DEF_STMT (gimple_call_arg (call, 0));
3084       if (is_gimple_call (stack_save))
3085         {
3086           callee = gimple_call_fndecl (stack_save);
3087           if (callee && fndecl_built_in_p (callee, BUILT_IN_STACK_SAVE))
3088             {
3089               gimple_stmt_iterator stack_save_gsi;
3090               tree rhs;
3091
3092               stack_save_gsi = gsi_for_stmt (stack_save);
3093               rhs = build_int_cst (TREE_TYPE (gimple_call_arg (call, 0)), 0);
3094               replace_call_with_value (&stack_save_gsi, rhs);
3095             }
3096         }
3097     }
3098
3099   /* No effect, so the statement will be deleted.  */
3100   return integer_zero_node;
3101 }
3102
3103 /* If va_list type is a simple pointer and nothing special is needed,
3104    optimize __builtin_va_start (&ap, 0) into ap = __builtin_next_arg (0),
3105    __builtin_va_end (&ap) out as NOP and __builtin_va_copy into a simple
3106    pointer assignment.  */
3107
3108 static tree
3109 optimize_stdarg_builtin (gimple *call)
3110 {
3111   tree callee, lhs, rhs, cfun_va_list;
3112   bool va_list_simple_ptr;
3113   location_t loc = gimple_location (call);
3114
3115   callee = gimple_call_fndecl (call);
3116
3117   cfun_va_list = targetm.fn_abi_va_list (callee);
3118   va_list_simple_ptr = POINTER_TYPE_P (cfun_va_list)
3119                        && (TREE_TYPE (cfun_va_list) == void_type_node
3120                            || TREE_TYPE (cfun_va_list) == char_type_node);
3121
3122   switch (DECL_FUNCTION_CODE (callee))
3123     {
3124     case BUILT_IN_VA_START:
3125       if (!va_list_simple_ptr
3126           || targetm.expand_builtin_va_start != NULL
3127           || !builtin_decl_explicit_p (BUILT_IN_NEXT_ARG))
3128         return NULL_TREE;
3129
3130       if (gimple_call_num_args (call) != 2)
3131         return NULL_TREE;
3132
3133       lhs = gimple_call_arg (call, 0);
3134       if (!POINTER_TYPE_P (TREE_TYPE (lhs))
3135           || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs)))
3136              != TYPE_MAIN_VARIANT (cfun_va_list))
3137         return NULL_TREE;
3138
3139       lhs = build_fold_indirect_ref_loc (loc, lhs);
3140       rhs = build_call_expr_loc (loc, builtin_decl_explicit (BUILT_IN_NEXT_ARG),
3141                              1, integer_zero_node);
3142       rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
3143       return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
3144
3145     case BUILT_IN_VA_COPY:
3146       if (!va_list_simple_ptr)
3147         return NULL_TREE;
3148
3149       if (gimple_call_num_args (call) != 2)
3150         return NULL_TREE;
3151
3152       lhs = gimple_call_arg (call, 0);
3153       if (!POINTER_TYPE_P (TREE_TYPE (lhs))
3154           || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs)))
3155              != TYPE_MAIN_VARIANT (cfun_va_list))
3156         return NULL_TREE;
3157
3158       lhs = build_fold_indirect_ref_loc (loc, lhs);
3159       rhs = gimple_call_arg (call, 1);
3160       if (TYPE_MAIN_VARIANT (TREE_TYPE (rhs))
3161           != TYPE_MAIN_VARIANT (cfun_va_list))
3162         return NULL_TREE;
3163
3164       rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
3165       return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
3166
3167     case BUILT_IN_VA_END:
3168       /* No effect, so the statement will be deleted.  */
3169       return integer_zero_node;
3170
3171     default:
3172       gcc_unreachable ();
3173     }
3174 }
3175
3176 /* Attemp to make the block of __builtin_unreachable I unreachable by changing
3177    the incoming jumps.  Return true if at least one jump was changed.  */
3178
3179 static bool
3180 optimize_unreachable (gimple_stmt_iterator i)
3181 {
3182   basic_block bb = gsi_bb (i);
3183   gimple_stmt_iterator gsi;
3184   gimple *stmt;
3185   edge_iterator ei;
3186   edge e;
3187   bool ret;
3188
3189   if (flag_sanitize & SANITIZE_UNREACHABLE)
3190     return false;
3191
3192   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3193     {
3194       stmt = gsi_stmt (gsi);
3195
3196       if (is_gimple_debug (stmt))
3197        continue;
3198
3199       if (glabel *label_stmt = dyn_cast <glabel *> (stmt))
3200         {
3201           /* Verify we do not need to preserve the label.  */
3202           if (FORCED_LABEL (gimple_label_label (label_stmt)))
3203             return false;
3204
3205           continue;
3206         }
3207
3208       /* Only handle the case that __builtin_unreachable is the first statement
3209          in the block.  We rely on DCE to remove stmts without side-effects
3210          before __builtin_unreachable.  */
3211       if (gsi_stmt (gsi) != gsi_stmt (i))
3212         return false;
3213     }
3214
3215   ret = false;
3216   FOR_EACH_EDGE (e, ei, bb->preds)
3217     {
3218       gsi = gsi_last_bb (e->src);
3219       if (gsi_end_p (gsi))
3220         continue;
3221
3222       stmt = gsi_stmt (gsi);
3223       if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
3224         {
3225           if (e->flags & EDGE_TRUE_VALUE)
3226             gimple_cond_make_false (cond_stmt);
3227           else if (e->flags & EDGE_FALSE_VALUE)
3228             gimple_cond_make_true (cond_stmt);
3229           else
3230             gcc_unreachable ();
3231           update_stmt (cond_stmt);
3232         }
3233       else
3234         {
3235           /* Todo: handle other cases.  Note that unreachable switch case
3236              statements have already been removed.  */
3237           continue;
3238         }
3239
3240       ret = true;
3241     }
3242
3243   return ret;
3244 }
3245
3246 /* Optimize
3247      mask_2 = 1 << cnt_1;
3248      _4 = __atomic_fetch_or_* (ptr_6, mask_2, _3);
3249      _5 = _4 & mask_2;
3250    to
3251      _4 = ATOMIC_BIT_TEST_AND_SET (ptr_6, cnt_1, 0, _3);
3252      _5 = _4;
3253    If _5 is only used in _5 != 0 or _5 == 0 comparisons, 1
3254    is passed instead of 0, and the builtin just returns a zero
3255    or 1 value instead of the actual bit.
3256    Similarly for __sync_fetch_and_or_* (without the ", _3" part
3257    in there), and/or if mask_2 is a power of 2 constant.
3258    Similarly for xor instead of or, use ATOMIC_BIT_TEST_AND_COMPLEMENT
3259    in that case.  And similarly for and instead of or, except that
3260    the second argument to the builtin needs to be one's complement
3261    of the mask instead of mask.  */
3262
3263 static void
3264 optimize_atomic_bit_test_and (gimple_stmt_iterator *gsip,
3265                               enum internal_fn fn, bool has_model_arg,
3266                               bool after)
3267 {
3268   gimple *call = gsi_stmt (*gsip);
3269   tree lhs = gimple_call_lhs (call);
3270   use_operand_p use_p;
3271   gimple *use_stmt;
3272   tree mask, bit;
3273   optab optab;
3274
3275   if (!flag_inline_atomics
3276       || optimize_debug
3277       || !gimple_call_builtin_p (call, BUILT_IN_NORMAL)
3278       || !lhs
3279       || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)
3280       || !single_imm_use (lhs, &use_p, &use_stmt)
3281       || !is_gimple_assign (use_stmt)
3282       || gimple_assign_rhs_code (use_stmt) != BIT_AND_EXPR
3283       || !gimple_vdef (call))
3284     return;
3285
3286   switch (fn)
3287     {
3288     case IFN_ATOMIC_BIT_TEST_AND_SET:
3289       optab = atomic_bit_test_and_set_optab;
3290       break;
3291     case IFN_ATOMIC_BIT_TEST_AND_COMPLEMENT:
3292       optab = atomic_bit_test_and_complement_optab;
3293       break;
3294     case IFN_ATOMIC_BIT_TEST_AND_RESET:
3295       optab = atomic_bit_test_and_reset_optab;
3296       break;
3297     default:
3298       return;
3299     }
3300
3301   if (optab_handler (optab, TYPE_MODE (TREE_TYPE (lhs))) == CODE_FOR_nothing)
3302     return;
3303
3304   mask = gimple_call_arg (call, 1);
3305   tree use_lhs = gimple_assign_lhs (use_stmt);
3306   if (!use_lhs)
3307     return;
3308
3309   if (TREE_CODE (mask) == INTEGER_CST)
3310     {
3311       if (fn == IFN_ATOMIC_BIT_TEST_AND_RESET)
3312         mask = const_unop (BIT_NOT_EXPR, TREE_TYPE (mask), mask);
3313       mask = fold_convert (TREE_TYPE (lhs), mask);
3314       int ibit = tree_log2 (mask);
3315       if (ibit < 0)
3316         return;
3317       bit = build_int_cst (TREE_TYPE (lhs), ibit);
3318     }
3319   else if (TREE_CODE (mask) == SSA_NAME)
3320     {
3321       gimple *g = SSA_NAME_DEF_STMT (mask);
3322       if (fn == IFN_ATOMIC_BIT_TEST_AND_RESET)
3323         {
3324           if (!is_gimple_assign (g)
3325               || gimple_assign_rhs_code (g) != BIT_NOT_EXPR)
3326             return;
3327           mask = gimple_assign_rhs1 (g);
3328           if (TREE_CODE (mask) != SSA_NAME)
3329             return;
3330           g = SSA_NAME_DEF_STMT (mask);
3331         }
3332       if (!is_gimple_assign (g)
3333           || gimple_assign_rhs_code (g) != LSHIFT_EXPR
3334           || !integer_onep (gimple_assign_rhs1 (g)))
3335         return;
3336       bit = gimple_assign_rhs2 (g);
3337     }
3338   else
3339     return;
3340
3341   if (gimple_assign_rhs1 (use_stmt) == lhs)
3342     {
3343       if (!operand_equal_p (gimple_assign_rhs2 (use_stmt), mask, 0))
3344         return;
3345     }
3346   else if (gimple_assign_rhs2 (use_stmt) != lhs
3347            || !operand_equal_p (gimple_assign_rhs1 (use_stmt), mask, 0))
3348     return;
3349
3350   bool use_bool = true;
3351   bool has_debug_uses = false;
3352   imm_use_iterator iter;
3353   gimple *g;
3354
3355   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use_lhs))
3356     use_bool = false;
3357   FOR_EACH_IMM_USE_STMT (g, iter, use_lhs)
3358     {
3359       enum tree_code code = ERROR_MARK;
3360       tree op0 = NULL_TREE, op1 = NULL_TREE;
3361       if (is_gimple_debug (g))
3362         {
3363           has_debug_uses = true;
3364           continue;
3365         }
3366       else if (is_gimple_assign (g))
3367         switch (gimple_assign_rhs_code (g))
3368           {
3369           case COND_EXPR:
3370             op1 = gimple_assign_rhs1 (g);
3371             code = TREE_CODE (op1);
3372             op0 = TREE_OPERAND (op1, 0);
3373             op1 = TREE_OPERAND (op1, 1);
3374             break;
3375           case EQ_EXPR:
3376           case NE_EXPR:
3377             code = gimple_assign_rhs_code (g);
3378             op0 = gimple_assign_rhs1 (g);
3379             op1 = gimple_assign_rhs2 (g);
3380             break;
3381           default:
3382             break;
3383           }
3384       else if (gimple_code (g) == GIMPLE_COND)
3385         {
3386           code = gimple_cond_code (g);
3387           op0 = gimple_cond_lhs (g);
3388           op1 = gimple_cond_rhs (g);
3389         }
3390
3391       if ((code == EQ_EXPR || code == NE_EXPR)
3392           && op0 == use_lhs
3393           && integer_zerop (op1))
3394         {
3395           use_operand_p use_p;
3396           int n = 0;
3397           FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
3398             n++;
3399           if (n == 1)
3400             continue;
3401         }
3402
3403       use_bool = false;
3404       break;
3405     }
3406
3407   tree new_lhs = make_ssa_name (TREE_TYPE (lhs));
3408   tree flag = build_int_cst (TREE_TYPE (lhs), use_bool);
3409   if (has_model_arg)
3410     g = gimple_build_call_internal (fn, 4, gimple_call_arg (call, 0),
3411                                     bit, flag, gimple_call_arg (call, 2));
3412   else
3413     g = gimple_build_call_internal (fn, 3, gimple_call_arg (call, 0),
3414                                     bit, flag);
3415   gimple_call_set_lhs (g, new_lhs);
3416   gimple_set_location (g, gimple_location (call));
3417   gimple_move_vops (g, call);
3418   bool throws = stmt_can_throw_internal (cfun, call);
3419   gimple_call_set_nothrow (as_a <gcall *> (g),
3420                            gimple_call_nothrow_p (as_a <gcall *> (call)));
3421   gimple_stmt_iterator gsi = *gsip;
3422   gsi_insert_after (&gsi, g, GSI_NEW_STMT);
3423   edge e = NULL;
3424   if (throws)
3425     {
3426       maybe_clean_or_replace_eh_stmt (call, g);
3427       if (after || (use_bool && has_debug_uses))
3428         e = find_fallthru_edge (gsi_bb (gsi)->succs);
3429     }
3430   if (after)
3431     {
3432       /* The internal function returns the value of the specified bit
3433          before the atomic operation.  If we are interested in the value
3434          of the specified bit after the atomic operation (makes only sense
3435          for xor, otherwise the bit content is compile time known),
3436          we need to invert the bit.  */
3437       g = gimple_build_assign (make_ssa_name (TREE_TYPE (lhs)),
3438                                BIT_XOR_EXPR, new_lhs,
3439                                use_bool ? build_int_cst (TREE_TYPE (lhs), 1)
3440                                         : mask);
3441       new_lhs = gimple_assign_lhs (g);
3442       if (throws)
3443         {
3444           gsi_insert_on_edge_immediate (e, g);
3445           gsi = gsi_for_stmt (g);
3446         }
3447       else
3448         gsi_insert_after (&gsi, g, GSI_NEW_STMT);
3449     }
3450   if (use_bool && has_debug_uses)
3451     {
3452       tree temp = NULL_TREE;
3453       if (!throws || after || single_pred_p (e->dest))
3454         {
3455           temp = make_node (DEBUG_EXPR_DECL);
3456           DECL_ARTIFICIAL (temp) = 1;
3457           TREE_TYPE (temp) = TREE_TYPE (lhs);
3458           SET_DECL_MODE (temp, TYPE_MODE (TREE_TYPE (lhs)));
3459           tree t = build2 (LSHIFT_EXPR, TREE_TYPE (lhs), new_lhs, bit);
3460           g = gimple_build_debug_bind (temp, t, g);
3461           if (throws && !after)
3462             {
3463               gsi = gsi_after_labels (e->dest);
3464               gsi_insert_before (&gsi, g, GSI_SAME_STMT);
3465             }
3466           else
3467             gsi_insert_after (&gsi, g, GSI_NEW_STMT);
3468         }
3469       FOR_EACH_IMM_USE_STMT (g, iter, use_lhs)
3470         if (is_gimple_debug (g))
3471           {
3472             use_operand_p use_p;
3473             if (temp == NULL_TREE)
3474               gimple_debug_bind_reset_value (g);
3475             else
3476               FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
3477                 SET_USE (use_p, temp);
3478             update_stmt (g);
3479           }
3480     }
3481   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_lhs)
3482     = SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use_lhs);
3483   replace_uses_by (use_lhs, new_lhs);
3484   gsi = gsi_for_stmt (use_stmt);
3485   gsi_remove (&gsi, true);
3486   release_defs (use_stmt);
3487   gsi_remove (gsip, true);
3488   release_ssa_name (lhs);
3489 }
3490
3491 /* Optimize
3492    a = {};
3493    b = a;
3494    into
3495    a = {};
3496    b = {};
3497    Similarly for memset (&a, ..., sizeof (a)); instead of a = {};
3498    and/or memcpy (&b, &a, sizeof (a)); instead of b = a;  */
3499
3500 static void
3501 optimize_memcpy (gimple_stmt_iterator *gsip, tree dest, tree src, tree len)
3502 {
3503   gimple *stmt = gsi_stmt (*gsip);
3504   if (gimple_has_volatile_ops (stmt))
3505     return;
3506
3507   tree vuse = gimple_vuse (stmt);
3508   if (vuse == NULL)
3509     return;
3510
3511   gimple *defstmt = SSA_NAME_DEF_STMT (vuse);
3512   tree src2 = NULL_TREE, len2 = NULL_TREE;
3513   poly_int64 offset, offset2;
3514   tree val = integer_zero_node;
3515   if (gimple_store_p (defstmt)
3516       && gimple_assign_single_p (defstmt)
3517       && TREE_CODE (gimple_assign_rhs1 (defstmt)) == CONSTRUCTOR
3518       && !gimple_clobber_p (defstmt))
3519     src2 = gimple_assign_lhs (defstmt);
3520   else if (gimple_call_builtin_p (defstmt, BUILT_IN_MEMSET)
3521            && TREE_CODE (gimple_call_arg (defstmt, 0)) == ADDR_EXPR
3522            && TREE_CODE (gimple_call_arg (defstmt, 1)) == INTEGER_CST)
3523     {
3524       src2 = TREE_OPERAND (gimple_call_arg (defstmt, 0), 0);
3525       len2 = gimple_call_arg (defstmt, 2);
3526       val = gimple_call_arg (defstmt, 1);
3527       /* For non-0 val, we'd have to transform stmt from assignment
3528          into memset (only if dest is addressable).  */
3529       if (!integer_zerop (val) && is_gimple_assign (stmt))
3530         src2 = NULL_TREE;
3531     }
3532
3533   if (src2 == NULL_TREE)
3534     return;
3535
3536   if (len == NULL_TREE)
3537     len = (TREE_CODE (src) == COMPONENT_REF
3538            ? DECL_SIZE_UNIT (TREE_OPERAND (src, 1))
3539            : TYPE_SIZE_UNIT (TREE_TYPE (src)));
3540   if (len2 == NULL_TREE)
3541     len2 = (TREE_CODE (src2) == COMPONENT_REF
3542             ? DECL_SIZE_UNIT (TREE_OPERAND (src2, 1))
3543             : TYPE_SIZE_UNIT (TREE_TYPE (src2)));
3544   if (len == NULL_TREE
3545       || !poly_int_tree_p (len)
3546       || len2 == NULL_TREE
3547       || !poly_int_tree_p (len2))
3548     return;
3549
3550   src = get_addr_base_and_unit_offset (src, &offset);
3551   src2 = get_addr_base_and_unit_offset (src2, &offset2);
3552   if (src == NULL_TREE
3553       || src2 == NULL_TREE
3554       || maybe_lt (offset, offset2))
3555     return;
3556
3557   if (!operand_equal_p (src, src2, 0))
3558     return;
3559
3560   /* [ src + offset2, src + offset2 + len2 - 1 ] is set to val.
3561      Make sure that
3562      [ src + offset, src + offset + len - 1 ] is a subset of that.  */
3563   if (maybe_gt (wi::to_poly_offset (len) + (offset - offset2),
3564                 wi::to_poly_offset (len2)))
3565     return;
3566
3567   if (dump_file && (dump_flags & TDF_DETAILS))
3568     {
3569       fprintf (dump_file, "Simplified\n  ");
3570       print_gimple_stmt (dump_file, stmt, 0, dump_flags);
3571       fprintf (dump_file, "after previous\n  ");
3572       print_gimple_stmt (dump_file, defstmt, 0, dump_flags);
3573     }
3574
3575   /* For simplicity, don't change the kind of the stmt,
3576      turn dest = src; into dest = {}; and memcpy (&dest, &src, len);
3577      into memset (&dest, val, len);
3578      In theory we could change dest = src into memset if dest
3579      is addressable (maybe beneficial if val is not 0), or
3580      memcpy (&dest, &src, len) into dest = {} if len is the size
3581      of dest, dest isn't volatile.  */
3582   if (is_gimple_assign (stmt))
3583     {
3584       tree ctor = build_constructor (TREE_TYPE (dest), NULL);
3585       gimple_assign_set_rhs_from_tree (gsip, ctor);
3586       update_stmt (stmt);
3587     }
3588   else /* If stmt is memcpy, transform it into memset.  */
3589     {
3590       gcall *call = as_a <gcall *> (stmt);
3591       tree fndecl = builtin_decl_implicit (BUILT_IN_MEMSET);
3592       gimple_call_set_fndecl (call, fndecl);
3593       gimple_call_set_fntype (call, TREE_TYPE (fndecl));
3594       gimple_call_set_arg (call, 1, val);
3595       update_stmt (stmt);
3596     }
3597
3598   if (dump_file && (dump_flags & TDF_DETAILS))
3599     {
3600       fprintf (dump_file, "into\n  ");
3601       print_gimple_stmt (dump_file, stmt, 0, dump_flags);
3602     }
3603 }
3604
3605 /* A simple pass that attempts to fold all builtin functions.  This pass
3606    is run after we've propagated as many constants as we can.  */
3607
3608 namespace {
3609
3610 const pass_data pass_data_fold_builtins =
3611 {
3612   GIMPLE_PASS, /* type */
3613   "fab", /* name */
3614   OPTGROUP_NONE, /* optinfo_flags */
3615   TV_NONE, /* tv_id */
3616   ( PROP_cfg | PROP_ssa ), /* properties_required */
3617   0, /* properties_provided */
3618   0, /* properties_destroyed */
3619   0, /* todo_flags_start */
3620   TODO_update_ssa, /* todo_flags_finish */
3621 };
3622
3623 class pass_fold_builtins : public gimple_opt_pass
3624 {
3625 public:
3626   pass_fold_builtins (gcc::context *ctxt)
3627     : gimple_opt_pass (pass_data_fold_builtins, ctxt)
3628   {}
3629
3630   /* opt_pass methods: */
3631   opt_pass * clone () { return new pass_fold_builtins (m_ctxt); }
3632   virtual unsigned int execute (function *);
3633
3634 }; // class pass_fold_builtins
3635
3636 unsigned int
3637 pass_fold_builtins::execute (function *fun)
3638 {
3639   bool cfg_changed = false;
3640   basic_block bb;
3641   unsigned int todoflags = 0;
3642
3643   FOR_EACH_BB_FN (bb, fun)
3644     {
3645       gimple_stmt_iterator i;
3646       for (i = gsi_start_bb (bb); !gsi_end_p (i); )
3647         {
3648           gimple *stmt, *old_stmt;
3649           tree callee;
3650           enum built_in_function fcode;
3651
3652           stmt = gsi_stmt (i);
3653
3654           if (gimple_code (stmt) != GIMPLE_CALL)
3655             {
3656               /* Remove all *ssaname_N ={v} {CLOBBER}; stmts,
3657                  after the last GIMPLE DSE they aren't needed and might
3658                  unnecessarily keep the SSA_NAMEs live.  */
3659               if (gimple_clobber_p (stmt))
3660                 {
3661                   tree lhs = gimple_assign_lhs (stmt);
3662                   if (TREE_CODE (lhs) == MEM_REF
3663                       && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME)
3664                     {
3665                       unlink_stmt_vdef (stmt);
3666                       gsi_remove (&i, true);
3667                       release_defs (stmt);
3668                       continue;
3669                     }
3670                 }
3671               else if (gimple_assign_load_p (stmt) && gimple_store_p (stmt))
3672                 optimize_memcpy (&i, gimple_assign_lhs (stmt),
3673                                  gimple_assign_rhs1 (stmt), NULL_TREE);
3674               gsi_next (&i);
3675               continue;
3676             }
3677
3678           callee = gimple_call_fndecl (stmt);
3679           if (!callee || !fndecl_built_in_p (callee, BUILT_IN_NORMAL))
3680             {
3681               gsi_next (&i);
3682               continue;
3683             }
3684
3685           fcode = DECL_FUNCTION_CODE (callee);
3686           if (fold_stmt (&i))
3687             ;
3688           else
3689             {
3690               tree result = NULL_TREE;
3691               switch (DECL_FUNCTION_CODE (callee))
3692                 {
3693                 case BUILT_IN_CONSTANT_P:
3694                   /* Resolve __builtin_constant_p.  If it hasn't been
3695                      folded to integer_one_node by now, it's fairly
3696                      certain that the value simply isn't constant.  */
3697                   result = integer_zero_node;
3698                   break;
3699
3700                 case BUILT_IN_ASSUME_ALIGNED:
3701                   /* Remove __builtin_assume_aligned.  */
3702                   result = gimple_call_arg (stmt, 0);
3703                   break;
3704
3705                 case BUILT_IN_STACK_RESTORE:
3706                   result = optimize_stack_restore (i);
3707                   if (result)
3708                     break;
3709                   gsi_next (&i);
3710                   continue;
3711
3712                 case BUILT_IN_UNREACHABLE:
3713                   if (optimize_unreachable (i))
3714                     cfg_changed = true;
3715                   break;
3716
3717                 case BUILT_IN_ATOMIC_FETCH_OR_1:
3718                 case BUILT_IN_ATOMIC_FETCH_OR_2:
3719                 case BUILT_IN_ATOMIC_FETCH_OR_4:
3720                 case BUILT_IN_ATOMIC_FETCH_OR_8:
3721                 case BUILT_IN_ATOMIC_FETCH_OR_16:
3722                   optimize_atomic_bit_test_and (&i,
3723                                                 IFN_ATOMIC_BIT_TEST_AND_SET,
3724                                                 true, false);
3725                   break;
3726                 case BUILT_IN_SYNC_FETCH_AND_OR_1:
3727                 case BUILT_IN_SYNC_FETCH_AND_OR_2:
3728                 case BUILT_IN_SYNC_FETCH_AND_OR_4:
3729                 case BUILT_IN_SYNC_FETCH_AND_OR_8:
3730                 case BUILT_IN_SYNC_FETCH_AND_OR_16:
3731                   optimize_atomic_bit_test_and (&i,
3732                                                 IFN_ATOMIC_BIT_TEST_AND_SET,
3733                                                 false, false);
3734                   break;
3735
3736                 case BUILT_IN_ATOMIC_FETCH_XOR_1:
3737                 case BUILT_IN_ATOMIC_FETCH_XOR_2:
3738                 case BUILT_IN_ATOMIC_FETCH_XOR_4:
3739                 case BUILT_IN_ATOMIC_FETCH_XOR_8:
3740                 case BUILT_IN_ATOMIC_FETCH_XOR_16:
3741                   optimize_atomic_bit_test_and
3742                         (&i, IFN_ATOMIC_BIT_TEST_AND_COMPLEMENT, true, false);
3743                   break;
3744                 case BUILT_IN_SYNC_FETCH_AND_XOR_1:
3745                 case BUILT_IN_SYNC_FETCH_AND_XOR_2:
3746                 case BUILT_IN_SYNC_FETCH_AND_XOR_4:
3747                 case BUILT_IN_SYNC_FETCH_AND_XOR_8:
3748                 case BUILT_IN_SYNC_FETCH_AND_XOR_16:
3749                   optimize_atomic_bit_test_and
3750                         (&i, IFN_ATOMIC_BIT_TEST_AND_COMPLEMENT, false, false);
3751                   break;
3752
3753                 case BUILT_IN_ATOMIC_XOR_FETCH_1:
3754                 case BUILT_IN_ATOMIC_XOR_FETCH_2:
3755                 case BUILT_IN_ATOMIC_XOR_FETCH_4:
3756                 case BUILT_IN_ATOMIC_XOR_FETCH_8:
3757                 case BUILT_IN_ATOMIC_XOR_FETCH_16:
3758                   optimize_atomic_bit_test_and
3759                         (&i, IFN_ATOMIC_BIT_TEST_AND_COMPLEMENT, true, true);
3760                   break;
3761                 case BUILT_IN_SYNC_XOR_AND_FETCH_1:
3762                 case BUILT_IN_SYNC_XOR_AND_FETCH_2:
3763                 case BUILT_IN_SYNC_XOR_AND_FETCH_4:
3764                 case BUILT_IN_SYNC_XOR_AND_FETCH_8:
3765                 case BUILT_IN_SYNC_XOR_AND_FETCH_16:
3766                   optimize_atomic_bit_test_and
3767                         (&i, IFN_ATOMIC_BIT_TEST_AND_COMPLEMENT, false, true);
3768                   break;
3769
3770                 case BUILT_IN_ATOMIC_FETCH_AND_1:
3771                 case BUILT_IN_ATOMIC_FETCH_AND_2:
3772                 case BUILT_IN_ATOMIC_FETCH_AND_4:
3773                 case BUILT_IN_ATOMIC_FETCH_AND_8:
3774                 case BUILT_IN_ATOMIC_FETCH_AND_16:
3775                   optimize_atomic_bit_test_and (&i,
3776                                                 IFN_ATOMIC_BIT_TEST_AND_RESET,
3777                                                 true, false);
3778                   break;
3779                 case BUILT_IN_SYNC_FETCH_AND_AND_1:
3780                 case BUILT_IN_SYNC_FETCH_AND_AND_2:
3781                 case BUILT_IN_SYNC_FETCH_AND_AND_4:
3782                 case BUILT_IN_SYNC_FETCH_AND_AND_8:
3783                 case BUILT_IN_SYNC_FETCH_AND_AND_16:
3784                   optimize_atomic_bit_test_and (&i,
3785                                                 IFN_ATOMIC_BIT_TEST_AND_RESET,
3786                                                 false, false);
3787                   break;
3788
3789                 case BUILT_IN_MEMCPY:
3790                   if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)
3791                       && TREE_CODE (gimple_call_arg (stmt, 0)) == ADDR_EXPR
3792                       && TREE_CODE (gimple_call_arg (stmt, 1)) == ADDR_EXPR
3793                       && TREE_CODE (gimple_call_arg (stmt, 2)) == INTEGER_CST)
3794                     {
3795                       tree dest = TREE_OPERAND (gimple_call_arg (stmt, 0), 0);
3796                       tree src = TREE_OPERAND (gimple_call_arg (stmt, 1), 0);
3797                       tree len = gimple_call_arg (stmt, 2);
3798                       optimize_memcpy (&i, dest, src, len);
3799                     }
3800                   break;
3801
3802                 case BUILT_IN_VA_START:
3803                 case BUILT_IN_VA_END:
3804                 case BUILT_IN_VA_COPY:
3805                   /* These shouldn't be folded before pass_stdarg.  */
3806                   result = optimize_stdarg_builtin (stmt);
3807                   break;
3808
3809                 default:;
3810                 }
3811
3812               if (!result)
3813                 {
3814                   gsi_next (&i);
3815                   continue;
3816                 }
3817
3818               gimplify_and_update_call_from_tree (&i, result);
3819             }
3820
3821           todoflags |= TODO_update_address_taken;
3822
3823           if (dump_file && (dump_flags & TDF_DETAILS))
3824             {
3825               fprintf (dump_file, "Simplified\n  ");
3826               print_gimple_stmt (dump_file, stmt, 0, dump_flags);
3827             }
3828
3829           old_stmt = stmt;
3830           stmt = gsi_stmt (i);
3831           update_stmt (stmt);
3832
3833           if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)
3834               && gimple_purge_dead_eh_edges (bb))
3835             cfg_changed = true;
3836
3837           if (dump_file && (dump_flags & TDF_DETAILS))
3838             {
3839               fprintf (dump_file, "to\n  ");
3840               print_gimple_stmt (dump_file, stmt, 0, dump_flags);
3841               fprintf (dump_file, "\n");
3842             }
3843
3844           /* Retry the same statement if it changed into another
3845              builtin, there might be new opportunities now.  */
3846           if (gimple_code (stmt) != GIMPLE_CALL)
3847             {
3848               gsi_next (&i);
3849               continue;
3850             }
3851           callee = gimple_call_fndecl (stmt);
3852           if (!callee
3853               || !fndecl_built_in_p (callee, fcode))
3854             gsi_next (&i);
3855         }
3856     }
3857
3858   /* Delete unreachable blocks.  */
3859   if (cfg_changed)
3860     todoflags |= TODO_cleanup_cfg;
3861
3862   return todoflags;
3863 }
3864
3865 } // anon namespace
3866
3867 gimple_opt_pass *
3868 make_pass_fold_builtins (gcc::context *ctxt)
3869 {
3870   return new pass_fold_builtins (ctxt);
3871 }
3872
3873 /* A simple pass that emits some warnings post IPA.  */
3874
3875 namespace {
3876
3877 const pass_data pass_data_post_ipa_warn =
3878 {
3879   GIMPLE_PASS, /* type */
3880   "post_ipa_warn", /* name */
3881   OPTGROUP_NONE, /* optinfo_flags */
3882   TV_NONE, /* tv_id */
3883   ( PROP_cfg | PROP_ssa ), /* properties_required */
3884   0, /* properties_provided */
3885   0, /* properties_destroyed */
3886   0, /* todo_flags_start */
3887   0, /* todo_flags_finish */
3888 };
3889
3890 class pass_post_ipa_warn : public gimple_opt_pass
3891 {
3892 public:
3893   pass_post_ipa_warn (gcc::context *ctxt)
3894     : gimple_opt_pass (pass_data_post_ipa_warn, ctxt)
3895   {}
3896
3897   /* opt_pass methods: */
3898   opt_pass * clone () { return new pass_post_ipa_warn (m_ctxt); }
3899   virtual bool gate (function *) { return warn_nonnull != 0; }
3900   virtual unsigned int execute (function *);
3901
3902 }; // class pass_fold_builtins
3903
3904 unsigned int
3905 pass_post_ipa_warn::execute (function *fun)
3906 {
3907   basic_block bb;
3908
3909   FOR_EACH_BB_FN (bb, fun)
3910     {
3911       gimple_stmt_iterator gsi;
3912       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3913         {
3914           gimple *stmt = gsi_stmt (gsi);
3915           if (!is_gimple_call (stmt) || warning_suppressed_p (stmt, OPT_Wnonnull))
3916             continue;
3917
3918           tree fntype = gimple_call_fntype (stmt);
3919           bitmap nonnullargs = get_nonnull_args (fntype);
3920           if (!nonnullargs)
3921             continue;
3922
3923           tree fndecl = gimple_call_fndecl (stmt);
3924           const bool closure = fndecl && DECL_LAMBDA_FUNCTION_P (fndecl);
3925
3926           for (unsigned i = 0; i < gimple_call_num_args (stmt); i++)
3927             {
3928               tree arg = gimple_call_arg (stmt, i);
3929               if (TREE_CODE (TREE_TYPE (arg)) != POINTER_TYPE)
3930                 continue;
3931               if (!integer_zerop (arg))
3932                 continue;
3933               if (i == 0 && closure)
3934                 /* Avoid warning for the first argument to lambda functions.  */
3935                 continue;
3936               if (!bitmap_empty_p (nonnullargs)
3937                   && !bitmap_bit_p (nonnullargs, i))
3938                 continue;
3939
3940               /* In C++ non-static member functions argument 0 refers
3941                  to the implicit this pointer.  Use the same one-based
3942                  numbering for ordinary arguments.  */
3943               unsigned argno = TREE_CODE (fntype) == METHOD_TYPE ? i : i + 1;
3944               location_t loc = (EXPR_HAS_LOCATION (arg)
3945                                 ? EXPR_LOCATION (arg)
3946                                 : gimple_location (stmt));
3947               auto_diagnostic_group d;
3948               if (argno == 0)
3949                 {
3950                   if (warning_at (loc, OPT_Wnonnull,
3951                                   "%qs pointer is null", "this")
3952                       && fndecl)
3953                     inform (DECL_SOURCE_LOCATION (fndecl),
3954                             "in a call to non-static member function %qD",
3955                             fndecl);
3956                   continue;
3957                 }
3958
3959               if (!warning_at (loc, OPT_Wnonnull,
3960                                "argument %u null where non-null "
3961                                "expected", argno))
3962                 continue;
3963
3964               tree fndecl = gimple_call_fndecl (stmt);
3965               if (fndecl && DECL_IS_UNDECLARED_BUILTIN (fndecl))
3966                 inform (loc, "in a call to built-in function %qD",
3967                         fndecl);
3968               else if (fndecl)
3969                 inform (DECL_SOURCE_LOCATION (fndecl),
3970                         "in a call to function %qD declared %qs",
3971                         fndecl, "nonnull");
3972             }
3973           BITMAP_FREE (nonnullargs);
3974         }
3975     }
3976   return 0;
3977 }
3978
3979 } // anon namespace
3980
3981 gimple_opt_pass *
3982 make_pass_post_ipa_warn (gcc::context *ctxt)
3983 {
3984   return new pass_post_ipa_warn (ctxt);
3985 }