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