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