gcc/tree-ssa-phiopt.c

   1 /* Optimization of PHI nodes by converting them into straightline code.
   2    Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 3, 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 COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "tm.h"
  24 #include "ggc.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "flags.h"
  28 #include "tm_p.h"
  29 #include "basic-block.h"
  30 #include "timevar.h"
  31 #include "diagnostic.h"
  32 #include "tree-flow.h"
  33 #include "tree-pass.h"
  34 #include "tree-dump.h"
  35 #include "langhooks.h"
  36
  37 static unsigned int tree_ssa_phiopt (void);
  38 static bool conditional_replacement (basic_block, basic_block,
  39                                      edge, edge, tree, tree, tree);
  40 static bool value_replacement (basic_block, basic_block,
  41                                edge, edge, tree, tree, tree);
  42 static bool minmax_replacement (basic_block, basic_block,
  43                                 edge, edge, tree, tree, tree);
  44 static bool abs_replacement (basic_block, basic_block,
  45                              edge, edge, tree, tree, tree);
  46 static void replace_phi_edge_with_variable (basic_block, edge, tree, tree);
  47
  48 /* This pass tries to replaces an if-then-else block with an
  49    assignment.  We have four kinds of transformations.  Some of these
  50    transformations are also performed by the ifcvt RTL optimizer.
  51
  52    Conditional Replacement
  53    -----------------------
  54
  55    This transformation, implemented in conditional_replacement,
  56    replaces
  57
  58      bb0:
  59       if (cond) goto bb2; else goto bb1;
  60      bb1:
  61      bb2:
  62       x = PHI <0 (bb1), 1 (bb0), ...>;
  63
  64    with
  65
  66      bb0:
  67       x' = cond;
  68       goto bb2;
  69      bb2:
  70       x = PHI <x' (bb0), ...>;
  71
  72    We remove bb1 as it becomes unreachable.  This occurs often due to
  73    gimplification of conditionals.
  74
  75    Value Replacement
  76    -----------------
  77
  78    This transformation, implemented in value_replacement, replaces
  79
  80      bb0:
  81        if (a != b) goto bb2; else goto bb1;
  82      bb1:
  83      bb2:
  84        x = PHI <a (bb1), b (bb0), ...>;
  85
  86    with
  87
  88      bb0:
  89      bb2:
  90        x = PHI <b (bb0), ...>;
  91
  92    This opportunity can sometimes occur as a result of other
  93    optimizations.
  94
  95    ABS Replacement
  96    ---------------
  97
  98    This transformation, implemented in abs_replacement, replaces
  99
 100      bb0:
 101        if (a >= 0) goto bb2; else goto bb1;
 102      bb1:
 103        x = -a;
 104      bb2:
 105        x = PHI <x (bb1), a (bb0), ...>;
 106
 107    with
 108
 109      bb0:
 110        x' = ABS_EXPR< a >;
 111      bb2:
 112        x = PHI <x' (bb0), ...>;
 113
 114    MIN/MAX Replacement
 115    -------------------
 116
 117    This transformation, minmax_replacement replaces
 118
 119      bb0:
 120        if (a <= b) goto bb2; else goto bb1;
 121      bb1:
 122      bb2:
 123        x = PHI <b (bb1), a (bb0), ...>;
 124
 125    with
 126
 127      bb0:
 128        x' = MIN_EXPR (a, b)
 129      bb2:
 130        x = PHI <x' (bb0), ...>;
 131
 132    A similar transformation is done for MAX_EXPR.  */
 133
 134 static unsigned int
 135 tree_ssa_phiopt (void)
 136 {
 137   basic_block bb;
 138   basic_block *bb_order;
 139   unsigned n, i;
 140   bool cfgchanged = false;
 141
 142   /* Search every basic block for COND_EXPR we may be able to optimize.
 143
 144      We walk the blocks in order that guarantees that a block with
 145      a single predecessor is processed before the predecessor.
 146      This ensures that we collapse inner ifs before visiting the
 147      outer ones, and also that we do not try to visit a removed
 148      block.  */
 149   bb_order = blocks_in_phiopt_order ();
 150   n = n_basic_blocks - NUM_FIXED_BLOCKS;
 151
 152   for (i = 0; i < n; i++)
 153     {
 154       tree cond_expr;
 155       tree phi;
 156       basic_block bb1, bb2;
 157       edge e1, e2;
 158       tree arg0, arg1;
 159
 160       bb = bb_order[i];
 161
 162       cond_expr = last_stmt (bb);
 163       /* Check to see if the last statement is a COND_EXPR.  */
 164       if (!cond_expr
 165           || TREE_CODE (cond_expr) != COND_EXPR)
 166         continue;
 167
 168       e1 = EDGE_SUCC (bb, 0);
 169       bb1 = e1->dest;
 170       e2 = EDGE_SUCC (bb, 1);
 171       bb2 = e2->dest;
 172
 173       /* We cannot do the optimization on abnormal edges.  */
 174       if ((e1->flags & EDGE_ABNORMAL) != 0
 175           || (e2->flags & EDGE_ABNORMAL) != 0)
 176        continue;
 177
 178       /* If either bb1's succ or bb2 or bb2's succ is non NULL.  */
 179       if (EDGE_COUNT (bb1->succs) == 0
 180           || bb2 == NULL
 181           || EDGE_COUNT (bb2->succs) == 0)
 182         continue;
 183
 184       /* Find the bb which is the fall through to the other.  */
 185       if (EDGE_SUCC (bb1, 0)->dest == bb2)
 186         ;
 187       else if (EDGE_SUCC (bb2, 0)->dest == bb1)
 188         {
 189           basic_block bb_tmp = bb1;
 190           edge e_tmp = e1;
 191           bb1 = bb2;
 192           bb2 = bb_tmp;
 193           e1 = e2;
 194           e2 = e_tmp;
 195         }
 196       else
 197         continue;
 198
 199       e1 = EDGE_SUCC (bb1, 0);
 200
 201       /* Make sure that bb1 is just a fall through.  */
 202       if (!single_succ_p (bb1)
 203           || (e1->flags & EDGE_FALLTHRU) == 0)
 204         continue;
 205
 206       /* Also make sure that bb1 only have one predecessor and that it
 207          is bb.  */
 208       if (!single_pred_p (bb1)
 209           || single_pred (bb1) != bb)
 210         continue;
 211
 212       phi = phi_nodes (bb2);
 213
 214       /* Check to make sure that there is only one PHI node.
 215          TODO: we could do it with more than one iff the other PHI nodes
 216          have the same elements for these two edges.  */
 217       if (!phi || PHI_CHAIN (phi) != NULL)
 218         continue;
 219
 220       arg0 = PHI_ARG_DEF_TREE (phi, e1->dest_idx);
 221       arg1 = PHI_ARG_DEF_TREE (phi, e2->dest_idx);
 222
 223       /* Something is wrong if we cannot find the arguments in the PHI
 224          node.  */
 225       gcc_assert (arg0 != NULL && arg1 != NULL);
 226
 227       /* Do the replacement of conditional if it can be done.  */
 228       if (conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
 229         cfgchanged = true;
 230       else if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
 231         cfgchanged = true;
 232       else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
 233         cfgchanged = true;
 234       else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
 235         cfgchanged = true;
 236     }
 237
 238   free (bb_order);
 239
 240   /* If the CFG has changed, we should cleanup the CFG. */
 241   return cfgchanged ? TODO_cleanup_cfg : 0;
 242 }
 243
 244 /* Returns the list of basic blocks in the function in an order that guarantees
 245    that if a block X has just a single predecessor Y, then Y is after X in the
 246    ordering.  */
 247
 248 basic_block *
 249 blocks_in_phiopt_order (void)
 250 {
 251   basic_block x, y;
 252   basic_block *order = XNEWVEC (basic_block, n_basic_blocks);
 253   unsigned n = n_basic_blocks - NUM_FIXED_BLOCKS;
 254   unsigned np, i;
 255   sbitmap visited = sbitmap_alloc (last_basic_block);
 256
 257 #define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
 258 #define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
 259
 260   sbitmap_zero (visited);
 261
 262   MARK_VISITED (ENTRY_BLOCK_PTR);
 263   FOR_EACH_BB (x)
 264     {
 265       if (VISITED_P (x))
 266         continue;
 267
 268       /* Walk the predecessors of x as long as they have precisely one
 269          predecessor and add them to the list, so that they get stored
 270          after x.  */
 271       for (y = x, np = 1;
 272            single_pred_p (y) && !VISITED_P (single_pred (y));
 273            y = single_pred (y))
 274         np++;
 275       for (y = x, i = n - np;
 276            single_pred_p (y) && !VISITED_P (single_pred (y));
 277            y = single_pred (y), i++)
 278         {
 279           order[i] = y;
 280           MARK_VISITED (y);
 281         }
 282       order[i] = y;
 283       MARK_VISITED (y);
 284
 285       gcc_assert (i == n - 1);
 286       n -= np;
 287     }
 288
 289   sbitmap_free (visited);
 290   gcc_assert (n == 0);
 291   return order;
 292
 293 #undef MARK_VISITED
 294 #undef VISITED_P
 295 }
 296
 297
 298 /* Return TRUE if block BB has no executable statements, otherwise return
 299    FALSE.  */
 300
 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_tree)
 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_tree);
 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_stmt, 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       && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (cond)))
 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 (!useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (cond)))
 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 = build_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_stmt = build_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_stmt = build_gimple_modify_stmt (cond_tmp, op0);
 518           SSA_NAME_DEF_STMT (cond_tmp) = new_stmt;
 519
 520           bsi_insert_after (&bsi, new_stmt, BSI_NEW_STMT);
 521           cond = fold_convert (TREE_TYPE (result), cond_tmp);
 522         }
 523
 524       new_stmt = build_gimple_modify_stmt (new_var1, cond);
 525     }
 526
 527   bsi_insert_after (&bsi, new_stmt, BSI_NEW_STMT);
 528
 529   SSA_NAME_DEF_STMT (new_var1) = new_stmt;
 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_stmt;
 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_stmt = build_gimple_modify_stmt (result, build2 (minmax, type, arg0, arg1));
 857   SSA_NAME_DEF_STMT (result) = new_stmt;
 858   bsi = bsi_last (cond_bb);
 859   bsi_insert_before (&bsi, new_stmt, BSI_NEW_STMT);
 860
 861   replace_phi_edge_with_variable (cond_bb, e1, phi, result);
 862   return true;
 863 }
 864
 865 /*  The function absolute_replacement does the main work of doing the absolute
 866     replacement.  Return true if the replacement is done.  Otherwise return
 867     false.
 868     bb is the basic block where the replacement is going to be done on.  arg0
 869     is argument 0 from the phi.  Likewise for arg1.  */
 870
 871 static bool
 872 abs_replacement (basic_block cond_bb, basic_block middle_bb,
 873                  edge e0 ATTRIBUTE_UNUSED, edge e1,
 874                  tree phi, tree arg0, tree arg1)
 875 {
 876   tree result;
 877   tree new_stmt, cond;
 878   block_stmt_iterator bsi;
 879   edge true_edge, false_edge;
 880   tree assign;
 881   edge e;
 882   tree rhs, lhs;
 883   bool negate;
 884   enum tree_code cond_code;
 885
 886   /* If the type says honor signed zeros we cannot do this
 887      optimization.  */
 888   if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
 889     return false;
 890
 891   /* OTHER_BLOCK must have only one executable statement which must have the
 892      form arg0 = -arg1 or arg1 = -arg0.  */
 893
 894   assign = last_and_only_stmt (middle_bb);
 895   /* If we did not find the proper negation assignment, then we can not
 896      optimize.  */
 897   if (assign == NULL)
 898     return false;
 899
 900   /* If we got here, then we have found the only executable statement
 901      in OTHER_BLOCK.  If it is anything other than arg = -arg1 or
 902      arg1 = -arg0, then we can not optimize.  */
 903   if (TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
 904     return false;
 905
 906   lhs = GIMPLE_STMT_OPERAND (assign, 0);
 907   rhs = GIMPLE_STMT_OPERAND (assign, 1);
 908
 909   if (TREE_CODE (rhs) != NEGATE_EXPR)
 910     return false;
 911
 912   rhs = TREE_OPERAND (rhs, 0);
 913
 914   /* The assignment has to be arg0 = -arg1 or arg1 = -arg0.  */
 915   if (!(lhs == arg0 && rhs == arg1)
 916       && !(lhs == arg1 && rhs == arg0))
 917     return false;
 918
 919   cond = COND_EXPR_COND (last_stmt (cond_bb));
 920   result = PHI_RESULT (phi);
 921
 922   /* Only relationals comparing arg[01] against zero are interesting.  */
 923   cond_code = TREE_CODE (cond);
 924   if (cond_code != GT_EXPR && cond_code != GE_EXPR
 925       && cond_code != LT_EXPR && cond_code != LE_EXPR)
 926     return false;
 927
 928   /* Make sure the conditional is arg[01] OP y.  */
 929   if (TREE_OPERAND (cond, 0) != rhs)
 930     return false;
 931
 932   if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))
 933                ? real_zerop (TREE_OPERAND (cond, 1))
 934                : integer_zerop (TREE_OPERAND (cond, 1)))
 935     ;
 936   else
 937     return false;
 938
 939   /* We need to know which is the true edge and which is the false
 940      edge so that we know if have abs or negative abs.  */
 941   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
 942
 943   /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
 944      will need to negate the result.  Similarly for LT_EXPR/LE_EXPR if
 945      the false edge goes to OTHER_BLOCK.  */
 946   if (cond_code == GT_EXPR || cond_code == GE_EXPR)
 947     e = true_edge;
 948   else
 949     e = false_edge;
 950
 951   if (e->dest == middle_bb)
 952     negate = true;
 953   else
 954     negate = false;
 955
 956   result = duplicate_ssa_name (result, NULL);
 957
 958   if (negate)
 959     {
 960       tree tmp = create_tmp_var (TREE_TYPE (result), NULL);
 961       add_referenced_var (tmp);
 962       lhs = make_ssa_name (tmp, NULL);
 963     }
 964   else
 965     lhs = result;
 966
 967   /* Build the modify expression with abs expression.  */
 968   new_stmt = build_gimple_modify_stmt (lhs,
 969                                        build1 (ABS_EXPR, TREE_TYPE (lhs), rhs));
 970   SSA_NAME_DEF_STMT (lhs) = new_stmt;
 971
 972   bsi = bsi_last (cond_bb);
 973   bsi_insert_before (&bsi, new_stmt, BSI_NEW_STMT);
 974
 975   if (negate)
 976     {
 977       /* Get the right BSI.  We want to insert after the recently
 978          added ABS_EXPR statement (which we know is the first statement
 979          in the block.  */
 980       new_stmt = build_gimple_modify_stmt (result,
 981                                            build1 (NEGATE_EXPR, TREE_TYPE (lhs),
 982                                                    lhs));
 983       SSA_NAME_DEF_STMT (result) = new_stmt;
 984
 985       bsi_insert_after (&bsi, new_stmt, 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 };