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.   It is hoped all of this can disappear
  40    when we have a generalized tree combiner.
  41
  42    Note carefully that after propagation the resulting statement
  43    must still be a proper gimple statement.  Right now we simply
  44    only perform propagations we know will result in valid gimple
  45    code.  One day we'll want to generalize this code.
  46
  47    One class of common cases we handle is forward propagating a single use
  48    variable into a COND_EXPR.
  49
  50      bb0:
  51        x = a COND b;
  52        if (x) goto ... else goto ...
  53
  54    Will be transformed into:
  55
  56      bb0:
  57        if (a COND b) goto ... else goto ...
  58
  59    Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
  60
  61    Or (assuming c1 and c2 are constants):
  62
  63      bb0:
  64        x = a + c1;
  65        if (x EQ/NEQ c2) goto ... else goto ...
  66
  67    Will be transformed into:
  68
  69      bb0:
  70         if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
  71
  72    Similarly for x = a - c1.
  73
  74    Or
  75
  76      bb0:
  77        x = !a
  78        if (x) goto ... else goto ...
  79
  80    Will be transformed into:
  81
  82      bb0:
  83         if (a == 0) goto ... else goto ...
  84
  85    Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
  86    For these cases, we propagate A into all, possibly more than one,
  87    COND_EXPRs that use X.
  88
  89    Or
  90
  91      bb0:
  92        x = (typecast) a
  93        if (x) goto ... else goto ...
  94
  95    Will be transformed into:
  96
  97      bb0:
  98         if (a != 0) goto ... else goto ...
  99
 100    (Assuming a is an integral type and x is a boolean or x is an
 101     integral and a is a boolean.)
 102
 103    Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
 104    For these cases, we propagate A into all, possibly more than one,
 105    COND_EXPRs that use X.
 106
 107    In addition to eliminating the variable and the statement which assigns
 108    a value to the variable, we may be able to later thread the jump without
 109    adding insane complexity in the dominator optimizer.
 110
 111    Also note these transformations can cascade.  We handle this by having
 112    a worklist of COND_EXPR statements to examine.  As we make a change to
 113    a statement, we put it back on the worklist to examine on the next
 114    iteration of the main loop.
 115
 116    A second class of propagation opportunities arises for ADDR_EXPR
 117    nodes.
 118
 119      ptr = &x->y->z;
 120      res = *ptr;
 121
 122    Will get turned into
 123
 124      res = x->y->z;
 125
 126    Or
 127
 128      ptr = &x[0];
 129      ptr2 = ptr + <constant>;
 130
 131    Will get turned into
 132
 133      ptr2 = &x[constant/elementsize];
 134
 135   Or
 136
 137      ptr = &x[0];
 138      offset = index * element_size;
 139      offset_p = (pointer) offset;
 140      ptr2 = ptr + offset_p
 141
 142   Will get turned into:
 143
 144      ptr2 = &x[index];
 145
 146   We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to
 147   allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent
 148   {NOT_EXPR,NEG_EXPR}.
 149
 150    This will (of course) be extended as other needs arise.  */
 151
 152 static bool forward_propagate_addr_expr (tree name, tree rhs);
 153
 154 /* Set to true if we delete EH edges during the optimization.  */
 155 static bool cfg_changed;
 156
 157
 158 /* Given an SSA_NAME VAR, return true if and only if VAR is defined by
 159    a comparison.  */
 160
 161 static bool
 162 ssa_name_defined_by_comparison_p (tree var)
 163 {
 164   tree def = SSA_NAME_DEF_STMT (var);
 165
 166   if (TREE_CODE (def) == GIMPLE_MODIFY_STMT)
 167     {
 168       tree rhs = GIMPLE_STMT_OPERAND (def, 1);
 169       return COMPARISON_CLASS_P (rhs);
 170     }
 171
 172   return 0;
 173 }
 174
 175 /* Forward propagate a single-use variable into COND once.  Return a
 176    new condition if successful.  Return NULL_TREE otherwise.  */
 177
 178 static tree
 179 forward_propagate_into_cond_1 (tree cond, tree *test_var_p)
 180 {
 181   tree new_cond = NULL_TREE;
 182   enum tree_code cond_code = TREE_CODE (cond);
 183   tree test_var = NULL_TREE;
 184   tree def;
 185   tree def_rhs;
 186
 187   /* If the condition is not a lone variable or an equality test of an
 188      SSA_NAME against an integral constant, then we do not have an
 189      optimizable case.
 190
 191      Note these conditions also ensure the COND_EXPR has no
 192      virtual operands or other side effects.  */
 193   if (cond_code != SSA_NAME
 194       && !((cond_code == EQ_EXPR || cond_code == NE_EXPR)
 195            && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
 196            && CONSTANT_CLASS_P (TREE_OPERAND (cond, 1))
 197            && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
 198     return NULL_TREE;
 199
 200   /* Extract the single variable used in the test into TEST_VAR.  */
 201   if (cond_code == SSA_NAME)
 202     test_var = cond;
 203   else
 204     test_var = TREE_OPERAND (cond, 0);
 205
 206   /* Now get the defining statement for TEST_VAR.  Skip this case if
 207      it's not defined by some GIMPLE_MODIFY_STMT.  */
 208   def = SSA_NAME_DEF_STMT (test_var);
 209   if (TREE_CODE (def) != GIMPLE_MODIFY_STMT)
 210     return NULL_TREE;
 211
 212   def_rhs = GIMPLE_STMT_OPERAND (def, 1);
 213
 214   /* If TEST_VAR is set by adding or subtracting a constant
 215      from an SSA_NAME, then it is interesting to us as we
 216      can adjust the constant in the conditional and thus
 217      eliminate the arithmetic operation.  */
 218   if (TREE_CODE (def_rhs) == PLUS_EXPR
 219       || TREE_CODE (def_rhs) == MINUS_EXPR)
 220     {
 221       tree op0 = TREE_OPERAND (def_rhs, 0);
 222       tree op1 = TREE_OPERAND (def_rhs, 1);
 223
 224       /* The first operand must be an SSA_NAME and the second
 225          operand must be a constant.  */
 226       if (TREE_CODE (op0) != SSA_NAME
 227           || !CONSTANT_CLASS_P (op1)
 228           || !INTEGRAL_TYPE_P (TREE_TYPE (op1)))
 229         return NULL_TREE;
 230
 231       /* Don't propagate if the first operand occurs in
 232          an abnormal PHI.  */
 233       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
 234         return NULL_TREE;
 235
 236       if (has_single_use (test_var))
 237         {
 238           enum tree_code new_code;
 239           tree t;
 240
 241           /* If the variable was defined via X + C, then we must
 242              subtract C from the constant in the conditional.
 243              Otherwise we add C to the constant in the
 244              conditional.  The result must fold into a valid
 245              gimple operand to be optimizable.  */
 246           new_code = (TREE_CODE (def_rhs) == PLUS_EXPR
 247                       ? MINUS_EXPR : PLUS_EXPR);
 248           t = int_const_binop (new_code, TREE_OPERAND (cond, 1), op1, 0);
 249           if (!is_gimple_val (t))
 250             return NULL_TREE;
 251
 252           new_cond = build2 (cond_code, boolean_type_node, op0, t);
 253         }
 254     }
 255
 256   /* These cases require comparisons of a naked SSA_NAME or
 257      comparison of an SSA_NAME against zero or one.  */
 258   else if (TREE_CODE (cond) == SSA_NAME
 259            || integer_zerop (TREE_OPERAND (cond, 1))
 260            || integer_onep (TREE_OPERAND (cond, 1)))
 261     {
 262       /* If TEST_VAR is set from a relational operation
 263          between two SSA_NAMEs or a combination of an SSA_NAME
 264          and a constant, then it is interesting.  */
 265       if (COMPARISON_CLASS_P (def_rhs))
 266         {
 267           tree op0 = TREE_OPERAND (def_rhs, 0);
 268           tree op1 = TREE_OPERAND (def_rhs, 1);
 269
 270           /* Both operands of DEF_RHS must be SSA_NAMEs or
 271              constants.  */
 272           if ((TREE_CODE (op0) != SSA_NAME
 273                && !is_gimple_min_invariant (op0))
 274               || (TREE_CODE (op1) != SSA_NAME
 275                   && !is_gimple_min_invariant (op1)))
 276             return NULL_TREE;
 277
 278           /* Don't propagate if the first operand occurs in
 279              an abnormal PHI.  */
 280           if (TREE_CODE (op0) == SSA_NAME
 281               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
 282             return NULL_TREE;
 283
 284           /* Don't propagate if the second operand occurs in
 285              an abnormal PHI.  */
 286           if (TREE_CODE (op1) == SSA_NAME
 287               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))
 288             return NULL_TREE;
 289
 290           if (has_single_use (test_var))
 291             {
 292               /* TEST_VAR was set from a relational operator.  */
 293               new_cond = build2 (TREE_CODE (def_rhs),
 294                                  boolean_type_node, op0, op1);
 295
 296               /* Invert the conditional if necessary.  */
 297               if ((cond_code == EQ_EXPR
 298                    && integer_zerop (TREE_OPERAND (cond, 1)))
 299                   || (cond_code == NE_EXPR
 300                       && integer_onep (TREE_OPERAND (cond, 1))))
 301                 {
 302                   new_cond = invert_truthvalue (new_cond);
 303
 304                   /* If we did not get a simple relational
 305                      expression or bare SSA_NAME, then we can
 306                      not optimize this case.  */
 307                   if (!COMPARISON_CLASS_P (new_cond)
 308                       && TREE_CODE (new_cond) != SSA_NAME)
 309                     new_cond = NULL_TREE;
 310                 }
 311             }
 312         }
 313
 314       /* If TEST_VAR is set from a TRUTH_NOT_EXPR, then it
 315          is interesting.  */
 316       else if (TREE_CODE (def_rhs) == TRUTH_NOT_EXPR)
 317         {
 318           enum tree_code new_code;
 319
 320           def_rhs = TREE_OPERAND (def_rhs, 0);
 321
 322           /* DEF_RHS must be an SSA_NAME or constant.  */
 323           if (TREE_CODE (def_rhs) != SSA_NAME
 324               && !is_gimple_min_invariant (def_rhs))
 325             return NULL_TREE;
 326
 327           /* Don't propagate if the operand occurs in
 328              an abnormal PHI.  */
 329           if (TREE_CODE (def_rhs) == SSA_NAME
 330               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_rhs))
 331             return NULL_TREE;
 332
 333           if (cond_code == SSA_NAME
 334               || (cond_code == NE_EXPR
 335                   && integer_zerop (TREE_OPERAND (cond, 1)))
 336               || (cond_code == EQ_EXPR
 337                   && integer_onep (TREE_OPERAND (cond, 1))))
 338             new_code = EQ_EXPR;
 339           else
 340             new_code = NE_EXPR;
 341
 342           new_cond = build2 (new_code, boolean_type_node, def_rhs,
 343                              fold_convert (TREE_TYPE (def_rhs),
 344                                            integer_zero_node));
 345         }
 346
 347       /* If TEST_VAR was set from a cast of an integer type
 348          to a boolean type or a cast of a boolean to an
 349          integral, then it is interesting.  */
 350       else if (TREE_CODE (def_rhs) == NOP_EXPR
 351                || TREE_CODE (def_rhs) == CONVERT_EXPR)
 352         {
 353           tree outer_type;
 354           tree inner_type;
 355
 356           outer_type = TREE_TYPE (def_rhs);
 357           inner_type = TREE_TYPE (TREE_OPERAND (def_rhs, 0));
 358
 359           if ((TREE_CODE (outer_type) == BOOLEAN_TYPE
 360                && INTEGRAL_TYPE_P (inner_type))
 361               || (TREE_CODE (inner_type) == BOOLEAN_TYPE
 362                   && INTEGRAL_TYPE_P (outer_type)))
 363             ;
 364           else if (INTEGRAL_TYPE_P (outer_type)
 365                    && INTEGRAL_TYPE_P (inner_type)
 366                    && TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME
 367                    && ssa_name_defined_by_comparison_p (TREE_OPERAND (def_rhs,
 368                                                                       0)))
 369             ;
 370           else
 371             return NULL_TREE;
 372
 373           /* Don't propagate if the operand occurs in
 374              an abnormal PHI.  */
 375           if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME
 376               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND
 377                                                   (def_rhs, 0)))
 378             return NULL_TREE;
 379
 380           if (has_single_use (test_var))
 381             {
 382               enum tree_code new_code;
 383               tree new_arg;
 384
 385               if (cond_code == SSA_NAME
 386                   || (cond_code == NE_EXPR
 387                       && integer_zerop (TREE_OPERAND (cond, 1)))
 388                   || (cond_code == EQ_EXPR
 389                       && integer_onep (TREE_OPERAND (cond, 1))))
 390                 new_code = NE_EXPR;
 391               else
 392                 new_code = EQ_EXPR;
 393
 394               new_arg = TREE_OPERAND (def_rhs, 0);
 395               new_cond = build2 (new_code, boolean_type_node, new_arg,
 396                                  fold_convert (TREE_TYPE (new_arg),
 397                                                integer_zero_node));
 398             }
 399         }
 400     }
 401
 402   *test_var_p = test_var;
 403   return new_cond;
 404 }
 405
 406 /* COND is a condition of the form:
 407
 408      x == const or x != const
 409
 410    Look back to x's defining statement and see if x is defined as
 411
 412      x = (type) y;
 413
 414    If const is unchanged if we convert it to type, then we can build
 415    the equivalent expression:
 416
 417
 418       y == const or y != const
 419
 420    Which may allow further optimizations.
 421
 422    Return the equivalent comparison or NULL if no such equivalent comparison
 423    was found.  */
 424
 425 static tree
 426 find_equivalent_equality_comparison (tree cond)
 427 {
 428   tree op0 = TREE_OPERAND (cond, 0);
 429   tree op1 = TREE_OPERAND (cond, 1);
 430   tree def_stmt = SSA_NAME_DEF_STMT (op0);
 431
 432   while (def_stmt
 433          && TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
 434          && TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == SSA_NAME)
 435     def_stmt = SSA_NAME_DEF_STMT (GIMPLE_STMT_OPERAND (def_stmt, 1));
 436
 437   /* OP0 might have been a parameter, so first make sure it
 438      was defined by a GIMPLE_MODIFY_STMT.  */
 439   if (def_stmt && TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT)
 440     {
 441       tree def_rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
 442
 443       /* If either operand to the comparison is a pointer to
 444          a function, then we can not apply this optimization
 445          as some targets require function pointers to be
 446          canonicalized and in this case this optimization would
 447          eliminate a necessary canonicalization.  */
 448       if ((POINTER_TYPE_P (TREE_TYPE (op0))
 449            && TREE_CODE (TREE_TYPE (TREE_TYPE (op0))) == FUNCTION_TYPE)
 450           || (POINTER_TYPE_P (TREE_TYPE (op1))
 451               && TREE_CODE (TREE_TYPE (TREE_TYPE (op1))) == FUNCTION_TYPE))
 452         return NULL;
 453
 454       /* Now make sure the RHS of the GIMPLE_MODIFY_STMT is a typecast.  */
 455       if ((TREE_CODE (def_rhs) == NOP_EXPR
 456            || TREE_CODE (def_rhs) == CONVERT_EXPR)
 457           && TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME)
 458         {
 459           tree def_rhs_inner = TREE_OPERAND (def_rhs, 0);
 460           tree def_rhs_inner_type = TREE_TYPE (def_rhs_inner);
 461           tree new;
 462
 463           if (TYPE_PRECISION (def_rhs_inner_type)
 464               > TYPE_PRECISION (TREE_TYPE (def_rhs)))
 465             return NULL;
 466
 467           /* If the inner type of the conversion is a pointer to
 468              a function, then we can not apply this optimization
 469              as some targets require function pointers to be
 470              canonicalized.  This optimization would result in
 471              canonicalization of the pointer when it was not originally
 472              needed/intended.  */
 473           if (POINTER_TYPE_P (def_rhs_inner_type)
 474               && TREE_CODE (TREE_TYPE (def_rhs_inner_type)) == FUNCTION_TYPE)
 475             return NULL;
 476
 477           /* What we want to prove is that if we convert OP1 to
 478              the type of the object inside the NOP_EXPR that the
 479              result is still equivalent to SRC.
 480
 481              If that is true, the build and return new equivalent
 482              condition which uses the source of the typecast and the
 483              new constant (which has only changed its type).  */
 484           new = fold_build1 (TREE_CODE (def_rhs), def_rhs_inner_type, op1);
 485           STRIP_USELESS_TYPE_CONVERSION (new);
 486           if (is_gimple_val (new) && tree_int_cst_equal (new, op1))
 487             return build2 (TREE_CODE (cond), TREE_TYPE (cond),
 488                            def_rhs_inner, new);
 489         }
 490     }
 491   return NULL;
 492 }
 493
 494 /* EXPR is a COND_EXPR
 495    STMT is the statement containing EXPR.
 496
 497    This routine attempts to find equivalent forms of the condition
 498    which we may be able to optimize better.  */
 499
 500 static void
 501 simplify_cond (tree cond_expr, tree stmt)
 502 {
 503   tree cond = COND_EXPR_COND (cond_expr);
 504
 505   if (COMPARISON_CLASS_P (cond))
 506     {
 507       tree op0 = TREE_OPERAND (cond, 0);
 508       tree op1 = TREE_OPERAND (cond, 1);
 509
 510       if (TREE_CODE (op0) == SSA_NAME && is_gimple_min_invariant (op1))
 511         {
 512           /* First see if we have test of an SSA_NAME against a constant
 513              where the SSA_NAME is defined by an earlier typecast which
 514              is irrelevant when performing tests against the given
 515              constant.  */
 516           if (TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
 517             {
 518               tree new_cond = find_equivalent_equality_comparison (cond);
 519
 520               if (new_cond)
 521                 {
 522                   COND_EXPR_COND (cond_expr) = new_cond;
 523                   update_stmt (stmt);
 524                 }
 525             }
 526         }
 527     }
 528 }
 529
 530 /* Forward propagate a single-use variable into COND_EXPR as many
 531    times as possible.  */
 532
 533 static void
 534 forward_propagate_into_cond (tree cond_expr, tree stmt)
 535 {
 536   gcc_assert (TREE_CODE (cond_expr) == COND_EXPR);
 537
 538   while (1)
 539     {
 540       tree test_var = NULL_TREE;
 541       tree cond = COND_EXPR_COND (cond_expr);
 542       tree new_cond = forward_propagate_into_cond_1 (cond, &test_var);
 543
 544       /* Return if unsuccessful.  */
 545       if (new_cond == NULL_TREE)
 546         break;
 547
 548       /* Dump details.  */
 549       if (dump_file && (dump_flags & TDF_DETAILS))
 550         {
 551           fprintf (dump_file, "  Replaced '");
 552           print_generic_expr (dump_file, cond, dump_flags);
 553           fprintf (dump_file, "' with '");
 554           print_generic_expr (dump_file, new_cond, dump_flags);
 555           fprintf (dump_file, "'\n");
 556         }
 557
 558       COND_EXPR_COND (cond_expr) = new_cond;
 559       update_stmt (stmt);
 560
 561       if (has_zero_uses (test_var))
 562         {
 563           tree def = SSA_NAME_DEF_STMT (test_var);
 564           block_stmt_iterator bsi = bsi_for_stmt (def);
 565           bsi_remove (&bsi, true);
 566           release_defs (def);
 567         }
 568     }
 569
 570   /* There are further simplifications that can be performed
 571      on COND_EXPRs.  Specifically, when comparing an SSA_NAME
 572      against a constant where the SSA_NAME is the result of a
 573      conversion.  Perhaps this should be folded into the rest
 574      of the COND_EXPR simplification code.  */
 575   simplify_cond (cond_expr, stmt);
 576 }
 577
 578 /* We've just substituted an ADDR_EXPR into stmt.  Update all the
 579    relevant data structures to match.  */
 580
 581 static void
 582 tidy_after_forward_propagate_addr (tree stmt)
 583 {
 584   /* We may have turned a trapping insn into a non-trapping insn.  */
 585   if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
 586       && tree_purge_dead_eh_edges (bb_for_stmt (stmt)))
 587     cfg_changed = true;
 588
 589   if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == ADDR_EXPR)
 590      recompute_tree_invariant_for_addr_expr (GIMPLE_STMT_OPERAND (stmt, 1));
 591
 592   mark_symbols_for_renaming (stmt);
 593 }
 594
 595 /* DEF_RHS defines LHS which is contains the address of the 0th element
 596    in an array.  USE_STMT uses LHS to compute the address of an
 597    arbitrary element within the array.  The (variable) byte offset
 598    of the element is contained in OFFSET.
 599
 600    We walk back through the use-def chains of OFFSET to verify that
 601    it is indeed computing the offset of an element within the array
 602    and extract the index corresponding to the given byte offset.
 603
 604    We then try to fold the entire address expression into a form
 605    &array[index].
 606
 607    If we are successful, we replace the right hand side of USE_STMT
 608    with the new address computation.  */
 609
 610 static bool
 611 forward_propagate_addr_into_variable_array_index (tree offset, tree lhs,
 612                                                   tree def_rhs, tree use_stmt)
 613 {
 614   tree index;
 615
 616   /* The offset must be defined by a simple GIMPLE_MODIFY_STMT statement.  */
 617   if (TREE_CODE (offset) != GIMPLE_MODIFY_STMT)
 618     return false;
 619
 620   /* The RHS of the statement which defines OFFSET must be a gimple
 621      cast of another SSA_NAME.  */
 622   offset = GIMPLE_STMT_OPERAND (offset, 1);
 623   if (!is_gimple_cast (offset))
 624     return false;
 625
 626   offset = TREE_OPERAND (offset, 0);
 627   if (TREE_CODE (offset) != SSA_NAME)
 628     return false;
 629
 630   /* Get the defining statement of the offset before type
 631      conversion.  */
 632   offset = SSA_NAME_DEF_STMT (offset);
 633
 634   /* The statement which defines OFFSET before type conversion
 635      must be a simple GIMPLE_MODIFY_STMT.  */
 636   if (TREE_CODE (offset) != GIMPLE_MODIFY_STMT)
 637     return false;
 638
 639   /* The RHS of the statement which defines OFFSET must be a
 640      multiplication of an object by the size of the array elements.
 641      This implicitly verifies that the size of the array elements
 642      is constant.  */
 643   offset = GIMPLE_STMT_OPERAND (offset, 1);
 644   if (TREE_CODE (offset) != MULT_EXPR
 645       || TREE_CODE (TREE_OPERAND (offset, 1)) != INTEGER_CST
 646       || !simple_cst_equal (TREE_OPERAND (offset, 1),
 647                             TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (lhs)))))
 648     return false;
 649
 650   /* The first operand to the MULT_EXPR is the desired index.  */
 651   index = TREE_OPERAND (offset, 0);
 652
 653   /* Replace the pointer addition with array indexing.  */
 654   GIMPLE_STMT_OPERAND (use_stmt, 1) = unshare_expr (def_rhs);
 655   TREE_OPERAND (TREE_OPERAND (GIMPLE_STMT_OPERAND (use_stmt, 1), 0), 1)
 656     = index;
 657
 658   /* That should have created gimple, so there is no need to
 659      record information to undo the propagation.  */
 660   fold_stmt_inplace (use_stmt);
 661   tidy_after_forward_propagate_addr (use_stmt);
 662   return true;
 663 }
 664
 665 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
 666    ADDR_EXPR <whatever>.
 667
 668    Try to forward propagate the ADDR_EXPR into the use USE_STMT.
 669    Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
 670    node or for recovery of array indexing from pointer arithmetic.
 671
 672    Return true if the propagation was successful (the propagation can
 673    be not totally successful, yet things may have been changed).  */
 674
 675 static bool
 676 forward_propagate_addr_expr_1 (tree name, tree def_rhs, tree use_stmt)
 677 {
 678   tree lhs, rhs, array_ref;
 679
 680   /* Strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
 681      ADDR_EXPR will not appear on the LHS.  */
 682   lhs = GIMPLE_STMT_OPERAND (use_stmt, 0);
 683   while (TREE_CODE (lhs) == COMPONENT_REF || TREE_CODE (lhs) == ARRAY_REF)
 684     lhs = TREE_OPERAND (lhs, 0);
 685
 686   rhs = GIMPLE_STMT_OPERAND (use_stmt, 1);
 687
 688   /* Now see if the LHS node is an INDIRECT_REF using NAME.  If so,
 689      propagate the ADDR_EXPR into the use of NAME and fold the result.  */
 690   if (TREE_CODE (lhs) == INDIRECT_REF && TREE_OPERAND (lhs, 0) == name)
 691     {
 692       /* This should always succeed in creating gimple, so there is
 693          no need to save enough state to undo this propagation.  */
 694       TREE_OPERAND (lhs, 0) = unshare_expr (def_rhs);
 695       fold_stmt_inplace (use_stmt);
 696       tidy_after_forward_propagate_addr (use_stmt);
 697
 698       /* The only case we did not replace all uses this way is if the
 699          use statement is of the form *name = name.  */
 700       return rhs != name;
 701     }
 702
 703   /* Trivial case.  The use statement could be a trivial copy or a
 704      useless conversion.  Recurse to the uses of the lhs as copyprop does
 705      not copy through differen variant pointers and FRE does not catch
 706      all useless conversions.  */
 707   else if ((TREE_CODE (lhs) == SSA_NAME
 708             && rhs == name)
 709            || ((TREE_CODE (rhs) == NOP_EXPR
 710                 || TREE_CODE (rhs) == CONVERT_EXPR)
 711                && tree_ssa_useless_type_conversion_1 (TREE_TYPE (rhs),
 712                                                       TREE_TYPE (def_rhs))))
 713     return forward_propagate_addr_expr (lhs, def_rhs);
 714
 715   /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
 716      nodes from the RHS.  */
 717   while (TREE_CODE (rhs) == COMPONENT_REF
 718          || TREE_CODE (rhs) == ARRAY_REF
 719          || TREE_CODE (rhs) == ADDR_EXPR)
 720     rhs = TREE_OPERAND (rhs, 0);
 721
 722   /* Now see if the RHS node is an INDIRECT_REF using NAME.  If so,
 723      propagate the ADDR_EXPR into the use of NAME and fold the result.  */
 724   if (TREE_CODE (rhs) == INDIRECT_REF && TREE_OPERAND (rhs, 0) == name)
 725     {
 726       /* This should always succeed in creating gimple, so there is
 727          no need to save enough state to undo this propagation.  */
 728       TREE_OPERAND (rhs, 0) = unshare_expr (def_rhs);
 729       fold_stmt_inplace (use_stmt);
 730       tidy_after_forward_propagate_addr (use_stmt);
 731       return true;
 732     }
 733
 734   /* The remaining cases are all for turning pointer arithmetic into
 735      array indexing.  They only apply when we have the address of
 736      element zero in an array.  If that is not the case then there
 737      is nothing to do.  */
 738   array_ref = TREE_OPERAND (def_rhs, 0);
 739   if (TREE_CODE (array_ref) != ARRAY_REF
 740       || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
 741       || !integer_zerop (TREE_OPERAND (array_ref, 1)))
 742     return false;
 743
 744   /* If the use of the ADDR_EXPR must be a PLUS_EXPR, or else there
 745      is nothing to do. */
 746   if (TREE_CODE (rhs) != PLUS_EXPR)
 747     return false;
 748
 749   /* Try to optimize &x[0] + C where C is a multiple of the size
 750      of the elements in X into &x[C/element size].  */
 751   if (TREE_OPERAND (rhs, 0) == name
 752       && TREE_CODE (TREE_OPERAND (rhs, 1)) == INTEGER_CST)
 753     {
 754       tree orig = unshare_expr (rhs);
 755       TREE_OPERAND (rhs, 0) = unshare_expr (def_rhs);
 756
 757       /* If folding succeeds, then we have just exposed new variables
 758          in USE_STMT which will need to be renamed.  If folding fails,
 759          then we need to put everything back the way it was.  */
 760       if (fold_stmt_inplace (use_stmt))
 761         {
 762           tidy_after_forward_propagate_addr (use_stmt);
 763           return true;
 764         }
 765       else
 766         {
 767           GIMPLE_STMT_OPERAND (use_stmt, 1) = orig;
 768           update_stmt (use_stmt);
 769           return false;
 770         }
 771     }
 772
 773   /* Try to optimize &x[0] + OFFSET where OFFSET is defined by
 774      converting a multiplication of an index by the size of the
 775      array elements, then the result is converted into the proper
 776      type for the arithmetic.  */
 777   if (TREE_OPERAND (rhs, 0) == name
 778       && TREE_CODE (TREE_OPERAND (rhs, 1)) == SSA_NAME
 779       /* Avoid problems with IVopts creating PLUS_EXPRs with a
 780          different type than their operands.  */
 781       && lang_hooks.types_compatible_p (TREE_TYPE (name), TREE_TYPE (rhs)))
 782     {
 783       bool res;
 784       tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1));
 785
 786       res = forward_propagate_addr_into_variable_array_index (offset_stmt, lhs,
 787                                                               def_rhs, use_stmt);
 788       return res;
 789     }
 790
 791   /* Same as the previous case, except the operands of the PLUS_EXPR
 792      were reversed.  */
 793   if (TREE_OPERAND (rhs, 1) == name
 794       && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
 795       /* Avoid problems with IVopts creating PLUS_EXPRs with a
 796          different type than their operands.  */
 797       && lang_hooks.types_compatible_p (TREE_TYPE (name), TREE_TYPE (rhs)))
 798     {
 799       bool res;
 800       tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
 801       res = forward_propagate_addr_into_variable_array_index (offset_stmt, lhs,
 802                                                               def_rhs, use_stmt);
 803       return res;
 804     }
 805   return false;
 806 }
 807
 808 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
 809
 810    Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
 811    Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
 812    node or for recovery of array indexing from pointer arithmetic.
 813    Returns true, if all uses have been propagated into.  */
 814
 815 static bool
 816 forward_propagate_addr_expr (tree name, tree rhs)
 817 {
 818   int stmt_loop_depth = bb_for_stmt (SSA_NAME_DEF_STMT (name))->loop_depth;
 819   imm_use_iterator iter;
 820   tree use_stmt;
 821   bool all = true;
 822
 823   FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
 824     {
 825       bool result;
 826
 827       /* If the use is not in a simple assignment statement, then
 828          there is nothing we can do.  */
 829       if (TREE_CODE (use_stmt) != GIMPLE_MODIFY_STMT)
 830         {
 831           all = false;
 832           continue;
 833         }
 834
 835      /* If the use is in a deeper loop nest, then we do not want
 836         to propagate the ADDR_EXPR into the loop as that is likely
 837         adding expression evaluations into the loop.  */
 838       if (bb_for_stmt (use_stmt)->loop_depth > stmt_loop_depth)
 839         {
 840           all = false;
 841           continue;
 842         }
 843
 844       push_stmt_changes (&use_stmt);
 845
 846       result = forward_propagate_addr_expr_1 (name, rhs, use_stmt);
 847       all &= result;
 848
 849       pop_stmt_changes (&use_stmt);
 850
 851       /* Remove intermediate now unused copy and conversion chains.  */
 852       if (result
 853           && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 0)) == SSA_NAME
 854           && (TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == SSA_NAME
 855               || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == NOP_EXPR
 856               || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == CONVERT_EXPR))
 857         {
 858           block_stmt_iterator bsi = bsi_for_stmt (use_stmt);
 859           release_defs (use_stmt);
 860           bsi_remove (&bsi, true);
 861         }
 862     }
 863
 864   return all;
 865 }
 866
 867 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
 868    If so, we can change STMT into lhs = y which can later be copy
 869    propagated.  Similarly for negation.
 870
 871    This could trivially be formulated as a forward propagation
 872    to immediate uses.  However, we already had an implementation
 873    from DOM which used backward propagation via the use-def links.
 874
 875    It turns out that backward propagation is actually faster as
 876    there's less work to do for each NOT/NEG expression we find.
 877    Backwards propagation needs to look at the statement in a single
 878    backlink.  Forward propagation needs to look at potentially more
 879    than one forward link.  */
 880
 881 static void
 882 simplify_not_neg_expr (tree stmt)
 883 {
 884   tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
 885   tree rhs_def_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
 886
 887   /* See if the RHS_DEF_STMT has the same form as our statement.  */
 888   if (TREE_CODE (rhs_def_stmt) == GIMPLE_MODIFY_STMT
 889       && TREE_CODE (GIMPLE_STMT_OPERAND (rhs_def_stmt, 1)) == TREE_CODE (rhs))
 890     {
 891       tree rhs_def_operand =
 892         TREE_OPERAND (GIMPLE_STMT_OPERAND (rhs_def_stmt, 1), 0);
 893
 894       /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME.  */
 895       if (TREE_CODE (rhs_def_operand) == SSA_NAME
 896           && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand))
 897         {
 898           GIMPLE_STMT_OPERAND (stmt, 1) = rhs_def_operand;
 899           update_stmt (stmt);
 900         }
 901     }
 902 }
 903
 904 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
 905    the condition which we may be able to optimize better.  */
 906
 907 static void
 908 simplify_switch_expr (tree stmt)
 909 {
 910   tree cond = SWITCH_COND (stmt);
 911   tree def, to, ti;
 912
 913   /* The optimization that we really care about is removing unnecessary
 914      casts.  That will let us do much better in propagating the inferred
 915      constant at the switch target.  */
 916   if (TREE_CODE (cond) == SSA_NAME)
 917     {
 918       def = SSA_NAME_DEF_STMT (cond);
 919       if (TREE_CODE (def) == GIMPLE_MODIFY_STMT)
 920         {
 921           def = GIMPLE_STMT_OPERAND (def, 1);
 922           if (TREE_CODE (def) == NOP_EXPR)
 923             {
 924               int need_precision;
 925               bool fail;
 926
 927               def = TREE_OPERAND (def, 0);
 928
 929 #ifdef ENABLE_CHECKING
 930               /* ??? Why was Jeff testing this?  We are gimple...  */
 931               gcc_assert (is_gimple_val (def));
 932 #endif
 933
 934               to = TREE_TYPE (cond);
 935               ti = TREE_TYPE (def);
 936
 937               /* If we have an extension that preserves value, then we
 938                  can copy the source value into the switch.  */
 939
 940               need_precision = TYPE_PRECISION (ti);
 941               fail = false;
 942               if (! INTEGRAL_TYPE_P (ti))
 943                 fail = true;
 944               else if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti))
 945                 fail = true;
 946               else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti))
 947                 need_precision += 1;
 948               if (TYPE_PRECISION (to) < need_precision)
 949                 fail = true;
 950
 951               if (!fail)
 952                 {
 953                   SWITCH_COND (stmt) = def;
 954                   update_stmt (stmt);
 955                 }
 956             }
 957         }
 958     }
 959 }
 960
 961 /* Main entry point for the forward propagation optimizer.  */
 962
 963 static unsigned int
 964 tree_ssa_forward_propagate_single_use_vars (void)
 965 {
 966   basic_block bb;
 967   unsigned int todoflags = 0;
 968
 969   cfg_changed = false;
 970
 971   FOR_EACH_BB (bb)
 972     {
 973       block_stmt_iterator bsi;
 974
 975       /* Note we update BSI within the loop as necessary.  */
 976       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
 977         {
 978           tree stmt = bsi_stmt (bsi);
 979
 980           /* If this statement sets an SSA_NAME to an address,
 981              try to propagate the address into the uses of the SSA_NAME.  */
 982           if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
 983             {
 984               tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
 985               tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
 986
 987
 988               if (TREE_CODE (lhs) != SSA_NAME)
 989                 {
 990                   bsi_next (&bsi);
 991                   continue;
 992                 }
 993
 994               if (TREE_CODE (rhs) == ADDR_EXPR)
 995                 {
 996                   if (forward_propagate_addr_expr (lhs, rhs))
 997                     {
 998                       release_defs (stmt);
 999                       todoflags |= TODO_remove_unused_locals;
1000                       bsi_remove (&bsi, true);
1001                     }
1002                   else
1003                     bsi_next (&bsi);
1004                 }
1005               else if ((TREE_CODE (rhs) == BIT_NOT_EXPR
1006                         || TREE_CODE (rhs) == NEGATE_EXPR)
1007                        && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
1008                 {
1009                   simplify_not_neg_expr (stmt);
1010                   bsi_next (&bsi);
1011                 }
1012               else if (TREE_CODE (rhs) == COND_EXPR)
1013                 {
1014                   forward_propagate_into_cond (rhs, stmt);
1015                   bsi_next (&bsi);
1016                 }
1017               else
1018                 bsi_next (&bsi);
1019             }
1020           else if (TREE_CODE (stmt) == SWITCH_EXPR)
1021             {
1022               simplify_switch_expr (stmt);
1023               bsi_next (&bsi);
1024             }
1025           else if (TREE_CODE (stmt) == COND_EXPR)
1026             {
1027               forward_propagate_into_cond (stmt, stmt);
1028               bsi_next (&bsi);
1029             }
1030           else
1031             bsi_next (&bsi);
1032         }
1033     }
1034
1035   if (cfg_changed)
1036     todoflags |= TODO_cleanup_cfg;
1037   return todoflags;
1038 }
1039
1040
1041 static bool
1042 gate_forwprop (void)
1043 {
1044   return 1;
1045 }
1046
1047 struct tree_opt_pass pass_forwprop = {
1048   "forwprop",                   /* name */
1049   gate_forwprop,                /* gate */
1050   tree_ssa_forward_propagate_single_use_vars,   /* execute */
1051   NULL,                         /* sub */
1052   NULL,                         /* next */
1053   0,                            /* static_pass_number */
1054   TV_TREE_FORWPROP,             /* tv_id */
1055   PROP_cfg | PROP_ssa,          /* properties_required */
1056   0,                            /* properties_provided */
1057   0,                            /* properties_destroyed */
1058   0,                            /* todo_flags_start */
1059   TODO_dump_func
1060   | TODO_ggc_collect
1061   | TODO_update_ssa
1062   | TODO_verify_ssa,            /* todo_flags_finish */
1063   0                             /* letter */
1064 };