tree-ssa-sink.c revision 169689
198567Sobrien/* Code sinking for trees 278344Sobrien Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc. 378344Sobrien Contributed by Daniel Berlin <dan@dberlin.org> 478344Sobrien 578344SobrienThis file is part of GCC. 678344Sobrien 778344SobrienGCC is free software; you can redistribute it and/or modify 878344Sobrienit under the terms of the GNU General Public License as published by 978344Sobrienthe Free Software Foundation; either version 2, or (at your option) 1078344Sobrienany later version. 1178344Sobrien 1278344SobrienGCC is distributed in the hope that it will be useful, 1378344Sobrienbut WITHOUT ANY WARRANTY; without even the implied warranty of 1478344SobrienMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1578344SobrienGNU General Public License for more details. 1678344Sobrien 1778344SobrienYou should have received a copy of the GNU General Public License 1878344Sobrienalong with GCC; see the file COPYING. If not, write to 1978344Sobrienthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 2078344SobrienBoston, MA 02110-1301, USA. */ 2178344Sobrien 2278344Sobrien#include "config.h" 2378344Sobrien#include "system.h" 2478344Sobrien#include "coretypes.h" 2578344Sobrien#include "tm.h" 2678344Sobrien#include "ggc.h" 2778344Sobrien#include "tree.h" 2878344Sobrien#include "basic-block.h" 2978344Sobrien#include "diagnostic.h" 3078344Sobrien#include "tree-inline.h" 3178344Sobrien#include "tree-flow.h" 3299502Scharnier#include "tree-gimple.h" 3378344Sobrien#include "tree-dump.h" 34224673Sdougb#include "timevar.h" 3578344Sobrien#include "fibheap.h" 3678344Sobrien#include "hashtab.h" 3778344Sobrien#include "tree-iterator.h" 3878344Sobrien#include "real.h" 3978344Sobrien#include "alloc-pool.h" 4078344Sobrien#include "tree-pass.h" 4178344Sobrien#include "flags.h" 4278344Sobrien#include "bitmap.h" 4378344Sobrien#include "langhooks.h" 4478344Sobrien#include "cfgloop.h" 4578344Sobrien 4699502Scharnier/* TODO: 4778344Sobrien 1. Sinking store only using scalar promotion (IE without moving the RHS): 4899502Scharnier 49107234Sru *q = p; 50107234Sru p = p + 1; 5178344Sobrien if (something) 5278344Sobrien *q = <not p>; 5378344Sobrien else 5478344Sobrien y = *q; 5578344Sobrien 5678344Sobrien 5778344Sobrien should become 5878344Sobrien sinktemp = p; 5978344Sobrien p = p + 1; 6078344Sobrien if (something) 6178344Sobrien *q = <not p>; 6278344Sobrien else 6378344Sobrien { 6478344Sobrien *q = sinktemp; 65107234Sru y = *q 66107234Sru } 67107234Sru Store copy propagation will take care of the store elimination above. 6878344Sobrien 69107234Sru 7078344Sobrien 2. Sinking using Partial Dead Code Elimination. */ 71107234Sru 72107234Sru 73107234Srustatic struct 7478344Sobrien{ 75107234Sru /* The number of statements sunk down the flowgraph by code sinking. */ 76107234Sru int sunk; 77107234Sru 7878344Sobrien} sink_stats; 79107234Sru 8078344Sobrien 8178344Sobrien/* Given a PHI, and one of its arguments (DEF), find the edge for 82107234Sru that argument and return it. If the argument occurs twice in the PHI node, 83107234Sru we return NULL. */ 84107234Sru 85107234Srustatic basic_block 86107234Srufind_bb_for_arg (tree phi, tree def) 8778344Sobrien{ 88107234Sru int i; 8998567Sobrien bool foundone = false; 9078344Sobrien basic_block result = NULL; 9178344Sobrien for (i = 0; i < PHI_NUM_ARGS (phi); i++) 92224673Sdougb if (PHI_ARG_DEF (phi, i) == def) 93224673Sdougb { 94224673Sdougb if (foundone) 9578344Sobrien return NULL; 9678344Sobrien foundone = true; 97107234Sru result = PHI_ARG_EDGE (phi, i)->src; 9878344Sobrien } 9978344Sobrien return result; 100107234Sru} 10178344Sobrien 10278344Sobrien/* When the first immediate use is in a statement, then return true if all 10378344Sobrien immediate uses in IMM are in the same statement. 10478344Sobrien We could also do the case where the first immediate use is in a phi node, 10578344Sobrien and all the other uses are in phis in the same basic block, but this 106107234Sru requires some expensive checking later (you have to make sure no def/vdef 10778344Sobrien in the statement occurs for multiple edges in the various phi nodes it's 10878344Sobrien used in, so that you only have one place you can sink it to. */ 10978344Sobrien 11078344Sobrienstatic bool 11178344Sobrienall_immediate_uses_same_place (tree stmt) 112131470Sru{ 11378344Sobrien tree firstuse = NULL_TREE; 11478344Sobrien ssa_op_iter op_iter; 11578344Sobrien imm_use_iterator imm_iter; 11678344Sobrien use_operand_p use_p; 11778344Sobrien tree var; 11878344Sobrien 11978344Sobrien FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS) 120107234Sru { 121107234Sru FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var) 12278344Sobrien { 123107234Sru if (firstuse == NULL_TREE) 12478344Sobrien firstuse = USE_STMT (use_p); 125107234Sru else 12678344Sobrien if (firstuse != USE_STMT (use_p)) 127107234Sru return false; 12878344Sobrien } 12978344Sobrien } 13078344Sobrien 131107234Sru return true; 13278344Sobrien} 133107234Sru 13478344Sobrien/* Some global stores don't necessarily have V_MAY_DEF's of global variables, 13578344Sobrien but we still must avoid moving them around. */ 13678344Sobrien 13778344Sobrienbool 13878344Sobrienis_hidden_global_store (tree stmt) 13978344Sobrien{ 14099502Scharnier /* Check virtual definitions. If we get here, the only virtual 14178344Sobrien definitions we should see are those generated by assignment 14299502Scharnier statements. */ 14378344Sobrien if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)) 14478344Sobrien { 14578344Sobrien tree lhs; 14678344Sobrien 147107234Sru gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR); 14878344Sobrien 149107234Sru /* Note that we must not check the individual virtual operands 15078344Sobrien here. In particular, if this is an aliased store, we could 15178344Sobrien end up with something like the following (SSA notation 15278344Sobrien redacted for brevity): 15378344Sobrien 15478344Sobrien foo (int *p, int i) 15578344Sobrien { 15678344Sobrien int x; 15778344Sobrien p_1 = (i_2 > 3) ? &x : p; 158208027Suqs 159208027Suqs # x_4 = V_MAY_DEF <x_3> 160208027Suqs *p_1 = 5; 161208027Suqs 162208027Suqs return 2; 163208027Suqs } 164208027Suqs 165208027Suqs Notice that the store to '*p_1' should be preserved, if we 166208027Suqs were to check the virtual definitions in that store, we would 167208027Suqs not mark it needed. This is because 'x' is not a global 168208027Suqs variable. 169208027Suqs 170208027Suqs Therefore, we check the base address of the LHS. If the 171179669Smtm address is a pointer, we check if its name tag or symbol tag is 172179669Smtm a global variable. Otherwise, we check if the base variable 173179669Smtm is a global. */ 174179669Smtm lhs = TREE_OPERAND (stmt, 0); 175179669Smtm if (REFERENCE_CLASS_P (lhs)) 176179669Smtm lhs = get_base_address (lhs); 177179669Smtm 178179669Smtm if (lhs == NULL_TREE) 179179669Smtm { 180179669Smtm /* If LHS is NULL, it means that we couldn't get the base 181179669Smtm address of the reference. In which case, we should not 182179669Smtm move this store. */ 183179669Smtm return true; 184233648Seadler } 185179669Smtm else if (DECL_P (lhs)) 186179669Smtm { 187179669Smtm /* If the store is to a global symbol, we need to keep it. */ 188179669Smtm if (is_global_var (lhs)) 189179669Smtm return true; 190 191 } 192 else if (INDIRECT_REF_P (lhs)) 193 { 194 tree ptr = TREE_OPERAND (lhs, 0); 195 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); 196 tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE; 197 tree smt = var_ann (SSA_NAME_VAR (ptr))->symbol_mem_tag; 198 199 /* If either the name tag or the symbol tag for PTR is a 200 global variable, then the store is necessary. */ 201 if ((nmt && is_global_var (nmt)) 202 || (smt && is_global_var (smt))) 203 { 204 return true; 205 } 206 } 207 else 208 gcc_unreachable (); 209 } 210 return false; 211} 212 213/* Find the nearest common dominator of all of the immediate uses in IMM. */ 214 215static basic_block 216nearest_common_dominator_of_uses (tree stmt) 217{ 218 bitmap blocks = BITMAP_ALLOC (NULL); 219 basic_block commondom; 220 unsigned int j; 221 bitmap_iterator bi; 222 ssa_op_iter op_iter; 223 imm_use_iterator imm_iter; 224 use_operand_p use_p; 225 tree var; 226 227 bitmap_clear (blocks); 228 FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS) 229 { 230 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var) 231 { 232 tree usestmt = USE_STMT (use_p); 233 basic_block useblock; 234 235 if (TREE_CODE (usestmt) == PHI_NODE) 236 { 237 int idx = PHI_ARG_INDEX_FROM_USE (use_p); 238 239 useblock = PHI_ARG_EDGE (usestmt, idx)->src; 240 } 241 else 242 { 243 useblock = bb_for_stmt (usestmt); 244 } 245 246 /* Short circuit. Nothing dominates the entry block. */ 247 if (useblock == ENTRY_BLOCK_PTR) 248 { 249 BITMAP_FREE (blocks); 250 return NULL; 251 } 252 bitmap_set_bit (blocks, useblock->index); 253 } 254 } 255 commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks)); 256 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi) 257 commondom = nearest_common_dominator (CDI_DOMINATORS, commondom, 258 BASIC_BLOCK (j)); 259 BITMAP_FREE (blocks); 260 return commondom; 261} 262 263/* Given a statement (STMT) and the basic block it is currently in (FROMBB), 264 determine the location to sink the statement to, if any. 265 Return the basic block to sink it to, or NULL if we should not sink 266 it. */ 267 268static tree 269statement_sink_location (tree stmt, basic_block frombb) 270{ 271 tree use, def; 272 use_operand_p one_use = NULL_USE_OPERAND_P; 273 basic_block sinkbb; 274 use_operand_p use_p; 275 def_operand_p def_p; 276 ssa_op_iter iter; 277 stmt_ann_t ann; 278 tree rhs; 279 imm_use_iterator imm_iter; 280 281 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 282 { 283 FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def) 284 { 285 break; 286 } 287 if (one_use != NULL_USE_OPERAND_P) 288 break; 289 } 290 291 /* Return if there are no immediate uses of this stmt. */ 292 if (one_use == NULL_USE_OPERAND_P) 293 return NULL; 294 295 if (TREE_CODE (stmt) != MODIFY_EXPR) 296 return NULL; 297 rhs = TREE_OPERAND (stmt, 1); 298 299 /* There are a few classes of things we can't or don't move, some because we 300 don't have code to handle it, some because it's not profitable and some 301 because it's not legal. 302 303 We can't sink things that may be global stores, at least not without 304 calculating a lot more information, because we may cause it to no longer 305 be seen by an external routine that needs it depending on where it gets 306 moved to. 307 308 We don't want to sink loads from memory. 309 310 We can't sink statements that end basic blocks without splitting the 311 incoming edge for the sink location to place it there. 312 313 We can't sink statements that have volatile operands. 314 315 We don't want to sink dead code, so anything with 0 immediate uses is not 316 sunk. 317 318 */ 319 ann = stmt_ann (stmt); 320 if (stmt_ends_bb_p (stmt) 321 || TREE_SIDE_EFFECTS (rhs) 322 || TREE_CODE (rhs) == EXC_PTR_EXPR 323 || TREE_CODE (rhs) == FILTER_EXPR 324 || is_hidden_global_store (stmt) 325 || ann->has_volatile_ops 326 || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE)) 327 return NULL; 328 329 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS) 330 { 331 tree def = DEF_FROM_PTR (def_p); 332 if (is_global_var (SSA_NAME_VAR (def)) 333 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)) 334 return NULL; 335 } 336 337 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) 338 { 339 tree use = USE_FROM_PTR (use_p); 340 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use)) 341 return NULL; 342 } 343 344 /* If all the immediate uses are not in the same place, find the nearest 345 common dominator of all the immediate uses. For PHI nodes, we have to 346 find the nearest common dominator of all of the predecessor blocks, since 347 that is where insertion would have to take place. */ 348 if (!all_immediate_uses_same_place (stmt)) 349 { 350 basic_block commondom = nearest_common_dominator_of_uses (stmt); 351 352 if (commondom == frombb) 353 return NULL; 354 355 /* Our common dominator has to be dominated by frombb in order to be a 356 trivially safe place to put this statement, since it has multiple 357 uses. */ 358 if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb)) 359 return NULL; 360 361 /* It doesn't make sense to move to a dominator that post-dominates 362 frombb, because it means we've just moved it into a path that always 363 executes if frombb executes, instead of reducing the number of 364 executions . */ 365 if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom)) 366 { 367 if (dump_file && (dump_flags & TDF_DETAILS)) 368 fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n"); 369 return NULL; 370 } 371 372 if (commondom == frombb || commondom->loop_depth > frombb->loop_depth) 373 return NULL; 374 if (dump_file && (dump_flags & TDF_DETAILS)) 375 { 376 fprintf (dump_file, "Common dominator of all uses is %d\n", 377 commondom->index); 378 } 379 return first_stmt (commondom); 380 } 381 382 use = USE_STMT (one_use); 383 if (TREE_CODE (use) != PHI_NODE) 384 { 385 sinkbb = bb_for_stmt (use); 386 if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth 387 || sinkbb->loop_father != frombb->loop_father) 388 return NULL; 389 return use; 390 } 391 392 /* Note that at this point, all uses must be in the same statement, so it 393 doesn't matter which def op we choose, pick the first one. */ 394 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 395 break; 396 397 398 sinkbb = find_bb_for_arg (use, def); 399 if (!sinkbb) 400 return NULL; 401 402 /* This will happen when you have 403 a_3 = PHI <a_13, a_26> 404 405 a_26 = V_MAY_DEF <a_3> 406 407 If the use is a phi, and is in the same bb as the def, 408 we can't sink it. */ 409 410 if (bb_for_stmt (use) == frombb) 411 return NULL; 412 if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth 413 || sinkbb->loop_father != frombb->loop_father) 414 return NULL; 415 416 return first_stmt (sinkbb); 417} 418 419/* Perform code sinking on BB */ 420 421static void 422sink_code_in_bb (basic_block bb) 423{ 424 basic_block son; 425 block_stmt_iterator bsi; 426 edge_iterator ei; 427 edge e; 428 429 /* If this block doesn't dominate anything, there can't be any place to sink 430 the statements to. */ 431 if (first_dom_son (CDI_DOMINATORS, bb) == NULL) 432 goto earlyout; 433 434 /* We can't move things across abnormal edges, so don't try. */ 435 FOR_EACH_EDGE (e, ei, bb->succs) 436 if (e->flags & EDGE_ABNORMAL) 437 goto earlyout; 438 439 for (bsi = bsi_last (bb); !bsi_end_p (bsi);) 440 { 441 tree stmt = bsi_stmt (bsi); 442 block_stmt_iterator tobsi; 443 tree sinkstmt; 444 445 sinkstmt = statement_sink_location (stmt, bb); 446 if (!sinkstmt) 447 { 448 if (!bsi_end_p (bsi)) 449 bsi_prev (&bsi); 450 continue; 451 } 452 if (dump_file) 453 { 454 fprintf (dump_file, "Sinking "); 455 print_generic_expr (dump_file, stmt, TDF_VOPS); 456 fprintf (dump_file, " from bb %d to bb %d\n", 457 bb->index, bb_for_stmt (sinkstmt)->index); 458 } 459 tobsi = bsi_for_stmt (sinkstmt); 460 /* Find the first non-label. */ 461 while (!bsi_end_p (tobsi) 462 && TREE_CODE (bsi_stmt (tobsi)) == LABEL_EXPR) 463 bsi_next (&tobsi); 464 465 /* If this is the end of the basic block, we need to insert at the end 466 of the basic block. */ 467 if (bsi_end_p (tobsi)) 468 bsi_move_to_bb_end (&bsi, bb_for_stmt (sinkstmt)); 469 else 470 bsi_move_before (&bsi, &tobsi); 471 472 sink_stats.sunk++; 473 if (!bsi_end_p (bsi)) 474 bsi_prev (&bsi); 475 476 } 477 earlyout: 478 for (son = first_dom_son (CDI_POST_DOMINATORS, bb); 479 son; 480 son = next_dom_son (CDI_POST_DOMINATORS, son)) 481 { 482 sink_code_in_bb (son); 483 } 484} 485 486/* Perform code sinking. 487 This moves code down the flowgraph when we know it would be 488 profitable to do so, or it wouldn't increase the number of 489 executions of the statement. 490 491 IE given 492 493 a_1 = b + c; 494 if (<something>) 495 { 496 } 497 else 498 { 499 foo (&b, &c); 500 a_5 = b + c; 501 } 502 a_6 = PHI (a_5, a_1); 503 USE a_6. 504 505 we'll transform this into: 506 507 if (<something>) 508 { 509 a_1 = b + c; 510 } 511 else 512 { 513 foo (&b, &c); 514 a_5 = b + c; 515 } 516 a_6 = PHI (a_5, a_1); 517 USE a_6. 518 519 Note that this reduces the number of computations of a = b + c to 1 520 when we take the else edge, instead of 2. 521*/ 522static void 523execute_sink_code (void) 524{ 525 struct loops *loops = loop_optimizer_init (LOOPS_NORMAL); 526 527 connect_infinite_loops_to_exit (); 528 memset (&sink_stats, 0, sizeof (sink_stats)); 529 calculate_dominance_info (CDI_DOMINATORS | CDI_POST_DOMINATORS); 530 sink_code_in_bb (EXIT_BLOCK_PTR); 531 if (dump_file && (dump_flags & TDF_STATS)) 532 fprintf (dump_file, "Sunk statements:%d\n", sink_stats.sunk); 533 free_dominance_info (CDI_POST_DOMINATORS); 534 remove_fake_exit_edges (); 535 loop_optimizer_finalize (loops); 536} 537 538/* Gate and execute functions for PRE. */ 539 540static unsigned int 541do_sink (void) 542{ 543 execute_sink_code (); 544 return 0; 545} 546 547static bool 548gate_sink (void) 549{ 550 return flag_tree_sink != 0; 551} 552 553struct tree_opt_pass pass_sink_code = 554{ 555 "sink", /* name */ 556 gate_sink, /* gate */ 557 do_sink, /* execute */ 558 NULL, /* sub */ 559 NULL, /* next */ 560 0, /* static_pass_number */ 561 TV_TREE_SINK, /* tv_id */ 562 PROP_no_crit_edges | PROP_cfg 563 | PROP_ssa | PROP_alias, /* properties_required */ 564 0, /* properties_provided */ 565 0, /* properties_destroyed */ 566 0, /* todo_flags_start */ 567 TODO_update_ssa 568 | TODO_dump_func 569 | TODO_ggc_collect 570 | TODO_verify_ssa, /* todo_flags_finish */ 571 0 /* letter */ 572}; 573