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