gcc/tree-ssa-forwprop.c

   1 /* Forward propagation of expressions for single use variables.
   2    Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010, 2011
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "tm_p.h"
  27 #include "basic-block.h"
  28 #include "timevar.h"
  29 #include "tree-pretty-print.h"
  30 #include "tree-flow.h"
  31 #include "tree-pass.h"
  32 #include "tree-dump.h"
  33 #include "langhooks.h"
  34 #include "flags.h"
  35 #include "gimple.h"
  36 #include "expr.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.   It is hoped all of this can disappear
  41    when we have a generalized tree combiner.
  42
  43    One class of common cases we handle is forward propagating a single use
  44    variable into a COND_EXPR.
  45
  46      bb0:
  47        x = a COND b;
  48        if (x) goto ... else goto ...
  49
  50    Will be transformed into:
  51
  52      bb0:
  53        if (a COND b) goto ... else goto ...
  54
  55    Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
  56
  57    Or (assuming c1 and c2 are constants):
  58
  59      bb0:
  60        x = a + c1;
  61        if (x EQ/NEQ c2) goto ... else goto ...
  62
  63    Will be transformed into:
  64
  65      bb0:
  66         if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
  67
  68    Similarly for x = a - c1.
  69
  70    Or
  71
  72      bb0:
  73        x = !a
  74        if (x) goto ... else goto ...
  75
  76    Will be transformed into:
  77
  78      bb0:
  79         if (a == 0) goto ... else goto ...
  80
  81    Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
  82    For these cases, we propagate A into all, possibly more than one,
  83    COND_EXPRs that use X.
  84
  85    Or
  86
  87      bb0:
  88        x = (typecast) a
  89        if (x) goto ... else goto ...
  90
  91    Will be transformed into:
  92
  93      bb0:
  94         if (a != 0) goto ... else goto ...
  95
  96    (Assuming a is an integral type and x is a boolean or x is an
  97     integral and a is a boolean.)
  98
  99    Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
 100    For these cases, we propagate A into all, possibly more than one,
 101    COND_EXPRs that use X.
 102
 103    In addition to eliminating the variable and the statement which assigns
 104    a value to the variable, we may be able to later thread the jump without
 105    adding insane complexity in the dominator optimizer.
 106
 107    Also note these transformations can cascade.  We handle this by having
 108    a worklist of COND_EXPR statements to examine.  As we make a change to
 109    a statement, we put it back on the worklist to examine on the next
 110    iteration of the main loop.
 111
 112    A second class of propagation opportunities arises for ADDR_EXPR
 113    nodes.
 114
 115      ptr = &x->y->z;
 116      res = *ptr;
 117
 118    Will get turned into
 119
 120      res = x->y->z;
 121
 122    Or
 123      ptr = (type1*)&type2var;
 124      res = *ptr
 125
 126    Will get turned into (if type1 and type2 are the same size
 127    and neither have volatile on them):
 128      res = VIEW_CONVERT_EXPR<type1>(type2var)
 129
 130    Or
 131
 132      ptr = &x[0];
 133      ptr2 = ptr + <constant>;
 134
 135    Will get turned into
 136
 137      ptr2 = &x[constant/elementsize];
 138
 139   Or
 140
 141      ptr = &x[0];
 142      offset = index * element_size;
 143      offset_p = (pointer) offset;
 144      ptr2 = ptr + offset_p
 145
 146   Will get turned into:
 147
 148      ptr2 = &x[index];
 149
 150   Or
 151     ssa = (int) decl
 152     res = ssa & 1
 153
 154   Provided that decl has known alignment >= 2, will get turned into
 155
 156     res = 0
 157
 158   We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to
 159   allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent
 160   {NOT_EXPR,NEG_EXPR}.
 161
 162    This will (of course) be extended as other needs arise.  */
 163
 164 static bool forward_propagate_addr_expr (tree name, tree rhs);
 165
 166 /* Set to true if we delete EH edges during the optimization.  */
 167 static bool cfg_changed;
 168
 169 static tree rhs_to_tree (tree type, gimple stmt);
 170
 171 /* Get the next statement we can propagate NAME's value into skipping
 172    trivial copies.  Returns the statement that is suitable as a
 173    propagation destination or NULL_TREE if there is no such one.
 174    This only returns destinations in a single-use chain.  FINAL_NAME_P
 175    if non-NULL is written to the ssa name that represents the use.  */
 176
 177 static gimple
 178 get_prop_dest_stmt (tree name, tree *final_name_p)
 179 {
 180   use_operand_p use;
 181   gimple use_stmt;
 182
 183   do {
 184     /* If name has multiple uses, bail out.  */
 185     if (!single_imm_use (name, &use, &use_stmt))
 186       return NULL;
 187
 188     /* If this is not a trivial copy, we found it.  */
 189     if (!gimple_assign_ssa_name_copy_p (use_stmt)
 190         || gimple_assign_rhs1 (use_stmt) != name)
 191       break;
 192
 193     /* Continue searching uses of the copy destination.  */
 194     name = gimple_assign_lhs (use_stmt);
 195   } while (1);
 196
 197   if (final_name_p)
 198     *final_name_p = name;
 199
 200   return use_stmt;
 201 }
 202
 203 /* Get the statement we can propagate from into NAME skipping
 204    trivial copies.  Returns the statement which defines the
 205    propagation source or NULL_TREE if there is no such one.
 206    If SINGLE_USE_ONLY is set considers only sources which have
 207    a single use chain up to NAME.  If SINGLE_USE_P is non-null,
 208    it is set to whether the chain to NAME is a single use chain
 209    or not.  SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set.  */
 210
 211 static gimple
 212 get_prop_source_stmt (tree name, bool single_use_only, bool *single_use_p)
 213 {
 214   bool single_use = true;
 215
 216   do {
 217     gimple def_stmt = SSA_NAME_DEF_STMT (name);
 218
 219     if (!has_single_use (name))
 220       {
 221         single_use = false;
 222         if (single_use_only)
 223           return NULL;
 224       }
 225
 226     /* If name is defined by a PHI node or is the default def, bail out.  */
 227     if (!is_gimple_assign (def_stmt))
 228       return NULL;
 229
 230     /* If def_stmt is not a simple copy, we possibly found it.  */
 231     if (!gimple_assign_ssa_name_copy_p (def_stmt))
 232       {
 233         tree rhs;
 234
 235         if (!single_use_only && single_use_p)
 236           *single_use_p = single_use;
 237
 238         /* We can look through pointer conversions in the search
 239            for a useful stmt for the comparison folding.  */
 240         rhs = gimple_assign_rhs1 (def_stmt);
 241         if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
 242             && TREE_CODE (rhs) == SSA_NAME
 243             && POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (def_stmt)))
 244             && POINTER_TYPE_P (TREE_TYPE (rhs)))
 245           name = rhs;
 246         else
 247           return def_stmt;
 248       }
 249     else
 250       {
 251         /* Continue searching the def of the copy source name.  */
 252         name = gimple_assign_rhs1 (def_stmt);
 253       }
 254   } while (1);
 255 }
 256
 257 /* Checks if the destination ssa name in DEF_STMT can be used as
 258    propagation source.  Returns true if so, otherwise false.  */
 259
 260 static bool
 261 can_propagate_from (gimple def_stmt)
 262 {
 263   gcc_assert (is_gimple_assign (def_stmt));
 264
 265   /* If the rhs has side-effects we cannot propagate from it.  */
 266   if (gimple_has_volatile_ops (def_stmt))
 267     return false;
 268
 269   /* If the rhs is a load we cannot propagate from it.  */
 270   if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_reference
 271       || TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_declaration)
 272     return false;
 273
 274   /* Constants can be always propagated.  */
 275   if (gimple_assign_single_p (def_stmt)
 276       && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt)))
 277     return true;
 278
 279   /* We cannot propagate ssa names that occur in abnormal phi nodes.  */
 280   if (stmt_references_abnormal_ssa_name (def_stmt))
 281     return false;
 282
 283   /* If the definition is a conversion of a pointer to a function type,
 284      then we can not apply optimizations as some targets require
 285      function pointers to be canonicalized and in this case this
 286      optimization could eliminate a necessary canonicalization.  */
 287   if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
 288     {
 289       tree rhs = gimple_assign_rhs1 (def_stmt);
 290       if (POINTER_TYPE_P (TREE_TYPE (rhs))
 291           && TREE_CODE (TREE_TYPE (TREE_TYPE (rhs))) == FUNCTION_TYPE)
 292         return false;
 293     }
 294
 295   return true;
 296 }
 297
 298 /* Remove a copy chain ending in NAME along the defs.
 299    If NAME was replaced in its only use then this function can be used
 300    to clean up dead stmts.  Returns true if cleanup-cfg has to run.  */
 301
 302 static bool
 303 remove_prop_source_from_use (tree name)
 304 {
 305   gimple_stmt_iterator gsi;
 306   gimple stmt;
 307   bool cfg_changed = false;
 308
 309   do {
 310     basic_block bb;
 311
 312     if (!has_zero_uses (name))
 313       return cfg_changed;
 314
 315     stmt = SSA_NAME_DEF_STMT (name);
 316     gsi = gsi_for_stmt (stmt);
 317     bb = gimple_bb (stmt);
 318     release_defs (stmt);
 319     gsi_remove (&gsi, true);
 320     cfg_changed |= gimple_purge_dead_eh_edges (bb);
 321
 322     name = (gimple_assign_copy_p (stmt)) ? gimple_assign_rhs1 (stmt) : NULL;
 323   } while (name && TREE_CODE (name) == SSA_NAME);
 324
 325   return cfg_changed;
 326 }
 327
 328 /* Return the rhs of a gimple_assign STMT in a form of a single tree,
 329    converted to type TYPE.
 330
 331    This should disappear, but is needed so we can combine expressions and use
 332    the fold() interfaces. Long term, we need to develop folding and combine
 333    routines that deal with gimple exclusively . */
 334
 335 static tree
 336 rhs_to_tree (tree type, gimple stmt)
 337 {
 338   location_t loc = gimple_location (stmt);
 339   enum tree_code code = gimple_assign_rhs_code (stmt);
 340   if (get_gimple_rhs_class (code) == GIMPLE_TERNARY_RHS)
 341     return fold_build3_loc (loc, code, type, gimple_assign_rhs1 (stmt),
 342                             gimple_assign_rhs2 (stmt),
 343                             gimple_assign_rhs3 (stmt));
 344   else if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
 345     return fold_build2_loc (loc, code, type, gimple_assign_rhs1 (stmt),
 346                         gimple_assign_rhs2 (stmt));
 347   else if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
 348     return build1 (code, type, gimple_assign_rhs1 (stmt));
 349   else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
 350     return gimple_assign_rhs1 (stmt);
 351   else
 352     gcc_unreachable ();
 353 }
 354
 355 /* Combine OP0 CODE OP1 in the context of a COND_EXPR.  Returns
 356    the folded result in a form suitable for COND_EXPR_COND or
 357    NULL_TREE, if there is no suitable simplified form.  If
 358    INVARIANT_ONLY is true only gimple_min_invariant results are
 359    considered simplified.  */
 360
 361 static tree
 362 combine_cond_expr_cond (location_t loc, enum tree_code code, tree type,
 363                         tree op0, tree op1, bool invariant_only)
 364 {
 365   tree t;
 366
 367   gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
 368
 369   t = fold_binary_loc (loc, code, type, op0, op1);
 370   if (!t)
 371     return NULL_TREE;
 372
 373   /* Require that we got a boolean type out if we put one in.  */
 374   gcc_assert (TREE_CODE (TREE_TYPE (t)) == TREE_CODE (type));
 375
 376   /* Canonicalize the combined condition for use in a COND_EXPR.  */
 377   t = canonicalize_cond_expr_cond (t);
 378
 379   /* Bail out if we required an invariant but didn't get one.  */
 380   if (!t || (invariant_only && !is_gimple_min_invariant (t)))
 381     return NULL_TREE;
 382
 383   return t;
 384 }
 385
 386 /* Propagate from the ssa name definition statements of COND_EXPR
 387    in GIMPLE_COND statement STMT into the conditional if that simplifies it.
 388    Returns zero if no statement was changed, one if there were
 389    changes and two if cfg_cleanup needs to run.
 390
 391    This must be kept in sync with forward_propagate_into_cond.  */
 392
 393 static int
 394 forward_propagate_into_gimple_cond (gimple stmt)
 395 {
 396   int did_something = 0;
 397   location_t loc = gimple_location (stmt);
 398
 399   do {
 400     tree tmp = NULL_TREE;
 401     tree name = NULL_TREE, rhs0 = NULL_TREE, rhs1 = NULL_TREE;
 402     gimple def_stmt;
 403     bool single_use0_p = false, single_use1_p = false;
 404     enum tree_code code = gimple_cond_code (stmt);
 405
 406     /* We can do tree combining on SSA_NAME and comparison expressions.  */
 407     if (TREE_CODE_CLASS (gimple_cond_code (stmt)) == tcc_comparison)
 408       {
 409         /* For comparisons use the first operand, that is likely to
 410            simplify comparisons against constants.  */
 411         if (TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME)
 412           {
 413             name = gimple_cond_lhs (stmt);
 414             def_stmt = get_prop_source_stmt (name, false, &single_use0_p);
 415             if (def_stmt && can_propagate_from (def_stmt))
 416               {
 417                 tree op1 = gimple_cond_rhs (stmt);
 418                 rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
 419                 tmp = combine_cond_expr_cond (loc, code, boolean_type_node,
 420                                               rhs0, op1, !single_use0_p);
 421               }
 422           }
 423         /* If that wasn't successful, try the second operand.  */
 424         if (tmp == NULL_TREE
 425             && TREE_CODE (gimple_cond_rhs (stmt)) == SSA_NAME)
 426           {
 427             tree op0 = gimple_cond_lhs (stmt);
 428             name = gimple_cond_rhs (stmt);
 429             def_stmt = get_prop_source_stmt (name, false, &single_use1_p);
 430             if (!def_stmt || !can_propagate_from (def_stmt))
 431               return did_something;
 432
 433             rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt);
 434             tmp = combine_cond_expr_cond (loc, code, boolean_type_node, op0,
 435                                           rhs1, !single_use1_p);
 436           }
 437         /* If that wasn't successful either, try both operands.  */
 438         if (tmp == NULL_TREE
 439             && rhs0 != NULL_TREE
 440             && rhs1 != NULL_TREE)
 441           tmp = combine_cond_expr_cond (loc, code, boolean_type_node, rhs0,
 442                                         fold_convert_loc (loc,
 443                                                           TREE_TYPE (rhs0),
 444                                                           rhs1),
 445                                         !(single_use0_p && single_use1_p));
 446       }
 447
 448     if (tmp)
 449       {
 450         if (dump_file && tmp)
 451           {
 452             tree cond = build2 (gimple_cond_code (stmt),
 453                                 boolean_type_node,
 454                                 gimple_cond_lhs (stmt),
 455                                 gimple_cond_rhs (stmt));
 456             fprintf (dump_file, "  Replaced '");
 457             print_generic_expr (dump_file, cond, 0);
 458             fprintf (dump_file, "' with '");
 459             print_generic_expr (dump_file, tmp, 0);
 460             fprintf (dump_file, "'\n");
 461           }
 462
 463         gimple_cond_set_condition_from_tree (stmt, unshare_expr (tmp));
 464         update_stmt (stmt);
 465
 466         /* Remove defining statements.  */
 467         if (remove_prop_source_from_use (name)
 468             || is_gimple_min_invariant (tmp))
 469           did_something = 2;
 470         else if (did_something == 0)
 471           did_something = 1;
 472
 473         /* Continue combining.  */
 474         continue;
 475       }
 476
 477     break;
 478   } while (1);
 479
 480   return did_something;
 481 }
 482
 483
 484 /* Propagate from the ssa name definition statements of COND_EXPR
 485    in the rhs of statement STMT into the conditional if that simplifies it.
 486    Returns zero if no statement was changed, one if there were
 487    changes and two if cfg_cleanup needs to run.
 488
 489    This must be kept in sync with forward_propagate_into_gimple_cond.  */
 490
 491 static int
 492 forward_propagate_into_cond (gimple_stmt_iterator *gsi_p)
 493 {
 494   gimple stmt = gsi_stmt (*gsi_p);
 495   location_t loc = gimple_location (stmt);
 496   int did_something = 0;
 497
 498   do {
 499     tree tmp = NULL_TREE;
 500     tree cond = gimple_assign_rhs1 (stmt);
 501     tree name, rhs0 = NULL_TREE, rhs1 = NULL_TREE;
 502     gimple def_stmt;
 503     bool single_use0_p = false, single_use1_p = false;
 504
 505     /* We can do tree combining on SSA_NAME and comparison expressions.  */
 506     if (COMPARISON_CLASS_P (cond)
 507         && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME)
 508       {
 509         /* For comparisons use the first operand, that is likely to
 510            simplify comparisons against constants.  */
 511         name = TREE_OPERAND (cond, 0);
 512         def_stmt = get_prop_source_stmt (name, false, &single_use0_p);
 513         if (def_stmt && can_propagate_from (def_stmt))
 514           {
 515             tree op1 = TREE_OPERAND (cond, 1);
 516             rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
 517             tmp = combine_cond_expr_cond (loc, TREE_CODE (cond),
 518                                           boolean_type_node,
 519                                           rhs0, op1, !single_use0_p);
 520           }
 521         /* If that wasn't successful, try the second operand.  */
 522         if (tmp == NULL_TREE
 523             && TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME)
 524           {
 525             tree op0 = TREE_OPERAND (cond, 0);
 526             name = TREE_OPERAND (cond, 1);
 527             def_stmt = get_prop_source_stmt (name, false, &single_use1_p);
 528             if (!def_stmt || !can_propagate_from (def_stmt))
 529               return did_something;
 530
 531             rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt);
 532             tmp = combine_cond_expr_cond (loc, TREE_CODE (cond),
 533                                           boolean_type_node,
 534                                           op0, rhs1, !single_use1_p);
 535           }
 536         /* If that wasn't successful either, try both operands.  */
 537         if (tmp == NULL_TREE
 538             && rhs0 != NULL_TREE
 539             && rhs1 != NULL_TREE)
 540           tmp = combine_cond_expr_cond (loc, TREE_CODE (cond),
 541                                         boolean_type_node,
 542                                         rhs0,
 543                                         fold_convert_loc (loc,
 544                                                           TREE_TYPE (rhs0),
 545                                                           rhs1),
 546                                         !(single_use0_p && single_use1_p));
 547       }
 548     else if (TREE_CODE (cond) == SSA_NAME)
 549       {
 550         name = cond;
 551         def_stmt = get_prop_source_stmt (name, true, NULL);
 552         if (def_stmt || !can_propagate_from (def_stmt))
 553           return did_something;
 554
 555         rhs0 = gimple_assign_rhs1 (def_stmt);
 556         tmp = combine_cond_expr_cond (loc, NE_EXPR, boolean_type_node, rhs0,
 557                                       build_int_cst (TREE_TYPE (rhs0), 0),
 558                                       false);
 559       }
 560
 561     if (tmp)
 562       {
 563         if (dump_file && tmp)
 564           {
 565             fprintf (dump_file, "  Replaced '");
 566             print_generic_expr (dump_file, cond, 0);
 567             fprintf (dump_file, "' with '");
 568             print_generic_expr (dump_file, tmp, 0);
 569             fprintf (dump_file, "'\n");
 570           }
 571
 572         gimple_assign_set_rhs_from_tree (gsi_p, unshare_expr (tmp));
 573         stmt = gsi_stmt (*gsi_p);
 574         update_stmt (stmt);
 575
 576         /* Remove defining statements.  */
 577         if (remove_prop_source_from_use (name)
 578             || is_gimple_min_invariant (tmp))
 579           did_something = 2;
 580         else if (did_something == 0)
 581           did_something = 1;
 582
 583         /* Continue combining.  */
 584         continue;
 585       }
 586
 587     break;
 588   } while (1);
 589
 590   return did_something;
 591 }
 592
 593 /* We've just substituted an ADDR_EXPR into stmt.  Update all the
 594    relevant data structures to match.  */
 595
 596 static void
 597 tidy_after_forward_propagate_addr (gimple stmt)
 598 {
 599   /* We may have turned a trapping insn into a non-trapping insn.  */
 600   if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
 601       && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
 602     cfg_changed = true;
 603
 604   if (TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR)
 605      recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
 606 }
 607
 608 /* DEF_RHS contains the address of the 0th element in an array.
 609    USE_STMT uses type of DEF_RHS to compute the address of an
 610    arbitrary element within the array.  The (variable) byte offset
 611    of the element is contained in OFFSET.
 612
 613    We walk back through the use-def chains of OFFSET to verify that
 614    it is indeed computing the offset of an element within the array
 615    and extract the index corresponding to the given byte offset.
 616
 617    We then try to fold the entire address expression into a form
 618    &array[index].
 619
 620    If we are successful, we replace the right hand side of USE_STMT
 621    with the new address computation.  */
 622
 623 static bool
 624 forward_propagate_addr_into_variable_array_index (tree offset,
 625                                                   tree def_rhs,
 626                                                   gimple_stmt_iterator *use_stmt_gsi)
 627 {
 628   tree index, tunit;
 629   gimple offset_def, use_stmt = gsi_stmt (*use_stmt_gsi);
 630   tree new_rhs, tmp;
 631
 632   if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == ARRAY_REF)
 633     tunit = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs)));
 634   else if (TREE_CODE (TREE_TYPE (TREE_OPERAND (def_rhs, 0))) == ARRAY_TYPE)
 635     tunit = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (TREE_TYPE (def_rhs))));
 636   else
 637     return false;
 638   if (!host_integerp (tunit, 1))
 639     return false;
 640
 641   /* Get the offset's defining statement.  */
 642   offset_def = SSA_NAME_DEF_STMT (offset);
 643
 644   /* Try to find an expression for a proper index.  This is either a
 645      multiplication expression by the element size or just the ssa name we came
 646      along in case the element size is one. In that case, however, we do not
 647      allow multiplications because they can be computing index to a higher
 648      level dimension (PR 37861). */
 649   if (integer_onep (tunit))
 650     {
 651       if (is_gimple_assign (offset_def)
 652           && gimple_assign_rhs_code (offset_def) == MULT_EXPR)
 653         return false;
 654
 655       index = offset;
 656     }
 657   else
 658     {
 659       /* The statement which defines OFFSET before type conversion
 660          must be a simple GIMPLE_ASSIGN.  */
 661       if (!is_gimple_assign (offset_def))
 662         return false;
 663
 664       /* The RHS of the statement which defines OFFSET must be a
 665          multiplication of an object by the size of the array elements.
 666          This implicitly verifies that the size of the array elements
 667          is constant.  */
 668      if (gimple_assign_rhs_code (offset_def) == MULT_EXPR
 669          && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
 670          && tree_int_cst_equal (gimple_assign_rhs2 (offset_def), tunit))
 671        {
 672          /* The first operand to the MULT_EXPR is the desired index.  */
 673          index = gimple_assign_rhs1 (offset_def);
 674        }
 675      /* If we have idx * tunit + CST * tunit re-associate that.  */
 676      else if ((gimple_assign_rhs_code (offset_def) == PLUS_EXPR
 677                || gimple_assign_rhs_code (offset_def) == MINUS_EXPR)
 678               && TREE_CODE (gimple_assign_rhs1 (offset_def)) == SSA_NAME
 679               && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
 680               && (tmp = div_if_zero_remainder (EXACT_DIV_EXPR,
 681                                                gimple_assign_rhs2 (offset_def),
 682                                                tunit)) != NULL_TREE)
 683        {
 684          gimple offset_def2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (offset_def));
 685          if (is_gimple_assign (offset_def2)
 686              && gimple_assign_rhs_code (offset_def2) == MULT_EXPR
 687              && TREE_CODE (gimple_assign_rhs2 (offset_def2)) == INTEGER_CST
 688              && tree_int_cst_equal (gimple_assign_rhs2 (offset_def2), tunit))
 689            {
 690              index = fold_build2 (gimple_assign_rhs_code (offset_def),
 691                                   TREE_TYPE (offset),
 692                                   gimple_assign_rhs1 (offset_def2), tmp);
 693            }
 694          else
 695            return false;
 696        }
 697      else
 698         return false;
 699     }
 700
 701   /* Replace the pointer addition with array indexing.  */
 702   index = force_gimple_operand_gsi (use_stmt_gsi, index, true, NULL_TREE,
 703                                     true, GSI_SAME_STMT);
 704   if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == ARRAY_REF)
 705     {
 706       new_rhs = unshare_expr (def_rhs);
 707       TREE_OPERAND (TREE_OPERAND (new_rhs, 0), 1) = index;
 708     }
 709   else
 710     {
 711       new_rhs = build4 (ARRAY_REF, TREE_TYPE (TREE_TYPE (TREE_TYPE (def_rhs))),
 712                         unshare_expr (TREE_OPERAND (def_rhs, 0)),
 713                         index, integer_zero_node, NULL_TREE);
 714       new_rhs = build_fold_addr_expr (new_rhs);
 715       if (!useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (use_stmt)),
 716                                       TREE_TYPE (new_rhs)))
 717         {
 718           new_rhs = force_gimple_operand_gsi (use_stmt_gsi, new_rhs, true,
 719                                               NULL_TREE, true, GSI_SAME_STMT);
 720           new_rhs = fold_convert (TREE_TYPE (gimple_assign_lhs (use_stmt)),
 721                                   new_rhs);
 722         }
 723     }
 724   gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
 725   use_stmt = gsi_stmt (*use_stmt_gsi);
 726
 727   /* That should have created gimple, so there is no need to
 728      record information to undo the propagation.  */
 729   fold_stmt_inplace (use_stmt);
 730   tidy_after_forward_propagate_addr (use_stmt);
 731   return true;
 732 }
 733
 734 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
 735    ADDR_EXPR <whatever>.
 736
 737    Try to forward propagate the ADDR_EXPR into the use USE_STMT.
 738    Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
 739    node or for recovery of array indexing from pointer arithmetic.
 740
 741    Return true if the propagation was successful (the propagation can
 742    be not totally successful, yet things may have been changed).  */
 743
 744 static bool
 745 forward_propagate_addr_expr_1 (tree name, tree def_rhs,
 746                                gimple_stmt_iterator *use_stmt_gsi,
 747                                bool single_use_p)
 748 {
 749   tree lhs, rhs, rhs2, array_ref;
 750   gimple use_stmt = gsi_stmt (*use_stmt_gsi);
 751   enum tree_code rhs_code;
 752   bool res = true;
 753
 754   gcc_assert (TREE_CODE (def_rhs) == ADDR_EXPR);
 755
 756   lhs = gimple_assign_lhs (use_stmt);
 757   rhs_code = gimple_assign_rhs_code (use_stmt);
 758   rhs = gimple_assign_rhs1 (use_stmt);
 759
 760   /* Trivial cases.  The use statement could be a trivial copy or a
 761      useless conversion.  Recurse to the uses of the lhs as copyprop does
 762      not copy through different variant pointers and FRE does not catch
 763      all useless conversions.  Treat the case of a single-use name and
 764      a conversion to def_rhs type separate, though.  */
 765   if (TREE_CODE (lhs) == SSA_NAME
 766       && ((rhs_code == SSA_NAME && rhs == name)
 767           || CONVERT_EXPR_CODE_P (rhs_code)))
 768     {
 769       /* Only recurse if we don't deal with a single use or we cannot
 770          do the propagation to the current statement.  In particular
 771          we can end up with a conversion needed for a non-invariant
 772          address which we cannot do in a single statement.  */
 773       if (!single_use_p
 774           || (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs))
 775               && (!is_gimple_min_invariant (def_rhs)
 776                   || (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
 777                       && POINTER_TYPE_P (TREE_TYPE (def_rhs))
 778                       && (TYPE_PRECISION (TREE_TYPE (lhs))
 779                           > TYPE_PRECISION (TREE_TYPE (def_rhs)))))))
 780         return forward_propagate_addr_expr (lhs, def_rhs);
 781
 782       gimple_assign_set_rhs1 (use_stmt, unshare_expr (def_rhs));
 783       if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
 784         gimple_assign_set_rhs_code (use_stmt, TREE_CODE (def_rhs));
 785       else
 786         gimple_assign_set_rhs_code (use_stmt, NOP_EXPR);
 787       return true;
 788     }
 789
 790   /* Propagate through constant pointer adjustments.  */
 791   if (TREE_CODE (lhs) == SSA_NAME
 792       && rhs_code == POINTER_PLUS_EXPR
 793       && rhs == name
 794       && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST)
 795     {
 796       tree new_def_rhs;
 797       /* As we come here with non-invariant addresses in def_rhs we need
 798          to make sure we can build a valid constant offsetted address
 799          for further propagation.  Simply rely on fold building that
 800          and check after the fact.  */
 801       new_def_rhs = fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (rhs)),
 802                                  def_rhs,
 803                                  fold_convert (ptr_type_node,
 804                                                gimple_assign_rhs2 (use_stmt)));
 805       if (TREE_CODE (new_def_rhs) == MEM_REF
 806           && !is_gimple_mem_ref_addr (TREE_OPERAND (new_def_rhs, 0)))
 807         return false;
 808       new_def_rhs = build_fold_addr_expr_with_type (new_def_rhs,
 809                                                     TREE_TYPE (rhs));
 810
 811       /* Recurse.  If we could propagate into all uses of lhs do not
 812          bother to replace into the current use but just pretend we did.  */
 813       if (TREE_CODE (new_def_rhs) == ADDR_EXPR
 814           && forward_propagate_addr_expr (lhs, new_def_rhs))
 815         return true;
 816
 817       if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (new_def_rhs)))
 818         gimple_assign_set_rhs_with_ops (use_stmt_gsi, TREE_CODE (new_def_rhs),
 819                                         new_def_rhs, NULL_TREE);
 820       else if (is_gimple_min_invariant (new_def_rhs))
 821         gimple_assign_set_rhs_with_ops (use_stmt_gsi, NOP_EXPR,
 822                                         new_def_rhs, NULL_TREE);
 823       else
 824         return false;
 825       gcc_assert (gsi_stmt (*use_stmt_gsi) == use_stmt);
 826       update_stmt (use_stmt);
 827       return true;
 828     }
 829
 830   /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
 831      ADDR_EXPR will not appear on the LHS.  */
 832   lhs = gimple_assign_lhs (use_stmt);
 833   while (handled_component_p (lhs))
 834     lhs = TREE_OPERAND (lhs, 0);
 835
 836   /* Now see if the LHS node is a MEM_REF using NAME.  If so,
 837      propagate the ADDR_EXPR into the use of NAME and fold the result.  */
 838   if (TREE_CODE (lhs) == MEM_REF
 839       && TREE_OPERAND (lhs, 0) == name)
 840     {
 841       tree def_rhs_base;
 842       HOST_WIDE_INT def_rhs_offset;
 843       /* If the address is invariant we can always fold it.  */
 844       if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
 845                                                          &def_rhs_offset)))
 846         {
 847           double_int off = mem_ref_offset (lhs);
 848           tree new_ptr;
 849           off = double_int_add (off,
 850                                 shwi_to_double_int (def_rhs_offset));
 851           if (TREE_CODE (def_rhs_base) == MEM_REF)
 852             {
 853               off = double_int_add (off, mem_ref_offset (def_rhs_base));
 854               new_ptr = TREE_OPERAND (def_rhs_base, 0);
 855             }
 856           else
 857             new_ptr = build_fold_addr_expr (def_rhs_base);
 858           TREE_OPERAND (lhs, 0) = new_ptr;
 859           TREE_OPERAND (lhs, 1)
 860             = double_int_to_tree (TREE_TYPE (TREE_OPERAND (lhs, 1)), off);
 861           tidy_after_forward_propagate_addr (use_stmt);
 862           /* Continue propagating into the RHS if this was not the only use.  */
 863           if (single_use_p)
 864             return true;
 865         }
 866       /* If the LHS is a plain dereference and the value type is the same as
 867          that of the pointed-to type of the address we can put the
 868          dereferenced address on the LHS preserving the original alias-type.  */
 869       else if (gimple_assign_lhs (use_stmt) == lhs
 870                && useless_type_conversion_p
 871                     (TREE_TYPE (TREE_OPERAND (def_rhs, 0)),
 872                      TREE_TYPE (gimple_assign_rhs1 (use_stmt))))
 873         {
 874           tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
 875           tree new_offset, new_base, saved, new_lhs;
 876           while (handled_component_p (*def_rhs_basep))
 877             def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
 878           saved = *def_rhs_basep;
 879           if (TREE_CODE (*def_rhs_basep) == MEM_REF)
 880             {
 881               new_base = TREE_OPERAND (*def_rhs_basep, 0);
 882               new_offset
 883                 = int_const_binop (PLUS_EXPR, TREE_OPERAND (lhs, 1),
 884                                    TREE_OPERAND (*def_rhs_basep, 1), 0);
 885             }
 886           else
 887             {
 888               new_base = build_fold_addr_expr (*def_rhs_basep);
 889               new_offset = TREE_OPERAND (lhs, 1);
 890             }
 891           *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
 892                                    new_base, new_offset);
 893           TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (lhs);
 894           TREE_SIDE_EFFECTS (*def_rhs_basep) = TREE_SIDE_EFFECTS (lhs);
 895           TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (lhs);
 896           new_lhs = unshare_expr (TREE_OPERAND (def_rhs, 0));
 897           gimple_assign_set_lhs (use_stmt, new_lhs);
 898           TREE_THIS_VOLATILE (new_lhs) = TREE_THIS_VOLATILE (lhs);
 899           TREE_SIDE_EFFECTS (new_lhs) = TREE_SIDE_EFFECTS (lhs);
 900           *def_rhs_basep = saved;
 901           tidy_after_forward_propagate_addr (use_stmt);
 902           /* Continue propagating into the RHS if this was not the
 903              only use.  */
 904           if (single_use_p)
 905             return true;
 906         }
 907       else
 908         /* We can have a struct assignment dereferencing our name twice.
 909            Note that we didn't propagate into the lhs to not falsely
 910            claim we did when propagating into the rhs.  */
 911         res = false;
 912     }
 913
 914   /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
 915      nodes from the RHS.  */
 916   rhs = gimple_assign_rhs1 (use_stmt);
 917   if (TREE_CODE (rhs) == ADDR_EXPR)
 918     rhs = TREE_OPERAND (rhs, 0);
 919   while (handled_component_p (rhs))
 920     rhs = TREE_OPERAND (rhs, 0);
 921
 922   /* Now see if the RHS node is a MEM_REF using NAME.  If so,
 923      propagate the ADDR_EXPR into the use of NAME and fold the result.  */
 924   if (TREE_CODE (rhs) == MEM_REF
 925       && TREE_OPERAND (rhs, 0) == name)
 926     {
 927       tree def_rhs_base;
 928       HOST_WIDE_INT def_rhs_offset;
 929       if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
 930                                                          &def_rhs_offset)))
 931         {
 932           double_int off = mem_ref_offset (rhs);
 933           tree new_ptr;
 934           off = double_int_add (off,
 935                                 shwi_to_double_int (def_rhs_offset));
 936           if (TREE_CODE (def_rhs_base) == MEM_REF)
 937             {
 938               off = double_int_add (off, mem_ref_offset (def_rhs_base));
 939               new_ptr = TREE_OPERAND (def_rhs_base, 0);
 940             }
 941           else
 942             new_ptr = build_fold_addr_expr (def_rhs_base);
 943           TREE_OPERAND (rhs, 0) = new_ptr;
 944           TREE_OPERAND (rhs, 1)
 945             = double_int_to_tree (TREE_TYPE (TREE_OPERAND (rhs, 1)), off);
 946           fold_stmt_inplace (use_stmt);
 947           tidy_after_forward_propagate_addr (use_stmt);
 948           return res;
 949         }
 950       /* If the RHS is a plain dereference and the value type is the same as
 951          that of the pointed-to type of the address we can put the
 952          dereferenced address on the RHS preserving the original alias-type.  */
 953       else if (gimple_assign_rhs1 (use_stmt) == rhs
 954                && useless_type_conversion_p
 955                     (TREE_TYPE (gimple_assign_lhs (use_stmt)),
 956                      TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
 957         {
 958           tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
 959           tree new_offset, new_base, saved, new_rhs;
 960           while (handled_component_p (*def_rhs_basep))
 961             def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
 962           saved = *def_rhs_basep;
 963           if (TREE_CODE (*def_rhs_basep) == MEM_REF)
 964             {
 965               new_base = TREE_OPERAND (*def_rhs_basep, 0);
 966               new_offset
 967                 = int_const_binop (PLUS_EXPR, TREE_OPERAND (rhs, 1),
 968                                    TREE_OPERAND (*def_rhs_basep, 1), 0);
 969             }
 970           else
 971             {
 972               new_base = build_fold_addr_expr (*def_rhs_basep);
 973               new_offset = TREE_OPERAND (rhs, 1);
 974             }
 975           *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
 976                                    new_base, new_offset);
 977           TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (rhs);
 978           TREE_SIDE_EFFECTS (*def_rhs_basep) = TREE_SIDE_EFFECTS (rhs);
 979           TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (rhs);
 980           new_rhs = unshare_expr (TREE_OPERAND (def_rhs, 0));
 981           gimple_assign_set_rhs1 (use_stmt, new_rhs);
 982           TREE_THIS_VOLATILE (new_rhs) = TREE_THIS_VOLATILE (rhs);
 983           TREE_SIDE_EFFECTS (new_rhs) = TREE_SIDE_EFFECTS (rhs);
 984           *def_rhs_basep = saved;
 985           fold_stmt_inplace (use_stmt);
 986           tidy_after_forward_propagate_addr (use_stmt);
 987           return res;
 988         }
 989     }
 990
 991   /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
 992      is nothing to do. */
 993   if (gimple_assign_rhs_code (use_stmt) != POINTER_PLUS_EXPR
 994       || gimple_assign_rhs1 (use_stmt) != name)
 995     return false;
 996
 997   /* The remaining cases are all for turning pointer arithmetic into
 998      array indexing.  They only apply when we have the address of
 999      element zero in an array.  If that is not the case then there
1000      is nothing to do.  */
1001   array_ref = TREE_OPERAND (def_rhs, 0);
1002   if ((TREE_CODE (array_ref) != ARRAY_REF
1003        || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
1004        || TREE_CODE (TREE_OPERAND (array_ref, 1)) != INTEGER_CST)
1005       && TREE_CODE (TREE_TYPE (array_ref)) != ARRAY_TYPE)
1006     return false;
1007
1008   rhs2 = gimple_assign_rhs2 (use_stmt);
1009   /* Try to optimize &x[C1] p+ C2 where C2 is a multiple of the size
1010      of the elements in X into &x[C1 + C2/element size].  */
1011   if (TREE_CODE (rhs2) == INTEGER_CST)
1012     {
1013       tree new_rhs = maybe_fold_stmt_addition (gimple_location (use_stmt),
1014                                                TREE_TYPE (def_rhs),
1015                                                def_rhs, rhs2);
1016       if (new_rhs)
1017         {
1018           tree type = TREE_TYPE (gimple_assign_lhs (use_stmt));
1019           new_rhs = unshare_expr (new_rhs);
1020           if (!useless_type_conversion_p (type, TREE_TYPE (new_rhs)))
1021             {
1022               if (!is_gimple_min_invariant (new_rhs))
1023                 new_rhs = force_gimple_operand_gsi (use_stmt_gsi, new_rhs,
1024                                                     true, NULL_TREE,
1025                                                     true, GSI_SAME_STMT);
1026               new_rhs = fold_convert (type, new_rhs);
1027             }
1028           gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
1029           use_stmt = gsi_stmt (*use_stmt_gsi);
1030           update_stmt (use_stmt);
1031           tidy_after_forward_propagate_addr (use_stmt);
1032           return true;
1033         }
1034     }
1035
1036   /* Try to optimize &x[0] p+ OFFSET where OFFSET is defined by
1037      converting a multiplication of an index by the size of the
1038      array elements, then the result is converted into the proper
1039      type for the arithmetic.  */
1040   if (TREE_CODE (rhs2) == SSA_NAME
1041       && (TREE_CODE (array_ref) != ARRAY_REF
1042           || integer_zerop (TREE_OPERAND (array_ref, 1)))
1043       && useless_type_conversion_p (TREE_TYPE (name), TREE_TYPE (def_rhs))
1044       /* Avoid problems with IVopts creating PLUS_EXPRs with a
1045          different type than their operands.  */
1046       && useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
1047     return forward_propagate_addr_into_variable_array_index (rhs2, def_rhs,
1048                                                              use_stmt_gsi);
1049   return false;
1050 }
1051
1052 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
1053
1054    Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
1055    Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
1056    node or for recovery of array indexing from pointer arithmetic.
1057    Returns true, if all uses have been propagated into.  */
1058
1059 static bool
1060 forward_propagate_addr_expr (tree name, tree rhs)
1061 {
1062   int stmt_loop_depth = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_depth;
1063   imm_use_iterator iter;
1064   gimple use_stmt;
1065   bool all = true;
1066   bool single_use_p = has_single_use (name);
1067
1068   FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
1069     {
1070       bool result;
1071       tree use_rhs;
1072
1073       /* If the use is not in a simple assignment statement, then
1074          there is nothing we can do.  */
1075       if (gimple_code (use_stmt) != GIMPLE_ASSIGN)
1076         {
1077           if (!is_gimple_debug (use_stmt))
1078             all = false;
1079           continue;
1080         }
1081
1082       /* If the use is in a deeper loop nest, then we do not want
1083          to propagate non-invariant ADDR_EXPRs into the loop as that
1084          is likely adding expression evaluations into the loop.  */
1085       if (gimple_bb (use_stmt)->loop_depth > stmt_loop_depth
1086           && !is_gimple_min_invariant (rhs))
1087         {
1088           all = false;
1089           continue;
1090         }
1091
1092       {
1093         gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1094         result = forward_propagate_addr_expr_1 (name, rhs, &gsi,
1095                                                 single_use_p);
1096         /* If the use has moved to a different statement adjust
1097            the update machinery for the old statement too.  */
1098         if (use_stmt != gsi_stmt (gsi))
1099           {
1100             update_stmt (use_stmt);
1101             use_stmt = gsi_stmt (gsi);
1102           }
1103
1104         update_stmt (use_stmt);
1105       }
1106       all &= result;
1107
1108       /* Remove intermediate now unused copy and conversion chains.  */
1109       use_rhs = gimple_assign_rhs1 (use_stmt);
1110       if (result
1111           && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
1112           && TREE_CODE (use_rhs) == SSA_NAME
1113           && has_zero_uses (gimple_assign_lhs (use_stmt)))
1114         {
1115           gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1116           release_defs (use_stmt);
1117           gsi_remove (&gsi, true);
1118         }
1119     }
1120
1121   return all && has_zero_uses (name);
1122 }
1123
1124 /* Forward propagate the comparison defined in STMT like
1125    cond_1 = x CMP y to uses of the form
1126      a_1 = (T')cond_1
1127      a_1 = !cond_1
1128      a_1 = cond_1 != 0
1129    Returns true if stmt is now unused.  */
1130
1131 static bool
1132 forward_propagate_comparison (gimple stmt)
1133 {
1134   tree name = gimple_assign_lhs (stmt);
1135   gimple use_stmt;
1136   tree tmp = NULL_TREE;
1137
1138   /* Don't propagate ssa names that occur in abnormal phis.  */
1139   if ((TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
1140        && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
1141       || (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME
1142         && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs2 (stmt))))
1143     return false;
1144
1145   /* Do not un-cse comparisons.  But propagate through copies.  */
1146   use_stmt = get_prop_dest_stmt (name, &name);
1147   if (!use_stmt)
1148     return false;
1149
1150   /* Conversion of the condition result to another integral type.  */
1151   if (is_gimple_assign (use_stmt)
1152       && (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt))
1153           || TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt))
1154              == tcc_comparison
1155           || gimple_assign_rhs_code (use_stmt) == TRUTH_NOT_EXPR)
1156       && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (use_stmt))))
1157     {
1158       tree lhs = gimple_assign_lhs (use_stmt);
1159
1160       /* We can propagate the condition into a conversion.  */
1161       if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt)))
1162         {
1163           /* Avoid using fold here as that may create a COND_EXPR with
1164              non-boolean condition as canonical form.  */
1165           tmp = build2 (gimple_assign_rhs_code (stmt), TREE_TYPE (lhs),
1166                         gimple_assign_rhs1 (stmt), gimple_assign_rhs2 (stmt));
1167         }
1168       /* We can propagate the condition into X op CST where op
1169          is EQ_EXPR or NE_EXPR and CST is either one or zero.  */
1170       else if (TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt))
1171               == tcc_comparison
1172              && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME
1173              && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST)
1174       {
1175         enum tree_code code = gimple_assign_rhs_code (use_stmt);
1176         tree cst = gimple_assign_rhs2 (use_stmt);
1177         tree cond;
1178
1179         cond = build2 (gimple_assign_rhs_code (stmt),
1180                        TREE_TYPE (cst),
1181                        gimple_assign_rhs1 (stmt),
1182                        gimple_assign_rhs2 (stmt));
1183
1184         tmp = combine_cond_expr_cond (gimple_location (use_stmt),
1185                                       code, TREE_TYPE (lhs),
1186                                       cond, cst, false);
1187         if (tmp == NULL_TREE)
1188           return false;
1189       }
1190       /* We can propagate the condition into a statement that
1191          computes the logical negation of the comparison result.  */
1192       else if (gimple_assign_rhs_code (use_stmt) == TRUTH_NOT_EXPR)
1193         {
1194           tree type = TREE_TYPE (gimple_assign_rhs1 (stmt));
1195           bool nans = HONOR_NANS (TYPE_MODE (type));
1196           enum tree_code code;
1197           code = invert_tree_comparison (gimple_assign_rhs_code (stmt), nans);
1198           if (code == ERROR_MARK)
1199             return false;
1200
1201           tmp = build2 (code, TREE_TYPE (lhs), gimple_assign_rhs1 (stmt),
1202                         gimple_assign_rhs2 (stmt));
1203         }
1204       else
1205         return false;
1206
1207       {
1208         gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1209         gimple_assign_set_rhs_from_tree (&gsi, unshare_expr (tmp));
1210         use_stmt = gsi_stmt (gsi);
1211         update_stmt (use_stmt);
1212       }
1213
1214       if (dump_file && (dump_flags & TDF_DETAILS))
1215         {
1216           tree old_rhs = rhs_to_tree (TREE_TYPE (gimple_assign_lhs (stmt)),
1217                                       stmt);
1218           fprintf (dump_file, "  Replaced '");
1219           print_generic_expr (dump_file, old_rhs, dump_flags);
1220           fprintf (dump_file, "' with '");
1221           print_generic_expr (dump_file, tmp, dump_flags);
1222           fprintf (dump_file, "'\n");
1223         }
1224
1225       /* Remove defining statements.  */
1226       return remove_prop_source_from_use (name);
1227     }
1228
1229   return false;
1230 }
1231
1232 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
1233    If so, we can change STMT into lhs = y which can later be copy
1234    propagated.  Similarly for negation.
1235
1236    This could trivially be formulated as a forward propagation
1237    to immediate uses.  However, we already had an implementation
1238    from DOM which used backward propagation via the use-def links.
1239
1240    It turns out that backward propagation is actually faster as
1241    there's less work to do for each NOT/NEG expression we find.
1242    Backwards propagation needs to look at the statement in a single
1243    backlink.  Forward propagation needs to look at potentially more
1244    than one forward link.  */
1245
1246 static void
1247 simplify_not_neg_expr (gimple_stmt_iterator *gsi_p)
1248 {
1249   gimple stmt = gsi_stmt (*gsi_p);
1250   tree rhs = gimple_assign_rhs1 (stmt);
1251   gimple rhs_def_stmt = SSA_NAME_DEF_STMT (rhs);
1252
1253   /* See if the RHS_DEF_STMT has the same form as our statement.  */
1254   if (is_gimple_assign (rhs_def_stmt)
1255       && gimple_assign_rhs_code (rhs_def_stmt) == gimple_assign_rhs_code (stmt))
1256     {
1257       tree rhs_def_operand = gimple_assign_rhs1 (rhs_def_stmt);
1258
1259       /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME.  */
1260       if (TREE_CODE (rhs_def_operand) == SSA_NAME
1261           && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand))
1262         {
1263           gimple_assign_set_rhs_from_tree (gsi_p, rhs_def_operand);
1264           stmt = gsi_stmt (*gsi_p);
1265           update_stmt (stmt);
1266         }
1267     }
1268 }
1269
1270 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1271    the condition which we may be able to optimize better.  */
1272
1273 static void
1274 simplify_gimple_switch (gimple stmt)
1275 {
1276   tree cond = gimple_switch_index (stmt);
1277   tree def, to, ti;
1278   gimple def_stmt;
1279
1280   /* The optimization that we really care about is removing unnecessary
1281      casts.  That will let us do much better in propagating the inferred
1282      constant at the switch target.  */
1283   if (TREE_CODE (cond) == SSA_NAME)
1284     {
1285       def_stmt = SSA_NAME_DEF_STMT (cond);
1286       if (is_gimple_assign (def_stmt))
1287         {
1288           if (gimple_assign_rhs_code (def_stmt) == NOP_EXPR)
1289             {
1290               int need_precision;
1291               bool fail;
1292
1293               def = gimple_assign_rhs1 (def_stmt);
1294
1295               /* ??? Why was Jeff testing this?  We are gimple...  */
1296               gcc_checking_assert (is_gimple_val (def));
1297
1298               to = TREE_TYPE (cond);
1299               ti = TREE_TYPE (def);
1300
1301               /* If we have an extension that preserves value, then we
1302                  can copy the source value into the switch.  */
1303
1304               need_precision = TYPE_PRECISION (ti);
1305               fail = false;
1306               if (! INTEGRAL_TYPE_P (ti))
1307                 fail = true;
1308               else if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti))
1309                 fail = true;
1310               else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti))
1311                 need_precision += 1;
1312               if (TYPE_PRECISION (to) < need_precision)
1313                 fail = true;
1314
1315               if (!fail)
1316                 {
1317                   gimple_switch_set_index (stmt, def);
1318                   update_stmt (stmt);
1319                 }
1320             }
1321         }
1322     }
1323 }
1324
1325 /* For pointers p2 and p1 return p2 - p1 if the
1326    difference is known and constant, otherwise return NULL.  */
1327
1328 static tree
1329 constant_pointer_difference (tree p1, tree p2)
1330 {
1331   int i, j;
1332 #define CPD_ITERATIONS 5
1333   tree exps[2][CPD_ITERATIONS];
1334   tree offs[2][CPD_ITERATIONS];
1335   int cnt[2];
1336
1337   for (i = 0; i < 2; i++)
1338     {
1339       tree p = i ? p1 : p2;
1340       tree off = size_zero_node;
1341       gimple stmt;
1342       enum tree_code code;
1343
1344       /* For each of p1 and p2 we need to iterate at least
1345          twice, to handle ADDR_EXPR directly in p1/p2,
1346          SSA_NAME with ADDR_EXPR or POINTER_PLUS_EXPR etc.
1347          on definition's stmt RHS.  Iterate a few extra times.  */
1348       j = 0;
1349       do
1350         {
1351           if (!POINTER_TYPE_P (TREE_TYPE (p)))
1352             break;
1353           if (TREE_CODE (p) == ADDR_EXPR)
1354             {
1355               tree q = TREE_OPERAND (p, 0);
1356               HOST_WIDE_INT offset;
1357               tree base = get_addr_base_and_unit_offset (q, &offset);
1358               if (base)
1359                 {
1360                   q = base;
1361                   if (offset)
1362                     off = size_binop (PLUS_EXPR, off, size_int (offset));
1363                 }
1364               if (TREE_CODE (q) == MEM_REF
1365                   && TREE_CODE (TREE_OPERAND (q, 0)) == SSA_NAME)
1366                 {
1367                   p = TREE_OPERAND (q, 0);
1368                   off = size_binop (PLUS_EXPR, off,
1369                                     double_int_to_tree (sizetype,
1370                                                         mem_ref_offset (q)));
1371                 }
1372               else
1373                 {
1374                   exps[i][j] = q;
1375                   offs[i][j++] = off;
1376                   break;
1377                 }
1378             }
1379           if (TREE_CODE (p) != SSA_NAME)
1380             break;
1381           exps[i][j] = p;
1382           offs[i][j++] = off;
1383           if (j == CPD_ITERATIONS)
1384             break;
1385           stmt = SSA_NAME_DEF_STMT (p);
1386           if (!is_gimple_assign (stmt) || gimple_assign_lhs (stmt) != p)
1387             break;
1388           code = gimple_assign_rhs_code (stmt);
1389           if (code == POINTER_PLUS_EXPR)
1390             {
1391               if (TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)
1392                 break;
1393               off = size_binop (PLUS_EXPR, off, gimple_assign_rhs2 (stmt));
1394               p = gimple_assign_rhs1 (stmt);
1395             }
1396           else if (code == ADDR_EXPR || code == NOP_EXPR)
1397             p = gimple_assign_rhs1 (stmt);
1398           else
1399             break;
1400         }
1401       while (1);
1402       cnt[i] = j;
1403     }
1404
1405   for (i = 0; i < cnt[0]; i++)
1406     for (j = 0; j < cnt[1]; j++)
1407       if (exps[0][i] == exps[1][j])
1408         return size_binop (MINUS_EXPR, offs[0][i], offs[1][j]);
1409
1410   return NULL_TREE;
1411 }
1412
1413 /* *GSI_P is a GIMPLE_CALL to a builtin function.
1414    Optimize
1415    memcpy (p, "abcd", 4);
1416    memset (p + 4, ' ', 3);
1417    into
1418    memcpy (p, "abcd   ", 7);
1419    call if the latter can be stored by pieces during expansion.  */
1420
1421 static bool
1422 simplify_builtin_call (gimple_stmt_iterator *gsi_p, tree callee2)
1423 {
1424   gimple stmt1, stmt2 = gsi_stmt (*gsi_p);
1425   tree vuse = gimple_vuse (stmt2);
1426   if (vuse == NULL)
1427     return false;
1428   stmt1 = SSA_NAME_DEF_STMT (vuse);
1429
1430   switch (DECL_FUNCTION_CODE (callee2))
1431     {
1432     case BUILT_IN_MEMSET:
1433       if (gimple_call_num_args (stmt2) != 3
1434           || gimple_call_lhs (stmt2)
1435           || CHAR_BIT != 8
1436           || BITS_PER_UNIT != 8)
1437         break;
1438       else
1439         {
1440           tree callee1;
1441           tree ptr1, src1, str1, off1, len1, lhs1;
1442           tree ptr2 = gimple_call_arg (stmt2, 0);
1443           tree val2 = gimple_call_arg (stmt2, 1);
1444           tree len2 = gimple_call_arg (stmt2, 2);
1445           tree diff, vdef, new_str_cst;
1446           gimple use_stmt;
1447           unsigned int ptr1_align;
1448           unsigned HOST_WIDE_INT src_len;
1449           char *src_buf;
1450           use_operand_p use_p;
1451
1452           if (!host_integerp (val2, 0)
1453               || !host_integerp (len2, 1))
1454             break;
1455           if (is_gimple_call (stmt1))
1456             {
1457               /* If first stmt is a call, it needs to be memcpy
1458                  or mempcpy, with string literal as second argument and
1459                  constant length.  */
1460               callee1 = gimple_call_fndecl (stmt1);
1461               if (callee1 == NULL_TREE
1462                   || DECL_BUILT_IN_CLASS (callee1) != BUILT_IN_NORMAL
1463                   || gimple_call_num_args (stmt1) != 3)
1464                 break;
1465               if (DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMCPY
1466                   && DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMPCPY)
1467                 break;
1468               ptr1 = gimple_call_arg (stmt1, 0);
1469               src1 = gimple_call_arg (stmt1, 1);
1470               len1 = gimple_call_arg (stmt1, 2);
1471               lhs1 = gimple_call_lhs (stmt1);
1472               if (!host_integerp (len1, 1))
1473                 break;
1474               str1 = string_constant (src1, &off1);
1475               if (str1 == NULL_TREE)
1476                 break;
1477               if (!host_integerp (off1, 1)
1478                   || compare_tree_int (off1, TREE_STRING_LENGTH (str1) - 1) > 0
1479                   || compare_tree_int (len1, TREE_STRING_LENGTH (str1)
1480                                              - tree_low_cst (off1, 1)) > 0
1481                   || TREE_CODE (TREE_TYPE (str1)) != ARRAY_TYPE
1482                   || TYPE_MODE (TREE_TYPE (TREE_TYPE (str1)))
1483                      != TYPE_MODE (char_type_node))
1484                 break;
1485             }
1486           else if (gimple_assign_single_p (stmt1))
1487             {
1488               /* Otherwise look for length 1 memcpy optimized into
1489                  assignment.  */
1490               ptr1 = gimple_assign_lhs (stmt1);
1491               src1 = gimple_assign_rhs1 (stmt1);
1492               if (TREE_CODE (ptr1) != MEM_REF
1493                   || TYPE_MODE (TREE_TYPE (ptr1)) != TYPE_MODE (char_type_node)
1494                   || !host_integerp (src1, 0))
1495                 break;
1496               ptr1 = build_fold_addr_expr (ptr1);
1497               callee1 = NULL_TREE;
1498               len1 = size_one_node;
1499               lhs1 = NULL_TREE;
1500               off1 = size_zero_node;
1501               str1 = NULL_TREE;
1502             }
1503           else
1504             break;
1505
1506           diff = constant_pointer_difference (ptr1, ptr2);
1507           if (diff == NULL && lhs1 != NULL)
1508             {
1509               diff = constant_pointer_difference (lhs1, ptr2);
1510               if (DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1511                   && diff != NULL)
1512                 diff = size_binop (PLUS_EXPR, diff,
1513                                    fold_convert (sizetype, len1));
1514             }
1515           /* If the difference between the second and first destination pointer
1516              is not constant, or is bigger than memcpy length, bail out.  */
1517           if (diff == NULL
1518               || !host_integerp (diff, 1)
1519               || tree_int_cst_lt (len1, diff))
1520             break;
1521
1522           /* Use maximum of difference plus memset length and memcpy length
1523              as the new memcpy length, if it is too big, bail out.  */
1524           src_len = tree_low_cst (diff, 1);
1525           src_len += tree_low_cst (len2, 1);
1526           if (src_len < (unsigned HOST_WIDE_INT) tree_low_cst (len1, 1))
1527             src_len = tree_low_cst (len1, 1);
1528           if (src_len > 1024)
1529             break;
1530
1531           /* If mempcpy value is used elsewhere, bail out, as mempcpy
1532              with bigger length will return different result.  */
1533           if (lhs1 != NULL_TREE
1534               && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1535               && (TREE_CODE (lhs1) != SSA_NAME
1536                   || !single_imm_use (lhs1, &use_p, &use_stmt)
1537                   || use_stmt != stmt2))
1538             break;
1539
1540           /* If anything reads memory in between memcpy and memset
1541              call, the modified memcpy call might change it.  */
1542           vdef = gimple_vdef (stmt1);
1543           if (vdef != NULL
1544               && (!single_imm_use (vdef, &use_p, &use_stmt)
1545                   || use_stmt != stmt2))
1546             break;
1547
1548           ptr1_align = get_pointer_alignment (ptr1, BIGGEST_ALIGNMENT);
1549           /* Construct the new source string literal.  */
1550           src_buf = XALLOCAVEC (char, src_len + 1);
1551           if (callee1)
1552             memcpy (src_buf,
1553                     TREE_STRING_POINTER (str1) + tree_low_cst (off1, 1),
1554                     tree_low_cst (len1, 1));
1555           else
1556             src_buf[0] = tree_low_cst (src1, 0);
1557           memset (src_buf + tree_low_cst (diff, 1),
1558                   tree_low_cst (val2, 1), tree_low_cst (len2, 1));
1559           src_buf[src_len] = '\0';
1560           /* Neither builtin_strncpy_read_str nor builtin_memcpy_read_str
1561              handle embedded '\0's.  */
1562           if (strlen (src_buf) != src_len)
1563             break;
1564           rtl_profile_for_bb (gimple_bb (stmt2));
1565           /* If the new memcpy wouldn't be emitted by storing the literal
1566              by pieces, this optimization might enlarge .rodata too much,
1567              as commonly used string literals couldn't be shared any
1568              longer.  */
1569           if (!can_store_by_pieces (src_len,
1570                                     builtin_strncpy_read_str,
1571                                     src_buf, ptr1_align, false))
1572             break;
1573
1574           new_str_cst = build_string_literal (src_len, src_buf);
1575           if (callee1)
1576             {
1577               /* If STMT1 is a mem{,p}cpy call, adjust it and remove
1578                  memset call.  */
1579               if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1580                 gimple_call_set_lhs (stmt1, NULL_TREE);
1581               gimple_call_set_arg (stmt1, 1, new_str_cst);
1582               gimple_call_set_arg (stmt1, 2,
1583                                    build_int_cst (TREE_TYPE (len1), src_len));
1584               update_stmt (stmt1);
1585               unlink_stmt_vdef (stmt2);
1586               gsi_remove (gsi_p, true);
1587               release_defs (stmt2);
1588               if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1589                 release_ssa_name (lhs1);
1590               return true;
1591             }
1592           else
1593             {
1594               /* Otherwise, if STMT1 is length 1 memcpy optimized into
1595                  assignment, remove STMT1 and change memset call into
1596                  memcpy call.  */
1597               gimple_stmt_iterator gsi = gsi_for_stmt (stmt1);
1598
1599               if (!is_gimple_val (ptr1))
1600                 ptr1 = force_gimple_operand_gsi (gsi_p, ptr1, true, NULL_TREE,
1601                                                  true, GSI_SAME_STMT);
1602               gimple_call_set_fndecl (stmt2, built_in_decls [BUILT_IN_MEMCPY]);
1603               gimple_call_set_arg (stmt2, 0, ptr1);
1604               gimple_call_set_arg (stmt2, 1, new_str_cst);
1605               gimple_call_set_arg (stmt2, 2,
1606                                    build_int_cst (TREE_TYPE (len2), src_len));
1607               unlink_stmt_vdef (stmt1);
1608               gsi_remove (&gsi, true);
1609               release_defs (stmt1);
1610               update_stmt (stmt2);
1611               return false;
1612             }
1613         }
1614       break;
1615     default:
1616       break;
1617     }
1618   return false;
1619 }
1620
1621 /* Run bitwise and assignments throug the folder.  If the first argument is an
1622    ssa name that is itself a result of a typecast of an ADDR_EXPR to an
1623    integer, feed the ADDR_EXPR to the folder rather than the ssa name.
1624 */
1625
1626 static void
1627 simplify_bitwise_and (gimple_stmt_iterator *gsi, gimple stmt)
1628 {
1629   tree res;
1630   tree arg1 = gimple_assign_rhs1 (stmt);
1631   tree arg2 = gimple_assign_rhs2 (stmt);
1632
1633   if (TREE_CODE (arg2) != INTEGER_CST)
1634     return;
1635
1636   if (TREE_CODE (arg1) == SSA_NAME && !SSA_NAME_IS_DEFAULT_DEF (arg1))
1637     {
1638       gimple def = SSA_NAME_DEF_STMT (arg1);
1639
1640       if (gimple_assign_cast_p (def)
1641           && INTEGRAL_TYPE_P (gimple_expr_type (def)))
1642         {
1643           tree op = gimple_assign_rhs1 (def);
1644
1645           if (TREE_CODE (op) == ADDR_EXPR)
1646             arg1 = op;
1647         }
1648     }
1649
1650   res = fold_binary_loc (gimple_location (stmt),
1651                      BIT_AND_EXPR, TREE_TYPE (gimple_assign_lhs (stmt)),
1652                      arg1, arg2);
1653   if (res && is_gimple_min_invariant (res))
1654     {
1655       gimple_assign_set_rhs_from_tree (gsi, res);
1656       update_stmt (stmt);
1657     }
1658   return;
1659 }
1660
1661
1662 /* Perform re-associations of the plus or minus statement STMT that are
1663    always permitted.  Returns true if the CFG was changed.  */
1664
1665 static bool
1666 associate_plusminus (gimple stmt)
1667 {
1668   tree rhs1 = gimple_assign_rhs1 (stmt);
1669   tree rhs2 = gimple_assign_rhs2 (stmt);
1670   enum tree_code code = gimple_assign_rhs_code (stmt);
1671   gimple_stmt_iterator gsi;
1672   bool changed;
1673
1674   /* We can't reassociate at all for saturating types.  */
1675   if (TYPE_SATURATING (TREE_TYPE (rhs1)))
1676     return false;
1677
1678   /* First contract negates.  */
1679   do
1680     {
1681       changed = false;
1682
1683       /* A +- (-B) -> A -+ B.  */
1684       if (TREE_CODE (rhs2) == SSA_NAME)
1685         {
1686           gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
1687           if (is_gimple_assign (def_stmt)
1688               && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
1689               && can_propagate_from (def_stmt))
1690             {
1691               code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR;
1692               gimple_assign_set_rhs_code (stmt, code);
1693               rhs2 = gimple_assign_rhs1 (def_stmt);
1694               gimple_assign_set_rhs2 (stmt, rhs2);
1695               gimple_set_modified (stmt, true);
1696               changed = true;
1697             }
1698         }
1699
1700       /* (-A) + B -> B - A.  */
1701       if (TREE_CODE (rhs1) == SSA_NAME
1702           && code == PLUS_EXPR)
1703         {
1704           gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
1705           if (is_gimple_assign (def_stmt)
1706               && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
1707               && can_propagate_from (def_stmt))
1708             {
1709               code = MINUS_EXPR;
1710               gimple_assign_set_rhs_code (stmt, code);
1711               rhs1 = rhs2;
1712               gimple_assign_set_rhs1 (stmt, rhs1);
1713               rhs2 = gimple_assign_rhs1 (def_stmt);
1714               gimple_assign_set_rhs2 (stmt, rhs2);
1715               gimple_set_modified (stmt, true);
1716               changed = true;
1717             }
1718         }
1719     }
1720   while (changed);
1721
1722   /* We can't reassociate floating-point or fixed-point plus or minus
1723      because of saturation to +-Inf.  */
1724   if (FLOAT_TYPE_P (TREE_TYPE (rhs1))
1725       || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1)))
1726     goto out;
1727
1728   /* Second match patterns that allow contracting a plus-minus pair
1729      irrespective of overflow issues.
1730
1731         (A +- B) - A       ->  +- B
1732         (A +- B) -+ B      ->  A
1733         (CST +- A) +- CST  ->  CST +- A
1734         (A + CST) +- CST   ->  A + CST
1735         ~A + A             ->  -1
1736         ~A + 1             ->  -A
1737         A - (A +- B)       ->  -+ B
1738         A +- (B +- A)      ->  +- B
1739         CST +- (CST +- A)  ->  CST +- A
1740         CST +- (A +- CST)  ->  CST +- A
1741         A + ~A             ->  -1
1742
1743      via commutating the addition and contracting operations to zero
1744      by reassociation.  */
1745
1746   gsi = gsi_for_stmt (stmt);
1747   if (TREE_CODE (rhs1) == SSA_NAME)
1748     {
1749       gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
1750       if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
1751         {
1752           enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
1753           if (def_code == PLUS_EXPR
1754               || def_code == MINUS_EXPR)
1755             {
1756               tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
1757               tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
1758               if (operand_equal_p (def_rhs1, rhs2, 0)
1759                   && code == MINUS_EXPR)
1760                 {
1761                   /* (A +- B) - A -> +- B.  */
1762                   code = ((def_code == PLUS_EXPR)
1763                           ? TREE_CODE (def_rhs2) : NEGATE_EXPR);
1764                   rhs1 = def_rhs2;
1765                   rhs2 = NULL_TREE;
1766                   gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
1767                   gcc_assert (gsi_stmt (gsi) == stmt);
1768                   gimple_set_modified (stmt, true);
1769                 }
1770               else if (operand_equal_p (def_rhs2, rhs2, 0)
1771                        && code != def_code)
1772                 {
1773                   /* (A +- B) -+ B -> A.  */
1774                   code = TREE_CODE (def_rhs1);
1775                   rhs1 = def_rhs1;
1776                   rhs2 = NULL_TREE;
1777                   gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
1778                   gcc_assert (gsi_stmt (gsi) == stmt);
1779                   gimple_set_modified (stmt, true);
1780                 }
1781               else if (TREE_CODE (rhs2) == INTEGER_CST
1782                        && TREE_CODE (def_rhs1) == INTEGER_CST)
1783                 {
1784                   /* (CST +- A) +- CST -> CST +- A.  */
1785                   tree cst = fold_binary (code, TREE_TYPE (rhs1),
1786                                           def_rhs1, rhs2);
1787                   if (cst && !TREE_OVERFLOW (cst))
1788                     {
1789                       code = def_code;
1790                       gimple_assign_set_rhs_code (stmt, code);
1791                       rhs1 = cst;
1792                       gimple_assign_set_rhs1 (stmt, rhs1);
1793                       rhs2 = def_rhs2;
1794                       gimple_assign_set_rhs2 (stmt, rhs2);
1795                       gimple_set_modified (stmt, true);
1796                     }
1797                 }
1798               else if (TREE_CODE (rhs2) == INTEGER_CST
1799                        && TREE_CODE (def_rhs2) == INTEGER_CST
1800                        && def_code == PLUS_EXPR)
1801                 {
1802                   /* (A + CST) +- CST -> A + CST.  */
1803                   tree cst = fold_binary (code, TREE_TYPE (rhs1),
1804                                           def_rhs2, rhs2);
1805                   if (cst && !TREE_OVERFLOW (cst))
1806                     {
1807                       code = PLUS_EXPR;
1808                       gimple_assign_set_rhs_code (stmt, code);
1809                       rhs1 = def_rhs1;
1810                       gimple_assign_set_rhs1 (stmt, rhs1);
1811                       rhs2 = cst;
1812                       gimple_assign_set_rhs2 (stmt, rhs2);
1813                       gimple_set_modified (stmt, true);
1814                     }
1815                 }
1816             }
1817           else if (def_code == BIT_NOT_EXPR
1818                    && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
1819             {
1820               tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
1821               if (code == PLUS_EXPR
1822                   && operand_equal_p (def_rhs1, rhs2, 0))
1823                 {
1824                   /* ~A + A -> -1.  */
1825                   code = INTEGER_CST;
1826                   rhs1 = build_int_cst_type (TREE_TYPE (rhs2), -1);
1827                   rhs2 = NULL_TREE;
1828                   gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
1829                   gcc_assert (gsi_stmt (gsi) == stmt);
1830                   gimple_set_modified (stmt, true);
1831                 }
1832               else if (code == PLUS_EXPR
1833                        && integer_onep (rhs1))
1834                 {
1835                   /* ~A + 1 -> -A.  */
1836                   code = NEGATE_EXPR;
1837                   rhs1 = def_rhs1;
1838                   rhs2 = NULL_TREE;
1839                   gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
1840                   gcc_assert (gsi_stmt (gsi) == stmt);
1841                   gimple_set_modified (stmt, true);
1842                 }
1843             }
1844         }
1845     }
1846
1847   if (rhs2 && TREE_CODE (rhs2) == SSA_NAME)
1848     {
1849       gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
1850       if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
1851         {
1852           enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
1853           if (def_code == PLUS_EXPR
1854               || def_code == MINUS_EXPR)
1855             {
1856               tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
1857               tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
1858               if (operand_equal_p (def_rhs1, rhs1, 0)
1859                   && code == MINUS_EXPR)
1860                 {
1861                   /* A - (A +- B) -> -+ B.  */
1862                   code = ((def_code == PLUS_EXPR)
1863                           ? NEGATE_EXPR : TREE_CODE (def_rhs2));
1864                   rhs1 = def_rhs2;
1865                   rhs2 = NULL_TREE;
1866                   gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
1867                   gcc_assert (gsi_stmt (gsi) == stmt);
1868                   gimple_set_modified (stmt, true);
1869                 }
1870               else if (operand_equal_p (def_rhs2, rhs1, 0)
1871                        && code != def_code)
1872                 {
1873                   /* A +- (B +- A) -> +- B.  */
1874                   code = ((code == PLUS_EXPR)
1875                           ? TREE_CODE (def_rhs1) : NEGATE_EXPR);
1876                   rhs1 = def_rhs1;
1877                   rhs2 = NULL_TREE;
1878                   gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
1879                   gcc_assert (gsi_stmt (gsi) == stmt);
1880                   gimple_set_modified (stmt, true);
1881                 }
1882               else if (TREE_CODE (rhs1) == INTEGER_CST
1883                        && TREE_CODE (def_rhs1) == INTEGER_CST)
1884                 {
1885                   /* CST +- (CST +- A) -> CST +- A.  */
1886                   tree cst = fold_binary (code, TREE_TYPE (rhs2),
1887                                           rhs1, def_rhs1);
1888                   if (cst && !TREE_OVERFLOW (cst))
1889                     {
1890                       code = (code == def_code ? PLUS_EXPR : MINUS_EXPR);
1891                       gimple_assign_set_rhs_code (stmt, code);
1892                       rhs1 = cst;
1893                       gimple_assign_set_rhs1 (stmt, rhs1);
1894                       rhs2 = def_rhs2;
1895                       gimple_assign_set_rhs2 (stmt, rhs2);
1896                       gimple_set_modified (stmt, true);
1897                     }
1898                 }
1899               else if (TREE_CODE (rhs1) == INTEGER_CST
1900                        && TREE_CODE (def_rhs2) == INTEGER_CST)
1901                 {
1902                   /* CST +- (A +- CST) -> CST +- A.  */
1903                   tree cst = fold_binary (def_code == code
1904                                           ? PLUS_EXPR : MINUS_EXPR,
1905                                           TREE_TYPE (rhs2),
1906                                           rhs1, def_rhs2);
1907                   if (cst && !TREE_OVERFLOW (cst))
1908                     {
1909                       rhs1 = cst;
1910                       gimple_assign_set_rhs1 (stmt, rhs1);
1911                       rhs2 = def_rhs1;
1912                       gimple_assign_set_rhs2 (stmt, rhs2);
1913                       gimple_set_modified (stmt, true);
1914                     }
1915                 }
1916             }
1917           else if (def_code == BIT_NOT_EXPR
1918                    && INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
1919             {
1920               tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
1921               if (code == PLUS_EXPR
1922                   && operand_equal_p (def_rhs1, rhs1, 0))
1923                 {
1924                   /* A + ~A -> -1.  */
1925                   code = INTEGER_CST;
1926                   rhs1 = build_int_cst_type (TREE_TYPE (rhs1), -1);
1927                   rhs2 = NULL_TREE;
1928                   gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
1929                   gcc_assert (gsi_stmt (gsi) == stmt);
1930                   gimple_set_modified (stmt, true);
1931                 }
1932             }
1933         }
1934     }
1935
1936 out:
1937   if (gimple_modified_p (stmt))
1938     {
1939       fold_stmt_inplace (stmt);
1940       update_stmt (stmt);
1941       if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
1942           && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
1943         return true;
1944     }
1945
1946   return false;
1947 }
1948
1949 /* Main entry point for the forward propagation optimizer.  */
1950
1951 static unsigned int
1952 tree_ssa_forward_propagate_single_use_vars (void)
1953 {
1954   basic_block bb;
1955   unsigned int todoflags = 0;
1956
1957   cfg_changed = false;
1958
1959   FOR_EACH_BB (bb)
1960     {
1961       gimple_stmt_iterator gsi;
1962
1963       /* Note we update GSI within the loop as necessary.  */
1964       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
1965         {
1966           gimple stmt = gsi_stmt (gsi);
1967
1968           /* If this statement sets an SSA_NAME to an address,
1969              try to propagate the address into the uses of the SSA_NAME.  */
1970           if (is_gimple_assign (stmt))
1971             {
1972               tree lhs = gimple_assign_lhs (stmt);
1973               tree rhs = gimple_assign_rhs1 (stmt);
1974
1975               if (TREE_CODE (lhs) != SSA_NAME)
1976                 {
1977                   gsi_next (&gsi);
1978                   continue;
1979                 }
1980
1981               if (gimple_assign_rhs_code (stmt) == ADDR_EXPR
1982                   /* Handle pointer conversions on invariant addresses
1983                      as well, as this is valid gimple.  */
1984                   || (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
1985                       && TREE_CODE (rhs) == ADDR_EXPR
1986                       && POINTER_TYPE_P (TREE_TYPE (lhs))))
1987                 {
1988                   tree base = get_base_address (TREE_OPERAND (rhs, 0));
1989                   if ((!base
1990                        || !DECL_P (base)
1991                        || decl_address_invariant_p (base))
1992                       && !stmt_references_abnormal_ssa_name (stmt)
1993                       && forward_propagate_addr_expr (lhs, rhs))
1994                     {
1995                       release_defs (stmt);
1996                       todoflags |= TODO_remove_unused_locals;
1997                       gsi_remove (&gsi, true);
1998                     }
1999                   else
2000                     gsi_next (&gsi);
2001                 }
2002               else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR
2003                        && can_propagate_from (stmt))
2004                 {
2005                   if (TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST
2006                       /* ???  Better adjust the interface to that function
2007                          instead of building new trees here.  */
2008                       && forward_propagate_addr_expr
2009                            (lhs,
2010                             build1 (ADDR_EXPR,
2011                                     TREE_TYPE (rhs),
2012                                     fold_build2 (MEM_REF,
2013                                                  TREE_TYPE (TREE_TYPE (rhs)),
2014                                                  rhs,
2015                                                  fold_convert
2016                                                    (ptr_type_node,
2017                                                     gimple_assign_rhs2 (stmt))))))
2018                     {
2019                       release_defs (stmt);
2020                       todoflags |= TODO_remove_unused_locals;
2021                       gsi_remove (&gsi, true);
2022                     }
2023                   else if (is_gimple_min_invariant (rhs))
2024                     {
2025                       /* Make sure to fold &a[0] + off_1 here.  */
2026                       fold_stmt_inplace (stmt);
2027                       update_stmt (stmt);
2028                       if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
2029                         gsi_next (&gsi);
2030                     }
2031                   else
2032                     gsi_next (&gsi);
2033                 }
2034               else if ((gimple_assign_rhs_code (stmt) == BIT_NOT_EXPR
2035                         || gimple_assign_rhs_code (stmt) == NEGATE_EXPR)
2036                        && TREE_CODE (rhs) == SSA_NAME)
2037                 {
2038                   simplify_not_neg_expr (&gsi);
2039                   gsi_next (&gsi);
2040                 }
2041               else if (gimple_assign_rhs_code (stmt) == COND_EXPR)
2042                 {
2043                   /* In this case the entire COND_EXPR is in rhs1. */
2044                   int did_something;
2045                   fold_defer_overflow_warnings ();
2046                   did_something = forward_propagate_into_cond (&gsi);
2047                   stmt = gsi_stmt (gsi);
2048                   if (did_something == 2)
2049                     cfg_changed = true;
2050                   fold_undefer_overflow_warnings (!TREE_NO_WARNING (rhs)
2051                     && did_something, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
2052                   gsi_next (&gsi);
2053                 }
2054               else if (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt))
2055                                         == tcc_comparison)
2056                 {
2057                   if (forward_propagate_comparison (stmt))
2058                     cfg_changed = true;
2059                   gsi_next (&gsi);
2060                 }
2061               else if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR)
2062                 {
2063                   simplify_bitwise_and (&gsi, stmt);
2064                   gsi_next (&gsi);
2065                 }
2066               else if (gimple_assign_rhs_code (stmt) == PLUS_EXPR
2067                        || gimple_assign_rhs_code (stmt) == MINUS_EXPR)
2068                 {
2069                   cfg_changed |= associate_plusminus (stmt);
2070                   gsi_next (&gsi);
2071                 }
2072               else
2073                 gsi_next (&gsi);
2074             }
2075           else if (gimple_code (stmt) == GIMPLE_SWITCH)
2076             {
2077               simplify_gimple_switch (stmt);
2078               gsi_next (&gsi);
2079             }
2080           else if (gimple_code (stmt) == GIMPLE_COND)
2081             {
2082               int did_something;
2083               fold_defer_overflow_warnings ();
2084               did_something = forward_propagate_into_gimple_cond (stmt);
2085               if (did_something == 2)
2086                 cfg_changed = true;
2087               fold_undefer_overflow_warnings (did_something, stmt,
2088                                               WARN_STRICT_OVERFLOW_CONDITIONAL);
2089               gsi_next (&gsi);
2090             }
2091           else if (is_gimple_call (stmt))
2092             {
2093               tree callee = gimple_call_fndecl (stmt);
2094               if (callee == NULL_TREE
2095                   || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL
2096                   || !simplify_builtin_call (&gsi, callee))
2097                 gsi_next (&gsi);
2098             }
2099           else
2100             gsi_next (&gsi);
2101         }
2102     }
2103
2104   if (cfg_changed)
2105     todoflags |= TODO_cleanup_cfg;
2106   return todoflags;
2107 }
2108
2109
2110 static bool
2111 gate_forwprop (void)
2112 {
2113   return flag_tree_forwprop;
2114 }
2115
2116 struct gimple_opt_pass pass_forwprop =
2117 {
2118  {
2119   GIMPLE_PASS,
2120   "forwprop",                   /* name */
2121   gate_forwprop,                /* gate */
2122   tree_ssa_forward_propagate_single_use_vars,   /* execute */
2123   NULL,                         /* sub */
2124   NULL,                         /* next */
2125   0,                            /* static_pass_number */
2126   TV_TREE_FORWPROP,             /* tv_id */
2127   PROP_cfg | PROP_ssa,          /* properties_required */
2128   0,                            /* properties_provided */
2129   0,                            /* properties_destroyed */
2130   0,                            /* todo_flags_start */
2131   TODO_dump_func
2132   | TODO_ggc_collect
2133   | TODO_update_ssa
2134   | TODO_verify_ssa             /* todo_flags_finish */
2135  }
2136 };
2137