gcc/gimple-fold.c

   1 /* Statement simplification on GIMPLE.
   2    Copyright (C) 2010, 2011 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 #include "gimple-fold.h"
  34
  35 /* Return true when DECL can be referenced from current unit.
  36    We can get declarations that are not possible to reference for
  37    various reasons:
  38
  39      1) When analyzing C++ virtual tables.
  40         C++ virtual tables do have known constructors even
  41         when they are keyed to other compilation unit.
  42         Those tables can contain pointers to methods and vars
  43         in other units.  Those methods have both STATIC and EXTERNAL
  44         set.
  45      2) In WHOPR mode devirtualization might lead to reference
  46         to method that was partitioned elsehwere.
  47         In this case we have static VAR_DECL or FUNCTION_DECL
  48         that has no corresponding callgraph/varpool node
  49         declaring the body.
  50      3) COMDAT functions referred by external vtables that
  51         we devirtualize only during final copmilation stage.
  52         At this time we already decided that we will not output
  53         the function body and thus we can't reference the symbol
  54         directly.  */
  55
  56 static bool
  57 can_refer_decl_in_current_unit_p (tree decl)
  58 {
  59   struct varpool_node *vnode;
  60   struct cgraph_node *node;
  61
  62   if (!TREE_STATIC (decl) && !DECL_EXTERNAL (decl))
  63     return true;
  64   /* External flag is set, so we deal with C++ reference
  65      to static object from other file.  */
  66   if (DECL_EXTERNAL (decl) && TREE_STATIC (decl)
  67       && TREE_CODE (decl) == VAR_DECL)
  68     {
  69       /* Just be sure it is not big in frontend setting
  70          flags incorrectly.  Those variables should never
  71          be finalized.  */
  72       gcc_checking_assert (!(vnode = varpool_get_node (decl))
  73                            || !vnode->finalized);
  74       return false;
  75     }
  76   /* When function is public, we always can introduce new reference.
  77      Exception are the COMDAT functions where introducing a direct
  78      reference imply need to include function body in the curren tunit.  */
  79   if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl))
  80     return true;
  81   /* We are not at ltrans stage; so don't worry about WHOPR.
  82      Also when still gimplifying all referred comdat functions will be
  83      produced.
  84      ??? as observed in PR20991 for already optimized out comdat virtual functions
  85      we may not neccesarily give up because the copy will be output elsewhere when
  86      corresponding vtable is output.  */
  87   if (!flag_ltrans && (!DECL_COMDAT (decl) || !cgraph_function_flags_ready))
  88     return true;
  89   /* If we already output the function body, we are safe.  */
  90   if (TREE_ASM_WRITTEN (decl))
  91     return true;
  92   if (TREE_CODE (decl) == FUNCTION_DECL)
  93     {
  94       node = cgraph_get_node (decl);
  95       /* Check that we still have function body and that we didn't took
  96          the decision to eliminate offline copy of the function yet.
  97          The second is important when devirtualization happens during final
  98          compilation stage when making a new reference no longer makes callee
  99          to be compiled.  */
 100       if (!node || !node->analyzed || node->global.inlined_to)
 101         return false;
 102     }
 103   else if (TREE_CODE (decl) == VAR_DECL)
 104     {
 105       vnode = varpool_get_node (decl);
 106       if (!vnode || !vnode->finalized)
 107         return false;
 108     }
 109   return true;
 110 }
 111
 112 /* CVAL is value taken from DECL_INITIAL of variable.  Try to transform it into
 113    acceptable form for is_gimple_min_invariant.   */
 114
 115 tree
 116 canonicalize_constructor_val (tree cval)
 117 {
 118   STRIP_NOPS (cval);
 119   if (TREE_CODE (cval) == POINTER_PLUS_EXPR
 120       && TREE_CODE (TREE_OPERAND (cval, 1)) == INTEGER_CST)
 121     {
 122       tree ptr = TREE_OPERAND (cval, 0);
 123       if (is_gimple_min_invariant (ptr))
 124         cval = build1_loc (EXPR_LOCATION (cval),
 125                            ADDR_EXPR, TREE_TYPE (ptr),
 126                            fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (ptr)),
 127                                         ptr,
 128                                         fold_convert (ptr_type_node,
 129                                                       TREE_OPERAND (cval, 1))));
 130     }
 131   if (TREE_CODE (cval) == ADDR_EXPR)
 132     {
 133       tree base = get_base_address (TREE_OPERAND (cval, 0));
 134
 135       if (base
 136           && (TREE_CODE (base) == VAR_DECL
 137               || TREE_CODE (base) == FUNCTION_DECL)
 138           && !can_refer_decl_in_current_unit_p (base))
 139         return NULL_TREE;
 140       if (cfun && base && TREE_CODE (base) == VAR_DECL)
 141         add_referenced_var (base);
 142       /* Fixup types in global initializers.  */
 143       if (TREE_TYPE (TREE_TYPE (cval)) != TREE_TYPE (TREE_OPERAND (cval, 0)))
 144         cval = build_fold_addr_expr (TREE_OPERAND (cval, 0));
 145     }
 146   return cval;
 147 }
 148
 149 /* If SYM is a constant variable with known value, return the value.
 150    NULL_TREE is returned otherwise.  */
 151
 152 tree
 153 get_symbol_constant_value (tree sym)
 154 {
 155   if (const_value_known_p (sym))
 156     {
 157       tree val = DECL_INITIAL (sym);
 158       if (val)
 159         {
 160           val = canonicalize_constructor_val (val);
 161           if (val && is_gimple_min_invariant (val))
 162             return val;
 163           else
 164             return NULL_TREE;
 165         }
 166       /* Variables declared 'const' without an initializer
 167          have zero as the initializer if they may not be
 168          overridden at link or run time.  */
 169       if (!val
 170           && (INTEGRAL_TYPE_P (TREE_TYPE (sym))
 171                || SCALAR_FLOAT_TYPE_P (TREE_TYPE (sym))))
 172         return build_zero_cst (TREE_TYPE (sym));
 173     }
 174
 175   return NULL_TREE;
 176 }
 177
 178
 179
 180 /* Subroutine of fold_stmt.  We perform several simplifications of the
 181    memory reference tree EXPR and make sure to re-gimplify them properly
 182    after propagation of constant addresses.  IS_LHS is true if the
 183    reference is supposed to be an lvalue.  */
 184
 185 static tree
 186 maybe_fold_reference (tree expr, bool is_lhs)
 187 {
 188   tree *t = &expr;
 189   tree result;
 190
 191   if ((TREE_CODE (expr) == VIEW_CONVERT_EXPR
 192        || TREE_CODE (expr) == REALPART_EXPR
 193        || TREE_CODE (expr) == IMAGPART_EXPR)
 194       && CONSTANT_CLASS_P (TREE_OPERAND (expr, 0)))
 195     return fold_unary_loc (EXPR_LOCATION (expr),
 196                            TREE_CODE (expr),
 197                            TREE_TYPE (expr),
 198                            TREE_OPERAND (expr, 0));
 199   else if (TREE_CODE (expr) == BIT_FIELD_REF
 200            && CONSTANT_CLASS_P (TREE_OPERAND (expr, 0)))
 201     return fold_ternary_loc (EXPR_LOCATION (expr),
 202                              TREE_CODE (expr),
 203                              TREE_TYPE (expr),
 204                              TREE_OPERAND (expr, 0),
 205                              TREE_OPERAND (expr, 1),
 206                              TREE_OPERAND (expr, 2));
 207
 208   while (handled_component_p (*t))
 209     t = &TREE_OPERAND (*t, 0);
 210
 211   /* Canonicalize MEM_REFs invariant address operand.  Do this first
 212      to avoid feeding non-canonical MEM_REFs elsewhere.  */
 213   if (TREE_CODE (*t) == MEM_REF
 214       && !is_gimple_mem_ref_addr (TREE_OPERAND (*t, 0)))
 215     {
 216       bool volatile_p = TREE_THIS_VOLATILE (*t);
 217       tree tem = fold_binary (MEM_REF, TREE_TYPE (*t),
 218                               TREE_OPERAND (*t, 0),
 219                               TREE_OPERAND (*t, 1));
 220       if (tem)
 221         {
 222           TREE_THIS_VOLATILE (tem) = volatile_p;
 223           *t = tem;
 224           tem = maybe_fold_reference (expr, is_lhs);
 225           if (tem)
 226             return tem;
 227           return expr;
 228         }
 229     }
 230
 231   if (!is_lhs
 232       && (result = fold_const_aggregate_ref (expr))
 233       && is_gimple_min_invariant (result))
 234     return result;
 235
 236   /* Fold back MEM_REFs to reference trees.  */
 237   if (TREE_CODE (*t) == MEM_REF
 238       && TREE_CODE (TREE_OPERAND (*t, 0)) == ADDR_EXPR
 239       && integer_zerop (TREE_OPERAND (*t, 1))
 240       && (TREE_THIS_VOLATILE (*t)
 241           == TREE_THIS_VOLATILE (TREE_OPERAND (TREE_OPERAND (*t, 0), 0)))
 242       && !TYPE_REF_CAN_ALIAS_ALL (TREE_TYPE (TREE_OPERAND (*t, 1)))
 243       && (TYPE_MAIN_VARIANT (TREE_TYPE (*t))
 244           == TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (TREE_OPERAND (*t, 1)))))
 245       /* We have to look out here to not drop a required conversion
 246          from the rhs to the lhs if is_lhs, but we don't have the
 247          rhs here to verify that.  Thus require strict type
 248          compatibility.  */
 249       && types_compatible_p (TREE_TYPE (*t),
 250                              TREE_TYPE (TREE_OPERAND
 251                                         (TREE_OPERAND (*t, 0), 0))))
 252     {
 253       tree tem;
 254       *t = TREE_OPERAND (TREE_OPERAND (*t, 0), 0);
 255       tem = maybe_fold_reference (expr, is_lhs);
 256       if (tem)
 257         return tem;
 258       return expr;
 259     }
 260   else if (TREE_CODE (*t) == TARGET_MEM_REF)
 261     {
 262       tree tem = maybe_fold_tmr (*t);
 263       if (tem)
 264         {
 265           *t = tem;
 266           tem = maybe_fold_reference (expr, is_lhs);
 267           if (tem)
 268             return tem;
 269           return expr;
 270         }
 271     }
 272
 273   return NULL_TREE;
 274 }
 275
 276
 277 /* Attempt to fold an assignment statement pointed-to by SI.  Returns a
 278    replacement rhs for the statement or NULL_TREE if no simplification
 279    could be made.  It is assumed that the operands have been previously
 280    folded.  */
 281
 282 static tree
 283 fold_gimple_assign (gimple_stmt_iterator *si)
 284 {
 285   gimple stmt = gsi_stmt (*si);
 286   enum tree_code subcode = gimple_assign_rhs_code (stmt);
 287   location_t loc = gimple_location (stmt);
 288
 289   tree result = NULL_TREE;
 290
 291   switch (get_gimple_rhs_class (subcode))
 292     {
 293     case GIMPLE_SINGLE_RHS:
 294       {
 295         tree rhs = gimple_assign_rhs1 (stmt);
 296
 297         if (REFERENCE_CLASS_P (rhs))
 298           return maybe_fold_reference (rhs, false);
 299
 300         else if (TREE_CODE (rhs) == ADDR_EXPR)
 301           {
 302             tree ref = TREE_OPERAND (rhs, 0);
 303             tree tem = maybe_fold_reference (ref, true);
 304             if (tem
 305                 && TREE_CODE (tem) == MEM_REF
 306                 && integer_zerop (TREE_OPERAND (tem, 1)))
 307               result = fold_convert (TREE_TYPE (rhs), TREE_OPERAND (tem, 0));
 308             else if (tem)
 309               result = fold_convert (TREE_TYPE (rhs),
 310                                      build_fold_addr_expr_loc (loc, tem));
 311             else if (TREE_CODE (ref) == MEM_REF
 312                      && integer_zerop (TREE_OPERAND (ref, 1)))
 313               result = fold_convert (TREE_TYPE (rhs), TREE_OPERAND (ref, 0));
 314           }
 315
 316         else if (TREE_CODE (rhs) == CONSTRUCTOR
 317                  && TREE_CODE (TREE_TYPE (rhs)) == VECTOR_TYPE
 318                  && (CONSTRUCTOR_NELTS (rhs)
 319                      == TYPE_VECTOR_SUBPARTS (TREE_TYPE (rhs))))
 320           {
 321             /* Fold a constant vector CONSTRUCTOR to VECTOR_CST.  */
 322             unsigned i;
 323             tree val;
 324
 325             FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (rhs), i, val)
 326               if (TREE_CODE (val) != INTEGER_CST
 327                   && TREE_CODE (val) != REAL_CST
 328                   && TREE_CODE (val) != FIXED_CST)
 329                 return NULL_TREE;
 330
 331             return build_vector_from_ctor (TREE_TYPE (rhs),
 332                                            CONSTRUCTOR_ELTS (rhs));
 333           }
 334
 335         else if (DECL_P (rhs))
 336           return unshare_expr (get_symbol_constant_value (rhs));
 337
 338         /* If we couldn't fold the RHS, hand over to the generic
 339            fold routines.  */
 340         if (result == NULL_TREE)
 341           result = fold (rhs);
 342
 343         /* Strip away useless type conversions.  Both the NON_LVALUE_EXPR
 344            that may have been added by fold, and "useless" type
 345            conversions that might now be apparent due to propagation.  */
 346         STRIP_USELESS_TYPE_CONVERSION (result);
 347
 348         if (result != rhs && valid_gimple_rhs_p (result))
 349           return result;
 350
 351         return NULL_TREE;
 352       }
 353       break;
 354
 355     case GIMPLE_UNARY_RHS:
 356       {
 357         tree rhs = gimple_assign_rhs1 (stmt);
 358
 359         result = fold_unary_loc (loc, subcode, gimple_expr_type (stmt), rhs);
 360         if (result)
 361           {
 362             /* If the operation was a conversion do _not_ mark a
 363                resulting constant with TREE_OVERFLOW if the original
 364                constant was not.  These conversions have implementation
 365                defined behavior and retaining the TREE_OVERFLOW flag
 366                here would confuse later passes such as VRP.  */
 367             if (CONVERT_EXPR_CODE_P (subcode)
 368                 && TREE_CODE (result) == INTEGER_CST
 369                 && TREE_CODE (rhs) == INTEGER_CST)
 370               TREE_OVERFLOW (result) = TREE_OVERFLOW (rhs);
 371
 372             STRIP_USELESS_TYPE_CONVERSION (result);
 373             if (valid_gimple_rhs_p (result))
 374               return result;
 375           }
 376       }
 377       break;
 378
 379     case GIMPLE_BINARY_RHS:
 380       /* Try to canonicalize for boolean-typed X the comparisons
 381          X == 0, X == 1, X != 0, and X != 1.  */
 382       if (gimple_assign_rhs_code (stmt) == EQ_EXPR
 383           || gimple_assign_rhs_code (stmt) == NE_EXPR)
 384         {
 385           tree lhs = gimple_assign_lhs (stmt);
 386           tree op1 = gimple_assign_rhs1 (stmt);
 387           tree op2 = gimple_assign_rhs2 (stmt);
 388           tree type = TREE_TYPE (op1);
 389
 390           /* Check whether the comparison operands are of the same boolean
 391              type as the result type is.
 392              Check that second operand is an integer-constant with value
 393              one or zero.  */
 394           if (TREE_CODE (op2) == INTEGER_CST
 395               && (integer_zerop (op2) || integer_onep (op2))
 396               && useless_type_conversion_p (TREE_TYPE (lhs), type))
 397             {
 398               enum tree_code cmp_code = gimple_assign_rhs_code (stmt);
 399               bool is_logical_not = false;
 400
 401               /* X == 0 and X != 1 is a logical-not.of X
 402                  X == 1 and X != 0 is X  */
 403               if ((cmp_code == EQ_EXPR && integer_zerop (op2))
 404                   || (cmp_code == NE_EXPR && integer_onep (op2)))
 405                 is_logical_not = true;
 406
 407               if (is_logical_not == false)
 408                 result = op1;
 409               /* Only for one-bit precision typed X the transformation
 410                  !X -> ~X is valied.  */
 411               else if (TYPE_PRECISION (type) == 1)
 412                 result = build1_loc (gimple_location (stmt), BIT_NOT_EXPR,
 413                                      type, op1);
 414               /* Otherwise we use !X -> X ^ 1.  */
 415               else
 416                 result = build2_loc (gimple_location (stmt), BIT_XOR_EXPR,
 417                                      type, op1, build_int_cst (type, 1));
 418
 419             }
 420         }
 421
 422       if (!result)
 423         result = fold_binary_loc (loc, subcode,
 424                                   TREE_TYPE (gimple_assign_lhs (stmt)),
 425                                   gimple_assign_rhs1 (stmt),
 426                                   gimple_assign_rhs2 (stmt));
 427
 428       if (result)
 429         {
 430           STRIP_USELESS_TYPE_CONVERSION (result);
 431           if (valid_gimple_rhs_p (result))
 432             return result;
 433         }
 434       break;
 435
 436     case GIMPLE_TERNARY_RHS:
 437       /* Try to fold a conditional expression.  */
 438       if (gimple_assign_rhs_code (stmt) == COND_EXPR)
 439         {
 440           tree op0 = gimple_assign_rhs1 (stmt);
 441           tree tem;
 442           bool set = false;
 443           location_t cond_loc = gimple_location (stmt);
 444
 445           if (COMPARISON_CLASS_P (op0))
 446             {
 447               fold_defer_overflow_warnings ();
 448               tem = fold_binary_loc (cond_loc,
 449                                      TREE_CODE (op0), TREE_TYPE (op0),
 450                                      TREE_OPERAND (op0, 0),
 451                                      TREE_OPERAND (op0, 1));
 452               /* This is actually a conditional expression, not a GIMPLE
 453                  conditional statement, however, the valid_gimple_rhs_p
 454                  test still applies.  */
 455               set = (tem && is_gimple_condexpr (tem)
 456                      && valid_gimple_rhs_p (tem));
 457               fold_undefer_overflow_warnings (set, stmt, 0);
 458             }
 459           else if (is_gimple_min_invariant (op0))
 460             {
 461               tem = op0;
 462               set = true;
 463             }
 464           else
 465             return NULL_TREE;
 466
 467           if (set)
 468             result = fold_build3_loc (cond_loc, COND_EXPR,
 469                                       TREE_TYPE (gimple_assign_lhs (stmt)), tem,
 470                                       gimple_assign_rhs2 (stmt),
 471                                       gimple_assign_rhs3 (stmt));
 472         }
 473
 474       if (!result)
 475         result = fold_ternary_loc (loc, subcode,
 476                                    TREE_TYPE (gimple_assign_lhs (stmt)),
 477                                    gimple_assign_rhs1 (stmt),
 478                                    gimple_assign_rhs2 (stmt),
 479                                    gimple_assign_rhs3 (stmt));
 480
 481       if (result)
 482         {
 483           STRIP_USELESS_TYPE_CONVERSION (result);
 484           if (valid_gimple_rhs_p (result))
 485             return result;
 486         }
 487       break;
 488
 489     case GIMPLE_INVALID_RHS:
 490       gcc_unreachable ();
 491     }
 492
 493   return NULL_TREE;
 494 }
 495
 496 /* Attempt to fold a conditional statement. Return true if any changes were
 497    made. We only attempt to fold the condition expression, and do not perform
 498    any transformation that would require alteration of the cfg.  It is
 499    assumed that the operands have been previously folded.  */
 500
 501 static bool
 502 fold_gimple_cond (gimple stmt)
 503 {
 504   tree result = fold_binary_loc (gimple_location (stmt),
 505                              gimple_cond_code (stmt),
 506                              boolean_type_node,
 507                              gimple_cond_lhs (stmt),
 508                              gimple_cond_rhs (stmt));
 509
 510   if (result)
 511     {
 512       STRIP_USELESS_TYPE_CONVERSION (result);
 513       if (is_gimple_condexpr (result) && valid_gimple_rhs_p (result))
 514         {
 515           gimple_cond_set_condition_from_tree (stmt, result);
 516           return true;
 517         }
 518     }
 519
 520   return false;
 521 }
 522
 523 /* Convert EXPR into a GIMPLE value suitable for substitution on the
 524    RHS of an assignment.  Insert the necessary statements before
 525    iterator *SI_P.  The statement at *SI_P, which must be a GIMPLE_CALL
 526    is replaced.  If the call is expected to produces a result, then it
 527    is replaced by an assignment of the new RHS to the result variable.
 528    If the result is to be ignored, then the call is replaced by a
 529    GIMPLE_NOP.  A proper VDEF chain is retained by making the first
 530    VUSE and the last VDEF of the whole sequence be the same as the replaced
 531    statement and using new SSA names for stores in between.  */
 532
 533 void
 534 gimplify_and_update_call_from_tree (gimple_stmt_iterator *si_p, tree expr)
 535 {
 536   tree lhs;
 537   tree tmp = NULL_TREE;  /* Silence warning.  */
 538   gimple stmt, new_stmt;
 539   gimple_stmt_iterator i;
 540   gimple_seq stmts = gimple_seq_alloc();
 541   struct gimplify_ctx gctx;
 542   gimple last = NULL;
 543   gimple laststore = NULL;
 544   tree reaching_vuse;
 545
 546   stmt = gsi_stmt (*si_p);
 547
 548   gcc_assert (is_gimple_call (stmt));
 549
 550   lhs = gimple_call_lhs (stmt);
 551   reaching_vuse = gimple_vuse (stmt);
 552
 553   push_gimplify_context (&gctx);
 554
 555   if (lhs == NULL_TREE)
 556     {
 557       gimplify_and_add (expr, &stmts);
 558       /* We can end up with folding a memcpy of an empty class assignment
 559          which gets optimized away by C++ gimplification.  */
 560       if (gimple_seq_empty_p (stmts))
 561         {
 562           pop_gimplify_context (NULL);
 563           if (gimple_in_ssa_p (cfun))
 564             {
 565               unlink_stmt_vdef (stmt);
 566               release_defs (stmt);
 567             }
 568           gsi_remove (si_p, true);
 569           return;
 570         }
 571     }
 572   else
 573     tmp = get_initialized_tmp_var (expr, &stmts, NULL);
 574
 575   pop_gimplify_context (NULL);
 576
 577   if (gimple_has_location (stmt))
 578     annotate_all_with_location (stmts, gimple_location (stmt));
 579
 580   /* The replacement can expose previously unreferenced variables.  */
 581   for (i = gsi_start (stmts); !gsi_end_p (i); gsi_next (&i))
 582     {
 583       if (last)
 584         {
 585           gsi_insert_before (si_p, last, GSI_NEW_STMT);
 586           gsi_next (si_p);
 587         }
 588       new_stmt = gsi_stmt (i);
 589       if (gimple_in_ssa_p (cfun))
 590         {
 591           find_new_referenced_vars (new_stmt);
 592           mark_symbols_for_renaming (new_stmt);
 593         }
 594       /* If the new statement has a VUSE, update it with exact SSA name we
 595          know will reach this one.  */
 596       if (gimple_vuse (new_stmt))
 597         {
 598           /* If we've also seen a previous store create a new VDEF for
 599              the latter one, and make that the new reaching VUSE.  */
 600           if (laststore)
 601             {
 602               reaching_vuse = make_ssa_name (gimple_vop (cfun), laststore);
 603               gimple_set_vdef (laststore, reaching_vuse);
 604               update_stmt (laststore);
 605               laststore = NULL;
 606             }
 607           gimple_set_vuse (new_stmt, reaching_vuse);
 608           gimple_set_modified (new_stmt, true);
 609         }
 610       if (gimple_assign_single_p (new_stmt)
 611           && !is_gimple_reg (gimple_assign_lhs (new_stmt)))
 612         {
 613           laststore = new_stmt;
 614         }
 615       last = new_stmt;
 616     }
 617
 618   if (lhs == NULL_TREE)
 619     {
 620       /* If we replace a call without LHS that has a VDEF and our new
 621          sequence ends with a store we must make that store have the same
 622          vdef in order not to break the sequencing.  This can happen
 623          for instance when folding memcpy calls into assignments.  */
 624       if (gimple_vdef (stmt) && laststore)
 625         {
 626           gimple_set_vdef (laststore, gimple_vdef (stmt));
 627           if (TREE_CODE (gimple_vdef (stmt)) == SSA_NAME)
 628             SSA_NAME_DEF_STMT (gimple_vdef (stmt)) = laststore;
 629           update_stmt (laststore);
 630         }
 631       else if (gimple_in_ssa_p (cfun))
 632         {
 633           unlink_stmt_vdef (stmt);
 634           release_defs (stmt);
 635         }
 636       new_stmt = last;
 637     }
 638   else
 639     {
 640       if (last)
 641         {
 642           gsi_insert_before (si_p, last, GSI_NEW_STMT);
 643           gsi_next (si_p);
 644         }
 645       if (laststore && is_gimple_reg (lhs))
 646         {
 647           gimple_set_vdef (laststore, gimple_vdef (stmt));
 648           update_stmt (laststore);
 649           if (TREE_CODE (gimple_vdef (stmt)) == SSA_NAME)
 650             SSA_NAME_DEF_STMT (gimple_vdef (stmt)) = laststore;
 651           laststore = NULL;
 652         }
 653       else if (laststore)
 654         {
 655           reaching_vuse = make_ssa_name (gimple_vop (cfun), laststore);
 656           gimple_set_vdef (laststore, reaching_vuse);
 657           update_stmt (laststore);
 658           laststore = NULL;
 659         }
 660       new_stmt = gimple_build_assign (lhs, tmp);
 661       if (!is_gimple_reg (tmp))
 662         gimple_set_vuse (new_stmt, reaching_vuse);
 663       if (!is_gimple_reg (lhs))
 664         {
 665           gimple_set_vdef (new_stmt, gimple_vdef (stmt));
 666           if (TREE_CODE (gimple_vdef (stmt)) == SSA_NAME)
 667             SSA_NAME_DEF_STMT (gimple_vdef (stmt)) = new_stmt;
 668         }
 669       else if (reaching_vuse == gimple_vuse (stmt))
 670         unlink_stmt_vdef (stmt);
 671     }
 672
 673   gimple_set_location (new_stmt, gimple_location (stmt));
 674   gsi_replace (si_p, new_stmt, false);
 675 }
 676
 677 /* Return the string length, maximum string length or maximum value of
 678    ARG in LENGTH.
 679    If ARG is an SSA name variable, follow its use-def chains.  If LENGTH
 680    is not NULL and, for TYPE == 0, its value is not equal to the length
 681    we determine or if we are unable to determine the length or value,
 682    return false.  VISITED is a bitmap of visited variables.
 683    TYPE is 0 if string length should be returned, 1 for maximum string
 684    length and 2 for maximum value ARG can have.  */
 685
 686 static bool
 687 get_maxval_strlen (tree arg, tree *length, bitmap visited, int type)
 688 {
 689   tree var, val;
 690   gimple def_stmt;
 691
 692   if (TREE_CODE (arg) != SSA_NAME)
 693     {
 694       if (TREE_CODE (arg) == COND_EXPR)
 695         return get_maxval_strlen (COND_EXPR_THEN (arg), length, visited, type)
 696                && get_maxval_strlen (COND_EXPR_ELSE (arg), length, visited, type);
 697       /* We can end up with &(*iftmp_1)[0] here as well, so handle it.  */
 698       else if (TREE_CODE (arg) == ADDR_EXPR
 699                && TREE_CODE (TREE_OPERAND (arg, 0)) == ARRAY_REF
 700                && integer_zerop (TREE_OPERAND (TREE_OPERAND (arg, 0), 1)))
 701         {
 702           tree aop0 = TREE_OPERAND (TREE_OPERAND (arg, 0), 0);
 703           if (TREE_CODE (aop0) == INDIRECT_REF
 704               && TREE_CODE (TREE_OPERAND (aop0, 0)) == SSA_NAME)
 705             return get_maxval_strlen (TREE_OPERAND (aop0, 0),
 706                                       length, visited, type);
 707         }
 708
 709       if (type == 2)
 710         {
 711           val = arg;
 712           if (TREE_CODE (val) != INTEGER_CST
 713               || tree_int_cst_sgn (val) < 0)
 714             return false;
 715         }
 716       else
 717         val = c_strlen (arg, 1);
 718       if (!val)
 719         return false;
 720
 721       if (*length)
 722         {
 723           if (type > 0)
 724             {
 725               if (TREE_CODE (*length) != INTEGER_CST
 726                   || TREE_CODE (val) != INTEGER_CST)
 727                 return false;
 728
 729               if (tree_int_cst_lt (*length, val))
 730                 *length = val;
 731               return true;
 732             }
 733           else if (simple_cst_equal (val, *length) != 1)
 734             return false;
 735         }
 736
 737       *length = val;
 738       return true;
 739     }
 740
 741   /* If we were already here, break the infinite cycle.  */
 742   if (!bitmap_set_bit (visited, SSA_NAME_VERSION (arg)))
 743     return true;
 744
 745   var = arg;
 746   def_stmt = SSA_NAME_DEF_STMT (var);
 747
 748   switch (gimple_code (def_stmt))
 749     {
 750       case GIMPLE_ASSIGN:
 751         /* The RHS of the statement defining VAR must either have a
 752            constant length or come from another SSA_NAME with a constant
 753            length.  */
 754         if (gimple_assign_single_p (def_stmt)
 755             || gimple_assign_unary_nop_p (def_stmt))
 756           {
 757             tree rhs = gimple_assign_rhs1 (def_stmt);
 758             return get_maxval_strlen (rhs, length, visited, type);
 759           }
 760         return false;
 761
 762       case GIMPLE_PHI:
 763         {
 764           /* All the arguments of the PHI node must have the same constant
 765              length.  */
 766           unsigned i;
 767
 768           for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
 769           {
 770             tree arg = gimple_phi_arg (def_stmt, i)->def;
 771
 772             /* If this PHI has itself as an argument, we cannot
 773                determine the string length of this argument.  However,
 774                if we can find a constant string length for the other
 775                PHI args then we can still be sure that this is a
 776                constant string length.  So be optimistic and just
 777                continue with the next argument.  */
 778             if (arg == gimple_phi_result (def_stmt))
 779               continue;
 780
 781             if (!get_maxval_strlen (arg, length, visited, type))
 782               return false;
 783           }
 784         }
 785         return true;
 786
 787       default:
 788         return false;
 789     }
 790 }
 791
 792
 793 /* Fold builtin call in statement STMT.  Returns a simplified tree.
 794    We may return a non-constant expression, including another call
 795    to a different function and with different arguments, e.g.,
 796    substituting memcpy for strcpy when the string length is known.
 797    Note that some builtins expand into inline code that may not
 798    be valid in GIMPLE.  Callers must take care.  */
 799
 800 tree
 801 gimple_fold_builtin (gimple stmt)
 802 {
 803   tree result, val[3];
 804   tree callee, a;
 805   int arg_idx, type;
 806   bitmap visited;
 807   bool ignore;
 808   int nargs;
 809   location_t loc = gimple_location (stmt);
 810
 811   gcc_assert (is_gimple_call (stmt));
 812
 813   ignore = (gimple_call_lhs (stmt) == NULL);
 814
 815   /* First try the generic builtin folder.  If that succeeds, return the
 816      result directly.  */
 817   result = fold_call_stmt (stmt, ignore);
 818   if (result)
 819     {
 820       if (ignore)
 821         STRIP_NOPS (result);
 822       return result;
 823     }
 824
 825   /* Ignore MD builtins.  */
 826   callee = gimple_call_fndecl (stmt);
 827   if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_MD)
 828     return NULL_TREE;
 829
 830   /* If the builtin could not be folded, and it has no argument list,
 831      we're done.  */
 832   nargs = gimple_call_num_args (stmt);
 833   if (nargs == 0)
 834     return NULL_TREE;
 835
 836   /* Limit the work only for builtins we know how to simplify.  */
 837   switch (DECL_FUNCTION_CODE (callee))
 838     {
 839     case BUILT_IN_STRLEN:
 840     case BUILT_IN_FPUTS:
 841     case BUILT_IN_FPUTS_UNLOCKED:
 842       arg_idx = 0;
 843       type = 0;
 844       break;
 845     case BUILT_IN_STRCPY:
 846     case BUILT_IN_STRNCPY:
 847       arg_idx = 1;
 848       type = 0;
 849       break;
 850     case BUILT_IN_MEMCPY_CHK:
 851     case BUILT_IN_MEMPCPY_CHK:
 852     case BUILT_IN_MEMMOVE_CHK:
 853     case BUILT_IN_MEMSET_CHK:
 854     case BUILT_IN_STRNCPY_CHK:
 855       arg_idx = 2;
 856       type = 2;
 857       break;
 858     case BUILT_IN_STRCPY_CHK:
 859     case BUILT_IN_STPCPY_CHK:
 860       arg_idx = 1;
 861       type = 1;
 862       break;
 863     case BUILT_IN_SNPRINTF_CHK:
 864     case BUILT_IN_VSNPRINTF_CHK:
 865       arg_idx = 1;
 866       type = 2;
 867       break;
 868     default:
 869       return NULL_TREE;
 870     }
 871
 872   if (arg_idx >= nargs)
 873     return NULL_TREE;
 874
 875   /* Try to use the dataflow information gathered by the CCP process.  */
 876   visited = BITMAP_ALLOC (NULL);
 877   bitmap_clear (visited);
 878
 879   memset (val, 0, sizeof (val));
 880   a = gimple_call_arg (stmt, arg_idx);
 881   if (!get_maxval_strlen (a, &val[arg_idx], visited, type))
 882     val[arg_idx] = NULL_TREE;
 883
 884   BITMAP_FREE (visited);
 885
 886   result = NULL_TREE;
 887   switch (DECL_FUNCTION_CODE (callee))
 888     {
 889     case BUILT_IN_STRLEN:
 890       if (val[0] && nargs == 1)
 891         {
 892           tree new_val =
 893               fold_convert (TREE_TYPE (gimple_call_lhs (stmt)), val[0]);
 894
 895           /* If the result is not a valid gimple value, or not a cast
 896              of a valid gimple value, then we cannot use the result.  */
 897           if (is_gimple_val (new_val)
 898               || (CONVERT_EXPR_P (new_val)
 899                   && is_gimple_val (TREE_OPERAND (new_val, 0))))
 900             return new_val;
 901         }
 902       break;
 903
 904     case BUILT_IN_STRCPY:
 905       if (val[1] && is_gimple_val (val[1]) && nargs == 2)
 906         result = fold_builtin_strcpy (loc, callee,
 907                                       gimple_call_arg (stmt, 0),
 908                                       gimple_call_arg (stmt, 1),
 909                                       val[1]);
 910       break;
 911
 912     case BUILT_IN_STRNCPY:
 913       if (val[1] && is_gimple_val (val[1]) && nargs == 3)
 914         result = fold_builtin_strncpy (loc, callee,
 915                                        gimple_call_arg (stmt, 0),
 916                                        gimple_call_arg (stmt, 1),
 917                                        gimple_call_arg (stmt, 2),
 918                                        val[1]);
 919       break;
 920
 921     case BUILT_IN_FPUTS:
 922       if (nargs == 2)
 923         result = fold_builtin_fputs (loc, gimple_call_arg (stmt, 0),
 924                                      gimple_call_arg (stmt, 1),
 925                                      ignore, false, val[0]);
 926       break;
 927
 928     case BUILT_IN_FPUTS_UNLOCKED:
 929       if (nargs == 2)
 930         result = fold_builtin_fputs (loc, gimple_call_arg (stmt, 0),
 931                                      gimple_call_arg (stmt, 1),
 932                                      ignore, true, val[0]);
 933       break;
 934
 935     case BUILT_IN_MEMCPY_CHK:
 936     case BUILT_IN_MEMPCPY_CHK:
 937     case BUILT_IN_MEMMOVE_CHK:
 938     case BUILT_IN_MEMSET_CHK:
 939       if (val[2] && is_gimple_val (val[2]) && nargs == 4)
 940         result = fold_builtin_memory_chk (loc, callee,
 941                                           gimple_call_arg (stmt, 0),
 942                                           gimple_call_arg (stmt, 1),
 943                                           gimple_call_arg (stmt, 2),
 944                                           gimple_call_arg (stmt, 3),
 945                                           val[2], ignore,
 946                                           DECL_FUNCTION_CODE (callee));
 947       break;
 948
 949     case BUILT_IN_STRCPY_CHK:
 950     case BUILT_IN_STPCPY_CHK:
 951       if (val[1] && is_gimple_val (val[1]) && nargs == 3)
 952         result = fold_builtin_stxcpy_chk (loc, callee,
 953                                           gimple_call_arg (stmt, 0),
 954                                           gimple_call_arg (stmt, 1),
 955                                           gimple_call_arg (stmt, 2),
 956                                           val[1], ignore,
 957                                           DECL_FUNCTION_CODE (callee));
 958       break;
 959
 960     case BUILT_IN_STRNCPY_CHK:
 961       if (val[2] && is_gimple_val (val[2]) && nargs == 4)
 962         result = fold_builtin_strncpy_chk (loc, gimple_call_arg (stmt, 0),
 963                                            gimple_call_arg (stmt, 1),
 964                                            gimple_call_arg (stmt, 2),
 965                                            gimple_call_arg (stmt, 3),
 966                                            val[2]);
 967       break;
 968
 969     case BUILT_IN_SNPRINTF_CHK:
 970     case BUILT_IN_VSNPRINTF_CHK:
 971       if (val[1] && is_gimple_val (val[1]))
 972         result = gimple_fold_builtin_snprintf_chk (stmt, val[1],
 973                                                    DECL_FUNCTION_CODE (callee));
 974       break;
 975
 976     default:
 977       gcc_unreachable ();
 978     }
 979
 980   if (result && ignore)
 981     result = fold_ignored_result (result);
 982   return result;
 983 }
 984
 985 /* Generate code adjusting the first parameter of a call statement determined
 986    by GSI by DELTA.  */
 987
 988 void
 989 gimple_adjust_this_by_delta (gimple_stmt_iterator *gsi, tree delta)
 990 {
 991   gimple call_stmt = gsi_stmt (*gsi);
 992   tree parm, tmp;
 993   gimple new_stmt;
 994
 995   delta = convert_to_ptrofftype (delta);
 996   gcc_assert (gimple_call_num_args (call_stmt) >= 1);
 997   parm = gimple_call_arg (call_stmt, 0);
 998   gcc_assert (POINTER_TYPE_P (TREE_TYPE (parm)));
 999   tmp = create_tmp_var (TREE_TYPE (parm), NULL);
1000   add_referenced_var (tmp);
1001
1002   tmp = make_ssa_name (tmp, NULL);
1003   new_stmt = gimple_build_assign_with_ops (POINTER_PLUS_EXPR, tmp, parm, delta);
1004   SSA_NAME_DEF_STMT (tmp) = new_stmt;
1005   gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1006   gimple_call_set_arg (call_stmt, 0, tmp);
1007 }
1008
1009 /* Return a binfo to be used for devirtualization of calls based on an object
1010    represented by a declaration (i.e. a global or automatically allocated one)
1011    or NULL if it cannot be found or is not safe.  CST is expected to be an
1012    ADDR_EXPR of such object or the function will return NULL.  Currently it is
1013    safe to use such binfo only if it has no base binfo (i.e. no ancestors).  */
1014
1015 tree
1016 gimple_extract_devirt_binfo_from_cst (tree cst)
1017 {
1018   HOST_WIDE_INT offset, size, max_size;
1019   tree base, type, expected_type, binfo;
1020   bool last_artificial = false;
1021
1022   if (!flag_devirtualize
1023       || TREE_CODE (cst) != ADDR_EXPR
1024       || TREE_CODE (TREE_TYPE (TREE_TYPE (cst))) != RECORD_TYPE)
1025     return NULL_TREE;
1026
1027   cst = TREE_OPERAND (cst, 0);
1028   expected_type = TREE_TYPE (cst);
1029   base = get_ref_base_and_extent (cst, &offset, &size, &max_size);
1030   type = TREE_TYPE (base);
1031   if (!DECL_P (base)
1032       || max_size == -1
1033       || max_size != size
1034       || TREE_CODE (type) != RECORD_TYPE)
1035     return NULL_TREE;
1036
1037   /* Find the sub-object the constant actually refers to and mark whether it is
1038      an artificial one (as opposed to a user-defined one).  */
1039   while (true)
1040     {
1041       HOST_WIDE_INT pos, size;
1042       tree fld;
1043
1044       if (TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (expected_type))
1045         break;
1046       if (offset < 0)
1047         return NULL_TREE;
1048
1049       for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
1050         {
1051           if (TREE_CODE (fld) != FIELD_DECL)
1052             continue;
1053
1054           pos = int_bit_position (fld);
1055           size = tree_low_cst (DECL_SIZE (fld), 1);
1056           if (pos <= offset && (pos + size) > offset)
1057             break;
1058         }
1059       if (!fld || TREE_CODE (TREE_TYPE (fld)) != RECORD_TYPE)
1060         return NULL_TREE;
1061
1062       last_artificial = DECL_ARTIFICIAL (fld);
1063       type = TREE_TYPE (fld);
1064       offset -= pos;
1065     }
1066   /* Artifical sub-objects are ancestors, we do not want to use them for
1067      devirtualization, at least not here.  */
1068   if (last_artificial)
1069     return NULL_TREE;
1070   binfo = TYPE_BINFO (type);
1071   if (!binfo || BINFO_N_BASE_BINFOS (binfo) > 0)
1072     return NULL_TREE;
1073   else
1074     return binfo;
1075 }
1076
1077 /* Attempt to fold a call statement referenced by the statement iterator GSI.
1078    The statement may be replaced by another statement, e.g., if the call
1079    simplifies to a constant value. Return true if any changes were made.
1080    It is assumed that the operands have been previously folded.  */
1081
1082 bool
1083 gimple_fold_call (gimple_stmt_iterator *gsi, bool inplace)
1084 {
1085   gimple stmt = gsi_stmt (*gsi);
1086   tree callee;
1087
1088   /* Check for builtins that CCP can handle using information not
1089      available in the generic fold routines.  */
1090   callee = gimple_call_fndecl (stmt);
1091   if (!inplace && callee && DECL_BUILT_IN (callee))
1092     {
1093       tree result = gimple_fold_builtin (stmt);
1094
1095       if (result)
1096         {
1097           if (!update_call_from_tree (gsi, result))
1098             gimplify_and_update_call_from_tree (gsi, result);
1099           return true;
1100         }
1101     }
1102
1103   /* Check for virtual calls that became direct calls.  */
1104   callee = gimple_call_fn (stmt);
1105   if (callee && TREE_CODE (callee) == OBJ_TYPE_REF)
1106     {
1107       tree binfo, fndecl, obj;
1108       HOST_WIDE_INT token;
1109
1110       if (gimple_call_addr_fndecl (OBJ_TYPE_REF_EXPR (callee)) != NULL_TREE)
1111         {
1112           gimple_call_set_fn (stmt, OBJ_TYPE_REF_EXPR (callee));
1113           return true;
1114         }
1115
1116       obj = OBJ_TYPE_REF_OBJECT (callee);
1117       binfo = gimple_extract_devirt_binfo_from_cst (obj);
1118       if (!binfo)
1119         return false;
1120       token = TREE_INT_CST_LOW (OBJ_TYPE_REF_TOKEN (callee));
1121       fndecl = gimple_get_virt_method_for_binfo (token, binfo);
1122       if (!fndecl)
1123         return false;
1124       gimple_call_set_fndecl (stmt, fndecl);
1125       return true;
1126     }
1127
1128   return false;
1129 }
1130
1131 /* Worker for both fold_stmt and fold_stmt_inplace.  The INPLACE argument
1132    distinguishes both cases.  */
1133
1134 static bool
1135 fold_stmt_1 (gimple_stmt_iterator *gsi, bool inplace)
1136 {
1137   bool changed = false;
1138   gimple stmt = gsi_stmt (*gsi);
1139   unsigned i;
1140   gimple_stmt_iterator gsinext = *gsi;
1141   gimple next_stmt;
1142
1143   gsi_next (&gsinext);
1144   next_stmt = gsi_end_p (gsinext) ? NULL : gsi_stmt (gsinext);
1145
1146   /* Fold the main computation performed by the statement.  */
1147   switch (gimple_code (stmt))
1148     {
1149     case GIMPLE_ASSIGN:
1150       {
1151         unsigned old_num_ops = gimple_num_ops (stmt);
1152         enum tree_code subcode = gimple_assign_rhs_code (stmt);
1153         tree lhs = gimple_assign_lhs (stmt);
1154         tree new_rhs;
1155         /* First canonicalize operand order.  This avoids building new
1156            trees if this is the only thing fold would later do.  */
1157         if ((commutative_tree_code (subcode)
1158              || commutative_ternary_tree_code (subcode))
1159             && tree_swap_operands_p (gimple_assign_rhs1 (stmt),
1160                                      gimple_assign_rhs2 (stmt), false))
1161           {
1162             tree tem = gimple_assign_rhs1 (stmt);
1163             gimple_assign_set_rhs1 (stmt, gimple_assign_rhs2 (stmt));
1164             gimple_assign_set_rhs2 (stmt, tem);
1165             changed = true;
1166           }
1167         new_rhs = fold_gimple_assign (gsi);
1168         if (new_rhs
1169             && !useless_type_conversion_p (TREE_TYPE (lhs),
1170                                            TREE_TYPE (new_rhs)))
1171           new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs);
1172         if (new_rhs
1173             && (!inplace
1174                 || get_gimple_rhs_num_ops (TREE_CODE (new_rhs)) < old_num_ops))
1175           {
1176             gimple_assign_set_rhs_from_tree (gsi, new_rhs);
1177             changed = true;
1178           }
1179         break;
1180       }
1181
1182     case GIMPLE_COND:
1183       changed |= fold_gimple_cond (stmt);
1184       break;
1185
1186     case GIMPLE_CALL:
1187       /* Fold *& in call arguments.  */
1188       for (i = 0; i < gimple_call_num_args (stmt); ++i)
1189         if (REFERENCE_CLASS_P (gimple_call_arg (stmt, i)))
1190           {
1191             tree tmp = maybe_fold_reference (gimple_call_arg (stmt, i), false);
1192             if (tmp)
1193               {
1194                 gimple_call_set_arg (stmt, i, tmp);
1195                 changed = true;
1196               }
1197           }
1198       changed |= gimple_fold_call (gsi, inplace);
1199       break;
1200
1201     case GIMPLE_ASM:
1202       /* Fold *& in asm operands.  */
1203       for (i = 0; i < gimple_asm_noutputs (stmt); ++i)
1204         {
1205           tree link = gimple_asm_output_op (stmt, i);
1206           tree op = TREE_VALUE (link);
1207           if (REFERENCE_CLASS_P (op)
1208               && (op = maybe_fold_reference (op, true)) != NULL_TREE)
1209             {
1210               TREE_VALUE (link) = op;
1211               changed = true;
1212             }
1213         }
1214       for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
1215         {
1216           tree link = gimple_asm_input_op (stmt, i);
1217           tree op = TREE_VALUE (link);
1218           if (REFERENCE_CLASS_P (op)
1219               && (op = maybe_fold_reference (op, false)) != NULL_TREE)
1220             {
1221               TREE_VALUE (link) = op;
1222               changed = true;
1223             }
1224         }
1225       break;
1226
1227     case GIMPLE_DEBUG:
1228       if (gimple_debug_bind_p (stmt))
1229         {
1230           tree val = gimple_debug_bind_get_value (stmt);
1231           if (val
1232               && REFERENCE_CLASS_P (val))
1233             {
1234               tree tem = maybe_fold_reference (val, false);
1235               if (tem)
1236                 {
1237                   gimple_debug_bind_set_value (stmt, tem);
1238                   changed = true;
1239                 }
1240             }
1241         }
1242       break;
1243
1244     default:;
1245     }
1246
1247   /* If stmt folds into nothing and it was the last stmt in a bb,
1248      don't call gsi_stmt.  */
1249   if (gsi_end_p (*gsi))
1250     {
1251       gcc_assert (next_stmt == NULL);
1252       return changed;
1253     }
1254
1255   stmt = gsi_stmt (*gsi);
1256
1257   /* Fold *& on the lhs.  Don't do this if stmt folded into nothing,
1258      as we'd changing the next stmt.  */
1259   if (gimple_has_lhs (stmt) && stmt != next_stmt)
1260     {
1261       tree lhs = gimple_get_lhs (stmt);
1262       if (lhs && REFERENCE_CLASS_P (lhs))
1263         {
1264           tree new_lhs = maybe_fold_reference (lhs, true);
1265           if (new_lhs)
1266             {
1267               gimple_set_lhs (stmt, new_lhs);
1268               changed = true;
1269             }
1270         }
1271     }
1272
1273   return changed;
1274 }
1275
1276 /* Fold the statement pointed to by GSI.  In some cases, this function may
1277    replace the whole statement with a new one.  Returns true iff folding
1278    makes any changes.
1279    The statement pointed to by GSI should be in valid gimple form but may
1280    be in unfolded state as resulting from for example constant propagation
1281    which can produce *&x = 0.  */
1282
1283 bool
1284 fold_stmt (gimple_stmt_iterator *gsi)
1285 {
1286   return fold_stmt_1 (gsi, false);
1287 }
1288
1289 /* Perform the minimal folding on statement *GSI.  Only operations like
1290    *&x created by constant propagation are handled.  The statement cannot
1291    be replaced with a new one.  Return true if the statement was
1292    changed, false otherwise.
1293    The statement *GSI should be in valid gimple form but may
1294    be in unfolded state as resulting from for example constant propagation
1295    which can produce *&x = 0.  */
1296
1297 bool
1298 fold_stmt_inplace (gimple_stmt_iterator *gsi)
1299 {
1300   gimple stmt = gsi_stmt (*gsi);
1301   bool changed = fold_stmt_1 (gsi, true);
1302   gcc_assert (gsi_stmt (*gsi) == stmt);
1303   return changed;
1304 }
1305
1306 /* Canonicalize and possibly invert the boolean EXPR; return NULL_TREE
1307    if EXPR is null or we don't know how.
1308    If non-null, the result always has boolean type.  */
1309
1310 static tree
1311 canonicalize_bool (tree expr, bool invert)
1312 {
1313   if (!expr)
1314     return NULL_TREE;
1315   else if (invert)
1316     {
1317       if (integer_nonzerop (expr))
1318         return boolean_false_node;
1319       else if (integer_zerop (expr))
1320         return boolean_true_node;
1321       else if (TREE_CODE (expr) == SSA_NAME)
1322         return fold_build2 (EQ_EXPR, boolean_type_node, expr,
1323                             build_int_cst (TREE_TYPE (expr), 0));
1324       else if (TREE_CODE_CLASS (TREE_CODE (expr)) == tcc_comparison)
1325         return fold_build2 (invert_tree_comparison (TREE_CODE (expr), false),
1326                             boolean_type_node,
1327                             TREE_OPERAND (expr, 0),
1328                             TREE_OPERAND (expr, 1));
1329       else
1330         return NULL_TREE;
1331     }
1332   else
1333     {
1334       if (TREE_CODE (TREE_TYPE (expr)) == BOOLEAN_TYPE)
1335         return expr;
1336       if (integer_nonzerop (expr))
1337         return boolean_true_node;
1338       else if (integer_zerop (expr))
1339         return boolean_false_node;
1340       else if (TREE_CODE (expr) == SSA_NAME)
1341         return fold_build2 (NE_EXPR, boolean_type_node, expr,
1342                             build_int_cst (TREE_TYPE (expr), 0));
1343       else if (TREE_CODE_CLASS (TREE_CODE (expr)) == tcc_comparison)
1344         return fold_build2 (TREE_CODE (expr),
1345                             boolean_type_node,
1346                             TREE_OPERAND (expr, 0),
1347                             TREE_OPERAND (expr, 1));
1348       else
1349         return NULL_TREE;
1350     }
1351 }
1352
1353 /* Check to see if a boolean expression EXPR is logically equivalent to the
1354    comparison (OP1 CODE OP2).  Check for various identities involving
1355    SSA_NAMEs.  */
1356
1357 static bool
1358 same_bool_comparison_p (const_tree expr, enum tree_code code,
1359                         const_tree op1, const_tree op2)
1360 {
1361   gimple s;
1362
1363   /* The obvious case.  */
1364   if (TREE_CODE (expr) == code
1365       && operand_equal_p (TREE_OPERAND (expr, 0), op1, 0)
1366       && operand_equal_p (TREE_OPERAND (expr, 1), op2, 0))
1367     return true;
1368
1369   /* Check for comparing (name, name != 0) and the case where expr
1370      is an SSA_NAME with a definition matching the comparison.  */
1371   if (TREE_CODE (expr) == SSA_NAME
1372       && TREE_CODE (TREE_TYPE (expr)) == BOOLEAN_TYPE)
1373     {
1374       if (operand_equal_p (expr, op1, 0))
1375         return ((code == NE_EXPR && integer_zerop (op2))
1376                 || (code == EQ_EXPR && integer_nonzerop (op2)));
1377       s = SSA_NAME_DEF_STMT (expr);
1378       if (is_gimple_assign (s)
1379           && gimple_assign_rhs_code (s) == code
1380           && operand_equal_p (gimple_assign_rhs1 (s), op1, 0)
1381           && operand_equal_p (gimple_assign_rhs2 (s), op2, 0))
1382         return true;
1383     }
1384
1385   /* If op1 is of the form (name != 0) or (name == 0), and the definition
1386      of name is a comparison, recurse.  */
1387   if (TREE_CODE (op1) == SSA_NAME
1388       && TREE_CODE (TREE_TYPE (op1)) == BOOLEAN_TYPE)
1389     {
1390       s = SSA_NAME_DEF_STMT (op1);
1391       if (is_gimple_assign (s)
1392           && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
1393         {
1394           enum tree_code c = gimple_assign_rhs_code (s);
1395           if ((c == NE_EXPR && integer_zerop (op2))
1396               || (c == EQ_EXPR && integer_nonzerop (op2)))
1397             return same_bool_comparison_p (expr, c,
1398                                            gimple_assign_rhs1 (s),
1399                                            gimple_assign_rhs2 (s));
1400           if ((c == EQ_EXPR && integer_zerop (op2))
1401               || (c == NE_EXPR && integer_nonzerop (op2)))
1402             return same_bool_comparison_p (expr,
1403                                            invert_tree_comparison (c, false),
1404                                            gimple_assign_rhs1 (s),
1405                                            gimple_assign_rhs2 (s));
1406         }
1407     }
1408   return false;
1409 }
1410
1411 /* Check to see if two boolean expressions OP1 and OP2 are logically
1412    equivalent.  */
1413
1414 static bool
1415 same_bool_result_p (const_tree op1, const_tree op2)
1416 {
1417   /* Simple cases first.  */
1418   if (operand_equal_p (op1, op2, 0))
1419     return true;
1420
1421   /* Check the cases where at least one of the operands is a comparison.
1422      These are a bit smarter than operand_equal_p in that they apply some
1423      identifies on SSA_NAMEs.  */
1424   if (TREE_CODE_CLASS (TREE_CODE (op2)) == tcc_comparison
1425       && same_bool_comparison_p (op1, TREE_CODE (op2),
1426                                  TREE_OPERAND (op2, 0),
1427                                  TREE_OPERAND (op2, 1)))
1428     return true;
1429   if (TREE_CODE_CLASS (TREE_CODE (op1)) == tcc_comparison
1430       && same_bool_comparison_p (op2, TREE_CODE (op1),
1431                                  TREE_OPERAND (op1, 0),
1432                                  TREE_OPERAND (op1, 1)))
1433     return true;
1434
1435   /* Default case.  */
1436   return false;
1437 }
1438
1439 /* Forward declarations for some mutually recursive functions.  */
1440
1441 static tree
1442 and_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
1443                    enum tree_code code2, tree op2a, tree op2b);
1444 static tree
1445 and_var_with_comparison (tree var, bool invert,
1446                          enum tree_code code2, tree op2a, tree op2b);
1447 static tree
1448 and_var_with_comparison_1 (gimple stmt,
1449                            enum tree_code code2, tree op2a, tree op2b);
1450 static tree
1451 or_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
1452                   enum tree_code code2, tree op2a, tree op2b);
1453 static tree
1454 or_var_with_comparison (tree var, bool invert,
1455                         enum tree_code code2, tree op2a, tree op2b);
1456 static tree
1457 or_var_with_comparison_1 (gimple stmt,
1458                           enum tree_code code2, tree op2a, tree op2b);
1459
1460 /* Helper function for and_comparisons_1:  try to simplify the AND of the
1461    ssa variable VAR with the comparison specified by (OP2A CODE2 OP2B).
1462    If INVERT is true, invert the value of the VAR before doing the AND.
1463    Return NULL_EXPR if we can't simplify this to a single expression.  */
1464
1465 static tree
1466 and_var_with_comparison (tree var, bool invert,
1467                          enum tree_code code2, tree op2a, tree op2b)
1468 {
1469   tree t;
1470   gimple stmt = SSA_NAME_DEF_STMT (var);
1471
1472   /* We can only deal with variables whose definitions are assignments.  */
1473   if (!is_gimple_assign (stmt))
1474     return NULL_TREE;
1475
1476   /* If we have an inverted comparison, apply DeMorgan's law and rewrite
1477      !var AND (op2a code2 op2b) => !(var OR !(op2a code2 op2b))
1478      Then we only have to consider the simpler non-inverted cases.  */
1479   if (invert)
1480     t = or_var_with_comparison_1 (stmt,
1481                                   invert_tree_comparison (code2, false),
1482                                   op2a, op2b);
1483   else
1484     t = and_var_with_comparison_1 (stmt, code2, op2a, op2b);
1485   return canonicalize_bool (t, invert);
1486 }
1487
1488 /* Try to simplify the AND of the ssa variable defined by the assignment
1489    STMT with the comparison specified by (OP2A CODE2 OP2B).
1490    Return NULL_EXPR if we can't simplify this to a single expression.  */
1491
1492 static tree
1493 and_var_with_comparison_1 (gimple stmt,
1494                            enum tree_code code2, tree op2a, tree op2b)
1495 {
1496   tree var = gimple_assign_lhs (stmt);
1497   tree true_test_var = NULL_TREE;
1498   tree false_test_var = NULL_TREE;
1499   enum tree_code innercode = gimple_assign_rhs_code (stmt);
1500
1501   /* Check for identities like (var AND (var == 0)) => false.  */
1502   if (TREE_CODE (op2a) == SSA_NAME
1503       && TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE)
1504     {
1505       if ((code2 == NE_EXPR && integer_zerop (op2b))
1506           || (code2 == EQ_EXPR && integer_nonzerop (op2b)))
1507         {
1508           true_test_var = op2a;
1509           if (var == true_test_var)
1510             return var;
1511         }
1512       else if ((code2 == EQ_EXPR && integer_zerop (op2b))
1513                || (code2 == NE_EXPR && integer_nonzerop (op2b)))
1514         {
1515           false_test_var = op2a;
1516           if (var == false_test_var)
1517             return boolean_false_node;
1518         }
1519     }
1520
1521   /* If the definition is a comparison, recurse on it.  */
1522   if (TREE_CODE_CLASS (innercode) == tcc_comparison)
1523     {
1524       tree t = and_comparisons_1 (innercode,
1525                                   gimple_assign_rhs1 (stmt),
1526                                   gimple_assign_rhs2 (stmt),
1527                                   code2,
1528                                   op2a,
1529                                   op2b);
1530       if (t)
1531         return t;
1532     }
1533
1534   /* If the definition is an AND or OR expression, we may be able to
1535      simplify by reassociating.  */
1536   if (TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE
1537       && (innercode == BIT_AND_EXPR || innercode == BIT_IOR_EXPR))
1538     {
1539       tree inner1 = gimple_assign_rhs1 (stmt);
1540       tree inner2 = gimple_assign_rhs2 (stmt);
1541       gimple s;
1542       tree t;
1543       tree partial = NULL_TREE;
1544       bool is_and = (innercode == BIT_AND_EXPR);
1545
1546       /* Check for boolean identities that don't require recursive examination
1547          of inner1/inner2:
1548          inner1 AND (inner1 AND inner2) => inner1 AND inner2 => var
1549          inner1 AND (inner1 OR inner2) => inner1
1550          !inner1 AND (inner1 AND inner2) => false
1551          !inner1 AND (inner1 OR inner2) => !inner1 AND inner2
1552          Likewise for similar cases involving inner2.  */
1553       if (inner1 == true_test_var)
1554         return (is_and ? var : inner1);
1555       else if (inner2 == true_test_var)
1556         return (is_and ? var : inner2);
1557       else if (inner1 == false_test_var)
1558         return (is_and
1559                 ? boolean_false_node
1560                 : and_var_with_comparison (inner2, false, code2, op2a, op2b));
1561       else if (inner2 == false_test_var)
1562         return (is_and
1563                 ? boolean_false_node
1564                 : and_var_with_comparison (inner1, false, code2, op2a, op2b));
1565
1566       /* Next, redistribute/reassociate the AND across the inner tests.
1567          Compute the first partial result, (inner1 AND (op2a code op2b))  */
1568       if (TREE_CODE (inner1) == SSA_NAME
1569           && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner1))
1570           && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
1571           && (t = maybe_fold_and_comparisons (gimple_assign_rhs_code (s),
1572                                               gimple_assign_rhs1 (s),
1573                                               gimple_assign_rhs2 (s),
1574                                               code2, op2a, op2b)))
1575         {
1576           /* Handle the AND case, where we are reassociating:
1577              (inner1 AND inner2) AND (op2a code2 op2b)
1578              => (t AND inner2)
1579              If the partial result t is a constant, we win.  Otherwise
1580              continue on to try reassociating with the other inner test.  */
1581           if (is_and)
1582             {
1583               if (integer_onep (t))
1584                 return inner2;
1585               else if (integer_zerop (t))
1586                 return boolean_false_node;
1587             }
1588
1589           /* Handle the OR case, where we are redistributing:
1590              (inner1 OR inner2) AND (op2a code2 op2b)
1591              => (t OR (inner2 AND (op2a code2 op2b)))  */
1592           else if (integer_onep (t))
1593             return boolean_true_node;
1594
1595           /* Save partial result for later.  */
1596           partial = t;
1597         }
1598
1599       /* Compute the second partial result, (inner2 AND (op2a code op2b)) */
1600       if (TREE_CODE (inner2) == SSA_NAME
1601           && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner2))
1602           && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
1603           && (t = maybe_fold_and_comparisons (gimple_assign_rhs_code (s),
1604                                               gimple_assign_rhs1 (s),
1605                                               gimple_assign_rhs2 (s),
1606                                               code2, op2a, op2b)))
1607         {
1608           /* Handle the AND case, where we are reassociating:
1609              (inner1 AND inner2) AND (op2a code2 op2b)
1610              => (inner1 AND t)  */
1611           if (is_and)
1612             {
1613               if (integer_onep (t))
1614                 return inner1;
1615               else if (integer_zerop (t))
1616                 return boolean_false_node;
1617               /* If both are the same, we can apply the identity
1618                  (x AND x) == x.  */
1619               else if (partial && same_bool_result_p (t, partial))
1620                 return t;
1621             }
1622
1623           /* Handle the OR case. where we are redistributing:
1624              (inner1 OR inner2) AND (op2a code2 op2b)
1625              => (t OR (inner1 AND (op2a code2 op2b)))
1626              => (t OR partial)  */
1627           else
1628             {
1629               if (integer_onep (t))
1630                 return boolean_true_node;
1631               else if (partial)
1632                 {
1633                   /* We already got a simplification for the other
1634                      operand to the redistributed OR expression.  The
1635                      interesting case is when at least one is false.
1636                      Or, if both are the same, we can apply the identity
1637                      (x OR x) == x.  */
1638                   if (integer_zerop (partial))
1639                     return t;
1640                   else if (integer_zerop (t))
1641                     return partial;
1642                   else if (same_bool_result_p (t, partial))
1643                     return t;
1644                 }
1645             }
1646         }
1647     }
1648   return NULL_TREE;
1649 }
1650
1651 /* Try to simplify the AND of two comparisons defined by
1652    (OP1A CODE1 OP1B) and (OP2A CODE2 OP2B), respectively.
1653    If this can be done without constructing an intermediate value,
1654    return the resulting tree; otherwise NULL_TREE is returned.
1655    This function is deliberately asymmetric as it recurses on SSA_DEFs
1656    in the first comparison but not the second.  */
1657
1658 static tree
1659 and_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
1660                    enum tree_code code2, tree op2a, tree op2b)
1661 {
1662   /* First check for ((x CODE1 y) AND (x CODE2 y)).  */
1663   if (operand_equal_p (op1a, op2a, 0)
1664       && operand_equal_p (op1b, op2b, 0))
1665     {
1666       /* Result will be either NULL_TREE, or a combined comparison.  */
1667       tree t = combine_comparisons (UNKNOWN_LOCATION,
1668                                     TRUTH_ANDIF_EXPR, code1, code2,
1669                                     boolean_type_node, op1a, op1b);
1670       if (t)
1671         return t;
1672     }
1673
1674   /* Likewise the swapped case of the above.  */
1675   if (operand_equal_p (op1a, op2b, 0)
1676       && operand_equal_p (op1b, op2a, 0))
1677     {
1678       /* Result will be either NULL_TREE, or a combined comparison.  */
1679       tree t = combine_comparisons (UNKNOWN_LOCATION,
1680                                     TRUTH_ANDIF_EXPR, code1,
1681                                     swap_tree_comparison (code2),
1682                                     boolean_type_node, op1a, op1b);
1683       if (t)
1684         return t;
1685     }
1686
1687   /* If both comparisons are of the same value against constants, we might
1688      be able to merge them.  */
1689   if (operand_equal_p (op1a, op2a, 0)
1690       && TREE_CODE (op1b) == INTEGER_CST
1691       && TREE_CODE (op2b) == INTEGER_CST)
1692     {
1693       int cmp = tree_int_cst_compare (op1b, op2b);
1694
1695       /* If we have (op1a == op1b), we should either be able to
1696          return that or FALSE, depending on whether the constant op1b
1697          also satisfies the other comparison against op2b.  */
1698       if (code1 == EQ_EXPR)
1699         {
1700           bool done = true;
1701           bool val;
1702           switch (code2)
1703             {
1704             case EQ_EXPR: val = (cmp == 0); break;
1705             case NE_EXPR: val = (cmp != 0); break;
1706             case LT_EXPR: val = (cmp < 0); break;
1707             case GT_EXPR: val = (cmp > 0); break;
1708             case LE_EXPR: val = (cmp <= 0); break;
1709             case GE_EXPR: val = (cmp >= 0); break;
1710             default: done = false;
1711             }
1712           if (done)
1713             {
1714               if (val)
1715                 return fold_build2 (code1, boolean_type_node, op1a, op1b);
1716               else
1717                 return boolean_false_node;
1718             }
1719         }
1720       /* Likewise if the second comparison is an == comparison.  */
1721       else if (code2 == EQ_EXPR)
1722         {
1723           bool done = true;
1724           bool val;
1725           switch (code1)
1726             {
1727             case EQ_EXPR: val = (cmp == 0); break;
1728             case NE_EXPR: val = (cmp != 0); break;
1729             case LT_EXPR: val = (cmp > 0); break;
1730             case GT_EXPR: val = (cmp < 0); break;
1731             case LE_EXPR: val = (cmp >= 0); break;
1732             case GE_EXPR: val = (cmp <= 0); break;
1733             default: done = false;
1734             }
1735           if (done)
1736             {
1737               if (val)
1738                 return fold_build2 (code2, boolean_type_node, op2a, op2b);
1739               else
1740                 return boolean_false_node;
1741             }
1742         }
1743
1744       /* Same business with inequality tests.  */
1745       else if (code1 == NE_EXPR)
1746         {
1747           bool val;
1748           switch (code2)
1749             {
1750             case EQ_EXPR: val = (cmp != 0); break;
1751             case NE_EXPR: val = (cmp == 0); break;
1752             case LT_EXPR: val = (cmp >= 0); break;
1753             case GT_EXPR: val = (cmp <= 0); break;
1754             case LE_EXPR: val = (cmp > 0); break;
1755             case GE_EXPR: val = (cmp < 0); break;
1756             default:
1757               val = false;
1758             }
1759           if (val)
1760             return fold_build2 (code2, boolean_type_node, op2a, op2b);
1761         }
1762       else if (code2 == NE_EXPR)
1763         {
1764           bool val;
1765           switch (code1)
1766             {
1767             case EQ_EXPR: val = (cmp == 0); break;
1768             case NE_EXPR: val = (cmp != 0); break;
1769             case LT_EXPR: val = (cmp <= 0); break;
1770             case GT_EXPR: val = (cmp >= 0); break;
1771             case LE_EXPR: val = (cmp < 0); break;
1772             case GE_EXPR: val = (cmp > 0); break;
1773             default:
1774               val = false;
1775             }
1776           if (val)
1777             return fold_build2 (code1, boolean_type_node, op1a, op1b);
1778         }
1779
1780       /* Chose the more restrictive of two < or <= comparisons.  */
1781       else if ((code1 == LT_EXPR || code1 == LE_EXPR)
1782                && (code2 == LT_EXPR || code2 == LE_EXPR))
1783         {
1784           if ((cmp < 0) || (cmp == 0 && code1 == LT_EXPR))
1785             return fold_build2 (code1, boolean_type_node, op1a, op1b);
1786           else
1787             return fold_build2 (code2, boolean_type_node, op2a, op2b);
1788         }
1789
1790       /* Likewise chose the more restrictive of two > or >= comparisons.  */
1791       else if ((code1 == GT_EXPR || code1 == GE_EXPR)
1792                && (code2 == GT_EXPR || code2 == GE_EXPR))
1793         {
1794           if ((cmp > 0) || (cmp == 0 && code1 == GT_EXPR))
1795             return fold_build2 (code1, boolean_type_node, op1a, op1b);
1796           else
1797             return fold_build2 (code2, boolean_type_node, op2a, op2b);
1798         }
1799
1800       /* Check for singleton ranges.  */
1801       else if (cmp == 0
1802                && ((code1 == LE_EXPR && code2 == GE_EXPR)
1803                    || (code1 == GE_EXPR && code2 == LE_EXPR)))
1804         return fold_build2 (EQ_EXPR, boolean_type_node, op1a, op2b);
1805
1806       /* Check for disjoint ranges. */
1807       else if (cmp <= 0
1808                && (code1 == LT_EXPR || code1 == LE_EXPR)
1809                && (code2 == GT_EXPR || code2 == GE_EXPR))
1810         return boolean_false_node;
1811       else if (cmp >= 0
1812                && (code1 == GT_EXPR || code1 == GE_EXPR)
1813                && (code2 == LT_EXPR || code2 == LE_EXPR))
1814         return boolean_false_node;
1815     }
1816
1817   /* Perhaps the first comparison is (NAME != 0) or (NAME == 1) where
1818      NAME's definition is a truth value.  See if there are any simplifications
1819      that can be done against the NAME's definition.  */
1820   if (TREE_CODE (op1a) == SSA_NAME
1821       && (code1 == NE_EXPR || code1 == EQ_EXPR)
1822       && (integer_zerop (op1b) || integer_onep (op1b)))
1823     {
1824       bool invert = ((code1 == EQ_EXPR && integer_zerop (op1b))
1825                      || (code1 == NE_EXPR && integer_onep (op1b)));
1826       gimple stmt = SSA_NAME_DEF_STMT (op1a);
1827       switch (gimple_code (stmt))
1828         {
1829         case GIMPLE_ASSIGN:
1830           /* Try to simplify by copy-propagating the definition.  */
1831           return and_var_with_comparison (op1a, invert, code2, op2a, op2b);
1832
1833         case GIMPLE_PHI:
1834           /* If every argument to the PHI produces the same result when
1835              ANDed with the second comparison, we win.
1836              Do not do this unless the type is bool since we need a bool
1837              result here anyway.  */
1838           if (TREE_CODE (TREE_TYPE (op1a)) == BOOLEAN_TYPE)
1839             {
1840               tree result = NULL_TREE;
1841               unsigned i;
1842               for (i = 0; i < gimple_phi_num_args (stmt); i++)
1843                 {
1844                   tree arg = gimple_phi_arg_def (stmt, i);
1845
1846                   /* If this PHI has itself as an argument, ignore it.
1847                      If all the other args produce the same result,
1848                      we're still OK.  */
1849                   if (arg == gimple_phi_result (stmt))
1850                     continue;
1851                   else if (TREE_CODE (arg) == INTEGER_CST)
1852                     {
1853                       if (invert ? integer_nonzerop (arg) : integer_zerop (arg))
1854                         {
1855                           if (!result)
1856                             result = boolean_false_node;
1857                           else if (!integer_zerop (result))
1858                             return NULL_TREE;
1859                         }
1860                       else if (!result)
1861                         result = fold_build2 (code2, boolean_type_node,
1862                                               op2a, op2b);
1863                       else if (!same_bool_comparison_p (result,
1864                                                         code2, op2a, op2b))
1865                         return NULL_TREE;
1866                     }
1867                   else if (TREE_CODE (arg) == SSA_NAME
1868                            && !SSA_NAME_IS_DEFAULT_DEF (arg))
1869                     {
1870                       tree temp;
1871                       gimple def_stmt = SSA_NAME_DEF_STMT (arg);
1872                       /* In simple cases we can look through PHI nodes,
1873                          but we have to be careful with loops.
1874                          See PR49073.  */
1875                       if (! dom_info_available_p (CDI_DOMINATORS)
1876                           || gimple_bb (def_stmt) == gimple_bb (stmt)
1877                           || dominated_by_p (CDI_DOMINATORS,
1878                                              gimple_bb (def_stmt),
1879                                              gimple_bb (stmt)))
1880                         return NULL_TREE;
1881                       temp = and_var_with_comparison (arg, invert, code2,
1882                                                       op2a, op2b);
1883                       if (!temp)
1884                         return NULL_TREE;
1885                       else if (!result)
1886                         result = temp;
1887                       else if (!same_bool_result_p (result, temp))
1888                         return NULL_TREE;
1889                     }
1890                   else
1891                     return NULL_TREE;
1892                 }
1893               return result;
1894             }
1895
1896         default:
1897           break;
1898         }
1899     }
1900   return NULL_TREE;
1901 }
1902
1903 /* Try to simplify the AND of two comparisons, specified by
1904    (OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
1905    If this can be simplified to a single expression (without requiring
1906    introducing more SSA variables to hold intermediate values),
1907    return the resulting tree.  Otherwise return NULL_TREE.
1908    If the result expression is non-null, it has boolean type.  */
1909
1910 tree
1911 maybe_fold_and_comparisons (enum tree_code code1, tree op1a, tree op1b,
1912                             enum tree_code code2, tree op2a, tree op2b)
1913 {
1914   tree t = and_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
1915   if (t)
1916     return t;
1917   else
1918     return and_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
1919 }
1920
1921 /* Helper function for or_comparisons_1:  try to simplify the OR of the
1922    ssa variable VAR with the comparison specified by (OP2A CODE2 OP2B).
1923    If INVERT is true, invert the value of VAR before doing the OR.
1924    Return NULL_EXPR if we can't simplify this to a single expression.  */
1925
1926 static tree
1927 or_var_with_comparison (tree var, bool invert,
1928                         enum tree_code code2, tree op2a, tree op2b)
1929 {
1930   tree t;
1931   gimple stmt = SSA_NAME_DEF_STMT (var);
1932
1933   /* We can only deal with variables whose definitions are assignments.  */
1934   if (!is_gimple_assign (stmt))
1935     return NULL_TREE;
1936
1937   /* If we have an inverted comparison, apply DeMorgan's law and rewrite
1938      !var OR (op2a code2 op2b) => !(var AND !(op2a code2 op2b))
1939      Then we only have to consider the simpler non-inverted cases.  */
1940   if (invert)
1941     t = and_var_with_comparison_1 (stmt,
1942                                    invert_tree_comparison (code2, false),
1943                                    op2a, op2b);
1944   else
1945     t = or_var_with_comparison_1 (stmt, code2, op2a, op2b);
1946   return canonicalize_bool (t, invert);
1947 }
1948
1949 /* Try to simplify the OR of the ssa variable defined by the assignment
1950    STMT with the comparison specified by (OP2A CODE2 OP2B).
1951    Return NULL_EXPR if we can't simplify this to a single expression.  */
1952
1953 static tree
1954 or_var_with_comparison_1 (gimple stmt,
1955                           enum tree_code code2, tree op2a, tree op2b)
1956 {
1957   tree var = gimple_assign_lhs (stmt);
1958   tree true_test_var = NULL_TREE;
1959   tree false_test_var = NULL_TREE;
1960   enum tree_code innercode = gimple_assign_rhs_code (stmt);
1961
1962   /* Check for identities like (var OR (var != 0)) => true .  */
1963   if (TREE_CODE (op2a) == SSA_NAME
1964       && TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE)
1965     {
1966       if ((code2 == NE_EXPR && integer_zerop (op2b))
1967           || (code2 == EQ_EXPR && integer_nonzerop (op2b)))
1968         {
1969           true_test_var = op2a;
1970           if (var == true_test_var)
1971             return var;
1972         }
1973       else if ((code2 == EQ_EXPR && integer_zerop (op2b))
1974                || (code2 == NE_EXPR && integer_nonzerop (op2b)))
1975         {
1976           false_test_var = op2a;
1977           if (var == false_test_var)
1978             return boolean_true_node;
1979         }
1980     }
1981
1982   /* If the definition is a comparison, recurse on it.  */
1983   if (TREE_CODE_CLASS (innercode) == tcc_comparison)
1984     {
1985       tree t = or_comparisons_1 (innercode,
1986                                  gimple_assign_rhs1 (stmt),
1987                                  gimple_assign_rhs2 (stmt),
1988                                  code2,
1989                                  op2a,
1990                                  op2b);
1991       if (t)
1992         return t;
1993     }
1994
1995   /* If the definition is an AND or OR expression, we may be able to
1996      simplify by reassociating.  */
1997   if (TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE
1998       && (innercode == BIT_AND_EXPR || innercode == BIT_IOR_EXPR))
1999     {
2000       tree inner1 = gimple_assign_rhs1 (stmt);
2001       tree inner2 = gimple_assign_rhs2 (stmt);
2002       gimple s;
2003       tree t;
2004       tree partial = NULL_TREE;
2005       bool is_or = (innercode == BIT_IOR_EXPR);
2006
2007       /* Check for boolean identities that don't require recursive examination
2008          of inner1/inner2:
2009          inner1 OR (inner1 OR inner2) => inner1 OR inner2 => var
2010          inner1 OR (inner1 AND inner2) => inner1
2011          !inner1 OR (inner1 OR inner2) => true
2012          !inner1 OR (inner1 AND inner2) => !inner1 OR inner2
2013       */
2014       if (inner1 == true_test_var)
2015         return (is_or ? var : inner1);
2016       else if (inner2 == true_test_var)
2017         return (is_or ? var : inner2);
2018       else if (inner1 == false_test_var)
2019         return (is_or
2020                 ? boolean_true_node
2021                 : or_var_with_comparison (inner2, false, code2, op2a, op2b));
2022       else if (inner2 == false_test_var)
2023         return (is_or
2024                 ? boolean_true_node
2025                 : or_var_with_comparison (inner1, false, code2, op2a, op2b));
2026
2027       /* Next, redistribute/reassociate the OR across the inner tests.
2028          Compute the first partial result, (inner1 OR (op2a code op2b))  */
2029       if (TREE_CODE (inner1) == SSA_NAME
2030           && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner1))
2031           && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
2032           && (t = maybe_fold_or_comparisons (gimple_assign_rhs_code (s),
2033                                              gimple_assign_rhs1 (s),
2034                                              gimple_assign_rhs2 (s),
2035                                              code2, op2a, op2b)))
2036         {
2037           /* Handle the OR case, where we are reassociating:
2038              (inner1 OR inner2) OR (op2a code2 op2b)
2039              => (t OR inner2)
2040              If the partial result t is a constant, we win.  Otherwise
2041              continue on to try reassociating with the other inner test.  */
2042           if (is_or)
2043             {
2044               if (integer_onep (t))
2045                 return boolean_true_node;
2046               else if (integer_zerop (t))
2047                 return inner2;
2048             }
2049
2050           /* Handle the AND case, where we are redistributing:
2051              (inner1 AND inner2) OR (op2a code2 op2b)
2052              => (t AND (inner2 OR (op2a code op2b)))  */
2053           else if (integer_zerop (t))
2054             return boolean_false_node;
2055
2056           /* Save partial result for later.  */
2057           partial = t;
2058         }
2059
2060       /* Compute the second partial result, (inner2 OR (op2a code op2b)) */
2061       if (TREE_CODE (inner2) == SSA_NAME
2062           && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner2))
2063           && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
2064           && (t = maybe_fold_or_comparisons (gimple_assign_rhs_code (s),
2065                                              gimple_assign_rhs1 (s),
2066                                              gimple_assign_rhs2 (s),
2067                                              code2, op2a, op2b)))
2068         {
2069           /* Handle the OR case, where we are reassociating:
2070              (inner1 OR inner2) OR (op2a code2 op2b)
2071              => (inner1 OR t)
2072              => (t OR partial)  */
2073           if (is_or)
2074             {
2075               if (integer_zerop (t))
2076                 return inner1;
2077               else if (integer_onep (t))
2078                 return boolean_true_node;
2079               /* If both are the same, we can apply the identity
2080                  (x OR x) == x.  */
2081               else if (partial && same_bool_result_p (t, partial))
2082                 return t;
2083             }
2084
2085           /* Handle the AND case, where we are redistributing:
2086              (inner1 AND inner2) OR (op2a code2 op2b)
2087              => (t AND (inner1 OR (op2a code2 op2b)))
2088              => (t AND partial)  */
2089           else
2090             {
2091               if (integer_zerop (t))
2092                 return boolean_false_node;
2093               else if (partial)
2094                 {
2095                   /* We already got a simplification for the other
2096                      operand to the redistributed AND expression.  The
2097                      interesting case is when at least one is true.
2098                      Or, if both are the same, we can apply the identity
2099                      (x AND x) == x.  */
2100                   if (integer_onep (partial))
2101                     return t;
2102                   else if (integer_onep (t))
2103                     return partial;
2104                   else if (same_bool_result_p (t, partial))
2105                     return t;
2106                 }
2107             }
2108         }
2109     }
2110   return NULL_TREE;
2111 }
2112
2113 /* Try to simplify the OR of two comparisons defined by
2114    (OP1A CODE1 OP1B) and (OP2A CODE2 OP2B), respectively.
2115    If this can be done without constructing an intermediate value,
2116    return the resulting tree; otherwise NULL_TREE is returned.
2117    This function is deliberately asymmetric as it recurses on SSA_DEFs
2118    in the first comparison but not the second.  */
2119
2120 static tree
2121 or_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
2122                   enum tree_code code2, tree op2a, tree op2b)
2123 {
2124   /* First check for ((x CODE1 y) OR (x CODE2 y)).  */
2125   if (operand_equal_p (op1a, op2a, 0)
2126       && operand_equal_p (op1b, op2b, 0))
2127     {
2128       /* Result will be either NULL_TREE, or a combined comparison.  */
2129       tree t = combine_comparisons (UNKNOWN_LOCATION,
2130                                     TRUTH_ORIF_EXPR, code1, code2,
2131                                     boolean_type_node, op1a, op1b);
2132       if (t)
2133         return t;
2134     }
2135
2136   /* Likewise the swapped case of the above.  */
2137   if (operand_equal_p (op1a, op2b, 0)
2138       && operand_equal_p (op1b, op2a, 0))
2139     {
2140       /* Result will be either NULL_TREE, or a combined comparison.  */
2141       tree t = combine_comparisons (UNKNOWN_LOCATION,
2142                                     TRUTH_ORIF_EXPR, code1,
2143                                     swap_tree_comparison (code2),
2144                                     boolean_type_node, op1a, op1b);
2145       if (t)
2146         return t;
2147     }
2148
2149   /* If both comparisons are of the same value against constants, we might
2150      be able to merge them.  */
2151   if (operand_equal_p (op1a, op2a, 0)
2152       && TREE_CODE (op1b) == INTEGER_CST
2153       && TREE_CODE (op2b) == INTEGER_CST)
2154     {
2155       int cmp = tree_int_cst_compare (op1b, op2b);
2156
2157       /* If we have (op1a != op1b), we should either be able to
2158          return that or TRUE, depending on whether the constant op1b
2159          also satisfies the other comparison against op2b.  */
2160       if (code1 == NE_EXPR)
2161         {
2162           bool done = true;
2163           bool val;
2164           switch (code2)
2165             {
2166             case EQ_EXPR: val = (cmp == 0); break;
2167             case NE_EXPR: val = (cmp != 0); break;
2168             case LT_EXPR: val = (cmp < 0); break;
2169             case GT_EXPR: val = (cmp > 0); break;
2170             case LE_EXPR: val = (cmp <= 0); break;
2171             case GE_EXPR: val = (cmp >= 0); break;
2172             default: done = false;
2173             }
2174           if (done)
2175             {
2176               if (val)
2177                 return boolean_true_node;
2178               else
2179                 return fold_build2 (code1, boolean_type_node, op1a, op1b);
2180             }
2181         }
2182       /* Likewise if the second comparison is a != comparison.  */
2183       else if (code2 == NE_EXPR)
2184         {
2185           bool done = true;
2186           bool val;
2187           switch (code1)
2188             {
2189             case EQ_EXPR: val = (cmp == 0); break;
2190             case NE_EXPR: val = (cmp != 0); break;
2191             case LT_EXPR: val = (cmp > 0); break;
2192             case GT_EXPR: val = (cmp < 0); break;
2193             case LE_EXPR: val = (cmp >= 0); break;
2194             case GE_EXPR: val = (cmp <= 0); break;
2195             default: done = false;
2196             }
2197           if (done)
2198             {
2199               if (val)
2200                 return boolean_true_node;
2201               else
2202                 return fold_build2 (code2, boolean_type_node, op2a, op2b);
2203             }
2204         }
2205
2206       /* See if an equality test is redundant with the other comparison.  */
2207       else if (code1 == EQ_EXPR)
2208         {
2209           bool val;
2210           switch (code2)
2211             {
2212             case EQ_EXPR: val = (cmp == 0); break;
2213             case NE_EXPR: val = (cmp != 0); break;
2214             case LT_EXPR: val = (cmp < 0); break;
2215             case GT_EXPR: val = (cmp > 0); break;
2216             case LE_EXPR: val = (cmp <= 0); break;
2217             case GE_EXPR: val = (cmp >= 0); break;
2218             default:
2219               val = false;
2220             }
2221           if (val)
2222             return fold_build2 (code2, boolean_type_node, op2a, op2b);
2223         }
2224       else if (code2 == EQ_EXPR)
2225         {
2226           bool val;
2227           switch (code1)
2228             {
2229             case EQ_EXPR: val = (cmp == 0); break;
2230             case NE_EXPR: val = (cmp != 0); break;
2231             case LT_EXPR: val = (cmp > 0); break;
2232             case GT_EXPR: val = (cmp < 0); break;
2233             case LE_EXPR: val = (cmp >= 0); break;
2234             case GE_EXPR: val = (cmp <= 0); break;
2235             default:
2236               val = false;
2237             }
2238           if (val)
2239             return fold_build2 (code1, boolean_type_node, op1a, op1b);
2240         }
2241
2242       /* Chose the less restrictive of two < or <= comparisons.  */
2243       else if ((code1 == LT_EXPR || code1 == LE_EXPR)
2244                && (code2 == LT_EXPR || code2 == LE_EXPR))
2245         {
2246           if ((cmp < 0) || (cmp == 0 && code1 == LT_EXPR))
2247             return fold_build2 (code2, boolean_type_node, op2a, op2b);
2248           else
2249             return fold_build2 (code1, boolean_type_node, op1a, op1b);
2250         }
2251
2252       /* Likewise chose the less restrictive of two > or >= comparisons.  */
2253       else if ((code1 == GT_EXPR || code1 == GE_EXPR)
2254                && (code2 == GT_EXPR || code2 == GE_EXPR))
2255         {
2256           if ((cmp > 0) || (cmp == 0 && code1 == GT_EXPR))
2257             return fold_build2 (code2, boolean_type_node, op2a, op2b);
2258           else
2259             return fold_build2 (code1, boolean_type_node, op1a, op1b);
2260         }
2261
2262       /* Check for singleton ranges.  */
2263       else if (cmp == 0
2264                && ((code1 == LT_EXPR && code2 == GT_EXPR)
2265                    || (code1 == GT_EXPR && code2 == LT_EXPR)))
2266         return fold_build2 (NE_EXPR, boolean_type_node, op1a, op2b);
2267
2268       /* Check for less/greater pairs that don't restrict the range at all.  */
2269       else if (cmp >= 0
2270                && (code1 == LT_EXPR || code1 == LE_EXPR)
2271                && (code2 == GT_EXPR || code2 == GE_EXPR))
2272         return boolean_true_node;
2273       else if (cmp <= 0
2274                && (code1 == GT_EXPR || code1 == GE_EXPR)
2275                && (code2 == LT_EXPR || code2 == LE_EXPR))
2276         return boolean_true_node;
2277     }
2278
2279   /* Perhaps the first comparison is (NAME != 0) or (NAME == 1) where
2280      NAME's definition is a truth value.  See if there are any simplifications
2281      that can be done against the NAME's definition.  */
2282   if (TREE_CODE (op1a) == SSA_NAME
2283       && (code1 == NE_EXPR || code1 == EQ_EXPR)
2284       && (integer_zerop (op1b) || integer_onep (op1b)))
2285     {
2286       bool invert = ((code1 == EQ_EXPR && integer_zerop (op1b))
2287                      || (code1 == NE_EXPR && integer_onep (op1b)));
2288       gimple stmt = SSA_NAME_DEF_STMT (op1a);
2289       switch (gimple_code (stmt))
2290         {
2291         case GIMPLE_ASSIGN:
2292           /* Try to simplify by copy-propagating the definition.  */
2293           return or_var_with_comparison (op1a, invert, code2, op2a, op2b);
2294
2295         case GIMPLE_PHI:
2296           /* If every argument to the PHI produces the same result when
2297              ORed with the second comparison, we win.
2298              Do not do this unless the type is bool since we need a bool
2299              result here anyway.  */
2300           if (TREE_CODE (TREE_TYPE (op1a)) == BOOLEAN_TYPE)
2301             {
2302               tree result = NULL_TREE;
2303               unsigned i;
2304               for (i = 0; i < gimple_phi_num_args (stmt); i++)
2305                 {
2306                   tree arg = gimple_phi_arg_def (stmt, i);
2307
2308                   /* If this PHI has itself as an argument, ignore it.
2309                      If all the other args produce the same result,
2310                      we're still OK.  */
2311                   if (arg == gimple_phi_result (stmt))
2312                     continue;
2313                   else if (TREE_CODE (arg) == INTEGER_CST)
2314                     {
2315                       if (invert ? integer_zerop (arg) : integer_nonzerop (arg))
2316                         {
2317                           if (!result)
2318                             result = boolean_true_node;
2319                           else if (!integer_onep (result))
2320                             return NULL_TREE;
2321                         }
2322                       else if (!result)
2323                         result = fold_build2 (code2, boolean_type_node,
2324                                               op2a, op2b);
2325                       else if (!same_bool_comparison_p (result,
2326                                                         code2, op2a, op2b))
2327                         return NULL_TREE;
2328                     }
2329                   else if (TREE_CODE (arg) == SSA_NAME
2330                            && !SSA_NAME_IS_DEFAULT_DEF (arg))
2331                     {
2332                       tree temp;
2333                       gimple def_stmt = SSA_NAME_DEF_STMT (arg);
2334                       /* In simple cases we can look through PHI nodes,
2335                          but we have to be careful with loops.
2336                          See PR49073.  */
2337                       if (! dom_info_available_p (CDI_DOMINATORS)
2338                           || gimple_bb (def_stmt) == gimple_bb (stmt)
2339                           || dominated_by_p (CDI_DOMINATORS,
2340                                              gimple_bb (def_stmt),
2341                                              gimple_bb (stmt)))
2342                         return NULL_TREE;
2343                       temp = or_var_with_comparison (arg, invert, code2,
2344                                                      op2a, op2b);
2345                       if (!temp)
2346                         return NULL_TREE;
2347                       else if (!result)
2348                         result = temp;
2349                       else if (!same_bool_result_p (result, temp))
2350                         return NULL_TREE;
2351                     }
2352                   else
2353                     return NULL_TREE;
2354                 }
2355               return result;
2356             }
2357
2358         default:
2359           break;
2360         }
2361     }
2362   return NULL_TREE;
2363 }
2364
2365 /* Try to simplify the OR of two comparisons, specified by
2366    (OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
2367    If this can be simplified to a single expression (without requiring
2368    introducing more SSA variables to hold intermediate values),
2369    return the resulting tree.  Otherwise return NULL_TREE.
2370    If the result expression is non-null, it has boolean type.  */
2371
2372 tree
2373 maybe_fold_or_comparisons (enum tree_code code1, tree op1a, tree op1b,
2374                            enum tree_code code2, tree op2a, tree op2b)
2375 {
2376   tree t = or_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
2377   if (t)
2378     return t;
2379   else
2380     return or_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
2381 }
2382
2383
2384 /* Fold STMT to a constant using VALUEIZE to valueize SSA names.
2385
2386    Either NULL_TREE, a simplified but non-constant or a constant
2387    is returned.
2388
2389    ???  This should go into a gimple-fold-inline.h file to be eventually
2390    privatized with the single valueize function used in the various TUs
2391    to avoid the indirect function call overhead.  */
2392
2393 tree
2394 gimple_fold_stmt_to_constant_1 (gimple stmt, tree (*valueize) (tree))
2395 {
2396   location_t loc = gimple_location (stmt);
2397   switch (gimple_code (stmt))
2398     {
2399     case GIMPLE_ASSIGN:
2400       {
2401         enum tree_code subcode = gimple_assign_rhs_code (stmt);
2402
2403         switch (get_gimple_rhs_class (subcode))
2404           {
2405           case GIMPLE_SINGLE_RHS:
2406             {
2407               tree rhs = gimple_assign_rhs1 (stmt);
2408               enum tree_code_class kind = TREE_CODE_CLASS (subcode);
2409
2410               if (TREE_CODE (rhs) == SSA_NAME)
2411                 {
2412                   /* If the RHS is an SSA_NAME, return its known constant value,
2413                      if any.  */
2414                   return (*valueize) (rhs);
2415                 }
2416               /* Handle propagating invariant addresses into address
2417                  operations.  */
2418               else if (TREE_CODE (rhs) == ADDR_EXPR
2419                        && !is_gimple_min_invariant (rhs))
2420                 {
2421                   HOST_WIDE_INT offset;
2422                   tree base;
2423                   base = get_addr_base_and_unit_offset_1 (TREE_OPERAND (rhs, 0),
2424                                                           &offset,
2425                                                           valueize);
2426                   if (base
2427                       && (CONSTANT_CLASS_P (base)
2428                           || decl_address_invariant_p (base)))
2429                     return build_invariant_address (TREE_TYPE (rhs),
2430                                                     base, offset);
2431                 }
2432               else if (TREE_CODE (rhs) == CONSTRUCTOR
2433                        && TREE_CODE (TREE_TYPE (rhs)) == VECTOR_TYPE
2434                        && (CONSTRUCTOR_NELTS (rhs)
2435                            == TYPE_VECTOR_SUBPARTS (TREE_TYPE (rhs))))
2436                 {
2437                   unsigned i;
2438                   tree val, list;
2439
2440                   list = NULL_TREE;
2441                   FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (rhs), i, val)
2442                     {
2443                       val = (*valueize) (val);
2444                       if (TREE_CODE (val) == INTEGER_CST
2445                           || TREE_CODE (val) == REAL_CST
2446                           || TREE_CODE (val) == FIXED_CST)
2447                         list = tree_cons (NULL_TREE, val, list);
2448                       else
2449                         return NULL_TREE;
2450                     }
2451
2452                   return build_vector (TREE_TYPE (rhs), nreverse (list));
2453                 }
2454
2455               if (kind == tcc_reference)
2456                 {
2457                   if ((TREE_CODE (rhs) == VIEW_CONVERT_EXPR
2458                        || TREE_CODE (rhs) == REALPART_EXPR
2459                        || TREE_CODE (rhs) == IMAGPART_EXPR)
2460                       && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
2461                     {
2462                       tree val = (*valueize) (TREE_OPERAND (rhs, 0));
2463                       return fold_unary_loc (EXPR_LOCATION (rhs),
2464                                              TREE_CODE (rhs),
2465                                              TREE_TYPE (rhs), val);
2466                     }
2467                   else if (TREE_CODE (rhs) == BIT_FIELD_REF
2468                            && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
2469                     {
2470                       tree val = (*valueize) (TREE_OPERAND (rhs, 0));
2471                       return fold_ternary_loc (EXPR_LOCATION (rhs),
2472                                                TREE_CODE (rhs),
2473                                                TREE_TYPE (rhs), val,
2474                                                TREE_OPERAND (rhs, 1),
2475                                                TREE_OPERAND (rhs, 2));
2476                     }
2477                   else if (TREE_CODE (rhs) == MEM_REF
2478                            && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
2479                     {
2480                       tree val = (*valueize) (TREE_OPERAND (rhs, 0));
2481                       if (TREE_CODE (val) == ADDR_EXPR
2482                           && is_gimple_min_invariant (val))
2483                         {
2484                           tree tem = fold_build2 (MEM_REF, TREE_TYPE (rhs),
2485                                                   unshare_expr (val),
2486                                                   TREE_OPERAND (rhs, 1));
2487                           if (tem)
2488                             rhs = tem;
2489                         }
2490                     }
2491                   return fold_const_aggregate_ref_1 (rhs, valueize);
2492                 }
2493               else if (kind == tcc_declaration)
2494                 return get_symbol_constant_value (rhs);
2495               return rhs;
2496             }
2497
2498           case GIMPLE_UNARY_RHS:
2499             {
2500               /* Handle unary operators that can appear in GIMPLE form.
2501                  Note that we know the single operand must be a constant,
2502                  so this should almost always return a simplified RHS.  */
2503               tree lhs = gimple_assign_lhs (stmt);
2504               tree op0 = (*valueize) (gimple_assign_rhs1 (stmt));
2505
2506               /* Conversions are useless for CCP purposes if they are
2507                  value-preserving.  Thus the restrictions that
2508                  useless_type_conversion_p places for restrict qualification
2509                  of pointer types should not apply here.
2510                  Substitution later will only substitute to allowed places.  */
2511               if (CONVERT_EXPR_CODE_P (subcode)
2512                   && POINTER_TYPE_P (TREE_TYPE (lhs))
2513                   && POINTER_TYPE_P (TREE_TYPE (op0))
2514                   && (TYPE_ADDR_SPACE (TREE_TYPE (lhs))
2515                       == TYPE_ADDR_SPACE (TREE_TYPE (op0))))
2516                 return op0;
2517
2518               return
2519                 fold_unary_ignore_overflow_loc (loc, subcode,
2520                                                 gimple_expr_type (stmt), op0);
2521             }
2522
2523           case GIMPLE_BINARY_RHS:
2524             {
2525               /* Handle binary operators that can appear in GIMPLE form.  */
2526               tree op0 = (*valueize) (gimple_assign_rhs1 (stmt));
2527               tree op1 = (*valueize) (gimple_assign_rhs2 (stmt));
2528
2529               /* Translate &x + CST into an invariant form suitable for
2530                  further propagation.  */
2531               if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR
2532                   && TREE_CODE (op0) == ADDR_EXPR
2533                   && TREE_CODE (op1) == INTEGER_CST)
2534                 {
2535                   tree off = fold_convert (ptr_type_node, op1);
2536                   return build_fold_addr_expr_loc
2537                            (loc,
2538                             fold_build2 (MEM_REF,
2539                                          TREE_TYPE (TREE_TYPE (op0)),
2540                                          unshare_expr (op0), off));
2541                 }
2542
2543               return fold_binary_loc (loc, subcode,
2544                                       gimple_expr_type (stmt), op0, op1);
2545             }
2546
2547           case GIMPLE_TERNARY_RHS:
2548             {
2549               /* Handle ternary operators that can appear in GIMPLE form.  */
2550               tree op0 = (*valueize) (gimple_assign_rhs1 (stmt));
2551               tree op1 = (*valueize) (gimple_assign_rhs2 (stmt));
2552               tree op2 = (*valueize) (gimple_assign_rhs3 (stmt));
2553
2554               return fold_ternary_loc (loc, subcode,
2555                                        gimple_expr_type (stmt), op0, op1, op2);
2556             }
2557
2558           default:
2559             gcc_unreachable ();
2560           }
2561       }
2562
2563     case GIMPLE_CALL:
2564       {
2565         tree fn;
2566
2567         if (gimple_call_internal_p (stmt))
2568           /* No folding yet for these functions.  */
2569           return NULL_TREE;
2570
2571         fn = (*valueize) (gimple_call_fn (stmt));
2572         if (TREE_CODE (fn) == ADDR_EXPR
2573             && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL
2574             && DECL_BUILT_IN (TREE_OPERAND (fn, 0)))
2575           {
2576             tree *args = XALLOCAVEC (tree, gimple_call_num_args (stmt));
2577             tree call, retval;
2578             unsigned i;
2579             for (i = 0; i < gimple_call_num_args (stmt); ++i)
2580               args[i] = (*valueize) (gimple_call_arg (stmt, i));
2581             call = build_call_array_loc (loc,
2582                                          gimple_call_return_type (stmt),
2583                                          fn, gimple_call_num_args (stmt), args);
2584             retval = fold_call_expr (EXPR_LOCATION (call), call, false);
2585             if (retval)
2586               /* fold_call_expr wraps the result inside a NOP_EXPR.  */
2587               STRIP_NOPS (retval);
2588             return retval;
2589           }
2590         return NULL_TREE;
2591       }
2592
2593     default:
2594       return NULL_TREE;
2595     }
2596 }
2597
2598 /* Fold STMT to a constant using VALUEIZE to valueize SSA names.
2599    Returns NULL_TREE if folding to a constant is not possible, otherwise
2600    returns a constant according to is_gimple_min_invariant.  */
2601
2602 tree
2603 gimple_fold_stmt_to_constant (gimple stmt, tree (*valueize) (tree))
2604 {
2605   tree res = gimple_fold_stmt_to_constant_1 (stmt, valueize);
2606   if (res && is_gimple_min_invariant (res))
2607     return res;
2608   return NULL_TREE;
2609 }
2610
2611
2612 /* The following set of functions are supposed to fold references using
2613    their constant initializers.  */
2614
2615 static tree fold_ctor_reference (tree type, tree ctor,
2616                                  unsigned HOST_WIDE_INT offset,
2617                                  unsigned HOST_WIDE_INT size);
2618
2619 /* See if we can find constructor defining value of BASE.
2620    When we know the consructor with constant offset (such as
2621    base is array[40] and we do know constructor of array), then
2622    BIT_OFFSET is adjusted accordingly.
2623
2624    As a special case, return error_mark_node when constructor
2625    is not explicitly available, but it is known to be zero
2626    such as 'static const int a;'.  */
2627 static tree
2628 get_base_constructor (tree base, HOST_WIDE_INT *bit_offset,
2629                       tree (*valueize)(tree))
2630 {
2631   HOST_WIDE_INT bit_offset2, size, max_size;
2632   if (TREE_CODE (base) == MEM_REF)
2633     {
2634       if (!integer_zerop (TREE_OPERAND (base, 1)))
2635         {
2636           if (!host_integerp (TREE_OPERAND (base, 1), 0))
2637             return NULL_TREE;
2638           *bit_offset += (mem_ref_offset (base).low
2639                           * BITS_PER_UNIT);
2640         }
2641
2642       if (valueize
2643           && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
2644         base = valueize (TREE_OPERAND (base, 0));
2645       if (!base || TREE_CODE (base) != ADDR_EXPR)
2646         return NULL_TREE;
2647       base = TREE_OPERAND (base, 0);
2648     }
2649
2650   /* Get a CONSTRUCTOR.  If BASE is a VAR_DECL, get its
2651      DECL_INITIAL.  If BASE is a nested reference into another
2652      ARRAY_REF or COMPONENT_REF, make a recursive call to resolve
2653      the inner reference.  */
2654   switch (TREE_CODE (base))
2655     {
2656     case VAR_DECL:
2657       if (!const_value_known_p (base))
2658         return NULL_TREE;
2659
2660       /* Fallthru.  */
2661     case CONST_DECL:
2662       if (!DECL_INITIAL (base)
2663           && (TREE_STATIC (base) || DECL_EXTERNAL (base)))
2664         return error_mark_node;
2665       return DECL_INITIAL (base);
2666
2667     case ARRAY_REF:
2668     case COMPONENT_REF:
2669       base = get_ref_base_and_extent (base, &bit_offset2, &size, &max_size);
2670       if (max_size == -1 || size != max_size)
2671         return NULL_TREE;
2672       *bit_offset +=  bit_offset2;
2673       return get_base_constructor (base, bit_offset, valueize);
2674
2675     case STRING_CST:
2676     case CONSTRUCTOR:
2677       return base;
2678
2679     default:
2680       return NULL_TREE;
2681     }
2682 }
2683
2684 /* CTOR is STRING_CST.  Fold reference of type TYPE and size SIZE
2685    to the memory at bit OFFSET.
2686
2687    We do only simple job of folding byte accesses.  */
2688
2689 static tree
2690 fold_string_cst_ctor_reference (tree type, tree ctor,
2691                                 unsigned HOST_WIDE_INT offset,
2692                                 unsigned HOST_WIDE_INT size)
2693 {
2694   if (INTEGRAL_TYPE_P (type)
2695       && (TYPE_MODE (type)
2696           == TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
2697       && (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
2698           == MODE_INT)
2699       && GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor)))) == 1
2700       && size == BITS_PER_UNIT
2701       && !(offset % BITS_PER_UNIT))
2702     {
2703       offset /= BITS_PER_UNIT;
2704       if (offset < (unsigned HOST_WIDE_INT) TREE_STRING_LENGTH (ctor))
2705         return build_int_cst_type (type, (TREE_STRING_POINTER (ctor)
2706                                    [offset]));
2707       /* Folding
2708          const char a[20]="hello";
2709          return a[10];
2710
2711          might lead to offset greater than string length.  In this case we
2712          know value is either initialized to 0 or out of bounds.  Return 0
2713          in both cases.  */
2714       return build_zero_cst (type);
2715     }
2716   return NULL_TREE;
2717 }
2718
2719 /* CTOR is CONSTRUCTOR of an array type.  Fold reference of type TYPE and size
2720    SIZE to the memory at bit OFFSET.  */
2721
2722 static tree
2723 fold_array_ctor_reference (tree type, tree ctor,
2724                            unsigned HOST_WIDE_INT offset,
2725                            unsigned HOST_WIDE_INT size)
2726 {
2727   unsigned HOST_WIDE_INT cnt;
2728   tree cfield, cval;
2729   double_int low_bound, elt_size;
2730   double_int index, max_index;
2731   double_int access_index;
2732   tree domain_type = TYPE_DOMAIN (TREE_TYPE (ctor));
2733   HOST_WIDE_INT inner_offset;
2734
2735   /* Compute low bound and elt size.  */
2736   if (domain_type && TYPE_MIN_VALUE (domain_type))
2737     {
2738       /* Static constructors for variably sized objects makes no sense.  */
2739       gcc_assert (TREE_CODE (TYPE_MIN_VALUE (domain_type)) == INTEGER_CST);
2740       low_bound = tree_to_double_int (TYPE_MIN_VALUE (domain_type));
2741     }
2742   else
2743     low_bound = double_int_zero;
2744   /* Static constructors for variably sized objects makes no sense.  */
2745   gcc_assert (TREE_CODE(TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (ctor))))
2746               == INTEGER_CST);
2747   elt_size =
2748     tree_to_double_int (TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (ctor))));
2749
2750
2751   /* We can handle only constantly sized accesses that are known to not
2752      be larger than size of array element.  */
2753   if (!TYPE_SIZE_UNIT (type)
2754       || TREE_CODE (TYPE_SIZE_UNIT (type)) != INTEGER_CST
2755       || double_int_cmp (elt_size,
2756                          tree_to_double_int (TYPE_SIZE_UNIT (type)), 0) < 0)
2757     return NULL_TREE;
2758
2759   /* Compute the array index we look for.  */
2760   access_index = double_int_udiv (uhwi_to_double_int (offset / BITS_PER_UNIT),
2761                                   elt_size, TRUNC_DIV_EXPR);
2762   access_index = double_int_add (access_index, low_bound);
2763
2764   /* And offset within the access.  */
2765   inner_offset = offset % (double_int_to_uhwi (elt_size) * BITS_PER_UNIT);
2766
2767   /* See if the array field is large enough to span whole access.  We do not
2768      care to fold accesses spanning multiple array indexes.  */
2769   if (inner_offset + size > double_int_to_uhwi (elt_size) * BITS_PER_UNIT)
2770     return NULL_TREE;
2771
2772   index = double_int_sub (low_bound, double_int_one);
2773   FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
2774     {
2775       /* Array constructor might explicitely set index, or specify range
2776          or leave index NULL meaning that it is next index after previous
2777          one.  */
2778       if (cfield)
2779         {
2780           if (TREE_CODE (cfield) == INTEGER_CST)
2781             max_index = index = tree_to_double_int (cfield);
2782           else
2783             {
2784               gcc_assert (TREE_CODE (cfield) == RANGE_EXPR);
2785               index = tree_to_double_int (TREE_OPERAND (cfield, 0));
2786               max_index = tree_to_double_int (TREE_OPERAND (cfield, 1));
2787             }
2788         }
2789       else
2790         max_index = index = double_int_add (index, double_int_one);
2791
2792       /* Do we have match?  */
2793       if (double_int_cmp (access_index, index, 1) >= 0
2794           && double_int_cmp (access_index, max_index, 1) <= 0)
2795         return fold_ctor_reference (type, cval, inner_offset, size);
2796     }
2797   /* When memory is not explicitely mentioned in constructor,
2798      it is 0 (or out of range).  */
2799   return build_zero_cst (type);
2800 }
2801
2802 /* CTOR is CONSTRUCTOR of an aggregate or vector.
2803    Fold reference of type TYPE and size SIZE to the memory at bit OFFSET.  */
2804
2805 static tree
2806 fold_nonarray_ctor_reference (tree type, tree ctor,
2807                               unsigned HOST_WIDE_INT offset,
2808                               unsigned HOST_WIDE_INT size)
2809 {
2810   unsigned HOST_WIDE_INT cnt;
2811   tree cfield, cval;
2812
2813   FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield,
2814                             cval)
2815     {
2816       tree byte_offset = DECL_FIELD_OFFSET (cfield);
2817       tree field_offset = DECL_FIELD_BIT_OFFSET (cfield);
2818       tree field_size = DECL_SIZE (cfield);
2819       double_int bitoffset;
2820       double_int byte_offset_cst = tree_to_double_int (byte_offset);
2821       double_int bits_per_unit_cst = uhwi_to_double_int (BITS_PER_UNIT);
2822       double_int bitoffset_end, access_end;
2823
2824       /* Variable sized objects in static constructors makes no sense,
2825          but field_size can be NULL for flexible array members.  */
2826       gcc_assert (TREE_CODE (field_offset) == INTEGER_CST
2827                   && TREE_CODE (byte_offset) == INTEGER_CST
2828                   && (field_size != NULL_TREE
2829                       ? TREE_CODE (field_size) == INTEGER_CST
2830                       : TREE_CODE (TREE_TYPE (cfield)) == ARRAY_TYPE));
2831
2832       /* Compute bit offset of the field.  */
2833       bitoffset = double_int_add (tree_to_double_int (field_offset),
2834                                   double_int_mul (byte_offset_cst,
2835                                                   bits_per_unit_cst));
2836       /* Compute bit offset where the field ends.  */
2837       if (field_size != NULL_TREE)
2838         bitoffset_end = double_int_add (bitoffset,
2839                                         tree_to_double_int (field_size));
2840       else
2841         bitoffset_end = double_int_zero;
2842
2843       access_end = double_int_add (uhwi_to_double_int (offset),
2844                                    uhwi_to_double_int (size));
2845
2846       /* Is there any overlap between [OFFSET, OFFSET+SIZE) and
2847          [BITOFFSET, BITOFFSET_END)?  */
2848       if (double_int_cmp (access_end, bitoffset, 0) > 0
2849           && (field_size == NULL_TREE
2850               || double_int_cmp (uhwi_to_double_int (offset),
2851                                  bitoffset_end, 0) < 0))
2852         {
2853           double_int inner_offset = double_int_sub (uhwi_to_double_int (offset),
2854                                                     bitoffset);
2855           /* We do have overlap.  Now see if field is large enough to
2856              cover the access.  Give up for accesses spanning multiple
2857              fields.  */
2858           if (double_int_cmp (access_end, bitoffset_end, 0) > 0)
2859             return NULL_TREE;
2860           if (double_int_cmp (uhwi_to_double_int (offset), bitoffset, 0) < 0)
2861             return NULL_TREE;
2862           return fold_ctor_reference (type, cval,
2863                                       double_int_to_uhwi (inner_offset), size);
2864         }
2865     }
2866   /* When memory is not explicitely mentioned in constructor, it is 0.  */
2867   return build_zero_cst (type);
2868 }
2869
2870 /* CTOR is value initializing memory, fold reference of type TYPE and size SIZE
2871    to the memory at bit OFFSET.  */
2872
2873 static tree
2874 fold_ctor_reference (tree type, tree ctor, unsigned HOST_WIDE_INT offset,
2875                      unsigned HOST_WIDE_INT size)
2876 {
2877   tree ret;
2878
2879   /* We found the field with exact match.  */
2880   if (useless_type_conversion_p (type, TREE_TYPE (ctor))
2881       && !offset)
2882     return canonicalize_constructor_val (ctor);
2883
2884   /* We are at the end of walk, see if we can view convert the
2885      result.  */
2886   if (!AGGREGATE_TYPE_P (TREE_TYPE (ctor)) && !offset
2887       /* VIEW_CONVERT_EXPR is defined only for matching sizes.  */
2888       && operand_equal_p (TYPE_SIZE (type),
2889                           TYPE_SIZE (TREE_TYPE (ctor)), 0))
2890     {
2891       ret = canonicalize_constructor_val (ctor);
2892       ret = fold_unary (VIEW_CONVERT_EXPR, type, ret);
2893       if (ret)
2894         STRIP_NOPS (ret);
2895       return ret;
2896     }
2897   if (TREE_CODE (ctor) == STRING_CST)
2898     return fold_string_cst_ctor_reference (type, ctor, offset, size);
2899   if (TREE_CODE (ctor) == CONSTRUCTOR)
2900     {
2901
2902       if (TREE_CODE (TREE_TYPE (ctor)) == ARRAY_TYPE)
2903         return fold_array_ctor_reference (type, ctor, offset, size);
2904       else
2905         return fold_nonarray_ctor_reference (type, ctor, offset, size);
2906     }
2907
2908   return NULL_TREE;
2909 }
2910
2911 /* Return the tree representing the element referenced by T if T is an
2912    ARRAY_REF or COMPONENT_REF into constant aggregates valuezing SSA
2913    names using VALUEIZE.  Return NULL_TREE otherwise.  */
2914
2915 tree
2916 fold_const_aggregate_ref_1 (tree t, tree (*valueize) (tree))
2917 {
2918   tree ctor, idx, base;
2919   HOST_WIDE_INT offset, size, max_size;
2920   tree tem;
2921
2922   if (TREE_CODE_CLASS (TREE_CODE (t)) == tcc_declaration)
2923     return get_symbol_constant_value (t);
2924
2925   tem = fold_read_from_constant_string (t);
2926   if (tem)
2927     return tem;
2928
2929   switch (TREE_CODE (t))
2930     {
2931     case ARRAY_REF:
2932     case ARRAY_RANGE_REF:
2933       /* Constant indexes are handled well by get_base_constructor.
2934          Only special case variable offsets.
2935          FIXME: This code can't handle nested references with variable indexes
2936          (they will be handled only by iteration of ccp).  Perhaps we can bring
2937          get_ref_base_and_extent here and make it use a valueize callback.  */
2938       if (TREE_CODE (TREE_OPERAND (t, 1)) == SSA_NAME
2939           && valueize
2940           && (idx = (*valueize) (TREE_OPERAND (t, 1)))
2941           && host_integerp (idx, 0))
2942         {
2943           tree low_bound, unit_size;
2944
2945           /* If the resulting bit-offset is constant, track it.  */
2946           if ((low_bound = array_ref_low_bound (t),
2947                host_integerp (low_bound, 0))
2948               && (unit_size = array_ref_element_size (t),
2949                   host_integerp (unit_size, 1)))
2950             {
2951               offset = TREE_INT_CST_LOW (idx);
2952               offset -= TREE_INT_CST_LOW (low_bound);
2953               offset *= TREE_INT_CST_LOW (unit_size);
2954               offset *= BITS_PER_UNIT;
2955
2956               base = TREE_OPERAND (t, 0);
2957               ctor = get_base_constructor (base, &offset, valueize);
2958               /* Empty constructor.  Always fold to 0.  */
2959               if (ctor == error_mark_node)
2960                 return build_zero_cst (TREE_TYPE (t));
2961               /* Out of bound array access.  Value is undefined,
2962                  but don't fold.  */
2963               if (offset < 0)
2964                 return NULL_TREE;
2965               /* We can not determine ctor.  */
2966               if (!ctor)
2967                 return NULL_TREE;
2968               return fold_ctor_reference (TREE_TYPE (t), ctor, offset,
2969                                           TREE_INT_CST_LOW (unit_size)
2970                                           * BITS_PER_UNIT);
2971             }
2972         }
2973       /* Fallthru.  */
2974
2975     case COMPONENT_REF:
2976     case BIT_FIELD_REF:
2977     case TARGET_MEM_REF:
2978     case MEM_REF:
2979       base = get_ref_base_and_extent (t, &offset, &size, &max_size);
2980       ctor = get_base_constructor (base, &offset, valueize);
2981
2982       /* Empty constructor.  Always fold to 0.  */
2983       if (ctor == error_mark_node)
2984         return build_zero_cst (TREE_TYPE (t));
2985       /* We do not know precise address.  */
2986       if (max_size == -1 || max_size != size)
2987         return NULL_TREE;
2988       /* We can not determine ctor.  */
2989       if (!ctor)
2990         return NULL_TREE;
2991
2992       /* Out of bound array access.  Value is undefined, but don't fold.  */
2993       if (offset < 0)
2994         return NULL_TREE;
2995
2996       return fold_ctor_reference (TREE_TYPE (t), ctor, offset, size);
2997
2998     case REALPART_EXPR:
2999     case IMAGPART_EXPR:
3000       {
3001         tree c = fold_const_aggregate_ref_1 (TREE_OPERAND (t, 0), valueize);
3002         if (c && TREE_CODE (c) == COMPLEX_CST)
3003           return fold_build1_loc (EXPR_LOCATION (t),
3004                               TREE_CODE (t), TREE_TYPE (t), c);
3005         break;
3006       }
3007
3008     default:
3009       break;
3010     }
3011
3012   return NULL_TREE;
3013 }
3014
3015 tree
3016 fold_const_aggregate_ref (tree t)
3017 {
3018   return fold_const_aggregate_ref_1 (t, NULL);
3019 }
3020
3021 /* Return a declaration of a function which an OBJ_TYPE_REF references. TOKEN
3022    is integer form of OBJ_TYPE_REF_TOKEN of the reference expression.
3023    KNOWN_BINFO carries the binfo describing the true type of
3024    OBJ_TYPE_REF_OBJECT(REF).  */
3025
3026 tree
3027 gimple_get_virt_method_for_binfo (HOST_WIDE_INT token, tree known_binfo)
3028 {
3029   unsigned HOST_WIDE_INT offset, size;
3030   tree v, fn;
3031
3032   v = BINFO_VTABLE (known_binfo);
3033   /* If there is no virtual methods table, leave the OBJ_TYPE_REF alone.  */
3034   if (!v)
3035     return NULL_TREE;
3036
3037   if (TREE_CODE (v) == POINTER_PLUS_EXPR)
3038     {
3039       offset = tree_low_cst (TREE_OPERAND (v, 1), 1) * BITS_PER_UNIT;
3040       v = TREE_OPERAND (v, 0);
3041     }
3042   else
3043     offset = 0;
3044
3045   if (TREE_CODE (v) != ADDR_EXPR)
3046     return NULL_TREE;
3047   v = TREE_OPERAND (v, 0);
3048
3049   if (TREE_CODE (v) != VAR_DECL
3050       || !DECL_VIRTUAL_P (v)
3051       || !DECL_INITIAL (v)
3052       || DECL_INITIAL (v) == error_mark_node)
3053     return NULL_TREE;
3054   gcc_checking_assert (TREE_CODE (TREE_TYPE (v)) == ARRAY_TYPE);
3055   size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (v))), 1);
3056   offset += token * size;
3057   fn = fold_ctor_reference (TREE_TYPE (TREE_TYPE (v)), DECL_INITIAL (v),
3058                             offset, size);
3059   if (!fn)
3060     return NULL_TREE;
3061   gcc_assert (TREE_CODE (fn) == ADDR_EXPR
3062               || TREE_CODE (fn) == FDESC_EXPR);
3063   fn = TREE_OPERAND (fn, 0);
3064   gcc_assert (TREE_CODE (fn) == FUNCTION_DECL);
3065
3066   /* When cgraph node is missing and function is not public, we cannot
3067      devirtualize.  This can happen in WHOPR when the actual method
3068      ends up in other partition, because we found devirtualization
3069      possibility too late.  */
3070   if (!can_refer_decl_in_current_unit_p (fn))
3071     return NULL_TREE;
3072
3073   return fn;
3074 }
3075
3076 /* Return true iff VAL is a gimple expression that is known to be
3077    non-negative.  Restricted to floating-point inputs.  */
3078
3079 bool
3080 gimple_val_nonnegative_real_p (tree val)
3081 {
3082   gimple def_stmt;
3083
3084   gcc_assert (val && SCALAR_FLOAT_TYPE_P (TREE_TYPE (val)));
3085
3086   /* Use existing logic for non-gimple trees.  */
3087   if (tree_expr_nonnegative_p (val))
3088     return true;
3089
3090   if (TREE_CODE (val) != SSA_NAME)
3091     return false;
3092
3093   /* Currently we look only at the immediately defining statement
3094      to make this determination, since recursion on defining
3095      statements of operands can lead to quadratic behavior in the
3096      worst case.  This is expected to catch almost all occurrences
3097      in practice.  It would be possible to implement limited-depth
3098      recursion if important cases are lost.  Alternatively, passes
3099      that need this information (such as the pow/powi lowering code
3100      in the cse_sincos pass) could be revised to provide it through
3101      dataflow propagation.  */
3102
3103   def_stmt = SSA_NAME_DEF_STMT (val);
3104
3105   if (is_gimple_assign (def_stmt))
3106     {
3107       tree op0, op1;
3108
3109       /* See fold-const.c:tree_expr_nonnegative_p for additional
3110          cases that could be handled with recursion.  */
3111
3112       switch (gimple_assign_rhs_code (def_stmt))
3113         {
3114         case ABS_EXPR:
3115           /* Always true for floating-point operands.  */
3116           return true;
3117
3118         case MULT_EXPR:
3119           /* True if the two operands are identical (since we are
3120              restricted to floating-point inputs).  */
3121           op0 = gimple_assign_rhs1 (def_stmt);
3122           op1 = gimple_assign_rhs2 (def_stmt);
3123
3124           if (op0 == op1
3125               || operand_equal_p (op0, op1, 0))
3126             return true;
3127
3128         default:
3129           return false;
3130         }
3131     }
3132   else if (is_gimple_call (def_stmt))
3133     {
3134       tree fndecl = gimple_call_fndecl (def_stmt);
3135       if (fndecl
3136           && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
3137         {
3138           tree arg1;
3139
3140           switch (DECL_FUNCTION_CODE (fndecl))
3141             {
3142             CASE_FLT_FN (BUILT_IN_ACOS):
3143             CASE_FLT_FN (BUILT_IN_ACOSH):
3144             CASE_FLT_FN (BUILT_IN_CABS):
3145             CASE_FLT_FN (BUILT_IN_COSH):
3146             CASE_FLT_FN (BUILT_IN_ERFC):
3147             CASE_FLT_FN (BUILT_IN_EXP):
3148             CASE_FLT_FN (BUILT_IN_EXP10):
3149             CASE_FLT_FN (BUILT_IN_EXP2):
3150             CASE_FLT_FN (BUILT_IN_FABS):
3151             CASE_FLT_FN (BUILT_IN_FDIM):
3152             CASE_FLT_FN (BUILT_IN_HYPOT):
3153             CASE_FLT_FN (BUILT_IN_POW10):
3154               return true;
3155
3156             CASE_FLT_FN (BUILT_IN_SQRT):
3157               /* sqrt(-0.0) is -0.0, and sqrt is not defined over other
3158                  nonnegative inputs.  */
3159               if (!HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (val))))
3160                 return true;
3161
3162               break;
3163
3164             CASE_FLT_FN (BUILT_IN_POWI):
3165               /* True if the second argument is an even integer.  */
3166               arg1 = gimple_call_arg (def_stmt, 1);
3167
3168               if (TREE_CODE (arg1) == INTEGER_CST
3169                   && (TREE_INT_CST_LOW (arg1) & 1) == 0)
3170                 return true;
3171
3172               break;
3173
3174             CASE_FLT_FN (BUILT_IN_POW):
3175               /* True if the second argument is an even integer-valued
3176                  real.  */
3177               arg1 = gimple_call_arg (def_stmt, 1);
3178
3179               if (TREE_CODE (arg1) == REAL_CST)
3180                 {
3181                   REAL_VALUE_TYPE c;
3182                   HOST_WIDE_INT n;
3183
3184                   c = TREE_REAL_CST (arg1);
3185                   n = real_to_integer (&c);
3186
3187                   if ((n & 1) == 0)
3188                     {
3189                       REAL_VALUE_TYPE cint;
3190                       real_from_integer (&cint, VOIDmode, n, n < 0 ? -1 : 0, 0);
3191                       if (real_identical (&c, &cint))
3192                         return true;
3193                     }
3194                 }
3195
3196               break;
3197
3198             default:
3199               return false;
3200             }
3201         }
3202     }
3203
3204   return false;
3205 }