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