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