gcc/tree-ssa-phiopt.c

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