gcc/tree-ssa-forwprop.c

   1 /* Forward propagation of expressions for single use variables.
   2    Copyright (C) 2004, 2005 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 2, 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 COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "errors.h"
  26 #include "ggc.h"
  27 #include "tree.h"
  28 #include "rtl.h"
  29 #include "tm_p.h"
  30 #include "basic-block.h"
  31 #include "timevar.h"
  32 #include "diagnostic.h"
  33 #include "tree-flow.h"
  34 #include "tree-pass.h"
  35 #include "tree-dump.h"
  36 #include "langhooks.h"
  37
  38 /* This pass propagates the RHS of assignment statements into use
  39    sites of the LHS of the assignment.  It's basically a specialized
  40    form of tree combination.
  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    variale 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
 147    This will (of course) be extended as other needs arise.  */
 148
 149 /* Given an SSA_NAME VAR, return true if and only if VAR is defined by
 150    a comparison.  */
 151
 152 static bool
 153 ssa_name_defined_by_comparison_p (tree var)
 154 {
 155   tree def = SSA_NAME_DEF_STMT (var);
 156
 157   if (TREE_CODE (def) == MODIFY_EXPR)
 158     {
 159       tree rhs = TREE_OPERAND (def, 1);
 160       return COMPARISON_CLASS_P (rhs);
 161     }
 162
 163   return 0;
 164 }
 165
 166 /* Forward propagate a single-use variable into COND once.  Return a
 167    new condition if successful.  Return NULL_TREE otherwise.  */
 168
 169 static tree
 170 forward_propagate_into_cond_1 (tree cond, tree *test_var_p)
 171 {
 172   tree new_cond = NULL_TREE;
 173   enum tree_code cond_code = TREE_CODE (cond);
 174   tree test_var = NULL_TREE;
 175   tree def;
 176   tree def_rhs;
 177
 178   /* If the condition is not a lone variable or an equality test of an
 179      SSA_NAME against an integral constant, then we do not have an
 180      optimizable case.
 181
 182      Note these conditions also ensure the COND_EXPR has no
 183      virtual operands or other side effects.  */
 184   if (cond_code != SSA_NAME
 185       && !((cond_code == EQ_EXPR || cond_code == NE_EXPR)
 186            && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
 187            && CONSTANT_CLASS_P (TREE_OPERAND (cond, 1))
 188            && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
 189     return NULL_TREE;
 190
 191   /* Extract the single variable used in the test into TEST_VAR.  */
 192   if (cond_code == SSA_NAME)
 193     test_var = cond;
 194   else
 195     test_var = TREE_OPERAND (cond, 0);
 196
 197   /* Now get the defining statement for TEST_VAR.  Skip this case if
 198      it's not defined by some MODIFY_EXPR.  */
 199   def = SSA_NAME_DEF_STMT (test_var);
 200   if (TREE_CODE (def) != MODIFY_EXPR)
 201     return NULL_TREE;
 202
 203   def_rhs = TREE_OPERAND (def, 1);
 204
 205   /* If TEST_VAR is set by adding or subtracting a constant
 206      from an SSA_NAME, then it is interesting to us as we
 207      can adjust the constant in the conditional and thus
 208      eliminate the arithmetic operation.  */
 209   if (TREE_CODE (def_rhs) == PLUS_EXPR
 210       || TREE_CODE (def_rhs) == MINUS_EXPR)
 211     {
 212       tree op0 = TREE_OPERAND (def_rhs, 0);
 213       tree op1 = TREE_OPERAND (def_rhs, 1);
 214
 215       /* The first operand must be an SSA_NAME and the second
 216          operand must be a constant.  */
 217       if (TREE_CODE (op0) != SSA_NAME
 218           || !CONSTANT_CLASS_P (op1)
 219           || !INTEGRAL_TYPE_P (TREE_TYPE (op1)))
 220         return NULL_TREE;
 221
 222       /* Don't propagate if the first operand occurs in
 223          an abnormal PHI.  */
 224       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
 225         return NULL_TREE;
 226
 227       if (has_single_use (test_var))
 228         {
 229           enum tree_code new_code;
 230           tree t;
 231
 232           /* If the variable was defined via X + C, then we must
 233              subtract C from the constant in the conditional.
 234              Otherwise we add C to the constant in the
 235              conditional.  The result must fold into a valid
 236              gimple operand to be optimizable.  */
 237           new_code = (TREE_CODE (def_rhs) == PLUS_EXPR
 238                       ? MINUS_EXPR : PLUS_EXPR);
 239           t = int_const_binop (new_code, TREE_OPERAND (cond, 1), op1, 0);
 240           if (!is_gimple_val (t))
 241             return NULL_TREE;
 242
 243           new_cond = build (cond_code, boolean_type_node, op0, t);
 244         }
 245     }
 246
 247   /* These cases require comparisons of a naked SSA_NAME or
 248      comparison of an SSA_NAME against zero or one.  */
 249   else if (TREE_CODE (cond) == SSA_NAME
 250            || integer_zerop (TREE_OPERAND (cond, 1))
 251            || integer_onep (TREE_OPERAND (cond, 1)))
 252     {
 253       /* If TEST_VAR is set from a relational operation
 254          between two SSA_NAMEs or a combination of an SSA_NAME
 255          and a constant, then it is interesting.  */
 256       if (COMPARISON_CLASS_P (def_rhs))
 257         {
 258           tree op0 = TREE_OPERAND (def_rhs, 0);
 259           tree op1 = TREE_OPERAND (def_rhs, 1);
 260
 261           /* Both operands of DEF_RHS must be SSA_NAMEs or
 262              constants.  */
 263           if ((TREE_CODE (op0) != SSA_NAME
 264                && !is_gimple_min_invariant (op0))
 265               || (TREE_CODE (op1) != SSA_NAME
 266                   && !is_gimple_min_invariant (op1)))
 267             return NULL_TREE;
 268
 269           /* Don't propagate if the first operand occurs in
 270              an abnormal PHI.  */
 271           if (TREE_CODE (op0) == SSA_NAME
 272               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
 273             return NULL_TREE;
 274
 275           /* Don't propagate if the second operand occurs in
 276              an abnormal PHI.  */
 277           if (TREE_CODE (op1) == SSA_NAME
 278               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))
 279             return NULL_TREE;
 280
 281           if (has_single_use (test_var))
 282             {
 283               /* TEST_VAR was set from a relational operator.  */
 284               new_cond = build (TREE_CODE (def_rhs),
 285                                 boolean_type_node, op0, op1);
 286
 287               /* Invert the conditional if necessary.  */
 288               if ((cond_code == EQ_EXPR
 289                    && integer_zerop (TREE_OPERAND (cond, 1)))
 290                   || (cond_code == NE_EXPR
 291                       && integer_onep (TREE_OPERAND (cond, 1))))
 292                 {
 293                   new_cond = invert_truthvalue (new_cond);
 294
 295                   /* If we did not get a simple relational
 296                      expression or bare SSA_NAME, then we can
 297                      not optimize this case.  */
 298                   if (!COMPARISON_CLASS_P (new_cond)
 299                       && TREE_CODE (new_cond) != SSA_NAME)
 300                     new_cond = NULL_TREE;
 301                 }
 302             }
 303         }
 304
 305       /* If TEST_VAR is set from a TRUTH_NOT_EXPR, then it
 306          is interesting.  */
 307       else if (TREE_CODE (def_rhs) == TRUTH_NOT_EXPR)
 308         {
 309           enum tree_code new_code;
 310
 311           def_rhs = TREE_OPERAND (def_rhs, 0);
 312
 313           /* DEF_RHS must be an SSA_NAME or constant.  */
 314           if (TREE_CODE (def_rhs) != SSA_NAME
 315               && !is_gimple_min_invariant (def_rhs))
 316             return NULL_TREE;
 317
 318           /* Don't propagate if the operand occurs in
 319              an abnormal PHI.  */
 320           if (TREE_CODE (def_rhs) == SSA_NAME
 321               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_rhs))
 322             return NULL_TREE;
 323
 324           if (cond_code == SSA_NAME
 325               || (cond_code == NE_EXPR
 326                   && integer_zerop (TREE_OPERAND (cond, 1)))
 327               || (cond_code == EQ_EXPR
 328                   && integer_onep (TREE_OPERAND (cond, 1))))
 329             new_code = EQ_EXPR;
 330           else
 331             new_code = NE_EXPR;
 332
 333           new_cond = build2 (new_code, boolean_type_node, def_rhs,
 334                              fold_convert (TREE_TYPE (def_rhs),
 335                                            integer_zero_node));
 336         }
 337
 338       /* If TEST_VAR was set from a cast of an integer type
 339          to a boolean type or a cast of a boolean to an
 340          integral, then it is interesting.  */
 341       else if (TREE_CODE (def_rhs) == NOP_EXPR
 342                || TREE_CODE (def_rhs) == CONVERT_EXPR)
 343         {
 344           tree outer_type;
 345           tree inner_type;
 346
 347           outer_type = TREE_TYPE (def_rhs);
 348           inner_type = TREE_TYPE (TREE_OPERAND (def_rhs, 0));
 349
 350           if ((TREE_CODE (outer_type) == BOOLEAN_TYPE
 351                && INTEGRAL_TYPE_P (inner_type))
 352               || (TREE_CODE (inner_type) == BOOLEAN_TYPE
 353                   && INTEGRAL_TYPE_P (outer_type)))
 354             ;
 355           else if (INTEGRAL_TYPE_P (outer_type)
 356                    && INTEGRAL_TYPE_P (inner_type)
 357                    && TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME
 358                    && ssa_name_defined_by_comparison_p (TREE_OPERAND (def_rhs,
 359                                                                       0)))
 360             ;
 361           else
 362             return NULL_TREE;
 363
 364           /* Don't propagate if the operand occurs in
 365              an abnormal PHI.  */
 366           if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME
 367               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND
 368                                                   (def_rhs, 0)))
 369             return NULL_TREE;
 370
 371           if (has_single_use (test_var))
 372             {
 373               enum tree_code new_code;
 374               tree new_arg;
 375
 376               if (cond_code == SSA_NAME
 377                   || (cond_code == NE_EXPR
 378                       && integer_zerop (TREE_OPERAND (cond, 1)))
 379                   || (cond_code == EQ_EXPR
 380                       && integer_onep (TREE_OPERAND (cond, 1))))
 381                 new_code = NE_EXPR;
 382               else
 383                 new_code = EQ_EXPR;
 384
 385               new_arg = TREE_OPERAND (def_rhs, 0);
 386               new_cond = build2 (new_code, boolean_type_node, new_arg,
 387                                  fold_convert (TREE_TYPE (new_arg),
 388                                                integer_zero_node));
 389             }
 390         }
 391     }
 392
 393   *test_var_p = test_var;
 394   return new_cond;
 395 }
 396
 397 /* Forward propagate a single-use variable into COND_EXPR as many
 398    times as possible.  */
 399
 400 static void
 401 forward_propagate_into_cond (tree cond_expr)
 402 {
 403   gcc_assert (TREE_CODE (cond_expr) == COND_EXPR);
 404
 405   while (1)
 406     {
 407       tree test_var = NULL_TREE;
 408       tree cond = COND_EXPR_COND (cond_expr);
 409       tree new_cond = forward_propagate_into_cond_1 (cond, &test_var);
 410
 411       /* Return if unsuccessful.  */
 412       if (new_cond == NULL_TREE)
 413         break;
 414
 415       /* Dump details.  */
 416       if (dump_file && (dump_flags & TDF_DETAILS))
 417         {
 418           fprintf (dump_file, "  Replaced '");
 419           print_generic_expr (dump_file, cond, dump_flags);
 420           fprintf (dump_file, "' with '");
 421           print_generic_expr (dump_file, new_cond, dump_flags);
 422           fprintf (dump_file, "'\n");
 423         }
 424
 425       COND_EXPR_COND (cond_expr) = new_cond;
 426       update_stmt (cond_expr);
 427
 428       if (has_zero_uses (test_var))
 429         {
 430           tree def = SSA_NAME_DEF_STMT (test_var);
 431           block_stmt_iterator bsi = bsi_for_stmt (def);
 432           bsi_remove (&bsi);
 433         }
 434     }
 435 }
 436
 437 /* STMT defines LHS which is contains the address of the 0th element
 438    in an array.  USE_STMT uses LHS to compute the address of an
 439    arbitrary element within the array.  The (variable) byte offset
 440    of the element is contained in OFFSET.
 441
 442    We walk back through the use-def chains of OFFSET to verify that
 443    it is indeed computing the offset of an element within the array
 444    and extract the index corresponding to the given byte offset.
 445
 446    We then try to fold the entire address expression into a form
 447    &array[index].
 448
 449    If we are successful, we replace the right hand side of USE_STMT
 450    with the new address computation.  */
 451
 452 static bool
 453 forward_propagate_addr_into_variable_array_index (tree offset, tree lhs,
 454                                                   tree stmt, tree use_stmt)
 455 {
 456   tree index;
 457
 458   /* The offset must be defined by a simple MODIFY_EXPR statement.  */
 459   if (TREE_CODE (offset) != MODIFY_EXPR)
 460     return false;
 461
 462   /* The RHS of the statement which defines OFFSET must be a gimple
 463      cast of another SSA_NAME.  */
 464   offset = TREE_OPERAND (offset, 1);
 465   if (!is_gimple_cast (offset))
 466     return false;
 467
 468   offset = TREE_OPERAND (offset, 0);
 469   if (TREE_CODE (offset) != SSA_NAME)
 470     return false;
 471
 472   /* Get the defining statement of the offset before type
 473      conversion.  */
 474   offset = SSA_NAME_DEF_STMT (offset);
 475
 476   /* The statement which defines OFFSET before type conversion
 477      must be a simple MODIFY_EXPR.  */
 478   if (TREE_CODE (offset) != MODIFY_EXPR)
 479     return false;
 480
 481   /* The RHS of the statement which defines OFFSET must be a
 482      multiplication of an object by the size of the array elements.
 483      This implicitly verifies that the size of the array elements
 484      is constant.  */
 485   offset = TREE_OPERAND (offset, 1);
 486   if (TREE_CODE (offset) != MULT_EXPR
 487       || TREE_CODE (TREE_OPERAND (offset, 1)) != INTEGER_CST
 488       || !simple_cst_equal (TREE_OPERAND (offset, 1),
 489                             TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (lhs)))))
 490     return false;
 491
 492   /* The first operand to the MULT_EXPR is the desired index.  */
 493   index = TREE_OPERAND (offset, 0);
 494
 495   /* Replace the pointer addition with array indexing.  */
 496   TREE_OPERAND (use_stmt, 1) = unshare_expr (TREE_OPERAND (stmt, 1));
 497   TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 0), 1) = index;
 498
 499   /* That should have created gimple, so there is no need to
 500      record information to undo the propagation.  */
 501   fold_stmt (bsi_stmt_ptr (bsi_for_stmt (use_stmt)));
 502   mark_new_vars_to_rename (use_stmt);
 503   update_stmt (use_stmt);
 504   return true;
 505 }
 506
 507 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
 508
 509    Try to forward propagate the ADDR_EXPR into the uses of the SSA_NAME.
 510    Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
 511    node or for recovery of array indexing from pointer arithmetic.  */
 512
 513 static bool
 514 forward_propagate_addr_expr (tree stmt)
 515 {
 516   int stmt_loop_depth = bb_for_stmt (stmt)->loop_depth;
 517   tree name = TREE_OPERAND (stmt, 0);
 518   use_operand_p imm_use;
 519   tree use_stmt, lhs, rhs, array_ref;
 520
 521   /* We require that the SSA_NAME holding the result of the ADDR_EXPR
 522      be used only once.  That may be overly conservative in that we
 523      could propagate into multiple uses.  However, that would effectively
 524      be un-cseing the ADDR_EXPR, which is probably not what we want.  */
 525   single_imm_use (name, &imm_use, &use_stmt);
 526   if (!use_stmt)
 527     return false;
 528
 529   /* If the use is not in a simple assignment statement, then
 530      there is nothing we can do.  */
 531   if (TREE_CODE (use_stmt) != MODIFY_EXPR)
 532     return false;
 533
 534   /* If the use is in a deeper loop nest, then we do not want
 535      to propagate the ADDR_EXPR into the loop as that is likely
 536      adding expression evaluations into the loop.  */
 537   if (bb_for_stmt (use_stmt)->loop_depth > stmt_loop_depth)
 538     return false;
 539
 540   /* If the two statements belong to different EH regions, then there
 541      is nothing we can or should try to do.  */
 542   if (lookup_stmt_eh_region (use_stmt) != lookup_stmt_eh_region (stmt))
 543     return false;
 544
 545   /* Strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.  */
 546   lhs = TREE_OPERAND (use_stmt, 0);
 547   while (TREE_CODE (lhs) == COMPONENT_REF || TREE_CODE (lhs) == ARRAY_REF)
 548     lhs = TREE_OPERAND (lhs, 0);
 549
 550   /* Now see if the LHS node is an INDIRECT_REF using NAME.  If so,
 551      propagate the ADDR_EXPR into the use of NAME and fold the result.  */
 552   if (TREE_CODE (lhs) == INDIRECT_REF && TREE_OPERAND (lhs, 0) == name)
 553     {
 554       /* This should always succeed in creating gimple, so there is
 555          no need to save enough state to undo this propagation.  */
 556       TREE_OPERAND (lhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1));
 557       fold_stmt (bsi_stmt_ptr (bsi_for_stmt (use_stmt)));
 558       mark_new_vars_to_rename (use_stmt);
 559       update_stmt (use_stmt);
 560       return true;
 561     }
 562
 563   /* Trivial case.  The use statement could be a trivial copy.  We
 564      go ahead and handle that case here since it's trivial and
 565      removes the need to run copy-prop before this pass to get
 566      the best results.  Also note that by handling this case here
 567      we can catch some cascading effects, ie the single use is
 568      in a copy, and the copy is used later by a single INDIRECT_REF
 569      for example.  */
 570   if (TREE_CODE (lhs) == SSA_NAME && TREE_OPERAND (use_stmt, 1) == name)
 571     {
 572       TREE_OPERAND (use_stmt, 1) = unshare_expr (TREE_OPERAND (stmt, 1));
 573       mark_new_vars_to_rename (use_stmt);
 574       update_stmt (use_stmt);
 575       return true;
 576     }
 577
 578   /* Strip away any outer COMPONENT_REF/ARRAY_REF nodes from the RHS.  */
 579   rhs = TREE_OPERAND (use_stmt, 1);
 580   while (TREE_CODE (rhs) == COMPONENT_REF || TREE_CODE (rhs) == ARRAY_REF)
 581     rhs = TREE_OPERAND (rhs, 0);
 582
 583   /* Now see if the RHS node is an INDIRECT_REF using NAME.  If so,
 584      propagate the ADDR_EXPR into the use of NAME and fold the result.  */
 585   if (TREE_CODE (rhs) == INDIRECT_REF && TREE_OPERAND (rhs, 0) == name)
 586     {
 587       /* This should always succeed in creating gimple, so there is
 588          no need to save enough state to undo this propagation.  */
 589       TREE_OPERAND (rhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1));
 590       fold_stmt (bsi_stmt_ptr (bsi_for_stmt (use_stmt)));
 591       mark_new_vars_to_rename (use_stmt);
 592       update_stmt (use_stmt);
 593       return true;
 594     }
 595
 596   /* The remaining cases are all for turning pointer arithmetic into
 597      array indexing.  They only apply when we have the address of
 598      element zero in an array.  If that is not the case then there
 599      is nothing to do.  */
 600   array_ref = TREE_OPERAND (TREE_OPERAND (stmt, 1), 0);
 601   if (TREE_CODE (array_ref) != ARRAY_REF
 602       || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
 603       || !integer_zerop (TREE_OPERAND (array_ref, 1)))
 604     return false;
 605
 606   /* If the use of the ADDR_EXPR must be a PLUS_EXPR, or else there
 607      is nothing to do. */
 608   if (TREE_CODE (rhs) != PLUS_EXPR)
 609     return false;
 610
 611   /* Try to optimize &x[0] + C where C is a multiple of the size
 612      of the elements in X into &x[C/element size].  */
 613   if (TREE_OPERAND (rhs, 0) == name
 614       && TREE_CODE (TREE_OPERAND (rhs, 1)) == INTEGER_CST)
 615     {
 616       tree orig = unshare_expr (rhs);
 617       TREE_OPERAND (rhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1));
 618
 619       /* If folding succeeds, then we have just exposed new variables
 620          in USE_STMT which will need to be renamed.  If folding fails,
 621          then we need to put everything back the way it was.  */
 622       if (fold_stmt (bsi_stmt_ptr (bsi_for_stmt (use_stmt))))
 623         {
 624           mark_new_vars_to_rename (use_stmt);
 625           update_stmt (use_stmt);
 626           return true;
 627         }
 628       else
 629         {
 630           TREE_OPERAND (use_stmt, 1) = orig;
 631           update_stmt (use_stmt);
 632           return false;
 633         }
 634     }
 635
 636   /* Try to optimize &x[0] + OFFSET where OFFSET is defined by
 637      converting a multiplication of an index by the size of the
 638      array elements, then the result is converted into the proper
 639      type for the arithmetic.  */
 640   if (TREE_OPERAND (rhs, 0) == name
 641       && TREE_CODE (TREE_OPERAND (rhs, 1)) == SSA_NAME
 642       /* Avoid problems with IVopts creating PLUS_EXPRs with a
 643          different type than their operands.  */
 644       && lang_hooks.types_compatible_p (TREE_TYPE (name), TREE_TYPE (rhs)))
 645     {
 646       tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1));
 647       return forward_propagate_addr_into_variable_array_index (offset_stmt, lhs,
 648                                                                stmt, use_stmt);
 649     }
 650
 651   /* Same as the previous case, except the operands of the PLUS_EXPR
 652      were reversed.  */
 653   if (TREE_OPERAND (rhs, 1) == name
 654       && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
 655       /* Avoid problems with IVopts creating PLUS_EXPRs with a
 656          different type than their operands.  */
 657       && lang_hooks.types_compatible_p (TREE_TYPE (name), TREE_TYPE (rhs)))
 658     {
 659       tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
 660       return forward_propagate_addr_into_variable_array_index (offset_stmt, lhs,
 661                                                                stmt, use_stmt);
 662     }
 663   return false;
 664 }
 665
 666 /* Main entry point for the forward propagation optimizer.  */
 667
 668 static void
 669 tree_ssa_forward_propagate_single_use_vars (void)
 670 {
 671   basic_block bb;
 672
 673   FOR_EACH_BB (bb)
 674     {
 675       block_stmt_iterator bsi;
 676
 677       /* Note we update BSI within the loop as necessary.  */
 678       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
 679         {
 680           tree stmt = bsi_stmt (bsi);
 681
 682           /* If this statement sets an SSA_NAME to an address,
 683              try to propagate the address into the uses of the SSA_NAME.  */
 684           if (TREE_CODE (stmt) == MODIFY_EXPR
 685               && TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR
 686               && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)
 687             {
 688               if (forward_propagate_addr_expr (stmt))
 689                 bsi_remove (&bsi);
 690               else
 691                 bsi_next (&bsi);
 692             }
 693           else if (TREE_CODE (stmt) == COND_EXPR)
 694             {
 695               forward_propagate_into_cond (stmt);
 696               bsi_next (&bsi);
 697             }
 698           else
 699             bsi_next (&bsi);
 700         }
 701     }
 702 }
 703
 704
 705 static bool
 706 gate_forwprop (void)
 707 {
 708   return 1;
 709 }
 710
 711 struct tree_opt_pass pass_forwprop = {
 712   "forwprop",                   /* name */
 713   gate_forwprop,                /* gate */
 714   tree_ssa_forward_propagate_single_use_vars,   /* execute */
 715   NULL,                         /* sub */
 716   NULL,                         /* next */
 717   0,                            /* static_pass_number */
 718   TV_TREE_FORWPROP,             /* tv_id */
 719   PROP_cfg | PROP_ssa
 720     | PROP_alias,               /* properties_required */
 721   0,                            /* properties_provided */
 722   0,                            /* properties_destroyed */
 723   0,                            /* todo_flags_start */
 724   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 725   | TODO_update_ssa | TODO_verify_ssa,
 726   0                                     /* letter */
 727 };