gcc/tree-ssa-phiopt.c

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