tree-ssa-phiopt.c revision 169689
1/* Optimization of PHI nodes by converting them into straightline code. 2 Copyright (C) 2004, 2005 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it 7under the terms of the GNU General Public License as published by the 8Free Software Foundation; either version 2, or (at your option) any 9later version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT 12ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING. If not, write to the Free 18Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 1902110-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 38static unsigned int tree_ssa_phiopt (void); 39static bool conditional_replacement (basic_block, basic_block, 40 edge, edge, tree, tree, tree); 41static bool value_replacement (basic_block, basic_block, 42 edge, edge, tree, tree, tree); 43static bool minmax_replacement (basic_block, basic_block, 44 edge, edge, tree, tree, tree); 45static bool abs_replacement (basic_block, basic_block, 46 edge, edge, tree, tree, tree); 47static void replace_phi_edge_with_variable (basic_block, edge, tree, tree); 48static 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 136static unsigned int 137tree_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 250static basic_block * 251blocks_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. */ 301bool 302empty_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 323static void 324replace_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 373static bool 374conditional_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 (MODIFY_EXPR, TREE_TYPE (old_result), 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 (MODIFY_EXPR, TREE_TYPE (new_var1), 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 (MODIFY_EXPR, TREE_TYPE (cond_tmp), 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 (MODIFY_EXPR, TREE_TYPE (new_var1), 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 543static bool 544value_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 621static bool 622minmax_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) != MODIFY_EXPR) 719 return false; 720 721 lhs = TREE_OPERAND (assign, 0); 722 rhs = TREE_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 (MODIFY_EXPR, type, 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 872static bool 873abs_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) != MODIFY_EXPR) 905 return false; 906 907 lhs = TREE_OPERAND (assign, 0); 908 rhs = TREE_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 (MODIFY_EXPR, TREE_TYPE (lhs), 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 (MODIFY_EXPR, TREE_TYPE (result), 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. */ 997static bool 998gate_phiopt (void) 999{ 1000 return 1; 1001} 1002 1003struct 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}; 1023