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