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