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