1/* Top-level control of tree optimizations. 2 Copyright 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3 Contributed by Diego Novillo <dnovillo@redhat.com> 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 2, 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 COPYING. If not, write to 19the Free Software Foundation, 51 Franklin Street, Fifth Floor, 20Boston, MA 02110-1301, USA. */ 21 22#include "config.h" 23#include "system.h" 24#include "coretypes.h" 25#include "tm.h" 26#include "tree.h" 27#include "rtl.h" 28#include "tm_p.h" 29#include "hard-reg-set.h" 30#include "basic-block.h" 31#include "output.h" 32#include "expr.h" 33#include "diagnostic.h" 34#include "basic-block.h" 35#include "flags.h" 36#include "tree-flow.h" 37#include "tree-dump.h" 38#include "timevar.h" 39#include "function.h" 40#include "langhooks.h" 41#include "toplev.h" 42#include "flags.h" 43#include "cgraph.h" 44#include "tree-inline.h" 45#include "tree-mudflap.h" 46#include "tree-pass.h" 47#include "ggc.h" 48#include "cgraph.h" 49#include "graph.h" 50#include "cfgloop.h" 51#include "except.h" 52 53 54/* Gate: execute, or not, all of the non-trivial optimizations. */ 55 56static bool 57gate_all_optimizations (void) 58{ 59 return (optimize >= 1 60 /* Don't bother doing anything if the program has errors. */ 61 && !(errorcount || sorrycount)); 62} 63 64struct tree_opt_pass pass_all_optimizations = 65{ 66 NULL, /* name */ 67 gate_all_optimizations, /* gate */ 68 NULL, /* execute */ 69 NULL, /* sub */ 70 NULL, /* next */ 71 0, /* static_pass_number */ 72 0, /* tv_id */ 73 0, /* properties_required */ 74 0, /* properties_provided */ 75 0, /* properties_destroyed */ 76 0, /* todo_flags_start */ 77 0, /* todo_flags_finish */ 78 0 /* letter */ 79}; 80 81struct tree_opt_pass pass_early_local_passes = 82{ 83 NULL, /* name */ 84 gate_all_optimizations, /* gate */ 85 NULL, /* execute */ 86 NULL, /* sub */ 87 NULL, /* next */ 88 0, /* static_pass_number */ 89 0, /* tv_id */ 90 0, /* properties_required */ 91 0, /* properties_provided */ 92 0, /* properties_destroyed */ 93 0, /* todo_flags_start */ 94 0, /* todo_flags_finish */ 95 0 /* letter */ 96}; 97 98/* Pass: cleanup the CFG just before expanding trees to RTL. 99 This is just a round of label cleanups and case node grouping 100 because after the tree optimizers have run such cleanups may 101 be necessary. */ 102 103static void 104execute_cleanup_cfg_pre_ipa (void) 105{ 106 cleanup_tree_cfg (); 107} 108 109struct tree_opt_pass pass_cleanup_cfg = 110{ 111 "cleanup_cfg", /* name */ 112 NULL, /* gate */ 113 execute_cleanup_cfg_pre_ipa, /* execute */ 114 NULL, /* sub */ 115 NULL, /* next */ 116 0, /* static_pass_number */ 117 0, /* tv_id */ 118 PROP_cfg, /* properties_required */ 119 0, /* properties_provided */ 120 0, /* properties_destroyed */ 121 0, /* todo_flags_start */ 122 TODO_dump_func, /* todo_flags_finish */ 123 0 /* letter */ 124}; 125 126 127/* Pass: cleanup the CFG just before expanding trees to RTL. 128 This is just a round of label cleanups and case node grouping 129 because after the tree optimizers have run such cleanups may 130 be necessary. */ 131 132static void 133execute_cleanup_cfg_post_optimizing (void) 134{ 135 fold_cond_expr_cond (); 136 cleanup_tree_cfg (); 137 cleanup_dead_labels (); 138 group_case_labels (); 139} 140 141struct tree_opt_pass pass_cleanup_cfg_post_optimizing = 142{ 143 "final_cleanup", /* name */ 144 NULL, /* gate */ 145 execute_cleanup_cfg_post_optimizing, /* execute */ 146 NULL, /* sub */ 147 NULL, /* next */ 148 0, /* static_pass_number */ 149 0, /* tv_id */ 150 PROP_cfg, /* properties_required */ 151 0, /* properties_provided */ 152 0, /* properties_destroyed */ 153 0, /* todo_flags_start */ 154 TODO_dump_func, /* todo_flags_finish */ 155 0 /* letter */ 156}; 157 158/* Pass: do the actions required to finish with tree-ssa optimization 159 passes. */ 160 161static void 162execute_free_datastructures (void) 163{ 164 /* ??? This isn't the right place for this. Worse, it got computed 165 more or less at random in various passes. */ 166 free_dominance_info (CDI_DOMINATORS); 167 free_dominance_info (CDI_POST_DOMINATORS); 168 169 /* Remove the ssa structures. Do it here since this includes statement 170 annotations that need to be intact during disband_implicit_edges. */ 171 delete_tree_ssa (); 172} 173 174struct tree_opt_pass pass_free_datastructures = 175{ 176 NULL, /* name */ 177 NULL, /* gate */ 178 execute_free_datastructures, /* execute */ 179 NULL, /* sub */ 180 NULL, /* next */ 181 0, /* static_pass_number */ 182 0, /* tv_id */ 183 PROP_cfg, /* properties_required */ 184 0, /* properties_provided */ 185 0, /* properties_destroyed */ 186 0, /* todo_flags_start */ 187 0, /* todo_flags_finish */ 188 0 /* letter */ 189}; 190/* Pass: free cfg annotations. */ 191 192static void 193execute_free_cfg_annotations (void) 194{ 195 basic_block bb; 196 block_stmt_iterator bsi; 197 198 /* Emit gotos for implicit jumps. */ 199 disband_implicit_edges (); 200 201 /* Remove annotations from every tree in the function. */ 202 FOR_EACH_BB (bb) 203 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 204 { 205 tree stmt = bsi_stmt (bsi); 206 ggc_free (stmt->common.ann); 207 stmt->common.ann = NULL; 208 } 209 210 /* And get rid of annotations we no longer need. */ 211 delete_tree_cfg_annotations (); 212} 213 214struct tree_opt_pass pass_free_cfg_annotations = 215{ 216 NULL, /* name */ 217 NULL, /* gate */ 218 execute_free_cfg_annotations, /* execute */ 219 NULL, /* sub */ 220 NULL, /* next */ 221 0, /* static_pass_number */ 222 0, /* tv_id */ 223 PROP_cfg, /* properties_required */ 224 0, /* properties_provided */ 225 0, /* properties_destroyed */ 226 0, /* todo_flags_start */ 227 0, /* todo_flags_finish */ 228 0 /* letter */ 229}; 230/* Pass: fixup_cfg - IPA passes or compilation of earlier functions might've 231 changed some properties - such as marked functions nothrow. Remove now 232 redundant edges and basic blocks. */ 233 234static void 235execute_fixup_cfg (void) 236{ 237 basic_block bb; 238 block_stmt_iterator bsi; 239 240 if (cfun->eh) 241 FOR_EACH_BB (bb) 242 { 243 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 244 { 245 tree stmt = bsi_stmt (bsi); 246 tree call = get_call_expr_in (stmt); 247 248 if (call && call_expr_flags (call) & (ECF_CONST | ECF_PURE)) 249 TREE_SIDE_EFFECTS (call) = 0; 250 if (!tree_could_throw_p (stmt) && lookup_stmt_eh_region (stmt)) 251 remove_stmt_from_eh_region (stmt); 252 } 253 tree_purge_dead_eh_edges (bb); 254 } 255 256 cleanup_tree_cfg (); 257} 258 259struct tree_opt_pass pass_fixup_cfg = 260{ 261 "fixupcfg", /* name */ 262 NULL, /* gate */ 263 execute_fixup_cfg, /* execute */ 264 NULL, /* sub */ 265 NULL, /* next */ 266 0, /* static_pass_number */ 267 0, /* tv_id */ 268 PROP_cfg, /* properties_required */ 269 0, /* properties_provided */ 270 0, /* properties_destroyed */ 271 0, /* todo_flags_start */ 272 TODO_dump_func, /* todo_flags_finish */ 273 0 /* letter */ 274}; 275 276/* Do the actions required to initialize internal data structures used 277 in tree-ssa optimization passes. */ 278 279static void 280execute_init_datastructures (void) 281{ 282 /* Allocate hash tables, arrays and other structures. */ 283 init_tree_ssa (); 284} 285 286struct tree_opt_pass pass_init_datastructures = 287{ 288 NULL, /* name */ 289 NULL, /* gate */ 290 execute_init_datastructures, /* execute */ 291 NULL, /* sub */ 292 NULL, /* next */ 293 0, /* static_pass_number */ 294 0, /* tv_id */ 295 PROP_cfg, /* properties_required */ 296 0, /* properties_provided */ 297 0, /* properties_destroyed */ 298 0, /* todo_flags_start */ 299 0, /* todo_flags_finish */ 300 0 /* letter */ 301}; 302 303void 304tree_lowering_passes (tree fn) 305{ 306 tree saved_current_function_decl = current_function_decl; 307 308 current_function_decl = fn; 309 push_cfun (DECL_STRUCT_FUNCTION (fn)); 310 tree_register_cfg_hooks (); 311 bitmap_obstack_initialize (NULL); 312 execute_pass_list (all_lowering_passes); 313 free_dominance_info (CDI_POST_DOMINATORS); 314 compact_blocks (); 315 current_function_decl = saved_current_function_decl; 316 bitmap_obstack_release (NULL); 317 pop_cfun (); 318} 319 320/* Update recursively all inlined_to pointers of functions 321 inlined into NODE to INLINED_TO. */ 322static void 323update_inlined_to_pointers (struct cgraph_node *node, 324 struct cgraph_node *inlined_to) 325{ 326 struct cgraph_edge *e; 327 for (e = node->callees; e; e = e->next_callee) 328 { 329 if (e->callee->global.inlined_to) 330 { 331 e->callee->global.inlined_to = inlined_to; 332 update_inlined_to_pointers (e->callee, inlined_to); 333 } 334 } 335} 336 337 338/* For functions-as-trees languages, this performs all optimization and 339 compilation for FNDECL. */ 340 341void 342tree_rest_of_compilation (tree fndecl) 343{ 344 location_t saved_loc; 345 struct cgraph_node *saved_node = NULL, *node; 346 347 timevar_push (TV_EXPAND); 348 349 gcc_assert (!flag_unit_at_a_time || cgraph_global_info_ready); 350 351 /* Initialize the RTL code for the function. */ 352 current_function_decl = fndecl; 353 saved_loc = input_location; 354 input_location = DECL_SOURCE_LOCATION (fndecl); 355 init_function_start (fndecl); 356 357 /* Even though we're inside a function body, we still don't want to 358 call expand_expr to calculate the size of a variable-sized array. 359 We haven't necessarily assigned RTL to all variables yet, so it's 360 not safe to try to expand expressions involving them. */ 361 cfun->x_dont_save_pending_sizes_p = 1; 362 cfun->after_inlining = true; 363 364 node = cgraph_node (fndecl); 365 366 /* We might need the body of this function so that we can expand 367 it inline somewhere else. This means not lowering some constructs 368 such as exception handling. */ 369 if (cgraph_preserve_function_body_p (fndecl)) 370 { 371 if (!flag_unit_at_a_time) 372 { 373 struct cgraph_edge *e; 374 375 saved_node = cgraph_clone_node (node, node->count, 1, false); 376 for (e = saved_node->callees; e; e = e->next_callee) 377 if (!e->inline_failed) 378 cgraph_clone_inlined_nodes (e, true, false); 379 } 380 cfun->saved_static_chain_decl = cfun->static_chain_decl; 381 save_body (fndecl, &cfun->saved_args, &cfun->saved_static_chain_decl); 382 } 383 384 if (flag_inline_trees) 385 { 386 struct cgraph_edge *e; 387 for (e = node->callees; e; e = e->next_callee) 388 if (!e->inline_failed || warn_inline) 389 break; 390 if (e) 391 { 392 timevar_push (TV_INTEGRATION); 393 optimize_inline_calls (fndecl); 394 timevar_pop (TV_INTEGRATION); 395 } 396 } 397 /* We are not going to maintain the cgraph edges up to date. 398 Kill it so it won't confuse us. */ 399 while (node->callees) 400 { 401 /* In non-unit-at-a-time we must mark all referenced functions as needed. 402 */ 403 if (node->callees->callee->analyzed && !flag_unit_at_a_time) 404 cgraph_mark_needed_node (node->callees->callee); 405 cgraph_remove_edge (node->callees); 406 } 407 408 /* We are not going to maintain the cgraph edges up to date. 409 Kill it so it won't confuse us. */ 410 cgraph_node_remove_callees (node); 411 412 413 /* Initialize the default bitmap obstack. */ 414 bitmap_obstack_initialize (NULL); 415 bitmap_obstack_initialize (®_obstack); /* FIXME, only at RTL generation*/ 416 417 tree_register_cfg_hooks (); 418 /* Perform all tree transforms and optimizations. */ 419 execute_pass_list (all_passes); 420 421 bitmap_obstack_release (®_obstack); 422 423 /* Release the default bitmap obstack. */ 424 bitmap_obstack_release (NULL); 425 426 /* Restore original body if still needed. */ 427 if (cfun->saved_cfg) 428 { 429 DECL_ARGUMENTS (fndecl) = cfun->saved_args; 430 cfun->cfg = cfun->saved_cfg; 431 cfun->eh = cfun->saved_eh; 432 DECL_INITIAL (fndecl) = cfun->saved_blocks; 433 cfun->unexpanded_var_list = cfun->saved_unexpanded_var_list; 434 cfun->saved_cfg = NULL; 435 cfun->saved_eh = NULL; 436 cfun->saved_args = NULL_TREE; 437 cfun->saved_blocks = NULL_TREE; 438 cfun->saved_unexpanded_var_list = NULL_TREE; 439 cfun->static_chain_decl = cfun->saved_static_chain_decl; 440 cfun->saved_static_chain_decl = NULL; 441 /* When not in unit-at-a-time mode, we must preserve out of line copy 442 representing node before inlining. Restore original outgoing edges 443 using clone we created earlier. */ 444 if (!flag_unit_at_a_time) 445 { 446 struct cgraph_edge *e; 447 448 node = cgraph_node (current_function_decl); 449 cgraph_node_remove_callees (node); 450 node->callees = saved_node->callees; 451 saved_node->callees = NULL; 452 update_inlined_to_pointers (node, node); 453 for (e = node->callees; e; e = e->next_callee) 454 e->caller = node; 455 cgraph_remove_node (saved_node); 456 } 457 } 458 else 459 DECL_SAVED_TREE (fndecl) = NULL; 460 cfun = 0; 461 462 /* If requested, warn about function definitions where the function will 463 return a value (usually of some struct or union type) which itself will 464 take up a lot of stack space. */ 465 if (warn_larger_than && !DECL_EXTERNAL (fndecl) && TREE_TYPE (fndecl)) 466 { 467 tree ret_type = TREE_TYPE (TREE_TYPE (fndecl)); 468 469 if (ret_type && TYPE_SIZE_UNIT (ret_type) 470 && TREE_CODE (TYPE_SIZE_UNIT (ret_type)) == INTEGER_CST 471 && 0 < compare_tree_int (TYPE_SIZE_UNIT (ret_type), 472 larger_than_size)) 473 { 474 unsigned int size_as_int 475 = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ret_type)); 476 477 if (compare_tree_int (TYPE_SIZE_UNIT (ret_type), size_as_int) == 0) 478 warning (0, "size of return value of %q+D is %u bytes", 479 fndecl, size_as_int); 480 else 481 warning (0, "size of return value of %q+D is larger than %wd bytes", 482 fndecl, larger_than_size); 483 } 484 } 485 486 if (!flag_inline_trees) 487 { 488 DECL_SAVED_TREE (fndecl) = NULL; 489 if (DECL_STRUCT_FUNCTION (fndecl) == 0 490 && !cgraph_node (fndecl)->origin) 491 { 492 /* Stop pointing to the local nodes about to be freed. 493 But DECL_INITIAL must remain nonzero so we know this 494 was an actual function definition. 495 For a nested function, this is done in c_pop_function_context. 496 If rest_of_compilation set this to 0, leave it 0. */ 497 if (DECL_INITIAL (fndecl) != 0) 498 DECL_INITIAL (fndecl) = error_mark_node; 499 } 500 } 501 502 input_location = saved_loc; 503 504 ggc_collect (); 505 timevar_pop (TV_EXPAND); 506} 507