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 /* Return TRUE if block BB has no executable statements, otherwise return
 298    FALSE.  */
 299 bool
 300 empty_block_p (const_basic_block bb)
 301 {
 302   const_block_stmt_iterator bsi;
 303
 304   /* BB must have no executable statements.  */
 305   bsi = cbsi_start (bb);
 306   while (!cbsi_end_p (bsi)
 307           && (TREE_CODE (cbsi_stmt (bsi)) == LABEL_EXPR
 308               || IS_EMPTY_STMT (cbsi_stmt (bsi))))
 309     cbsi_next (&bsi);
 310
 311   if (!cbsi_end_p (bsi))
 312     return false;
 313
 314   return true;
 315 }
 316
 317 /* Replace PHI node element whose edge is E in block BB with variable NEW.
 318    Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
 319    is known to have two edges, one of which must reach BB).  */
 320
 321 static void
 322 replace_phi_edge_with_variable (basic_block cond_block,
 323                                 edge e, tree phi, tree new_tree)
 324 {
 325   basic_block bb = bb_for_stmt (phi);
 326   basic_block block_to_remove;
 327   block_stmt_iterator bsi;
 328
 329   /* Change the PHI argument to new.  */
 330   SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new_tree);
 331
 332   /* Remove the empty basic block.  */
 333   if (EDGE_SUCC (cond_block, 0)->dest == bb)
 334     {
 335       EDGE_SUCC (cond_block, 0)->flags |= EDGE_FALLTHRU;
 336       EDGE_SUCC (cond_block, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 337       EDGE_SUCC (cond_block, 0)->probability = REG_BR_PROB_BASE;
 338       EDGE_SUCC (cond_block, 0)->count += EDGE_SUCC (cond_block, 1)->count;
 339
 340       block_to_remove = EDGE_SUCC (cond_block, 1)->dest;
 341     }
 342   else
 343     {
 344       EDGE_SUCC (cond_block, 1)->flags |= EDGE_FALLTHRU;
 345       EDGE_SUCC (cond_block, 1)->flags
 346         &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 347       EDGE_SUCC (cond_block, 1)->probability = REG_BR_PROB_BASE;
 348       EDGE_SUCC (cond_block, 1)->count += EDGE_SUCC (cond_block, 0)->count;
 349
 350       block_to_remove = EDGE_SUCC (cond_block, 0)->dest;
 351     }
 352   delete_basic_block (block_to_remove);
 353
 354   /* Eliminate the COND_EXPR at the end of COND_BLOCK.  */
 355   bsi = bsi_last (cond_block);
 356   bsi_remove (&bsi, true);
 357
 358   if (dump_file && (dump_flags & TDF_DETAILS))
 359     fprintf (dump_file,
 360               "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
 361               cond_block->index,
 362               bb->index);
 363 }
 364
 365 /*  The function conditional_replacement does the main work of doing the
 366     conditional replacement.  Return true if the replacement is done.
 367     Otherwise return false.
 368     BB is the basic block where the replacement is going to be done on.  ARG0
 369     is argument 0 from PHI.  Likewise for ARG1.  */
 370
 371 static bool
 372 conditional_replacement (basic_block cond_bb, basic_block middle_bb,
 373                          edge e0, edge e1, tree phi,
 374                          tree arg0, tree arg1)
 375 {
 376   tree result;
 377   tree old_result = NULL;
 378   tree new_stmt, cond;
 379   block_stmt_iterator bsi;
 380   edge true_edge, false_edge;
 381   tree new_var = NULL;
 382   tree new_var1;
 383
 384   /* The PHI arguments have the constants 0 and 1, then convert
 385      it to the conditional.  */
 386   if ((integer_zerop (arg0) && integer_onep (arg1))
 387       || (integer_zerop (arg1) && integer_onep (arg0)))
 388     ;
 389   else
 390     return false;
 391
 392   if (!empty_block_p (middle_bb))
 393     return false;
 394
 395   /* If the condition is not a naked SSA_NAME and its type does not
 396      match the type of the result, then we have to create a new
 397      variable to optimize this case as it would likely create
 398      non-gimple code when the condition was converted to the
 399      result's type.  */
 400   cond = COND_EXPR_COND (last_stmt (cond_bb));
 401   result = PHI_RESULT (phi);
 402   if (TREE_CODE (cond) != SSA_NAME
 403       && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (cond)))
 404     {
 405       tree tmp;
 406
 407       if (!COMPARISON_CLASS_P (cond))
 408         return false;
 409
 410       tmp = create_tmp_var (TREE_TYPE (cond), NULL);
 411       add_referenced_var (tmp);
 412       new_var = make_ssa_name (tmp, NULL);
 413       old_result = cond;
 414       cond = new_var;
 415     }
 416
 417   /* If the condition was a naked SSA_NAME and the type is not the
 418      same as the type of the result, then convert the type of the
 419      condition.  */
 420   if (!useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (cond)))
 421     cond = fold_convert (TREE_TYPE (result), cond);
 422
 423   /* We need to know which is the true edge and which is the false
 424      edge so that we know when to invert the condition below.  */
 425   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
 426
 427   /* Insert our new statement at the end of conditional block before the
 428      COND_EXPR.  */
 429   bsi = bsi_last (cond_bb);
 430   bsi_insert_before (&bsi, build_empty_stmt (), BSI_NEW_STMT);
 431
 432   if (old_result)
 433     {
 434       tree new1;
 435
 436       new1 = build2 (TREE_CODE (old_result), TREE_TYPE (old_result),
 437                      TREE_OPERAND (old_result, 0),
 438                      TREE_OPERAND (old_result, 1));
 439
 440       new1 = build_gimple_modify_stmt (new_var, new1);
 441       SSA_NAME_DEF_STMT (new_var) = new1;
 442
 443       bsi_insert_after (&bsi, new1, BSI_NEW_STMT);
 444     }
 445
 446   new_var1 = duplicate_ssa_name (PHI_RESULT (phi), NULL);
 447
 448
 449   /* At this point we know we have a COND_EXPR with two successors.
 450      One successor is BB, the other successor is an empty block which
 451      falls through into BB.
 452
 453      There is a single PHI node at the join point (BB) and its arguments
 454      are constants (0, 1).
 455
 456      So, given the condition COND, and the two PHI arguments, we can
 457      rewrite this PHI into non-branching code:
 458
 459        dest = (COND) or dest = COND'
 460
 461      We use the condition as-is if the argument associated with the
 462      true edge has the value one or the argument associated with the
 463      false edge as the value zero.  Note that those conditions are not
 464      the same since only one of the outgoing edges from the COND_EXPR
 465      will directly reach BB and thus be associated with an argument.  */
 466   if ((e0 == true_edge && integer_onep (arg0))
 467       || (e0 == false_edge && integer_zerop (arg0))
 468       || (e1 == true_edge && integer_onep (arg1))
 469       || (e1 == false_edge && integer_zerop (arg1)))
 470     {
 471       new_stmt = build_gimple_modify_stmt (new_var1, cond);
 472     }
 473   else
 474     {
 475       tree cond1 = invert_truthvalue (cond);
 476
 477       cond = cond1;
 478
 479       /* If what we get back is a conditional expression, there is no
 480           way that it can be gimple.  */
 481       if (TREE_CODE (cond) == COND_EXPR)
 482         {
 483           release_ssa_name (new_var1);
 484           return false;
 485         }
 486
 487       /* If COND is not something we can expect to be reducible to a GIMPLE
 488          condition, return early.  */
 489       if (is_gimple_cast (cond))
 490         cond1 = TREE_OPERAND (cond, 0);
 491       if (TREE_CODE (cond1) == TRUTH_NOT_EXPR
 492           && !is_gimple_val (TREE_OPERAND (cond1, 0)))
 493         {
 494           release_ssa_name (new_var1);
 495           return false;
 496         }
 497
 498       /* If what we get back is not gimple try to create it as gimple by
 499          using a temporary variable.  */
 500       if (is_gimple_cast (cond)
 501           && !is_gimple_val (TREE_OPERAND (cond, 0)))
 502         {
 503           tree op0, tmp, cond_tmp;
 504
 505           /* Only "real" casts are OK here, not everything that is
 506              acceptable to is_gimple_cast.  Make sure we don't do
 507              anything stupid here.  */
 508           gcc_assert (TREE_CODE (cond) == NOP_EXPR
 509                       || TREE_CODE (cond) == CONVERT_EXPR);
 510
 511           op0 = TREE_OPERAND (cond, 0);
 512           tmp = create_tmp_var (TREE_TYPE (op0), NULL);
 513           add_referenced_var (tmp);
 514           cond_tmp = make_ssa_name (tmp, NULL);
 515           new_stmt = build_gimple_modify_stmt (cond_tmp, op0);
 516           SSA_NAME_DEF_STMT (cond_tmp) = new_stmt;
 517
 518           bsi_insert_after (&bsi, new_stmt, BSI_NEW_STMT);
 519           cond = fold_convert (TREE_TYPE (result), cond_tmp);
 520         }
 521
 522       new_stmt = build_gimple_modify_stmt (new_var1, cond);
 523     }
 524
 525   bsi_insert_after (&bsi, new_stmt, BSI_NEW_STMT);
 526
 527   SSA_NAME_DEF_STMT (new_var1) = new_stmt;
 528
 529   replace_phi_edge_with_variable (cond_bb, e1, phi, new_var1);
 530
 531   /* Note that we optimized this PHI.  */
 532   return true;
 533 }
 534
 535 /*  The function value_replacement does the main work of doing the value
 536     replacement.  Return true if the replacement is done.  Otherwise return
 537     false.
 538     BB is the basic block where the replacement is going to be done on.  ARG0
 539     is argument 0 from the PHI.  Likewise for ARG1.  */
 540
 541 static bool
 542 value_replacement (basic_block cond_bb, basic_block middle_bb,
 543                    edge e0, edge e1, tree phi,
 544                    tree arg0, tree arg1)
 545 {
 546   tree cond;
 547   edge true_edge, false_edge;
 548
 549   /* If the type says honor signed zeros we cannot do this
 550      optimization.  */
 551   if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
 552     return false;
 553
 554   if (!empty_block_p (middle_bb))
 555     return false;
 556
 557   cond = COND_EXPR_COND (last_stmt (cond_bb));
 558
 559   /* This transformation is only valid for equality comparisons.  */
 560   if (TREE_CODE (cond) != NE_EXPR && TREE_CODE (cond) != EQ_EXPR)
 561     return false;
 562
 563   /* We need to know which is the true edge and which is the false
 564       edge so that we know if have abs or negative abs.  */
 565   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
 566
 567   /* At this point we know we have a COND_EXPR with two successors.
 568      One successor is BB, the other successor is an empty block which
 569      falls through into BB.
 570
 571      The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
 572
 573      There is a single PHI node at the join point (BB) with two arguments.
 574
 575      We now need to verify that the two arguments in the PHI node match
 576      the two arguments to the equality comparison.  */
 577
 578   if ((operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 0))
 579        && operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 1)))
 580       || (operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 0))
 581           && operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 1))))
 582     {
 583       edge e;
 584       tree arg;
 585
 586       /* For NE_EXPR, we want to build an assignment result = arg where
 587          arg is the PHI argument associated with the true edge.  For
 588          EQ_EXPR we want the PHI argument associated with the false edge.  */
 589       e = (TREE_CODE (cond) == NE_EXPR ? true_edge : false_edge);
 590
 591       /* Unfortunately, E may not reach BB (it may instead have gone to
 592          OTHER_BLOCK).  If that is the case, then we want the single outgoing
 593          edge from OTHER_BLOCK which reaches BB and represents the desired
 594          path from COND_BLOCK.  */
 595       if (e->dest == middle_bb)
 596         e = single_succ_edge (e->dest);
 597
 598       /* Now we know the incoming edge to BB that has the argument for the
 599          RHS of our new assignment statement.  */
 600       if (e0 == e)
 601         arg = arg0;
 602       else
 603         arg = arg1;
 604
 605       replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
 606
 607       /* Note that we optimized this PHI.  */
 608       return true;
 609     }
 610   return false;
 611 }
 612
 613 /*  The function minmax_replacement does the main work of doing the minmax
 614     replacement.  Return true if the replacement is done.  Otherwise return
 615     false.
 616     BB is the basic block where the replacement is going to be done on.  ARG0
 617     is argument 0 from the PHI.  Likewise for ARG1.  */
 618
 619 static bool
 620 minmax_replacement (basic_block cond_bb, basic_block middle_bb,
 621                     edge e0, edge e1, tree phi,
 622                     tree arg0, tree arg1)
 623 {
 624   tree result, type;
 625   tree cond, new_stmt;
 626   edge true_edge, false_edge;
 627   enum tree_code cmp, minmax, ass_code;
 628   tree smaller, larger, arg_true, arg_false;
 629   block_stmt_iterator bsi, bsi_from;
 630
 631   type = TREE_TYPE (PHI_RESULT (phi));
 632
 633   /* The optimization may be unsafe due to NaNs.  */
 634   if (HONOR_NANS (TYPE_MODE (type)))
 635     return false;
 636
 637   cond = COND_EXPR_COND (last_stmt (cond_bb));
 638   cmp = TREE_CODE (cond);
 639   result = PHI_RESULT (phi);
 640
 641   /* This transformation is only valid for order comparisons.  Record which
 642      operand is smaller/larger if the result of the comparison is true.  */
 643   if (cmp == LT_EXPR || cmp == LE_EXPR)
 644     {
 645       smaller = TREE_OPERAND (cond, 0);
 646       larger = TREE_OPERAND (cond, 1);
 647     }
 648   else if (cmp == GT_EXPR || cmp == GE_EXPR)
 649     {
 650       smaller = TREE_OPERAND (cond, 1);
 651       larger = TREE_OPERAND (cond, 0);
 652     }
 653   else
 654     return false;
 655
 656   /* We need to know which is the true edge and which is the false
 657       edge so that we know if have abs or negative abs.  */
 658   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
 659
 660   /* Forward the edges over the middle basic block.  */
 661   if (true_edge->dest == middle_bb)
 662     true_edge = EDGE_SUCC (true_edge->dest, 0);
 663   if (false_edge->dest == middle_bb)
 664     false_edge = EDGE_SUCC (false_edge->dest, 0);
 665
 666   if (true_edge == e0)
 667     {
 668       gcc_assert (false_edge == e1);
 669       arg_true = arg0;
 670       arg_false = arg1;
 671     }
 672   else
 673     {
 674       gcc_assert (false_edge == e0);
 675       gcc_assert (true_edge == e1);
 676       arg_true = arg1;
 677       arg_false = arg0;
 678     }
 679
 680   if (empty_block_p (middle_bb))
 681     {
 682       if (operand_equal_for_phi_arg_p (arg_true, smaller)
 683           && operand_equal_for_phi_arg_p (arg_false, larger))
 684         {
 685           /* Case
 686
 687              if (smaller < larger)
 688              rslt = smaller;
 689              else
 690              rslt = larger;  */
 691           minmax = MIN_EXPR;
 692         }
 693       else if (operand_equal_for_phi_arg_p (arg_false, smaller)
 694                && operand_equal_for_phi_arg_p (arg_true, larger))
 695         minmax = MAX_EXPR;
 696       else
 697         return false;
 698     }
 699   else
 700     {
 701       /* Recognize the following case, assuming d <= u:
 702
 703          if (a <= u)
 704            b = MAX (a, d);
 705          x = PHI <b, u>
 706
 707          This is equivalent to
 708
 709          b = MAX (a, d);
 710          x = MIN (b, u);  */
 711
 712       tree assign = last_and_only_stmt (middle_bb);
 713       tree lhs, rhs, op0, op1, bound;
 714
 715       if (!assign
 716           || TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
 717         return false;
 718
 719       lhs = GIMPLE_STMT_OPERAND (assign, 0);
 720       rhs = GIMPLE_STMT_OPERAND (assign, 1);
 721       ass_code = TREE_CODE (rhs);
 722       if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
 723         return false;
 724       op0 = TREE_OPERAND (rhs, 0);
 725       op1 = TREE_OPERAND (rhs, 1);
 726
 727       if (true_edge->src == middle_bb)
 728         {
 729           /* We got here if the condition is true, i.e., SMALLER < LARGER.  */
 730           if (!operand_equal_for_phi_arg_p (lhs, arg_true))
 731             return false;
 732
 733           if (operand_equal_for_phi_arg_p (arg_false, larger))
 734             {
 735               /* Case
 736
 737                  if (smaller < larger)
 738                    {
 739                      r' = MAX_EXPR (smaller, bound)
 740                    }
 741                  r = PHI <r', larger>  --> to be turned to MIN_EXPR.  */
 742               if (ass_code != MAX_EXPR)
 743                 return false;
 744
 745               minmax = MIN_EXPR;
 746               if (operand_equal_for_phi_arg_p (op0, smaller))
 747                 bound = op1;
 748               else if (operand_equal_for_phi_arg_p (op1, smaller))
 749                 bound = op0;
 750               else
 751                 return false;
 752
 753               /* We need BOUND <= LARGER.  */
 754               if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
 755                                                   bound, larger)))
 756                 return false;
 757             }
 758           else if (operand_equal_for_phi_arg_p (arg_false, smaller))
 759             {
 760               /* Case
 761
 762                  if (smaller < larger)
 763                    {
 764                      r' = MIN_EXPR (larger, bound)
 765                    }
 766                  r = PHI <r', smaller>  --> to be turned to MAX_EXPR.  */
 767               if (ass_code != MIN_EXPR)
 768                 return false;
 769
 770               minmax = MAX_EXPR;
 771               if (operand_equal_for_phi_arg_p (op0, larger))
 772                 bound = op1;
 773               else if (operand_equal_for_phi_arg_p (op1, larger))
 774                 bound = op0;
 775               else
 776                 return false;
 777
 778               /* We need BOUND >= SMALLER.  */
 779               if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
 780                                                   bound, smaller)))
 781                 return false;
 782             }
 783           else
 784             return false;
 785         }
 786       else
 787         {
 788           /* We got here if the condition is false, i.e., SMALLER > LARGER.  */
 789           if (!operand_equal_for_phi_arg_p (lhs, arg_false))
 790             return false;
 791
 792           if (operand_equal_for_phi_arg_p (arg_true, larger))
 793             {
 794               /* Case
 795
 796                  if (smaller > larger)
 797                    {
 798                      r' = MIN_EXPR (smaller, bound)
 799                    }
 800                  r = PHI <r', larger>  --> to be turned to MAX_EXPR.  */
 801               if (ass_code != MIN_EXPR)
 802                 return false;
 803
 804               minmax = MAX_EXPR;
 805               if (operand_equal_for_phi_arg_p (op0, smaller))
 806                 bound = op1;
 807               else if (operand_equal_for_phi_arg_p (op1, smaller))
 808                 bound = op0;
 809               else
 810                 return false;
 811
 812               /* We need BOUND >= LARGER.  */
 813               if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
 814                                                   bound, larger)))
 815                 return false;
 816             }
 817           else if (operand_equal_for_phi_arg_p (arg_true, smaller))
 818             {
 819               /* Case
 820
 821                  if (smaller > larger)
 822                    {
 823                      r' = MAX_EXPR (larger, bound)
 824                    }
 825                  r = PHI <r', smaller>  --> to be turned to MIN_EXPR.  */
 826               if (ass_code != MAX_EXPR)
 827                 return false;
 828
 829               minmax = MIN_EXPR;
 830               if (operand_equal_for_phi_arg_p (op0, larger))
 831                 bound = op1;
 832               else if (operand_equal_for_phi_arg_p (op1, larger))
 833                 bound = op0;
 834               else
 835                 return false;
 836
 837               /* We need BOUND <= SMALLER.  */
 838               if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
 839                                                   bound, smaller)))
 840                 return false;
 841             }
 842           else
 843             return false;
 844         }
 845
 846       /* Move the statement from the middle block.  */
 847       bsi = bsi_last (cond_bb);
 848       bsi_from = bsi_last (middle_bb);
 849       bsi_move_before (&bsi_from, &bsi);
 850     }
 851
 852   /* Emit the statement to compute min/max.  */
 853   result = duplicate_ssa_name (PHI_RESULT (phi), NULL);
 854   new_stmt = build_gimple_modify_stmt (result, build2 (minmax, type, arg0, arg1));
 855   SSA_NAME_DEF_STMT (result) = new_stmt;
 856   bsi = bsi_last (cond_bb);
 857   bsi_insert_before (&bsi, new_stmt, 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_stmt, 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) != GIMPLE_MODIFY_STMT)
 902     return false;
 903
 904   lhs = GIMPLE_STMT_OPERAND (assign, 0);
 905   rhs = GIMPLE_STMT_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_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_stmt = build_gimple_modify_stmt (lhs,
 967                                        build1 (ABS_EXPR, TREE_TYPE (lhs), rhs));
 968   SSA_NAME_DEF_STMT (lhs) = new_stmt;
 969
 970   bsi = bsi_last (cond_bb);
 971   bsi_insert_before (&bsi, new_stmt, 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_stmt = build_gimple_modify_stmt (result,
 979                                            build1 (NEGATE_EXPR, TREE_TYPE (lhs),
 980                                                    lhs));
 981       SSA_NAME_DEF_STMT (result) = new_stmt;
 982
 983       bsi_insert_after (&bsi, new_stmt, BSI_NEW_STMT);
 984     }
 985
 986   replace_phi_edge_with_variable (cond_bb, e1, phi, result);
 987
 988   /* Note that we optimized this PHI.  */
 989   return true;
 990 }
 991
 992
 993 /* Always do these optimizations if we have SSA
 994    trees to work on.  */
 995 static bool
 996 gate_phiopt (void)
 997 {
 998   return 1;
 999 }
1000
1001 struct tree_opt_pass pass_phiopt =
1002 {
1003   "phiopt",                             /* name */
1004   gate_phiopt,                          /* gate */
1005   tree_ssa_phiopt,                      /* execute */
1006   NULL,                                 /* sub */
1007   NULL,                                 /* next */
1008   0,                                    /* static_pass_number */
1009   TV_TREE_PHIOPT,                       /* tv_id */
1010   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1011   0,                                    /* properties_provided */
1012   0,                                    /* properties_destroyed */
1013   0,                                    /* todo_flags_start */
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 };