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