1 /* Optimization of PHI nodes by converting them into straightline code. 2 Copyright (C) 2004-2018 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it 7 under the terms of the GNU General Public License as published by the 8 Free Software Foundation; either version 3, or (at your option) any 9 later version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT 12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20 #include "config.h" 21 #include "system.h" 22 #include "coretypes.h" 23 #include "backend.h" 24 #include "insn-codes.h" 25 #include "rtl.h" 26 #include "tree.h" 27 #include "gimple.h" 28 #include "cfghooks.h" 29 #include "tree-pass.h" 30 #include "ssa.h" 31 #include "optabs-tree.h" 32 #include "insn-config.h" 33 #include "gimple-pretty-print.h" 34 #include "fold-const.h" 35 #include "stor-layout.h" 36 #include "cfganal.h" 37 #include "gimplify.h" 38 #include "gimple-iterator.h" 39 #include "gimplify-me.h" 40 #include "tree-cfg.h" 41 #include "tree-dfa.h" 42 #include "domwalk.h" 43 #include "cfgloop.h" 44 #include "tree-data-ref.h" 45 #include "tree-scalar-evolution.h" 46 #include "tree-inline.h" 47 #include "params.h" 48 49 static unsigned int tree_ssa_phiopt_worker (bool, bool); 50 static bool conditional_replacement (basic_block, basic_block, 51 edge, edge, gphi *, tree, tree); 52 static gphi *factor_out_conditional_conversion (edge, edge, gphi *, tree, tree, 53 gimple *); 54 static int value_replacement (basic_block, basic_block, 55 edge, edge, gimple *, tree, tree); 56 static bool minmax_replacement (basic_block, basic_block, 57 edge, edge, gimple *, tree, tree); 58 static bool abs_replacement (basic_block, basic_block, 59 edge, edge, gimple *, tree, tree); 60 static bool cond_store_replacement (basic_block, basic_block, edge, edge, 61 hash_set<tree> *); 62 static bool cond_if_else_store_replacement (basic_block, basic_block, basic_block); 63 static hash_set<tree> * get_non_trapping (); 64 static void replace_phi_edge_with_variable (basic_block, edge, gimple *, tree); 65 static void hoist_adjacent_loads (basic_block, basic_block, 66 basic_block, basic_block); 67 static bool gate_hoist_loads (void); 68 69 /* This pass tries to transform conditional stores into unconditional 70 ones, enabling further simplifications with the simpler then and else 71 blocks. In particular it replaces this: 72 73 bb0: 74 if (cond) goto bb2; else goto bb1; 75 bb1: 76 *p = RHS; 77 bb2: 78 79 with 80 81 bb0: 82 if (cond) goto bb1; else goto bb2; 83 bb1: 84 condtmp' = *p; 85 bb2: 86 condtmp = PHI <RHS, condtmp'> 87 *p = condtmp; 88 89 This transformation can only be done under several constraints, 90 documented below. It also replaces: 91 92 bb0: 93 if (cond) goto bb2; else goto bb1; 94 bb1: 95 *p = RHS1; 96 goto bb3; 97 bb2: 98 *p = RHS2; 99 bb3: 100 101 with 102 103 bb0: 104 if (cond) goto bb3; else goto bb1; 105 bb1: 106 bb3: 107 condtmp = PHI <RHS1, RHS2> 108 *p = condtmp; */ 109 110 static unsigned int 111 tree_ssa_cs_elim (void) 112 { 113 unsigned todo; 114 /* ??? We are not interested in loop related info, but the following 115 will create it, ICEing as we didn't init loops with pre-headers. 116 An interfacing issue of find_data_references_in_bb. */ 117 loop_optimizer_init (LOOPS_NORMAL); 118 scev_initialize (); 119 todo = tree_ssa_phiopt_worker (true, false); 120 scev_finalize (); 121 loop_optimizer_finalize (); 122 return todo; 123 } 124 125 /* Return the singleton PHI in the SEQ of PHIs for edges E0 and E1. */ 126 127 static gphi * 128 single_non_singleton_phi_for_edges (gimple_seq seq, edge e0, edge e1) 129 { 130 gimple_stmt_iterator i; 131 gphi *phi = NULL; 132 if (gimple_seq_singleton_p (seq)) 133 return as_a <gphi *> (gsi_stmt (gsi_start (seq))); 134 for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i)) 135 { 136 gphi *p = as_a <gphi *> (gsi_stmt (i)); 137 /* If the PHI arguments are equal then we can skip this PHI. */ 138 if (operand_equal_for_phi_arg_p (gimple_phi_arg_def (p, e0->dest_idx), 139 gimple_phi_arg_def (p, e1->dest_idx))) 140 continue; 141 142 /* If we already have a PHI that has the two edge arguments are 143 different, then return it is not a singleton for these PHIs. */ 144 if (phi) 145 return NULL; 146 147 phi = p; 148 } 149 return phi; 150 } 151 152 /* The core routine of conditional store replacement and normal 153 phi optimizations. Both share much of the infrastructure in how 154 to match applicable basic block patterns. DO_STORE_ELIM is true 155 when we want to do conditional store replacement, false otherwise. 156 DO_HOIST_LOADS is true when we want to hoist adjacent loads out 157 of diamond control flow patterns, false otherwise. */ 158 static unsigned int 159 tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads) 160 { 161 basic_block bb; 162 basic_block *bb_order; 163 unsigned n, i; 164 bool cfgchanged = false; 165 hash_set<tree> *nontrap = 0; 166 167 if (do_store_elim) 168 /* Calculate the set of non-trapping memory accesses. */ 169 nontrap = get_non_trapping (); 170 171 /* Search every basic block for COND_EXPR we may be able to optimize. 172 173 We walk the blocks in order that guarantees that a block with 174 a single predecessor is processed before the predecessor. 175 This ensures that we collapse inner ifs before visiting the 176 outer ones, and also that we do not try to visit a removed 177 block. */ 178 bb_order = single_pred_before_succ_order (); 179 n = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; 180 181 for (i = 0; i < n; i++) 182 { 183 gimple *cond_stmt; 184 gphi *phi; 185 basic_block bb1, bb2; 186 edge e1, e2; 187 tree arg0, arg1; 188 189 bb = bb_order[i]; 190 191 cond_stmt = last_stmt (bb); 192 /* Check to see if the last statement is a GIMPLE_COND. */ 193 if (!cond_stmt 194 || gimple_code (cond_stmt) != GIMPLE_COND) 195 continue; 196 197 e1 = EDGE_SUCC (bb, 0); 198 bb1 = e1->dest; 199 e2 = EDGE_SUCC (bb, 1); 200 bb2 = e2->dest; 201 202 /* We cannot do the optimization on abnormal edges. */ 203 if ((e1->flags & EDGE_ABNORMAL) != 0 204 || (e2->flags & EDGE_ABNORMAL) != 0) 205 continue; 206 207 /* If either bb1's succ or bb2 or bb2's succ is non NULL. */ 208 if (EDGE_COUNT (bb1->succs) == 0 209 || bb2 == NULL 210 || EDGE_COUNT (bb2->succs) == 0) 211 continue; 212 213 /* Find the bb which is the fall through to the other. */ 214 if (EDGE_SUCC (bb1, 0)->dest == bb2) 215 ; 216 else if (EDGE_SUCC (bb2, 0)->dest == bb1) 217 { 218 std::swap (bb1, bb2); 219 std::swap (e1, e2); 220 } 221 else if (do_store_elim 222 && EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest) 223 { 224 basic_block bb3 = EDGE_SUCC (bb1, 0)->dest; 225 226 if (!single_succ_p (bb1) 227 || (EDGE_SUCC (bb1, 0)->flags & EDGE_FALLTHRU) == 0 228 || !single_succ_p (bb2) 229 || (EDGE_SUCC (bb2, 0)->flags & EDGE_FALLTHRU) == 0 230 || EDGE_COUNT (bb3->preds) != 2) 231 continue; 232 if (cond_if_else_store_replacement (bb1, bb2, bb3)) 233 cfgchanged = true; 234 continue; 235 } 236 else if (do_hoist_loads 237 && EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest) 238 { 239 basic_block bb3 = EDGE_SUCC (bb1, 0)->dest; 240 241 if (!FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (cond_stmt))) 242 && single_succ_p (bb1) 243 && single_succ_p (bb2) 244 && single_pred_p (bb1) 245 && single_pred_p (bb2) 246 && EDGE_COUNT (bb->succs) == 2 247 && EDGE_COUNT (bb3->preds) == 2 248 /* If one edge or the other is dominant, a conditional move 249 is likely to perform worse than the well-predicted branch. */ 250 && !predictable_edge_p (EDGE_SUCC (bb, 0)) 251 && !predictable_edge_p (EDGE_SUCC (bb, 1))) 252 hoist_adjacent_loads (bb, bb1, bb2, bb3); 253 continue; 254 } 255 else 256 continue; 257 258 e1 = EDGE_SUCC (bb1, 0); 259 260 /* Make sure that bb1 is just a fall through. */ 261 if (!single_succ_p (bb1) 262 || (e1->flags & EDGE_FALLTHRU) == 0) 263 continue; 264 265 /* Also make sure that bb1 only have one predecessor and that it 266 is bb. */ 267 if (!single_pred_p (bb1) 268 || single_pred (bb1) != bb) 269 continue; 270 271 if (do_store_elim) 272 { 273 /* bb1 is the middle block, bb2 the join block, bb the split block, 274 e1 the fallthrough edge from bb1 to bb2. We can't do the 275 optimization if the join block has more than two predecessors. */ 276 if (EDGE_COUNT (bb2->preds) > 2) 277 continue; 278 if (cond_store_replacement (bb1, bb2, e1, e2, nontrap)) 279 cfgchanged = true; 280 } 281 else 282 { 283 gimple_seq phis = phi_nodes (bb2); 284 gimple_stmt_iterator gsi; 285 bool candorest = true; 286 287 /* Value replacement can work with more than one PHI 288 so try that first. */ 289 for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi)) 290 { 291 phi = as_a <gphi *> (gsi_stmt (gsi)); 292 arg0 = gimple_phi_arg_def (phi, e1->dest_idx); 293 arg1 = gimple_phi_arg_def (phi, e2->dest_idx); 294 if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1) == 2) 295 { 296 candorest = false; 297 cfgchanged = true; 298 break; 299 } 300 } 301 302 if (!candorest) 303 continue; 304 305 phi = single_non_singleton_phi_for_edges (phis, e1, e2); 306 if (!phi) 307 continue; 308 309 arg0 = gimple_phi_arg_def (phi, e1->dest_idx); 310 arg1 = gimple_phi_arg_def (phi, e2->dest_idx); 311 312 /* Something is wrong if we cannot find the arguments in the PHI 313 node. */ 314 gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE); 315 316 gphi *newphi = factor_out_conditional_conversion (e1, e2, phi, 317 arg0, arg1, 318 cond_stmt); 319 if (newphi != NULL) 320 { 321 phi = newphi; 322 /* factor_out_conditional_conversion may create a new PHI in 323 BB2 and eliminate an existing PHI in BB2. Recompute values 324 that may be affected by that change. */ 325 arg0 = gimple_phi_arg_def (phi, e1->dest_idx); 326 arg1 = gimple_phi_arg_def (phi, e2->dest_idx); 327 gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE); 328 } 329 330 /* Do the replacement of conditional if it can be done. */ 331 if (conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) 332 cfgchanged = true; 333 else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) 334 cfgchanged = true; 335 else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) 336 cfgchanged = true; 337 } 338 } 339 340 free (bb_order); 341 342 if (do_store_elim) 343 delete nontrap; 344 /* If the CFG has changed, we should cleanup the CFG. */ 345 if (cfgchanged && do_store_elim) 346 { 347 /* In cond-store replacement we have added some loads on edges 348 and new VOPS (as we moved the store, and created a load). */ 349 gsi_commit_edge_inserts (); 350 return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals; 351 } 352 else if (cfgchanged) 353 return TODO_cleanup_cfg; 354 return 0; 355 } 356 357 /* Replace PHI node element whose edge is E in block BB with variable NEW. 358 Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK 359 is known to have two edges, one of which must reach BB). */ 360 361 static void 362 replace_phi_edge_with_variable (basic_block cond_block, 363 edge e, gimple *phi, tree new_tree) 364 { 365 basic_block bb = gimple_bb (phi); 366 basic_block block_to_remove; 367 gimple_stmt_iterator gsi; 368 369 /* Change the PHI argument to new. */ 370 SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new_tree); 371 372 /* Remove the empty basic block. */ 373 if (EDGE_SUCC (cond_block, 0)->dest == bb) 374 { 375 EDGE_SUCC (cond_block, 0)->flags |= EDGE_FALLTHRU; 376 EDGE_SUCC (cond_block, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); 377 EDGE_SUCC (cond_block, 0)->probability = profile_probability::always (); 378 379 block_to_remove = EDGE_SUCC (cond_block, 1)->dest; 380 } 381 else 382 { 383 EDGE_SUCC (cond_block, 1)->flags |= EDGE_FALLTHRU; 384 EDGE_SUCC (cond_block, 1)->flags 385 &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); 386 EDGE_SUCC (cond_block, 1)->probability = profile_probability::always (); 387 388 block_to_remove = EDGE_SUCC (cond_block, 0)->dest; 389 } 390 delete_basic_block (block_to_remove); 391 392 /* Eliminate the COND_EXPR at the end of COND_BLOCK. */ 393 gsi = gsi_last_bb (cond_block); 394 gsi_remove (&gsi, true); 395 396 if (dump_file && (dump_flags & TDF_DETAILS)) 397 fprintf (dump_file, 398 "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n", 399 cond_block->index, 400 bb->index); 401 } 402 403 /* PR66726: Factor conversion out of COND_EXPR. If the arguments of the PHI 404 stmt are CONVERT_STMT, factor out the conversion and perform the conversion 405 to the result of PHI stmt. COND_STMT is the controlling predicate. 406 Return the newly-created PHI, if any. */ 407 408 static gphi * 409 factor_out_conditional_conversion (edge e0, edge e1, gphi *phi, 410 tree arg0, tree arg1, gimple *cond_stmt) 411 { 412 gimple *arg0_def_stmt = NULL, *arg1_def_stmt = NULL, *new_stmt; 413 tree new_arg0 = NULL_TREE, new_arg1 = NULL_TREE; 414 tree temp, result; 415 gphi *newphi; 416 gimple_stmt_iterator gsi, gsi_for_def; 417 source_location locus = gimple_location (phi); 418 enum tree_code convert_code; 419 420 /* Handle only PHI statements with two arguments. TODO: If all 421 other arguments to PHI are INTEGER_CST or if their defining 422 statement have the same unary operation, we can handle more 423 than two arguments too. */ 424 if (gimple_phi_num_args (phi) != 2) 425 return NULL; 426 427 /* First canonicalize to simplify tests. */ 428 if (TREE_CODE (arg0) != SSA_NAME) 429 { 430 std::swap (arg0, arg1); 431 std::swap (e0, e1); 432 } 433 434 if (TREE_CODE (arg0) != SSA_NAME 435 || (TREE_CODE (arg1) != SSA_NAME 436 && TREE_CODE (arg1) != INTEGER_CST)) 437 return NULL; 438 439 /* Check if arg0 is an SSA_NAME and the stmt which defines arg0 is 440 a conversion. */ 441 arg0_def_stmt = SSA_NAME_DEF_STMT (arg0); 442 if (!gimple_assign_cast_p (arg0_def_stmt)) 443 return NULL; 444 445 /* Use the RHS as new_arg0. */ 446 convert_code = gimple_assign_rhs_code (arg0_def_stmt); 447 new_arg0 = gimple_assign_rhs1 (arg0_def_stmt); 448 if (convert_code == VIEW_CONVERT_EXPR) 449 { 450 new_arg0 = TREE_OPERAND (new_arg0, 0); 451 if (!is_gimple_reg_type (TREE_TYPE (new_arg0))) 452 return NULL; 453 } 454 455 if (TREE_CODE (arg1) == SSA_NAME) 456 { 457 /* Check if arg1 is an SSA_NAME and the stmt which defines arg1 458 is a conversion. */ 459 arg1_def_stmt = SSA_NAME_DEF_STMT (arg1); 460 if (!is_gimple_assign (arg1_def_stmt) 461 || gimple_assign_rhs_code (arg1_def_stmt) != convert_code) 462 return NULL; 463 464 /* Use the RHS as new_arg1. */ 465 new_arg1 = gimple_assign_rhs1 (arg1_def_stmt); 466 if (convert_code == VIEW_CONVERT_EXPR) 467 new_arg1 = TREE_OPERAND (new_arg1, 0); 468 } 469 else 470 { 471 /* If arg1 is an INTEGER_CST, fold it to new type. */ 472 if (INTEGRAL_TYPE_P (TREE_TYPE (new_arg0)) 473 && int_fits_type_p (arg1, TREE_TYPE (new_arg0))) 474 { 475 if (gimple_assign_cast_p (arg0_def_stmt)) 476 { 477 /* For the INTEGER_CST case, we are just moving the 478 conversion from one place to another, which can often 479 hurt as the conversion moves further away from the 480 statement that computes the value. So, perform this 481 only if new_arg0 is an operand of COND_STMT, or 482 if arg0_def_stmt is the only non-debug stmt in 483 its basic block, because then it is possible this 484 could enable further optimizations (minmax replacement 485 etc.). See PR71016. */ 486 if (new_arg0 != gimple_cond_lhs (cond_stmt) 487 && new_arg0 != gimple_cond_rhs (cond_stmt) 488 && gimple_bb (arg0_def_stmt) == e0->src) 489 { 490 gsi = gsi_for_stmt (arg0_def_stmt); 491 gsi_prev_nondebug (&gsi); 492 if (!gsi_end_p (gsi)) 493 return NULL; 494 gsi = gsi_for_stmt (arg0_def_stmt); 495 gsi_next_nondebug (&gsi); 496 if (!gsi_end_p (gsi)) 497 return NULL; 498 } 499 new_arg1 = fold_convert (TREE_TYPE (new_arg0), arg1); 500 } 501 else 502 return NULL; 503 } 504 else 505 return NULL; 506 } 507 508 /* If arg0/arg1 have > 1 use, then this transformation actually increases 509 the number of expressions evaluated at runtime. */ 510 if (!has_single_use (arg0) 511 || (arg1_def_stmt && !has_single_use (arg1))) 512 return NULL; 513 514 /* If types of new_arg0 and new_arg1 are different bailout. */ 515 if (!types_compatible_p (TREE_TYPE (new_arg0), TREE_TYPE (new_arg1))) 516 return NULL; 517 518 /* Create a new PHI stmt. */ 519 result = PHI_RESULT (phi); 520 temp = make_ssa_name (TREE_TYPE (new_arg0), NULL); 521 newphi = create_phi_node (temp, gimple_bb (phi)); 522 523 if (dump_file && (dump_flags & TDF_DETAILS)) 524 { 525 fprintf (dump_file, "PHI "); 526 print_generic_expr (dump_file, gimple_phi_result (phi)); 527 fprintf (dump_file, 528 " changed to factor conversion out from COND_EXPR.\n"); 529 fprintf (dump_file, "New stmt with CAST that defines "); 530 print_generic_expr (dump_file, result); 531 fprintf (dump_file, ".\n"); 532 } 533 534 /* Remove the old cast(s) that has single use. */ 535 gsi_for_def = gsi_for_stmt (arg0_def_stmt); 536 gsi_remove (&gsi_for_def, true); 537 release_defs (arg0_def_stmt); 538 539 if (arg1_def_stmt) 540 { 541 gsi_for_def = gsi_for_stmt (arg1_def_stmt); 542 gsi_remove (&gsi_for_def, true); 543 release_defs (arg1_def_stmt); 544 } 545 546 add_phi_arg (newphi, new_arg0, e0, locus); 547 add_phi_arg (newphi, new_arg1, e1, locus); 548 549 /* Create the conversion stmt and insert it. */ 550 if (convert_code == VIEW_CONVERT_EXPR) 551 { 552 temp = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (result), temp); 553 new_stmt = gimple_build_assign (result, temp); 554 } 555 else 556 new_stmt = gimple_build_assign (result, convert_code, temp); 557 gsi = gsi_after_labels (gimple_bb (phi)); 558 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT); 559 560 /* Remove the original PHI stmt. */ 561 gsi = gsi_for_stmt (phi); 562 gsi_remove (&gsi, true); 563 return newphi; 564 } 565 566 /* The function conditional_replacement does the main work of doing the 567 conditional replacement. Return true if the replacement is done. 568 Otherwise return false. 569 BB is the basic block where the replacement is going to be done on. ARG0 570 is argument 0 from PHI. Likewise for ARG1. */ 571 572 static bool 573 conditional_replacement (basic_block cond_bb, basic_block middle_bb, 574 edge e0, edge e1, gphi *phi, 575 tree arg0, tree arg1) 576 { 577 tree result; 578 gimple *stmt; 579 gassign *new_stmt; 580 tree cond; 581 gimple_stmt_iterator gsi; 582 edge true_edge, false_edge; 583 tree new_var, new_var2; 584 bool neg; 585 586 /* FIXME: Gimplification of complex type is too hard for now. */ 587 /* We aren't prepared to handle vectors either (and it is a question 588 if it would be worthwhile anyway). */ 589 if (!(INTEGRAL_TYPE_P (TREE_TYPE (arg0)) 590 || POINTER_TYPE_P (TREE_TYPE (arg0))) 591 || !(INTEGRAL_TYPE_P (TREE_TYPE (arg1)) 592 || POINTER_TYPE_P (TREE_TYPE (arg1)))) 593 return false; 594 595 /* The PHI arguments have the constants 0 and 1, or 0 and -1, then 596 convert it to the conditional. */ 597 if ((integer_zerop (arg0) && integer_onep (arg1)) 598 || (integer_zerop (arg1) && integer_onep (arg0))) 599 neg = false; 600 else if ((integer_zerop (arg0) && integer_all_onesp (arg1)) 601 || (integer_zerop (arg1) && integer_all_onesp (arg0))) 602 neg = true; 603 else 604 return false; 605 606 if (!empty_block_p (middle_bb)) 607 return false; 608 609 /* At this point we know we have a GIMPLE_COND with two successors. 610 One successor is BB, the other successor is an empty block which 611 falls through into BB. 612 613 There is a single PHI node at the join point (BB) and its arguments 614 are constants (0, 1) or (0, -1). 615 616 So, given the condition COND, and the two PHI arguments, we can 617 rewrite this PHI into non-branching code: 618 619 dest = (COND) or dest = COND' 620 621 We use the condition as-is if the argument associated with the 622 true edge has the value one or the argument associated with the 623 false edge as the value zero. Note that those conditions are not 624 the same since only one of the outgoing edges from the GIMPLE_COND 625 will directly reach BB and thus be associated with an argument. */ 626 627 stmt = last_stmt (cond_bb); 628 result = PHI_RESULT (phi); 629 630 /* To handle special cases like floating point comparison, it is easier and 631 less error-prone to build a tree and gimplify it on the fly though it is 632 less efficient. */ 633 cond = fold_build2_loc (gimple_location (stmt), 634 gimple_cond_code (stmt), boolean_type_node, 635 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); 636 637 /* We need to know which is the true edge and which is the false 638 edge so that we know when to invert the condition below. */ 639 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge); 640 if ((e0 == true_edge && integer_zerop (arg0)) 641 || (e0 == false_edge && !integer_zerop (arg0)) 642 || (e1 == true_edge && integer_zerop (arg1)) 643 || (e1 == false_edge && !integer_zerop (arg1))) 644 cond = fold_build1_loc (gimple_location (stmt), 645 TRUTH_NOT_EXPR, TREE_TYPE (cond), cond); 646 647 if (neg) 648 { 649 cond = fold_convert_loc (gimple_location (stmt), 650 TREE_TYPE (result), cond); 651 cond = fold_build1_loc (gimple_location (stmt), 652 NEGATE_EXPR, TREE_TYPE (cond), cond); 653 } 654 655 /* Insert our new statements at the end of conditional block before the 656 COND_STMT. */ 657 gsi = gsi_for_stmt (stmt); 658 new_var = force_gimple_operand_gsi (&gsi, cond, true, NULL, true, 659 GSI_SAME_STMT); 660 661 if (!useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (new_var))) 662 { 663 source_location locus_0, locus_1; 664 665 new_var2 = make_ssa_name (TREE_TYPE (result)); 666 new_stmt = gimple_build_assign (new_var2, CONVERT_EXPR, new_var); 667 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT); 668 new_var = new_var2; 669 670 /* Set the locus to the first argument, unless is doesn't have one. */ 671 locus_0 = gimple_phi_arg_location (phi, 0); 672 locus_1 = gimple_phi_arg_location (phi, 1); 673 if (locus_0 == UNKNOWN_LOCATION) 674 locus_0 = locus_1; 675 gimple_set_location (new_stmt, locus_0); 676 } 677 678 replace_phi_edge_with_variable (cond_bb, e1, phi, new_var); 679 680 /* Note that we optimized this PHI. */ 681 return true; 682 } 683 684 /* Update *ARG which is defined in STMT so that it contains the 685 computed value if that seems profitable. Return true if the 686 statement is made dead by that rewriting. */ 687 688 static bool 689 jump_function_from_stmt (tree *arg, gimple *stmt) 690 { 691 enum tree_code code = gimple_assign_rhs_code (stmt); 692 if (code == ADDR_EXPR) 693 { 694 /* For arg = &p->i transform it to p, if possible. */ 695 tree rhs1 = gimple_assign_rhs1 (stmt); 696 poly_int64 offset; 697 tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs1, 0), 698 &offset); 699 if (tem 700 && TREE_CODE (tem) == MEM_REF 701 && known_eq (mem_ref_offset (tem) + offset, 0)) 702 { 703 *arg = TREE_OPERAND (tem, 0); 704 return true; 705 } 706 } 707 /* TODO: Much like IPA-CP jump-functions we want to handle constant 708 additions symbolically here, and we'd need to update the comparison 709 code that compares the arg + cst tuples in our caller. For now the 710 code above exactly handles the VEC_BASE pattern from vec.h. */ 711 return false; 712 } 713 714 /* RHS is a source argument in a BIT_AND_EXPR which feeds a conditional 715 of the form SSA_NAME NE 0. 716 717 If RHS is fed by a simple EQ_EXPR comparison of two values, see if 718 the two input values of the EQ_EXPR match arg0 and arg1. 719 720 If so update *code and return TRUE. Otherwise return FALSE. */ 721 722 static bool 723 rhs_is_fed_for_value_replacement (const_tree arg0, const_tree arg1, 724 enum tree_code *code, const_tree rhs) 725 { 726 /* Obviously if RHS is not an SSA_NAME, we can't look at the defining 727 statement. */ 728 if (TREE_CODE (rhs) == SSA_NAME) 729 { 730 gimple *def1 = SSA_NAME_DEF_STMT (rhs); 731 732 /* Verify the defining statement has an EQ_EXPR on the RHS. */ 733 if (is_gimple_assign (def1) && gimple_assign_rhs_code (def1) == EQ_EXPR) 734 { 735 /* Finally verify the source operands of the EQ_EXPR are equal 736 to arg0 and arg1. */ 737 tree op0 = gimple_assign_rhs1 (def1); 738 tree op1 = gimple_assign_rhs2 (def1); 739 if ((operand_equal_for_phi_arg_p (arg0, op0) 740 && operand_equal_for_phi_arg_p (arg1, op1)) 741 || (operand_equal_for_phi_arg_p (arg0, op1) 742 && operand_equal_for_phi_arg_p (arg1, op0))) 743 { 744 /* We will perform the optimization. */ 745 *code = gimple_assign_rhs_code (def1); 746 return true; 747 } 748 } 749 } 750 return false; 751 } 752 753 /* Return TRUE if arg0/arg1 are equal to the rhs/lhs or lhs/rhs of COND. 754 755 Also return TRUE if arg0/arg1 are equal to the source arguments of a 756 an EQ comparison feeding a BIT_AND_EXPR which feeds COND. 757 758 Return FALSE otherwise. */ 759 760 static bool 761 operand_equal_for_value_replacement (const_tree arg0, const_tree arg1, 762 enum tree_code *code, gimple *cond) 763 { 764 gimple *def; 765 tree lhs = gimple_cond_lhs (cond); 766 tree rhs = gimple_cond_rhs (cond); 767 768 if ((operand_equal_for_phi_arg_p (arg0, lhs) 769 && operand_equal_for_phi_arg_p (arg1, rhs)) 770 || (operand_equal_for_phi_arg_p (arg1, lhs) 771 && operand_equal_for_phi_arg_p (arg0, rhs))) 772 return true; 773 774 /* Now handle more complex case where we have an EQ comparison 775 which feeds a BIT_AND_EXPR which feeds COND. 776 777 First verify that COND is of the form SSA_NAME NE 0. */ 778 if (*code != NE_EXPR || !integer_zerop (rhs) 779 || TREE_CODE (lhs) != SSA_NAME) 780 return false; 781 782 /* Now ensure that SSA_NAME is set by a BIT_AND_EXPR. */ 783 def = SSA_NAME_DEF_STMT (lhs); 784 if (!is_gimple_assign (def) || gimple_assign_rhs_code (def) != BIT_AND_EXPR) 785 return false; 786 787 /* Now verify arg0/arg1 correspond to the source arguments of an 788 EQ comparison feeding the BIT_AND_EXPR. */ 789 790 tree tmp = gimple_assign_rhs1 (def); 791 if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp)) 792 return true; 793 794 tmp = gimple_assign_rhs2 (def); 795 if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp)) 796 return true; 797 798 return false; 799 } 800 801 /* Returns true if ARG is a neutral element for operation CODE 802 on the RIGHT side. */ 803 804 static bool 805 neutral_element_p (tree_code code, tree arg, bool right) 806 { 807 switch (code) 808 { 809 case PLUS_EXPR: 810 case BIT_IOR_EXPR: 811 case BIT_XOR_EXPR: 812 return integer_zerop (arg); 813 814 case LROTATE_EXPR: 815 case RROTATE_EXPR: 816 case LSHIFT_EXPR: 817 case RSHIFT_EXPR: 818 case MINUS_EXPR: 819 case POINTER_PLUS_EXPR: 820 return right && integer_zerop (arg); 821 822 case MULT_EXPR: 823 return integer_onep (arg); 824 825 case TRUNC_DIV_EXPR: 826 case CEIL_DIV_EXPR: 827 case FLOOR_DIV_EXPR: 828 case ROUND_DIV_EXPR: 829 case EXACT_DIV_EXPR: 830 return right && integer_onep (arg); 831 832 case BIT_AND_EXPR: 833 return integer_all_onesp (arg); 834 835 default: 836 return false; 837 } 838 } 839 840 /* Returns true if ARG is an absorbing element for operation CODE. */ 841 842 static bool 843 absorbing_element_p (tree_code code, tree arg, bool right, tree rval) 844 { 845 switch (code) 846 { 847 case BIT_IOR_EXPR: 848 return integer_all_onesp (arg); 849 850 case MULT_EXPR: 851 case BIT_AND_EXPR: 852 return integer_zerop (arg); 853 854 case LSHIFT_EXPR: 855 case RSHIFT_EXPR: 856 case LROTATE_EXPR: 857 case RROTATE_EXPR: 858 return !right && integer_zerop (arg); 859 860 case TRUNC_DIV_EXPR: 861 case CEIL_DIV_EXPR: 862 case FLOOR_DIV_EXPR: 863 case ROUND_DIV_EXPR: 864 case EXACT_DIV_EXPR: 865 case TRUNC_MOD_EXPR: 866 case CEIL_MOD_EXPR: 867 case FLOOR_MOD_EXPR: 868 case ROUND_MOD_EXPR: 869 return (!right 870 && integer_zerop (arg) 871 && tree_single_nonzero_warnv_p (rval, NULL)); 872 873 default: 874 return false; 875 } 876 } 877 878 /* The function value_replacement does the main work of doing the value 879 replacement. Return non-zero if the replacement is done. Otherwise return 880 0. If we remove the middle basic block, return 2. 881 BB is the basic block where the replacement is going to be done on. ARG0 882 is argument 0 from the PHI. Likewise for ARG1. */ 883 884 static int 885 value_replacement (basic_block cond_bb, basic_block middle_bb, 886 edge e0, edge e1, gimple *phi, 887 tree arg0, tree arg1) 888 { 889 gimple_stmt_iterator gsi; 890 gimple *cond; 891 edge true_edge, false_edge; 892 enum tree_code code; 893 bool emtpy_or_with_defined_p = true; 894 895 /* If the type says honor signed zeros we cannot do this 896 optimization. */ 897 if (HONOR_SIGNED_ZEROS (arg1)) 898 return 0; 899 900 /* If there is a statement in MIDDLE_BB that defines one of the PHI 901 arguments, then adjust arg0 or arg1. */ 902 gsi = gsi_start_nondebug_after_labels_bb (middle_bb); 903 while (!gsi_end_p (gsi)) 904 { 905 gimple *stmt = gsi_stmt (gsi); 906 tree lhs; 907 gsi_next_nondebug (&gsi); 908 if (!is_gimple_assign (stmt)) 909 { 910 emtpy_or_with_defined_p = false; 911 continue; 912 } 913 /* Now try to adjust arg0 or arg1 according to the computation 914 in the statement. */ 915 lhs = gimple_assign_lhs (stmt); 916 if (!(lhs == arg0 917 && jump_function_from_stmt (&arg0, stmt)) 918 || (lhs == arg1 919 && jump_function_from_stmt (&arg1, stmt))) 920 emtpy_or_with_defined_p = false; 921 } 922 923 cond = last_stmt (cond_bb); 924 code = gimple_cond_code (cond); 925 926 /* This transformation is only valid for equality comparisons. */ 927 if (code != NE_EXPR && code != EQ_EXPR) 928 return 0; 929 930 /* We need to know which is the true edge and which is the false 931 edge so that we know if have abs or negative abs. */ 932 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge); 933 934 /* At this point we know we have a COND_EXPR with two successors. 935 One successor is BB, the other successor is an empty block which 936 falls through into BB. 937 938 The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR. 939 940 There is a single PHI node at the join point (BB) with two arguments. 941 942 We now need to verify that the two arguments in the PHI node match 943 the two arguments to the equality comparison. */ 944 945 if (operand_equal_for_value_replacement (arg0, arg1, &code, cond)) 946 { 947 edge e; 948 tree arg; 949 950 /* For NE_EXPR, we want to build an assignment result = arg where 951 arg is the PHI argument associated with the true edge. For 952 EQ_EXPR we want the PHI argument associated with the false edge. */ 953 e = (code == NE_EXPR ? true_edge : false_edge); 954 955 /* Unfortunately, E may not reach BB (it may instead have gone to 956 OTHER_BLOCK). If that is the case, then we want the single outgoing 957 edge from OTHER_BLOCK which reaches BB and represents the desired 958 path from COND_BLOCK. */ 959 if (e->dest == middle_bb) 960 e = single_succ_edge (e->dest); 961 962 /* Now we know the incoming edge to BB that has the argument for the 963 RHS of our new assignment statement. */ 964 if (e0 == e) 965 arg = arg0; 966 else 967 arg = arg1; 968 969 /* If the middle basic block was empty or is defining the 970 PHI arguments and this is a single phi where the args are different 971 for the edges e0 and e1 then we can remove the middle basic block. */ 972 if (emtpy_or_with_defined_p 973 && single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)), 974 e0, e1) == phi) 975 { 976 replace_phi_edge_with_variable (cond_bb, e1, phi, arg); 977 /* Note that we optimized this PHI. */ 978 return 2; 979 } 980 else 981 { 982 /* Replace the PHI arguments with arg. */ 983 SET_PHI_ARG_DEF (phi, e0->dest_idx, arg); 984 SET_PHI_ARG_DEF (phi, e1->dest_idx, arg); 985 if (dump_file && (dump_flags & TDF_DETAILS)) 986 { 987 fprintf (dump_file, "PHI "); 988 print_generic_expr (dump_file, gimple_phi_result (phi)); 989 fprintf (dump_file, " reduced for COND_EXPR in block %d to ", 990 cond_bb->index); 991 print_generic_expr (dump_file, arg); 992 fprintf (dump_file, ".\n"); 993 } 994 return 1; 995 } 996 997 } 998 999 /* Now optimize (x != 0) ? x + y : y to just x + y. */ 1000 gsi = gsi_last_nondebug_bb (middle_bb); 1001 if (gsi_end_p (gsi)) 1002 return 0; 1003 1004 gimple *assign = gsi_stmt (gsi); 1005 if (!is_gimple_assign (assign) 1006 || gimple_assign_rhs_class (assign) != GIMPLE_BINARY_RHS 1007 || (!INTEGRAL_TYPE_P (TREE_TYPE (arg0)) 1008 && !POINTER_TYPE_P (TREE_TYPE (arg0)))) 1009 return 0; 1010 1011 /* Punt if there are (degenerate) PHIs in middle_bb, there should not be. */ 1012 if (!gimple_seq_empty_p (phi_nodes (middle_bb))) 1013 return 0; 1014 1015 /* Allow up to 2 cheap preparation statements that prepare argument 1016 for assign, e.g.: 1017 if (y_4 != 0) 1018 goto <bb 3>; 1019 else 1020 goto <bb 4>; 1021 <bb 3>: 1022 _1 = (int) y_4; 1023 iftmp.0_6 = x_5(D) r<< _1; 1024 <bb 4>: 1025 # iftmp.0_2 = PHI <iftmp.0_6(3), x_5(D)(2)> 1026 or: 1027 if (y_3(D) == 0) 1028 goto <bb 4>; 1029 else 1030 goto <bb 3>; 1031 <bb 3>: 1032 y_4 = y_3(D) & 31; 1033 _1 = (int) y_4; 1034 _6 = x_5(D) r<< _1; 1035 <bb 4>: 1036 # _2 = PHI <x_5(D)(2), _6(3)> */ 1037 gimple *prep_stmt[2] = { NULL, NULL }; 1038 int prep_cnt; 1039 for (prep_cnt = 0; ; prep_cnt++) 1040 { 1041 gsi_prev_nondebug (&gsi); 1042 if (gsi_end_p (gsi)) 1043 break; 1044 1045 gimple *g = gsi_stmt (gsi); 1046 if (gimple_code (g) == GIMPLE_LABEL) 1047 break; 1048 1049 if (prep_cnt == 2 || !is_gimple_assign (g)) 1050 return 0; 1051 1052 tree lhs = gimple_assign_lhs (g); 1053 tree rhs1 = gimple_assign_rhs1 (g); 1054 use_operand_p use_p; 1055 gimple *use_stmt; 1056 if (TREE_CODE (lhs) != SSA_NAME 1057 || TREE_CODE (rhs1) != SSA_NAME 1058 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 1059 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1)) 1060 || !single_imm_use (lhs, &use_p, &use_stmt) 1061 || use_stmt != (prep_cnt ? prep_stmt[prep_cnt - 1] : assign)) 1062 return 0; 1063 switch (gimple_assign_rhs_code (g)) 1064 { 1065 CASE_CONVERT: 1066 break; 1067 case PLUS_EXPR: 1068 case BIT_AND_EXPR: 1069 case BIT_IOR_EXPR: 1070 case BIT_XOR_EXPR: 1071 if (TREE_CODE (gimple_assign_rhs2 (g)) != INTEGER_CST) 1072 return 0; 1073 break; 1074 default: 1075 return 0; 1076 } 1077 prep_stmt[prep_cnt] = g; 1078 } 1079 1080 /* Only transform if it removes the condition. */ 1081 if (!single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)), e0, e1)) 1082 return 0; 1083 1084 /* Size-wise, this is always profitable. */ 1085 if (optimize_bb_for_speed_p (cond_bb) 1086 /* The special case is useless if it has a low probability. */ 1087 && profile_status_for_fn (cfun) != PROFILE_ABSENT 1088 && EDGE_PRED (middle_bb, 0)->probability < profile_probability::even () 1089 /* If assign is cheap, there is no point avoiding it. */ 1090 && estimate_num_insns (bb_seq (middle_bb), &eni_time_weights) 1091 >= 3 * estimate_num_insns (cond, &eni_time_weights)) 1092 return 0; 1093 1094 tree lhs = gimple_assign_lhs (assign); 1095 tree rhs1 = gimple_assign_rhs1 (assign); 1096 tree rhs2 = gimple_assign_rhs2 (assign); 1097 enum tree_code code_def = gimple_assign_rhs_code (assign); 1098 tree cond_lhs = gimple_cond_lhs (cond); 1099 tree cond_rhs = gimple_cond_rhs (cond); 1100 1101 /* Propagate the cond_rhs constant through preparation stmts, 1102 make sure UB isn't invoked while doing that. */ 1103 for (int i = prep_cnt - 1; i >= 0; --i) 1104 { 1105 gimple *g = prep_stmt[i]; 1106 tree grhs1 = gimple_assign_rhs1 (g); 1107 if (!operand_equal_for_phi_arg_p (cond_lhs, grhs1)) 1108 return 0; 1109 cond_lhs = gimple_assign_lhs (g); 1110 cond_rhs = fold_convert (TREE_TYPE (grhs1), cond_rhs); 1111 if (TREE_CODE (cond_rhs) != INTEGER_CST 1112 || TREE_OVERFLOW (cond_rhs)) 1113 return 0; 1114 if (gimple_assign_rhs_class (g) == GIMPLE_BINARY_RHS) 1115 { 1116 cond_rhs = int_const_binop (gimple_assign_rhs_code (g), cond_rhs, 1117 gimple_assign_rhs2 (g)); 1118 if (TREE_OVERFLOW (cond_rhs)) 1119 return 0; 1120 } 1121 cond_rhs = fold_convert (TREE_TYPE (cond_lhs), cond_rhs); 1122 if (TREE_CODE (cond_rhs) != INTEGER_CST 1123 || TREE_OVERFLOW (cond_rhs)) 1124 return 0; 1125 } 1126 1127 if (((code == NE_EXPR && e1 == false_edge) 1128 || (code == EQ_EXPR && e1 == true_edge)) 1129 && arg0 == lhs 1130 && ((arg1 == rhs1 1131 && operand_equal_for_phi_arg_p (rhs2, cond_lhs) 1132 && neutral_element_p (code_def, cond_rhs, true)) 1133 || (arg1 == rhs2 1134 && operand_equal_for_phi_arg_p (rhs1, cond_lhs) 1135 && neutral_element_p (code_def, cond_rhs, false)) 1136 || (operand_equal_for_phi_arg_p (arg1, cond_rhs) 1137 && ((operand_equal_for_phi_arg_p (rhs2, cond_lhs) 1138 && absorbing_element_p (code_def, cond_rhs, true, rhs2)) 1139 || (operand_equal_for_phi_arg_p (rhs1, cond_lhs) 1140 && absorbing_element_p (code_def, 1141 cond_rhs, false, rhs2)))))) 1142 { 1143 gsi = gsi_for_stmt (cond); 1144 /* Moving ASSIGN might change VR of lhs, e.g. when moving u_6 1145 def-stmt in: 1146 if (n_5 != 0) 1147 goto <bb 3>; 1148 else 1149 goto <bb 4>; 1150 1151 <bb 3>: 1152 # RANGE [0, 4294967294] 1153 u_6 = n_5 + 4294967295; 1154 1155 <bb 4>: 1156 # u_3 = PHI <u_6(3), 4294967295(2)> */ 1157 reset_flow_sensitive_info (lhs); 1158 if (INTEGRAL_TYPE_P (TREE_TYPE (lhs))) 1159 { 1160 /* If available, we can use VR of phi result at least. */ 1161 tree phires = gimple_phi_result (phi); 1162 struct range_info_def *phires_range_info 1163 = SSA_NAME_RANGE_INFO (phires); 1164 if (phires_range_info) 1165 duplicate_ssa_name_range_info (lhs, SSA_NAME_RANGE_TYPE (phires), 1166 phires_range_info); 1167 } 1168 gimple_stmt_iterator gsi_from; 1169 for (int i = prep_cnt - 1; i >= 0; --i) 1170 { 1171 tree plhs = gimple_assign_lhs (prep_stmt[i]); 1172 reset_flow_sensitive_info (plhs); 1173 gsi_from = gsi_for_stmt (prep_stmt[i]); 1174 gsi_move_before (&gsi_from, &gsi); 1175 } 1176 gsi_from = gsi_for_stmt (assign); 1177 gsi_move_before (&gsi_from, &gsi); 1178 replace_phi_edge_with_variable (cond_bb, e1, phi, lhs); 1179 return 2; 1180 } 1181 1182 return 0; 1183 } 1184 1185 /* The function minmax_replacement does the main work of doing the minmax 1186 replacement. Return true if the replacement is done. Otherwise return 1187 false. 1188 BB is the basic block where the replacement is going to be done on. ARG0 1189 is argument 0 from the PHI. Likewise for ARG1. */ 1190 1191 static bool 1192 minmax_replacement (basic_block cond_bb, basic_block middle_bb, 1193 edge e0, edge e1, gimple *phi, 1194 tree arg0, tree arg1) 1195 { 1196 tree result, type; 1197 gcond *cond; 1198 gassign *new_stmt; 1199 edge true_edge, false_edge; 1200 enum tree_code cmp, minmax, ass_code; 1201 tree smaller, alt_smaller, larger, alt_larger, arg_true, arg_false; 1202 gimple_stmt_iterator gsi, gsi_from; 1203 1204 type = TREE_TYPE (PHI_RESULT (phi)); 1205 1206 /* The optimization may be unsafe due to NaNs. */ 1207 if (HONOR_NANS (type) || HONOR_SIGNED_ZEROS (type)) 1208 return false; 1209 1210 cond = as_a <gcond *> (last_stmt (cond_bb)); 1211 cmp = gimple_cond_code (cond); 1212 1213 /* This transformation is only valid for order comparisons. Record which 1214 operand is smaller/larger if the result of the comparison is true. */ 1215 alt_smaller = NULL_TREE; 1216 alt_larger = NULL_TREE; 1217 if (cmp == LT_EXPR || cmp == LE_EXPR) 1218 { 1219 smaller = gimple_cond_lhs (cond); 1220 larger = gimple_cond_rhs (cond); 1221 /* If we have smaller < CST it is equivalent to smaller <= CST-1. 1222 Likewise smaller <= CST is equivalent to smaller < CST+1. */ 1223 if (TREE_CODE (larger) == INTEGER_CST) 1224 { 1225 if (cmp == LT_EXPR) 1226 { 1227 bool overflow; 1228 wide_int alt = wi::sub (wi::to_wide (larger), 1, 1229 TYPE_SIGN (TREE_TYPE (larger)), 1230 &overflow); 1231 if (! overflow) 1232 alt_larger = wide_int_to_tree (TREE_TYPE (larger), alt); 1233 } 1234 else 1235 { 1236 bool overflow; 1237 wide_int alt = wi::add (wi::to_wide (larger), 1, 1238 TYPE_SIGN (TREE_TYPE (larger)), 1239 &overflow); 1240 if (! overflow) 1241 alt_larger = wide_int_to_tree (TREE_TYPE (larger), alt); 1242 } 1243 } 1244 } 1245 else if (cmp == GT_EXPR || cmp == GE_EXPR) 1246 { 1247 smaller = gimple_cond_rhs (cond); 1248 larger = gimple_cond_lhs (cond); 1249 /* If we have larger > CST it is equivalent to larger >= CST+1. 1250 Likewise larger >= CST is equivalent to larger > CST-1. */ 1251 if (TREE_CODE (smaller) == INTEGER_CST) 1252 { 1253 if (cmp == GT_EXPR) 1254 { 1255 bool overflow; 1256 wide_int alt = wi::add (wi::to_wide (smaller), 1, 1257 TYPE_SIGN (TREE_TYPE (smaller)), 1258 &overflow); 1259 if (! overflow) 1260 alt_smaller = wide_int_to_tree (TREE_TYPE (smaller), alt); 1261 } 1262 else 1263 { 1264 bool overflow; 1265 wide_int alt = wi::sub (wi::to_wide (smaller), 1, 1266 TYPE_SIGN (TREE_TYPE (smaller)), 1267 &overflow); 1268 if (! overflow) 1269 alt_smaller = wide_int_to_tree (TREE_TYPE (smaller), alt); 1270 } 1271 } 1272 } 1273 else 1274 return false; 1275 1276 /* We need to know which is the true edge and which is the false 1277 edge so that we know if have abs or negative abs. */ 1278 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge); 1279 1280 /* Forward the edges over the middle basic block. */ 1281 if (true_edge->dest == middle_bb) 1282 true_edge = EDGE_SUCC (true_edge->dest, 0); 1283 if (false_edge->dest == middle_bb) 1284 false_edge = EDGE_SUCC (false_edge->dest, 0); 1285 1286 if (true_edge == e0) 1287 { 1288 gcc_assert (false_edge == e1); 1289 arg_true = arg0; 1290 arg_false = arg1; 1291 } 1292 else 1293 { 1294 gcc_assert (false_edge == e0); 1295 gcc_assert (true_edge == e1); 1296 arg_true = arg1; 1297 arg_false = arg0; 1298 } 1299 1300 if (empty_block_p (middle_bb)) 1301 { 1302 if ((operand_equal_for_phi_arg_p (arg_true, smaller) 1303 || (alt_smaller 1304 && operand_equal_for_phi_arg_p (arg_true, alt_smaller))) 1305 && (operand_equal_for_phi_arg_p (arg_false, larger) 1306 || (alt_larger 1307 && operand_equal_for_phi_arg_p (arg_true, alt_larger)))) 1308 { 1309 /* Case 1310 1311 if (smaller < larger) 1312 rslt = smaller; 1313 else 1314 rslt = larger; */ 1315 minmax = MIN_EXPR; 1316 } 1317 else if ((operand_equal_for_phi_arg_p (arg_false, smaller) 1318 || (alt_smaller 1319 && operand_equal_for_phi_arg_p (arg_false, alt_smaller))) 1320 && (operand_equal_for_phi_arg_p (arg_true, larger) 1321 || (alt_larger 1322 && operand_equal_for_phi_arg_p (arg_true, alt_larger)))) 1323 minmax = MAX_EXPR; 1324 else 1325 return false; 1326 } 1327 else 1328 { 1329 /* Recognize the following case, assuming d <= u: 1330 1331 if (a <= u) 1332 b = MAX (a, d); 1333 x = PHI <b, u> 1334 1335 This is equivalent to 1336 1337 b = MAX (a, d); 1338 x = MIN (b, u); */ 1339 1340 gimple *assign = last_and_only_stmt (middle_bb); 1341 tree lhs, op0, op1, bound; 1342 1343 if (!assign 1344 || gimple_code (assign) != GIMPLE_ASSIGN) 1345 return false; 1346 1347 lhs = gimple_assign_lhs (assign); 1348 ass_code = gimple_assign_rhs_code (assign); 1349 if (ass_code != MAX_EXPR && ass_code != MIN_EXPR) 1350 return false; 1351 op0 = gimple_assign_rhs1 (assign); 1352 op1 = gimple_assign_rhs2 (assign); 1353 1354 if (true_edge->src == middle_bb) 1355 { 1356 /* We got here if the condition is true, i.e., SMALLER < LARGER. */ 1357 if (!operand_equal_for_phi_arg_p (lhs, arg_true)) 1358 return false; 1359 1360 if (operand_equal_for_phi_arg_p (arg_false, larger) 1361 || (alt_larger 1362 && operand_equal_for_phi_arg_p (arg_false, alt_larger))) 1363 { 1364 /* Case 1365 1366 if (smaller < larger) 1367 { 1368 r' = MAX_EXPR (smaller, bound) 1369 } 1370 r = PHI <r', larger> --> to be turned to MIN_EXPR. */ 1371 if (ass_code != MAX_EXPR) 1372 return false; 1373 1374 minmax = MIN_EXPR; 1375 if (operand_equal_for_phi_arg_p (op0, smaller) 1376 || (alt_smaller 1377 && operand_equal_for_phi_arg_p (op0, alt_smaller))) 1378 bound = op1; 1379 else if (operand_equal_for_phi_arg_p (op1, smaller) 1380 || (alt_smaller 1381 && operand_equal_for_phi_arg_p (op1, alt_smaller))) 1382 bound = op0; 1383 else 1384 return false; 1385 1386 /* We need BOUND <= LARGER. */ 1387 if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node, 1388 bound, larger))) 1389 return false; 1390 } 1391 else if (operand_equal_for_phi_arg_p (arg_false, smaller) 1392 || (alt_smaller 1393 && operand_equal_for_phi_arg_p (arg_false, alt_smaller))) 1394 { 1395 /* Case 1396 1397 if (smaller < larger) 1398 { 1399 r' = MIN_EXPR (larger, bound) 1400 } 1401 r = PHI <r', smaller> --> to be turned to MAX_EXPR. */ 1402 if (ass_code != MIN_EXPR) 1403 return false; 1404 1405 minmax = MAX_EXPR; 1406 if (operand_equal_for_phi_arg_p (op0, larger) 1407 || (alt_larger 1408 && operand_equal_for_phi_arg_p (op0, alt_larger))) 1409 bound = op1; 1410 else if (operand_equal_for_phi_arg_p (op1, larger) 1411 || (alt_larger 1412 && operand_equal_for_phi_arg_p (op1, alt_larger))) 1413 bound = op0; 1414 else 1415 return false; 1416 1417 /* We need BOUND >= SMALLER. */ 1418 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node, 1419 bound, smaller))) 1420 return false; 1421 } 1422 else 1423 return false; 1424 } 1425 else 1426 { 1427 /* We got here if the condition is false, i.e., SMALLER > LARGER. */ 1428 if (!operand_equal_for_phi_arg_p (lhs, arg_false)) 1429 return false; 1430 1431 if (operand_equal_for_phi_arg_p (arg_true, larger) 1432 || (alt_larger 1433 && operand_equal_for_phi_arg_p (arg_true, alt_larger))) 1434 { 1435 /* Case 1436 1437 if (smaller > larger) 1438 { 1439 r' = MIN_EXPR (smaller, bound) 1440 } 1441 r = PHI <r', larger> --> to be turned to MAX_EXPR. */ 1442 if (ass_code != MIN_EXPR) 1443 return false; 1444 1445 minmax = MAX_EXPR; 1446 if (operand_equal_for_phi_arg_p (op0, smaller) 1447 || (alt_smaller 1448 && operand_equal_for_phi_arg_p (op0, alt_smaller))) 1449 bound = op1; 1450 else if (operand_equal_for_phi_arg_p (op1, smaller) 1451 || (alt_smaller 1452 && operand_equal_for_phi_arg_p (op1, alt_smaller))) 1453 bound = op0; 1454 else 1455 return false; 1456 1457 /* We need BOUND >= LARGER. */ 1458 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node, 1459 bound, larger))) 1460 return false; 1461 } 1462 else if (operand_equal_for_phi_arg_p (arg_true, smaller) 1463 || (alt_smaller 1464 && operand_equal_for_phi_arg_p (arg_true, alt_smaller))) 1465 { 1466 /* Case 1467 1468 if (smaller > larger) 1469 { 1470 r' = MAX_EXPR (larger, bound) 1471 } 1472 r = PHI <r', smaller> --> to be turned to MIN_EXPR. */ 1473 if (ass_code != MAX_EXPR) 1474 return false; 1475 1476 minmax = MIN_EXPR; 1477 if (operand_equal_for_phi_arg_p (op0, larger)) 1478 bound = op1; 1479 else if (operand_equal_for_phi_arg_p (op1, larger)) 1480 bound = op0; 1481 else 1482 return false; 1483 1484 /* We need BOUND <= SMALLER. */ 1485 if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node, 1486 bound, smaller))) 1487 return false; 1488 } 1489 else 1490 return false; 1491 } 1492 1493 /* Move the statement from the middle block. */ 1494 gsi = gsi_last_bb (cond_bb); 1495 gsi_from = gsi_last_nondebug_bb (middle_bb); 1496 reset_flow_sensitive_info (SINGLE_SSA_TREE_OPERAND (gsi_stmt (gsi_from), 1497 SSA_OP_DEF)); 1498 gsi_move_before (&gsi_from, &gsi); 1499 } 1500 1501 /* Create an SSA var to hold the min/max result. If we're the only 1502 things setting the target PHI, then we can clone the PHI 1503 variable. Otherwise we must create a new one. */ 1504 result = PHI_RESULT (phi); 1505 if (EDGE_COUNT (gimple_bb (phi)->preds) == 2) 1506 result = duplicate_ssa_name (result, NULL); 1507 else 1508 result = make_ssa_name (TREE_TYPE (result)); 1509 1510 /* Emit the statement to compute min/max. */ 1511 new_stmt = gimple_build_assign (result, minmax, arg0, arg1); 1512 gsi = gsi_last_bb (cond_bb); 1513 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT); 1514 1515 replace_phi_edge_with_variable (cond_bb, e1, phi, result); 1516 1517 return true; 1518 } 1519 1520 /* The function absolute_replacement does the main work of doing the absolute 1521 replacement. Return true if the replacement is done. Otherwise return 1522 false. 1523 bb is the basic block where the replacement is going to be done on. arg0 1524 is argument 0 from the phi. Likewise for arg1. */ 1525 1526 static bool 1527 abs_replacement (basic_block cond_bb, basic_block middle_bb, 1528 edge e0 ATTRIBUTE_UNUSED, edge e1, 1529 gimple *phi, tree arg0, tree arg1) 1530 { 1531 tree result; 1532 gassign *new_stmt; 1533 gimple *cond; 1534 gimple_stmt_iterator gsi; 1535 edge true_edge, false_edge; 1536 gimple *assign; 1537 edge e; 1538 tree rhs, lhs; 1539 bool negate; 1540 enum tree_code cond_code; 1541 1542 /* If the type says honor signed zeros we cannot do this 1543 optimization. */ 1544 if (HONOR_SIGNED_ZEROS (arg1)) 1545 return false; 1546 1547 /* OTHER_BLOCK must have only one executable statement which must have the 1548 form arg0 = -arg1 or arg1 = -arg0. */ 1549 1550 assign = last_and_only_stmt (middle_bb); 1551 /* If we did not find the proper negation assignment, then we can not 1552 optimize. */ 1553 if (assign == NULL) 1554 return false; 1555 1556 /* If we got here, then we have found the only executable statement 1557 in OTHER_BLOCK. If it is anything other than arg = -arg1 or 1558 arg1 = -arg0, then we can not optimize. */ 1559 if (gimple_code (assign) != GIMPLE_ASSIGN) 1560 return false; 1561 1562 lhs = gimple_assign_lhs (assign); 1563 1564 if (gimple_assign_rhs_code (assign) != NEGATE_EXPR) 1565 return false; 1566 1567 rhs = gimple_assign_rhs1 (assign); 1568 1569 /* The assignment has to be arg0 = -arg1 or arg1 = -arg0. */ 1570 if (!(lhs == arg0 && rhs == arg1) 1571 && !(lhs == arg1 && rhs == arg0)) 1572 return false; 1573 1574 cond = last_stmt (cond_bb); 1575 result = PHI_RESULT (phi); 1576 1577 /* Only relationals comparing arg[01] against zero are interesting. */ 1578 cond_code = gimple_cond_code (cond); 1579 if (cond_code != GT_EXPR && cond_code != GE_EXPR 1580 && cond_code != LT_EXPR && cond_code != LE_EXPR) 1581 return false; 1582 1583 /* Make sure the conditional is arg[01] OP y. */ 1584 if (gimple_cond_lhs (cond) != rhs) 1585 return false; 1586 1587 if (FLOAT_TYPE_P (TREE_TYPE (gimple_cond_rhs (cond))) 1588 ? real_zerop (gimple_cond_rhs (cond)) 1589 : integer_zerop (gimple_cond_rhs (cond))) 1590 ; 1591 else 1592 return false; 1593 1594 /* We need to know which is the true edge and which is the false 1595 edge so that we know if have abs or negative abs. */ 1596 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge); 1597 1598 /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we 1599 will need to negate the result. Similarly for LT_EXPR/LE_EXPR if 1600 the false edge goes to OTHER_BLOCK. */ 1601 if (cond_code == GT_EXPR || cond_code == GE_EXPR) 1602 e = true_edge; 1603 else 1604 e = false_edge; 1605 1606 if (e->dest == middle_bb) 1607 negate = true; 1608 else 1609 negate = false; 1610 1611 /* If the code negates only iff positive then make sure to not 1612 introduce undefined behavior when negating or computing the absolute. 1613 ??? We could use range info if present to check for arg1 == INT_MIN. */ 1614 if (negate 1615 && (ANY_INTEGRAL_TYPE_P (TREE_TYPE (arg1)) 1616 && ! TYPE_OVERFLOW_WRAPS (TREE_TYPE (arg1)))) 1617 return false; 1618 1619 result = duplicate_ssa_name (result, NULL); 1620 1621 if (negate) 1622 lhs = make_ssa_name (TREE_TYPE (result)); 1623 else 1624 lhs = result; 1625 1626 /* Build the modify expression with abs expression. */ 1627 new_stmt = gimple_build_assign (lhs, ABS_EXPR, rhs); 1628 1629 gsi = gsi_last_bb (cond_bb); 1630 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT); 1631 1632 if (negate) 1633 { 1634 /* Get the right GSI. We want to insert after the recently 1635 added ABS_EXPR statement (which we know is the first statement 1636 in the block. */ 1637 new_stmt = gimple_build_assign (result, NEGATE_EXPR, lhs); 1638 1639 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT); 1640 } 1641 1642 replace_phi_edge_with_variable (cond_bb, e1, phi, result); 1643 1644 /* Note that we optimized this PHI. */ 1645 return true; 1646 } 1647 1648 /* Auxiliary functions to determine the set of memory accesses which 1649 can't trap because they are preceded by accesses to the same memory 1650 portion. We do that for MEM_REFs, so we only need to track 1651 the SSA_NAME of the pointer indirectly referenced. The algorithm 1652 simply is a walk over all instructions in dominator order. When 1653 we see an MEM_REF we determine if we've already seen a same 1654 ref anywhere up to the root of the dominator tree. If we do the 1655 current access can't trap. If we don't see any dominating access 1656 the current access might trap, but might also make later accesses 1657 non-trapping, so we remember it. We need to be careful with loads 1658 or stores, for instance a load might not trap, while a store would, 1659 so if we see a dominating read access this doesn't mean that a later 1660 write access would not trap. Hence we also need to differentiate the 1661 type of access(es) seen. 1662 1663 ??? We currently are very conservative and assume that a load might 1664 trap even if a store doesn't (write-only memory). This probably is 1665 overly conservative. */ 1666 1667 /* A hash-table of SSA_NAMEs, and in which basic block an MEM_REF 1668 through it was seen, which would constitute a no-trap region for 1669 same accesses. */ 1670 struct name_to_bb 1671 { 1672 unsigned int ssa_name_ver; 1673 unsigned int phase; 1674 bool store; 1675 HOST_WIDE_INT offset, size; 1676 basic_block bb; 1677 }; 1678 1679 /* Hashtable helpers. */ 1680 1681 struct ssa_names_hasher : free_ptr_hash <name_to_bb> 1682 { 1683 static inline hashval_t hash (const name_to_bb *); 1684 static inline bool equal (const name_to_bb *, const name_to_bb *); 1685 }; 1686 1687 /* Used for quick clearing of the hash-table when we see calls. 1688 Hash entries with phase < nt_call_phase are invalid. */ 1689 static unsigned int nt_call_phase; 1690 1691 /* The hash function. */ 1692 1693 inline hashval_t 1694 ssa_names_hasher::hash (const name_to_bb *n) 1695 { 1696 return n->ssa_name_ver ^ (((hashval_t) n->store) << 31) 1697 ^ (n->offset << 6) ^ (n->size << 3); 1698 } 1699 1700 /* The equality function of *P1 and *P2. */ 1701 1702 inline bool 1703 ssa_names_hasher::equal (const name_to_bb *n1, const name_to_bb *n2) 1704 { 1705 return n1->ssa_name_ver == n2->ssa_name_ver 1706 && n1->store == n2->store 1707 && n1->offset == n2->offset 1708 && n1->size == n2->size; 1709 } 1710 1711 class nontrapping_dom_walker : public dom_walker 1712 { 1713 public: 1714 nontrapping_dom_walker (cdi_direction direction, hash_set<tree> *ps) 1715 : dom_walker (direction), m_nontrapping (ps), m_seen_ssa_names (128) {} 1716 1717 virtual edge before_dom_children (basic_block); 1718 virtual void after_dom_children (basic_block); 1719 1720 private: 1721 1722 /* We see the expression EXP in basic block BB. If it's an interesting 1723 expression (an MEM_REF through an SSA_NAME) possibly insert the 1724 expression into the set NONTRAP or the hash table of seen expressions. 1725 STORE is true if this expression is on the LHS, otherwise it's on 1726 the RHS. */ 1727 void add_or_mark_expr (basic_block, tree, bool); 1728 1729 hash_set<tree> *m_nontrapping; 1730 1731 /* The hash table for remembering what we've seen. */ 1732 hash_table<ssa_names_hasher> m_seen_ssa_names; 1733 }; 1734 1735 /* Called by walk_dominator_tree, when entering the block BB. */ 1736 edge 1737 nontrapping_dom_walker::before_dom_children (basic_block bb) 1738 { 1739 edge e; 1740 edge_iterator ei; 1741 gimple_stmt_iterator gsi; 1742 1743 /* If we haven't seen all our predecessors, clear the hash-table. */ 1744 FOR_EACH_EDGE (e, ei, bb->preds) 1745 if ((((size_t)e->src->aux) & 2) == 0) 1746 { 1747 nt_call_phase++; 1748 break; 1749 } 1750 1751 /* Mark this BB as being on the path to dominator root and as visited. */ 1752 bb->aux = (void*)(1 | 2); 1753 1754 /* And walk the statements in order. */ 1755 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1756 { 1757 gimple *stmt = gsi_stmt (gsi); 1758 1759 if ((gimple_code (stmt) == GIMPLE_ASM && gimple_vdef (stmt)) 1760 || (is_gimple_call (stmt) 1761 && (!nonfreeing_call_p (stmt) || !nonbarrier_call_p (stmt)))) 1762 nt_call_phase++; 1763 else if (gimple_assign_single_p (stmt) && !gimple_has_volatile_ops (stmt)) 1764 { 1765 add_or_mark_expr (bb, gimple_assign_lhs (stmt), true); 1766 add_or_mark_expr (bb, gimple_assign_rhs1 (stmt), false); 1767 } 1768 } 1769 return NULL; 1770 } 1771 1772 /* Called by walk_dominator_tree, when basic block BB is exited. */ 1773 void 1774 nontrapping_dom_walker::after_dom_children (basic_block bb) 1775 { 1776 /* This BB isn't on the path to dominator root anymore. */ 1777 bb->aux = (void*)2; 1778 } 1779 1780 /* We see the expression EXP in basic block BB. If it's an interesting 1781 expression (an MEM_REF through an SSA_NAME) possibly insert the 1782 expression into the set NONTRAP or the hash table of seen expressions. 1783 STORE is true if this expression is on the LHS, otherwise it's on 1784 the RHS. */ 1785 void 1786 nontrapping_dom_walker::add_or_mark_expr (basic_block bb, tree exp, bool store) 1787 { 1788 HOST_WIDE_INT size; 1789 1790 if (TREE_CODE (exp) == MEM_REF 1791 && TREE_CODE (TREE_OPERAND (exp, 0)) == SSA_NAME 1792 && tree_fits_shwi_p (TREE_OPERAND (exp, 1)) 1793 && (size = int_size_in_bytes (TREE_TYPE (exp))) > 0) 1794 { 1795 tree name = TREE_OPERAND (exp, 0); 1796 struct name_to_bb map; 1797 name_to_bb **slot; 1798 struct name_to_bb *n2bb; 1799 basic_block found_bb = 0; 1800 1801 /* Try to find the last seen MEM_REF through the same 1802 SSA_NAME, which can trap. */ 1803 map.ssa_name_ver = SSA_NAME_VERSION (name); 1804 map.phase = 0; 1805 map.bb = 0; 1806 map.store = store; 1807 map.offset = tree_to_shwi (TREE_OPERAND (exp, 1)); 1808 map.size = size; 1809 1810 slot = m_seen_ssa_names.find_slot (&map, INSERT); 1811 n2bb = *slot; 1812 if (n2bb && n2bb->phase >= nt_call_phase) 1813 found_bb = n2bb->bb; 1814 1815 /* If we've found a trapping MEM_REF, _and_ it dominates EXP 1816 (it's in a basic block on the path from us to the dominator root) 1817 then we can't trap. */ 1818 if (found_bb && (((size_t)found_bb->aux) & 1) == 1) 1819 { 1820 m_nontrapping->add (exp); 1821 } 1822 else 1823 { 1824 /* EXP might trap, so insert it into the hash table. */ 1825 if (n2bb) 1826 { 1827 n2bb->phase = nt_call_phase; 1828 n2bb->bb = bb; 1829 } 1830 else 1831 { 1832 n2bb = XNEW (struct name_to_bb); 1833 n2bb->ssa_name_ver = SSA_NAME_VERSION (name); 1834 n2bb->phase = nt_call_phase; 1835 n2bb->bb = bb; 1836 n2bb->store = store; 1837 n2bb->offset = map.offset; 1838 n2bb->size = size; 1839 *slot = n2bb; 1840 } 1841 } 1842 } 1843 } 1844 1845 /* This is the entry point of gathering non trapping memory accesses. 1846 It will do a dominator walk over the whole function, and it will 1847 make use of the bb->aux pointers. It returns a set of trees 1848 (the MEM_REFs itself) which can't trap. */ 1849 static hash_set<tree> * 1850 get_non_trapping (void) 1851 { 1852 nt_call_phase = 0; 1853 hash_set<tree> *nontrap = new hash_set<tree>; 1854 /* We're going to do a dominator walk, so ensure that we have 1855 dominance information. */ 1856 calculate_dominance_info (CDI_DOMINATORS); 1857 1858 nontrapping_dom_walker (CDI_DOMINATORS, nontrap) 1859 .walk (cfun->cfg->x_entry_block_ptr); 1860 1861 clear_aux_for_blocks (); 1862 return nontrap; 1863 } 1864 1865 /* Do the main work of conditional store replacement. We already know 1866 that the recognized pattern looks like so: 1867 1868 split: 1869 if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1) 1870 MIDDLE_BB: 1871 something 1872 fallthrough (edge E0) 1873 JOIN_BB: 1874 some more 1875 1876 We check that MIDDLE_BB contains only one store, that that store 1877 doesn't trap (not via NOTRAP, but via checking if an access to the same 1878 memory location dominates us) and that the store has a "simple" RHS. */ 1879 1880 static bool 1881 cond_store_replacement (basic_block middle_bb, basic_block join_bb, 1882 edge e0, edge e1, hash_set<tree> *nontrap) 1883 { 1884 gimple *assign = last_and_only_stmt (middle_bb); 1885 tree lhs, rhs, name, name2; 1886 gphi *newphi; 1887 gassign *new_stmt; 1888 gimple_stmt_iterator gsi; 1889 source_location locus; 1890 1891 /* Check if middle_bb contains of only one store. */ 1892 if (!assign 1893 || !gimple_assign_single_p (assign) 1894 || gimple_has_volatile_ops (assign)) 1895 return false; 1896 1897 locus = gimple_location (assign); 1898 lhs = gimple_assign_lhs (assign); 1899 rhs = gimple_assign_rhs1 (assign); 1900 if (TREE_CODE (lhs) != MEM_REF 1901 || TREE_CODE (TREE_OPERAND (lhs, 0)) != SSA_NAME 1902 || !is_gimple_reg_type (TREE_TYPE (lhs))) 1903 return false; 1904 1905 /* Prove that we can move the store down. We could also check 1906 TREE_THIS_NOTRAP here, but in that case we also could move stores, 1907 whose value is not available readily, which we want to avoid. */ 1908 if (!nontrap->contains (lhs)) 1909 return false; 1910 1911 /* Now we've checked the constraints, so do the transformation: 1912 1) Remove the single store. */ 1913 gsi = gsi_for_stmt (assign); 1914 unlink_stmt_vdef (assign); 1915 gsi_remove (&gsi, true); 1916 release_defs (assign); 1917 1918 /* Make both store and load use alias-set zero as we have to 1919 deal with the case of the store being a conditional change 1920 of the dynamic type. */ 1921 lhs = unshare_expr (lhs); 1922 tree *basep = &lhs; 1923 while (handled_component_p (*basep)) 1924 basep = &TREE_OPERAND (*basep, 0); 1925 if (TREE_CODE (*basep) == MEM_REF 1926 || TREE_CODE (*basep) == TARGET_MEM_REF) 1927 TREE_OPERAND (*basep, 1) 1928 = fold_convert (ptr_type_node, TREE_OPERAND (*basep, 1)); 1929 else 1930 *basep = build2 (MEM_REF, TREE_TYPE (*basep), 1931 build_fold_addr_expr (*basep), 1932 build_zero_cst (ptr_type_node)); 1933 1934 /* 2) Insert a load from the memory of the store to the temporary 1935 on the edge which did not contain the store. */ 1936 name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore"); 1937 new_stmt = gimple_build_assign (name, lhs); 1938 gimple_set_location (new_stmt, locus); 1939 gsi_insert_on_edge (e1, new_stmt); 1940 1941 /* 3) Create a PHI node at the join block, with one argument 1942 holding the old RHS, and the other holding the temporary 1943 where we stored the old memory contents. */ 1944 name2 = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore"); 1945 newphi = create_phi_node (name2, join_bb); 1946 add_phi_arg (newphi, rhs, e0, locus); 1947 add_phi_arg (newphi, name, e1, locus); 1948 1949 lhs = unshare_expr (lhs); 1950 new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi)); 1951 1952 /* 4) Insert that PHI node. */ 1953 gsi = gsi_after_labels (join_bb); 1954 if (gsi_end_p (gsi)) 1955 { 1956 gsi = gsi_last_bb (join_bb); 1957 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT); 1958 } 1959 else 1960 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT); 1961 1962 return true; 1963 } 1964 1965 /* Do the main work of conditional store replacement. */ 1966 1967 static bool 1968 cond_if_else_store_replacement_1 (basic_block then_bb, basic_block else_bb, 1969 basic_block join_bb, gimple *then_assign, 1970 gimple *else_assign) 1971 { 1972 tree lhs_base, lhs, then_rhs, else_rhs, name; 1973 source_location then_locus, else_locus; 1974 gimple_stmt_iterator gsi; 1975 gphi *newphi; 1976 gassign *new_stmt; 1977 1978 if (then_assign == NULL 1979 || !gimple_assign_single_p (then_assign) 1980 || gimple_clobber_p (then_assign) 1981 || gimple_has_volatile_ops (then_assign) 1982 || else_assign == NULL 1983 || !gimple_assign_single_p (else_assign) 1984 || gimple_clobber_p (else_assign) 1985 || gimple_has_volatile_ops (else_assign)) 1986 return false; 1987 1988 lhs = gimple_assign_lhs (then_assign); 1989 if (!is_gimple_reg_type (TREE_TYPE (lhs)) 1990 || !operand_equal_p (lhs, gimple_assign_lhs (else_assign), 0)) 1991 return false; 1992 1993 lhs_base = get_base_address (lhs); 1994 if (lhs_base == NULL_TREE 1995 || (!DECL_P (lhs_base) && TREE_CODE (lhs_base) != MEM_REF)) 1996 return false; 1997 1998 then_rhs = gimple_assign_rhs1 (then_assign); 1999 else_rhs = gimple_assign_rhs1 (else_assign); 2000 then_locus = gimple_location (then_assign); 2001 else_locus = gimple_location (else_assign); 2002 2003 /* Now we've checked the constraints, so do the transformation: 2004 1) Remove the stores. */ 2005 gsi = gsi_for_stmt (then_assign); 2006 unlink_stmt_vdef (then_assign); 2007 gsi_remove (&gsi, true); 2008 release_defs (then_assign); 2009 2010 gsi = gsi_for_stmt (else_assign); 2011 unlink_stmt_vdef (else_assign); 2012 gsi_remove (&gsi, true); 2013 release_defs (else_assign); 2014 2015 /* 2) Create a PHI node at the join block, with one argument 2016 holding the old RHS, and the other holding the temporary 2017 where we stored the old memory contents. */ 2018 name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore"); 2019 newphi = create_phi_node (name, join_bb); 2020 add_phi_arg (newphi, then_rhs, EDGE_SUCC (then_bb, 0), then_locus); 2021 add_phi_arg (newphi, else_rhs, EDGE_SUCC (else_bb, 0), else_locus); 2022 2023 new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi)); 2024 2025 /* 3) Insert that PHI node. */ 2026 gsi = gsi_after_labels (join_bb); 2027 if (gsi_end_p (gsi)) 2028 { 2029 gsi = gsi_last_bb (join_bb); 2030 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT); 2031 } 2032 else 2033 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT); 2034 2035 return true; 2036 } 2037 2038 /* Return the single store in BB with VDEF or NULL if there are 2039 other stores in the BB or loads following the store. */ 2040 2041 static gimple * 2042 single_trailing_store_in_bb (basic_block bb, tree vdef) 2043 { 2044 if (SSA_NAME_IS_DEFAULT_DEF (vdef)) 2045 return NULL; 2046 gimple *store = SSA_NAME_DEF_STMT (vdef); 2047 if (gimple_bb (store) != bb 2048 || gimple_code (store) == GIMPLE_PHI) 2049 return NULL; 2050 2051 /* Verify there is no other store in this BB. */ 2052 if (!SSA_NAME_IS_DEFAULT_DEF (gimple_vuse (store)) 2053 && gimple_bb (SSA_NAME_DEF_STMT (gimple_vuse (store))) == bb 2054 && gimple_code (SSA_NAME_DEF_STMT (gimple_vuse (store))) != GIMPLE_PHI) 2055 return NULL; 2056 2057 /* Verify there is no load or store after the store. */ 2058 use_operand_p use_p; 2059 imm_use_iterator imm_iter; 2060 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_vdef (store)) 2061 if (USE_STMT (use_p) != store 2062 && gimple_bb (USE_STMT (use_p)) == bb) 2063 return NULL; 2064 2065 return store; 2066 } 2067 2068 /* Conditional store replacement. We already know 2069 that the recognized pattern looks like so: 2070 2071 split: 2072 if (cond) goto THEN_BB; else goto ELSE_BB (edge E1) 2073 THEN_BB: 2074 ... 2075 X = Y; 2076 ... 2077 goto JOIN_BB; 2078 ELSE_BB: 2079 ... 2080 X = Z; 2081 ... 2082 fallthrough (edge E0) 2083 JOIN_BB: 2084 some more 2085 2086 We check that it is safe to sink the store to JOIN_BB by verifying that 2087 there are no read-after-write or write-after-write dependencies in 2088 THEN_BB and ELSE_BB. */ 2089 2090 static bool 2091 cond_if_else_store_replacement (basic_block then_bb, basic_block else_bb, 2092 basic_block join_bb) 2093 { 2094 vec<data_reference_p> then_datarefs, else_datarefs; 2095 vec<ddr_p> then_ddrs, else_ddrs; 2096 gimple *then_store, *else_store; 2097 bool found, ok = false, res; 2098 struct data_dependence_relation *ddr; 2099 data_reference_p then_dr, else_dr; 2100 int i, j; 2101 tree then_lhs, else_lhs; 2102 basic_block blocks[3]; 2103 2104 /* Handle the case with single store in THEN_BB and ELSE_BB. That is 2105 cheap enough to always handle as it allows us to elide dependence 2106 checking. */ 2107 gphi *vphi = NULL; 2108 for (gphi_iterator si = gsi_start_phis (join_bb); !gsi_end_p (si); 2109 gsi_next (&si)) 2110 if (virtual_operand_p (gimple_phi_result (si.phi ()))) 2111 { 2112 vphi = si.phi (); 2113 break; 2114 } 2115 if (!vphi) 2116 return false; 2117 tree then_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, single_succ_edge (then_bb)); 2118 tree else_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, single_succ_edge (else_bb)); 2119 gimple *then_assign = single_trailing_store_in_bb (then_bb, then_vdef); 2120 if (then_assign) 2121 { 2122 gimple *else_assign = single_trailing_store_in_bb (else_bb, else_vdef); 2123 if (else_assign) 2124 return cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb, 2125 then_assign, else_assign); 2126 } 2127 2128 if (MAX_STORES_TO_SINK == 0) 2129 return false; 2130 2131 /* Find data references. */ 2132 then_datarefs.create (1); 2133 else_datarefs.create (1); 2134 if ((find_data_references_in_bb (NULL, then_bb, &then_datarefs) 2135 == chrec_dont_know) 2136 || !then_datarefs.length () 2137 || (find_data_references_in_bb (NULL, else_bb, &else_datarefs) 2138 == chrec_dont_know) 2139 || !else_datarefs.length ()) 2140 { 2141 free_data_refs (then_datarefs); 2142 free_data_refs (else_datarefs); 2143 return false; 2144 } 2145 2146 /* Find pairs of stores with equal LHS. */ 2147 auto_vec<gimple *, 1> then_stores, else_stores; 2148 FOR_EACH_VEC_ELT (then_datarefs, i, then_dr) 2149 { 2150 if (DR_IS_READ (then_dr)) 2151 continue; 2152 2153 then_store = DR_STMT (then_dr); 2154 then_lhs = gimple_get_lhs (then_store); 2155 if (then_lhs == NULL_TREE) 2156 continue; 2157 found = false; 2158 2159 FOR_EACH_VEC_ELT (else_datarefs, j, else_dr) 2160 { 2161 if (DR_IS_READ (else_dr)) 2162 continue; 2163 2164 else_store = DR_STMT (else_dr); 2165 else_lhs = gimple_get_lhs (else_store); 2166 if (else_lhs == NULL_TREE) 2167 continue; 2168 2169 if (operand_equal_p (then_lhs, else_lhs, 0)) 2170 { 2171 found = true; 2172 break; 2173 } 2174 } 2175 2176 if (!found) 2177 continue; 2178 2179 then_stores.safe_push (then_store); 2180 else_stores.safe_push (else_store); 2181 } 2182 2183 /* No pairs of stores found. */ 2184 if (!then_stores.length () 2185 || then_stores.length () > (unsigned) MAX_STORES_TO_SINK) 2186 { 2187 free_data_refs (then_datarefs); 2188 free_data_refs (else_datarefs); 2189 return false; 2190 } 2191 2192 /* Compute and check data dependencies in both basic blocks. */ 2193 then_ddrs.create (1); 2194 else_ddrs.create (1); 2195 if (!compute_all_dependences (then_datarefs, &then_ddrs, 2196 vNULL, false) 2197 || !compute_all_dependences (else_datarefs, &else_ddrs, 2198 vNULL, false)) 2199 { 2200 free_dependence_relations (then_ddrs); 2201 free_dependence_relations (else_ddrs); 2202 free_data_refs (then_datarefs); 2203 free_data_refs (else_datarefs); 2204 return false; 2205 } 2206 blocks[0] = then_bb; 2207 blocks[1] = else_bb; 2208 blocks[2] = join_bb; 2209 renumber_gimple_stmt_uids_in_blocks (blocks, 3); 2210 2211 /* Check that there are no read-after-write or write-after-write dependencies 2212 in THEN_BB. */ 2213 FOR_EACH_VEC_ELT (then_ddrs, i, ddr) 2214 { 2215 struct data_reference *dra = DDR_A (ddr); 2216 struct data_reference *drb = DDR_B (ddr); 2217 2218 if (DDR_ARE_DEPENDENT (ddr) != chrec_known 2219 && ((DR_IS_READ (dra) && DR_IS_WRITE (drb) 2220 && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb))) 2221 || (DR_IS_READ (drb) && DR_IS_WRITE (dra) 2222 && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra))) 2223 || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb)))) 2224 { 2225 free_dependence_relations (then_ddrs); 2226 free_dependence_relations (else_ddrs); 2227 free_data_refs (then_datarefs); 2228 free_data_refs (else_datarefs); 2229 return false; 2230 } 2231 } 2232 2233 /* Check that there are no read-after-write or write-after-write dependencies 2234 in ELSE_BB. */ 2235 FOR_EACH_VEC_ELT (else_ddrs, i, ddr) 2236 { 2237 struct data_reference *dra = DDR_A (ddr); 2238 struct data_reference *drb = DDR_B (ddr); 2239 2240 if (DDR_ARE_DEPENDENT (ddr) != chrec_known 2241 && ((DR_IS_READ (dra) && DR_IS_WRITE (drb) 2242 && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb))) 2243 || (DR_IS_READ (drb) && DR_IS_WRITE (dra) 2244 && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra))) 2245 || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb)))) 2246 { 2247 free_dependence_relations (then_ddrs); 2248 free_dependence_relations (else_ddrs); 2249 free_data_refs (then_datarefs); 2250 free_data_refs (else_datarefs); 2251 return false; 2252 } 2253 } 2254 2255 /* Sink stores with same LHS. */ 2256 FOR_EACH_VEC_ELT (then_stores, i, then_store) 2257 { 2258 else_store = else_stores[i]; 2259 res = cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb, 2260 then_store, else_store); 2261 ok = ok || res; 2262 } 2263 2264 free_dependence_relations (then_ddrs); 2265 free_dependence_relations (else_ddrs); 2266 free_data_refs (then_datarefs); 2267 free_data_refs (else_datarefs); 2268 2269 return ok; 2270 } 2271 2272 /* Return TRUE if STMT has a VUSE whose corresponding VDEF is in BB. */ 2273 2274 static bool 2275 local_mem_dependence (gimple *stmt, basic_block bb) 2276 { 2277 tree vuse = gimple_vuse (stmt); 2278 gimple *def; 2279 2280 if (!vuse) 2281 return false; 2282 2283 def = SSA_NAME_DEF_STMT (vuse); 2284 return (def && gimple_bb (def) == bb); 2285 } 2286 2287 /* Given a "diamond" control-flow pattern where BB0 tests a condition, 2288 BB1 and BB2 are "then" and "else" blocks dependent on this test, 2289 and BB3 rejoins control flow following BB1 and BB2, look for 2290 opportunities to hoist loads as follows. If BB3 contains a PHI of 2291 two loads, one each occurring in BB1 and BB2, and the loads are 2292 provably of adjacent fields in the same structure, then move both 2293 loads into BB0. Of course this can only be done if there are no 2294 dependencies preventing such motion. 2295 2296 One of the hoisted loads will always be speculative, so the 2297 transformation is currently conservative: 2298 2299 - The fields must be strictly adjacent. 2300 - The two fields must occupy a single memory block that is 2301 guaranteed to not cross a page boundary. 2302 2303 The last is difficult to prove, as such memory blocks should be 2304 aligned on the minimum of the stack alignment boundary and the 2305 alignment guaranteed by heap allocation interfaces. Thus we rely 2306 on a parameter for the alignment value. 2307 2308 Provided a good value is used for the last case, the first 2309 restriction could possibly be relaxed. */ 2310 2311 static void 2312 hoist_adjacent_loads (basic_block bb0, basic_block bb1, 2313 basic_block bb2, basic_block bb3) 2314 { 2315 int param_align = PARAM_VALUE (PARAM_L1_CACHE_LINE_SIZE); 2316 unsigned param_align_bits = (unsigned) (param_align * BITS_PER_UNIT); 2317 gphi_iterator gsi; 2318 2319 /* Walk the phis in bb3 looking for an opportunity. We are looking 2320 for phis of two SSA names, one each of which is defined in bb1 and 2321 bb2. */ 2322 for (gsi = gsi_start_phis (bb3); !gsi_end_p (gsi); gsi_next (&gsi)) 2323 { 2324 gphi *phi_stmt = gsi.phi (); 2325 gimple *def1, *def2; 2326 tree arg1, arg2, ref1, ref2, field1, field2; 2327 tree tree_offset1, tree_offset2, tree_size2, next; 2328 int offset1, offset2, size2; 2329 unsigned align1; 2330 gimple_stmt_iterator gsi2; 2331 basic_block bb_for_def1, bb_for_def2; 2332 2333 if (gimple_phi_num_args (phi_stmt) != 2 2334 || virtual_operand_p (gimple_phi_result (phi_stmt))) 2335 continue; 2336 2337 arg1 = gimple_phi_arg_def (phi_stmt, 0); 2338 arg2 = gimple_phi_arg_def (phi_stmt, 1); 2339 2340 if (TREE_CODE (arg1) != SSA_NAME 2341 || TREE_CODE (arg2) != SSA_NAME 2342 || SSA_NAME_IS_DEFAULT_DEF (arg1) 2343 || SSA_NAME_IS_DEFAULT_DEF (arg2)) 2344 continue; 2345 2346 def1 = SSA_NAME_DEF_STMT (arg1); 2347 def2 = SSA_NAME_DEF_STMT (arg2); 2348 2349 if ((gimple_bb (def1) != bb1 || gimple_bb (def2) != bb2) 2350 && (gimple_bb (def2) != bb1 || gimple_bb (def1) != bb2)) 2351 continue; 2352 2353 /* Check the mode of the arguments to be sure a conditional move 2354 can be generated for it. */ 2355 if (optab_handler (movcc_optab, TYPE_MODE (TREE_TYPE (arg1))) 2356 == CODE_FOR_nothing) 2357 continue; 2358 2359 /* Both statements must be assignments whose RHS is a COMPONENT_REF. */ 2360 if (!gimple_assign_single_p (def1) 2361 || !gimple_assign_single_p (def2) 2362 || gimple_has_volatile_ops (def1) 2363 || gimple_has_volatile_ops (def2)) 2364 continue; 2365 2366 ref1 = gimple_assign_rhs1 (def1); 2367 ref2 = gimple_assign_rhs1 (def2); 2368 2369 if (TREE_CODE (ref1) != COMPONENT_REF 2370 || TREE_CODE (ref2) != COMPONENT_REF) 2371 continue; 2372 2373 /* The zeroth operand of the two component references must be 2374 identical. It is not sufficient to compare get_base_address of 2375 the two references, because this could allow for different 2376 elements of the same array in the two trees. It is not safe to 2377 assume that the existence of one array element implies the 2378 existence of a different one. */ 2379 if (!operand_equal_p (TREE_OPERAND (ref1, 0), TREE_OPERAND (ref2, 0), 0)) 2380 continue; 2381 2382 field1 = TREE_OPERAND (ref1, 1); 2383 field2 = TREE_OPERAND (ref2, 1); 2384 2385 /* Check for field adjacency, and ensure field1 comes first. */ 2386 for (next = DECL_CHAIN (field1); 2387 next && TREE_CODE (next) != FIELD_DECL; 2388 next = DECL_CHAIN (next)) 2389 ; 2390 2391 if (next != field2) 2392 { 2393 for (next = DECL_CHAIN (field2); 2394 next && TREE_CODE (next) != FIELD_DECL; 2395 next = DECL_CHAIN (next)) 2396 ; 2397 2398 if (next != field1) 2399 continue; 2400 2401 std::swap (field1, field2); 2402 std::swap (def1, def2); 2403 } 2404 2405 bb_for_def1 = gimple_bb (def1); 2406 bb_for_def2 = gimple_bb (def2); 2407 2408 /* Check for proper alignment of the first field. */ 2409 tree_offset1 = bit_position (field1); 2410 tree_offset2 = bit_position (field2); 2411 tree_size2 = DECL_SIZE (field2); 2412 2413 if (!tree_fits_uhwi_p (tree_offset1) 2414 || !tree_fits_uhwi_p (tree_offset2) 2415 || !tree_fits_uhwi_p (tree_size2)) 2416 continue; 2417 2418 offset1 = tree_to_uhwi (tree_offset1); 2419 offset2 = tree_to_uhwi (tree_offset2); 2420 size2 = tree_to_uhwi (tree_size2); 2421 align1 = DECL_ALIGN (field1) % param_align_bits; 2422 2423 if (offset1 % BITS_PER_UNIT != 0) 2424 continue; 2425 2426 /* For profitability, the two field references should fit within 2427 a single cache line. */ 2428 if (align1 + offset2 - offset1 + size2 > param_align_bits) 2429 continue; 2430 2431 /* The two expressions cannot be dependent upon vdefs defined 2432 in bb1/bb2. */ 2433 if (local_mem_dependence (def1, bb_for_def1) 2434 || local_mem_dependence (def2, bb_for_def2)) 2435 continue; 2436 2437 /* The conditions are satisfied; hoist the loads from bb1 and bb2 into 2438 bb0. We hoist the first one first so that a cache miss is handled 2439 efficiently regardless of hardware cache-fill policy. */ 2440 gsi2 = gsi_for_stmt (def1); 2441 gsi_move_to_bb_end (&gsi2, bb0); 2442 gsi2 = gsi_for_stmt (def2); 2443 gsi_move_to_bb_end (&gsi2, bb0); 2444 2445 if (dump_file && (dump_flags & TDF_DETAILS)) 2446 { 2447 fprintf (dump_file, 2448 "\nHoisting adjacent loads from %d and %d into %d: \n", 2449 bb_for_def1->index, bb_for_def2->index, bb0->index); 2450 print_gimple_stmt (dump_file, def1, 0, TDF_VOPS|TDF_MEMSYMS); 2451 print_gimple_stmt (dump_file, def2, 0, TDF_VOPS|TDF_MEMSYMS); 2452 } 2453 } 2454 } 2455 2456 /* Determine whether we should attempt to hoist adjacent loads out of 2457 diamond patterns in pass_phiopt. Always hoist loads if 2458 -fhoist-adjacent-loads is specified and the target machine has 2459 both a conditional move instruction and a defined cache line size. */ 2460 2461 static bool 2462 gate_hoist_loads (void) 2463 { 2464 return (flag_hoist_adjacent_loads == 1 2465 && PARAM_VALUE (PARAM_L1_CACHE_LINE_SIZE) 2466 && HAVE_conditional_move); 2467 } 2468 2469 /* This pass tries to replaces an if-then-else block with an 2470 assignment. We have four kinds of transformations. Some of these 2471 transformations are also performed by the ifcvt RTL optimizer. 2472 2473 Conditional Replacement 2474 ----------------------- 2475 2476 This transformation, implemented in conditional_replacement, 2477 replaces 2478 2479 bb0: 2480 if (cond) goto bb2; else goto bb1; 2481 bb1: 2482 bb2: 2483 x = PHI <0 (bb1), 1 (bb0), ...>; 2484 2485 with 2486 2487 bb0: 2488 x' = cond; 2489 goto bb2; 2490 bb2: 2491 x = PHI <x' (bb0), ...>; 2492 2493 We remove bb1 as it becomes unreachable. This occurs often due to 2494 gimplification of conditionals. 2495 2496 Value Replacement 2497 ----------------- 2498 2499 This transformation, implemented in value_replacement, replaces 2500 2501 bb0: 2502 if (a != b) goto bb2; else goto bb1; 2503 bb1: 2504 bb2: 2505 x = PHI <a (bb1), b (bb0), ...>; 2506 2507 with 2508 2509 bb0: 2510 bb2: 2511 x = PHI <b (bb0), ...>; 2512 2513 This opportunity can sometimes occur as a result of other 2514 optimizations. 2515 2516 2517 Another case caught by value replacement looks like this: 2518 2519 bb0: 2520 t1 = a == CONST; 2521 t2 = b > c; 2522 t3 = t1 & t2; 2523 if (t3 != 0) goto bb1; else goto bb2; 2524 bb1: 2525 bb2: 2526 x = PHI (CONST, a) 2527 2528 Gets replaced with: 2529 bb0: 2530 bb2: 2531 t1 = a == CONST; 2532 t2 = b > c; 2533 t3 = t1 & t2; 2534 x = a; 2535 2536 ABS Replacement 2537 --------------- 2538 2539 This transformation, implemented in abs_replacement, replaces 2540 2541 bb0: 2542 if (a >= 0) goto bb2; else goto bb1; 2543 bb1: 2544 x = -a; 2545 bb2: 2546 x = PHI <x (bb1), a (bb0), ...>; 2547 2548 with 2549 2550 bb0: 2551 x' = ABS_EXPR< a >; 2552 bb2: 2553 x = PHI <x' (bb0), ...>; 2554 2555 MIN/MAX Replacement 2556 ------------------- 2557 2558 This transformation, minmax_replacement replaces 2559 2560 bb0: 2561 if (a <= b) goto bb2; else goto bb1; 2562 bb1: 2563 bb2: 2564 x = PHI <b (bb1), a (bb0), ...>; 2565 2566 with 2567 2568 bb0: 2569 x' = MIN_EXPR (a, b) 2570 bb2: 2571 x = PHI <x' (bb0), ...>; 2572 2573 A similar transformation is done for MAX_EXPR. 2574 2575 2576 This pass also performs a fifth transformation of a slightly different 2577 flavor. 2578 2579 Factor conversion in COND_EXPR 2580 ------------------------------ 2581 2582 This transformation factors the conversion out of COND_EXPR with 2583 factor_out_conditional_conversion. 2584 2585 For example: 2586 if (a <= CST) goto <bb 3>; else goto <bb 4>; 2587 <bb 3>: 2588 tmp = (int) a; 2589 <bb 4>: 2590 tmp = PHI <tmp, CST> 2591 2592 Into: 2593 if (a <= CST) goto <bb 3>; else goto <bb 4>; 2594 <bb 3>: 2595 <bb 4>: 2596 a = PHI <a, CST> 2597 tmp = (int) a; 2598 2599 Adjacent Load Hoisting 2600 ---------------------- 2601 2602 This transformation replaces 2603 2604 bb0: 2605 if (...) goto bb2; else goto bb1; 2606 bb1: 2607 x1 = (<expr>).field1; 2608 goto bb3; 2609 bb2: 2610 x2 = (<expr>).field2; 2611 bb3: 2612 # x = PHI <x1, x2>; 2613 2614 with 2615 2616 bb0: 2617 x1 = (<expr>).field1; 2618 x2 = (<expr>).field2; 2619 if (...) goto bb2; else goto bb1; 2620 bb1: 2621 goto bb3; 2622 bb2: 2623 bb3: 2624 # x = PHI <x1, x2>; 2625 2626 The purpose of this transformation is to enable generation of conditional 2627 move instructions such as Intel CMOVE or PowerPC ISEL. Because one of 2628 the loads is speculative, the transformation is restricted to very 2629 specific cases to avoid introducing a page fault. We are looking for 2630 the common idiom: 2631 2632 if (...) 2633 x = y->left; 2634 else 2635 x = y->right; 2636 2637 where left and right are typically adjacent pointers in a tree structure. */ 2638 2639 namespace { 2640 2641 const pass_data pass_data_phiopt = 2642 { 2643 GIMPLE_PASS, /* type */ 2644 "phiopt", /* name */ 2645 OPTGROUP_NONE, /* optinfo_flags */ 2646 TV_TREE_PHIOPT, /* tv_id */ 2647 ( PROP_cfg | PROP_ssa ), /* properties_required */ 2648 0, /* properties_provided */ 2649 0, /* properties_destroyed */ 2650 0, /* todo_flags_start */ 2651 0, /* todo_flags_finish */ 2652 }; 2653 2654 class pass_phiopt : public gimple_opt_pass 2655 { 2656 public: 2657 pass_phiopt (gcc::context *ctxt) 2658 : gimple_opt_pass (pass_data_phiopt, ctxt) 2659 {} 2660 2661 /* opt_pass methods: */ 2662 opt_pass * clone () { return new pass_phiopt (m_ctxt); } 2663 virtual bool gate (function *) { return flag_ssa_phiopt; } 2664 virtual unsigned int execute (function *) 2665 { 2666 return tree_ssa_phiopt_worker (false, gate_hoist_loads ()); 2667 } 2668 2669 }; // class pass_phiopt 2670 2671 } // anon namespace 2672 2673 gimple_opt_pass * 2674 make_pass_phiopt (gcc::context *ctxt) 2675 { 2676 return new pass_phiopt (ctxt); 2677 } 2678 2679 namespace { 2680 2681 const pass_data pass_data_cselim = 2682 { 2683 GIMPLE_PASS, /* type */ 2684 "cselim", /* name */ 2685 OPTGROUP_NONE, /* optinfo_flags */ 2686 TV_TREE_PHIOPT, /* tv_id */ 2687 ( PROP_cfg | PROP_ssa ), /* properties_required */ 2688 0, /* properties_provided */ 2689 0, /* properties_destroyed */ 2690 0, /* todo_flags_start */ 2691 0, /* todo_flags_finish */ 2692 }; 2693 2694 class pass_cselim : public gimple_opt_pass 2695 { 2696 public: 2697 pass_cselim (gcc::context *ctxt) 2698 : gimple_opt_pass (pass_data_cselim, ctxt) 2699 {} 2700 2701 /* opt_pass methods: */ 2702 virtual bool gate (function *) { return flag_tree_cselim; } 2703 virtual unsigned int execute (function *) { return tree_ssa_cs_elim (); } 2704 2705 }; // class pass_cselim 2706 2707 } // anon namespace 2708 2709 gimple_opt_pass * 2710 make_pass_cselim (gcc::context *ctxt) 2711 { 2712 return new pass_cselim (ctxt); 2713 } 2714