contrib/gcc-4.4/gcc/tree-ssa-forwprop.c

   1 /* Forward propagation of expressions for single use variables.
   2    Copyright (C) 2004, 2005, 2007, 2008, 2009 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 3, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "tm.h"
  24 #include "ggc.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "basic-block.h"
  29 #include "timevar.h"
  30 #include "diagnostic.h"
  31 #include "tree-flow.h"
  32 #include "tree-pass.h"
  33 #include "tree-dump.h"
  34 #include "langhooks.h"
  35 #include "flags.h"
  36 #include "gimple.h"
  37
  38 /* This pass propagates the RHS of assignment statements into use
  39    sites of the LHS of the assignment.  It's basically a specialized
  40    form of tree combination.   It is hoped all of this can disappear
  41    when we have a generalized tree combiner.
  42
  43    One class of common cases we handle is forward propagating a single use
  44    variable into a COND_EXPR.
  45
  46      bb0:
  47        x = a COND b;
  48        if (x) goto ... else goto ...
  49
  50    Will be transformed into:
  51
  52      bb0:
  53        if (a COND b) goto ... else goto ...
  54
  55    Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
  56
  57    Or (assuming c1 and c2 are constants):
  58
  59      bb0:
  60        x = a + c1;
  61        if (x EQ/NEQ c2) goto ... else goto ...
  62
  63    Will be transformed into:
  64
  65      bb0:
  66         if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
  67
  68    Similarly for x = a - c1.
  69
  70    Or
  71
  72      bb0:
  73        x = !a
  74        if (x) goto ... else goto ...
  75
  76    Will be transformed into:
  77
  78      bb0:
  79         if (a == 0) goto ... else goto ...
  80
  81    Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
  82    For these cases, we propagate A into all, possibly more than one,
  83    COND_EXPRs that use X.
  84
  85    Or
  86
  87      bb0:
  88        x = (typecast) a
  89        if (x) goto ... else goto ...
  90
  91    Will be transformed into:
  92
  93      bb0:
  94         if (a != 0) goto ... else goto ...
  95
  96    (Assuming a is an integral type and x is a boolean or x is an
  97     integral and a is a boolean.)
  98
  99    Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
 100    For these cases, we propagate A into all, possibly more than one,
 101    COND_EXPRs that use X.
 102
 103    In addition to eliminating the variable and the statement which assigns
 104    a value to the variable, we may be able to later thread the jump without
 105    adding insane complexity in the dominator optimizer.
 106
 107    Also note these transformations can cascade.  We handle this by having
 108    a worklist of COND_EXPR statements to examine.  As we make a change to
 109    a statement, we put it back on the worklist to examine on the next
 110    iteration of the main loop.
 111
 112    A second class of propagation opportunities arises for ADDR_EXPR
 113    nodes.
 114
 115      ptr = &x->y->z;
 116      res = *ptr;
 117
 118    Will get turned into
 119
 120      res = x->y->z;
 121
 122    Or
 123      ptr = (type1*)&type2var;
 124      res = *ptr
 125
 126    Will get turned into (if type1 and type2 are the same size
 127    and neither have volatile on them):
 128      res = VIEW_CONVERT_EXPR<type1>(type2var)
 129
 130    Or
 131
 132      ptr = &x[0];
 133      ptr2 = ptr + <constant>;
 134
 135    Will get turned into
 136
 137      ptr2 = &x[constant/elementsize];
 138
 139   Or
 140
 141      ptr = &x[0];
 142      offset = index * element_size;
 143      offset_p = (pointer) offset;
 144      ptr2 = ptr + offset_p
 145
 146   Will get turned into:
 147
 148      ptr2 = &x[index];
 149
 150   We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to
 151   allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent
 152   {NOT_EXPR,NEG_EXPR}.
 153
 154    This will (of course) be extended as other needs arise.  */
 155
 156 static bool forward_propagate_addr_expr (tree name, tree rhs);
 157
 158 /* Set to true if we delete EH edges during the optimization.  */
 159 static bool cfg_changed;
 160
 161 static tree rhs_to_tree (tree type, gimple stmt);
 162
 163 /* Get the next statement we can propagate NAME's value into skipping
 164    trivial copies.  Returns the statement that is suitable as a
 165    propagation destination or NULL_TREE if there is no such one.
 166    This only returns destinations in a single-use chain.  FINAL_NAME_P
 167    if non-NULL is written to the ssa name that represents the use.  */
 168
 169 static gimple
 170 get_prop_dest_stmt (tree name, tree *final_name_p)
 171 {
 172   use_operand_p use;
 173   gimple use_stmt;
 174
 175   do {
 176     /* If name has multiple uses, bail out.  */
 177     if (!single_imm_use (name, &use, &use_stmt))
 178       return NULL;
 179
 180     /* If this is not a trivial copy, we found it.  */
 181     if (!gimple_assign_copy_p (use_stmt)
 182         || TREE_CODE (gimple_assign_lhs (use_stmt)) != SSA_NAME
 183         || gimple_assign_rhs1 (use_stmt) != name)
 184       break;
 185
 186     /* Continue searching uses of the copy destination.  */
 187     name = gimple_assign_lhs (use_stmt);
 188   } while (1);
 189
 190   if (final_name_p)
 191     *final_name_p = name;
 192
 193   return use_stmt;
 194 }
 195
 196 /* Get the statement we can propagate from into NAME skipping
 197    trivial copies.  Returns the statement which defines the
 198    propagation source or NULL_TREE if there is no such one.
 199    If SINGLE_USE_ONLY is set considers only sources which have
 200    a single use chain up to NAME.  If SINGLE_USE_P is non-null,
 201    it is set to whether the chain to NAME is a single use chain
 202    or not.  SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set.  */
 203
 204 static gimple
 205 get_prop_source_stmt (tree name, bool single_use_only, bool *single_use_p)
 206 {
 207   bool single_use = true;
 208
 209   do {
 210     gimple def_stmt = SSA_NAME_DEF_STMT (name);
 211
 212     if (!has_single_use (name))
 213       {
 214         single_use = false;
 215         if (single_use_only)
 216           return NULL;
 217       }
 218
 219     /* If name is defined by a PHI node or is the default def, bail out.  */
 220     if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
 221       return NULL;
 222
 223     /* If name is not a simple copy destination, we found it.  */
 224     if (!gimple_assign_copy_p (def_stmt)
 225         || TREE_CODE (gimple_assign_rhs1 (def_stmt)) != SSA_NAME)
 226       {
 227         tree rhs;
 228
 229         if (!single_use_only && single_use_p)
 230           *single_use_p = single_use;
 231
 232         /* We can look through pointer conversions in the search
 233            for a useful stmt for the comparison folding.  */
 234         rhs = gimple_assign_rhs1 (def_stmt);
 235         if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
 236             && TREE_CODE (rhs) == SSA_NAME
 237             && POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (def_stmt)))
 238             && POINTER_TYPE_P (TREE_TYPE (rhs)))
 239           name = rhs;
 240         else
 241           return def_stmt;
 242       }
 243     else
 244       {
 245         /* Continue searching the def of the copy source name.  */
 246         name = gimple_assign_rhs1 (def_stmt);
 247       }
 248   } while (1);
 249 }
 250
 251 /* Checks if the destination ssa name in DEF_STMT can be used as
 252    propagation source.  Returns true if so, otherwise false.  */
 253
 254 static bool
 255 can_propagate_from (gimple def_stmt)
 256 {
 257   use_operand_p use_p;
 258   ssa_op_iter iter;
 259
 260   gcc_assert (is_gimple_assign (def_stmt));
 261   /* If the rhs has side-effects we cannot propagate from it.  */
 262   if (gimple_has_volatile_ops (def_stmt))
 263     return false;
 264
 265   /* If the rhs is a load we cannot propagate from it.  */
 266   if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_reference
 267       || TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_declaration)
 268     return false;
 269
 270   /* Constants can be always propagated.  */
 271   if (is_gimple_min_invariant
 272       (rhs_to_tree (TREE_TYPE (gimple_assign_lhs (def_stmt)), def_stmt)))
 273     return true;
 274
 275   /* We cannot propagate ssa names that occur in abnormal phi nodes.  */
 276   FOR_EACH_SSA_USE_OPERAND (use_p, def_stmt, iter, SSA_OP_USE)
 277     if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
 278       return false;
 279
 280   /* If the definition is a conversion of a pointer to a function type,
 281      then we can not apply optimizations as some targets require
 282      function pointers to be canonicalized and in this case this
 283      optimization could eliminate a necessary canonicalization.  */
 284   if (is_gimple_assign (def_stmt)
 285       && (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))))
 286     {
 287       tree rhs = gimple_assign_rhs1 (def_stmt);
 288       if (POINTER_TYPE_P (TREE_TYPE (rhs))
 289           && TREE_CODE (TREE_TYPE (TREE_TYPE (rhs))) == FUNCTION_TYPE)
 290         return false;
 291     }
 292   return true;
 293 }
 294
 295 /* Remove a copy chain ending in NAME along the defs but not
 296    further or including UP_TO_STMT.  If NAME was replaced in
 297    its only use then this function can be used to clean up
 298    dead stmts.  Returns true if UP_TO_STMT can be removed
 299    as well, otherwise false.  */
 300
 301 static bool
 302 remove_prop_source_from_use (tree name, gimple up_to_stmt)
 303 {
 304   gimple_stmt_iterator gsi;
 305   gimple stmt;
 306
 307   do {
 308     if (!has_zero_uses (name))
 309       return false;
 310
 311     stmt = SSA_NAME_DEF_STMT (name);
 312     if (stmt == up_to_stmt)
 313       return true;
 314
 315     gsi = gsi_for_stmt (stmt);
 316     release_defs (stmt);
 317     gsi_remove (&gsi, true);
 318
 319     name = (gimple_assign_copy_p (stmt)) ? gimple_assign_rhs1 (stmt) : NULL;
 320   } while (name && TREE_CODE (name) == SSA_NAME);
 321
 322   return false;
 323 }
 324
 325 /* Return the rhs of a gimple_assign STMT in a form of a single tree,
 326    converted to type TYPE.
 327
 328    This should disappear, but is needed so we can combine expressions and use
 329    the fold() interfaces. Long term, we need to develop folding and combine
 330    routines that deal with gimple exclusively . */
 331
 332 static tree
 333 rhs_to_tree (tree type, gimple stmt)
 334 {
 335   enum tree_code code = gimple_assign_rhs_code (stmt);
 336   if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
 337     return fold_build2 (code, type, gimple_assign_rhs1 (stmt),
 338                         gimple_assign_rhs2 (stmt));
 339   else if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
 340     return build1 (code, type, gimple_assign_rhs1 (stmt));
 341   else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
 342     return gimple_assign_rhs1 (stmt);
 343   else
 344     gcc_unreachable ();
 345 }
 346
 347 /* Combine OP0 CODE OP1 in the context of a COND_EXPR.  Returns
 348    the folded result in a form suitable for COND_EXPR_COND or
 349    NULL_TREE, if there is no suitable simplified form.  If
 350    INVARIANT_ONLY is true only gimple_min_invariant results are
 351    considered simplified.  */
 352
 353 static tree
 354 combine_cond_expr_cond (enum tree_code code, tree type,
 355                         tree op0, tree op1, bool invariant_only)
 356 {
 357   tree t;
 358
 359   gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
 360
 361   t = fold_binary (code, type, op0, op1);
 362   if (!t)
 363     return NULL_TREE;
 364
 365   /* Require that we got a boolean type out if we put one in.  */
 366   gcc_assert (TREE_CODE (TREE_TYPE (t)) == TREE_CODE (type));
 367
 368   /* Canonicalize the combined condition for use in a COND_EXPR.  */
 369   t = canonicalize_cond_expr_cond (t);
 370
 371   /* Bail out if we required an invariant but didn't get one.  */
 372   if (!t || (invariant_only && !is_gimple_min_invariant (t)))
 373     return NULL_TREE;
 374
 375   return t;
 376 }
 377
 378 /* Propagate from the ssa name definition statements of COND_EXPR
 379    in GIMPLE_COND statement STMT into the conditional if that simplifies it.
 380    Returns zero if no statement was changed, one if there were
 381    changes and two if cfg_cleanup needs to run.
 382
 383    This must be kept in sync with forward_propagate_into_cond.  */
 384
 385 static int
 386 forward_propagate_into_gimple_cond (gimple stmt)
 387 {
 388    int did_something = 0;
 389
 390   do {
 391     tree tmp = NULL_TREE;
 392     tree name, rhs0 = NULL_TREE, rhs1 = NULL_TREE;
 393     gimple def_stmt;
 394     bool single_use0_p = false, single_use1_p = false;
 395     enum tree_code code = gimple_cond_code (stmt);
 396
 397     /* We can do tree combining on SSA_NAME and comparison expressions.  */
 398     if (TREE_CODE_CLASS (gimple_cond_code (stmt)) == tcc_comparison
 399         && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME)
 400       {
 401         /* For comparisons use the first operand, that is likely to
 402            simplify comparisons against constants.  */
 403         name = gimple_cond_lhs (stmt);
 404         def_stmt = get_prop_source_stmt (name, false, &single_use0_p);
 405         if (def_stmt && can_propagate_from (def_stmt))
 406           {
 407             tree op1 = gimple_cond_rhs (stmt);
 408             rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
 409             tmp = combine_cond_expr_cond (code, boolean_type_node, rhs0,
 410                                           op1, !single_use0_p);
 411           }
 412         /* If that wasn't successful, try the second operand.  */
 413         if (tmp == NULL_TREE
 414             && TREE_CODE (gimple_cond_rhs (stmt)) == SSA_NAME)
 415           {
 416             tree op0 = gimple_cond_lhs (stmt);
 417             name = gimple_cond_rhs (stmt);
 418             def_stmt = get_prop_source_stmt (name, false, &single_use1_p);
 419             if (!def_stmt || !can_propagate_from (def_stmt))
 420               return did_something;
 421
 422             rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt);
 423             tmp = combine_cond_expr_cond (code, boolean_type_node, op0, rhs1,
 424                                           !single_use1_p);
 425           }
 426         /* If that wasn't successful either, try both operands.  */
 427         if (tmp == NULL_TREE
 428             && rhs0 != NULL_TREE
 429             && rhs1 != NULL_TREE)
 430           tmp = combine_cond_expr_cond (code, boolean_type_node, rhs0,
 431                                         fold_convert (TREE_TYPE (rhs0), rhs1),
 432                                         !(single_use0_p && single_use1_p));
 433       }
 434
 435     if (tmp)
 436       {
 437         if (dump_file && tmp)
 438           {
 439             tree cond = build2 (gimple_cond_code (stmt),
 440                                 boolean_type_node,
 441                                 gimple_cond_lhs (stmt),
 442                                 gimple_cond_rhs (stmt));
 443             fprintf (dump_file, "  Replaced '");
 444             print_generic_expr (dump_file, cond, 0);
 445             fprintf (dump_file, "' with '");
 446             print_generic_expr (dump_file, tmp, 0);
 447             fprintf (dump_file, "'\n");
 448           }
 449
 450         gimple_cond_set_condition_from_tree (stmt, unshare_expr (tmp));
 451         update_stmt (stmt);
 452
 453         /* Remove defining statements.  */
 454         remove_prop_source_from_use (name, NULL);
 455
 456         if (is_gimple_min_invariant (tmp))
 457           did_something = 2;
 458         else if (did_something == 0)
 459           did_something = 1;
 460
 461         /* Continue combining.  */
 462         continue;
 463       }
 464
 465     break;
 466   } while (1);
 467
 468   return did_something;
 469 }
 470
 471
 472 /* Propagate from the ssa name definition statements of COND_EXPR
 473    in the rhs of statement STMT into the conditional if that simplifies it.
 474    Returns zero if no statement was changed, one if there were
 475    changes and two if cfg_cleanup needs to run.
 476
 477    This must be kept in sync with forward_propagate_into_gimple_cond.  */
 478
 479 static int
 480 forward_propagate_into_cond (gimple_stmt_iterator *gsi_p)
 481 {
 482   gimple stmt = gsi_stmt (*gsi_p);
 483   int did_something = 0;
 484
 485   do {
 486     tree tmp = NULL_TREE;
 487     tree cond = gimple_assign_rhs1 (stmt);
 488     tree name, rhs0 = NULL_TREE, rhs1 = NULL_TREE;
 489     gimple def_stmt;
 490     bool single_use0_p = false, single_use1_p = false;
 491
 492     /* We can do tree combining on SSA_NAME and comparison expressions.  */
 493     if (COMPARISON_CLASS_P (cond)
 494         && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME)
 495       {
 496         /* For comparisons use the first operand, that is likely to
 497            simplify comparisons against constants.  */
 498         name = TREE_OPERAND (cond, 0);
 499         def_stmt = get_prop_source_stmt (name, false, &single_use0_p);
 500         if (def_stmt && can_propagate_from (def_stmt))
 501           {
 502             tree op1 = TREE_OPERAND (cond, 1);
 503             rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
 504             tmp = combine_cond_expr_cond (TREE_CODE (cond), boolean_type_node,
 505                                           rhs0, op1, !single_use0_p);
 506           }
 507         /* If that wasn't successful, try the second operand.  */
 508         if (tmp == NULL_TREE
 509             && TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME)
 510           {
 511             tree op0 = TREE_OPERAND (cond, 0);
 512             name = TREE_OPERAND (cond, 1);
 513             def_stmt = get_prop_source_stmt (name, false, &single_use1_p);
 514             if (!def_stmt || !can_propagate_from (def_stmt))
 515               return did_something;
 516
 517             rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt);
 518             tmp = combine_cond_expr_cond (TREE_CODE (cond), boolean_type_node,
 519                                           op0, rhs1, !single_use1_p);
 520           }
 521         /* If that wasn't successful either, try both operands.  */
 522         if (tmp == NULL_TREE
 523             && rhs0 != NULL_TREE
 524             && rhs1 != NULL_TREE)
 525           tmp = combine_cond_expr_cond (TREE_CODE (cond), boolean_type_node,
 526                                         rhs0, fold_convert (TREE_TYPE (rhs0),
 527                                                             rhs1),
 528                                         !(single_use0_p && single_use1_p));
 529       }
 530     else if (TREE_CODE (cond) == SSA_NAME)
 531       {
 532         name = cond;
 533         def_stmt = get_prop_source_stmt (name, true, NULL);
 534         if (def_stmt || !can_propagate_from (def_stmt))
 535           return did_something;
 536
 537         rhs0 = gimple_assign_rhs1 (def_stmt);
 538         tmp = combine_cond_expr_cond (NE_EXPR, boolean_type_node, rhs0,
 539                                       build_int_cst (TREE_TYPE (rhs0), 0),
 540                                       false);
 541       }
 542
 543     if (tmp)
 544       {
 545         if (dump_file && tmp)
 546           {
 547             fprintf (dump_file, "  Replaced '");
 548             print_generic_expr (dump_file, cond, 0);
 549             fprintf (dump_file, "' with '");
 550             print_generic_expr (dump_file, tmp, 0);
 551             fprintf (dump_file, "'\n");
 552           }
 553
 554         gimple_assign_set_rhs_from_tree (gsi_p, unshare_expr (tmp));
 555         stmt = gsi_stmt (*gsi_p);
 556         update_stmt (stmt);
 557
 558         /* Remove defining statements.  */
 559         remove_prop_source_from_use (name, NULL);
 560
 561         if (is_gimple_min_invariant (tmp))
 562           did_something = 2;
 563         else if (did_something == 0)
 564           did_something = 1;
 565
 566         /* Continue combining.  */
 567         continue;
 568       }
 569
 570     break;
 571   } while (1);
 572
 573   return did_something;
 574 }
 575
 576 /* We've just substituted an ADDR_EXPR into stmt.  Update all the
 577    relevant data structures to match.  */
 578
 579 static void
 580 tidy_after_forward_propagate_addr (gimple stmt)
 581 {
 582   /* We may have turned a trapping insn into a non-trapping insn.  */
 583   if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
 584       && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
 585     cfg_changed = true;
 586
 587   if (TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR)
 588      recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
 589
 590   mark_symbols_for_renaming (stmt);
 591 }
 592
 593 /* DEF_RHS contains the address of the 0th element in an array.
 594    USE_STMT uses type of DEF_RHS to compute the address of an
 595    arbitrary element within the array.  The (variable) byte offset
 596    of the element is contained in OFFSET.
 597
 598    We walk back through the use-def chains of OFFSET to verify that
 599    it is indeed computing the offset of an element within the array
 600    and extract the index corresponding to the given byte offset.
 601
 602    We then try to fold the entire address expression into a form
 603    &array[index].
 604
 605    If we are successful, we replace the right hand side of USE_STMT
 606    with the new address computation.  */
 607
 608 static bool
 609 forward_propagate_addr_into_variable_array_index (tree offset,
 610                                                   tree def_rhs,
 611                                                   gimple_stmt_iterator *use_stmt_gsi)
 612 {
 613   tree index;
 614   gimple offset_def, use_stmt = gsi_stmt (*use_stmt_gsi);
 615
 616   /* Get the offset's defining statement.  */
 617   offset_def = SSA_NAME_DEF_STMT (offset);
 618
 619   /* Try to find an expression for a proper index.  This is either a
 620      multiplication expression by the element size or just the ssa name we came
 621      along in case the element size is one. In that case, however, we do not
 622      allow multiplications because they can be computing index to a higher
 623      level dimension (PR 37861). */
 624   if (integer_onep (TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs)))))
 625     {
 626       if (is_gimple_assign (offset_def)
 627           && gimple_assign_rhs_code (offset_def) == MULT_EXPR)
 628         return false;
 629
 630       index = offset;
 631     }
 632   else
 633     {
 634       /* The statement which defines OFFSET before type conversion
 635          must be a simple GIMPLE_ASSIGN.  */
 636       if (!is_gimple_assign (offset_def))
 637         return false;
 638
 639       /* The RHS of the statement which defines OFFSET must be a
 640          multiplication of an object by the size of the array elements.
 641          This implicitly verifies that the size of the array elements
 642          is constant.  */
 643      offset = gimple_assign_rhs1 (offset_def);
 644      if (gimple_assign_rhs_code (offset_def) != MULT_EXPR
 645          || TREE_CODE (gimple_assign_rhs2 (offset_def)) != INTEGER_CST
 646          || !simple_cst_equal (gimple_assign_rhs2 (offset_def),
 647                                TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs)))))
 648         return false;
 649
 650       /* The first operand to the MULT_EXPR is the desired index.  */
 651       index = offset;
 652     }
 653
 654   /* Replace the pointer addition with array indexing.  */
 655   gimple_assign_set_rhs_from_tree (use_stmt_gsi, unshare_expr (def_rhs));
 656   use_stmt = gsi_stmt (*use_stmt_gsi);
 657   TREE_OPERAND (TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0), 1)
 658     = index;
 659
 660   /* That should have created gimple, so there is no need to
 661      record information to undo the propagation.  */
 662   fold_stmt_inplace (use_stmt);
 663   tidy_after_forward_propagate_addr (use_stmt);
 664   return true;
 665 }
 666
 667 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
 668    ADDR_EXPR <whatever>.
 669
 670    Try to forward propagate the ADDR_EXPR into the use USE_STMT.
 671    Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
 672    node or for recovery of array indexing from pointer arithmetic.
 673
 674    Return true if the propagation was successful (the propagation can
 675    be not totally successful, yet things may have been changed).  */
 676
 677 static bool
 678 forward_propagate_addr_expr_1 (tree name, tree def_rhs,
 679                                gimple_stmt_iterator *use_stmt_gsi,
 680                                bool single_use_p)
 681 {
 682   tree lhs, rhs, rhs2, array_ref;
 683   tree *rhsp, *lhsp;
 684   gimple use_stmt = gsi_stmt (*use_stmt_gsi);
 685   enum tree_code rhs_code;
 686   bool res = true;
 687
 688   gcc_assert (TREE_CODE (def_rhs) == ADDR_EXPR);
 689
 690   lhs = gimple_assign_lhs (use_stmt);
 691   rhs_code = gimple_assign_rhs_code (use_stmt);
 692   rhs = gimple_assign_rhs1 (use_stmt);
 693
 694   /* Trivial cases.  The use statement could be a trivial copy or a
 695      useless conversion.  Recurse to the uses of the lhs as copyprop does
 696      not copy through different variant pointers and FRE does not catch
 697      all useless conversions.  Treat the case of a single-use name and
 698      a conversion to def_rhs type separate, though.  */
 699   if (TREE_CODE (lhs) == SSA_NAME
 700       && ((rhs_code == SSA_NAME && rhs == name)
 701           || CONVERT_EXPR_CODE_P (rhs_code)))
 702     {
 703       /* Only recurse if we don't deal with a single use or we cannot
 704          do the propagation to the current statement.  In particular
 705          we can end up with a conversion needed for a non-invariant
 706          address which we cannot do in a single statement.  */
 707       if (!single_use_p
 708           || (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs))
 709               && !is_gimple_min_invariant (def_rhs)))
 710         return forward_propagate_addr_expr (lhs, def_rhs);
 711
 712       gimple_assign_set_rhs1 (use_stmt, unshare_expr (def_rhs));
 713       if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
 714         gimple_assign_set_rhs_code (use_stmt, TREE_CODE (def_rhs));
 715       else
 716         gimple_assign_set_rhs_code (use_stmt, NOP_EXPR);
 717       return true;
 718     }
 719
 720   /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
 721      ADDR_EXPR will not appear on the LHS.  */
 722   lhsp = gimple_assign_lhs_ptr (use_stmt);
 723   while (handled_component_p (*lhsp))
 724     lhsp = &TREE_OPERAND (*lhsp, 0);
 725   lhs = *lhsp;
 726
 727   /* Now see if the LHS node is an INDIRECT_REF using NAME.  If so,
 728      propagate the ADDR_EXPR into the use of NAME and fold the result.  */
 729   if (TREE_CODE (lhs) == INDIRECT_REF
 730       && TREE_OPERAND (lhs, 0) == name)
 731     {
 732       if (may_propagate_address_into_dereference (def_rhs, lhs)
 733           && (lhsp != gimple_assign_lhs_ptr (use_stmt)
 734               || useless_type_conversion_p
 735                    (TREE_TYPE (TREE_OPERAND (def_rhs, 0)), TREE_TYPE (rhs))))
 736         {
 737           *lhsp = unshare_expr (TREE_OPERAND (def_rhs, 0));
 738           fold_stmt_inplace (use_stmt);
 739           tidy_after_forward_propagate_addr (use_stmt);
 740
 741           /* Continue propagating into the RHS if this was not the only use.  */
 742           if (single_use_p)
 743             return true;
 744         }
 745       else
 746         /* We can have a struct assignment dereferencing our name twice.
 747            Note that we didn't propagate into the lhs to not falsely
 748            claim we did when propagating into the rhs.  */
 749         res = false;
 750     }
 751
 752   /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
 753      nodes from the RHS.  */
 754   rhsp = gimple_assign_rhs1_ptr (use_stmt);
 755   while (handled_component_p (*rhsp)
 756          || TREE_CODE (*rhsp) == ADDR_EXPR)
 757     rhsp = &TREE_OPERAND (*rhsp, 0);
 758   rhs = *rhsp;
 759
 760   /* Now see if the RHS node is an INDIRECT_REF using NAME.  If so,
 761      propagate the ADDR_EXPR into the use of NAME and fold the result.  */
 762   if (TREE_CODE (rhs) == INDIRECT_REF
 763       && TREE_OPERAND (rhs, 0) == name
 764       && may_propagate_address_into_dereference (def_rhs, rhs))
 765     {
 766       *rhsp = unshare_expr (TREE_OPERAND (def_rhs, 0));
 767       fold_stmt_inplace (use_stmt);
 768       tidy_after_forward_propagate_addr (use_stmt);
 769       return res;
 770     }
 771
 772   /* Now see if the RHS node is an INDIRECT_REF using NAME.  If so,
 773      propagate the ADDR_EXPR into the use of NAME and try to
 774      create a VCE and fold the result.  */
 775   if (TREE_CODE (rhs) == INDIRECT_REF
 776       && TREE_OPERAND (rhs, 0) == name
 777       && TYPE_SIZE (TREE_TYPE (rhs))
 778       && TYPE_SIZE (TREE_TYPE (TREE_OPERAND (def_rhs, 0)))
 779       /* Function decls should not be used for VCE either as it could be a
 780          function descriptor that we want and not the actual function code.  */
 781       && TREE_CODE (TREE_OPERAND (def_rhs, 0)) != FUNCTION_DECL
 782       /* We should not convert volatile loads to non volatile loads. */
 783       && !TYPE_VOLATILE (TREE_TYPE (rhs))
 784       && !TYPE_VOLATILE (TREE_TYPE (TREE_OPERAND (def_rhs, 0)))
 785       && operand_equal_p (TYPE_SIZE (TREE_TYPE (rhs)),
 786                           TYPE_SIZE (TREE_TYPE (TREE_OPERAND (def_rhs, 0))), 0))
 787    {
 788      tree def_rhs_base, new_rhs = unshare_expr (TREE_OPERAND (def_rhs, 0));
 789      new_rhs = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (rhs), new_rhs);
 790      if (TREE_CODE (new_rhs) != VIEW_CONVERT_EXPR)
 791        {
 792          /* If we have folded the VIEW_CONVERT_EXPR then the result is only
 793             valid if we can replace the whole rhs of the use statement.  */
 794          if (rhs != gimple_assign_rhs1 (use_stmt))
 795            return false;
 796          new_rhs = force_gimple_operand_gsi (use_stmt_gsi, new_rhs, true, NULL,
 797                                              true, GSI_NEW_STMT);
 798          gimple_assign_set_rhs1 (use_stmt, new_rhs);
 799          tidy_after_forward_propagate_addr (use_stmt);
 800          return res;
 801        }
 802      /* If the defining rhs comes from an indirect reference, then do not
 803         convert into a VIEW_CONVERT_EXPR.  */
 804      def_rhs_base = TREE_OPERAND (def_rhs, 0);
 805      while (handled_component_p (def_rhs_base))
 806        def_rhs_base = TREE_OPERAND (def_rhs_base, 0);
 807      if (!INDIRECT_REF_P (def_rhs_base))
 808        {
 809          /* We may have arbitrary VIEW_CONVERT_EXPRs in a nested component
 810             reference.  Place it there and fold the thing.  */
 811          *rhsp = new_rhs;
 812          fold_stmt_inplace (use_stmt);
 813          tidy_after_forward_propagate_addr (use_stmt);
 814          return res;
 815        }
 816    }
 817
 818   /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
 819      is nothing to do. */
 820   if (gimple_assign_rhs_code (use_stmt) != POINTER_PLUS_EXPR
 821       || gimple_assign_rhs1 (use_stmt) != name)
 822     return false;
 823
 824   /* The remaining cases are all for turning pointer arithmetic into
 825      array indexing.  They only apply when we have the address of
 826      element zero in an array.  If that is not the case then there
 827      is nothing to do.  */
 828   array_ref = TREE_OPERAND (def_rhs, 0);
 829   if (TREE_CODE (array_ref) != ARRAY_REF
 830       || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
 831       || !integer_zerop (TREE_OPERAND (array_ref, 1)))
 832     return false;
 833
 834   rhs2 = gimple_assign_rhs2 (use_stmt);
 835   /* Try to optimize &x[0] p+ C where C is a multiple of the size
 836      of the elements in X into &x[C/element size].  */
 837   if (TREE_CODE (rhs2) == INTEGER_CST)
 838     {
 839       tree new_rhs = maybe_fold_stmt_addition (gimple_expr_type (use_stmt),
 840                                                array_ref, rhs2);
 841       if (new_rhs)
 842         {
 843           gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
 844           use_stmt = gsi_stmt (*use_stmt_gsi);
 845           update_stmt (use_stmt);
 846           tidy_after_forward_propagate_addr (use_stmt);
 847           return true;
 848         }
 849     }
 850
 851   /* Try to optimize &x[0] p+ OFFSET where OFFSET is defined by
 852      converting a multiplication of an index by the size of the
 853      array elements, then the result is converted into the proper
 854      type for the arithmetic.  */
 855   if (TREE_CODE (rhs2) == SSA_NAME
 856       && useless_type_conversion_p (TREE_TYPE (name), TREE_TYPE (def_rhs))
 857       /* Avoid problems with IVopts creating PLUS_EXPRs with a
 858          different type than their operands.  */
 859       && useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
 860     return forward_propagate_addr_into_variable_array_index (rhs2, def_rhs,
 861                                                              use_stmt_gsi);
 862   return false;
 863 }
 864
 865 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
 866
 867    Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
 868    Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
 869    node or for recovery of array indexing from pointer arithmetic.
 870    Returns true, if all uses have been propagated into.  */
 871
 872 static bool
 873 forward_propagate_addr_expr (tree name, tree rhs)
 874 {
 875   int stmt_loop_depth = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_depth;
 876   imm_use_iterator iter;
 877   gimple use_stmt;
 878   bool all = true;
 879   bool single_use_p = has_single_use (name);
 880
 881   FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
 882     {
 883       bool result;
 884       tree use_rhs;
 885
 886       /* If the use is not in a simple assignment statement, then
 887          there is nothing we can do.  */
 888       if (gimple_code (use_stmt) != GIMPLE_ASSIGN)
 889         {
 890           all = false;
 891           continue;
 892         }
 893
 894       /* If the use is in a deeper loop nest, then we do not want
 895          to propagate the ADDR_EXPR into the loop as that is likely
 896          adding expression evaluations into the loop.  */
 897       if (gimple_bb (use_stmt)->loop_depth > stmt_loop_depth)
 898         {
 899           all = false;
 900           continue;
 901         }
 902
 903       push_stmt_changes (&use_stmt);
 904
 905       {
 906         gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
 907         result = forward_propagate_addr_expr_1 (name, rhs, &gsi,
 908                                                 single_use_p);
 909         use_stmt = gsi_stmt (gsi);
 910       }
 911       all &= result;
 912
 913       pop_stmt_changes (&use_stmt);
 914
 915       /* Remove intermediate now unused copy and conversion chains.  */
 916       use_rhs = gimple_assign_rhs1 (use_stmt);
 917       if (result
 918           && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
 919           && (TREE_CODE (use_rhs) == SSA_NAME
 920               || (CONVERT_EXPR_P (use_rhs)
 921                   && TREE_CODE (TREE_OPERAND (use_rhs, 0)) == SSA_NAME)))
 922         {
 923           gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
 924           release_defs (use_stmt);
 925           gsi_remove (&gsi, true);
 926         }
 927     }
 928
 929   return all;
 930 }
 931
 932 /* Forward propagate the comparison defined in STMT like
 933    cond_1 = x CMP y to uses of the form
 934      a_1 = (T')cond_1
 935      a_1 = !cond_1
 936      a_1 = cond_1 != 0
 937    Returns true if stmt is now unused.  */
 938
 939 static bool
 940 forward_propagate_comparison (gimple stmt)
 941 {
 942   tree name = gimple_assign_lhs (stmt);
 943   gimple use_stmt;
 944   tree tmp = NULL_TREE;
 945
 946   /* Don't propagate ssa names that occur in abnormal phis.  */
 947   if ((TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
 948        && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
 949       || (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME
 950         && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs2 (stmt))))
 951     return false;
 952
 953   /* Do not un-cse comparisons.  But propagate through copies.  */
 954   use_stmt = get_prop_dest_stmt (name, &name);
 955   if (!use_stmt)
 956     return false;
 957
 958   /* Conversion of the condition result to another integral type.  */
 959   if (is_gimple_assign (use_stmt)
 960       && (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt))
 961           || TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt))
 962              == tcc_comparison
 963           || gimple_assign_rhs_code (use_stmt) == TRUTH_NOT_EXPR)
 964       && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (use_stmt))))
 965     {
 966       tree lhs = gimple_assign_lhs (use_stmt);
 967
 968       /* We can propagate the condition into a conversion.  */
 969       if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt)))
 970         {
 971           /* Avoid using fold here as that may create a COND_EXPR with
 972              non-boolean condition as canonical form.  */
 973           tmp = build2 (gimple_assign_rhs_code (stmt), TREE_TYPE (lhs),
 974                         gimple_assign_rhs1 (stmt), gimple_assign_rhs2 (stmt));
 975         }
 976       /* We can propagate the condition into X op CST where op
 977          is EQ_EXPR or NE_EXPR and CST is either one or zero.  */
 978       else if (TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt))
 979               == tcc_comparison
 980              && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME
 981              && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST)
 982       {
 983         enum tree_code code = gimple_assign_rhs_code (use_stmt);
 984         tree cst = gimple_assign_rhs2 (use_stmt);
 985         tree cond;
 986
 987         cond = build2 (gimple_assign_rhs_code (stmt),
 988                        TREE_TYPE (cst),
 989                        gimple_assign_rhs1 (stmt),
 990                        gimple_assign_rhs2 (stmt));
 991
 992         tmp = combine_cond_expr_cond (code, TREE_TYPE (lhs), cond, cst, false);
 993         if (tmp == NULL_TREE)
 994           return false;
 995       }
 996       /* We can propagate the condition into a statement that
 997          computes the logical negation of the comparison result.  */
 998       else if (gimple_assign_rhs_code (use_stmt) == TRUTH_NOT_EXPR)
 999         {
1000           tree type = TREE_TYPE (gimple_assign_rhs1 (stmt));
1001           bool nans = HONOR_NANS (TYPE_MODE (type));
1002           enum tree_code code;
1003           code = invert_tree_comparison (gimple_assign_rhs_code (stmt), nans);
1004           if (code == ERROR_MARK)
1005             return false;
1006
1007           tmp = build2 (code, TREE_TYPE (lhs), gimple_assign_rhs1 (stmt),
1008                         gimple_assign_rhs2 (stmt));
1009         }
1010       else
1011         return false;
1012
1013       {
1014         gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1015         gimple_assign_set_rhs_from_tree (&gsi, unshare_expr (tmp));
1016         use_stmt = gsi_stmt (gsi);
1017         update_stmt (use_stmt);
1018       }
1019
1020       /* Remove defining statements.  */
1021       remove_prop_source_from_use (name, stmt);
1022
1023       if (dump_file && (dump_flags & TDF_DETAILS))
1024         {
1025           tree old_rhs = rhs_to_tree (TREE_TYPE (gimple_assign_lhs (stmt)),
1026                                       stmt);
1027           fprintf (dump_file, "  Replaced '");
1028           print_generic_expr (dump_file, old_rhs, dump_flags);
1029           fprintf (dump_file, "' with '");
1030           print_generic_expr (dump_file, tmp, dump_flags);
1031           fprintf (dump_file, "'\n");
1032         }
1033
1034       return true;
1035     }
1036
1037   return false;
1038 }
1039
1040 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
1041    If so, we can change STMT into lhs = y which can later be copy
1042    propagated.  Similarly for negation.
1043
1044    This could trivially be formulated as a forward propagation
1045    to immediate uses.  However, we already had an implementation
1046    from DOM which used backward propagation via the use-def links.
1047
1048    It turns out that backward propagation is actually faster as
1049    there's less work to do for each NOT/NEG expression we find.
1050    Backwards propagation needs to look at the statement in a single
1051    backlink.  Forward propagation needs to look at potentially more
1052    than one forward link.  */
1053
1054 static void
1055 simplify_not_neg_expr (gimple_stmt_iterator *gsi_p)
1056 {
1057   gimple stmt = gsi_stmt (*gsi_p);
1058   tree rhs = gimple_assign_rhs1 (stmt);
1059   gimple rhs_def_stmt = SSA_NAME_DEF_STMT (rhs);
1060
1061   /* See if the RHS_DEF_STMT has the same form as our statement.  */
1062   if (is_gimple_assign (rhs_def_stmt)
1063       && gimple_assign_rhs_code (rhs_def_stmt) == gimple_assign_rhs_code (stmt))
1064     {
1065       tree rhs_def_operand = gimple_assign_rhs1 (rhs_def_stmt);
1066
1067       /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME.  */
1068       if (TREE_CODE (rhs_def_operand) == SSA_NAME
1069           && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand))
1070         {
1071           gimple_assign_set_rhs_from_tree (gsi_p, rhs_def_operand);
1072           stmt = gsi_stmt (*gsi_p);
1073           update_stmt (stmt);
1074         }
1075     }
1076 }
1077
1078 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1079    the condition which we may be able to optimize better.  */
1080
1081 static void
1082 simplify_gimple_switch (gimple stmt)
1083 {
1084   tree cond = gimple_switch_index (stmt);
1085   tree def, to, ti;
1086   gimple def_stmt;
1087
1088   /* The optimization that we really care about is removing unnecessary
1089      casts.  That will let us do much better in propagating the inferred
1090      constant at the switch target.  */
1091   if (TREE_CODE (cond) == SSA_NAME)
1092     {
1093       def_stmt = SSA_NAME_DEF_STMT (cond);
1094       if (is_gimple_assign (def_stmt))
1095         {
1096           if (gimple_assign_rhs_code (def_stmt) == NOP_EXPR)
1097             {
1098               int need_precision;
1099               bool fail;
1100
1101               def = gimple_assign_rhs1 (def_stmt);
1102
1103 #ifdef ENABLE_CHECKING
1104               /* ??? Why was Jeff testing this?  We are gimple...  */
1105               gcc_assert (is_gimple_val (def));
1106 #endif
1107
1108               to = TREE_TYPE (cond);
1109               ti = TREE_TYPE (def);
1110
1111               /* If we have an extension that preserves value, then we
1112                  can copy the source value into the switch.  */
1113
1114               need_precision = TYPE_PRECISION (ti);
1115               fail = false;
1116               if (! INTEGRAL_TYPE_P (ti))
1117                 fail = true;
1118               else if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti))
1119                 fail = true;
1120               else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti))
1121                 need_precision += 1;
1122               if (TYPE_PRECISION (to) < need_precision)
1123                 fail = true;
1124
1125               if (!fail)
1126                 {
1127                   gimple_switch_set_index (stmt, def);
1128                   update_stmt (stmt);
1129                 }
1130             }
1131         }
1132     }
1133 }
1134
1135 /* Main entry point for the forward propagation optimizer.  */
1136
1137 static unsigned int
1138 tree_ssa_forward_propagate_single_use_vars (void)
1139 {
1140   basic_block bb;
1141   unsigned int todoflags = 0;
1142
1143   cfg_changed = false;
1144
1145   FOR_EACH_BB (bb)
1146     {
1147       gimple_stmt_iterator gsi;
1148
1149       /* Note we update GSI within the loop as necessary.  */
1150       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
1151         {
1152           gimple stmt = gsi_stmt (gsi);
1153
1154           /* If this statement sets an SSA_NAME to an address,
1155              try to propagate the address into the uses of the SSA_NAME.  */
1156           if (is_gimple_assign (stmt))
1157             {
1158               tree lhs = gimple_assign_lhs (stmt);
1159               tree rhs = gimple_assign_rhs1 (stmt);
1160
1161               if (TREE_CODE (lhs) != SSA_NAME)
1162                 {
1163                   gsi_next (&gsi);
1164                   continue;
1165                 }
1166
1167               if (gimple_assign_rhs_code (stmt) == ADDR_EXPR
1168                   /* Handle pointer conversions on invariant addresses
1169                      as well, as this is valid gimple.  */
1170                   || (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
1171                       && TREE_CODE (rhs) == ADDR_EXPR
1172                       && POINTER_TYPE_P (TREE_TYPE (lhs))))
1173                 {
1174                   STRIP_NOPS (rhs);
1175                   if (!stmt_references_abnormal_ssa_name (stmt)
1176                       && forward_propagate_addr_expr (lhs, rhs))
1177                     {
1178                       release_defs (stmt);
1179                       todoflags |= TODO_remove_unused_locals;
1180                       gsi_remove (&gsi, true);
1181                     }
1182                   else
1183                     gsi_next (&gsi);
1184                 }
1185               else if ((gimple_assign_rhs_code (stmt) == BIT_NOT_EXPR
1186                         || gimple_assign_rhs_code (stmt) == NEGATE_EXPR)
1187                        && TREE_CODE (rhs) == SSA_NAME)
1188                 {
1189                   simplify_not_neg_expr (&gsi);
1190                   gsi_next (&gsi);
1191                 }
1192               else if (gimple_assign_rhs_code (stmt) == COND_EXPR)
1193                 {
1194                   /* In this case the entire COND_EXPR is in rhs1. */
1195                   int did_something;
1196                   fold_defer_overflow_warnings ();
1197                   did_something = forward_propagate_into_cond (&gsi);
1198                   stmt = gsi_stmt (gsi);
1199                   if (did_something == 2)
1200                     cfg_changed = true;
1201                   fold_undefer_overflow_warnings (!TREE_NO_WARNING (rhs)
1202                     && did_something, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
1203                   gsi_next (&gsi);
1204                 }
1205               else if (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt))
1206                                         == tcc_comparison)
1207                 {
1208                   if (forward_propagate_comparison (stmt))
1209                     {
1210                       release_defs (stmt);
1211                       todoflags |= TODO_remove_unused_locals;
1212                       gsi_remove (&gsi, true);
1213                     }
1214                   else
1215                     gsi_next (&gsi);
1216                 }
1217               else
1218                 gsi_next (&gsi);
1219             }
1220           else if (gimple_code (stmt) == GIMPLE_SWITCH)
1221             {
1222               simplify_gimple_switch (stmt);
1223               gsi_next (&gsi);
1224             }
1225           else if (gimple_code (stmt) == GIMPLE_COND)
1226             {
1227               int did_something;
1228               fold_defer_overflow_warnings ();
1229               did_something = forward_propagate_into_gimple_cond (stmt);
1230               if (did_something == 2)
1231                 cfg_changed = true;
1232               fold_undefer_overflow_warnings (did_something, stmt,
1233                                               WARN_STRICT_OVERFLOW_CONDITIONAL);
1234               gsi_next (&gsi);
1235             }
1236           else
1237             gsi_next (&gsi);
1238         }
1239     }
1240
1241   if (cfg_changed)
1242     todoflags |= TODO_cleanup_cfg;
1243   return todoflags;
1244 }
1245
1246
1247 static bool
1248 gate_forwprop (void)
1249 {
1250   return 1;
1251 }
1252
1253 struct gimple_opt_pass pass_forwprop =
1254 {
1255  {
1256   GIMPLE_PASS,
1257   "forwprop",                   /* name */
1258   gate_forwprop,                /* gate */
1259   tree_ssa_forward_propagate_single_use_vars,   /* execute */
1260   NULL,                         /* sub */
1261   NULL,                         /* next */
1262   0,                            /* static_pass_number */
1263   TV_TREE_FORWPROP,             /* tv_id */
1264   PROP_cfg | PROP_ssa,          /* properties_required */
1265   0,                            /* properties_provided */
1266   0,                            /* properties_destroyed */
1267   0,                            /* todo_flags_start */
1268   TODO_dump_func
1269   | TODO_ggc_collect
1270   | TODO_update_ssa
1271   | TODO_verify_ssa             /* todo_flags_finish */
1272  }
1273 };
1274