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, 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301, 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       EDGE_SUCC (cond_block, 0)->probability = REG_BR_PROB_BASE;
 335       EDGE_SUCC (cond_block, 0)->count += EDGE_SUCC (cond_block, 1)->count;
 336
 337       block_to_remove = EDGE_SUCC (cond_block, 1)->dest;
 338     }
 339   else
 340     {
 341       EDGE_SUCC (cond_block, 1)->flags |= EDGE_FALLTHRU;
 342       EDGE_SUCC (cond_block, 1)->flags
 343         &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 344       EDGE_SUCC (cond_block, 1)->probability = REG_BR_PROB_BASE;
 345       EDGE_SUCC (cond_block, 1)->count += EDGE_SUCC (cond_block, 0)->count;
 346
 347       block_to_remove = EDGE_SUCC (cond_block, 0)->dest;
 348     }
 349   delete_basic_block (block_to_remove);
 350
 351   /* Eliminate the COND_EXPR at the end of COND_BLOCK.  */
 352   bsi = bsi_last (cond_block);
 353   bsi_remove (&bsi);
 354
 355   if (dump_file && (dump_flags & TDF_DETAILS))
 356     fprintf (dump_file,
 357               "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
 358               cond_block->index,
 359               bb->index);
 360 }
 361
 362 /*  The function conditional_replacement does the main work of doing the
 363     conditional replacement.  Return true if the replacement is done.
 364     Otherwise return false.
 365     BB is the basic block where the replacement is going to be done on.  ARG0
 366     is argument 0 from PHI.  Likewise for ARG1.  */
 367
 368 static bool
 369 conditional_replacement (basic_block cond_bb, basic_block middle_bb,
 370                          edge e0, edge e1, tree phi,
 371                          tree arg0, tree arg1)
 372 {
 373   tree result;
 374   tree old_result = NULL;
 375   tree new, cond;
 376   block_stmt_iterator bsi;
 377   edge true_edge, false_edge;
 378   tree new_var = NULL;
 379   tree new_var1;
 380
 381   /* The PHI arguments have the constants 0 and 1, then convert
 382      it to the conditional.  */
 383   if ((integer_zerop (arg0) && integer_onep (arg1))
 384       || (integer_zerop (arg1) && integer_onep (arg0)))
 385     ;
 386   else
 387     return false;
 388
 389   if (!empty_block_p (middle_bb))
 390     return false;
 391
 392   /* If the condition is not a naked SSA_NAME and its type does not
 393      match the type of the result, then we have to create a new
 394      variable to optimize this case as it would likely create
 395      non-gimple code when the condition was converted to the
 396      result's type.  */
 397   cond = COND_EXPR_COND (last_stmt (cond_bb));
 398   result = PHI_RESULT (phi);
 399   if (TREE_CODE (cond) != SSA_NAME
 400       && !lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
 401     {
 402       new_var = make_rename_temp (TREE_TYPE (cond), NULL);
 403       old_result = cond;
 404       cond = new_var;
 405     }
 406
 407   /* If the condition was a naked SSA_NAME and the type is not the
 408      same as the type of the result, then convert the type of the
 409      condition.  */
 410   if (!lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
 411     cond = fold_convert (TREE_TYPE (result), cond);
 412
 413   /* We need to know which is the true edge and which is the false
 414      edge so that we know when to invert the condition below.  */
 415   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
 416
 417   /* Insert our new statement at the end of conditional block before the
 418      COND_EXPR.  */
 419   bsi = bsi_last (cond_bb);
 420   bsi_insert_before (&bsi, build_empty_stmt (), BSI_NEW_STMT);
 421
 422   if (old_result)
 423     {
 424       tree new1;
 425       if (!COMPARISON_CLASS_P (old_result))
 426         return false;
 427
 428       new1 = build2 (TREE_CODE (old_result), TREE_TYPE (old_result),
 429                      TREE_OPERAND (old_result, 0),
 430                      TREE_OPERAND (old_result, 1));
 431
 432       new1 = build2 (MODIFY_EXPR, TREE_TYPE (old_result), new_var, new1);
 433       bsi_insert_after (&bsi, new1, BSI_NEW_STMT);
 434     }
 435
 436   new_var1 = duplicate_ssa_name (PHI_RESULT (phi), NULL);
 437
 438
 439   /* At this point we know we have a COND_EXPR with two successors.
 440      One successor is BB, the other successor is an empty block which
 441      falls through into BB.
 442
 443      There is a single PHI node at the join point (BB) and its arguments
 444      are constants (0, 1).
 445
 446      So, given the condition COND, and the two PHI arguments, we can
 447      rewrite this PHI into non-branching code:
 448
 449        dest = (COND) or dest = COND'
 450
 451      We use the condition as-is if the argument associated with the
 452      true edge has the value one or the argument associated with the
 453      false edge as the value zero.  Note that those conditions are not
 454      the same since only one of the outgoing edges from the COND_EXPR
 455      will directly reach BB and thus be associated with an argument.  */
 456   if ((e0 == true_edge && integer_onep (arg0))
 457       || (e0 == false_edge && integer_zerop (arg0))
 458       || (e1 == true_edge && integer_onep (arg1))
 459       || (e1 == false_edge && integer_zerop (arg1)))
 460     {
 461       new = build2 (MODIFY_EXPR, TREE_TYPE (new_var1), new_var1, cond);
 462     }
 463   else
 464     {
 465       tree cond1 = invert_truthvalue (cond);
 466
 467       cond = cond1;
 468       /* If what we get back is a conditional expression, there is no
 469           way that it can be gimple.  */
 470       if (TREE_CODE (cond) == COND_EXPR)
 471         {
 472           release_ssa_name (new_var1);
 473           return false;
 474         }
 475
 476       /* If what we get back is not gimple try to create it as gimple by
 477          using a temporary variable.  */
 478       if (is_gimple_cast (cond)
 479           && !is_gimple_val (TREE_OPERAND (cond, 0)))
 480         {
 481           tree temp = TREE_OPERAND (cond, 0);
 482           tree new_var_1 = make_rename_temp (TREE_TYPE (temp), NULL);
 483           new = build2 (MODIFY_EXPR, TREE_TYPE (new_var_1), new_var_1, temp);
 484           bsi_insert_after (&bsi, new, BSI_NEW_STMT);
 485           cond = fold_convert (TREE_TYPE (result), new_var_1);
 486         }
 487
 488       if (TREE_CODE (cond) == TRUTH_NOT_EXPR
 489           &&  !is_gimple_val (TREE_OPERAND (cond, 0)))
 490         {
 491           release_ssa_name (new_var1);
 492           return false;
 493         }
 494
 495       new = build2 (MODIFY_EXPR, TREE_TYPE (new_var1), new_var1, cond);
 496     }
 497
 498   bsi_insert_after (&bsi, new, BSI_NEW_STMT);
 499
 500   SSA_NAME_DEF_STMT (new_var1) = new;
 501
 502   replace_phi_edge_with_variable (cond_bb, e1, phi, new_var1);
 503
 504   /* Note that we optimized this PHI.  */
 505   return true;
 506 }
 507
 508 /*  The function value_replacement does the main work of doing the value
 509     replacement.  Return true if the replacement is done.  Otherwise return
 510     false.
 511     BB is the basic block where the replacement is going to be done on.  ARG0
 512     is argument 0 from the PHI.  Likewise for ARG1.  */
 513
 514 static bool
 515 value_replacement (basic_block cond_bb, basic_block middle_bb,
 516                    edge e0, edge e1, tree phi,
 517                    tree arg0, tree arg1)
 518 {
 519   tree cond;
 520   edge true_edge, false_edge;
 521
 522   /* If the type says honor signed zeros we cannot do this
 523      optimization.  */
 524   if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
 525     return false;
 526
 527   if (!empty_block_p (middle_bb))
 528     return false;
 529
 530   cond = COND_EXPR_COND (last_stmt (cond_bb));
 531
 532   /* This transformation is only valid for equality comparisons.  */
 533   if (TREE_CODE (cond) != NE_EXPR && TREE_CODE (cond) != EQ_EXPR)
 534     return false;
 535
 536   /* We need to know which is the true edge and which is the false
 537       edge so that we know if have abs or negative abs.  */
 538   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
 539
 540   /* At this point we know we have a COND_EXPR with two successors.
 541      One successor is BB, the other successor is an empty block which
 542      falls through into BB.
 543
 544      The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
 545
 546      There is a single PHI node at the join point (BB) with two arguments.
 547
 548      We now need to verify that the two arguments in the PHI node match
 549      the two arguments to the equality comparison.  */
 550
 551   if ((operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 0))
 552        && operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 1)))
 553       || (operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 0))
 554           && operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 1))))
 555     {
 556       edge e;
 557       tree arg;
 558
 559       /* For NE_EXPR, we want to build an assignment result = arg where
 560          arg is the PHI argument associated with the true edge.  For
 561          EQ_EXPR we want the PHI argument associated with the false edge.  */
 562       e = (TREE_CODE (cond) == NE_EXPR ? true_edge : false_edge);
 563
 564       /* Unfortunately, E may not reach BB (it may instead have gone to
 565          OTHER_BLOCK).  If that is the case, then we want the single outgoing
 566          edge from OTHER_BLOCK which reaches BB and represents the desired
 567          path from COND_BLOCK.  */
 568       if (e->dest == middle_bb)
 569         e = single_succ_edge (e->dest);
 570
 571       /* Now we know the incoming edge to BB that has the argument for the
 572          RHS of our new assignment statement.  */
 573       if (e0 == e)
 574         arg = arg0;
 575       else
 576         arg = arg1;
 577
 578       replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
 579
 580       /* Note that we optimized this PHI.  */
 581       return true;
 582     }
 583   return false;
 584 }
 585
 586 /*  The function minmax_replacement does the main work of doing the minmax
 587     replacement.  Return true if the replacement is done.  Otherwise return
 588     false.
 589     BB is the basic block where the replacement is going to be done on.  ARG0
 590     is argument 0 from the PHI.  Likewise for ARG1.  */
 591
 592 static bool
 593 minmax_replacement (basic_block cond_bb, basic_block middle_bb,
 594                     edge e0, edge e1, tree phi,
 595                     tree arg0, tree arg1)
 596 {
 597   tree result, type;
 598   tree cond, new;
 599   edge true_edge, false_edge;
 600   enum tree_code cmp, minmax, ass_code;
 601   tree smaller, larger, arg_true, arg_false;
 602   block_stmt_iterator bsi, bsi_from;
 603
 604   type = TREE_TYPE (PHI_RESULT (phi));
 605
 606   /* The optimization may be unsafe due to NaNs.  */
 607   if (HONOR_NANS (TYPE_MODE (type)))
 608     return false;
 609
 610   cond = COND_EXPR_COND (last_stmt (cond_bb));
 611   cmp = TREE_CODE (cond);
 612   result = PHI_RESULT (phi);
 613
 614   /* This transformation is only valid for order comparisons.  Record which
 615      operand is smaller/larger if the result of the comparison is true.  */
 616   if (cmp == LT_EXPR || cmp == LE_EXPR)
 617     {
 618       smaller = TREE_OPERAND (cond, 0);
 619       larger = TREE_OPERAND (cond, 1);
 620     }
 621   else if (cmp == GT_EXPR || cmp == GE_EXPR)
 622     {
 623       smaller = TREE_OPERAND (cond, 1);
 624       larger = TREE_OPERAND (cond, 0);
 625     }
 626   else
 627     return false;
 628
 629   /* We need to know which is the true edge and which is the false
 630       edge so that we know if have abs or negative abs.  */
 631   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
 632
 633   /* Forward the edges over the middle basic block.  */
 634   if (true_edge->dest == middle_bb)
 635     true_edge = EDGE_SUCC (true_edge->dest, 0);
 636   if (false_edge->dest == middle_bb)
 637     false_edge = EDGE_SUCC (false_edge->dest, 0);
 638
 639   if (true_edge == e0)
 640     {
 641       gcc_assert (false_edge == e1);
 642       arg_true = arg0;
 643       arg_false = arg1;
 644     }
 645   else
 646     {
 647       gcc_assert (false_edge == e0);
 648       gcc_assert (true_edge == e1);
 649       arg_true = arg1;
 650       arg_false = arg0;
 651     }
 652
 653   if (empty_block_p (middle_bb))
 654     {
 655       if (operand_equal_for_phi_arg_p (arg_true, smaller)
 656           && operand_equal_for_phi_arg_p (arg_false, larger))
 657         {
 658           /* Case
 659
 660              if (smaller < larger)
 661              rslt = smaller;
 662              else
 663              rslt = larger;  */
 664           minmax = MIN_EXPR;
 665         }
 666       else if (operand_equal_for_phi_arg_p (arg_false, smaller)
 667                && operand_equal_for_phi_arg_p (arg_true, larger))
 668         minmax = MAX_EXPR;
 669       else
 670         return false;
 671     }
 672   else
 673     {
 674       /* Recognize the following case, assuming d <= u:
 675
 676          if (a <= u)
 677            b = MAX (a, d);
 678          x = PHI <b, u>
 679
 680          This is equivalent to
 681
 682          b = MAX (a, d);
 683          x = MIN (b, u);  */
 684
 685       tree assign = last_and_only_stmt (middle_bb);
 686       tree lhs, rhs, op0, op1, bound;
 687
 688       if (!assign
 689           || TREE_CODE (assign) != MODIFY_EXPR)
 690         return false;
 691
 692       lhs = TREE_OPERAND (assign, 0);
 693       rhs = TREE_OPERAND (assign, 1);
 694       ass_code = TREE_CODE (rhs);
 695       if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
 696         return false;
 697       op0 = TREE_OPERAND (rhs, 0);
 698       op1 = TREE_OPERAND (rhs, 1);
 699
 700       if (true_edge->src == middle_bb)
 701         {
 702           /* We got here if the condition is true, i.e., SMALLER < LARGER.  */
 703           if (!operand_equal_for_phi_arg_p (lhs, arg_true))
 704             return false;
 705
 706           if (operand_equal_for_phi_arg_p (arg_false, larger))
 707             {
 708               /* Case
 709
 710                  if (smaller < larger)
 711                    {
 712                      r' = MAX_EXPR (smaller, bound)
 713                    }
 714                  r = PHI <r', larger>  --> to be turned to MIN_EXPR.  */
 715               if (ass_code != MAX_EXPR)
 716                 return false;
 717
 718               minmax = MIN_EXPR;
 719               if (operand_equal_for_phi_arg_p (op0, smaller))
 720                 bound = op1;
 721               else if (operand_equal_for_phi_arg_p (op1, smaller))
 722                 bound = op0;
 723               else
 724                 return false;
 725
 726               /* We need BOUND <= LARGER.  */
 727               if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
 728                                                   bound, larger)))
 729                 return false;
 730             }
 731           else if (operand_equal_for_phi_arg_p (arg_false, smaller))
 732             {
 733               /* Case
 734
 735                  if (smaller < larger)
 736                    {
 737                      r' = MIN_EXPR (larger, bound)
 738                    }
 739                  r = PHI <r', smaller>  --> to be turned to MAX_EXPR.  */
 740               if (ass_code != MIN_EXPR)
 741                 return false;
 742
 743               minmax = MAX_EXPR;
 744               if (operand_equal_for_phi_arg_p (op0, larger))
 745                 bound = op1;
 746               else if (operand_equal_for_phi_arg_p (op1, larger))
 747                 bound = op0;
 748               else
 749                 return false;
 750
 751               /* We need BOUND >= SMALLER.  */
 752               if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
 753                                                   bound, smaller)))
 754                 return false;
 755             }
 756           else
 757             return false;
 758         }
 759       else
 760         {
 761           /* We got here if the condition is false, i.e., SMALLER > LARGER.  */
 762           if (!operand_equal_for_phi_arg_p (lhs, arg_false))
 763             return false;
 764
 765           if (operand_equal_for_phi_arg_p (arg_true, larger))
 766             {
 767               /* Case
 768
 769                  if (smaller > larger)
 770                    {
 771                      r' = MIN_EXPR (smaller, bound)
 772                    }
 773                  r = PHI <r', larger>  --> to be turned to MAX_EXPR.  */
 774               if (ass_code != MIN_EXPR)
 775                 return false;
 776
 777               minmax = MAX_EXPR;
 778               if (operand_equal_for_phi_arg_p (op0, smaller))
 779                 bound = op1;
 780               else if (operand_equal_for_phi_arg_p (op1, smaller))
 781                 bound = op0;
 782               else
 783                 return false;
 784
 785               /* We need BOUND >= LARGER.  */
 786               if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
 787                                                   bound, larger)))
 788                 return false;
 789             }
 790           else if (operand_equal_for_phi_arg_p (arg_true, smaller))
 791             {
 792               /* Case
 793
 794                  if (smaller > larger)
 795                    {
 796                      r' = MAX_EXPR (larger, bound)
 797                    }
 798                  r = PHI <r', smaller>  --> to be turned to MIN_EXPR.  */
 799               if (ass_code != MAX_EXPR)
 800                 return false;
 801
 802               minmax = MIN_EXPR;
 803               if (operand_equal_for_phi_arg_p (op0, larger))
 804                 bound = op1;
 805               else if (operand_equal_for_phi_arg_p (op1, larger))
 806                 bound = op0;
 807               else
 808                 return false;
 809
 810               /* We need BOUND <= SMALLER.  */
 811               if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
 812                                                   bound, smaller)))
 813                 return false;
 814             }
 815           else
 816             return false;
 817         }
 818
 819       /* Move the statement from the middle block.  */
 820       bsi = bsi_last (cond_bb);
 821       bsi_from = bsi_last (middle_bb);
 822       bsi_move_before (&bsi_from, &bsi);
 823     }
 824
 825   /* Emit the statement to compute min/max.  */
 826   result = duplicate_ssa_name (PHI_RESULT (phi), NULL);
 827   new = build2 (MODIFY_EXPR, type, result,
 828                 build2 (minmax, type, arg0, arg1));
 829   SSA_NAME_DEF_STMT (result) = new;
 830   bsi = bsi_last (cond_bb);
 831   bsi_insert_before (&bsi, new, BSI_NEW_STMT);
 832
 833   replace_phi_edge_with_variable (cond_bb, e1, phi, result);
 834   return true;
 835 }
 836
 837 /*  The function absolute_replacement does the main work of doing the absolute
 838     replacement.  Return true if the replacement is done.  Otherwise return
 839     false.
 840     bb is the basic block where the replacement is going to be done on.  arg0
 841     is argument 0 from the phi.  Likewise for arg1.  */
 842
 843 static bool
 844 abs_replacement (basic_block cond_bb, basic_block middle_bb,
 845                  edge e0 ATTRIBUTE_UNUSED, edge e1,
 846                  tree phi, tree arg0, tree arg1)
 847 {
 848   tree result;
 849   tree new, cond;
 850   block_stmt_iterator bsi;
 851   edge true_edge, false_edge;
 852   tree assign;
 853   edge e;
 854   tree rhs, lhs;
 855   bool negate;
 856   enum tree_code cond_code;
 857
 858   /* If the type says honor signed zeros we cannot do this
 859      optimization.  */
 860   if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
 861     return false;
 862
 863   /* OTHER_BLOCK must have only one executable statement which must have the
 864      form arg0 = -arg1 or arg1 = -arg0.  */
 865
 866   assign = last_and_only_stmt (middle_bb);
 867   /* If we did not find the proper negation assignment, then we can not
 868      optimize.  */
 869   if (assign == NULL)
 870     return false;
 871
 872   /* If we got here, then we have found the only executable statement
 873      in OTHER_BLOCK.  If it is anything other than arg = -arg1 or
 874      arg1 = -arg0, then we can not optimize.  */
 875   if (TREE_CODE (assign) != MODIFY_EXPR)
 876     return false;
 877
 878   lhs = TREE_OPERAND (assign, 0);
 879   rhs = TREE_OPERAND (assign, 1);
 880
 881   if (TREE_CODE (rhs) != NEGATE_EXPR)
 882     return false;
 883
 884   rhs = TREE_OPERAND (rhs, 0);
 885
 886   /* The assignment has to be arg0 = -arg1 or arg1 = -arg0.  */
 887   if (!(lhs == arg0 && rhs == arg1)
 888       && !(lhs == arg1 && rhs == arg0))
 889     return false;
 890
 891   cond = COND_EXPR_COND (last_stmt (cond_bb));
 892   result = PHI_RESULT (phi);
 893
 894   /* Only relationals comparing arg[01] against zero are interesting.  */
 895   cond_code = TREE_CODE (cond);
 896   if (cond_code != GT_EXPR && cond_code != GE_EXPR
 897       && cond_code != LT_EXPR && cond_code != LE_EXPR)
 898     return false;
 899
 900   /* Make sure the conditional is arg[01] OP y.  */
 901   if (TREE_OPERAND (cond, 0) != rhs)
 902     return false;
 903
 904   if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))
 905                ? real_zerop (TREE_OPERAND (cond, 1))
 906                : integer_zerop (TREE_OPERAND (cond, 1)))
 907     ;
 908   else
 909     return false;
 910
 911   /* We need to know which is the true edge and which is the false
 912      edge so that we know if have abs or negative abs.  */
 913   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
 914
 915   /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
 916      will need to negate the result.  Similarly for LT_EXPR/LE_EXPR if
 917      the false edge goes to OTHER_BLOCK.  */
 918   if (cond_code == GT_EXPR || cond_code == GE_EXPR)
 919     e = true_edge;
 920   else
 921     e = false_edge;
 922
 923   if (e->dest == middle_bb)
 924     negate = true;
 925   else
 926     negate = false;
 927
 928   result = duplicate_ssa_name (result, NULL);
 929
 930   if (negate)
 931     lhs = make_rename_temp (TREE_TYPE (result), NULL);
 932   else
 933     lhs = result;
 934
 935   /* Build the modify expression with abs expression.  */
 936   new = build2 (MODIFY_EXPR, TREE_TYPE (lhs),
 937                 lhs, build1 (ABS_EXPR, TREE_TYPE (lhs), rhs));
 938
 939   bsi = bsi_last (cond_bb);
 940   bsi_insert_before (&bsi, new, BSI_NEW_STMT);
 941
 942   if (negate)
 943     {
 944       /* Get the right BSI.  We want to insert after the recently
 945          added ABS_EXPR statement (which we know is the first statement
 946          in the block.  */
 947       new = build2 (MODIFY_EXPR, TREE_TYPE (result),
 948                     result, build1 (NEGATE_EXPR, TREE_TYPE (lhs), lhs));
 949
 950       bsi_insert_after (&bsi, new, BSI_NEW_STMT);
 951     }
 952
 953   SSA_NAME_DEF_STMT (result) = new;
 954   replace_phi_edge_with_variable (cond_bb, e1, phi, result);
 955
 956   /* Note that we optimized this PHI.  */
 957   return true;
 958 }
 959
 960
 961 /* Always do these optimizations if we have SSA
 962    trees to work on.  */
 963 static bool
 964 gate_phiopt (void)
 965 {
 966   return 1;
 967 }
 968
 969 struct tree_opt_pass pass_phiopt =
 970 {
 971   "phiopt",                             /* name */
 972   gate_phiopt,                          /* gate */
 973   tree_ssa_phiopt,                      /* execute */
 974   NULL,                                 /* sub */
 975   NULL,                                 /* next */
 976   0,                                    /* static_pass_number */
 977   TV_TREE_PHIOPT,                       /* tv_id */
 978   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 979   0,                                    /* properties_provided */
 980   0,                                    /* properties_destroyed */
 981   0,                                    /* todo_flags_start */
 982   TODO_cleanup_cfg
 983     | TODO_dump_func
 984     | TODO_ggc_collect
 985     | TODO_verify_ssa
 986     | TODO_update_ssa
 987     | TODO_verify_flow
 988     | TODO_verify_stmts,                /* todo_flags_finish */
 989   0                                     /* letter */
 990 };