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 /* Simplify bitwise binary operations.
1776    Return true if a transformation applied, otherwise return false.  */
1777
1778 static bool
1779 simplify_bitwise_binary (gimple_stmt_iterator *gsi)
1780 {
1781   gimple stmt = gsi_stmt (*gsi);
1782   tree arg1 = gimple_assign_rhs1 (stmt);
1783   tree arg2 = gimple_assign_rhs2 (stmt);
1784   enum tree_code code = gimple_assign_rhs_code (stmt);
1785   tree res;
1786   tree def1_arg1, def1_arg2, def2_arg1, def2_arg2;
1787   enum tree_code def1_code, def2_code;
1788
1789   defcodefor_name (arg1, &def1_code, &def1_arg1, &def1_arg2);
1790   defcodefor_name (arg2, &def2_code, &def2_arg1, &def2_arg2);
1791
1792   /* Try to fold (type) X op CST -> (type) (X op ((type-x) CST)).  */
1793   if (TREE_CODE (arg2) == INTEGER_CST
1794       && CONVERT_EXPR_CODE_P (def1_code)
1795       && INTEGRAL_TYPE_P (TREE_TYPE (def1_arg1))
1796       && int_fits_type_p (arg2, TREE_TYPE (def1_arg1)))
1797     {
1798       gimple newop;
1799       tree tem = make_ssa_name (TREE_TYPE (def1_arg1), NULL);
1800       newop =
1801         gimple_build_assign_with_ops (code, tem, def1_arg1,
1802                                       fold_convert_loc (gimple_location (stmt),
1803                                                         TREE_TYPE (def1_arg1),
1804                                                         arg2));
1805       gimple_set_location (newop, gimple_location (stmt));
1806       gsi_insert_before (gsi, newop, GSI_SAME_STMT);
1807       gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
1808                                         tem, NULL_TREE, NULL_TREE);
1809       update_stmt (gsi_stmt (*gsi));
1810       return true;
1811     }
1812
1813   /* For bitwise binary operations apply operand conversions to the
1814      binary operation result instead of to the operands.  This allows
1815      to combine successive conversions and bitwise binary operations.  */
1816   if (CONVERT_EXPR_CODE_P (def1_code)
1817       && CONVERT_EXPR_CODE_P (def2_code)
1818       && types_compatible_p (TREE_TYPE (def1_arg1), TREE_TYPE (def2_arg1))
1819       /* Make sure that the conversion widens the operands, or has same
1820          precision,  or that it changes the operation to a bitfield
1821          precision.  */
1822       && ((TYPE_PRECISION (TREE_TYPE (def1_arg1))
1823            <= TYPE_PRECISION (TREE_TYPE (arg1)))
1824           || (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (arg1)))
1825               != MODE_INT)
1826           || (TYPE_PRECISION (TREE_TYPE (arg1))
1827               != GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (arg1))))))
1828     {
1829       gimple newop;
1830       tree tem = make_ssa_name (TREE_TYPE (def1_arg1), NULL);
1831       newop = gimple_build_assign_with_ops (code, tem, def1_arg1, def2_arg1);
1832       gimple_set_location (newop, gimple_location (stmt));
1833       gsi_insert_before (gsi, newop, GSI_SAME_STMT);
1834       gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
1835                                         tem, NULL_TREE, NULL_TREE);
1836       update_stmt (gsi_stmt (*gsi));
1837       return true;
1838     }
1839
1840
1841    /* Simplify (A & B) OP0 (C & B) to (A OP0 C) & B. */
1842    if (def1_code == def2_code
1843        && def1_code == BIT_AND_EXPR
1844        && operand_equal_for_phi_arg_p (def1_arg2,
1845                                        def2_arg2))
1846     {
1847       tree b = def1_arg2;
1848       tree a = def1_arg1;
1849       tree c = def2_arg1;
1850       tree inner = fold_build2 (code, TREE_TYPE (arg2), a, c);
1851       /* If A OP0 C (this usually means C is the same as A) is 0
1852          then fold it down correctly. */
1853       if (integer_zerop (inner))
1854         {
1855           gimple_assign_set_rhs_from_tree (gsi, inner);
1856           update_stmt (stmt);
1857           return true;
1858         }
1859       /* If A OP0 C (this usually means C is the same as A) is a ssa_name
1860          then fold it down correctly. */
1861       else if (TREE_CODE (inner) == SSA_NAME)
1862         {
1863           tree outer = fold_build2 (def1_code, TREE_TYPE (inner),
1864                                     inner, b);
1865           gimple_assign_set_rhs_from_tree (gsi, outer);
1866           update_stmt (stmt);
1867           return true;
1868         }
1869       else
1870         {
1871           gimple newop;
1872           tree tem;
1873           tem = make_ssa_name (TREE_TYPE (arg2), NULL);
1874           newop = gimple_build_assign_with_ops (code, tem, a, c);
1875           gimple_set_location (newop, gimple_location (stmt));
1876           /* Make sure to re-process the new stmt as it's walking upwards.  */
1877           gsi_insert_before (gsi, newop, GSI_NEW_STMT);
1878           gimple_assign_set_rhs1 (stmt, tem);
1879           gimple_assign_set_rhs2 (stmt, b);
1880           gimple_assign_set_rhs_code (stmt, def1_code);
1881           update_stmt (stmt);
1882           return true;
1883         }
1884     }
1885
1886   /* (a | CST1) & CST2  ->  (a & CST2) | (CST1 & CST2).  */
1887   if (code == BIT_AND_EXPR
1888       && def1_code == BIT_IOR_EXPR
1889       && TREE_CODE (arg2) == INTEGER_CST
1890       && TREE_CODE (def1_arg2) == INTEGER_CST)
1891     {
1892       tree cst = fold_build2 (BIT_AND_EXPR, TREE_TYPE (arg2),
1893                               arg2, def1_arg2);
1894       tree tem;
1895       gimple newop;
1896       if (integer_zerop (cst))
1897         {
1898           gimple_assign_set_rhs1 (stmt, def1_arg1);
1899           update_stmt (stmt);
1900           return true;
1901         }
1902       tem = make_ssa_name (TREE_TYPE (arg2), NULL);
1903       newop = gimple_build_assign_with_ops (BIT_AND_EXPR,
1904                                             tem, def1_arg1, arg2);
1905       gimple_set_location (newop, gimple_location (stmt));
1906       /* Make sure to re-process the new stmt as it's walking upwards.  */
1907       gsi_insert_before (gsi, newop, GSI_NEW_STMT);
1908       gimple_assign_set_rhs1 (stmt, tem);
1909       gimple_assign_set_rhs2 (stmt, cst);
1910       gimple_assign_set_rhs_code (stmt, BIT_IOR_EXPR);
1911       update_stmt (stmt);
1912       return true;
1913     }
1914
1915   /* Combine successive equal operations with constants.  */
1916   if ((code == BIT_AND_EXPR
1917        || code == BIT_IOR_EXPR
1918        || code == BIT_XOR_EXPR)
1919       && def1_code == code
1920       && TREE_CODE (arg2) == INTEGER_CST
1921       && TREE_CODE (def1_arg2) == INTEGER_CST)
1922     {
1923       tree cst = fold_build2 (code, TREE_TYPE (arg2),
1924                               arg2, def1_arg2);
1925       gimple_assign_set_rhs1 (stmt, def1_arg1);
1926       gimple_assign_set_rhs2 (stmt, cst);
1927       update_stmt (stmt);
1928       return true;
1929     }
1930
1931   /* Canonicalize X ^ ~0 to ~X.  */
1932   if (code == BIT_XOR_EXPR
1933       && TREE_CODE (arg2) == INTEGER_CST
1934       && integer_all_onesp (arg2))
1935     {
1936       gimple_assign_set_rhs_with_ops (gsi, BIT_NOT_EXPR, arg1, NULL_TREE);
1937       gcc_assert (gsi_stmt (*gsi) == stmt);
1938       update_stmt (stmt);
1939       return true;
1940     }
1941
1942   /* Try simple folding for X op !X, and X op X.  */
1943   res = simplify_bitwise_binary_1 (code, TREE_TYPE (arg1), arg1, arg2);
1944   if (res != NULL_TREE)
1945     {
1946       gimple_assign_set_rhs_from_tree (gsi, res);
1947       update_stmt (gsi_stmt (*gsi));
1948       return true;
1949     }
1950
1951   if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
1952     {
1953       enum tree_code ocode = code == BIT_AND_EXPR ? BIT_IOR_EXPR : BIT_AND_EXPR;
1954       if (def1_code == ocode)
1955         {
1956           tree x = arg2;
1957           enum tree_code coden;
1958           tree a1, a2;
1959           /* ( X | Y) & X -> X */
1960           /* ( X & Y) | X -> X */
1961           if (x == def1_arg1
1962               || x == def1_arg2)
1963             {
1964               gimple_assign_set_rhs_from_tree (gsi, x);
1965               update_stmt (gsi_stmt (*gsi));
1966               return true;
1967             }
1968
1969           defcodefor_name (def1_arg1, &coden, &a1, &a2);
1970           /* (~X | Y) & X -> X & Y */
1971           /* (~X & Y) | X -> X | Y */
1972           if (coden == BIT_NOT_EXPR && a1 == x)
1973             {
1974               gimple_assign_set_rhs_with_ops (gsi, code,
1975                                               x, def1_arg2);
1976               gcc_assert (gsi_stmt (*gsi) == stmt);
1977               update_stmt (stmt);
1978               return true;
1979             }
1980           defcodefor_name (def1_arg2, &coden, &a1, &a2);
1981           /* (Y | ~X) & X -> X & Y */
1982           /* (Y & ~X) | X -> X | Y */
1983           if (coden == BIT_NOT_EXPR && a1 == x)
1984             {
1985               gimple_assign_set_rhs_with_ops (gsi, code,
1986                                               x, def1_arg1);
1987               gcc_assert (gsi_stmt (*gsi) == stmt);
1988               update_stmt (stmt);
1989               return true;
1990             }
1991         }
1992       if (def2_code == ocode)
1993         {
1994           enum tree_code coden;
1995           tree a1;
1996           tree x = arg1;
1997           /* X & ( X | Y) -> X */
1998           /* X | ( X & Y) -> X */
1999           if (x == def2_arg1
2000               || x == def2_arg2)
2001             {
2002               gimple_assign_set_rhs_from_tree (gsi, x);
2003               update_stmt (gsi_stmt (*gsi));
2004               return true;
2005             }
2006           defcodefor_name (def2_arg1, &coden, &a1, NULL);
2007           /* (~X | Y) & X -> X & Y */
2008           /* (~X & Y) | X -> X | Y */
2009           if (coden == BIT_NOT_EXPR && a1 == x)
2010             {
2011               gimple_assign_set_rhs_with_ops (gsi, code,
2012                                               x, def2_arg2);
2013               gcc_assert (gsi_stmt (*gsi) == stmt);
2014               update_stmt (stmt);
2015               return true;
2016             }
2017           defcodefor_name (def2_arg2, &coden, &a1, NULL);
2018           /* (Y | ~X) & X -> X & Y */
2019           /* (Y & ~X) | X -> X | Y */
2020           if (coden == BIT_NOT_EXPR && a1 == x)
2021             {
2022               gimple_assign_set_rhs_with_ops (gsi, code,
2023                                               x, def2_arg1);
2024               gcc_assert (gsi_stmt (*gsi) == stmt);
2025               update_stmt (stmt);
2026               return true;
2027             }
2028         }
2029     }
2030
2031   return false;
2032 }
2033
2034
2035 /* Perform re-associations of the plus or minus statement STMT that are
2036    always permitted.  Returns true if the CFG was changed.  */
2037
2038 static bool
2039 associate_plusminus (gimple_stmt_iterator *gsi)
2040 {
2041   gimple stmt = gsi_stmt (*gsi);
2042   tree rhs1 = gimple_assign_rhs1 (stmt);
2043   tree rhs2 = gimple_assign_rhs2 (stmt);
2044   enum tree_code code = gimple_assign_rhs_code (stmt);
2045   bool changed;
2046
2047   /* We can't reassociate at all for saturating types.  */
2048   if (TYPE_SATURATING (TREE_TYPE (rhs1)))
2049     return false;
2050
2051   /* First contract negates.  */
2052   do
2053     {
2054       changed = false;
2055
2056       /* A +- (-B) -> A -+ B.  */
2057       if (TREE_CODE (rhs2) == SSA_NAME)
2058         {
2059           gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
2060           if (is_gimple_assign (def_stmt)
2061               && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
2062               && can_propagate_from (def_stmt))
2063             {
2064               code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR;
2065               gimple_assign_set_rhs_code (stmt, code);
2066               rhs2 = gimple_assign_rhs1 (def_stmt);
2067               gimple_assign_set_rhs2 (stmt, rhs2);
2068               gimple_set_modified (stmt, true);
2069               changed = true;
2070             }
2071         }
2072
2073       /* (-A) + B -> B - A.  */
2074       if (TREE_CODE (rhs1) == SSA_NAME
2075           && code == PLUS_EXPR)
2076         {
2077           gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
2078           if (is_gimple_assign (def_stmt)
2079               && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
2080               && can_propagate_from (def_stmt))
2081             {
2082               code = MINUS_EXPR;
2083               gimple_assign_set_rhs_code (stmt, code);
2084               rhs1 = rhs2;
2085               gimple_assign_set_rhs1 (stmt, rhs1);
2086               rhs2 = gimple_assign_rhs1 (def_stmt);
2087               gimple_assign_set_rhs2 (stmt, rhs2);
2088               gimple_set_modified (stmt, true);
2089               changed = true;
2090             }
2091         }
2092     }
2093   while (changed);
2094
2095   /* We can't reassociate floating-point or fixed-point plus or minus
2096      because of saturation to +-Inf.  */
2097   if (FLOAT_TYPE_P (TREE_TYPE (rhs1))
2098       || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1)))
2099     goto out;
2100
2101   /* Second match patterns that allow contracting a plus-minus pair
2102      irrespective of overflow issues.
2103
2104         (A +- B) - A       ->  +- B
2105         (A +- B) -+ B      ->  A
2106         (CST +- A) +- CST  ->  CST +- A
2107         (A + CST) +- CST   ->  A + CST
2108         ~A + A             ->  -1
2109         ~A + 1             ->  -A
2110         A - (A +- B)       ->  -+ B
2111         A +- (B +- A)      ->  +- B
2112         CST +- (CST +- A)  ->  CST +- A
2113         CST +- (A +- CST)  ->  CST +- A
2114         A + ~A             ->  -1
2115
2116      via commutating the addition and contracting operations to zero
2117      by reassociation.  */
2118
2119   if (TREE_CODE (rhs1) == SSA_NAME)
2120     {
2121       gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
2122       if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
2123         {
2124           enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
2125           if (def_code == PLUS_EXPR
2126               || def_code == MINUS_EXPR)
2127             {
2128               tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2129               tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
2130               if (operand_equal_p (def_rhs1, rhs2, 0)
2131                   && code == MINUS_EXPR)
2132                 {
2133                   /* (A +- B) - A -> +- B.  */
2134                   code = ((def_code == PLUS_EXPR)
2135                           ? TREE_CODE (def_rhs2) : NEGATE_EXPR);
2136                   rhs1 = def_rhs2;
2137                   rhs2 = NULL_TREE;
2138                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2139                   gcc_assert (gsi_stmt (*gsi) == stmt);
2140                   gimple_set_modified (stmt, true);
2141                 }
2142               else if (operand_equal_p (def_rhs2, rhs2, 0)
2143                        && code != def_code)
2144                 {
2145                   /* (A +- B) -+ B -> A.  */
2146                   code = TREE_CODE (def_rhs1);
2147                   rhs1 = def_rhs1;
2148                   rhs2 = NULL_TREE;
2149                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2150                   gcc_assert (gsi_stmt (*gsi) == stmt);
2151                   gimple_set_modified (stmt, true);
2152                 }
2153               else if (TREE_CODE (rhs2) == INTEGER_CST
2154                        && TREE_CODE (def_rhs1) == INTEGER_CST)
2155                 {
2156                   /* (CST +- A) +- CST -> CST +- A.  */
2157                   tree cst = fold_binary (code, TREE_TYPE (rhs1),
2158                                           def_rhs1, rhs2);
2159                   if (cst && !TREE_OVERFLOW (cst))
2160                     {
2161                       code = def_code;
2162                       gimple_assign_set_rhs_code (stmt, code);
2163                       rhs1 = cst;
2164                       gimple_assign_set_rhs1 (stmt, rhs1);
2165                       rhs2 = def_rhs2;
2166                       gimple_assign_set_rhs2 (stmt, rhs2);
2167                       gimple_set_modified (stmt, true);
2168                     }
2169                 }
2170               else if (TREE_CODE (rhs2) == INTEGER_CST
2171                        && TREE_CODE (def_rhs2) == INTEGER_CST
2172                        && def_code == PLUS_EXPR)
2173                 {
2174                   /* (A + CST) +- CST -> A + CST.  */
2175                   tree cst = fold_binary (code, TREE_TYPE (rhs1),
2176                                           def_rhs2, rhs2);
2177                   if (cst && !TREE_OVERFLOW (cst))
2178                     {
2179                       code = PLUS_EXPR;
2180                       gimple_assign_set_rhs_code (stmt, code);
2181                       rhs1 = def_rhs1;
2182                       gimple_assign_set_rhs1 (stmt, rhs1);
2183                       rhs2 = cst;
2184                       gimple_assign_set_rhs2 (stmt, rhs2);
2185                       gimple_set_modified (stmt, true);
2186                     }
2187                 }
2188             }
2189           else if (def_code == BIT_NOT_EXPR
2190                    && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
2191             {
2192               tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2193               if (code == PLUS_EXPR
2194                   && operand_equal_p (def_rhs1, rhs2, 0))
2195                 {
2196                   /* ~A + A -> -1.  */
2197                   code = INTEGER_CST;
2198                   rhs1 = build_int_cst_type (TREE_TYPE (rhs2), -1);
2199                   rhs2 = NULL_TREE;
2200                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2201                   gcc_assert (gsi_stmt (*gsi) == stmt);
2202                   gimple_set_modified (stmt, true);
2203                 }
2204               else if (code == PLUS_EXPR
2205                        && integer_onep (rhs1))
2206                 {
2207                   /* ~A + 1 -> -A.  */
2208                   code = NEGATE_EXPR;
2209                   rhs1 = def_rhs1;
2210                   rhs2 = NULL_TREE;
2211                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2212                   gcc_assert (gsi_stmt (*gsi) == stmt);
2213                   gimple_set_modified (stmt, true);
2214                 }
2215             }
2216         }
2217     }
2218
2219   if (rhs2 && TREE_CODE (rhs2) == SSA_NAME)
2220     {
2221       gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
2222       if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
2223         {
2224           enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
2225           if (def_code == PLUS_EXPR
2226               || def_code == MINUS_EXPR)
2227             {
2228               tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2229               tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
2230               if (operand_equal_p (def_rhs1, rhs1, 0)
2231                   && code == MINUS_EXPR)
2232                 {
2233                   /* A - (A +- B) -> -+ B.  */
2234                   code = ((def_code == PLUS_EXPR)
2235                           ? NEGATE_EXPR : TREE_CODE (def_rhs2));
2236                   rhs1 = def_rhs2;
2237                   rhs2 = NULL_TREE;
2238                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2239                   gcc_assert (gsi_stmt (*gsi) == stmt);
2240                   gimple_set_modified (stmt, true);
2241                 }
2242               else if (operand_equal_p (def_rhs2, rhs1, 0)
2243                        && code != def_code)
2244                 {
2245                   /* A +- (B +- A) -> +- B.  */
2246                   code = ((code == PLUS_EXPR)
2247                           ? TREE_CODE (def_rhs1) : NEGATE_EXPR);
2248                   rhs1 = def_rhs1;
2249                   rhs2 = NULL_TREE;
2250                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2251                   gcc_assert (gsi_stmt (*gsi) == stmt);
2252                   gimple_set_modified (stmt, true);
2253                 }
2254               else if (TREE_CODE (rhs1) == INTEGER_CST
2255                        && TREE_CODE (def_rhs1) == INTEGER_CST)
2256                 {
2257                   /* CST +- (CST +- A) -> CST +- A.  */
2258                   tree cst = fold_binary (code, TREE_TYPE (rhs2),
2259                                           rhs1, def_rhs1);
2260                   if (cst && !TREE_OVERFLOW (cst))
2261                     {
2262                       code = (code == def_code ? PLUS_EXPR : MINUS_EXPR);
2263                       gimple_assign_set_rhs_code (stmt, code);
2264                       rhs1 = cst;
2265                       gimple_assign_set_rhs1 (stmt, rhs1);
2266                       rhs2 = def_rhs2;
2267                       gimple_assign_set_rhs2 (stmt, rhs2);
2268                       gimple_set_modified (stmt, true);
2269                     }
2270                 }
2271               else if (TREE_CODE (rhs1) == INTEGER_CST
2272                        && TREE_CODE (def_rhs2) == INTEGER_CST)
2273                 {
2274                   /* CST +- (A +- CST) -> CST +- A.  */
2275                   tree cst = fold_binary (def_code == code
2276                                           ? PLUS_EXPR : MINUS_EXPR,
2277                                           TREE_TYPE (rhs2),
2278                                           rhs1, def_rhs2);
2279                   if (cst && !TREE_OVERFLOW (cst))
2280                     {
2281                       rhs1 = cst;
2282                       gimple_assign_set_rhs1 (stmt, rhs1);
2283                       rhs2 = def_rhs1;
2284                       gimple_assign_set_rhs2 (stmt, rhs2);
2285                       gimple_set_modified (stmt, true);
2286                     }
2287                 }
2288             }
2289           else if (def_code == BIT_NOT_EXPR
2290                    && INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
2291             {
2292               tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2293               if (code == PLUS_EXPR
2294                   && operand_equal_p (def_rhs1, rhs1, 0))
2295                 {
2296                   /* A + ~A -> -1.  */
2297                   code = INTEGER_CST;
2298                   rhs1 = build_int_cst_type (TREE_TYPE (rhs1), -1);
2299                   rhs2 = NULL_TREE;
2300                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2301                   gcc_assert (gsi_stmt (*gsi) == stmt);
2302                   gimple_set_modified (stmt, true);
2303                 }
2304             }
2305         }
2306     }
2307
2308 out:
2309   if (gimple_modified_p (stmt))
2310     {
2311       fold_stmt_inplace (gsi);
2312       update_stmt (stmt);
2313       if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
2314           && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
2315         return true;
2316     }
2317
2318   return false;
2319 }
2320
2321 /* Associate operands of a POINTER_PLUS_EXPR assignmen at *GSI.  Returns
2322    true if anything changed, false otherwise.  */
2323
2324 static bool
2325 associate_pointerplus (gimple_stmt_iterator *gsi)
2326 {
2327   gimple stmt = gsi_stmt (*gsi);
2328   gimple def_stmt;
2329   tree ptr, rhs, algn;
2330
2331   /* Pattern match
2332        tem = (sizetype) ptr;
2333        tem = tem & algn;
2334        tem = -tem;
2335        ... = ptr p+ tem;
2336      and produce the simpler and easier to analyze with respect to alignment
2337        ... = ptr & ~algn;  */
2338   ptr = gimple_assign_rhs1 (stmt);
2339   rhs = gimple_assign_rhs2 (stmt);
2340   if (TREE_CODE (rhs) != SSA_NAME)
2341     return false;
2342   def_stmt = SSA_NAME_DEF_STMT (rhs);
2343   if (!is_gimple_assign (def_stmt)
2344       || gimple_assign_rhs_code (def_stmt) != NEGATE_EXPR)
2345     return false;
2346   rhs = gimple_assign_rhs1 (def_stmt);
2347   if (TREE_CODE (rhs) != SSA_NAME)
2348     return false;
2349   def_stmt = SSA_NAME_DEF_STMT (rhs);
2350   if (!is_gimple_assign (def_stmt)
2351       || gimple_assign_rhs_code (def_stmt) != BIT_AND_EXPR)
2352     return false;
2353   rhs = gimple_assign_rhs1 (def_stmt);
2354   algn = gimple_assign_rhs2 (def_stmt);
2355   if (TREE_CODE (rhs) != SSA_NAME
2356       || TREE_CODE (algn) != INTEGER_CST)
2357     return false;
2358   def_stmt = SSA_NAME_DEF_STMT (rhs);
2359   if (!is_gimple_assign (def_stmt)
2360       || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
2361     return false;
2362   if (gimple_assign_rhs1 (def_stmt) != ptr)
2363     return false;
2364
2365   algn = double_int_to_tree (TREE_TYPE (ptr), ~tree_to_double_int (algn));
2366   gimple_assign_set_rhs_with_ops (gsi, BIT_AND_EXPR, ptr, algn);
2367   fold_stmt_inplace (gsi);
2368   update_stmt (stmt);
2369
2370   return true;
2371 }
2372
2373 /* Combine two conversions in a row for the second conversion at *GSI.
2374    Returns 1 if there were any changes made, 2 if cfg-cleanup needs to
2375    run.  Else it returns 0.  */
2376
2377 static int
2378 combine_conversions (gimple_stmt_iterator *gsi)
2379 {
2380   gimple stmt = gsi_stmt (*gsi);
2381   gimple def_stmt;
2382   tree op0, lhs;
2383   enum tree_code code = gimple_assign_rhs_code (stmt);
2384   enum tree_code code2;
2385
2386   gcc_checking_assert (CONVERT_EXPR_CODE_P (code)
2387                        || code == FLOAT_EXPR
2388                        || code == FIX_TRUNC_EXPR);
2389
2390   lhs = gimple_assign_lhs (stmt);
2391   op0 = gimple_assign_rhs1 (stmt);
2392   if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (op0)))
2393     {
2394       gimple_assign_set_rhs_code (stmt, TREE_CODE (op0));
2395       return 1;
2396     }
2397
2398   if (TREE_CODE (op0) != SSA_NAME)
2399     return 0;
2400
2401   def_stmt = SSA_NAME_DEF_STMT (op0);
2402   if (!is_gimple_assign (def_stmt))
2403     return 0;
2404
2405   code2 = gimple_assign_rhs_code (def_stmt);
2406
2407   if (CONVERT_EXPR_CODE_P (code2) || code2 == FLOAT_EXPR)
2408     {
2409       tree defop0 = gimple_assign_rhs1 (def_stmt);
2410       tree type = TREE_TYPE (lhs);
2411       tree inside_type = TREE_TYPE (defop0);
2412       tree inter_type = TREE_TYPE (op0);
2413       int inside_int = INTEGRAL_TYPE_P (inside_type);
2414       int inside_ptr = POINTER_TYPE_P (inside_type);
2415       int inside_float = FLOAT_TYPE_P (inside_type);
2416       int inside_vec = TREE_CODE (inside_type) == VECTOR_TYPE;
2417       unsigned int inside_prec = TYPE_PRECISION (inside_type);
2418       int inside_unsignedp = TYPE_UNSIGNED (inside_type);
2419       int inter_int = INTEGRAL_TYPE_P (inter_type);
2420       int inter_ptr = POINTER_TYPE_P (inter_type);
2421       int inter_float = FLOAT_TYPE_P (inter_type);
2422       int inter_vec = TREE_CODE (inter_type) == VECTOR_TYPE;
2423       unsigned int inter_prec = TYPE_PRECISION (inter_type);
2424       int inter_unsignedp = TYPE_UNSIGNED (inter_type);
2425       int final_int = INTEGRAL_TYPE_P (type);
2426       int final_ptr = POINTER_TYPE_P (type);
2427       int final_float = FLOAT_TYPE_P (type);
2428       int final_vec = TREE_CODE (type) == VECTOR_TYPE;
2429       unsigned int final_prec = TYPE_PRECISION (type);
2430       int final_unsignedp = TYPE_UNSIGNED (type);
2431
2432       /* Don't propagate ssa names that occur in abnormal phis.  */
2433       if (TREE_CODE (defop0) == SSA_NAME
2434           && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defop0))
2435         return 0;
2436
2437       /* In addition to the cases of two conversions in a row
2438          handled below, if we are converting something to its own
2439          type via an object of identical or wider precision, neither
2440          conversion is needed.  */
2441       if (useless_type_conversion_p (type, inside_type)
2442           && (((inter_int || inter_ptr) && final_int)
2443               || (inter_float && final_float))
2444           && inter_prec >= final_prec)
2445         {
2446           gimple_assign_set_rhs1 (stmt, unshare_expr (defop0));
2447           gimple_assign_set_rhs_code (stmt, TREE_CODE (defop0));
2448           update_stmt (stmt);
2449           return remove_prop_source_from_use (op0) ? 2 : 1;
2450         }
2451
2452       /* Likewise, if the intermediate and initial types are either both
2453          float or both integer, we don't need the middle conversion if the
2454          former is wider than the latter and doesn't change the signedness
2455          (for integers).  Avoid this if the final type is a pointer since
2456          then we sometimes need the middle conversion.  Likewise if the
2457          final type has a precision not equal to the size of its mode.  */
2458       if (((inter_int && inside_int)
2459            || (inter_float && inside_float)
2460            || (inter_vec && inside_vec))
2461           && inter_prec >= inside_prec
2462           && (inter_float || inter_vec
2463               || inter_unsignedp == inside_unsignedp)
2464           && ! (final_prec != GET_MODE_PRECISION (TYPE_MODE (type))
2465                 && TYPE_MODE (type) == TYPE_MODE (inter_type))
2466           && ! final_ptr
2467           && (! final_vec || inter_prec == inside_prec))
2468         {
2469           gimple_assign_set_rhs1 (stmt, defop0);
2470           update_stmt (stmt);
2471           return remove_prop_source_from_use (op0) ? 2 : 1;
2472         }
2473
2474       /* If we have a sign-extension of a zero-extended value, we can
2475          replace that by a single zero-extension.  Likewise if the
2476          final conversion does not change precision we can drop the
2477          intermediate conversion.  */
2478       if (inside_int && inter_int && final_int
2479           && ((inside_prec < inter_prec && inter_prec < final_prec
2480                && inside_unsignedp && !inter_unsignedp)
2481               || final_prec == inter_prec))
2482         {
2483           gimple_assign_set_rhs1 (stmt, defop0);
2484           update_stmt (stmt);
2485           return remove_prop_source_from_use (op0) ? 2 : 1;
2486         }
2487
2488       /* Two conversions in a row are not needed unless:
2489          - some conversion is floating-point (overstrict for now), or
2490          - some conversion is a vector (overstrict for now), or
2491          - the intermediate type is narrower than both initial and
2492          final, or
2493          - the intermediate type and innermost type differ in signedness,
2494          and the outermost type is wider than the intermediate, or
2495          - the initial type is a pointer type and the precisions of the
2496          intermediate and final types differ, or
2497          - the final type is a pointer type and the precisions of the
2498          initial and intermediate types differ.  */
2499       if (! inside_float && ! inter_float && ! final_float
2500           && ! inside_vec && ! inter_vec && ! final_vec
2501           && (inter_prec >= inside_prec || inter_prec >= final_prec)
2502           && ! (inside_int && inter_int
2503                 && inter_unsignedp != inside_unsignedp
2504                 && inter_prec < final_prec)
2505           && ((inter_unsignedp && inter_prec > inside_prec)
2506               == (final_unsignedp && final_prec > inter_prec))
2507           && ! (inside_ptr && inter_prec != final_prec)
2508           && ! (final_ptr && inside_prec != inter_prec)
2509           && ! (final_prec != GET_MODE_PRECISION (TYPE_MODE (type))
2510                 && TYPE_MODE (type) == TYPE_MODE (inter_type)))
2511         {
2512           gimple_assign_set_rhs1 (stmt, defop0);
2513           update_stmt (stmt);
2514           return remove_prop_source_from_use (op0) ? 2 : 1;
2515         }
2516
2517       /* A truncation to an unsigned type should be canonicalized as
2518          bitwise and of a mask.  */
2519       if (final_int && inter_int && inside_int
2520           && final_prec == inside_prec
2521           && final_prec > inter_prec
2522           && inter_unsignedp)
2523         {
2524           tree tem;
2525           tem = fold_build2 (BIT_AND_EXPR, inside_type,
2526                              defop0,
2527                              double_int_to_tree
2528                                (inside_type, double_int::mask (inter_prec)));
2529           if (!useless_type_conversion_p (type, inside_type))
2530             {
2531               tem = force_gimple_operand_gsi (gsi, tem, true, NULL_TREE, true,
2532                                               GSI_SAME_STMT);
2533               gimple_assign_set_rhs1 (stmt, tem);
2534             }
2535           else
2536             gimple_assign_set_rhs_from_tree (gsi, tem);
2537           update_stmt (gsi_stmt (*gsi));
2538           return 1;
2539         }
2540
2541       /* If we are converting an integer to a floating-point that can
2542          represent it exactly and back to an integer, we can skip the
2543          floating-point conversion.  */
2544       if (inside_int && inter_float && final_int &&
2545           (unsigned) significand_size (TYPE_MODE (inter_type))
2546           >= inside_prec - !inside_unsignedp)
2547         {
2548           if (useless_type_conversion_p (type, inside_type))
2549             {
2550               gimple_assign_set_rhs1 (stmt, unshare_expr (defop0));
2551               gimple_assign_set_rhs_code (stmt, TREE_CODE (defop0));
2552               update_stmt (stmt);
2553               return remove_prop_source_from_use (op0) ? 2 : 1;
2554             }
2555           else
2556             {
2557               gimple_assign_set_rhs1 (stmt, defop0);
2558               gimple_assign_set_rhs_code (stmt, CONVERT_EXPR);
2559               update_stmt (stmt);
2560               return remove_prop_source_from_use (op0) ? 2 : 1;
2561             }
2562         }
2563     }
2564
2565   return 0;
2566 }
2567
2568 /* Combine an element access with a shuffle.  Returns true if there were
2569    any changes made, else it returns false.  */
2570
2571 static bool
2572 simplify_bitfield_ref (gimple_stmt_iterator *gsi)
2573 {
2574   gimple stmt = gsi_stmt (*gsi);
2575   gimple def_stmt;
2576   tree op, op0, op1, op2;
2577   tree elem_type;
2578   unsigned idx, n, size;
2579   enum tree_code code;
2580
2581   op = gimple_assign_rhs1 (stmt);
2582   gcc_checking_assert (TREE_CODE (op) == BIT_FIELD_REF);
2583
2584   op0 = TREE_OPERAND (op, 0);
2585   if (TREE_CODE (op0) != SSA_NAME
2586       || TREE_CODE (TREE_TYPE (op0)) != VECTOR_TYPE)
2587     return false;
2588
2589   def_stmt = get_prop_source_stmt (op0, false, NULL);
2590   if (!def_stmt || !can_propagate_from (def_stmt))
2591     return false;
2592
2593   op1 = TREE_OPERAND (op, 1);
2594   op2 = TREE_OPERAND (op, 2);
2595   code = gimple_assign_rhs_code (def_stmt);
2596
2597   if (code == CONSTRUCTOR)
2598     {
2599       tree tem = fold_ternary (BIT_FIELD_REF, TREE_TYPE (op),
2600                                gimple_assign_rhs1 (def_stmt), op1, op2);
2601       if (!tem || !valid_gimple_rhs_p (tem))
2602         return false;
2603       gimple_assign_set_rhs_from_tree (gsi, tem);
2604       update_stmt (gsi_stmt (*gsi));
2605       return true;
2606     }
2607
2608   elem_type = TREE_TYPE (TREE_TYPE (op0));
2609   if (TREE_TYPE (op) != elem_type)
2610     return false;
2611
2612   size = TREE_INT_CST_LOW (TYPE_SIZE (elem_type));
2613   n = TREE_INT_CST_LOW (op1) / size;
2614   if (n != 1)
2615     return false;
2616   idx = TREE_INT_CST_LOW (op2) / size;
2617
2618   if (code == VEC_PERM_EXPR)
2619     {
2620       tree p, m, index, tem;
2621       unsigned nelts;
2622       m = gimple_assign_rhs3 (def_stmt);
2623       if (TREE_CODE (m) != VECTOR_CST)
2624         return false;
2625       nelts = VECTOR_CST_NELTS (m);
2626       idx = TREE_INT_CST_LOW (VECTOR_CST_ELT (m, idx));
2627       idx %= 2 * nelts;
2628       if (idx < nelts)
2629         {
2630           p = gimple_assign_rhs1 (def_stmt);
2631         }
2632       else
2633         {
2634           p = gimple_assign_rhs2 (def_stmt);
2635           idx -= nelts;
2636         }
2637       index = build_int_cst (TREE_TYPE (TREE_TYPE (m)), idx * size);
2638       tem = build3 (BIT_FIELD_REF, TREE_TYPE (op),
2639                     unshare_expr (p), op1, index);
2640       gimple_assign_set_rhs1 (stmt, tem);
2641       fold_stmt (gsi);
2642       update_stmt (gsi_stmt (*gsi));
2643       return true;
2644     }
2645
2646   return false;
2647 }
2648
2649 /* Determine whether applying the 2 permutations (mask1 then mask2)
2650    gives back one of the input.  */
2651
2652 static int
2653 is_combined_permutation_identity (tree mask1, tree mask2)
2654 {
2655   tree mask;
2656   unsigned int nelts, i, j;
2657   bool maybe_identity1 = true;
2658   bool maybe_identity2 = true;
2659
2660   gcc_checking_assert (TREE_CODE (mask1) == VECTOR_CST
2661                        && TREE_CODE (mask2) == VECTOR_CST);
2662   mask = fold_ternary (VEC_PERM_EXPR, TREE_TYPE (mask1), mask1, mask1, mask2);
2663   gcc_assert (TREE_CODE (mask) == VECTOR_CST);
2664
2665   nelts = VECTOR_CST_NELTS (mask);
2666   for (i = 0; i < nelts; i++)
2667     {
2668       tree val = VECTOR_CST_ELT (mask, i);
2669       gcc_assert (TREE_CODE (val) == INTEGER_CST);
2670       j = TREE_INT_CST_LOW (val) & (2 * nelts - 1);
2671       if (j == i)
2672         maybe_identity2 = false;
2673       else if (j == i + nelts)
2674         maybe_identity1 = false;
2675       else
2676         return 0;
2677     }
2678   return maybe_identity1 ? 1 : maybe_identity2 ? 2 : 0;
2679 }
2680
2681 /* Combine a shuffle with its arguments.  Returns 1 if there were any
2682    changes made, 2 if cfg-cleanup needs to run.  Else it returns 0.  */
2683
2684 static int
2685 simplify_permutation (gimple_stmt_iterator *gsi)
2686 {
2687   gimple stmt = gsi_stmt (*gsi);
2688   gimple def_stmt;
2689   tree op0, op1, op2, op3, arg0, arg1;
2690   enum tree_code code;
2691   bool single_use_op0 = false;
2692
2693   gcc_checking_assert (gimple_assign_rhs_code (stmt) == VEC_PERM_EXPR);
2694
2695   op0 = gimple_assign_rhs1 (stmt);
2696   op1 = gimple_assign_rhs2 (stmt);
2697   op2 = gimple_assign_rhs3 (stmt);
2698
2699   if (TREE_CODE (op2) != VECTOR_CST)
2700     return 0;
2701
2702   if (TREE_CODE (op0) == VECTOR_CST)
2703     {
2704       code = VECTOR_CST;
2705       arg0 = op0;
2706     }
2707   else if (TREE_CODE (op0) == SSA_NAME)
2708     {
2709       def_stmt = get_prop_source_stmt (op0, false, &single_use_op0);
2710       if (!def_stmt || !can_propagate_from (def_stmt))
2711         return 0;
2712
2713       code = gimple_assign_rhs_code (def_stmt);
2714       arg0 = gimple_assign_rhs1 (def_stmt);
2715     }
2716   else
2717     return 0;
2718
2719   /* Two consecutive shuffles.  */
2720   if (code == VEC_PERM_EXPR)
2721     {
2722       tree orig;
2723       int ident;
2724
2725       if (op0 != op1)
2726         return 0;
2727       op3 = gimple_assign_rhs3 (def_stmt);
2728       if (TREE_CODE (op3) != VECTOR_CST)
2729         return 0;
2730       ident = is_combined_permutation_identity (op3, op2);
2731       if (!ident)
2732         return 0;
2733       orig = (ident == 1) ? gimple_assign_rhs1 (def_stmt)
2734                           : gimple_assign_rhs2 (def_stmt);
2735       gimple_assign_set_rhs1 (stmt, unshare_expr (orig));
2736       gimple_assign_set_rhs_code (stmt, TREE_CODE (orig));
2737       gimple_set_num_ops (stmt, 2);
2738       update_stmt (stmt);
2739       return remove_prop_source_from_use (op0) ? 2 : 1;
2740     }
2741
2742   /* Shuffle of a constructor.  */
2743   else if (code == CONSTRUCTOR || code == VECTOR_CST)
2744     {
2745       tree opt;
2746       bool ret = false;
2747       if (op0 != op1)
2748         {
2749           if (TREE_CODE (op0) == SSA_NAME && !single_use_op0)
2750             return 0;
2751
2752           if (TREE_CODE (op1) == VECTOR_CST)
2753             arg1 = op1;
2754           else if (TREE_CODE (op1) == SSA_NAME)
2755             {
2756               enum tree_code code2;
2757
2758               gimple def_stmt2 = get_prop_source_stmt (op1, true, NULL);
2759               if (!def_stmt2 || !can_propagate_from (def_stmt2))
2760                 return 0;
2761
2762               code2 = gimple_assign_rhs_code (def_stmt2);
2763               if (code2 != CONSTRUCTOR && code2 != VECTOR_CST)
2764                 return 0;
2765               arg1 = gimple_assign_rhs1 (def_stmt2);
2766             }
2767           else
2768             return 0;
2769         }
2770       else
2771         {
2772           /* Already used twice in this statement.  */
2773           if (TREE_CODE (op0) == SSA_NAME && num_imm_uses (op0) > 2)
2774             return 0;
2775           arg1 = arg0;
2776         }
2777       opt = fold_ternary (VEC_PERM_EXPR, TREE_TYPE(op0), arg0, arg1, op2);
2778       if (!opt
2779           || (TREE_CODE (opt) != CONSTRUCTOR && TREE_CODE(opt) != VECTOR_CST))
2780         return 0;
2781       gimple_assign_set_rhs_from_tree (gsi, opt);
2782       update_stmt (gsi_stmt (*gsi));
2783       if (TREE_CODE (op0) == SSA_NAME)
2784         ret = remove_prop_source_from_use (op0);
2785       if (op0 != op1 && TREE_CODE (op1) == SSA_NAME)
2786         ret |= remove_prop_source_from_use (op1);
2787       return ret ? 2 : 1;
2788     }
2789
2790   return 0;
2791 }
2792
2793 /* Recognize a VEC_PERM_EXPR.  Returns true if there were any changes.  */
2794
2795 static bool
2796 simplify_vector_constructor (gimple_stmt_iterator *gsi)
2797 {
2798   gimple stmt = gsi_stmt (*gsi);
2799   gimple def_stmt;
2800   tree op, op2, orig, type, elem_type;
2801   unsigned elem_size, nelts, i;
2802   enum tree_code code;
2803   constructor_elt *elt;
2804   unsigned char *sel;
2805   bool maybe_ident;
2806
2807   gcc_checking_assert (gimple_assign_rhs_code (stmt) == CONSTRUCTOR);
2808
2809   op = gimple_assign_rhs1 (stmt);
2810   type = TREE_TYPE (op);
2811   gcc_checking_assert (TREE_CODE (type) == VECTOR_TYPE);
2812
2813   nelts = TYPE_VECTOR_SUBPARTS (type);
2814   elem_type = TREE_TYPE (type);
2815   elem_size = TREE_INT_CST_LOW (TYPE_SIZE (elem_type));
2816
2817   sel = XALLOCAVEC (unsigned char, nelts);
2818   orig = NULL;
2819   maybe_ident = true;
2820   FOR_EACH_VEC_SAFE_ELT (CONSTRUCTOR_ELTS (op), i, elt)
2821     {
2822       tree ref, op1;
2823
2824       if (i >= nelts)
2825         return false;
2826
2827       if (TREE_CODE (elt->value) != SSA_NAME)
2828         return false;
2829       def_stmt = get_prop_source_stmt (elt->value, false, NULL);
2830       if (!def_stmt)
2831         return false;
2832       code = gimple_assign_rhs_code (def_stmt);
2833       if (code != BIT_FIELD_REF)
2834         return false;
2835       op1 = gimple_assign_rhs1 (def_stmt);
2836       ref = TREE_OPERAND (op1, 0);
2837       if (orig)
2838         {
2839           if (ref != orig)
2840             return false;
2841         }
2842       else
2843         {
2844           if (TREE_CODE (ref) != SSA_NAME)
2845             return false;
2846           if (!useless_type_conversion_p (type, TREE_TYPE (ref)))
2847             return false;
2848           orig = ref;
2849         }
2850       if (TREE_INT_CST_LOW (TREE_OPERAND (op1, 1)) != elem_size)
2851         return false;
2852       sel[i] = TREE_INT_CST_LOW (TREE_OPERAND (op1, 2)) / elem_size;
2853       if (sel[i] != i) maybe_ident = false;
2854     }
2855   if (i < nelts)
2856     return false;
2857
2858   if (maybe_ident)
2859     gimple_assign_set_rhs_from_tree (gsi, orig);
2860   else
2861     {
2862       tree mask_type, *mask_elts;
2863
2864       if (!can_vec_perm_p (TYPE_MODE (type), false, sel))
2865         return false;
2866       mask_type
2867         = build_vector_type (build_nonstandard_integer_type (elem_size, 1),
2868                              nelts);
2869       if (GET_MODE_CLASS (TYPE_MODE (mask_type)) != MODE_VECTOR_INT
2870           || GET_MODE_SIZE (TYPE_MODE (mask_type))
2871              != GET_MODE_SIZE (TYPE_MODE (type)))
2872         return false;
2873       mask_elts = XALLOCAVEC (tree, nelts);
2874       for (i = 0; i < nelts; i++)
2875         mask_elts[i] = build_int_cst (TREE_TYPE (mask_type), sel[i]);
2876       op2 = build_vector (mask_type, mask_elts);
2877       gimple_assign_set_rhs_with_ops_1 (gsi, VEC_PERM_EXPR, orig, orig, op2);
2878     }
2879   update_stmt (gsi_stmt (*gsi));
2880   return true;
2881 }
2882
2883 /* Main entry point for the forward propagation and statement combine
2884    optimizer.  */
2885
2886 static unsigned int
2887 ssa_forward_propagate_and_combine (void)
2888 {
2889   basic_block bb;
2890   unsigned int todoflags = 0;
2891
2892   cfg_changed = false;
2893
2894   FOR_EACH_BB (bb)
2895     {
2896       gimple_stmt_iterator gsi;
2897
2898       /* Apply forward propagation to all stmts in the basic-block.
2899          Note we update GSI within the loop as necessary.  */
2900       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2901         {
2902           gimple stmt = gsi_stmt (gsi);
2903           tree lhs, rhs;
2904           enum tree_code code;
2905
2906           if (!is_gimple_assign (stmt))
2907             {
2908               gsi_next (&gsi);
2909               continue;
2910             }
2911
2912           lhs = gimple_assign_lhs (stmt);
2913           rhs = gimple_assign_rhs1 (stmt);
2914           code = gimple_assign_rhs_code (stmt);
2915           if (TREE_CODE (lhs) != SSA_NAME
2916               || has_zero_uses (lhs))
2917             {
2918               gsi_next (&gsi);
2919               continue;
2920             }
2921
2922           /* If this statement sets an SSA_NAME to an address,
2923              try to propagate the address into the uses of the SSA_NAME.  */
2924           if (code == ADDR_EXPR
2925               /* Handle pointer conversions on invariant addresses
2926                  as well, as this is valid gimple.  */
2927               || (CONVERT_EXPR_CODE_P (code)
2928                   && TREE_CODE (rhs) == ADDR_EXPR
2929                   && POINTER_TYPE_P (TREE_TYPE (lhs))))
2930             {
2931               tree base = get_base_address (TREE_OPERAND (rhs, 0));
2932               if ((!base
2933                    || !DECL_P (base)
2934                    || decl_address_invariant_p (base))
2935                   && !stmt_references_abnormal_ssa_name (stmt)
2936                   && forward_propagate_addr_expr (lhs, rhs))
2937                 {
2938                   release_defs (stmt);
2939                   gsi_remove (&gsi, true);
2940                 }
2941               else
2942                 gsi_next (&gsi);
2943             }
2944           else if (code == POINTER_PLUS_EXPR)
2945             {
2946               tree off = gimple_assign_rhs2 (stmt);
2947               if (TREE_CODE (off) == INTEGER_CST
2948                   && can_propagate_from (stmt)
2949                   && !simple_iv_increment_p (stmt)
2950                   /* ???  Better adjust the interface to that function
2951                      instead of building new trees here.  */
2952                   && forward_propagate_addr_expr
2953                        (lhs,
2954                         build1_loc (gimple_location (stmt),
2955                                     ADDR_EXPR, TREE_TYPE (rhs),
2956                                     fold_build2 (MEM_REF,
2957                                                  TREE_TYPE (TREE_TYPE (rhs)),
2958                                                  rhs,
2959                                                  fold_convert (ptr_type_node,
2960                                                                off)))))
2961                 {
2962                   release_defs (stmt);
2963                   gsi_remove (&gsi, true);
2964                 }
2965               else if (is_gimple_min_invariant (rhs))
2966                 {
2967                   /* Make sure to fold &a[0] + off_1 here.  */
2968                   fold_stmt_inplace (&gsi);
2969                   update_stmt (stmt);
2970                   if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
2971                     gsi_next (&gsi);
2972                 }
2973               else
2974                 gsi_next (&gsi);
2975             }
2976           else if (TREE_CODE_CLASS (code) == tcc_comparison)
2977             {
2978               if (forward_propagate_comparison (&gsi))
2979                 cfg_changed = true;
2980             }
2981           else
2982             gsi_next (&gsi);
2983         }
2984
2985       /* Combine stmts with the stmts defining their operands.
2986          Note we update GSI within the loop as necessary.  */
2987       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
2988         {
2989           gimple stmt = gsi_stmt (gsi);
2990           bool changed = false;
2991
2992           /* Mark stmt as potentially needing revisiting.  */
2993           gimple_set_plf (stmt, GF_PLF_1, false);
2994
2995           switch (gimple_code (stmt))
2996             {
2997             case GIMPLE_ASSIGN:
2998               {
2999                 tree rhs1 = gimple_assign_rhs1 (stmt);
3000                 enum tree_code code = gimple_assign_rhs_code (stmt);
3001
3002                 if ((code == BIT_NOT_EXPR
3003                      || code == NEGATE_EXPR)
3004                     && TREE_CODE (rhs1) == SSA_NAME)
3005                   changed = simplify_not_neg_expr (&gsi);
3006                 else if (code == COND_EXPR
3007                          || code == VEC_COND_EXPR)
3008                   {
3009                     /* In this case the entire COND_EXPR is in rhs1. */
3010                     if (forward_propagate_into_cond (&gsi)
3011                         || combine_cond_exprs (&gsi))
3012                       {
3013                         changed = true;
3014                         stmt = gsi_stmt (gsi);
3015                       }
3016                   }
3017                 else if (TREE_CODE_CLASS (code) == tcc_comparison)
3018                   {
3019                     int did_something;
3020                     did_something = forward_propagate_into_comparison (&gsi);
3021                     if (did_something == 2)
3022                       cfg_changed = true;
3023                     changed = did_something != 0;
3024                   }
3025                 else if (code == BIT_AND_EXPR
3026                          || code == BIT_IOR_EXPR
3027                          || code == BIT_XOR_EXPR)
3028                   changed = simplify_bitwise_binary (&gsi);
3029                 else if (code == PLUS_EXPR
3030                          || code == MINUS_EXPR)
3031                   changed = associate_plusminus (&gsi);
3032                 else if (code == POINTER_PLUS_EXPR)
3033                   changed = associate_pointerplus (&gsi);
3034                 else if (CONVERT_EXPR_CODE_P (code)
3035                          || code == FLOAT_EXPR
3036                          || code == FIX_TRUNC_EXPR)
3037                   {
3038                     int did_something = combine_conversions (&gsi);
3039                     if (did_something == 2)
3040                       cfg_changed = true;
3041                     changed = did_something != 0;
3042                   }
3043                 else if (code == VEC_PERM_EXPR)
3044                   {
3045                     int did_something = simplify_permutation (&gsi);
3046                     if (did_something == 2)
3047                       cfg_changed = true;
3048                     changed = did_something != 0;
3049                   }
3050                 else if (code == BIT_FIELD_REF)
3051                   changed = simplify_bitfield_ref (&gsi);
3052                 else if (code == CONSTRUCTOR
3053                          && TREE_CODE (TREE_TYPE (rhs1)) == VECTOR_TYPE)
3054                   changed = simplify_vector_constructor (&gsi);
3055                 break;
3056               }
3057
3058             case GIMPLE_SWITCH:
3059               changed = simplify_gimple_switch (stmt);
3060               break;
3061
3062             case GIMPLE_COND:
3063               {
3064                 int did_something;
3065                 did_something = forward_propagate_into_gimple_cond (stmt);
3066                 if (did_something == 2)
3067                   cfg_changed = true;
3068                 changed = did_something != 0;
3069                 break;
3070               }
3071
3072             case GIMPLE_CALL:
3073               {
3074                 tree callee = gimple_call_fndecl (stmt);
3075                 if (callee != NULL_TREE
3076                     && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
3077                   changed = simplify_builtin_call (&gsi, callee);
3078                 break;
3079               }
3080
3081             default:;
3082             }
3083
3084           if (changed)
3085             {
3086               /* If the stmt changed then re-visit it and the statements
3087                  inserted before it.  */
3088               for (; !gsi_end_p (gsi); gsi_prev (&gsi))
3089                 if (gimple_plf (gsi_stmt (gsi), GF_PLF_1))
3090                   break;
3091               if (gsi_end_p (gsi))
3092                 gsi = gsi_start_bb (bb);
3093               else
3094                 gsi_next (&gsi);
3095             }
3096           else
3097             {
3098               /* Stmt no longer needs to be revisited.  */
3099               gimple_set_plf (stmt, GF_PLF_1, true);
3100               gsi_next (&gsi);
3101             }
3102         }
3103     }
3104
3105   if (cfg_changed)
3106     todoflags |= TODO_cleanup_cfg;
3107
3108   return todoflags;
3109 }
3110
3111
3112 static bool
3113 gate_forwprop (void)
3114 {
3115   return flag_tree_forwprop;
3116 }
3117
3118 struct gimple_opt_pass pass_forwprop =
3119 {
3120  {
3121   GIMPLE_PASS,
3122   "forwprop",                   /* name */
3123   OPTGROUP_NONE,                /* optinfo_flags */
3124   gate_forwprop,                /* gate */
3125   ssa_forward_propagate_and_combine,    /* execute */
3126   NULL,                         /* sub */
3127   NULL,                         /* next */
3128   0,                            /* static_pass_number */
3129   TV_TREE_FORWPROP,             /* tv_id */
3130   PROP_cfg | PROP_ssa,          /* properties_required */
3131   0,                            /* properties_provided */
3132   0,                            /* properties_destroyed */
3133   0,                            /* todo_flags_start */
3134   TODO_ggc_collect
3135   | TODO_update_ssa
3136   | TODO_verify_ssa             /* todo_flags_finish */
3137  }
3138 };