gcc/tree-ssa-ccp.cc

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