gcc/tree-ssa-forwprop.c

   1 /* Forward propagation of expressions for single use variables.
   2    Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010, 2011, 2012
   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 "gimple-pretty-print.h"
  29 #include "tree-flow.h"
  30 #include "tree-pass.h"
  31 #include "langhooks.h"
  32 #include "flags.h"
  33 #include "gimple.h"
  34 #include "expr.h"
  35
  36 /* This pass propagates the RHS of assignment statements into use
  37    sites of the LHS of the assignment.  It's basically a specialized
  38    form of tree combination.   It is hoped all of this can disappear
  39    when we have a generalized tree combiner.
  40
  41    One class of common cases we handle is forward propagating a single use
  42    variable into a COND_EXPR.
  43
  44      bb0:
  45        x = a COND b;
  46        if (x) goto ... else goto ...
  47
  48    Will be transformed into:
  49
  50      bb0:
  51        if (a COND b) goto ... else goto ...
  52
  53    Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
  54
  55    Or (assuming c1 and c2 are constants):
  56
  57      bb0:
  58        x = a + c1;
  59        if (x EQ/NEQ c2) goto ... else goto ...
  60
  61    Will be transformed into:
  62
  63      bb0:
  64         if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
  65
  66    Similarly for x = a - c1.
  67
  68    Or
  69
  70      bb0:
  71        x = !a
  72        if (x) goto ... else goto ...
  73
  74    Will be transformed into:
  75
  76      bb0:
  77         if (a == 0) goto ... else goto ...
  78
  79    Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
  80    For these cases, we propagate A into all, possibly more than one,
  81    COND_EXPRs that use X.
  82
  83    Or
  84
  85      bb0:
  86        x = (typecast) a
  87        if (x) goto ... else goto ...
  88
  89    Will be transformed into:
  90
  91      bb0:
  92         if (a != 0) goto ... else goto ...
  93
  94    (Assuming a is an integral type and x is a boolean or x is an
  95     integral and a is a boolean.)
  96
  97    Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
  98    For these cases, we propagate A into all, possibly more than one,
  99    COND_EXPRs that use X.
 100
 101    In addition to eliminating the variable and the statement which assigns
 102    a value to the variable, we may be able to later thread the jump without
 103    adding insane complexity in the dominator optimizer.
 104
 105    Also note these transformations can cascade.  We handle this by having
 106    a worklist of COND_EXPR statements to examine.  As we make a change to
 107    a statement, we put it back on the worklist to examine on the next
 108    iteration of the main loop.
 109
 110    A second class of propagation opportunities arises for ADDR_EXPR
 111    nodes.
 112
 113      ptr = &x->y->z;
 114      res = *ptr;
 115
 116    Will get turned into
 117
 118      res = x->y->z;
 119
 120    Or
 121      ptr = (type1*)&type2var;
 122      res = *ptr
 123
 124    Will get turned into (if type1 and type2 are the same size
 125    and neither have volatile on them):
 126      res = VIEW_CONVERT_EXPR<type1>(type2var)
 127
 128    Or
 129
 130      ptr = &x[0];
 131      ptr2 = ptr + <constant>;
 132
 133    Will get turned into
 134
 135      ptr2 = &x[constant/elementsize];
 136
 137   Or
 138
 139      ptr = &x[0];
 140      offset = index * element_size;
 141      offset_p = (pointer) offset;
 142      ptr2 = ptr + offset_p
 143
 144   Will get turned into:
 145
 146      ptr2 = &x[index];
 147
 148   Or
 149     ssa = (int) decl
 150     res = ssa & 1
 151
 152   Provided that decl has known alignment >= 2, will get turned into
 153
 154     res = 0
 155
 156   We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to
 157   allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent
 158   {NOT_EXPR,NEG_EXPR}.
 159
 160    This will (of course) be extended as other needs arise.  */
 161
 162 static bool forward_propagate_addr_expr (tree name, tree rhs);
 163
 164 /* Set to true if we delete dead edges during the optimization.  */
 165 static bool cfg_changed;
 166
 167 static tree rhs_to_tree (tree type, gimple stmt);
 168
 169 /* Get the next statement we can propagate NAME's value into skipping
 170    trivial copies.  Returns the statement that is suitable as a
 171    propagation destination or NULL_TREE if there is no such one.
 172    This only returns destinations in a single-use chain.  FINAL_NAME_P
 173    if non-NULL is written to the ssa name that represents the use.  */
 174
 175 static gimple
 176 get_prop_dest_stmt (tree name, tree *final_name_p)
 177 {
 178   use_operand_p use;
 179   gimple use_stmt;
 180
 181   do {
 182     /* If name has multiple uses, bail out.  */
 183     if (!single_imm_use (name, &use, &use_stmt))
 184       return NULL;
 185
 186     /* If this is not a trivial copy, we found it.  */
 187     if (!gimple_assign_ssa_name_copy_p (use_stmt)
 188         || gimple_assign_rhs1 (use_stmt) != name)
 189       break;
 190
 191     /* Continue searching uses of the copy destination.  */
 192     name = gimple_assign_lhs (use_stmt);
 193   } while (1);
 194
 195   if (final_name_p)
 196     *final_name_p = name;
 197
 198   return use_stmt;
 199 }
 200
 201 /* Get the statement we can propagate from into NAME skipping
 202    trivial copies.  Returns the statement which defines the
 203    propagation source or NULL_TREE if there is no such one.
 204    If SINGLE_USE_ONLY is set considers only sources which have
 205    a single use chain up to NAME.  If SINGLE_USE_P is non-null,
 206    it is set to whether the chain to NAME is a single use chain
 207    or not.  SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set.  */
 208
 209 static gimple
 210 get_prop_source_stmt (tree name, bool single_use_only, bool *single_use_p)
 211 {
 212   bool single_use = true;
 213
 214   do {
 215     gimple def_stmt = SSA_NAME_DEF_STMT (name);
 216
 217     if (!has_single_use (name))
 218       {
 219         single_use = false;
 220         if (single_use_only)
 221           return NULL;
 222       }
 223
 224     /* If name is defined by a PHI node or is the default def, bail out.  */
 225     if (!is_gimple_assign (def_stmt))
 226       return NULL;
 227
 228     /* If def_stmt is not a simple copy, we possibly found it.  */
 229     if (!gimple_assign_ssa_name_copy_p (def_stmt))
 230       {
 231         tree rhs;
 232
 233         if (!single_use_only && single_use_p)
 234           *single_use_p = single_use;
 235
 236         /* We can look through pointer conversions in the search
 237            for a useful stmt for the comparison folding.  */
 238         rhs = gimple_assign_rhs1 (def_stmt);
 239         if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
 240             && TREE_CODE (rhs) == SSA_NAME
 241             && POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (def_stmt)))
 242             && POINTER_TYPE_P (TREE_TYPE (rhs)))
 243           name = rhs;
 244         else
 245           return def_stmt;
 246       }
 247     else
 248       {
 249         /* Continue searching the def of the copy source name.  */
 250         name = gimple_assign_rhs1 (def_stmt);
 251       }
 252   } while (1);
 253 }
 254
 255 /* Checks if the destination ssa name in DEF_STMT can be used as
 256    propagation source.  Returns true if so, otherwise false.  */
 257
 258 static bool
 259 can_propagate_from (gimple def_stmt)
 260 {
 261   gcc_assert (is_gimple_assign (def_stmt));
 262
 263   /* If the rhs has side-effects we cannot propagate from it.  */
 264   if (gimple_has_volatile_ops (def_stmt))
 265     return false;
 266
 267   /* If the rhs is a load we cannot propagate from it.  */
 268   if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_reference
 269       || TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_declaration)
 270     return false;
 271
 272   /* Constants can be always propagated.  */
 273   if (gimple_assign_single_p (def_stmt)
 274       && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt)))
 275     return true;
 276
 277   /* We cannot propagate ssa names that occur in abnormal phi nodes.  */
 278   if (stmt_references_abnormal_ssa_name (def_stmt))
 279     return false;
 280
 281   /* If the definition is a conversion of a pointer to a function type,
 282      then we can not apply optimizations as some targets require
 283      function pointers to be canonicalized and in this case this
 284      optimization could eliminate a necessary canonicalization.  */
 285   if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
 286     {
 287       tree rhs = gimple_assign_rhs1 (def_stmt);
 288       if (POINTER_TYPE_P (TREE_TYPE (rhs))
 289           && TREE_CODE (TREE_TYPE (TREE_TYPE (rhs))) == FUNCTION_TYPE)
 290         return false;
 291     }
 292
 293   return true;
 294 }
 295
 296 /* Remove a chain of dead statements starting at the definition of
 297    NAME.  The chain is linked via the first operand of the defining statements.
 298    If NAME was replaced in its only use then this function can be used
 299    to clean up dead stmts.  The function handles already released SSA
 300    names gracefully.
 301    Returns true if cleanup-cfg has to run.  */
 302
 303 static bool
 304 remove_prop_source_from_use (tree name)
 305 {
 306   gimple_stmt_iterator gsi;
 307   gimple stmt;
 308   bool cfg_changed = false;
 309
 310   do {
 311     basic_block bb;
 312
 313     if (SSA_NAME_IN_FREE_LIST (name)
 314         || SSA_NAME_IS_DEFAULT_DEF (name)
 315         || !has_zero_uses (name))
 316       return cfg_changed;
 317
 318     stmt = SSA_NAME_DEF_STMT (name);
 319     if (gimple_code (stmt) == GIMPLE_PHI
 320         || gimple_has_side_effects (stmt))
 321       return cfg_changed;
 322
 323     bb = gimple_bb (stmt);
 324     gsi = gsi_for_stmt (stmt);
 325     unlink_stmt_vdef (stmt);
 326     if (gsi_remove (&gsi, true))
 327       cfg_changed |= gimple_purge_dead_eh_edges (bb);
 328     release_defs (stmt);
 329
 330     name = is_gimple_assign (stmt) ? gimple_assign_rhs1 (stmt) : NULL_TREE;
 331   } while (name && TREE_CODE (name) == SSA_NAME);
 332
 333   return cfg_changed;
 334 }
 335
 336 /* Return the rhs of a gimple_assign STMT in a form of a single tree,
 337    converted to type TYPE.
 338
 339    This should disappear, but is needed so we can combine expressions and use
 340    the fold() interfaces. Long term, we need to develop folding and combine
 341    routines that deal with gimple exclusively . */
 342
 343 static tree
 344 rhs_to_tree (tree type, gimple stmt)
 345 {
 346   location_t loc = gimple_location (stmt);
 347   enum tree_code code = gimple_assign_rhs_code (stmt);
 348   if (get_gimple_rhs_class (code) == GIMPLE_TERNARY_RHS)
 349     return fold_build3_loc (loc, code, type, gimple_assign_rhs1 (stmt),
 350                             gimple_assign_rhs2 (stmt),
 351                             gimple_assign_rhs3 (stmt));
 352   else if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
 353     return fold_build2_loc (loc, code, type, gimple_assign_rhs1 (stmt),
 354                         gimple_assign_rhs2 (stmt));
 355   else if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
 356     return build1 (code, type, gimple_assign_rhs1 (stmt));
 357   else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
 358     return gimple_assign_rhs1 (stmt);
 359   else
 360     gcc_unreachable ();
 361 }
 362
 363 /* Combine OP0 CODE OP1 in the context of a COND_EXPR.  Returns
 364    the folded result in a form suitable for COND_EXPR_COND or
 365    NULL_TREE, if there is no suitable simplified form.  If
 366    INVARIANT_ONLY is true only gimple_min_invariant results are
 367    considered simplified.  */
 368
 369 static tree
 370 combine_cond_expr_cond (gimple stmt, enum tree_code code, tree type,
 371                         tree op0, tree op1, bool invariant_only)
 372 {
 373   tree t;
 374
 375   gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
 376
 377   fold_defer_overflow_warnings ();
 378   t = fold_binary_loc (gimple_location (stmt), code, type, op0, op1);
 379   if (!t)
 380     {
 381       fold_undefer_overflow_warnings (false, NULL, 0);
 382       return NULL_TREE;
 383     }
 384
 385   /* Require that we got a boolean type out if we put one in.  */
 386   gcc_assert (TREE_CODE (TREE_TYPE (t)) == TREE_CODE (type));
 387
 388   /* Canonicalize the combined condition for use in a COND_EXPR.  */
 389   t = canonicalize_cond_expr_cond (t);
 390
 391   /* Bail out if we required an invariant but didn't get one.  */
 392   if (!t || (invariant_only && !is_gimple_min_invariant (t)))
 393     {
 394       fold_undefer_overflow_warnings (false, NULL, 0);
 395       return NULL_TREE;
 396     }
 397
 398   fold_undefer_overflow_warnings (!gimple_no_warning_p (stmt), stmt, 0);
 399
 400   return t;
 401 }
 402
 403 /* Combine the comparison OP0 CODE OP1 at LOC with the defining statements
 404    of its operand.  Return a new comparison tree or NULL_TREE if there
 405    were no simplifying combines.  */
 406
 407 static tree
 408 forward_propagate_into_comparison_1 (gimple stmt,
 409                                      enum tree_code code, tree type,
 410                                      tree op0, tree op1)
 411 {
 412   tree tmp = NULL_TREE;
 413   tree rhs0 = NULL_TREE, rhs1 = NULL_TREE;
 414   bool single_use0_p = false, single_use1_p = false;
 415
 416   /* For comparisons use the first operand, that is likely to
 417      simplify comparisons against constants.  */
 418   if (TREE_CODE (op0) == SSA_NAME)
 419     {
 420       gimple def_stmt = get_prop_source_stmt (op0, false, &single_use0_p);
 421       if (def_stmt && can_propagate_from (def_stmt))
 422         {
 423           rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
 424           tmp = combine_cond_expr_cond (stmt, code, type,
 425                                         rhs0, op1, !single_use0_p);
 426           if (tmp)
 427             return tmp;
 428         }
 429     }
 430
 431   /* If that wasn't successful, try the second operand.  */
 432   if (TREE_CODE (op1) == SSA_NAME)
 433     {
 434       gimple def_stmt = get_prop_source_stmt (op1, false, &single_use1_p);
 435       if (def_stmt && can_propagate_from (def_stmt))
 436         {
 437           rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt);
 438           tmp = combine_cond_expr_cond (stmt, code, type,
 439                                         op0, rhs1, !single_use1_p);
 440           if (tmp)
 441             return tmp;
 442         }
 443     }
 444
 445   /* If that wasn't successful either, try both operands.  */
 446   if (rhs0 != NULL_TREE
 447       && rhs1 != NULL_TREE)
 448     tmp = combine_cond_expr_cond (stmt, code, type,
 449                                   rhs0, rhs1,
 450                                   !(single_use0_p && single_use1_p));
 451
 452   return tmp;
 453 }
 454
 455 /* Propagate from the ssa name definition statements of the assignment
 456    from a comparison at *GSI into the conditional if that simplifies it.
 457    Returns 1 if the stmt was modified and 2 if the CFG needs cleanup,
 458    otherwise returns 0.  */
 459
 460 static int
 461 forward_propagate_into_comparison (gimple_stmt_iterator *gsi)
 462 {
 463   gimple stmt = gsi_stmt (*gsi);
 464   tree tmp;
 465   bool cfg_changed = false;
 466   tree type = TREE_TYPE (gimple_assign_lhs (stmt));
 467   tree rhs1 = gimple_assign_rhs1 (stmt);
 468   tree rhs2 = gimple_assign_rhs2 (stmt);
 469
 470   /* Combine the comparison with defining statements.  */
 471   tmp = forward_propagate_into_comparison_1 (stmt,
 472                                              gimple_assign_rhs_code (stmt),
 473                                              type, rhs1, rhs2);
 474   if (tmp && useless_type_conversion_p (type, TREE_TYPE (tmp)))
 475     {
 476       gimple_assign_set_rhs_from_tree (gsi, tmp);
 477       fold_stmt (gsi);
 478       update_stmt (gsi_stmt (*gsi));
 479
 480       if (TREE_CODE (rhs1) == SSA_NAME)
 481         cfg_changed |= remove_prop_source_from_use (rhs1);
 482       if (TREE_CODE (rhs2) == SSA_NAME)
 483         cfg_changed |= remove_prop_source_from_use (rhs2);
 484       return cfg_changed ? 2 : 1;
 485     }
 486
 487   return 0;
 488 }
 489
 490 /* Propagate from the ssa name definition statements of COND_EXPR
 491    in GIMPLE_COND statement STMT into the conditional if that simplifies it.
 492    Returns zero if no statement was changed, one if there were
 493    changes and two if cfg_cleanup needs to run.
 494
 495    This must be kept in sync with forward_propagate_into_cond.  */
 496
 497 static int
 498 forward_propagate_into_gimple_cond (gimple stmt)
 499 {
 500   tree tmp;
 501   enum tree_code code = gimple_cond_code (stmt);
 502   bool cfg_changed = false;
 503   tree rhs1 = gimple_cond_lhs (stmt);
 504   tree rhs2 = gimple_cond_rhs (stmt);
 505
 506   /* We can do tree combining on SSA_NAME and comparison expressions.  */
 507   if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison)
 508     return 0;
 509
 510   tmp = forward_propagate_into_comparison_1 (stmt, code,
 511                                              boolean_type_node,
 512                                              rhs1, rhs2);
 513   if (tmp)
 514     {
 515       if (dump_file && tmp)
 516         {
 517           fprintf (dump_file, "  Replaced '");
 518           print_gimple_expr (dump_file, stmt, 0, 0);
 519           fprintf (dump_file, "' with '");
 520           print_generic_expr (dump_file, tmp, 0);
 521           fprintf (dump_file, "'\n");
 522         }
 523
 524       gimple_cond_set_condition_from_tree (stmt, unshare_expr (tmp));
 525       update_stmt (stmt);
 526
 527       if (TREE_CODE (rhs1) == SSA_NAME)
 528         cfg_changed |= remove_prop_source_from_use (rhs1);
 529       if (TREE_CODE (rhs2) == SSA_NAME)
 530         cfg_changed |= remove_prop_source_from_use (rhs2);
 531       return (cfg_changed || is_gimple_min_invariant (tmp)) ? 2 : 1;
 532     }
 533
 534   /* Canonicalize _Bool == 0 and _Bool != 1 to _Bool != 0 by swapping edges.  */
 535   if ((TREE_CODE (TREE_TYPE (rhs1)) == BOOLEAN_TYPE
 536        || (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
 537            && TYPE_PRECISION (TREE_TYPE (rhs1)) == 1))
 538       && ((code == EQ_EXPR
 539            && integer_zerop (rhs2))
 540           || (code == NE_EXPR
 541               && integer_onep (rhs2))))
 542     {
 543       basic_block bb = gimple_bb (stmt);
 544       gimple_cond_set_code (stmt, NE_EXPR);
 545       gimple_cond_set_rhs (stmt, build_zero_cst (TREE_TYPE (rhs1)));
 546       EDGE_SUCC (bb, 0)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
 547       EDGE_SUCC (bb, 1)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
 548       return 1;
 549     }
 550
 551   return 0;
 552 }
 553
 554
 555 /* Propagate from the ssa name definition statements of COND_EXPR
 556    in the rhs of statement STMT into the conditional if that simplifies it.
 557    Returns true zero if the stmt was changed.  */
 558
 559 static bool
 560 forward_propagate_into_cond (gimple_stmt_iterator *gsi_p)
 561 {
 562   gimple stmt = gsi_stmt (*gsi_p);
 563   tree tmp = NULL_TREE;
 564   tree cond = gimple_assign_rhs1 (stmt);
 565   bool swap = false;
 566
 567   /* We can do tree combining on SSA_NAME and comparison expressions.  */
 568   if (COMPARISON_CLASS_P (cond))
 569     tmp = forward_propagate_into_comparison_1 (stmt, TREE_CODE (cond),
 570                                                boolean_type_node,
 571                                                TREE_OPERAND (cond, 0),
 572                                                TREE_OPERAND (cond, 1));
 573   else if (TREE_CODE (cond) == SSA_NAME)
 574     {
 575       enum tree_code code;
 576       tree name = cond;
 577       gimple def_stmt = get_prop_source_stmt (name, true, NULL);
 578       if (!def_stmt || !can_propagate_from (def_stmt))
 579         return 0;
 580
 581       code = gimple_assign_rhs_code (def_stmt);
 582       if (TREE_CODE_CLASS (code) == tcc_comparison)
 583         tmp = fold_build2_loc (gimple_location (def_stmt),
 584                                code,
 585                                boolean_type_node,
 586                                gimple_assign_rhs1 (def_stmt),
 587                                gimple_assign_rhs2 (def_stmt));
 588       else if ((code == BIT_NOT_EXPR
 589                 && TYPE_PRECISION (TREE_TYPE (cond)) == 1)
 590                || (code == BIT_XOR_EXPR
 591                    && integer_onep (gimple_assign_rhs2 (def_stmt))))
 592         {
 593           tmp = gimple_assign_rhs1 (def_stmt);
 594           swap = true;
 595         }
 596     }
 597
 598   if (tmp
 599       && is_gimple_condexpr (tmp))
 600     {
 601       if (dump_file && tmp)
 602         {
 603           fprintf (dump_file, "  Replaced '");
 604           print_generic_expr (dump_file, cond, 0);
 605           fprintf (dump_file, "' with '");
 606           print_generic_expr (dump_file, tmp, 0);
 607           fprintf (dump_file, "'\n");
 608         }
 609
 610       if (integer_onep (tmp))
 611         gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs2 (stmt));
 612       else if (integer_zerop (tmp))
 613         gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs3 (stmt));
 614       else
 615         {
 616           gimple_assign_set_rhs1 (stmt, unshare_expr (tmp));
 617           if (swap)
 618             {
 619               tree t = gimple_assign_rhs2 (stmt);
 620               gimple_assign_set_rhs2 (stmt, gimple_assign_rhs3 (stmt));
 621               gimple_assign_set_rhs3 (stmt, t);
 622             }
 623         }
 624       stmt = gsi_stmt (*gsi_p);
 625       update_stmt (stmt);
 626
 627       return true;
 628     }
 629
 630   return 0;
 631 }
 632
 633 /* Propagate from the ssa name definition statements of COND_EXPR
 634    values in the rhs of statement STMT into the conditional arms
 635    if that simplifies it.
 636    Returns true if the stmt was changed.  */
 637
 638 static bool
 639 combine_cond_exprs (gimple_stmt_iterator *gsi_p)
 640 {
 641   gimple stmt = gsi_stmt (*gsi_p);
 642   tree cond, val1, val2;
 643   bool changed = false;
 644
 645   cond = gimple_assign_rhs1 (stmt);
 646   val1 = gimple_assign_rhs2 (stmt);
 647   if (TREE_CODE (val1) == SSA_NAME)
 648     {
 649       gimple def_stmt = SSA_NAME_DEF_STMT (val1);
 650       if (is_gimple_assign (def_stmt)
 651           && gimple_assign_rhs_code (def_stmt) == gimple_assign_rhs_code (stmt)
 652           && operand_equal_p (gimple_assign_rhs1 (def_stmt), cond, 0))
 653         {
 654           val1 = unshare_expr (gimple_assign_rhs2 (def_stmt));
 655           gimple_assign_set_rhs2 (stmt, val1);
 656           changed = true;
 657         }
 658     }
 659   val2 = gimple_assign_rhs3 (stmt);
 660   if (TREE_CODE (val2) == SSA_NAME)
 661     {
 662       gimple def_stmt = SSA_NAME_DEF_STMT (val2);
 663       if (is_gimple_assign (def_stmt)
 664           && gimple_assign_rhs_code (def_stmt) == gimple_assign_rhs_code (stmt)
 665           && operand_equal_p (gimple_assign_rhs1 (def_stmt), cond, 0))
 666         {
 667           val2 = unshare_expr (gimple_assign_rhs3 (def_stmt));
 668           gimple_assign_set_rhs3 (stmt, val2);
 669           changed = true;
 670         }
 671     }
 672   if (operand_equal_p (val1, val2, 0))
 673     {
 674       gimple_assign_set_rhs_from_tree (gsi_p, val1);
 675       stmt = gsi_stmt (*gsi_p);
 676       changed = true;
 677     }
 678
 679   if (changed)
 680     update_stmt (stmt);
 681
 682   return changed;
 683 }
 684
 685 /* We've just substituted an ADDR_EXPR into stmt.  Update all the
 686    relevant data structures to match.  */
 687
 688 static void
 689 tidy_after_forward_propagate_addr (gimple stmt)
 690 {
 691   /* We may have turned a trapping insn into a non-trapping insn.  */
 692   if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
 693       && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
 694     cfg_changed = true;
 695
 696   if (TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR)
 697      recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
 698 }
 699
 700 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
 701    ADDR_EXPR <whatever>.
 702
 703    Try to forward propagate the ADDR_EXPR into the use USE_STMT.
 704    Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
 705    node or for recovery of array indexing from pointer arithmetic.
 706
 707    Return true if the propagation was successful (the propagation can
 708    be not totally successful, yet things may have been changed).  */
 709
 710 static bool
 711 forward_propagate_addr_expr_1 (tree name, tree def_rhs,
 712                                gimple_stmt_iterator *use_stmt_gsi,
 713                                bool single_use_p)
 714 {
 715   tree lhs, rhs, rhs2, array_ref;
 716   gimple use_stmt = gsi_stmt (*use_stmt_gsi);
 717   enum tree_code rhs_code;
 718   bool res = true;
 719
 720   gcc_assert (TREE_CODE (def_rhs) == ADDR_EXPR);
 721
 722   lhs = gimple_assign_lhs (use_stmt);
 723   rhs_code = gimple_assign_rhs_code (use_stmt);
 724   rhs = gimple_assign_rhs1 (use_stmt);
 725
 726   /* Trivial cases.  The use statement could be a trivial copy or a
 727      useless conversion.  Recurse to the uses of the lhs as copyprop does
 728      not copy through different variant pointers and FRE does not catch
 729      all useless conversions.  Treat the case of a single-use name and
 730      a conversion to def_rhs type separate, though.  */
 731   if (TREE_CODE (lhs) == SSA_NAME
 732       && ((rhs_code == SSA_NAME && rhs == name)
 733           || CONVERT_EXPR_CODE_P (rhs_code)))
 734     {
 735       /* Only recurse if we don't deal with a single use or we cannot
 736          do the propagation to the current statement.  In particular
 737          we can end up with a conversion needed for a non-invariant
 738          address which we cannot do in a single statement.  */
 739       if (!single_use_p
 740           || (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs))
 741               && (!is_gimple_min_invariant (def_rhs)
 742                   || (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
 743                       && POINTER_TYPE_P (TREE_TYPE (def_rhs))
 744                       && (TYPE_PRECISION (TREE_TYPE (lhs))
 745                           > TYPE_PRECISION (TREE_TYPE (def_rhs)))))))
 746         return forward_propagate_addr_expr (lhs, def_rhs);
 747
 748       gimple_assign_set_rhs1 (use_stmt, unshare_expr (def_rhs));
 749       if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
 750         gimple_assign_set_rhs_code (use_stmt, TREE_CODE (def_rhs));
 751       else
 752         gimple_assign_set_rhs_code (use_stmt, NOP_EXPR);
 753       return true;
 754     }
 755
 756   /* Propagate through constant pointer adjustments.  */
 757   if (TREE_CODE (lhs) == SSA_NAME
 758       && rhs_code == POINTER_PLUS_EXPR
 759       && rhs == name
 760       && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST)
 761     {
 762       tree new_def_rhs;
 763       /* As we come here with non-invariant addresses in def_rhs we need
 764          to make sure we can build a valid constant offsetted address
 765          for further propagation.  Simply rely on fold building that
 766          and check after the fact.  */
 767       new_def_rhs = fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (rhs)),
 768                                  def_rhs,
 769                                  fold_convert (ptr_type_node,
 770                                                gimple_assign_rhs2 (use_stmt)));
 771       if (TREE_CODE (new_def_rhs) == MEM_REF
 772           && !is_gimple_mem_ref_addr (TREE_OPERAND (new_def_rhs, 0)))
 773         return false;
 774       new_def_rhs = build_fold_addr_expr_with_type (new_def_rhs,
 775                                                     TREE_TYPE (rhs));
 776
 777       /* Recurse.  If we could propagate into all uses of lhs do not
 778          bother to replace into the current use but just pretend we did.  */
 779       if (TREE_CODE (new_def_rhs) == ADDR_EXPR
 780           && forward_propagate_addr_expr (lhs, new_def_rhs))
 781         return true;
 782
 783       if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (new_def_rhs)))
 784         gimple_assign_set_rhs_with_ops (use_stmt_gsi, TREE_CODE (new_def_rhs),
 785                                         new_def_rhs, NULL_TREE);
 786       else if (is_gimple_min_invariant (new_def_rhs))
 787         gimple_assign_set_rhs_with_ops (use_stmt_gsi, NOP_EXPR,
 788                                         new_def_rhs, NULL_TREE);
 789       else
 790         return false;
 791       gcc_assert (gsi_stmt (*use_stmt_gsi) == use_stmt);
 792       update_stmt (use_stmt);
 793       return true;
 794     }
 795
 796   /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
 797      ADDR_EXPR will not appear on the LHS.  */
 798   lhs = gimple_assign_lhs (use_stmt);
 799   while (handled_component_p (lhs))
 800     lhs = TREE_OPERAND (lhs, 0);
 801
 802   /* Now see if the LHS node is a MEM_REF using NAME.  If so,
 803      propagate the ADDR_EXPR into the use of NAME and fold the result.  */
 804   if (TREE_CODE (lhs) == MEM_REF
 805       && TREE_OPERAND (lhs, 0) == name)
 806     {
 807       tree def_rhs_base;
 808       HOST_WIDE_INT def_rhs_offset;
 809       /* If the address is invariant we can always fold it.  */
 810       if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
 811                                                          &def_rhs_offset)))
 812         {
 813           double_int off = mem_ref_offset (lhs);
 814           tree new_ptr;
 815           off = double_int_add (off,
 816                                 shwi_to_double_int (def_rhs_offset));
 817           if (TREE_CODE (def_rhs_base) == MEM_REF)
 818             {
 819               off = double_int_add (off, mem_ref_offset (def_rhs_base));
 820               new_ptr = TREE_OPERAND (def_rhs_base, 0);
 821             }
 822           else
 823             new_ptr = build_fold_addr_expr (def_rhs_base);
 824           TREE_OPERAND (lhs, 0) = new_ptr;
 825           TREE_OPERAND (lhs, 1)
 826             = double_int_to_tree (TREE_TYPE (TREE_OPERAND (lhs, 1)), off);
 827           tidy_after_forward_propagate_addr (use_stmt);
 828           /* Continue propagating into the RHS if this was not the only use.  */
 829           if (single_use_p)
 830             return true;
 831         }
 832       /* If the LHS is a plain dereference and the value type is the same as
 833          that of the pointed-to type of the address we can put the
 834          dereferenced address on the LHS preserving the original alias-type.  */
 835       else if (gimple_assign_lhs (use_stmt) == lhs
 836                && integer_zerop (TREE_OPERAND (lhs, 1))
 837                && useless_type_conversion_p
 838                     (TREE_TYPE (TREE_OPERAND (def_rhs, 0)),
 839                      TREE_TYPE (gimple_assign_rhs1 (use_stmt))))
 840         {
 841           tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
 842           tree new_offset, new_base, saved, new_lhs;
 843           while (handled_component_p (*def_rhs_basep))
 844             def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
 845           saved = *def_rhs_basep;
 846           if (TREE_CODE (*def_rhs_basep) == MEM_REF)
 847             {
 848               new_base = TREE_OPERAND (*def_rhs_basep, 0);
 849               new_offset = fold_convert (TREE_TYPE (TREE_OPERAND (lhs, 1)),
 850                                          TREE_OPERAND (*def_rhs_basep, 1));
 851             }
 852           else
 853             {
 854               new_base = build_fold_addr_expr (*def_rhs_basep);
 855               new_offset = TREE_OPERAND (lhs, 1);
 856             }
 857           *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
 858                                    new_base, new_offset);
 859           TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (lhs);
 860           TREE_SIDE_EFFECTS (*def_rhs_basep) = TREE_SIDE_EFFECTS (lhs);
 861           TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (lhs);
 862           new_lhs = unshare_expr (TREE_OPERAND (def_rhs, 0));
 863           gimple_assign_set_lhs (use_stmt, new_lhs);
 864           TREE_THIS_VOLATILE (new_lhs) = TREE_THIS_VOLATILE (lhs);
 865           TREE_SIDE_EFFECTS (new_lhs) = TREE_SIDE_EFFECTS (lhs);
 866           *def_rhs_basep = saved;
 867           tidy_after_forward_propagate_addr (use_stmt);
 868           /* Continue propagating into the RHS if this was not the
 869              only use.  */
 870           if (single_use_p)
 871             return true;
 872         }
 873       else
 874         /* We can have a struct assignment dereferencing our name twice.
 875            Note that we didn't propagate into the lhs to not falsely
 876            claim we did when propagating into the rhs.  */
 877         res = false;
 878     }
 879
 880   /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
 881      nodes from the RHS.  */
 882   rhs = gimple_assign_rhs1 (use_stmt);
 883   if (TREE_CODE (rhs) == ADDR_EXPR)
 884     rhs = TREE_OPERAND (rhs, 0);
 885   while (handled_component_p (rhs))
 886     rhs = TREE_OPERAND (rhs, 0);
 887
 888   /* Now see if the RHS node is a MEM_REF using NAME.  If so,
 889      propagate the ADDR_EXPR into the use of NAME and fold the result.  */
 890   if (TREE_CODE (rhs) == MEM_REF
 891       && TREE_OPERAND (rhs, 0) == name)
 892     {
 893       tree def_rhs_base;
 894       HOST_WIDE_INT def_rhs_offset;
 895       if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
 896                                                          &def_rhs_offset)))
 897         {
 898           double_int off = mem_ref_offset (rhs);
 899           tree new_ptr;
 900           off = double_int_add (off,
 901                                 shwi_to_double_int (def_rhs_offset));
 902           if (TREE_CODE (def_rhs_base) == MEM_REF)
 903             {
 904               off = double_int_add (off, mem_ref_offset (def_rhs_base));
 905               new_ptr = TREE_OPERAND (def_rhs_base, 0);
 906             }
 907           else
 908             new_ptr = build_fold_addr_expr (def_rhs_base);
 909           TREE_OPERAND (rhs, 0) = new_ptr;
 910           TREE_OPERAND (rhs, 1)
 911             = double_int_to_tree (TREE_TYPE (TREE_OPERAND (rhs, 1)), off);
 912           fold_stmt_inplace (use_stmt_gsi);
 913           tidy_after_forward_propagate_addr (use_stmt);
 914           return res;
 915         }
 916       /* If the RHS is a plain dereference and the value type is the same as
 917          that of the pointed-to type of the address we can put the
 918          dereferenced address on the RHS preserving the original alias-type.  */
 919       else if (gimple_assign_rhs1 (use_stmt) == rhs
 920                && integer_zerop (TREE_OPERAND (rhs, 1))
 921                && useless_type_conversion_p
 922                     (TREE_TYPE (gimple_assign_lhs (use_stmt)),
 923                      TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
 924         {
 925           tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
 926           tree new_offset, new_base, saved, new_rhs;
 927           while (handled_component_p (*def_rhs_basep))
 928             def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
 929           saved = *def_rhs_basep;
 930           if (TREE_CODE (*def_rhs_basep) == MEM_REF)
 931             {
 932               new_base = TREE_OPERAND (*def_rhs_basep, 0);
 933               new_offset = fold_convert (TREE_TYPE (TREE_OPERAND (rhs, 1)),
 934                                          TREE_OPERAND (*def_rhs_basep, 1));
 935             }
 936           else
 937             {
 938               new_base = build_fold_addr_expr (*def_rhs_basep);
 939               new_offset = TREE_OPERAND (rhs, 1);
 940             }
 941           *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
 942                                    new_base, new_offset);
 943           TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (rhs);
 944           TREE_SIDE_EFFECTS (*def_rhs_basep) = TREE_SIDE_EFFECTS (rhs);
 945           TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (rhs);
 946           new_rhs = unshare_expr (TREE_OPERAND (def_rhs, 0));
 947           gimple_assign_set_rhs1 (use_stmt, new_rhs);
 948           TREE_THIS_VOLATILE (new_rhs) = TREE_THIS_VOLATILE (rhs);
 949           TREE_SIDE_EFFECTS (new_rhs) = TREE_SIDE_EFFECTS (rhs);
 950           *def_rhs_basep = saved;
 951           fold_stmt_inplace (use_stmt_gsi);
 952           tidy_after_forward_propagate_addr (use_stmt);
 953           return res;
 954         }
 955     }
 956
 957   /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
 958      is nothing to do. */
 959   if (gimple_assign_rhs_code (use_stmt) != POINTER_PLUS_EXPR
 960       || gimple_assign_rhs1 (use_stmt) != name)
 961     return false;
 962
 963   /* The remaining cases are all for turning pointer arithmetic into
 964      array indexing.  They only apply when we have the address of
 965      element zero in an array.  If that is not the case then there
 966      is nothing to do.  */
 967   array_ref = TREE_OPERAND (def_rhs, 0);
 968   if ((TREE_CODE (array_ref) != ARRAY_REF
 969        || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
 970        || TREE_CODE (TREE_OPERAND (array_ref, 1)) != INTEGER_CST)
 971       && TREE_CODE (TREE_TYPE (array_ref)) != ARRAY_TYPE)
 972     return false;
 973
 974   rhs2 = gimple_assign_rhs2 (use_stmt);
 975   /* Optimize &x[C1] p+ C2 to  &x p+ C3 with C3 = C1 * element_size + C2.  */
 976   if (TREE_CODE (rhs2) == INTEGER_CST)
 977     {
 978       tree new_rhs = build1_loc (gimple_location (use_stmt),
 979                                  ADDR_EXPR, TREE_TYPE (def_rhs),
 980                                  fold_build2 (MEM_REF,
 981                                               TREE_TYPE (TREE_TYPE (def_rhs)),
 982                                               unshare_expr (def_rhs),
 983                                               fold_convert (ptr_type_node,
 984                                                             rhs2)));
 985       gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
 986       use_stmt = gsi_stmt (*use_stmt_gsi);
 987       update_stmt (use_stmt);
 988       tidy_after_forward_propagate_addr (use_stmt);
 989       return true;
 990     }
 991
 992   return false;
 993 }
 994
 995 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
 996
 997    Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
 998    Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
 999    node or for recovery of array indexing from pointer arithmetic.
