gcc/tree-ssa-forwprop.c

   1 /* Forward propagation of expressions for single use variables.
   2    Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010, 2011
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "tm_p.h"
  27 #include "basic-block.h"
  28 #include "timevar.h"
  29 #include "gimple-pretty-print.h"
  30 #include "tree-flow.h"
  31 #include "tree-pass.h"
  32 #include "tree-dump.h"
  33 #include "langhooks.h"
  34 #include "flags.h"
  35 #include "gimple.h"
  36 #include "expr.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 EH 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 not a simple copy, we possibly found it.  */
 231     if (!gimple_assign_ssa_name_copy_p (def_stmt))
 232       {
 233         tree rhs;
 234
 235         if (!single_use_only && single_use_p)
 236           *single_use_p = single_use;
 237
 238         /* We can look through pointer conversions in the search
 239            for a useful stmt for the comparison folding.  */
 240         rhs = gimple_assign_rhs1 (def_stmt);
 241         if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
 242             && TREE_CODE (rhs) == SSA_NAME
 243             && POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (def_stmt)))
 244             && POINTER_TYPE_P (TREE_TYPE (rhs)))
 245           name = rhs;
 246         else
 247           return def_stmt;
 248       }
 249     else
 250       {
 251         /* Continue searching the def of the copy source name.  */
 252         name = gimple_assign_rhs1 (def_stmt);
 253       }
 254   } while (1);
 255 }
 256
 257 /* Checks if the destination ssa name in DEF_STMT can be used as
 258    propagation source.  Returns true if so, otherwise false.  */
 259
 260 static bool
 261 can_propagate_from (gimple def_stmt)
 262 {
 263   gcc_assert (is_gimple_assign (def_stmt));
 264
 265   /* If the rhs has side-effects we cannot propagate from it.  */
 266   if (gimple_has_volatile_ops (def_stmt))
 267     return false;
 268
 269   /* If the rhs is a load we cannot propagate from it.  */
 270   if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_reference
 271       || TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_declaration)
 272     return false;
 273
 274   /* Constants can be always propagated.  */
 275   if (gimple_assign_single_p (def_stmt)
 276       && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt)))
 277     return true;
 278
 279   /* We cannot propagate ssa names that occur in abnormal phi nodes.  */
 280   if (stmt_references_abnormal_ssa_name (def_stmt))
 281     return false;
 282
 283   /* If the definition is a conversion of a pointer to a function type,
 284      then we can not apply optimizations as some targets require
 285      function pointers to be canonicalized and in this case this
 286      optimization could eliminate a necessary canonicalization.  */
 287   if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
 288     {
 289       tree rhs = gimple_assign_rhs1 (def_stmt);
 290       if (POINTER_TYPE_P (TREE_TYPE (rhs))
 291           && TREE_CODE (TREE_TYPE (TREE_TYPE (rhs))) == FUNCTION_TYPE)
 292         return false;
 293     }
 294
 295   return true;
 296 }
 297
 298 /* Remove a chain of dead statements starting at the definition of
 299    NAME.  The chain is linked via the first operand of the defining statements.
 300    If NAME was replaced in its only use then this function can be used
 301    to clean up dead stmts.  The function handles already released SSA
 302    names gracefully.
 303    Returns true if cleanup-cfg has to run.  */
 304
 305 static bool
 306 remove_prop_source_from_use (tree name)
 307 {
 308   gimple_stmt_iterator gsi;
 309   gimple stmt;
 310   bool cfg_changed = false;
 311
 312   do {
 313     basic_block bb;
 314
 315     if (SSA_NAME_IN_FREE_LIST (name)
 316         || SSA_NAME_IS_DEFAULT_DEF (name)
 317         || !has_zero_uses (name))
 318       return cfg_changed;
 319
 320     stmt = SSA_NAME_DEF_STMT (name);
 321     if (gimple_code (stmt) == GIMPLE_PHI
 322         || gimple_has_side_effects (stmt))
 323       return cfg_changed;
 324
 325     bb = gimple_bb (stmt);
 326     gsi = gsi_for_stmt (stmt);
 327     unlink_stmt_vdef (stmt);
 328     gsi_remove (&gsi, true);
 329     release_defs (stmt);
 330     cfg_changed |= gimple_purge_dead_eh_edges (bb);
 331
 332     name = is_gimple_assign (stmt) ? gimple_assign_rhs1 (stmt) : NULL_TREE;
 333   } while (name && TREE_CODE (name) == SSA_NAME);
 334
 335   return cfg_changed;
 336 }
 337
 338 /* Return the rhs of a gimple_assign STMT in a form of a single tree,
 339    converted to type TYPE.
 340
 341    This should disappear, but is needed so we can combine expressions and use
 342    the fold() interfaces. Long term, we need to develop folding and combine
 343    routines that deal with gimple exclusively . */
 344
 345 static tree
 346 rhs_to_tree (tree type, gimple stmt)
 347 {
 348   location_t loc = gimple_location (stmt);
 349   enum tree_code code = gimple_assign_rhs_code (stmt);
 350   if (get_gimple_rhs_class (code) == GIMPLE_TERNARY_RHS)
 351     return fold_build3_loc (loc, code, type, gimple_assign_rhs1 (stmt),
 352                             gimple_assign_rhs2 (stmt),
 353                             gimple_assign_rhs3 (stmt));
 354   else if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
 355     return fold_build2_loc (loc, code, type, gimple_assign_rhs1 (stmt),
 356                         gimple_assign_rhs2 (stmt));
 357   else if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
 358     return build1 (code, type, gimple_assign_rhs1 (stmt));
 359   else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
 360     return gimple_assign_rhs1 (stmt);
 361   else
 362     gcc_unreachable ();
 363 }
 364
 365 /* Combine OP0 CODE OP1 in the context of a COND_EXPR.  Returns
 366    the folded result in a form suitable for COND_EXPR_COND or
 367    NULL_TREE, if there is no suitable simplified form.  If
 368    INVARIANT_ONLY is true only gimple_min_invariant results are
 369    considered simplified.  */
 370
 371 static tree
 372 combine_cond_expr_cond (gimple stmt, enum tree_code code, tree type,
 373                         tree op0, tree op1, bool invariant_only)
 374 {
 375   tree t;
 376
 377   gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
 378
 379   fold_defer_overflow_warnings ();
 380   t = fold_binary_loc (gimple_location (stmt), code, type, op0, op1);
 381   if (!t)
 382     {
 383       fold_undefer_overflow_warnings (false, NULL, 0);
 384       return NULL_TREE;
 385     }
 386
 387   /* Require that we got a boolean type out if we put one in.  */
 388   gcc_assert (TREE_CODE (TREE_TYPE (t)) == TREE_CODE (type));
 389
 390   /* Canonicalize the combined condition for use in a COND_EXPR.  */
 391   t = canonicalize_cond_expr_cond (t);
 392
 393   /* Bail out if we required an invariant but didn't get one.  */
 394   if (!t || (invariant_only && !is_gimple_min_invariant (t)))
 395     {
 396       fold_undefer_overflow_warnings (false, NULL, 0);
 397       return NULL_TREE;
 398     }
 399
 400   fold_undefer_overflow_warnings (!gimple_no_warning_p (stmt), stmt, 0);
 401
 402   return t;
 403 }
 404
 405 /* Combine the comparison OP0 CODE OP1 at LOC with the defining statements
 406    of its operand.  Return a new comparison tree or NULL_TREE if there
 407    were no simplifying combines.  */
 408
 409 static tree
 410 forward_propagate_into_comparison_1 (gimple stmt,
 411                                      enum tree_code code, tree type,
 412                                      tree op0, tree op1)
 413 {
 414   tree tmp = NULL_TREE;
 415   tree rhs0 = NULL_TREE, rhs1 = NULL_TREE;
 416   bool single_use0_p = false, single_use1_p = false;
 417
 418   /* For comparisons use the first operand, that is likely to
 419      simplify comparisons against constants.  */
 420   if (TREE_CODE (op0) == SSA_NAME)
 421     {
 422       gimple def_stmt = get_prop_source_stmt (op0, false, &single_use0_p);
 423       if (def_stmt && can_propagate_from (def_stmt))
 424         {
 425           rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
 426           tmp = combine_cond_expr_cond (stmt, code, type,
 427                                         rhs0, op1, !single_use0_p);
 428           if (tmp)
 429             return tmp;
 430         }
 431     }
 432
 433   /* If that wasn't successful, try the second operand.  */
 434   if (TREE_CODE (op1) == SSA_NAME)
 435     {
 436       gimple def_stmt = get_prop_source_stmt (op1, false, &single_use1_p);
 437       if (def_stmt && can_propagate_from (def_stmt))
 438         {
 439           rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt);
 440           tmp = combine_cond_expr_cond (stmt, code, type,
 441                                         op0, rhs1, !single_use1_p);
 442           if (tmp)
 443             return tmp;
 444         }
 445     }
 446
 447   /* If that wasn't successful either, try both operands.  */
 448   if (rhs0 != NULL_TREE
 449       && rhs1 != NULL_TREE)
 450     tmp = combine_cond_expr_cond (stmt, code, type,
 451                                   rhs0, rhs1,
 452                                   !(single_use0_p && single_use1_p));
 453
 454   return tmp;
 455 }
 456
 457 /* Propagate from the ssa name definition statements of the assignment
 458    from a comparison at *GSI into the conditional if that simplifies it.
 459    Returns 1 if the stmt was modified and 2 if the CFG needs cleanup,
 460    otherwise returns 0.  */
 461
 462 static int
 463 forward_propagate_into_comparison (gimple_stmt_iterator *gsi)
 464 {
 465   gimple stmt = gsi_stmt (*gsi);
 466   tree tmp;
 467   bool cfg_changed = false;
 468   tree type = TREE_TYPE (gimple_assign_lhs (stmt));
 469   tree rhs1 = gimple_assign_rhs1 (stmt);
 470   tree rhs2 = gimple_assign_rhs2 (stmt);
 471
 472   /* Combine the comparison with defining statements.  */
 473   tmp = forward_propagate_into_comparison_1 (stmt,
 474                                              gimple_assign_rhs_code (stmt),
 475                                              type, rhs1, rhs2);
 476   if (tmp && useless_type_conversion_p (type, TREE_TYPE (tmp)))
 477     {
 478       gimple_assign_set_rhs_from_tree (gsi, tmp);
 479       fold_stmt (gsi);
 480       update_stmt (gsi_stmt (*gsi));
 481
 482       if (TREE_CODE (rhs1) == SSA_NAME)
 483         cfg_changed |= remove_prop_source_from_use (rhs1);
 484       if (TREE_CODE (rhs2) == SSA_NAME)
 485         cfg_changed |= remove_prop_source_from_use (rhs2);
 486       return cfg_changed ? 2 : 1;
 487     }
 488
 489   return 0;
 490 }
 491
 492 /* Propagate from the ssa name definition statements of COND_EXPR
 493    in GIMPLE_COND statement STMT into the conditional if that simplifies it.
 494    Returns zero if no statement was changed, one if there were
 495    changes and two if cfg_cleanup needs to run.
 496
 497    This must be kept in sync with forward_propagate_into_cond.  */
 498
 499 static int
 500 forward_propagate_into_gimple_cond (gimple stmt)
 501 {
 502   tree tmp;
 503   enum tree_code code = gimple_cond_code (stmt);
 504   bool cfg_changed = false;
 505   tree rhs1 = gimple_cond_lhs (stmt);
 506   tree rhs2 = gimple_cond_rhs (stmt);
 507
 508   /* We can do tree combining on SSA_NAME and comparison expressions.  */
 509   if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison)
 510     return 0;
 511
 512   tmp = forward_propagate_into_comparison_1 (stmt, code,
 513                                              boolean_type_node,
 514                                              rhs1, rhs2);
 515   if (tmp)
 516     {
 517       if (dump_file && tmp)
 518         {
 519           fprintf (dump_file, "  Replaced '");
 520           print_gimple_expr (dump_file, stmt, 0, 0);
 521           fprintf (dump_file, "' with '");
 522           print_generic_expr (dump_file, tmp, 0);
 523           fprintf (dump_file, "'\n");
 524         }
 525
 526       gimple_cond_set_condition_from_tree (stmt, unshare_expr (tmp));
 527       update_stmt (stmt);
 528
 529       if (TREE_CODE (rhs1) == SSA_NAME)
 530         cfg_changed |= remove_prop_source_from_use (rhs1);
 531       if (TREE_CODE (rhs2) == SSA_NAME)
 532         cfg_changed |= remove_prop_source_from_use (rhs2);
 533       return (cfg_changed || is_gimple_min_invariant (tmp)) ? 2 : 1;
 534     }
 535
 536   /* Canonicalize _Bool == 0 and _Bool != 1 to _Bool != 0 by swapping edges.  */
 537   if ((TREE_CODE (TREE_TYPE (rhs1)) == BOOLEAN_TYPE
 538        || (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
 539            && TYPE_PRECISION (TREE_TYPE (rhs1)) == 1))
 540       && ((code == EQ_EXPR
 541            && integer_zerop (rhs2))
 542           || (code == NE_EXPR
 543               && integer_onep (rhs2))))
 544     {
 545       basic_block bb = gimple_bb (stmt);
 546       gimple_cond_set_code (stmt, NE_EXPR);
 547       gimple_cond_set_rhs (stmt, build_zero_cst (TREE_TYPE (rhs1)));
 548       EDGE_SUCC (bb, 0)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
 549       EDGE_SUCC (bb, 1)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
 550       return 1;
 551     }
 552
 553   return 0;
 554 }
 555
 556
 557 /* Propagate from the ssa name definition statements of COND_EXPR
 558    in the rhs of statement STMT into the conditional if that simplifies it.
 559    Returns true zero if the stmt was changed.  */
 560
 561 static bool
 562 forward_propagate_into_cond (gimple_stmt_iterator *gsi_p)
 563 {
 564   gimple stmt = gsi_stmt (*gsi_p);
 565   tree tmp = NULL_TREE;
 566   tree cond = gimple_assign_rhs1 (stmt);
 567   bool swap = false;
 568
 569   /* We can do tree combining on SSA_NAME and comparison expressions.  */
 570   if (COMPARISON_CLASS_P (cond))
 571     tmp = forward_propagate_into_comparison_1 (stmt, TREE_CODE (cond),
 572                                                boolean_type_node,
 573                                                TREE_OPERAND (cond, 0),
 574                                                TREE_OPERAND (cond, 1));
 575   else if (TREE_CODE (cond) == SSA_NAME)
 576     {
 577       enum tree_code code;
 578       tree name = cond;
 579       gimple def_stmt = get_prop_source_stmt (name, true, NULL);
 580       if (!def_stmt || !can_propagate_from (def_stmt))
 581         return 0;
 582
 583       code = gimple_assign_rhs_code (def_stmt);
 584       if (TREE_CODE_CLASS (code) == tcc_comparison)
 585         tmp = fold_build2_loc (gimple_location (def_stmt),
 586                                code,
 587                                boolean_type_node,
 588                                gimple_assign_rhs1 (def_stmt),
 589                                gimple_assign_rhs2 (def_stmt));
 590       else if ((code == BIT_NOT_EXPR
 591                 && TYPE_PRECISION (TREE_TYPE (cond)) == 1)
 592                || (code == BIT_XOR_EXPR
 593                    && integer_onep (gimple_assign_rhs2 (def_stmt))))
 594         {
 595           tmp = gimple_assign_rhs1 (def_stmt);
 596           swap = true;
 597         }
 598     }
 599
 600   if (tmp
 601       && is_gimple_condexpr (tmp))
 602     {
 603       if (dump_file && tmp)
 604         {
 605           fprintf (dump_file, "  Replaced '");
 606           print_generic_expr (dump_file, cond, 0);
 607           fprintf (dump_file, "' with '");
 608           print_generic_expr (dump_file, tmp, 0);
 609           fprintf (dump_file, "'\n");
 610         }
 611
 612       if (integer_onep (tmp))
 613         gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs2 (stmt));
 614       else if (integer_zerop (tmp))
 615         gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs3 (stmt));
 616       else
 617         {
 618           gimple_assign_set_rhs1 (stmt, unshare_expr (tmp));
 619           if (swap)
 620             {
 621               tree t = gimple_assign_rhs2 (stmt);
 622               gimple_assign_set_rhs2 (stmt, gimple_assign_rhs3 (stmt));
 623               gimple_assign_set_rhs3 (stmt, t);
 624             }
 625         }
 626       stmt = gsi_stmt (*gsi_p);
 627       update_stmt (stmt);
 628
 629       return true;
 630     }
 631
 632   return 0;
 633 }
 634
 635 /* We've just substituted an ADDR_EXPR into stmt.  Update all the
 636    relevant data structures to match.  */
 637
 638 static void
 639 tidy_after_forward_propagate_addr (gimple stmt)
 640 {
 641   /* We may have turned a trapping insn into a non-trapping insn.  */
 642   if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
 643       && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
 644     cfg_changed = true;
 645
 646   if (TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR)
 647      recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
 648 }
 649
 650 /* DEF_RHS contains the address of the 0th element in an array.
 651    USE_STMT uses type of DEF_RHS to compute the address of an
 652    arbitrary element within the array.  The (variable) byte offset
 653    of the element is contained in OFFSET.
 654
 655    We walk back through the use-def chains of OFFSET to verify that
 656    it is indeed computing the offset of an element within the array
 657    and extract the index corresponding to the given byte offset.
 658
 659    We then try to fold the entire address expression into a form
 660    &array[index].
 661
 662    If we are successful, we replace the right hand side of USE_STMT
 663    with the new address computation.  */
 664
 665 static bool
 666 forward_propagate_addr_into_variable_array_index (tree offset,
 667                                                   tree def_rhs,
 668                                                   gimple_stmt_iterator *use_stmt_gsi)
 669 {
 670   tree index, tunit;
 671   gimple offset_def, use_stmt = gsi_stmt (*use_stmt_gsi);
 672   tree new_rhs, tmp;
 673
 674   if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == ARRAY_REF)
 675     tunit = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs)));
 676   else if (TREE_CODE (TREE_TYPE (TREE_OPERAND (def_rhs, 0))) == ARRAY_TYPE)
 677     tunit = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (TREE_TYPE (def_rhs))));
 678   else
 679     return false;
 680   if (!host_integerp (tunit, 1))
 681     return false;
 682
 683   /* Get the offset's defining statement.  */
 684   offset_def = SSA_NAME_DEF_STMT (offset);
 685
 686   /* Try to find an expression for a proper index.  This is either a
 687      multiplication expression by the element size or just the ssa name we came
 688      along in case the element size is one. In that case, however, we do not
 689      allow multiplications because they can be computing index to a higher
 690      level dimension (PR 37861). */
 691   if (integer_onep (tunit))
 692     {
 693       if (is_gimple_assign (offset_def)
 694           && gimple_assign_rhs_code (offset_def) == MULT_EXPR)
 695         return false;
 696
 697       index = offset;
 698     }
 699   else
 700     {
 701       /* The statement which defines OFFSET before type conversion
 702          must be a simple GIMPLE_ASSIGN.  */
 703       if (!is_gimple_assign (offset_def))
 704         return false;
 705
 706       /* The RHS of the statement which defines OFFSET must be a
 707          multiplication of an object by the size of the array elements.
 708          This implicitly verifies that the size of the array elements
 709          is constant.  */
 710      if (gimple_assign_rhs_code (offset_def) == MULT_EXPR
 711          && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
 712          && tree_int_cst_equal (gimple_assign_rhs2 (offset_def), tunit))
 713        {
 714          /* The first operand to the MULT_EXPR is the desired index.  */
 715          index = gimple_assign_rhs1 (offset_def);
 716        }
 717      /* If we have idx * tunit + CST * tunit re-associate that.  */
 718      else if ((gimple_assign_rhs_code (offset_def) == PLUS_EXPR
 719                || gimple_assign_rhs_code (offset_def) == MINUS_EXPR)
 720               && TREE_CODE (gimple_assign_rhs1 (offset_def)) == SSA_NAME
 721               && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
 722               && (tmp = div_if_zero_remainder (EXACT_DIV_EXPR,
 723                                                gimple_assign_rhs2 (offset_def),
 724                                                tunit)) != NULL_TREE)
 725        {
 726          gimple offset_def2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (offset_def));
 727          if (is_gimple_assign (offset_def2)
 728              && gimple_assign_rhs_code (offset_def2) == MULT_EXPR
 729              && TREE_CODE (gimple_assign_rhs2 (offset_def2)) == INTEGER_CST
 730              && tree_int_cst_equal (gimple_assign_rhs2 (offset_def2), tunit))
 731            {
 732              index = fold_build2 (gimple_assign_rhs_code (offset_def),
 733                                   TREE_TYPE (offset),
 734                                   gimple_assign_rhs1 (offset_def2), tmp);
 735            }
 736          else
 737            return false;
 738        }
 739      else
 740         return false;
 741     }
 742
 743   /* Replace the pointer addition with array indexing.  */
 744   index = force_gimple_operand_gsi (use_stmt_gsi, index, true, NULL_TREE,
 745                                     true, GSI_SAME_STMT);
 746   if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == ARRAY_REF)
 747     {
 748       new_rhs = unshare_expr (def_rhs);
 749       TREE_OPERAND (TREE_OPERAND (new_rhs, 0), 1) = index;
 750     }
 751   else
 752     {
 753       new_rhs = build4 (ARRAY_REF, TREE_TYPE (TREE_TYPE (TREE_TYPE (def_rhs))),
 754                         unshare_expr (TREE_OPERAND (def_rhs, 0)),
 755                         index, integer_zero_node, NULL_TREE);
 756       new_rhs = build_fold_addr_expr (new_rhs);
 757       if (!useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (use_stmt)),
 758                                       TREE_TYPE (new_rhs)))
 759         {
 760           new_rhs = force_gimple_operand_gsi (use_stmt_gsi, new_rhs, true,
 761                                               NULL_TREE, true, GSI_SAME_STMT);
 762           new_rhs = fold_convert (TREE_TYPE (gimple_assign_lhs (use_stmt)),
 763                                   new_rhs);
 764         }
 765     }
 766   gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
 767   fold_stmt (use_stmt_gsi);
 768   tidy_after_forward_propagate_addr (gsi_stmt (*use_stmt_gsi));
 769   return true;
 770 }
 771
 772 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
 773    ADDR_EXPR <whatever>.
 774
 775    Try to forward propagate the ADDR_EXPR into the use USE_STMT.
 776    Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
 777    node or for recovery of array indexing from pointer arithmetic.
 778
 779    Return true if the propagation was successful (the propagation can
 780    be not totally successful, yet things may have been changed).  */
 781
 782 static bool
 783 forward_propagate_addr_expr_1 (tree name, tree def_rhs,
 784                                gimple_stmt_iterator *use_stmt_gsi,
 785                                bool single_use_p)
 786 {
 787   tree lhs, rhs, rhs2, array_ref;
 788   gimple use_stmt = gsi_stmt (*use_stmt_gsi);
 789   enum tree_code rhs_code;
 790   bool res = true;
 791
 792   gcc_assert (TREE_CODE (def_rhs) == ADDR_EXPR);
 793
 794   lhs = gimple_assign_lhs (use_stmt);
 795   rhs_code = gimple_assign_rhs_code (use_stmt);
 796   rhs = gimple_assign_rhs1 (use_stmt);
 797
 798   /* Trivial cases.  The use statement could be a trivial copy or a
 799      useless conversion.  Recurse to the uses of the lhs as copyprop does
 800      not copy through different variant pointers and FRE does not catch
 801      all useless conversions.  Treat the case of a single-use name and
 802      a conversion to def_rhs type separate, though.  */
 803   if (TREE_CODE (lhs) == SSA_NAME
 804       && ((rhs_code == SSA_NAME && rhs == name)
 805           || CONVERT_EXPR_CODE_P (rhs_code)))
 806     {
 807       /* Only recurse if we don't deal with a single use or we cannot
 808          do the propagation to the current statement.  In particular
 809          we can end up with a conversion needed for a non-invariant
 810          address which we cannot do in a single statement.  */
 811       if (!single_use_p
 812           || (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs))
 813               && (!is_gimple_min_invariant (def_rhs)
 814                   || (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
 815                       && POINTER_TYPE_P (TREE_TYPE (def_rhs))
 816                       && (TYPE_PRECISION (TREE_TYPE (lhs))
 817                           > TYPE_PRECISION (TREE_TYPE (def_rhs)))))))
 818         return forward_propagate_addr_expr (lhs, def_rhs);
 819
 820       gimple_assign_set_rhs1 (use_stmt, unshare_expr (def_rhs));
 821       if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
 822         gimple_assign_set_rhs_code (use_stmt, TREE_CODE (def_rhs));
 823       else
 824         gimple_assign_set_rhs_code (use_stmt, NOP_EXPR);
 825       return true;
 826     }
 827
 828   /* Propagate through constant pointer adjustments.  */
 829   if (TREE_CODE (lhs) == SSA_NAME
 830       && rhs_code == POINTER_PLUS_EXPR
 831       && rhs == name
 832       && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST)
 833     {
 834       tree new_def_rhs;
 835       /* As we come here with non-invariant addresses in def_rhs we need
 836          to make sure we can build a valid constant offsetted address
 837          for further propagation.  Simply rely on fold building that
 838          and check after the fact.  */
 839       new_def_rhs = fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (rhs)),
 840                                  def_rhs,
 841                                  fold_convert (ptr_type_node,
 842                                                gimple_assign_rhs2 (use_stmt)));
 843       if (TREE_CODE (new_def_rhs) == MEM_REF
 844           && !is_gimple_mem_ref_addr (TREE_OPERAND (new_def_rhs, 0)))
 845         return false;
 846       new_def_rhs = build_fold_addr_expr_with_type (new_def_rhs,
 847                                                     TREE_TYPE (rhs));
 848
 849       /* Recurse.  If we could propagate into all uses of lhs do not
 850          bother to replace into the current use but just pretend we did.  */
 851       if (TREE_CODE (new_def_rhs) == ADDR_EXPR
 852           && forward_propagate_addr_expr (lhs, new_def_rhs))
 853         return true;
 854
 855       if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (new_def_rhs)))
 856         gimple_assign_set_rhs_with_ops (use_stmt_gsi, TREE_CODE (new_def_rhs),
 857                                         new_def_rhs, NULL_TREE);
 858       else if (is_gimple_min_invariant (new_def_rhs))
 859         gimple_assign_set_rhs_with_ops (use_stmt_gsi, NOP_EXPR,
 860                                         new_def_rhs, NULL_TREE);
 861       else
 862         return false;
 863       gcc_assert (gsi_stmt (*use_stmt_gsi) == use_stmt);
 864       update_stmt (use_stmt);
 865       return true;
 866     }
 867
 868   /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
 869      ADDR_EXPR will not appear on the LHS.  */
 870   lhs = gimple_assign_lhs (use_stmt);
 871   while (handled_component_p (lhs))
 872     lhs = TREE_OPERAND (lhs, 0);
 873
 874   /* Now see if the LHS node is a MEM_REF using NAME.  If so,
 875      propagate the ADDR_EXPR into the use of NAME and fold the result.  */
 876   if (TREE_CODE (lhs) == MEM_REF
 877       && TREE_OPERAND (lhs, 0) == name)
 878     {
 879       tree def_rhs_base;
 880       HOST_WIDE_INT def_rhs_offset;
 881       /* If the address is invariant we can always fold it.  */
 882       if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
 883                                                          &def_rhs_offset)))
 884         {
 885           double_int off = mem_ref_offset (lhs);
 886           tree new_ptr;
 887           off = double_int_add (off,
 888                                 shwi_to_double_int (def_rhs_offset));
 889           if (TREE_CODE (def_rhs_base) == MEM_REF)
 890             {
 891               off = double_int_add (off, mem_ref_offset (def_rhs_base));
 892               new_ptr = TREE_OPERAND (def_rhs_base, 0);
 893             }
 894           else
 895             new_ptr = build_fold_addr_expr (def_rhs_base);
 896           TREE_OPERAND (lhs, 0) = new_ptr;
 897           TREE_OPERAND (lhs, 1)
 898             = double_int_to_tree (TREE_TYPE (TREE_OPERAND (lhs, 1)), off);
 899           tidy_after_forward_propagate_addr (use_stmt);
 900           /* Continue propagating into the RHS if this was not the only use.  */
 901           if (single_use_p)
 902             return true;
 903         }
 904       /* If the LHS is a plain dereference and the value type is the same as
 905          that of the pointed-to type of the address we can put the
 906          dereferenced address on the LHS preserving the original alias-type.  */
 907       else if (gimple_assign_lhs (use_stmt) == lhs
 908                && integer_zerop (TREE_OPERAND (lhs, 1))
 909                && useless_type_conversion_p
 910                     (TREE_TYPE (TREE_OPERAND (def_rhs, 0)),
 911                      TREE_TYPE (gimple_assign_rhs1 (use_stmt))))
 912         {
 913           tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
 914           tree new_offset, new_base, saved, new_lhs;
 915           while (handled_component_p (*def_rhs_basep))
 916             def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
 917           saved = *def_rhs_basep;
 918           if (TREE_CODE (*def_rhs_basep) == MEM_REF)
 919             {
 920               new_base = TREE_OPERAND (*def_rhs_basep, 0);
 921               new_offset = fold_convert (TREE_TYPE (TREE_OPERAND (lhs, 1)),
 922                                          TREE_OPERAND (*def_rhs_basep, 1));
 923             }
 924           else
 925             {
 926               new_base = build_fold_addr_expr (*def_rhs_basep);
 927               new_offset = TREE_OPERAND (lhs, 1);
 928             }
 929           *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
 930                                    new_base, new_offset);
 931           TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (lhs);
 932           TREE_SIDE_EFFECTS (*def_rhs_basep) = TREE_SIDE_EFFECTS (lhs);
 933           TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (lhs);
 934           new_lhs = unshare_expr (TREE_OPERAND (def_rhs, 0));
 935           gimple_assign_set_lhs (use_stmt, new_lhs);
 936           TREE_THIS_VOLATILE (new_lhs) = TREE_THIS_VOLATILE (lhs);
 937           TREE_SIDE_EFFECTS (new_lhs) = TREE_SIDE_EFFECTS (lhs);
 938           *def_rhs_basep = saved;
 939           tidy_after_forward_propagate_addr (use_stmt);
 940           /* Continue propagating into the RHS if this was not the
 941              only use.  */
 942           if (single_use_p)
 943             return true;
 944         }
 945       else
 946         /* We can have a struct assignment dereferencing our name twice.
 947            Note that we didn't propagate into the lhs to not falsely
 948            claim we did when propagating into the rhs.  */
 949         res = false;
 950     }
 951
 952   /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
 953      nodes from the RHS.  */
 954   rhs = gimple_assign_rhs1 (use_stmt);
 955   if (TREE_CODE (rhs) == ADDR_EXPR)
 956     rhs = TREE_OPERAND (rhs, 0);
 957   while (handled_component_p (rhs))
 958     rhs = TREE_OPERAND (rhs, 0);
 959
 960   /* Now see if the RHS node is a MEM_REF using NAME.  If so,
 961      propagate the ADDR_EXPR into the use of NAME and fold the result.  */
 962   if (TREE_CODE (rhs) == MEM_REF
 963       && TREE_OPERAND (rhs, 0) == name)
 964     {
 965       tree def_rhs_base;
 966       HOST_WIDE_INT def_rhs_offset;
 967       if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
 968                                                          &def_rhs_offset)))
 969         {
 970           double_int off = mem_ref_offset (rhs);
 971           tree new_ptr;
 972           off = double_int_add (off,
 973                                 shwi_to_double_int (def_rhs_offset));
 974           if (TREE_CODE (def_rhs_base) == MEM_REF)
 975             {
 976               off = double_int_add (off, mem_ref_offset (def_rhs_base));
 977               new_ptr = TREE_OPERAND (def_rhs_base, 0);
 978             }
 979           else
 980             new_ptr = build_fold_addr_expr (def_rhs_base);
 981           TREE_OPERAND (rhs, 0) = new_ptr;
 982           TREE_OPERAND (rhs, 1)
 983             = double_int_to_tree (TREE_TYPE (TREE_OPERAND (rhs, 1)), off);
 984           fold_stmt_inplace (use_stmt_gsi);
 985           tidy_after_forward_propagate_addr (use_stmt);
 986           return res;
 987         }
 988       /* If the RHS is a plain dereference and the value type is the same as
 989          that of the pointed-to type of the address we can put the
 990          dereferenced address on the RHS preserving the original alias-type.  */
 991       else if (gimple_assign_rhs1 (use_stmt) == rhs
 992                && integer_zerop (TREE_OPERAND (rhs, 1))
 993                && useless_type_conversion_p
 994                     (TREE_TYPE (gimple_assign_lhs (use_stmt)),
 995                      TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
 996         {
 997           tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
 998           tree new_offset, new_base, saved, new_rhs;
 999           while (handled_component_p (*def_rhs_basep))
1000             def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
1001           saved = *def_rhs_basep;
1002           if (TREE_CODE (*def_rhs_basep) == MEM_REF)
1003             {
1004               new_base = TREE_OPERAND (*def_rhs_basep, 0);
1005               new_offset = fold_convert (TREE_TYPE (TREE_OPERAND (rhs, 1)),
1006                                          TREE_OPERAND (*def_rhs_basep, 1));
1007             }
1008           else
1009             {
1010               new_base = build_fold_addr_expr (*def_rhs_basep);
1011               new_offset = TREE_OPERAND (rhs, 1);
1012             }
1013           *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
1014                                    new_base, new_offset);
1015           TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (rhs);
1016           TREE_SIDE_EFFECTS (*def_rhs_basep) = TREE_SIDE_EFFECTS (rhs);
1017           TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (rhs);
1018           new_rhs = unshare_expr (TREE_OPERAND (def_rhs, 0));
1019           gimple_assign_set_rhs1 (use_stmt, new_rhs);
1020           TREE_THIS_VOLATILE (new_rhs) = TREE_THIS_VOLATILE (rhs);
1021           TREE_SIDE_EFFECTS (new_rhs) = TREE_SIDE_EFFECTS (rhs);
1022           *def_rhs_basep = saved;
1023           fold_stmt_inplace (use_stmt_gsi);
1024           tidy_after_forward_propagate_addr (use_stmt);
1025           return res;
1026         }
1027     }
1028
1029   /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
1030      is nothing to do. */
1031   if (gimple_assign_rhs_code (use_stmt) != POINTER_PLUS_EXPR
1032       || gimple_assign_rhs1 (use_stmt) != name)
1033     return false;
1034
1035   /* The remaining cases are all for turning pointer arithmetic into
1036      array indexing.  They only apply when we have the address of
1037      element zero in an array.  If that is not the case then there
1038      is nothing to do.  */
1039   array_ref = TREE_OPERAND (def_rhs, 0);
1040   if ((TREE_CODE (array_ref) != ARRAY_REF
1041        || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
1042        || TREE_CODE (TREE_OPERAND (array_ref, 1)) != INTEGER_CST)
1043       && TREE_CODE (TREE_TYPE (array_ref)) != ARRAY_TYPE)
1044     return false;
1045
1046   rhs2 = gimple_assign_rhs2 (use_stmt);
1047   /* Optimize &x[C1] p+ C2 to  &x p+ C3 with C3 = C1 * element_size + C2.  */
1048   if (TREE_CODE (rhs2) == INTEGER_CST)
1049     {
1050       tree new_rhs = build1_loc (gimple_location (use_stmt),
1051                                  ADDR_EXPR, TREE_TYPE (def_rhs),
1052                                  fold_build2 (MEM_REF,
1053                                               TREE_TYPE (TREE_TYPE (def_rhs)),
1054                                               unshare_expr (def_rhs),
1055                                               fold_convert (ptr_type_node,
1056                                                             rhs2)));
1057       gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
1058       use_stmt = gsi_stmt (*use_stmt_gsi);
1059       update_stmt (use_stmt);
1060       tidy_after_forward_propagate_addr (use_stmt);
1061       return true;
1062     }
1063
1064   /* Try to optimize &x[0] p+ OFFSET where OFFSET is defined by
1065      converting a multiplication of an index by the size of the
1066      array elements, then the result is converted into the proper
1067      type for the arithmetic.  */
1068   if (TREE_CODE (rhs2) == SSA_NAME
1069       && (TREE_CODE (array_ref) != ARRAY_REF
1070           || integer_zerop (TREE_OPERAND (array_ref, 1)))
1071       && useless_type_conversion_p (TREE_TYPE (name), TREE_TYPE (def_rhs))
1072       /* Avoid problems with IVopts creating PLUS_EXPRs with a
1073          different type than their operands.  */
1074       && useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
1075     return forward_propagate_addr_into_variable_array_index (rhs2, def_rhs,
1076                                                              use_stmt_gsi);
1077   return false;
1078 }
1079
1080 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
1081
1082    Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
1083    Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
1084    node or for recovery of array indexing from pointer arithmetic.
1085    Returns true, if all uses have been propagated into.  */
1086
1087 static bool
1088 forward_propagate_addr_expr (tree name, tree rhs)
1089 {
1090   int stmt_loop_depth = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_depth;
1091   imm_use_iterator iter;
1092   gimple use_stmt;
1093   bool all = true;
1094   bool single_use_p = has_single_use (name);
1095
1096   FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
1097     {
1098       bool result;
1099       tree use_rhs;
1100
1101       /* If the use is not in a simple assignment statement, then
1102          there is nothing we can do.  */
1103       if (gimple_code (use_stmt) != GIMPLE_ASSIGN)
1104         {
1105           if (!is_gimple_debug (use_stmt))
1106             all = false;
1107           continue;
1108         }
1109
1110       /* If the use is in a deeper loop nest, then we do not want
1111          to propagate non-invariant ADDR_EXPRs into the loop as that
1112          is likely adding expression evaluations into the loop.  */
1113       if (gimple_bb (use_stmt)->loop_depth > stmt_loop_depth
1114           && !is_gimple_min_invariant (rhs))
1115         {
1116           all = false;
1117           continue;
1118         }
1119
1120       {
1121         gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1122         result = forward_propagate_addr_expr_1 (name, rhs, &gsi,
1123                                                 single_use_p);
1124         /* If the use has moved to a different statement adjust
1125            the update machinery for the old statement too.  */
1126         if (use_stmt != gsi_stmt (gsi))
1127           {
1128             update_stmt (use_stmt);
1129             use_stmt = gsi_stmt (gsi);
1130           }
1131
1132         update_stmt (use_stmt);
1133       }
1134       all &= result;
1135
1136       /* Remove intermediate now unused copy and conversion chains.  */
1137       use_rhs = gimple_assign_rhs1 (use_stmt);
1138       if (result
1139           && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
1140           && TREE_CODE (use_rhs) == SSA_NAME
1141           && has_zero_uses (gimple_assign_lhs (use_stmt)))
1142         {
1143           gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1144           release_defs (use_stmt);
1145           gsi_remove (&gsi, true);
1146         }
1147     }
1148
1149   return all && has_zero_uses (name);
1150 }
1151
1152
1153 /* Forward propagate the comparison defined in STMT like
1154    cond_1 = x CMP y to uses of the form
1155      a_1 = (T')cond_1
1156      a_1 = !cond_1
1157      a_1 = cond_1 != 0
1158    Returns true if stmt is now unused.  */
1159
1160 static bool
1161 forward_propagate_comparison (gimple stmt)
1162 {
1163   tree name = gimple_assign_lhs (stmt);
1164   gimple use_stmt;
1165   tree tmp = NULL_TREE;
1166   gimple_stmt_iterator gsi;
1167   enum tree_code code;
1168   tree lhs;
1169
1170   /* Don't propagate ssa names that occur in abnormal phis.  */
1171   if ((TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
1172        && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
1173       || (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME
1174         && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs2 (stmt))))
1175     return false;
1176
1177   /* Do not un-cse comparisons.  But propagate through copies.  */
1178   use_stmt = get_prop_dest_stmt (name, &name);
1179   if (!use_stmt
1180       || !is_gimple_assign (use_stmt))
1181     return false;
1182
1183   code = gimple_assign_rhs_code (use_stmt);
1184   lhs = gimple_assign_lhs (use_stmt);
1185   if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
1186     return false;
1187
1188   /* We can propagate the condition into a statement that
1189      computes the logical negation of the comparison result.  */
1190   if ((code == BIT_NOT_EXPR
1191        && TYPE_PRECISION (TREE_TYPE (lhs)) == 1)
1192       || (code == BIT_XOR_EXPR
1193           && integer_onep (gimple_assign_rhs2 (use_stmt))))
1194     {
1195       tree type = TREE_TYPE (gimple_assign_rhs1 (stmt));
1196       bool nans = HONOR_NANS (TYPE_MODE (type));
1197       enum tree_code inv_code;
1198       inv_code = invert_tree_comparison (gimple_assign_rhs_code (stmt), nans);
1199       if (inv_code == ERROR_MARK)
1200         return false;
1201
1202       tmp = build2 (inv_code, TREE_TYPE (lhs), gimple_assign_rhs1 (stmt),
1203                     gimple_assign_rhs2 (stmt));
1204     }
1205   else
1206     return false;
1207
1208   gsi = gsi_for_stmt (use_stmt);
1209   gimple_assign_set_rhs_from_tree (&gsi, unshare_expr (tmp));
1210   use_stmt = gsi_stmt (gsi);
1211   update_stmt (use_stmt);
1212
1213   if (dump_file && (dump_flags & TDF_DETAILS))
1214     {
1215       fprintf (dump_file, "  Replaced '");
1216       print_gimple_expr (dump_file, stmt, 0, dump_flags);
1217       fprintf (dump_file, "' with '");
1218       print_gimple_expr (dump_file, use_stmt, 0, dump_flags);
1219       fprintf (dump_file, "'\n");
1220     }
1221
1222   /* Remove defining statements.  */
1223   return remove_prop_source_from_use (name);
1224 }
1225
1226
1227 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
1228    If so, we can change STMT into lhs = y which can later be copy
1229    propagated.  Similarly for negation.
1230
1231    This could trivially be formulated as a forward propagation
1232    to immediate uses.  However, we already had an implementation
1233    from DOM which used backward propagation via the use-def links.
1234
1235    It turns out that backward propagation is actually faster as
1236    there's less work to do for each NOT/NEG expression we find.
1237    Backwards propagation needs to look at the statement in a single
1238    backlink.  Forward propagation needs to look at potentially more
1239    than one forward link.
1240
1241    Returns true when the statement was changed.  */
1242
1243 static bool
1244 simplify_not_neg_expr (gimple_stmt_iterator *gsi_p)
1245 {
1246   gimple stmt = gsi_stmt (*gsi_p);
1247   tree rhs = gimple_assign_rhs1 (stmt);
1248   gimple rhs_def_stmt = SSA_NAME_DEF_STMT (rhs);
1249
1250   /* See if the RHS_DEF_STMT has the same form as our statement.  */
1251   if (is_gimple_assign (rhs_def_stmt)
1252       && gimple_assign_rhs_code (rhs_def_stmt) == gimple_assign_rhs_code (stmt))
1253     {
1254       tree rhs_def_operand = gimple_assign_rhs1 (rhs_def_stmt);
1255
1256       /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME.  */
1257       if (TREE_CODE (rhs_def_operand) == SSA_NAME
1258           && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand))
1259         {
1260           gimple_assign_set_rhs_from_tree (gsi_p, rhs_def_operand);
1261           stmt = gsi_stmt (*gsi_p);
1262           update_stmt (stmt);
1263           return true;
1264         }
1265     }
1266
1267   return false;
1268 }
1269
1270 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1271    the condition which we may be able to optimize better.  */
1272
1273 static bool
1274 simplify_gimple_switch (gimple stmt)
1275 {
1276   tree cond = gimple_switch_index (stmt);
1277   tree def, to, ti;
1278   gimple def_stmt;
1279
1280   /* The optimization that we really care about is removing unnecessary
1281      casts.  That will let us do much better in propagating the inferred
1282      constant at the switch target.  */
1283   if (TREE_CODE (cond) == SSA_NAME)
1284     {
1285       def_stmt = SSA_NAME_DEF_STMT (cond);
1286       if (is_gimple_assign (def_stmt))
1287         {
1288           if (gimple_assign_rhs_code (def_stmt) == NOP_EXPR)
1289             {
1290               int need_precision;
1291               bool fail;
1292
1293               def = gimple_assign_rhs1 (def_stmt);
1294
1295               /* ??? Why was Jeff testing this?  We are gimple...  */
1296               gcc_checking_assert (is_gimple_val (def));
1297
1298               to = TREE_TYPE (cond);
1299               ti = TREE_TYPE (def);
1300
1301               /* If we have an extension that preserves value, then we
1302                  can copy the source value into the switch.  */
1303
1304               need_precision = TYPE_PRECISION (ti);
1305               fail = false;
1306               if (! INTEGRAL_TYPE_P (ti))
1307                 fail = true;
1308               else if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti))
1309                 fail = true;
1310               else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti))
1311                 need_precision += 1;
1312               if (TYPE_PRECISION (to) < need_precision)
1313                 fail = true;
1314
1315               if (!fail)
1316                 {
1317                   gimple_switch_set_index (stmt, def);
1318                   update_stmt (stmt);
1319                   return true;
1320                 }
1321             }
1322         }
1323     }
1324
1325   return false;
1326 }
1327
1328 /* For pointers p2 and p1 return p2 - p1 if the
1329    difference is known and constant, otherwise return NULL.  */
1330
1331 static tree
1332 constant_pointer_difference (tree p1, tree p2)
1333 {
1334   int i, j;
1335 #define CPD_ITERATIONS 5
1336   tree exps[2][CPD_ITERATIONS];
1337   tree offs[2][CPD_ITERATIONS];
1338   int cnt[2];
1339
1340   for (i = 0; i < 2; i++)
1341     {
1342       tree p = i ? p1 : p2;
1343       tree off = size_zero_node;
1344       gimple stmt;
1345       enum tree_code code;
1346
1347       /* For each of p1 and p2 we need to iterate at least
1348          twice, to handle ADDR_EXPR directly in p1/p2,
1349          SSA_NAME with ADDR_EXPR or POINTER_PLUS_EXPR etc.
1350          on definition's stmt RHS.  Iterate a few extra times.  */
1351       j = 0;
1352       do
1353         {
1354           if (!POINTER_TYPE_P (TREE_TYPE (p)))
1355             break;
1356           if (TREE_CODE (p) == ADDR_EXPR)
1357             {
1358               tree q = TREE_OPERAND (p, 0);
1359               HOST_WIDE_INT offset;
1360               tree base = get_addr_base_and_unit_offset (q, &offset);
1361               if (base)
1362                 {
1363                   q = base;
1364                   if (offset)
1365                     off = size_binop (PLUS_EXPR, off, size_int (offset));
1366                 }
1367               if (TREE_CODE (q) == MEM_REF
1368                   && TREE_CODE (TREE_OPERAND (q, 0)) == SSA_NAME)
1369                 {
1370                   p = TREE_OPERAND (q, 0);
1371                   off = size_binop (PLUS_EXPR, off,
1372                                     double_int_to_tree (sizetype,
1373                                                         mem_ref_offset (q)));
1374                 }
1375               else
1376                 {
1377                   exps[i][j] = q;
1378                   offs[i][j++] = off;
1379                   break;
1380                 }
1381             }
1382           if (TREE_CODE (p) != SSA_NAME)
1383             break;
1384           exps[i][j] = p;
1385           offs[i][j++] = off;
1386           if (j == CPD_ITERATIONS)
1387             break;
1388           stmt = SSA_NAME_DEF_STMT (p);
1389           if (!is_gimple_assign (stmt) || gimple_assign_lhs (stmt) != p)
1390             break;
1391           code = gimple_assign_rhs_code (stmt);
1392           if (code == POINTER_PLUS_EXPR)
1393             {
1394               if (TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)
1395                 break;
1396               off = size_binop (PLUS_EXPR, off, gimple_assign_rhs2 (stmt));
1397               p = gimple_assign_rhs1 (stmt);
1398             }
1399           else if (code == ADDR_EXPR || code == NOP_EXPR)
1400             p = gimple_assign_rhs1 (stmt);
1401           else
1402             break;
1403         }
1404       while (1);
1405       cnt[i] = j;
1406     }
1407
1408   for (i = 0; i < cnt[0]; i++)
1409     for (j = 0; j < cnt[1]; j++)
1410       if (exps[0][i] == exps[1][j])
1411         return size_binop (MINUS_EXPR, offs[0][i], offs[1][j]);
1412
1413   return NULL_TREE;
1414 }
1415
1416 /* *GSI_P is a GIMPLE_CALL to a builtin function.
1417    Optimize
1418    memcpy (p, "abcd", 4);
1419    memset (p + 4, ' ', 3);
1420    into
1421    memcpy (p, "abcd   ", 7);
1422    call if the latter can be stored by pieces during expansion.  */
1423
1424 static bool
1425 simplify_builtin_call (gimple_stmt_iterator *gsi_p, tree callee2)
1426 {
1427   gimple stmt1, stmt2 = gsi_stmt (*gsi_p);
1428   tree vuse = gimple_vuse (stmt2);
1429   if (vuse == NULL)
1430     return false;
1431   stmt1 = SSA_NAME_DEF_STMT (vuse);
1432
1433   switch (DECL_FUNCTION_CODE (callee2))
1434     {
1435     case BUILT_IN_MEMSET:
1436       if (gimple_call_num_args (stmt2) != 3
1437           || gimple_call_lhs (stmt2)
1438           || CHAR_BIT != 8
1439           || BITS_PER_UNIT != 8)
1440         break;
1441       else
1442         {
1443           tree callee1;
1444           tree ptr1, src1, str1, off1, len1, lhs1;
1445           tree ptr2 = gimple_call_arg (stmt2, 0);
1446           tree val2 = gimple_call_arg (stmt2, 1);
1447           tree len2 = gimple_call_arg (stmt2, 2);
1448           tree diff, vdef, new_str_cst;
1449           gimple use_stmt;
1450           unsigned int ptr1_align;
1451           unsigned HOST_WIDE_INT src_len;
1452           char *src_buf;
1453           use_operand_p use_p;
1454
1455           if (!host_integerp (val2, 0)
1456               || !host_integerp (len2, 1))
1457             break;
1458           if (is_gimple_call (stmt1))
1459             {
1460               /* If first stmt is a call, it needs to be memcpy
1461                  or mempcpy, with string literal as second argument and
1462                  constant length.  */
1463               callee1 = gimple_call_fndecl (stmt1);
1464               if (callee1 == NULL_TREE
1465                   || DECL_BUILT_IN_CLASS (callee1) != BUILT_IN_NORMAL
1466                   || gimple_call_num_args (stmt1) != 3)
1467                 break;
1468               if (DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMCPY
1469                   && DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMPCPY)
1470                 break;
1471               ptr1 = gimple_call_arg (stmt1, 0);
1472               src1 = gimple_call_arg (stmt1, 1);
1473               len1 = gimple_call_arg (stmt1, 2);
1474               lhs1 = gimple_call_lhs (stmt1);
1475               if (!host_integerp (len1, 1))
1476                 break;
1477               str1 = string_constant (src1, &off1);
1478               if (str1 == NULL_TREE)
1479                 break;
1480               if (!host_integerp (off1, 1)
1481                   || compare_tree_int (off1, TREE_STRING_LENGTH (str1) - 1) > 0
1482                   || compare_tree_int (len1, TREE_STRING_LENGTH (str1)
1483                                              - tree_low_cst (off1, 1)) > 0
1484                   || TREE_CODE (TREE_TYPE (str1)) != ARRAY_TYPE
1485                   || TYPE_MODE (TREE_TYPE (TREE_TYPE (str1)))
1486                      != TYPE_MODE (char_type_node))
1487                 break;
1488             }
1489           else if (gimple_assign_single_p (stmt1))
1490             {
1491               /* Otherwise look for length 1 memcpy optimized into
1492                  assignment.  */
1493               ptr1 = gimple_assign_lhs (stmt1);
1494               src1 = gimple_assign_rhs1 (stmt1);
1495               if (TREE_CODE (ptr1) != MEM_REF
1496                   || TYPE_MODE (TREE_TYPE (ptr1)) != TYPE_MODE (char_type_node)
1497                   || !host_integerp (src1, 0))
1498                 break;
1499               ptr1 = build_fold_addr_expr (ptr1);
1500               callee1 = NULL_TREE;
1501               len1 = size_one_node;
1502               lhs1 = NULL_TREE;
1503               off1 = size_zero_node;
1504               str1 = NULL_TREE;
1505             }
1506           else
1507             break;
1508
1509           diff = constant_pointer_difference (ptr1, ptr2);
1510           if (diff == NULL && lhs1 != NULL)
1511             {
1512               diff = constant_pointer_difference (lhs1, ptr2);
1513               if (DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1514                   && diff != NULL)
1515                 diff = size_binop (PLUS_EXPR, diff,
1516                                    fold_convert (sizetype, len1));
1517             }
1518           /* If the difference between the second and first destination pointer
1519              is not constant, or is bigger than memcpy length, bail out.  */
1520           if (diff == NULL
1521               || !host_integerp (diff, 1)
1522               || tree_int_cst_lt (len1, diff))
1523             break;
1524
1525           /* Use maximum of difference plus memset length and memcpy length
1526              as the new memcpy length, if it is too big, bail out.  */
1527           src_len = tree_low_cst (diff, 1);
1528           src_len += tree_low_cst (len2, 1);
1529           if (src_len < (unsigned HOST_WIDE_INT) tree_low_cst (len1, 1))
1530             src_len = tree_low_cst (len1, 1);
1531           if (src_len > 1024)
1532             break;
1533
1534           /* If mempcpy value is used elsewhere, bail out, as mempcpy
1535              with bigger length will return different result.  */
1536           if (lhs1 != NULL_TREE
1537               && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1538               && (TREE_CODE (lhs1) != SSA_NAME
1539                   || !single_imm_use (lhs1, &use_p, &use_stmt)
1540                   || use_stmt != stmt2))
1541             break;
1542
1543           /* If anything reads memory in between memcpy and memset
1544              call, the modified memcpy call might change it.  */
1545           vdef = gimple_vdef (stmt1);
1546           if (vdef != NULL
1547               && (!single_imm_use (vdef, &use_p, &use_stmt)
1548                   || use_stmt != stmt2))
1549             break;
1550
1551           ptr1_align = get_pointer_alignment (ptr1);
1552           /* Construct the new source string literal.  */
1553           src_buf = XALLOCAVEC (char, src_len + 1);
1554           if (callee1)
1555             memcpy (src_buf,
1556                     TREE_STRING_POINTER (str1) + tree_low_cst (off1, 1),
1557                     tree_low_cst (len1, 1));
1558           else
1559             src_buf[0] = tree_low_cst (src1, 0);
1560           memset (src_buf + tree_low_cst (diff, 1),
1561                   tree_low_cst (val2, 1), tree_low_cst (len2, 1));
1562           src_buf[src_len] = '\0';
1563           /* Neither builtin_strncpy_read_str nor builtin_memcpy_read_str
1564              handle embedded '\0's.  */
1565           if (strlen (src_buf) != src_len)
1566             break;
1567           rtl_profile_for_bb (gimple_bb (stmt2));
1568           /* If the new memcpy wouldn't be emitted by storing the literal
1569              by pieces, this optimization might enlarge .rodata too much,
1570              as commonly used string literals couldn't be shared any
1571              longer.  */
1572           if (!can_store_by_pieces (src_len,
1573                                     builtin_strncpy_read_str,
1574                                     src_buf, ptr1_align, false))
1575             break;
1576
1577           new_str_cst = build_string_literal (src_len, src_buf);
1578           if (callee1)
1579             {
1580               /* If STMT1 is a mem{,p}cpy call, adjust it and remove
1581                  memset call.  */
1582               if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1583                 gimple_call_set_lhs (stmt1, NULL_TREE);
1584               gimple_call_set_arg (stmt1, 1, new_str_cst);
1585               gimple_call_set_arg (stmt1, 2,
1586                                    build_int_cst (TREE_TYPE (len1), src_len));
1587               update_stmt (stmt1);
1588               unlink_stmt_vdef (stmt2);
1589               gsi_remove (gsi_p, true);
1590               release_defs (stmt2);
1591               if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1592                 release_ssa_name (lhs1);
1593               return true;
1594             }
1595           else
1596             {
1597               /* Otherwise, if STMT1 is length 1 memcpy optimized into
1598                  assignment, remove STMT1 and change memset call into
1599                  memcpy call.  */
1600               gimple_stmt_iterator gsi = gsi_for_stmt (stmt1);
1601
1602               if (!is_gimple_val (ptr1))
1603                 ptr1 = force_gimple_operand_gsi (gsi_p, ptr1, true, NULL_TREE,
1604                                                  true, GSI_SAME_STMT);
1605               gimple_call_set_fndecl (stmt2,
1606                                       builtin_decl_explicit (BUILT_IN_MEMCPY));
1607               gimple_call_set_arg (stmt2, 0, ptr1);
1608               gimple_call_set_arg (stmt2, 1, new_str_cst);
1609               gimple_call_set_arg (stmt2, 2,
1610                                    build_int_cst (TREE_TYPE (len2), src_len));
1611               unlink_stmt_vdef (stmt1);
1612               gsi_remove (&gsi, true);
1613               release_defs (stmt1);
1614               update_stmt (stmt2);
1615               return false;
1616             }
1617         }
1618       break;
1619     default:
1620       break;
1621     }
1622   return false;
1623 }
1624
1625 /* Checks if expression has type of one-bit precision, or is a known
1626    truth-valued expression.  */
1627 static bool
1628 truth_valued_ssa_name (tree name)
1629 {
1630   gimple def;
1631   tree type = TREE_TYPE (name);
1632
1633   if (!INTEGRAL_TYPE_P (type))
1634     return false;
1635   /* Don't check here for BOOLEAN_TYPE as the precision isn't
1636      necessarily one and so ~X is not equal to !X.  */
1637   if (TYPE_PRECISION (type) == 1)
1638     return true;
1639   def = SSA_NAME_DEF_STMT (name);
1640   if (is_gimple_assign (def))
1641     return truth_value_p (gimple_assign_rhs_code (def));
1642   return false;
1643 }
1644
1645 /* Helper routine for simplify_bitwise_binary_1 function.
1646    Return for the SSA name NAME the expression X if it mets condition
1647    NAME = !X. Otherwise return NULL_TREE.
1648    Detected patterns for NAME = !X are:
1649      !X and X == 0 for X with integral type.
1650      X ^ 1, X != 1,or ~X for X with integral type with precision of one.  */
1651 static tree
1652 lookup_logical_inverted_value (tree name)
1653 {
1654   tree op1, op2;
1655   enum tree_code code;
1656   gimple def;
1657
1658   /* If name has none-intergal type, or isn't a SSA_NAME, then
1659      return.  */
1660   if (TREE_CODE (name) != SSA_NAME
1661       || !INTEGRAL_TYPE_P (TREE_TYPE (name)))
1662     return NULL_TREE;
1663   def = SSA_NAME_DEF_STMT (name);
1664   if (!is_gimple_assign (def))
1665     return NULL_TREE;
1666
1667   code = gimple_assign_rhs_code (def);
1668   op1 = gimple_assign_rhs1 (def);
1669   op2 = NULL_TREE;
1670
1671   /* Get for EQ_EXPR or BIT_XOR_EXPR operation the second operand.
1672      If CODE isn't an EQ_EXPR, BIT_XOR_EXPR, or BIT_NOT_EXPR, then return.  */
1673   if (code == EQ_EXPR || code == NE_EXPR
1674       || code == BIT_XOR_EXPR)
1675     op2 = gimple_assign_rhs2 (def);
1676
1677   switch (code)
1678     {
1679     case BIT_NOT_EXPR:
1680       if (truth_valued_ssa_name (name))
1681         return op1;
1682       break;
1683     case EQ_EXPR:
1684       /* Check if we have X == 0 and X has an integral type.  */
1685       if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
1686         break;
1687       if (integer_zerop (op2))
1688         return op1;
1689       break;
1690     case NE_EXPR:
1691       /* Check if we have X != 1 and X is a truth-valued.  */
1692       if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
1693         break;
1694       if (integer_onep (op2) && truth_valued_ssa_name (op1))
1695         return op1;
1696       break;
1697     case BIT_XOR_EXPR:
1698       /* Check if we have X ^ 1 and X is truth valued.  */
1699       if (integer_onep (op2) && truth_valued_ssa_name (op1))
1700         return op1;
1701       break;
1702     default:
1703       break;
1704     }
1705
1706   return NULL_TREE;
1707 }
1708
1709 /* Optimize ARG1 CODE ARG2 to a constant for bitwise binary
1710    operations CODE, if one operand has the logically inverted
1711    value of the other.  */
1712 static tree
1713 simplify_bitwise_binary_1 (enum tree_code code, tree type,
1714                            tree arg1, tree arg2)
1715 {
1716   tree anot;
1717
1718   /* If CODE isn't a bitwise binary operation, return NULL_TREE.  */
1719   if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR
1720       && code != BIT_XOR_EXPR)
1721     return NULL_TREE;
1722
1723   /* First check if operands ARG1 and ARG2 are equal.  If so
1724      return NULL_TREE as this optimization is handled fold_stmt.  */
1725   if (arg1 == arg2)
1726     return NULL_TREE;
1727   /* See if we have in arguments logical-not patterns.  */
1728   if (((anot = lookup_logical_inverted_value (arg1)) == NULL_TREE
1729        || anot != arg2)
1730       && ((anot = lookup_logical_inverted_value (arg2)) == NULL_TREE
1731           || anot != arg1))
1732     return NULL_TREE;
1733
1734   /* X & !X -> 0.  */
1735   if (code == BIT_AND_EXPR)
1736     return fold_convert (type, integer_zero_node);
1737   /* X | !X -> 1 and X ^ !X -> 1, if X is truth-valued.  */
1738   if (truth_valued_ssa_name (anot))
1739     return fold_convert (type, integer_one_node);
1740
1741   /* ??? Otherwise result is (X != 0 ? X : 1).  not handled.  */
1742   return NULL_TREE;
1743 }
1744
1745 /* Simplify bitwise binary operations.
1746    Return true if a transformation applied, otherwise return false.  */
1747
1748 static bool
1749 simplify_bitwise_binary (gimple_stmt_iterator *gsi)
1750 {
1751   gimple stmt = gsi_stmt (*gsi);
1752   tree arg1 = gimple_assign_rhs1 (stmt);
1753   tree arg2 = gimple_assign_rhs2 (stmt);
1754   enum tree_code code = gimple_assign_rhs_code (stmt);
1755   tree res;
1756   gimple def1 = NULL, def2 = NULL;
1757   tree def1_arg1, def2_arg1;
1758   enum tree_code def1_code, def2_code;
1759
1760   def1_code = TREE_CODE (arg1);
1761   def1_arg1 = arg1;
1762   if (TREE_CODE (arg1) == SSA_NAME)
1763     {
1764       def1 = SSA_NAME_DEF_STMT (arg1);
1765       if (is_gimple_assign (def1))
1766         {
1767           def1_code = gimple_assign_rhs_code (def1);
1768           def1_arg1 = gimple_assign_rhs1 (def1);
1769         }
1770     }
1771
1772   def2_code = TREE_CODE (arg2);
1773   def2_arg1 = arg2;
1774   if (TREE_CODE (arg2) == SSA_NAME)
1775     {
1776       def2 = SSA_NAME_DEF_STMT (arg2);
1777       if (is_gimple_assign (def2))
1778         {
1779           def2_code = gimple_assign_rhs_code (def2);
1780           def2_arg1 = gimple_assign_rhs1 (def2);
1781         }
1782     }
1783
1784   /* Try to fold (type) X op CST -> (type) (X op ((type-x) CST)).  */
1785   if (TREE_CODE (arg2) == INTEGER_CST
1786       && CONVERT_EXPR_CODE_P (def1_code)
1787       && INTEGRAL_TYPE_P (TREE_TYPE (def1_arg1))
1788       && int_fits_type_p (arg2, TREE_TYPE (def1_arg1)))
1789     {
1790       gimple newop;
1791       tree tem = create_tmp_reg (TREE_TYPE (def1_arg1), NULL);
1792       newop =
1793         gimple_build_assign_with_ops (code, tem, def1_arg1,
1794                                       fold_convert_loc (gimple_location (stmt),
1795                                                         TREE_TYPE (def1_arg1),
1796                                                         arg2));
1797       tem = make_ssa_name (tem, newop);
1798       gimple_assign_set_lhs (newop, tem);
1799       gimple_set_location (newop, gimple_location (stmt));
1800       gsi_insert_before (gsi, newop, GSI_SAME_STMT);
1801       gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
1802                                         tem, NULL_TREE, NULL_TREE);
1803       update_stmt (gsi_stmt (*gsi));
1804       return true;
1805     }
1806
1807   /* For bitwise binary operations apply operand conversions to the
1808      binary operation result instead of to the operands.  This allows
1809      to combine successive conversions and bitwise binary operations.  */
1810   if (CONVERT_EXPR_CODE_P (def1_code)
1811       && CONVERT_EXPR_CODE_P (def2_code)
1812       && types_compatible_p (TREE_TYPE (def1_arg1), TREE_TYPE (def2_arg1))
1813       /* Make sure that the conversion widens the operands, or has same
1814          precision,  or that it changes the operation to a bitfield
1815          precision.  */
1816       && ((TYPE_PRECISION (TREE_TYPE (def1_arg1))
1817            <= TYPE_PRECISION (TREE_TYPE (arg1)))
1818           || (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (arg1)))
1819               != MODE_INT)
1820           || (TYPE_PRECISION (TREE_TYPE (arg1))
1821               != GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (arg1))))))
1822     {
1823       gimple newop;
1824       tree tem = create_tmp_reg (TREE_TYPE (def1_arg1),
1825                                  NULL);
1826       newop = gimple_build_assign_with_ops (code, tem, def1_arg1, def2_arg1);
1827       tem = make_ssa_name (tem, newop);
1828       gimple_assign_set_lhs (newop, tem);
1829       gimple_set_location (newop, gimple_location (stmt));
1830       gsi_insert_before (gsi, newop, GSI_SAME_STMT);
1831       gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
1832                                         tem, NULL_TREE, NULL_TREE);
1833       update_stmt (gsi_stmt (*gsi));
1834       return true;
1835     }
1836
1837   /* (a | CST1) & CST2  ->  (a & CST2) | (CST1 & CST2).  */
1838   if (code == BIT_AND_EXPR
1839       && def1_code == BIT_IOR_EXPR
1840       && TREE_CODE (arg2) == INTEGER_CST
1841       && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST)
1842     {
1843       tree cst = fold_build2 (BIT_AND_EXPR, TREE_TYPE (arg2),
1844                               arg2, gimple_assign_rhs2 (def1));
1845       tree tem;
1846       gimple newop;
1847       if (integer_zerop (cst))
1848         {
1849           gimple_assign_set_rhs1 (stmt, def1_arg1);
1850           update_stmt (stmt);
1851           return true;
1852         }
1853       tem = create_tmp_reg (TREE_TYPE (arg2), NULL);
1854       newop = gimple_build_assign_with_ops (BIT_AND_EXPR,
1855                                             tem, def1_arg1, arg2);
1856       tem = make_ssa_name (tem, newop);
1857       gimple_assign_set_lhs (newop, tem);
1858       gimple_set_location (newop, gimple_location (stmt));
1859       /* Make sure to re-process the new stmt as it's walking upwards.  */
1860       gsi_insert_before (gsi, newop, GSI_NEW_STMT);
1861       gimple_assign_set_rhs1 (stmt, tem);
1862       gimple_assign_set_rhs2 (stmt, cst);
1863       gimple_assign_set_rhs_code (stmt, BIT_IOR_EXPR);
1864       update_stmt (stmt);
1865       return true;
1866     }
1867
1868   /* Combine successive equal operations with constants.  */
1869   if ((code == BIT_AND_EXPR
1870        || code == BIT_IOR_EXPR
1871        || code == BIT_XOR_EXPR)
1872       && def1_code == code
1873       && TREE_CODE (arg2) == INTEGER_CST
1874       && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST)
1875     {
1876       tree cst = fold_build2 (code, TREE_TYPE (arg2),
1877                               arg2, gimple_assign_rhs2 (def1));
1878       gimple_assign_set_rhs1 (stmt, def1_arg1);
1879       gimple_assign_set_rhs2 (stmt, cst);
1880       update_stmt (stmt);
1881       return true;
1882     }
1883
1884   /* Canonicalize X ^ ~0 to ~X.  */
1885   if (code == BIT_XOR_EXPR
1886       && TREE_CODE (arg2) == INTEGER_CST
1887       && integer_all_onesp (arg2))
1888     {
1889       gimple_assign_set_rhs_with_ops (gsi, BIT_NOT_EXPR, arg1, NULL_TREE);
1890       gcc_assert (gsi_stmt (*gsi) == stmt);
1891       update_stmt (stmt);
1892       return true;
1893     }
1894
1895   /* Try simple folding for X op !X, and X op X.  */
1896   res = simplify_bitwise_binary_1 (code, TREE_TYPE (arg1), arg1, arg2);
1897   if (res != NULL_TREE)
1898     {
1899       gimple_assign_set_rhs_from_tree (gsi, res);
1900       update_stmt (gsi_stmt (*gsi));
1901       return true;
1902     }
1903
1904   return false;
1905 }
1906
1907
1908 /* Perform re-associations of the plus or minus statement STMT that are
1909    always permitted.  Returns true if the CFG was changed.  */
1910
1911 static bool
1912 associate_plusminus (gimple_stmt_iterator *gsi)
1913 {
1914   gimple stmt = gsi_stmt (*gsi);
1915   tree rhs1 = gimple_assign_rhs1 (stmt);
1916   tree rhs2 = gimple_assign_rhs2 (stmt);
1917   enum tree_code code = gimple_assign_rhs_code (stmt);
1918   bool changed;
1919
1920   /* We can't reassociate at all for saturating types.  */
1921   if (TYPE_SATURATING (TREE_TYPE (rhs1)))
1922     return false;
1923
1924   /* First contract negates.  */
1925   do
1926     {
1927       changed = false;
1928
1929       /* A +- (-B) -> A -+ B.  */
1930       if (TREE_CODE (rhs2) == SSA_NAME)
1931         {
1932           gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
1933           if (is_gimple_assign (def_stmt)
1934               && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
1935               && can_propagate_from (def_stmt))
1936             {
1937               code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR;
1938               gimple_assign_set_rhs_code (stmt, code);
1939               rhs2 = gimple_assign_rhs1 (def_stmt);
1940               gimple_assign_set_rhs2 (stmt, rhs2);
1941               gimple_set_modified (stmt, true);
1942               changed = true;
1943             }
1944         }
1945
1946       /* (-A) + B -> B - A.  */
1947       if (TREE_CODE (rhs1) == SSA_NAME
1948           && code == PLUS_EXPR)
1949         {
1950           gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
1951           if (is_gimple_assign (def_stmt)
1952               && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
1953               && can_propagate_from (def_stmt))
1954             {
1955               code = MINUS_EXPR;
1956               gimple_assign_set_rhs_code (stmt, code);
1957               rhs1 = rhs2;
1958               gimple_assign_set_rhs1 (stmt, rhs1);
1959               rhs2 = gimple_assign_rhs1 (def_stmt);
1960               gimple_assign_set_rhs2 (stmt, rhs2);
1961               gimple_set_modified (stmt, true);
1962               changed = true;
1963             }
1964         }
1965     }
1966   while (changed);
1967
1968   /* We can't reassociate floating-point or fixed-point plus or minus
1969      because of saturation to +-Inf.  */
1970   if (FLOAT_TYPE_P (TREE_TYPE (rhs1))
1971       || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1)))
1972     goto out;
1973
1974   /* Second match patterns that allow contracting a plus-minus pair
1975      irrespective of overflow issues.
1976
1977         (A +- B) - A       ->  +- B
1978         (A +- B) -+ B      ->  A
1979         (CST +- A) +- CST  ->  CST +- A
1980         (A + CST) +- CST   ->  A + CST
1981         ~A + A             ->  -1
1982         ~A + 1             ->  -A
1983         A - (A +- B)       ->  -+ B
1984         A +- (B +- A)      ->  +- B
1985         CST +- (CST +- A)  ->  CST +- A
1986         CST +- (A +- CST)  ->  CST +- A
1987         A + ~A             ->  -1
1988
1989      via commutating the addition and contracting operations to zero
1990      by reassociation.  */
1991
1992   if (TREE_CODE (rhs1) == SSA_NAME)
1993     {
1994       gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
1995       if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
1996         {
1997           enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
1998           if (def_code == PLUS_EXPR
1999               || def_code == MINUS_EXPR)
2000             {
2001               tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2002               tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
2003               if (operand_equal_p (def_rhs1, rhs2, 0)
2004                   && code == MINUS_EXPR)
2005                 {
2006                   /* (A +- B) - A -> +- B.  */
2007                   code = ((def_code == PLUS_EXPR)
2008                           ? TREE_CODE (def_rhs2) : NEGATE_EXPR);
2009                   rhs1 = def_rhs2;
2010                   rhs2 = NULL_TREE;
2011                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2012                   gcc_assert (gsi_stmt (*gsi) == stmt);
2013                   gimple_set_modified (stmt, true);
2014                 }
2015               else if (operand_equal_p (def_rhs2, rhs2, 0)
2016                        && code != def_code)
2017                 {
2018                   /* (A +- B) -+ B -> A.  */
2019                   code = TREE_CODE (def_rhs1);
2020                   rhs1 = def_rhs1;
2021                   rhs2 = NULL_TREE;
2022                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2023                   gcc_assert (gsi_stmt (*gsi) == stmt);
2024                   gimple_set_modified (stmt, true);
2025                 }
2026               else if (TREE_CODE (rhs2) == INTEGER_CST
2027                        && TREE_CODE (def_rhs1) == INTEGER_CST)
2028                 {
2029                   /* (CST +- A) +- CST -> CST +- A.  */
2030                   tree cst = fold_binary (code, TREE_TYPE (rhs1),
2031                                           def_rhs1, rhs2);
2032                   if (cst && !TREE_OVERFLOW (cst))
2033                     {
2034                       code = def_code;
2035                       gimple_assign_set_rhs_code (stmt, code);
2036                       rhs1 = cst;
2037                       gimple_assign_set_rhs1 (stmt, rhs1);
2038                       rhs2 = def_rhs2;
2039                       gimple_assign_set_rhs2 (stmt, rhs2);
2040                       gimple_set_modified (stmt, true);
2041                     }
2042                 }
2043               else if (TREE_CODE (rhs2) == INTEGER_CST
2044                        && TREE_CODE (def_rhs2) == INTEGER_CST
2045                        && def_code == PLUS_EXPR)
2046                 {
2047                   /* (A + CST) +- CST -> A + CST.  */
2048                   tree cst = fold_binary (code, TREE_TYPE (rhs1),
2049                                           def_rhs2, rhs2);
2050                   if (cst && !TREE_OVERFLOW (cst))
2051                     {
2052                       code = PLUS_EXPR;
2053                       gimple_assign_set_rhs_code (stmt, code);
2054                       rhs1 = def_rhs1;
2055                       gimple_assign_set_rhs1 (stmt, rhs1);
2056                       rhs2 = cst;
2057                       gimple_assign_set_rhs2 (stmt, rhs2);
2058                       gimple_set_modified (stmt, true);
2059                     }
2060                 }
2061             }
2062           else if (def_code == BIT_NOT_EXPR
2063                    && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
2064             {
2065               tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2066               if (code == PLUS_EXPR
2067                   && operand_equal_p (def_rhs1, rhs2, 0))
2068                 {
2069                   /* ~A + A -> -1.  */
2070                   code = INTEGER_CST;
2071                   rhs1 = build_int_cst_type (TREE_TYPE (rhs2), -1);
2072                   rhs2 = NULL_TREE;
2073                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2074                   gcc_assert (gsi_stmt (*gsi) == stmt);
2075                   gimple_set_modified (stmt, true);
2076                 }
2077               else if (code == PLUS_EXPR
2078                        && integer_onep (rhs1))
2079                 {
2080                   /* ~A + 1 -> -A.  */
2081                   code = NEGATE_EXPR;
2082                   rhs1 = def_rhs1;
2083                   rhs2 = NULL_TREE;
2084                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2085                   gcc_assert (gsi_stmt (*gsi) == stmt);
2086                   gimple_set_modified (stmt, true);
2087                 }
2088             }
2089         }
2090     }
2091
2092   if (rhs2 && TREE_CODE (rhs2) == SSA_NAME)
2093     {
2094       gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
2095       if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
2096         {
2097           enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
2098           if (def_code == PLUS_EXPR
2099               || def_code == MINUS_EXPR)
2100             {
2101               tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2102               tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
2103               if (operand_equal_p (def_rhs1, rhs1, 0)
2104                   && code == MINUS_EXPR)
2105                 {
2106                   /* A - (A +- B) -> -+ B.  */
2107                   code = ((def_code == PLUS_EXPR)
2108                           ? NEGATE_EXPR : TREE_CODE (def_rhs2));
2109                   rhs1 = def_rhs2;
2110                   rhs2 = NULL_TREE;
2111                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2112                   gcc_assert (gsi_stmt (*gsi) == stmt);
2113                   gimple_set_modified (stmt, true);
2114                 }
2115               else if (operand_equal_p (def_rhs2, rhs1, 0)
2116                        && code != def_code)
2117                 {
2118                   /* A +- (B +- A) -> +- B.  */
2119                   code = ((code == PLUS_EXPR)
2120                           ? TREE_CODE (def_rhs1) : NEGATE_EXPR);
2121                   rhs1 = def_rhs1;
2122                   rhs2 = NULL_TREE;
2123                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2124                   gcc_assert (gsi_stmt (*gsi) == stmt);
2125                   gimple_set_modified (stmt, true);
2126                 }
2127               else if (TREE_CODE (rhs1) == INTEGER_CST
2128                        && TREE_CODE (def_rhs1) == INTEGER_CST)
2129                 {
2130                   /* CST +- (CST +- A) -> CST +- A.  */
2131                   tree cst = fold_binary (code, TREE_TYPE (rhs2),
2132                                           rhs1, def_rhs1);
2133                   if (cst && !TREE_OVERFLOW (cst))
2134                     {
2135                       code = (code == def_code ? PLUS_EXPR : MINUS_EXPR);
2136                       gimple_assign_set_rhs_code (stmt, code);
2137                       rhs1 = cst;
2138                       gimple_assign_set_rhs1 (stmt, rhs1);
2139                       rhs2 = def_rhs2;
2140                       gimple_assign_set_rhs2 (stmt, rhs2);
2141                       gimple_set_modified (stmt, true);
2142                     }
2143                 }
2144               else if (TREE_CODE (rhs1) == INTEGER_CST
2145                        && TREE_CODE (def_rhs2) == INTEGER_CST)
2146                 {
2147                   /* CST +- (A +- CST) -> CST +- A.  */
2148                   tree cst = fold_binary (def_code == code
2149                                           ? PLUS_EXPR : MINUS_EXPR,
2150                                           TREE_TYPE (rhs2),
2151                                           rhs1, def_rhs2);
2152                   if (cst && !TREE_OVERFLOW (cst))
2153                     {
2154                       rhs1 = cst;
2155                       gimple_assign_set_rhs1 (stmt, rhs1);
2156                       rhs2 = def_rhs1;
2157                       gimple_assign_set_rhs2 (stmt, rhs2);
2158                       gimple_set_modified (stmt, true);
2159                     }
2160                 }
2161             }
2162           else if (def_code == BIT_NOT_EXPR
2163                    && INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
2164             {
2165               tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2166               if (code == PLUS_EXPR
2167                   && operand_equal_p (def_rhs1, rhs1, 0))
2168                 {
2169                   /* A + ~A -> -1.  */
2170                   code = INTEGER_CST;
2171                   rhs1 = build_int_cst_type (TREE_TYPE (rhs1), -1);
2172                   rhs2 = NULL_TREE;
2173                   gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2174                   gcc_assert (gsi_stmt (*gsi) == stmt);
2175                   gimple_set_modified (stmt, true);
2176                 }
2177             }
2178         }
2179     }
2180
2181 out:
2182   if (gimple_modified_p (stmt))
2183     {
2184       fold_stmt_inplace (gsi);
2185       update_stmt (stmt);
2186       if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
2187           && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
2188         return true;
2189     }
2190
2191   return false;
2192 }
2193
2194 /* Combine two conversions in a row for the second conversion at *GSI.
2195    Returns 1 if there were any changes made, 2 if cfg-cleanup needs to
2196    run.  Else it returns 0.  */
2197
2198 static int
2199 combine_conversions (gimple_stmt_iterator *gsi)
2200 {
2201   gimple stmt = gsi_stmt (*gsi);
2202   gimple def_stmt;
2203   tree op0, lhs;
2204   enum tree_code code = gimple_assign_rhs_code (stmt);
2205
2206   gcc_checking_assert (CONVERT_EXPR_CODE_P (code)
2207                        || code == FLOAT_EXPR
2208                        || code == FIX_TRUNC_EXPR);
2209
2210   lhs = gimple_assign_lhs (stmt);
2211   op0 = gimple_assign_rhs1 (stmt);
2212   if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (op0)))
2213     {
2214       gimple_assign_set_rhs_code (stmt, TREE_CODE (op0));
2215       return 1;
2216     }
2217
2218   if (TREE_CODE (op0) != SSA_NAME)
2219     return 0;
2220
2221   def_stmt = SSA_NAME_DEF_STMT (op0);
2222   if (!is_gimple_assign (def_stmt))
2223     return 0;
2224
2225   if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
2226     {
2227       tree defop0 = gimple_assign_rhs1 (def_stmt);
2228       tree type = TREE_TYPE (lhs);
2229       tree inside_type = TREE_TYPE (defop0);
2230       tree inter_type = TREE_TYPE (op0);
2231       int inside_int = INTEGRAL_TYPE_P (inside_type);
2232       int inside_ptr = POINTER_TYPE_P (inside_type);
2233       int inside_float = FLOAT_TYPE_P (inside_type);
2234       int inside_vec = TREE_CODE (inside_type) == VECTOR_TYPE;
2235       unsigned int inside_prec = TYPE_PRECISION (inside_type);
2236       int inside_unsignedp = TYPE_UNSIGNED (inside_type);
2237       int inter_int = INTEGRAL_TYPE_P (inter_type);
2238       int inter_ptr = POINTER_TYPE_P (inter_type);
2239       int inter_float = FLOAT_TYPE_P (inter_type);
2240       int inter_vec = TREE_CODE (inter_type) == VECTOR_TYPE;
2241       unsigned int inter_prec = TYPE_PRECISION (inter_type);
2242       int inter_unsignedp = TYPE_UNSIGNED (inter_type);
2243       int final_int = INTEGRAL_TYPE_P (type);
2244       int final_ptr = POINTER_TYPE_P (type);
2245       int final_float = FLOAT_TYPE_P (type);
2246       int final_vec = TREE_CODE (type) == VECTOR_TYPE;
2247       unsigned int final_prec = TYPE_PRECISION (type);
2248       int final_unsignedp = TYPE_UNSIGNED (type);
2249
2250       /* Don't propagate ssa names that occur in abnormal phis.  */
2251       if (TREE_CODE (defop0) == SSA_NAME
2252           && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defop0))
2253         return 0;
2254
2255       /* In addition to the cases of two conversions in a row
2256          handled below, if we are converting something to its own
2257          type via an object of identical or wider precision, neither
2258          conversion is needed.  */
2259       if (useless_type_conversion_p (type, inside_type)
2260           && (((inter_int || inter_ptr) && final_int)
2261               || (inter_float && final_float))
2262           && inter_prec >= final_prec)
2263         {
2264           gimple_assign_set_rhs1 (stmt, unshare_expr (defop0));
2265           gimple_assign_set_rhs_code (stmt, TREE_CODE (defop0));
2266           update_stmt (stmt);
2267           return remove_prop_source_from_use (op0) ? 2 : 1;
2268         }
2269
2270       /* Likewise, if the intermediate and initial types are either both
2271          float or both integer, we don't need the middle conversion if the
2272          former is wider than the latter and doesn't change the signedness
2273          (for integers).  Avoid this if the final type is a pointer since
2274          then we sometimes need the middle conversion.  Likewise if the
2275          final type has a precision not equal to the size of its mode.  */
2276       if (((inter_int && inside_int)
2277            || (inter_float && inside_float)
2278            || (inter_vec && inside_vec))
2279           && inter_prec >= inside_prec
2280           && (inter_float || inter_vec
2281               || inter_unsignedp == inside_unsignedp)
2282           && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (type))
2283                 && TYPE_MODE (type) == TYPE_MODE (inter_type))
2284           && ! final_ptr
2285           && (! final_vec || inter_prec == inside_prec))
2286         {
2287           gimple_assign_set_rhs1 (stmt, defop0);
2288           update_stmt (stmt);
2289           return remove_prop_source_from_use (op0) ? 2 : 1;
2290         }
2291
2292       /* If we have a sign-extension of a zero-extended value, we can
2293          replace that by a single zero-extension.  */
2294       if (inside_int && inter_int && final_int
2295           && inside_prec < inter_prec && inter_prec < final_prec
2296           && inside_unsignedp && !inter_unsignedp)
2297         {
2298           gimple_assign_set_rhs1 (stmt, defop0);
2299           update_stmt (stmt);
2300           return remove_prop_source_from_use (op0) ? 2 : 1;
2301         }
2302
2303       /* Two conversions in a row are not needed unless:
2304          - some conversion is floating-point (overstrict for now), or
2305          - some conversion is a vector (overstrict for now), or
2306          - the intermediate type is narrower than both initial and
2307          final, or
2308          - the intermediate type and innermost type differ in signedness,
2309          and the outermost type is wider than the intermediate, or
2310          - the initial type is a pointer type and the precisions of the
2311          intermediate and final types differ, or
2312          - the final type is a pointer type and the precisions of the
2313          initial and intermediate types differ.  */
2314       if (! inside_float && ! inter_float && ! final_float
2315           && ! inside_vec && ! inter_vec && ! final_vec
2316           && (inter_prec >= inside_prec || inter_prec >= final_prec)
2317           && ! (inside_int && inter_int
2318                 && inter_unsignedp != inside_unsignedp
2319                 && inter_prec < final_prec)
2320           && ((inter_unsignedp && inter_prec > inside_prec)
2321               == (final_unsignedp && final_prec > inter_prec))
2322           && ! (inside_ptr && inter_prec != final_prec)
2323           && ! (final_ptr && inside_prec != inter_prec)
2324           && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (type))
2325                 && TYPE_MODE (type) == TYPE_MODE (inter_type)))
2326         {
2327           gimple_assign_set_rhs1 (stmt, defop0);
2328           update_stmt (stmt);
2329           return remove_prop_source_from_use (op0) ? 2 : 1;
2330         }
2331
2332       /* A truncation to an unsigned type should be canonicalized as
2333          bitwise and of a mask.  */
2334       if (final_int && inter_int && inside_int
2335           && final_prec == inside_prec
2336           && final_prec > inter_prec
2337           && inter_unsignedp)
2338         {
2339           tree tem;
2340           tem = fold_build2 (BIT_AND_EXPR, inside_type,
2341                              defop0,
2342                              double_int_to_tree
2343                                (inside_type, double_int_mask (inter_prec)));
2344           if (!useless_type_conversion_p (type, inside_type))
2345             {
2346               tem = force_gimple_operand_gsi (gsi, tem, true, NULL_TREE, true,
2347                                               GSI_SAME_STMT);
2348               gimple_assign_set_rhs1 (stmt, tem);
2349             }
2350           else
2351             gimple_assign_set_rhs_from_tree (gsi, tem);
2352           update_stmt (gsi_stmt (*gsi));
2353           return 1;
2354         }
2355     }
2356
2357   return 0;
2358 }
2359
2360 /* Main entry point for the forward propagation and statement combine
2361    optimizer.  */
2362
2363 static unsigned int
2364 ssa_forward_propagate_and_combine (void)
2365 {
2366   basic_block bb;
2367   unsigned int todoflags = 0;
2368
2369   cfg_changed = false;
2370
2371   FOR_EACH_BB (bb)
2372     {
2373       gimple_stmt_iterator gsi, prev;
2374       bool prev_initialized;
2375
2376       /* Apply forward propagation to all stmts in the basic-block.
2377          Note we update GSI within the loop as necessary.  */
2378       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2379         {
2380           gimple stmt = gsi_stmt (gsi);
2381           tree lhs, rhs;
2382           enum tree_code code;
2383
2384           if (!is_gimple_assign (stmt))
2385             {
2386               gsi_next (&gsi);
2387               continue;
2388             }
2389
2390           lhs = gimple_assign_lhs (stmt);
2391           rhs = gimple_assign_rhs1 (stmt);
2392           code = gimple_assign_rhs_code (stmt);
2393           if (TREE_CODE (lhs) != SSA_NAME
2394               || has_zero_uses (lhs))
2395             {
2396               gsi_next (&gsi);
2397               continue;
2398             }
2399
2400           /* If this statement sets an SSA_NAME to an address,
2401              try to propagate the address into the uses of the SSA_NAME.  */
2402           if (code == ADDR_EXPR
2403               /* Handle pointer conversions on invariant addresses
2404                  as well, as this is valid gimple.  */
2405               || (CONVERT_EXPR_CODE_P (code)
2406                   && TREE_CODE (rhs) == ADDR_EXPR
2407                   && POINTER_TYPE_P (TREE_TYPE (lhs))))
2408             {
2409               tree base = get_base_address (TREE_OPERAND (rhs, 0));
2410               if ((!base
2411                    || !DECL_P (base)
2412                    || decl_address_invariant_p (base))
2413                   && !stmt_references_abnormal_ssa_name (stmt)
2414                   && forward_propagate_addr_expr (lhs, rhs))
2415                 {
2416                   release_defs (stmt);
2417                   todoflags |= TODO_remove_unused_locals;
2418                   gsi_remove (&gsi, true);
2419                 }
2420               else
2421                 gsi_next (&gsi);
2422             }
2423           else if (code == POINTER_PLUS_EXPR)
2424             {
2425               tree off = gimple_assign_rhs2 (stmt);
2426               if (TREE_CODE (off) == INTEGER_CST
2427                   && can_propagate_from (stmt)
2428                   && !simple_iv_increment_p (stmt)
2429                   /* ???  Better adjust the interface to that function
2430                      instead of building new trees here.  */
2431                   && forward_propagate_addr_expr
2432                        (lhs,
2433                         build1_loc (gimple_location (stmt),
2434                                     ADDR_EXPR, TREE_TYPE (rhs),
2435                                     fold_build2 (MEM_REF,
2436                                                  TREE_TYPE (TREE_TYPE (rhs)),
2437                                                  rhs,
2438                                                  fold_convert (ptr_type_node,
2439                                                                off)))))
2440                 {
2441                   release_defs (stmt);
2442                   todoflags |= TODO_remove_unused_locals;
2443                   gsi_remove (&gsi, true);
2444                 }
2445               else if (is_gimple_min_invariant (rhs))
2446                 {
2447                   /* Make sure to fold &a[0] + off_1 here.  */
2448                   fold_stmt_inplace (&gsi);
2449                   update_stmt (stmt);
2450                   if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
2451                     gsi_next (&gsi);
2452                 }
2453               else
2454                 gsi_next (&gsi);
2455             }
2456           else if (TREE_CODE_CLASS (code) == tcc_comparison)
2457             {
2458               if (forward_propagate_comparison (stmt))
2459                 cfg_changed = true;
2460               gsi_next (&gsi);
2461             }
2462           else
2463             gsi_next (&gsi);
2464         }
2465
2466       /* Combine stmts with the stmts defining their operands.
2467          Note we update GSI within the loop as necessary.  */
2468       prev_initialized = false;
2469       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
2470         {
2471           gimple stmt = gsi_stmt (gsi);
2472           bool changed = false;
2473
2474           switch (gimple_code (stmt))
2475             {
2476             case GIMPLE_ASSIGN:
2477               {
2478                 tree rhs1 = gimple_assign_rhs1 (stmt);
2479                 enum tree_code code = gimple_assign_rhs_code (stmt);
2480
2481                 if ((code == BIT_NOT_EXPR
2482                      || code == NEGATE_EXPR)
2483                     && TREE_CODE (rhs1) == SSA_NAME)
2484                   changed = simplify_not_neg_expr (&gsi);
2485                 else if (code == COND_EXPR)
2486                   {
2487                     /* In this case the entire COND_EXPR is in rhs1. */
2488                     changed |= forward_propagate_into_cond (&gsi);
2489                     stmt = gsi_stmt (gsi);
2490                   }
2491                 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2492                   {
2493                     int did_something;
2494                     did_something = forward_propagate_into_comparison (&gsi);
2495                     if (did_something == 2)
2496                       cfg_changed = true;
2497                     changed = did_something != 0;
2498                   }
2499                 else if (code == BIT_AND_EXPR
2500                          || code == BIT_IOR_EXPR
2501                          || code == BIT_XOR_EXPR)
2502                   changed = simplify_bitwise_binary (&gsi);
2503                 else if (code == PLUS_EXPR
2504                          || code == MINUS_EXPR)
2505                   changed = associate_plusminus (&gsi);
2506                 else if (CONVERT_EXPR_CODE_P (code)
2507                          || code == FLOAT_EXPR
2508                          || code == FIX_TRUNC_EXPR)
2509                   {
2510                     int did_something = combine_conversions (&gsi);
2511                     if (did_something == 2)
2512                       cfg_changed = true;
2513                     changed = did_something != 0;
2514                   }
2515                 break;
2516               }
2517
2518             case GIMPLE_SWITCH:
2519               changed = simplify_gimple_switch (stmt);
2520               break;
2521
2522             case GIMPLE_COND:
2523               {
2524                 int did_something;
2525                 did_something = forward_propagate_into_gimple_cond (stmt);
2526                 if (did_something == 2)
2527                   cfg_changed = true;
2528                 changed = did_something != 0;
2529                 break;
2530               }
2531
2532             case GIMPLE_CALL:
2533               {
2534                 tree callee = gimple_call_fndecl (stmt);
2535                 if (callee != NULL_TREE
2536                     && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
2537                   changed = simplify_builtin_call (&gsi, callee);
2538                 break;
2539               }
2540
2541             default:;
2542             }
2543
2544           if (changed)
2545             {
2546               /* If the stmt changed then re-visit it and the statements
2547                  inserted before it.  */
2548               if (!prev_initialized)
2549                 gsi = gsi_start_bb (bb);
2550               else
2551                 {
2552                   gsi = prev;
2553                   gsi_next (&gsi);
2554                 }
2555             }
2556           else
2557             {
2558               prev = gsi;
2559               prev_initialized = true;
2560               gsi_next (&gsi);
2561             }
2562         }
2563     }
2564
2565   if (cfg_changed)
2566     todoflags |= TODO_cleanup_cfg;
2567
2568   return todoflags;
2569 }
2570
2571
2572 static bool
2573 gate_forwprop (void)
2574 {
2575   return flag_tree_forwprop;
2576 }
2577
2578 struct gimple_opt_pass pass_forwprop =
2579 {
2580  {
2581   GIMPLE_PASS,
2582   "forwprop",                   /* name */
2583   gate_forwprop,                /* gate */
2584   ssa_forward_propagate_and_combine,    /* execute */
2585   NULL,                         /* sub */
2586   NULL,                         /* next */
2587   0,                            /* static_pass_number */
2588   TV_TREE_FORWPROP,             /* tv_id */
2589   PROP_cfg | PROP_ssa,          /* properties_required */
2590   0,                            /* properties_provided */
2591   0,                            /* properties_destroyed */
2592   0,                            /* todo_flags_start */
2593   TODO_ggc_collect
2594   | TODO_update_ssa
2595   | TODO_verify_ssa             /* todo_flags_finish */
2596  }
2597 };