gcc/tree-ssa-phiopt.c

   1 /* Optimization of PHI nodes by converting them into straightline code.
   2    Copyright (C) 2004, 2005 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, basic_block, basic_block,
  41                                      edge, edge, tree, tree, tree);
  42 static bool value_replacement (basic_block, basic_block, basic_block,
  43                                edge, edge, tree, tree, tree);
  44 static bool minmax_replacement (basic_block, basic_block, basic_block,
  45                                 edge, edge, tree, tree, tree);
  46 static bool abs_replacement (basic_block, basic_block, basic_block,
  47                              edge, edge, tree, tree, tree);
  48 static void replace_phi_edge_with_variable (basic_block, basic_block, edge,
  49                                             tree, tree);
  50 static basic_block *blocks_in_phiopt_order (void);
  51
  52 /* This pass eliminates PHI nodes which can be trivially implemented as
  53    an assignment from a conditional expression.  i.e. if we have something
  54    like:
  55
  56      bb0:
  57       if (cond) goto bb2; else goto bb1;
  58      bb1:
  59      bb2:
  60       x = PHI (0 (bb1), 1 (bb0)
  61
  62    We can rewrite that as:
  63
  64      bb0:
  65      bb1:
  66      bb2:
  67       x = cond;
  68
  69    bb1 will become unreachable and bb0 and bb2 will almost always
  70    be merged into a single block.  This occurs often due to gimplification
  71     of conditionals.
  72
  73    Also done is the following optimization:
  74
  75      bb0:
  76       if (a != b) goto bb2; else goto bb1;
  77      bb1:
  78      bb2:
  79       x = PHI (a (bb1), b (bb0))
  80
  81    We can rewrite that as:
  82
  83      bb0:
  84      bb1:
  85      bb2:
  86       x = b;
  87
  88    This can sometimes occur as a result of other optimizations.  A
  89    similar transformation is done by the ifcvt RTL optimizer.
  90
  91    This pass also eliminates PHI nodes which are really absolute
  92    values.  i.e. if we have something like:
  93
  94      bb0:
  95       if (a >= 0) goto bb2; else goto bb1;
  96      bb1:
  97       x = -a;
  98      bb2:
  99       x = PHI (x (bb1), a (bb0));
 100
 101    We can rewrite that as:
 102
 103      bb0:
 104      bb1:
 105      bb2:
 106       x = ABS_EXPR< a >;
 107
 108    Similarly,
 109
 110      bb0:
 111       if (a <= b) goto bb2; else goto bb1;
 112      bb1:
 113       goto bb2;
 114      bb2:
 115       x = PHI (b (bb1), a (bb0));
 116
 117    Becomes
 118
 119      x = MIN_EXPR (a, b)
 120
 121    And the same transformation for MAX_EXPR.
 122
 123    bb1 will become unreachable and bb0 and bb2 will almost always be merged
 124    into a single block.  Similar transformations are done by the ifcvt
 125    RTL optimizer.  */
 126
 127 static void
 128 tree_ssa_phiopt (void)
 129 {
 130   basic_block bb;
 131   basic_block *bb_order;
 132   unsigned n, i;
 133
 134   /* Search every basic block for COND_EXPR we may be able to optimize.
 135
 136      We walk the blocks in order that guarantees that a block with
 137      a single predecessor is processed before the predecessor.
 138      This ensures that we collapse inner ifs before visiting the
 139      outer ones, and also that we do not try to visit a removed
 140      block.  */
 141   bb_order = blocks_in_phiopt_order ();
 142   n = n_basic_blocks;
 143
 144   for (i = 0; i < n; i++)
 145     {
 146       tree cond_expr;
 147       tree phi;
 148       basic_block bb1, bb2;
 149       edge e1, e2;
 150       tree arg0, arg1;
 151
 152       bb = bb_order[i];
 153
 154       cond_expr = last_stmt (bb);
 155       /* Check to see if the last statement is a COND_EXPR.  */
 156       if (!cond_expr
 157           || TREE_CODE (cond_expr) != COND_EXPR)
 158         continue;
 159
 160       e1 = EDGE_SUCC (bb, 0);
 161       bb1 = e1->dest;
 162       e2 = EDGE_SUCC (bb, 1);
 163       bb2 = e2->dest;
 164
 165       /* We cannot do the optimization on abnormal edges.  */
 166       if ((e1->flags & EDGE_ABNORMAL) != 0
 167           || (e2->flags & EDGE_ABNORMAL) != 0)
 168        continue;
 169
 170       /* If either bb1's succ or bb2 or bb2's succ is non NULL.  */
 171       if (EDGE_COUNT (bb1->succs) == 0
 172           || bb2 == NULL
 173           || EDGE_COUNT (bb2->succs) == 0)
 174         continue;
 175
 176       /* Find the bb which is the fall through to the other.  */
 177       if (EDGE_SUCC (bb1, 0)->dest == bb2)
 178         ;
 179       else if (EDGE_SUCC (bb2, 0)->dest == bb1)
 180         {
 181           basic_block bb_tmp = bb1;
 182           edge e_tmp = e1;
 183           bb1 = bb2;
 184           bb2 = bb_tmp;
 185           e1 = e2;
 186           e2 = e_tmp;
 187         }
 188       else
 189         continue;
 190
 191       e1 = EDGE_SUCC (bb1, 0);
 192
 193       /* Make sure that bb1 is just a fall through.  */
 194       if (!single_succ_p (bb1) > 1
 195           || (e1->flags & EDGE_FALLTHRU) == 0)
 196         continue;
 197
 198       /* Also make that bb1 only have one pred and it is bb.  */
 199       if (!single_pred_p (bb1)
 200           || single_pred (bb1) != bb)
 201         continue;
 202
 203       phi = phi_nodes (bb2);
 204
 205       /* Check to make sure that there is only one PHI node.
 206          TODO: we could do it with more than one iff the other PHI nodes
 207          have the same elements for these two edges.  */
 208       if (!phi || PHI_CHAIN (phi) != NULL)
 209         continue;
 210
 211       arg0 = PHI_ARG_DEF_TREE (phi, e1->dest_idx);
 212       arg1 = PHI_ARG_DEF_TREE (phi, e2->dest_idx);
 213
 214       /* We know something is wrong if we cannot find the edges in the PHI
 215          node.  */
 216       gcc_assert (arg0 != NULL && arg1 != NULL);
 217
 218       /* Do the replacement of conditional if it can be done.  */
 219       if (conditional_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1))
 220         ;
 221       else if (value_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1))
 222         ;
 223       else if (abs_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1))
 224         ;
 225       else
 226         minmax_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1);
 227     }
 228
 229   free (bb_order);
 230 }
 231
 232 /* Returns the list of basic blocks in the function in an order that guarantees
 233    that if a block X has just a single predecessor Y, then Y is after X in the
 234    ordering.  */
 235
 236 static basic_block *
 237 blocks_in_phiopt_order (void)
 238 {
 239   basic_block x, y;
 240   basic_block *order = xmalloc (sizeof (basic_block) * n_basic_blocks);
 241   unsigned n = n_basic_blocks, np, i;
 242   sbitmap visited = sbitmap_alloc (last_basic_block + 2);
 243
 244 #define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index + 2))
 245 #define VISITED_P(BB) (TEST_BIT (visited, (BB)->index + 2))
 246
 247   sbitmap_zero (visited);
 248
 249   MARK_VISITED (ENTRY_BLOCK_PTR);
 250   FOR_EACH_BB (x)
 251     {
 252       if (VISITED_P (x))
 253         continue;
 254
 255       /* Walk the predecessors of x as long as they have precisely one
 256          predecessor and add them to the list, so that they get stored
 257          after x.  */
 258       for (y = x, np = 1;
 259            single_pred_p (y) && !VISITED_P (single_pred (y));
 260            y = single_pred (y))
 261         np++;
 262       for (y = x, i = n - np;
 263            single_pred_p (y) && !VISITED_P (single_pred (y));
 264            y = single_pred (y), i++)
 265         {
 266           order[i] = y;
 267           MARK_VISITED (y);
 268         }
 269       order[i] = y;
 270       MARK_VISITED (y);
 271
 272       gcc_assert (i == n - 1);
 273       n -= np;
 274     }
 275
 276   sbitmap_free (visited);
 277   gcc_assert (n == 0);
 278   return order;
 279
 280 #undef MARK_VISITED
 281 #undef VISITED_P
 282 }
 283
 284 /* Return TRUE if block BB has no executable statements, otherwise return
 285    FALSE.  */
 286 bool
 287 empty_block_p (basic_block bb)
 288 {
 289   block_stmt_iterator bsi;
 290
 291   /* BB must have no executable statements.  */
 292   bsi = bsi_start (bb);
 293   while (!bsi_end_p (bsi)
 294           && (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR
 295               || IS_EMPTY_STMT (bsi_stmt (bsi))))
 296     bsi_next (&bsi);
 297
 298   if (!bsi_end_p (bsi))
 299     return false;
 300
 301   return true;
 302 }
 303
 304 /* Replace PHI node element whoes edge is E in block BB with variable NEW.
 305    Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
 306    is known to have two edges, one of which must reach BB).  */
 307
 308 static void
 309 replace_phi_edge_with_variable (basic_block cond_block, basic_block bb,
 310                                 edge e, tree phi, tree new)
 311 {
 312   basic_block block_to_remove;
 313   block_stmt_iterator bsi;
 314
 315   /* Change the PHI argument to new.  */
 316   PHI_ARG_DEF_TREE (phi, e->dest_idx) = new;
 317
 318   /* Remove the empty basic block.  */
 319   if (EDGE_SUCC (cond_block, 0)->dest == bb)
 320     {
 321       EDGE_SUCC (cond_block, 0)->flags |= EDGE_FALLTHRU;
 322       EDGE_SUCC (cond_block, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 323
 324       block_to_remove = EDGE_SUCC (cond_block, 1)->dest;
 325     }
 326   else
 327     {
 328       EDGE_SUCC (cond_block, 1)->flags |= EDGE_FALLTHRU;
 329       EDGE_SUCC (cond_block, 1)->flags
 330         &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 331
 332       block_to_remove = EDGE_SUCC (cond_block, 0)->dest;
 333     }
 334   delete_basic_block (block_to_remove);
 335
 336   /* Eliminate the COND_EXPR at the end of COND_BLOCK.  */
 337   bsi = bsi_last (cond_block);
 338   bsi_remove (&bsi);
 339
 340   if (dump_file && (dump_flags & TDF_DETAILS))
 341     fprintf (dump_file,
 342               "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
 343               cond_block->index,
 344               bb->index);
 345 }
 346
 347 /*  The function conditional_replacement does the main work of doing the
 348     conditional replacement.  Return true if the replacement is done.
 349     Otherwise return false.
 350     BB is the basic block where the replacement is going to be done on.  ARG0
 351     is argument 0 from PHI.  Likewise for ARG1.  */
 352
 353 static bool
 354 conditional_replacement (basic_block cond_bb, basic_block middle_bb,
 355                          basic_block phi_bb, edge e0, edge e1, tree phi,
 356                          tree arg0, tree arg1)
 357 {
 358   tree result;
 359   tree old_result = NULL;
 360   tree new, cond;
 361   block_stmt_iterator bsi;
 362   edge true_edge, false_edge;
 363   tree new_var = NULL;
 364   tree new_var1;
 365
 366   /* The PHI arguments have the constants 0 and 1, then convert
 367      it to the conditional.  */
 368   if ((integer_zerop (arg0) && integer_onep (arg1))
 369       || (integer_zerop (arg1) && integer_onep (arg0)))
 370     ;
 371   else
 372     return false;
 373
 374   if (!empty_block_p (middle_bb))
 375     return false;
 376
 377   /* If the condition is not a naked SSA_NAME and its type does not
 378      match the type of the result, then we have to create a new
 379      variable to optimize this case as it would likely create
 380      non-gimple code when the condition was converted to the
 381      result's type.  */
 382   cond = COND_EXPR_COND (last_stmt (cond_bb));
 383   result = PHI_RESULT (phi);
 384   if (TREE_CODE (cond) != SSA_NAME
 385       && !lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
 386     {
 387       new_var = make_rename_temp (TREE_TYPE (cond), NULL);
 388       old_result = cond;
 389       cond = new_var;
 390     }
 391
 392   /* If the condition was a naked SSA_NAME and the type is not the
 393      same as the type of the result, then convert the type of the
 394      condition.  */
 395   if (!lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
 396     cond = fold_convert (TREE_TYPE (result), cond);
 397
 398   /* We need to know which is the true edge and which is the false
 399      edge so that we know when to invert the condition below.  */
 400   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
 401
 402   /* Insert our new statement at the end of conditional block before the
 403      COND_EXPR.  */
 404   bsi = bsi_last (cond_bb);
 405   bsi_insert_before (&bsi, build_empty_stmt (), BSI_NEW_STMT);
 406
 407   if (old_result)
 408     {
 409       tree new1;
 410       if (!COMPARISON_CLASS_P (old_result))
 411         return false;
 412
 413       new1 = build2 (TREE_CODE (old_result), TREE_TYPE (old_result),
 414                      TREE_OPERAND (old_result, 0),
 415                      TREE_OPERAND (old_result, 1));
 416
 417       new1 = build2 (MODIFY_EXPR, TREE_TYPE (old_result), new_var, new1);
 418       bsi_insert_after (&bsi, new1, BSI_NEW_STMT);
 419     }
 420
 421   new_var1 = duplicate_ssa_name (PHI_RESULT (phi), NULL);
 422
 423
 424   /* At this point we know we have a COND_EXPR with two successors.
 425      One successor is BB, the other successor is an empty block which
 426      falls through into BB.
 427
 428      There is a single PHI node at the join point (BB) and its arguments
 429      are constants (0, 1).
 430
 431      So, given the condition COND, and the two PHI arguments, we can
 432      rewrite this PHI into non-branching code:
 433
 434        dest = (COND) or dest = COND'
 435
 436      We use the condition as-is if the argument associated with the
 437      true edge has the value one or the argument associated with the
 438      false edge as the value zero.  Note that those conditions are not
 439      the same since only one of the outgoing edges from the COND_EXPR
 440      will directly reach BB and thus be associated with an argument.  */
 441   if ((e0 == true_edge && integer_onep (arg0))
 442       || (e0 == false_edge && integer_zerop (arg0))
 443       || (e1 == true_edge && integer_onep (arg1))
 444       || (e1 == false_edge && integer_zerop (arg1)))
 445     {
 446       new = build2 (MODIFY_EXPR, TREE_TYPE (new_var1), new_var1, cond);
 447     }
 448   else
 449     {
 450       tree cond1 = invert_truthvalue (cond);
 451
 452       cond = cond1;
 453       /* If what we get back is a conditional expression, there is no
 454           way that it can be gimple.  */
 455       if (TREE_CODE (cond) == COND_EXPR)
 456         {
 457           release_ssa_name (new_var1);
 458           return false;
 459         }
 460
 461       /* If what we get back is not gimple try to create it as gimple by
 462          using a temporary variable.  */
 463       if (is_gimple_cast (cond)
 464           && !is_gimple_val (TREE_OPERAND (cond, 0)))
 465         {
 466           tree temp = TREE_OPERAND (cond, 0);
 467           tree new_var_1 = make_rename_temp (TREE_TYPE (temp), NULL);
 468           new = build2 (MODIFY_EXPR, TREE_TYPE (new_var_1), new_var_1, temp);
 469           bsi_insert_after (&bsi, new, BSI_NEW_STMT);
 470           cond = fold_convert (TREE_TYPE (result), new_var_1);
 471         }
 472
 473       if (TREE_CODE (cond) == TRUTH_NOT_EXPR
 474           &&  !is_gimple_val (TREE_OPERAND (cond, 0)))
 475         {
 476           release_ssa_name (new_var1);
 477           return false;
 478         }
 479
 480       new = build2 (MODIFY_EXPR, TREE_TYPE (new_var1), new_var1, cond);
 481     }
 482
 483   bsi_insert_after (&bsi, new, BSI_NEW_STMT);
 484
 485   SSA_NAME_DEF_STMT (new_var1) = new;
 486
 487   replace_phi_edge_with_variable (cond_bb, phi_bb, e1, phi, new_var1);
 488
 489   /* Note that we optimized this PHI.  */
 490   return true;
 491 }
 492
 493 /*  The function value_replacement does the main work of doing the value
 494     replacement.  Return true if the replacement is done.  Otherwise return
 495     false.
 496     BB is the basic block where the replacement is going to be done on.  ARG0
 497     is argument 0 from the PHI.  Likewise for ARG1.  */
 498
 499 static bool
 500 value_replacement (basic_block cond_bb, basic_block middle_bb,
 501                    basic_block phi_bb, edge e0, edge e1, tree phi,
 502                    tree arg0, tree arg1)
 503 {
 504   tree cond;
 505   edge true_edge, false_edge;
 506
 507   /* If the type says honor signed zeros we cannot do this
 508      optimization.  */
 509   if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
 510     return false;
 511
 512   if (!empty_block_p (middle_bb))
 513     return false;
 514
 515   cond = COND_EXPR_COND (last_stmt (cond_bb));
 516
 517   /* This transformation is only valid for equality comparisons.  */
 518   if (TREE_CODE (cond) != NE_EXPR && TREE_CODE (cond) != EQ_EXPR)
 519     return false;
 520
 521   /* We need to know which is the true edge and which is the false
 522       edge so that we know if have abs or negative abs.  */
 523   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
 524
 525   /* At this point we know we have a COND_EXPR with two successors.
 526      One successor is BB, the other successor is an empty block which
 527      falls through into BB.
 528
 529      The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
 530
 531      There is a single PHI node at the join point (BB) with two arguments.
 532
 533      We now need to verify that the two arguments in the PHI node match
 534      the two arguments to the equality comparison.  */
 535
 536   if ((operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 0))
 537        && operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 1)))
 538       || (operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 0))
 539           && operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 1))))
 540     {
 541       edge e;
 542       tree arg;
 543
 544       /* For NE_EXPR, we want to build an assignment result = arg where
 545          arg is the PHI argument associated with the true edge.  For
 546          EQ_EXPR we want the PHI argument associated with the false edge.  */
 547       e = (TREE_CODE (cond) == NE_EXPR ? true_edge : false_edge);
 548
 549       /* Unfortunately, E may not reach BB (it may instead have gone to
 550          OTHER_BLOCK).  If that is the case, then we want the single outgoing
 551          edge from OTHER_BLOCK which reaches BB and represents the desired
 552          path from COND_BLOCK.  */
 553       if (e->dest == middle_bb)
 554         e = single_succ_edge (e->dest);
 555
 556       /* Now we know the incoming edge to BB that has the argument for the
 557          RHS of our new assignment statement.  */
 558       if (e0 == e)
 559         arg = arg0;
 560       else
 561         arg = arg1;
 562
 563       replace_phi_edge_with_variable (cond_bb, phi_bb, e1, phi, arg);
 564
 565       /* Note that we optimized this PHI.  */
 566       return true;
 567     }
 568   return false;
 569 }
 570
 571 /*  The function minmax_replacement does the main work of doing the minmax
 572     replacement.  Return true if the replacement is done.  Otherwise return
 573     false.
 574     BB is the basic block where the replacement is going to be done on.  ARG0
 575     is argument 0 from the PHI.  Likewise for ARG1.  */
 576
 577 static bool
 578 minmax_replacement (basic_block cond_bb, basic_block middle_bb,
 579                     basic_block phi_bb, edge e0, edge e1, tree phi,
 580                     tree arg0, tree arg1)
 581 {
 582   tree result, type;
 583   tree cond, new;
 584   edge true_edge, false_edge;
 585   enum tree_code cmp, minmax, ass_code;
 586   tree smaller, larger, arg_true, arg_false;
 587   block_stmt_iterator bsi, bsi_from;
 588
 589   type = TREE_TYPE (PHI_RESULT (phi));
 590
 591   /* The optimization may be unsafe due to NaNs.  */
 592   if (HONOR_NANS (TYPE_MODE (type)))
 593     return false;
 594
 595   cond = COND_EXPR_COND (last_stmt (cond_bb));
 596   cmp = TREE_CODE (cond);
 597   result = PHI_RESULT (phi);
 598
 599   /* This transformation is only valid for order comparisons.  Record which
 600      operand is smaller/larger if the result of the comparison is true.  */
 601   if (cmp == LT_EXPR || cmp == LE_EXPR)
 602     {
 603       smaller = TREE_OPERAND (cond, 0);
 604       larger = TREE_OPERAND (cond, 1);
 605     }
 606   else if (cmp == GT_EXPR || cmp == GE_EXPR)
 607     {
 608       smaller = TREE_OPERAND (cond, 1);
 609       larger = TREE_OPERAND (cond, 0);
 610     }
 611   else
 612     return false;
 613
 614   /* We need to know which is the true edge and which is the false
 615       edge so that we know if have abs or negative abs.  */
 616   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
 617
 618   /* Forward the edges over the middle basic block.  */
 619   if (true_edge->dest == middle_bb)
 620     true_edge = EDGE_SUCC (true_edge->dest, 0);
 621   if (false_edge->dest == middle_bb)
 622     false_edge = EDGE_SUCC (false_edge->dest, 0);
 623
 624   if (true_edge == e0)
 625     {
 626       gcc_assert (false_edge == e1);
 627       arg_true = arg0;
 628       arg_false = arg1;
 629     }
 630   else
 631     {
 632       gcc_assert (false_edge == e0);
 633       gcc_assert (true_edge == e1);
 634       arg_true = arg1;
 635       arg_false = arg0;
 636     }
 637
 638   if (empty_block_p (middle_bb))
 639     {
 640       if (operand_equal_for_phi_arg_p (arg_true, smaller)
 641           && operand_equal_for_phi_arg_p (arg_false, larger))
 642         {
 643           /* Case
 644
 645              if (smaller < larger)
 646              rslt = smaller;
 647              else
 648              rslt = larger;  */
 649           minmax = MIN_EXPR;
 650         }
 651       else if (operand_equal_for_phi_arg_p (arg_false, smaller)
 652                && operand_equal_for_phi_arg_p (arg_true, larger))
 653         minmax = MAX_EXPR;
 654       else
 655         return false;
 656     }
 657   else
 658     {
 659       /* Recognize the following case, assuming d <= u:
 660
 661          if (a <= u)
 662            b = MAX (a, d);
 663          x = PHI <b, u>
 664
 665          This is equivalent to
 666
 667          b = MAX (a, d);
 668          x = MIN (b, u);  */
 669
 670       tree assign = last_and_only_stmt (middle_bb);
 671       tree lhs, rhs, op0, op1, bound;
 672
 673       if (!assign
 674           || TREE_CODE (assign) != MODIFY_EXPR)
 675         return false;
 676
 677       lhs = TREE_OPERAND (assign, 0);
 678       rhs = TREE_OPERAND (assign, 1);
 679       ass_code = TREE_CODE (rhs);
 680       if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
 681         return false;
 682       op0 = TREE_OPERAND (rhs, 0);
 683       op1 = TREE_OPERAND (rhs, 1);
 684
 685       if (true_edge->src == middle_bb)
 686         {
 687           /* We got here if the condition is true, i.e., SMALLER < LARGER.  */
 688           if (!operand_equal_for_phi_arg_p (lhs, arg_true))
 689             return false;
 690
 691           if (operand_equal_for_phi_arg_p (arg_false, larger))
 692             {
 693               /* Case
 694
 695                  if (smaller < larger)
 696                    {
 697                      r' = MAX_EXPR (smaller, bound)
 698                    }
 699                  r = PHI <r', larger>  --> to be turned to MIN_EXPR.  */
 700               if (ass_code != MAX_EXPR)
 701                 return false;
 702
 703               minmax = MIN_EXPR;
 704               if (operand_equal_for_phi_arg_p (op0, smaller))
 705                 bound = op1;
 706               else if (operand_equal_for_phi_arg_p (op1, smaller))
 707                 bound = op0;
 708               else
 709                 return false;
 710
 711               /* We need BOUND <= LARGER.  */
 712               if (!integer_nonzerop (fold (build2 (LE_EXPR, boolean_type_node,
 713                                                    bound, larger))))
 714                 return false;
 715             }
 716           else if (operand_equal_for_phi_arg_p (arg_false, smaller))
 717             {
 718               /* Case
 719
 720                  if (smaller < larger)
 721                    {
 722                      r' = MIN_EXPR (larger, bound)
 723                    }
 724                  r = PHI <r', smaller>  --> to be turned to MAX_EXPR.  */
 725               if (ass_code != MIN_EXPR)
 726                 return false;
 727
 728               minmax = MAX_EXPR;
 729               if (operand_equal_for_phi_arg_p (op0, larger))
 730                 bound = op1;
 731               else if (operand_equal_for_phi_arg_p (op1, larger))
 732                 bound = op0;
 733               else
 734                 return false;
 735
 736               /* We need BOUND >= SMALLER.  */
 737               if (!integer_nonzerop (fold (build2 (GE_EXPR, boolean_type_node,
 738                                                    bound, smaller))))
 739                 return false;
 740             }
 741           else
 742             return false;
 743         }
 744       else
 745         {
 746           /* We got here if the condition is false, i.e., SMALLER > LARGER.  */
 747           if (!operand_equal_for_phi_arg_p (lhs, arg_false))
 748             return false;
 749
 750           if (operand_equal_for_phi_arg_p (arg_true, larger))
 751             {
 752               /* Case
 753
 754                  if (smaller > larger)
 755                    {
 756                      r' = MIN_EXPR (smaller, bound)
 757                    }
 758                  r = PHI <r', larger>  --> to be turned to MAX_EXPR.  */
 759               if (ass_code != MIN_EXPR)
 760                 return false;
 761
 762               minmax = MAX_EXPR;
 763               if (operand_equal_for_phi_arg_p (op0, smaller))
 764                 bound = op1;
 765               else if (operand_equal_for_phi_arg_p (op1, smaller))
 766                 bound = op0;
 767               else
 768                 return false;
 769
 770               /* We need BOUND >= LARGER.  */
 771               if (!integer_nonzerop (fold (build2 (GE_EXPR, boolean_type_node,
 772                                                    bound, larger))))
 773                 return false;
 774             }
 775           else if (operand_equal_for_phi_arg_p (arg_true, smaller))
 776             {
 777               /* Case
 778
 779                  if (smaller > larger)
 780                    {
 781                      r' = MAX_EXPR (larger, bound)
 782                    }
 783                  r = PHI <r', smaller>  --> to be turned to MIN_EXPR.  */
 784               if (ass_code != MAX_EXPR)
 785                 return false;
 786
 787               minmax = MIN_EXPR;
 788               if (operand_equal_for_phi_arg_p (op0, larger))
 789                 bound = op1;
 790               else if (operand_equal_for_phi_arg_p (op1, larger))
 791                 bound = op0;
 792               else
 793                 return false;
 794
 795               /* We need BOUND <= SMALLER.  */
 796               if (!integer_nonzerop (fold (build2 (LE_EXPR, boolean_type_node,
 797                                                    bound, smaller))))
 798                 return false;
 799             }
 800           else
 801             return false;
 802         }
 803
 804       /* Move the statement from the middle block.  */
 805       bsi = bsi_last (cond_bb);
 806       bsi_from = bsi_last (middle_bb);
 807       bsi_move_before (&bsi_from, &bsi);
 808     }
 809
 810   /* Emit the statement to compute min/max.  */
 811   result = duplicate_ssa_name (PHI_RESULT (phi), NULL);
 812   new = build2 (MODIFY_EXPR, type, result,
 813                 build2 (minmax, type, arg0, arg1));
 814   SSA_NAME_DEF_STMT (result) = new;
 815   bsi = bsi_last (cond_bb);
 816   bsi_insert_before (&bsi, new, BSI_NEW_STMT);
 817
 818   replace_phi_edge_with_variable (cond_bb, phi_bb, e1, phi, result);
 819   return true;
 820 }
 821
 822 /*  The function absolute_replacement does the main work of doing the absolute
 823     replacement.  Return true if the replacement is done.  Otherwise return
 824     false.
 825     bb is the basic block where the replacement is going to be done on.  arg0
 826     is argument 0 from the phi.  Likewise for arg1.  */
 827
 828 static bool
 829 abs_replacement (basic_block cond_bb, basic_block middle_bb,
 830                  basic_block phi_bb, edge e0 ATTRIBUTE_UNUSED, edge e1,
 831                  tree phi, tree arg0, tree arg1)
 832 {
 833   tree result;
 834   tree new, cond;
 835   block_stmt_iterator bsi;
 836   edge true_edge, false_edge;
 837   tree assign;
 838   edge e;
 839   tree rhs, lhs;
 840   bool negate;
 841   enum tree_code cond_code;
 842
 843   /* If the type says honor signed zeros we cannot do this
 844      optimization.  */
 845   if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
 846     return false;
 847
 848   /* OTHER_BLOCK must have only one executable statement which must have the
 849      form arg0 = -arg1 or arg1 = -arg0.  */
 850
 851   assign = last_and_only_stmt (middle_bb);
 852   /* If we did not find the proper negation assignment, then we can not
 853      optimize.  */
 854   if (assign == NULL)
 855     return false;
 856
 857   /* If we got here, then we have found the only executable statement
 858      in OTHER_BLOCK.  If it is anything other than arg = -arg1 or
 859      arg1 = -arg0, then we can not optimize.  */
 860   if (TREE_CODE (assign) != MODIFY_EXPR)
 861     return false;
 862
 863   lhs = TREE_OPERAND (assign, 0);
 864   rhs = TREE_OPERAND (assign, 1);
 865
 866   if (TREE_CODE (rhs) != NEGATE_EXPR)
 867     return false;
 868
 869   rhs = TREE_OPERAND (rhs, 0);
 870
 871   /* The assignment has to be arg0 = -arg1 or arg1 = -arg0.  */
 872   if (!(lhs == arg0 && rhs == arg1)
 873       && !(lhs == arg1 && rhs == arg0))
 874     return false;
 875
 876   cond = COND_EXPR_COND (last_stmt (cond_bb));
 877   result = PHI_RESULT (phi);
 878
 879   /* Only relationals comparing arg[01] against zero are interesting.  */
 880   cond_code = TREE_CODE (cond);
 881   if (cond_code != GT_EXPR && cond_code != GE_EXPR
 882       && cond_code != LT_EXPR && cond_code != LE_EXPR)
 883     return false;
 884
 885   /* Make sure the conditional is arg[01] OP y.  */
 886   if (TREE_OPERAND (cond, 0) != rhs)
 887     return false;
 888
 889   if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))
 890                ? real_zerop (TREE_OPERAND (cond, 1))
 891                : integer_zerop (TREE_OPERAND (cond, 1)))
 892     ;
 893   else
 894     return false;
 895
 896   /* We need to know which is the true edge and which is the false
 897      edge so that we know if have abs or negative abs.  */
 898   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
 899
 900   /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
 901      will need to negate the result.  Similarly for LT_EXPR/LE_EXPR if
 902      the false edge goes to OTHER_BLOCK.  */
 903   if (cond_code == GT_EXPR || cond_code == GE_EXPR)
 904     e = true_edge;
 905   else
 906     e = false_edge;
 907
 908   if (e->dest == middle_bb)
 909     negate = true;
 910   else
 911     negate = false;
 912
 913   result = duplicate_ssa_name (result, NULL);
 914
 915   if (negate)
 916     lhs = make_rename_temp (TREE_TYPE (result), NULL);
 917   else
 918     lhs = result;
 919
 920   /* Build the modify expression with abs expression.  */
 921   new = build2 (MODIFY_EXPR, TREE_TYPE (lhs),
 922                 lhs, build1 (ABS_EXPR, TREE_TYPE (lhs), rhs));
 923
 924   bsi = bsi_last (cond_bb);
 925   bsi_insert_before (&bsi, new, BSI_NEW_STMT);
 926
 927   if (negate)
 928     {
 929       /* Get the right BSI.  We want to insert after the recently
 930          added ABS_EXPR statement (which we know is the first statement
 931          in the block.  */
 932       new = build2 (MODIFY_EXPR, TREE_TYPE (result),
 933                     result, build1 (NEGATE_EXPR, TREE_TYPE (lhs), lhs));
 934
 935       bsi_insert_after (&bsi, new, BSI_NEW_STMT);
 936     }
 937
 938   SSA_NAME_DEF_STMT (result) = new;
 939   replace_phi_edge_with_variable (cond_bb, phi_bb, e1, phi, result);
 940
 941   /* Note that we optimized this PHI.  */
 942   return true;
 943 }
 944
 945
 946 /* Always do these optimizations if we have SSA
 947    trees to work on.  */
 948 static bool
 949 gate_phiopt (void)
 950 {
 951   return 1;
 952 }
 953
 954 struct tree_opt_pass pass_phiopt =
 955 {
 956   "phiopt",                             /* name */
 957   gate_phiopt,                          /* gate */
 958   tree_ssa_phiopt,                      /* execute */
 959   NULL,                                 /* sub */
 960   NULL,                                 /* next */
 961   0,                                    /* static_pass_number */
 962   TV_TREE_PHIOPT,                       /* tv_id */
 963   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 964   0,                                    /* properties_provided */
 965   0,                                    /* properties_destroyed */
 966   0,                                    /* todo_flags_start */
 967   TODO_cleanup_cfg | TODO_dump_func | TODO_ggc_collect  /* todo_flags_finish */
 968     | TODO_verify_ssa | TODO_rename_vars
 969     | TODO_verify_flow | TODO_verify_stmts,
 970   0                                     /* letter */
 971 };