1169689Skan/* Code sinking for trees 2169689Skan Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc. 3169689Skan Contributed by Daniel Berlin <dan@dberlin.org> 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify 8169689Skanit under the terms of the GNU General Public License as published by 9169689Skanthe Free Software Foundation; either version 2, or (at your option) 10169689Skanany later version. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, 13169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 14169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15169689SkanGNU General Public License for more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to 19169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 20169689SkanBoston, MA 02110-1301, USA. */ 21169689Skan 22169689Skan#include "config.h" 23169689Skan#include "system.h" 24169689Skan#include "coretypes.h" 25169689Skan#include "tm.h" 26169689Skan#include "ggc.h" 27169689Skan#include "tree.h" 28169689Skan#include "basic-block.h" 29169689Skan#include "diagnostic.h" 30169689Skan#include "tree-inline.h" 31169689Skan#include "tree-flow.h" 32169689Skan#include "tree-gimple.h" 33169689Skan#include "tree-dump.h" 34169689Skan#include "timevar.h" 35169689Skan#include "fibheap.h" 36169689Skan#include "hashtab.h" 37169689Skan#include "tree-iterator.h" 38169689Skan#include "real.h" 39169689Skan#include "alloc-pool.h" 40169689Skan#include "tree-pass.h" 41169689Skan#include "flags.h" 42169689Skan#include "bitmap.h" 43169689Skan#include "langhooks.h" 44169689Skan#include "cfgloop.h" 45169689Skan 46169689Skan/* TODO: 47169689Skan 1. Sinking store only using scalar promotion (IE without moving the RHS): 48169689Skan 49169689Skan *q = p; 50169689Skan p = p + 1; 51169689Skan if (something) 52169689Skan *q = <not p>; 53169689Skan else 54169689Skan y = *q; 55169689Skan 56169689Skan 57169689Skan should become 58169689Skan sinktemp = p; 59169689Skan p = p + 1; 60169689Skan if (something) 61169689Skan *q = <not p>; 62169689Skan else 63169689Skan { 64169689Skan *q = sinktemp; 65169689Skan y = *q 66169689Skan } 67169689Skan Store copy propagation will take care of the store elimination above. 68169689Skan 69169689Skan 70169689Skan 2. Sinking using Partial Dead Code Elimination. */ 71169689Skan 72169689Skan 73169689Skanstatic struct 74169689Skan{ 75169689Skan /* The number of statements sunk down the flowgraph by code sinking. */ 76169689Skan int sunk; 77169689Skan 78169689Skan} sink_stats; 79169689Skan 80169689Skan 81169689Skan/* Given a PHI, and one of its arguments (DEF), find the edge for 82169689Skan that argument and return it. If the argument occurs twice in the PHI node, 83169689Skan we return NULL. */ 84169689Skan 85169689Skanstatic basic_block 86169689Skanfind_bb_for_arg (tree phi, tree def) 87169689Skan{ 88169689Skan int i; 89169689Skan bool foundone = false; 90169689Skan basic_block result = NULL; 91169689Skan for (i = 0; i < PHI_NUM_ARGS (phi); i++) 92169689Skan if (PHI_ARG_DEF (phi, i) == def) 93169689Skan { 94169689Skan if (foundone) 95169689Skan return NULL; 96169689Skan foundone = true; 97169689Skan result = PHI_ARG_EDGE (phi, i)->src; 98169689Skan } 99169689Skan return result; 100169689Skan} 101169689Skan 102169689Skan/* When the first immediate use is in a statement, then return true if all 103169689Skan immediate uses in IMM are in the same statement. 104169689Skan We could also do the case where the first immediate use is in a phi node, 105169689Skan and all the other uses are in phis in the same basic block, but this 106169689Skan requires some expensive checking later (you have to make sure no def/vdef 107169689Skan in the statement occurs for multiple edges in the various phi nodes it's 108169689Skan used in, so that you only have one place you can sink it to. */ 109169689Skan 110169689Skanstatic bool 111169689Skanall_immediate_uses_same_place (tree stmt) 112169689Skan{ 113169689Skan tree firstuse = NULL_TREE; 114169689Skan ssa_op_iter op_iter; 115169689Skan imm_use_iterator imm_iter; 116169689Skan use_operand_p use_p; 117169689Skan tree var; 118169689Skan 119169689Skan FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS) 120169689Skan { 121169689Skan FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var) 122169689Skan { 123169689Skan if (firstuse == NULL_TREE) 124169689Skan firstuse = USE_STMT (use_p); 125169689Skan else 126169689Skan if (firstuse != USE_STMT (use_p)) 127169689Skan return false; 128169689Skan } 129169689Skan } 130169689Skan 131169689Skan return true; 132169689Skan} 133169689Skan 134169689Skan/* Some global stores don't necessarily have V_MAY_DEF's of global variables, 135169689Skan but we still must avoid moving them around. */ 136169689Skan 137169689Skanbool 138169689Skanis_hidden_global_store (tree stmt) 139169689Skan{ 140169689Skan /* Check virtual definitions. If we get here, the only virtual 141169689Skan definitions we should see are those generated by assignment 142169689Skan statements. */ 143169689Skan if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)) 144169689Skan { 145169689Skan tree lhs; 146169689Skan 147169689Skan gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR); 148169689Skan 149169689Skan /* Note that we must not check the individual virtual operands 150169689Skan here. In particular, if this is an aliased store, we could 151169689Skan end up with something like the following (SSA notation 152169689Skan redacted for brevity): 153169689Skan 154169689Skan foo (int *p, int i) 155169689Skan { 156169689Skan int x; 157169689Skan p_1 = (i_2 > 3) ? &x : p; 158169689Skan 159169689Skan # x_4 = V_MAY_DEF <x_3> 160169689Skan *p_1 = 5; 161169689Skan 162169689Skan return 2; 163169689Skan } 164169689Skan 165169689Skan Notice that the store to '*p_1' should be preserved, if we 166169689Skan were to check the virtual definitions in that store, we would 167169689Skan not mark it needed. This is because 'x' is not a global 168169689Skan variable. 169169689Skan 170169689Skan Therefore, we check the base address of the LHS. If the 171169689Skan address is a pointer, we check if its name tag or symbol tag is 172169689Skan a global variable. Otherwise, we check if the base variable 173169689Skan is a global. */ 174169689Skan lhs = TREE_OPERAND (stmt, 0); 175169689Skan if (REFERENCE_CLASS_P (lhs)) 176169689Skan lhs = get_base_address (lhs); 177169689Skan 178169689Skan if (lhs == NULL_TREE) 179169689Skan { 180169689Skan /* If LHS is NULL, it means that we couldn't get the base 181169689Skan address of the reference. In which case, we should not 182169689Skan move this store. */ 183169689Skan return true; 184169689Skan } 185169689Skan else if (DECL_P (lhs)) 186169689Skan { 187169689Skan /* If the store is to a global symbol, we need to keep it. */ 188169689Skan if (is_global_var (lhs)) 189169689Skan return true; 190169689Skan 191169689Skan } 192169689Skan else if (INDIRECT_REF_P (lhs)) 193169689Skan { 194169689Skan tree ptr = TREE_OPERAND (lhs, 0); 195169689Skan struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); 196169689Skan tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE; 197169689Skan tree smt = var_ann (SSA_NAME_VAR (ptr))->symbol_mem_tag; 198169689Skan 199169689Skan /* If either the name tag or the symbol tag for PTR is a 200169689Skan global variable, then the store is necessary. */ 201169689Skan if ((nmt && is_global_var (nmt)) 202169689Skan || (smt && is_global_var (smt))) 203169689Skan { 204169689Skan return true; 205169689Skan } 206169689Skan } 207169689Skan else 208169689Skan gcc_unreachable (); 209169689Skan } 210169689Skan return false; 211169689Skan} 212169689Skan 213169689Skan/* Find the nearest common dominator of all of the immediate uses in IMM. */ 214169689Skan 215169689Skanstatic basic_block 216169689Skannearest_common_dominator_of_uses (tree stmt) 217169689Skan{ 218169689Skan bitmap blocks = BITMAP_ALLOC (NULL); 219169689Skan basic_block commondom; 220169689Skan unsigned int j; 221169689Skan bitmap_iterator bi; 222169689Skan ssa_op_iter op_iter; 223169689Skan imm_use_iterator imm_iter; 224169689Skan use_operand_p use_p; 225169689Skan tree var; 226169689Skan 227169689Skan bitmap_clear (blocks); 228169689Skan FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS) 229169689Skan { 230169689Skan FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var) 231169689Skan { 232169689Skan tree usestmt = USE_STMT (use_p); 233169689Skan basic_block useblock; 234169689Skan 235169689Skan if (TREE_CODE (usestmt) == PHI_NODE) 236169689Skan { 237169689Skan int idx = PHI_ARG_INDEX_FROM_USE (use_p); 238169689Skan 239169689Skan useblock = PHI_ARG_EDGE (usestmt, idx)->src; 240169689Skan } 241169689Skan else 242169689Skan { 243169689Skan useblock = bb_for_stmt (usestmt); 244169689Skan } 245169689Skan 246169689Skan /* Short circuit. Nothing dominates the entry block. */ 247169689Skan if (useblock == ENTRY_BLOCK_PTR) 248169689Skan { 249169689Skan BITMAP_FREE (blocks); 250169689Skan return NULL; 251169689Skan } 252169689Skan bitmap_set_bit (blocks, useblock->index); 253169689Skan } 254169689Skan } 255169689Skan commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks)); 256169689Skan EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi) 257169689Skan commondom = nearest_common_dominator (CDI_DOMINATORS, commondom, 258169689Skan BASIC_BLOCK (j)); 259169689Skan BITMAP_FREE (blocks); 260169689Skan return commondom; 261169689Skan} 262169689Skan 263169689Skan/* Given a statement (STMT) and the basic block it is currently in (FROMBB), 264169689Skan determine the location to sink the statement to, if any. 265169689Skan Return the basic block to sink it to, or NULL if we should not sink 266169689Skan it. */ 267169689Skan 268169689Skanstatic tree 269169689Skanstatement_sink_location (tree stmt, basic_block frombb) 270169689Skan{ 271169689Skan tree use, def; 272169689Skan use_operand_p one_use = NULL_USE_OPERAND_P; 273169689Skan basic_block sinkbb; 274169689Skan use_operand_p use_p; 275169689Skan def_operand_p def_p; 276169689Skan ssa_op_iter iter; 277169689Skan stmt_ann_t ann; 278169689Skan tree rhs; 279169689Skan imm_use_iterator imm_iter; 280169689Skan 281169689Skan FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 282169689Skan { 283169689Skan FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def) 284169689Skan { 285169689Skan break; 286169689Skan } 287169689Skan if (one_use != NULL_USE_OPERAND_P) 288169689Skan break; 289169689Skan } 290169689Skan 291169689Skan /* Return if there are no immediate uses of this stmt. */ 292169689Skan if (one_use == NULL_USE_OPERAND_P) 293169689Skan return NULL; 294169689Skan 295169689Skan if (TREE_CODE (stmt) != MODIFY_EXPR) 296169689Skan return NULL; 297169689Skan rhs = TREE_OPERAND (stmt, 1); 298169689Skan 299169689Skan /* There are a few classes of things we can't or don't move, some because we 300169689Skan don't have code to handle it, some because it's not profitable and some 301169689Skan because it's not legal. 302169689Skan 303169689Skan We can't sink things that may be global stores, at least not without 304169689Skan calculating a lot more information, because we may cause it to no longer 305169689Skan be seen by an external routine that needs it depending on where it gets 306169689Skan moved to. 307169689Skan 308169689Skan We don't want to sink loads from memory. 309169689Skan 310169689Skan We can't sink statements that end basic blocks without splitting the 311169689Skan incoming edge for the sink location to place it there. 312169689Skan 313169689Skan We can't sink statements that have volatile operands. 314169689Skan 315169689Skan We don't want to sink dead code, so anything with 0 immediate uses is not 316169689Skan sunk. 317169689Skan 318169689Skan */ 319169689Skan ann = stmt_ann (stmt); 320169689Skan if (stmt_ends_bb_p (stmt) 321169689Skan || TREE_SIDE_EFFECTS (rhs) 322169689Skan || TREE_CODE (rhs) == EXC_PTR_EXPR 323169689Skan || TREE_CODE (rhs) == FILTER_EXPR 324169689Skan || is_hidden_global_store (stmt) 325169689Skan || ann->has_volatile_ops 326169689Skan || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE)) 327169689Skan return NULL; 328169689Skan 329169689Skan FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS) 330169689Skan { 331169689Skan tree def = DEF_FROM_PTR (def_p); 332169689Skan if (is_global_var (SSA_NAME_VAR (def)) 333169689Skan || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)) 334169689Skan return NULL; 335169689Skan } 336169689Skan 337169689Skan FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) 338169689Skan { 339169689Skan tree use = USE_FROM_PTR (use_p); 340169689Skan if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use)) 341169689Skan return NULL; 342169689Skan } 343169689Skan 344169689Skan /* If all the immediate uses are not in the same place, find the nearest 345169689Skan common dominator of all the immediate uses. For PHI nodes, we have to 346169689Skan find the nearest common dominator of all of the predecessor blocks, since 347169689Skan that is where insertion would have to take place. */ 348169689Skan if (!all_immediate_uses_same_place (stmt)) 349169689Skan { 350169689Skan basic_block commondom = nearest_common_dominator_of_uses (stmt); 351169689Skan 352169689Skan if (commondom == frombb) 353169689Skan return NULL; 354169689Skan 355169689Skan /* Our common dominator has to be dominated by frombb in order to be a 356169689Skan trivially safe place to put this statement, since it has multiple 357169689Skan uses. */ 358169689Skan if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb)) 359169689Skan return NULL; 360169689Skan 361169689Skan /* It doesn't make sense to move to a dominator that post-dominates 362169689Skan frombb, because it means we've just moved it into a path that always 363169689Skan executes if frombb executes, instead of reducing the number of 364169689Skan executions . */ 365169689Skan if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom)) 366169689Skan { 367169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 368169689Skan fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n"); 369169689Skan return NULL; 370169689Skan } 371169689Skan 372169689Skan if (commondom == frombb || commondom->loop_depth > frombb->loop_depth) 373169689Skan return NULL; 374169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 375169689Skan { 376169689Skan fprintf (dump_file, "Common dominator of all uses is %d\n", 377169689Skan commondom->index); 378169689Skan } 379169689Skan return first_stmt (commondom); 380169689Skan } 381169689Skan 382169689Skan use = USE_STMT (one_use); 383169689Skan if (TREE_CODE (use) != PHI_NODE) 384169689Skan { 385169689Skan sinkbb = bb_for_stmt (use); 386169689Skan if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth 387169689Skan || sinkbb->loop_father != frombb->loop_father) 388169689Skan return NULL; 389169689Skan return use; 390169689Skan } 391169689Skan 392169689Skan /* Note that at this point, all uses must be in the same statement, so it 393169689Skan doesn't matter which def op we choose, pick the first one. */ 394169689Skan FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 395169689Skan break; 396169689Skan 397169689Skan 398169689Skan sinkbb = find_bb_for_arg (use, def); 399169689Skan if (!sinkbb) 400169689Skan return NULL; 401169689Skan 402169689Skan /* This will happen when you have 403169689Skan a_3 = PHI <a_13, a_26> 404169689Skan 405169689Skan a_26 = V_MAY_DEF <a_3> 406169689Skan 407169689Skan If the use is a phi, and is in the same bb as the def, 408169689Skan we can't sink it. */ 409169689Skan 410169689Skan if (bb_for_stmt (use) == frombb) 411169689Skan return NULL; 412169689Skan if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth 413169689Skan || sinkbb->loop_father != frombb->loop_father) 414169689Skan return NULL; 415169689Skan 416169689Skan return first_stmt (sinkbb); 417169689Skan} 418169689Skan 419169689Skan/* Perform code sinking on BB */ 420169689Skan 421169689Skanstatic void 422169689Skansink_code_in_bb (basic_block bb) 423169689Skan{ 424169689Skan basic_block son; 425169689Skan block_stmt_iterator bsi; 426169689Skan edge_iterator ei; 427169689Skan edge e; 428169689Skan 429169689Skan /* If this block doesn't dominate anything, there can't be any place to sink 430169689Skan the statements to. */ 431169689Skan if (first_dom_son (CDI_DOMINATORS, bb) == NULL) 432169689Skan goto earlyout; 433169689Skan 434169689Skan /* We can't move things across abnormal edges, so don't try. */ 435169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 436169689Skan if (e->flags & EDGE_ABNORMAL) 437169689Skan goto earlyout; 438169689Skan 439169689Skan for (bsi = bsi_last (bb); !bsi_end_p (bsi);) 440169689Skan { 441169689Skan tree stmt = bsi_stmt (bsi); 442169689Skan block_stmt_iterator tobsi; 443169689Skan tree sinkstmt; 444169689Skan 445169689Skan sinkstmt = statement_sink_location (stmt, bb); 446169689Skan if (!sinkstmt) 447169689Skan { 448169689Skan if (!bsi_end_p (bsi)) 449169689Skan bsi_prev (&bsi); 450169689Skan continue; 451169689Skan } 452169689Skan if (dump_file) 453169689Skan { 454169689Skan fprintf (dump_file, "Sinking "); 455169689Skan print_generic_expr (dump_file, stmt, TDF_VOPS); 456169689Skan fprintf (dump_file, " from bb %d to bb %d\n", 457169689Skan bb->index, bb_for_stmt (sinkstmt)->index); 458169689Skan } 459169689Skan tobsi = bsi_for_stmt (sinkstmt); 460169689Skan /* Find the first non-label. */ 461169689Skan while (!bsi_end_p (tobsi) 462169689Skan && TREE_CODE (bsi_stmt (tobsi)) == LABEL_EXPR) 463169689Skan bsi_next (&tobsi); 464169689Skan 465169689Skan /* If this is the end of the basic block, we need to insert at the end 466169689Skan of the basic block. */ 467169689Skan if (bsi_end_p (tobsi)) 468169689Skan bsi_move_to_bb_end (&bsi, bb_for_stmt (sinkstmt)); 469169689Skan else 470169689Skan bsi_move_before (&bsi, &tobsi); 471169689Skan 472169689Skan sink_stats.sunk++; 473169689Skan if (!bsi_end_p (bsi)) 474169689Skan bsi_prev (&bsi); 475169689Skan 476169689Skan } 477169689Skan earlyout: 478169689Skan for (son = first_dom_son (CDI_POST_DOMINATORS, bb); 479169689Skan son; 480169689Skan son = next_dom_son (CDI_POST_DOMINATORS, son)) 481169689Skan { 482169689Skan sink_code_in_bb (son); 483169689Skan } 484169689Skan} 485169689Skan 486169689Skan/* Perform code sinking. 487169689Skan This moves code down the flowgraph when we know it would be 488169689Skan profitable to do so, or it wouldn't increase the number of 489169689Skan executions of the statement. 490169689Skan 491169689Skan IE given 492169689Skan 493169689Skan a_1 = b + c; 494169689Skan if (<something>) 495169689Skan { 496169689Skan } 497169689Skan else 498169689Skan { 499169689Skan foo (&b, &c); 500169689Skan a_5 = b + c; 501169689Skan } 502169689Skan a_6 = PHI (a_5, a_1); 503169689Skan USE a_6. 504169689Skan 505169689Skan we'll transform this into: 506169689Skan 507169689Skan if (<something>) 508169689Skan { 509169689Skan a_1 = b + c; 510169689Skan } 511169689Skan else 512169689Skan { 513169689Skan foo (&b, &c); 514169689Skan a_5 = b + c; 515169689Skan } 516169689Skan a_6 = PHI (a_5, a_1); 517169689Skan USE a_6. 518169689Skan 519169689Skan Note that this reduces the number of computations of a = b + c to 1 520169689Skan when we take the else edge, instead of 2. 521169689Skan*/ 522169689Skanstatic void 523169689Skanexecute_sink_code (void) 524169689Skan{ 525169689Skan struct loops *loops = loop_optimizer_init (LOOPS_NORMAL); 526169689Skan 527169689Skan connect_infinite_loops_to_exit (); 528169689Skan memset (&sink_stats, 0, sizeof (sink_stats)); 529169689Skan calculate_dominance_info (CDI_DOMINATORS | CDI_POST_DOMINATORS); 530169689Skan sink_code_in_bb (EXIT_BLOCK_PTR); 531169689Skan if (dump_file && (dump_flags & TDF_STATS)) 532169689Skan fprintf (dump_file, "Sunk statements:%d\n", sink_stats.sunk); 533169689Skan free_dominance_info (CDI_POST_DOMINATORS); 534169689Skan remove_fake_exit_edges (); 535169689Skan loop_optimizer_finalize (loops); 536169689Skan} 537169689Skan 538169689Skan/* Gate and execute functions for PRE. */ 539169689Skan 540169689Skanstatic unsigned int 541169689Skando_sink (void) 542169689Skan{ 543169689Skan execute_sink_code (); 544169689Skan return 0; 545169689Skan} 546169689Skan 547169689Skanstatic bool 548169689Skangate_sink (void) 549169689Skan{ 550169689Skan return flag_tree_sink != 0; 551169689Skan} 552169689Skan 553169689Skanstruct tree_opt_pass pass_sink_code = 554169689Skan{ 555169689Skan "sink", /* name */ 556169689Skan gate_sink, /* gate */ 557169689Skan do_sink, /* execute */ 558169689Skan NULL, /* sub */ 559169689Skan NULL, /* next */ 560169689Skan 0, /* static_pass_number */ 561169689Skan TV_TREE_SINK, /* tv_id */ 562169689Skan PROP_no_crit_edges | PROP_cfg 563169689Skan | PROP_ssa | PROP_alias, /* properties_required */ 564169689Skan 0, /* properties_provided */ 565169689Skan 0, /* properties_destroyed */ 566169689Skan 0, /* todo_flags_start */ 567169689Skan TODO_update_ssa 568169689Skan | TODO_dump_func 569169689Skan | TODO_ggc_collect 570169689Skan | TODO_verify_ssa, /* todo_flags_finish */ 571169689Skan 0 /* letter */ 572169689Skan}; 573