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