gcc/tree-ssa-forwprop.c

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