1169689Skan/* Optimization of PHI nodes by converting them into straightline code. 2169689Skan Copyright (C) 2004, 2005 Free Software Foundation, Inc. 3169689Skan 4169689SkanThis file is part of GCC. 5169689Skan 6169689SkanGCC is free software; you can redistribute it and/or modify it 7169689Skanunder the terms of the GNU General Public License as published by the 8169689SkanFree Software Foundation; either version 2, or (at your option) any 9169689Skanlater version. 10169689Skan 11169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT 12169689SkanANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14169689Skanfor more details. 15169689Skan 16169689SkanYou should have received a copy of the GNU General Public License 17169689Skanalong with GCC; see the file COPYING. If not, write to the Free 18169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19169689Skan02110-1301, USA. */ 20169689Skan 21169689Skan#include "config.h" 22169689Skan#include "system.h" 23169689Skan#include "coretypes.h" 24169689Skan#include "tm.h" 25169689Skan#include "ggc.h" 26169689Skan#include "tree.h" 27169689Skan#include "rtl.h" 28169689Skan#include "flags.h" 29169689Skan#include "tm_p.h" 30169689Skan#include "basic-block.h" 31169689Skan#include "timevar.h" 32169689Skan#include "diagnostic.h" 33169689Skan#include "tree-flow.h" 34169689Skan#include "tree-pass.h" 35169689Skan#include "tree-dump.h" 36169689Skan#include "langhooks.h" 37169689Skan 38169689Skanstatic unsigned int tree_ssa_phiopt (void); 39169689Skanstatic bool conditional_replacement (basic_block, basic_block, 40169689Skan edge, edge, tree, tree, tree); 41169689Skanstatic bool value_replacement (basic_block, basic_block, 42169689Skan edge, edge, tree, tree, tree); 43169689Skanstatic bool minmax_replacement (basic_block, basic_block, 44169689Skan edge, edge, tree, tree, tree); 45169689Skanstatic bool abs_replacement (basic_block, basic_block, 46169689Skan edge, edge, tree, tree, tree); 47169689Skanstatic void replace_phi_edge_with_variable (basic_block, edge, tree, tree); 48169689Skanstatic basic_block *blocks_in_phiopt_order (void); 49169689Skan 50169689Skan/* This pass tries to replaces an if-then-else block with an 51169689Skan assignment. We have four kinds of transformations. Some of these 52169689Skan transformations are also performed by the ifcvt RTL optimizer. 53169689Skan 54169689Skan Conditional Replacement 55169689Skan ----------------------- 56169689Skan 57169689Skan This transformation, implemented in conditional_replacement, 58169689Skan replaces 59169689Skan 60169689Skan bb0: 61169689Skan if (cond) goto bb2; else goto bb1; 62169689Skan bb1: 63169689Skan bb2: 64169689Skan x = PHI <0 (bb1), 1 (bb0), ...>; 65169689Skan 66169689Skan with 67169689Skan 68169689Skan bb0: 69169689Skan x' = cond; 70169689Skan goto bb2; 71169689Skan bb2: 72169689Skan x = PHI <x' (bb0), ...>; 73169689Skan 74169689Skan We remove bb1 as it becomes unreachable. This occurs often due to 75169689Skan gimplification of conditionals. 76169689Skan 77169689Skan Value Replacement 78169689Skan ----------------- 79169689Skan 80169689Skan This transformation, implemented in value_replacement, replaces 81169689Skan 82169689Skan bb0: 83169689Skan if (a != b) goto bb2; else goto bb1; 84169689Skan bb1: 85169689Skan bb2: 86169689Skan x = PHI <a (bb1), b (bb0), ...>; 87169689Skan 88169689Skan with 89169689Skan 90169689Skan bb0: 91169689Skan bb2: 92169689Skan x = PHI <b (bb0), ...>; 93169689Skan 94169689Skan This opportunity can sometimes occur as a result of other 95169689Skan optimizations. 96169689Skan 97169689Skan ABS Replacement 98169689Skan --------------- 99169689Skan 100169689Skan This transformation, implemented in abs_replacement, replaces 101169689Skan 102169689Skan bb0: 103169689Skan if (a >= 0) goto bb2; else goto bb1; 104169689Skan bb1: 105169689Skan x = -a; 106169689Skan bb2: 107169689Skan x = PHI <x (bb1), a (bb0), ...>; 108169689Skan 109169689Skan with 110169689Skan 111169689Skan bb0: 112169689Skan x' = ABS_EXPR< a >; 113169689Skan bb2: 114169689Skan x = PHI <x' (bb0), ...>; 115169689Skan 116169689Skan MIN/MAX Replacement 117169689Skan ------------------- 118169689Skan 119169689Skan This transformation, minmax_replacement replaces 120169689Skan 121169689Skan bb0: 122169689Skan if (a <= b) goto bb2; else goto bb1; 123169689Skan bb1: 124169689Skan bb2: 125169689Skan x = PHI <b (bb1), a (bb0), ...>; 126169689Skan 127169689Skan with 128169689Skan 129169689Skan bb0: 130169689Skan x' = MIN_EXPR (a, b) 131169689Skan bb2: 132169689Skan x = PHI <x' (bb0), ...>; 133169689Skan 134169689Skan A similar transformation is done for MAX_EXPR. */ 135169689Skan 136169689Skanstatic unsigned int 137169689Skantree_ssa_phiopt (void) 138169689Skan{ 139169689Skan basic_block bb; 140169689Skan basic_block *bb_order; 141169689Skan unsigned n, i; 142169689Skan bool cfgchanged = false; 143169689Skan 144169689Skan /* Search every basic block for COND_EXPR we may be able to optimize. 145169689Skan 146169689Skan We walk the blocks in order that guarantees that a block with 147169689Skan a single predecessor is processed before the predecessor. 148169689Skan This ensures that we collapse inner ifs before visiting the 149169689Skan outer ones, and also that we do not try to visit a removed 150169689Skan block. */ 151169689Skan bb_order = blocks_in_phiopt_order (); 152169689Skan n = n_basic_blocks - NUM_FIXED_BLOCKS; 153169689Skan 154169689Skan for (i = 0; i < n; i++) 155169689Skan { 156169689Skan tree cond_expr; 157169689Skan tree phi; 158169689Skan basic_block bb1, bb2; 159169689Skan edge e1, e2; 160169689Skan tree arg0, arg1; 161169689Skan 162169689Skan bb = bb_order[i]; 163169689Skan 164169689Skan cond_expr = last_stmt (bb); 165169689Skan /* Check to see if the last statement is a COND_EXPR. */ 166169689Skan if (!cond_expr 167169689Skan || TREE_CODE (cond_expr) != COND_EXPR) 168169689Skan continue; 169169689Skan 170169689Skan e1 = EDGE_SUCC (bb, 0); 171169689Skan bb1 = e1->dest; 172169689Skan e2 = EDGE_SUCC (bb, 1); 173169689Skan bb2 = e2->dest; 174169689Skan 175169689Skan /* We cannot do the optimization on abnormal edges. */ 176169689Skan if ((e1->flags & EDGE_ABNORMAL) != 0 177169689Skan || (e2->flags & EDGE_ABNORMAL) != 0) 178169689Skan continue; 179169689Skan 180169689Skan /* If either bb1's succ or bb2 or bb2's succ is non NULL. */ 181169689Skan if (EDGE_COUNT (bb1->succs) == 0 182169689Skan || bb2 == NULL 183169689Skan || EDGE_COUNT (bb2->succs) == 0) 184169689Skan continue; 185169689Skan 186169689Skan /* Find the bb which is the fall through to the other. */ 187169689Skan if (EDGE_SUCC (bb1, 0)->dest == bb2) 188169689Skan ; 189169689Skan else if (EDGE_SUCC (bb2, 0)->dest == bb1) 190169689Skan { 191169689Skan basic_block bb_tmp = bb1; 192169689Skan edge e_tmp = e1; 193169689Skan bb1 = bb2; 194169689Skan bb2 = bb_tmp; 195169689Skan e1 = e2; 196169689Skan e2 = e_tmp; 197169689Skan } 198169689Skan else 199169689Skan continue; 200169689Skan 201169689Skan e1 = EDGE_SUCC (bb1, 0); 202169689Skan 203169689Skan /* Make sure that bb1 is just a fall through. */ 204169689Skan if (!single_succ_p (bb1) 205169689Skan || (e1->flags & EDGE_FALLTHRU) == 0) 206169689Skan continue; 207169689Skan 208169689Skan /* Also make sure that bb1 only have one predecessor and that it 209169689Skan is bb. */ 210169689Skan if (!single_pred_p (bb1) 211169689Skan || single_pred (bb1) != bb) 212169689Skan continue; 213169689Skan 214169689Skan phi = phi_nodes (bb2); 215169689Skan 216169689Skan /* Check to make sure that there is only one PHI node. 217169689Skan TODO: we could do it with more than one iff the other PHI nodes 218169689Skan have the same elements for these two edges. */ 219169689Skan if (!phi || PHI_CHAIN (phi) != NULL) 220169689Skan continue; 221169689Skan 222169689Skan arg0 = PHI_ARG_DEF_TREE (phi, e1->dest_idx); 223169689Skan arg1 = PHI_ARG_DEF_TREE (phi, e2->dest_idx); 224169689Skan 225169689Skan /* Something is wrong if we cannot find the arguments in the PHI 226169689Skan node. */ 227169689Skan gcc_assert (arg0 != NULL && arg1 != NULL); 228169689Skan 229169689Skan /* Do the replacement of conditional if it can be done. */ 230169689Skan if (conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) 231169689Skan cfgchanged = true; 232169689Skan else if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) 233169689Skan cfgchanged = true; 234169689Skan else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) 235169689Skan cfgchanged = true; 236169689Skan else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) 237169689Skan cfgchanged = true; 238169689Skan } 239169689Skan 240169689Skan free (bb_order); 241169689Skan 242169689Skan /* If the CFG has changed, we should cleanup the CFG. */ 243169689Skan return cfgchanged ? TODO_cleanup_cfg : 0; 244169689Skan} 245169689Skan 246169689Skan/* Returns the list of basic blocks in the function in an order that guarantees 247169689Skan that if a block X has just a single predecessor Y, then Y is after X in the 248169689Skan ordering. */ 249169689Skan 250169689Skanstatic basic_block * 251169689Skanblocks_in_phiopt_order (void) 252169689Skan{ 253169689Skan basic_block x, y; 254169689Skan basic_block *order = XNEWVEC (basic_block, n_basic_blocks); 255169689Skan unsigned n = n_basic_blocks - NUM_FIXED_BLOCKS; 256169689Skan unsigned np, i; 257169689Skan sbitmap visited = sbitmap_alloc (last_basic_block); 258169689Skan 259169689Skan#define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index)) 260169689Skan#define VISITED_P(BB) (TEST_BIT (visited, (BB)->index)) 261169689Skan 262169689Skan sbitmap_zero (visited); 263169689Skan 264169689Skan MARK_VISITED (ENTRY_BLOCK_PTR); 265169689Skan FOR_EACH_BB (x) 266169689Skan { 267169689Skan if (VISITED_P (x)) 268169689Skan continue; 269169689Skan 270169689Skan /* Walk the predecessors of x as long as they have precisely one 271169689Skan predecessor and add them to the list, so that they get stored 272169689Skan after x. */ 273169689Skan for (y = x, np = 1; 274169689Skan single_pred_p (y) && !VISITED_P (single_pred (y)); 275169689Skan y = single_pred (y)) 276169689Skan np++; 277169689Skan for (y = x, i = n - np; 278169689Skan single_pred_p (y) && !VISITED_P (single_pred (y)); 279169689Skan y = single_pred (y), i++) 280169689Skan { 281169689Skan order[i] = y; 282169689Skan MARK_VISITED (y); 283169689Skan } 284169689Skan order[i] = y; 285169689Skan MARK_VISITED (y); 286169689Skan 287169689Skan gcc_assert (i == n - 1); 288169689Skan n -= np; 289169689Skan } 290169689Skan 291169689Skan sbitmap_free (visited); 292169689Skan gcc_assert (n == 0); 293169689Skan return order; 294169689Skan 295169689Skan#undef MARK_VISITED 296169689Skan#undef VISITED_P 297169689Skan} 298169689Skan 299169689Skan/* Return TRUE if block BB has no executable statements, otherwise return 300169689Skan FALSE. */ 301169689Skanbool 302169689Skanempty_block_p (basic_block bb) 303169689Skan{ 304169689Skan block_stmt_iterator bsi; 305169689Skan 306169689Skan /* BB must have no executable statements. */ 307169689Skan bsi = bsi_start (bb); 308169689Skan while (!bsi_end_p (bsi) 309169689Skan && (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR 310169689Skan || IS_EMPTY_STMT (bsi_stmt (bsi)))) 311169689Skan bsi_next (&bsi); 312169689Skan 313169689Skan if (!bsi_end_p (bsi)) 314169689Skan return false; 315169689Skan 316169689Skan return true; 317169689Skan} 318169689Skan 319169689Skan/* Replace PHI node element whose edge is E in block BB with variable NEW. 320169689Skan Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK 321169689Skan is known to have two edges, one of which must reach BB). */ 322169689Skan 323169689Skanstatic void 324169689Skanreplace_phi_edge_with_variable (basic_block cond_block, 325169689Skan edge e, tree phi, tree new) 326169689Skan{ 327169689Skan basic_block bb = bb_for_stmt (phi); 328169689Skan basic_block block_to_remove; 329169689Skan block_stmt_iterator bsi; 330169689Skan 331169689Skan /* Change the PHI argument to new. */ 332169689Skan SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new); 333169689Skan 334169689Skan /* Remove the empty basic block. */ 335169689Skan if (EDGE_SUCC (cond_block, 0)->dest == bb) 336169689Skan { 337169689Skan EDGE_SUCC (cond_block, 0)->flags |= EDGE_FALLTHRU; 338169689Skan EDGE_SUCC (cond_block, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); 339169689Skan EDGE_SUCC (cond_block, 0)->probability = REG_BR_PROB_BASE; 340169689Skan EDGE_SUCC (cond_block, 0)->count += EDGE_SUCC (cond_block, 1)->count; 341169689Skan 342169689Skan block_to_remove = EDGE_SUCC (cond_block, 1)->dest; 343169689Skan } 344169689Skan else 345169689Skan { 346169689Skan EDGE_SUCC (cond_block, 1)->flags |= EDGE_FALLTHRU; 347169689Skan EDGE_SUCC (cond_block, 1)->flags 348169689Skan &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); 349169689Skan EDGE_SUCC (cond_block, 1)->probability = REG_BR_PROB_BASE; 350169689Skan EDGE_SUCC (cond_block, 1)->count += EDGE_SUCC (cond_block, 0)->count; 351169689Skan 352169689Skan block_to_remove = EDGE_SUCC (cond_block, 0)->dest; 353169689Skan } 354169689Skan delete_basic_block (block_to_remove); 355169689Skan 356169689Skan /* Eliminate the COND_EXPR at the end of COND_BLOCK. */ 357169689Skan bsi = bsi_last (cond_block); 358169689Skan bsi_remove (&bsi, true); 359169689Skan 360169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 361169689Skan fprintf (dump_file, 362169689Skan "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n", 363169689Skan cond_block->index, 364169689Skan bb->index); 365169689Skan} 366169689Skan 367169689Skan/* The function conditional_replacement does the main work of doing the 368169689Skan conditional replacement. Return true if the replacement is done. 369169689Skan Otherwise return false. 370169689Skan BB is the basic block where the replacement is going to be done on. ARG0 371169689Skan is argument 0 from PHI. Likewise for ARG1. */ 372169689Skan 373169689Skanstatic bool 374169689Skanconditional_replacement (basic_block cond_bb, basic_block middle_bb, 375169689Skan edge e0, edge e1, tree phi, 376169689Skan tree arg0, tree arg1) 377169689Skan{ 378169689Skan tree result; 379169689Skan tree old_result = NULL; 380169689Skan tree new, cond; 381169689Skan block_stmt_iterator bsi; 382169689Skan edge true_edge, false_edge; 383169689Skan tree new_var = NULL; 384169689Skan tree new_var1; 385169689Skan 386169689Skan /* The PHI arguments have the constants 0 and 1, then convert 387169689Skan it to the conditional. */ 388169689Skan if ((integer_zerop (arg0) && integer_onep (arg1)) 389169689Skan || (integer_zerop (arg1) && integer_onep (arg0))) 390169689Skan ; 391169689Skan else 392169689Skan return false; 393169689Skan 394169689Skan if (!empty_block_p (middle_bb)) 395169689Skan return false; 396169689Skan 397169689Skan /* If the condition is not a naked SSA_NAME and its type does not 398169689Skan match the type of the result, then we have to create a new 399169689Skan variable to optimize this case as it would likely create 400169689Skan non-gimple code when the condition was converted to the 401169689Skan result's type. */ 402169689Skan cond = COND_EXPR_COND (last_stmt (cond_bb)); 403169689Skan result = PHI_RESULT (phi); 404169689Skan if (TREE_CODE (cond) != SSA_NAME 405169689Skan && !lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result))) 406169689Skan { 407169689Skan tree tmp; 408169689Skan 409169689Skan if (!COMPARISON_CLASS_P (cond)) 410169689Skan return false; 411169689Skan 412169689Skan tmp = create_tmp_var (TREE_TYPE (cond), NULL); 413169689Skan add_referenced_var (tmp); 414169689Skan new_var = make_ssa_name (tmp, NULL); 415169689Skan old_result = cond; 416169689Skan cond = new_var; 417169689Skan } 418169689Skan 419169689Skan /* If the condition was a naked SSA_NAME and the type is not the 420169689Skan same as the type of the result, then convert the type of the 421169689Skan condition. */ 422169689Skan if (!lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result))) 423169689Skan cond = fold_convert (TREE_TYPE (result), cond); 424169689Skan 425169689Skan /* We need to know which is the true edge and which is the false 426169689Skan edge so that we know when to invert the condition below. */ 427169689Skan extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge); 428169689Skan 429169689Skan /* Insert our new statement at the end of conditional block before the 430169689Skan COND_EXPR. */ 431169689Skan bsi = bsi_last (cond_bb); 432169689Skan bsi_insert_before (&bsi, build_empty_stmt (), BSI_NEW_STMT); 433169689Skan 434169689Skan if (old_result) 435169689Skan { 436169689Skan tree new1; 437169689Skan 438169689Skan new1 = build2 (TREE_CODE (old_result), TREE_TYPE (old_result), 439169689Skan TREE_OPERAND (old_result, 0), 440169689Skan TREE_OPERAND (old_result, 1)); 441169689Skan 442169689Skan new1 = build2 (MODIFY_EXPR, TREE_TYPE (old_result), new_var, new1); 443169689Skan SSA_NAME_DEF_STMT (new_var) = new1; 444169689Skan 445169689Skan bsi_insert_after (&bsi, new1, BSI_NEW_STMT); 446169689Skan } 447169689Skan 448169689Skan new_var1 = duplicate_ssa_name (PHI_RESULT (phi), NULL); 449169689Skan 450169689Skan 451169689Skan /* At this point we know we have a COND_EXPR with two successors. 452169689Skan One successor is BB, the other successor is an empty block which 453169689Skan falls through into BB. 454169689Skan 455169689Skan There is a single PHI node at the join point (BB) and its arguments 456169689Skan are constants (0, 1). 457169689Skan 458169689Skan So, given the condition COND, and the two PHI arguments, we can 459169689Skan rewrite this PHI into non-branching code: 460169689Skan 461169689Skan dest = (COND) or dest = COND' 462169689Skan 463169689Skan We use the condition as-is if the argument associated with the 464169689Skan true edge has the value one or the argument associated with the 465169689Skan false edge as the value zero. Note that those conditions are not 466169689Skan the same since only one of the outgoing edges from the COND_EXPR 467169689Skan will directly reach BB and thus be associated with an argument. */ 468169689Skan if ((e0 == true_edge && integer_onep (arg0)) 469169689Skan || (e0 == false_edge && integer_zerop (arg0)) 470169689Skan || (e1 == true_edge && integer_onep (arg1)) 471169689Skan || (e1 == false_edge && integer_zerop (arg1))) 472169689Skan { 473169689Skan new = build2 (MODIFY_EXPR, TREE_TYPE (new_var1), new_var1, cond); 474169689Skan } 475169689Skan else 476169689Skan { 477169689Skan tree cond1 = invert_truthvalue (cond); 478169689Skan 479169689Skan cond = cond1; 480169689Skan 481169689Skan /* If what we get back is a conditional expression, there is no 482169689Skan way that it can be gimple. */ 483169689Skan if (TREE_CODE (cond) == COND_EXPR) 484169689Skan { 485169689Skan release_ssa_name (new_var1); 486169689Skan return false; 487169689Skan } 488169689Skan 489169689Skan /* If COND is not something we can expect to be reducible to a GIMPLE 490169689Skan condition, return early. */ 491169689Skan if (is_gimple_cast (cond)) 492169689Skan cond1 = TREE_OPERAND (cond, 0); 493169689Skan if (TREE_CODE (cond1) == TRUTH_NOT_EXPR 494169689Skan && !is_gimple_val (TREE_OPERAND (cond1, 0))) 495169689Skan { 496169689Skan release_ssa_name (new_var1); 497169689Skan return false; 498169689Skan } 499169689Skan 500169689Skan /* If what we get back is not gimple try to create it as gimple by 501169689Skan using a temporary variable. */ 502169689Skan if (is_gimple_cast (cond) 503169689Skan && !is_gimple_val (TREE_OPERAND (cond, 0))) 504169689Skan { 505169689Skan tree op0, tmp, cond_tmp; 506169689Skan 507169689Skan /* Only "real" casts are OK here, not everything that is 508169689Skan acceptable to is_gimple_cast. Make sure we don't do 509169689Skan anything stupid here. */ 510169689Skan gcc_assert (TREE_CODE (cond) == NOP_EXPR 511169689Skan || TREE_CODE (cond) == CONVERT_EXPR); 512169689Skan 513169689Skan op0 = TREE_OPERAND (cond, 0); 514169689Skan tmp = create_tmp_var (TREE_TYPE (op0), NULL); 515169689Skan add_referenced_var (tmp); 516169689Skan cond_tmp = make_ssa_name (tmp, NULL); 517169689Skan new = build2 (MODIFY_EXPR, TREE_TYPE (cond_tmp), cond_tmp, op0); 518169689Skan SSA_NAME_DEF_STMT (cond_tmp) = new; 519169689Skan 520169689Skan bsi_insert_after (&bsi, new, BSI_NEW_STMT); 521169689Skan cond = fold_convert (TREE_TYPE (result), cond_tmp); 522169689Skan } 523169689Skan 524169689Skan new = build2 (MODIFY_EXPR, TREE_TYPE (new_var1), new_var1, cond); 525169689Skan } 526169689Skan 527169689Skan bsi_insert_after (&bsi, new, BSI_NEW_STMT); 528169689Skan 529169689Skan SSA_NAME_DEF_STMT (new_var1) = new; 530169689Skan 531169689Skan replace_phi_edge_with_variable (cond_bb, e1, phi, new_var1); 532169689Skan 533169689Skan /* Note that we optimized this PHI. */ 534169689Skan return true; 535169689Skan} 536169689Skan 537169689Skan/* The function value_replacement does the main work of doing the value 538169689Skan replacement. Return true if the replacement is done. Otherwise return 539169689Skan false. 540169689Skan BB is the basic block where the replacement is going to be done on. ARG0 541169689Skan is argument 0 from the PHI. Likewise for ARG1. */ 542169689Skan 543169689Skanstatic bool 544169689Skanvalue_replacement (basic_block cond_bb, basic_block middle_bb, 545169689Skan edge e0, edge e1, tree phi, 546169689Skan tree arg0, tree arg1) 547169689Skan{ 548169689Skan tree cond; 549169689Skan edge true_edge, false_edge; 550169689Skan 551169689Skan /* If the type says honor signed zeros we cannot do this 552169689Skan optimization. */ 553169689Skan if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1)))) 554169689Skan return false; 555169689Skan 556169689Skan if (!empty_block_p (middle_bb)) 557169689Skan return false; 558169689Skan 559169689Skan cond = COND_EXPR_COND (last_stmt (cond_bb)); 560169689Skan 561169689Skan /* This transformation is only valid for equality comparisons. */ 562169689Skan if (TREE_CODE (cond) != NE_EXPR && TREE_CODE (cond) != EQ_EXPR) 563169689Skan return false; 564169689Skan 565169689Skan /* We need to know which is the true edge and which is the false 566169689Skan edge so that we know if have abs or negative abs. */ 567169689Skan extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge); 568169689Skan 569169689Skan /* At this point we know we have a COND_EXPR with two successors. 570169689Skan One successor is BB, the other successor is an empty block which 571169689Skan falls through into BB. 572169689Skan 573169689Skan The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR. 574169689Skan 575169689Skan There is a single PHI node at the join point (BB) with two arguments. 576169689Skan 577169689Skan We now need to verify that the two arguments in the PHI node match 578169689Skan the two arguments to the equality comparison. */ 579169689Skan 580169689Skan if ((operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 0)) 581169689Skan && operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 1))) 582169689Skan || (operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 0)) 583169689Skan && operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 1)))) 584169689Skan { 585169689Skan edge e; 586169689Skan tree arg; 587169689Skan 588169689Skan /* For NE_EXPR, we want to build an assignment result = arg where 589169689Skan arg is the PHI argument associated with the true edge. For 590169689Skan EQ_EXPR we want the PHI argument associated with the false edge. */ 591169689Skan e = (TREE_CODE (cond) == NE_EXPR ? true_edge : false_edge); 592169689Skan 593169689Skan /* Unfortunately, E may not reach BB (it may instead have gone to 594169689Skan OTHER_BLOCK). If that is the case, then we want the single outgoing 595169689Skan edge from OTHER_BLOCK which reaches BB and represents the desired 596169689Skan path from COND_BLOCK. */ 597169689Skan if (e->dest == middle_bb) 598169689Skan e = single_succ_edge (e->dest); 599169689Skan 600169689Skan /* Now we know the incoming edge to BB that has the argument for the 601169689Skan RHS of our new assignment statement. */ 602169689Skan if (e0 == e) 603169689Skan arg = arg0; 604169689Skan else 605169689Skan arg = arg1; 606169689Skan 607169689Skan replace_phi_edge_with_variable (cond_bb, e1, phi, arg); 608169689Skan 609169689Skan /* Note that we optimized this PHI. */ 610169689Skan return true; 611169689Skan } 612169689Skan return false; 613169689Skan} 614169689Skan 615169689Skan/* The function minmax_replacement does the main work of doing the minmax 616169689Skan replacement. Return true if the replacement is done. Otherwise return 617169689Skan false. 618169689Skan BB is the basic block where the replacement is going to be done on. ARG0 619169689Skan is argument 0 from the PHI. Likewise for ARG1. */ 620169689Skan 621169689Skanstatic bool 622169689Skanminmax_replacement (basic_block cond_bb, basic_block middle_bb, 623169689Skan edge e0, edge e1, tree phi, 624169689Skan tree arg0, tree arg1) 625169689Skan{ 626169689Skan tree result, type; 627169689Skan tree cond, new; 628169689Skan edge true_edge, false_edge; 629169689Skan enum tree_code cmp, minmax, ass_code; 630169689Skan tree smaller, larger, arg_true, arg_false; 631169689Skan block_stmt_iterator bsi, bsi_from; 632169689Skan 633169689Skan type = TREE_TYPE (PHI_RESULT (phi)); 634169689Skan 635169689Skan /* The optimization may be unsafe due to NaNs. */ 636169689Skan if (HONOR_NANS (TYPE_MODE (type))) 637169689Skan return false; 638169689Skan 639169689Skan cond = COND_EXPR_COND (last_stmt (cond_bb)); 640169689Skan cmp = TREE_CODE (cond); 641169689Skan result = PHI_RESULT (phi); 642169689Skan 643169689Skan /* This transformation is only valid for order comparisons. Record which 644169689Skan operand is smaller/larger if the result of the comparison is true. */ 645169689Skan if (cmp == LT_EXPR || cmp == LE_EXPR) 646169689Skan { 647169689Skan smaller = TREE_OPERAND (cond, 0); 648169689Skan larger = TREE_OPERAND (cond, 1); 649169689Skan } 650169689Skan else if (cmp == GT_EXPR || cmp == GE_EXPR) 651169689Skan { 652169689Skan smaller = TREE_OPERAND (cond, 1); 653169689Skan larger = TREE_OPERAND (cond, 0); 654169689Skan } 655169689Skan else 656169689Skan return false; 657169689Skan 658169689Skan /* We need to know which is the true edge and which is the false 659169689Skan edge so that we know if have abs or negative abs. */ 660169689Skan extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge); 661169689Skan 662169689Skan /* Forward the edges over the middle basic block. */ 663169689Skan if (true_edge->dest == middle_bb) 664169689Skan true_edge = EDGE_SUCC (true_edge->dest, 0); 665169689Skan if (false_edge->dest == middle_bb) 666169689Skan false_edge = EDGE_SUCC (false_edge->dest, 0); 667169689Skan 668169689Skan if (true_edge == e0) 669169689Skan { 670169689Skan gcc_assert (false_edge == e1); 671169689Skan arg_true = arg0; 672169689Skan arg_false = arg1; 673169689Skan } 674169689Skan else 675169689Skan { 676169689Skan gcc_assert (false_edge == e0); 677169689Skan gcc_assert (true_edge == e1); 678169689Skan arg_true = arg1; 679169689Skan arg_false = arg0; 680169689Skan } 681169689Skan 682169689Skan if (empty_block_p (middle_bb)) 683169689Skan { 684169689Skan if (operand_equal_for_phi_arg_p (arg_true, smaller) 685169689Skan && operand_equal_for_phi_arg_p (arg_false, larger)) 686169689Skan { 687169689Skan /* Case 688169689Skan 689169689Skan if (smaller < larger) 690169689Skan rslt = smaller; 691169689Skan else 692169689Skan rslt = larger; */ 693169689Skan minmax = MIN_EXPR; 694169689Skan } 695169689Skan else if (operand_equal_for_phi_arg_p (arg_false, smaller) 696169689Skan && operand_equal_for_phi_arg_p (arg_true, larger)) 697169689Skan minmax = MAX_EXPR; 698169689Skan else 699169689Skan return false; 700169689Skan } 701169689Skan else 702169689Skan { 703169689Skan /* Recognize the following case, assuming d <= u: 704169689Skan 705169689Skan if (a <= u) 706169689Skan b = MAX (a, d); 707169689Skan x = PHI <b, u> 708169689Skan 709169689Skan This is equivalent to 710169689Skan 711169689Skan b = MAX (a, d); 712169689Skan x = MIN (b, u); */ 713169689Skan 714169689Skan tree assign = last_and_only_stmt (middle_bb); 715169689Skan tree lhs, rhs, op0, op1, bound; 716169689Skan 717169689Skan if (!assign 718169689Skan || TREE_CODE (assign) != MODIFY_EXPR) 719169689Skan return false; 720169689Skan 721169689Skan lhs = TREE_OPERAND (assign, 0); 722169689Skan rhs = TREE_OPERAND (assign, 1); 723169689Skan ass_code = TREE_CODE (rhs); 724169689Skan if (ass_code != MAX_EXPR && ass_code != MIN_EXPR) 725169689Skan return false; 726169689Skan op0 = TREE_OPERAND (rhs, 0); 727169689Skan op1 = TREE_OPERAND (rhs, 1); 728169689Skan 729169689Skan if (true_edge->src == middle_bb) 730169689Skan { 731169689Skan /* We got here if the condition is true, i.e., SMALLER < LARGER. */ 732169689Skan if (!operand_equal_for_phi_arg_p (lhs, arg_true)) 733169689Skan return false; 734169689Skan 735169689Skan if (operand_equal_for_phi_arg_p (arg_false, larger)) 736169689Skan { 737169689Skan /* Case 738169689Skan 739169689Skan if (smaller < larger) 740169689Skan { 741169689Skan r' = MAX_EXPR (smaller, bound) 742169689Skan } 743169689Skan r = PHI <r', larger> --> to be turned to MIN_EXPR. */ 744169689Skan if (ass_code != MAX_EXPR) 745169689Skan return false; 746169689Skan 747169689Skan minmax = MIN_EXPR; 748169689Skan if (operand_equal_for_phi_arg_p (op0, smaller)) 749169689Skan bound = op1; 750169689Skan else if (operand_equal_for_phi_arg_p (op1, smaller)) 751169689Skan bound = op0; 752169689Skan else 753169689Skan return false; 754169689Skan 755169689Skan /* We need BOUND <= LARGER. */ 756169689Skan if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node, 757169689Skan bound, larger))) 758169689Skan return false; 759169689Skan } 760169689Skan else if (operand_equal_for_phi_arg_p (arg_false, smaller)) 761169689Skan { 762169689Skan /* Case 763169689Skan 764169689Skan if (smaller < larger) 765169689Skan { 766169689Skan r' = MIN_EXPR (larger, bound) 767169689Skan } 768169689Skan r = PHI <r', smaller> --> to be turned to MAX_EXPR. */ 769169689Skan if (ass_code != MIN_EXPR) 770169689Skan return false; 771169689Skan 772169689Skan minmax = MAX_EXPR; 773169689Skan if (operand_equal_for_phi_arg_p (op0, larger)) 774169689Skan bound = op1; 775169689Skan else if (operand_equal_for_phi_arg_p (op1, larger)) 776169689Skan bound = op0; 777169689Skan else 778169689Skan return false; 779169689Skan 780169689Skan /* We need BOUND >= SMALLER. */ 781169689Skan if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node, 782169689Skan bound, smaller))) 783169689Skan return false; 784169689Skan } 785169689Skan else 786169689Skan return false; 787169689Skan } 788169689Skan else 789169689Skan { 790169689Skan /* We got here if the condition is false, i.e., SMALLER > LARGER. */ 791169689Skan if (!operand_equal_for_phi_arg_p (lhs, arg_false)) 792169689Skan return false; 793169689Skan 794169689Skan if (operand_equal_for_phi_arg_p (arg_true, larger)) 795169689Skan { 796169689Skan /* Case 797169689Skan 798169689Skan if (smaller > larger) 799169689Skan { 800169689Skan r' = MIN_EXPR (smaller, bound) 801169689Skan } 802169689Skan r = PHI <r', larger> --> to be turned to MAX_EXPR. */ 803169689Skan if (ass_code != MIN_EXPR) 804169689Skan return false; 805169689Skan 806169689Skan minmax = MAX_EXPR; 807169689Skan if (operand_equal_for_phi_arg_p (op0, smaller)) 808169689Skan bound = op1; 809169689Skan else if (operand_equal_for_phi_arg_p (op1, smaller)) 810169689Skan bound = op0; 811169689Skan else 812169689Skan return false; 813169689Skan 814169689Skan /* We need BOUND >= LARGER. */ 815169689Skan if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node, 816169689Skan bound, larger))) 817169689Skan return false; 818169689Skan } 819169689Skan else if (operand_equal_for_phi_arg_p (arg_true, smaller)) 820169689Skan { 821169689Skan /* Case 822169689Skan 823169689Skan if (smaller > larger) 824169689Skan { 825169689Skan r' = MAX_EXPR (larger, bound) 826169689Skan } 827169689Skan r = PHI <r', smaller> --> to be turned to MIN_EXPR. */ 828169689Skan if (ass_code != MAX_EXPR) 829169689Skan return false; 830169689Skan 831169689Skan minmax = MIN_EXPR; 832169689Skan if (operand_equal_for_phi_arg_p (op0, larger)) 833169689Skan bound = op1; 834169689Skan else if (operand_equal_for_phi_arg_p (op1, larger)) 835169689Skan bound = op0; 836169689Skan else 837169689Skan return false; 838169689Skan 839169689Skan /* We need BOUND <= SMALLER. */ 840169689Skan if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node, 841169689Skan bound, smaller))) 842169689Skan return false; 843169689Skan } 844169689Skan else 845169689Skan return false; 846169689Skan } 847169689Skan 848169689Skan /* Move the statement from the middle block. */ 849169689Skan bsi = bsi_last (cond_bb); 850169689Skan bsi_from = bsi_last (middle_bb); 851169689Skan bsi_move_before (&bsi_from, &bsi); 852169689Skan } 853169689Skan 854169689Skan /* Emit the statement to compute min/max. */ 855169689Skan result = duplicate_ssa_name (PHI_RESULT (phi), NULL); 856169689Skan new = build2 (MODIFY_EXPR, type, result, 857169689Skan build2 (minmax, type, arg0, arg1)); 858169689Skan SSA_NAME_DEF_STMT (result) = new; 859169689Skan bsi = bsi_last (cond_bb); 860169689Skan bsi_insert_before (&bsi, new, BSI_NEW_STMT); 861169689Skan 862169689Skan replace_phi_edge_with_variable (cond_bb, e1, phi, result); 863169689Skan return true; 864169689Skan} 865169689Skan 866169689Skan/* The function absolute_replacement does the main work of doing the absolute 867169689Skan replacement. Return true if the replacement is done. Otherwise return 868169689Skan false. 869169689Skan bb is the basic block where the replacement is going to be done on. arg0 870169689Skan is argument 0 from the phi. Likewise for arg1. */ 871169689Skan 872169689Skanstatic bool 873169689Skanabs_replacement (basic_block cond_bb, basic_block middle_bb, 874169689Skan edge e0 ATTRIBUTE_UNUSED, edge e1, 875169689Skan tree phi, tree arg0, tree arg1) 876169689Skan{ 877169689Skan tree result; 878169689Skan tree new, cond; 879169689Skan block_stmt_iterator bsi; 880169689Skan edge true_edge, false_edge; 881169689Skan tree assign; 882169689Skan edge e; 883169689Skan tree rhs, lhs; 884169689Skan bool negate; 885169689Skan enum tree_code cond_code; 886169689Skan 887169689Skan /* If the type says honor signed zeros we cannot do this 888169689Skan optimization. */ 889169689Skan if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1)))) 890169689Skan return false; 891169689Skan 892169689Skan /* OTHER_BLOCK must have only one executable statement which must have the 893169689Skan form arg0 = -arg1 or arg1 = -arg0. */ 894169689Skan 895169689Skan assign = last_and_only_stmt (middle_bb); 896169689Skan /* If we did not find the proper negation assignment, then we can not 897169689Skan optimize. */ 898169689Skan if (assign == NULL) 899169689Skan return false; 900169689Skan 901169689Skan /* If we got here, then we have found the only executable statement 902169689Skan in OTHER_BLOCK. If it is anything other than arg = -arg1 or 903169689Skan arg1 = -arg0, then we can not optimize. */ 904169689Skan if (TREE_CODE (assign) != MODIFY_EXPR) 905169689Skan return false; 906169689Skan 907169689Skan lhs = TREE_OPERAND (assign, 0); 908169689Skan rhs = TREE_OPERAND (assign, 1); 909169689Skan 910169689Skan if (TREE_CODE (rhs) != NEGATE_EXPR) 911169689Skan return false; 912169689Skan 913169689Skan rhs = TREE_OPERAND (rhs, 0); 914169689Skan 915169689Skan /* The assignment has to be arg0 = -arg1 or arg1 = -arg0. */ 916169689Skan if (!(lhs == arg0 && rhs == arg1) 917169689Skan && !(lhs == arg1 && rhs == arg0)) 918169689Skan return false; 919169689Skan 920169689Skan cond = COND_EXPR_COND (last_stmt (cond_bb)); 921169689Skan result = PHI_RESULT (phi); 922169689Skan 923169689Skan /* Only relationals comparing arg[01] against zero are interesting. */ 924169689Skan cond_code = TREE_CODE (cond); 925169689Skan if (cond_code != GT_EXPR && cond_code != GE_EXPR 926169689Skan && cond_code != LT_EXPR && cond_code != LE_EXPR) 927169689Skan return false; 928169689Skan 929169689Skan /* Make sure the conditional is arg[01] OP y. */ 930169689Skan if (TREE_OPERAND (cond, 0) != rhs) 931169689Skan return false; 932169689Skan 933169689Skan if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1))) 934169689Skan ? real_zerop (TREE_OPERAND (cond, 1)) 935169689Skan : integer_zerop (TREE_OPERAND (cond, 1))) 936169689Skan ; 937169689Skan else 938169689Skan return false; 939169689Skan 940169689Skan /* We need to know which is the true edge and which is the false 941169689Skan edge so that we know if have abs or negative abs. */ 942169689Skan extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge); 943169689Skan 944169689Skan /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we 945169689Skan will need to negate the result. Similarly for LT_EXPR/LE_EXPR if 946169689Skan the false edge goes to OTHER_BLOCK. */ 947169689Skan if (cond_code == GT_EXPR || cond_code == GE_EXPR) 948169689Skan e = true_edge; 949169689Skan else 950169689Skan e = false_edge; 951169689Skan 952169689Skan if (e->dest == middle_bb) 953169689Skan negate = true; 954169689Skan else 955169689Skan negate = false; 956169689Skan 957169689Skan result = duplicate_ssa_name (result, NULL); 958169689Skan 959169689Skan if (negate) 960169689Skan { 961169689Skan tree tmp = create_tmp_var (TREE_TYPE (result), NULL); 962169689Skan add_referenced_var (tmp); 963169689Skan lhs = make_ssa_name (tmp, NULL); 964169689Skan } 965169689Skan else 966169689Skan lhs = result; 967169689Skan 968169689Skan /* Build the modify expression with abs expression. */ 969169689Skan new = build2 (MODIFY_EXPR, TREE_TYPE (lhs), 970169689Skan lhs, build1 (ABS_EXPR, TREE_TYPE (lhs), rhs)); 971169689Skan SSA_NAME_DEF_STMT (lhs) = new; 972169689Skan 973169689Skan bsi = bsi_last (cond_bb); 974169689Skan bsi_insert_before (&bsi, new, BSI_NEW_STMT); 975169689Skan 976169689Skan if (negate) 977169689Skan { 978169689Skan /* Get the right BSI. We want to insert after the recently 979169689Skan added ABS_EXPR statement (which we know is the first statement 980169689Skan in the block. */ 981169689Skan new = build2 (MODIFY_EXPR, TREE_TYPE (result), 982169689Skan result, build1 (NEGATE_EXPR, TREE_TYPE (lhs), lhs)); 983169689Skan SSA_NAME_DEF_STMT (result) = new; 984169689Skan 985169689Skan bsi_insert_after (&bsi, new, BSI_NEW_STMT); 986169689Skan } 987169689Skan 988169689Skan replace_phi_edge_with_variable (cond_bb, e1, phi, result); 989169689Skan 990169689Skan /* Note that we optimized this PHI. */ 991169689Skan return true; 992169689Skan} 993169689Skan 994169689Skan 995169689Skan/* Always do these optimizations if we have SSA 996169689Skan trees to work on. */ 997169689Skanstatic bool 998169689Skangate_phiopt (void) 999169689Skan{ 1000169689Skan return 1; 1001169689Skan} 1002169689Skan 1003169689Skanstruct tree_opt_pass pass_phiopt = 1004169689Skan{ 1005169689Skan "phiopt", /* name */ 1006169689Skan gate_phiopt, /* gate */ 1007169689Skan tree_ssa_phiopt, /* execute */ 1008169689Skan NULL, /* sub */ 1009169689Skan NULL, /* next */ 1010169689Skan 0, /* static_pass_number */ 1011169689Skan TV_TREE_PHIOPT, /* tv_id */ 1012169689Skan PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 1013169689Skan 0, /* properties_provided */ 1014169689Skan 0, /* properties_destroyed */ 1015169689Skan 0, /* todo_flags_start */ 1016169689Skan TODO_dump_func 1017169689Skan | TODO_ggc_collect 1018169689Skan | TODO_verify_ssa 1019169689Skan | TODO_verify_flow 1020169689Skan | TODO_verify_stmts, /* todo_flags_finish */ 1021169689Skan 0 /* letter */ 1022169689Skan}; 1023