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