gcc/gimple-fold.c

   1 /* Statement simplification on GIMPLE.
   2    Copyright (C) 2010 Free Software Foundation, Inc.
   3    Split out from tree-ssa-ccp.c.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by the
   9 Free Software Foundation; either version 3, or (at your option) any
  10 later version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT
  13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "flags.h"
  27 #include "function.h"
  28 #include "tree-dump.h"
  29 #include "tree-flow.h"
  30 #include "tree-pass.h"
  31 #include "tree-ssa-propagate.h"
  32 #include "target.h"
  33
  34 /* CVAL is value taken from DECL_INITIAL of variable.  Try to transorm it into
  35    acceptable form for is_gimple_min_invariant.   */
  36
  37 tree
  38 canonicalize_constructor_val (tree cval)
  39 {
  40   STRIP_NOPS (cval);
  41   if (TREE_CODE (cval) == POINTER_PLUS_EXPR)
  42     {
  43       tree t = maybe_fold_offset_to_address (EXPR_LOCATION (cval),
  44                                              TREE_OPERAND (cval, 0),
  45                                              TREE_OPERAND (cval, 1),
  46                                              TREE_TYPE (cval));
  47       if (t)
  48         cval = t;
  49     }
  50   if (TREE_CODE (cval) == ADDR_EXPR)
  51     {
  52       tree base = get_base_address (TREE_OPERAND (cval, 0));
  53       if (base && TREE_CODE (base) == VAR_DECL)
  54         add_referenced_var (base);
  55     }
  56   return cval;
  57 }
  58
  59 /* If SYM is a constant variable with known value, return the value.
  60    NULL_TREE is returned otherwise.  */
  61
  62 tree
  63 get_symbol_constant_value (tree sym)
  64 {
  65   if ((TREE_STATIC (sym) || DECL_EXTERNAL (sym))
  66       && (TREE_CODE (sym) == CONST_DECL
  67           || varpool_get_node (sym)->const_value_known))
  68     {
  69       tree val = DECL_INITIAL (sym);
  70       if (val)
  71         {
  72           val = canonicalize_constructor_val (val);
  73           if (is_gimple_min_invariant (val))
  74             return val;
  75         }
  76       /* Variables declared 'const' without an initializer
  77          have zero as the initializer if they may not be
  78          overridden at link or run time.  */
  79       if (!val
  80           && (INTEGRAL_TYPE_P (TREE_TYPE (sym))
  81                || SCALAR_FLOAT_TYPE_P (TREE_TYPE (sym))))
  82         return fold_convert (TREE_TYPE (sym), integer_zero_node);
  83     }
  84
  85   return NULL_TREE;
  86 }
  87
  88
  89 /* Return true if we may propagate the address expression ADDR into the
  90    dereference DEREF and cancel them.  */
  91
  92 bool
  93 may_propagate_address_into_dereference (tree addr, tree deref)
  94 {
  95   gcc_assert (TREE_CODE (deref) == MEM_REF
  96               && TREE_CODE (addr) == ADDR_EXPR);
  97
  98   /* Don't propagate if ADDR's operand has incomplete type.  */
  99   if (!COMPLETE_TYPE_P (TREE_TYPE (TREE_OPERAND (addr, 0))))
 100     return false;
 101
 102   /* If the address is invariant then we do not need to preserve restrict
 103      qualifications.  But we do need to preserve volatile qualifiers until
 104      we can annotate the folded dereference itself properly.  */
 105   if (is_gimple_min_invariant (addr)
 106       && (!TREE_THIS_VOLATILE (deref)
 107           || TYPE_VOLATILE (TREE_TYPE (addr))))
 108     return useless_type_conversion_p (TREE_TYPE (deref),
 109                                       TREE_TYPE (TREE_OPERAND (addr, 0)));
 110
 111   /* Else both the address substitution and the folding must result in
 112      a valid useless type conversion sequence.  */
 113   return (useless_type_conversion_p (TREE_TYPE (TREE_OPERAND (deref, 0)),
 114                                      TREE_TYPE (addr))
 115           && useless_type_conversion_p (TREE_TYPE (deref),
 116                                         TREE_TYPE (TREE_OPERAND (addr, 0))));
 117 }
 118
 119
 120 /* A subroutine of fold_stmt.  Attempts to fold *(A+O) to A[X].
 121    BASE is an array type.  OFFSET is a byte displacement.
 122
 123    LOC is the location of the original expression.  */
 124
 125 static tree
 126 maybe_fold_offset_to_array_ref (location_t loc, tree base, tree offset)
 127 {
 128   tree min_idx, idx, idx_type, elt_offset = integer_zero_node;
 129   tree array_type, elt_type, elt_size;
 130   tree domain_type;
 131
 132   /* If BASE is an ARRAY_REF, we can pick up another offset (this time
 133      measured in units of the size of elements type) from that ARRAY_REF).
 134      We can't do anything if either is variable.
 135
 136      The case we handle here is *(&A[N]+O).  */
 137   if (TREE_CODE (base) == ARRAY_REF)
 138     {
 139       tree low_bound = array_ref_low_bound (base);
 140
 141       elt_offset = TREE_OPERAND (base, 1);
 142       if (TREE_CODE (low_bound) != INTEGER_CST
 143           || TREE_CODE (elt_offset) != INTEGER_CST)
 144         return NULL_TREE;
 145
 146       elt_offset = int_const_binop (MINUS_EXPR, elt_offset, low_bound, 0);
 147       base = TREE_OPERAND (base, 0);
 148     }
 149
 150   /* Ignore stupid user tricks of indexing non-array variables.  */
 151   array_type = TREE_TYPE (base);
 152   if (TREE_CODE (array_type) != ARRAY_TYPE)
 153     return NULL_TREE;
 154   elt_type = TREE_TYPE (array_type);
 155
 156   /* Use signed size type for intermediate computation on the index.  */
 157   idx_type = ssizetype;
 158
 159   /* If OFFSET and ELT_OFFSET are zero, we don't care about the size of the
 160      element type (so we can use the alignment if it's not constant).
 161      Otherwise, compute the offset as an index by using a division.  If the
 162      division isn't exact, then don't do anything.  */
 163   elt_size = TYPE_SIZE_UNIT (elt_type);
 164   if (!elt_size)
 165     return NULL;
 166   if (integer_zerop (offset))
 167     {
 168       if (TREE_CODE (elt_size) != INTEGER_CST)
 169         elt_size = size_int (TYPE_ALIGN (elt_type));
 170
 171       idx = build_int_cst (idx_type, 0);
 172     }
 173   else
 174     {
 175       unsigned HOST_WIDE_INT lquo, lrem;
 176       HOST_WIDE_INT hquo, hrem;
 177       double_int soffset;
 178
 179       /* The final array offset should be signed, so we need
 180          to sign-extend the (possibly pointer) offset here
 181          and use signed division.  */
 182       soffset = double_int_sext (tree_to_double_int (offset),
 183                                  TYPE_PRECISION (TREE_TYPE (offset)));
 184       if (TREE_CODE (elt_size) != INTEGER_CST
 185           || div_and_round_double (TRUNC_DIV_EXPR, 0,
 186                                    soffset.low, soffset.high,
 187                                    TREE_INT_CST_LOW (elt_size),
 188                                    TREE_INT_CST_HIGH (elt_size),
 189                                    &lquo, &hquo, &lrem, &hrem)
 190           || lrem || hrem)
 191         return NULL_TREE;
 192
 193       idx = build_int_cst_wide (idx_type, lquo, hquo);
 194     }
 195
 196   /* Assume the low bound is zero.  If there is a domain type, get the
 197      low bound, if any, convert the index into that type, and add the
 198      low bound.  */
 199   min_idx = build_int_cst (idx_type, 0);
 200   domain_type = TYPE_DOMAIN (array_type);
 201   if (domain_type)
 202     {
 203       idx_type = domain_type;
 204       if (TYPE_MIN_VALUE (idx_type))
 205         min_idx = TYPE_MIN_VALUE (idx_type);
 206       else
 207         min_idx = fold_convert (idx_type, min_idx);
 208
 209       if (TREE_CODE (min_idx) != INTEGER_CST)
 210         return NULL_TREE;
 211
 212       elt_offset = fold_convert (idx_type, elt_offset);
 213     }
 214
 215   if (!integer_zerop (min_idx))
 216     idx = int_const_binop (PLUS_EXPR, idx, min_idx, 0);
 217   if (!integer_zerop (elt_offset))
 218     idx = int_const_binop (PLUS_EXPR, idx, elt_offset, 0);
 219
 220   /* Make sure to possibly truncate late after offsetting.  */
 221   idx = fold_convert (idx_type, idx);
 222
 223   /* We don't want to construct access past array bounds. For example
 224        char *(c[4]);
 225        c[3][2];
 226      should not be simplified into (*c)[14] or tree-vrp will
 227      give false warnings.
 228      This is only an issue for multi-dimensional arrays.  */
 229   if (TREE_CODE (elt_type) == ARRAY_TYPE
 230       && domain_type)
 231     {
 232       if (TYPE_MAX_VALUE (domain_type)
 233           && TREE_CODE (TYPE_MAX_VALUE (domain_type)) == INTEGER_CST
 234           && tree_int_cst_lt (TYPE_MAX_VALUE (domain_type), idx))
 235         return NULL_TREE;
 236       else if (TYPE_MIN_VALUE (domain_type)
 237                && TREE_CODE (TYPE_MIN_VALUE (domain_type)) == INTEGER_CST
 238                && tree_int_cst_lt (idx, TYPE_MIN_VALUE (domain_type)))
 239         return NULL_TREE;
 240       else if (compare_tree_int (idx, 0) < 0)
 241         return NULL_TREE;
 242     }
 243
 244   {
 245     tree t = build4 (ARRAY_REF, elt_type, base, idx, NULL_TREE, NULL_TREE);
 246     SET_EXPR_LOCATION (t, loc);
 247     return t;
 248   }
 249 }
 250
 251
 252 /* Attempt to express (ORIG_TYPE)BASE+OFFSET as BASE[index].
 253    LOC is the location of original expression.
 254
 255    Before attempting the conversion strip off existing ADDR_EXPRs.  */
 256
 257 tree
 258 maybe_fold_offset_to_reference (location_t loc, tree base, tree offset,
 259                                 tree orig_type)
 260 {
 261   tree ret;
 262
 263   STRIP_NOPS (base);
 264   if (TREE_CODE (base) != ADDR_EXPR)
 265     return NULL_TREE;
 266
 267   base = TREE_OPERAND (base, 0);
 268   if (types_compatible_p (orig_type, TREE_TYPE (base))
 269       && integer_zerop (offset))
 270     return base;
 271
 272   ret = maybe_fold_offset_to_array_ref (loc, base, offset);
 273   if (ret && types_compatible_p (orig_type, TREE_TYPE (ret)))
 274     return ret;
 275   return NULL_TREE;
 276 }
 277
 278 /* Attempt to express (ORIG_TYPE)ADDR+OFFSET as (*ADDR)[index].
 279    LOC is the location of the original expression.  */
 280
 281 tree
 282 maybe_fold_offset_to_address (location_t loc, tree addr, tree offset,
 283                               tree orig_type)
 284 {
 285   tree base, ret;
 286
 287   STRIP_NOPS (addr);
 288   if (TREE_CODE (addr) != ADDR_EXPR)
 289     return NULL_TREE;
 290   base = TREE_OPERAND (addr, 0);
 291   ret = maybe_fold_offset_to_array_ref (loc, base, offset);
 292   if (ret)
 293     {
 294       ret = build_fold_addr_expr (ret);
 295       if (!useless_type_conversion_p (orig_type, TREE_TYPE (ret)))
 296         return NULL_TREE;
 297       SET_EXPR_LOCATION (ret, loc);
 298     }
 299
 300   return ret;
 301 }
 302
 303
 304 /* A quaint feature extant in our address arithmetic is that there
 305    can be hidden type changes here.  The type of the result need
 306    not be the same as the type of the input pointer.
 307
 308    What we're after here is an expression of the form
 309         (T *)(&array + const)
 310    where array is OP0, const is OP1, RES_TYPE is T and
 311    the cast doesn't actually exist, but is implicit in the
 312    type of the POINTER_PLUS_EXPR.  We'd like to turn this into
 313         &array[x]
 314    which may be able to propagate further.  */
 315
 316 tree
 317 maybe_fold_stmt_addition (location_t loc, tree res_type, tree op0, tree op1)
 318 {
 319   tree ptd_type;
 320   tree t;
 321
 322   /* The first operand should be an ADDR_EXPR.  */
 323   if (TREE_CODE (op0) != ADDR_EXPR)
 324     return NULL_TREE;
 325   op0 = TREE_OPERAND (op0, 0);
 326
 327   /* It had better be a constant.  */
 328   if (TREE_CODE (op1) != INTEGER_CST)
 329     {
 330       /* Or op0 should now be A[0] and the non-constant offset defined
 331          via a multiplication by the array element size.  */
 332       if (TREE_CODE (op0) == ARRAY_REF
 333           /* As we will end up creating a variable index array access
 334              in the outermost array dimension make sure there isn't
 335              a more inner array that the index could overflow to.  */
 336           && TREE_CODE (TREE_OPERAND (op0, 0)) != ARRAY_REF
 337           && integer_zerop (TREE_OPERAND (op0, 1))
 338           && TREE_CODE (op1) == SSA_NAME)
 339         {
 340           gimple offset_def = SSA_NAME_DEF_STMT (op1);
 341           tree elsz = TYPE_SIZE_UNIT (TREE_TYPE (op0));
 342           if (!host_integerp (elsz, 1)
 343               || !is_gimple_assign (offset_def))
 344             return NULL_TREE;
 345
 346           /* Do not build array references of something that we can't
 347              see the true number of array dimensions for.  */
 348           if (!DECL_P (TREE_OPERAND (op0, 0))
 349               && !handled_component_p (TREE_OPERAND (op0, 0)))
 350             return NULL_TREE;
 351
 352           if (gimple_assign_rhs_code (offset_def) == MULT_EXPR
 353               && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
 354               && tree_int_cst_equal (gimple_assign_rhs2 (offset_def), elsz))
 355             return build_fold_addr_expr
 356                           (build4 (ARRAY_REF, TREE_TYPE (op0),
 357                                    TREE_OPERAND (op0, 0),
 358                                    gimple_assign_rhs1 (offset_def),
 359                                    TREE_OPERAND (op0, 2),
 360                                    TREE_OPERAND (op0, 3)));
 361           else if (integer_onep (elsz)
 362                    && gimple_assign_rhs_code (offset_def) != MULT_EXPR)
 363             return build_fold_addr_expr
 364                           (build4 (ARRAY_REF, TREE_TYPE (op0),
 365                                    TREE_OPERAND (op0, 0),
 366                                    op1,
 367                                    TREE_OPERAND (op0, 2),
 368                                    TREE_OPERAND (op0, 3)));
 369         }
 370       else if (TREE_CODE (TREE_TYPE (op0)) == ARRAY_TYPE
 371                /* Dto.  */
 372                && TREE_CODE (TREE_TYPE (TREE_TYPE (op0))) != ARRAY_TYPE
 373                && TREE_CODE (op1) == SSA_NAME)
 374         {
 375           gimple offset_def = SSA_NAME_DEF_STMT (op1);
 376           tree elsz = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (op0)));
 377           if (!host_integerp (elsz, 1)
 378               || !is_gimple_assign (offset_def))
 379             return NULL_TREE;
 380
 381           /* Do not build array references of something that we can't
 382              see the true number of array dimensions for.  */
 383           if (!DECL_P (op0)
 384               && !handled_component_p (op0))
 385             return NULL_TREE;
 386
 387           if (gimple_assign_rhs_code (offset_def) == MULT_EXPR
 388               && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
 389               && tree_int_cst_equal (gimple_assign_rhs2 (offset_def), elsz))
 390             return build_fold_addr_expr
 391                           (build4 (ARRAY_REF, TREE_TYPE (TREE_TYPE (op0)),
 392                                    op0, gimple_assign_rhs1 (offset_def),
 393                                    integer_zero_node, NULL_TREE));
 394           else if (integer_onep (elsz)
 395                    && gimple_assign_rhs_code (offset_def) != MULT_EXPR)
 396             return build_fold_addr_expr
 397                           (build4 (ARRAY_REF, TREE_TYPE (TREE_TYPE (op0)),
 398                                    op0, op1,
 399                                    integer_zero_node, NULL_TREE));
 400         }
 401
 402       return NULL_TREE;
 403     }
 404
 405   /* If the first operand is an ARRAY_REF, expand it so that we can fold
 406      the offset into it.  */
 407   while (TREE_CODE (op0) == ARRAY_REF)
 408     {
 409       tree array_obj = TREE_OPERAND (op0, 0);
 410       tree array_idx = TREE_OPERAND (op0, 1);
 411       tree elt_type = TREE_TYPE (op0);
 412       tree elt_size = TYPE_SIZE_UNIT (elt_type);
 413       tree min_idx;
 414
 415       if (TREE_CODE (array_idx) != INTEGER_CST)
 416         break;
 417       if (TREE_CODE (elt_size) != INTEGER_CST)
 418         break;
 419
 420       /* Un-bias the index by the min index of the array type.  */
 421       min_idx = TYPE_DOMAIN (TREE_TYPE (array_obj));
 422       if (min_idx)
 423         {
 424           min_idx = TYPE_MIN_VALUE (min_idx);
 425           if (min_idx)
 426             {
 427               if (TREE_CODE (min_idx) != INTEGER_CST)
 428                 break;
 429
 430               array_idx = fold_convert (TREE_TYPE (min_idx), array_idx);
 431               if (!integer_zerop (min_idx))
 432                 array_idx = int_const_binop (MINUS_EXPR, array_idx,
 433                                              min_idx, 0);
 434             }
 435         }
 436
 437       /* Convert the index to a byte offset.  */
 438       array_idx = fold_convert (sizetype, array_idx);
 439       array_idx = int_const_binop (MULT_EXPR, array_idx, elt_size, 0);
 440
 441       /* Update the operands for the next round, or for folding.  */
 442       op1 = int_const_binop (PLUS_EXPR,
 443                              array_idx, op1, 0);
 444       op0 = array_obj;
 445     }
 446
 447   ptd_type = TREE_TYPE (res_type);
 448   /* If we want a pointer to void, reconstruct the reference from the
 449      array element type.  A pointer to that can be trivially converted
 450      to void *.  This happens as we fold (void *)(ptr p+ off).  */
 451   if (VOID_TYPE_P (ptd_type)
 452       && TREE_CODE (TREE_TYPE (op0)) == ARRAY_TYPE)
 453     ptd_type = TREE_TYPE (TREE_TYPE (op0));
 454
 455   /* At which point we can try some of the same things as for indirects.  */
 456   t = maybe_fold_offset_to_array_ref (loc, op0, op1);
 457   if (t)
 458     {
 459       t = build_fold_addr_expr (t);
 460       if (!useless_type_conversion_p (res_type, TREE_TYPE (t)))
 461         return NULL_TREE;
 462       SET_EXPR_LOCATION (t, loc);
 463     }
 464
 465   return t;
 466 }
 467
 468 /* Subroutine of fold_stmt.  We perform several simplifications of the
 469    memory reference tree EXPR and make sure to re-gimplify them properly
 470    after propagation of constant addresses.  IS_LHS is true if the
 471    reference is supposed to be an lvalue.  */
 472
 473 static tree
 474 maybe_fold_reference (tree expr, bool is_lhs)
 475 {
 476   tree *t = &expr;
 477   tree result;
 478
 479   if (!is_lhs
 480       && (result = fold_const_aggregate_ref (expr))
 481       && is_gimple_min_invariant (result))
 482     return result;
 483
 484   /* ???  We might want to open-code the relevant remaining cases
 485      to avoid using the generic fold.  */
 486   if (handled_component_p (*t)
 487       && CONSTANT_CLASS_P (TREE_OPERAND (*t, 0)))
 488     {
 489       tree tem = fold (*t);
 490       if (tem != *t)
 491         return tem;
 492     }
 493
 494   while (handled_component_p (*t))
 495     t = &TREE_OPERAND (*t, 0);
 496
 497   /* Fold back MEM_REFs to reference trees.  */
 498   if (TREE_CODE (*t) == MEM_REF
 499       && TREE_CODE (TREE_OPERAND (*t, 0)) == ADDR_EXPR
 500       && integer_zerop (TREE_OPERAND (*t, 1))
 501       && (TREE_THIS_VOLATILE (*t)
 502           == TREE_THIS_VOLATILE (TREE_OPERAND (TREE_OPERAND (*t, 0), 0)))
 503       && !TYPE_REF_CAN_ALIAS_ALL (TREE_TYPE (TREE_OPERAND (*t, 1)))
 504       && (TYPE_MAIN_VARIANT (TREE_TYPE (*t))
 505           == TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (TREE_OPERAND (*t, 1)))))
 506       /* We have to look out here to not drop a required conversion
 507          from the rhs to the lhs if is_lhs, but we don't have the
 508          rhs here to verify that.  Thus require strict type
 509          compatibility.  */
 510       && types_compatible_p (TREE_TYPE (*t),
 511                              TREE_TYPE (TREE_OPERAND
 512                                           (TREE_OPERAND (*t, 0), 0))))
 513     {
 514       tree tem;
 515       *t = TREE_OPERAND (TREE_OPERAND (*t, 0), 0);
 516       tem = maybe_fold_reference (expr, is_lhs);
 517       if (tem)
 518         return tem;
 519       return expr;
 520     }
 521   /* Canonicalize MEM_REFs invariant address operand.  */
 522   else if (TREE_CODE (*t) == MEM_REF
 523            && TREE_CODE (TREE_OPERAND (*t, 0)) == ADDR_EXPR
 524            && !DECL_P (TREE_OPERAND (TREE_OPERAND (*t, 0), 0))
 525            && !CONSTANT_CLASS_P (TREE_OPERAND (TREE_OPERAND (*t, 0), 0)))
 526     {
 527       tree tem = fold_binary (MEM_REF, TREE_TYPE (*t),
 528                               TREE_OPERAND (*t, 0),
 529                               TREE_OPERAND (*t, 1));
 530       if (tem)
 531         {
 532           *t = tem;
 533           tem = maybe_fold_reference (expr, is_lhs);
 534           if (tem)
 535             return tem;
 536           return expr;
 537         }
 538     }
 539   else if (TREE_CODE (*t) == TARGET_MEM_REF)
 540     {
 541       tree tem = maybe_fold_tmr (*t);
 542       if (tem)
 543         {
 544           *t = tem;
 545           tem = maybe_fold_reference (expr, is_lhs);
 546           if (tem)
 547             return tem;
 548           return expr;
 549         }
 550     }
 551   else if (!is_lhs
 552            && DECL_P (*t))
 553     {
 554       tree tem = get_symbol_constant_value (*t);
 555       if (tem
 556           && useless_type_conversion_p (TREE_TYPE (*t), TREE_TYPE (tem)))
 557         {
 558           *t = unshare_expr (tem);
 559           tem = maybe_fold_reference (expr, is_lhs);
 560           if (tem)
 561             return tem;
 562           return expr;
 563         }
 564     }
 565
 566   return NULL_TREE;
 567 }
 568
 569
 570 /* Attempt to fold an assignment statement pointed-to by SI.  Returns a
 571    replacement rhs for the statement or NULL_TREE if no simplification
 572    could be made.  It is assumed that the operands have been previously
 573    folded.  */
 574
 575 static tree
 576 fold_gimple_assign (gimple_stmt_iterator *si)
 577 {
 578   gimple stmt = gsi_stmt (*si);
 579   enum tree_code subcode = gimple_assign_rhs_code (stmt);
 580   location_t loc = gimple_location (stmt);
 581
 582   tree result = NULL_TREE;
 583
 584   switch (get_gimple_rhs_class (subcode))
 585     {
 586     case GIMPLE_SINGLE_RHS:
 587       {
 588         tree rhs = gimple_assign_rhs1 (stmt);
 589
 590         /* Try to fold a conditional expression.  */
 591         if (TREE_CODE (rhs) == COND_EXPR)
 592           {
 593             tree op0 = COND_EXPR_COND (rhs);
 594             tree tem;
 595             bool set = false;
 596             location_t cond_loc = EXPR_LOCATION (rhs);
 597
 598             if (COMPARISON_CLASS_P (op0))
 599               {
 600                 fold_defer_overflow_warnings ();
 601                 tem = fold_binary_loc (cond_loc,
 602                                    TREE_CODE (op0), TREE_TYPE (op0),
 603                                    TREE_OPERAND (op0, 0),
 604                                    TREE_OPERAND (op0, 1));
 605                 /* This is actually a conditional expression, not a GIMPLE
 606                    conditional statement, however, the valid_gimple_rhs_p
 607                    test still applies.  */
 608                 set = (tem && is_gimple_condexpr (tem)
 609                        && valid_gimple_rhs_p (tem));
 610                 fold_undefer_overflow_warnings (set, stmt, 0);
 611               }
 612             else if (is_gimple_min_invariant (op0))
 613               {
 614                 tem = op0;
 615                 set = true;
 616               }
 617             else
 618               return NULL_TREE;
 619
 620             if (set)
 621               result = fold_build3_loc (cond_loc, COND_EXPR, TREE_TYPE (rhs), tem,
 622                                     COND_EXPR_THEN (rhs), COND_EXPR_ELSE (rhs));
 623           }
 624
 625         else if (REFERENCE_CLASS_P (rhs))
 626           return maybe_fold_reference (rhs, false);
 627
 628         else if (TREE_CODE (rhs) == ADDR_EXPR)
 629           {
 630             tree ref = TREE_OPERAND (rhs, 0);
 631             tree tem = maybe_fold_reference (ref, true);
 632             if (tem
 633                 && TREE_CODE (tem) == MEM_REF
 634                 && integer_zerop (TREE_OPERAND (tem, 1)))
 635               result = fold_convert (TREE_TYPE (rhs), TREE_OPERAND (tem, 0));
 636             else if (tem)
 637               result = fold_convert (TREE_TYPE (rhs),
 638                                      build_fold_addr_expr_loc (loc, tem));
 639             else if (TREE_CODE (ref) == MEM_REF
 640                      && integer_zerop (TREE_OPERAND (ref, 1)))
 641               result = fold_convert (TREE_TYPE (rhs), TREE_OPERAND (ref, 0));
 642           }
 643
 644         else if (TREE_CODE (rhs) == CONSTRUCTOR
 645                  && TREE_CODE (TREE_TYPE (rhs)) == VECTOR_TYPE
 646                  && (CONSTRUCTOR_NELTS (rhs)
 647                      == TYPE_VECTOR_SUBPARTS (TREE_TYPE (rhs))))
 648           {
 649             /* Fold a constant vector CONSTRUCTOR to VECTOR_CST.  */
 650             unsigned i;
 651             tree val;
 652
 653             FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (rhs), i, val)
 654               if (TREE_CODE (val) != INTEGER_CST
 655                   && TREE_CODE (val) != REAL_CST
 656                   && TREE_CODE (val) != FIXED_CST)
 657                 return NULL_TREE;
 658
 659             return build_vector_from_ctor (TREE_TYPE (rhs),
 660                                            CONSTRUCTOR_ELTS (rhs));
 661           }
 662
 663         else if (DECL_P (rhs))
 664           return unshare_expr (get_symbol_constant_value (rhs));
 665
 666         /* If we couldn't fold the RHS, hand over to the generic
 667            fold routines.  */
 668         if (result == NULL_TREE)
 669           result = fold (rhs);
 670
 671         /* Strip away useless type conversions.  Both the NON_LVALUE_EXPR
 672            that may have been added by fold, and "useless" type
 673            conversions that might now be apparent due to propagation.  */
 674         STRIP_USELESS_TYPE_CONVERSION (result);
 675
 676         if (result != rhs && valid_gimple_rhs_p (result))
 677           return result;
 678
 679         return NULL_TREE;
 680       }
 681       break;
 682
 683     case GIMPLE_UNARY_RHS:
 684       {
 685         tree rhs = gimple_assign_rhs1 (stmt);
 686
 687         result = fold_unary_loc (loc, subcode, gimple_expr_type (stmt), rhs);
 688         if (result)
 689           {
 690             /* If the operation was a conversion do _not_ mark a
 691                resulting constant with TREE_OVERFLOW if the original
 692                constant was not.  These conversions have implementation
 693                defined behavior and retaining the TREE_OVERFLOW flag
 694                here would confuse later passes such as VRP.  */
 695             if (CONVERT_EXPR_CODE_P (subcode)
 696                 && TREE_CODE (result) == INTEGER_CST
 697                 && TREE_CODE (rhs) == INTEGER_CST)
 698               TREE_OVERFLOW (result) = TREE_OVERFLOW (rhs);
 699
 700             STRIP_USELESS_TYPE_CONVERSION (result);
 701             if (valid_gimple_rhs_p (result))
 702               return result;
 703           }
 704         else if (CONVERT_EXPR_CODE_P (subcode)
 705                  && POINTER_TYPE_P (gimple_expr_type (stmt))
 706                  && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt))))
 707           {
 708             tree type = gimple_expr_type (stmt);
 709             tree t = maybe_fold_offset_to_address (loc,
 710                                                    gimple_assign_rhs1 (stmt),
 711                                                    integer_zero_node, type);
 712             if (t)
 713               return t;
 714           }
 715       }
 716       break;
 717
 718     case GIMPLE_BINARY_RHS:
 719       /* Try to fold pointer addition.  */
 720       if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
 721         {
 722           tree type = TREE_TYPE (gimple_assign_rhs1 (stmt));
 723           if (TREE_CODE (TREE_TYPE (type)) == ARRAY_TYPE)
 724             {
 725               type = build_pointer_type (TREE_TYPE (TREE_TYPE (type)));
 726               if (!useless_type_conversion_p
 727                     (TREE_TYPE (gimple_assign_lhs (stmt)), type))
 728                 type = TREE_TYPE (gimple_assign_rhs1 (stmt));
 729             }
 730           result = maybe_fold_stmt_addition (gimple_location (stmt),
 731                                              type,
 732                                              gimple_assign_rhs1 (stmt),
 733                                              gimple_assign_rhs2 (stmt));
 734         }
 735
 736       if (!result)
 737         result = fold_binary_loc (loc, subcode,
 738                               TREE_TYPE (gimple_assign_lhs (stmt)),
 739                               gimple_assign_rhs1 (stmt),
 740                               gimple_assign_rhs2 (stmt));
 741
 742       if (result)
 743         {
 744           STRIP_USELESS_TYPE_CONVERSION (result);
 745           if (valid_gimple_rhs_p (result))
 746             return result;
 747
 748           /* Fold might have produced non-GIMPLE, so if we trust it blindly
 749              we lose canonicalization opportunities.  Do not go again
 750              through fold here though, or the same non-GIMPLE will be
 751              produced.  */
 752           if (commutative_tree_code (subcode)
 753               && tree_swap_operands_p (gimple_assign_rhs1 (stmt),
 754                                        gimple_assign_rhs2 (stmt), false))
 755             return build2 (subcode, TREE_TYPE (gimple_assign_lhs (stmt)),
 756                            gimple_assign_rhs2 (stmt),
 757                            gimple_assign_rhs1 (stmt));
 758         }
 759       break;
 760
 761     case GIMPLE_TERNARY_RHS:
 762       result = fold_ternary_loc (loc, subcode,
 763                                  TREE_TYPE (gimple_assign_lhs (stmt)),
 764                                  gimple_assign_rhs1 (stmt),
 765                                  gimple_assign_rhs2 (stmt),
 766                                  gimple_assign_rhs3 (stmt));
 767
 768       if (result)
 769         {
 770           STRIP_USELESS_TYPE_CONVERSION (result);
 771           if (valid_gimple_rhs_p (result))
 772             return result;
 773
 774           /* Fold might have produced non-GIMPLE, so if we trust it blindly
 775              we lose canonicalization opportunities.  Do not go again
 776              through fold here though, or the same non-GIMPLE will be
 777              produced.  */
 778           if (commutative_ternary_tree_code (subcode)
 779               && tree_swap_operands_p (gimple_assign_rhs1 (stmt),
 780                                        gimple_assign_rhs2 (stmt), false))
 781             return build3 (subcode, TREE_TYPE (gimple_assign_lhs (stmt)),
 782                            gimple_assign_rhs2 (stmt),
 783                            gimple_assign_rhs1 (stmt),
 784                            gimple_assign_rhs3 (stmt));
 785         }
 786       break;
 787
 788     case GIMPLE_INVALID_RHS:
 789       gcc_unreachable ();
 790     }
 791
 792   return NULL_TREE;
 793 }
 794
 795 /* Attempt to fold a conditional statement. Return true if any changes were
 796    made. We only attempt to fold the condition expression, and do not perform
 797    any transformation that would require alteration of the cfg.  It is
 798    assumed that the operands have been previously folded.  */
 799
 800 static bool
 801 fold_gimple_cond (gimple stmt)
 802 {
 803   tree result = fold_binary_loc (gimple_location (stmt),
 804                              gimple_cond_code (stmt),
 805                              boolean_type_node,
 806                              gimple_cond_lhs (stmt),
 807                              gimple_cond_rhs (stmt));
 808
 809   if (result)
 810     {
 811       STRIP_USELESS_TYPE_CONVERSION (result);
 812       if (is_gimple_condexpr (result) && valid_gimple_rhs_p (result))
 813         {
 814           gimple_cond_set_condition_from_tree (stmt, result);
 815           return true;
 816         }
 817     }
 818
 819   return false;
 820 }
 821
 822 /* Convert EXPR into a GIMPLE value suitable for substitution on the
 823    RHS of an assignment.  Insert the necessary statements before
 824    iterator *SI_P.  The statement at *SI_P, which must be a GIMPLE_CALL
 825    is replaced.  If the call is expected to produces a result, then it
 826    is replaced by an assignment of the new RHS to the result variable.
 827    If the result is to be ignored, then the call is replaced by a
 828    GIMPLE_NOP.  A proper VDEF chain is retained by making the first
 829    VUSE and the last VDEF of the whole sequence be the same as the replaced
 830    statement and using new SSA names for stores in between.  */
 831
 832 void
 833 gimplify_and_update_call_from_tree (gimple_stmt_iterator *si_p, tree expr)
 834 {
 835   tree lhs;
 836   tree tmp = NULL_TREE;  /* Silence warning.  */
 837   gimple stmt, new_stmt;
 838   gimple_stmt_iterator i;
 839   gimple_seq stmts = gimple_seq_alloc();
 840   struct gimplify_ctx gctx;
 841   gimple last = NULL;
 842   gimple laststore = NULL;
 843   tree reaching_vuse;
 844
 845   stmt = gsi_stmt (*si_p);
 846
 847   gcc_assert (is_gimple_call (stmt));
 848
 849   lhs = gimple_call_lhs (stmt);
 850   reaching_vuse = gimple_vuse (stmt);
 851
 852   push_gimplify_context (&gctx);
 853
 854   if (lhs == NULL_TREE)
 855     gimplify_and_add (expr, &stmts);
 856   else
 857     tmp = get_initialized_tmp_var (expr, &stmts, NULL);
 858
 859   pop_gimplify_context (NULL);
 860
 861   if (gimple_has_location (stmt))
 862     annotate_all_with_location (stmts, gimple_location (stmt));
 863
 864   /* The replacement can expose previously unreferenced variables.  */
 865   for (i = gsi_start (stmts); !gsi_end_p (i); gsi_next (&i))
 866     {
 867       if (last)
 868         {
 869           gsi_insert_before (si_p, last, GSI_NEW_STMT);
 870           gsi_next (si_p);
 871         }
 872       new_stmt = gsi_stmt (i);
 873       if (gimple_in_ssa_p (cfun))
 874         {
 875           find_new_referenced_vars (new_stmt);
 876           mark_symbols_for_renaming (new_stmt);
 877         }
 878       /* If the new statement has a VUSE, update it with exact SSA name we
 879          know will reach this one.  */
 880       if (gimple_vuse (new_stmt))
 881         {
 882           /* If we've also seen a previous store create a new VDEF for
 883              the latter one, and make that the new reaching VUSE.  */
 884           if (laststore)
 885             {
 886               reaching_vuse = make_ssa_name (gimple_vop (cfun), laststore);
 887               gimple_set_vdef (laststore, reaching_vuse);
 888               update_stmt (laststore);
 889               laststore = NULL;
 890             }
 891           gimple_set_vuse (new_stmt, reaching_vuse);
 892           gimple_set_modified (new_stmt, true);
 893         }
 894       if (gimple_assign_single_p (new_stmt)
 895           && !is_gimple_reg (gimple_assign_lhs (new_stmt)))
 896         {
 897           laststore = new_stmt;
 898         }
 899       last = new_stmt;
 900     }
 901
 902   if (lhs == NULL_TREE)
 903     {
 904       /* If we replace a call without LHS that has a VDEF and our new
 905          sequence ends with a store we must make that store have the same
 906          vdef in order not to break the sequencing.  This can happen
 907          for instance when folding memcpy calls into assignments.  */
 908       if (gimple_vdef (stmt) && laststore)
 909         {
 910           gimple_set_vdef (laststore, gimple_vdef (stmt));
 911           if (TREE_CODE (gimple_vdef (stmt)) == SSA_NAME)
 912             SSA_NAME_DEF_STMT (gimple_vdef (stmt)) = laststore;
 913           update_stmt (laststore);
 914         }
 915       else if (gimple_in_ssa_p (cfun))
 916         {
 917           unlink_stmt_vdef (stmt);
 918           release_defs (stmt);
 919         }
 920       new_stmt = last;
 921     }
 922   else
 923     {
 924       if (last)
 925         {
 926           gsi_insert_before (si_p, last, GSI_NEW_STMT);
 927           gsi_next (si_p);
 928         }
 929       if (laststore && is_gimple_reg (lhs))
 930         {
 931           gimple_set_vdef (laststore, gimple_vdef (stmt));
 932           update_stmt (laststore);
 933           if (TREE_CODE (gimple_vdef (stmt)) == SSA_NAME)
 934             SSA_NAME_DEF_STMT (gimple_vdef (stmt)) = laststore;
 935           laststore = NULL;
 936         }
 937       else if (laststore)
 938         {
 939           reaching_vuse = make_ssa_name (gimple_vop (cfun), laststore);
 940           gimple_set_vdef (laststore, reaching_vuse);
 941           update_stmt (laststore);
 942           laststore = NULL;
 943         }
 944       new_stmt = gimple_build_assign (lhs, tmp);
 945       if (!is_gimple_reg (tmp))
 946         gimple_set_vuse (new_stmt, reaching_vuse);
 947       if (!is_gimple_reg (lhs))
 948         {
 949           gimple_set_vdef (new_stmt, gimple_vdef (stmt));
 950           if (TREE_CODE (gimple_vdef (stmt)) == SSA_NAME)
 951             SSA_NAME_DEF_STMT (gimple_vdef (stmt)) = new_stmt;
 952         }
 953     }
 954
 955   gimple_set_location (new_stmt, gimple_location (stmt));
 956   gsi_replace (si_p, new_stmt, false);
 957 }
 958
 959 /* Return the string length, maximum string length or maximum value of
 960    ARG in LENGTH.
 961    If ARG is an SSA name variable, follow its use-def chains.  If LENGTH
 962    is not NULL and, for TYPE == 0, its value is not equal to the length
 963    we determine or if we are unable to determine the length or value,
 964    return false.  VISITED is a bitmap of visited variables.
 965    TYPE is 0 if string length should be returned, 1 for maximum string
 966    length and 2 for maximum value ARG can have.  */
 967
 968 static bool
 969 get_maxval_strlen (tree arg, tree *length, bitmap visited, int type)
 970 {
 971   tree var, val;
 972   gimple def_stmt;
 973
 974   if (TREE_CODE (arg) != SSA_NAME)
 975     {
 976       if (TREE_CODE (arg) == COND_EXPR)
 977         return get_maxval_strlen (COND_EXPR_THEN (arg), length, visited, type)
 978                && get_maxval_strlen (COND_EXPR_ELSE (arg), length, visited, type);
 979       /* We can end up with &(*iftmp_1)[0] here as well, so handle it.  */
 980       else if (TREE_CODE (arg) == ADDR_EXPR
 981                && TREE_CODE (TREE_OPERAND (arg, 0)) == ARRAY_REF
 982                && integer_zerop (TREE_OPERAND (TREE_OPERAND (arg, 0), 1)))
 983         {
 984           tree aop0 = TREE_OPERAND (TREE_OPERAND (arg, 0), 0);
 985           if (TREE_CODE (aop0) == INDIRECT_REF
 986               && TREE_CODE (TREE_OPERAND (aop0, 0)) == SSA_NAME)
 987             return get_maxval_strlen (TREE_OPERAND (aop0, 0),
 988                                       length, visited, type);
 989         }
 990
 991       if (type == 2)
 992         {
 993           val = arg;
 994           if (TREE_CODE (val) != INTEGER_CST
 995               || tree_int_cst_sgn (val) < 0)
 996             return false;
 997         }
 998       else
 999         val = c_strlen (arg, 1);
1000       if (!val)
1001         return false;
1002
1003       if (*length)
1004         {
1005           if (type > 0)
1006             {
1007               if (TREE_CODE (*length) != INTEGER_CST
1008                   || TREE_CODE (val) != INTEGER_CST)
1009                 return false;
1010
1011               if (tree_int_cst_lt (*length, val))
1012                 *length = val;
1013               return true;
1014             }
1015           else if (simple_cst_equal (val, *length) != 1)
1016             return false;
1017         }
1018
1019       *length = val;
1020       return true;
1021     }
1022
1023   /* If we were already here, break the infinite cycle.  */
1024   if (!bitmap_set_bit (visited, SSA_NAME_VERSION (arg)))
1025     return true;
1026
1027   var = arg;
1028   def_stmt = SSA_NAME_DEF_STMT (var);
1029
1030   switch (gimple_code (def_stmt))
1031     {
1032       case GIMPLE_ASSIGN:
1033         /* The RHS of the statement defining VAR must either have a
1034            constant length or come from another SSA_NAME with a constant
1035            length.  */
1036         if (gimple_assign_single_p (def_stmt)
1037             || gimple_assign_unary_nop_p (def_stmt))
1038           {
1039             tree rhs = gimple_assign_rhs1 (def_stmt);
1040             return get_maxval_strlen (rhs, length, visited, type);
1041           }
1042         return false;
1043
1044       case GIMPLE_PHI:
1045         {
1046           /* All the arguments of the PHI node must have the same constant
1047              length.  */
1048           unsigned i;
1049
1050           for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
1051           {
1052             tree arg = gimple_phi_arg (def_stmt, i)->def;
1053
1054             /* If this PHI has itself as an argument, we cannot
1055                determine the string length of this argument.  However,
1056                if we can find a constant string length for the other
1057                PHI args then we can still be sure that this is a
1058                constant string length.  So be optimistic and just
1059                continue with the next argument.  */
1060             if (arg == gimple_phi_result (def_stmt))
1061               continue;
1062
1063             if (!get_maxval_strlen (arg, length, visited, type))
1064               return false;
1065           }
1066         }
1067         return true;
1068
1069       default:
1070         return false;
1071     }
1072 }
1073
1074
1075 /* Fold builtin call in statement STMT.  Returns a simplified tree.
1076    We may return a non-constant expression, including another call
1077    to a different function and with different arguments, e.g.,
1078    substituting memcpy for strcpy when the string length is known.
1079    Note that some builtins expand into inline code that may not
1080    be valid in GIMPLE.  Callers must take care.  */
1081
1082 tree
1083 gimple_fold_builtin (gimple stmt)
1084 {
1085   tree result, val[3];
1086   tree callee, a;
1087   int arg_idx, type;
1088   bitmap visited;
1089   bool ignore;
1090   int nargs;
1091   location_t loc = gimple_location (stmt);
1092
1093   gcc_assert (is_gimple_call (stmt));
1094
1095   ignore = (gimple_call_lhs (stmt) == NULL);
1096
1097   /* First try the generic builtin folder.  If that succeeds, return the
1098      result directly.  */
1099   result = fold_call_stmt (stmt, ignore);
1100   if (result)
1101     {
1102       if (ignore)
1103         STRIP_NOPS (result);
1104       return result;
1105     }
1106
1107   /* Ignore MD builtins.  */
1108   callee = gimple_call_fndecl (stmt);
1109   if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_MD)
1110     return NULL_TREE;
1111
1112   /* If the builtin could not be folded, and it has no argument list,
1113      we're done.  */
1114   nargs = gimple_call_num_args (stmt);
1115   if (nargs == 0)
1116     return NULL_TREE;
1117
1118   /* Limit the work only for builtins we know how to simplify.  */
1119   switch (DECL_FUNCTION_CODE (callee))
1120     {
1121     case BUILT_IN_STRLEN:
1122     case BUILT_IN_FPUTS:
1123     case BUILT_IN_FPUTS_UNLOCKED:
1124       arg_idx = 0;
1125       type = 0;
1126       break;
1127     case BUILT_IN_STRCPY:
1128     case BUILT_IN_STRNCPY:
1129       arg_idx = 1;
1130       type = 0;
1131       break;
1132     case BUILT_IN_MEMCPY_CHK:
1133     case BUILT_IN_MEMPCPY_CHK:
1134     case BUILT_IN_MEMMOVE_CHK:
1135     case BUILT_IN_MEMSET_CHK:
1136     case BUILT_IN_STRNCPY_CHK:
1137       arg_idx = 2;
1138       type = 2;
1139       break;
1140     case BUILT_IN_STRCPY_CHK:
1141     case BUILT_IN_STPCPY_CHK:
1142       arg_idx = 1;
1143       type = 1;
1144       break;
1145     case BUILT_IN_SNPRINTF_CHK:
1146     case BUILT_IN_VSNPRINTF_CHK:
1147       arg_idx = 1;
1148       type = 2;
1149       break;
1150     default:
1151       return NULL_TREE;
1152     }
1153
1154   if (arg_idx >= nargs)
1155     return NULL_TREE;
1156
1157   /* Try to use the dataflow information gathered by the CCP process.  */
1158   visited = BITMAP_ALLOC (NULL);
1159   bitmap_clear (visited);
1160
1161   memset (val, 0, sizeof (val));
1162   a = gimple_call_arg (stmt, arg_idx);
1163   if (!get_maxval_strlen (a, &val[arg_idx], visited, type))
1164     val[arg_idx] = NULL_TREE;
1165
1166   BITMAP_FREE (visited);
1167
1168   result = NULL_TREE;
1169   switch (DECL_FUNCTION_CODE (callee))
1170     {
1171     case BUILT_IN_STRLEN:
1172       if (val[0] && nargs == 1)
1173         {
1174           tree new_val =
1175               fold_convert (TREE_TYPE (gimple_call_lhs (stmt)), val[0]);
1176
1177           /* If the result is not a valid gimple value, or not a cast
1178              of a valid gimple value, then we cannot use the result.  */
1179           if (is_gimple_val (new_val)
1180               || (is_gimple_cast (new_val)
1181                   && is_gimple_val (TREE_OPERAND (new_val, 0))))
1182             return new_val;
1183         }
1184       break;
1185
1186     case BUILT_IN_STRCPY:
1187       if (val[1] && is_gimple_val (val[1]) && nargs == 2)
1188         result = fold_builtin_strcpy (loc, callee,
1189                                       gimple_call_arg (stmt, 0),
1190                                       gimple_call_arg (stmt, 1),
1191                                       val[1]);
1192       break;
1193
1194     case BUILT_IN_STRNCPY:
1195       if (val[1] && is_gimple_val (val[1]) && nargs == 3)
1196         result = fold_builtin_strncpy (loc, callee,
1197                                        gimple_call_arg (stmt, 0),
1198                                        gimple_call_arg (stmt, 1),
1199                                        gimple_call_arg (stmt, 2),
1200                                        val[1]);
1201       break;
1202
1203     case BUILT_IN_FPUTS:
1204       if (nargs == 2)
1205         result = fold_builtin_fputs (loc, gimple_call_arg (stmt, 0),
1206                                      gimple_call_arg (stmt, 1),
1207                                      ignore, false, val[0]);
1208       break;
1209
1210     case BUILT_IN_FPUTS_UNLOCKED:
1211       if (nargs == 2)
1212         result = fold_builtin_fputs (loc, gimple_call_arg (stmt, 0),
1213                                      gimple_call_arg (stmt, 1),
1214                                      ignore, true, val[0]);
1215       break;
1216
1217     case BUILT_IN_MEMCPY_CHK:
1218     case BUILT_IN_MEMPCPY_CHK:
1219     case BUILT_IN_MEMMOVE_CHK:
1220     case BUILT_IN_MEMSET_CHK:
1221       if (val[2] && is_gimple_val (val[2]) && nargs == 4)
1222         result = fold_builtin_memory_chk (loc, callee,
1223                                           gimple_call_arg (stmt, 0),
1224                                           gimple_call_arg (stmt, 1),
1225                                           gimple_call_arg (stmt, 2),
1226                                           gimple_call_arg (stmt, 3),
1227                                           val[2], ignore,
1228                                           DECL_FUNCTION_CODE (callee));
1229       break;
1230
1231     case BUILT_IN_STRCPY_CHK:
1232     case BUILT_IN_STPCPY_CHK:
1233       if (val[1] && is_gimple_val (val[1]) && nargs == 3)
1234         result = fold_builtin_stxcpy_chk (loc, callee,
1235                                           gimple_call_arg (stmt, 0),
1236                                           gimple_call_arg (stmt, 1),
1237                                           gimple_call_arg (stmt, 2),
1238                                           val[1], ignore,
1239                                           DECL_FUNCTION_CODE (callee));
1240       break;
1241
1242     case BUILT_IN_STRNCPY_CHK:
1243       if (val[2] && is_gimple_val (val[2]) && nargs == 4)
1244         result = fold_builtin_strncpy_chk (loc, gimple_call_arg (stmt, 0),
1245                                            gimple_call_arg (stmt, 1),
1246                                            gimple_call_arg (stmt, 2),
1247                                            gimple_call_arg (stmt, 3),
1248                                            val[2]);
1249       break;
1250
1251     case BUILT_IN_SNPRINTF_CHK:
1252     case BUILT_IN_VSNPRINTF_CHK:
1253       if (val[1] && is_gimple_val (val[1]))
1254         result = gimple_fold_builtin_snprintf_chk (stmt, val[1],
1255                                                    DECL_FUNCTION_CODE (callee));
1256       break;
1257
1258     default:
1259       gcc_unreachable ();
1260     }
1261
1262   if (result && ignore)
1263     result = fold_ignored_result (result);
1264   return result;
1265 }
1266
1267 /* Return the first of the base binfos of BINFO that has virtual functions.  */
1268
1269 static tree
1270 get_first_base_binfo_with_virtuals (tree binfo)
1271 {
1272   int i;
1273   tree base_binfo;
1274
1275   for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
1276     if (BINFO_VIRTUALS (base_binfo))
1277       return base_binfo;
1278
1279   return NULL_TREE;
1280 }
1281
1282
1283 /* Search for a base binfo of BINFO that corresponds to TYPE and return it if
1284    it is found or NULL_TREE if it is not.  */
1285
1286 static tree
1287 get_base_binfo_for_type (tree binfo, tree type)
1288 {
1289   int i;
1290   tree base_binfo;
1291   tree res = NULL_TREE;
1292
1293   for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
1294     if (TREE_TYPE (base_binfo) == type)
1295       {
1296         gcc_assert (!res);
1297         res = base_binfo;
1298       }
1299
1300   return res;
1301 }
1302
1303 /* Return a binfo describing the part of object referenced by expression REF.
1304    Return NULL_TREE if it cannot be determined.  REF can consist of a series of
1305    COMPONENT_REFs of a declaration or of an INDIRECT_REF or it can also be just
1306    a simple declaration, indirect reference or an SSA_NAME.  If the function
1307    discovers an INDIRECT_REF or an SSA_NAME, it will assume that the
1308    encapsulating type is described by KNOWN_BINFO, if it is not NULL_TREE.
1309    Otherwise the first non-artificial field declaration or the base declaration
1310    will be examined to get the encapsulating type. */
1311
1312 tree
1313 gimple_get_relevant_ref_binfo (tree ref, tree known_binfo)
1314 {
1315   while (true)
1316     {
1317       if (TREE_CODE (ref) == COMPONENT_REF)
1318         {
1319           tree par_type;
1320           tree binfo, base_binfo;
1321           tree field = TREE_OPERAND (ref, 1);
1322
1323           if (!DECL_ARTIFICIAL (field))
1324             {
1325               tree type = TREE_TYPE (field);
1326               if (TREE_CODE (type) == RECORD_TYPE)
1327                 return TYPE_BINFO (type);
1328               else
1329                 return NULL_TREE;
1330             }
1331
1332           par_type = TREE_TYPE (TREE_OPERAND (ref, 0));
1333           binfo = TYPE_BINFO (par_type);
1334           if (!binfo
1335               || BINFO_N_BASE_BINFOS (binfo) == 0)
1336             return NULL_TREE;
1337
1338           base_binfo = get_first_base_binfo_with_virtuals (binfo);
1339           if (base_binfo && BINFO_TYPE (base_binfo) != TREE_TYPE (field))
1340             {
1341               tree d_binfo;
1342
1343               d_binfo = gimple_get_relevant_ref_binfo (TREE_OPERAND (ref, 0),
1344                                                        known_binfo);
1345               /* Get descendant binfo. */
1346               if (!d_binfo)
1347                 return NULL_TREE;
1348               return get_base_binfo_for_type (d_binfo, TREE_TYPE (field));
1349             }
1350
1351           ref = TREE_OPERAND (ref, 0);
1352         }
1353       else if (DECL_P (ref) && TREE_CODE (TREE_TYPE (ref)) == RECORD_TYPE)
1354         return TYPE_BINFO (TREE_TYPE (ref));
1355       else if (known_binfo
1356                && (TREE_CODE (ref) == SSA_NAME
1357                    || TREE_CODE (ref) == MEM_REF))
1358         return known_binfo;
1359       else
1360         return NULL_TREE;
1361     }
1362 }
1363
1364 /* Fold a OBJ_TYPE_REF expression to the address of a function. TOKEN is
1365    integer form of OBJ_TYPE_REF_TOKEN of the reference expression.  KNOWN_BINFO
1366    carries the binfo describing the true type of OBJ_TYPE_REF_OBJECT(REF).  */
1367
1368 tree
1369 gimple_fold_obj_type_ref_known_binfo (HOST_WIDE_INT token, tree known_binfo)
1370 {
1371   HOST_WIDE_INT i;
1372   tree v, fndecl;
1373   struct cgraph_node *node;
1374
1375   v = BINFO_VIRTUALS (known_binfo);
1376   i = 0;
1377   while (i != token)
1378     {
1379       i += (TARGET_VTABLE_USES_DESCRIPTORS
1380             ? TARGET_VTABLE_USES_DESCRIPTORS : 1);
1381       v = TREE_CHAIN (v);
1382     }
1383
1384   fndecl = TREE_VALUE (v);
1385   node = cgraph_get_node (fndecl);
1386   /* When cgraph node is missing and function is not public, we cannot
1387      devirtualize.  This can happen in WHOPR when the actual method
1388      ends up in other partition, because we found devirtualization
1389      possibility too late.  */
1390   if ((!node || (!node->analyzed && !node->in_other_partition))
1391       && (!TREE_PUBLIC (fndecl) || DECL_COMDAT (fndecl)))
1392     return NULL;
1393   return build_fold_addr_expr (fndecl);
1394 }
1395
1396
1397 /* Fold a OBJ_TYPE_REF expression to the address of a function.  If KNOWN_TYPE
1398    is not NULL_TREE, it is the true type of the outmost encapsulating object if
1399    that comes from a pointer SSA_NAME.  If the true outmost encapsulating type
1400    can be determined from a declaration OBJ_TYPE_REF_OBJECT(REF), it is used
1401    regardless of KNOWN_TYPE (which thus can be NULL_TREE).  */
1402
1403 tree
1404 gimple_fold_obj_type_ref (tree ref, tree known_type)
1405 {
1406   tree obj = OBJ_TYPE_REF_OBJECT (ref);
1407   tree known_binfo = known_type ? TYPE_BINFO (known_type) : NULL_TREE;
1408   tree binfo;
1409
1410   if (TREE_CODE (obj) == ADDR_EXPR)
1411     obj = TREE_OPERAND (obj, 0);
1412
1413   binfo = gimple_get_relevant_ref_binfo (obj, known_binfo);
1414   if (binfo)
1415     {
1416       HOST_WIDE_INT token = tree_low_cst (OBJ_TYPE_REF_TOKEN (ref), 1);
1417       return gimple_fold_obj_type_ref_known_binfo (token, binfo);
1418     }
1419   else
1420     return NULL_TREE;
1421 }
1422
1423 /* Attempt to fold a call statement referenced by the statement iterator GSI.
1424    The statement may be replaced by another statement, e.g., if the call
1425    simplifies to a constant value. Return true if any changes were made.
1426    It is assumed that the operands have been previously folded.  */
1427
1428 static bool
1429 fold_gimple_call (gimple_stmt_iterator *gsi)
1430 {
1431   gimple stmt = gsi_stmt (*gsi);
1432
1433   tree callee = gimple_call_fndecl (stmt);
1434
1435   /* Check for builtins that CCP can handle using information not
1436      available in the generic fold routines.  */
1437   if (callee && DECL_BUILT_IN (callee))
1438     {
1439       tree result = gimple_fold_builtin (stmt);
1440
1441       if (result)
1442         {
1443           if (!update_call_from_tree (gsi, result))
1444             gimplify_and_update_call_from_tree (gsi, result);
1445           return true;
1446         }
1447     }
1448   else
1449     {
1450       /* ??? Should perhaps do this in fold proper.  However, doing it
1451          there requires that we create a new CALL_EXPR, and that requires
1452          copying EH region info to the new node.  Easier to just do it
1453          here where we can just smash the call operand.  */
1454       /* ??? Is there a good reason not to do this in fold_stmt_inplace?  */
1455       callee = gimple_call_fn (stmt);
1456       if (TREE_CODE (callee) == OBJ_TYPE_REF
1457           && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR)
1458         {
1459           tree t;
1460
1461           t = gimple_fold_obj_type_ref (callee, NULL_TREE);
1462           if (t)
1463             {
1464               gimple_call_set_fn (stmt, t);
1465               return true;
1466             }
1467         }
1468     }
1469
1470   return false;
1471 }
1472
1473 /* Worker for both fold_stmt and fold_stmt_inplace.  The INPLACE argument
1474    distinguishes both cases.  */
1475
1476 static bool
1477 fold_stmt_1 (gimple_stmt_iterator *gsi, bool inplace)
1478 {
1479   bool changed = false;
1480   gimple stmt = gsi_stmt (*gsi);
1481   unsigned i;
1482
1483   /* Fold the main computation performed by the statement.  */
1484   switch (gimple_code (stmt))
1485     {
1486     case GIMPLE_ASSIGN:
1487       {
1488         unsigned old_num_ops = gimple_num_ops (stmt);
1489         tree new_rhs = fold_gimple_assign (gsi);
1490         tree lhs = gimple_assign_lhs (stmt);
1491         if (new_rhs
1492             && !useless_type_conversion_p (TREE_TYPE (lhs),
1493                                            TREE_TYPE (new_rhs)))
1494           new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs);
1495         if (new_rhs
1496             && (!inplace
1497                 || get_gimple_rhs_num_ops (TREE_CODE (new_rhs)) < old_num_ops))
1498           {
1499             gimple_assign_set_rhs_from_tree (gsi, new_rhs);
1500             changed = true;
1501           }
1502         break;
1503       }
1504
1505     case GIMPLE_COND:
1506       changed |= fold_gimple_cond (stmt);
1507       break;
1508
1509     case GIMPLE_CALL:
1510       /* Fold *& in call arguments.  */
1511       for (i = 0; i < gimple_call_num_args (stmt); ++i)
1512         if (REFERENCE_CLASS_P (gimple_call_arg (stmt, i)))
1513           {
1514             tree tmp = maybe_fold_reference (gimple_call_arg (stmt, i), false);
1515             if (tmp)
1516               {
1517                 gimple_call_set_arg (stmt, i, tmp);
1518                 changed = true;
1519               }
1520           }
1521       /* The entire statement may be replaced in this case.  */
1522       if (!inplace)
1523         changed |= fold_gimple_call (gsi);
1524       break;
1525
1526     case GIMPLE_ASM:
1527       /* Fold *& in asm operands.  */
1528       for (i = 0; i < gimple_asm_noutputs (stmt); ++i)
1529         {
1530           tree link = gimple_asm_output_op (stmt, i);
1531           tree op = TREE_VALUE (link);
1532           if (REFERENCE_CLASS_P (op)
1533               && (op = maybe_fold_reference (op, true)) != NULL_TREE)
1534             {
1535               TREE_VALUE (link) = op;
1536               changed = true;
1537             }
1538         }
1539       for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
1540         {
1541           tree link = gimple_asm_input_op (stmt, i);
1542           tree op = TREE_VALUE (link);
1543           if (REFERENCE_CLASS_P (op)
1544               && (op = maybe_fold_reference (op, false)) != NULL_TREE)
1545             {
1546               TREE_VALUE (link) = op;
1547               changed = true;
1548             }
1549         }
1550       break;
1551
1552     case GIMPLE_DEBUG:
1553       if (gimple_debug_bind_p (stmt))
1554         {
1555           tree val = gimple_debug_bind_get_value (stmt);
1556           if (val
1557               && REFERENCE_CLASS_P (val))
1558             {
1559               tree tem = maybe_fold_reference (val, false);
1560               if (tem)
1561                 {
1562                   gimple_debug_bind_set_value (stmt, tem);
1563                   changed = true;
1564                 }
1565             }
1566         }
1567       break;
1568
1569     default:;
1570     }
1571
1572   stmt = gsi_stmt (*gsi);
1573
1574   /* Fold *& on the lhs.  */
1575   if (gimple_has_lhs (stmt))
1576     {
1577       tree lhs = gimple_get_lhs (stmt);
1578       if (lhs && REFERENCE_CLASS_P (lhs))
1579         {
1580           tree new_lhs = maybe_fold_reference (lhs, true);
1581           if (new_lhs)
1582             {
1583               gimple_set_lhs (stmt, new_lhs);
1584               changed = true;
1585             }
1586         }
1587     }
1588
1589   return changed;
1590 }
1591
1592 /* Fold the statement pointed to by GSI.  In some cases, this function may
1593    replace the whole statement with a new one.  Returns true iff folding
1594    makes any changes.
1595    The statement pointed to by GSI should be in valid gimple form but may
1596    be in unfolded state as resulting from for example constant propagation
1597    which can produce *&x = 0.  */
1598
1599 bool
1600 fold_stmt (gimple_stmt_iterator *gsi)
1601 {
1602   return fold_stmt_1 (gsi, false);
1603 }
1604
1605 /* Perform the minimal folding on statement STMT.  Only operations like
1606    *&x created by constant propagation are handled.  The statement cannot
1607    be replaced with a new one.  Return true if the statement was
1608    changed, false otherwise.
1609    The statement STMT should be in valid gimple form but may
1610    be in unfolded state as resulting from for example constant propagation
1611    which can produce *&x = 0.  */
1612
1613 bool
1614 fold_stmt_inplace (gimple stmt)
1615 {
1616   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1617   bool changed = fold_stmt_1 (&gsi, true);
1618   gcc_assert (gsi_stmt (gsi) == stmt);
1619   return changed;
1620 }
1621
1622 /* Canonicalize and possibly invert the boolean EXPR; return NULL_TREE
1623    if EXPR is null or we don't know how.
1624    If non-null, the result always has boolean type.  */
1625
1626 static tree
1627 canonicalize_bool (tree expr, bool invert)
1628 {
1629   if (!expr)
1630     return NULL_TREE;
1631   else if (invert)
1632     {
1633       if (integer_nonzerop (expr))
1634         return boolean_false_node;
1635       else if (integer_zerop (expr))
1636         return boolean_true_node;
1637       else if (TREE_CODE (expr) == SSA_NAME)
1638         return fold_build2 (EQ_EXPR, boolean_type_node, expr,
1639                             build_int_cst (TREE_TYPE (expr), 0));
1640       else if (TREE_CODE_CLASS (TREE_CODE (expr)) == tcc_comparison)
1641         return fold_build2 (invert_tree_comparison (TREE_CODE (expr), false),
1642                             boolean_type_node,
1643                             TREE_OPERAND (expr, 0),
1644                             TREE_OPERAND (expr, 1));
1645       else
1646         return NULL_TREE;
1647     }
1648   else
1649     {
1650       if (TREE_CODE (TREE_TYPE (expr)) == BOOLEAN_TYPE)
1651         return expr;
1652       if (integer_nonzerop (expr))
1653         return boolean_true_node;
1654       else if (integer_zerop (expr))
1655         return boolean_false_node;
1656       else if (TREE_CODE (expr) == SSA_NAME)
1657         return fold_build2 (NE_EXPR, boolean_type_node, expr,
1658                             build_int_cst (TREE_TYPE (expr), 0));
1659       else if (TREE_CODE_CLASS (TREE_CODE (expr)) == tcc_comparison)
1660         return fold_build2 (TREE_CODE (expr),
1661                             boolean_type_node,
1662                             TREE_OPERAND (expr, 0),
1663                             TREE_OPERAND (expr, 1));
1664       else
1665         return NULL_TREE;
1666     }
1667 }
1668
1669 /* Check to see if a boolean expression EXPR is logically equivalent to the
1670    comparison (OP1 CODE OP2).  Check for various identities involving
1671    SSA_NAMEs.  */
1672
1673 static bool
1674 same_bool_comparison_p (const_tree expr, enum tree_code code,
1675                         const_tree op1, const_tree op2)
1676 {
1677   gimple s;
1678
1679   /* The obvious case.  */
1680   if (TREE_CODE (expr) == code
1681       && operand_equal_p (TREE_OPERAND (expr, 0), op1, 0)
1682       && operand_equal_p (TREE_OPERAND (expr, 1), op2, 0))
1683     return true;
1684
1685   /* Check for comparing (name, name != 0) and the case where expr
1686      is an SSA_NAME with a definition matching the comparison.  */
1687   if (TREE_CODE (expr) == SSA_NAME
1688       && TREE_CODE (TREE_TYPE (expr)) == BOOLEAN_TYPE)
1689     {
1690       if (operand_equal_p (expr, op1, 0))
1691         return ((code == NE_EXPR && integer_zerop (op2))
1692                 || (code == EQ_EXPR && integer_nonzerop (op2)));
1693       s = SSA_NAME_DEF_STMT (expr);
1694       if (is_gimple_assign (s)
1695           && gimple_assign_rhs_code (s) == code
1696           && operand_equal_p (gimple_assign_rhs1 (s), op1, 0)
1697           && operand_equal_p (gimple_assign_rhs2 (s), op2, 0))
1698         return true;
1699     }
1700
1701   /* If op1 is of the form (name != 0) or (name == 0), and the definition
1702      of name is a comparison, recurse.  */
1703   if (TREE_CODE (op1) == SSA_NAME
1704       && TREE_CODE (TREE_TYPE (op1)) == BOOLEAN_TYPE)
1705     {
1706       s = SSA_NAME_DEF_STMT (op1);
1707       if (is_gimple_assign (s)
1708           && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
1709         {
1710           enum tree_code c = gimple_assign_rhs_code (s);
1711           if ((c == NE_EXPR && integer_zerop (op2))
1712               || (c == EQ_EXPR && integer_nonzerop (op2)))
1713             return same_bool_comparison_p (expr, c,
1714                                            gimple_assign_rhs1 (s),
1715                                            gimple_assign_rhs2 (s));
1716           if ((c == EQ_EXPR && integer_zerop (op2))
1717               || (c == NE_EXPR && integer_nonzerop (op2)))
1718             return same_bool_comparison_p (expr,
1719                                            invert_tree_comparison (c, false),
1720                                            gimple_assign_rhs1 (s),
1721                                            gimple_assign_rhs2 (s));
1722         }
1723     }
1724   return false;
1725 }
1726
1727 /* Check to see if two boolean expressions OP1 and OP2 are logically
1728    equivalent.  */
1729
1730 static bool
1731 same_bool_result_p (const_tree op1, const_tree op2)
1732 {
1733   /* Simple cases first.  */
1734   if (operand_equal_p (op1, op2, 0))
1735     return true;
1736
1737   /* Check the cases where at least one of the operands is a comparison.
1738      These are a bit smarter than operand_equal_p in that they apply some
1739      identifies on SSA_NAMEs.  */
1740   if (TREE_CODE_CLASS (TREE_CODE (op2)) == tcc_comparison
1741       && same_bool_comparison_p (op1, TREE_CODE (op2),
1742                                  TREE_OPERAND (op2, 0),
1743                                  TREE_OPERAND (op2, 1)))
1744     return true;
1745   if (TREE_CODE_CLASS (TREE_CODE (op1)) == tcc_comparison
1746       && same_bool_comparison_p (op2, TREE_CODE (op1),
1747                                  TREE_OPERAND (op1, 0),
1748                                  TREE_OPERAND (op1, 1)))
1749     return true;
1750
1751   /* Default case.  */
1752   return false;
1753 }
1754
1755 /* Forward declarations for some mutually recursive functions.  */
1756
1757 static tree
1758 and_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
1759                    enum tree_code code2, tree op2a, tree op2b);
1760 static tree
1761 and_var_with_comparison (tree var, bool invert,
1762                          enum tree_code code2, tree op2a, tree op2b);
1763 static tree
1764 and_var_with_comparison_1 (gimple stmt,
1765                            enum tree_code code2, tree op2a, tree op2b);
1766 static tree
1767 or_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
1768                   enum tree_code code2, tree op2a, tree op2b);
1769 static tree
1770 or_var_with_comparison (tree var, bool invert,
1771                         enum tree_code code2, tree op2a, tree op2b);
1772 static tree
1773 or_var_with_comparison_1 (gimple stmt,
1774                           enum tree_code code2, tree op2a, tree op2b);
1775
1776 /* Helper function for and_comparisons_1:  try to simplify the AND of the
1777    ssa variable VAR with the comparison specified by (OP2A CODE2 OP2B).
1778    If INVERT is true, invert the value of the VAR before doing the AND.
1779    Return NULL_EXPR if we can't simplify this to a single expression.  */
1780
1781 static tree
1782 and_var_with_comparison (tree var, bool invert,
1783                          enum tree_code code2, tree op2a, tree op2b)
1784 {
1785   tree t;
1786   gimple stmt = SSA_NAME_DEF_STMT (var);
1787
1788   /* We can only deal with variables whose definitions are assignments.  */
1789   if (!is_gimple_assign (stmt))
1790     return NULL_TREE;
1791
1792   /* If we have an inverted comparison, apply DeMorgan's law and rewrite
1793      !var AND (op2a code2 op2b) => !(var OR !(op2a code2 op2b))
1794      Then we only have to consider the simpler non-inverted cases.  */
1795   if (invert)
1796     t = or_var_with_comparison_1 (stmt,
1797                                   invert_tree_comparison (code2, false),
1798                                   op2a, op2b);
1799   else
1800     t = and_var_with_comparison_1 (stmt, code2, op2a, op2b);
1801   return canonicalize_bool (t, invert);
1802 }
1803
1804 /* Try to simplify the AND of the ssa variable defined by the assignment
1805    STMT with the comparison specified by (OP2A CODE2 OP2B).
1806    Return NULL_EXPR if we can't simplify this to a single expression.  */
1807
1808 static tree
1809 and_var_with_comparison_1 (gimple stmt,
1810                            enum tree_code code2, tree op2a, tree op2b)
1811 {
1812   tree var = gimple_assign_lhs (stmt);
1813   tree true_test_var = NULL_TREE;
1814   tree false_test_var = NULL_TREE;
1815   enum tree_code innercode = gimple_assign_rhs_code (stmt);
1816
1817   /* Check for identities like (var AND (var == 0)) => false.  */
1818   if (TREE_CODE (op2a) == SSA_NAME
1819       && TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE)
1820     {
1821       if ((code2 == NE_EXPR && integer_zerop (op2b))
1822           || (code2 == EQ_EXPR && integer_nonzerop (op2b)))
1823         {
1824           true_test_var = op2a;
1825           if (var == true_test_var)
1826             return var;
1827         }
1828       else if ((code2 == EQ_EXPR && integer_zerop (op2b))
1829                || (code2 == NE_EXPR && integer_nonzerop (op2b)))
1830         {
1831           false_test_var = op2a;
1832           if (var == false_test_var)
1833             return boolean_false_node;
1834         }
1835     }
1836
1837   /* If the definition is a comparison, recurse on it.  */
1838   if (TREE_CODE_CLASS (innercode) == tcc_comparison)
1839     {
1840       tree t = and_comparisons_1 (innercode,
1841                                   gimple_assign_rhs1 (stmt),
1842                                   gimple_assign_rhs2 (stmt),
1843                                   code2,
1844                                   op2a,
1845                                   op2b);
1846       if (t)
1847         return t;
1848     }
1849
1850   /* If the definition is an AND or OR expression, we may be able to
1851      simplify by reassociating.  */
1852   if (innercode == TRUTH_AND_EXPR
1853       || innercode == TRUTH_OR_EXPR
1854       || (TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE
1855           && (innercode == BIT_AND_EXPR || innercode == BIT_IOR_EXPR)))
1856     {
1857       tree inner1 = gimple_assign_rhs1 (stmt);
1858       tree inner2 = gimple_assign_rhs2 (stmt);
1859       gimple s;
1860       tree t;
1861       tree partial = NULL_TREE;
1862       bool is_and = (innercode == TRUTH_AND_EXPR || innercode == BIT_AND_EXPR);
1863
1864       /* Check for boolean identities that don't require recursive examination
1865          of inner1/inner2:
1866          inner1 AND (inner1 AND inner2) => inner1 AND inner2 => var
1867          inner1 AND (inner1 OR inner2) => inner1
1868          !inner1 AND (inner1 AND inner2) => false
1869          !inner1 AND (inner1 OR inner2) => !inner1 AND inner2
1870          Likewise for similar cases involving inner2.  */
1871       if (inner1 == true_test_var)
1872         return (is_and ? var : inner1);
1873       else if (inner2 == true_test_var)
1874         return (is_and ? var : inner2);
1875       else if (inner1 == false_test_var)
1876         return (is_and
1877                 ? boolean_false_node
1878                 : and_var_with_comparison (inner2, false, code2, op2a, op2b));
1879       else if (inner2 == false_test_var)
1880         return (is_and
1881                 ? boolean_false_node
1882                 : and_var_with_comparison (inner1, false, code2, op2a, op2b));
1883
1884       /* Next, redistribute/reassociate the AND across the inner tests.
1885          Compute the first partial result, (inner1 AND (op2a code op2b))  */
1886       if (TREE_CODE (inner1) == SSA_NAME
1887           && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner1))
1888           && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
1889           && (t = maybe_fold_and_comparisons (gimple_assign_rhs_code (s),
1890                                               gimple_assign_rhs1 (s),
1891                                               gimple_assign_rhs2 (s),
1892                                               code2, op2a, op2b)))
1893         {
1894           /* Handle the AND case, where we are reassociating:
1895              (inner1 AND inner2) AND (op2a code2 op2b)
1896              => (t AND inner2)
1897              If the partial result t is a constant, we win.  Otherwise
1898              continue on to try reassociating with the other inner test.  */
1899           if (is_and)
1900             {
1901               if (integer_onep (t))
1902                 return inner2;
1903               else if (integer_zerop (t))
1904                 return boolean_false_node;
1905             }
1906
1907           /* Handle the OR case, where we are redistributing:
1908              (inner1 OR inner2) AND (op2a code2 op2b)
1909              => (t OR (inner2 AND (op2a code2 op2b)))  */
1910           else
1911             {
1912               if (integer_onep (t))
1913                 return boolean_true_node;
1914               else
1915                 /* Save partial result for later.  */
1916                 partial = t;
1917             }
1918         }
1919
1920       /* Compute the second partial result, (inner2 AND (op2a code op2b)) */
1921       if (TREE_CODE (inner2) == SSA_NAME
1922           && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner2))
1923           && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
1924           && (t = maybe_fold_and_comparisons (gimple_assign_rhs_code (s),
1925                                               gimple_assign_rhs1 (s),
1926                                               gimple_assign_rhs2 (s),
1927                                               code2, op2a, op2b)))
1928         {
1929           /* Handle the AND case, where we are reassociating:
1930              (inner1 AND inner2) AND (op2a code2 op2b)
1931              => (inner1 AND t)  */
1932           if (is_and)
1933             {
1934               if (integer_onep (t))
1935                 return inner1;
1936               else if (integer_zerop (t))
1937                 return boolean_false_node;
1938             }
1939
1940           /* Handle the OR case. where we are redistributing:
1941              (inner1 OR inner2) AND (op2a code2 op2b)
1942              => (t OR (inner1 AND (op2a code2 op2b)))
1943              => (t OR partial)  */
1944           else
1945             {
1946               if (integer_onep (t))
1947                 return boolean_true_node;
1948               else if (partial)
1949                 {
1950                   /* We already got a simplification for the other
1951                      operand to the redistributed OR expression.  The
1952                      interesting case is when at least one is false.
1953                      Or, if both are the same, we can apply the identity
1954                      (x OR x) == x.  */
1955                   if (integer_zerop (partial))
1956                     return t;
1957                   else if (integer_zerop (t))
1958                     return partial;
1959                   else if (same_bool_result_p (t, partial))
1960                     return t;
1961                 }
1962             }
1963         }
1964     }
1965   return NULL_TREE;
1966 }
1967
1968 /* Try to simplify the AND of two comparisons defined by
1969    (OP1A CODE1 OP1B) and (OP2A CODE2 OP2B), respectively.
1970    If this can be done without constructing an intermediate value,
1971    return the resulting tree; otherwise NULL_TREE is returned.
1972    This function is deliberately asymmetric as it recurses on SSA_DEFs
1973    in the first comparison but not the second.  */
1974
1975 static tree
1976 and_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
1977                    enum tree_code code2, tree op2a, tree op2b)
1978 {
1979   /* First check for ((x CODE1 y) AND (x CODE2 y)).  */
1980   if (operand_equal_p (op1a, op2a, 0)
1981       && operand_equal_p (op1b, op2b, 0))
1982     {
1983       tree t = combine_comparisons (UNKNOWN_LOCATION,
1984                                     TRUTH_ANDIF_EXPR, code1, code2,
1985                                     boolean_type_node, op1a, op1b);
1986       if (t)
1987         return t;
1988     }
1989
1990   /* Likewise the swapped case of the above.  */
1991   if (operand_equal_p (op1a, op2b, 0)
1992       && operand_equal_p (op1b, op2a, 0))
1993     {
1994       tree t = combine_comparisons (UNKNOWN_LOCATION,
1995                                     TRUTH_ANDIF_EXPR, code1,
1996                                     swap_tree_comparison (code2),
1997                                     boolean_type_node, op1a, op1b);
1998       if (t)
1999         return t;
2000     }
2001
2002   /* If both comparisons are of the same value against constants, we might
2003      be able to merge them.  */
2004   if (operand_equal_p (op1a, op2a, 0)
2005       && TREE_CODE (op1b) == INTEGER_CST
2006       && TREE_CODE (op2b) == INTEGER_CST)
2007     {
2008       int cmp = tree_int_cst_compare (op1b, op2b);
2009
2010       /* If we have (op1a == op1b), we should either be able to
2011          return that or FALSE, depending on whether the constant op1b
2012          also satisfies the other comparison against op2b.  */
2013       if (code1 == EQ_EXPR)
2014         {
2015           bool done = true;
2016           bool val;
2017           switch (code2)
2018             {
2019             case EQ_EXPR: val = (cmp == 0); break;
2020             case NE_EXPR: val = (cmp != 0); break;
2021             case LT_EXPR: val = (cmp < 0); break;
2022             case GT_EXPR: val = (cmp > 0); break;
2023             case LE_EXPR: val = (cmp <= 0); break;
2024             case GE_EXPR: val = (cmp >= 0); break;
2025             default: done = false;
2026             }
2027           if (done)
2028             {
2029               if (val)
2030                 return fold_build2 (code1, boolean_type_node, op1a, op1b);
2031               else
2032                 return boolean_false_node;
2033             }
2034         }
2035       /* Likewise if the second comparison is an == comparison.  */
2036       else if (code2 == EQ_EXPR)
2037         {
2038           bool done = true;
2039           bool val;
2040           switch (code1)
2041             {
2042             case EQ_EXPR: val = (cmp == 0); break;
2043             case NE_EXPR: val = (cmp != 0); break;
2044             case LT_EXPR: val = (cmp > 0); break;
2045             case GT_EXPR: val = (cmp < 0); break;
2046             case LE_EXPR: val = (cmp >= 0); break;
2047             case GE_EXPR: val = (cmp <= 0); break;
2048             default: done = false;
2049             }
2050           if (done)
2051             {
2052               if (val)
2053                 return fold_build2 (code2, boolean_type_node, op2a, op2b);
2054               else
2055                 return boolean_false_node;
2056             }
2057         }
2058
2059       /* Same business with inequality tests.  */
2060       else if (code1 == NE_EXPR)
2061         {
2062           bool val;
2063           switch (code2)
2064             {
2065             case EQ_EXPR: val = (cmp != 0); break;
2066             case NE_EXPR: val = (cmp == 0); break;
2067             case LT_EXPR: val = (cmp >= 0); break;
2068             case GT_EXPR: val = (cmp <= 0); break;
2069             case LE_EXPR: val = (cmp > 0); break;
2070             case GE_EXPR: val = (cmp < 0); break;
2071             default:
2072               val = false;
2073             }
2074           if (val)
2075             return fold_build2 (code2, boolean_type_node, op2a, op2b);
2076         }
2077       else if (code2 == NE_EXPR)
2078         {
2079           bool val;
2080           switch (code1)
2081             {
2082             case EQ_EXPR: val = (cmp == 0); break;
2083             case NE_EXPR: val = (cmp != 0); break;
2084             case LT_EXPR: val = (cmp <= 0); break;
2085             case GT_EXPR: val = (cmp >= 0); break;
2086             case LE_EXPR: val = (cmp < 0); break;
2087             case GE_EXPR: val = (cmp > 0); break;
2088             default:
2089               val = false;
2090             }
2091           if (val)
2092             return fold_build2 (code1, boolean_type_node, op1a, op1b);
2093         }
2094
2095       /* Chose the more restrictive of two < or <= comparisons.  */
2096       else if ((code1 == LT_EXPR || code1 == LE_EXPR)
2097                && (code2 == LT_EXPR || code2 == LE_EXPR))
2098         {
2099           if ((cmp < 0) || (cmp == 0 && code1 == LT_EXPR))
2100             return fold_build2 (code1, boolean_type_node, op1a, op1b);
2101           else
2102             return fold_build2 (code2, boolean_type_node, op2a, op2b);
2103         }
2104
2105       /* Likewise chose the more restrictive of two > or >= comparisons.  */
2106       else if ((code1 == GT_EXPR || code1 == GE_EXPR)
2107                && (code2 == GT_EXPR || code2 == GE_EXPR))
2108         {
2109           if ((cmp > 0) || (cmp == 0 && code1 == GT_EXPR))
2110             return fold_build2 (code1, boolean_type_node, op1a, op1b);
2111           else
2112             return fold_build2 (code2, boolean_type_node, op2a, op2b);
2113         }
2114
2115       /* Check for singleton ranges.  */
2116       else if (cmp == 0
2117                && ((code1 == LE_EXPR && code2 == GE_EXPR)
2118                    || (code1 == GE_EXPR && code2 == LE_EXPR)))
2119         return fold_build2 (EQ_EXPR, boolean_type_node, op1a, op2b);
2120
2121       /* Check for disjoint ranges. */
2122       else if (cmp <= 0
2123                && (code1 == LT_EXPR || code1 == LE_EXPR)
2124                && (code2 == GT_EXPR || code2 == GE_EXPR))
2125         return boolean_false_node;
2126       else if (cmp >= 0
2127                && (code1 == GT_EXPR || code1 == GE_EXPR)
2128                && (code2 == LT_EXPR || code2 == LE_EXPR))
2129         return boolean_false_node;
2130     }
2131
2132   /* Perhaps the first comparison is (NAME != 0) or (NAME == 1) where
2133      NAME's definition is a truth value.  See if there are any simplifications
2134      that can be done against the NAME's definition.  */
2135   if (TREE_CODE (op1a) == SSA_NAME
2136       && (code1 == NE_EXPR || code1 == EQ_EXPR)
2137       && (integer_zerop (op1b) || integer_onep (op1b)))
2138     {
2139       bool invert = ((code1 == EQ_EXPR && integer_zerop (op1b))
2140                      || (code1 == NE_EXPR && integer_onep (op1b)));
2141       gimple stmt = SSA_NAME_DEF_STMT (op1a);
2142       switch (gimple_code (stmt))
2143         {
2144         case GIMPLE_ASSIGN:
2145           /* Try to simplify by copy-propagating the definition.  */
2146           return and_var_with_comparison (op1a, invert, code2, op2a, op2b);
2147
2148         case GIMPLE_PHI:
2149           /* If every argument to the PHI produces the same result when
2150              ANDed with the second comparison, we win.
2151              Do not do this unless the type is bool since we need a bool
2152              result here anyway.  */
2153           if (TREE_CODE (TREE_TYPE (op1a)) == BOOLEAN_TYPE)
2154             {
2155               tree result = NULL_TREE;
2156               unsigned i;
2157               for (i = 0; i < gimple_phi_num_args (stmt); i++)
2158                 {
2159                   tree arg = gimple_phi_arg_def (stmt, i);
2160
2161                   /* If this PHI has itself as an argument, ignore it.
2162                      If all the other args produce the same result,
2163                      we're still OK.  */
2164                   if (arg == gimple_phi_result (stmt))
2165                     continue;
2166                   else if (TREE_CODE (arg) == INTEGER_CST)
2167                     {
2168                       if (invert ? integer_nonzerop (arg) : integer_zerop (arg))
2169                         {
2170                           if (!result)
2171                             result = boolean_false_node;
2172                           else if (!integer_zerop (result))
2173                             return NULL_TREE;
2174                         }
2175                       else if (!result)
2176                         result = fold_build2 (code2, boolean_type_node,
2177                                               op2a, op2b);
2178                       else if (!same_bool_comparison_p (result,
2179                                                         code2, op2a, op2b))
2180                         return NULL_TREE;
2181                     }
2182                   else if (TREE_CODE (arg) == SSA_NAME)
2183                     {
2184                       tree temp = and_var_with_comparison (arg, invert,
2185                                                            code2, op2a, op2b);
2186                       if (!temp)
2187                         return NULL_TREE;
2188                       else if (!result)
2189                         result = temp;
2190                       else if (!same_bool_result_p (result, temp))
2191                         return NULL_TREE;
2192                     }
2193                   else
2194                     return NULL_TREE;
2195                 }
2196               return result;
2197             }
2198
2199         default:
2200           break;
2201         }
2202     }
2203   return NULL_TREE;
2204 }
2205
2206 /* Try to simplify the AND of two comparisons, specified by
2207    (OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
2208    If this can be simplified to a single expression (without requiring
2209    introducing more SSA variables to hold intermediate values),
2210    return the resulting tree.  Otherwise return NULL_TREE.
2211    If the result expression is non-null, it has boolean type.  */
2212
2213 tree
2214 maybe_fold_and_comparisons (enum tree_code code1, tree op1a, tree op1b,
2215                             enum tree_code code2, tree op2a, tree op2b)
2216 {
2217   tree t = and_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
2218   if (t)
2219     return t;
2220   else
2221     return and_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
2222 }
2223
2224 /* Helper function for or_comparisons_1:  try to simplify the OR of the
2225    ssa variable VAR with the comparison specified by (OP2A CODE2 OP2B).
2226    If INVERT is true, invert the value of VAR before doing the OR.
2227    Return NULL_EXPR if we can't simplify this to a single expression.  */
2228
2229 static tree
2230 or_var_with_comparison (tree var, bool invert,
2231                         enum tree_code code2, tree op2a, tree op2b)
2232 {
2233   tree t;
2234   gimple stmt = SSA_NAME_DEF_STMT (var);
2235
2236   /* We can only deal with variables whose definitions are assignments.  */
2237   if (!is_gimple_assign (stmt))
2238     return NULL_TREE;
2239
2240   /* If we have an inverted comparison, apply DeMorgan's law and rewrite
2241      !var OR (op2a code2 op2b) => !(var AND !(op2a code2 op2b))
2242      Then we only have to consider the simpler non-inverted cases.  */
2243   if (invert)
2244     t = and_var_with_comparison_1 (stmt,
2245                                    invert_tree_comparison (code2, false),
2246                                    op2a, op2b);
2247   else
2248     t = or_var_with_comparison_1 (stmt, code2, op2a, op2b);
2249   return canonicalize_bool (t, invert);
2250 }
2251
2252 /* Try to simplify the OR of the ssa variable defined by the assignment
2253    STMT with the comparison specified by (OP2A CODE2 OP2B).
2254    Return NULL_EXPR if we can't simplify this to a single expression.  */
2255
2256 static tree
2257 or_var_with_comparison_1 (gimple stmt,
2258                           enum tree_code code2, tree op2a, tree op2b)
2259 {
2260   tree var = gimple_assign_lhs (stmt);
2261   tree true_test_var = NULL_TREE;
2262   tree false_test_var = NULL_TREE;
2263   enum tree_code innercode = gimple_assign_rhs_code (stmt);
2264
2265   /* Check for identities like (var OR (var != 0)) => true .  */
2266   if (TREE_CODE (op2a) == SSA_NAME
2267       && TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE)
2268     {
2269       if ((code2 == NE_EXPR && integer_zerop (op2b))
2270           || (code2 == EQ_EXPR && integer_nonzerop (op2b)))
2271         {
2272           true_test_var = op2a;
2273           if (var == true_test_var)
2274             return var;
2275         }
2276       else if ((code2 == EQ_EXPR && integer_zerop (op2b))
2277                || (code2 == NE_EXPR && integer_nonzerop (op2b)))
2278         {
2279           false_test_var = op2a;
2280           if (var == false_test_var)
2281             return boolean_true_node;
2282         }
2283     }
2284
2285   /* If the definition is a comparison, recurse on it.  */
2286   if (TREE_CODE_CLASS (innercode) == tcc_comparison)
2287     {
2288       tree t = or_comparisons_1 (innercode,
2289                                  gimple_assign_rhs1 (stmt),
2290                                  gimple_assign_rhs2 (stmt),
2291                                  code2,
2292                                  op2a,
2293                                  op2b);
2294       if (t)
2295         return t;
2296     }
2297
2298   /* If the definition is an AND or OR expression, we may be able to
2299      simplify by reassociating.  */
2300   if (innercode == TRUTH_AND_EXPR
2301       || innercode == TRUTH_OR_EXPR
2302       || (TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE
2303           && (innercode == BIT_AND_EXPR || innercode == BIT_IOR_EXPR)))
2304     {
2305       tree inner1 = gimple_assign_rhs1 (stmt);
2306       tree inner2 = gimple_assign_rhs2 (stmt);
2307       gimple s;
2308       tree t;
2309       tree partial = NULL_TREE;
2310       bool is_or = (innercode == TRUTH_OR_EXPR || innercode == BIT_IOR_EXPR);
2311
2312       /* Check for boolean identities that don't require recursive examination
2313          of inner1/inner2:
2314          inner1 OR (inner1 OR inner2) => inner1 OR inner2 => var
2315          inner1 OR (inner1 AND inner2) => inner1
2316          !inner1 OR (inner1 OR inner2) => true
2317          !inner1 OR (inner1 AND inner2) => !inner1 OR inner2
2318       */
2319       if (inner1 == true_test_var)
2320         return (is_or ? var : inner1);
2321       else if (inner2 == true_test_var)
2322         return (is_or ? var : inner2);
2323       else if (inner1 == false_test_var)
2324         return (is_or
2325                 ? boolean_true_node
2326                 : or_var_with_comparison (inner2, false, code2, op2a, op2b));
2327       else if (inner2 == false_test_var)
2328         return (is_or
2329                 ? boolean_true_node
2330                 : or_var_with_comparison (inner1, false, code2, op2a, op2b));
2331
2332       /* Next, redistribute/reassociate the OR across the inner tests.
2333          Compute the first partial result, (inner1 OR (op2a code op2b))  */
2334       if (TREE_CODE (inner1) == SSA_NAME
2335           && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner1))
2336           && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
2337           && (t = maybe_fold_or_comparisons (gimple_assign_rhs_code (s),
2338                                              gimple_assign_rhs1 (s),
2339                                              gimple_assign_rhs2 (s),
2340                                              code2, op2a, op2b)))
2341         {
2342           /* Handle the OR case, where we are reassociating:
2343              (inner1 OR inner2) OR (op2a code2 op2b)
2344              => (t OR inner2)
2345              If the partial result t is a constant, we win.  Otherwise
2346              continue on to try reassociating with the other inner test.  */
2347           if (innercode == TRUTH_OR_EXPR)
2348             {
2349               if (integer_onep (t))
2350                 return boolean_true_node;
2351               else if (integer_zerop (t))
2352                 return inner2;
2353             }
2354
2355           /* Handle the AND case, where we are redistributing:
2356              (inner1 AND inner2) OR (op2a code2 op2b)
2357              => (t AND (inner2 OR (op2a code op2b)))  */
2358           else
2359             {
2360               if (integer_zerop (t))
2361                 return boolean_false_node;
2362               else
2363                 /* Save partial result for later.  */
2364                 partial = t;
2365             }
2366         }
2367
2368       /* Compute the second partial result, (inner2 OR (op2a code op2b)) */
2369       if (TREE_CODE (inner2) == SSA_NAME
2370           && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner2))
2371           && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
2372           && (t = maybe_fold_or_comparisons (gimple_assign_rhs_code (s),
2373                                              gimple_assign_rhs1 (s),
2374                                              gimple_assign_rhs2 (s),
2375                                              code2, op2a, op2b)))
2376         {
2377           /* Handle the OR case, where we are reassociating:
2378              (inner1 OR inner2) OR (op2a code2 op2b)
2379              => (inner1 OR t)  */
2380           if (innercode == TRUTH_OR_EXPR)
2381             {
2382               if (integer_zerop (t))
2383                 return inner1;
2384               else if (integer_onep (t))
2385                 return boolean_true_node;
2386             }
2387
2388           /* Handle the AND case, where we are redistributing:
2389              (inner1 AND inner2) OR (op2a code2 op2b)
2390              => (t AND (inner1 OR (op2a code2 op2b)))
2391              => (t AND partial)  */
2392           else
2393             {
2394               if (integer_zerop (t))
2395                 return boolean_false_node;
2396               else if (partial)
2397                 {
2398                   /* We already got a simplification for the other
2399                      operand to the redistributed AND expression.  The
2400                      interesting case is when at least one is true.
2401                      Or, if both are the same, we can apply the identity
2402                      (x AND x) == true.  */
2403                   if (integer_onep (partial))
2404                     return t;
2405                   else if (integer_onep (t))
2406                     return partial;
2407                   else if (same_bool_result_p (t, partial))
2408                     return boolean_true_node;
2409                 }
2410             }
2411         }
2412     }
2413   return NULL_TREE;
2414 }
2415
2416 /* Try to simplify the OR of two comparisons defined by
2417    (OP1A CODE1 OP1B) and (OP2A CODE2 OP2B), respectively.
2418    If this can be done without constructing an intermediate value,
2419    return the resulting tree; otherwise NULL_TREE is returned.
2420    This function is deliberately asymmetric as it recurses on SSA_DEFs
2421    in the first comparison but not the second.  */
2422
2423 static tree
2424 or_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
2425                   enum tree_code code2, tree op2a, tree op2b)
2426 {
2427   /* First check for ((x CODE1 y) OR (x CODE2 y)).  */
2428   if (operand_equal_p (op1a, op2a, 0)
2429       && operand_equal_p (op1b, op2b, 0))
2430     {
2431       tree t = combine_comparisons (UNKNOWN_LOCATION,
2432                                     TRUTH_ORIF_EXPR, code1, code2,
2433                                     boolean_type_node, op1a, op1b);
2434       if (t)
2435         return t;
2436     }
2437
2438   /* Likewise the swapped case of the above.  */
2439   if (operand_equal_p (op1a, op2b, 0)
2440       && operand_equal_p (op1b, op2a, 0))
2441     {
2442       tree t = combine_comparisons (UNKNOWN_LOCATION,
2443                                     TRUTH_ORIF_EXPR, code1,
2444                                     swap_tree_comparison (code2),
2445                                     boolean_type_node, op1a, op1b);
2446       if (t)
2447         return t;
2448     }
2449
2450   /* If both comparisons are of the same value against constants, we might
2451      be able to merge them.  */
2452   if (operand_equal_p (op1a, op2a, 0)
2453       && TREE_CODE (op1b) == INTEGER_CST
2454       && TREE_CODE (op2b) == INTEGER_CST)
2455     {
2456       int cmp = tree_int_cst_compare (op1b, op2b);
2457
2458       /* If we have (op1a != op1b), we should either be able to
2459          return that or TRUE, depending on whether the constant op1b
2460          also satisfies the other comparison against op2b.  */
2461       if (code1 == NE_EXPR)
2462         {
2463           bool done = true;
2464           bool val;
2465           switch (code2)
2466             {
2467             case EQ_EXPR: val = (cmp == 0); break;
2468             case NE_EXPR: val = (cmp != 0); break;
2469             case LT_EXPR: val = (cmp < 0); break;
2470             case GT_EXPR: val = (cmp > 0); break;
2471             case LE_EXPR: val = (cmp <= 0); break;
2472             case GE_EXPR: val = (cmp >= 0); break;
2473             default: done = false;
2474             }
2475           if (done)
2476             {
2477               if (val)
2478                 return boolean_true_node;
2479               else
2480                 return fold_build2 (code1, boolean_type_node, op1a, op1b);
2481             }
2482         }
2483       /* Likewise if the second comparison is a != comparison.  */
2484       else if (code2 == NE_EXPR)
2485         {
2486           bool done = true;
2487           bool val;
2488           switch (code1)
2489             {
2490             case EQ_EXPR: val = (cmp == 0); break;
2491             case NE_EXPR: val = (cmp != 0); break;
2492             case LT_EXPR: val = (cmp > 0); break;
2493             case GT_EXPR: val = (cmp < 0); break;
2494             case LE_EXPR: val = (cmp >= 0); break;
2495             case GE_EXPR: val = (cmp <= 0); break;
2496             default: done = false;
2497             }
2498           if (done)
2499             {
2500               if (val)
2501                 return boolean_true_node;
2502               else
2503                 return fold_build2 (code2, boolean_type_node, op2a, op2b);
2504             }
2505         }
2506
2507       /* See if an equality test is redundant with the other comparison.  */
2508       else if (code1 == EQ_EXPR)
2509         {
2510           bool val;
2511           switch (code2)
2512             {
2513             case EQ_EXPR: val = (cmp == 0); break;
2514             case NE_EXPR: val = (cmp != 0); break;
2515             case LT_EXPR: val = (cmp < 0); break;
2516             case GT_EXPR: val = (cmp > 0); break;
2517             case LE_EXPR: val = (cmp <= 0); break;
2518             case GE_EXPR: val = (cmp >= 0); break;
2519             default:
2520               val = false;
2521             }
2522           if (val)
2523             return fold_build2 (code2, boolean_type_node, op2a, op2b);
2524         }
2525       else if (code2 == EQ_EXPR)
2526         {
2527           bool val;
2528           switch (code1)
2529             {
2530             case EQ_EXPR: val = (cmp == 0); break;
2531             case NE_EXPR: val = (cmp != 0); break;
2532             case LT_EXPR: val = (cmp > 0); break;
2533             case GT_EXPR: val = (cmp < 0); break;
2534             case LE_EXPR: val = (cmp >= 0); break;
2535             case GE_EXPR: val = (cmp <= 0); break;
2536             default:
2537               val = false;
2538             }
2539           if (val)
2540             return fold_build2 (code1, boolean_type_node, op1a, op1b);
2541         }
2542
2543       /* Chose the less restrictive of two < or <= comparisons.  */
2544       else if ((code1 == LT_EXPR || code1 == LE_EXPR)
2545                && (code2 == LT_EXPR || code2 == LE_EXPR))
2546         {
2547           if ((cmp < 0) || (cmp == 0 && code1 == LT_EXPR))
2548             return fold_build2 (code2, boolean_type_node, op2a, op2b);
2549           else
2550             return fold_build2 (code1, boolean_type_node, op1a, op1b);
2551         }
2552
2553       /* Likewise chose the less restrictive of two > or >= comparisons.  */
2554       else if ((code1 == GT_EXPR || code1 == GE_EXPR)
2555                && (code2 == GT_EXPR || code2 == GE_EXPR))
2556         {
2557           if ((cmp > 0) || (cmp == 0 && code1 == GT_EXPR))
2558             return fold_build2 (code2, boolean_type_node, op2a, op2b);
2559           else
2560             return fold_build2 (code1, boolean_type_node, op1a, op1b);
2561         }
2562
2563       /* Check for singleton ranges.  */
2564       else if (cmp == 0
2565                && ((code1 == LT_EXPR && code2 == GT_EXPR)
2566                    || (code1 == GT_EXPR && code2 == LT_EXPR)))
2567         return fold_build2 (NE_EXPR, boolean_type_node, op1a, op2b);
2568
2569       /* Check for less/greater pairs that don't restrict the range at all.  */
2570       else if (cmp >= 0
2571                && (code1 == LT_EXPR || code1 == LE_EXPR)
2572                && (code2 == GT_EXPR || code2 == GE_EXPR))
2573         return boolean_true_node;
2574       else if (cmp <= 0
2575                && (code1 == GT_EXPR || code1 == GE_EXPR)
2576                && (code2 == LT_EXPR || code2 == LE_EXPR))
2577         return boolean_true_node;
2578     }
2579
2580   /* Perhaps the first comparison is (NAME != 0) or (NAME == 1) where
2581      NAME's definition is a truth value.  See if there are any simplifications
2582      that can be done against the NAME's definition.  */
2583   if (TREE_CODE (op1a) == SSA_NAME
2584       && (code1 == NE_EXPR || code1 == EQ_EXPR)
2585       && (integer_zerop (op1b) || integer_onep (op1b)))
2586     {
2587       bool invert = ((code1 == EQ_EXPR && integer_zerop (op1b))
2588                      || (code1 == NE_EXPR && integer_onep (op1b)));
2589       gimple stmt = SSA_NAME_DEF_STMT (op1a);
2590       switch (gimple_code (stmt))
2591         {
2592         case GIMPLE_ASSIGN:
2593           /* Try to simplify by copy-propagating the definition.  */
2594           return or_var_with_comparison (op1a, invert, code2, op2a, op2b);
2595
2596         case GIMPLE_PHI:
2597           /* If every argument to the PHI produces the same result when
2598              ORed with the second comparison, we win.
2599              Do not do this unless the type is bool since we need a bool
2600              result here anyway.  */
2601           if (TREE_CODE (TREE_TYPE (op1a)) == BOOLEAN_TYPE)
2602             {
2603               tree result = NULL_TREE;
2604               unsigned i;
2605               for (i = 0; i < gimple_phi_num_args (stmt); i++)
2606                 {
2607                   tree arg = gimple_phi_arg_def (stmt, i);
2608
2609                   /* If this PHI has itself as an argument, ignore it.
2610                      If all the other args produce the same result,
2611                      we're still OK.  */
2612                   if (arg == gimple_phi_result (stmt))
2613                     continue;
2614                   else if (TREE_CODE (arg) == INTEGER_CST)
2615                     {
2616                       if (invert ? integer_zerop (arg) : integer_nonzerop (arg))
2617                         {
2618                           if (!result)
2619                             result = boolean_true_node;
2620                           else if (!integer_onep (result))
2621                             return NULL_TREE;
2622                         }
2623                       else if (!result)
2624                         result = fold_build2 (code2, boolean_type_node,
2625                                               op2a, op2b);
2626                       else if (!same_bool_comparison_p (result,
2627                                                         code2, op2a, op2b))
2628                         return NULL_TREE;
2629                     }
2630                   else if (TREE_CODE (arg) == SSA_NAME)
2631                     {
2632                       tree temp = or_var_with_comparison (arg, invert,
2633                                                           code2, op2a, op2b);
2634                       if (!temp)
2635                         return NULL_TREE;
2636                       else if (!result)
2637                         result = temp;
2638                       else if (!same_bool_result_p (result, temp))
2639                         return NULL_TREE;
2640                     }
2641                   else
2642                     return NULL_TREE;
2643                 }
2644               return result;
2645             }
2646
2647         default:
2648           break;
2649         }
2650     }
2651   return NULL_TREE;
2652 }
2653
2654 /* Try to simplify the OR of two comparisons, specified by
2655    (OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
2656    If this can be simplified to a single expression (without requiring
2657    introducing more SSA variables to hold intermediate values),
2658    return the resulting tree.  Otherwise return NULL_TREE.
2659    If the result expression is non-null, it has boolean type.  */
2660
2661 tree
2662 maybe_fold_or_comparisons (enum tree_code code1, tree op1a, tree op1b,
2663                            enum tree_code code2, tree op2a, tree op2b)
2664 {
2665   tree t = or_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
2666   if (t)
2667     return t;
2668   else
2669     return or_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
2670 }