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 use USE_STMT.
 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    Return true, if the propagation was successful.  */
 535
 536 static bool
 537 forward_propagate_addr_expr_1 (tree stmt, tree use_stmt)
 538 {
 539   tree name = TREE_OPERAND (stmt, 0);
 540   tree lhs, rhs, array_ref;
 541
 542   /* Strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
 543      ADDR_EXPR will not appear on the LHS.  */
 544   lhs = TREE_OPERAND (use_stmt, 0);
 545   while (TREE_CODE (lhs) == COMPONENT_REF || TREE_CODE (lhs) == ARRAY_REF)
 546     lhs = TREE_OPERAND (lhs, 0);
 547
 548   /* Now see if the LHS node is an INDIRECT_REF using NAME.  If so,
 549      propagate the ADDR_EXPR into the use of NAME and fold the result.  */
 550   if (TREE_CODE (lhs) == INDIRECT_REF && TREE_OPERAND (lhs, 0) == name)
 551     {
 552       /* This should always succeed in creating gimple, so there is
 553          no need to save enough state to undo this propagation.  */
 554       TREE_OPERAND (lhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1));
 555       fold_stmt_inplace (use_stmt);
 556       tidy_after_forward_propagate_addr (use_stmt);
 557       return true;
 558     }
 559
 560   /* Trivial case.  The use statement could be a trivial copy.  We
 561      go ahead and handle that case here since it's trivial and
 562      removes the need to run copy-prop before this pass to get
 563      the best results.  Also note that by handling this case here
 564      we can catch some cascading effects, ie the single use is
 565      in a copy, and the copy is used later by a single INDIRECT_REF
 566      for example.  */
 567   if (TREE_CODE (lhs) == SSA_NAME && TREE_OPERAND (use_stmt, 1) == name)
 568     {
 569       TREE_OPERAND (use_stmt, 1) = unshare_expr (TREE_OPERAND (stmt, 1));
 570       tidy_after_forward_propagate_addr (use_stmt);
 571       return true;
 572     }
 573
 574   /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
 575      nodes from the RHS.  */
 576   rhs = TREE_OPERAND (use_stmt, 1);
 577   while (TREE_CODE (rhs) == COMPONENT_REF
 578          || TREE_CODE (rhs) == ARRAY_REF
 579          || TREE_CODE (rhs) == ADDR_EXPR)
 580     rhs = TREE_OPERAND (rhs, 0);
 581
 582   /* Now see if the RHS node is an INDIRECT_REF using NAME.  If so,
 583      propagate the ADDR_EXPR into the use of NAME and fold the result.  */
 584   if (TREE_CODE (rhs) == INDIRECT_REF && TREE_OPERAND (rhs, 0) == name)
 585     {
 586       /* This should always succeed in creating gimple, so there is
 587          no need to save enough state to undo this propagation.  */
 588       TREE_OPERAND (rhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1));
 589       fold_stmt_inplace (use_stmt);
 590       tidy_after_forward_propagate_addr (use_stmt);
 591       return true;
 592     }
 593
 594   /* The remaining cases are all for turning pointer arithmetic into
 595      array indexing.  They only apply when we have the address of
 596      element zero in an array.  If that is not the case then there
 597      is nothing to do.  */
 598   array_ref = TREE_OPERAND (TREE_OPERAND (stmt, 1), 0);
 599   if (TREE_CODE (array_ref) != ARRAY_REF
 600       || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
 601       || !integer_zerop (TREE_OPERAND (array_ref, 1)))
 602     return false;
 603
 604   /* If the use of the ADDR_EXPR must be a PLUS_EXPR, or else there
 605      is nothing to do. */
 606   if (TREE_CODE (rhs) != PLUS_EXPR)
 607     return false;
 608
 609   /* Try to optimize &x[0] + C where C is a multiple of the size
 610      of the elements in X into &x[C/element size].  */
 611   if (TREE_OPERAND (rhs, 0) == name
 612       && TREE_CODE (TREE_OPERAND (rhs, 1)) == INTEGER_CST)
 613     {
 614       tree orig = unshare_expr (rhs);
 615       TREE_OPERAND (rhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1));
 616
 617       /* If folding succeeds, then we have just exposed new variables
 618          in USE_STMT which will need to be renamed.  If folding fails,
 619          then we need to put everything back the way it was.  */
 620       if (fold_stmt_inplace (use_stmt))
 621         {
 622           tidy_after_forward_propagate_addr (use_stmt);
 623           return true;
 624         }
 625       else
 626         {
 627           TREE_OPERAND (use_stmt, 1) = orig;
 628           update_stmt (use_stmt);
 629           return false;
 630         }
 631     }
 632
 633   /* Try to optimize &x[0] + OFFSET where OFFSET is defined by
 634      converting a multiplication of an index by the size of the
 635      array elements, then the result is converted into the proper
 636      type for the arithmetic.  */
 637   if (TREE_OPERAND (rhs, 0) == name
 638       && TREE_CODE (TREE_OPERAND (rhs, 1)) == SSA_NAME
 639       /* Avoid problems with IVopts creating PLUS_EXPRs with a
 640          different type than their operands.  */
 641       && lang_hooks.types_compatible_p (TREE_TYPE (name), TREE_TYPE (rhs)))
 642     {
 643       tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1));
 644       return forward_propagate_addr_into_variable_array_index (offset_stmt, lhs,
 645                                                                stmt, use_stmt);
 646     }
 647
 648   /* Same as the previous case, except the operands of the PLUS_EXPR
 649      were reversed.  */
 650   if (TREE_OPERAND (rhs, 1) == name
 651       && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
 652       /* Avoid problems with IVopts creating PLUS_EXPRs with a
 653          different type than their operands.  */
 654       && lang_hooks.types_compatible_p (TREE_TYPE (name), TREE_TYPE (rhs)))
 655     {
 656       tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
 657       return forward_propagate_addr_into_variable_array_index (offset_stmt, lhs,
 658                                                                stmt, use_stmt);
 659     }
 660   return false;
 661 }
 662
 663 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
 664
 665    Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
 666    Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
 667    node or for recovery of array indexing from pointer arithmetic.
 668    Returns true, if all uses have been propagated into.  */
 669
 670 static bool
 671 forward_propagate_addr_expr (tree stmt)
 672 {
 673   int stmt_loop_depth = bb_for_stmt (stmt)->loop_depth;
 674   tree name = TREE_OPERAND (stmt, 0);
 675   use_operand_p imm_use;
 676   imm_use_iterator iter;
 677   bool all = true;
 678
 679   FOR_EACH_IMM_USE_SAFE (imm_use, iter, name)
 680     {
 681       tree use_stmt = USE_STMT (imm_use);
 682
 683       /* If the use is not in a simple assignment statement, then
 684          there is nothing we can do.  */
 685       if (TREE_CODE (use_stmt) != MODIFY_EXPR)
 686         {
 687           all = false;
 688           continue;
 689         }
 690
 691      /* If the use is in a deeper loop nest, then we do not want
 692         to propagate the ADDR_EXPR into the loop as that is likely
 693         adding expression evaluations into the loop.  */
 694       if (bb_for_stmt (use_stmt)->loop_depth > stmt_loop_depth)
 695         {
 696           all = false;
 697           continue;
 698         }
 699
 700       all = all && forward_propagate_addr_expr_1 (stmt, use_stmt);
 701     }
 702
 703   return all;
 704 }
 705
 706
 707 /* Main entry point for the forward propagation optimizer.  */
 708
 709 static void
 710 tree_ssa_forward_propagate_single_use_vars (void)
 711 {
 712   basic_block bb;
 713
 714   cfg_changed = false;
 715
 716   FOR_EACH_BB (bb)
 717     {
 718       block_stmt_iterator bsi;
 719
 720       /* Note we update BSI within the loop as necessary.  */
 721       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
 722         {
 723           tree stmt = bsi_stmt (bsi);
 724
 725           /* If this statement sets an SSA_NAME to an address,
 726              try to propagate the address into the uses of the SSA_NAME.  */
 727           if (TREE_CODE (stmt) == MODIFY_EXPR
 728               && TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR
 729               && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)
 730             {
 731               if (forward_propagate_addr_expr (stmt))
 732                 bsi_remove (&bsi);
 733               else
 734                 bsi_next (&bsi);
 735             }
 736           else if (TREE_CODE (stmt) == COND_EXPR)
 737             {
 738               forward_propagate_into_cond (stmt);
 739               bsi_next (&bsi);
 740             }
 741           else
 742             bsi_next (&bsi);
 743         }
 744     }
 745
 746   if (cfg_changed)
 747     cleanup_tree_cfg ();
 748 }
 749
 750
 751 static bool
 752 gate_forwprop (void)
 753 {
 754   return 1;
 755 }
 756
 757 struct tree_opt_pass pass_forwprop = {
 758   "forwprop",                   /* name */
 759   gate_forwprop,                /* gate */
 760   tree_ssa_forward_propagate_single_use_vars,   /* execute */
 761   NULL,                         /* sub */
 762   NULL,                         /* next */
 763   0,                            /* static_pass_number */
 764   TV_TREE_FORWPROP,             /* tv_id */
 765   PROP_cfg | PROP_ssa
 766     | PROP_alias,               /* properties_required */
 767   0,                            /* properties_provided */
 768   0,                            /* properties_destroyed */
 769   0,                            /* todo_flags_start */
 770   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 771   | TODO_update_ssa | TODO_verify_ssa,
 772   0                                     /* letter */
 773 };