1000    Returns true, if all uses have been propagated into.  */
1001
1002 static bool
1003 forward_propagate_addr_expr (tree name, tree rhs)
1004 {
1005   int stmt_loop_depth = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_depth;
1006   imm_use_iterator iter;
1007   gimple use_stmt;
1008   bool all = true;
1009   bool single_use_p = has_single_use (name);
1010
1011   FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
1012     {
1013       bool result;
1014       tree use_rhs;
1015
1016       /* If the use is not in a simple assignment statement, then
1017          there is nothing we can do.  */
1018       if (gimple_code (use_stmt) != GIMPLE_ASSIGN)
1019         {
1020           if (!is_gimple_debug (use_stmt))
1021             all = false;
1022           continue;
1023         }
1024
1025       /* If the use is in a deeper loop nest, then we do not want
1026          to propagate non-invariant ADDR_EXPRs into the loop as that
1027          is likely adding expression evaluations into the loop.  */
1028       if (gimple_bb (use_stmt)->loop_depth > stmt_loop_depth
1029           && !is_gimple_min_invariant (rhs))
1030         {
1031           all = false;
1032           continue;
1033         }
1034
1035       {
1036         gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1037         result = forward_propagate_addr_expr_1 (name, rhs, &gsi,
1038                                                 single_use_p);
1039         /* If the use has moved to a different statement adjust
1040            the update machinery for the old statement too.  */
1041         if (use_stmt != gsi_stmt (gsi))
1042           {
1043             update_stmt (use_stmt);
1044             use_stmt = gsi_stmt (gsi);
1045           }
1046
1047         update_stmt (use_stmt);
1048       }
1049       all &= result;
1050
1051       /* Remove intermediate now unused copy and conversion chains.  */
1052       use_rhs = gimple_assign_rhs1 (use_stmt);
1053       if (result
1054           && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
1055           && TREE_CODE (use_rhs) == SSA_NAME
1056           && has_zero_uses (gimple_assign_lhs (use_stmt)))
1057         {
1058           gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1059           release_defs (use_stmt);
1060           gsi_remove (&gsi, true);
1061         }
1062     }
1063
1064   return all && has_zero_uses (name);
1065 }
1066
1067
1068 /* Forward propagate the comparison defined in *DEFGSI like
1069    cond_1 = x CMP y to uses of the form
1070      a_1 = (T')cond_1
1071      a_1 = !cond_1
1072      a_1 = cond_1 != 0
1073    Returns true if stmt is now unused.  Advance DEFGSI to the next
1074    statement.  */
1075
1076 static bool
1077 forward_propagate_comparison (gimple_stmt_iterator *defgsi)
1078 {
1079   gimple stmt = gsi_stmt (*defgsi);
1080   tree name = gimple_assign_lhs (stmt);
1081   gimple use_stmt;
1082   tree tmp = NULL_TREE;
1083   gimple_stmt_iterator gsi;
1084   enum tree_code code;
1085   tree lhs;
1086
1087   /* Don't propagate ssa names that occur in abnormal phis.  */
1088   if ((TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
1089        && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
1090       || (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME
1091         && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs2 (stmt))))
1092     goto bailout;
1093
1094   /* Do not un-cse comparisons.  But propagate through copies.  */
1095   use_stmt = get_prop_dest_stmt (name, &name);
1096   if (!use_stmt
1097       || !is_gimple_assign (use_stmt))
1098     goto bailout;
1099
1100   code = gimple_assign_rhs_code (use_stmt);
1101   lhs = gimple_assign_lhs (use_stmt);
1102   if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
1103     goto bailout;
1104
1105   /* We can propagate the condition into a statement that
1106      computes the logical negation of the comparison result.  */
1107   if ((code == BIT_NOT_EXPR
1108        && TYPE_PRECISION (TREE_TYPE (lhs)) == 1)
1109       || (code == BIT_XOR_EXPR
1110           && integer_onep (gimple_assign_rhs2 (use_stmt))))
1111     {
1112       tree type = TREE_TYPE (gimple_assign_rhs1 (stmt));
1113       bool nans = HONOR_NANS (TYPE_MODE (type));
1114       enum tree_code inv_code;
1115       inv_code = invert_tree_comparison (gimple_assign_rhs_code (stmt), nans);
1116       if (inv_code == ERROR_MARK)
1117         goto bailout;
1118
1119       tmp = build2 (inv_code, TREE_TYPE (lhs), gimple_assign_rhs1 (stmt),
1120                     gimple_assign_rhs2 (stmt));
1121     }
1122   else
1123     goto bailout;
1124
1125   gsi = gsi_for_stmt (use_stmt);
1126   gimple_assign_set_rhs_from_tree (&gsi, unshare_expr (tmp));
1127   use_stmt = gsi_stmt (gsi);
1128   update_stmt (use_stmt);
1129
1130   if (dump_file && (dump_flags & TDF_DETAILS))
1131     {
1132       fprintf (dump_file, "  Replaced '");
1133       print_gimple_expr (dump_file, stmt, 0, dump_flags);
1134       fprintf (dump_file, "' with '");
1135       print_gimple_expr (dump_file, use_stmt, 0, dump_flags);
1136       fprintf (dump_file, "'\n");
1137     }
1138
1139   /* When we remove stmt now the iterator defgsi goes off it's current
1140      sequence, hence advance it now.  */
1141   gsi_next (defgsi);
1142
1143   /* Remove defining statements.  */
1144   return remove_prop_source_from_use (name);
1145
1146 bailout:
1147   gsi_next (defgsi);
1148   return false;
1149 }
1150
1151
1152 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
1153    If so, we can change STMT into lhs = y which can later be copy
1154    propagated.  Similarly for negation.
1155
1156    This could trivially be formulated as a forward propagation
1157    to immediate uses.  However, we already had an implementation
1158    from DOM which used backward propagation via the use-def links.
1159
1160    It turns out that backward propagation is actually faster as
1161    there's less work to do for each NOT/NEG expression we find.
1162    Backwards propagation needs to look at the statement in a single
1163    backlink.  Forward propagation needs to look at potentially more
1164    than one forward link.
1165
1166    Returns true when the statement was changed.  */
1167
1168 static bool
1169 simplify_not_neg_expr (gimple_stmt_iterator *gsi_p)
1170 {
1171   gimple stmt = gsi_stmt (*gsi_p);
1172   tree rhs = gimple_assign_rhs1 (stmt);
1173   gimple rhs_def_stmt = SSA_NAME_DEF_STMT (rhs);
1174
1175   /* See if the RHS_DEF_STMT has the same form as our statement.  */
1176   if (is_gimple_assign (rhs_def_stmt)
1177       && gimple_assign_rhs_code (rhs_def_stmt) == gimple_assign_rhs_code (stmt))
1178     {
1179       tree rhs_def_operand = gimple_assign_rhs1 (rhs_def_stmt);
1180
1181       /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME.  */
1182       if (TREE_CODE (rhs_def_operand) == SSA_NAME
1183           && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand))
1184         {
1185           gimple_assign_set_rhs_from_tree (gsi_p, rhs_def_operand);
1186           stmt = gsi_stmt (*gsi_p);
1187           update_stmt (stmt);
1188           return true;
1189         }
1190     }
1191
1192   return false;
1193 }
1194
1195 /* Helper function for simplify_gimple_switch.  Remove case labels that
1196    have values outside the range of the new type.  */
1197
1198 static void
1199 simplify_gimple_switch_label_vec (gimple stmt, tree index_type)
1200 {
1201   unsigned int branch_num = gimple_switch_num_labels (stmt);
1202   VEC(tree, heap) *labels = VEC_alloc (tree, heap, branch_num);
1203   unsigned int i, len;
1204
1205   /* Collect the existing case labels in a VEC, and preprocess it as if
1206      we are gimplifying a GENERIC SWITCH_EXPR.  */
1207   for (i = 1; i < branch_num; i++)
1208     VEC_quick_push (tree, labels, gimple_switch_label (stmt, i));
1209   preprocess_case_label_vec_for_gimple (labels, index_type, NULL);
1210
1211   /* If any labels were removed, replace the existing case labels
1212      in the GIMPLE_SWITCH statement with the correct ones.
1213      Note that the type updates were done in-place on the case labels,
1214      so we only have to replace the case labels in the GIMPLE_SWITCH
1215      if the number of labels changed.  */
1216   len = VEC_length (tree, labels);
1217   if (len < branch_num - 1)
1218     {
1219       bitmap target_blocks;
1220       edge_iterator ei;
1221       edge e;
1222
1223       /* Corner case: *all* case labels have been removed as being
1224          out-of-range for INDEX_TYPE.  Push one label and let the
1225          CFG cleanups deal with this further.  */
1226       if (len == 0)
1227         {
1228           tree label, elt;
1229
1230           label = CASE_LABEL (gimple_switch_default_label (stmt));
1231           elt = build_case_label (build_int_cst (index_type, 0), NULL, label);
1232           VEC_quick_push (tree, labels, elt);
1233           len = 1;
1234         }
1235
1236       for (i = 0; i < VEC_length (tree, labels); i++)
1237         gimple_switch_set_label (stmt, i + 1, VEC_index (tree, labels, i));
1238       for (i++ ; i < branch_num; i++)
1239         gimple_switch_set_label (stmt, i, NULL_TREE);
1240       gimple_switch_set_num_labels (stmt, len + 1);
1241
1242       /* Cleanup any edges that are now dead.  */
1243       target_blocks = BITMAP_ALLOC (NULL);
1244       for (i = 0; i < gimple_switch_num_labels (stmt); i++)
1245         {
1246           tree elt = gimple_switch_label (stmt, i);
1247           basic_block target = label_to_block (CASE_LABEL (elt));
1248           bitmap_set_bit (target_blocks, target->index);
1249         }
1250       for (ei = ei_start (gimple_bb (stmt)->succs); (e = ei_safe_edge (ei)); )
1251         {
1252           if (! bitmap_bit_p (target_blocks, e->dest->index))
1253             {
1254               remove_edge (e);
1255               cfg_changed = true;
1256               free_dominance_info (CDI_DOMINATORS);
1257             }
1258           else
1259             ei_next (&ei);
1260         }
1261       BITMAP_FREE (target_blocks);
1262     }
1263
1264   VEC_free (tree, heap, labels);
1265 }
1266
1267 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1268    the condition which we may be able to optimize better.  */
1269
1270 static bool
1271 simplify_gimple_switch (gimple stmt)
1272 {
1273   tree cond = gimple_switch_index (stmt);
1274   tree def, to, ti;
1275   gimple def_stmt;
1276
1277   /* The optimization that we really care about is removing unnecessary
1278      casts.  That will let us do much better in propagating the inferred
1279      constant at the switch target.  */
1280   if (TREE_CODE (cond) == SSA_NAME)
1281     {
1282       def_stmt = SSA_NAME_DEF_STMT (cond);
1283       if (is_gimple_assign (def_stmt))
1284         {
1285           if (gimple_assign_rhs_code (def_stmt) == NOP_EXPR)
1286             {
1287               int need_precision;
1288               bool fail;
1289
1290               def = gimple_assign_rhs1 (def_stmt);
1291
1292               to = TREE_TYPE (cond);
1293               ti = TREE_TYPE (def);
1294
1295               /* If we have an extension that preserves value, then we
1296                  can copy the source value into the switch.  */
1297
1298               need_precision = TYPE_PRECISION (ti);
1299               fail = false;
1300               if (! INTEGRAL_TYPE_P (ti))
1301                 fail = true;
1302               else if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti))
1303                 fail = true;
1304               else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti))
1305                 need_precision += 1;
1306               if (TYPE_PRECISION (to) < need_precision)
1307                 fail = true;
1308
1309               if (!fail)
1310                 {
1311                   gimple_switch_set_index (stmt, def);
1312                   simplify_gimple_switch_label_vec (stmt, ti);
1313                   update_stmt (stmt);
1314                   return true;
1315                 }
1316             }
1317         }
1318     }
1319
1320   return false;
1321 }
1322
1323 /* For pointers p2 and p1 return p2 - p1 if the
1324    difference is known and constant, otherwise return NULL.  */
1325
1326 static tree
1327 constant_pointer_difference (tree p1, tree p2)
1328 {
1329   int i, j;
1330 #define CPD_ITERATIONS 5
1331   tree exps[2][CPD_ITERATIONS];
1332   tree offs[2][CPD_ITERATIONS];
1333   int cnt[2];
1334
1335   for (i = 0; i < 2; i++)
1336     {
1337       tree p = i ? p1 : p2;
1338       tree off = size_zero_node;
1339       gimple stmt;
1340       enum tree_code code;
1341
1342       /* For each of p1 and p2 we need to iterate at least
1343          twice, to handle ADDR_EXPR directly in p1/p2,
1344          SSA_NAME with ADDR_EXPR or POINTER_PLUS_EXPR etc.
1345          on definition's stmt RHS.  Iterate a few extra times.  */
1346       j = 0;
1347       do
1348         {
1349           if (!POINTER_TYPE_P (TREE_TYPE (p)))
1350             break;
1351           if (TREE_CODE (p) == ADDR_EXPR)
1352             {
1353               tree q = TREE_OPERAND (p, 0);
1354               HOST_WIDE_INT offset;
1355               tree base = get_addr_base_and_unit_offset (q, &offset);
1356               if (base)
1357                 {
1358                   q = base;
1359                   if (offset)
1360                     off = size_binop (PLUS_EXPR, off, size_int (offset));
1361                 }
1362               if (TREE_CODE (q) == MEM_REF
1363                   && TREE_CODE (TREE_OPERAND (q, 0)) == SSA_NAME)
1364                 {
1365                   p = TREE_OPERAND (q, 0);
1366                   off = size_binop (PLUS_EXPR, off,
1367                                     double_int_to_tree (sizetype,
1368                                                         mem_ref_offset (q)));
1369                 }
1370               else
1371                 {
1372                   exps[i][j] = q;
1373                   offs[i][j++] = off;
1374                   break;
1375                 }
1376             }
1377           if (TREE_CODE (p) != SSA_NAME)
1378             break;
1379           exps[i][j] = p;
1380           offs[i][j++] = off;
1381           if (j == CPD_ITERATIONS)
1382             break;
1383           stmt = SSA_NAME_DEF_STMT (p);
1384           if (!is_gimple_assign (stmt) || gimple_assign_lhs (stmt) != p)
1385             break;
1386           code = gimple_assign_rhs_code (stmt);
1387           if (code == POINTER_PLUS_EXPR)
1388             {
1389               if (TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)
1390                 break;
1391               off = size_binop (PLUS_EXPR, off, gimple_assign_rhs2 (stmt));
1392               p = gimple_assign_rhs1 (stmt);
1393             }
1394           else if (code == ADDR_EXPR || code == NOP_EXPR)
1395             p = gimple_assign_rhs1 (stmt);
1396           else
1397             break;
1398         }
1399       while (1);
1400       cnt[i] = j;
1401     }
1402
1403   for (i = 0; i < cnt[0]; i++)
1404     for (j = 0; j < cnt[1]; j++)
1405       if (exps[0][i] == exps[1][j])
1406         return size_binop (MINUS_EXPR, offs[0][i], offs[1][j]);
1407
1408   return NULL_TREE;
1409 }
1410
1411 /* *GSI_P is a GIMPLE_CALL to a builtin function.
1412    Optimize
1413    memcpy (p, "abcd", 4);
1414    memset (p + 4, ' ', 3);
1415    into
1416    memcpy (p, "abcd   ", 7);
1417    call if the latter can be stored by pieces during expansion.  */
1418
1419 static bool
1420 simplify_builtin_call (gimple_stmt_iterator *gsi_p, tree callee2)
1421 {
1422   gimple stmt1, stmt2 = gsi_stmt (*gsi_p);
1423   tree vuse = gimple_vuse (stmt2);
1424   if (vuse == NULL)
1425     return false;
1426   stmt1 = SSA_NAME_DEF_STMT (vuse);
1427
1428   switch (DECL_FUNCTION_CODE (callee2))
1429     {
1430     case BUILT_IN_MEMSET:
1431       if (gimple_call_num_args (stmt2) != 3
1432           || gimple_call_lhs (stmt2)
1433           || CHAR_BIT != 8
1434           || BITS_PER_UNIT != 8)
1435         break;
1436       else
1437         {
1438           tree callee1;
1439           tree ptr1, src1, str1, off1, len1, lhs1;
1440           tree ptr2 = gimple_call_arg (stmt2, 0);
1441           tree val2 = gimple_call_arg (stmt2, 1);
1442           tree len2 = gimple_call_arg (stmt2, 2);
1443           tree diff, vdef, new_str_cst;
1444           gimple use_stmt;
1445           unsigned int ptr1_align;
1446           unsigned HOST_WIDE_INT src_len;
1447           char *src_buf;
1448           use_operand_p use_p;
1449
1450           if (!host_integerp (val2, 0)
1451               || !host_integerp (len2, 1))
1452             break;
1453           if (is_gimple_call (stmt1))
1454             {
1455               /* If first stmt is a call, it needs to be memcpy
1456                  or mempcpy, with string literal as second argument and
1457                  constant length.  */
1458               callee1 = gimple_call_fndecl (stmt1);
1459               if (callee1 == NULL_TREE
1460                   || DECL_BUILT_IN_CLASS (callee1) != BUILT_IN_NORMAL
1461                   || gimple_call_num_args (stmt1) != 3)
1462                 break;
1463               if (DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMCPY
1464                   && DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMPCPY)
1465                 break;
1466               ptr1 = gimple_call_arg (stmt1, 0);
1467               src1 = gimple_call_arg (stmt1, 1);
1468               len1 = gimple_call_arg (stmt1, 2);
1469               lhs1 = gimple_call_lhs (stmt1);
1470               if (!host_integerp (len1, 1))
1471                 break;
1472               str1 = string_constant (src1, &off1);
1473               if (str1 == NULL_TREE)
1474                 break;
1475               if (!host_integerp (off1, 1)
1476                   || compare_tree_int (off1, TREE_STRING_LENGTH (str1) - 1) > 0
1477                   || compare_tree_int (len1, TREE_STRING_LENGTH (str1)
1478                                              - tree_low_cst (off1, 1)) > 0
1479                   || TREE_CODE (TREE_TYPE (str1)) != ARRAY_TYPE
1480                   || TYPE_MODE (TREE_TYPE (TREE_TYPE (str1)))
1481                      != TYPE_MODE (char_type_node))
1482                 break;
1483             }
1484           else if (gimple_assign_single_p (stmt1))
1485             {
1486               /* Otherwise look for length 1 memcpy optimized into
1487                  assignment.  */
1488               ptr1 = gimple_assign_lhs (stmt1);
1489               src1 = gimple_assign_rhs1 (stmt1);
1490               if (TREE_CODE (ptr1) != MEM_REF
1491                   || TYPE_MODE (TREE_TYPE (ptr1)) != TYPE_MODE (char_type_node)
1492                   || !host_integerp (src1, 0))
1493                 break;
1494               ptr1 = build_fold_addr_expr (ptr1);
1495               callee1 = NULL_TREE;
1496               len1 = size_one_node;
1497               lhs1 = NULL_TREE;
1498               off1 = size_zero_node;
1499               str1 = NULL_TREE;
1500             }
1501           else
1502             break;
1503
1504           diff = constant_pointer_difference (ptr1, ptr2);
1505           if (diff == NULL && lhs1 != NULL)
1506             {
1507               diff = constant_pointer_difference (lhs1, ptr2);
1508               if (DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1509                   && diff != NULL)
1510                 diff = size_binop (PLUS_EXPR, diff,
1511                                    fold_convert (sizetype, len1));
1512             }
1513           /* If the difference between the second and first destination pointer
1514              is not constant, or is bigger than memcpy length, bail out.  */
1515           if (diff == NULL
1516               || !host_integerp (diff, 1)
1517               || tree_int_cst_lt (len1, diff))
1518             break;
1519
1520           /* Use maximum of difference plus memset length and memcpy length
1521              as the new memcpy length, if it is too big, bail out.  */
1522           src_len = tree_low_cst (diff, 1);
1523           src_len += tree_low_cst (len2, 1);
1524           if (src_len < (unsigned HOST_WIDE_INT) tree_low_cst (len1, 1))
1525             src_len = tree_low_cst (len1, 1);
1526           if (src_len > 1024)
1527             break;
1528
1529           /* If mempcpy value is used elsewhere, bail out, as mempcpy
1530              with bigger length will return different result.  */
1531           if (lhs1 != NULL_TREE
1532               && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1533               && (TREE_CODE (lhs1) != SSA_NAME
1534                   || !single_imm_use (lhs1, &use_p, &use_stmt)
1535                   || use_stmt != stmt2))
1536             break;
1537
1538           /* If anything reads memory in between memcpy and memset
1539              call, the modified memcpy call might change it.  */
1540           vdef = gimple_vdef (stmt1);
1541           if (vdef != NULL
1542               && (!single_imm_use (vdef, &use_p, &use_stmt)
1543                   || use_stmt != stmt2))
1544             break;
1545
1546           ptr1_align = get_pointer_alignment (ptr1);
1547           /* Construct the new source string literal.  */
1548           src_buf = XALLOCAVEC (char, src_len + 1);
1549           if (callee1)
1550             memcpy (src_buf,
1551                     TREE_STRING_POINTER (str1) + tree_low_cst (off1, 1),
1552                     tree_low_cst (len1, 1));
1553           else
1554             src_buf[0] = tree_low_cst (src1, 0);
1555           memset (src_buf + tree_low_cst (diff, 1),
1556                   tree_low_cst (val2, 1), tree_low_cst (len2, 1));
1557           src_buf[src_len] = '\0';
1558           /* Neither builtin_strncpy_read_str nor builtin_memcpy_read_str
1559              handle embedded '\0's.  */
1560           if (strlen (src_buf) != src_len)
1561             break;
1562           rtl_profile_for_bb (gimple_bb (stmt2));
1563           /* If the new memcpy wouldn't be emitted by storing the literal
1564              by pieces, this optimization might enlarge .rodata too much,
1565              as commonly used string literals couldn't be shared any
1566              longer.  */
1567           if (!can_store_by_pieces (src_len,
1568                                     builtin_strncpy_read_str,
1569                                     src_buf, ptr1_align, false))
1570             break;
1571
1572           new_str_cst = build_string_literal (src_len, src_buf);
1573           if (callee1)
1574             {
1575               /* If STMT1 is a mem{,p}cpy call, adjust it and remove
1576                  memset call.  */
1577               if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1578                 gimple_call_set_lhs (stmt1, NULL_TREE);
1579               gimple_call_set_arg (stmt1, 1, new_str_cst);
1580               gimple_call_set_arg (stmt1, 2,
1581                                    build_int_cst (TREE_TYPE (len1), src_len));
1582               update_stmt (stmt1);
1583               unlink_stmt_vdef (stmt2);
1584               gsi_remove (gsi_p, true);
1585               release_defs (stmt2);
1586               if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1587                 release_ssa_name (lhs1);
1588               return true;
1589             }
1590           else
1591             {
1592               /* Otherwise, if STMT1 is length 1 memcpy optimized into
1593                  assignment, remove STMT1 and change memset call into
1594                  memcpy call.  */
1595               gimple_stmt_iterator gsi = gsi_for_stmt (stmt1);
1596
1597               if (!is_gimple_val (ptr1))
1598                 ptr1 = force_gimple_operand_gsi (gsi_p, ptr1, true, NULL_TREE,
1599                                                  true, GSI_SAME_STMT);
1600               gimple_call_set_fndecl (stmt2,
1601                                       builtin_decl_explicit (BUILT_IN_MEMCPY));
1602               gimple_call_set_arg (stmt2, 0, ptr1);
1603               gimple_call_set_arg (stmt2, 1, new_str_cst);
1604               gimple_call_set_arg (stmt2, 2,
1605                                    build_int_cst (TREE_TYPE (len2), src_len));
1606               unlink_stmt_vdef (stmt1);
1607               gsi_remove (&gsi, true);
1608               release_defs (stmt1);
1609               update_stmt (stmt2);
1610               return false;
1611             }
1612         }
1613       break;
1614     default:
1615       break;
1616     }
1617   return false;
1618 }
1619
1620 /* Checks if expression has type of one-bit precision, or is a known
1621    truth-valued expression.  */
1622 static bool
1623 truth_valued_ssa_name (tree name)
1624 {
1625   gimple def;
1626   tree type = TREE_TYPE (name);
1627
1628   if (!INTEGRAL_TYPE_P (type))
1629     return false;
1630   /* Don't check here for BOOLEAN_TYPE as the precision isn't
1631      necessarily one and so ~X is not equal to !X.  */
1632   if (TYPE_PRECISION (type) == 1)
1633     return true;
1634   def = SSA_NAME_DEF_STMT (name);
1635   if (is_gimple_assign (def))
1636     return truth_value_p (gimple_assign_rhs_code (def));
1637   return false;
1638 }
1639
1640 /* Helper routine for simplify_bitwise_binary_1 function.
1641    Return for the SSA name NAME the expression X if it mets condition
1642    NAME = !X. Otherwise return NULL_TREE.
1643    Detected patterns for NAME = !X are:
1644      !X and X == 0 for X with integral type.
1645      X ^ 1, X != 1,or ~X for X with integral type with precision of one.  */
1646 static tree
1647 lookup_logical_inverted_value (tree name)
1648 {
1649   tree op1, op2;
1650   enum tree_code code;
1651   gimple def;
1652
1653   /* If name has none-intergal type, or isn't a SSA_NAME, then
1654      return.  */
1655   if (TREE_CODE (name) != SSA_NAME
1656       || !INTEGRAL_TYPE_P (TREE_TYPE (name)))
1657     return NULL_TREE;
1658   def = SSA_NAME_DEF_STMT (name);
1659   if (!is_gimple_assign (def))
1660     return NULL_TREE;
1661
1662   code = gimple_assign_rhs_code (def);
1663   op1 = gimple_assign_rhs1 (def);
1664   op2 = NULL_TREE;
1665
1666   /* Get for EQ_EXPR or BIT_XOR_EXPR operation the second operand.
1667      If CODE isn't an EQ_EXPR, BIT_XOR_EXPR, or BIT_NOT_EXPR, then return.  */
1668   if (code == EQ_EXPR || code == NE_EXPR
1669       || code == BIT_XOR_EXPR)
1670     op2 = gimple_assign_rhs2 (def);
1671
1672   switch (code)
1673     {
1674     case BIT_NOT_EXPR:
1675       if (truth_valued_ssa_name (name))
1676         return op1;
1677       break;
1678     case EQ_EXPR:
1679       /* Check if we have X == 0 and X has an integral type.  */
1680       if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
1681         break;
1682       if (integer_zerop (op2))
1683         return op1;
1684       break;
1685     case NE_EXPR:
1686       /* Check if we have X != 1 and X is a truth-valued.  */
1687       if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
1688         break;
1689       if (integer_onep (op2) && truth_valued_ssa_name (op1))
1690         return op1;
1691       break;
1692     case BIT_XOR_EXPR:
1693       /* Check if we have X ^ 1 and X is truth valued.  */
1694       if (integer_onep (op2) && truth_valued_ssa_name (op1))
1695         return op1;
1696       break;
1697     default:
1698       break;
1699     }
1700
1701   return NULL_TREE;
1702 }
1703
1704 /* Optimize ARG1 CODE ARG2 to a constant for bitwise binary
1705    operations CODE, if one operand has the logically inverted
1706    value of the other.  */
1707 static tree
1708 simplify_bitwise_binary_1 (enum tree_code code, tree type,
1709                            tree arg1, tree arg2)
1710 {
1711   tree anot;
1712
1713   /* If CODE isn't a bitwise binary operation, return NULL_TREE.  */
1714   if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR
1715       && code != BIT_XOR_EXPR)
1716     return NULL_TREE;
1717
1718   /* First check if operands ARG1 and ARG2 are equal.  If so
1719      return NULL_TREE as this optimization is handled fold_stmt.  */
1720   if (arg1 == arg2)
1721     return NULL_TREE;
1722   /* See if we have in arguments logical-not patterns.  */
1723   if (((anot = lookup_logical_inverted_value (arg1)) == NULL_TREE
1724        || anot != arg2)
1725       && ((anot = lookup_logical_inverted_value (arg2)) == NULL_TREE
1726           || anot != arg1))
1727     return NULL_TREE;
1728
1729   /* X & !X -> 0.  */
1730   if (code == BIT_AND_EXPR)
1731     return fold_convert (type, integer_zero_node);
1732   /* X | !X -> 1 and X ^ !X -> 1, if X is truth-valued.  */
1733   if (truth_valued_ssa_name (anot))
1734     return fold_convert (type, integer_one_node);
1735
1736   /* ??? Otherwise result is (X != 0 ? X : 1).  not handled.  */
1737   return NULL_TREE;
1738 }
1739
1740 /* Given a ssa_name in NAME see if it was defined by an assignment and
1741    set CODE to be the code and ARG1 to the first operand on the rhs and ARG2
1742    to the second operand on the rhs. */
1743
1744 static inline void
1745 defcodefor_name (tree name, enum tree_code *code, tree *arg1, tree *arg2)
1746 {
1747   gimple def;
1748   enum tree_code code1;
1749   tree arg11;
1750   tree arg21;
1751   tree arg31;
1752   enum gimple_rhs_class grhs_class;
1753
1754   code1 = TREE_CODE (name);
1755   arg11 = name;
1756   arg21 = NULL_TREE;
1757   grhs_class = get_gimple_rhs_class (code1);
1758
1759   if (code1 == SSA_NAME)
1760     {
1761       def = SSA_NAME_DEF_STMT (name);
1762
1763       if (def && is_gimple_assign (def)
1764           && can_propagate_from (def))
1765         {
1766           code1 = gimple_assign_rhs_code (def);
1767           arg11 = gimple_assign_rhs1 (def);
1768           arg21 = gimple_assign_rhs2 (def);
1769           arg31 = gimple_assign_rhs2 (def);
1770         }
1771     }
1772   else if (grhs_class == GIMPLE_TERNARY_RHS
1773            || GIMPLE_BINARY_RHS
1774            || GIMPLE_UNARY_RHS
1775            || GIMPLE_SINGLE_RHS)
1776     extract_ops_from_tree_1 (name, &code1, &arg11, &arg21, &arg31);
1777
1778   *code = code1;
1779   *arg1 = arg11;
1780   if (arg2)
1781     *arg2 = arg21;
1782   /* Ignore arg3 currently. */
1783 }
1784
1785 /* Simplify bitwise binary operations.
1786    Return true if a transformation applied, otherwise return false.  */
1787
1788 static bool
1789 simplify_bitwise_binary (gimple_stmt_iterator *gsi)
1790 {
1791   gimple stmt = gsi_stmt (*gsi);
1792   tree arg1 = gimple_assign_rhs1 (stmt);
1793   tree arg2 = gimple_assign_rhs2 (stmt);
1794   enum tree_code code = gimple_assign_rhs_code (stmt);
1795   tree res;
1796   tree def1_arg1, def1_arg2, def2_arg1, def2_arg2;
1797   enum tree_code def1_code, def2_code;
1798
1799   defcodefor_name (arg1, &def1_code, &def1_arg1, &def1_arg2);
1800   defcodefor_name (arg2, &def2_code, &def2_arg1, &def2_arg2);
1801
1802   /* Try to fold (type) X op CST -> (type) (X op ((type-x) CST)).  */
1803   if (TREE_CODE (arg2) == INTEGER_CST
1804       && CONVERT_EXPR_CODE_P (def1_code)
1805       && INTEGRAL_TYPE_P (TREE_TYPE (def1_arg1))
1806       && int_fits_type_p (arg2, TREE_TYPE (def1_arg1)))
1807     {
1808       gimple newop;
1809       tree tem = make_ssa_name (TREE_TYPE (def1_arg1), NULL);
1810       newop =
1811         gimple_build_assign_with_ops (code, tem, def1_arg1,
1812                                       fold_convert_loc (gimple_location (stmt),
1813                                                         TREE_TYPE (def1_arg1),
1814                                                         arg2));
1815       gimple_set_location (newop, gimple_location (stmt));
1816       gsi_insert_before (gsi, newop, GSI_SAME_STMT);
1817       gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
1818                                         tem, NULL_TREE, NULL_TREE);
1819       update_stmt (gsi_stmt (*gsi));
1820       return true;
1821     }
1822
1823   /* For bitwise binary operations apply operand conversions to the
1824      binary operation result instead of to the operands.  This allows
1825      to combine successive conversions and bitwise binary operations.  */
1826   if (CONVERT_EXPR_CODE_P (def1_code)
1827       && CONVERT_EXPR_CODE_P (def2_code)
1828       && types_compatible_p (TREE_TYPE (def1_arg1), TREE_TYPE (def2_arg1))
1829       /* Make sure that the conversion widens the operands, or has same
1830          precision,  or that it changes the operation to a bitfield
1831          precision.  */
1832       && ((TYPE_PRECISION (TREE_TYPE (def1_arg1))
1833            <= TYPE_PRECISION (TREE_TYPE (arg1)))
1834           || (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (arg1)))
1835               != MODE_INT)
1836           || (TYPE_PRECISION (TREE_TYPE (arg1))
1837               != GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (arg1))))))
1838     {
1839       gimple newop;
1840       tree tem = make_ssa_name (TREE_TYPE (def1_arg1), NULL);
1841       newop = gimple_build_assign_with_ops (code, tem, def1_arg1, def2_arg1);
1842       gimple_set_location (newop, gimple_location (stmt));
1843       gsi_insert_before (gsi, newop, GSI_SAME_STMT);
1844       gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
1845                                         tem, NULL_TREE, NULL_TREE);
1846       update_stmt (gsi_stmt (*gsi));
1847       return true;
1848     }
1849
1850
1851    /* Simplify (A & B) OP0 (C & B) to (A OP0 C) & B. */
1852    if (def1_code == def2_code
1853        && def1_code == BIT_AND_EXPR
1854        && operand_equal_for_phi_arg_p (def1_arg2,
1855                                        def2_arg2))
1856     {
1857       tree b = def1_arg2;
1858       tree a = def1_arg1;
1859       tree c = def2_arg1;
1860       tree inner = fold_build2 (code, TREE_TYPE (arg2), a, c);
1861       /* If A OP0 C (this usually means C is the same as A) is 0
1862          then fold it down correctly. */
1863       if (integer_zerop (inner))
1864         {
1865           gimple_assign_set_rhs_from_tree (gsi, inner);
1866           update_stmt (stmt);
1867           return true;
1868         }
1869       /* If A OP0 C (this usually means C is the same as A) is a ssa_name
1870          then fold it down correctly. */
1871       else if (TREE_CODE (inner) == SSA_NAME)
1872         {
1873           tree outer = fold_build2 (def1_code, TREE_TYPE (inner),
1874                                     inner, b);
1875           gimple_assign_set_rhs_from_tree (gsi, outer);
1876           update_stmt (stmt);
1877           return true;
1878         }
1879       else
1880         {
1881           gimple newop;
1882           tree tem;
1883           tem = make_ssa_name (TREE_TYPE (arg2), NULL);
1884           newop = gimple_build_assign_with_ops (code, tem, a, c);
1885           gimple_set_location (newop, gimple_location (stmt));
1886           /* Make sure to re-process the new stmt as it's walking upwards.  */
1887           gsi_insert_before (gsi, newop, GSI_NEW_STMT);
1888           gimple_assign_set_rhs1 (stmt, tem);
1889           gimple_assign_set_rhs2 (stmt, b);
1890           gimple_assign_set_rhs_code (stmt, def1_code);
1891           update_stmt (stmt);
1892           return true;
1893         }
1894     }
1895
1896   /* (a | CST1) & CST2  ->  (a & CST2) | (CST1 & CST2).  */
1897   if (code == BIT_AND_EXPR
1898       && def1_code == BIT_IOR_EXPR
1899       && TREE_CODE (arg2) == INTEGER_CST
1900       && TREE_CODE (def1_arg2) == INTEGER_CST)
1901     {
1902       tree cst = fold_build2 (BIT_AND_EXPR, TREE_TYPE (arg2),
1903                               arg2, def1_arg2);
1904       tree tem;
1905       gimple newop;
1906       if (integer_zerop (cst))
1907         {
1908           gimple_assign_set_rhs1 (stmt, def1_arg1);
1909           update_stmt (stmt);
1910           return true;
1911         }
1912       tem = make_ssa_name (TREE_TYPE (arg2), NULL);
1913       newop = gimple_build_assign_with_ops (BIT_AND_EXPR,
1914                                             tem, def1_arg1, arg2);
1915       gimple_set_location (newop, gimple_location (stmt));
1916       /* Make sure to re-process the new stmt as it's walking upwards.  */
1917       gsi_insert_before (gsi, newop, GSI_NEW_STMT);
1918       gimple_assign_set_rhs1 (stmt, tem);
1919       gimple_assign_set_rhs2 (stmt, cst);
1920       gimple_assign_set_rhs_code (stmt, BIT_IOR_EXPR);
1921       update_stmt (stmt);
1922       return true;
1923     }
1924
1925   /* Combine successive equal operations with constants.  */
1926   if ((code == BIT_AND_EXPR
1927        || code == BIT_IOR_EXPR
1928        || code == BIT_XOR_EXPR)
1929       && def1_code == code
1930       && TREE_CODE (arg2) == INTEGER_CST
1931       && TREE_CODE (def1_arg2) == INTEGER_CST)
1932     {
1933       tree cst = fold_build2 (code, TREE_TYPE (arg2),
1934                               arg2, def1_arg2);
1935       gimple_assign_set_rhs1 (stmt, def1_arg1);
1936       gimple_assign_set_rhs2 (stmt, cst);
1937       update_stmt (stmt);
1938       return true;
1939     }
1940
1941   /* Canonicalize X ^ ~0 to ~X.  */
1942   if (code == BIT_XOR_EXPR
1943       && TREE_CODE (arg2) == INTEGER_CST
1944       && integer_all_onesp (arg2))
1945     {
1946       gimple_assign_set_rhs_with_ops (gsi, BIT_NOT_EXPR, arg1, NULL_TREE);
1947       gcc_assert (gsi_stmt (*gsi) == stmt);
1948       update_stmt (stmt);
1949       return true;
1950     }
1951
1952   /* Try simple folding for X op !X, and X op X.  */
1953   res = simplify_bitwise_binary_1 (code, TREE_TYPE (arg1), arg1, arg2);
1954   if (res != NULL_TREE)
1955     {
1956       gimple_assign_set_rhs_from_tree (gsi, res);
1957       update_stmt (gsi_stmt (*gsi));
1958       return true;
1959     }
1960
1961   if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
1962     {
1963       enum tree_code ocode = code == BIT_AND_EXPR ? BIT_IOR_EXPR : BIT_AND_EXPR;
1964       if (def1_code == ocode)
1965         {
1966           tree x = arg2;
1967           enum tree_code coden;
1968           tree a1, a2;
1969           /* ( X | Y) & X -> X */
1970           /* ( X & Y) | X -> X */
1971           if (x == def1_arg1
1972               || x == def1_arg2)
1973             {
1974               gimple_assign_set_rhs_from_tree (gsi, x);
1975               update_stmt (gsi_stmt (*gsi));
1976               return true;
1977             }
1978
1979           defcodefor_name (def1_arg1, &coden, &a1, &a2);
1980           /* (~X | Y) & X -> X & Y */
1981           /* (~X & Y) | X -> X | Y */
1982           if (coden == BIT_NOT_EXPR && a1 == x)
1983             {
1984               gimple_assign_set_rhs_with_ops (gsi, code,
1985                                               x, def1_arg2);
1986               gcc_assert (gsi_stmt (*gsi) == stmt);
1987               update_stmt (stmt);
1988               return true;
1989             }
1990           defcodefor_name (def1_arg2, &coden, &a1, &a2);
1991           /* (Y | ~X) & X -> X & Y */
1992           /* (Y & ~X) | X -> X | Y */
1993           if (coden == BIT_NOT_EXPR && a1 == x)
1994             {
1995               gimple_assign_set_rhs_with_ops (gsi, code,
1996                                               x, def1_arg1);
1997               gcc_assert (gsi_stmt (*gsi) == stmt);
1998               update_stmt (stmt);
1999               return true;
2000             }
2001         }
2002       if (def2_code == ocode)
2003         {
2004           enum tree_code coden;
2005           tree a1;
2006           tree x = arg1;
2007           /* X & ( X | Y) -> X */
2008           /* X | ( X & Y) -> X */
2009           if (x == def2_arg1
2010               || x == def2_arg2)
2011             {
2012               gimple_assign_set_rhs_from_tree (gsi, x);
2013               update_stmt (gsi_stmt (*gsi));
2014               return true;
2015             }
2016           defcodefor_name (def2_arg1, &coden, &a1, NULL);
2017           /* (~X | Y) & X -> X & Y */
2018           /* (~X & Y) | X -> X | Y */
2019           if (coden == BIT_NOT_EXPR && a1 == x)
2020             {
2021               gimple_assign_set_rhs_with_ops (gsi, code,
2022                                               x, def2_arg2);
2023               gcc_assert (gsi_stmt (*gsi) == stmt);
2024               update_stmt (stmt);
2025               return true;
2026             }
2027           defcodefor_name (def2_arg2, &coden, &a1, NULL);
2028           /* (Y | ~X) & X -> X & Y */
2029           /* (Y & ~X) | X -> X | Y */
2030           if (coden == BIT_NOT_EXPR && a1 == x)
2031             {
2032               gimple_assign_set_rhs_with_ops (gsi, code,
2033                                               x, def2_arg1);
2034               gcc_assert (gsi_stmt (*gsi) == stmt);
2035               update_stmt (stmt);
2036               return true;
2037             }
2038         }
2039     }
2040
2041   return false;
2042 }
2043
2044
2045 /* Perform re-associations of the plus or minus statement STMT that are
2046    always permitted.  Returns true if the CFG was changed.  */
2047
2048 static bool
2049 associate_plusminus (gimple_stmt_iterator *gsi)
2050 {
2051   gimple stmt = gsi_stmt (*gsi);
2052   tree rhs1 = gimple_assign_rhs1 (stmt);
2053   tree rhs2 = gimple_assign_rhs2 (stmt);
2054   enum tree_code code = gimple_assign_rhs_code (stmt);
2055   bool changed;
2056
2057   /* We can't reassociate at all for saturating types.  */
2058   if (TYPE_SATURATING (TREE_TYPE (rhs1)))
2059     return false;
2060
2061   /* First contract negates.  */
2062   do
2063     {
2064       changed = false;
2065
2066       /* A +- (-B) -> A -+ B.  */
2067       if (TREE_CODE (rhs2) == SSA_NAME)
2068         {
2069           gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
2070           if (is_gimple_assign (def_stmt)
2071               && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
2072               && can_propagate_from (def_stmt))
2073             {
2074               code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR;
2075               gimple_assign_set_rhs_code (stmt, code);
2076               rhs2 = gimple_assign_rhs1 (def_stmt);
2077               gimple_assign_set_rhs2 (stmt, rhs2);
2078               gimple_set_modified (stmt, true);
2079               changed = true;
2080             }
2081         }
2082
2083       /* (-A) + B -> B - A.  */
2084       if (TREE_CODE (rhs1) == SSA_NAME
2085           && code == PLUS_EXPR)
2086         {
2087           gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
2088           if (is_gimple_assign (def_stmt)
2089               && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
2090               && can_propagate_from (def_stmt))
2091             {
2092               code = MINUS_EXPR;
2093               gimple_assign_set_rhs_code (stmt, code);
2094               rhs1 = rhs2;
2095               gimple_assign_set_rhs1 (stmt, rhs1);
2096               rhs2 = gimple_assign_rhs1 (def_stmt);
2097               gimple_assign_set_rhs2 (stmt, rhs2);
2098               gimple_set_modified (stmt, true);
2099               changed = true;
2100             }
2101         }
2102     }
2103   while (changed);
2104
2105   /* We can't reassociate floating-point or fixed-point plus or minus
2106      because of saturation to +-Inf.  */
2107   if (FLOAT_TYPE_P (TREE_TYPE (rhs1))
2108       || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1)))
2109     goto out;
2110
2111   /* Second match patterns that allow contracting a plus-minus pair
2112      irrespective of overflow issues.
2113
2114         (A +- B) - A       ->  +- B
2115         (A +- B) -+ B      ->  A
2116         (CST +- A) +- CST  ->  CST +- A
2117         (A + CST) +- CST   ->  A + CST
2118         ~A + A             ->  -1
2119         ~A + 1             ->  -A
2120         A - (A +- B)       ->  -+ B
2121         A +- (B +- A)      ->  +- B
2122         CST +- (CST +- A)  ->  CST +- A
2123         CST +- (A +- CST)  ->  CST +- A
2124         A + ~A             ->  -1
2125
2126      via commutating the addition and contracting operations to zero
2127      by reassociation.  */
2128
2129   if (TREE_CODE (rhs1) == SSA_NAME)
2130     {
2131       gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
2132       if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
2133         {
2134           enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
2135           if (def_code == PLUS_EXPR
2136               || def_code == MINUS_EXPR)
2137             {
2138               tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2139               tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
2140               if (operand_equal_p (def_rhs1, rhs2, 0)
2141                   && code == MINUS_EXPR)
2142                 {
2143                   /* (A +- B) - A -> +- B.  */
2144                   code = ((def_code == PLUS_EXPR)
2145                           ? TREE_CODE (def_rhs2) : NEGATE_EXPR);
2146                   rhs1 = def_rhs2;
2147                   rhs2 = NULL_TREE;
2148                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2149                   gcc_assert (gsi_stmt (*gsi) == stmt);
2150                   gimple_set_modified (stmt, true);
2151                 }
2152               else if (operand_equal_p (def_rhs2, rhs2, 0)
2153                        && code != def_code)
2154                 {
2155                   /* (A +- B) -+ B -> A.  */
2156                   code = TREE_CODE (def_rhs1);
2157                   rhs1 = def_rhs1;
2158                   rhs2 = NULL_TREE;
2159                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2160                   gcc_assert (gsi_stmt (*gsi) == stmt);
2161                   gimple_set_modified (stmt, true);
2162                 }
2163               else if (TREE_CODE (rhs2) == INTEGER_CST
2164                        && TREE_CODE (def_rhs1) == INTEGER_CST)
2165                 {
2166                   /* (CST +- A) +- CST -> CST +- A.  */
2167                   tree cst = fold_binary (code, TREE_TYPE (rhs1),
2168                                           def_rhs1, rhs2);
2169                   if (cst && !TREE_OVERFLOW (cst))
2170                     {
2171                       code = def_code;
2172                       gimple_assign_set_rhs_code (stmt, code);
2173                       rhs1 = cst;
2174                       gimple_assign_set_rhs1 (stmt, rhs1);
2175                       rhs2 = def_rhs2;
2176                       gimple_assign_set_rhs2 (stmt, rhs2);
2177                       gimple_set_modified (stmt, true);
2178                     }
2179                 }
2180               else if (TREE_CODE (rhs2) == INTEGER_CST
2181                        && TREE_CODE (def_rhs2) == INTEGER_CST
2182                        && def_code == PLUS_EXPR)
2183                 {
2184                   /* (A + CST) +- CST -> A + CST.  */
2185                   tree cst = fold_binary (code, TREE_TYPE (rhs1),
2186                                           def_rhs2, rhs2);
2187                   if (cst && !TREE_OVERFLOW (cst))
2188                     {
2189                       code = PLUS_EXPR;
2190                       gimple_assign_set_rhs_code (stmt, code);
2191                       rhs1 = def_rhs1;
2192                       gimple_assign_set_rhs1 (stmt, rhs1);
2193                       rhs2 = cst;
2194                       gimple_assign_set_rhs2 (stmt, rhs2);
2195                       gimple_set_modified (stmt, true);
2196                     }
2197                 }
2198             }
2199           else if (def_code == BIT_NOT_EXPR
2200                    && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
2201             {
2202               tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2203               if (code == PLUS_EXPR
2204                   && operand_equal_p (def_rhs1, rhs2, 0))
2205                 {
2206                   /* ~A + A -> -1.  */
2207                   code = INTEGER_CST;
2208                   rhs1 = build_int_cst_type (TREE_TYPE (rhs2), -1);
2209                   rhs2 = NULL_TREE;
2210                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2211                   gcc_assert (gsi_stmt (*gsi) == stmt);
2212                   gimple_set_modified (stmt, true);
2213                 }
2214               else if (code == PLUS_EXPR
2215                        && integer_onep (rhs1))
2216                 {
2217                   /* ~A + 1 -> -A.  */
2218                   code = NEGATE_EXPR;
2219                   rhs1 = def_rhs1;
2220                   rhs2 = NULL_TREE;
2221                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2222                   gcc_assert (gsi_stmt (*gsi) == stmt);
2223                   gimple_set_modified (stmt, true);
2224                 }
2225             }
2226         }
2227     }
2228
2229   if (rhs2 && TREE_CODE (rhs2) == SSA_NAME)
2230     {
2231       gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
2232       if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
2233         {
2234           enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
2235           if (def_code == PLUS_EXPR
2236               || def_code == MINUS_EXPR)
2237             {
2238               tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2239               tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
2240               if (operand_equal_p (def_rhs1, rhs1, 0)
2241                   && code == MINUS_EXPR)
2242                 {
2243                   /* A - (A +- B) -> -+ B.  */
2244                   code = ((def_code == PLUS_EXPR)
2245                           ? NEGATE_EXPR : TREE_CODE (def_rhs2));
2246                   rhs1 = def_rhs2;
2247                   rhs2 = NULL_TREE;
2248                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2249                   gcc_assert (gsi_stmt (*gsi) == stmt);
2250                   gimple_set_modified (stmt, true);
2251                 }
2252               else if (operand_equal_p (def_rhs2, rhs1, 0)
2253                        && code != def_code)
2254                 {
2255                   /* A +- (B +- A) -> +- B.  */
2256                   code = ((code == PLUS_EXPR)
2257                           ? TREE_CODE (def_rhs1) : NEGATE_EXPR);
2258                   rhs1 = def_rhs1;
2259                   rhs2 = NULL_TREE;
2260                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2261                   gcc_assert (gsi_stmt (*gsi) == stmt);
2262                   gimple_set_modified (stmt, true);
2263                 }
2264               else if (TREE_CODE (rhs1) == INTEGER_CST
2265                        && TREE_CODE (def_rhs1) == INTEGER_CST)
2266                 {
2267                   /* CST +- (CST +- A) -> CST +- A.  */
2268                   tree cst = fold_binary (code, TREE_TYPE (rhs2),
2269                                           rhs1, def_rhs1);
2270                   if (cst && !TREE_OVERFLOW (cst))
2271                     {
2272                       code = (code == def_code ? PLUS_EXPR : MINUS_EXPR);
2273                       gimple_assign_set_rhs_code (stmt, code);
2274                       rhs1 = cst;
2275                       gimple_assign_set_rhs1 (stmt, rhs1);
2276                       rhs2 = def_rhs2;
2277                       gimple_assign_set_rhs2 (stmt, rhs2);
2278                       gimple_set_modified (stmt, true);
2279                     }
2280                 }
2281               else if (TREE_CODE (rhs1) == INTEGER_CST
2282                        && TREE_CODE (def_rhs2) == INTEGER_CST)
2283                 {
2284                   /* CST +- (A +- CST) -> CST +- A.  */
2285                   tree cst = fold_binary (def_code == code
2286                                           ? PLUS_EXPR : MINUS_EXPR,
2287                                           TREE_TYPE (rhs2),
2288                                           rhs1, def_rhs2);
2289                   if (cst && !TREE_OVERFLOW (cst))
2290                     {
2291                       rhs1 = cst;
2292                       gimple_assign_set_rhs1 (stmt, rhs1);
2293                       rhs2 = def_rhs1;
2294                       gimple_assign_set_rhs2 (stmt, rhs2);
2295                       gimple_set_modified (stmt, true);
2296                     }
2297                 }
2298             }
2299           else if (def_code == BIT_NOT_EXPR
2300                    && INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
2301             {
2302               tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2303               if (code == PLUS_EXPR
2304                   && operand_equal_p (def_rhs1, rhs1, 0))
2305                 {
2306                   /* A + ~A -> -1.  */
2307                   code = INTEGER_CST;
2308                   rhs1 = build_int_cst_type (TREE_TYPE (rhs1), -1);
2309                   rhs2 = NULL_TREE;
2310                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2311                   gcc_assert (gsi_stmt (*gsi) == stmt);
2312                   gimple_set_modified (stmt, true);
2313                 }
2314             }
2315         }
2316     }
2317
2318 out:
2319   if (gimple_modified_p (stmt))
2320     {
2321       fold_stmt_inplace (gsi);
2322       update_stmt (stmt);
2323       if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
2324           && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
2325         return true;
2326     }
2327
2328   return false;
2329 }
2330
2331 /* Associate operands of a POINTER_PLUS_EXPR assignmen at *GSI.  Returns
2332    true if anything changed, false otherwise.  */
2333
2334 static bool
2335 associate_pointerplus (gimple_stmt_iterator *gsi)
2336 {
2337   gimple stmt = gsi_stmt (*gsi);
2338   gimple def_stmt;
2339   tree ptr, rhs, algn;
2340
2341   /* Pattern match
2342        tem = (sizetype) ptr;
2343        tem = tem & algn;
2344        tem = -tem;
2345        ... = ptr p+ tem;
2346      and produce the simpler and easier to analyze with respect to alignment
2347        ... = ptr & ~algn;  */
2348   ptr = gimple_assign_rhs1 (stmt);
2349   rhs = gimple_assign_rhs2 (stmt);
2350   if (TREE_CODE (rhs) != SSA_NAME)
2351     return false;
2352   def_stmt = SSA_NAME_DEF_STMT (rhs);
2353   if (!is_gimple_assign (def_stmt)
2354       || gimple_assign_rhs_code (def_stmt) != NEGATE_EXPR)
2355     return false;
2356   rhs = gimple_assign_rhs1 (def_stmt);
2357   if (TREE_CODE (rhs) != SSA_NAME)
2358     return false;
2359   def_stmt = SSA_NAME_DEF_STMT (rhs);
2360   if (!is_gimple_assign (def_stmt)
2361       || gimple_assign_rhs_code (def_stmt) != BIT_AND_EXPR)
2362     return false;
2363   rhs = gimple_assign_rhs1 (def_stmt);
2364   algn = gimple_assign_rhs2 (def_stmt);
2365   if (TREE_CODE (rhs) != SSA_NAME
2366       || TREE_CODE (algn) != INTEGER_CST)
2367     return false;
2368   def_stmt = SSA_NAME_DEF_STMT (rhs);
2369   if (!is_gimple_assign (def_stmt)
2370       || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
2371     return false;
2372   if (gimple_assign_rhs1 (def_stmt) != ptr)
2373     return false;
2374
2375   algn = double_int_to_tree (TREE_TYPE (ptr),
2376                              double_int_not (tree_to_double_int (algn)));
2377   gimple_assign_set_rhs_with_ops (gsi, BIT_AND_EXPR, ptr, algn);
2378   fold_stmt_inplace (gsi);
2379   update_stmt (stmt);
2380
2381   return true;
2382 }
2383
2384 /* Combine two conversions in a row for the second conversion at *GSI.
2385    Returns 1 if there were any changes made, 2 if cfg-cleanup needs to
2386    run.  Else it returns 0.  */
2387
2388 static int
2389 combine_conversions (gimple_stmt_iterator *gsi)
2390 {
2391   gimple stmt = gsi_stmt (*gsi);
2392   gimple def_stmt;
2393   tree op0, lhs;
2394   enum tree_code code = gimple_assign_rhs_code (stmt);
2395   enum tree_code code2;
2396
2397   gcc_checking_assert (CONVERT_EXPR_CODE_P (code)
2398                        || code == FLOAT_EXPR
2399                        || code == FIX_TRUNC_EXPR);
2400
2401   lhs = gimple_assign_lhs (stmt);
2402   op0 = gimple_assign_rhs1 (stmt);
2403   if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (op0)))
2404     {
2405       gimple_assign_set_rhs_code (stmt, TREE_CODE (op0));
2406       return 1;
2407     }
2408
2409   if (TREE_CODE (op0) != SSA_NAME)
2410     return 0;
2411
2412   def_stmt = SSA_NAME_DEF_STMT (op0);
2413   if (!is_gimple_assign (def_stmt))
2414     return 0;
2415
2416   code2 = gimple_assign_rhs_code (def_stmt);
2417
2418   if (CONVERT_EXPR_CODE_P (code2) || code2 == FLOAT_EXPR)
2419     {
2420       tree defop0 = gimple_assign_rhs1 (def_stmt);
2421       tree type = TREE_TYPE (lhs);
2422       tree inside_type = TREE_TYPE (defop0);
2423       tree inter_type = TREE_TYPE (op0);
2424       int inside_int = INTEGRAL_TYPE_P (inside_type);
2425       int inside_ptr = POINTER_TYPE_P (inside_type);
2426       int inside_float = FLOAT_TYPE_P (inside_type);
2427       int inside_vec = TREE_CODE (inside_type) == VECTOR_TYPE;
2428       unsigned int inside_prec = TYPE_PRECISION (inside_type);
2429       int inside_unsignedp = TYPE_UNSIGNED (inside_type);
2430       int inter_int = INTEGRAL_TYPE_P (inter_type);
2431       int inter_ptr = POINTER_TYPE_P (inter_type);
2432       int inter_float = FLOAT_TYPE_P (inter_type);
2433       int inter_vec = TREE_CODE (inter_type) == VECTOR_TYPE;
2434       unsigned int inter_prec = TYPE_PRECISION (inter_type);
2435       int inter_unsignedp = TYPE_UNSIGNED (inter_type);
2436       int final_int = INTEGRAL_TYPE_P (type);
2437       int final_ptr = POINTER_TYPE_P (type);
2438       int final_float = FLOAT_TYPE_P (type);
2439       int final_vec = TREE_CODE (type) == VECTOR_TYPE;
2440       unsigned int final_prec = TYPE_PRECISION (type);
2441       int final_unsignedp = TYPE_UNSIGNED (type);
2442
2443       /* Don't propagate ssa names that occur in abnormal phis.  */
2444       if (TREE_CODE (defop0) == SSA_NAME
2445           && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defop0))
2446         return 0;
2447
2448       /* In addition to the cases of two conversions in a row
2449          handled below, if we are converting something to its own
2450          type via an object of identical or wider precision, neither
2451          conversion is needed.  */
2452       if (useless_type_conversion_p (type, inside_type)
2453           && (((inter_int || inter_ptr) && final_int)
2454               || (inter_float && final_float))
2455           && inter_prec >= final_prec)
2456         {
2457           gimple_assign_set_rhs1 (stmt, unshare_expr (defop0));
2458           gimple_assign_set_rhs_code (stmt, TREE_CODE (defop0));
2459           update_stmt (stmt);
2460           return remove_prop_source_from_use (op0) ? 2 : 1;
2461         }
2462
2463       /* Likewise, if the intermediate and initial types are either both
2464          float or both integer, we don't need the middle conversion if the
2465          former is wider than the latter and doesn't change the signedness
2466          (for integers).  Avoid this if the final type is a pointer since
2467          then we sometimes need the middle conversion.  Likewise if the
2468          final type has a precision not equal to the size of its mode.  */
2469       if (((inter_int && inside_int)
2470            || (inter_float && inside_float)
2471            || (inter_vec && inside_vec))
2472           && inter_prec >= inside_prec
2473           && (inter_float || inter_vec
2474               || inter_unsignedp == inside_unsignedp)
2475           && ! (final_prec != GET_MODE_PRECISION (TYPE_MODE (type))
2476                 && TYPE_MODE (type) == TYPE_MODE (inter_type))
2477           && ! final_ptr
2478           && (! final_vec || inter_prec == inside_prec))
2479         {
2480           gimple_assign_set_rhs1 (stmt, defop0);
2481           update_stmt (stmt);
2482           return remove_prop_source_from_use (op0) ? 2 : 1;
2483         }
2484
2485       /* If we have a sign-extension of a zero-extended value, we can
2486          replace that by a single zero-extension.  Likewise if the
2487          final conversion does not change precision we can drop the
2488          intermediate conversion.  */
2489       if (inside_int && inter_int && final_int
2490           && ((inside_prec < inter_prec && inter_prec < final_prec
2491                && inside_unsignedp && !inter_unsignedp)
2492               || final_prec == inter_prec))
2493         {
2494           gimple_assign_set_rhs1 (stmt, defop0);
2495           update_stmt (stmt);
2496           return remove_prop_source_from_use (op0) ? 2 : 1;
2497         }
2498
2499       /* Two conversions in a row are not needed unless:
2500          - some conversion is floating-point (overstrict for now), or
2501          - some conversion is a vector (overstrict for now), or
2502          - the intermediate type is narrower than both initial and
2503          final, or
2504          - the intermediate type and innermost type differ in signedness,
2505          and the outermost type is wider than the intermediate, or
2506          - the initial type is a pointer type and the precisions of the
2507          intermediate and final types differ, or
2508          - the final type is a pointer type and the precisions of the
2509          initial and intermediate types differ.  */
2510       if (! inside_float && ! inter_float && ! final_float
2511           && ! inside_vec && ! inter_vec && ! final_vec
2512           && (inter_prec >= inside_prec || inter_prec >= final_prec)
2513           && ! (inside_int && inter_int
2514                 && inter_unsignedp != inside_unsignedp
2515                 && inter_prec < final_prec)
2516           && ((inter_unsignedp && inter_prec > inside_prec)
2517               == (final_unsignedp && final_prec > inter_prec))
2518           && ! (inside_ptr && inter_prec != final_prec)
2519           && ! (final_ptr && inside_prec != inter_prec)
2520           && ! (final_prec != GET_MODE_PRECISION (TYPE_MODE (type))
2521                 && TYPE_MODE (type) == TYPE_MODE (inter_type)))
2522         {
2523           gimple_assign_set_rhs1 (stmt, defop0);
2524           update_stmt (stmt);
2525           return remove_prop_source_from_use (op0) ? 2 : 1;
2526         }
2527
2528       /* A truncation to an unsigned type should be canonicalized as
2529          bitwise and of a mask.  */
2530       if (final_int && inter_int && inside_int
2531           && final_prec == inside_prec
2532           && final_prec > inter_prec
2533           && inter_unsignedp)
2534         {
2535           tree tem;
2536           tem = fold_build2 (BIT_AND_EXPR, inside_type,
2537                              defop0,
2538                              double_int_to_tree
2539                                (inside_type, double_int_mask (inter_prec)));
2540           if (!useless_type_conversion_p (type, inside_type))
2541             {
2542               tem = force_gimple_operand_gsi (gsi, tem, true, NULL_TREE, true,
2543                                               GSI_SAME_STMT);
2544               gimple_assign_set_rhs1 (stmt, tem);
2545             }
2546           else
2547             gimple_assign_set_rhs_from_tree (gsi, tem);
2548           update_stmt (gsi_stmt (*gsi));
2549           return 1;
2550         }
2551
2552       /* If we are converting an integer to a floating-point that can
2553          represent it exactly and back to an integer, we can skip the
2554          floating-point conversion.  */
2555       if (inside_int && inter_float && final_int &&
2556           (unsigned) significand_size (TYPE_MODE (inter_type))
2557           >= inside_prec - !inside_unsignedp)
2558         {
2559           if (useless_type_conversion_p (type, inside_type))
2560             {
2561               gimple_assign_set_rhs1 (stmt, unshare_expr (defop0));
2562               gimple_assign_set_rhs_code (stmt, TREE_CODE (defop0));
2563               update_stmt (stmt);
2564               return remove_prop_source_from_use (op0) ? 2 : 1;
2565             }
2566           else
2567             {
2568               gimple_assign_set_rhs1 (stmt, defop0);
2569               gimple_assign_set_rhs_code (stmt, CONVERT_EXPR);
2570               update_stmt (stmt);
2571               return remove_prop_source_from_use (op0) ? 2 : 1;
2572             }
2573         }
2574     }
2575
2576   return 0;
2577 }
2578
2579 /* Main entry point for the forward propagation and statement combine
2580    optimizer.  */
2581
2582 static unsigned int
2583 ssa_forward_propagate_and_combine (void)
2584 {
2585   basic_block bb;
2586   unsigned int todoflags = 0;
2587
2588   cfg_changed = false;
2589
2590   FOR_EACH_BB (bb)
2591     {
2592       gimple_stmt_iterator gsi;
2593
2594       /* Apply forward propagation to all stmts in the basic-block.
2595          Note we update GSI within the loop as necessary.  */
2596       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2597         {
2598           gimple stmt = gsi_stmt (gsi);
2599           tree lhs, rhs;
2600           enum tree_code code;
2601
2602           if (!is_gimple_assign (stmt))
2603             {
2604               gsi_next (&gsi);
2605               continue;
2606             }
2607
2608           lhs = gimple_assign_lhs (stmt);
2609           rhs = gimple_assign_rhs1 (stmt);
2610           code = gimple_assign_rhs_code (stmt);
2611           if (TREE_CODE (lhs) != SSA_NAME
2612               || has_zero_uses (lhs))
2613             {
2614               gsi_next (&gsi);
2615               continue;
2616             }
2617
2618           /* If this statement sets an SSA_NAME to an address,
2619              try to propagate the address into the uses of the SSA_NAME.  */
2620           if (code == ADDR_EXPR
2621               /* Handle pointer conversions on invariant addresses
2622                  as well, as this is valid gimple.  */
2623               || (CONVERT_EXPR_CODE_P (code)
2624                   && TREE_CODE (rhs) == ADDR_EXPR
2625                   && POINTER_TYPE_P (TREE_TYPE (lhs))))
2626             {
2627               tree base = get_base_address (TREE_OPERAND (rhs, 0));
2628               if ((!base
2629                    || !DECL_P (base)
2630                    || decl_address_invariant_p (base))
2631                   && !stmt_references_abnormal_ssa_name (stmt)
2632                   && forward_propagate_addr_expr (lhs, rhs))
2633                 {
2634                   release_defs (stmt);
2635                   todoflags |= TODO_remove_unused_locals;
2636                   gsi_remove (&gsi, true);
2637                 }
2638               else
2639                 gsi_next (&gsi);
2640             }
2641           else if (code == POINTER_PLUS_EXPR)
2642             {
2643               tree off = gimple_assign_rhs2 (stmt);
2644               if (TREE_CODE (off) == INTEGER_CST
2645                   && can_propagate_from (stmt)
2646                   && !simple_iv_increment_p (stmt)
2647                   /* ???  Better adjust the interface to that function
2648                      instead of building new trees here.  */
2649                   && forward_propagate_addr_expr
2650                        (lhs,
2651                         build1_loc (gimple_location (stmt),
2652                                     ADDR_EXPR, TREE_TYPE (rhs),
2653                                     fold_build2 (MEM_REF,
2654                                                  TREE_TYPE (TREE_TYPE (rhs)),
2655                                                  rhs,
2656                                                  fold_convert (ptr_type_node,
2657                                                                off)))))
2658                 {
2659                   release_defs (stmt);
2660                   todoflags |= TODO_remove_unused_locals;
2661                   gsi_remove (&gsi, true);
2662                 }
2663               else if (is_gimple_min_invariant (rhs))
2664                 {
2665                   /* Make sure to fold &a[0] + off_1 here.  */
2666                   fold_stmt_inplace (&gsi);
2667                   update_stmt (stmt);
2668                   if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
2669                     gsi_next (&gsi);
2670                 }
2671               else
2672                 gsi_next (&gsi);
2673             }
2674           else if (TREE_CODE_CLASS (code) == tcc_comparison)
2675             {
2676               if (forward_propagate_comparison (&gsi))
2677                 cfg_changed = true;
2678             }
2679           else
2680             gsi_next (&gsi);
2681         }
2682
2683       /* Combine stmts with the stmts defining their operands.
2684          Note we update GSI within the loop as necessary.  */
2685       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
2686         {
2687           gimple stmt = gsi_stmt (gsi);
2688           bool changed = false;
2689
2690           /* Mark stmt as potentially needing revisiting.  */
2691           gimple_set_plf (stmt, GF_PLF_1, false);
2692
2693           switch (gimple_code (stmt))
2694             {
2695             case GIMPLE_ASSIGN:
2696               {
2697                 tree rhs1 = gimple_assign_rhs1 (stmt);
2698                 enum tree_code code = gimple_assign_rhs_code (stmt);
2699
2700                 if ((code == BIT_NOT_EXPR
2701                      || code == NEGATE_EXPR)
2702                     && TREE_CODE (rhs1) == SSA_NAME)
2703                   changed = simplify_not_neg_expr (&gsi);
2704                 else if (code == COND_EXPR
2705                          || code == VEC_COND_EXPR)
2706                   {
2707                     /* In this case the entire COND_EXPR is in rhs1. */
2708                     if (forward_propagate_into_cond (&gsi)
2709                         || combine_cond_exprs (&gsi))
2710                       {
2711                         changed = true;
2712                         stmt = gsi_stmt (gsi);
2713                       }
2714                   }
2715                 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2716                   {
2717                     int did_something;
2718                     did_something = forward_propagate_into_comparison (&gsi);
2719                     if (did_something == 2)
2720                       cfg_changed = true;
2721                     changed = did_something != 0;
2722                   }
2723                 else if (code == BIT_AND_EXPR
2724                          || code == BIT_IOR_EXPR
2725                          || code == BIT_XOR_EXPR)
2726                   changed = simplify_bitwise_binary (&gsi);
2727                 else if (code == PLUS_EXPR
2728                          || code == MINUS_EXPR)
2729                   changed = associate_plusminus (&gsi);
2730                 else if (code == POINTER_PLUS_EXPR)
2731                   changed = associate_pointerplus (&gsi);
2732                 else if (CONVERT_EXPR_CODE_P (code)
2733                          || code == FLOAT_EXPR
2734                          || code == FIX_TRUNC_EXPR)
2735                   {
2736                     int did_something = combine_conversions (&gsi);
2737                     if (did_something == 2)
2738                       cfg_changed = true;
2739                     changed = did_something != 0;
2740                   }
2741                 break;
2742               }
2743
2744             case GIMPLE_SWITCH:
2745               changed = simplify_gimple_switch (stmt);
2746               break;
2747
2748             case GIMPLE_COND:
2749               {
2750                 int did_something;
2751                 did_something = forward_propagate_into_gimple_cond (stmt);
2752                 if (did_something == 2)
2753                   cfg_changed = true;
2754                 changed = did_something != 0;
2755                 break;
2756               }
2757
2758             case GIMPLE_CALL:
2759               {
2760                 tree callee = gimple_call_fndecl (stmt);
2761                 if (callee != NULL_TREE
2762                     && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
2763                   changed = simplify_builtin_call (&gsi, callee);
2764                 break;
2765               }
2766
2767             default:;
2768             }
2769
2770           if (changed)
2771             {
2772               /* If the stmt changed then re-visit it and the statements
2773                  inserted before it.  */
2774               for (; !gsi_end_p (gsi); gsi_prev (&gsi))
2775                 if (gimple_plf (gsi_stmt (gsi), GF_PLF_1))
2776                   break;
2777               if (gsi_end_p (gsi))
2778                 gsi = gsi_start_bb (bb);
2779               else
2780                 gsi_next (&gsi);
2781             }
2782           else
2783             {
2784               /* Stmt no longer needs to be revisited.  */
2785               gimple_set_plf (stmt, GF_PLF_1, true);
2786               gsi_next (&gsi);
2787             }
2788         }
2789     }
2790
2791   if (cfg_changed)
2792     todoflags |= TODO_cleanup_cfg;
2793
2794   return todoflags;
2795 }
2796
2797
2798 static bool
2799 gate_forwprop (void)
2800 {
2801   return flag_tree_forwprop;
2802 }
2803
2804 struct gimple_opt_pass pass_forwprop =
2805 {
2806  {
2807   GIMPLE_PASS,
2808   "forwprop",                   /* name */
2809   gate_forwprop,                /* gate */
2810   ssa_forward_propagate_and_combine,    /* execute */
2811   NULL,                         /* sub */
2812   NULL,                         /* next */
2813   0,                            /* static_pass_number */
2814   TV_TREE_FORWPROP,             /* tv_id */
2815   PROP_cfg | PROP_ssa,          /* properties_required */
2816   0,                            /* properties_provided */
2817   0,                            /* properties_destroyed */
2818   0,                            /* todo_flags_start */
2819   TODO_ggc_collect
2820   | TODO_update_ssa
2821   | TODO_verify_ssa             /* todo_flags_finish */
2822  }
2823 };