gcc/tree-ssa-phiopt.c

   1 /* Optimization of PHI nodes by converting them into straightline code.
   2    Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 3, or (at your option) any
   9 later version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT
  12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "tm.h"
  24 #include "ggc.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "flags.h"
  28 #include "tm_p.h"
  29 #include "basic-block.h"
  30 #include "timevar.h"
  31 #include "diagnostic.h"
  32 #include "tree-flow.h"
  33 #include "tree-pass.h"
  34 #include "tree-dump.h"
  35 #include "langhooks.h"
  36 #include "pointer-set.h"
  37 #include "domwalk.h"
  38
  39 static unsigned int tree_ssa_phiopt_worker (bool);
  40 static bool conditional_replacement (basic_block, basic_block,
  41                                      edge, edge, tree, tree, tree);
  42 static bool value_replacement (basic_block, basic_block,
  43                                edge, edge, tree, tree, tree);
  44 static bool minmax_replacement (basic_block, basic_block,
  45                                 edge, edge, tree, tree, tree);
  46 static bool abs_replacement (basic_block, basic_block,
  47                              edge, edge, tree, tree, tree);
  48 static bool cond_store_replacement (basic_block, basic_block, edge, edge,
  49                                     struct pointer_set_t *);
  50 static struct pointer_set_t * get_non_trapping (void);
  51 static void replace_phi_edge_with_variable (basic_block, edge, tree, tree);
  52
  53 /* This pass tries to replaces an if-then-else block with an
  54    assignment.  We have four kinds of transformations.  Some of these
  55    transformations are also performed by the ifcvt RTL optimizer.
  56
  57    Conditional Replacement
  58    -----------------------
  59
  60    This transformation, implemented in conditional_replacement,
  61    replaces
  62
  63      bb0:
  64       if (cond) goto bb2; else goto bb1;
  65      bb1:
  66      bb2:
  67       x = PHI <0 (bb1), 1 (bb0), ...>;
  68
  69    with
  70
  71      bb0:
  72       x' = cond;
  73       goto bb2;
  74      bb2:
  75       x = PHI <x' (bb0), ...>;
  76
  77    We remove bb1 as it becomes unreachable.  This occurs often due to
  78    gimplification of conditionals.
  79
  80    Value Replacement
  81    -----------------
  82
  83    This transformation, implemented in value_replacement, replaces
  84
  85      bb0:
  86        if (a != b) goto bb2; else goto bb1;
  87      bb1:
  88      bb2:
  89        x = PHI <a (bb1), b (bb0), ...>;
  90
  91    with
  92
  93      bb0:
  94      bb2:
  95        x = PHI <b (bb0), ...>;
  96
  97    This opportunity can sometimes occur as a result of other
  98    optimizations.
  99
 100    ABS Replacement
 101    ---------------
 102
 103    This transformation, implemented in abs_replacement, replaces
 104
 105      bb0:
 106        if (a >= 0) goto bb2; else goto bb1;
 107      bb1:
 108        x = -a;
 109      bb2:
 110        x = PHI <x (bb1), a (bb0), ...>;
 111
 112    with
 113
 114      bb0:
 115        x' = ABS_EXPR< a >;
 116      bb2:
 117        x = PHI <x' (bb0), ...>;
 118
 119    MIN/MAX Replacement
 120    -------------------
 121
 122    This transformation, minmax_replacement replaces
 123
 124      bb0:
 125        if (a <= b) goto bb2; else goto bb1;
 126      bb1:
 127      bb2:
 128        x = PHI <b (bb1), a (bb0), ...>;
 129
 130    with
 131
 132      bb0:
 133        x' = MIN_EXPR (a, b)
 134      bb2:
 135        x = PHI <x' (bb0), ...>;
 136
 137    A similar transformation is done for MAX_EXPR.  */
 138
 139 static unsigned int
 140 tree_ssa_phiopt (void)
 141 {
 142   return tree_ssa_phiopt_worker (false);
 143 }
 144
 145 /* This pass tries to transform conditional stores into unconditional
 146    ones, enabling further simplifications with the simpler then and else
 147    blocks.  In particular it replaces this:
 148
 149      bb0:
 150        if (cond) goto bb2; else goto bb1;
 151      bb1:
 152        *p = RHS
 153      bb2:
 154
 155    with
 156
 157      bb0:
 158        if (cond) goto bb1; else goto bb2;
 159      bb1:
 160        condtmp' = *p;
 161      bb2:
 162        condtmp = PHI <RHS, condtmp'>
 163        *p = condtmp
 164
 165    This transformation can only be done under several constraints,
 166    documented below.  */
 167
 168 static unsigned int
 169 tree_ssa_cs_elim (void)
 170 {
 171   return tree_ssa_phiopt_worker (true);
 172 }
 173
 174 /* For conditional store replacement we need a temporary to
 175    put the old contents of the memory in.  */
 176 static tree condstoretemp;
 177
 178 /* The core routine of conditional store replacement and normal
 179    phi optimizations.  Both share much of the infrastructure in how
 180    to match applicable basic block patterns.  DO_STORE_ELIM is true
 181    when we want to do conditional store replacement, false otherwise.  */
 182 static unsigned int
 183 tree_ssa_phiopt_worker (bool do_store_elim)
 184 {
 185   basic_block bb;
 186   basic_block *bb_order;
 187   unsigned n, i;
 188   bool cfgchanged = false;
 189   struct pointer_set_t *nontrap = 0;
 190
 191   if (do_store_elim)
 192     {
 193       condstoretemp = NULL_TREE;
 194       /* Calculate the set of non-trapping memory accesses.  */
 195       nontrap = get_non_trapping ();
 196     }
 197
 198   /* Search every basic block for COND_EXPR we may be able to optimize.
 199
 200      We walk the blocks in order that guarantees that a block with
 201      a single predecessor is processed before the predecessor.
 202      This ensures that we collapse inner ifs before visiting the
 203      outer ones, and also that we do not try to visit a removed
 204      block.  */
 205   bb_order = blocks_in_phiopt_order ();
 206   n = n_basic_blocks - NUM_FIXED_BLOCKS;
 207
 208   for (i = 0; i < n; i++)
 209     {
 210       tree cond_expr;
 211       tree phi;
 212       basic_block bb1, bb2;
 213       edge e1, e2;
 214       tree arg0, arg1;
 215
 216       bb = bb_order[i];
 217
 218       cond_expr = last_stmt (bb);
 219       /* Check to see if the last statement is a COND_EXPR.  */
 220       if (!cond_expr
 221           || TREE_CODE (cond_expr) != COND_EXPR)
 222         continue;
 223
 224       e1 = EDGE_SUCC (bb, 0);
 225       bb1 = e1->dest;
 226       e2 = EDGE_SUCC (bb, 1);
 227       bb2 = e2->dest;
 228
 229       /* We cannot do the optimization on abnormal edges.  */
 230       if ((e1->flags & EDGE_ABNORMAL) != 0
 231           || (e2->flags & EDGE_ABNORMAL) != 0)
 232        continue;
 233
 234       /* If either bb1's succ or bb2 or bb2's succ is non NULL.  */
 235       if (EDGE_COUNT (bb1->succs) == 0
 236           || bb2 == NULL
 237           || EDGE_COUNT (bb2->succs) == 0)
 238         continue;
 239
 240       /* Find the bb which is the fall through to the other.  */
 241       if (EDGE_SUCC (bb1, 0)->dest == bb2)
 242         ;
 243       else if (EDGE_SUCC (bb2, 0)->dest == bb1)
 244         {
 245           basic_block bb_tmp = bb1;
 246           edge e_tmp = e1;
 247           bb1 = bb2;
 248           bb2 = bb_tmp;
 249           e1 = e2;
 250           e2 = e_tmp;
 251         }
 252       else
 253         continue;
 254
 255       e1 = EDGE_SUCC (bb1, 0);
 256
 257       /* Make sure that bb1 is just a fall through.  */
 258       if (!single_succ_p (bb1)
 259           || (e1->flags & EDGE_FALLTHRU) == 0)
 260         continue;
 261
 262       /* Also make sure that bb1 only have one predecessor and that it
 263          is bb.  */
 264       if (!single_pred_p (bb1)
 265           || single_pred (bb1) != bb)
 266         continue;
 267
 268       if (do_store_elim)
 269         {
 270           /* bb1 is the middle block, bb2 the join block, bb the split block,
 271              e1 the fallthrough edge from bb1 to bb2.  We can't do the
 272              optimization if the join block has more than two predecessors.  */
 273           if (EDGE_COUNT (bb2->preds) > 2)
 274             continue;
 275           if (cond_store_replacement (bb1, bb2, e1, e2, nontrap))
 276             cfgchanged = true;
 277         }
 278       else
 279         {
 280           phi = phi_nodes (bb2);
 281
 282           /* Check to make sure that there is only one PHI node.
 283              TODO: we could do it with more than one iff the other PHI nodes
 284              have the same elements for these two edges.  */
 285           if (!phi || PHI_CHAIN (phi) != NULL)
 286             continue;
 287
 288           arg0 = PHI_ARG_DEF_TREE (phi, e1->dest_idx);
 289           arg1 = PHI_ARG_DEF_TREE (phi, e2->dest_idx);
 290
 291           /* Something is wrong if we cannot find the arguments in the PHI
 292              node.  */
 293           gcc_assert (arg0 != NULL && arg1 != NULL);
 294
 295           /* Do the replacement of conditional if it can be done.  */
 296           if (conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
 297             cfgchanged = true;
 298           else if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
 299             cfgchanged = true;
 300           else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
 301             cfgchanged = true;
 302           else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
 303             cfgchanged = true;
 304         }
 305     }
 306
 307   free (bb_order);
 308
 309   if (do_store_elim)
 310     pointer_set_destroy (nontrap);
 311   /* If the CFG has changed, we should cleanup the CFG.  */
 312   if (cfgchanged && do_store_elim)
 313     {
 314       /* In cond-store replacement we have added some loads on edges
 315          and new VOPS (as we moved the store, and created a load).  */
 316       bsi_commit_edge_inserts ();
 317       return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
 318     }
 319   else if (cfgchanged)
 320     return TODO_cleanup_cfg;
 321   return 0;
 322 }
 323
 324 /* Returns the list of basic blocks in the function in an order that guarantees
 325    that if a block X has just a single predecessor Y, then Y is after X in the
 326    ordering.  */
 327
 328 basic_block *
 329 blocks_in_phiopt_order (void)
 330 {
 331   basic_block x, y;
 332   basic_block *order = XNEWVEC (basic_block, n_basic_blocks);
 333   unsigned n = n_basic_blocks - NUM_FIXED_BLOCKS;
 334   unsigned np, i;
 335   sbitmap visited = sbitmap_alloc (last_basic_block);
 336
 337 #define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
 338 #define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
 339
 340   sbitmap_zero (visited);
 341
 342   MARK_VISITED (ENTRY_BLOCK_PTR);
 343   FOR_EACH_BB (x)
 344     {
 345       if (VISITED_P (x))
 346         continue;
 347
 348       /* Walk the predecessors of x as long as they have precisely one
 349          predecessor and add them to the list, so that they get stored
 350          after x.  */
 351       for (y = x, np = 1;
 352            single_pred_p (y) && !VISITED_P (single_pred (y));
 353            y = single_pred (y))
 354         np++;
 355       for (y = x, i = n - np;
 356            single_pred_p (y) && !VISITED_P (single_pred (y));
 357            y = single_pred (y), i++)
 358         {
 359           order[i] = y;
 360           MARK_VISITED (y);
 361         }
 362       order[i] = y;
 363       MARK_VISITED (y);
 364
 365       gcc_assert (i == n - 1);
 366       n -= np;
 367     }
 368
 369   sbitmap_free (visited);
 370   gcc_assert (n == 0);
 371   return order;
 372
 373 #undef MARK_VISITED
 374 #undef VISITED_P
 375 }
 376
 377
 378 /* Return TRUE if block BB has no executable statements, otherwise return
 379    FALSE.  */
 380
 381 bool
 382 empty_block_p (basic_block bb)
 383 {
 384   block_stmt_iterator bsi;
 385
 386   /* BB must have no executable statements.  */
 387   bsi = bsi_start (bb);
 388   while (!bsi_end_p (bsi)
 389           && (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR
 390               || IS_EMPTY_STMT (bsi_stmt (bsi))))
 391     bsi_next (&bsi);
 392
 393   if (!bsi_end_p (bsi))
 394     return false;
 395
 396   return true;
 397 }
 398
 399 /* Replace PHI node element whose edge is E in block BB with variable NEW.
 400    Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
 401    is known to have two edges, one of which must reach BB).  */
 402
 403 static void
 404 replace_phi_edge_with_variable (basic_block cond_block,
 405                                 edge e, tree phi, tree new_tree)
 406 {
 407   basic_block bb = bb_for_stmt (phi);
 408   basic_block block_to_remove;
 409   block_stmt_iterator bsi;
 410
 411   /* Change the PHI argument to new.  */
 412   SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new_tree);
 413
 414   /* Remove the empty basic block.  */
 415   if (EDGE_SUCC (cond_block, 0)->dest == bb)
 416     {
 417       EDGE_SUCC (cond_block, 0)->flags |= EDGE_FALLTHRU;
 418       EDGE_SUCC (cond_block, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 419       EDGE_SUCC (cond_block, 0)->probability = REG_BR_PROB_BASE;
 420       EDGE_SUCC (cond_block, 0)->count += EDGE_SUCC (cond_block, 1)->count;
 421
 422       block_to_remove = EDGE_SUCC (cond_block, 1)->dest;
 423     }
 424   else
 425     {
 426       EDGE_SUCC (cond_block, 1)->flags |= EDGE_FALLTHRU;
 427       EDGE_SUCC (cond_block, 1)->flags
 428         &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 429       EDGE_SUCC (cond_block, 1)->probability = REG_BR_PROB_BASE;
 430       EDGE_SUCC (cond_block, 1)->count += EDGE_SUCC (cond_block, 0)->count;
 431
 432       block_to_remove = EDGE_SUCC (cond_block, 0)->dest;
 433     }
 434   delete_basic_block (block_to_remove);
 435
 436   /* Eliminate the COND_EXPR at the end of COND_BLOCK.  */
 437   bsi = bsi_last (cond_block);
 438   bsi_remove (&bsi, true);
 439
 440   if (dump_file && (dump_flags & TDF_DETAILS))
 441     fprintf (dump_file,
 442               "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
 443               cond_block->index,
 444               bb->index);
 445 }
 446
 447 /*  The function conditional_replacement does the main work of doing the
 448     conditional replacement.  Return true if the replacement is done.
 449     Otherwise return false.
 450     BB is the basic block where the replacement is going to be done on.  ARG0
 451     is argument 0 from PHI.  Likewise for ARG1.  */
 452
 453 static bool
 454 conditional_replacement (basic_block cond_bb, basic_block middle_bb,
 455                          edge e0, edge e1, tree phi,
 456                          tree arg0, tree arg1)
 457 {
 458   tree result;
 459   tree old_result = NULL;
 460   tree new_stmt, cond;
 461   block_stmt_iterator bsi;
 462   edge true_edge, false_edge;
 463   tree new_var = NULL;
 464   tree new_var1;
 465
 466   /* FIXME: Gimplification of complex type is too hard for now.  */
 467   if (TREE_CODE (TREE_TYPE (arg0)) == COMPLEX_TYPE
 468       || TREE_CODE (TREE_TYPE (arg1)) == COMPLEX_TYPE)
 469     return false;
 470
 471   /* The PHI arguments have the constants 0 and 1, then convert
 472      it to the conditional.  */
 473   if ((integer_zerop (arg0) && integer_onep (arg1))
 474       || (integer_zerop (arg1) && integer_onep (arg0)))
 475     ;
 476   else
 477     return false;
 478
 479   if (!empty_block_p (middle_bb))
 480     return false;
 481
 482   /* If the condition is not a naked SSA_NAME and its type does not
 483      match the type of the result, then we have to create a new
 484      variable to optimize this case as it would likely create
 485      non-gimple code when the condition was converted to the
 486      result's type.  */
 487   cond = COND_EXPR_COND (last_stmt (cond_bb));
 488   result = PHI_RESULT (phi);
 489   if (TREE_CODE (cond) != SSA_NAME
 490       && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (cond)))
 491     {
 492       tree tmp;
 493
 494       if (!COMPARISON_CLASS_P (cond))
 495         return false;
 496
 497       tmp = create_tmp_var (TREE_TYPE (cond), NULL);
 498       add_referenced_var (tmp);
 499       new_var = make_ssa_name (tmp, NULL);
 500       old_result = cond;
 501       cond = new_var;
 502     }
 503
 504   /* If the condition was a naked SSA_NAME and the type is not the
 505      same as the type of the result, then convert the type of the
 506      condition.  */
 507   if (!useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (cond)))
 508     cond = fold_convert (TREE_TYPE (result), cond);
 509
 510   /* We need to know which is the true edge and which is the false
 511      edge so that we know when to invert the condition below.  */
 512   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
 513
 514   /* Insert our new statement at the end of conditional block before the
 515      COND_EXPR.  */
 516   bsi = bsi_last (cond_bb);
 517   bsi_insert_before (&bsi, build_empty_stmt (), BSI_NEW_STMT);
 518
 519   if (old_result)
 520     {
 521       tree new1;
 522
 523       new1 = build2 (TREE_CODE (old_result), TREE_TYPE (old_result),
 524                      TREE_OPERAND (old_result, 0),
 525                      TREE_OPERAND (old_result, 1));
 526
 527       new1 = build_gimple_modify_stmt (new_var, new1);
 528       SSA_NAME_DEF_STMT (new_var) = new1;
 529
 530       bsi_insert_after (&bsi, new1, BSI_NEW_STMT);
 531     }
 532
 533   new_var1 = duplicate_ssa_name (PHI_RESULT (phi), NULL);
 534
 535
 536   /* At this point we know we have a COND_EXPR with two successors.
 537      One successor is BB, the other successor is an empty block which
 538      falls through into BB.
 539
 540      There is a single PHI node at the join point (BB) and its arguments
 541      are constants (0, 1).
 542
 543      So, given the condition COND, and the two PHI arguments, we can
 544      rewrite this PHI into non-branching code:
 545
 546        dest = (COND) or dest = COND'
 547
 548      We use the condition as-is if the argument associated with the
 549      true edge has the value one or the argument associated with the
 550      false edge as the value zero.  Note that those conditions are not
 551      the same since only one of the outgoing edges from the COND_EXPR
 552      will directly reach BB and thus be associated with an argument.  */
 553   if ((e0 == true_edge && integer_onep (arg0))
 554       || (e0 == false_edge && integer_zerop (arg0))
 555       || (e1 == true_edge && integer_onep (arg1))
 556       || (e1 == false_edge && integer_zerop (arg1)))
 557     {
 558       new_stmt = build_gimple_modify_stmt (new_var1, cond);
 559     }
 560   else
 561     {
 562       tree cond1 = invert_truthvalue (cond);
 563
 564       cond = cond1;
 565
 566       /* If what we get back is a conditional expression, there is no
 567           way that it can be gimple.  */
 568       if (TREE_CODE (cond) == COND_EXPR)
 569         {
 570           release_ssa_name (new_var1);
 571           return false;
 572         }
 573
 574       /* If COND is not something we can expect to be reducible to a GIMPLE
 575          condition, return early.  */
 576       if (is_gimple_cast (cond))
 577         cond1 = TREE_OPERAND (cond, 0);
 578       if (TREE_CODE (cond1) == TRUTH_NOT_EXPR
 579           && !is_gimple_val (TREE_OPERAND (cond1, 0)))
 580         {
 581           release_ssa_name (new_var1);
 582           return false;
 583         }
 584
 585       /* If what we get back is not gimple try to create it as gimple by
 586          using a temporary variable.  */
 587       if (is_gimple_cast (cond)
 588           && !is_gimple_val (TREE_OPERAND (cond, 0)))
 589         {
 590           tree op0, tmp, cond_tmp;
 591
 592           /* Only "real" casts are OK here, not everything that is
 593              acceptable to is_gimple_cast.  Make sure we don't do
 594              anything stupid here.  */
 595           gcc_assert (CONVERT_EXPR_P (cond));
 596
 597           op0 = TREE_OPERAND (cond, 0);
 598           tmp = create_tmp_var (TREE_TYPE (op0), NULL);
 599           add_referenced_var (tmp);
 600           cond_tmp = make_ssa_name (tmp, NULL);
 601           new_stmt = build_gimple_modify_stmt (cond_tmp, op0);
 602           SSA_NAME_DEF_STMT (cond_tmp) = new_stmt;
 603
 604           bsi_insert_after (&bsi, new_stmt, BSI_NEW_STMT);
 605           cond = fold_convert (TREE_TYPE (result), cond_tmp);
 606         }
 607
 608       new_stmt = build_gimple_modify_stmt (new_var1, cond);
 609     }
 610
 611   bsi_insert_after (&bsi, new_stmt, BSI_NEW_STMT);
 612
 613   SSA_NAME_DEF_STMT (new_var1) = new_stmt;
 614
 615   replace_phi_edge_with_variable (cond_bb, e1, phi, new_var1);
 616
 617   /* Note that we optimized this PHI.  */
 618   return true;
 619 }
 620
 621 /*  The function value_replacement does the main work of doing the value
 622     replacement.  Return true if the replacement is done.  Otherwise return
 623     false.
 624     BB is the basic block where the replacement is going to be done on.  ARG0
 625     is argument 0 from the PHI.  Likewise for ARG1.  */
 626
 627 static bool
 628 value_replacement (basic_block cond_bb, basic_block middle_bb,
 629                    edge e0, edge e1, tree phi,
 630                    tree arg0, tree arg1)
 631 {
 632   tree cond;
 633   edge true_edge, false_edge;
 634
 635   /* If the type says honor signed zeros we cannot do this
 636      optimization.  */
 637   if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
 638     return false;
 639
 640   if (!empty_block_p (middle_bb))
 641     return false;
 642
 643   cond = COND_EXPR_COND (last_stmt (cond_bb));
 644
 645   /* This transformation is only valid for equality comparisons.  */
 646   if (TREE_CODE (cond) != NE_EXPR && TREE_CODE (cond) != EQ_EXPR)
 647     return false;
 648
 649   /* We need to know which is the true edge and which is the false
 650       edge so that we know if have abs or negative abs.  */
 651   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
 652
 653   /* At this point we know we have a COND_EXPR with two successors.
 654      One successor is BB, the other successor is an empty block which
 655      falls through into BB.
 656
 657      The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
 658
 659      There is a single PHI node at the join point (BB) with two arguments.
 660
 661      We now need to verify that the two arguments in the PHI node match
 662      the two arguments to the equality comparison.  */
 663
 664   if ((operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 0))
 665        && operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 1)))
 666       || (operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 0))
 667           && operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 1))))
 668     {
 669       edge e;
 670       tree arg;
 671
 672       /* For NE_EXPR, we want to build an assignment result = arg where
 673          arg is the PHI argument associated with the true edge.  For
 674          EQ_EXPR we want the PHI argument associated with the false edge.  */
 675       e = (TREE_CODE (cond) == NE_EXPR ? true_edge : false_edge);
 676
 677       /* Unfortunately, E may not reach BB (it may instead have gone to
 678          OTHER_BLOCK).  If that is the case, then we want the single outgoing
 679          edge from OTHER_BLOCK which reaches BB and represents the desired
 680          path from COND_BLOCK.  */
 681       if (e->dest == middle_bb)
 682         e = single_succ_edge (e->dest);
 683
 684       /* Now we know the incoming edge to BB that has the argument for the
 685          RHS of our new assignment statement.  */
 686       if (e0 == e)
 687         arg = arg0;
 688       else
 689         arg = arg1;
 690
 691       replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
 692
 693       /* Note that we optimized this PHI.  */
 694       return true;
 695     }
 696   return false;
 697 }
 698
 699 /*  The function minmax_replacement does the main work of doing the minmax
 700     replacement.  Return true if the replacement is done.  Otherwise return
 701     false.
 702     BB is the basic block where the replacement is going to be done on.  ARG0
 703     is argument 0 from the PHI.  Likewise for ARG1.  */
 704
 705 static bool
 706 minmax_replacement (basic_block cond_bb, basic_block middle_bb,
 707                     edge e0, edge e1, tree phi,
 708                     tree arg0, tree arg1)
 709 {
 710   tree result, type;
 711   tree cond, new_stmt;
 712   edge true_edge, false_edge;
 713   enum tree_code cmp, minmax, ass_code;
 714   tree smaller, larger, arg_true, arg_false;
 715   block_stmt_iterator bsi, bsi_from;
 716
 717   type = TREE_TYPE (PHI_RESULT (phi));
 718
 719   /* The optimization may be unsafe due to NaNs.  */
 720   if (HONOR_NANS (TYPE_MODE (type)))
 721     return false;
 722
 723   cond = COND_EXPR_COND (last_stmt (cond_bb));
 724   cmp = TREE_CODE (cond);
 725   result = PHI_RESULT (phi);
 726
 727   /* This transformation is only valid for order comparisons.  Record which
 728      operand is smaller/larger if the result of the comparison is true.  */
 729   if (cmp == LT_EXPR || cmp == LE_EXPR)
 730     {
 731       smaller = TREE_OPERAND (cond, 0);
 732       larger = TREE_OPERAND (cond, 1);
 733     }
 734   else if (cmp == GT_EXPR || cmp == GE_EXPR)
 735     {
 736       smaller = TREE_OPERAND (cond, 1);
 737       larger = TREE_OPERAND (cond, 0);
 738     }
 739   else
 740     return false;
 741
 742   /* We need to know which is the true edge and which is the false
 743       edge so that we know if have abs or negative abs.  */
 744   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
 745
 746   /* Forward the edges over the middle basic block.  */
 747   if (true_edge->dest == middle_bb)
 748     true_edge = EDGE_SUCC (true_edge->dest, 0);
 749   if (false_edge->dest == middle_bb)
 750     false_edge = EDGE_SUCC (false_edge->dest, 0);
 751
 752   if (true_edge == e0)
 753     {
 754       gcc_assert (false_edge == e1);
 755       arg_true = arg0;
 756       arg_false = arg1;
 757     }
 758   else
 759     {
 760       gcc_assert (false_edge == e0);
 761       gcc_assert (true_edge == e1);
 762       arg_true = arg1;
 763       arg_false = arg0;
 764     }
 765
 766   if (empty_block_p (middle_bb))
 767     {
 768       if (operand_equal_for_phi_arg_p (arg_true, smaller)
 769           && operand_equal_for_phi_arg_p (arg_false, larger))
 770         {
 771           /* Case
 772
 773              if (smaller < larger)
 774              rslt = smaller;
 775              else
 776              rslt = larger;  */
 777           minmax = MIN_EXPR;
 778         }
 779       else if (operand_equal_for_phi_arg_p (arg_false, smaller)
 780                && operand_equal_for_phi_arg_p (arg_true, larger))
 781         minmax = MAX_EXPR;
 782       else
 783         return false;
 784     }
 785   else
 786     {
 787       /* Recognize the following case, assuming d <= u:
 788
 789          if (a <= u)
 790            b = MAX (a, d);
 791          x = PHI <b, u>
 792
 793          This is equivalent to
 794
 795          b = MAX (a, d);
 796          x = MIN (b, u);  */
 797
 798       tree assign = last_and_only_stmt (middle_bb);
 799       tree lhs, rhs, op0, op1, bound;
 800
 801       if (!assign
 802           || TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
 803         return false;
 804
 805       lhs = GIMPLE_STMT_OPERAND (assign, 0);
 806       rhs = GIMPLE_STMT_OPERAND (assign, 1);
 807       ass_code = TREE_CODE (rhs);
 808       if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
 809         return false;
 810       op0 = TREE_OPERAND (rhs, 0);
 811       op1 = TREE_OPERAND (rhs, 1);
 812
 813       if (true_edge->src == middle_bb)
 814         {
 815           /* We got here if the condition is true, i.e., SMALLER < LARGER.  */
 816           if (!operand_equal_for_phi_arg_p (lhs, arg_true))
 817             return false;
 818
 819           if (operand_equal_for_phi_arg_p (arg_false, larger))
 820             {
 821               /* Case
 822
 823                  if (smaller < larger)
 824                    {
 825                      r' = MAX_EXPR (smaller, bound)
 826                    }
 827                  r = PHI <r', larger>  --> to be turned to MIN_EXPR.  */
 828               if (ass_code != MAX_EXPR)
 829                 return false;
 830
 831               minmax = MIN_EXPR;
 832               if (operand_equal_for_phi_arg_p (op0, smaller))
 833                 bound = op1;
 834               else if (operand_equal_for_phi_arg_p (op1, smaller))
 835                 bound = op0;
 836               else
 837                 return false;
 838
 839               /* We need BOUND <= LARGER.  */
 840               if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
 841                                                   bound, larger)))
 842                 return false;
 843             }
 844           else if (operand_equal_for_phi_arg_p (arg_false, smaller))
 845             {
 846               /* Case
 847
 848                  if (smaller < larger)
 849                    {
 850                      r' = MIN_EXPR (larger, bound)
 851                    }
 852                  r = PHI <r', smaller>  --> to be turned to MAX_EXPR.  */
 853               if (ass_code != MIN_EXPR)
 854                 return false;
 855
 856               minmax = MAX_EXPR;
 857               if (operand_equal_for_phi_arg_p (op0, larger))
 858                 bound = op1;
 859               else if (operand_equal_for_phi_arg_p (op1, larger))
 860                 bound = op0;
 861               else
 862                 return false;
 863
 864               /* We need BOUND >= SMALLER.  */
 865               if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
 866                                                   bound, smaller)))
 867                 return false;
 868             }
 869           else
 870             return false;
 871         }
 872       else
 873         {
 874           /* We got here if the condition is false, i.e., SMALLER > LARGER.  */
 875           if (!operand_equal_for_phi_arg_p (lhs, arg_false))
 876             return false;
 877
 878           if (operand_equal_for_phi_arg_p (arg_true, larger))
 879             {
 880               /* Case
 881
 882                  if (smaller > larger)
 883                    {
 884                      r' = MIN_EXPR (smaller, bound)
 885                    }
 886                  r = PHI <r', larger>  --> to be turned to MAX_EXPR.  */
 887               if (ass_code != MIN_EXPR)
 888                 return false;
 889
 890               minmax = MAX_EXPR;
 891               if (operand_equal_for_phi_arg_p (op0, smaller))
 892                 bound = op1;
 893               else if (operand_equal_for_phi_arg_p (op1, smaller))
 894                 bound = op0;
 895               else
 896                 return false;
 897
 898               /* We need BOUND >= LARGER.  */
 899               if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
 900                                                   bound, larger)))
 901                 return false;
 902             }
 903           else if (operand_equal_for_phi_arg_p (arg_true, smaller))
 904             {
 905               /* Case
 906
 907                  if (smaller > larger)
 908                    {
 909                      r' = MAX_EXPR (larger, bound)
 910                    }
 911                  r = PHI <r', smaller>  --> to be turned to MIN_EXPR.  */
 912               if (ass_code != MAX_EXPR)
 913                 return false;
 914
 915               minmax = MIN_EXPR;
 916               if (operand_equal_for_phi_arg_p (op0, larger))
 917                 bound = op1;
 918               else if (operand_equal_for_phi_arg_p (op1, larger))
 919                 bound = op0;
 920               else
 921                 return false;
 922
 923               /* We need BOUND <= SMALLER.  */
 924               if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
 925                                                   bound, smaller)))
 926                 return false;
 927             }
 928           else
 929             return false;
 930         }
 931
 932       /* Move the statement from the middle block.  */
 933       bsi = bsi_last (cond_bb);
 934       bsi_from = bsi_last (middle_bb);
 935       bsi_move_before (&bsi_from, &bsi);
 936     }
 937
 938   /* Emit the statement to compute min/max.  */
 939   result = duplicate_ssa_name (PHI_RESULT (phi), NULL);
 940   new_stmt = build_gimple_modify_stmt (result, build2 (minmax, type, arg0, arg1));
 941   SSA_NAME_DEF_STMT (result) = new_stmt;
 942   bsi = bsi_last (cond_bb);
 943   bsi_insert_before (&bsi, new_stmt, BSI_NEW_STMT);
 944
 945   replace_phi_edge_with_variable (cond_bb, e1, phi, result);
 946   return true;
 947 }
 948
 949 /*  The function absolute_replacement does the main work of doing the absolute
 950     replacement.  Return true if the replacement is done.  Otherwise return
 951     false.
 952     bb is the basic block where the replacement is going to be done on.  arg0
 953     is argument 0 from the phi.  Likewise for arg1.  */
 954
 955 static bool
 956 abs_replacement (basic_block cond_bb, basic_block middle_bb,
 957                  edge e0 ATTRIBUTE_UNUSED, edge e1,
 958                  tree phi, tree arg0, tree arg1)
 959 {
 960   tree result;
 961   tree new_stmt, cond;
 962   block_stmt_iterator bsi;
 963   edge true_edge, false_edge;
 964   tree assign;
 965   edge e;
 966   tree rhs, lhs;
 967   bool negate;
 968   enum tree_code cond_code;
 969
 970   /* If the type says honor signed zeros we cannot do this
 971      optimization.  */
 972   if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
 973     return false;
 974
 975   /* OTHER_BLOCK must have only one executable statement which must have the
 976      form arg0 = -arg1 or arg1 = -arg0.  */
 977
 978   assign = last_and_only_stmt (middle_bb);
 979   /* If we did not find the proper negation assignment, then we can not
 980      optimize.  */
 981   if (assign == NULL)
 982     return false;
 983
 984   /* If we got here, then we have found the only executable statement
 985      in OTHER_BLOCK.  If it is anything other than arg = -arg1 or
 986      arg1 = -arg0, then we can not optimize.  */
 987   if (TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
 988     return false;
 989
 990   lhs = GIMPLE_STMT_OPERAND (assign, 0);
 991   rhs = GIMPLE_STMT_OPERAND (assign, 1);
 992
 993   if (TREE_CODE (rhs) != NEGATE_EXPR)
 994     return false;
 995
 996   rhs = TREE_OPERAND (rhs, 0);
 997
 998   /* The assignment has to be arg0 = -arg1 or arg1 = -arg0.  */
 999   if (!(lhs == arg0 && rhs == arg1)
1000       && !(lhs == arg1 && rhs == arg0))
1001     return false;
1002
1003   cond = COND_EXPR_COND (last_stmt (cond_bb));
1004   result = PHI_RESULT (phi);
1005
1006   /* Only relationals comparing arg[01] against zero are interesting.  */
1007   cond_code = TREE_CODE (cond);
1008   if (cond_code != GT_EXPR && cond_code != GE_EXPR
1009       && cond_code != LT_EXPR && cond_code != LE_EXPR)
1010     return false;
1011
1012   /* Make sure the conditional is arg[01] OP y.  */
1013   if (TREE_OPERAND (cond, 0) != rhs)
1014     return false;
1015
1016   if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))
1017                ? real_zerop (TREE_OPERAND (cond, 1))
1018                : integer_zerop (TREE_OPERAND (cond, 1)))
1019     ;
1020   else
1021     return false;
1022
1023   /* We need to know which is the true edge and which is the false
1024      edge so that we know if have abs or negative abs.  */
1025   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1026
1027   /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
1028      will need to negate the result.  Similarly for LT_EXPR/LE_EXPR if
1029      the false edge goes to OTHER_BLOCK.  */
1030   if (cond_code == GT_EXPR || cond_code == GE_EXPR)
1031     e = true_edge;
1032   else
1033     e = false_edge;
1034
1035   if (e->dest == middle_bb)
1036     negate = true;
1037   else
1038     negate = false;
1039
1040   result = duplicate_ssa_name (result, NULL);
1041
1042   if (negate)
1043     {
1044       tree tmp = create_tmp_var (TREE_TYPE (result), NULL);
1045       add_referenced_var (tmp);
1046       lhs = make_ssa_name (tmp, NULL);
1047     }
1048   else
1049     lhs = result;
1050
1051   /* Build the modify expression with abs expression.  */
1052   new_stmt = build_gimple_modify_stmt (lhs,
1053                                        build1 (ABS_EXPR, TREE_TYPE (lhs), rhs));
1054   SSA_NAME_DEF_STMT (lhs) = new_stmt;
1055
1056   bsi = bsi_last (cond_bb);
1057   bsi_insert_before (&bsi, new_stmt, BSI_NEW_STMT);
1058
1059   if (negate)
1060     {
1061       /* Get the right BSI.  We want to insert after the recently
1062          added ABS_EXPR statement (which we know is the first statement
1063          in the block.  */
1064       new_stmt = build_gimple_modify_stmt (result,
1065                                            build1 (NEGATE_EXPR, TREE_TYPE (lhs),
1066                                                    lhs));
1067       SSA_NAME_DEF_STMT (result) = new_stmt;
1068
1069       bsi_insert_after (&bsi, new_stmt, BSI_NEW_STMT);
1070     }
1071
1072   replace_phi_edge_with_variable (cond_bb, e1, phi, result);
1073
1074   /* Note that we optimized this PHI.  */
1075   return true;
1076 }
1077
1078 /* Auxiliary functions to determine the set of memory accesses which
1079    can't trap because they are preceded by accesses to the same memory
1080    portion.  We do that for INDIRECT_REFs, so we only need to track
1081    the SSA_NAME of the pointer indirectly referenced.  The algorithm
1082    simply is a walk over all instructions in dominator order.  When
1083    we see an INDIRECT_REF we determine if we've already seen a same
1084    ref anywhere up to the root of the dominator tree.  If we do the
1085    current access can't trap.  If we don't see any dominating access
1086    the current access might trap, but might also make later accesses
1087    non-trapping, so we remember it.  We need to be careful with loads
1088    or stores, for instance a load might not trap, while a store would,
1089    so if we see a dominating read access this doesn't mean that a later
1090    write access would not trap.  Hence we also need to differentiate the
1091    type of access(es) seen.
1092
1093    ??? We currently are very conservative and assume that a load might
1094    trap even if a store doesn't (write-only memory).  This probably is
1095    overly conservative.  */
1096
1097 /* A hash-table of SSA_NAMEs, and in which basic block an INDIRECT_REF
1098    through it was seen, which would constitute a no-trap region for
1099    same accesses.  */
1100 struct name_to_bb
1101 {
1102   tree ssa_name;
1103   basic_block bb;
1104   unsigned store : 1;
1105 };
1106
1107 /* The hash table for remembering what we've seen.  */
1108 static htab_t seen_ssa_names;
1109
1110 /* The set of INDIRECT_REFs which can't trap.  */
1111 static struct pointer_set_t *nontrap_set;
1112
1113 /* The hash function, based on the pointer to the pointer SSA_NAME.  */
1114 static hashval_t
1115 name_to_bb_hash (const void *p)
1116 {
1117   tree n = ((struct name_to_bb *)p)->ssa_name;
1118   return htab_hash_pointer (n) ^ ((struct name_to_bb *)p)->store;
1119 }
1120
1121 /* The equality function of *P1 and *P2.  SSA_NAMEs are shared, so
1122    it's enough to simply compare them for equality.  */
1123 static int
1124 name_to_bb_eq (const void *p1, const void *p2)
1125 {
1126   const struct name_to_bb *n1 = (const struct name_to_bb *)p1;
1127   const struct name_to_bb *n2 = (const struct name_to_bb *)p2;
1128
1129   return n1->ssa_name == n2->ssa_name && n1->store == n2->store;
1130 }
1131
1132 /* We see a the expression EXP in basic block BB.  If it's an interesting
1133    expression (an INDIRECT_REF through an SSA_NAME) possibly insert the
1134    expression into the set NONTRAP or the hash table of seen expressions.
1135    STORE is true if this expression is on the LHS, otherwise it's on
1136    the RHS.  */
1137 static void
1138 add_or_mark_expr (basic_block bb, tree exp,
1139                   struct pointer_set_t *nontrap, bool store)
1140 {
1141   if (INDIRECT_REF_P (exp)
1142       && TREE_CODE (TREE_OPERAND (exp, 0)) == SSA_NAME)
1143     {
1144       tree name = TREE_OPERAND (exp, 0);
1145       struct name_to_bb map;
1146       void **slot;
1147       struct name_to_bb *n2bb;
1148       basic_block found_bb = 0;
1149
1150       /* Try to find the last seen INDIRECT_REF through the same
1151          SSA_NAME, which can trap.  */
1152       map.ssa_name = name;
1153       map.bb = 0;
1154       map.store = store;
1155       slot = htab_find_slot (seen_ssa_names, &map, INSERT);
1156       n2bb = (struct name_to_bb *) *slot;
1157       if (n2bb)
1158         found_bb = n2bb->bb;
1159
1160       /* If we've found a trapping INDIRECT_REF, _and_ it dominates EXP
1161          (it's in a basic block on the path from us to the dominator root)
1162          then we can't trap.  */
1163       if (found_bb && found_bb->aux == (void *)1)
1164         {
1165           pointer_set_insert (nontrap, exp);
1166         }
1167       else
1168         {
1169           /* EXP might trap, so insert it into the hash table.  */
1170           if (n2bb)
1171             {
1172               n2bb->bb = bb;
1173             }
1174           else
1175             {
1176               n2bb = XNEW (struct name_to_bb);
1177               n2bb->ssa_name = name;
1178               n2bb->bb = bb;
1179               n2bb->store = store;
1180               *slot = n2bb;
1181             }
1182         }
1183     }
1184 }
1185
1186 /* Called by walk_dominator_tree, when entering the block BB.  */
1187 static void
1188 nt_init_block (struct dom_walk_data *data ATTRIBUTE_UNUSED, basic_block bb)
1189 {
1190   block_stmt_iterator bsi;
1191   /* Mark this BB as being on the path to dominator root.  */
1192   bb->aux = (void*)1;
1193
1194   /* And walk the statements in order.  */
1195   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1196     {
1197       tree stmt = bsi_stmt (bsi);
1198
1199       if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1200         {
1201           tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1202           tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1203           add_or_mark_expr (bb, rhs, nontrap_set, false);
1204           add_or_mark_expr (bb, lhs, nontrap_set, true);
1205         }
1206     }
1207 }
1208
1209 /* Called by walk_dominator_tree, when basic block BB is exited.  */
1210 static void
1211 nt_fini_block (struct dom_walk_data *data ATTRIBUTE_UNUSED, basic_block bb)
1212 {
1213   /* This BB isn't on the path to dominator root anymore.  */
1214   bb->aux = NULL;
1215 }
1216
1217 /* This is the entry point of gathering non trapping memory accesses.
1218    It will do a dominator walk over the whole function, and it will
1219    make use of the bb->aux pointers.  It returns a set of trees
1220    (the INDIRECT_REFs itself) which can't trap.  */
1221 static struct pointer_set_t *
1222 get_non_trapping (void)
1223 {
1224   struct pointer_set_t *nontrap;
1225   struct dom_walk_data walk_data;
1226
1227   nontrap = pointer_set_create ();
1228   seen_ssa_names = htab_create (128, name_to_bb_hash, name_to_bb_eq,
1229                                 free);
1230   /* We're going to do a dominator walk, so ensure that we have
1231      dominance information.  */
1232   calculate_dominance_info (CDI_DOMINATORS);
1233
1234   /* Setup callbacks for the generic dominator tree walker.  */
1235   nontrap_set = nontrap;
1236   walk_data.walk_stmts_backward = false;
1237   walk_data.dom_direction = CDI_DOMINATORS;
1238   walk_data.initialize_block_local_data = NULL;
1239   walk_data.before_dom_children_before_stmts = nt_init_block;
1240   walk_data.before_dom_children_walk_stmts = NULL;
1241   walk_data.before_dom_children_after_stmts = NULL;
1242   walk_data.after_dom_children_before_stmts = NULL;
1243   walk_data.after_dom_children_walk_stmts = NULL;
1244   walk_data.after_dom_children_after_stmts = nt_fini_block;
1245   walk_data.global_data = NULL;
1246   walk_data.block_local_data_size = 0;
1247   walk_data.interesting_blocks = NULL;
1248
1249   init_walk_dominator_tree (&walk_data);
1250   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1251   fini_walk_dominator_tree (&walk_data);
1252   htab_delete (seen_ssa_names);
1253
1254   return nontrap;
1255 }
1256
1257 /* Do the main work of conditional store replacement.  We already know
1258    that the recognized pattern looks like so:
1259
1260    split:
1261      if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
1262    MIDDLE_BB:
1263      something
1264      fallthrough (edge E0)
1265    JOIN_BB:
1266      some more
1267
1268    We check that MIDDLE_BB contains only one store, that that store
1269    doesn't trap (not via NOTRAP, but via checking if an access to the same
1270    memory location dominates us) and that the store has a "simple" RHS.  */
1271
1272 static bool
1273 cond_store_replacement (basic_block middle_bb, basic_block join_bb,
1274                         edge e0, edge e1, struct pointer_set_t *nontrap)
1275 {
1276   tree assign = last_and_only_stmt (middle_bb);
1277   tree lhs, rhs, newexpr, name;
1278   tree newphi;
1279   block_stmt_iterator bsi;
1280
1281   /* Check if middle_bb contains of only one store.  */
1282   if (!assign
1283       || TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
1284     return false;
1285
1286   lhs = GIMPLE_STMT_OPERAND (assign, 0);
1287   if (!INDIRECT_REF_P (lhs))
1288     return false;
1289   rhs = GIMPLE_STMT_OPERAND (assign, 1);
1290   if (TREE_CODE (rhs) != SSA_NAME && !is_gimple_min_invariant (rhs))
1291     return false;
1292   /* Prove that we can move the store down.  We could also check
1293      TREE_THIS_NOTRAP here, but in that case we also could move stores,
1294      whose value is not available readily, which we want to avoid.  */
1295   if (!pointer_set_contains (nontrap, lhs))
1296     return false;
1297
1298   /* Now we've checked the constraints, so do the transformation:
1299      1) Remove the single store.  */
1300   mark_symbols_for_renaming (assign);
1301   bsi = bsi_for_stmt (assign);
1302   bsi_remove (&bsi, true);
1303
1304   /* 2) Create a temporary where we can store the old content
1305         of the memory touched by the store, if we need to.  */
1306   if (!condstoretemp || TREE_TYPE (lhs) != TREE_TYPE (condstoretemp))
1307     {
1308       condstoretemp = create_tmp_var (TREE_TYPE (lhs), "cstore");
1309       get_var_ann (condstoretemp);
1310       if (TREE_CODE (TREE_TYPE (lhs)) == COMPLEX_TYPE
1311           || TREE_CODE (TREE_TYPE (lhs)) == VECTOR_TYPE)
1312         DECL_GIMPLE_REG_P (condstoretemp) = 1;
1313     }
1314   add_referenced_var (condstoretemp);
1315
1316   /* 3) Insert a load from the memory of the store to the temporary
1317         on the edge which did not contain the store.  */
1318   lhs = unshare_expr (lhs);
1319   newexpr = build_gimple_modify_stmt (condstoretemp, lhs);
1320   name = make_ssa_name (condstoretemp, newexpr);
1321   GIMPLE_STMT_OPERAND (newexpr, 0) = name;
1322   mark_symbols_for_renaming (newexpr);
1323   bsi_insert_on_edge (e1, newexpr);
1324
1325   /* 4) Create a PHI node at the join block, with one argument
1326         holding the old RHS, and the other holding the temporary
1327         where we stored the old memory contents.  */
1328   newphi = create_phi_node (condstoretemp, join_bb);
1329   add_phi_arg (newphi, rhs, e0);
1330   add_phi_arg (newphi, name, e1);
1331
1332   lhs = unshare_expr (lhs);
1333   newexpr = build_gimple_modify_stmt (lhs, PHI_RESULT (newphi));
1334   mark_symbols_for_renaming (newexpr);
1335
1336   /* 5) Insert that PHI node.  */
1337   bsi = bsi_start (join_bb);
1338   while (!bsi_end_p (bsi) && TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
1339     bsi_next (&bsi);
1340   if (bsi_end_p (bsi))
1341     {
1342       bsi = bsi_last (join_bb);
1343       bsi_insert_after (&bsi, newexpr, BSI_NEW_STMT);
1344     }
1345   else
1346     bsi_insert_before (&bsi, newexpr, BSI_NEW_STMT);
1347
1348   return true;
1349 }
1350
1351 /* Always do these optimizations if we have SSA
1352    trees to work on.  */
1353 static bool
1354 gate_phiopt (void)
1355 {
1356   return 1;
1357 }
1358
1359 struct gimple_opt_pass pass_phiopt =
1360 {
1361  {
1362   GIMPLE_PASS,
1363   "phiopt",                             /* name */
1364   gate_phiopt,                          /* gate */
1365   tree_ssa_phiopt,                      /* execute */
1366   NULL,                                 /* sub */
1367   NULL,                                 /* next */
1368   0,                                    /* static_pass_number */
1369   TV_TREE_PHIOPT,                       /* tv_id */
1370   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1371   0,                                    /* properties_provided */
1372   0,                                    /* properties_destroyed */
1373   0,                                    /* todo_flags_start */
1374   TODO_dump_func
1375     | TODO_ggc_collect
1376     | TODO_verify_ssa
1377     | TODO_verify_flow
1378     | TODO_verify_stmts                 /* todo_flags_finish */
1379  }
1380 };
1381
1382 static bool
1383 gate_cselim (void)
1384 {
1385   return flag_tree_cselim;
1386 }
1387
1388 struct gimple_opt_pass pass_cselim =
1389 {
1390  {
1391   GIMPLE_PASS,
1392   "cselim",                             /* name */
1393   gate_cselim,                          /* gate */
1394   tree_ssa_cs_elim,                     /* execute */
1395   NULL,                                 /* sub */
1396   NULL,                                 /* next */
1397   0,                                    /* static_pass_number */
1398   TV_TREE_PHIOPT,                       /* tv_id */
1399   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1400   0,                                    /* properties_provided */
1401   0,                                    /* properties_destroyed */
1402   0,                                    /* todo_flags_start */
1403   TODO_dump_func
1404     | TODO_ggc_collect
1405     | TODO_verify_ssa
1406     | TODO_verify_flow
1407     | TODO_verify_stmts                 /* todo_flags_finish */
1408  }
1409 };