1 /* Support routines for Splitting Paths to loop backedges 2 Copyright (C) 2015-2022 Free Software Foundation, Inc. 3 Contributed by Ajit Kumar Agarwal <ajitkum@xilinx.com>. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 3, or (at your option) 10 any later version. 11 12 GCC is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "backend.h" 25 #include "tree.h" 26 #include "gimple.h" 27 #include "tree-pass.h" 28 #include "tree-cfg.h" 29 #include "cfganal.h" 30 #include "cfgloop.h" 31 #include "gimple-iterator.h" 32 #include "tracer.h" 33 #include "predict.h" 34 #include "gimple-ssa.h" 35 #include "tree-phinodes.h" 36 #include "ssa-iterators.h" 37 #include "fold-const.h" 38 39 /* Given LATCH, the latch block in a loop, see if the shape of the 40 path reaching LATCH is suitable for being split by duplication. 41 If so, return the block that will be duplicated into its predecessor 42 paths. Else return NULL. */ 43 44 static basic_block 45 find_block_to_duplicate_for_splitting_paths (basic_block latch) 46 { 47 /* We should have simple latches at this point. So the latch should 48 have a single successor. This implies the predecessor of the latch 49 likely has the loop exit. And it's that predecessor we're most 50 interested in. To keep things simple, we're going to require that 51 the latch have a single predecessor too. */ 52 if (single_succ_p (latch) && single_pred_p (latch)) 53 { 54 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, latch); 55 gcc_assert (single_pred_edge (latch)->src == bb); 56 57 /* If BB has been marked as not to be duplicated, then honor that 58 request. */ 59 if (ignore_bb_p (bb)) 60 return NULL; 61 62 gimple *last = gsi_stmt (gsi_last_nondebug_bb (bb)); 63 /* The immediate dominator of the latch must end in a conditional. */ 64 if (!last || gimple_code (last) != GIMPLE_COND) 65 return NULL; 66 67 /* We're hoping that BB is a join point for an IF-THEN-ELSE diamond 68 region. Verify that it is. 69 70 First, verify that BB has two predecessors (each arm of the 71 IF-THEN-ELSE) and two successors (the latch and exit) and that 72 all edges are normal. */ 73 if (EDGE_COUNT (bb->preds) == 2 74 && !(EDGE_PRED (bb, 0)->flags & EDGE_COMPLEX) 75 && !(EDGE_PRED (bb, 1)->flags & EDGE_COMPLEX) 76 && EDGE_COUNT (bb->succs) == 2 77 && !(EDGE_SUCC (bb, 0)->flags & EDGE_COMPLEX) 78 && !(EDGE_SUCC (bb, 1)->flags & EDGE_COMPLEX)) 79 { 80 /* Now verify that BB's immediate dominator ends in a 81 conditional as well. */ 82 basic_block bb_idom = get_immediate_dominator (CDI_DOMINATORS, bb); 83 gimple *last = gsi_stmt (gsi_last_nondebug_bb (bb_idom)); 84 if (!last || gimple_code (last) != GIMPLE_COND) 85 return NULL; 86 87 /* And that BB's immediate dominator's successors are the 88 predecessors of BB or BB itself. */ 89 if (!(EDGE_PRED (bb, 0)->src == bb_idom 90 || find_edge (bb_idom, EDGE_PRED (bb, 0)->src)) 91 || !(EDGE_PRED (bb, 1)->src == bb_idom 92 || find_edge (bb_idom, EDGE_PRED (bb, 1)->src))) 93 return NULL; 94 95 /* And that the predecessors of BB each have a single successor 96 or are BB's immediate domiator itself. */ 97 if (!(EDGE_PRED (bb, 0)->src == bb_idom 98 || single_succ_p (EDGE_PRED (bb, 0)->src)) 99 || !(EDGE_PRED (bb, 1)->src == bb_idom 100 || single_succ_p (EDGE_PRED (bb, 1)->src))) 101 return NULL; 102 103 /* So at this point we have a simple diamond for an IF-THEN-ELSE 104 construct starting at BB_IDOM, with a join point at BB. BB 105 pass control outside the loop or to the loop latch. 106 107 We're going to want to create two duplicates of BB, one for 108 each successor of BB_IDOM. */ 109 return bb; 110 } 111 } 112 return NULL; 113 } 114 115 /* Return the number of non-debug statements in a block. */ 116 static unsigned int 117 count_stmts_in_block (basic_block bb) 118 { 119 gimple_stmt_iterator gsi; 120 unsigned int num_stmts = 0; 121 122 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 123 { 124 gimple *stmt = gsi_stmt (gsi); 125 if (!is_gimple_debug (stmt)) 126 num_stmts++; 127 } 128 return num_stmts; 129 } 130 131 /* Return TRUE if CODE represents a tree code that is not likely to 132 be easily if-convertable because it likely expands into multiple 133 insns, FALSE otherwise. */ 134 static bool 135 poor_ifcvt_candidate_code (enum tree_code code) 136 { 137 return (code == MIN_EXPR 138 || code == MAX_EXPR 139 || code == ABS_EXPR 140 || code == COND_EXPR 141 || code == CALL_EXPR); 142 } 143 144 /* Return TRUE if BB is a reasonable block to duplicate by examining 145 its size, false otherwise. BB will always be a loop latch block. 146 147 Things to consider: 148 149 We do not want to spoil if-conversion if at all possible. 150 151 Most of the benefit seems to be from eliminating the unconditional 152 jump rather than CSE/DCE opportunities. So favor duplicating 153 small latches. A latch with just a conditional branch is ideal. 154 155 CSE/DCE opportunties crop up when statements from the predecessors 156 feed statements in the latch and allow statements in the latch to 157 simplify. */ 158 159 static bool 160 is_feasible_trace (basic_block bb) 161 { 162 basic_block pred1 = EDGE_PRED (bb, 0)->src; 163 basic_block pred2 = EDGE_PRED (bb, 1)->src; 164 int num_stmts_in_join = count_stmts_in_block (bb); 165 int num_stmts_in_pred1 166 = EDGE_COUNT (pred1->succs) == 1 ? count_stmts_in_block (pred1) : 0; 167 int num_stmts_in_pred2 168 = EDGE_COUNT (pred2->succs) == 1 ? count_stmts_in_block (pred2) : 0; 169 170 /* This is meant to catch cases that are likely opportunities for 171 if-conversion. Essentially we look for the case where 172 BB's predecessors are both single statement blocks where 173 the output of that statement feed the same PHI in BB. */ 174 if (num_stmts_in_pred1 == 1 && num_stmts_in_pred2 == 1) 175 { 176 gimple *stmt1 = last_and_only_stmt (pred1); 177 gimple *stmt2 = last_and_only_stmt (pred2); 178 179 if (stmt1 && stmt2 180 && gimple_code (stmt1) == GIMPLE_ASSIGN 181 && gimple_code (stmt2) == GIMPLE_ASSIGN) 182 { 183 enum tree_code code1 = gimple_assign_rhs_code (stmt1); 184 enum tree_code code2 = gimple_assign_rhs_code (stmt2); 185 186 if (!poor_ifcvt_candidate_code (code1) 187 && !poor_ifcvt_candidate_code (code2)) 188 { 189 tree lhs1 = gimple_assign_lhs (stmt1); 190 tree lhs2 = gimple_assign_lhs (stmt2); 191 gimple_stmt_iterator gsi; 192 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 193 { 194 gimple *phi = gsi_stmt (gsi); 195 if ((gimple_phi_arg_def (phi, 0) == lhs1 196 && gimple_phi_arg_def (phi, 1) == lhs2) 197 || (gimple_phi_arg_def (phi, 1) == lhs1 198 && gimple_phi_arg_def (phi, 0) == lhs2)) 199 { 200 if (dump_file && (dump_flags & TDF_DETAILS)) 201 fprintf (dump_file, 202 "Block %d appears to be a join point for " 203 "if-convertable diamond.\n", 204 bb->index); 205 return false; 206 } 207 } 208 } 209 } 210 } 211 212 /* Canonicalize the form. */ 213 if (num_stmts_in_pred1 == 0 && num_stmts_in_pred2 == 1) 214 { 215 std::swap (pred1, pred2); 216 std::swap (num_stmts_in_pred1, num_stmts_in_pred2); 217 } 218 219 /* Another variant. This one is half-diamond. */ 220 if (num_stmts_in_pred1 == 1 && num_stmts_in_pred2 == 0 221 && dominated_by_p (CDI_DOMINATORS, pred1, pred2)) 222 { 223 gimple *stmt1 = last_and_only_stmt (pred1); 224 225 /* The only statement in PRED1 must be an assignment that is 226 not a good candidate for if-conversion. This may need some 227 generalization. */ 228 if (stmt1 && gimple_code (stmt1) == GIMPLE_ASSIGN) 229 { 230 enum tree_code code1 = gimple_assign_rhs_code (stmt1); 231 232 if (!poor_ifcvt_candidate_code (code1)) 233 { 234 tree lhs1 = gimple_assign_lhs (stmt1); 235 tree rhs1 = gimple_assign_rhs1 (stmt1); 236 237 gimple_stmt_iterator gsi; 238 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 239 { 240 gimple *phi = gsi_stmt (gsi); 241 if ((gimple_phi_arg_def (phi, 0) == lhs1 242 && gimple_phi_arg_def (phi, 1) == rhs1) 243 || (gimple_phi_arg_def (phi, 1) == lhs1 244 && gimple_phi_arg_def (phi, 0) == rhs1)) 245 { 246 if (dump_file && (dump_flags & TDF_DETAILS)) 247 fprintf (dump_file, 248 "Block %d appears to be a join point for " 249 "if-convertable half-diamond.\n", 250 bb->index); 251 return false; 252 } 253 } 254 } 255 } 256 } 257 258 /* Canonicalize the form. */ 259 if (single_pred_p (pred1) && single_pred (pred1) == pred2 260 && num_stmts_in_pred1 == 0) 261 std::swap (pred1, pred2); 262 263 /* This is meant to catch another kind of cases that are likely opportunities 264 for if-conversion. After canonicalizing, PRED2 must be an empty block and 265 PRED1 must be the only predecessor of PRED2. Moreover, PRED1 is supposed 266 to end with a cond_stmt which has the same args with the PHI in BB. */ 267 if (single_pred_p (pred2) && single_pred (pred2) == pred1 268 && num_stmts_in_pred2 == 0) 269 { 270 gimple *cond_stmt = last_stmt (pred1); 271 if (cond_stmt && gimple_code (cond_stmt) == GIMPLE_COND) 272 { 273 tree lhs = gimple_cond_lhs (cond_stmt); 274 tree rhs = gimple_cond_rhs (cond_stmt); 275 276 gimple_stmt_iterator gsi; 277 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 278 { 279 gimple *phi = gsi_stmt (gsi); 280 if ((operand_equal_p (gimple_phi_arg_def (phi, 0), lhs) 281 && operand_equal_p (gimple_phi_arg_def (phi, 1), rhs)) 282 || (operand_equal_p (gimple_phi_arg_def (phi, 0), rhs) 283 && (operand_equal_p (gimple_phi_arg_def (phi, 1), lhs)))) 284 { 285 if (dump_file && (dump_flags & TDF_DETAILS)) 286 fprintf (dump_file, 287 "Block %d appears to be optimized to a join " 288 "point for if-convertable half-diamond.\n", 289 bb->index); 290 return false; 291 } 292 } 293 } 294 } 295 296 /* If the joiner has no PHIs with useful uses there is zero chance 297 of CSE/DCE/jump-threading possibilities exposed by duplicating it. */ 298 bool found_useful_phi = false; 299 for (gphi_iterator si = gsi_start_phis (bb); ! gsi_end_p (si); 300 gsi_next (&si)) 301 { 302 gphi *phi = si.phi (); 303 use_operand_p use_p; 304 imm_use_iterator iter; 305 FOR_EACH_IMM_USE_FAST (use_p, iter, gimple_phi_result (phi)) 306 { 307 gimple *stmt = USE_STMT (use_p); 308 if (is_gimple_debug (stmt)) 309 continue; 310 /* If there's a use in the joiner this might be a CSE/DCE 311 opportunity, but not if the use is in a conditional 312 which makes this a likely if-conversion candidate. */ 313 if (gimple_bb (stmt) == bb 314 && (!is_gimple_assign (stmt) 315 || (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) 316 != tcc_comparison))) 317 { 318 found_useful_phi = true; 319 break; 320 } 321 /* If the use is on a loop header PHI and on one path the 322 value is unchanged this might expose a jump threading 323 opportunity. */ 324 if (gimple_code (stmt) == GIMPLE_PHI 325 && gimple_bb (stmt) == bb->loop_father->header 326 /* But for memory the PHI alone isn't good enough. */ 327 && ! virtual_operand_p (gimple_phi_result (stmt))) 328 { 329 bool found_unchanged_path = false; 330 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i) 331 if (gimple_phi_arg_def (phi, i) == gimple_phi_result (stmt)) 332 { 333 found_unchanged_path = true; 334 break; 335 } 336 /* If we found an unchanged path this can only be a threading 337 opportunity if we have uses of the loop header PHI result 338 in a stmt dominating the merge block. Otherwise the 339 splitting may prevent if-conversion. */ 340 if (found_unchanged_path) 341 { 342 use_operand_p use2_p; 343 imm_use_iterator iter2; 344 FOR_EACH_IMM_USE_FAST (use2_p, iter2, gimple_phi_result (stmt)) 345 { 346 gimple *use_stmt = USE_STMT (use2_p); 347 if (is_gimple_debug (use_stmt)) 348 continue; 349 basic_block use_bb = gimple_bb (use_stmt); 350 if (use_bb != bb 351 && dominated_by_p (CDI_DOMINATORS, bb, use_bb)) 352 { 353 if (gcond *cond = dyn_cast <gcond *> (use_stmt)) 354 if (gimple_cond_code (cond) == EQ_EXPR 355 || gimple_cond_code (cond) == NE_EXPR) 356 found_useful_phi = true; 357 break; 358 } 359 } 360 } 361 if (found_useful_phi) 362 break; 363 } 364 } 365 if (found_useful_phi) 366 break; 367 } 368 /* There is one exception namely a controlling condition we can propagate 369 an equivalence from to the joiner. */ 370 bool found_cprop_opportunity = false; 371 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb); 372 gcond *cond = as_a <gcond *> (last_stmt (dom)); 373 if (gimple_cond_code (cond) == EQ_EXPR 374 || gimple_cond_code (cond) == NE_EXPR) 375 for (unsigned i = 0; i < 2; ++i) 376 { 377 tree op = gimple_op (cond, i); 378 if (TREE_CODE (op) == SSA_NAME) 379 { 380 use_operand_p use_p; 381 imm_use_iterator iter; 382 FOR_EACH_IMM_USE_FAST (use_p, iter, op) 383 { 384 if (is_gimple_debug (USE_STMT (use_p))) 385 continue; 386 if (gimple_bb (USE_STMT (use_p)) == bb) 387 { 388 found_cprop_opportunity = true; 389 break; 390 } 391 } 392 } 393 if (found_cprop_opportunity) 394 break; 395 } 396 397 if (! found_useful_phi && ! found_cprop_opportunity) 398 { 399 if (dump_file && (dump_flags & TDF_DETAILS)) 400 fprintf (dump_file, 401 "Block %d is a join that does not expose CSE/DCE/jump-thread " 402 "opportunities when duplicated.\n", 403 bb->index); 404 return false; 405 } 406 407 /* We may want something here which looks at dataflow and tries 408 to guess if duplication of BB is likely to result in simplification 409 of instructions in BB in either the original or the duplicate. */ 410 411 /* Upper Hard limit on the number statements to copy. */ 412 if (num_stmts_in_join 413 >= param_max_jump_thread_duplication_stmts) 414 return false; 415 416 return true; 417 } 418 419 /* If the immediate dominator of the latch of the loop is 420 block with conditional branch, then the loop latch is 421 duplicated to its predecessors path preserving the SSA 422 semantics. 423 424 CFG before transformation. 425 426 2 427 | 428 | 429 +---->3 430 | / \ 431 | / \ 432 | 4 5 433 | \ / 434 | \ / 435 | 6 436 | / \ 437 | / \ 438 | 8 7 439 | | | 440 ---+ E 441 442 443 444 Block 8 is the latch. We're going to make copies of block 6 (9 & 10) 445 and wire things up so they look like this: 446 447 2 448 | 449 | 450 +---->3 451 | / \ 452 | / \ 453 | 4 5 454 | | | 455 | | | 456 | 9 10 457 | |\ /| 458 | | \ / | 459 | | 7 | 460 | | | | 461 | | E | 462 | | | 463 | \ / 464 | \ / 465 +-----8 466 467 468 Blocks 9 and 10 will get merged into blocks 4 & 5 respectively which 469 enables CSE, DCE and other optimizations to occur on a larger block 470 of code. */ 471 472 static bool 473 split_paths () 474 { 475 bool changed = false; 476 477 loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS); 478 initialize_original_copy_tables (); 479 calculate_dominance_info (CDI_DOMINATORS); 480 481 for (auto loop : loops_list (cfun, LI_FROM_INNERMOST)) 482 { 483 /* Only split paths if we are optimizing this loop for speed. */ 484 if (!optimize_loop_for_speed_p (loop)) 485 continue; 486 487 /* See if there is a block that we can duplicate to split the 488 path to the loop latch. */ 489 basic_block bb 490 = find_block_to_duplicate_for_splitting_paths (loop->latch); 491 492 /* BB is the merge point for an IF-THEN-ELSE we want to transform. 493 494 Essentially we want to create a duplicate of bb and redirect the 495 first predecessor of BB to the duplicate (leaving the second 496 predecessor as is. This will split the path leading to the latch 497 re-using BB to avoid useless copying. */ 498 if (bb && is_feasible_trace (bb)) 499 { 500 if (dump_file && (dump_flags & TDF_DETAILS)) 501 fprintf (dump_file, 502 "Duplicating join block %d into predecessor paths\n", 503 bb->index); 504 basic_block pred0 = EDGE_PRED (bb, 0)->src; 505 if (EDGE_COUNT (pred0->succs) != 1) 506 pred0 = EDGE_PRED (bb, 1)->src; 507 transform_duplicate (pred0, bb); 508 changed = true; 509 510 /* If BB has an outgoing edge marked as IRREDUCIBLE, then 511 duplicating BB may result in an irreducible region turning 512 into a natural loop. 513 514 Long term we might want to hook this into the block 515 duplication code, but as we've seen with similar changes 516 for edge removal, that can be somewhat risky. */ 517 if (EDGE_SUCC (bb, 0)->flags & EDGE_IRREDUCIBLE_LOOP 518 || EDGE_SUCC (bb, 1)->flags & EDGE_IRREDUCIBLE_LOOP) 519 { 520 if (dump_file && (dump_flags & TDF_DETAILS)) 521 fprintf (dump_file, 522 "Join block %d has EDGE_IRREDUCIBLE_LOOP set. " 523 "Scheduling loop fixups.\n", 524 bb->index); 525 loops_state_set (LOOPS_NEED_FIXUP); 526 } 527 } 528 } 529 530 loop_optimizer_finalize (); 531 free_original_copy_tables (); 532 return changed; 533 } 534 535 /* Main entry point for splitting paths. Returns TODO_cleanup_cfg if any 536 paths where split, otherwise return zero. */ 537 538 static unsigned int 539 execute_split_paths () 540 { 541 /* If we don't have at least 2 real blocks and backedges in the 542 CFG, then there's no point in trying to perform path splitting. */ 543 if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1 544 || !mark_dfs_back_edges ()) 545 return 0; 546 547 bool changed = split_paths(); 548 if (changed) 549 free_dominance_info (CDI_DOMINATORS); 550 551 return changed ? TODO_cleanup_cfg : 0; 552 } 553 554 static bool 555 gate_split_paths () 556 { 557 return flag_split_paths; 558 } 559 560 namespace { 561 562 const pass_data pass_data_split_paths = 563 { 564 GIMPLE_PASS, /* type */ 565 "split-paths", /* name */ 566 OPTGROUP_NONE, /* optinfo_flags */ 567 TV_SPLIT_PATHS, /* tv_id */ 568 PROP_ssa, /* properties_required */ 569 0, /* properties_provided */ 570 0, /* properties_destroyed */ 571 0, /* todo_flags_start */ 572 TODO_update_ssa, /* todo_flags_finish */ 573 }; 574 575 class pass_split_paths : public gimple_opt_pass 576 { 577 public: 578 pass_split_paths (gcc::context *ctxt) 579 : gimple_opt_pass (pass_data_split_paths, ctxt) 580 {} 581 /* opt_pass methods: */ 582 opt_pass * clone () { return new pass_split_paths (m_ctxt); } 583 virtual bool gate (function *) { return gate_split_paths (); } 584 virtual unsigned int execute (function *) { return execute_split_paths (); } 585 586 }; // class pass_split_paths 587 588 } // anon namespace 589 590 gimple_opt_pass * 591 make_pass_split_paths (gcc::context *ctxt) 592 { 593 return new pass_split_paths (ctxt); 594 } 595