gcc/tree-ssa-forwprop.c

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