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 dominator access
1082    the current access might trap, but might also make later accesses
1083    non-trapping, so we remember it.  */
1084
1085 /* A hash-table of SSA_NAMEs, and in which basic block an INDIRECT_REF
1086    through it was seen, which would constitute a no-trap region for
1087    same accesses.  */
1088 struct name_to_bb
1089 {
1090   tree ssa_name;
1091   basic_block bb;
1092 };
1093
1094 /* The hash table for remembering what we've seen.  */
1095 static htab_t seen_ssa_names;
1096
1097 /* The set of INDIRECT_REFs which can't trap.  */
1098 static struct pointer_set_t *nontrap_set;
1099
1100 /* The hash function, based on the pointer to the pointer SSA_NAME.  */
1101 static hashval_t
1102 name_to_bb_hash (const void *p)
1103 {
1104   tree n = ((struct name_to_bb *)p)->ssa_name;
1105   return htab_hash_pointer (n);
1106 }
1107
1108 /* The equality function of *P1 and *P2.  SSA_NAMEs are shared, so
1109    it's enough to simply compare them for equality.  */
1110 static int
1111 name_to_bb_eq (const void *p1, const void *p2)
1112 {
1113   tree n1 = ((struct name_to_bb *)p1)->ssa_name;
1114   tree n2 = ((struct name_to_bb *)p2)->ssa_name;
1115
1116   return n1 == n2;
1117 }
1118
1119 /* We see a the expression EXP in basic block BB.  If it's an interesting
1120    expression (an INDIRECT_REF through an SSA_NAME) possibly insert the
1121    expression into the set NONTRAP or the hash table of seen expressions.  */
1122 static void
1123 add_or_mark_expr (basic_block bb, tree exp, struct pointer_set_t *nontrap)
1124 {
1125   if (INDIRECT_REF_P (exp)
1126       && TREE_CODE (TREE_OPERAND (exp, 0)) == SSA_NAME)
1127     {
1128       tree name = TREE_OPERAND (exp, 0);
1129       struct name_to_bb map;
1130       void **slot;
1131       basic_block found_bb = 0;
1132
1133       /* Try to find the last seen INDIRECT_REF through the same
1134          SSA_NAME, which can trap.  */
1135       map.ssa_name = name;
1136       map.bb = 0;
1137       slot = htab_find_slot (seen_ssa_names, &map, INSERT);
1138       if (*slot)
1139         found_bb = ((struct name_to_bb *)*slot)->bb;
1140
1141       /* If we've found a trapping INDIRECT_REF, _and_ it dominates EXP
1142          (it's in a basic block on the path from us to the dominator root)
1143          then we can't trap.  */
1144       if (found_bb && found_bb->aux == (void *)1)
1145         {
1146           pointer_set_insert (nontrap, exp);
1147         }
1148       else
1149         {
1150           /* EXP might trap, so insert it into the hash table.  */
1151           if (*slot)
1152             {
1153               ((struct name_to_bb *)*slot)->bb = bb;
1154             }
1155           else
1156             {
1157               struct name_to_bb *nmap = XNEW (struct name_to_bb);
1158               nmap->ssa_name = name;
1159               nmap->bb = bb;
1160               *slot = nmap;
1161             }
1162         }
1163     }
1164 }
1165
1166 /* Called by walk_dominator_tree, when entering the block BB.  */
1167 static void
1168 nt_init_block (struct dom_walk_data *data ATTRIBUTE_UNUSED, basic_block bb)
1169 {
1170   block_stmt_iterator bsi;
1171   /* Mark this BB as being on the path to dominator root.  */
1172   bb->aux = (void*)1;
1173
1174   /* And walk the statements in order.  */
1175   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1176     {
1177       tree stmt = bsi_stmt (bsi);
1178
1179       if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1180         {
1181           tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1182           tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1183           add_or_mark_expr (bb, rhs, nontrap_set);
1184           add_or_mark_expr (bb, lhs, nontrap_set);
1185         }
1186     }
1187 }
1188
1189 /* Called by walk_dominator_tree, when basic block BB is exited.  */
1190 static void
1191 nt_fini_block (struct dom_walk_data *data ATTRIBUTE_UNUSED, basic_block bb)
1192 {
1193   /* This BB isn't on the path to dominator root anymore.  */
1194   bb->aux = NULL;
1195 }
1196
1197 /* This is the entry point of gathering non trapping memory accesses.
1198    It will do a dominator walk over the whole function, and it will
1199    make use of the bb->aux pointers.  It returns a set of trees
1200    (the INDIRECT_REFs itself) which can't trap.  */
1201 static struct pointer_set_t *
1202 get_non_trapping (void)
1203 {
1204   struct pointer_set_t *nontrap;
1205   struct dom_walk_data walk_data;
1206
1207   nontrap = pointer_set_create ();
1208   seen_ssa_names = htab_create (128, name_to_bb_hash, name_to_bb_eq,
1209                                 free);
1210   /* We're going to do a dominator walk, so ensure that we have
1211      dominance information.  */
1212   calculate_dominance_info (CDI_DOMINATORS);
1213
1214   /* Setup callbacks for the generic dominator tree walker.  */
1215   nontrap_set = nontrap;
1216   walk_data.walk_stmts_backward = false;
1217   walk_data.dom_direction = CDI_DOMINATORS;
1218   walk_data.initialize_block_local_data = NULL;
1219   walk_data.before_dom_children_before_stmts = nt_init_block;
1220   walk_data.before_dom_children_walk_stmts = NULL;
1221   walk_data.before_dom_children_after_stmts = NULL;
1222   walk_data.after_dom_children_before_stmts = NULL;
1223   walk_data.after_dom_children_walk_stmts = NULL;
1224   walk_data.after_dom_children_after_stmts = nt_fini_block;
1225   walk_data.global_data = NULL;
1226   walk_data.block_local_data_size = 0;
1227   walk_data.interesting_blocks = NULL;
1228
1229   init_walk_dominator_tree (&walk_data);
1230   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1231   fini_walk_dominator_tree (&walk_data);
1232   htab_delete (seen_ssa_names);
1233
1234   return nontrap;
1235 }
1236
1237 /* Do the main work of conditional store replacement.  We already know
1238    that the recognized pattern looks like so:
1239
1240    split:
1241      if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
1242    MIDDLE_BB:
1243      something
1244      fallthrough (edge E0)
1245    JOIN_BB:
1246      some more
1247
1248    We check that MIDDLE_BB contains only one store, that that store
1249    doesn't trap (not via NOTRAP, but via checking if an access to the same
1250    memory location dominates us) and that the store has a "simple" RHS.  */
1251
1252 static bool
1253 cond_store_replacement (basic_block middle_bb, basic_block join_bb,
1254                         edge e0, edge e1, struct pointer_set_t *nontrap)
1255 {
1256   tree assign = last_and_only_stmt (middle_bb);
1257   tree lhs, rhs, newexpr, name;
1258   tree newphi;
1259   block_stmt_iterator bsi;
1260
1261   /* Check if middle_bb contains of only one store.  */
1262   if (!assign
1263       || TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
1264     return false;
1265
1266   lhs = GIMPLE_STMT_OPERAND (assign, 0);
1267   if (!INDIRECT_REF_P (lhs))
1268     return false;
1269   rhs = GIMPLE_STMT_OPERAND (assign, 1);
1270   if (TREE_CODE (rhs) != SSA_NAME && !is_gimple_min_invariant (rhs))
1271     return false;
1272   /* Prove that we can move the store down.  We could also check
1273      TREE_THIS_NOTRAP here, but in that case we also could move stores,
1274      whose value is not available readily, which we want to avoid.  */
1275   if (!pointer_set_contains (nontrap, lhs))
1276     return false;
1277
1278   /* Now we've checked the constraints, so do the transformation:
1279      1) Remove the single store.  */
1280   mark_symbols_for_renaming (assign);
1281   bsi = bsi_for_stmt (assign);
1282   bsi_remove (&bsi, true);
1283
1284   /* 2) Create a temporary where we can store the old content
1285         of the memory touched by the store, if we need to.  */
1286   if (!condstoretemp || TREE_TYPE (lhs) != TREE_TYPE (condstoretemp))
1287     {
1288       condstoretemp = create_tmp_var (TREE_TYPE (lhs), "cstore");
1289       get_var_ann (condstoretemp);
1290     }
1291   add_referenced_var (condstoretemp);
1292
1293   /* 3) Insert a load from the memory of the store to the temporary
1294         on the edge which did not contain the store.  */
1295   lhs = unshare_expr (lhs);
1296   newexpr = build_gimple_modify_stmt (condstoretemp, lhs);
1297   name = make_ssa_name (condstoretemp, newexpr);
1298   GIMPLE_STMT_OPERAND (newexpr, 0) = name;
1299   mark_symbols_for_renaming (newexpr);
1300   bsi_insert_on_edge (e1, newexpr);
1301
1302   /* 4) Create a PHI node at the join block, with one argument
1303         holding the old RHS, and the other holding the temporary
1304         where we stored the old memory contents.  */
1305   newphi = create_phi_node (condstoretemp, join_bb);
1306   add_phi_arg (newphi, rhs, e0);
1307   add_phi_arg (newphi, name, e1);
1308
1309   lhs = unshare_expr (lhs);
1310   newexpr = build_gimple_modify_stmt (lhs, PHI_RESULT (newphi));
1311   mark_symbols_for_renaming (newexpr);
1312
1313   /* 5) Insert that PHI node.  */
1314   bsi = bsi_start (join_bb);
1315   while (!bsi_end_p (bsi) && TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
1316     bsi_next (&bsi);
1317   if (bsi_end_p (bsi))
1318     {
1319       bsi = bsi_last (join_bb);
1320       bsi_insert_after (&bsi, newexpr, BSI_NEW_STMT);
1321     }
1322   else
1323     bsi_insert_before (&bsi, newexpr, BSI_NEW_STMT);
1324
1325   return true;
1326 }
1327
1328 /* Always do these optimizations if we have SSA
1329    trees to work on.  */
1330 static bool
1331 gate_phiopt (void)
1332 {
1333   return 1;
1334 }
1335
1336 struct tree_opt_pass pass_phiopt =
1337 {
1338   "phiopt",                             /* name */
1339   gate_phiopt,                          /* gate */
1340   tree_ssa_phiopt,                      /* execute */
1341   NULL,                                 /* sub */
1342   NULL,                                 /* next */
1343   0,                                    /* static_pass_number */
1344   TV_TREE_PHIOPT,                       /* tv_id */
1345   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1346   0,                                    /* properties_provided */
1347   0,                                    /* properties_destroyed */
1348   0,                                    /* todo_flags_start */
1349   TODO_dump_func
1350     | TODO_ggc_collect
1351     | TODO_verify_ssa
1352     | TODO_verify_flow
1353     | TODO_verify_stmts,                /* todo_flags_finish */
1354   0                                     /* letter */
1355 };
1356
1357 static bool
1358 gate_cselim (void)
1359 {
1360   return flag_tree_cselim;
1361 }
1362
1363 struct tree_opt_pass pass_cselim =
1364 {
1365   "cselim",                             /* name */
1366   gate_cselim,                          /* gate */
1367   tree_ssa_cs_elim,                     /* execute */
1368   NULL,                                 /* sub */
1369   NULL,                                 /* next */
1370   0,                                    /* static_pass_number */
1371   TV_TREE_PHIOPT,                       /* tv_id */
1372   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1373   0,                                    /* properties_provided */
1374   0,                                    /* properties_destroyed */
1375   0,                                    /* todo_flags_start */
1376   TODO_dump_func
1377     | TODO_ggc_collect
1378     | TODO_verify_ssa
1379     | TODO_verify_flow
1380     | TODO_verify_stmts,                /* todo_flags_finish */
1381   0                                     /* letter */
1382 };