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