1169689Skan/* Top-level control of tree optimizations. 2169689Skan Copyright 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3169689Skan Contributed by Diego Novillo <dnovillo@redhat.com> 4132718Skan 5132718SkanThis file is part of GCC. 6132718Skan 7132718SkanGCC is free software; you can redistribute it and/or modify 8132718Skanit under the terms of the GNU General Public License as published by 9132718Skanthe Free Software Foundation; either version 2, or (at your option) 10132718Skanany later version. 11132718Skan 12132718SkanGCC is distributed in the hope that it will be useful, 13132718Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 14132718SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15132718SkanGNU General Public License for more details. 16132718Skan 17132718SkanYou should have received a copy of the GNU General Public License 18132718Skanalong with GCC; see the file COPYING. If not, write to 19169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 20169689SkanBoston, MA 02110-1301, USA. */ 21132718Skan 22132718Skan#include "config.h" 23132718Skan#include "system.h" 24132718Skan#include "coretypes.h" 25169689Skan#include "tm.h" 26132718Skan#include "tree.h" 27169689Skan#include "rtl.h" 28169689Skan#include "tm_p.h" 29169689Skan#include "hard-reg-set.h" 30169689Skan#include "basic-block.h" 31169689Skan#include "output.h" 32169689Skan#include "expr.h" 33169689Skan#include "diagnostic.h" 34169689Skan#include "basic-block.h" 35132718Skan#include "flags.h" 36169689Skan#include "tree-flow.h" 37169689Skan#include "tree-dump.h" 38169689Skan#include "timevar.h" 39169689Skan#include "function.h" 40132718Skan#include "langhooks.h" 41169689Skan#include "toplev.h" 42169689Skan#include "flags.h" 43132718Skan#include "cgraph.h" 44169689Skan#include "tree-inline.h" 45169689Skan#include "tree-mudflap.h" 46169689Skan#include "tree-pass.h" 47132718Skan#include "ggc.h" 48169689Skan#include "cgraph.h" 49169689Skan#include "graph.h" 50169689Skan#include "cfgloop.h" 51169689Skan#include "except.h" 52132718Skan 53132718Skan 54169689Skan/* Gate: execute, or not, all of the non-trivial optimizations. */ 55132718Skan 56169689Skanstatic bool 57169689Skangate_all_optimizations (void) 58132718Skan{ 59169689Skan return (optimize >= 1 60169689Skan /* Don't bother doing anything if the program has errors. */ 61169689Skan && !(errorcount || sorrycount)); 62169689Skan} 63132718Skan 64169689Skanstruct tree_opt_pass pass_all_optimizations = 65169689Skan{ 66169689Skan NULL, /* name */ 67169689Skan gate_all_optimizations, /* gate */ 68169689Skan NULL, /* execute */ 69169689Skan NULL, /* sub */ 70169689Skan NULL, /* next */ 71169689Skan 0, /* static_pass_number */ 72169689Skan 0, /* tv_id */ 73169689Skan 0, /* properties_required */ 74169689Skan 0, /* properties_provided */ 75169689Skan 0, /* properties_destroyed */ 76169689Skan 0, /* todo_flags_start */ 77169689Skan 0, /* todo_flags_finish */ 78169689Skan 0 /* letter */ 79169689Skan}; 80169689Skan 81169689Skanstruct tree_opt_pass pass_early_local_passes = 82169689Skan{ 83169689Skan NULL, /* name */ 84169689Skan gate_all_optimizations, /* gate */ 85169689Skan NULL, /* execute */ 86169689Skan NULL, /* sub */ 87169689Skan NULL, /* next */ 88169689Skan 0, /* static_pass_number */ 89169689Skan 0, /* tv_id */ 90169689Skan 0, /* properties_required */ 91169689Skan 0, /* properties_provided */ 92169689Skan 0, /* properties_destroyed */ 93169689Skan 0, /* todo_flags_start */ 94169689Skan 0, /* todo_flags_finish */ 95169689Skan 0 /* letter */ 96169689Skan}; 97169689Skan 98169689Skan/* Pass: cleanup the CFG just before expanding trees to RTL. 99169689Skan This is just a round of label cleanups and case node grouping 100169689Skan because after the tree optimizers have run such cleanups may 101169689Skan be necessary. */ 102169689Skan 103169689Skanstatic unsigned int 104169689Skanexecute_cleanup_cfg_pre_ipa (void) 105169689Skan{ 106169689Skan cleanup_tree_cfg (); 107169689Skan return 0; 108132718Skan} 109132718Skan 110169689Skanstruct tree_opt_pass pass_cleanup_cfg = 111169689Skan{ 112169689Skan "cleanup_cfg", /* name */ 113169689Skan NULL, /* gate */ 114169689Skan execute_cleanup_cfg_pre_ipa, /* execute */ 115169689Skan NULL, /* sub */ 116169689Skan NULL, /* next */ 117169689Skan 0, /* static_pass_number */ 118169689Skan 0, /* tv_id */ 119169689Skan PROP_cfg, /* properties_required */ 120169689Skan 0, /* properties_provided */ 121169689Skan 0, /* properties_destroyed */ 122169689Skan 0, /* todo_flags_start */ 123169689Skan TODO_dump_func, /* todo_flags_finish */ 124169689Skan 0 /* letter */ 125169689Skan}; 126132718Skan 127169689Skan 128169689Skan/* Pass: cleanup the CFG just before expanding trees to RTL. 129169689Skan This is just a round of label cleanups and case node grouping 130169689Skan because after the tree optimizers have run such cleanups may 131169689Skan be necessary. */ 132169689Skan 133169689Skanstatic unsigned int 134169689Skanexecute_cleanup_cfg_post_optimizing (void) 135132718Skan{ 136169689Skan fold_cond_expr_cond (); 137169689Skan cleanup_tree_cfg (); 138169689Skan cleanup_dead_labels (); 139169689Skan group_case_labels (); 140169689Skan return 0; 141169689Skan} 142132718Skan 143169689Skanstruct tree_opt_pass pass_cleanup_cfg_post_optimizing = 144169689Skan{ 145169689Skan "final_cleanup", /* name */ 146169689Skan NULL, /* gate */ 147169689Skan execute_cleanup_cfg_post_optimizing, /* execute */ 148169689Skan NULL, /* sub */ 149169689Skan NULL, /* next */ 150169689Skan 0, /* static_pass_number */ 151169689Skan 0, /* tv_id */ 152169689Skan PROP_cfg, /* properties_required */ 153169689Skan 0, /* properties_provided */ 154169689Skan 0, /* properties_destroyed */ 155169689Skan 0, /* todo_flags_start */ 156169689Skan TODO_dump_func, /* todo_flags_finish */ 157169689Skan 0 /* letter */ 158169689Skan}; 159132718Skan 160169689Skan/* Pass: do the actions required to finish with tree-ssa optimization 161169689Skan passes. */ 162132718Skan 163169689Skanstatic unsigned int 164169689Skanexecute_free_datastructures (void) 165169689Skan{ 166169689Skan /* ??? This isn't the right place for this. Worse, it got computed 167169689Skan more or less at random in various passes. */ 168169689Skan free_dominance_info (CDI_DOMINATORS); 169169689Skan free_dominance_info (CDI_POST_DOMINATORS); 170132718Skan 171169689Skan /* Remove the ssa structures. Do it here since this includes statement 172169689Skan annotations that need to be intact during disband_implicit_edges. */ 173169689Skan delete_tree_ssa (); 174169689Skan return 0; 175169689Skan} 176132718Skan 177169689Skanstruct tree_opt_pass pass_free_datastructures = 178169689Skan{ 179169689Skan NULL, /* name */ 180169689Skan NULL, /* gate */ 181169689Skan execute_free_datastructures, /* execute */ 182169689Skan NULL, /* sub */ 183169689Skan NULL, /* next */ 184169689Skan 0, /* static_pass_number */ 185169689Skan 0, /* tv_id */ 186169689Skan PROP_cfg, /* properties_required */ 187169689Skan 0, /* properties_provided */ 188169689Skan 0, /* properties_destroyed */ 189169689Skan 0, /* todo_flags_start */ 190169689Skan 0, /* todo_flags_finish */ 191169689Skan 0 /* letter */ 192169689Skan}; 193169689Skan/* Pass: free cfg annotations. */ 194132718Skan 195169689Skanstatic unsigned int 196169689Skanexecute_free_cfg_annotations (void) 197169689Skan{ 198169689Skan basic_block bb; 199169689Skan block_stmt_iterator bsi; 200169689Skan 201169689Skan /* Emit gotos for implicit jumps. */ 202169689Skan disband_implicit_edges (); 203169689Skan 204169689Skan /* Remove annotations from every tree in the function. */ 205169689Skan FOR_EACH_BB (bb) 206169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 207169689Skan { 208169689Skan tree stmt = bsi_stmt (bsi); 209169689Skan ggc_free (stmt->common.ann); 210169689Skan stmt->common.ann = NULL; 211169689Skan } 212169689Skan 213169689Skan /* And get rid of annotations we no longer need. */ 214169689Skan delete_tree_cfg_annotations (); 215169689Skan 216169689Skan#ifdef ENABLE_CHECKING 217169689Skan /* Once the statement annotations have been removed, we can verify 218169689Skan the integrity of statements in the EH throw table. */ 219169689Skan verify_eh_throw_table_statements (); 220169689Skan#endif 221169689Skan return 0; 222132718Skan} 223132718Skan 224169689Skanstruct tree_opt_pass pass_free_cfg_annotations = 225169689Skan{ 226169689Skan NULL, /* name */ 227169689Skan NULL, /* gate */ 228169689Skan execute_free_cfg_annotations, /* execute */ 229169689Skan NULL, /* sub */ 230169689Skan NULL, /* next */ 231169689Skan 0, /* static_pass_number */ 232169689Skan 0, /* tv_id */ 233169689Skan PROP_cfg, /* properties_required */ 234169689Skan 0, /* properties_provided */ 235169689Skan 0, /* properties_destroyed */ 236169689Skan 0, /* todo_flags_start */ 237169689Skan 0, /* todo_flags_finish */ 238169689Skan 0 /* letter */ 239169689Skan}; 240169689Skan 241169689Skan/* Return true if BB has at least one abnormal outgoing edge. */ 242169689Skan 243169689Skanstatic inline bool 244169689Skanhas_abnormal_outgoing_edge_p (basic_block bb) 245169689Skan{ 246169689Skan edge e; 247169689Skan edge_iterator ei; 248169689Skan 249169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 250169689Skan if (e->flags & EDGE_ABNORMAL) 251169689Skan return true; 252169689Skan 253169689Skan return false; 254169689Skan} 255169689Skan 256169689Skan/* Pass: fixup_cfg. IPA passes, compilation of earlier functions or inlining 257169689Skan might have changed some properties, such as marked functions nothrow or 258169689Skan added calls that can potentially go to non-local labels. Remove redundant 259169689Skan edges and basic blocks, and create new ones if necessary. */ 260169689Skan 261169689Skanstatic unsigned int 262169689Skanexecute_fixup_cfg (void) 263169689Skan{ 264169689Skan basic_block bb; 265169689Skan block_stmt_iterator bsi; 266169689Skan 267169689Skan if (cfun->eh) 268169689Skan FOR_EACH_BB (bb) 269169689Skan { 270169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 271169689Skan { 272169689Skan tree stmt = bsi_stmt (bsi); 273169689Skan tree call = get_call_expr_in (stmt); 274169689Skan 275169689Skan if (call && call_expr_flags (call) & (ECF_CONST | ECF_PURE)) 276169689Skan TREE_SIDE_EFFECTS (call) = 0; 277169689Skan if (!tree_could_throw_p (stmt) && lookup_stmt_eh_region (stmt)) 278169689Skan remove_stmt_from_eh_region (stmt); 279169689Skan } 280169689Skan tree_purge_dead_eh_edges (bb); 281169689Skan } 282169689Skan 283169689Skan if (current_function_has_nonlocal_label) 284169689Skan FOR_EACH_BB (bb) 285169689Skan { 286169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 287169689Skan { 288169689Skan tree stmt = bsi_stmt (bsi); 289169689Skan if (tree_can_make_abnormal_goto (stmt)) 290169689Skan { 291169689Skan if (stmt == bsi_stmt (bsi_last (bb))) 292169689Skan { 293169689Skan if (!has_abnormal_outgoing_edge_p (bb)) 294169689Skan make_abnormal_goto_edges (bb, true); 295169689Skan } 296169689Skan else 297169689Skan { 298169689Skan edge e = split_block (bb, stmt); 299169689Skan bb = e->src; 300169689Skan make_abnormal_goto_edges (bb, true); 301169689Skan } 302169689Skan break; 303169689Skan } 304169689Skan } 305169689Skan } 306169689Skan 307169689Skan cleanup_tree_cfg (); 308169689Skan 309169689Skan /* Dump a textual representation of the flowgraph. */ 310169689Skan if (dump_file) 311169689Skan dump_tree_cfg (dump_file, dump_flags); 312169689Skan 313169689Skan return 0; 314169689Skan} 315169689Skan 316169689Skanstruct tree_opt_pass pass_fixup_cfg = 317169689Skan{ 318169689Skan "fixupcfg", /* name */ 319169689Skan NULL, /* gate */ 320169689Skan execute_fixup_cfg, /* execute */ 321169689Skan NULL, /* sub */ 322169689Skan NULL, /* next */ 323169689Skan 0, /* static_pass_number */ 324169689Skan 0, /* tv_id */ 325169689Skan PROP_cfg, /* properties_required */ 326169689Skan 0, /* properties_provided */ 327169689Skan 0, /* properties_destroyed */ 328169689Skan 0, /* todo_flags_start */ 329169689Skan 0, /* todo_flags_finish */ 330169689Skan 0 /* letter */ 331169689Skan}; 332169689Skan 333169689Skan/* Do the actions required to initialize internal data structures used 334169689Skan in tree-ssa optimization passes. */ 335169689Skan 336169689Skanstatic unsigned int 337169689Skanexecute_init_datastructures (void) 338169689Skan{ 339169689Skan /* Allocate hash tables, arrays and other structures. */ 340169689Skan init_tree_ssa (); 341169689Skan return 0; 342169689Skan} 343169689Skan 344169689Skanstruct tree_opt_pass pass_init_datastructures = 345169689Skan{ 346169689Skan NULL, /* name */ 347169689Skan NULL, /* gate */ 348169689Skan execute_init_datastructures, /* execute */ 349169689Skan NULL, /* sub */ 350169689Skan NULL, /* next */ 351169689Skan 0, /* static_pass_number */ 352169689Skan 0, /* tv_id */ 353169689Skan PROP_cfg, /* properties_required */ 354169689Skan 0, /* properties_provided */ 355169689Skan 0, /* properties_destroyed */ 356169689Skan 0, /* todo_flags_start */ 357169689Skan 0, /* todo_flags_finish */ 358169689Skan 0 /* letter */ 359169689Skan}; 360169689Skan 361169689Skanvoid 362169689Skantree_lowering_passes (tree fn) 363169689Skan{ 364169689Skan tree saved_current_function_decl = current_function_decl; 365169689Skan 366169689Skan current_function_decl = fn; 367169689Skan push_cfun (DECL_STRUCT_FUNCTION (fn)); 368169689Skan tree_register_cfg_hooks (); 369169689Skan bitmap_obstack_initialize (NULL); 370169689Skan execute_pass_list (all_lowering_passes); 371169689Skan free_dominance_info (CDI_POST_DOMINATORS); 372169689Skan compact_blocks (); 373169689Skan current_function_decl = saved_current_function_decl; 374169689Skan bitmap_obstack_release (NULL); 375169689Skan pop_cfun (); 376169689Skan} 377169689Skan 378169689Skan/* Update recursively all inlined_to pointers of functions 379169689Skan inlined into NODE to INLINED_TO. */ 380169689Skanstatic void 381169689Skanupdate_inlined_to_pointers (struct cgraph_node *node, 382169689Skan struct cgraph_node *inlined_to) 383169689Skan{ 384169689Skan struct cgraph_edge *e; 385169689Skan for (e = node->callees; e; e = e->next_callee) 386169689Skan { 387169689Skan if (e->callee->global.inlined_to) 388169689Skan { 389169689Skan e->callee->global.inlined_to = inlined_to; 390169689Skan update_inlined_to_pointers (e->callee, inlined_to); 391169689Skan } 392169689Skan } 393169689Skan} 394169689Skan 395169689Skan 396132718Skan/* For functions-as-trees languages, this performs all optimization and 397132718Skan compilation for FNDECL. */ 398132718Skan 399132718Skanvoid 400169689Skantree_rest_of_compilation (tree fndecl) 401132718Skan{ 402132718Skan location_t saved_loc; 403169689Skan struct cgraph_node *node; 404132718Skan 405132718Skan timevar_push (TV_EXPAND); 406132718Skan 407169689Skan gcc_assert (!flag_unit_at_a_time || cgraph_global_info_ready); 408132718Skan 409169689Skan node = cgraph_node (fndecl); 410169689Skan 411169689Skan /* We might need the body of this function so that we can expand 412169689Skan it inline somewhere else. */ 413169689Skan if (cgraph_preserve_function_body_p (fndecl)) 414169689Skan save_inline_function_body (node); 415169689Skan 416132718Skan /* Initialize the RTL code for the function. */ 417132718Skan current_function_decl = fndecl; 418132718Skan saved_loc = input_location; 419132718Skan input_location = DECL_SOURCE_LOCATION (fndecl); 420132718Skan init_function_start (fndecl); 421132718Skan 422132718Skan /* Even though we're inside a function body, we still don't want to 423132718Skan call expand_expr to calculate the size of a variable-sized array. 424132718Skan We haven't necessarily assigned RTL to all variables yet, so it's 425132718Skan not safe to try to expand expressions involving them. */ 426132718Skan cfun->x_dont_save_pending_sizes_p = 1; 427169689Skan cfun->after_inlining = true; 428132718Skan 429169689Skan if (flag_inline_trees) 430169689Skan { 431169689Skan struct cgraph_edge *e; 432169689Skan for (e = node->callees; e; e = e->next_callee) 433169689Skan if (!e->inline_failed || warn_inline) 434169689Skan break; 435169689Skan if (e) 436169689Skan { 437169689Skan timevar_push (TV_INTEGRATION); 438169689Skan optimize_inline_calls (fndecl); 439169689Skan timevar_pop (TV_INTEGRATION); 440169689Skan } 441169689Skan } 442169689Skan /* In non-unit-at-a-time we must mark all referenced functions as needed. 443169689Skan */ 444169689Skan if (!flag_unit_at_a_time) 445169689Skan { 446169689Skan struct cgraph_edge *e; 447169689Skan for (e = node->callees; e; e = e->next_callee) 448169689Skan if (e->callee->analyzed) 449169689Skan cgraph_mark_needed_node (e->callee); 450169689Skan } 451132718Skan 452169689Skan /* We are not going to maintain the cgraph edges up to date. 453169689Skan Kill it so it won't confuse us. */ 454169689Skan cgraph_node_remove_callees (node); 455132718Skan 456132718Skan 457169689Skan /* Initialize the default bitmap obstack. */ 458169689Skan bitmap_obstack_initialize (NULL); 459169689Skan bitmap_obstack_initialize (®_obstack); /* FIXME, only at RTL generation*/ 460169689Skan 461169689Skan tree_register_cfg_hooks (); 462169689Skan /* Perform all tree transforms and optimizations. */ 463169689Skan execute_pass_list (all_passes); 464169689Skan 465169689Skan bitmap_obstack_release (®_obstack); 466132718Skan 467169689Skan /* Release the default bitmap obstack. */ 468169689Skan bitmap_obstack_release (NULL); 469169689Skan 470169689Skan DECL_SAVED_TREE (fndecl) = NULL; 471169689Skan cfun = 0; 472132718Skan 473132718Skan /* If requested, warn about function definitions where the function will 474132718Skan return a value (usually of some struct or union type) which itself will 475132718Skan take up a lot of stack space. */ 476132718Skan if (warn_larger_than && !DECL_EXTERNAL (fndecl) && TREE_TYPE (fndecl)) 477132718Skan { 478132718Skan tree ret_type = TREE_TYPE (TREE_TYPE (fndecl)); 479132718Skan 480132718Skan if (ret_type && TYPE_SIZE_UNIT (ret_type) 481132718Skan && TREE_CODE (TYPE_SIZE_UNIT (ret_type)) == INTEGER_CST 482132718Skan && 0 < compare_tree_int (TYPE_SIZE_UNIT (ret_type), 483132718Skan larger_than_size)) 484132718Skan { 485132718Skan unsigned int size_as_int 486132718Skan = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ret_type)); 487132718Skan 488132718Skan if (compare_tree_int (TYPE_SIZE_UNIT (ret_type), size_as_int) == 0) 489169689Skan warning (0, "size of return value of %q+D is %u bytes", 490169689Skan fndecl, size_as_int); 491132718Skan else 492169689Skan warning (0, "size of return value of %q+D is larger than %wd bytes", 493169689Skan fndecl, larger_than_size); 494132718Skan } 495132718Skan } 496132718Skan 497169689Skan if (!flag_inline_trees) 498132718Skan { 499169689Skan DECL_SAVED_TREE (fndecl) = NULL; 500169689Skan if (DECL_STRUCT_FUNCTION (fndecl) == 0 501169689Skan && !cgraph_node (fndecl)->origin) 502132718Skan { 503169689Skan /* Stop pointing to the local nodes about to be freed. 504169689Skan But DECL_INITIAL must remain nonzero so we know this 505169689Skan was an actual function definition. 506169689Skan For a nested function, this is done in c_pop_function_context. 507169689Skan If rest_of_compilation set this to 0, leave it 0. */ 508169689Skan if (DECL_INITIAL (fndecl) != 0) 509169689Skan DECL_INITIAL (fndecl) = error_mark_node; 510132718Skan } 511132718Skan } 512132718Skan 513132718Skan input_location = saved_loc; 514132718Skan 515169689Skan ggc_collect (); 516132718Skan timevar_pop (TV_EXPAND); 517132718Skan} 518