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   /* The PHI arguments have the constants 0 and 1, then convert
 467      it to the conditional.  */
 468   if ((integer_zerop (arg0) && integer_onep (arg1))
 469       || (integer_zerop (arg1) && integer_onep (arg0)))
 470     ;
 471   else
 472     return false;
 473
 474   if (!empty_block_p (middle_bb))
 475     return false;
 476
 477   /* If the condition is not a naked SSA_NAME and its type does not
 478      match the type of the result, then we have to create a new
 479      variable to optimize this case as it would likely create
 480      non-gimple code when the condition was converted to the
 481      result's type.  */
 482   cond = COND_EXPR_COND (last_stmt (cond_bb));
 483   result = PHI_RESULT (phi);
 484   if (TREE_CODE (cond) != SSA_NAME
 485       && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (cond)))
 486     {
 487       tree tmp;
 488
 489       if (!COMPARISON_CLASS_P (cond))
 490         return false;
 491
 492       tmp = create_tmp_var (TREE_TYPE (cond), NULL);
 493       add_referenced_var (tmp);
 494       new_var = make_ssa_name (tmp, NULL);
 495       old_result = cond;
 496       cond = new_var;
 497     }
 498
 499   /* If the condition was a naked SSA_NAME and the type is not the
 500      same as the type of the result, then convert the type of the
 501      condition.  */
 502   if (!useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (cond)))
 503     cond = fold_convert (TREE_TYPE (result), cond);
 504
 505   /* We need to know which is the true edge and which is the false
 506      edge so that we know when to invert the condition below.  */
 507   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
 508
 509   /* Insert our new statement at the end of conditional block before the
 510      COND_EXPR.  */
 511   bsi = bsi_last (cond_bb);
 512   bsi_insert_before (&bsi, build_empty_stmt (), BSI_NEW_STMT);
 513
 514   if (old_result)
 515     {
 516       tree new1;
 517
 518       new1 = build2 (TREE_CODE (old_result), TREE_TYPE (old_result),
 519                      TREE_OPERAND (old_result, 0),
 520                      TREE_OPERAND (old_result, 1));
 521
 522       new1 = build_gimple_modify_stmt (new_var, new1);
 523       SSA_NAME_DEF_STMT (new_var) = new1;
 524
 525       bsi_insert_after (&bsi, new1, BSI_NEW_STMT);
 526     }
 527
 528   new_var1 = duplicate_ssa_name (PHI_RESULT (phi), NULL);
 529
 530
 531   /* At this point we know we have a COND_EXPR with two successors.
 532      One successor is BB, the other successor is an empty block which
 533      falls through into BB.
 534
 535      There is a single PHI node at the join point (BB) and its arguments
 536      are constants (0, 1).
 537
 538      So, given the condition COND, and the two PHI arguments, we can
 539      rewrite this PHI into non-branching code:
 540
 541        dest = (COND) or dest = COND'
 542
 543      We use the condition as-is if the argument associated with the
 544      true edge has the value one or the argument associated with the
 545      false edge as the value zero.  Note that those conditions are not
 546      the same since only one of the outgoing edges from the COND_EXPR
 547      will directly reach BB and thus be associated with an argument.  */
 548   if ((e0 == true_edge && integer_onep (arg0))
 549       || (e0 == false_edge && integer_zerop (arg0))
 550       || (e1 == true_edge && integer_onep (arg1))
 551       || (e1 == false_edge && integer_zerop (arg1)))
 552     {
 553       new_stmt = build_gimple_modify_stmt (new_var1, cond);
 554     }
 555   else
 556     {
 557       tree cond1 = invert_truthvalue (cond);
 558
 559       cond = cond1;
 560
 561       /* If what we get back is a conditional expression, there is no
 562           way that it can be gimple.  */
 563       if (TREE_CODE (cond) == COND_EXPR)
 564         {
 565           release_ssa_name (new_var1);
 566           return false;
 567         }
 568
 569       /* If COND is not something we can expect to be reducible to a GIMPLE
 570          condition, return early.  */
 571       if (is_gimple_cast (cond))
 572         cond1 = TREE_OPERAND (cond, 0);
 573       if (TREE_CODE (cond1) == TRUTH_NOT_EXPR
 574           && !is_gimple_val (TREE_OPERAND (cond1, 0)))
 575         {
 576           release_ssa_name (new_var1);
 577           return false;
 578         }
 579
 580       /* If what we get back is not gimple try to create it as gimple by
 581          using a temporary variable.  */
 582       if (is_gimple_cast (cond)
 583           && !is_gimple_val (TREE_OPERAND (cond, 0)))
 584         {
 585           tree op0, tmp, cond_tmp;
 586
 587           /* Only "real" casts are OK here, not everything that is
 588              acceptable to is_gimple_cast.  Make sure we don't do
 589              anything stupid here.  */
 590           gcc_assert (TREE_CODE (cond) == NOP_EXPR
 591                       || TREE_CODE (cond) == CONVERT_EXPR);
 592
 593           op0 = TREE_OPERAND (cond, 0);
 594           tmp = create_tmp_var (TREE_TYPE (op0), NULL);
 595           add_referenced_var (tmp);
 596           cond_tmp = make_ssa_name (tmp, NULL);
 597           new_stmt = build_gimple_modify_stmt (cond_tmp, op0);
 598           SSA_NAME_DEF_STMT (cond_tmp) = new_stmt;
 599
 600           bsi_insert_after (&bsi, new_stmt, BSI_NEW_STMT);
 601           cond = fold_convert (TREE_TYPE (result), cond_tmp);
 602         }
 603
 604       new_stmt = build_gimple_modify_stmt (new_var1, cond);
 605     }
 606
 607   bsi_insert_after (&bsi, new_stmt, BSI_NEW_STMT);
 608
 609   SSA_NAME_DEF_STMT (new_var1) = new_stmt;
 610
 611   replace_phi_edge_with_variable (cond_bb, e1, phi, new_var1);
 612
 613   /* Note that we optimized this PHI.  */
 614   return true;
 615 }
 616
 617 /*  The function value_replacement does the main work of doing the value
 618     replacement.  Return true if the replacement is done.  Otherwise return
 619     false.
 620     BB is the basic block where the replacement is going to be done on.  ARG0
 621     is argument 0 from the PHI.  Likewise for ARG1.  */
 622
 623 static bool
 624 value_replacement (basic_block cond_bb, basic_block middle_bb,
 625                    edge e0, edge e1, tree phi,
 626                    tree arg0, tree arg1)
 627 {
 628   tree cond;
 629   edge true_edge, false_edge;
 630
 631   /* If the type says honor signed zeros we cannot do this
 632      optimization.  */
 633   if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
 634     return false;
 635
 636   if (!empty_block_p (middle_bb))
 637     return false;
 638
 639   cond = COND_EXPR_COND (last_stmt (cond_bb));
 640
 641   /* This transformation is only valid for equality comparisons.  */
 642   if (TREE_CODE (cond) != NE_EXPR && TREE_CODE (cond) != EQ_EXPR)
 643     return false;
 644
 645   /* We need to know which is the true edge and which is the false
 646       edge so that we know if have abs or negative abs.  */
 647   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
 648
 649   /* At this point we know we have a COND_EXPR with two successors.
 650      One successor is BB, the other successor is an empty block which
 651      falls through into BB.
 652
 653      The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
 654
 655      There is a single PHI node at the join point (BB) with two arguments.
 656
 657      We now need to verify that the two arguments in the PHI node match
 658      the two arguments to the equality comparison.  */
 659
 660   if ((operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 0))
 661        && operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 1)))
 662       || (operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 0))
 663           && operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 1))))
 664     {
 665       edge e;
 666       tree arg;
 667
 668       /* For NE_EXPR, we want to build an assignment result = arg where
 669          arg is the PHI argument associated with the true edge.  For
 670          EQ_EXPR we want the PHI argument associated with the false edge.  */
 671       e = (TREE_CODE (cond) == NE_EXPR ? true_edge : false_edge);
 672
 673       /* Unfortunately, E may not reach BB (it may instead have gone to
 674          OTHER_BLOCK).  If that is the case, then we want the single outgoing
 675          edge from OTHER_BLOCK which reaches BB and represents the desired
 676          path from COND_BLOCK.  */
 677       if (e->dest == middle_bb)
 678         e = single_succ_edge (e->dest);
 679
 680       /* Now we know the incoming edge to BB that has the argument for the
 681          RHS of our new assignment statement.  */
 682       if (e0 == e)
 683         arg = arg0;
 684       else
 685         arg = arg1;
 686
 687       replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
 688
 689       /* Note that we optimized this PHI.  */
 690       return true;
 691     }
 692   return false;
 693 }
 694
 695 /*  The function minmax_replacement does the main work of doing the minmax
 696     replacement.  Return true if the replacement is done.  Otherwise return
 697     false.
 698     BB is the basic block where the replacement is going to be done on.  ARG0
 699     is argument 0 from the PHI.  Likewise for ARG1.  */
 700
 701 static bool
 702 minmax_replacement (basic_block cond_bb, basic_block middle_bb,
 703                     edge e0, edge e1, tree phi,
 704                     tree arg0, tree arg1)
 705 {
 706   tree result, type;
 707   tree cond, new_stmt;
 708   edge true_edge, false_edge;
 709   enum tree_code cmp, minmax, ass_code;
 710   tree smaller, larger, arg_true, arg_false;
 711   block_stmt_iterator bsi, bsi_from;
 712
 713   type = TREE_TYPE (PHI_RESULT (phi));
 714
 715   /* The optimization may be unsafe due to NaNs.  */
 716   if (HONOR_NANS (TYPE_MODE (type)))
 717     return false;
 718
 719   cond = COND_EXPR_COND (last_stmt (cond_bb));
 720   cmp = TREE_CODE (cond);
 721   result = PHI_RESULT (phi);
 722
 723   /* This transformation is only valid for order comparisons.  Record which
 724      operand is smaller/larger if the result of the comparison is true.  */
 725   if (cmp == LT_EXPR || cmp == LE_EXPR)
 726     {
 727       smaller = TREE_OPERAND (cond, 0);
 728       larger = TREE_OPERAND (cond, 1);
 729     }
 730   else if (cmp == GT_EXPR || cmp == GE_EXPR)
 731     {
 732       smaller = TREE_OPERAND (cond, 1);
 733       larger = TREE_OPERAND (cond, 0);
 734     }
 735   else
 736     return false;
 737
 738   /* We need to know which is the true edge and which is the false
 739       edge so that we know if have abs or negative abs.  */
 740   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
 741
 742   /* Forward the edges over the middle basic block.  */
 743   if (true_edge->dest == middle_bb)
 744     true_edge = EDGE_SUCC (true_edge->dest, 0);
 745   if (false_edge->dest == middle_bb)
 746     false_edge = EDGE_SUCC (false_edge->dest, 0);
 747
 748   if (true_edge == e0)
 749     {
 750       gcc_assert (false_edge == e1);
 751       arg_true = arg0;
 752       arg_false = arg1;
 753     }
 754   else
 755     {
 756       gcc_assert (false_edge == e0);
 757       gcc_assert (true_edge == e1);
 758       arg_true = arg1;
 759       arg_false = arg0;
 760     }
 761
 762   if (empty_block_p (middle_bb))
 763     {
 764       if (operand_equal_for_phi_arg_p (arg_true, smaller)
 765           && operand_equal_for_phi_arg_p (arg_false, larger))
 766         {
 767           /* Case
 768
 769              if (smaller < larger)
 770              rslt = smaller;
 771              else
 772              rslt = larger;  */
 773           minmax = MIN_EXPR;
 774         }
 775       else if (operand_equal_for_phi_arg_p (arg_false, smaller)
 776                && operand_equal_for_phi_arg_p (arg_true, larger))
 777         minmax = MAX_EXPR;
 778       else
 779         return false;
 780     }
 781   else
 782     {
 783       /* Recognize the following case, assuming d <= u:
 784
 785          if (a <= u)
 786            b = MAX (a, d);
 787          x = PHI <b, u>
 788
 789          This is equivalent to
 790
 791          b = MAX (a, d);
 792          x = MIN (b, u);  */
 793
 794       tree assign = last_and_only_stmt (middle_bb);
 795       tree lhs, rhs, op0, op1, bound;
 796
 797       if (!assign
 798           || TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
 799         return false;
 800
 801       lhs = GIMPLE_STMT_OPERAND (assign, 0);
 802       rhs = GIMPLE_STMT_OPERAND (assign, 1);
 803       ass_code = TREE_CODE (rhs);
 804       if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
 805         return false;
 806       op0 = TREE_OPERAND (rhs, 0);
 807       op1 = TREE_OPERAND (rhs, 1);
 808
 809       if (true_edge->src == middle_bb)
 810         {
 811           /* We got here if the condition is true, i.e., SMALLER < LARGER.  */
 812           if (!operand_equal_for_phi_arg_p (lhs, arg_true))
 813             return false;
 814
 815           if (operand_equal_for_phi_arg_p (arg_false, larger))
 816             {
 817               /* Case
 818
 819                  if (smaller < larger)
 820                    {
 821                      r' = MAX_EXPR (smaller, bound)
 822                    }
 823                  r = PHI <r', larger>  --> to be turned to MIN_EXPR.  */
 824               if (ass_code != MAX_EXPR)
 825                 return false;
 826
 827               minmax = MIN_EXPR;
 828               if (operand_equal_for_phi_arg_p (op0, smaller))
 829                 bound = op1;
 830               else if (operand_equal_for_phi_arg_p (op1, smaller))
 831                 bound = op0;
 832               else
 833                 return false;
 834
 835               /* We need BOUND <= LARGER.  */
 836               if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
 837                                                   bound, larger)))
 838                 return false;
 839             }
 840           else if (operand_equal_for_phi_arg_p (arg_false, smaller))
 841             {
 842               /* Case
 843
 844                  if (smaller < larger)
 845                    {
 846                      r' = MIN_EXPR (larger, bound)
 847                    }
 848                  r = PHI <r', smaller>  --> to be turned to MAX_EXPR.  */
 849               if (ass_code != MIN_EXPR)
 850                 return false;
 851
 852               minmax = MAX_EXPR;
 853               if (operand_equal_for_phi_arg_p (op0, larger))
 854                 bound = op1;
 855               else if (operand_equal_for_phi_arg_p (op1, larger))
 856                 bound = op0;
 857               else
 858                 return false;
 859
 860               /* We need BOUND >= SMALLER.  */
 861               if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
 862                                                   bound, smaller)))
 863                 return false;
 864             }
 865           else
 866             return false;
 867         }
 868       else
 869         {
 870           /* We got here if the condition is false, i.e., SMALLER > LARGER.  */
 871           if (!operand_equal_for_phi_arg_p (lhs, arg_false))
 872             return false;
 873
 874           if (operand_equal_for_phi_arg_p (arg_true, larger))
 875             {
 876               /* Case
 877
 878                  if (smaller > larger)
 879                    {
 880                      r' = MIN_EXPR (smaller, bound)
 881                    }
 882                  r = PHI <r', larger>  --> to be turned to MAX_EXPR.  */
 883               if (ass_code != MIN_EXPR)
 884                 return false;
 885
 886               minmax = MAX_EXPR;
 887               if (operand_equal_for_phi_arg_p (op0, smaller))
 888                 bound = op1;
 889               else if (operand_equal_for_phi_arg_p (op1, smaller))
 890                 bound = op0;
 891               else
 892                 return false;
 893
 894               /* We need BOUND >= LARGER.  */
 895               if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
 896                                                   bound, larger)))
 897                 return false;
 898             }
 899           else if (operand_equal_for_phi_arg_p (arg_true, smaller))
 900             {
 901               /* Case
 902
 903                  if (smaller > larger)
 904                    {
 905                      r' = MAX_EXPR (larger, bound)
 906                    }
 907                  r = PHI <r', smaller>  --> to be turned to MIN_EXPR.  */
 908               if (ass_code != MAX_EXPR)
 909                 return false;
 910
 911               minmax = MIN_EXPR;
 912               if (operand_equal_for_phi_arg_p (op0, larger))
 913                 bound = op1;
 914               else if (operand_equal_for_phi_arg_p (op1, larger))
 915                 bound = op0;
 916               else
 917                 return false;
 918
 919               /* We need BOUND <= SMALLER.  */
 920               if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
 921                                                   bound, smaller)))
 922                 return false;
 923             }
 924           else
 925             return false;
 926         }
 927
 928       /* Move the statement from the middle block.  */
 929       bsi = bsi_last (cond_bb);
 930       bsi_from = bsi_last (middle_bb);
 931       bsi_move_before (&bsi_from, &bsi);
 932     }
 933
 934   /* Emit the statement to compute min/max.  */
 935   result = duplicate_ssa_name (PHI_RESULT (phi), NULL);
 936   new_stmt = build_gimple_modify_stmt (result, build2 (minmax, type, arg0, arg1));
 937   SSA_NAME_DEF_STMT (result) = new_stmt;
 938   bsi = bsi_last (cond_bb);
 939   bsi_insert_before (&bsi, new_stmt, BSI_NEW_STMT);
 940
 941   replace_phi_edge_with_variable (cond_bb, e1, phi, result);
 942   return true;
 943 }
 944
 945 /*  The function absolute_replacement does the main work of doing the absolute
 946     replacement.  Return true if the replacement is done.  Otherwise return
 947     false.
 948     bb is the basic block where the replacement is going to be done on.  arg0
 949     is argument 0 from the phi.  Likewise for arg1.  */
 950
 951 static bool
 952 abs_replacement (basic_block cond_bb, basic_block middle_bb,
 953                  edge e0 ATTRIBUTE_UNUSED, edge e1,
 954                  tree phi, tree arg0, tree arg1)
 955 {
 956   tree result;
 957   tree new_stmt, cond;
 958   block_stmt_iterator bsi;
 959   edge true_edge, false_edge;
 960   tree assign;
 961   edge e;
 962   tree rhs, lhs;
 963   bool negate;
 964   enum tree_code cond_code;
 965
 966   /* If the type says honor signed zeros we cannot do this
 967      optimization.  */
 968   if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
 969     return false;
 970
 971   /* OTHER_BLOCK must have only one executable statement which must have the
 972      form arg0 = -arg1 or arg1 = -arg0.  */
 973
 974   assign = last_and_only_stmt (middle_bb);
 975   /* If we did not find the proper negation assignment, then we can not
 976      optimize.  */
 977   if (assign == NULL)
 978     return false;
 979
 980   /* If we got here, then we have found the only executable statement
 981      in OTHER_BLOCK.  If it is anything other than arg = -arg1 or
 982      arg1 = -arg0, then we can not optimize.  */
 983   if (TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
 984     return false;
 985
 986   lhs = GIMPLE_STMT_OPERAND (assign, 0);
 987   rhs = GIMPLE_STMT_OPERAND (assign, 1);
 988
 989   if (TREE_CODE (rhs) != NEGATE_EXPR)
 990     return false;
 991
 992   rhs = TREE_OPERAND (rhs, 0);
 993
 994   /* The assignment has to be arg0 = -arg1 or arg1 = -arg0.  */
 995   if (!(lhs == arg0 && rhs == arg1)
 996       && !(lhs == arg1 && rhs == arg0))
 997     return false;
 998
 999   cond = COND_EXPR_COND (last_stmt (cond_bb));
1000   result = PHI_RESULT (phi);
1001
1002   /* Only relationals comparing arg[01] against zero are interesting.  */
1003   cond_code = TREE_CODE (cond);
1004   if (cond_code != GT_EXPR && cond_code != GE_EXPR
1005       && cond_code != LT_EXPR && cond_code != LE_EXPR)
1006     return false;
1007
1008   /* Make sure the conditional is arg[01] OP y.  */
1009   if (TREE_OPERAND (cond, 0) != rhs)
1010     return false;
1011
1012   if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))
1013                ? real_zerop (TREE_OPERAND (cond, 1))
1014                : integer_zerop (TREE_OPERAND (cond, 1)))
1015     ;
1016   else
1017     return false;
1018
1019   /* We need to know which is the true edge and which is the false
1020      edge so that we know if have abs or negative abs.  */
1021   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1022
1023   /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
1024      will need to negate the result.  Similarly for LT_EXPR/LE_EXPR if
1025      the false edge goes to OTHER_BLOCK.  */
1026   if (cond_code == GT_EXPR || cond_code == GE_EXPR)
1027     e = true_edge;
1028   else
1029     e = false_edge;
1030
1031   if (e->dest == middle_bb)
1032     negate = true;
1033   else
1034     negate = false;
1035
1036   result = duplicate_ssa_name (result, NULL);
1037
1038   if (negate)
1039     {
1040       tree tmp = create_tmp_var (TREE_TYPE (result), NULL);
1041       add_referenced_var (tmp);
1042       lhs = make_ssa_name (tmp, NULL);
1043     }
1044   else
1045     lhs = result;
1046
1047   /* Build the modify expression with abs expression.  */
1048   new_stmt = build_gimple_modify_stmt (lhs,
1049                                        build1 (ABS_EXPR, TREE_TYPE (lhs), rhs));
1050   SSA_NAME_DEF_STMT (lhs) = new_stmt;
1051
1052   bsi = bsi_last (cond_bb);
1053   bsi_insert_before (&bsi, new_stmt, BSI_NEW_STMT);
1054
1055   if (negate)
1056     {
1057       /* Get the right BSI.  We want to insert after the recently
1058          added ABS_EXPR statement (which we know is the first statement
1059          in the block.  */
1060       new_stmt = build_gimple_modify_stmt (result,
1061                                            build1 (NEGATE_EXPR, TREE_TYPE (lhs),
1062                                                    lhs));
1063       SSA_NAME_DEF_STMT (result) = new_stmt;
1064
1065       bsi_insert_after (&bsi, new_stmt, BSI_NEW_STMT);
1066     }
1067
1068   replace_phi_edge_with_variable (cond_bb, e1, phi, result);
1069
1070   /* Note that we optimized this PHI.  */
1071   return true;
1072 }
1073
1074 /* Auxiliary functions to determine the set of memory accesses which
1075    can't trap because they are preceded by accesses to the same memory
1076    portion.  We do that for INDIRECT_REFs, so we only need to track
1077    the SSA_NAME of the pointer indirectly referenced.  The algorithm
1078    simply is a walk over all instructions in dominator order.  When
1079    we see an INDIRECT_REF we determine if we've already seen a same
1080    ref anywhere up to the root of the dominator tree.  If we do the
1081    current access can't trap.  If we don't see any dominating access
1082    the current access might trap, but might also make later accesses
1083    non-trapping, so we remember it.  We need to be careful with loads
1084    or stores, for instance a load might not trap, while a store would,
1085    so if we see a dominating read access this doesn't mean that a later
1086    write access would not trap.  Hence we also need to differentiate the
1087    type of access(es) seen.
1088
1089    ??? We currently are very conservative and assume that a load might
1090    trap even if a store doesn't (write-only memory).  This probably is
1091    overly conservative.  */
1092
1093 /* A hash-table of SSA_NAMEs, and in which basic block an INDIRECT_REF
1094    through it was seen, which would constitute a no-trap region for
1095    same accesses.  */
1096 struct name_to_bb
1097 {
1098   tree ssa_name;
1099   basic_block bb;
1100   unsigned store : 1;
1101 };
1102
1103 /* The hash table for remembering what we've seen.  */
1104 static htab_t seen_ssa_names;
1105
1106 /* The set of INDIRECT_REFs which can't trap.  */
1107 static struct pointer_set_t *nontrap_set;
1108
1109 /* The hash function, based on the pointer to the pointer SSA_NAME.  */
1110 static hashval_t
1111 name_to_bb_hash (const void *p)
1112 {
1113   tree n = ((struct name_to_bb *)p)->ssa_name;
1114   return htab_hash_pointer (n) ^ ((struct name_to_bb *)p)->store;
1115 }
1116
1117 /* The equality function of *P1 and *P2.  SSA_NAMEs are shared, so
1118    it's enough to simply compare them for equality.  */
1119 static int
1120 name_to_bb_eq (const void *p1, const void *p2)
1121 {
1122   const struct name_to_bb *n1 = (const struct name_to_bb *)p1;
1123   const struct name_to_bb *n2 = (const struct name_to_bb *)p2;
1124
1125   return n1->ssa_name == n2->ssa_name && n1->store == n2->store;
1126 }
1127
1128 /* We see a the expression EXP in basic block BB.  If it's an interesting
1129    expression (an INDIRECT_REF through an SSA_NAME) possibly insert the
1130    expression into the set NONTRAP or the hash table of seen expressions.
1131    STORE is true if this expression is on the LHS, otherwise it's on
1132    the RHS.  */
1133 static void
1134 add_or_mark_expr (basic_block bb, tree exp,
1135                   struct pointer_set_t *nontrap, bool store)
1136 {
1137   if (INDIRECT_REF_P (exp)
1138       && TREE_CODE (TREE_OPERAND (exp, 0)) == SSA_NAME)
1139     {
1140       tree name = TREE_OPERAND (exp, 0);
1141       struct name_to_bb map;
1142       void **slot;
1143       struct name_to_bb *n2bb;
1144       basic_block found_bb = 0;
1145
1146       /* Try to find the last seen INDIRECT_REF through the same
1147          SSA_NAME, which can trap.  */
1148       map.ssa_name = name;
1149       map.bb = 0;
1150       map.store = store;
1151       slot = htab_find_slot (seen_ssa_names, &map, INSERT);
1152       n2bb = (struct name_to_bb *) *slot;
1153       if (n2bb)
1154         found_bb = n2bb->bb;
1155
1156       /* If we've found a trapping INDIRECT_REF, _and_ it dominates EXP
1157          (it's in a basic block on the path from us to the dominator root)
1158          then we can't trap.  */
1159       if (found_bb && found_bb->aux == (void *)1)
1160         {
1161           pointer_set_insert (nontrap, exp);
1162         }
1163       else
1164         {
1165           /* EXP might trap, so insert it into the hash table.  */
1166           if (n2bb)
1167             {
1168               n2bb->bb = bb;
1169             }
1170           else
1171             {
1172               n2bb = XNEW (struct name_to_bb);
1173               n2bb->ssa_name = name;
1174               n2bb->bb = bb;
1175               n2bb->store = store;
1176               *slot = n2bb;
1177             }
1178         }
1179     }
1180 }
1181
1182 /* Called by walk_dominator_tree, when entering the block BB.  */
1183 static void
1184 nt_init_block (struct dom_walk_data *data ATTRIBUTE_UNUSED, basic_block bb)
1185 {
1186   block_stmt_iterator bsi;
1187   /* Mark this BB as being on the path to dominator root.  */
1188   bb->aux = (void*)1;
1189
1190   /* And walk the statements in order.  */
1191   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1192     {
1193       tree stmt = bsi_stmt (bsi);
1194
1195       if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1196         {
1197           tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1198           tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1199           add_or_mark_expr (bb, rhs, nontrap_set, false);
1200           add_or_mark_expr (bb, lhs, nontrap_set, true);
1201         }
1202     }
1203 }
1204
1205 /* Called by walk_dominator_tree, when basic block BB is exited.  */
1206 static void
1207 nt_fini_block (struct dom_walk_data *data ATTRIBUTE_UNUSED, basic_block bb)
1208 {
1209   /* This BB isn't on the path to dominator root anymore.  */
1210   bb->aux = NULL;
1211 }
1212
1213 /* This is the entry point of gathering non trapping memory accesses.
1214    It will do a dominator walk over the whole function, and it will
1215    make use of the bb->aux pointers.  It returns a set of trees
1216    (the INDIRECT_REFs itself) which can't trap.  */
1217 static struct pointer_set_t *
1218 get_non_trapping (void)
1219 {
1220   struct pointer_set_t *nontrap;
1221   struct dom_walk_data walk_data;
1222
1223   nontrap = pointer_set_create ();
1224   seen_ssa_names = htab_create (128, name_to_bb_hash, name_to_bb_eq,
1225                                 free);
1226   /* We're going to do a dominator walk, so ensure that we have
1227      dominance information.  */
1228   calculate_dominance_info (CDI_DOMINATORS);
1229
1230   /* Setup callbacks for the generic dominator tree walker.  */
1231   nontrap_set = nontrap;
1232   walk_data.walk_stmts_backward = false;
1233   walk_data.dom_direction = CDI_DOMINATORS;
1234   walk_data.initialize_block_local_data = NULL;
1235   walk_data.before_dom_children_before_stmts = nt_init_block;
1236   walk_data.before_dom_children_walk_stmts = NULL;
1237   walk_data.before_dom_children_after_stmts = NULL;
1238   walk_data.after_dom_children_before_stmts = NULL;
1239   walk_data.after_dom_children_walk_stmts = NULL;
1240   walk_data.after_dom_children_after_stmts = nt_fini_block;
1241   walk_data.global_data = NULL;
1242   walk_data.block_local_data_size = 0;
1243   walk_data.interesting_blocks = NULL;
1244
1245   init_walk_dominator_tree (&walk_data);
1246   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1247   fini_walk_dominator_tree (&walk_data);
1248   htab_delete (seen_ssa_names);
1249
1250   return nontrap;
1251 }
1252
1253 /* Do the main work of conditional store replacement.  We already know
1254    that the recognized pattern looks like so:
1255
1256    split:
1257      if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
1258    MIDDLE_BB:
1259      something
1260      fallthrough (edge E0)
1261    JOIN_BB:
1262      some more
1263
1264    We check that MIDDLE_BB contains only one store, that that store
1265    doesn't trap (not via NOTRAP, but via checking if an access to the same
1266    memory location dominates us) and that the store has a "simple" RHS.  */
1267
1268 static bool
1269 cond_store_replacement (basic_block middle_bb, basic_block join_bb,
1270                         edge e0, edge e1, struct pointer_set_t *nontrap)
1271 {
1272   tree assign = last_and_only_stmt (middle_bb);
1273   tree lhs, rhs, newexpr, name;
1274   tree newphi;
1275   block_stmt_iterator bsi;
1276
1277   /* Check if middle_bb contains of only one store.  */
1278   if (!assign
1279       || TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
1280     return false;
1281
1282   lhs = GIMPLE_STMT_OPERAND (assign, 0);
1283   if (!INDIRECT_REF_P (lhs))
1284     return false;
1285   rhs = GIMPLE_STMT_OPERAND (assign, 1);
1286   if (TREE_CODE (rhs) != SSA_NAME && !is_gimple_min_invariant (rhs))
1287     return false;
1288   /* Prove that we can move the store down.  We could also check
1289      TREE_THIS_NOTRAP here, but in that case we also could move stores,
1290      whose value is not available readily, which we want to avoid.  */
1291   if (!pointer_set_contains (nontrap, lhs))
1292     return false;
1293
1294   /* Now we've checked the constraints, so do the transformation:
1295      1) Remove the single store.  */
1296   mark_symbols_for_renaming (assign);
1297   bsi = bsi_for_stmt (assign);
1298   bsi_remove (&bsi, true);
1299
1300   /* 2) Create a temporary where we can store the old content
1301         of the memory touched by the store, if we need to.  */
1302   if (!condstoretemp || TREE_TYPE (lhs) != TREE_TYPE (condstoretemp))
1303     {
1304       condstoretemp = create_tmp_var (TREE_TYPE (lhs), "cstore");
1305       get_var_ann (condstoretemp);
1306       if (TREE_CODE (TREE_TYPE (lhs)) == COMPLEX_TYPE
1307           || TREE_CODE (TREE_TYPE (lhs)) == VECTOR_TYPE)
1308         DECL_GIMPLE_REG_P (condstoretemp) = 1;
1309     }
1310   add_referenced_var (condstoretemp);
1311
1312   /* 3) Insert a load from the memory of the store to the temporary
1313         on the edge which did not contain the store.  */
1314   lhs = unshare_expr (lhs);
1315   newexpr = build_gimple_modify_stmt (condstoretemp, lhs);
1316   name = make_ssa_name (condstoretemp, newexpr);
1317   GIMPLE_STMT_OPERAND (newexpr, 0) = name;
1318   mark_symbols_for_renaming (newexpr);
1319   bsi_insert_on_edge (e1, newexpr);
1320
1321   /* 4) Create a PHI node at the join block, with one argument
1322         holding the old RHS, and the other holding the temporary
1323         where we stored the old memory contents.  */
1324   newphi = create_phi_node (condstoretemp, join_bb);
1325   add_phi_arg (newphi, rhs, e0);
1326   add_phi_arg (newphi, name, e1);
1327
1328   lhs = unshare_expr (lhs);
1329   newexpr = build_gimple_modify_stmt (lhs, PHI_RESULT (newphi));
1330   mark_symbols_for_renaming (newexpr);
1331
1332   /* 5) Insert that PHI node.  */
1333   bsi = bsi_start (join_bb);
1334   while (!bsi_end_p (bsi) && TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
1335     bsi_next (&bsi);
1336   if (bsi_end_p (bsi))
1337     {
1338       bsi = bsi_last (join_bb);
1339       bsi_insert_after (&bsi, newexpr, BSI_NEW_STMT);
1340     }
1341   else
1342     bsi_insert_before (&bsi, newexpr, BSI_NEW_STMT);
1343
1344   return true;
1345 }
1346
1347 /* Always do these optimizations if we have SSA
1348    trees to work on.  */
1349 static bool
1350 gate_phiopt (void)
1351 {
1352   return 1;
1353 }
1354
1355 struct gimple_opt_pass pass_phiopt =
1356 {
1357  {
1358   GIMPLE_PASS,
1359   "phiopt",                             /* name */
1360   gate_phiopt,                          /* gate */
1361   tree_ssa_phiopt,                      /* execute */
1362   NULL,                                 /* sub */
1363   NULL,                                 /* next */
1364   0,                                    /* static_pass_number */
1365   TV_TREE_PHIOPT,                       /* tv_id */
1366   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1367   0,                                    /* properties_provided */
1368   0,                                    /* properties_destroyed */
1369   0,                                    /* todo_flags_start */
1370   TODO_dump_func
1371     | TODO_ggc_collect
1372     | TODO_verify_ssa
1373     | TODO_verify_flow
1374     | TODO_verify_stmts                 /* todo_flags_finish */
1375  }
1376 };
1377
1378 static bool
1379 gate_cselim (void)
1380 {
1381   return flag_tree_cselim;
1382 }
1383
1384 struct gimple_opt_pass pass_cselim =
1385 {
1386  {
1387   GIMPLE_PASS,
1388   "cselim",                             /* name */
1389   gate_cselim,                          /* gate */
1390   tree_ssa_cs_elim,                     /* execute */
1391   NULL,                                 /* sub */
1392   NULL,                                 /* next */
1393   0,                                    /* static_pass_number */
1394   TV_TREE_PHIOPT,                       /* tv_id */
1395   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1396   0,                                    /* properties_provided */
1397   0,                                    /* properties_destroyed */
1398   0,                                    /* todo_flags_start */
1399   TODO_dump_func
1400     | TODO_ggc_collect
1401     | TODO_verify_ssa
1402     | TODO_verify_flow
1403     | TODO_verify_stmts                 /* todo_flags_finish */
1404  }
1405 };