cgraphunit.c revision 261188
1/* Callgraph based interprocedural optimizations. 2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3 Contributed by Jan Hubicka 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for 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 the Free 19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2002110-1301, USA. */ 21 22/* This module implements main driver of compilation process as well as 23 few basic interprocedural optimizers. 24 25 The main scope of this file is to act as an interface in between 26 tree based frontends and the backend (and middle end) 27 28 The front-end is supposed to use following functionality: 29 30 - cgraph_finalize_function 31 32 This function is called once front-end has parsed whole body of function 33 and it is certain that the function body nor the declaration will change. 34 35 (There is one exception needed for implementing GCC extern inline function.) 36 37 - cgraph_varpool_finalize_variable 38 39 This function has same behavior as the above but is used for static 40 variables. 41 42 - cgraph_finalize_compilation_unit 43 44 This function is called once compilation unit is finalized and it will 45 no longer change. 46 47 In the unit-at-a-time the call-graph construction and local function 48 analysis takes place here. Bodies of unreachable functions are released 49 to conserve memory usage. 50 51 ??? The compilation unit in this point of view should be compilation 52 unit as defined by the language - for instance C frontend allows multiple 53 compilation units to be parsed at once and it should call function each 54 time parsing is done so we save memory. 55 56 - cgraph_optimize 57 58 In this unit-at-a-time compilation the intra procedural analysis takes 59 place here. In particular the static functions whose address is never 60 taken are marked as local. Backend can then use this information to 61 modify calling conventions, do better inlining or similar optimizations. 62 63 - cgraph_assemble_pending_functions 64 - cgraph_varpool_assemble_pending_variables 65 66 In non-unit-at-a-time mode these functions can be used to force compilation 67 of functions or variables that are known to be needed at given stage 68 of compilation 69 70 - cgraph_mark_needed_node 71 - cgraph_varpool_mark_needed_node 72 73 When function or variable is referenced by some hidden way (for instance 74 via assembly code and marked by attribute "used"), the call-graph data structure 75 must be updated accordingly by this function. 76 77 - analyze_expr callback 78 79 This function is responsible for lowering tree nodes not understood by 80 generic code into understandable ones or alternatively marking 81 callgraph and varpool nodes referenced by the as needed. 82 83 ??? On the tree-ssa genericizing should take place here and we will avoid 84 need for these hooks (replacing them by genericizing hook) 85 86 - expand_function callback 87 88 This function is used to expand function and pass it into RTL back-end. 89 Front-end should not make any assumptions about when this function can be 90 called. In particular cgraph_assemble_pending_functions, 91 cgraph_varpool_assemble_pending_variables, cgraph_finalize_function, 92 cgraph_varpool_finalize_function, cgraph_optimize can cause arbitrarily 93 previously finalized functions to be expanded. 94 95 We implement two compilation modes. 96 97 - unit-at-a-time: In this mode analyzing of all functions is deferred 98 to cgraph_finalize_compilation_unit and expansion into cgraph_optimize. 99 100 In cgraph_finalize_compilation_unit the reachable functions are 101 analyzed. During analysis the call-graph edges from reachable 102 functions are constructed and their destinations are marked as 103 reachable. References to functions and variables are discovered too 104 and variables found to be needed output to the assembly file. Via 105 mark_referenced call in assemble_variable functions referenced by 106 static variables are noticed too. 107 108 The intra-procedural information is produced and its existence 109 indicated by global_info_ready. Once this flag is set it is impossible 110 to change function from !reachable to reachable and thus 111 assemble_variable no longer call mark_referenced. 112 113 Finally the call-graph is topologically sorted and all reachable functions 114 that has not been completely inlined or are not external are output. 115 116 ??? It is possible that reference to function or variable is optimized 117 out. We can not deal with this nicely because topological order is not 118 suitable for it. For tree-ssa we may consider another pass doing 119 optimization and re-discovering reachable functions. 120 121 ??? Reorganize code so variables are output very last and only if they 122 really has been referenced by produced code, so we catch more cases 123 where reference has been optimized out. 124 125 - non-unit-at-a-time 126 127 All functions are variables are output as early as possible to conserve 128 memory consumption. This may or may not result in less memory used but 129 it is still needed for some legacy code that rely on particular ordering 130 of things output from the compiler. 131 132 Varpool data structures are not used and variables are output directly. 133 134 Functions are output early using call of 135 cgraph_assemble_pending_function from cgraph_finalize_function. The 136 decision on whether function is needed is made more conservative so 137 uninlininable static functions are needed too. During the call-graph 138 construction the edge destinations are not marked as reachable and it 139 is completely relied upn assemble_variable to mark them. */ 140 141 142#include "config.h" 143#include "system.h" 144#include "coretypes.h" 145#include "tm.h" 146#include "tree.h" 147#include "rtl.h" 148#include "tree-flow.h" 149#include "tree-inline.h" 150#include "langhooks.h" 151#include "pointer-set.h" 152#include "toplev.h" 153#include "flags.h" 154#include "ggc.h" 155#include "debug.h" 156#include "target.h" 157#include "cgraph.h" 158#include "diagnostic.h" 159#include "timevar.h" 160#include "params.h" 161#include "fibheap.h" 162#include "c-common.h" 163#include "intl.h" 164#include "function.h" 165#include "ipa-prop.h" 166#include "tree-gimple.h" 167#include "tree-pass.h" 168#include "output.h" 169 170static void cgraph_expand_all_functions (void); 171static void cgraph_mark_functions_to_output (void); 172static void cgraph_expand_function (struct cgraph_node *); 173static tree record_reference (tree *, int *, void *); 174static void cgraph_output_pending_asms (void); 175static void cgraph_increase_alignment (void); 176 177/* Lists all assembled variables to be sent to debugger output later on. */ 178static GTY(()) struct cgraph_varpool_node *cgraph_varpool_assembled_nodes_queue; 179 180/* Records tree nodes seen in record_reference. Simply using 181 walk_tree_without_duplicates doesn't guarantee each node is visited 182 once because it gets a new htab upon each recursive call from 183 record_reference itself. */ 184static struct pointer_set_t *visited_nodes; 185 186static FILE *cgraph_dump_file; 187 188/* Determine if function DECL is needed. That is, visible to something 189 either outside this translation unit, something magic in the system 190 configury, or (if not doing unit-at-a-time) to something we havn't 191 seen yet. */ 192 193static bool 194decide_is_function_needed (struct cgraph_node *node, tree decl) 195{ 196 tree origin; 197 if (MAIN_NAME_P (DECL_NAME (decl)) 198 && TREE_PUBLIC (decl)) 199 { 200 node->local.externally_visible = true; 201 return true; 202 } 203 204 /* If the user told us it is used, then it must be so. */ 205 if (node->local.externally_visible) 206 return true; 207 208 if (!flag_unit_at_a_time && lookup_attribute ("used", DECL_ATTRIBUTES (decl))) 209 return true; 210 211 /* ??? If the assembler name is set by hand, it is possible to assemble 212 the name later after finalizing the function and the fact is noticed 213 in assemble_name then. This is arguably a bug. */ 214 if (DECL_ASSEMBLER_NAME_SET_P (decl) 215 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))) 216 return true; 217 218 /* If we decided it was needed before, but at the time we didn't have 219 the body of the function available, then it's still needed. We have 220 to go back and re-check its dependencies now. */ 221 if (node->needed) 222 return true; 223 224 /* Externally visible functions must be output. The exception is 225 COMDAT functions that must be output only when they are needed. 226 227 When not optimizing, also output the static functions. (see 228 PR24561), but don't do so for always_inline functions, functions 229 declared inline and nested functions. These was optimized out 230 in the original implementation and it is unclear whether we want 231 to change the behavior here. */ 232 if (((TREE_PUBLIC (decl) 233 || (!optimize && !node->local.disregard_inline_limits 234 && !DECL_DECLARED_INLINE_P (decl) 235 && !node->origin)) 236 && !flag_whole_program) 237 && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl)) 238 return true; 239 240 /* Constructors and destructors are reachable from the runtime by 241 some mechanism. */ 242 if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl)) 243 return true; 244 245 if (flag_unit_at_a_time) 246 return false; 247 248 /* If not doing unit at a time, then we'll only defer this function 249 if its marked for inlining. Otherwise we want to emit it now. */ 250 251 /* "extern inline" functions are never output locally. */ 252 if (DECL_EXTERNAL (decl)) 253 return false; 254 /* Nested functions of extern inline function shall not be emit unless 255 we inlined the origin. */ 256 for (origin = decl_function_context (decl); origin; 257 origin = decl_function_context (origin)) 258 if (DECL_EXTERNAL (origin)) 259 return false; 260 /* We want to emit COMDAT functions only when absolutely necessary. */ 261 if (DECL_COMDAT (decl)) 262 return false; 263 if (!DECL_INLINE (decl) 264 || (!node->local.disregard_inline_limits 265 /* When declared inline, defer even the uninlinable functions. 266 This allows them to be eliminated when unused. */ 267 && !DECL_DECLARED_INLINE_P (decl) 268 && (!node->local.inlinable || !cgraph_default_inline_p (node, NULL)))) 269 return true; 270 271 return false; 272} 273 274/* Walk the decls we marked as necessary and see if they reference new 275 variables or functions and add them into the worklists. */ 276static bool 277cgraph_varpool_analyze_pending_decls (void) 278{ 279 bool changed = false; 280 timevar_push (TV_CGRAPH); 281 282 while (cgraph_varpool_first_unanalyzed_node) 283 { 284 tree decl = cgraph_varpool_first_unanalyzed_node->decl; 285 286 cgraph_varpool_first_unanalyzed_node->analyzed = true; 287 288 cgraph_varpool_first_unanalyzed_node = cgraph_varpool_first_unanalyzed_node->next_needed; 289 290 /* Compute the alignment early so function body expanders are 291 already informed about increased alignment. */ 292 align_variable (decl, 0); 293 294 if (DECL_INITIAL (decl)) 295 { 296 visited_nodes = pointer_set_create (); 297 walk_tree (&DECL_INITIAL (decl), record_reference, NULL, visited_nodes); 298 pointer_set_destroy (visited_nodes); 299 visited_nodes = NULL; 300 } 301 changed = true; 302 } 303 timevar_pop (TV_CGRAPH); 304 return changed; 305} 306 307/* Optimization of function bodies might've rendered some variables as 308 unnecessary so we want to avoid these from being compiled. 309 310 This is done by pruning the queue and keeping only the variables that 311 really appear needed (ie they are either externally visible or referenced 312 by compiled function). Re-doing the reachability analysis on variables 313 brings back the remaining variables referenced by these. */ 314static void 315cgraph_varpool_remove_unreferenced_decls (void) 316{ 317 struct cgraph_varpool_node *next, *node = cgraph_varpool_nodes_queue; 318 319 cgraph_varpool_reset_queue (); 320 321 if (errorcount || sorrycount) 322 return; 323 324 while (node) 325 { 326 tree decl = node->decl; 327 next = node->next_needed; 328 node->needed = 0; 329 330 if (node->finalized 331 && ((DECL_ASSEMBLER_NAME_SET_P (decl) 332 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))) 333 || node->force_output 334 || decide_is_variable_needed (node, decl) 335 /* ??? Cgraph does not yet rule the world with an iron hand, 336 and does not control the emission of debug information. 337 After a variable has its DECL_RTL set, we must assume that 338 it may be referenced by the debug information, and we can 339 no longer elide it. */ 340 || DECL_RTL_SET_P (decl))) 341 cgraph_varpool_mark_needed_node (node); 342 343 node = next; 344 } 345 /* Make sure we mark alias targets as used targets. */ 346 finish_aliases_1 (); 347 cgraph_varpool_analyze_pending_decls (); 348} 349 350 351/* When not doing unit-at-a-time, output all functions enqueued. 352 Return true when such a functions were found. */ 353 354bool 355cgraph_assemble_pending_functions (void) 356{ 357 bool output = false; 358 359 if (flag_unit_at_a_time) 360 return false; 361 362 cgraph_output_pending_asms (); 363 364 while (cgraph_nodes_queue) 365 { 366 struct cgraph_node *n = cgraph_nodes_queue; 367 368 cgraph_nodes_queue = cgraph_nodes_queue->next_needed; 369 n->next_needed = NULL; 370 if (!n->global.inlined_to 371 && !n->alias 372 && !DECL_EXTERNAL (n->decl)) 373 { 374 cgraph_expand_function (n); 375 output = true; 376 } 377 } 378 379 /* Process CGRAPH_EXPAND_QUEUE, these are functions created during 380 the expansion process. Note that this queue may grow as its 381 being processed, as the new functions may generate new ones. */ 382 while (cgraph_expand_queue) 383 { 384 struct cgraph_node *n = cgraph_expand_queue; 385 cgraph_expand_queue = cgraph_expand_queue->next_needed; 386 n->next_needed = NULL; 387 cgraph_finalize_function (n->decl, false); 388 output = true; 389 } 390 391 return output; 392} 393 394 395/* As an GCC extension we allow redefinition of the function. The 396 semantics when both copies of bodies differ is not well defined. 397 We replace the old body with new body so in unit at a time mode 398 we always use new body, while in normal mode we may end up with 399 old body inlined into some functions and new body expanded and 400 inlined in others. 401 402 ??? It may make more sense to use one body for inlining and other 403 body for expanding the function but this is difficult to do. */ 404 405static void 406cgraph_reset_node (struct cgraph_node *node) 407{ 408 /* If node->output is set, then this is a unit-at-a-time compilation 409 and we have already begun whole-unit analysis. This is *not* 410 testing for whether we've already emitted the function. That 411 case can be sort-of legitimately seen with real function 412 redefinition errors. I would argue that the front end should 413 never present us with such a case, but don't enforce that for now. */ 414 gcc_assert (!node->output); 415 416 /* Reset our data structures so we can analyze the function again. */ 417 memset (&node->local, 0, sizeof (node->local)); 418 memset (&node->global, 0, sizeof (node->global)); 419 memset (&node->rtl, 0, sizeof (node->rtl)); 420 node->analyzed = false; 421 node->local.redefined_extern_inline = true; 422 node->local.finalized = false; 423 424 if (!flag_unit_at_a_time) 425 { 426 struct cgraph_node *n, *next; 427 428 for (n = cgraph_nodes; n; n = next) 429 { 430 next = n->next; 431 if (n->global.inlined_to == node) 432 cgraph_remove_node (n); 433 } 434 } 435 436 cgraph_node_remove_callees (node); 437 438 /* We may need to re-queue the node for assembling in case 439 we already proceeded it and ignored as not needed. */ 440 if (node->reachable && !flag_unit_at_a_time) 441 { 442 struct cgraph_node *n; 443 444 for (n = cgraph_nodes_queue; n; n = n->next_needed) 445 if (n == node) 446 break; 447 if (!n) 448 node->reachable = 0; 449 } 450} 451 452static void 453cgraph_lower_function (struct cgraph_node *node) 454{ 455 if (node->lowered) 456 return; 457 tree_lowering_passes (node->decl); 458 node->lowered = true; 459} 460 461/* APPLE LOCAL begin radar 6305545 */ 462/** lower_if_nested_functions - This routine is called from cplus side only. 463 Its purpose is to lower block helper (or any other nested function) 464 which may have been nested in a constructor or destructor. We have to 465 do this because structors are cloned and are not lowered themselves (which 466 is the only way to lower the nested functions). */ 467void 468lower_if_nested_functions (tree decl) 469{ 470 lower_nested_functions (decl, true); 471} 472/* APPLE LOCAL end radar 6305545 */ 473 474/* DECL has been parsed. Take it, queue it, compile it at the whim of the 475 logic in effect. If NESTED is true, then our caller cannot stand to have 476 the garbage collector run at the moment. We would need to either create 477 a new GC context, or just not compile right now. */ 478 479void 480cgraph_finalize_function (tree decl, bool nested) 481{ 482 struct cgraph_node *node = cgraph_node (decl); 483 484 if (node->local.finalized) 485 cgraph_reset_node (node); 486 487 notice_global_symbol (decl); 488 node->decl = decl; 489 node->local.finalized = true; 490 node->lowered = DECL_STRUCT_FUNCTION (decl)->cfg != NULL; 491 if (node->nested) 492 /* APPLE LOCAL radar 6305545 */ 493 lower_nested_functions (decl, false); 494 gcc_assert (!node->nested); 495 496 /* If not unit at a time, then we need to create the call graph 497 now, so that called functions can be queued and emitted now. */ 498 if (!flag_unit_at_a_time) 499 { 500 cgraph_analyze_function (node); 501 cgraph_decide_inlining_incrementally (node, false); 502 } 503 504 if (decide_is_function_needed (node, decl)) 505 cgraph_mark_needed_node (node); 506 507 /* Since we reclaim unreachable nodes at the end of every language 508 level unit, we need to be conservative about possible entry points 509 there. */ 510 if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))) 511 cgraph_mark_reachable_node (node); 512 513 /* If not unit at a time, go ahead and emit everything we've found 514 to be reachable at this time. */ 515 if (!nested) 516 { 517 if (!cgraph_assemble_pending_functions ()) 518 ggc_collect (); 519 } 520 521 /* If we've not yet emitted decl, tell the debug info about it. */ 522 if (!TREE_ASM_WRITTEN (decl)) 523 (*debug_hooks->deferred_inline_function) (decl); 524 525 /* Possibly warn about unused parameters. */ 526 if (warn_unused_parameter) 527 do_warn_unused_parameter (decl); 528} 529 530/* Walk tree and record all calls. Called via walk_tree. */ 531static tree 532record_reference (tree *tp, int *walk_subtrees, void *data) 533{ 534 tree t = *tp; 535 536 switch (TREE_CODE (t)) 537 { 538 case VAR_DECL: 539 /* ??? Really, we should mark this decl as *potentially* referenced 540 by this function and re-examine whether the decl is actually used 541 after rtl has been generated. */ 542 if (TREE_STATIC (t) || DECL_EXTERNAL (t)) 543 { 544 cgraph_varpool_mark_needed_node (cgraph_varpool_node (t)); 545 if (lang_hooks.callgraph.analyze_expr) 546 return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees, 547 data); 548 } 549 break; 550 551 case FDESC_EXPR: 552 case ADDR_EXPR: 553 if (flag_unit_at_a_time) 554 { 555 /* Record dereferences to the functions. This makes the 556 functions reachable unconditionally. */ 557 tree decl = TREE_OPERAND (*tp, 0); 558 if (TREE_CODE (decl) == FUNCTION_DECL) 559 cgraph_mark_needed_node (cgraph_node (decl)); 560 } 561 break; 562 563 default: 564 /* Save some cycles by not walking types and declaration as we 565 won't find anything useful there anyway. */ 566 if (IS_TYPE_OR_DECL_P (*tp)) 567 { 568 *walk_subtrees = 0; 569 break; 570 } 571 572 if ((unsigned int) TREE_CODE (t) >= LAST_AND_UNUSED_TREE_CODE) 573 return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees, data); 574 break; 575 } 576 577 return NULL; 578} 579 580/* Create cgraph edges for function calls inside BODY from NODE. */ 581 582static void 583cgraph_create_edges (struct cgraph_node *node, tree body) 584{ 585 basic_block bb; 586 587 struct function *this_cfun = DECL_STRUCT_FUNCTION (body); 588 block_stmt_iterator bsi; 589 tree step; 590 visited_nodes = pointer_set_create (); 591 592 /* Reach the trees by walking over the CFG, and note the 593 enclosing basic-blocks in the call edges. */ 594 FOR_EACH_BB_FN (bb, this_cfun) 595 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 596 { 597 tree stmt = bsi_stmt (bsi); 598 tree call = get_call_expr_in (stmt); 599 tree decl; 600 601 if (call && (decl = get_callee_fndecl (call))) 602 { 603 cgraph_create_edge (node, cgraph_node (decl), stmt, 604 bb->count, 605 bb->loop_depth); 606 walk_tree (&TREE_OPERAND (call, 1), 607 record_reference, node, visited_nodes); 608 if (TREE_CODE (stmt) == MODIFY_EXPR) 609 walk_tree (&TREE_OPERAND (stmt, 0), 610 record_reference, node, visited_nodes); 611 } 612 else 613 walk_tree (bsi_stmt_ptr (bsi), record_reference, node, visited_nodes); 614 } 615 616 /* Look for initializers of constant variables and private statics. */ 617 for (step = DECL_STRUCT_FUNCTION (body)->unexpanded_var_list; 618 step; 619 step = TREE_CHAIN (step)) 620 { 621 tree decl = TREE_VALUE (step); 622 if (TREE_CODE (decl) == VAR_DECL 623 && (TREE_STATIC (decl) && !DECL_EXTERNAL (decl)) 624 && flag_unit_at_a_time) 625 cgraph_varpool_finalize_decl (decl); 626 else if (TREE_CODE (decl) == VAR_DECL && DECL_INITIAL (decl)) 627 walk_tree (&DECL_INITIAL (decl), record_reference, node, visited_nodes); 628 } 629 630 pointer_set_destroy (visited_nodes); 631 visited_nodes = NULL; 632} 633 634/* Give initial reasons why inlining would fail. Those gets 635 either NULLified or usually overwritten by more precise reason 636 later. */ 637static void 638initialize_inline_failed (struct cgraph_node *node) 639{ 640 struct cgraph_edge *e; 641 642 for (e = node->callers; e; e = e->next_caller) 643 { 644 gcc_assert (!e->callee->global.inlined_to); 645 gcc_assert (e->inline_failed); 646 if (node->local.redefined_extern_inline) 647 e->inline_failed = N_("redefined extern inline functions are not " 648 "considered for inlining"); 649 else if (!node->local.inlinable) 650 e->inline_failed = N_("function not inlinable"); 651 else 652 e->inline_failed = N_("function not considered for inlining"); 653 } 654} 655 656/* Rebuild call edges from current function after a passes not aware 657 of cgraph updating. */ 658static unsigned int 659rebuild_cgraph_edges (void) 660{ 661 basic_block bb; 662 struct cgraph_node *node = cgraph_node (current_function_decl); 663 block_stmt_iterator bsi; 664 665 cgraph_node_remove_callees (node); 666 667 node->count = ENTRY_BLOCK_PTR->count; 668 669 FOR_EACH_BB (bb) 670 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 671 { 672 tree stmt = bsi_stmt (bsi); 673 tree call = get_call_expr_in (stmt); 674 tree decl; 675 676 if (call && (decl = get_callee_fndecl (call))) 677 cgraph_create_edge (node, cgraph_node (decl), stmt, 678 bb->count, 679 bb->loop_depth); 680 } 681 initialize_inline_failed (node); 682 gcc_assert (!node->global.inlined_to); 683 return 0; 684} 685 686struct tree_opt_pass pass_rebuild_cgraph_edges = 687{ 688 NULL, /* name */ 689 NULL, /* gate */ 690 rebuild_cgraph_edges, /* execute */ 691 NULL, /* sub */ 692 NULL, /* next */ 693 0, /* static_pass_number */ 694 0, /* tv_id */ 695 PROP_cfg, /* properties_required */ 696 0, /* properties_provided */ 697 0, /* properties_destroyed */ 698 0, /* todo_flags_start */ 699 0, /* todo_flags_finish */ 700 0 /* letter */ 701}; 702 703/* Verify cgraph nodes of given cgraph node. */ 704void 705verify_cgraph_node (struct cgraph_node *node) 706{ 707 struct cgraph_edge *e; 708 struct cgraph_node *main_clone; 709 struct function *this_cfun = DECL_STRUCT_FUNCTION (node->decl); 710 basic_block this_block; 711 block_stmt_iterator bsi; 712 bool error_found = false; 713 714 if (errorcount || sorrycount) 715 return; 716 717 timevar_push (TV_CGRAPH_VERIFY); 718 for (e = node->callees; e; e = e->next_callee) 719 if (e->aux) 720 { 721 error ("aux field set for edge %s->%s", 722 cgraph_node_name (e->caller), cgraph_node_name (e->callee)); 723 error_found = true; 724 } 725 if (node->count < 0) 726 { 727 error ("Execution count is negative"); 728 error_found = true; 729 } 730 for (e = node->callers; e; e = e->next_caller) 731 { 732 if (e->count < 0) 733 { 734 error ("caller edge count is negative"); 735 error_found = true; 736 } 737 if (!e->inline_failed) 738 { 739 if (node->global.inlined_to 740 != (e->caller->global.inlined_to 741 ? e->caller->global.inlined_to : e->caller)) 742 { 743 error ("inlined_to pointer is wrong"); 744 error_found = true; 745 } 746 if (node->callers->next_caller) 747 { 748 error ("multiple inline callers"); 749 error_found = true; 750 } 751 } 752 else 753 if (node->global.inlined_to) 754 { 755 error ("inlined_to pointer set for noninline callers"); 756 error_found = true; 757 } 758 } 759 if (!node->callers && node->global.inlined_to) 760 { 761 error ("inlined_to pointer is set but no predecessors found"); 762 error_found = true; 763 } 764 if (node->global.inlined_to == node) 765 { 766 error ("inlined_to pointer refers to itself"); 767 error_found = true; 768 } 769 770 for (main_clone = cgraph_node (node->decl); main_clone; 771 main_clone = main_clone->next_clone) 772 if (main_clone == node) 773 break; 774 if (!cgraph_node (node->decl)) 775 { 776 error ("node not found in cgraph_hash"); 777 error_found = true; 778 } 779 780 if (node->analyzed 781 && DECL_SAVED_TREE (node->decl) && !TREE_ASM_WRITTEN (node->decl) 782 && (!DECL_EXTERNAL (node->decl) || node->global.inlined_to)) 783 { 784 if (this_cfun->cfg) 785 { 786 /* The nodes we're interested in are never shared, so walk 787 the tree ignoring duplicates. */ 788 visited_nodes = pointer_set_create (); 789 /* Reach the trees by walking over the CFG, and note the 790 enclosing basic-blocks in the call edges. */ 791 FOR_EACH_BB_FN (this_block, this_cfun) 792 for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi)) 793 { 794 tree stmt = bsi_stmt (bsi); 795 tree call = get_call_expr_in (stmt); 796 tree decl; 797 if (call && (decl = get_callee_fndecl (call))) 798 { 799 struct cgraph_edge *e = cgraph_edge (node, stmt); 800 if (e) 801 { 802 if (e->aux) 803 { 804 error ("shared call_stmt:"); 805 debug_generic_stmt (stmt); 806 error_found = true; 807 } 808 if (e->callee->decl != cgraph_node (decl)->decl 809 && e->inline_failed) 810 { 811 error ("edge points to wrong declaration:"); 812 debug_tree (e->callee->decl); 813 fprintf (stderr," Instead of:"); 814 debug_tree (decl); 815 } 816 e->aux = (void *)1; 817 } 818 else 819 { 820 error ("missing callgraph edge for call stmt:"); 821 debug_generic_stmt (stmt); 822 error_found = true; 823 } 824 } 825 } 826 pointer_set_destroy (visited_nodes); 827 visited_nodes = NULL; 828 } 829 else 830 /* No CFG available?! */ 831 gcc_unreachable (); 832 833 for (e = node->callees; e; e = e->next_callee) 834 { 835 if (!e->aux) 836 { 837 error ("edge %s->%s has no corresponding call_stmt", 838 cgraph_node_name (e->caller), 839 cgraph_node_name (e->callee)); 840 debug_generic_stmt (e->call_stmt); 841 error_found = true; 842 } 843 e->aux = 0; 844 } 845 } 846 if (error_found) 847 { 848 dump_cgraph_node (stderr, node); 849 internal_error ("verify_cgraph_node failed"); 850 } 851 timevar_pop (TV_CGRAPH_VERIFY); 852} 853 854/* Verify whole cgraph structure. */ 855void 856verify_cgraph (void) 857{ 858 struct cgraph_node *node; 859 860 if (sorrycount || errorcount) 861 return; 862 863 for (node = cgraph_nodes; node; node = node->next) 864 verify_cgraph_node (node); 865} 866 867/* Output one variable, if necessary. Return whether we output it. */ 868static bool 869cgraph_varpool_assemble_decl (struct cgraph_varpool_node *node) 870{ 871 tree decl = node->decl; 872 873 if (!TREE_ASM_WRITTEN (decl) 874 && !node->alias 875 && !DECL_EXTERNAL (decl) 876 && (TREE_CODE (decl) != VAR_DECL || !DECL_HAS_VALUE_EXPR_P (decl))) 877 { 878 assemble_variable (decl, 0, 1, 0); 879 return TREE_ASM_WRITTEN (decl); 880 } 881 882 return false; 883} 884 885/* Output all variables enqueued to be assembled. */ 886bool 887cgraph_varpool_assemble_pending_decls (void) 888{ 889 bool changed = false; 890 891 if (errorcount || sorrycount) 892 return false; 893 894 /* EH might mark decls as needed during expansion. This should be safe since 895 we don't create references to new function, but it should not be used 896 elsewhere. */ 897 cgraph_varpool_analyze_pending_decls (); 898 899 while (cgraph_varpool_nodes_queue) 900 { 901 struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue; 902 903 cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->next_needed; 904 if (cgraph_varpool_assemble_decl (node)) 905 { 906 changed = true; 907 node->next_needed = cgraph_varpool_assembled_nodes_queue; 908 cgraph_varpool_assembled_nodes_queue = node; 909 node->finalized = 1; 910 } 911 else 912 node->next_needed = NULL; 913 } 914 /* cgraph_varpool_nodes_queue is now empty, clear the pointer to the last 915 element in the queue. */ 916 cgraph_varpool_last_needed_node = NULL; 917 return changed; 918} 919/* Output all variables enqueued to be assembled. */ 920static void 921cgraph_varpool_output_debug_info (void) 922{ 923 timevar_push (TV_SYMOUT); 924 if (errorcount == 0 && sorrycount == 0) 925 while (cgraph_varpool_assembled_nodes_queue) 926 { 927 struct cgraph_varpool_node *node = cgraph_varpool_assembled_nodes_queue; 928 929 /* Local static variables are never seen by check_global_declarations 930 so we need to output debug info by hand. */ 931 if (DECL_CONTEXT (node->decl) 932 && (TREE_CODE (DECL_CONTEXT (node->decl)) == BLOCK 933 || TREE_CODE (DECL_CONTEXT (node->decl)) == FUNCTION_DECL) 934 && errorcount == 0 && sorrycount == 0) 935 (*debug_hooks->global_decl) (node->decl); 936 cgraph_varpool_assembled_nodes_queue = node->next_needed; 937 node->next_needed = 0; 938 } 939 timevar_pop (TV_SYMOUT); 940} 941 942/* Output all asm statements we have stored up to be output. */ 943 944static void 945cgraph_output_pending_asms (void) 946{ 947 struct cgraph_asm_node *can; 948 949 if (errorcount || sorrycount) 950 return; 951 952 for (can = cgraph_asm_nodes; can; can = can->next) 953 assemble_asm (can->asm_str); 954 cgraph_asm_nodes = NULL; 955} 956 957/* Analyze the function scheduled to be output. */ 958void 959cgraph_analyze_function (struct cgraph_node *node) 960{ 961 tree decl = node->decl; 962 963 current_function_decl = decl; 964 push_cfun (DECL_STRUCT_FUNCTION (decl)); 965 cgraph_lower_function (node); 966 967 /* First kill forward declaration so reverse inlining works properly. */ 968 cgraph_create_edges (node, decl); 969 970 node->local.inlinable = tree_inlinable_function_p (decl); 971 if (!flag_unit_at_a_time) 972 node->local.self_insns = estimate_num_insns (decl); 973 if (node->local.inlinable) 974 node->local.disregard_inline_limits 975 = lang_hooks.tree_inlining.disregard_inline_limits (decl); 976 initialize_inline_failed (node); 977 if (flag_really_no_inline && !node->local.disregard_inline_limits) 978 node->local.inlinable = 0; 979 /* Inlining characteristics are maintained by the cgraph_mark_inline. */ 980 node->global.insns = node->local.self_insns; 981 982 node->analyzed = true; 983 pop_cfun (); 984 current_function_decl = NULL; 985} 986 987/* Look for externally_visible and used attributes and mark cgraph nodes 988 accordingly. 989 990 We cannot mark the nodes at the point the attributes are processed (in 991 handle_*_attribute) because the copy of the declarations available at that 992 point may not be canonical. For example, in: 993 994 void f(); 995 void f() __attribute__((used)); 996 997 the declaration we see in handle_used_attribute will be the second 998 declaration -- but the front end will subsequently merge that declaration 999 with the original declaration and discard the second declaration. 1000 1001 Furthermore, we can't mark these nodes in cgraph_finalize_function because: 1002 1003 void f() {} 1004 void f() __attribute__((externally_visible)); 1005 1006 is valid. 1007 1008 So, we walk the nodes at the end of the translation unit, applying the 1009 attributes at that point. */ 1010 1011static void 1012process_function_and_variable_attributes (struct cgraph_node *first, 1013 struct cgraph_varpool_node *first_var) 1014{ 1015 struct cgraph_node *node; 1016 struct cgraph_varpool_node *vnode; 1017 1018 for (node = cgraph_nodes; node != first; node = node->next) 1019 { 1020 tree decl = node->decl; 1021 if (lookup_attribute ("used", DECL_ATTRIBUTES (decl))) 1022 { 1023 mark_decl_referenced (decl); 1024 if (node->local.finalized) 1025 cgraph_mark_needed_node (node); 1026 } 1027 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl))) 1028 { 1029 if (! TREE_PUBLIC (node->decl)) 1030 warning (OPT_Wattributes, 1031 "%J%<externally_visible%> attribute have effect only on public objects", 1032 node->decl); 1033 else 1034 { 1035 if (node->local.finalized) 1036 cgraph_mark_needed_node (node); 1037 node->local.externally_visible = true; 1038 } 1039 } 1040 } 1041 for (vnode = cgraph_varpool_nodes; vnode != first_var; vnode = vnode->next) 1042 { 1043 tree decl = vnode->decl; 1044 if (lookup_attribute ("used", DECL_ATTRIBUTES (decl))) 1045 { 1046 mark_decl_referenced (decl); 1047 if (vnode->finalized) 1048 cgraph_varpool_mark_needed_node (vnode); 1049 } 1050 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl))) 1051 { 1052 if (! TREE_PUBLIC (vnode->decl)) 1053 warning (OPT_Wattributes, 1054 "%J%<externally_visible%> attribute have effect only on public objects", 1055 vnode->decl); 1056 else 1057 { 1058 if (vnode->finalized) 1059 cgraph_varpool_mark_needed_node (vnode); 1060 vnode->externally_visible = true; 1061 } 1062 } 1063 } 1064} 1065 1066/* Analyze the whole compilation unit once it is parsed completely. */ 1067 1068void 1069cgraph_finalize_compilation_unit (void) 1070{ 1071 struct cgraph_node *node, *next; 1072 /* Keep track of already processed nodes when called multiple times for 1073 intermodule optimization. */ 1074 static struct cgraph_node *first_analyzed; 1075 struct cgraph_node *first_processed = first_analyzed; 1076 static struct cgraph_varpool_node *first_analyzed_var; 1077 1078 if (errorcount || sorrycount) 1079 return; 1080 1081 finish_aliases_1 (); 1082 1083 if (!flag_unit_at_a_time) 1084 { 1085 cgraph_output_pending_asms (); 1086 cgraph_assemble_pending_functions (); 1087 cgraph_varpool_output_debug_info (); 1088 return; 1089 } 1090 1091 if (!quiet_flag) 1092 { 1093 fprintf (stderr, "\nAnalyzing compilation unit"); 1094 fflush (stderr); 1095 } 1096 1097 timevar_push (TV_CGRAPH); 1098 process_function_and_variable_attributes (first_processed, 1099 first_analyzed_var); 1100 first_processed = cgraph_nodes; 1101 first_analyzed_var = cgraph_varpool_nodes; 1102 cgraph_varpool_analyze_pending_decls (); 1103 if (cgraph_dump_file) 1104 { 1105 fprintf (cgraph_dump_file, "Initial entry points:"); 1106 for (node = cgraph_nodes; node != first_analyzed; node = node->next) 1107 if (node->needed && DECL_SAVED_TREE (node->decl)) 1108 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node)); 1109 fprintf (cgraph_dump_file, "\n"); 1110 } 1111 1112 /* Propagate reachability flag and lower representation of all reachable 1113 functions. In the future, lowering will introduce new functions and 1114 new entry points on the way (by template instantiation and virtual 1115 method table generation for instance). */ 1116 while (cgraph_nodes_queue) 1117 { 1118 struct cgraph_edge *edge; 1119 tree decl = cgraph_nodes_queue->decl; 1120 1121 node = cgraph_nodes_queue; 1122 cgraph_nodes_queue = cgraph_nodes_queue->next_needed; 1123 node->next_needed = NULL; 1124 1125 /* ??? It is possible to create extern inline function and later using 1126 weak alias attribute to kill its body. See 1127 gcc.c-torture/compile/20011119-1.c */ 1128 if (!DECL_SAVED_TREE (decl)) 1129 { 1130 cgraph_reset_node (node); 1131 continue; 1132 } 1133 1134 gcc_assert (!node->analyzed && node->reachable); 1135 gcc_assert (DECL_SAVED_TREE (decl)); 1136 1137 cgraph_analyze_function (node); 1138 1139 for (edge = node->callees; edge; edge = edge->next_callee) 1140 if (!edge->callee->reachable) 1141 cgraph_mark_reachable_node (edge->callee); 1142 1143 /* We finalize local static variables during constructing callgraph 1144 edges. Process their attributes too. */ 1145 process_function_and_variable_attributes (first_processed, 1146 first_analyzed_var); 1147 first_processed = cgraph_nodes; 1148 first_analyzed_var = cgraph_varpool_nodes; 1149 cgraph_varpool_analyze_pending_decls (); 1150 } 1151 1152 /* Collect entry points to the unit. */ 1153 if (cgraph_dump_file) 1154 { 1155 fprintf (cgraph_dump_file, "Unit entry points:"); 1156 for (node = cgraph_nodes; node != first_analyzed; node = node->next) 1157 if (node->needed && DECL_SAVED_TREE (node->decl)) 1158 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node)); 1159 fprintf (cgraph_dump_file, "\n\nInitial "); 1160 dump_cgraph (cgraph_dump_file); 1161 } 1162 1163 if (cgraph_dump_file) 1164 fprintf (cgraph_dump_file, "\nReclaiming functions:"); 1165 1166 for (node = cgraph_nodes; node != first_analyzed; node = next) 1167 { 1168 tree decl = node->decl; 1169 next = node->next; 1170 1171 if (node->local.finalized && !DECL_SAVED_TREE (decl)) 1172 cgraph_reset_node (node); 1173 1174 if (!node->reachable && DECL_SAVED_TREE (decl)) 1175 { 1176 if (cgraph_dump_file) 1177 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node)); 1178 cgraph_remove_node (node); 1179 continue; 1180 } 1181 else 1182 node->next_needed = NULL; 1183 gcc_assert (!node->local.finalized || DECL_SAVED_TREE (decl)); 1184 gcc_assert (node->analyzed == node->local.finalized); 1185 } 1186 if (cgraph_dump_file) 1187 { 1188 fprintf (cgraph_dump_file, "\n\nReclaimed "); 1189 dump_cgraph (cgraph_dump_file); 1190 } 1191 first_analyzed = cgraph_nodes; 1192 ggc_collect (); 1193 timevar_pop (TV_CGRAPH); 1194} 1195/* Figure out what functions we want to assemble. */ 1196 1197static void 1198cgraph_mark_functions_to_output (void) 1199{ 1200 struct cgraph_node *node; 1201 1202 for (node = cgraph_nodes; node; node = node->next) 1203 { 1204 tree decl = node->decl; 1205 struct cgraph_edge *e; 1206 1207 gcc_assert (!node->output); 1208 1209 for (e = node->callers; e; e = e->next_caller) 1210 if (e->inline_failed) 1211 break; 1212 1213 /* We need to output all local functions that are used and not 1214 always inlined, as well as those that are reachable from 1215 outside the current compilation unit. */ 1216 if (DECL_SAVED_TREE (decl) 1217 && !node->global.inlined_to 1218 && (node->needed 1219 || (e && node->reachable)) 1220 && !TREE_ASM_WRITTEN (decl) 1221 && !DECL_EXTERNAL (decl)) 1222 node->output = 1; 1223 else 1224 { 1225 /* We should've reclaimed all functions that are not needed. */ 1226#ifdef ENABLE_CHECKING 1227 if (!node->global.inlined_to && DECL_SAVED_TREE (decl) 1228 && !DECL_EXTERNAL (decl)) 1229 { 1230 dump_cgraph_node (stderr, node); 1231 internal_error ("failed to reclaim unneeded function"); 1232 } 1233#endif 1234 gcc_assert (node->global.inlined_to || !DECL_SAVED_TREE (decl) 1235 || DECL_EXTERNAL (decl)); 1236 1237 } 1238 1239 } 1240} 1241 1242/* Expand function specified by NODE. */ 1243 1244static void 1245cgraph_expand_function (struct cgraph_node *node) 1246{ 1247 tree decl = node->decl; 1248 1249 /* We ought to not compile any inline clones. */ 1250 gcc_assert (!node->global.inlined_to); 1251 1252 if (flag_unit_at_a_time) 1253 announce_function (decl); 1254 1255 cgraph_lower_function (node); 1256 1257 /* Generate RTL for the body of DECL. */ 1258 lang_hooks.callgraph.expand_function (decl); 1259 1260 /* Make sure that BE didn't give up on compiling. */ 1261 /* ??? Can happen with nested function of extern inline. */ 1262 gcc_assert (TREE_ASM_WRITTEN (node->decl)); 1263 1264 current_function_decl = NULL; 1265 if (!cgraph_preserve_function_body_p (node->decl)) 1266 { 1267 DECL_SAVED_TREE (node->decl) = NULL; 1268 DECL_STRUCT_FUNCTION (node->decl) = NULL; 1269 DECL_INITIAL (node->decl) = error_mark_node; 1270 /* Eliminate all call edges. This is important so the call_expr no longer 1271 points to the dead function body. */ 1272 cgraph_node_remove_callees (node); 1273 } 1274 1275 cgraph_function_flags_ready = true; 1276} 1277 1278/* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */ 1279 1280bool 1281cgraph_inline_p (struct cgraph_edge *e, const char **reason) 1282{ 1283 *reason = e->inline_failed; 1284 return !e->inline_failed; 1285} 1286 1287 1288 1289/* Expand all functions that must be output. 1290 1291 Attempt to topologically sort the nodes so function is output when 1292 all called functions are already assembled to allow data to be 1293 propagated across the callgraph. Use a stack to get smaller distance 1294 between a function and its callees (later we may choose to use a more 1295 sophisticated algorithm for function reordering; we will likely want 1296 to use subsections to make the output functions appear in top-down 1297 order). */ 1298 1299static void 1300cgraph_expand_all_functions (void) 1301{ 1302 struct cgraph_node *node; 1303 struct cgraph_node **order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); 1304 int order_pos = 0, new_order_pos = 0; 1305 int i; 1306 1307 order_pos = cgraph_postorder (order); 1308 gcc_assert (order_pos == cgraph_n_nodes); 1309 1310 /* Garbage collector may remove inline clones we eliminate during 1311 optimization. So we must be sure to not reference them. */ 1312 for (i = 0; i < order_pos; i++) 1313 if (order[i]->output) 1314 order[new_order_pos++] = order[i]; 1315 1316 for (i = new_order_pos - 1; i >= 0; i--) 1317 { 1318 node = order[i]; 1319 if (node->output) 1320 { 1321 gcc_assert (node->reachable); 1322 node->output = 0; 1323 cgraph_expand_function (node); 1324 } 1325 } 1326 1327 free (order); 1328 1329 /* Process CGRAPH_EXPAND_QUEUE, these are functions created during 1330 the expansion process. Note that this queue may grow as its 1331 being processed, as the new functions may generate new ones. */ 1332 while (cgraph_expand_queue) 1333 { 1334 node = cgraph_expand_queue; 1335 cgraph_expand_queue = cgraph_expand_queue->next_needed; 1336 node->next_needed = NULL; 1337 node->output = 0; 1338 node->lowered = DECL_STRUCT_FUNCTION (node->decl)->cfg != NULL; 1339 cgraph_expand_function (node); 1340 } 1341} 1342 1343/* This is used to sort the node types by the cgraph order number. */ 1344 1345struct cgraph_order_sort 1346{ 1347 enum { ORDER_UNDEFINED = 0, ORDER_FUNCTION, ORDER_VAR, ORDER_ASM } kind; 1348 union 1349 { 1350 struct cgraph_node *f; 1351 struct cgraph_varpool_node *v; 1352 struct cgraph_asm_node *a; 1353 } u; 1354}; 1355 1356/* Output all functions, variables, and asm statements in the order 1357 according to their order fields, which is the order in which they 1358 appeared in the file. This implements -fno-toplevel-reorder. In 1359 this mode we may output functions and variables which don't really 1360 need to be output. */ 1361 1362static void 1363cgraph_output_in_order (void) 1364{ 1365 int max; 1366 size_t size; 1367 struct cgraph_order_sort *nodes; 1368 int i; 1369 struct cgraph_node *pf; 1370 struct cgraph_varpool_node *pv; 1371 struct cgraph_asm_node *pa; 1372 1373 max = cgraph_order; 1374 size = max * sizeof (struct cgraph_order_sort); 1375 nodes = (struct cgraph_order_sort *) alloca (size); 1376 memset (nodes, 0, size); 1377 1378 cgraph_varpool_analyze_pending_decls (); 1379 1380 for (pf = cgraph_nodes; pf; pf = pf->next) 1381 { 1382 if (pf->output) 1383 { 1384 i = pf->order; 1385 gcc_assert (nodes[i].kind == ORDER_UNDEFINED); 1386 nodes[i].kind = ORDER_FUNCTION; 1387 nodes[i].u.f = pf; 1388 } 1389 } 1390 1391 for (pv = cgraph_varpool_nodes_queue; pv; pv = pv->next_needed) 1392 { 1393 i = pv->order; 1394 gcc_assert (nodes[i].kind == ORDER_UNDEFINED); 1395 nodes[i].kind = ORDER_VAR; 1396 nodes[i].u.v = pv; 1397 } 1398 1399 for (pa = cgraph_asm_nodes; pa; pa = pa->next) 1400 { 1401 i = pa->order; 1402 gcc_assert (nodes[i].kind == ORDER_UNDEFINED); 1403 nodes[i].kind = ORDER_ASM; 1404 nodes[i].u.a = pa; 1405 } 1406 1407 for (i = 0; i < max; ++i) 1408 { 1409 switch (nodes[i].kind) 1410 { 1411 case ORDER_FUNCTION: 1412 nodes[i].u.f->output = 0; 1413 cgraph_expand_function (nodes[i].u.f); 1414 break; 1415 1416 case ORDER_VAR: 1417 cgraph_varpool_assemble_decl (nodes[i].u.v); 1418 break; 1419 1420 case ORDER_ASM: 1421 assemble_asm (nodes[i].u.a->asm_str); 1422 break; 1423 1424 case ORDER_UNDEFINED: 1425 break; 1426 1427 default: 1428 gcc_unreachable (); 1429 } 1430 } 1431 1432 cgraph_asm_nodes = NULL; 1433} 1434 1435/* Mark visibility of all functions. 1436 1437 A local function is one whose calls can occur only in the current 1438 compilation unit and all its calls are explicit, so we can change 1439 its calling convention. We simply mark all static functions whose 1440 address is not taken as local. 1441 1442 We also change the TREE_PUBLIC flag of all declarations that are public 1443 in language point of view but we want to overwrite this default 1444 via visibilities for the backend point of view. */ 1445 1446static void 1447cgraph_function_and_variable_visibility (void) 1448{ 1449 struct cgraph_node *node; 1450 struct cgraph_varpool_node *vnode; 1451 1452 for (node = cgraph_nodes; node; node = node->next) 1453 { 1454 if (node->reachable 1455 && (DECL_COMDAT (node->decl) 1456 || (!flag_whole_program 1457 && TREE_PUBLIC (node->decl) && !DECL_EXTERNAL (node->decl)))) 1458 node->local.externally_visible = true; 1459 if (!node->local.externally_visible && node->analyzed 1460 && !DECL_EXTERNAL (node->decl)) 1461 { 1462 gcc_assert (flag_whole_program || !TREE_PUBLIC (node->decl)); 1463 TREE_PUBLIC (node->decl) = 0; 1464 } 1465 node->local.local = (!node->needed 1466 && node->analyzed 1467 && !DECL_EXTERNAL (node->decl) 1468 && !node->local.externally_visible); 1469 } 1470 for (vnode = cgraph_varpool_nodes_queue; vnode; vnode = vnode->next_needed) 1471 { 1472 if (vnode->needed 1473 && !flag_whole_program 1474 && (DECL_COMDAT (vnode->decl) || TREE_PUBLIC (vnode->decl))) 1475 vnode->externally_visible = 1; 1476 if (!vnode->externally_visible) 1477 { 1478 gcc_assert (flag_whole_program || !TREE_PUBLIC (vnode->decl)); 1479 TREE_PUBLIC (vnode->decl) = 0; 1480 } 1481 gcc_assert (TREE_STATIC (vnode->decl)); 1482 } 1483 1484 /* Because we have to be conservative on the boundaries of source 1485 level units, it is possible that we marked some functions in 1486 reachable just because they might be used later via external 1487 linkage, but after making them local they are really unreachable 1488 now. */ 1489 cgraph_remove_unreachable_nodes (true, cgraph_dump_file); 1490 1491 if (cgraph_dump_file) 1492 { 1493 fprintf (cgraph_dump_file, "\nMarking local functions:"); 1494 for (node = cgraph_nodes; node; node = node->next) 1495 if (node->local.local) 1496 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node)); 1497 fprintf (cgraph_dump_file, "\n\n"); 1498 fprintf (cgraph_dump_file, "\nMarking externally visible functions:"); 1499 for (node = cgraph_nodes; node; node = node->next) 1500 if (node->local.externally_visible) 1501 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node)); 1502 fprintf (cgraph_dump_file, "\n\n"); 1503 } 1504 cgraph_function_flags_ready = true; 1505} 1506 1507/* Return true when function body of DECL still needs to be kept around 1508 for later re-use. */ 1509bool 1510cgraph_preserve_function_body_p (tree decl) 1511{ 1512 struct cgraph_node *node; 1513 if (!cgraph_global_info_ready) 1514 return (flag_really_no_inline 1515 ? lang_hooks.tree_inlining.disregard_inline_limits (decl) 1516 : DECL_INLINE (decl)); 1517 /* Look if there is any clone around. */ 1518 for (node = cgraph_node (decl); node; node = node->next_clone) 1519 if (node->global.inlined_to) 1520 return true; 1521 return false; 1522} 1523 1524static void 1525ipa_passes (void) 1526{ 1527 cfun = NULL; 1528 tree_register_cfg_hooks (); 1529 bitmap_obstack_initialize (NULL); 1530 execute_ipa_pass_list (all_ipa_passes); 1531 bitmap_obstack_release (NULL); 1532} 1533 1534/* Perform simple optimizations based on callgraph. */ 1535 1536void 1537cgraph_optimize (void) 1538{ 1539 if (errorcount || sorrycount) 1540 return; 1541 1542#ifdef ENABLE_CHECKING 1543 verify_cgraph (); 1544#endif 1545 if (!flag_unit_at_a_time) 1546 { 1547 cgraph_output_pending_asms (); 1548 cgraph_varpool_assemble_pending_decls (); 1549 cgraph_varpool_output_debug_info (); 1550 return; 1551 } 1552 1553 /* Frontend may output common variables after the unit has been finalized. 1554 It is safe to deal with them here as they are always zero initialized. */ 1555 cgraph_varpool_analyze_pending_decls (); 1556 1557 timevar_push (TV_CGRAPHOPT); 1558 if (!quiet_flag) 1559 fprintf (stderr, "Performing interprocedural optimizations\n"); 1560 1561 cgraph_function_and_variable_visibility (); 1562 if (cgraph_dump_file) 1563 { 1564 fprintf (cgraph_dump_file, "Marked "); 1565 dump_cgraph (cgraph_dump_file); 1566 } 1567 1568 /* Don't run the IPA passes if there was any error or sorry messages. */ 1569 if (errorcount == 0 && sorrycount == 0) 1570 ipa_passes (); 1571 1572 /* This pass remove bodies of extern inline functions we never inlined. 1573 Do this later so other IPA passes see what is really going on. */ 1574 cgraph_remove_unreachable_nodes (false, dump_file); 1575 cgraph_increase_alignment (); 1576 cgraph_global_info_ready = true; 1577 if (cgraph_dump_file) 1578 { 1579 fprintf (cgraph_dump_file, "Optimized "); 1580 dump_cgraph (cgraph_dump_file); 1581 dump_varpool (cgraph_dump_file); 1582 } 1583 timevar_pop (TV_CGRAPHOPT); 1584 1585 /* Output everything. */ 1586 if (!quiet_flag) 1587 fprintf (stderr, "Assembling functions:\n"); 1588#ifdef ENABLE_CHECKING 1589 verify_cgraph (); 1590#endif 1591 1592 cgraph_mark_functions_to_output (); 1593 1594 if (!flag_toplevel_reorder) 1595 cgraph_output_in_order (); 1596 else 1597 { 1598 cgraph_output_pending_asms (); 1599 1600 cgraph_expand_all_functions (); 1601 cgraph_varpool_remove_unreferenced_decls (); 1602 1603 cgraph_varpool_assemble_pending_decls (); 1604 cgraph_varpool_output_debug_info (); 1605 } 1606 1607 if (cgraph_dump_file) 1608 { 1609 fprintf (cgraph_dump_file, "\nFinal "); 1610 dump_cgraph (cgraph_dump_file); 1611 } 1612#ifdef ENABLE_CHECKING 1613 verify_cgraph (); 1614 /* Double check that all inline clones are gone and that all 1615 function bodies have been released from memory. */ 1616 if (flag_unit_at_a_time 1617 && !(sorrycount || errorcount)) 1618 { 1619 struct cgraph_node *node; 1620 bool error_found = false; 1621 1622 for (node = cgraph_nodes; node; node = node->next) 1623 if (node->analyzed 1624 && (node->global.inlined_to 1625 || DECL_SAVED_TREE (node->decl))) 1626 { 1627 error_found = true; 1628 dump_cgraph_node (stderr, node); 1629 } 1630 if (error_found) 1631 internal_error ("nodes with no released memory found"); 1632 } 1633#endif 1634} 1635 1636/* Increase alignment of global arrays to improve vectorization potential. 1637 TODO: 1638 - Consider also structs that have an array field. 1639 - Use ipa analysis to prune arrays that can't be vectorized? 1640 This should involve global alignment analysis and in the future also 1641 array padding. */ 1642 1643static void 1644cgraph_increase_alignment (void) 1645{ 1646 if (flag_section_anchors && flag_tree_vectorize) 1647 { 1648 struct cgraph_varpool_node *vnode; 1649 1650 /* Increase the alignment of all global arrays for vectorization. */ 1651 for (vnode = cgraph_varpool_nodes_queue; 1652 vnode; 1653 vnode = vnode->next_needed) 1654 { 1655 tree vectype, decl = vnode->decl; 1656 unsigned int alignment; 1657 1658 if (TREE_CODE (TREE_TYPE (decl)) != ARRAY_TYPE) 1659 continue; 1660 vectype = get_vectype_for_scalar_type (TREE_TYPE (TREE_TYPE (decl))); 1661 if (!vectype) 1662 continue; 1663 alignment = TYPE_ALIGN (vectype); 1664 if (DECL_ALIGN (decl) >= alignment) 1665 continue; 1666 1667 if (vect_can_force_dr_alignment_p (decl, alignment)) 1668 { 1669 DECL_ALIGN (decl) = TYPE_ALIGN (vectype); 1670 DECL_USER_ALIGN (decl) = 1; 1671 if (cgraph_dump_file) 1672 { 1673 fprintf (cgraph_dump_file, "Increasing alignment of decl: "); 1674 print_generic_expr (cgraph_dump_file, decl, TDF_SLIM); 1675 } 1676 } 1677 } 1678 } 1679} 1680 1681/* Generate and emit a static constructor or destructor. WHICH must be 1682 one of 'I' or 'D'. BODY should be a STATEMENT_LIST containing 1683 GENERIC statements. */ 1684 1685void 1686cgraph_build_static_cdtor (char which, tree body, int priority) 1687{ 1688 static int counter = 0; 1689 char which_buf[16]; 1690 tree decl, name, resdecl; 1691 1692 sprintf (which_buf, "%c_%d", which, counter++); 1693 name = get_file_function_name (which_buf); 1694 1695 decl = build_decl (FUNCTION_DECL, name, 1696 build_function_type (void_type_node, void_list_node)); 1697 current_function_decl = decl; 1698 1699 resdecl = build_decl (RESULT_DECL, NULL_TREE, void_type_node); 1700 DECL_ARTIFICIAL (resdecl) = 1; 1701 DECL_IGNORED_P (resdecl) = 1; 1702 DECL_RESULT (decl) = resdecl; 1703 1704 allocate_struct_function (decl); 1705 1706 TREE_STATIC (decl) = 1; 1707 TREE_USED (decl) = 1; 1708 DECL_ARTIFICIAL (decl) = 1; 1709 DECL_IGNORED_P (decl) = 1; 1710 DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl) = 1; 1711 DECL_SAVED_TREE (decl) = body; 1712 TREE_PUBLIC (decl) = ! targetm.have_ctors_dtors; 1713 DECL_UNINLINABLE (decl) = 1; 1714 1715 DECL_INITIAL (decl) = make_node (BLOCK); 1716 TREE_USED (DECL_INITIAL (decl)) = 1; 1717 1718 DECL_SOURCE_LOCATION (decl) = input_location; 1719 cfun->function_end_locus = input_location; 1720 1721 switch (which) 1722 { 1723 case 'I': 1724 DECL_STATIC_CONSTRUCTOR (decl) = 1; 1725 break; 1726 case 'D': 1727 DECL_STATIC_DESTRUCTOR (decl) = 1; 1728 break; 1729 default: 1730 gcc_unreachable (); 1731 } 1732 1733 gimplify_function_tree (decl); 1734 1735 /* ??? We will get called LATE in the compilation process. */ 1736 if (cgraph_global_info_ready) 1737 { 1738 tree_lowering_passes (decl); 1739 tree_rest_of_compilation (decl); 1740 } 1741 else 1742 cgraph_finalize_function (decl, 0); 1743 1744 if (targetm.have_ctors_dtors) 1745 { 1746 void (*fn) (rtx, int); 1747 1748 if (which == 'I') 1749 fn = targetm.asm_out.constructor; 1750 else 1751 fn = targetm.asm_out.destructor; 1752 fn (XEXP (DECL_RTL (decl), 0), priority); 1753 } 1754} 1755 1756void 1757init_cgraph (void) 1758{ 1759 cgraph_dump_file = dump_begin (TDI_cgraph, NULL); 1760} 1761 1762/* The edges representing the callers of the NEW_VERSION node were 1763 fixed by cgraph_function_versioning (), now the call_expr in their 1764 respective tree code should be updated to call the NEW_VERSION. */ 1765 1766static void 1767update_call_expr (struct cgraph_node *new_version) 1768{ 1769 struct cgraph_edge *e; 1770 1771 gcc_assert (new_version); 1772 for (e = new_version->callers; e; e = e->next_caller) 1773 /* Update the call expr on the edges 1774 to call the new version. */ 1775 TREE_OPERAND (TREE_OPERAND (get_call_expr_in (e->call_stmt), 0), 0) = new_version->decl; 1776} 1777 1778 1779/* Create a new cgraph node which is the new version of 1780 OLD_VERSION node. REDIRECT_CALLERS holds the callers 1781 edges which should be redirected to point to 1782 NEW_VERSION. ALL the callees edges of OLD_VERSION 1783 are cloned to the new version node. Return the new 1784 version node. */ 1785 1786static struct cgraph_node * 1787cgraph_copy_node_for_versioning (struct cgraph_node *old_version, 1788 tree new_decl, 1789 VEC(cgraph_edge_p,heap) *redirect_callers) 1790 { 1791 struct cgraph_node *new_version; 1792 struct cgraph_edge *e, *new_e; 1793 struct cgraph_edge *next_callee; 1794 unsigned i; 1795 1796 gcc_assert (old_version); 1797 1798 new_version = cgraph_node (new_decl); 1799 1800 new_version->analyzed = true; 1801 new_version->local = old_version->local; 1802 new_version->global = old_version->global; 1803 new_version->rtl = new_version->rtl; 1804 new_version->reachable = true; 1805 new_version->count = old_version->count; 1806 1807 /* Clone the old node callees. Recursive calls are 1808 also cloned. */ 1809 for (e = old_version->callees;e; e=e->next_callee) 1810 { 1811 new_e = cgraph_clone_edge (e, new_version, e->call_stmt, 0, e->loop_nest, true); 1812 new_e->count = e->count; 1813 } 1814 /* Fix recursive calls. 1815 If OLD_VERSION has a recursive call after the 1816 previous edge cloning, the new version will have an edge 1817 pointing to the old version, which is wrong; 1818 Redirect it to point to the new version. */ 1819 for (e = new_version->callees ; e; e = next_callee) 1820 { 1821 next_callee = e->next_callee; 1822 if (e->callee == old_version) 1823 cgraph_redirect_edge_callee (e, new_version); 1824 1825 if (!next_callee) 1826 break; 1827 } 1828 for (i = 0; VEC_iterate (cgraph_edge_p, redirect_callers, i, e); i++) 1829 { 1830 /* Redirect calls to the old version node to point to its new 1831 version. */ 1832 cgraph_redirect_edge_callee (e, new_version); 1833 } 1834 1835 return new_version; 1836 } 1837 1838 /* Perform function versioning. 1839 Function versioning includes copying of the tree and 1840 a callgraph update (creating a new cgraph node and updating 1841 its callees and callers). 1842 1843 REDIRECT_CALLERS varray includes the edges to be redirected 1844 to the new version. 1845 1846 TREE_MAP is a mapping of tree nodes we want to replace with 1847 new ones (according to results of prior analysis). 1848 OLD_VERSION_NODE is the node that is versioned. 1849 It returns the new version's cgraph node. */ 1850 1851struct cgraph_node * 1852cgraph_function_versioning (struct cgraph_node *old_version_node, 1853 VEC(cgraph_edge_p,heap) *redirect_callers, 1854 varray_type tree_map) 1855{ 1856 tree old_decl = old_version_node->decl; 1857 struct cgraph_node *new_version_node = NULL; 1858 tree new_decl; 1859 1860 if (!tree_versionable_function_p (old_decl)) 1861 return NULL; 1862 1863 /* Make a new FUNCTION_DECL tree node for the 1864 new version. */ 1865 new_decl = copy_node (old_decl); 1866 1867 /* Create the new version's call-graph node. 1868 and update the edges of the new node. */ 1869 new_version_node = 1870 cgraph_copy_node_for_versioning (old_version_node, new_decl, 1871 redirect_callers); 1872 1873 /* Copy the OLD_VERSION_NODE function tree to the new version. */ 1874 tree_function_versioning (old_decl, new_decl, tree_map, false); 1875 /* Update the call_expr on the edges to call the new version node. */ 1876 update_call_expr (new_version_node); 1877 1878 /* Update the new version's properties. 1879 Make The new version visible only within this translation unit. 1880 ??? We cannot use COMDAT linkage because there is no 1881 ABI support for this. */ 1882 DECL_EXTERNAL (new_version_node->decl) = 0; 1883 DECL_ONE_ONLY (new_version_node->decl) = 0; 1884 TREE_PUBLIC (new_version_node->decl) = 0; 1885 DECL_COMDAT (new_version_node->decl) = 0; 1886 new_version_node->local.externally_visible = 0; 1887 new_version_node->local.local = 1; 1888 new_version_node->lowered = true; 1889 return new_version_node; 1890} 1891 1892/* Produce separate function body for inline clones so the offline copy can be 1893 modified without affecting them. */ 1894struct cgraph_node * 1895save_inline_function_body (struct cgraph_node *node) 1896{ 1897 struct cgraph_node *first_clone; 1898 1899 gcc_assert (node == cgraph_node (node->decl)); 1900 1901 cgraph_lower_function (node); 1902 1903 /* In non-unit-at-a-time we construct full fledged clone we never output to 1904 assembly file. This clone is pointed out by inline_decl of original function 1905 and inlining infrastructure knows how to deal with this. */ 1906 if (!flag_unit_at_a_time) 1907 { 1908 struct cgraph_edge *e; 1909 1910 first_clone = cgraph_clone_node (node, node->count, 0, false); 1911 first_clone->needed = 0; 1912 first_clone->reachable = 1; 1913 /* Recursively clone all bodies. */ 1914 for (e = first_clone->callees; e; e = e->next_callee) 1915 if (!e->inline_failed) 1916 cgraph_clone_inlined_nodes (e, true, false); 1917 } 1918 else 1919 first_clone = node->next_clone; 1920 1921 first_clone->decl = copy_node (node->decl); 1922 node->next_clone = NULL; 1923 if (!flag_unit_at_a_time) 1924 node->inline_decl = first_clone->decl; 1925 first_clone->prev_clone = NULL; 1926 cgraph_insert_node_to_hashtable (first_clone); 1927 gcc_assert (first_clone == cgraph_node (first_clone->decl)); 1928 1929 /* Copy the OLD_VERSION_NODE function tree to the new version. */ 1930 tree_function_versioning (node->decl, first_clone->decl, NULL, true); 1931 1932 DECL_EXTERNAL (first_clone->decl) = 0; 1933 DECL_ONE_ONLY (first_clone->decl) = 0; 1934 TREE_PUBLIC (first_clone->decl) = 0; 1935 DECL_COMDAT (first_clone->decl) = 0; 1936 1937 for (node = first_clone->next_clone; node; node = node->next_clone) 1938 node->decl = first_clone->decl; 1939#ifdef ENABLE_CHECKING 1940 verify_cgraph_node (first_clone); 1941#endif 1942 return first_clone; 1943} 1944 1945#include "gt-cgraphunit.h" 1946