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