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