1 /* Code sinking for trees 2 Copyright (C) 2001-2018 Free Software Foundation, Inc. 3 Contributed by Daniel Berlin <dan@dberlin.org> 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 "cfghooks.h" 28 #include "tree-pass.h" 29 #include "ssa.h" 30 #include "gimple-pretty-print.h" 31 #include "fold-const.h" 32 #include "stor-layout.h" 33 #include "cfganal.h" 34 #include "gimple-iterator.h" 35 #include "tree-cfg.h" 36 #include "cfgloop.h" 37 #include "params.h" 38 39 /* TODO: 40 1. Sinking store only using scalar promotion (IE without moving the RHS): 41 42 *q = p; 43 p = p + 1; 44 if (something) 45 *q = <not p>; 46 else 47 y = *q; 48 49 50 should become 51 sinktemp = p; 52 p = p + 1; 53 if (something) 54 *q = <not p>; 55 else 56 { 57 *q = sinktemp; 58 y = *q 59 } 60 Store copy propagation will take care of the store elimination above. 61 62 63 2. Sinking using Partial Dead Code Elimination. */ 64 65 66 static struct 67 { 68 /* The number of statements sunk down the flowgraph by code sinking. */ 69 int sunk; 70 71 } sink_stats; 72 73 74 /* Given a PHI, and one of its arguments (DEF), find the edge for 75 that argument and return it. If the argument occurs twice in the PHI node, 76 we return NULL. */ 77 78 static basic_block 79 find_bb_for_arg (gphi *phi, tree def) 80 { 81 size_t i; 82 bool foundone = false; 83 basic_block result = NULL; 84 for (i = 0; i < gimple_phi_num_args (phi); i++) 85 if (PHI_ARG_DEF (phi, i) == def) 86 { 87 if (foundone) 88 return NULL; 89 foundone = true; 90 result = gimple_phi_arg_edge (phi, i)->src; 91 } 92 return result; 93 } 94 95 /* When the first immediate use is in a statement, then return true if all 96 immediate uses in IMM are in the same statement. 97 We could also do the case where the first immediate use is in a phi node, 98 and all the other uses are in phis in the same basic block, but this 99 requires some expensive checking later (you have to make sure no def/vdef 100 in the statement occurs for multiple edges in the various phi nodes it's 101 used in, so that you only have one place you can sink it to. */ 102 103 static bool 104 all_immediate_uses_same_place (def_operand_p def_p) 105 { 106 tree var = DEF_FROM_PTR (def_p); 107 imm_use_iterator imm_iter; 108 use_operand_p use_p; 109 110 gimple *firstuse = NULL; 111 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var) 112 { 113 if (is_gimple_debug (USE_STMT (use_p))) 114 continue; 115 if (firstuse == NULL) 116 firstuse = USE_STMT (use_p); 117 else 118 if (firstuse != USE_STMT (use_p)) 119 return false; 120 } 121 122 return true; 123 } 124 125 /* Find the nearest common dominator of all of the immediate uses in IMM. */ 126 127 static basic_block 128 nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts) 129 { 130 tree var = DEF_FROM_PTR (def_p); 131 auto_bitmap blocks; 132 basic_block commondom; 133 unsigned int j; 134 bitmap_iterator bi; 135 imm_use_iterator imm_iter; 136 use_operand_p use_p; 137 138 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var) 139 { 140 gimple *usestmt = USE_STMT (use_p); 141 basic_block useblock; 142 143 if (gphi *phi = dyn_cast <gphi *> (usestmt)) 144 { 145 int idx = PHI_ARG_INDEX_FROM_USE (use_p); 146 147 useblock = gimple_phi_arg_edge (phi, idx)->src; 148 } 149 else if (is_gimple_debug (usestmt)) 150 { 151 *debug_stmts = true; 152 continue; 153 } 154 else 155 { 156 useblock = gimple_bb (usestmt); 157 } 158 159 /* Short circuit. Nothing dominates the entry block. */ 160 if (useblock == ENTRY_BLOCK_PTR_FOR_FN (cfun)) 161 return NULL; 162 163 bitmap_set_bit (blocks, useblock->index); 164 } 165 commondom = BASIC_BLOCK_FOR_FN (cfun, bitmap_first_set_bit (blocks)); 166 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi) 167 commondom = nearest_common_dominator (CDI_DOMINATORS, commondom, 168 BASIC_BLOCK_FOR_FN (cfun, j)); 169 return commondom; 170 } 171 172 /* Given EARLY_BB and LATE_BB, two blocks in a path through the dominator 173 tree, return the best basic block between them (inclusive) to place 174 statements. 175 176 We want the most control dependent block in the shallowest loop nest. 177 178 If the resulting block is in a shallower loop nest, then use it. Else 179 only use the resulting block if it has significantly lower execution 180 frequency than EARLY_BB to avoid gratutious statement movement. We 181 consider statements with VOPS more desirable to move. 182 183 This pass would obviously benefit from PDO as it utilizes block 184 frequencies. It would also benefit from recomputing frequencies 185 if profile data is not available since frequencies often get out 186 of sync with reality. */ 187 188 static basic_block 189 select_best_block (basic_block early_bb, 190 basic_block late_bb, 191 gimple *stmt) 192 { 193 basic_block best_bb = late_bb; 194 basic_block temp_bb = late_bb; 195 int threshold; 196 197 while (temp_bb != early_bb) 198 { 199 /* If we've moved into a lower loop nest, then that becomes 200 our best block. */ 201 if (bb_loop_depth (temp_bb) < bb_loop_depth (best_bb)) 202 best_bb = temp_bb; 203 204 /* Walk up the dominator tree, hopefully we'll find a shallower 205 loop nest. */ 206 temp_bb = get_immediate_dominator (CDI_DOMINATORS, temp_bb); 207 } 208 209 /* If we found a shallower loop nest, then we always consider that 210 a win. This will always give us the most control dependent block 211 within that loop nest. */ 212 if (bb_loop_depth (best_bb) < bb_loop_depth (early_bb)) 213 return best_bb; 214 215 /* Get the sinking threshold. If the statement to be moved has memory 216 operands, then increase the threshold by 7% as those are even more 217 profitable to avoid, clamping at 100%. */ 218 threshold = PARAM_VALUE (PARAM_SINK_FREQUENCY_THRESHOLD); 219 if (gimple_vuse (stmt) || gimple_vdef (stmt)) 220 { 221 threshold += 7; 222 if (threshold > 100) 223 threshold = 100; 224 } 225 226 /* If BEST_BB is at the same nesting level, then require it to have 227 significantly lower execution frequency to avoid gratutious movement. */ 228 if (bb_loop_depth (best_bb) == bb_loop_depth (early_bb) 229 /* If result of comparsion is unknown, preffer EARLY_BB. 230 Thus use !(...>=..) rather than (...<...) */ 231 && !(best_bb->count.apply_scale (100, 1) 232 > (early_bb->count.apply_scale (threshold, 1)))) 233 return best_bb; 234 235 /* No better block found, so return EARLY_BB, which happens to be the 236 statement's original block. */ 237 return early_bb; 238 } 239 240 /* Given a statement (STMT) and the basic block it is currently in (FROMBB), 241 determine the location to sink the statement to, if any. 242 Returns true if there is such location; in that case, TOGSI points to the 243 statement before that STMT should be moved. */ 244 245 static bool 246 statement_sink_location (gimple *stmt, basic_block frombb, 247 gimple_stmt_iterator *togsi, bool *zero_uses_p) 248 { 249 gimple *use; 250 use_operand_p one_use = NULL_USE_OPERAND_P; 251 basic_block sinkbb; 252 use_operand_p use_p; 253 def_operand_p def_p; 254 ssa_op_iter iter; 255 imm_use_iterator imm_iter; 256 257 *zero_uses_p = false; 258 259 /* We only can sink assignments and non-looping const/pure calls. */ 260 int cf; 261 if (!is_gimple_assign (stmt) 262 && (!is_gimple_call (stmt) 263 || !((cf = gimple_call_flags (stmt)) & (ECF_CONST|ECF_PURE)) 264 || (cf & ECF_LOOPING_CONST_OR_PURE))) 265 return false; 266 267 /* We only can sink stmts with a single definition. */ 268 def_p = single_ssa_def_operand (stmt, SSA_OP_ALL_DEFS); 269 if (def_p == NULL_DEF_OPERAND_P) 270 return false; 271 272 /* There are a few classes of things we can't or don't move, some because we 273 don't have code to handle it, some because it's not profitable and some 274 because it's not legal. 275 276 We can't sink things that may be global stores, at least not without 277 calculating a lot more information, because we may cause it to no longer 278 be seen by an external routine that needs it depending on where it gets 279 moved to. 280 281 We can't sink statements that end basic blocks without splitting the 282 incoming edge for the sink location to place it there. 283 284 We can't sink statements that have volatile operands. 285 286 We don't want to sink dead code, so anything with 0 immediate uses is not 287 sunk. 288 289 Don't sink BLKmode assignments if current function has any local explicit 290 register variables, as BLKmode assignments may involve memcpy or memset 291 calls or, on some targets, inline expansion thereof that sometimes need 292 to use specific hard registers. 293 294 */ 295 if (stmt_ends_bb_p (stmt) 296 || gimple_has_side_effects (stmt) 297 || (cfun->has_local_explicit_reg_vars 298 && TYPE_MODE (TREE_TYPE (gimple_get_lhs (stmt))) == BLKmode)) 299 return false; 300 301 /* Return if there are no immediate uses of this stmt. */ 302 if (has_zero_uses (DEF_FROM_PTR (def_p))) 303 { 304 *zero_uses_p = true; 305 return false; 306 } 307 308 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (DEF_FROM_PTR (def_p))) 309 return false; 310 311 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) 312 { 313 tree use = USE_FROM_PTR (use_p); 314 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use)) 315 return false; 316 } 317 318 use = NULL; 319 320 /* If stmt is a store the one and only use needs to be the VOP 321 merging PHI node. */ 322 if (virtual_operand_p (DEF_FROM_PTR (def_p))) 323 { 324 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p)) 325 { 326 gimple *use_stmt = USE_STMT (use_p); 327 328 /* A killing definition is not a use. */ 329 if ((gimple_has_lhs (use_stmt) 330 && operand_equal_p (gimple_get_lhs (stmt), 331 gimple_get_lhs (use_stmt), 0)) 332 || stmt_kills_ref_p (use_stmt, gimple_get_lhs (stmt))) 333 { 334 /* If use_stmt is or might be a nop assignment then USE_STMT 335 acts as a use as well as definition. */ 336 if (stmt != use_stmt 337 && ref_maybe_used_by_stmt_p (use_stmt, 338 gimple_get_lhs (stmt))) 339 return false; 340 continue; 341 } 342 343 if (gimple_code (use_stmt) != GIMPLE_PHI) 344 return false; 345 346 if (use 347 && use != use_stmt) 348 return false; 349 350 use = use_stmt; 351 } 352 if (!use) 353 return false; 354 } 355 /* If all the immediate uses are not in the same place, find the nearest 356 common dominator of all the immediate uses. For PHI nodes, we have to 357 find the nearest common dominator of all of the predecessor blocks, since 358 that is where insertion would have to take place. */ 359 else if (gimple_vuse (stmt) 360 || !all_immediate_uses_same_place (def_p)) 361 { 362 bool debug_stmts = false; 363 basic_block commondom = nearest_common_dominator_of_uses (def_p, 364 &debug_stmts); 365 366 if (commondom == frombb) 367 return false; 368 369 /* If this is a load then do not sink past any stores. 370 ??? This is overly simple but cheap. We basically look 371 for an existing load with the same VUSE in the path to one 372 of the sink candidate blocks and we adjust commondom to the 373 nearest to commondom. */ 374 if (gimple_vuse (stmt)) 375 { 376 /* Do not sink loads from hard registers. */ 377 if (gimple_assign_single_p (stmt) 378 && TREE_CODE (gimple_assign_rhs1 (stmt)) == VAR_DECL 379 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt))) 380 return false; 381 382 imm_use_iterator imm_iter; 383 use_operand_p use_p; 384 basic_block found = NULL; 385 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_vuse (stmt)) 386 { 387 gimple *use_stmt = USE_STMT (use_p); 388 basic_block bb = gimple_bb (use_stmt); 389 /* For PHI nodes the block we know sth about 390 is the incoming block with the use. */ 391 if (gimple_code (use_stmt) == GIMPLE_PHI) 392 bb = EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src; 393 /* Any dominator of commondom would be ok with 394 adjusting commondom to that block. */ 395 bb = nearest_common_dominator (CDI_DOMINATORS, bb, commondom); 396 if (!found) 397 found = bb; 398 else if (dominated_by_p (CDI_DOMINATORS, bb, found)) 399 found = bb; 400 /* If we can't improve, stop. */ 401 if (found == commondom) 402 break; 403 } 404 commondom = found; 405 if (commondom == frombb) 406 return false; 407 } 408 409 /* Our common dominator has to be dominated by frombb in order to be a 410 trivially safe place to put this statement, since it has multiple 411 uses. */ 412 if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb)) 413 return false; 414 415 commondom = select_best_block (frombb, commondom, stmt); 416 417 if (commondom == frombb) 418 return false; 419 420 *togsi = gsi_after_labels (commondom); 421 422 return true; 423 } 424 else 425 { 426 FOR_EACH_IMM_USE_FAST (one_use, imm_iter, DEF_FROM_PTR (def_p)) 427 { 428 if (is_gimple_debug (USE_STMT (one_use))) 429 continue; 430 break; 431 } 432 use = USE_STMT (one_use); 433 434 if (gimple_code (use) != GIMPLE_PHI) 435 { 436 sinkbb = gimple_bb (use); 437 sinkbb = select_best_block (frombb, gimple_bb (use), stmt); 438 439 if (sinkbb == frombb) 440 return false; 441 442 *togsi = gsi_for_stmt (use); 443 444 return true; 445 } 446 } 447 448 sinkbb = find_bb_for_arg (as_a <gphi *> (use), DEF_FROM_PTR (def_p)); 449 450 /* This can happen if there are multiple uses in a PHI. */ 451 if (!sinkbb) 452 return false; 453 454 sinkbb = select_best_block (frombb, sinkbb, stmt); 455 if (!sinkbb || sinkbb == frombb) 456 return false; 457 458 /* If the latch block is empty, don't make it non-empty by sinking 459 something into it. */ 460 if (sinkbb == frombb->loop_father->latch 461 && empty_block_p (sinkbb)) 462 return false; 463 464 *togsi = gsi_after_labels (sinkbb); 465 466 return true; 467 } 468 469 /* Perform code sinking on BB */ 470 471 static void 472 sink_code_in_bb (basic_block bb) 473 { 474 basic_block son; 475 gimple_stmt_iterator gsi; 476 edge_iterator ei; 477 edge e; 478 bool last = true; 479 480 /* If this block doesn't dominate anything, there can't be any place to sink 481 the statements to. */ 482 if (first_dom_son (CDI_DOMINATORS, bb) == NULL) 483 goto earlyout; 484 485 /* We can't move things across abnormal edges, so don't try. */ 486 FOR_EACH_EDGE (e, ei, bb->succs) 487 if (e->flags & EDGE_ABNORMAL) 488 goto earlyout; 489 490 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);) 491 { 492 gimple *stmt = gsi_stmt (gsi); 493 gimple_stmt_iterator togsi; 494 bool zero_uses_p; 495 496 if (!statement_sink_location (stmt, bb, &togsi, &zero_uses_p)) 497 { 498 gimple_stmt_iterator saved = gsi; 499 if (!gsi_end_p (gsi)) 500 gsi_prev (&gsi); 501 /* If we face a dead stmt remove it as it possibly blocks 502 sinking of uses. */ 503 if (zero_uses_p 504 && ! gimple_vdef (stmt)) 505 { 506 gsi_remove (&saved, true); 507 release_defs (stmt); 508 } 509 else 510 last = false; 511 continue; 512 } 513 if (dump_file) 514 { 515 fprintf (dump_file, "Sinking "); 516 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS); 517 fprintf (dump_file, " from bb %d to bb %d\n", 518 bb->index, (gsi_bb (togsi))->index); 519 } 520 521 /* Update virtual operands of statements in the path we 522 do not sink to. */ 523 if (gimple_vdef (stmt)) 524 { 525 imm_use_iterator iter; 526 use_operand_p use_p; 527 gimple *vuse_stmt; 528 529 FOR_EACH_IMM_USE_STMT (vuse_stmt, iter, gimple_vdef (stmt)) 530 if (gimple_code (vuse_stmt) != GIMPLE_PHI) 531 FOR_EACH_IMM_USE_ON_STMT (use_p, iter) 532 SET_USE (use_p, gimple_vuse (stmt)); 533 } 534 535 /* If this is the end of the basic block, we need to insert at the end 536 of the basic block. */ 537 if (gsi_end_p (togsi)) 538 gsi_move_to_bb_end (&gsi, gsi_bb (togsi)); 539 else 540 gsi_move_before (&gsi, &togsi); 541 542 sink_stats.sunk++; 543 544 /* If we've just removed the last statement of the BB, the 545 gsi_end_p() test below would fail, but gsi_prev() would have 546 succeeded, and we want it to succeed. So we keep track of 547 whether we're at the last statement and pick up the new last 548 statement. */ 549 if (last) 550 { 551 gsi = gsi_last_bb (bb); 552 continue; 553 } 554 555 last = false; 556 if (!gsi_end_p (gsi)) 557 gsi_prev (&gsi); 558 559 } 560 earlyout: 561 for (son = first_dom_son (CDI_POST_DOMINATORS, bb); 562 son; 563 son = next_dom_son (CDI_POST_DOMINATORS, son)) 564 { 565 sink_code_in_bb (son); 566 } 567 } 568 569 /* Perform code sinking. 570 This moves code down the flowgraph when we know it would be 571 profitable to do so, or it wouldn't increase the number of 572 executions of the statement. 573 574 IE given 575 576 a_1 = b + c; 577 if (<something>) 578 { 579 } 580 else 581 { 582 foo (&b, &c); 583 a_5 = b + c; 584 } 585 a_6 = PHI (a_5, a_1); 586 USE a_6. 587 588 we'll transform this into: 589 590 if (<something>) 591 { 592 a_1 = b + c; 593 } 594 else 595 { 596 foo (&b, &c); 597 a_5 = b + c; 598 } 599 a_6 = PHI (a_5, a_1); 600 USE a_6. 601 602 Note that this reduces the number of computations of a = b + c to 1 603 when we take the else edge, instead of 2. 604 */ 605 namespace { 606 607 const pass_data pass_data_sink_code = 608 { 609 GIMPLE_PASS, /* type */ 610 "sink", /* name */ 611 OPTGROUP_NONE, /* optinfo_flags */ 612 TV_TREE_SINK, /* tv_id */ 613 /* PROP_no_crit_edges is ensured by running split_critical_edges in 614 pass_data_sink_code::execute (). */ 615 ( PROP_cfg | PROP_ssa ), /* properties_required */ 616 0, /* properties_provided */ 617 0, /* properties_destroyed */ 618 0, /* todo_flags_start */ 619 TODO_update_ssa, /* todo_flags_finish */ 620 }; 621 622 class pass_sink_code : public gimple_opt_pass 623 { 624 public: 625 pass_sink_code (gcc::context *ctxt) 626 : gimple_opt_pass (pass_data_sink_code, ctxt) 627 {} 628 629 /* opt_pass methods: */ 630 virtual bool gate (function *) { return flag_tree_sink != 0; } 631 virtual unsigned int execute (function *); 632 633 }; // class pass_sink_code 634 635 unsigned int 636 pass_sink_code::execute (function *fun) 637 { 638 loop_optimizer_init (LOOPS_NORMAL); 639 split_critical_edges (); 640 connect_infinite_loops_to_exit (); 641 memset (&sink_stats, 0, sizeof (sink_stats)); 642 calculate_dominance_info (CDI_DOMINATORS); 643 calculate_dominance_info (CDI_POST_DOMINATORS); 644 sink_code_in_bb (EXIT_BLOCK_PTR_FOR_FN (fun)); 645 statistics_counter_event (fun, "Sunk statements", sink_stats.sunk); 646 free_dominance_info (CDI_POST_DOMINATORS); 647 remove_fake_exit_edges (); 648 loop_optimizer_finalize (); 649 650 return 0; 651 } 652 653 } // anon namespace 654 655 gimple_opt_pass * 656 make_pass_sink_code (gcc::context *ctxt) 657 { 658 return new pass_sink_code (ctxt); 659 } 660