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