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