gcc/tree-ssa-phiopt.c

   1 /* Optimization of PHI nodes by converting them into straightline code.
   2    Copyright (C) 2004 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 2, 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 COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "errors.h"
  26 #include "ggc.h"
  27 #include "tree.h"
  28 #include "rtl.h"
  29 #include "flags.h"
  30 #include "tm_p.h"
  31 #include "basic-block.h"
  32 #include "timevar.h"
  33 #include "diagnostic.h"
  34 #include "tree-flow.h"
  35 #include "tree-pass.h"
  36 #include "tree-dump.h"
  37 #include "langhooks.h"
  38
  39 static void tree_ssa_phiopt (void);
  40 static bool conditional_replacement (basic_block, tree, tree, tree);
  41 static bool value_replacement (basic_block, tree, tree, tree);
  42 static bool abs_replacement (basic_block, tree, tree, tree);
  43 static void replace_phi_with_stmt (block_stmt_iterator, basic_block,
  44                                    basic_block, tree, tree);
  45 static bool candidate_bb_for_phi_optimization (basic_block,
  46                                                basic_block *,
  47                                                basic_block *);
  48
  49 /* This pass eliminates PHI nodes which can be trivially implemented as
  50    an assignment from a conditional expression.  ie if we have something
  51    like:
  52
  53      bb0:
  54       if (cond) goto bb2; else goto bb1;
  55      bb1:
  56      bb2:
  57       x = PHI (0 (bb1), 1 (bb0)
  58
  59    We can rewrite that as:
  60
  61      bb0:
  62      bb1:
  63      bb2:
  64       x = cond;
  65
  66    bb1 will become unreachable and bb0 and bb2 will almost always
  67    be merged into a single block.  This occurs often due to gimplification
  68     of conditionals.
  69
  70    Also done is the following optimization:
  71
  72      bb0:
  73       if (a != b) goto bb2; else goto bb1;
  74      bb1:
  75      bb2:
  76       x = PHI (a (bb1), b (bb0))
  77
  78    We can rewrite that as:
  79
  80      bb0:
  81      bb1:
  82      bb2:
  83       x = b;
  84
  85    This can sometimes occur as a result of other optimizations.  A
  86    similar transformation is done by the ifcvt RTL optimizer.
  87
  88    This pass also eliminates PHI nodes which are really absolute
  89    values.  i.e. if we have something like:
  90
  91      bb0:
  92       if (a >= 0) goto bb2; else goto bb1;
  93      bb1:
  94       x = -a;
  95      bb2:
  96       x = PHI (x (bb1), a (bb0));
  97
  98    We can rewrite that as:
  99
 100      bb0:
 101      bb1:
 102      bb2:
 103       x = ABS_EXPR< a >;
 104
 105    bb1 will become unreachable and bb0 and bb2 will almost always be merged
 106    into a single block.  Similar transformations are done by the ifcvt
 107    RTL optimizer.  */
 108
 109 static void
 110 tree_ssa_phiopt (void)
 111 {
 112   basic_block bb;
 113   bool removed_phis = false;
 114
 115   /* Search every basic block for PHI nodes we may be able to optimize.  */
 116   FOR_EACH_BB (bb)
 117     {
 118       tree arg0, arg1, phi;
 119
 120       /* We're searching for blocks with one PHI node which has two
 121          arguments.  */
 122       phi = phi_nodes (bb);
 123       if (phi && PHI_CHAIN (phi) == NULL
 124           && PHI_NUM_ARGS (phi) == 2)
 125         {
 126           arg0 = PHI_ARG_DEF (phi, 0);
 127           arg1 = PHI_ARG_DEF (phi, 1);
 128
 129           /* Do the replacement of conditional if it can be done.  */
 130             if (conditional_replacement (bb, phi, arg0, arg1)
 131                 || value_replacement (bb, phi, arg0, arg1)
 132                 || abs_replacement (bb, phi, arg0, arg1))
 133               {
 134                 /* We have done the replacement so we need to rebuild the
 135                    cfg when this pass is complete.  */
 136                 removed_phis = true;
 137               }
 138         }
 139     }
 140
 141   /* If we removed any PHIs, then we have unreachable blocks and blocks
 142      which need to be merged in the CFG.  */
 143   if (removed_phis)
 144     cleanup_tree_cfg ();
 145 }
 146
 147 /* Return TRUE if block BB has no executable statements, otherwise return
 148    FALSE.  */
 149 bool
 150 empty_block_p (basic_block bb)
 151 {
 152   block_stmt_iterator bsi;
 153
 154   /* BB must have no executable statements.  */
 155   bsi = bsi_start (bb);
 156   while (!bsi_end_p (bsi)
 157           && (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR
 158               || IS_EMPTY_STMT (bsi_stmt (bsi))))
 159     bsi_next (&bsi);
 160
 161   if (!bsi_end_p (bsi))
 162     return false;
 163
 164   return true;
 165 }
 166
 167 /* BB is a basic block which has only one PHI node with precisely two
 168    arguments.
 169
 170    Examine both of BB's predecessors to see if one ends with a
 171    COND_EXPR and the other is a successor of the COND_EXPR.  If so, then
 172    we may be able to optimize PHI nodes at the start of BB.
 173
 174    If so, mark store the block with the COND_EXPR into COND_BLOCK_P
 175    and the other block into OTHER_BLOCK_P and return true, otherwise
 176    return false.  */
 177
 178 static bool
 179 candidate_bb_for_phi_optimization (basic_block bb,
 180                                    basic_block *cond_block_p,
 181                                    basic_block *other_block_p)
 182 {
 183   tree last0, last1;
 184   basic_block cond_block, other_block;
 185
 186   /* One of the alternatives must come from a block ending with
 187      a COND_EXPR.  */
 188   last0 = last_stmt (bb->pred->src);
 189   last1 = last_stmt (bb->pred->pred_next->src);
 190   if (last0 && TREE_CODE (last0) == COND_EXPR)
 191     {
 192       cond_block = bb->pred->src;
 193       other_block = bb->pred->pred_next->src;
 194     }
 195   else if (last1 && TREE_CODE (last1) == COND_EXPR)
 196     {
 197       other_block = bb->pred->src;
 198       cond_block = bb->pred->pred_next->src;
 199     }
 200   else
 201     return false;
 202
 203   /* COND_BLOCK must have precisely two successors.  We indirectly
 204      verify that those successors are BB and OTHER_BLOCK.  */
 205   if (!cond_block->succ
 206       || !cond_block->succ->succ_next
 207       || cond_block->succ->succ_next->succ_next
 208       || (cond_block->succ->flags & EDGE_ABNORMAL) != 0
 209       || (cond_block->succ->succ_next->flags & EDGE_ABNORMAL) != 0)
 210     return false;
 211
 212   /* OTHER_BLOCK must have a single predecessor which is COND_BLOCK,
 213      OTHER_BLOCK must have a single successor which is BB and
 214      OTHER_BLOCK must have no PHI nodes.  */
 215   if (!other_block->pred
 216       || other_block->pred->src != cond_block
 217       || other_block->pred->pred_next
 218       || !other_block->succ
 219       || other_block->succ->dest != bb
 220       || other_block->succ->succ_next
 221       || phi_nodes (other_block))
 222     return false;
 223
 224   *cond_block_p = cond_block;
 225   *other_block_p = other_block;
 226   /* Everything looks OK.  */
 227   return true;
 228 }
 229
 230 /* Replace PHI in block BB with statement NEW.  NEW is inserted after
 231    BSI.  Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
 232    is known to have two edges, one of which must reach BB).  */
 233
 234 static void
 235 replace_phi_with_stmt (block_stmt_iterator bsi, basic_block bb,
 236                        basic_block cond_block, tree phi, tree new)
 237 {
 238   basic_block block_to_remove;
 239
 240   /* Insert our new statement at the head of our block.  */
 241   bsi_insert_after (&bsi, new, BSI_NEW_STMT);
 242
 243   /* Register our new statement as the defining statement for
 244      the result.  */
 245   SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new;
 246
 247   /* Remove the now useless PHI node.
 248
 249      We do not want to use remove_phi_node since that releases the
 250      SSA_NAME as well and the SSA_NAME is still being used.  */
 251   release_phi_node (phi);
 252   bb_ann (bb)->phi_nodes = NULL;
 253
 254   /* Remove the empty basic block.  */
 255   if (cond_block->succ->dest == bb)
 256     {
 257       cond_block->succ->flags |= EDGE_FALLTHRU;
 258       cond_block->succ->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 259
 260       block_to_remove = cond_block->succ->succ_next->dest;
 261     }
 262   else
 263     {
 264       cond_block->succ->succ_next->flags |= EDGE_FALLTHRU;
 265       cond_block->succ->succ_next->flags
 266         &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 267
 268       block_to_remove = cond_block->succ->dest;
 269     }
 270   delete_basic_block (block_to_remove);
 271
 272   /* Eliminate the COND_EXPR at the end of COND_BLOCK.  */
 273   bsi = bsi_last (cond_block);
 274   bsi_remove (&bsi);
 275
 276   if (dump_file && (dump_flags & TDF_DETAILS))
 277     fprintf (dump_file,
 278               "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
 279               cond_block->index,
 280               bb->index);
 281 }
 282
 283 /*  The function conditional_replacement does the main work of doing the
 284     conditional replacement.  Return true if the replacement is done.
 285     Otherwise return false.
 286     BB is the basic block where the replacement is going to be done on.  ARG0
 287     is argument 0 from PHI.  Likewise for ARG1.   */
 288
 289 static bool
 290 conditional_replacement (basic_block bb, tree phi, tree arg0, tree arg1)
 291 {
 292   tree result;
 293   tree old_result = NULL;
 294   basic_block other_block = NULL;
 295   basic_block cond_block = NULL;
 296   tree new, cond;
 297   block_stmt_iterator bsi;
 298   edge true_edge, false_edge;
 299   tree new_var = NULL;
 300
 301   /* The PHI arguments have the constants 0 and 1, then convert
 302      it to the conditional.  */
 303   if ((integer_zerop (arg0) && integer_onep (arg1))
 304       || (integer_zerop (arg1) && integer_onep (arg0)))
 305     ;
 306   else
 307     return false;
 308
 309   if (!candidate_bb_for_phi_optimization (bb, &cond_block, &other_block)
 310       || !empty_block_p (other_block))
 311     return false;
 312
 313   /* If the condition is not a naked SSA_NAME and its type does not
 314      match the type of the result, then we have to create a new
 315      variable to optimize this case as it would likely create
 316      non-gimple code when the condition was converted to the
 317      result's type.  */
 318   cond = COND_EXPR_COND (last_stmt (cond_block));
 319   result = PHI_RESULT (phi);
 320   if (TREE_CODE (cond) != SSA_NAME
 321       && !lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
 322     {
 323       new_var = make_rename_temp (TREE_TYPE (cond), NULL);
 324       old_result = cond;
 325       cond = new_var;
 326     }
 327
 328   /* If the condition was a naked SSA_NAME and the type is not the
 329      same as the type of the result, then convert the type of the
 330      condition.  */
 331   if (!lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
 332     cond = fold_convert (TREE_TYPE (result), cond);
 333
 334   /* We need to know which is the true edge and which is the false
 335      edge so that we know when to invert the condition below.  */
 336   extract_true_false_edges_from_block (cond_block, &true_edge, &false_edge);
 337
 338   /* Insert our new statement at the head of our block.  */
 339   bsi = bsi_start (bb);
 340
 341   if (old_result)
 342     {
 343       tree new1;
 344       if (TREE_CODE_CLASS (TREE_CODE (old_result)) != '<')
 345         return false;
 346
 347       new1 = build (TREE_CODE (old_result), TREE_TYPE (result),
 348                     TREE_OPERAND (old_result, 0),
 349                     TREE_OPERAND (old_result, 1));
 350
 351       new1 = build (MODIFY_EXPR, TREE_TYPE (result), new_var, new1);
 352       bsi_insert_after (&bsi, new1, BSI_NEW_STMT);
 353     }
 354
 355   /* At this point we know we have a COND_EXPR with two successors.
 356      One successor is BB, the other successor is an empty block which
 357      falls through into BB.
 358
 359      There is a single PHI node at the join point (BB) and its arguments
 360      are constants (0, 1).
 361
 362      So, given the condition COND, and the two PHI arguments, we can
 363      rewrite this PHI into non-branching code:
 364
 365        dest = (COND) or dest = COND'
 366
 367      We use the condition as-is if the argument associated with the
 368      true edge has the value one or the argument associated with the
 369      false edge as the value zero.  Note that those conditions are not
 370      the same since only one of the outgoing edges from the COND_EXPR
 371      will directly reach BB and thus be associated with an argument.  */
 372   if ((PHI_ARG_EDGE (phi, 0) == true_edge && integer_onep (arg0))
 373       || (PHI_ARG_EDGE (phi, 0) == false_edge && integer_zerop (arg0))
 374       || (PHI_ARG_EDGE (phi, 1) == true_edge && integer_onep (arg1))
 375       || (PHI_ARG_EDGE (phi, 1) == false_edge && integer_zerop (arg1)))
 376     {
 377       new = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 378                     PHI_RESULT (phi), cond);
 379     }
 380   else
 381     {
 382       tree cond1 = invert_truthvalue (cond);
 383
 384       cond = cond1;
 385       /* If what we get back is a conditional expression, there is no
 386           way that it can be gimple.  */
 387       if (TREE_CODE (cond) == COND_EXPR)
 388         return false;
 389
 390       /* If what we get back is not gimple try to create it as gimple by
 391          using a temporary variable.   */
 392       if (is_gimple_cast (cond)
 393           && !is_gimple_val (TREE_OPERAND (cond, 0)))
 394         {
 395           tree temp = TREE_OPERAND (cond, 0);
 396           tree new_var_1 = make_rename_temp (TREE_TYPE (temp), NULL);
 397           new = build (MODIFY_EXPR, TREE_TYPE (new_var_1), new_var_1, temp);
 398           bsi_insert_after (&bsi, new, BSI_NEW_STMT);
 399           cond = fold_convert (TREE_TYPE (result), new_var_1);
 400         }
 401
 402       if (TREE_CODE (cond) == TRUTH_NOT_EXPR
 403           &&  !is_gimple_val (TREE_OPERAND (cond, 0)))
 404         return false;
 405
 406       new = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 407                     PHI_RESULT (phi), cond);
 408     }
 409
 410   replace_phi_with_stmt (bsi, bb, cond_block, phi, new);
 411
 412   /* Note that we optimized this PHI.  */
 413   return true;
 414 }
 415
 416 /*  The function value_replacement does the main work of doing the value
 417     replacement.  Return true if the replacement is done.  Otherwise return
 418     false.
 419     BB is the basic block where the replacement is going to be done on.  ARG0
 420     is argument 0 from the PHI.  Likewise for ARG1.   */
 421
 422 static bool
 423 value_replacement (basic_block bb, tree phi, tree arg0, tree arg1)
 424 {
 425   tree result;
 426   basic_block other_block = NULL;
 427   basic_block cond_block = NULL;
 428   tree new, cond;
 429   edge true_edge, false_edge;
 430
 431   /* If the type says honor signed zeros we cannot do this
 432      optimization.   */
 433   if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
 434     return false;
 435
 436   if (!candidate_bb_for_phi_optimization (bb, &cond_block, &other_block)
 437       || !empty_block_p (other_block))
 438     return false;
 439
 440   cond = COND_EXPR_COND (last_stmt (cond_block));
 441   result = PHI_RESULT (phi);
 442
 443   /* This transformation is only valid for equality comparisons.  */
 444   if (TREE_CODE (cond) != NE_EXPR && TREE_CODE (cond) != EQ_EXPR)
 445     return false;
 446
 447   /* We need to know which is the true edge and which is the false
 448       edge so that we know if have abs or negative abs.  */
 449   extract_true_false_edges_from_block (cond_block, &true_edge, &false_edge);
 450
 451   /* At this point we know we have a COND_EXPR with two successors.
 452      One successor is BB, the other successor is an empty block which
 453      falls through into BB.
 454
 455      The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
 456
 457      There is a single PHI node at the join point (BB) with two arguments.
 458
 459      We now need to verify that the two arguments in the PHI node match
 460      the two arguments to the equality comparison.  */
 461
 462   if ((operand_equal_p (arg0, TREE_OPERAND (cond, 0), 0)
 463        && operand_equal_p (arg1, TREE_OPERAND (cond, 1), 0))
 464       || (operand_equal_p (arg1, TREE_OPERAND (cond, 0), 0)
 465           && operand_equal_p (arg0, TREE_OPERAND (cond, 1), 0)))
 466     {
 467       edge e;
 468       tree arg;
 469
 470       /* For NE_EXPR, we want to build an assignment result = arg where
 471          arg is the PHI argument associated with the true edge.  For
 472          EQ_EXPR we want the PHI argument associated with the false edge.  */
 473       e = (TREE_CODE (cond) == NE_EXPR ? true_edge : false_edge);
 474
 475       /* Unfortunately, E may not reach BB (it may instead have gone to
 476          OTHER_BLOCK).  If that is the case, then we want the single outgoing
 477          edge from OTHER_BLOCK which reaches BB and represents the desired
 478          path from COND_BLOCK.  */
 479       if (e->dest == other_block)
 480         e = e->dest->succ;
 481
 482       /* Now we know the incoming edge to BB that has the argument for the
 483          RHS of our new assignment statement.  */
 484       if (PHI_ARG_EDGE (phi, 0) == e)
 485         arg = arg0;
 486       else
 487         arg = arg1;
 488
 489       /* Build the new assignment.  */
 490       new = build (MODIFY_EXPR, TREE_TYPE (result), result, arg);
 491
 492       replace_phi_with_stmt (bsi_start (bb), bb, cond_block, phi, new);
 493
 494       /* Note that we optimized this PHI.  */
 495       return true;
 496     }
 497   return false;
 498 }
 499
 500 /*  The function absolute_replacement does the main work of doing the absolute
 501     replacement.  Return true if the replacement is done.  Otherwise return
 502     false.
 503     bb is the basic block where the replacement is going to be done on.  arg0
 504     is argument 0 from the phi.  Likewise for arg1.   */
 505 static bool
 506 abs_replacement (basic_block bb, tree phi, tree arg0, tree arg1)
 507 {
 508   tree result;
 509   basic_block other_block = NULL;
 510   basic_block cond_block = NULL;
 511   tree new, cond;
 512   block_stmt_iterator bsi;
 513   edge true_edge, false_edge;
 514   tree assign = NULL;
 515   edge e;
 516   tree rhs = NULL, lhs = NULL;
 517   bool negate;
 518   enum tree_code cond_code;
 519
 520   /* If the type says honor signed zeros we cannot do this
 521      optimization.   */
 522   if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
 523     return false;
 524
 525   if (!candidate_bb_for_phi_optimization (bb, &cond_block, &other_block))
 526     return false;
 527
 528   /* OTHER_BLOCK must have only one executable statement which must have the
 529      form arg0 = -arg1 or arg1 = -arg0.  */
 530   bsi = bsi_start (other_block);
 531   while (!bsi_end_p (bsi))
 532     {
 533       tree stmt = bsi_stmt (bsi);
 534
 535       /* Empty statements and labels are uninteresting.  */
 536       if (TREE_CODE (stmt) == LABEL_EXPR
 537           || IS_EMPTY_STMT (stmt))
 538         {
 539           bsi_next (&bsi);
 540           continue;
 541         }
 542
 543       /* If we found the assignment, but it was not the only executable
 544          statement in OTHER_BLOCK, then we can not optimize.  */
 545       if (assign)
 546         return false;
 547
 548       /* If we got here, then we have found the first executable statement
 549          in OTHER_BLOCK.  If it is anything other than arg = -arg1 or
 550          arg1 = -arg0, then we can not optimize.  */
 551       if (TREE_CODE (stmt) == MODIFY_EXPR)
 552         {
 553           lhs = TREE_OPERAND (stmt, 0);
 554           rhs = TREE_OPERAND (stmt, 1);
 555
 556           if (TREE_CODE (rhs) == NEGATE_EXPR)
 557             {
 558               rhs = TREE_OPERAND (rhs, 0);
 559
 560               /* The assignment has to be arg0 = -arg1 or arg1 = -arg0.  */
 561               if ((lhs == arg0 && rhs == arg1)
 562                   || (lhs == arg1 && rhs == arg0))
 563                 {
 564                   assign = stmt;
 565                   bsi_next (&bsi);
 566                 }
 567               else
 568                 return false;
 569             }
 570           else
 571             return false;
 572         }
 573       else
 574         return false;
 575     }
 576
 577   /* If we did not find the proper negation assignment, then we can not
 578      optimize.  */
 579   if (assign == NULL)
 580     return false;
 581
 582   cond = COND_EXPR_COND (last_stmt (cond_block));
 583   result = PHI_RESULT (phi);
 584
 585   /* Only relationals comparing arg[01] against zero are interesting.  */
 586   cond_code = TREE_CODE (cond);
 587   if (cond_code != GT_EXPR && cond_code != GE_EXPR
 588       && cond_code != LT_EXPR && cond_code != LE_EXPR)
 589     return false;
 590
 591   /* Make sure the conditional is arg[01] OP y.   */
 592   if (TREE_OPERAND (cond, 0) != rhs)
 593     return false;
 594
 595   if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))
 596                ? real_zerop (TREE_OPERAND (cond, 1))
 597                : integer_zerop (TREE_OPERAND (cond, 1)))
 598     ;
 599   else
 600     return false;
 601
 602   /* We need to know which is the true edge and which is the false
 603      edge so that we know if have abs or negative abs.  */
 604   extract_true_false_edges_from_block (cond_block, &true_edge, &false_edge);
 605
 606   /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
 607      will need to negate the result.  Similarly for LT_EXPR/LE_EXPR if
 608      the false edge goes to OTHER_BLOCK.  */
 609   if (cond_code == GT_EXPR || cond_code == GE_EXPR)
 610     e = true_edge;
 611   else
 612     e = false_edge;
 613
 614   if (e->dest == other_block)
 615     negate = true;
 616   else
 617     negate = false;
 618
 619   if (negate)
 620     lhs = make_rename_temp (TREE_TYPE (result), NULL);
 621   else
 622     lhs = result;
 623
 624   /*  Build the modify expression with abs expression.   */
 625   new = build (MODIFY_EXPR, TREE_TYPE (lhs),
 626                lhs, build1 (ABS_EXPR, TREE_TYPE (lhs), rhs));
 627
 628   replace_phi_with_stmt (bsi_start (bb), bb, cond_block, phi, new);
 629
 630   if (negate)
 631     {
 632
 633       /* Get the right BSI.  We want to insert after the recently
 634          added ABS_EXPR statement (which we know is the first statement
 635          in the block.  */
 636       bsi = bsi_start (bb);
 637       bsi_next (&bsi);
 638       new = build (MODIFY_EXPR, TREE_TYPE (result),
 639                    result, build1 (NEGATE_EXPR, TREE_TYPE (lhs), lhs));
 640
 641       bsi_insert_after (&bsi, new, BSI_NEW_STMT);
 642
 643       /* Register the new statement as defining the temporary -- this is
 644          normally done by replace_phi_with_stmt, but the link will be wrong
 645          if we had to negate the resulting value.  */
 646       SSA_NAME_DEF_STMT (result) = new;
 647     }
 648
 649   /* Note that we optimized this PHI.  */
 650   return true;
 651 }
 652
 653
 654 /* Always do these optimizations if we have SSA
 655    trees to work on.  */
 656 static bool
 657 gate_phiopt (void)
 658 {
 659   return 1;
 660 }
 661
 662 struct tree_opt_pass pass_phiopt =
 663 {
 664   "phiopt",                             /* name */
 665   gate_phiopt,                          /* gate */
 666   tree_ssa_phiopt,                      /* execute */
 667   NULL,                                 /* sub */
 668   NULL,                                 /* next */
 669   0,                                    /* static_pass_number */
 670   TV_TREE_PHIOPT,                       /* tv_id */
 671   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 672   0,                                    /* properties_provided */
 673   0,                                    /* properties_destroyed */
 674   0,                                    /* todo_flags_start */
 675   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 676     | TODO_verify_ssa | TODO_rename_vars
 677     | TODO_verify_flow,
 678   0                                     /* letter */
 679 };
 680
 681