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