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