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