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