gcc/tree-ssa-phiopt.c

   1 /* Optimization of PHI nodes by converting them into straightline code.
   2    Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation,
   3    Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by the
   9 Free Software Foundation; either version 3, or (at your option) any
  10 later version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT
  13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "ggc.h"
  26 #include "tree.h"
  27 #include "rtl.h"
  28 #include "flags.h"
  29 #include "tm_p.h"
  30 #include "basic-block.h"
  31 #include "timevar.h"
  32 #include "diagnostic.h"
  33 #include "tree-flow.h"
  34 #include "tree-pass.h"
  35 #include "tree-dump.h"
  36 #include "langhooks.h"
  37 #include "pointer-set.h"
  38 #include "domwalk.h"
  39
  40 static unsigned int tree_ssa_phiopt_worker (bool);
  41 static bool conditional_replacement (basic_block, basic_block,
  42                                      edge, edge, tree, tree, tree);
  43 static bool value_replacement (basic_block, basic_block,
  44                                edge, edge, tree, tree, tree);
  45 static bool minmax_replacement (basic_block, basic_block,
  46                                 edge, edge, tree, tree, tree);
  47 static bool abs_replacement (basic_block, basic_block,
  48                              edge, edge, tree, tree, tree);
  49 static bool cond_store_replacement (basic_block, basic_block, edge, edge,
  50                                     struct pointer_set_t *);
  51 static struct pointer_set_t * get_non_trapping (void);
  52 static void replace_phi_edge_with_variable (basic_block, edge, tree, tree);
  53
  54 /* This pass tries to replaces an if-then-else block with an
  55    assignment.  We have four kinds of transformations.  Some of these
  56    transformations are also performed by the ifcvt RTL optimizer.
  57
  58    Conditional Replacement
  59    -----------------------
  60
  61    This transformation, implemented in conditional_replacement,
  62    replaces
  63
  64      bb0:
  65       if (cond) goto bb2; else goto bb1;
  66      bb1:
  67      bb2:
  68       x = PHI <0 (bb1), 1 (bb0), ...>;
  69
  70    with
  71
  72      bb0:
  73       x' = cond;
  74       goto bb2;
  75      bb2:
  76       x = PHI <x' (bb0), ...>;
  77
  78    We remove bb1 as it becomes unreachable.  This occurs often due to
  79    gimplification of conditionals.
  80
  81    Value Replacement
  82    -----------------
  83
  84    This transformation, implemented in value_replacement, replaces
  85
  86      bb0:
  87        if (a != b) goto bb2; else goto bb1;
  88      bb1:
  89      bb2:
  90        x = PHI <a (bb1), b (bb0), ...>;
  91
  92    with
  93
  94      bb0:
  95      bb2:
  96        x = PHI <b (bb0), ...>;
  97
  98    This opportunity can sometimes occur as a result of other
  99    optimizations.
 100
 101    ABS Replacement
 102    ---------------
 103
 104    This transformation, implemented in abs_replacement, replaces
 105
 106      bb0:
 107        if (a >= 0) goto bb2; else goto bb1;
 108      bb1:
 109        x = -a;
 110      bb2:
 111        x = PHI <x (bb1), a (bb0), ...>;
 112
 113    with
 114
 115      bb0:
 116        x' = ABS_EXPR< a >;
 117      bb2:
 118        x = PHI <x' (bb0), ...>;
 119
 120    MIN/MAX Replacement
 121    -------------------
 122
 123    This transformation, minmax_replacement replaces
 124
 125      bb0:
 126        if (a <= b) goto bb2; else goto bb1;
 127      bb1:
 128      bb2:
 129        x = PHI <b (bb1), a (bb0), ...>;
 130
 131    with
 132
 133      bb0:
 134        x' = MIN_EXPR (a, b)
 135      bb2:
 136        x = PHI <x' (bb0), ...>;
 137
 138    A similar transformation is done for MAX_EXPR.  */
 139
 140 static unsigned int
 141 tree_ssa_phiopt (void)
 142 {
 143   return tree_ssa_phiopt_worker (false);
 144 }
 145
 146 /* This pass tries to transform conditional stores into unconditional
 147    ones, enabling further simplifications with the simpler then and else
 148    blocks.  In particular it replaces this:
 149
 150      bb0:
 151        if (cond) goto bb2; else goto bb1;
 152      bb1:
 153        *p = RHS
 154      bb2:
 155
 156    with
 157
 158      bb0:
 159        if (cond) goto bb1; else goto bb2;
 160      bb1:
 161        condtmp' = *p;
 162      bb2:
 163        condtmp = PHI <RHS, condtmp'>
 164        *p = condtmp
 165
 166    This transformation can only be done under several constraints,
 167    documented below.  */
 168
 169 static unsigned int
 170 tree_ssa_cs_elim (void)
 171 {
 172   return tree_ssa_phiopt_worker (true);
 173 }
 174
 175 /* For conditional store replacement we need a temporary to
 176    put the old contents of the memory in.  */
 177 static tree condstoretemp;
 178
 179 /* The core routine of conditional store replacement and normal
 180    phi optimizations.  Both share much of the infrastructure in how
 181    to match applicable basic block patterns.  DO_STORE_ELIM is true
 182    when we want to do conditional store replacement, false otherwise.  */
 183 static unsigned int
 184 tree_ssa_phiopt_worker (bool do_store_elim)
 185 {
 186   basic_block bb;
 187   basic_block *bb_order;
 188   unsigned n, i;
 189   bool cfgchanged = false;
 190   struct pointer_set_t *nontrap = 0;
 191
 192   if (do_store_elim)
 193     {
 194       condstoretemp = NULL_TREE;
 195       /* Calculate the set of non-trapping memory accesses.  */
 196       nontrap = get_non_trapping ();
 197     }
 198
 199   /* Search every basic block for COND_EXPR we may be able to optimize.
 200
 201      We walk the blocks in order that guarantees that a block with
 202      a single predecessor is processed before the predecessor.
 203      This ensures that we collapse inner ifs before visiting the
 204      outer ones, and also that we do not try to visit a removed
 205      block.  */
 206   bb_order = blocks_in_phiopt_order ();
 207   n = n_basic_blocks - NUM_FIXED_BLOCKS;
 208
 209   for (i = 0; i < n; i++)
 210     {
 211       tree cond_expr;
 212       tree phi;
 213       basic_block bb1, bb2;
 214       edge e1, e2;
 215       tree arg0, arg1;
 216
 217       bb = bb_order[i];
 218
 219       cond_expr = last_stmt (bb);
 220       /* Check to see if the last statement is a COND_EXPR.  */
 221       if (!cond_expr
 222           || TREE_CODE (cond_expr) != COND_EXPR)
 223         continue;
 224
 225       e1 = EDGE_SUCC (bb, 0);
 226       bb1 = e1->dest;
 227       e2 = EDGE_SUCC (bb, 1);
 228       bb2 = e2->dest;
 229
 230       /* We cannot do the optimization on abnormal edges.  */
 231       if ((e1->flags & EDGE_ABNORMAL) != 0
 232           || (e2->flags & EDGE_ABNORMAL) != 0)
 233        continue;
 234
 235       /* If either bb1's succ or bb2 or bb2's succ is non NULL.  */
 236       if (EDGE_COUNT (bb1->succs) == 0
 237           || bb2 == NULL
 238           || EDGE_COUNT (bb2->succs) == 0)
 239         continue;
 240
 241       /* Find the bb which is the fall through to the other.  */
 242       if (EDGE_SUCC (bb1, 0)->dest == bb2)
 243         ;
 244       else if (EDGE_SUCC (bb2, 0)->dest == bb1)
 245         {
 246           basic_block bb_tmp = bb1;
 247           edge e_tmp = e1;
 248           bb1 = bb2;
 249           bb2 = bb_tmp;
 250           e1 = e2;
 251           e2 = e_tmp;
 252         }
 253       else
 254         continue;
 255
 256       e1 = EDGE_SUCC (bb1, 0);
 257
 258       /* Make sure that bb1 is just a fall through.  */
 259       if (!single_succ_p (bb1)
 260           || (e1->flags & EDGE_FALLTHRU) == 0)
 261         continue;
 262
 263       /* Also make sure that bb1 only have one predecessor and that it
 264          is bb.  */
 265       if (!single_pred_p (bb1)
 266           || single_pred (bb1) != bb)
 267         continue;
 268
 269       if (do_store_elim)
 270         {
 271           /* bb1 is the middle block, bb2 the join block, bb the split block,
 272              e1 the fallthrough edge from bb1 to bb2.  We can't do the
 273              optimization if the join block has more than two predecessors.  */
 274           if (EDGE_COUNT (bb2->preds) > 2)
 275             continue;
 276           if (cond_store_replacement (bb1, bb2, e1, e2, nontrap))
 277             cfgchanged = true;
 278         }
 279       else
 280         {
 281           phi = phi_nodes (bb2);
 282
 283           /* Check to make sure that there is only one PHI node.
 284              TODO: we could do it with more than one iff the other PHI nodes
 285              have the same elements for these two edges.  */
 286           if (!phi || PHI_CHAIN (phi) != NULL)
 287             continue;
 288
 289           arg0 = PHI_ARG_DEF_TREE (phi, e1->dest_idx);
 290           arg1 = PHI_ARG_DEF_TREE (phi, e2->dest_idx);
 291
 292           /* Something is wrong if we cannot find the arguments in the PHI
 293              node.  */
 294           gcc_assert (arg0 != NULL && arg1 != NULL);
 295
 296           /* Do the replacement of conditional if it can be done.  */
 297           if (conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
 298             cfgchanged = true;
 299           else if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
 300             cfgchanged = true;
 301           else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
 302             cfgchanged = true;
 303           else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
 304             cfgchanged = true;
 305         }
 306     }
 307
 308   free (bb_order);
 309
 310   if (do_store_elim)
 311     pointer_set_destroy (nontrap);
 312   /* If the CFG has changed, we should cleanup the CFG.  */
 313   if (cfgchanged && do_store_elim)
 314     {
 315       /* In cond-store replacement we have added some loads on edges
 316          and new VOPS (as we moved the store, and created a load).  */
 317       bsi_commit_edge_inserts ();
 318       return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
 319     }
 320   else if (cfgchanged)
 321     return TODO_cleanup_cfg;
 322   return 0;
 323 }
 324
 325 /* Returns the list of basic blocks in the function in an order that guarantees
 326    that if a block X has just a single predecessor Y, then Y is after X in the
 327    ordering.  */
 328
 329 basic_block *
 330 blocks_in_phiopt_order (void)
 331 {
 332   basic_block x, y;
 333   basic_block *order = XNEWVEC (basic_block, n_basic_blocks);
 334   unsigned n = n_basic_blocks - NUM_FIXED_BLOCKS;
 335   unsigned np, i;
 336   sbitmap visited = sbitmap_alloc (last_basic_block);
 337
 338 #define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
 339 #define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
 340
 341   sbitmap_zero (visited);
 342
 343   MARK_VISITED (ENTRY_BLOCK_PTR);
 344   FOR_EACH_BB (x)
 345     {
 346       if (VISITED_P (x))
 347         continue;
 348
 349       /* Walk the predecessors of x as long as they have precisely one
 350          predecessor and add them to the list, so that they get stored
 351          after x.  */
 352       for (y = x, np = 1;
 353            single_pred_p (y) && !VISITED_P (single_pred (y));
 354            y = single_pred (y))
 355         np++;
 356       for (y = x, i = n - np;
 357            single_pred_p (y) && !VISITED_P (single_pred (y));
 358            y = single_pred (y), i++)
 359         {
 360           order[i] = y;
 361           MARK_VISITED (y);
 362         }
 363       order[i] = y;
 364       MARK_VISITED (y);
 365
 366       gcc_assert (i == n - 1);
 367       n -= np;
 368     }
 369
 370   sbitmap_free (visited);
 371   gcc_assert (n == 0);
 372   return order;
 373
 374 #undef MARK_VISITED
 375 #undef VISITED_P
 376 }
 377
 378
 379 /* Return TRUE if block BB has no executable statements, otherwise return
 380    FALSE.  */
 381
 382 bool
 383 empty_block_p (basic_block bb)
 384 {
 385   block_stmt_iterator bsi;
 386
 387   /* BB must have no executable statements.  */
 388   bsi = bsi_start (bb);
 389   while (!bsi_end_p (bsi)
 390           && (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR
 391               || IS_EMPTY_STMT (bsi_stmt (bsi))))
 392     bsi_next (&bsi);
 393
 394   if (!bsi_end_p (bsi))
 395     return false;
 396
 397   return true;
 398 }
 399
 400 /* Replace PHI node element whose edge is E in block BB with variable NEW.
 401    Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
 402    is known to have two edges, one of which must reach BB).  */
 403
 404 static void
 405 replace_phi_edge_with_variable (basic_block cond_block,
 406                                 edge e, tree phi, tree new_tree)
 407 {
 408   basic_block bb = bb_for_stmt (phi);
 409   basic_block block_to_remove;
 410   block_stmt_iterator bsi;
 411
 412   /* Change the PHI argument to new.  */
 413   SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new_tree);
 414
 415   /* Remove the empty basic block.  */
 416   if (EDGE_SUCC (cond_block, 0)->dest == bb)
 417     {
 418       EDGE_SUCC (cond_block, 0)->flags |= EDGE_FALLTHRU;
 419       EDGE_SUCC (cond_block, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 420       EDGE_SUCC (cond_block, 0)->probability = REG_BR_PROB_BASE;
 421       EDGE_SUCC (cond_block, 0)->count += EDGE_SUCC (cond_block, 1)->count;
 422
 423       block_to_remove = EDGE_SUCC (cond_block, 1)->dest;
 424     }
 425   else
 426     {
 427       EDGE_SUCC (cond_block, 1)->flags |= EDGE_FALLTHRU;
 428       EDGE_SUCC (cond_block, 1)->flags
 429         &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 430       EDGE_SUCC (cond_block, 1)->probability = REG_BR_PROB_BASE;
 431       EDGE_SUCC (cond_block, 1)->count += EDGE_SUCC (cond_block, 0)->count;
 432
 433       block_to_remove = EDGE_SUCC (cond_block, 0)->dest;
 434     }
 435   delete_basic_block (block_to_remove);
 436
 437   /* Eliminate the COND_EXPR at the end of COND_BLOCK.  */
 438   bsi = bsi_last (cond_block);
 439   bsi_remove (&bsi, true);
 440
 441   if (dump_file && (dump_flags & TDF_DETAILS))
 442     fprintf (dump_file,
 443               "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
 444               cond_block->index,
 445               bb->index);
 446 }
 447
 448 /*  The function conditional_replacement does the main work of doing the
 449     conditional replacement.  Return true if the replacement is done.
 450     Otherwise return false.
 451     BB is the basic block where the replacement is going to be done on.  ARG0
 452     is argument 0 from PHI.  Likewise for ARG1.  */
 453
 454 static bool
 455 conditional_replacement (basic_block cond_bb, basic_block middle_bb,
 456                          edge e0, edge e1, tree phi,
 457                          tree arg0, tree arg1)
 458 {
 459   tree result;
 460   tree old_result = NULL;
 461   tree new_stmt, cond;
 462   block_stmt_iterator bsi;
 463   edge true_edge, false_edge;
 464   tree new_var = NULL;
 465   tree new_var1;
 466
 467   /* FIXME: Gimplification of complex type is too hard for now.  */
 468   if (TREE_CODE (TREE_TYPE (arg0)) == COMPLEX_TYPE
 469       || TREE_CODE (TREE_TYPE (arg1)) == COMPLEX_TYPE)
 470     return false;
 471
 472   /* The PHI arguments have the constants 0 and 1, then convert
 473      it to the conditional.  */
 474   if ((integer_zerop (arg0) && integer_onep (arg1))
 475       || (integer_zerop (arg1) && integer_onep (arg0)))
 476     ;
 477   else
 478     return false;
 479
 480   if (!empty_block_p (middle_bb))
 481     return false;
 482
 483   /* If the condition is not a naked SSA_NAME and its type does not
 484      match the type of the result, then we have to create a new
 485      variable to optimize this case as it would likely create
 486      non-gimple code when the condition was converted to the
 487      result's type.  */
 488   cond = COND_EXPR_COND (last_stmt (cond_bb));
 489   result = PHI_RESULT (phi);
 490   if (TREE_CODE (cond) != SSA_NAME
 491       && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (cond)))
 492     {
 493       tree tmp;
 494
 495       if (!COMPARISON_CLASS_P (cond))
 496         return false;
 497
 498       tmp = create_tmp_var (TREE_TYPE (cond), NULL);
 499       add_referenced_var (tmp);
 500       new_var = make_ssa_name (tmp, NULL);
 501       old_result = cond;
 502       cond = new_var;
 503     }
 504
 505   /* If the condition was a naked SSA_NAME and the type is not the
 506      same as the type of the result, then convert the type of the
 507      condition.  */
 508   if (!useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (cond)))
 509     cond = fold_convert (TREE_TYPE (result), cond);
 510
 511   /* We need to know which is the true edge and which is the false
 512      edge so that we know when to invert the condition below.  */
 513   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
 514
 515   /* Insert our new statement at the end of conditional block before the
 516      COND_EXPR.  */
 517   bsi = bsi_last (cond_bb);
 518   bsi_insert_before (&bsi, build_empty_stmt (), BSI_NEW_STMT);
 519
 520   if (old_result)
 521     {
 522       tree new1;
 523
 524       new1 = build2 (TREE_CODE (old_result), TREE_TYPE (old_result),
 525                      TREE_OPERAND (old_result, 0),
 526                      TREE_OPERAND (old_result, 1));
 527
 528       new1 = build_gimple_modify_stmt (new_var, new1);
 529       SSA_NAME_DEF_STMT (new_var) = new1;
 530
 531       bsi_insert_after (&bsi, new1, BSI_NEW_STMT);
 532     }
 533
 534   new_var1 = duplicate_ssa_name (PHI_RESULT (phi), NULL);
 535
 536
 537   /* At this point we know we have a COND_EXPR with two successors.
 538      One successor is BB, the other successor is an empty block which
 539      falls through into BB.
 540
 541      There is a single PHI node at the join point (BB) and its arguments
 542      are constants (0, 1).
 543
 544      So, given the condition COND, and the two PHI arguments, we can
 545      rewrite this PHI into non-branching code:
 546
 547        dest = (COND) or dest = COND'
 548
 549      We use the condition as-is if the argument associated with the
 550      true edge has the value one or the argument associated with the
 551      false edge as the value zero.  Note that those conditions are not
 552      the same since only one of the outgoing edges from the COND_EXPR
 553      will directly reach BB and thus be associated with an argument.  */
 554   if ((e0 == true_edge && integer_onep (arg0))
 555       || (e0 == false_edge && integer_zerop (arg0))
 556       || (e1 == true_edge && integer_onep (arg1))
 557       || (e1 == false_edge && integer_zerop (arg1)))
 558     {
 559       new_stmt = build_gimple_modify_stmt (new_var1, cond);
 560     }
 561   else
 562     {
 563       tree cond1 = invert_truthvalue (cond);
 564
 565       cond = cond1;
 566
 567       /* If what we get back is a conditional expression, there is no
 568           way that it can be gimple.  */
 569       if (TREE_CODE (cond) == COND_EXPR)
 570         {
 571           release_ssa_name (new_var1);
 572           return false;
 573         }
 574
 575       /* If COND is not something we can expect to be reducible to a GIMPLE
 576          condition, return early.  */
 577       if (is_gimple_cast (cond))
 578         cond1 = TREE_OPERAND (cond, 0);
 579       if (TREE_CODE (cond1) == TRUTH_NOT_EXPR
 580           && !is_gimple_val (TREE_OPERAND (cond1, 0)))
 581         {
 582           release_ssa_name (new_var1);
 583           return false;
 584         }
 585
 586       /* If what we get back is not gimple try to create it as gimple by
 587          using a temporary variable.  */
 588       if (is_gimple_cast (cond)
 589           && !is_gimple_val (TREE_OPERAND (cond, 0)))
 590         {
 591           tree op0, tmp, cond_tmp;
 592
 593           /* Only "real" casts are OK here, not everything that is
 594              acceptable to is_gimple_cast.  Make sure we don't do
 595              anything stupid here.  */
 596           gcc_assert (CONVERT_EXPR_P (cond));
 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   const_tree n = ((const struct name_to_bb *)p)->ssa_name;
1119   return htab_hash_pointer (n) ^ ((const 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 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 };