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