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