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